Bounded Regret for Finite-Armed Structured Bandits

Abstract

We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of problems and show that under certain circumstances it is possible to achieve finite expected cumulative regret. We also give problem-dependent lower bounds on the cumulative regret showing that at least in special cases the new algorithm is nearly optimal.

arXiv comment16 pages

References in corpus (3)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Further Optimal Regret Bounds for Thompson Sampling
• Thompson Sampling for 1-Dimensional Exponential Family Bandits

Cited by in corpus (8)

• Latent Bandits Revisited
• Regime Switching Bandits
• Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits
• A Novel Confidence-Based Algorithm for Structured Bandits
• Diversity-Preserving K-Armed Bandits, Revisited
• Lexicographic Multiarmed Bandit