Bounded regret in stochastic multi-armed bandits
Not on the map. Why?
Abstract (arXiv)
We study the stochastic multi-armed bandit problem when one knows the value μ(star) of an optimal arm, as a well as a positive lower bound on the smallest positive gap Delta. We propose a new randomized policy that attains a regret em uniformly bounded over time in this setting. We also prove several lower bounds, which show in particular that bounded regret is not possible if one only knows Delta, and bounded regret of order 1/Delta is not possible if one only knows μ(star)
Key facts. Cited by 10 papers in the map (data through 13 Oct 2026). First posted on arXiv 6 Feb 2013.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 4; 2023: 2; 2024: 0; 2025: 1; 2026: 1.
10 papers.
- 2021Model Selection in Batch Policy Optimizationcited by 11
- 2021Risk and optimal policies in bandit experimentscited by 7
- 2022Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Boundscited by 5
- 2022A Joint Imitation-Reinforcement Learning Framework for Reduced Baseline Regretcited by 3
- 2023Communication-Efficient Collaborative Regret Minimization in Multi-Armed Banditscited by 3
- 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
- 2022Anonymous Bandits for Multi-User Systemscited by 1
- 2025Balancing Performance and Costs in Best Arm Identificationcited by 1
- 2026Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Valuescited by 1
- 2023(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Banditscited by 0
- 2026Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values1 Mar 2026
- 2025Balancing Performance and Costs in Best Arm Identification26 May 2025
- 2023(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits4 Oct 2023
- 2023Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits26 Jan 2023
- 2022Anonymous Bandits for Multi-User Systems21 Oct 2022
- 2022A Joint Imitation-Reinforcement Learning Framework for Reduced Baseline Regret20 Sep 2022
- 2022Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds6 Jun 2022
- 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs18 May 2022
- 2021Model Selection in Batch Policy Optimization23 Dec 2021
- 2021Risk and optimal policies in bandit experiments13 Dec 2021