Stochastic Multi-armed Bandits in Constant Space

2017/12/25 by David Liau, Eric Price, Liau, David +5
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1712.09007

openalex publication_date 2017/12/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the stochastic bandit problem in the sublinear space setting, where one cannot record the win-loss record for all K arms. We give an algorithm using O(1) words of space with regret ∑_i=1^K(1)/(Δ_i)log \fracΔ_iΔlog T where Δ_i is the gap between the best arm and arm i and Δ is the gap between the best and the second-best arms. If the rewards are bounded away from 0 and 1, this is within an O(log 1/Δ) factor of the optimum regret possible without space constraints.

Related

• Sparse Stochastic Bandits
• Bounded regret in stochastic multi-armed bandits
• Continuum armed bandit problem of few variables in high dimensions
• Simple regret for infinitely many armed bandits
• Parametrized Stochastic Multi-armed Bandits with Binary Rewards