We study $K$-armed bandit problems where the reward distributions of the arms are all supported on the $[0,1]$ interval. It has been a challenge to design regret-efficient randomized exploration algorithms in this setting. Maillard sampling \cite{maillard13apprentissage}, an attractive alternative to Thompson sampling, has recently been shown to achieve competitive regret guarantees in the sub-Gaussian reward setting \cite{bian2022maillard} while maintaining closed-form action probabilities, which is useful for offline policy evaluation. In this work, we propose the Kullback-Leibler Maillard Sampling (KL-MS) algorithm, a natural extension of Maillard sampling for achieving KL-style gap-dependent regret bound. We show that KL-MS enjoys the asymptotic optimality when the rewards are Bernoulli and has a worst-case regret bound of the form $O(\sqrt{\mu^*(1-\mu^*) K T \ln K} + K \ln T)$, where $\mu^*$ is the expected reward of the optimal arm, and $T$ is the time horizon length.
Paper
Similar papers
Peer review
Summary
In this paper, the author analyzes the MED algorithm proposed by Honda \& Takemura (2011) for Bernoulli distributions in the context of general bounded distributions, and under the name KL-Maillard Sampling. This work is a follow-up of a previous work that proposed Maillard Sampling for sub-gaussian distributions. KL-MS is a bandit algorithm that samples an arm at each time step with probability $p(t) \propto \exp(-N_a(t) \text{kl}(\mu_{t-1,a}, \mu_{t-1, \text{max}}))$, where kl is the KL divergence corresponding to Bernoulli distributions. The interest of this simple strategy is that one can explicitly compute the probability to pull each arm, which is useful for instance in the context of off-policy evaluation. Contrarily to the initial work of Honda & Takemura that focused on instance-dependent bounds, and in the spirit of the previous MS paper, the authors provide both optimal instance-dependent and minimax bounds for the algorithm for Bernoulli distributions. The same guarantees naturally hold for general bounded distributions, losing the optimality for problem-dependent guarantees compared to the original MED algorithm using the ``tight'' divergence. It is also proved that the worst-case guarantees scale in the standard deviation of the best arm, which is on par with what is known from the sub-gaussian case.
Strengths
* The paper is well-written, clear, and easy to follow. Furthermore, it seems technically sound, and the proofs are carefully detailed. The literature review is well-covered regarding the scope of the paper. * The analysis of asymptotic optimality of MED for the Bernoulli case is largely simplified compared to the original proof of Honda \& Takemura (2011). Furthermore, the worst case optimality is a novel result compared to this work. Compared to the previous MS paper, it is also interesting that the optimal minimax ratio is achieved without tweaking the algorithm. To prove these results, the the authors perfectly used the analysis tricks introduced recently in the TS literature (e.g all the cited works from Jin et al.). * The main novel element/insight of the paper compared to its two major inspirations is the refined analysis of the "under-exploration" term (F3) in the regret analysis, that lead to the $\log(K)$ vs. $\log(T)$ improvement of the minimax ratio of MS without having to change the algorithm, making MS+ obsolete. The changes in the proof for this are rather substantial so the contribution is valuable. * Maybe the most surprising result in the paper is the minimax bound scaling with the variance term $\mu_1(1-\mu_1)$. Therefore I would have appreciated some explanation in the main text as to where Theorem 4 comes from. If I understand correctly, it follows from a tighter version of Pinsker's inequality (Lemma 28) which is worth highlighting. While interesting, this trick could certainly be applied to the analysis of other bandit algorithms (as done for KL-UCB in an Appendix), so the result cannot really be interpreted as an indicator of the superior performance of KL-MS.
Weaknesses
* I am a bit uncomfortable with the re-branding of MED as KL-MS. This was understandable for the initial MS paper since Honda & Takemura tackled bounded distributions, but here the algorithm exactly matches MED for Bernoulli distributions. Furthermore, it is folklore that for algorithms using divergences the Bernoulli divergence can be used for general bounded distributions. Hence, there is no real reason for this re-branding in my opinion. However, I insist on the fact that I find the novel elements of analysis intereting. * Regarding the analysis, it seems that it differs from the original paper only from term (F3). The way the authors handle this term is very interesting and a valuable contribution in itself, but this should be better highlighted in the paper. However, even this part seems largely inspired by recent papers from Jian et al. for the analysis of Thompson Sampling, so I wonder if there is a really novel theoretical contribution in the paper. * Minor: the authors should cite a recent follow-up of Honda and co-authors on the MED algorithm: https://arxiv.org/abs/2303.06058 This do not alter the contribution of this paper since the authors focus on problem-dependent guarantees of MED for a broader class of distributions, but answer some of the questions presented in the conclusion of the paper.
Questions
I don't have specific questions for this work, everything seems clear to me.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
3 good
Contribution
2 fair
Limitations
N/A
Summary
This paper considers a classic bandit problem, where the algorithm should explicitly output the random distribution of the next pulling arm (as a comparason, in classic case, the algortihm only needs to generate one arm from this random distribution and outputs that arm). Existing results only work on the case that the random rewards are unbounded and subgaussian. In this paper, the authors extend the existing works to the case that the rewards are bounded in $[0,1]$, design a KL-MS algorithm (using a KL-divergence approach). They show that the regret upper bound of KL-MS is near optimal. They also use some experiments to show that the performance of KL-MS (in outputing the random distribution precisely) outperforms existing baselines.
Strengths
The regret bound in this paper is nearly tight. The writting is clear for me to understand.
Weaknesses
My first concern is about the model setting, i.e., why we require to know the exact random distribution of pulling the arm? Though there is an example of estimating the average reward, I do not think this is a well-motivated one. Can you provide more examples about the why we require that distribution in reality? Besides, why not just use a UCB-type algorithm, which can easily give you the exact probability distribution, as long as tight analysis? I know that there are works, e.g., MOSS, to achieve the tight $O(\sqrt{KT})$ regret upper bound, but not very sure whether there are UCB algorithms that achieve $O(\sqrt{\mu(1-\mu)KT})$ regret upper bound (though I think after using some variance-based concentration, the steps are straightforward). My second question is about the experiments of this paper (in appendix H). I do not see any comparason about the regrets between different algorithms, and I am wondering the regret performances of KL-MS. Finally, do you think the idea (of either MS or KL-MS) could be applied to infinite-arm case (e.g., linear bandits), for example, return a distribution supported on an infinite set?
Questions
Please see the above "Weaknesses"
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
N/A
Summary
The submission considers the vanilla setting of stochastic K-armed bandits and studies a strategy introduced by Maillard (2013), which relies on exponential weights and outputs at each round probabilities of taking each action. This is often convenient in offline policy evaluation, when estimates based on inverse propensity weighting [IPW] are constructed. Distribution-dependent and distribution-free regret bounds are provided, either in a general non-parametric model of all probability distributions over [0,1], or in the much specific model of Bernoulli distributions. The general distribution-dependent regret bounds asymptotically match the gap-based bounds of UCB (Theorem 1 and Remark 2) and is actually optimal in the Bernoulli model (Theorem 5). The general distribution-free bound improves on the one for UCB by featuring a \sqrt{\mu^\star (1-\mu^\star)} term (Theorem 3). Another main result is formed by Figure 1 and Table 1: there are actually few randomized strategies (Thompson sampling, MED) and none of them exhibits closed-form expressions for probabilities of plays. This shows that the core result of this article is: a strategy for the vanilla case of stochastic K-armed bandits, with decent (though not optimal) distribution-dependent and distribution-free regret bounds, and based on determining actual probabilities of playing arms, which is useful for offline policy evaluation.
Strengths
The idea of constraining the strategy to output probability distributions while getting decent bounds is nice and may turn useful---I have witnessed several recent articles critically using IPW in bandit contexts. By 'decent bounds', I mean bounds that are as good as, or slightly better than, UCB, but not optimal (as IMED and recent versions of KL-UCB achieve). The exposition is clear and I enjoyed reading the main body of the submission.
Weaknesses
1. Exponential weights are actually difficult to compute in practice with a good accuracy, at least for suboptimal arms that are played often. Perhaps this case does not arise (suboptimal arms are played only logarithmically many times and the probabilities are easy to compute with a good accuracy), but the accuracy in the computation should be commented, especially given the critiques against Thompson sampling on these issues on page 2. 2. The comparison to previous works could be clarified and reorganized in pages 4--5. In particular, it would have been better to recall first the typical (e.g., for UCB) as well as the optimal distribution-dependent and distribution-free regret bounds, in the Bernoulli model and in the model P(0,1) of all distributions over [0,1], when no constraint of outputting probability distributions is imposed. The sub-UCB criterion could be omitted, I don't think it adds anything. The literature review seems a bit outdated. In particular, a new reference is critically missing: https://www.jmlr.org/papers/volume23/20-717/20-717.pdf / it shows that in the model P(0,1) there exists a strategy called KL-UCB-switch that achieves simultaneously the optimal distribution-dependent and the optimal distribution-free bounds. 3. The regret bounds are unprecise: (i) they involve O(...) terms and (ii) even the main terms are difficult to read because of +/- c \Delta_a terms in the kl, (iii) not mentioning the additive T \Delta term, where \Delta is a parameter that must then be << \ln T / T and therefore should vanish. Even worse, Lemma 9 and Theorem 5 are proved by taking \Delta = 0 in the bound of Theorem 1, while Theorem 1 assumes \Delta > 0. 4. The proof sketches are too vague: pages 8-9 merely indicate a proof structure in terms of decompositions of events and other immediate considerations, but the actual boundings of the probabilities of interest is not explained in the main body (but is detailed in the extremely long appendix). At least two or three salient (new?) ingredients of these proofs should have been given in the main body. What I read on pages 8-9 is too high level and actually takes almost 2 pages without learning anything specific to the reader. I regretfully couldn't check the proofs and get a sense of their correctness, but I don't feel guilty for this, as nothing or almost helped me doing this in the main body. Better editorial choices could have been made as far as proof sketches are concerned. Other comments / remarks / typos along the text: - Lines 9-10: I wouldn't insist on the distribution-dependent optimality for Bernoulli distributions (which is a minor point) but rather on getting decent (better than UCB) bounds - Line 28: also Garivier and Cappé 2011 - Footnote 1: yes, but for known L and U - Caption of Figure 1: difficult to understand in itself, I have to read lines 770--773 in appendix to understand (these explanations should thus be moved in the main body) - Line 48: the empirical averages \mu_{t,a} were not formally defined - Lines 54-55: sounds like an overstatement; the submission proposes decent but not optimal distribution-dependent and distribution-free regret bounds - Table 1: Tsallis-INF is among the few strategies that output distributions, so it should not have been excluded on the ground of a minor issue given its non-optimal bound for Bernoulli distribution; this Table 1 is generally not helpful given that it contains too many strategies that do not output distributions - Lines 65-67: I would be less enthusiastic; getting rid of the \sqrt{\ln K} is uneasy but was achieved for some algorithms that are optimal from the distribution-dependent viewpoint (see https://www.jmlr.org/papers/volume23/20-717/20-717.pdf) though I appreciate as well the \sqrt{\mu^*(1-\mu^*)} term, which indeed may be smaller than \sqrt{\ln K} in some situations - Line 69: drop 'with' - Line 82: OK for this definition in case of absolute continuity, otherwise, = +\infty - Lines 108-109: syntax issue - Line 119: > b, not \geq b; this quantity is called K_inf - Lines 154-155: some strategies like KL-UCB-switch (see https://www.jmlr.org/papers/volume23/20-717/20-717.pdf) would be sub-UCB and enjoy a \sqrt{KT} distribution-free regret bound---I thus disagree with the statement made here - Lines 205-206: same kind of comments - Lines 239-241: there is no such issue if the Bernoullization trick of lines 115-119 is implemented - Line 258: rather (6) instead of (8)
Questions
I would like to read authors' opinion on the four main weaknesses that I raised.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
(They are well-addressed in the conclusion, Section 6, and include extensions of the optimality results of Maillard sampling to general exponential families and even to the non-parametric setting of all distributions over [0,1].)
Summary
The paper studies the classical regret-minimization problem in the stochastic multi-armed bandit framework. In particular, the manuscript's focus is on randomized algorithms with an aim to develop one with closed-form arm-selection probabilities at each step. Data collected by such algorithms can be used for offline policy evaluation. The manuscript proposes an algorithm called KL-MS for bounded-support distributions, that achieves KL-style regret guarantees. It is asymptotically optimal (in the instance-dependent stochastic sense) for bernoulli bandits, and order optimal for more general bounded-support distributions. It also enjoys an optimal worst-case regret guarantee. The paper also presents numerical study comparing the offline evaluation when the data is collected using the proposed KL-MS and Thompson Sampling with Monte-carlo on bernoulli bandits.
Strengths
The paper is written well and easy-to-read. I particularly enjoyed the various remarks and discussions after the results, providing insights into the results and comparing the analysis to existing ones. While in some settings randomness should also be treated as a resource (and hence be used with care), there are indeed benefits to using randomized algorithms in other settings. For example, as highlighted in the paper, the data collected by randomized algorithms can be used for offline evaluation. The paper develops an algorithm that simultaneously satisfies different desirable properties, while being optimal (or close-to-optimal) in a non-parametric setting of bounded-support distributions.
Weaknesses
1. The plots in the appendix are not very clear. The text along the vertical lines is overlapping and unreadable. It would be good to spread-out the fugures and probably figures in a vector form for clearer display. 2. In view of the recent results on fragility of optimized bandit algorithm, I believe that the MAB results should be studied and stated beyond the expected regret. See for instance "Fan, Lin, and Peter W. Glynn. "The fragility of optimized bandit algorithms." arXiv preprint arXiv:2109.13595 (2021)."
Questions
1. In line 21, the Reg(T) is referred to as pseudo-regret. How is this different from the usual expected regret? Why "pseudo" in the regret? 2. How would the analysis change (or challenges in extending) if instead of Bernoulli-kl in the exponent, one uses KL (the lower bound opt.)? Could the current results and analysis be already extended to that algorithm? I believe that is then the MED algorithm? It would then suggest a natural way to extend the algorithm and analysis for exponential families and more general distributions, like the heavy-tailed ones considered in Agrawal, Juneja, Koolen, 2021. A discussion along these lines would be interesting to see. 3. How does MS compare with KL-MS numerically? 4. How is the performance of the algorithm affected if the bounds [0,1] are not exactly known. For example, if the samples are from some misspecified setting, i.e., distribution with support in [-0.5, 0.5] but the algorithms is guaranteed only [0,1]-supported distributions?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
NA
post-rebuttal comment
Thank you for your response. Along with the other reviews, it confirms my positive evaluation of the paper. (1) I see, so for you the terminology "Maillard Sampling" may refer to algorithms that are easier-to-compute (but sometimes sub-optimal) proxies of MED in some sense? (2) I see. I still believe hat most of the difficulty in handling this term has been addressed in other works (of Jin et al.), but due to the technicality of the arguments this is not a limitation of the paper and I agree that the proof must have required some work. (3) I agree with your comment. This is related to your discussion with reviewer Gstc, but for the bounded case I believe that there is indeed some work to adapt your analysis to MED, because for instance the existing concentration inequality on KL-inf scales as (n x exp(-n ..)) (while for Bernoulli kl we have $\exp(-n...)$), and this multiplicative n itself would worsens the worst-case bound. Obtaining tighter concentration may be challenging, and it is not even clear that this is possible. Hence, the MS framework has an interest in the sense that it makes worst-case analysis easier with the tools developed by JIn et al. for exponential families, since it only requires to concentrate empirical means.
(1) Yes, that was our intention. We also see your point that, if we go with a generous interpretation of MED in the sense of [Baudry, Suzuki, and Honda, 2023, Eq. (4)], By choosing $D_\pi(F_k(t), \mu^\star(t))$ to be $\mathsf{kl}(\mu_k(t), \mu^\star)$, MED specializes to our KL-MS. (2, 3) We wish to point out that only a small part of our proof is inspired by [Jin et al. 2022] (specifically, our application of Lemma 25 in bounding $F3_1$ is inspired by their usage of Lemma A.4 to prove Lemma A.1, which is for refining the minimax ratio from $\sqrt{ \dot\mu_1 \ln T }$ to $\sqrt{\dot \mu_1 \ln K}$; even that time-uniform concentration inequality of empirical rewards was originally due to [Menard and Garivier, 2017], to the best of our knowledge). For the high-level case splits on bounding $\mathbb{E}[N_{T, a}]$, [Jin et al. 2022] uses a standard split in frequentist analysis of Thompson Sampling [e.g. Agrawal and Goyal, 2017, Eq. (2)], depending on whether the posterior sample of arm i exceeds $\mu_1 - \varepsilon$; In contrast, our split of F1, F2, F3 is similar to (and perhaps simplifies) the analysis of MS [Maillard, 2013, Bian and Jun, 2022] and MED [Honda and Takemura, 2010]. (3) We acknowledge the reviewer’s finding and appreciate the explanation.
I acknowledge reading the entire thread of reviews and corresponding rebuttals. On this specific rebuttal, I'm satisfied with answers 1-2-3. For answer 4, I believe that the KL-UCB-Switch paper is a good example of a paper with precise bounds not relying on O(...) terms, but perhaps this is too high a standard. I still believe that better proof sketches could have been provided, beyond the mere descriptions of the proof structures. All in all I am ready to increase my score to 5 and will update my report accordingly.
We can give an exact bound of KL-MS’s regret by replacing the Big-O term in Eq. (3) with exact constants. Specifically, the exact form of Eq. (3) is $$\mathrm{Reg}(T) \leq T\Delta + \sum_{a: \Delta_a > \Delta} \frac{\Delta_a \ln(T \mathsf{kl}(\mu_a + c \Delta_a, \mu_1 - c \Delta_a) \vee e^2 )} {\mathsf{kl}(\mu_a + c \Delta_a, \mu_1 - c \Delta_a)} +\left( \frac{34}{c^2} + \frac{8}{(1-2c)^2} \right) \cdot \sum_{a: \Delta_a > \Delta} \left( \frac{\dot\mu_1 + \Delta_a}{\Delta_a} \right) \ln \left( \left( \frac{\dot\mu_1 + \Delta_a}{\Delta_a^2} \wedge \frac{T\Delta_a^2}{\dot\mu_1 + \Delta_a} \right) \vee e^2 \right) $$ . As an example, if we choose $c=\dfrac{1}{4}$, the final regret bound given by Eq. (3) would be $$\mathrm{Reg}(T) \leq T\Delta + \sum_{a: \Delta_a > \Delta} \frac{\Delta_a \ln(T \mathsf{kl}(\mu_a + c \Delta_a, \mu_1 - c \Delta_a) \vee e^2 )} {\mathsf{kl}(\mu_a + c \Delta_a, \mu_1 - c \Delta_a)} +576 \cdot \sum_{a: \Delta_a > \Delta} \left( \frac{\dot\mu_1 + \Delta_a}{\Delta_a} \right) \ln \left( \left( \frac{\dot\mu_1 + \Delta_a}{\Delta_a^2} \wedge \frac{T\Delta_a^2}{\dot\mu_1 + \Delta_a} \right) \vee e^2 \right) $$. To see this, we first note that Lemma 10 is exact in that it does not hide constant factors. By tracking the exact constants in the proof of Theorem 1 (lines 435-438), we have that $$ \mathbb{E}\left[ N_{T,a} \right] \leq \frac{\ln(T \mathsf{kl}(\mu_a + c \Delta_a, \mu_1 - c \Delta_a) \vee e^2 )}{\mathsf{kl}(\mu_a + c \Delta_a, \mu_1 - c \Delta_a)} + \left( \frac{34}{c^2}+\frac{8}{(1-2c)^2} \right) \cdot \left( \frac{\dot\mu_1 + \Delta_a}{c^2 \Delta_a^2} \right) \ln\left( \left( \frac{\dot\mu_1 + \Delta_a}{c^2 \Delta_a^2} \wedge \frac{c^2 T \Delta_a^2}{\dot\mu_1 + \Delta_a} \right) \vee e^2 \right). $$
Stating more explicitly such exact bounds in the paper looks like a good idea to me, e.g., by keeping the O(...) form in the theorem and providing a pointer to later equations providing exact bounds.
Response to the rebuttal
Thank you for your response. I acknowledge reading the entire thread of reviews and corresponding rebuttals. For now, I don't have further questions.
Thank you
Thanks for your reply. For (1), I am still wondering whether we can use UCB method to achieve the same goal. Can you give me some insights about why UCB-based policies do not work in your example?
Note that deterministic exploration algorithms such as UCB generates logged data that cannot be reliably combined with the IPW estimator for offline evaluation. More precisely, logged data is generated by a UCB-based policy with $p_{t,I_t}=1$ for all t. Considering the offline evaluation setup in Appendix I, the IPW estimator will be $\hat\mu := \sum_{t=1}^T \frac{r_t}{K T}$. However, such an IPW estimator is biased with respect to the estimation target $\mu = \frac{1}{K} \sum_{i=1}^K \mu_i$. Consider a UCB-type algorithm, the fraction of the optimal arm in the historical arm pull $N_{T,1}/T $ will go $1$, therefore when we let $T \rightarrow \infty$, $\hat\mu = \sum_{t=1}^T \frac{r_t}{K T} \rightarrow \sum_{t=1}^T \frac{\mu_1}{K T}=\frac{r_1}{K}$ which is not equal to $\mu$.
Decision
Accept (poster)