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 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 state-of-the-art index schemes proposed for the Bayesian MAB problem in recent years by offering substantially improved performance with little to no additional computational overhead. In addition, we prove that the simplest of these approximations yields frequentist regret that matches the Lai-Robbins lower bound, including achieving matching constants.
The authors propose a new anytime bandit algorithm based on an efficient approximation of the discounted Gittins index. There are two main ideas. The first is to increase the discount rate as a function of time, which saves the strategy from linear regret. The second is to approximate the Gittins index via a truncation after which the signal noise drops to zero.   The primary technical contribution is a theoretical analysis showing the frequentist asymptotic optimality of the strategy when the lookahead is just 1. 
*************************************************** POST REBUTTAL.  Thanks for the correction. I agree this makes things OK again. Nice paper. ***************************************************   Overall the paper is reasonably well written. I get the feeling the authors removed a lot of intuition to make the paper fit. I'm sympathetic to this plight, but still wish there was a little more there. Even simple things like noting that the effective horizon for discount gamma = 1 - 1/t is O(t) would be helpful. Also, in Examples 3.1/3.2 it would be nice to see some approximate solutions that reveal the strategy has a form approximately the same as some existing strategies (see minor comments).  Technically the paper is generally OK, but I do have some possibly serious issues described below. The authors should focus on these in their response to this review  to increase my score.   * It is claimed at the start of Section 4 that because the strategy is asymptotically optimal in the Lai & Robbins sense that it is also asymptotically Bayesian optimal. Please justify this claim. As far as I know the UCB strategy is not asymptotically Bayesian optimal, but it is optimal in the Lai & Robbins sense. The first index-strategy that is Bayesian optimal is by Lai in '87 (you cite it). I do believe your strategy gets both, but I don't understand the argument.  * In L397 in the supplementary material. I don't understand the > in the display. What if q = 1/10 and p = 1/2. Then the first logarithmic term is negative. I tried a little to fix this result and could not. This lemma seems quite critical and I wonder if this is where the improvement is coming from that allows some log factors to be shaved in the confidence interval essentially (I am talking about the discussion in L223).  Besides the theoretical results there are also some experiments. I found these to be a bit of a tease because (a) the performance is excellent and (b) we only get to see examples from a two (random) experiments. One Gaussian and one Bernoulli. It's nice to see the quantiles of the distribution, but I would have preferred to see the expected regret over a larger range of problems. Eg., the worst-case regime. Instead the focus is on a very easy problem with few arms and a distribution for which most of the arms are well separated. That said, the results are impressive.   Overall I find the paper very interesting. The technical issues force me to lower my score and I wish the execution were better (crisp intuition/experiments). See below for some minor comments.    Minor comments:  * It might be worth discussing the approximations given in Examples 3.1 and 3.2 in a little more depth. I did not investigate the former, but the latter turns out to be quite interesting. Solving the inequality and doing some naive approximation suggests that the optimal lambda has approximately the form  lambda = sqrt(2sigma^2 log(t sigma^2)   (here I have chosen gamma = 1 - 1/t as recommended). If the prior is the flat improper Gaussian prior, then in round t we have  sigma^2 = 1/N_i(t-1) and one recovers a well-known index, which at least for the Gaussian case has now extremely tight, but not quite optimal (in finite time),  regret guarantees. There are also asymptotic guarantees, see [1]. Note that this is basically the algorithm that Lai showed was Bayesian optimal (replace t by n).  * L39. I think Berry & Fristedt showed already that the Bayesian strategy is index-based only if geometric discounting and infinite horizon are assumed.  * L76. This reference is wrong, although that paper does study the case where the horizon is not known, so may also be relevant. I guess you mean [2]  * L216. Not everything that decays faster than 1/t is summable (eg., 1/(t log(t))  * The regret analysis included in the main body is all totally standard, while the interesting stuff is deferred to the appendix. An odd choice?  * L208: s_t, s_t' are introduced. Are they ever used?  * A bit petty, but I find some of the notation a bit displeasing. For example, T is used for the non-random horizon while k_i(t) is used for the  random number of times arm i has been chosen.  * Is it written which priors were used by Thompson sampling/Bayes UCB in the experiments?  * For what prior is Theorem 1 proven? (looks like flat beta prior, but is it written?). Can you get asymptotic optimality for any prior? Also see [1] for a more general results on BayesUCB   References:  [1] On Bayesian index policies for sequential resource allocation. Kaufmann, 2015 [2] Regret analysis of the finite-horizon Gittins index strategy for multi-armed bandits. Lattimore, 2016