Research map / Bandits and online learning / Online convex optimization and games
Replicable Constrained Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Designs replicable UCB-style algorithms (DEBORA, DEBORA-S, DEBORA-H) for stochastic unconstrained and constrained multi-armed bandits with soft and hard constraints, matching non-replicable regret rates in T.
Problem
Replicable online learning in stochastic multi-armed bandits with multiple cost constraints (soft and hard), where existing replicable bandit algorithms rely on arm elimination that does not extend to constrained settings.
Approach
A dynamic epoch-based UCB-style algorithm (epoch ends when the played action doubles its count) using replicable mean estimators (RepMean) with confidence widths, avoiding arm elimination; constrained variants optimize over an optimistic safe polytope and, for hard constraints, mix with a known strictly safe strategy.
Key results
- DEBORA achieves unconstrained regret O~(K^{3/2} sqrt(T)/(rho-delta)) with high probability, matching the worst-case rate of prior replicable bandit results.
- DEBORA-S attains both regret and cumulative positive violation of O~(sqrt(T)) in the soft-constraint setting, matching non-replicable rates up to a factor m.
- DEBORA-H is safe at every round with high probability and achieves O~(sqrt(T)) regret under Slater's condition, with an additive T-independent term and 1/lambda_min dependence.
Limitations
- Replicability costs a 1/rho factor in regret and the bounds carry a K^2 or m K^2 multiplicative overhead.
- Hard-constraint setting requires knowledge of a strictly safe strategy and Slater's condition, with 1/lambda_min dependence.
Experimental setup
Metrics: regret constraint violation
Baselines: replicable bandit algorithm (arm elimination) RSE non-replicable constrained bandit algorithms
Builds on: RepMean replicable mean estimator UCB1 replicable bandits arm elimination Slater-condition constrained bandits
Closest papers by meaning
- Replicable Online Learning (NeurIPS 2025 · similarity 0.89)
- Replication-proof Bandit Mechanism Design with Bayesian Agents (AAAI 2025 · similarity 0.87)
- Data-Dependent Regret Bounds for Constrained MABs (NeurIPS 2025 · similarity 0.87)
- On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.86)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.86)
- Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.