Bounded regret in stochastic multi-armed bandits

Abstract

We study the stochastic multi-armed bandit problem when one knows the value ${\mu }^{(\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 ${\mu }^{(\star )}$

References in corpus (1)

• Nonparametric Bandits with Covariates

Cited by in corpus (15)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Batched bandit problems
• Risk-Averse Multi-Armed Bandit Problems under Mean-Variance Measure
• Refined Lower Bounds for Adversarial Bandits
• Batched Multi-armed Bandits Problem
• Online Allocation and Pricing: Constant Regret via Bellman Inequalities
• Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
• Combining Offline Causal Inference and Online Bandit Learning for Data Driven Decision
• Dynamic Pricing with Finitely Many Unknown Valuations
• Non-asymptotic confidence bounds for the optimal value of a stochastic program
• Decision Variance in Online Learning
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits
• Regional Multi-Armed Bandits
• Regret in Online Recommendation Systems
• Lexicographic Multiarmed Bandit