2020/06/05 by Hédi Hadiji, Hadiji, Hédi, Gilles Stoltz +1 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Search Problems #Reinforcement Learning in Robotics #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2006.03378
openalex publication_date 2020/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider stochastic bandit problems with K arms, each associated with a bounded distribution supported on the range [m,M]. We do not assume that the range [m,M] is known and show that there is a cost for learning this range. Indeed, a new trade-off between distribution-dependent and distribution-free regret bounds arises, which prevents from simultaneously achieving the typical ln T and √(T) bounds. For instance, a √(T)distribution-free regret bound may only be achieved if the distribution-dependent regret bounds are at least of order √(T). We exhibit a strategy achieving the rates for regret indicated by the new trade-off.