Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
I analyse the frequentist regret of the famous Gittins index strategy for multi-armed bandits with Gaussian noise and a finite horizon. Remarkably it turns out that this approach leads to finite-time regret guarantees comparable to those available for the popular UCB algorithm. Along the way I derive finite-time bounds on the Gittins index that are asymptotically exact and may be of independent interest. I also discuss some computational issues and present experimental results suggesting that a particular version of the Gittins index strategy is a modest improvement on existing algorithms with finite-time regret guarantees such as UCB and Thompson sampling.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsThompson SamplingSimilar Papers 제목 키워드 기반
Optimistic Gittins Indices
Starting with the Thomspon sampling algorithm, recent years have seen a resurgence of interest in Bayesian algorithms for the Multi-armed Bandit (MAB) problem. These algorithms seek to exploit prior information on arm bi…
On Bayesian index policies for sequential resource allocation
This paper is about index policies for minimizing (frequentist) regret in a stochastic multi-armed bandit model, inspired by a Bayesian view on the problem. Our main contribution is to prove that the Bayes-UCB algorithm,…
The Gittins Index: A Design Principle for Decision-Making Under Uncertainty
The Gittins index is a tool that optimally solves a variety of decision-making problems involving uncertainty, including multi-armed bandit problems, minimizing mean latency in queues, and search problems like the Pandor…
Bayesian OptimizationDecision MakingDecision Making Under UncertaintyCost-aware Bayesian Optimization via the Pandora's Box Gittins Index
Bayesian optimization is a technique for efficiently optimizing unknown functions in a black-box manner. To handle practical settings where gathering data requires use of finite resources, it is desirable to explicitly i…
Bayesian OptimizationThompson Sampling with Information Relaxation Penalties
We consider a finite-horizon multi-armed bandit (MAB) problem in a Bayesian setting, for which we propose an information relaxation sampling framework. With this framework, we define an intuitive family of control polici…
Thompson Sampling