Explore no more: Improved high-probability regret bounds for non-stochastic bandits
This work addresses the problem of regret minimization in non-stochastic multiarmed bandit problems, focusing on performance guarantees that hold with high probability. Such results are rather scarce in the literature since proving them requires a large deal of technical effort and significant modifications to the standard, more intuitive algorithms that come only with guarantees that hold on expectation. One of these modifications is forcing the learner to sample arms from the uniform distribution at least Ω( √ T ) times over T rounds, which can adversely affect performance if many of the arms are suboptimal. While it is widely conjectured that this property is essential for proving high-probability regret bounds, we show in this paper that it is possible to achieve such strong results without this undesirable exploration component. Our result relies on a simple and intuitive loss-estimation strategy called Implicit eXploration (IX) that allows a remarkably clean analysis. To demonstrate the flexibility of our technique, we derive several improved high-probability bounds for various extensions of the standard multi-armed bandit framework. Finally, we conduct a simple experiment that illustrates the robustness of our implicit exploration technique.
ADDED after author response:Thank you for the clarifications. It would be great if you could include some of the points about implicit vs. explicit exploration and about choice of parameters in the two settings in the final version.======The work is motivated by the observation that the explicit exploration term often used in multi-armed bandit algorithms when selecting the next arm can adversely affect performance, especially in situations where some arms are "obviously" suboptimal. The authors instead propose to use the implicit exploration (IX) idea of Kocak et al [NIPS-2014] and show that the corresponding loss function with implicit exploration (a) simplifies the regret bound analysis and (b) improves the constant factor in known regret bounds for many variants of the basic MAB problem.      The paper is interesting, the writing is clear, and the math seems solid (although I didn't check all proofs carefully). Table 1 neatly summarizes the main theoretical results. I enjoyed reading the paper but have only lukewarm feelings of acceptance because:      1. Novelty and significance: The novel part here is the application of the known IX idea to a number of known algorithms, and their analysis. The results in table 1 are clearly improvements, but "only" by small constant factors. I'm not sure how significant is the result in advancing the field or how much practical impact they would have.      2. Implicit vs. Explicit exploration: The basic tenet here is that explicit exploration is undesirable, which I agree with. There are at least two things that make it undesirable. First is that with explicit exploration comes a tradeoff parameter (how much to explore, how much to exploit) that must often be tuned in practice based on the domain at hand. The proposed algorithm, however, effectively has this parameter as well (the gamma in the denominator) and thus doesn't resolve this issue. Second, as noted in the abstract, explicit exploration makes algorithms sample the losses of every arm at least Omega(sqrt(T)) times over T rounds, even when many arms are "obviously suboptimal". The (implicit) claim is that the proposed algorithm is less wasteful on arms that are "obviously suboptimal". However, this part of the theory has not been explored in the paper. Table 1 doesn't address this. Reading the abstract, I was expecting to see some result of the form: if some fraction of arms is "obviously suboptimal" then the IX algorithm will provably waste less resources on them. Having a result along these lines would have made the paper significantly stronger.      Overall, I like the paper but have some reservations.