Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards
Authors: Hao Qin
Kwang-Sung Jun
Chicheng Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-armed bandits
bounded rewards

Abstract: We study $K$-armed bandit problems where the reward distributions of the arms are all supported on the $[0,1]$ interval. 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 analyze the Kullback-Leibler Maillard Sampling (KL-MS) algorithm, a natural extension of Maillard sampling {and a special case of Minimum Empirical Divergence (MED)~\cite{honda2011asymptotically}} for achieving a KL-style finite-time gap-dependent regret bound. We show that KL-MS enjoys the asymptotic optimality when the rewards are Bernoulli and has an {adaptive} 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; {this is the first time such adaptivity is reported in the literature for an algorithm with asymptotic optimality guarantees.}

Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards
Hao Qin University of Arizona hqinCarizona. edu
Kwang-Sung Jun University of Arizona kjunθcs arizona. edu
Chicheng Zhang University of Arizona chichengzOcs arizona. edu
Abstract
We study K-armed bandit problems where the reward distributions of the arms all supported on the [0, 1] interval. Maillard sampling [30], an attractive alternative Thompson sampling, has recently been shown achieve competitive regret guarantees in the sub-Gaussian reward setting [ while maintaining closed-form action probabilities, which useful for offline policy evaluation. In this work, we analyze the Kullback-Leibe ural extension of Maillard sampling and special case of Minimum Empirical Divergence (MED) [9] for achieving a KL-style finite-time gap-dependent re- gret bound. We show that KI.-MS enjoys the asymptotic optimality when the rewards are Bernoulli and has an adaptive worst-case regret bound of the form OlVi'(1 _²*) K mal arm, and T is the time horizon length; this is the first time such adaptivity reported in the literature for an algorithm with asymptotic optimality guarantees.
Maillard Sampling (KL-MS) algorithm, nat-
In K + K In where μ² is the expected reward of the opti-
1 Introduction
The multi-armed bandit (abbrev. MAB) problem [4 27 29 a stateless version of the reinforcement
learning problem, has received much attention by the research community, due its relevance in may applications such as online advertising, recommendation, and clinical trials. In a multi-armed bandit problem. learning agent has access set of K arms (also known as actions), where for each i [K] == {1..... "i....,K, K}, arm i is associated with a distribution V; with mean μą at each time step the agent adaptively chooses an arm 4 E [K] by sampling from probability distribution E A K- and receives reward yr VI,, based on the information the agent has so far. The goal of
EΣ Vr. where the agent is minimize its pseudo-regret over T time steps: Reg(T) = Tu" E Et= 4 max; Jr is the optimal expected reward.
In this paper, we study the multi-armed bandit setting where reward distributions of all arms are supported on [0, 1]. I An important special case is Bernoulli bandits, where for each arm i, 2 = Bernoulli(ua) for some μ4 E [0, 1]. It has practical relevance in settings such as computational advertising, where the reward feedback is oftentimes binary (click vs. not-click, buy vs. not-
Broadly speaking, there are two popular families of provably regret-efficient algorithms for bounded- reward bandit problems: deterministic exploration algorithms (such as KL-UCB 17 [3] 31) and
randomized exploration algorithms (such as Thompson sampling (TS) [1). Randomized exploration algorithms such as have been very popular, perhaps due to excellent empirical performance and the ability to cope with delayed rewards better than deterministic counterparts [15] In addition, the logged data collected from randomized exploration, the form chosen, useful for offline evaluation purposes by
(Je, Pt. 3/t Y where Pt.r,
the probability with which arm
All of our results can be extended to distributions supported in [L, U] for any known S U by shifting and scaling the rewards to lie in 1).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Figure 1: Histogram of the average rewards computed from the offline evaluation where the logged data is col- lected from Bernoulli TS and KL-MS (Algorithm) [T in a Bernoulli bandit environment with the mean reward (0.8, 0.9) with time horizon T = 10, 000. For Bernoulli TS's log, we approximate the action probability by Monte Carlo Sampling with 1000 samples for each step. Here we es- timate the expected reward of the uniform policy which has expected average reward of 0.85 (black dashed line). Across 2000 trials, the logged data of KL-MS induces an MSE of 0.00796; however, for half of the trials, the IPW estimator induced by Bernoulli TS's log returns invalid values due to the action probability estimates being zero Even excluding those invalid values, the Bernoulli TS's logged data induces an MSE of 0.02015. See Appendix H for additional experiments.
100
BemoullITS
KL MS
80-
Cracle
mequency
BermuuliTS
60-
KL-M5
40
20
Sradle
0.75
1.00
1.25
1:50
1.75
2,00
averace reward
employing the inverse propensity weighting (IPW) estimator 22 the doubly robust estimator 38 However, calculating the arm sampling probability distribution for Thompson sampling is nontrivial. Specifically, there is no known closed-form and generic numerical integration methods and Monte-Carlo approximations suffer from instability issues: the time complexity for obtaining a numerical precision of is (ppoly(1/e) B6). This too slow to be useful especially for web-scale deployments; e.g., Google AdWords receives 233M clicks per day. Furthermore, the computed probability will used after taking the inversion, which means that even moderate amount of errors are intolerable. Indeed, Figure I shows that the offline evaluation with Thompson sampling as the behavioral policy will be largely biased and inaccurate due to the errors from the Monte Carlo approximation.
Recently, many studies have introduced alternative randomized algorithms that allow an efficient computation of Ps [19] 30 43]. Of these, Maillard sampling (MS) (30 [.]. Gaussian adaptation
of the Minimum Empirical Divergence (MED) algorithm [19] originally designed for finite-support reward distributions, provides a simple algorithm for the sub-Gaussian bandit setting that computes Pe in a closed form:
-3-1.
- -No-1,.
Pt.a & exp
20
where at time step i, Nr.a is the number of pulling arm a. We define the estimator of Pha as Arra == Eim 1(1 and the best performed mean value as fl, == maX (e, Â max,' P P4- is the empirical suboptimality gap of arm a, and a is the subgaussian parameter of the reward distribution of all arms. For sub-Gaussian reward distributions, MS enjoys the asymptotic optimality under the special case of Gaussian rewards and near-minimax optimality (II, making it an attractive alternative to Thompson sampling. Also, MS satisfies the sub-UCB criterion (see Section for a precise definition) to help establish sharp finite-time instance- instance-dependen regret guarantees. Can we adapt MS to the bounded reward setting and achieve the asymptotic, minimax optimality and sub-UCB criterion while computing the sampling probability in closed-form) In this paper, we make significant progress on this question.
No,
2
Our contributions. We focus on Bernoulli adaptation of MS that we call Kullback- Maillard Sampling (abbrev. KL-MS) and perform a finite-time analysis of it in the bounded-reward bandit problem. KL-MS uses sampling probability similar to MS but tailored to the [0, bouudedd reward setting:
Pr. X exp (- Ne-1,all (ia--1,a (ee
where kl( ,²) == pnn # + 14) In 1- is the binary Kullback-Leibler (KI.) divergence. We can also view KL-MS as an instantiation of MED 19 for Bernoulli rewards; See Section 3 for
I-p"
"Suppose the arms' mean reward posterior distributions' PMFs and PDFs are (Pı,..., PK) and (F1, Fx) respectively; for example, they are Beta distributions with different parameters, i.c. p=(x) x i 1) E [0, 1J) for some a; b. To the best of our knowledge, the action probabilities have the following integral expression: P(L, a) = Jg pa (x) Hkya F((x) dæ and cannot be further simplified.

---

Algorithm&
Unite-Time Regret
Closed-form Probability
Reference
Analysis
Minimax Ratio
Sub-UCB
TS
Vln K
no
See the caption
ExpTS
In K
yes
no
Jin et al. [24]
ExpTS*
no
Jin et al. 124
kl-UCB
vIn T
yes
N/A
Cappé et al.
13
kI-UCB++
N/A
Ménard and Garivier
33
kI-UCB-switch
N/A
Garivier al. 18
MED
no
Honda and Takemura
19
DMED
N/A
Honda and Takemura 20
IMED
N/A Honda and Takemura
KL-MS
In
yes
yes this paper
Table 1: Comparison of regret bounds for bounded reward distributions; for space constraints we only include those that achieves the asymptotic optimality for the special case of Bernoulli distributions (this excludes, c.g., Maillard Sampling [30] [T] Tsallis-NN [43] and UCB-V (8). -- 'indicates that the corresponding analysis is not reported. "N/A'indicee A'iindicssss that the algorithm does have closed-form,
but it is deterministic. "*'indicates that its computational complexity for calculating the action probability is In (1 ( /pprecision.. *** 'indicates that we conjecture that the algorithm is not sub-UCB. The results on TS are reported by Agrawal and Goyal 3
Korda al. [26
detailed comparison. KL-MS performs efficient exploration for bounded rewards since can use kl(a, b) 2 2(a - b)2 to verify that the probability being assigned to each empirical non-best arm by KL-MS is never larger than that of MS with o² = 1/4, the best sub-Gaussian parameter for the bounded rewards in [0, IJ. We show that KL-MS achieves a sharp finite-time regret guarantee (Theorem that can be simultaneously converted to:
an asymptotic regret upper bound (Theorem which asymptotically optimal when specialized to the Bernoulli bandit setting;
vT-style regret guarantee of (r) + K Kln(T)) (Theorem 3) where '² the mean reward of the best arm. This bound has two salient features. First, in the worst case, is at most VIn K factor suboptimal than the minimax optimal regret of ((VKT)
Second, its O(V - μ²) coefficient adapts to the variance of the optimal arm reward; this is the first time such adaptivity is reported in the literature for an algorithm with asymptotical optimality guarantees.
10
sub-UCB regret guarantee, which many existing minimax optimal algorithms B3 18 have not been proven to satisfy.
We also conduct experiments that show that thanks to its closed-form action probabilities, KL-MS generates much more reliable logged data than Bernoulli TS with Monte Carlo estimation of action probabilities; this is reflected their offline evaluation performance using the IPW estimator, see Figure and Appendix H for more details.
2 Preliminaries
Let Nr. be the number of times arm has been pulled until time step t (inclusively). Denote the suboptimality gap of arm by A. := μ Mas where μ² max;e[]] (4i is the optimal expected reward. Denote the empirical suboptimality gap of arm a by Å == futmaa - iita; here, Pr.a is the empirical estimation to Pa up to time step I, i.e., fit,a := 1 - v. 1 1. = a). and
N.
fr, [ Pr,a is the best empirical reward time step t. For arm a, define T, (s)
min {t 1: Nr., = the time step when arm a is pulled for the s-th time, which is a stopping time; we also use ((s))a == (8), to denote empirical mean of the first reward values received from pulling arm a.
3 As side results, we show Appendix F that with some modifications the analysis, existing algorithms B 33 also achieve regret of the form Ō (1
(1- 4² polyy (YY))) for [0, 1] bouuned reward MABs.
3

---

We define the Kullback-Leibe divergence between two distributions v and as KL = ap (x) if v is absolutely continuous w.r.t and = +o0 otherwise. Recall that we define the binary Kullback-Leibke divergence between two numbers μ4, in [0, 1] as M'),p')
Ex-e In de
pInn L 27 + (1 - p)) In = which is also the KL divergence between two Bernoulli distributions with mean parameters ya and μz respectively. We define jA = pa1 p)), which is the variance of Bernoulli(p) ()) but otherwise an upper bound on any distribution supported on [0, with mean pe; see Lemma T6 for formal justification.
In the regret analysis, we will oftentimes use the following notation for comparison up constant factors: define J S (resp. f 2 g) to denote that J S Cg (resp. f 2 Cg) for some numerical constant C O. We define V and a A b as max(a, b) and min(a, b). respectively. For event F, we use E to denote its complement.
Below, we define some useful criteria for measuring the performance of bandit algorithms, specialized to the [0, 1] bounded reward setting.
Asymptotic optimality in the Bernoulli reward setting An algorithm is asymptotically optimal in the Bernoulli reward setting [2 if for any Bernoulli bandit instance (Va (erroouli((e)))ee((]
lim supT T Ea.d.> kl(p
Reg(T)
Aa
Minimax ratio The minimax optimal regret of the [0, 1] bounded reward bandit problem is Given K-armed bandit problem with time horizon T, an algorithm has
@
KT
5
10].
minimax ratio of f(T, if its has a worst-case regret bound of O(OKKT
Sub-UCB Sub-UCB is originally defined in the context of sub-Gaussian bandits [29]: given a bandit problem with K arms whose reward distributions are all uau-Gassi,n,, an algorithm is said to be sub-UCB if there exists some positive constants C1 and Cg. such that for all P-suu-Gauusiie bandit instances, RTg(T) S Ct E.... o Aa + C2 E..d.> A. In T. Specialized to setting, any distribution supported on [o, 1] is also ssub-Gaussian and all suboptimal arm gaps A, E (0, 1] are such that A. < - C, such that for all [0, 1] b-oundedd reward bandit instances, Reg(T) S C "E:s..>0 A
3. the above sub-UCB criterion simplifies to: there exists some positive constant la
3 Related Work
Bandits with bounded rewards. Early works of Lai et al. (27,. Burnetas and Katehakis 12 show that in the bounded reward setting, for any consistent stochastic bandit algorithm, the regret lower bounded by (1 + o(1)) Ea.d. KLiar(Pe.HH) and KLinr(Pa, v²") is defined as
A, In
KLint (v. n²)=== == inf (KL(U, Ex-p [X] > ,=, supp(p) c [0,
(2)
where the random variable follows distribution p bounded in [o, 1]. Therefore, any algorithm whose regret upper bound matches the lower bound is said to achieve asymptotic optimality. Cappé et al. [13 propose the KL-UCB algorithm and provide a finite time regret analysis, which is further refined by Lattimore and Szepesvári 29 Chapter 10]. Another line of work establishes asymptotic and
finite-time regret guarantees for Thompson sampling algorithms and its variants 22 4 25 24], which, when specialized to the Bernoulli bandit setting, can be combined with Beta priors for the Bernoulli parameters design efficient algorithms.
A number of studies even go beyond the Bernoulli-KL. KL-ttupe----tteeeeee regret bound and adapt to the variance of each arm in the bounded reward setting. UCB-V 7 achieves regret bound that adapts to the variance. Efficient-UCBV (35) achieves a variance-adaptive regret bound and also an optimal minimax regret bound D(KKT) but it is not sub-UCB. Honda and Takemura 19 propose the MED algorithm that is asymptotically optimal for bounded rewards, but it only works for rewards that with finite supports. Honda and Takemura (2I] propose the Indexed MED (IMED) algorithm that can handle more challenging case where the reward distributions supported in (-o0, 1).
As with worst-case regret bounds, first, is well-known that for Bernoulli bandits as well as bandits with [0, 1] bounded rewards, the minimax optimal regrets are of order ((VKT) 10 5] Of the algorithms that enjoy asymptotic optimality under the Bernoulli reward setting described above,
KL-UCB [3 has worst-case regret bound of O(v /VVK KT In T)), which is refined by the KL-UCB++

---

algorithm [33 that has a worst-case regret bound of ((VKT) We also show in Appendix F.1 and F2d that with some modifications of existing analysis, KL-UCB and KL-UCB++ enjoy regret O(v
bound of O(v 1r (1 - 1 ) In T and Ol 4 - μ²) - In T) respectively. Although the
regret is worse in the order of K, it adapts to f and will have a better regret when μ is small (say, " 1/KK). KL-UCB++ [a and KL-UCBB-Swithh [8] achieves O(vKT) regret in the finite-time regime and asymptotic optimality, while the sub-UCB criterion has not been satisfied. However, Lattimore 28, $3 shows that MOSS (6) suffers sub-optimal regret worse than UCB-like algorithms because of not satisfying sub-UCB criteria, and we suspect that LL-UCB-switeh experience the same issue as MOSS. For Thompson Sampling style algorithms, Agrawal and Goyal [3] shows that the original Thompson Sampling algorithm has worst-case regret of O( KTT In K). and the ExpTSS+ algorithm 24 has worst-case regret of O(V
Randomized exploration for bandits. Many randomized exploration methods have been proposed
for multi-armed bandits. Perhaps the most well-known is Thompson sampling [1]. which is shown to
achieve Bayesian and frequentist-style regret bounds in a broad range of settings [39 2 25 26 23 24
A drawback of Thompson sampling. as mentioned above, is that the action probabilities cannot be obtained easily and robustly. To cope with this, a line of works design randomized exploration algorithms with action probabilities in closed forms. For nub-Gaussian bandits, Cesa-Bianchh et al. [4] propose a variant of the Boltzmann exploration rule (that is, the action probabilities are proportional to exponential to empirical rewards, scaled by some positive numbers), and show that it has O K Kla"T
instance-dependent and O (KTlmnK worst-case regret bounds respectively,
where A= mina:A,20 A, is the minimum suboptimalty gap. Maillard sampling (MS; Eq. (T) is an algorithm proposed by the thesis of Maillard (30] where the author reports that MS achieves the asymptotic optimality and has a finite-time regret of order En:A.>
In
+ Σ from which A.
worst-case regret bound of O( M(VKT3/4 can be derived. MED [19], albeit achieves asymptotic optimality for a broad family of bandits with finitely supported reward distributions, also has a high
Recently, Bian and Jun report a refined analysis of Maillard [30 is sampling rule, showing that it has finite time regret In(T
finite-time regret bound of at least E.:d.>0 >0
IT A.
A
of order E.d. >0 A. + +0 Ea.d..o 1 A. In( 2.)). and additionally enjoys a O (VKThi) (KTTTT worst-case regret, and by inflating the exploration slightly (called MS*), the bound can be improved and enjoy the minimax regret of O (VKTInK) which matches the best-known regret bound among those that satisfy sub-UCB criterion, except for AdaUCB. In fact, it is easy to adapt our proof technique in this paper to show that MS, without any further modification, achieves a O (VKTmn worst-case regret.
Randomized exploration has also been studied from nonstochastic bandit perspective [10 55, where randomization serves both as a tool for exploration and a way to hedge bets against the nonstationarity of the arm rewards. Many recent efforts focus on designing randomized exploration bandit algorithms that achieve "best of both worlds" adaptive guarantees, i.e., achieving logarithmic regret for stochastic environments while achieving VT regret for adversarial environments [e.g. 43
Binarization trick. It is a folklore result that bandits with [0. 1] bounded reward distributions can be reduced to Bernoulli bandits via a simple binarization trick: at each time step t, the learner sees reward r E [o. 1). draws f, ~ Bernoullir.)) and feeds it to Bernoulli bandit algorithm. However, this reduction does not result in asymptotic optimality for the general bounded reward setting, where the asymptotic optimal regret is of the form (1 + o())) E.:d.0 (LnrrMa.. defined in the Eq (2. If we combine the binarization trick and the MED algorithm in the bounded reward setting, the size of the support set is viewed 2, the finite-time regret bound is at best as 0(K1/178/4) (ignoring logarithmic factors), which is much higher than O( O(VKT).
T with KLine p²)
'A close examination of [19 Lemma 9 (specifically, equation (20) shows that for each suboptimal arm a. the authors bound E [a)r,a] by term least Σ/= K (t 11 (ipp(er)) exp (-IC((u H - =)). where C(u, n') == 21((1)))
(m-a')² and < A.; this is Ω
1 when is bounded away from 0 and 1.
A 2
5

---

Algorithm KL Maillard Sampling (KL-MS)
1: Input: K X22
2: for = 1,2, .T do
3: if S K then
4: Pull the arm I, = and observe reward V/ ~ V4.
5: else
6: For every a E [K] compute
1
Pt.e M₁ exp (- I-N-11a kl(ft 14.
where M₁ >x N 1, P 1,xx)) is the normalizer.
7: Pull the Ie Pt.
8: Observe reward yt Vl.
9: end if
10: end for
Bandit algorithms with worst-case regrets that depend the optimal reward. Recent linear
logistic bandit works have shown worst-case regret bounds that depend on the variance of the best 332 I. When the arms standard basis vectors, logistic bandits are equivalent to
Bernoulli bandits, and the bounds of Abeille et al. [ become Ô VVVT K² A (K2 + A)) where Amin = min 3ú and A is an instance dependent quantity that can be as large as T. This bound, compared to ours, has extra factor of VK in the leading term and the lower order term has an extra factor of K. Even worse, it has the term Pmin in the lower order term, which can be arbitrarily large. The bound in Mason et al. 32 becomes Ô (Vir KT + i K²) which matches our bound in the leading term up to logarithmic factors yet still have extra factors of K and imin in the lower order term
Pmnm
4
Main Result
The KL Maillard Sampling Algorithm. We propose an algorithm called KL Maillard sampling
(KL-MS) for bounded reward distributions (Algorithm []] For the first K times steps, the algorithm pulls each arm once (steps 3 4) this ensures that starting from time step K + 1, the estimates of the reward distribution of all arms are well-defined From time step t = K + 1 on, the learner computes the empirical mean 74= of all arms a. For each arm a, the learner computes the measure of empirical
binary KL. divergence between f4- and f 1.max. kl(f4-1,0, m1 suboptimality of that arm. The sampling probability of arm a, denoted by Pt.a, proportional to the exponential of negative product between Nt and kl(āt-1.. 1.:: Pr-1 (Eq. (3) of step (6). This policy naturally trades off between exploration and exploitation: arm is sampled with higher probability. if either it has not been pulled many times (N, 1.a is small) or it appears to be close to
optimal empirically (kl(m)-1.0s (mxx)m)x)) small). The algorithm samples an arm I from Pt. and observe reward y/ of the arm chosen.
We remark that if the reward distributions v4 are Bernoulli, KL-MS equivalent the MED algorithm [9 since in this case, all reward distributions have a binary support of (0. 1). However, KL-MS is different from MED in general: MED computes the empirical distributions of arm rewards P. Pr and chooses action according to probabilities Pt.a x exp(-NN-1,a. D. here, De-1.a = KL(Fi-1,ax f m,max) (recall its definition in Section 3) is the "minimum empirical divergence" between arm a and the highest empirical mean reward, which different from the binary KL divergence of the mean rewards used in KL-MS.
4.1 Main Regret Theorem
Our main result of this paper is the following theorem on the regret guarantee of KL-MS (Algorithm Without loss of generality, throughout the rest of the paper, we assume #1 2 p2 2 ... 2 PK.

---

Theorem 1. For any K arm bandit problem with reward distribution supported on [0, 11. KL-MS has regret bounded as follows. For any A 2 and E (0, 1
Da (n(Tk)(1 + a0 p1 cDa)) V e²
Reg(T) ST +
Σ
kl(Ha + c.a, -cda)
a: >A
iu + Da In
CT inn + An
+ 560
A
Ve²
(4)
2 A
a:A.>A
The regret bound of Theorem i composed of three terms. The first term is TA. which controls the contribution of regret from all A A-near-optimal arms. The second term is asymptotically (1 A In(T") with an appropriate choice of which is term that grows in T in logarithmic rate. The third term is simultaneously upper bounded by two expressions. One is which is of order I and helps establish tight worst-case
o(1) La:s,>0 )[(aad))
Em:a,>0
(1+AA c²A.
In
Craa V ve²)
regret bound (Theorem 3 the other is Ea:d.>0
In
Ve²
which does not
C
grow in T and helps establish a tight asymptotic upper bound on the regret (Theorem 4
To the best of our knowledge, existing regret analysis on Bernoulli bandits or bandits with bounded support have regret bounds of the form
+0 1
Reg(T) +TA+
Du IT(T) a:A,>A kl(Mo, cBa, μn cA.)
Σ
)
ΣE
NoiA, >A
for some e > O, where the third term is much larger than its counterpart given by Theorem when Ae and ji are small. As we will see shortly, as a consequence of its tighter bounds, our regret theorem yields superior worst-case regret guarantee over previous works.
Theorem 2 (Sub-UCB). KL-MS's regret is bounded by Reg(T) & ExidAD lT A."
Therefore, KL-MS
is sub-UCB.
Sub-UCB criterion is important for measuring a bandit algorithm's 's finite-time instance deseadce performance. Indeed, Lattimore (2% $3) points out that MOSS (6 does not satisfy sub-UCB and that leads to a strictly suboptimal regret in a specific instance compared to the standard UCB algorithm [.. A close inspection of the finite-time regret bounds of existing asymptotically optimal and minimax optimal algorithms for the [0, 1]-reward setting, such as KL-UCB++ (33] and KL- sub-UCB. Thus, we speculate that they would also have
UCB-switch (18), reveals that they suboptimal performance in the aforementioned instance.
In light of Theorem [ our first corollary is that KL Maillard sampling achieves the following adaptive worst-case regret guarantee.
Theorem (A (Adaptive worst-case regret). For any K-arm bandit problem with reward distribution supported [0, 1). KL-MS has regret bounded as: Reg(T) S jin K Kln T.
An immediate corollary is that KL Maillard sampling has regret of order KTVKI,K,, which
is factor of O(VIn K) within the minimax optimal regret O (KT) B3 5). This also matches the worst-case regret bound O CVV/KTTT CVVV/KIII/K/ variance for Bernoulli bandits using a Thompson sampling-style algorithm. Another main feature of this regret bound is its adaptivity to jr, the variance of the reward of the optimal arm for the Bernoulli bandit setting, or its upper bound the general bounded reward setting (sce Lemma (6). Specifically, if μn is close to 1, ii is very small, which results in the regret being much smaller than ((VKTM) In K).
of Jin et al. 24 where V = 4 is the worst-case
Note that UCB-V and KL-UCB/KL-UCB+++ while not reported, enjoy a worst-case regret bound of KT T). which is worse than our bound in its logarithmic factor; see Appendix F3 and F. for the proofs. Among these, UCB-V does not achieve the asymptotic optimality for the Bernoulli case. While logistic linear bandits 1 32 can be applied to Bernoulli K Kaarmed bandits and achieve similar worst-case regret bounds involving fu, their lower order term can be much worse as discussed in Section
7

---

Our second corollary is that KL Maillard sampling achieves tight asymptotic regret guarantee for the special case of Bernoulli rewards:
Theorem (Asymptotic Optimality) For any K-arm bandit problem with reward distribution supported on [0, 11, KL-MS satisfies the following asymptotic regret upper bound:
RTg(T) In(T)
lim sup T0
(5)
kl(Has p11)
aE[K]:A.>0 30
Specialized to the Bernoulli bandit setting, in light of the asymptotic lower bounds asymptotic regret upper bound implies that KL-MS asymptotically optimal.
the above
While the regret guarantee of KL-MS is not asymptotically optimal for the general [0, 1] bounded reward setting. it nevertheless is better regret guarantee than naively viewing this problem sub-Gaussian bandit problem and applying sub GabbGan bandit algorithms on it. To see this, note that any reward distribution supported on (0, 1] is _ sub aub-Gaussian; therefore, standard uub-aaussian bandit ln algorithms will yield an asymptotic regret (1 + o(1)) EaE[K]: >0 2d. This is always no better
than the asymptotic regret provided by Eq. (5), in view of Pinsker's inequality that kl(pa: (1) 2 24
5 Proof Sketch of Theorem
We provide an outline of our proof of Theorem I with full proof details deferred to Appendix C Our approach is akin to the recent analysis of the sub-Gause nub-Gaussian Maillard Sampling algorithm in Bian and Jun [1]] with several refinements tailored to the bounded reward setting and achieving vIn K minimax ratio. First, for any time horizon length T, Reg(T) can be bounded by:
(Tg(T)=
Σ
A. E Nr.a] S AT +
Σ
A.E [Nr,0]>
(6)
dE[K]:A,>A
i.e. the total regret can be decomposed to TA term and the sum of regret A. [Nr,a] from pulling
A A-suboptimal arms Therefore, in subsequent analysis, we focus on bounding IE [Nra). To this end, we show the following lemma.
Lemma 5. For any suboptimal arm a, let S1, > O be such that E + E2 < An. Then its expected number of pulls is bounded as:
In (TKK(Ha +11,81 - -22) e²
1
E [r,a] $1+
kl(Ha +11,11 E2)
kl(po + t11,41 E2)
kl(Haa + E1 pa)
T
4
6n In
A
H
v
kl(M - E2, Hz)
tes and h(11, 62) ;= In (1-mite)mm of
where (1-mite2)(e ee
(11
Theorem follows immediately from Lemma 5 See section Cfor details; show sketch here.
Proof sketch of Theorem Fix any c E (0, H.. Let = cA.; by the choice of of < A.. From Lemma E NT. is bounded by Eq. Plugging in the values of = and using Lemma that lower bounds the binary KL divergence, along with Lemma 22 that gives H te2 and algebra, all terms except the second term on the right hand side of Eq. 7 are bounded by
(34
(
(1
-a
(11 A.
CTAR
^
ve2)
c2
(1 2c)²
C²A
in
+ A
As result, KL-MS satisfies that, for any arm a, for any E (0, 1):
[n(Tl((ju + c u1 - cAa)
E [Nr,al
kl(pa c cAa)
+
34
+
4
In
(!
[1 [1++A
TTAZ
Ve²
(1
2c)2
C
A A.
8

---

Theorem follows by plugging the above bound to Eq. 6 for arms a s.t. Aa > A with c == 1
5.1 Proof sketch of Lemma
We sketch the proof of Lemma in this subsection. For full details of the proof, please refer to
Appendix C.2 We first set up some useful notations that will be used throughout the proof. Let
W = In( Tki( +6101 -F2)lve))"""
We define the following events
te -ea)
A, (1, = a}. B, = {No. < u). C. {fr,max 2 M1 E2) D, = (Mr. S Mo + E1)
By algebra, one has the following elementary upper bound on E [Nr,a]: E [NTr,]] S
E
Intuitively, the u term serves to control the length of a "burn-in" (it+11ff [A,,
phase when the number of pulls to arm is most u. It now remains to control the second term, the number of pulls to arm after it is large enough, i.e., N1-1,a 2 u. We decompose it to Fl, F2, and F3, resulting the following inequality:
Nr,a Su
{A, Ct,,
Lt=++1
T
T +
+
Σ L=K+1
[ B C--1, D
{ B c
U==++
F:
F3
Here:
Fl corresponds to the "steady state" when the empirical means of arm and the optimal arm are both estimated accurately, i.e., 1,mx 2 j4 82 and f S Ma 51. It can straightforwardly bounded by klfn, +1,11-11)11- as we show in Lemma 10 (section D.1b
F2 corresponds to the case when the empirical mean of arm a is abnormally high, i.e., Pr- > P4 + E1. It can be straightforwardly bounded by tip..ei. we show in Lemma
[ (section [.2].
F3 corresponds the case when the empirical mean of the optimal arm is abnormally low, i.., f4-1,max S f41 E2; it is the most challenging term and we discuss our techniques in bounding it in detail below (section
We provide an outline of our analysis of F3 in Appendix D.3. and sketch its main ideas and technical challenges here.
We follow the derivation from Bian and Jun 11 by first using a probability transferring argument (Lemma(3) (3) to bound the expected counts of pulling suboptimal arm by the expectation of indicators of pulling the optimal arm with multiplicative factor and then change the counting from global time step é to local count of pulling the optimal arm. Then, F3 is bounded by,
20
Σ 1 (P())) Sn Eg exp(k: kl(A E2)
M2
Intuitively, each M, should be controlled: when exp(k: (((gg) 14 - 82)) is large, (oz).1 must significantly negatively deviate from (41 F2, which happens with low probability by Chernoff bound (Lemma 25). Using double integration argument, we can bound each Mr by
2HH
Mr
exp( expl_xkl(a kkl(jn -2,
Summing over all k we can bound F31 by O In ( e?) Rign - Combining the #
bounds on F'l and F2, we can show bound on E [N. similar to Eq. 7 without the "T ^" term
in the logarithmic factor. This yields a regret bound of KL-MS, in the form of Eq. 44) without the
eTA term in the logarithmic factor. Such regret bound can be readily used to show KL-MS's 4r.

---

Bernoulli asympototic optimality and sub-UCB property. An adaptive worst-cass regret bound of Vin KT In (T) also follows immediately.
To show that MS has tighter adaptive worst-case regret bound of v KT In (K), ). we adopt First, we observe that the looseness of the above bound on F3 comes from small & (denoted as F31
a technique in [3 24
Eich Mg), the summation of Mr for large l (denoted as F32 == Σx>H H M2) is well-controlled. The key challenge in better control of F31 comes from the difficulty in bounding the tail probability Aaa), for < H beyond Chernoff bound. To cope with this, observe that a modified version of F31 that contains an extra favorable indicator of 2Tn(T/))
(1)
denoted as:
I Aua S p1 -1-122 E2, (1((()))) 2ln (T/k) 11AAus
Σ E
k exp(k kl(A(s))), - -22)
can be well-controlled. Utilizing this introduces another term in the regret analysis, T PP(E))
where & {Av E [1, HJ, ((()))) (())))))))1)) 2lm(T/k) }. which we bound by O(H) via time- uniform version of Chernoff bound. Putting everything together, we prove a bound of F3 of O IH (Gr A H) V e²) + -=--22))))) which yields our final regret bound of KL-MS in Theo- rem and the refined minimax ratio.
Remark 6. Although our technique inspired by [24 331, we carefully set the case splitting
threshold for Nt-1,1 (to obtain F31 and F32)) to be H =0 te2 which is significantly different
from prior works (Ō(
One port our proof strategy back to sub-Gaussian MS and show that it achieves minimax ratio of vln K opposed to VInT reported in Bian and Jun [Л]]; sketch of the proof is in Appendix G Recall that Bian and Jun (I7] proposed another algorithm MS that achieved the minimax ratio of /In at the price of extra exploration. Our result makes MS obsolete; MS should be preferred over MS at all times.
Remark 7.
6 Conclusion
We have proposed KL-MS, KL version of Maillard sampling for stochastic multi-armed bandits in the [0, lJ-bounded reward setting, with closed-form probability computation, which is highly amenable to off- off-policy evaluation. Our algorithm requires constant time complexity with respect to the target numerical precision in computing the action probabilities, and our regret analysis shows that KL-MS achieves the best regret bound among those in the literature that allows computing the action probabilities with (polyyogg(1 /precision)) time complexity, for example, Tsallis-NNF 4 EXP3++ 40). in the stochastic setting.
Our study opens up numerous open problems. One immediate open problem generalize KL-MS to handle exponential family reward distributions. Another exciting direction is to design randomized and as good as IMED (21).
amenable algorithms that achieve the asymptotic optimality for bounded rewards (i.e..
One possible avenue is to extend MED 19] and remove the restriction that the reward distribution must have bounded support. Furthermore, it would be interesting to extend MS to structured bandits and find connections to the to characterize the optimal minimax regret rate for structured bandits. Finally, we believe MS is practical by incorporating the booster hyperparameter introduced in Bian and Jun ( Extensive empirical evaluations on real-world problems would be an interesting future research direction.
Coefficient [16). which have recently been reported
References
[1] M. Abeille, L. Faury, and C. Calauzenes. Iistance-Wise Minimax-Optinat Algorithms for Logistic Bandits. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3691-3699, 2021.
10

---

[2] S. Agrawal and N. Goyal. Analysis of Thompson Sampling for the Multi- -umtid Bandit Problem. In Proceedings of the Conference on Learning Theory (COLT), volume 23, pages 39.1-39.26, 2012.
[3] S. Agrawal and N. Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics, pages 99-107, 2013.
[4] S. Agrawal and N. Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1-24, 2017.
[5] J.-Y. Y. Audibert, S. Bubeck, and Others. Minimax Policies for Adversarial and Stochastic Bandits. In Proceedings of the Conference on Learning Theory (COLT), 2009.
[6] J.-Y. Audibert, S. Bubeck, et al. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pages 1-122, 2009.
[7] J.-Y. Audibert, R. Munos, and C. Szepesvári. Exploration-exploiiee tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410019):1876-1102 2009.
[8] J.-Y. Audibert, R. Munos, and C. Szepesvári. Exploration tradeoff using variance estimates multi-armed bandits. Theoretical Computer Science, 110(19):1866-1002 2009.
[9] Auer. Using Confidence Bounds for Exploitation-Explorrtion Trade-offs. Journal of Machine Learning Research, 3:397-422, 2002.
[10] Auer, N. Resa-Bianchi, Y. Freund, and R. E. Schapire. The Nonstochastic Multiarmed Bandit Problem. SIAM J. Comput., 32(1):48-77, jan 2003. ISSN 0097-5397. doi: 10.1137/ 50097539701398375
[11] Bian and K.-S. Jun. Maillard Sampling: Boltzmann Exploration Done Optimally, In International Conference Artificial Intelligence and Statistics (AISTATS), pages 54-72, 2022.
[12] A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122-442, 1996.
[13] O. Cappé, A. Garivier, O.-A. Maillard, R. Munos, and G. Stoltz. Kullback-leibler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, pages 1516-1541, 2013.
[14] N. Cesa-Bianchi, C. Gentile, G. Lugosi, and G. Neu. Boltzmann exploration done right. Advances in Neural Information Processing Systems (NeurIPS), 2017.
[15] O. Chapelle and L. Li. An Empirical Evaluation of Thompson Sampling. In Advances in Neural Information Processing Systems (NIPS), pages 2249-2257, 2011.
[16] D. J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The Statistical Complexity of Interactive Decision Making. CoRR, abs/21 12.1, 2021.
[17] A. Garivier and O. Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
[18] A. Garivier, H. Hadiji, P. Menard, and G. Stoltz. Kl-ucb-switch: optimal regret bounds for stochastic bandits from both distribution-dependenn and distribution-free viewpoints. The Journal of Machine Learning Research, 23(1):8049-8) 14, 2022.
[19] J. Honda and A. Takemura. An asymptotically optimal policy for finite support models in the multiarmed bandit problem. Machine Learning, 85(3), 201
[20] J. Honda and A. Takemura. Finite-time regret bound of bandit algorithm for the semi-bounded support model. arXiv preprint arXiv: 2012.
[21] Honda and A. Takemura. Non-asymptottic analysis of a new bandit algorithm for semi- bounded rewards. J. Mach. Learn. Res., 16:3721-3756, 2015.

---

[22] D. G. Horvitz and D. J. Thompson. A generalization of sampling without replacement from finite universe. Journal of the American statistical Association, 47(260):66366333 685. 1952.
[23] T. Jin, P. Xu, J. Shi, X. Xiao, and Q. Gu. Mots: Minimax optimal thompson sampling. In PMLR, 2021.
International Conference on Machine Learning, pages
[24] T. Jin, P. Xu, X. Xiao, and A. Anandkumar. Finite-time regret of thompson sampling algorithms for exponential family multi-armer bandits. In Advances in Neural Information Processing Systems, 2022.
[25] E. Kaufmann, N. Korda, and R. Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Proceedings of the international conference on Algorithmic Learning Theory (ALT), pages 199-213, 2012.
[26] N. Korda, E. Kaufmann, and R. Munos. Thompson sampling for 1-dimensional exponential family bandits. Advances in neural information processing systems, 26, 2013.
[27] T. L. Lai, H. Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22) 1985.
[28] T. Lattimore. Refining the confidence level for optimistic bandit strategies. The Journal of Machine Learning Research, 19(1):765-79)) 2018.
[29] T. Lattimore and C. Szepesvári. Bandit Algorithmss Cambridge University Press, 2020. URL httpp:://tor-latttinnoot comm://oommmmaaadaooooo/oooooo http:://aaa..llaaaaa..cccccoooop
[30] O.-A. Maillard. APPRENTISSAGE SÉQUENTIEL: Bandits, Statistique et Renforcement. PhD thesis, Université des Sciences et Technologic de Lille-Lille I, 2013.
[31] O.-A. Maillard, R. Munos, and G. Stoltz. A finite-time analysis of multi-armed bandits problems with kullback-leibe -eibler divergences. In Proceedings of the Conference On Learning Theory (COLT), pages 497-514, 2011.
[32] B. Mason, K.-S. Jun, and L. Jain. An experimental design approach for regret minimization in logistic bandits. In Proceedings of the AAAI Conference on Artificial Intelligenee, volume 36, pages 7736-7777777 7743,,7733170 2022.
[33] P. Ménard and A. Garivier. A minimax and asymptotically optimal algorithm for stochastic bandits. In Proceedings the international conference on Algorithmic Learning Theory (ALT), pages 223-237, 2017.
[34] Ménard and A. Garivier. A minimax and asymptotically optimal algorithm for stochastic bandits. In International Conference on Algorithmic Learning Theory, pages 223-237. PMLR, 2017.
[35] S. Mukherjee, Naveen, N. Sudarsanam, and B. Ravindran, Efficient-ucbv: An almost optimal algorithm using variance estimates. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 2018
[36] E. Novak. Some results on the complexity of numerical integration. Monte Carlo and Quasi- Monte Carlo Methods: MCQMC, Leuven, Belgium, April 2014, pages 161-183, 2016.
[37] F. Orabona. A modern introduction to online learning. arXiv preprint arXiv: /912. /32/3, 2019.
[38] J. M. Robins and A. Rotnitzky. Semiparametric efficiency in multivariate regression models with missing data, Journal of the American Statistical Association, 124429):122-129 1995.
[39] D. Russo and B. Roy. Learning to Optimize via Posterior Sampling. Mathematics of Operations Research, 3224):12 2014.
[40] Y. Seldin and A. Slivkins. One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning, pages 1287-1295. PMLR, 2014.
[41] W. R. Thompson. On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3/4):285, 1933.
12

---

[42] C.-Y. Wei and H. Luo. More Adaptive Algorithmss for Adversarial Bandits. In Proceedings of the Conference on Learning Theory (COLT), pages 1291, 2018. /Rthttp://axxiv org/abs/ haabs//8801.0320
[43] J. Zimmert and Y. Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. The Journal of Machine Learning Research, 22(1):1310-1355 2021.
13


Reviews:
[{"review_id": "zggwPqwNuW", "reviewer": "Reviewer_GStc", "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.\n\n\n\n", "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?\n\n2. 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. \n\n3. How does MS compare with KL-MS numerically? \n\n4. 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? ", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n", "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. \n\n2. 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).\"\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all responses and for taking the time to review our work and provide valuable feedback thoroughly.\n\n*(1) The plots in the appendix could be clearer.*\n\nWe appreciate the reviewer pointing out the problem. We will make necessary modifications to the plots to present them more clearly. E.g., for the plots in the appendix H, we will remove the (overlapping) vertical text and retain the legend to clarify the plot.\n\n\n*(2) What is the definition of pseudo-regret?*\n\nFor the definition of pseudo-regret, we follow the definition of [1, Eq. (1.4)]. This is the same as the 'expected regret' notion in the Fan & Glynn reference you gave (and probably what you meant by 'expected regret'). \n\nNote that another notion of 'expected regret' is in the literature [1, Eq. (1.2)]. We will add a remark in the final version, clarifying this terminology overload issue in the literature.\n\n*(3) The MAB results should be studied and stated beyond the ‘expected regret’ (in the sense of Fan and Glynn, 2021).*\n\nThanks for the reference. We agree that studying the tail property of the pseudo-regret (in the sense of Fan and Glynn, 2021) of MS is interesting and leave it for future work. \n\n*(4) How would the analysis change (or challenges in extending) if instead of Bernoulli-KL in the exponent, one uses KL (the lower bound opt.)?*\n\nBy the KL (the lower bound opt.), we think that you meant KL( empirical distribution of arm a, maximum empirical reward) in the sense of the KL defined in our line 119. If so, indeed this would be the MED algorithm. We don’t yet know how to adapt our analysis to provide a new analysis of MED; although we agree that this is an interesting question for further investigation.\n\n*(5) How does MS compare with KL-MS numerically?*\n\nWe added two plots in the global response to show an comparison between MS and KL-MS in the [0,1]-bounded reward stochastic bandits environments. KL-MS has lower regrets overall, due to its exploitation of the [0,1]-bounded reward structure. \n\n*(6) Does KL-MS work in a misspecified model setting, say the support of the reward set is [-0.5,0.5]?*\n\nIn this case, KL-MS may not work correctly: according to the KL-MS algorithm (Eq. (2)), KL is undefined if $\\hat{\\mu}_{t-1,a}$ is negative. \n\n[1] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems, 2012\n"}, {"review_id": "BQfyFt3Vbu", "reviewer": "Reviewer_Mj4M", "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. \n\nThis 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.\n", "questions": "I would like to read authors' opinion on the four main weaknesses that I raised.", "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].) ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "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).\n\nThe exposition is clear and I enjoyed reading the main body of the submission. \n", "weaknesses": "1.\nExponential 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. \n\n2. \nThe 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. \n\n3.\nThe 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.\n\n4.\nThe 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. \n\n\nOther comments / remarks / typos along the text:\n- 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 \n- Line 28: also Garivier and Cappé 2011 \n- Footnote 1: yes, but for known L and U \n- 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)\n- Line 48: the empirical averages \\mu_{t,a} were not formally defined \n- Lines 54-55: sounds like an overstatement; the submission proposes decent but not optimal distribution-dependent and distribution-free regret bounds \n- 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\n- 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 \n- Line 69: drop 'with'\n- Line 82: OK for this definition in case of absolute continuity, otherwise, = +\\infty\n- Lines 108-109: syntax issue\n- Line 119: > b, not \\geq b; this quantity is called K_inf \n- 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 \n- Lines 205-206: same kind of comments \n- Lines 239-241: there is no such issue if the Bernoullization trick of lines 115-119 is implemented \n- Line 258: rather (6) instead of (8)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for taking the time to review our work and provide valuable feedback thoroughly. We genuinely appreciate reviewers carefully examining our results and offering insightful comments to improve the quality of our research. We have carefully considered each of the weaknesses raised by the reviewer and committed to making the necessary revisions to solidify our arguments.\n\nAllow us to address each of the specific points the reviewer raised.\n\n*(1) The accuracy of computation of action probabilities of KL-MS and comparison against Thompson sampling.*\n\nIf we understand your concern, 'Exponential weights are actually difficult to compute in practice with a good accuracy' correctly, the imprecision of the exponential weight calculation comes from floating-point number underflow when evaluating the exponential function. This numerical imprecision is insignificant because it only affects the action probabilities by a minuscule additive factor of the smallest float value in the computer. \n\nAlso, if we consider the inconsistency brought by using the log data generated by KL-MS and TS, using TS inevitably introduces bias since the agent cannot access the actual generation probability, while in the KL-MS, it is not.\n\nPlease let us know if we have missed anything (we would appreciate it if you could elaborate on your concerns by, e.g., giving some references). \n\n*(2) The sub-UCB criterion could be omitted because it does not add anything.*\n\nOur paper focuses on a finite-time (i.e. nonasymptotic) analysis, and the sub-UCB criterion _does_ play an essential role in this view. More precisely, any algorithm satisfying the sub-UCB criterion guarantees not to suffer a higher regret order than UCB-like algorithms at any time. \n\nA typical example that illustrates the relevance of the sub-UCB property is in [1]’s section \"Failure of MOSS\", where it gives a bandit instance of K arms such that any sub-UCB algorithm has a regret at most O(K \\ln K), while in contrast, MOSS, a non-sub-UCB algorithm, has a regret of at least Omega(K^2), which is significantly larger when K is large. As another example, lines 148-150 (see also footnote 4) show that MED's best-known regret guarantee does not imply that MED is sub-UCB. Finally, recall from Table 1 that not all algorithms are sub-UCB. \n\n*(3) The comparison to previous works could be clarified and reorganized in pages 4--5.*\n\nThe current organization of the previous works is based on different criteria an algorithm satisfies. Thank you for your suggestion, we will add a discussion on the earlier UCB algorithm. Thank you for your reference on KL-UCB Switch. We will also add relevant discussions in the final version. \n\n*(4) Imprecise regret bound in Theorem 1.*\n\nWe appreciate the reviewer's careful reading. \n\n* We had a typo in theorem 1 (and Lemma 8): '$\\Delta > 0$' should instead be '$\\Delta \\geq 0$' (note that the proof of Theorem 1 continues to hold when $\\Delta = 0$, specifically the equation display in line 439). \n\n* The + / - $\\Delta_a$ terms in the main term is standard in the analysis of Bernoulli bandits, similar to the $\\varepsilon_1$, $\\varepsilon_2$ factors in standard KL-UCB analysis [Lattimore and Szepesvari, Bandit Algorithms, Theorem 10.6]. \n\n* Note that in the downstream applications of Theorem 1, we do not always choose $\\Delta \\ll \\ln T / T$ (although $\\Delta \\ll \\ln T / T$ makes sense for showing asymptotic $\\ln T$-style regret bounds): for example, in the proof of worst-case regret bound Theorem 3, we chose $\\Delta = \\sqrt{\\dot\\mu_1 K \\ln K / T}$.\n\n* Throughout this paper, big O only hides absolute constants. The main reason we present KL-MS's regret bound in this form is its flexibility in deriving asymptotic and nonasymptotic regret guarantees: to derive asymptotic guarantees, we choose $\\Delta = 0$ and treat the terms inside the big-O as lower-order terms; to derive nonasymptotic properties such as sub-UCB or worst-case regret guarantees, we are generous in giving up constant factors and apply Lemma 8. We will correct the typos and add these clarifications in the final version.\n\n*(5) the proof sketches are too vague.*\n\nWe refer the reviewer to the global response for a recap of our proof sketches and technical highlights.\n\n*(6) Minor comments.*\n\nThank you for these; we will make a pass over our paper to incorporate them. \n\n* Reorganizing Table 1: if we include Tsallis-INF, it also seems to make sense to include other randomized exploration algorithms, such as: EXP3, EXP3-IX, and the Boltzmann-Gumbel exploration algorithm [5] (and many others), which, although can maintain closed-form action distributions, do not have sharp regret guarantees in the stochastic setting, such as asymptotic optimality in Bernoulli case and sub-UCB. Nevertheless, we are open to any suggestions that can help elucidate comparisons between our algorithm and previous works.\n\n\n[1] T. Lattimore. Refining the confidence level for optimistic bandit strategies. Journal of Machine Learning Research, 19(20):1–32, 2018.\nURL http://jmlr.org/papers/v19/17-513.html\n\n[2] Agrawal, S., & Goyal, N. (2017). Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5), 1-24.\n\n[3] Garivier, A., Hadiji, H., Menard, P., & Stoltz, G. (2022). KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints. The Journal of Machine Learning Research, 23(1), 8049-8114.\n\n[4] Cesa-Bianchi, N., Gentile, C., Lugosi, G., & Neu, G. (2017). Boltzmann exploration done right. Advances in neural information processing systems, 30.\n"}, {"review_id": "3UtPBN6NZu", "reviewer": "Reviewer_QYoJ", "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. ", "questions": "Please see the above \"Weaknesses\"", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The regret bound in this paper is nearly tight.\nThe 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). \n\nMy 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.\n\nFinally, 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for taking the time to review our work and provide valuable feedback thoroughly.\n\n*(1) Why do we need the exact action distribution in reality?*\n\nOur motivation comes from the broad field of off-policy evaluation and optimization for contextual bandits and reinforcement learning, where learners use previously-collected logged data to make inferences about the unknown environment [1]. For example, in an online advertisements recommendation system, before deploying a new policy, the platform would like to evaluate its performance using historical data (collected by previous policies), possibly for safety considerations. As we demonstrated in the experiments, Thompson Sampling, albeit having good regret performance, when combined with Monte Carlo estimation of action probabilities, yields logged data that produces reward estimates that are less reliable than that of KL-MS (which instead maintains closed-form action probabilities).\n\n*(2) Regret comparison between algorithms.*\n\nSince we focus on the performance of offline policy evaluation, we put the most essential plots in Appendix H. We now include two experimental evaluations on the comparison between KL-MS, MS and Thompson Sampling in the global response for your reference.\n\n*(3) Generalizing KL-MS to an infinite-arm case.*\n\nWe agree that this is an interesting topic and leave it for future work.\n\n[1] Saito, Y., Udagawa, T., Kiyohara, H., Mogi, K., Narita, Y., & Tateno, K. (2021, September). Evaluating the robustness of off-policy evaluation. In Proceedings of the 15th ACM Conference on Recommender Systems (pp. 114-123).\n"}, {"review_id": "cDd8c7tt8q", "reviewer": "Reviewer_nCy6", "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. \n\nKL-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.\n\nContrarily 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.", "questions": "I don't have specific questions for this work, everything seems clear to me.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "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.\n \n*  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.).\n  \n* 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. \n\n* 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.\n", "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.\n\n* 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. \n\n* Minor: the authors should cite a recent follow-up of Honda and co-authors on the MED algorithm: https://arxiv.org/abs/2303.06058 \nThis 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for taking the time to review our work and provide valuable feedback thoroughly.\n\n*(1) The shared common mechanism with MED and KL-MS.*\n\nWe agree with the reviewer that under Bernoulli environments, our algorithm and MED are identical. The main reason we see our algorithm as a 'Maillard sampling'-style algorithm is that its action probabilities are calculated only based on empirical mean rewards of all arms. In contrast, MED algorithms and their variants compute action probabilities based on a notion of 'empirical divergence' that relies on the full empirical distribution of rewards.\n\n*(2) The novelty of our paper should be appropriately highlighted.*\n\nWe include the most challenging part in Appendix D.3.1, \"Roadmap of analysis of F3,\" and highlight some critical techniques that can be of independent interest. For example, extending MS to the KL version is not trivial and requires much work. Also, choosing a separating point in F3 takes a lot of work to find. Please also see our global response for a recap of our analysis and technical highlights.\n\n\n*(3) Reference [1]*\n\nThank you for the reference. Indeed, [1] gives randomized and off-policy-amenable algorithms that achieve asymptotic optimality for unbounded rewards, which answers our question in lines 298-300. However, it does not (yet) yield easily interpretable finite-time regret bounds, which we believe is an important research direction.\n\n[1] D. Baudry, K. Suzuki, and J. Honda. A general recipe for the analysis of randomized multi-armed\nbandit algorithms, 2023.\n"}]

Author rebuttal:
We thank all reviewers for taking the time to review our work and provide valuable feedback thoroughly. Here we address two common points shared by reviewers.

**The comparison between algorithms in terms of regret.**

We chose the reward setting following the experimental setup of Thompson sampling literature [1], where we consider two 2-arm bandit environments with expected rewards being [0.2, 0.25] and [0.80, 0.90] respectively, with 2000 time simulations to estimate the regret of KL-MS, MS and Thompson Sampling. Our result (see attached PDF file) shows that in terms of performance: (1) KL-MS is better than MS by exploiting the variance information of all arms; (2) KL-MS performs worse than Bernoulli Thompson Sampling; we suspect that this is due to Thompson sampling exploiting more aggressively in such relatively-easy environments. 

**The proof idea and the novelty in the analysis (R2, R4).**

Since the focus of our paper is on establishing both asymptotic and finite-time regret guarantees for the KL-MS algorithm (specifically, asymptotic optimality in Bernoulli setting, sub-UCB property, $\sqrt{ \dot\mu_1 \ln K }$ minimax ratio), we need to give a finite-sample bound on $\mathbf{E}[N_{T, a}]$, the expected number of pulls to suboptimal arm a. To this end, we divide it into four parts (divisions similar in spirit is standard in the analysis of bandit algorithms, e.g. [1, Eq. (2)]), and bound each part respectively. The four parts are: 

* u, a burn-in term, 
* F1, which corresponds to the "steady state" when the empirical means of arm a and the optimal arm are both estimated accurately;
* F2, which corresponds to the case when the empirical mean of arm a is abnormally high; 
* F3, which corresponds to the case when the empirical mean of the optimal arm is abnormally low. 

As we mention in lines 272-275, bounding F1 and F2 are relatively straightforward, similar to the MS analysis [3]. Our main technical challenge lies in the analysis of F3. For that term, we had a detailed 'roadmap of analysis' in Appendix D.3.1 that explains our intuition and the main techniques used. 
Of these, we wish to highlight two techniques from our paper that can be of independent interest: 

* a careful double-integral argument that simplifies prior works that bounds the expectation of a certain function of the empirical reward using a tail probability bound on the empirical reward, which already establishes Bernoulli asymptotic optimality, sub-UCB property, and $\sqrt{\dot\mu_1 \ln T}$ minimax ratio (lines 481-487). This effectively mimics a “peeling argument” over uncountably infinite layers. We can avoid unnecessary analysis by using the double trick instead of deploying a fine-tuning peeling device as in [2], which may become frustrating in the Bernoulli case.

* To further establish a $\sqrt{\dot\mu_1 \ln K}$ minimax ratio, we conduct refined analysis on F3 by splitting the cases based on whether the value of $N_{t,1}$ exceeds H, a new choice of threshold that ensures adaptivity to $\dot\mu_1$ (lines 498-512 and Remark 7).

We apologize that the important Appendix D.3.1 (which carries our intuition and summarizes the key techniques) was not linked from the original main submission; we will add that link from the main paper in the final version.

[1] Kaufmann, E., Korda, N., & Munos, R. (2012, October). Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory (pp. 199-213). Berlin, Heidelberg: Springer Berlin Heidelberg.

[2] Agrawal, S., & Goyal, N. (2017). Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5), 1-24.

[3] Bian, J., & Jun, K. S. (2022, May). Maillard sampling: Boltzmann exploration done optimally. In International Conference on Artificial Intelligence and Statistics (pp. 54-72). PML

Meta-review: The reviewers came to consensus that this paper has strong contribution in the context of randomized bandit algorithms. On the other hand, many presentation issues are raised such as the experiments, positioning of the algorithms and relation with existing work. I determined to recommend acceptance but I also agree with the opinions that the paper needs through revision on the above presentation issues. I strongly expect that the authors seriously take these comments and improve the paper in the final version.
Decision: Accept (poster)