Two-Target Algorithms for Infinite-Armed Bandits with Bernoulli Rewards
We consider an infinite-armed bandit problem with Bernoulli rewards. The mean rewards are independent, uniformly distributed over [0,1]. Rewards 0 and 1 are referred to as a success and a failure, respectively. We propose a novel algorithm where the decision to exploit any arm is based on two successive targets, namely, the total number of successes until the first failure and until the first m failures, respectively, where m is a fixed parameter. This two-target algorithm achieves a long-term average regret in √ 2n for a large parameter m and a known time horizon n. This regret is optimal and strictly less than the regret achieved by the best known algorithms, which is in 2 √ n. The results are extended to any mean-reward distribution whose support contains 1 and to unknown time horizons. Numerical experiments show the performance of the algorithm for finite time horizons.
The main contribution of the paper is to close a 
      constant gap between the lower and upper bounds of the asymptotic regret 
      in an infinite-armed bandit setting where the arms are drawn from a 
      uniform distribution and the length of the horizon is known. The result is 
      extended for unknown horizons and more generic distributions, at the 
      expense of loosing the tightness between the lower and the upper bounds. 
      Quality Algorithm 1 is an interesting addition to the 
      literature. Its upper bound matches the lower bound proven in [2]. The 
      algorithmic idea is novel and non-obvious and the regret proof is sound. 
      It is important to note that the algorithmic strategy is only of 
      theoretical interest at this point, as its regret guarantee holds when 
      both n (the horizon length) and m (the number of "runs" of an arm) go to 
      infinity. My first question is whether you tried to get an upper 
      bound for m in terms of n so that we can get a more informative result 
      than Proposition 1? Such a result would help get rid of m as a parameter 
      if one would actually want to use the algorithm in an applied setting. 
      One weakness of the paper is the lack of at least basic numerical 
      results about the finite time behavior of Algorithm 1. Even though the 
      result is asymptotic, it is interesting to understand how it behaves for a 
      well defined horizon length (as discussed on page 2105 in [2] for 
      example). While in section 5, the authors compare the empirical regret of 
      the algorithm with the asymptotic lower bound, it would be interesting 
      (since it might have an impact in an applied setting) to verify how the 
      algorithm compares with the strategies introduced in [2] or [6] for 
      example. My second question is about the statement that the lower 
      bound in [2] is incorrect (line 064). First, the authors mention Theorem 2 
      in [2], but Theorem 2 in the referred paper is about the upper bound for 
      the k-failure strategy. So I am assuming they talk about the Theorem 3. 
      The note at lines 102-105 mention an assumption from the lower bound 
      theorem in [2] that I was unable to locate in that paper. As a 
      consequence, I am not convinced that the original lower bound proof is 
      incorrect. Could you please clarify? Also, in the case the paper is 
      accepted and the lower bound is indeed incorrect, please add a more 
      detailed description of the error in the appendix. Clarity The 
      paper is well written and relatively easy to follow. Regarding the 
      organization, I would recommend decreasing the space allocated to the 
      description of Algorithm 2 as it is pretty similar at a high level to 
      Algorithm 1 and it clearly doesn't need 3/4 of a page to understand. 
      Originality and Significance I am not fully convinced of the 
      significance of the paper (at least from the point of view of being 
      published in a conference like NIPS). While I think it is important that a 
      gap is closed, I would like to understand the impact of the algorithm 
      either from a more applied perspective or get some insights with respect 
      to where it could be used from a theoretical perspective. That being said, 
      to the best of my knowledge, the algorithmic ideas are novel and 
      interesting and they might be of use for other bandit 
      algorithms.