Timezone: »

 
Poster
Optimistic Gittins Indices
Eli Gutin · Vivek Farias

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #157
in Tuesday Posters »

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 biases and while several have been shown to be regret optimal, their design has not emerged from a principled approach. In contrast, if one cared about Bayesian regret discounted over an infinite horizon at a fixed, pre-specified rate, the celebrated Gittins index theorem offers an optimal algorithm. Unfortunately, the Gittins analysis does not appear to carry over to minimizing Bayesian regret over all sufficiently large horizons and computing a Gittins index is onerous relative to essentially any incumbent index scheme for the Bayesian MAB problem. The present paper proposes a sequence of 'optimistic' approximations to the Gittins index. We show that the use of these approximations in concert with the use of an increasing discount factor appears to offer a compelling alternative to a variety of index schemes proposed for the Bayesian MAB problem in recent years. In addition, we show that the simplest of these approximations yields regret that matches the Lai-Robbins lower bound, including achieving matching constants.

Keywords: (Other) Optimization · Reinforcement Learning Algorithms
[ PDF] 

Author Information

Eli Gutin (Massachusetts Institute of Tec)
Vivek Farias (Massachusetts Institute of Technology)

More from the Same Authors