# Bounded regret in stochastic multi-armed bandits

arXiv: https://arxiv.org/abs/1302.1611 · HTML: https://mlsanity.com/paper/1302.1611/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2013.

## Built on by (most cited first, 10 of 10)

- [Model Selection in Batch Policy Optimization](https://mlsanity.com/paper/2112.12320/) (2021)
- [Risk and optimal policies in bandit experiments](https://mlsanity.com/paper/2112.06363/) (2021)
- [Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2206.02834/) (2022)
- [A Joint Imitation-Reinforcement Learning Framework for Reduced Baseline Regret](https://mlsanity.com/paper/2209.09446/) (2022)
- [Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits](https://mlsanity.com/paper/2301.11442/) (2023)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values](https://mlsanity.com/paper/2603.00945/) (2026)
- [Anonymous Bandits for Multi-User Systems](https://mlsanity.com/paper/2210.12198/) (2022)
- [Balancing Performance and Costs in Best Arm Identification](https://mlsanity.com/paper/2505.20583/) (2025)
- [(ε, u)-Adaptive Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2310.02975/) (2023)

## 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)