Fast Asymptotically Optimal Algorithms for Non-Parametric Stochastic Bandits
Authors: Dorian Baudry
Fabien Pesquerel
Rémy Degenne
Odalric-Ambrym Maillard
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-Armed Bandits
TL;DR: We propose computationally efficient variants of some optimal non-parametric bandit algorithms.

Abstract: We consider the problem of regret minimization in non-parametric stochastic bandits. When the rewards are known to be bounded from above, there exists asymptotically optimal algorithms, with asymptotic regret depending on an infimum of Kullback-Leibler divergences (KL). These algorithms are computationally expensive and require storing all past rewards, thus simpler but non-optimal algorithms are often used instead. We introduce several methods to approximate the infimum KL which reduce drastically the computational and memory costs of existing optimal algorithms, while keeping their regret guaranties. We apply our findings to design new variants of the MED and IMED algorithms, and demonstrate their interest with extensive numerical simulations.

Fast Asymptotically Optimal Algorithms for Non-Parametric Stochastic Bandits
Dorian Baudry
Fabien Pesquerel
Ecole Polytechnique, CREST
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France fabien. babiee..esqueree@inne pesquerel@inria.f fr
Palaiseau, France dorian. baudry@ensae fr
Rémy Degenne
Odalric-Ambrym Maillard
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRISIAL, F-59000 Lille, France remy. deng.ddeeene@iiri.frr
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRISIAL, F-59000 Lille, France
odalric, malaaiicmilllrdiiniiii...
Abstract
We consider the problem of regret minimization in pe-paarameticc stochastic bandits. When the rewards are known be bounded from above, there exists asymptotically optimal algorithms, with asymptotic regret depending an infi- mum of Kullback-Leibler divergences (KI.). These algorithms are computationally expensive and require storing all past rewards, thus simpler but non-optimal al- gorithms are often used instead. We introduce several methods to approximate the infimum KL. which reduce drastically the computational and memory costs of existing optimal algorithms, while keeping their regret guaranties. We apply our findings design variants of the MED and IMED algorithms, and demonstrate their interest with extensive numerical simulations.
1 Introduction
A Multi-Armed Bandit (MAB) is sequential decision-making problem where at each time step t E a learner collects reward from an arm A, chosen among E N alternatives. We consider the stochastic case, in which all rewards collected from an arm k E [K] are i.i.d. and drawn from fixed distribution Fk. of expectation μgg. For time horizon T we define the number of pulls an arm by
(T) Σ T(A, = k). and their sub-optimality gap by A = Ju" - /4k, with µz = maxie]K] Pk- The goal of the learner is to maximize their expected sum of rewards, or equivalently minimize the regret, defined as
1=
T Σ (p*
K Σ (E
R2 E
MA.)
To achieve this goal, the learner can leverage the rewards collected up to time / and their knowledge on the family of distributions F to which Fr belong. The definition J determines the complexity of the bandit problem, since any uniformly efficient algorithm' satisfies the lower bound [Lai and Robbins, 1985, Burnetas and Katchakis, 1996]: for all [K] with A > O,
iim (T)] log(T)
1
KJT (TT(Fa inf (KL(FR, :):Eo| 43) GET
(2)
(FF,
V(F...., FR) FK; Va > 0. E[Nx(T) = o(I")) ) for all & satisfying A. >
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

where (L(...) denotes the Kullback-Leible divergence between two distributions. We call an algorithm asymptotically optimal (sometimes shortened to optimal) its regret upper bound matches this lower bound. That is, if for all k. lim - [B(N log(()) 1 Kr k²).
For some parametric families (e.g. Gaussian), K has a convenient closed-form expression. However, for more general non- non-parametric families of distributions this may not be the case. In this work we consider the most famous example of such model, where the learner only knows that the distributions are bounded. Given range (b, B), we formally define
FI..81 = (F& E P(IR) supp(F) C [b, BJ C CR),
but in the rest of the paper we keep the notation F (for F(b,B)) for simplicity. We always assume that B is known, but in some cases knowing that b is finite will be sufficient. By analyzing a dual optimization problem derived from (2), Honda and Takemura [2010] obtained that
YEEF, :
(F. = max Ex-F [log (1 - A (X)
(4)
AE AE(0.=-11
Optimal algorithms for bounded distributions The literature on MABs has become diverse in the past years, so in the following we present a won-exhaustive selection of works that focus on asymptotically optimal algorithms for (bounded) stochastic bandits. We refer the reader to [Lattimore and Szepesvári, 2020, Bubeck et al., 2012] for broader surveys.
The most famous optimal algorithm is certainly KL-UCB [Cappé et al., 2013, Agrawal et al., 2021]. Based on the principle of optimism in face of uncertainty [Auer et al., 2002], it uses confidence intervals on empirical K to choose the arm with the largest plausible mean. The optimality of KL-UCB was only proved recently [Agrawal [2013] only proved it for Multinomial distributions. A second family of algorithms, Minimized Empirical Divergence (MED) [Honda and Takemura, 2010, 201 1, 2015, Baudry et al., 2023], aims at exploiting the lower bound (2): these algorithms are based on the computation of AC for the empirical distributions and the current best empirical mean, and hence differ from KL-UCB (they perform only one computation per arm/step). More recently, an optimal algorithm based on Thompson Sampling (TS) [TThompson, 1933] was proposed for general bounded distributions, under the name of Non-Parametiic Thompson Sampling (NPTS) [Riou and Honda, 2020]. In this work, the authors generalize the TS algorithms for Bernoulli distributions [Agrawal and Goyal, 2012, Kaufmann et al., 2012] by using an improper Dirac prior and Dirichlet posterior.
al., 2021], as the seminal work of Cappé al.
Throughout the paper, we use "MED algorithms" (or simply MED) refer to the family of algorithms. We denote by MED the randomized algorithm presented in [Honda and Takemura, 2010], that we detail in Algorithm 3, and IMED its deterministic counterpart ([Honda and Takemura, 2015], Algorithm 2).
Cost/performance trade-off In practice, the choice of bandit algorithm may be motivated by its theoretical guarantees, but also by its computation and memory costs. Unfortunately, optimal algo- rithms are quite costly: MED and KL-UCB need to compute an empirical K (costing Onn log(n)) for n samples, solving (4) with precision 1/n) for each arm/round, KL-UCB being more costly (sev- eral K/ per step), while the cost of sampling in NPTS is linear in the number of samples of each arm. For that reason, cheaper sub-optimal alternatives are often considered in place of optimal algorithms. For instance, UCB [Auer et al., 2002] has constant run time and memory, and achieves a logarithmic regret with multiplicative constant O (E AE I) More generally, all the algorithms designed for //4--ubb-gaussiar distributions can be used on F if the rewards are rescaled in [0, 1]. A finer approximation consists in using the KI. divergence of Bernoulli distributions, that lower bounds K [Cappé et al., 2013]. However, it is important to note that these approximations are sensitive to the value (and knowledge) of the lower bound of the support b (as rescaling in [0, 1] is necessary). contrarily to asymptotically optimal algorithms. Pushing further this idea, a procedure proposed by Riou and Honda [2020], inspired by Agrawal and Goyal [2012], consists in discretizing the rewards: a reward X E [b. B] is transformed in Y E X = {x1 b, b...., ZM B} for some finite grid X, such that E Y X = X. Hence, the expectations of the arms are unchanged while the memory is reduced to (M and the computation time of K for discretized distributions is proportional to M. Unfortunately, even if all these techniques lead to logarithmic regret, the multiplicative constant before (Tg can be arbitrarily large compared with the optimal one. More precisely, we show in Lemma 6 that for a small gap A the ratio K.F AA2 can be of order -1 We detail this result and the description of the discretization procedure in Appendix D.
2

---

We illustrate this gap with an example from [Baudry et al., 2021a], that consider problem of crop-managee nop-management optimization agriculture. In Figure 1, we represent four distributions of crop yields generated from the DSSAT simulator [Hoogenhoom et al., 2019], corresponding to different crop-management policies. The distributions are naturally bounded due to the physical constraints of the problem and are non-parametric. In Table 1 we compare K to the Bernoulli KI.-divergence, denoted by kl (see (16) for definition), and to A for each arm, and we obtain on the 4-armed bandit that regret bound scaling with kl or 2 is almost 10 times larger than the asymptotically optimal regret defined by (2). We include this problem our experiments of Section to check the practical consequences of this asymptotic property.
Pg (Dpt.) == 36330
(TL(FE))))) 227
3013
Dist.
density
3317
F2
4.4
4.72
F3
11.73
12.44
3396
F4
12.04
12.73
Table 1: Comparison of Ki kl and 24 & for each sub-optimal arm.
200 4204
.000
10001
value
Figure I: Four yield distributions from DSSAT, and comparison of K kl, and 2
Algorithm
Run time
Memory
Optimality
KL-UCB [Cappé al., 2013]
On log(n))) (log(n))
n ((1)
Opt. Sub-opt. (kl) Sub-opt. (24
kl-UCB
UCB [Auer et al., 2002]
((1)
O(1)
NPTS
[Riou and Honda, 2020]
((n)
n
Opt.
MED/IMED
[Honda and Takemura, 2015] Mult. MED/IMED (M items)
On log(n)
n
Opt.
O(M log(n))
((M)
Sub-opt. (C mult.)
FMED/FIMED (this paper)
On log(n)) if pulled, O(1) otherwise.
Opt.
(Theorem I) Opt. under assumptions of T'Therem
OMED/OIMED (this paper)
((1)
O(K)
Table 2: Comparison of memory and run time needed per step and for arm k with observations
Outline and contributions The results presented in previous paragraphs motivate the search for novel cheap and asymptotically optimal non-parametric bandit algorithms. We build on MED to propose two novel approaches that achieve this goal. We first propose FMED (resp. FIMED) as a fast variant of MED (resp. IMED), that computes K/Lr only for the arm that is pulled while for the other arms a first-order Taylor expansion is used. This simple change translates to a considerable speed-up of the algorithms, as for large enough horizons the best empirical arm (for which K is 0) is pulled most of the time, and preserves the theoretical guarantees of the two algorithms. However, FMED and FIMED still require store all rewards and fully compute K (sometimes). Hence we propose another approach, in which estimates of K are computed using an online portfolio selection algorithm. We highlight a property that would ensure that such an algorithm also keeps the guarantees of MED and IMED, while having much faster computation time and at most (KK2) memory.
Decision Support System for Agrotechnology Transfer
3

---

The novel algorithms are presented in Section 2, while we discuss their guarantees in Section 3. Finally, in Section we perform numerical simulations that confirm the benefits of our novel algorithms in terms of computation time, and show their strong empirical performance. Table 2 summarizes our results. We detail all computations in Appendix F.1.
Fast MED algorithms
In the following, we denote by (t)(t), (t(() and (²(t) max; (t((t) respectively the empirical distribution and mean of arm k and the best empirical mean at time t. We propose fast variants of MED and IMED, that avoid computing (F. (t))
for each arm and at each time.
2.1 On-access update and linearization: FMED and FIMED
We use that K is non-decreasing and convex in its second argument (Lemma 2, prop. 1). Given F E F and two thresholds (1) E [b, BJ and assuming that (F, μj) and its derivative (w.rt p)) have already been computed and are available in memory, we can use that
DIG Op (F,1)(a' 44)
(F. (F, +
(5)
This inequality is cheap approximation of jut from below when only the second argument changes: as long as E [K] is not pulled its empirical distribution (t) is constant. Furthermore, the derivative is equal to the maximizer of (4) [Honda and Takemura, 2015], which is provided at no additional cost when computing K Using this result, we propose FMED and F FIMED as fast variants of MED and IMED respectively, for which at each time step (F)
(1). p² (t)) replaced by
[t,(t) max {0, (
(t), (" (sx(t))) + (s (t)) x (μ* (t) - μ³ (sx(s)))))
(6)
where (t) sup {s < t: A. 13) is the time of last pull of arm & before and for E N.
{s(s)= argmax (x) [log(1 X(X 1 (s)))
LB(0((B-='())
We detail their implementation in Appendix A.2. Despite its simplicity, this method already permits huge gain of computation time. Indeed, in Theorem (see Section 3) we prove that each sub- optimal arm is pulled only (log T') in expectation, which is thus the expected number of full K computations. Additionally, at most one K- is computed at each stage, while for MED/IMED K computations are required. However, FMED/FIME still require keep every sample memory. This motivates us to investigate an alternative approach in the next section.
2.2 Sequential update: OMED and OIMED
We now propose bandit algorithms that update (Fi, pt))) a purely sequential fashion, for any arm k. We use that its formulation as a maximization problem (4) can be reformulated as an online portfolio selection problem, class online convex optimization problems. In the following we drop the index k to simplify the presentation, and thus use the notation N(t) and F(t) for the sample size and empirical edf of the selected arm at time t, and by X, the n-th observation collected by this arm.
Formulation Online portfolio selection is sequential interaction between a learner and an adver-
sary. Before the interaction, the adversary selects (#n)ne(N] E TR Nxd for dimension d > 2. At iteration n E the learner chooses An Ad S Rd (the simplex of dimension d 1) and receives the reward log(A,, xx). The regret of the learner after N iterations is defined by
RN(D .I....... (n)
max Σ XEA
log(A xn.)
Σ log( (2 x
The objective of the learner then to find a sequence (An)neN, where An depends only on (A1, Zi,.... .,, Ap- In-1), that minimizes Ry. We now express the computation of (F(t)

---

as portfolio selection algorithm in dimension 2,
N(t) Σ log aa)())))) AEA2
with with -(1 B Xn 1 (1)
(FO))
mmxx
However, this expression is unpractical since z1 (t)...... (t) all depend μu" (t), that is not revealed before time t. At the n-th iteration, we can only use the current best empirical mean, denoted by 1 for simplicity: a portfolio algorithm can only try to minimize Ry (Z1,..... .NN. with In (1, [ ( ). We call that quantity portfolio regret in the rest of the paper.
On the other hand, if μú diverges too often from μ² (t) the estimation of K will not be accurate. We define the bias of the portfolio algorithm (or portfolio bias) by
Na(e)
NOO Σ log (A (ATxn(t)) xx)()) XE ==
(R (t))) =
max XEA2
Σ ==
log(A (0(AATn)>=
max
(8)
This term can be studied independently of the portfolio regret and only depends on the variations of the best empirical mean. It is not negligible: we will have to modify the structure of the MED algorithms and assume that the best mean is not too close to B to control its magnitude.
In summary, and using all the previously introduced notation, at each stage we propose to approx- imate N (tt (t)) by LN(e) Σ In=1 log(A,Tzz,) where An is updated sequentially by a portfolio algorithm. Furthermore, the accuracy of the estimate can be expressed in terms of the portfolio bias and regret follows,
N (())
LN(s) + RN(o) + ( (t))
(9)
the theoretical results presented in Section are hence obtained by bounding these two quantities.
Portfolio algorithms See [Tsai et al., 2023] for a recent review of portfolio selection algorithms. Different methods vary based on their computational complexities and their regret. Some have regret upper bounds low Odd T) but computationally expensive, like UPS [Cover, 1991, Cover and Ordentlich, 1996, Kalai and Vempala, 2002]. Our goal is to use portfolio methods to obtain a computationally efficient A hence we cannot use those. On the other hand, we can afford a looser regret upper bound since we will use it on O(log T) samples from the sub-optimal arms. Other algorithms have (d) computational complexity per round, which is cheap in our case where d = 2. This is, for example, the case for Soft- [Orseau et al., 2017]. which has regret O(VIT). Other algorithms achieve intermediate raade-offs: see [Zimmert et al., 2022. Tsai et al., 2023]. Among the computationally cheap algorithms, we chose Soft- oott-Bayes for its simple implementation and the fact that Orseau et al. [2017] provide bounds on the regret valid for an adaptive step-size parameter, which we need since we don't known the total number of samples we will see for the arms.
While we are the first to use a portfolio algorithm to estimate X:F in a bandit algorithm, the link between /C and portfolio selection was previously used in [Agrawal et al., 2021, Lemma E. where the authors use the existence of a portfolio algorithm with logarithmic regret obtain concentration inequality on K.F. However, they only use that observation to obtain a bound for the analysis and they don't explore any algorithmic use of the portfolio formulation.
Furthermore, our theoretical analysis is based on a non-standard assumption, that the regret of the portfolio al algorithm admits sub-linear upper and lower bounds. We discuss this assumption in the next section.
Algorithm structure of OMED and OIMED We introduce the OMED and OIMED algorithms for generic portfolio algorithm. As discussed above, using an online estimate of empirical Kig makes the MED algorithms highly sensitive to variations of the best empirical mean. For this reason, we apply several structural changes to the algorithms in order to prevent the portfolio bias be large, and assume the knowledge of an upper bound Pmax p with Mmax < B.
First, we use a duel-based algorithm: inspired by Chan [2020], each round t we define a leader as l E argmax (t).) Then, the other arms (called challengers) compete against the leader in pairwise
tiies are broken in favor of the arm with best empirical mean, then at random if several candidates remain
5

---

Algorithm Online Indexed Minimum Empirical Divergence OIMED
Input: K arms, B, portfolio selection algorithm ALG (and its parameters), function f. Mmnxx Initialization: Pull each arm once. v(k, !) E [K] set N₂ 1, Nr.t 0, Rig XR,11 Lige
Aue = 1/2 (init. for ALG).
for i 1 K do
Set A = {). choose leader & E arg maxRE[K] N&
b Break ties comparing (mx)
for k * & do
if No & f(Nu,e) or fie 2 Mmax then (if Pi 2 fie then add & to A, set Z 0); b Greedy
else (if L,,E + log( Nk,e) & log(Ne) then add lo to A, set Zz 1);
IMED duel
if A- =0 then add / A, set Zt 0:
Pull leader if challenger
for l: E A do
Pull k observe reward X, update ūik, No-
b General update (even if Z& 0)
if 2* = 1 then
Update Xu,e with ALG, knowing Nu.e and B-X B-pi
D Portfolio update
No. + No.e + 1, Luge f- Lige + log du.e X Re A
comparisons called duels. At the end of the round, all winning challengers (if any) are pulled. If there none, the leader is pulled. Hence several arms can be pulled per round. The main ideas are to replace μ² (t) by pe, (t) for the reference value used by the challengers, and to implement a different Kinn estimate Lx,e, (t) for each possible pair (k, l)).
We now introduce some notation and terminology to describe the duel between a challenger & and leader L. In some cases (described below) perform greedy duel, for which the winner is } We introduce a variable [t), that indicates if the duel played by arm & was greedy (t) = 0) or not (Za. (t) 1), and then (t,,(t)= = Σ'=l I(k: E Ast1, = =,, (s()) = =1), the number of observations of challenger i collected against the leader i after a non-greedy duel.
(t)
Using this notation and considering a function f N + R+ satisfying n (n)), the duels of OMED/OIMED are implemented follow: if Ne(() & f (()),.(() or pe(l) > Mmax the duel is greedy, otherwise MED and IMED are respectively adapted as follows.
Non-greedy OIMED duel:
k wins if Lx,((t) + (og(Nt,e(t)) & log((N((t).
(10)
Non-greedy OMED duel:
l wins if W&(t) = with (t) Ber e (c-...(())
(11)
Then, we update (t,)(() using the portfolio selection algorithm only if the duel was non-greedy, i.e. (t) = providing (I) and the reward collected from le this the main ingredient to control the portfolio bias in our analysis. We provide condensed implementation of OIMED in Algorithm 1, and the detailed implementation of OKED Appendix A.2 (Algorithm 6).
Theoretical guarantees
We present theoretical results the MED algorithms introduced in Section and some insights from their analysis. We start with the theoretical guarantees of FMED and FIMED.
Theorem (Regret bound for fast MED). Consider (F1,.... Fx) FK and p² max:e[K] Pk- Then, for any time horizon T E N and 8 > 0, MED, INED, FMED and FIMED all satisfy
log(T)
E (NN(
(( + + (log(T))
(12)
where (l(o))TT) denotes term that is asymptotically dominated by log(T) for a fixed e. but with polynomial dependency in =1_ Furthermore, all the algorithms are asymptotically optimal.
We prove Theorem in Appendix B. The main result that FMED and FIMED both preserve the theoretical guarantees of their original algorithm. We apply analysis MED and IMED too, in

---

order to exhibit more precisely the new terms induced by the approximation, and their scaling in Note that the components of the or (l)) terms are explicit in the proof. When is small, we obtain more precisely scaling in & that allows to obtain a sub-linear problem-independent bound of order 76/6, though not the optimal vT bound. Note however that the same scaling can be obtained for MED with the proof techniques presented in [Baudry et al., 2023], so the fast implementation do not deteriorate that bound. The strong empirical performance of MED/IMED hints that this result is likely to be not tight, but to the best of our knowledge it remains open to prove that an optimal* (instance-dependent) algorithm achieves the ((VT) moblem-indeeendent bound for general bounded distributions. Finally, we emphasize that the analysis of IMED presented in Appendix B is drastically simplified compared to Honda and Takemura [2015], although their result is more general (they allow b -00).
Proof sketch. First, the inequality Ke(() > (Fx())))))))))))))))))))())))) (()) (Eq. (5) and (6)) makes FMED and FIMED least exploratory as the vanilla algorithms. Their regret is thus smaller in pre- convergence regime, defined by the time steps for which (²(() & ne¹ S. The main challenge then to prove that using (K)(t))eE(R) do not lead over-exploration of the sub-optimal arms in post-convergence regime, where 1 (t) >/2 nu* c. The main ingredient of the proof consists in showing that this kind of scenario can only be caused by events of the form
3j E [K] : {A++1 = N,)) Hy > n² + or {Ai+1 (t) = n. Myn < p - =}
Each of them can cause at most 1 pull of a sub-optimal arm. With union bounds and Hoeffding's inequality we obtain an additional (s) term in the regret bound compared to MED and IMED. O
We now provide a very similar result OMED and OIMED, under some additional assumptions: first, we need the largest mean to be well-separated from B to control the portfolio bias. This is a mild assumption, since the decision-maker can also choose to slightly increase the value of B used by the algorithm if it does not clearly hold. Then, we require strong guarantees on the portfolio regret, that discuss at the end of this section.
Theorem 2 (Regret bound for online MED algorithms). Consider (F1...., Fk) E FK, and n² [aX Pa < Pmmxs for a known Pmax < B. Assume that OMED and OIMED use a portfolio selection algorithm ALG that satisfies for any (kc, f) E [K]² and n E N the deterministic guarantee
R... = o(n) (sub-linear absolute portfolio regret).
(13)
Then, both OKED and OIMED satisfy Equation (12) (with different second-order term) and are asymptotically optimal: they enjoy the same asymptotic guarantees as MED and INED
Strikingly, the performance of OMED/OIMED only depend on the regret bounds of the portfolio regret. As detailed below, this is largely due to our modified algorithm's 's structure.
Proof sketch. The general proof scheme is inspired by [Chan, 2020], that proposed a similar duel-based approach. The main difficulty consists in controlling the deviation of LR,r, (1) from
K/ (Fr,,, (t), Me, (t)), denoting by FA,,, (t) the empirical distribution of the Nk.e, (t) observations used to update Lx,e, (t). Both over and under-estimation are bad: one may prevent sufficient explo- ration of the best arm, while the other may lead evereexplonation of sub-optimal arms. Building on the discussion of Section 2, our proof relies on the following crucial result: for fixed arms (k, L).
sample size Nt.e(t) n. and any threshold μ holds that
(14) where Bk (1)) is the portfolio bias with respect to fixed threshold μ., defined in (8), and where L and Fx.e, are used to denote (t) and Ft,e(t) when Ne.((t) = n, for simplicity. In the proofs, the portfolio regret is controlled by assumption, but the bias requires more careful examination. To analyze it, we prove the following result (details in Appendix E). For & n, we denote by 4x,r, the time when the i-th iteration of Le,t, occurred.
nk (r,,, 11) = LI,e, + Ra,e, + (E),,
Le. with bounds depending K2 and not A or kl
7

---

Lemma 1 (Deviations of (u.),((i)) Let (0,1), 1), and set CR,pa B B-uelleaa.) it holds that B-
Σ log (Cits) ((ue()) 2 1)) & (p)
log (Cr,e.) li(u 2 vellnas)) (15)
We always use this result for μt E (maxkkus <n" Pk 1² and (e((a,e,)) < Mmax. Hence, the upper bound (resp. lower bound) of (15) is expected to be sub-linear when { f== (resp. * 1), thanks to the use of different estimates according to the leader's identity. The rate of convergence of these sums is also important: our proof techniques work if n = o(Ne(fz,e,)), which justifies the greedy duels. Indeed, we need e < -x) to be small enough (for some a, x > and large n), and with this trick we obtain E f(n)y= > (for some y/2 depending on X).
The modifications introduced in OMED and DIMED guarantee small absolute bias with large probabil- ity. is natural to ask whether they are necessary. We cannot formally prove it, but our experiments in Section 4 suggest that the regret of OIMED/OMED may be linear without them.
Assumption on the portfolio regret As detailed in Section there are several candidates for the implementation of OIMED/IMED. The literature regret lower bounds is however scarce. In [Gofer and Mansour, 2016], the authors characterize algorithms with non-negative regret, but for linear losses. Guzmán et al. [2021] showed that the regret of FTRL algorithms is bounded as ((VT) both from above and below, in a setting that encompasses portfolio selection. Unfortunately, FTRL is computationally inefficient, which makes it unsuitable for our application. We used Soft-Bayes for its simplicity and computational efficiency, but it might not have the desired lower bound. Our problem seems to be among the first where a large negative regret is detrimental, and obtaining a portfolio algorithm with both small computational complexity and a regret lower bound is an open question. On the other hand, it may be that this lower bound requirement could be relaxed in the analysis, and that for example high-probability lower bound could be enough. Our experimental study in the next section supports the hypothesis that using Soft-Bayes in OIMED gives good regret bounds for the bandit problem.
Experiments
We numerically assess the regret and run time of the two novel approaches presented in this paper. We benchmark our approaches with the known asymptotically optimal algorithms: IMED [Honda and Takemura, 2015], KL-UCB [Cappé et al., 2013] and NPTS [Riou and Honda, 2020]; and the more efficient but sub-optimal UCB [Auer et al., 2002], k1-UCB [Cappé et al., 2013] and KI-IMED (that denotes the binarized version of IMED). We provide the pseudo-code of KL-UCB and NPTS in Appendix A.2 for completeness. Our code is available in the supplementary material of the paper.
We showcase our main findings by presenting selection of experiments, focusing on FIMED and OIMED, while we present a broader set of experiments and more detailed results in Appendix F. In each case, we plot the average 10%-90%. The run times are dependent of the Python implementation of our algorithms, and are thus only indicative. We refer to Appendix F.1 for discussions their theoretical complexity.
time and regret of each algorithm, along with their quantiles
Distributions from DSSAT We first consider the crop- mrop-management optimization problem intro- duced in Section and detailed for instance in [Baudry al., 2021a], as it illustrates the theoretical advantage of asymptotically optimal algorithms (Figure 1). A learner needs to select a planting date for maize grains among seven possible options. For each distribution, the rewards are drawn uniformly at random among 10a points sampled from the DSSAT simulator, in order to emulate the distributions at reduced cost.". Our results, displayed in Figure show that on this problem optimal algorithms also achieve hetter empirical performance. IMED, NPTS and KL-UCB perform similarly, while k1 IMED and UCB achieve significantly larger regret. Furthermore, FIMED 10 times faster than IMED for T' = 10 (and as fast as k1 -C-) with almost no difference in terms of regret. As expected, OIMED is as fast as UCB and k1-IMEB It achieves better regret than those algorithms, but its performance is deteriorated compare to IMED. This can be seen as the cost of the ability to forget
'The dataset is available the supplementary material of the paper
8

---

past observations. In summary, this experiment illustrates the respective benefits of our two novel approaches: FIMED the fastest algorithm among those with the smallest regret, while OIMED has the smallest regret among the fastest algorithm.
NP15
304
IMED
OIMED
FIMED
KI-ICB
Soun thrme
KL-UCB
Number samples
Number samples
Figure 2: Average regret (left) and run time (right) of the algorithms on the DSSAT bandit problem
Bernoulli bandit For our second experiment we consider Bernoulli bandit with several means close to 0.5, for which all optimal algorithms match their implementation with the Bernoulli KI- divergence. Intuitively, sequences of and with high variance may lead to the most potentially confusing inputs for portfolio algorithms, that case. Our results, summarized in Figure 3, are promising: the average regret of OIMED on par with other algorithms, while it still is among the fastest. In that experiment only UCB is sub-optimal, and performs much worse than the other algorithms.
our objective is to check the performance of OIMED in
412
NPTS
OIMED FIMED
(ossomma sron ong
2008
A00g
6012 samples
1002
2000
Number of stsamplss
Figure 3: Average regret (left) and time (right) of the algorithms 6-arms Bernoulli bandit problem with means {0.3, 0.4, 0.45, 0.5, 0.52, 0.55).
Importance of the duel-based structure In Section 3 we detailed our theoretical motivations for introducing duel-based approach when approximating X/// with portfolio algorithm. We now provide empirical evidence that this change may prevent OIMED from suffering a linear regret. In Figure 4, we compare the regret of OIMED and variant of OIMED that does not the duel-based structure of Algorithm for the two experiments introduced in previous paragraphs. In that algorithm, the online estimates of Kir We observe that the regret of the "no duel" variant of OIMED may be better in some cases: for the DSSAT experiment, its average regret matches the best algorithms of Figure 2. However, the Bernoulli experiment its regret is linear. Overall, OIMED needs a modification like the duels to ensure that it has sub-linear regret.
updated each pull of an
with the current best empirical mean.
Further experiments In Appendix F we show that FMED and OMED exhibit the same characteristics as FIMED and OIMED, as expected. We also consider other Bernoulli bandits, for instance with means close to the boundaries of the support. We then show that the conclusions of this section still hold on problems with distributions of various shapes, by testing our algorithms on several examples of Beta distributions. We also investigate the sensitivity of OIMED to the learning rate of Soft-Bayes, which is the only hapar-parameter of the algorithm. Finally, we perform experiments with the discretized IMED algorithms that is briefly presented in the introduction and discussed more thoroughly in Appendix D.

---

OIMED no duels
10.
Negeet
358
6010 samples
1200
samples
Figure 4: Average regrets of OIMED and "OIMED no duels" on the previous 7-armed DSSAT bandit (left) and 6-armed Bernoulli bandit (right).
Conclusion
We introduced methods compute efficiently approximations of K and demonstrated their use in algorithms for regret minimization in stochastic bandits. The FKED and FIMED variants have the same asymptotic optimality properties as the base MED algorithms, but have much reduced computational complexity. OMED and OIMED push the computational gains further and are also memory efficient. They can also be asymptotically optimal, under the hypothesis that the portfolio algorithm they use satisfies a deterministic regret lower bound.
While experiments show the good practical performance of OIMED and OMED with the Soft-Bayes portfolio algorithm, this question is however still open: can we have a portfolio algorithm which is computationally efficient, does not store all past gains memory and has sub-linear regret upper and lower bounds?
Finally, work towards enabling the use of K in computationally efficient way has potential applications beyond regret minimization stochastic bandits. First, similar quantities are used RL algorithms like IMED-RL [Pesquerel and Maillard, 2022]. Second, other bandit tasks like best arm identification also have complexities that depend on K quantity, and could benefit from faster variants of the algorithms that need to compute it [Jourdan al., 2022].
Acknowledgements
R. Degenne acknowledges the funding of the French National Research Agency under the project FATE (ANR-22-CE23-2 CE23-0001--0)) This work beneficiated from the support of the French Ministry of Higher Education and Research, of Inria and of the fauts-de-Bal de-France region.
10

---

References
S. Agrawal and N. Goyal. Analysis Thompson sampling for the multi-armed bandit problem. In Proceedings of the 25th Annual Conference Learning Theory, 2012.
Agrawal, S. Juneja, and W. M. Koolen. Regret minimization heavy-tailed bandits. In Conference Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, 2021.
Auer, N. Cesa- Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
D. Baudry, R. Gautron, E. Kaufmann, and O. Maillard. Optimal thompson sampling strategies for support-aware evar bandits. Proceedings of Machine Learning Research. PMI., 2021a.
D. Baudry, P. Saux, and O.-A. Maillard. From optimality to robustness: Adaptive re-sampling strategies in stochastic bandits. In Advances Neural Information Processing Systems, 202
D. Baudry, K. Suzuki, and J. Honda. A general recipe for the analysis of randomized multi-arme aumti-armed bandit algorithms, 2023.
S. Bubeck, N. Cesa-Bianchi,, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends(K) in Machine Learning, 5(1):1-122, 2012.
A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122-144) 1996.
O. Cappé, Garivier, O.-A. Maillard, R. Munos, and G. Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 41(3):1516-1541) 2013.
H. Chan. The multi-armed bandit problem: An efficient nonparametric solution. The Annals of Statistics, 48(1):346-373, 2020.
T. M. Cover. Universal portfolios. Mathematical finance, 1(1):1-29, 1991.
M. Cover and E. Ordentlich. Universal portfolios with side information. IEEE Transactions on Information Theory, 42(2))348-363, 1996.
E. Gofer and Y. Mansour. Lower bounds individual sequence regret. Machine Learning, 103: 1-26, 2016.
C. Guzmán, N. Mehta, and A. Mortazavi. Best-case lower bounds in online learning. Advances in Neural Information Processing Systems, 14421193-211333 2021.
J. Honda and A. Takemura. An asymptotically optimal bandit algorithm for bounded support models. In COLT, pages 67-79, 2010.
J. Honda and A. Takemura. An asymptotically optimal policy for finite support models in the multiarmed bandit problem. Mach. Learn., 2011.
J. Honda and A. Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. J. Mach. Learn. Res., 16:3721-3756, 2015.
G. Hoogenboom, C. Porter, Boote, Shelia, Wilkens, U. Singh, J. White, Asseng, Lizaso,
L. Moreno, et al. The dssat crop modeling ecosystem. Advances in crop modelling for sustainable agriculture, pages 173-216. 2019.
M. Jourdan, R. Degenne, D. Baudry, R. de Heide, and E. Kaufmann. Top two algorithms revisited. In NeurIPS 2022-36th Conference Neural Information Processing System, 2022.
A. T. Kalai and S. Vempala. Efficient algorithms for universal portfolios. Journal of Machine Learning Research, pages 423-440, 2002.
E. Kaufmann, Korda, and R. Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory 23rd International Conference, ALT 2012, 2012.

---

L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
L. Orseau, Lattimore, and S. Legg. Soft-bayes: Prod for mixtures experts with log-loss. In International Conference Algorithmic Learning Theory, pages 372-399. PMLR, 2017.
Pesquerel and O.-A. Maillard. Imed-rl: Regret optimal learning of ergodic markov decision processes. In NeurlPS 2022- -ii-thirty-siith Conference on Neural Information Processing Systems, 2022.
C. Riou and Honda. Bandit algorithms based on Thompson sampling for bounded reward distribu- tions. In Algorithmic Learning Theory, pages 777-826. PMLR, 2020.
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-294, 1933.
C.-E. Tsai, H.-C. Cheng, and Y.-H. Li. Online self-concordant and relatively smooth minimization, with applications to online portfolio selection and learning quantum states. In International Conference on Algorithmic Learning Theory, pages 1481-1488 PMLR, 2023.
J. Zimmert, N. Agarwal, and S. Kale. Pushing the efficiency-regrel pareto frontier for online learning of portfolios and quantum states, In Conference Learning Theory, pages 182-226. PMLR, 2022.
12

---

A Index, notation and algorithms
A.1 Index and notation
In this section we summarize the notation used in the proofs of Theorem and 2, and recall some of the definitions presented in the paper.
k (1,...,K) K)
F the family of distributions supported on [6, B] R.
(Fi...., Fk) E Fz denote the distribution of the K arms of bandit problem. Their expectations denoted by P1....:: PK. Without loss of generality we assume the proofs that μ4 ma Mg, and also define 2h BLtR
For any FEF. p [b, BJ, (F, p)) = maxxejo.1 Er [Log (1 X x
A4+1: arm selected by the learner at the beginning of round t + 1.
(t): number of pulls of arm k up to (including) time step
(EK),)e( sequences of rewards: Xk,n is the n-th reward collected from arm k.
(t): empirical distribution of arm & at time We also denote for convenience by Fe.. the empirical distribution of arm l after collecting observations: FR,,.(() = (t).).
(t) and 14 denote the empirical mean of arm l respectively at time / and after collecting n observations.
μ² (t) max (t).). (t) argmax.u=t)) kE[K]
For randomized algorithm, where Fr denotes the o-algebra generated by the rewards collected by the learner up to (and including) time We call (t) the sampling probability of arm k at time
the shorthand notation Ps(t) P(A4+1 k(FF),
We use "MED" general terminology to call some existing bandit algorithms based on the computation of XC Takemura, 2010], MED [Honda and Takemura, 2011] I] and IMED [Honda and Takemura, 2015]. Hence, MED denotes a specific algorithm and MED a general family of algorithms this paper.
Some these algorithms are DMED [Honda and
FMED and FIMED:
(f): time of the last pull of arm & at time f, formally (t) = inf < N&(s) Na(O)).
(t((t) KiT (Fi (f)) nr (sx(t)) As (s) (sx(((()))),
is a first order approximation T (F (t), /r (f)) satisfying (t)()) < KTT (F))) (*)) where for any E N
>x(s)=
argmax
E [log(1 A(X (*))))
AEJO, B-P
OMED and OIMED:
4 leader at round t, defined as l E a (t). Ties are broken favor of the arm with
kE[K]
the best empirical mean. If there are still several candidates choose one of them randomly.
Challengers: all arms except the leader le
A++1: set of arms to pull at the beginning of round
Duel: comparison between challenger arm k and the leader l, time
(t) 0 if the duel for challenger & is greedy comparison, Zu = 1 otherwise (e.g. if the index comparison of IMED used). We use the expressions "greedy duel" and "non-greedy duel" to distinguish the two cases.
13

---

Ma(t) I' - E A,+1, = 4, (s(s
1): number of observations collected by
l as a challenger against the current leader E(t) and thanks non-greedy duel. We denote by (t) the empirical distribution associated with these observations, and use the shorthand notation FR... for (L)
For any k [K] 2 E [K], N, Xk,,, is the n-th observation collected from arm against the leader l after a non-greedy duel
The online estimate used by arm against leader with N&(t)
Xx.e. - 1= (1n.62))
B - -1 (tx,e,))) -
L
Σ log
Aki
where fg,6, is the time step satisfying ( (t No(() + 1, = =.), and (AR,) is provided by portfolio selection algorithm.
Xk.e. - p= (tmnee))
)) Lu,e,
Rg =
max X
log
1->
B 1 (tx,e.))
is the portfolio regret.
For any μ B),
X 1r (((taee)) B (ta.es)) (
Bx.e,( = XE(U,1]
log 1-
nKKin((nn
is the bias of the portfolio selection sub-routine with respect (NCTr(FRrs)))
We also use Lu.e, (1) L N..o. Be(l, (B
A.2 Detailed implementations
In this section detail the implementations of the algorithms presented in the paper, along with their main competitors. We start with the implementation of IMED and MED, presented respectively in Algorithms 2 and 3. We then present FIMED and FMED, respectively in Algorithms 4 and 5. Finally, we detail OMED Algorithm 6, and recall that the implementation of OIMED presented Section (Algorithm 1).
In Algorithm 7, we also detail the implementation of the discretization process proposed by Riou and Honda [2020], that allows to map the rewards in grid X' = (æ1, ( .M) without changing the means of the arms.
Finally, for comparison we also detail the implementation of the two other existing optimal algorithms for general bounded rewards: KL-UCB (Algorithm 8), implemented with parameter f t log(t) + log log(t)) and NPTS (Algorithm 9).
Algorithm 2 Indexed Minimized Empirical Divergence (IMED)
Input: K arms, support upper bound Initialization: vk E [K] Ng = 0 (nb. of pulls), f4x = 0 (emp. mean), K₃ = 0 (emp. K.T
for t do
if < K then
a
else
Set a = argmin N₂ + log( Nx); Index comparison, break ties at random
kE]K]
Pull arm observe reward Na,Na+1. update (or define) Pa. Na. F. (emp. distrib.).
Ift K: Ak E [K], set K2 ( max pk).
ICT update
14

---

Algorithm 3 Minimized Empirical Divergence (MED)
Input: K arms, support upper bound B 8 Initialization: vk E [K]: N₂ = (nb. of pulls), 7h = 0 (emp. mean), K₁: = 0 (emp. 1
for t E N do
10
i K then
L Set a
12
else
13
Sample ~ Mult (=-g))
Nx
with S = Σ e NaK
Sampling
Pull arm a, observe reward Na,N++1, +1, update (or define) iaa Na. Fa (emp. distrib.).
If K: vk E [K], set Ks = K Fk. maxke[K] (
10
update
Algorithm Fast Indexed Minimized Empirical Divergence (F (FIMED)
Input: K arms, support upper bound B Initialization: Ak [K]: N₂ (nb. of pulls), eu (emp. mean), K₃ 0 (emp. KiT)).
16
for t E N do
17
ift K then
18
L a =t
19
else
Set argmin N&Cc log(N&) Index comparison, break ties at random kE[K]
Pull arm a, observe reward X No update (or define) Pa. Na. Fa (emp. distrib.).
for & E [K] do
22
if 1e then
N > 1, set KC = N ma A&) and Rs = Kk.
23
where FR is the empirical distribution of (X XRNz):i
K computation
Keep in memory Tht max Pk. and d the maximizer of (4) when computing K4:- else
24
Set Kr K₂ do x (ma Pe : Fast update k not pulled
25
Algorithm 5 Fast Minimized Empirical Divergence (FMED)
Input: K arms, support upper bound B Initialization: Vk E [K]: N₂ = (nb. of pulls), fu 0 (emp. mean), K₁ = 0 (emp. Ki
26
for t E N do
28
if K then
29
Set a =t else
30
31
Sample a Mult
(e-M N1
Nx
with =x -NKKs
>. Sampling
Pull arm observe reward No,N.+1, update (or define) Po. Na. Fo (emp. distrib.). for [K]de do if = 1: then
32
If 1, set KG KE max ( and K2 = KR.
34
where Fx is the empirical distribution of (X....... XkNe).;
IT computation
Keep in memory 3 max fo. and d the maximizer of (4) when computing Kt+ else
35
Set K₁ Kr No x (maxxe[[] The - :2):
Fast update if k not pulled
15

---

Pull each arm once Algorithm 6 Online Minimum Empirical Divergence (OMED)
Input: K arms, upper bound B, portfolio selection algorithm ALG (and its parameters), function Initialization: vk E [K]: N& 0 (total nb. of pulls), Nue 0 (nb of pulls as challenger after non-greedy duel against leader E), P (emp. mean), Lue (emp. K challenger against leader é), Ase = 1/2 (initialization for ALG).
for / N do
39
if't then
40
L Set A (I,...,K} K}:
else
42
Set A = O
Initialize the set of arms to pull
Set S argmax je[K] N₂=
Candidates for leadership
44
If [ > 1, set S t Jes
Tie breaking
45
Choose leader uniformly random in for k + e; do
Organize duels between & and all challengers
46
Ne. 2 [(Ne) or Pa 2 Pmax then
47
If Thk 32 Tee add le to A, set Za 0: Greedy duel if Ng is too small
49
else
Draw W ~ Ber(e Lx,),, WA = then Add A. Zn
50
MED duel if Ng large enough Pull arm observe a reward X, update Pu,, NR. if Zu = then
52
for 1: E A do
53
54
NE. <- Ne.e +1
Update de, with ALG, knowing Ne.t and B
Portfolio update
B-
Liee Line log (1- Au.t A
Ree
55
Algorithm 7 Discretization algorithm from [Riou and Honda, 2020]
Input: Reward X, grid X' (Ii,...,
56 Set m = max (j E M Bj <
X)
if
mı, m = otherwise.
Sample Z ~ Ber
X-2,
x1+1 -F;
Return: Y z [1[(2 2 = 0) + I3-1 = 1)
Algorithm 8 KL-UCB [Cappé et al., 2013]
Input: K arms, support upper bound
Initialization: vk E [K]: N₃- (nb. of pulls), function f.
58
for t do
ift K then
60
Set a =t
else
62
for l E [K] do
63
Set f4g max (N [b, B]
No p) f(t)
64
Set a argmax fix kE[K]
> Index comparison, break ties at random
Pull arm a, observe reward No,N update (or define) Po, Na. F. (emp. distrib.).
16

---

Algorithm 9 Con-Parametric Thompson Sampling [Riou and Honda, 2020]
Input: K arms, support upper bound B Initialization: vk E [K] N₂ = (nb. of pulls), H1 = (history).
66
for t E N do
68
if K then
L
70
else
71
for k E [K] do
72
Sample weights w ~ Dir(1..... (Nx ones)
Set 1 = Em= wi Xi + WN++1B;
Re-weighted mean
73
Set argmin Ix. kE[K]
Index comparison, break ties at random
74
Pull arm observe reward No,N.+1, set H. = Ho U (Xo.N+++1
B Proof of Theorem 1: regret analysis of the index policies
Before proving the theorem, we recall some useful properties from previous works.
B.1 Toolbox for bounded distributions.
In the proofs we use the following results, that come from several works on bounded distributions in bandits (e.g. [Honda and Takemura, 2015, Cappé al., 2013]), and are detailed in Appendix D.3 of Baudry et al. [2023].
Lemma (Useful properties of KTt)). Let F FF be a distribution of mean μ.F. We denote by Fr and pn respectively the empirical cdf and empirical mean corresponding to ii.d observations collected from F. It holds that
1. Kly is continuous, non-decreasing and convex in its second argument (Theorem 7 of [Honda and Takemura, 2010]).
2. There exists constants
O, 80 > O such that Vp >> μ.p, and 8 E (0, 8gl holds that (Fa 14) & (F, - 8) & e -ooh.
3. For any and p pn + 8, holds that
2=a
KTTg (F, 1) K-T (Fa 2 85 == (B b)2
4. For any > 0, it holds that (Lemma 6 from Cappé et al. (2013])
P(C (Fn p1) x) & e(n + 2)e ne
5. For any > (Hoeffding's inequality).
P(p, pF =) 2nne and P(p, > pF + & 2ns=
Proof. Property 3. can be deduced from Lemma 13 of Honda and Takemura [2010]. Using the convexity of k and Pinsker inequality we obtain that
Xf Fn. p1) Kff (F, n: / e) Ki
(F Pn + > kl(jn, Mr, + +E) 2="
if the range is [o. 1]. The factor (B-b)² comes from using this result on rescaled distributions for general ranges.
Then, property can be obtained with a straightforward adaptation of the proof of Lemma of Agrawal et al. [2021] (in their Appendix B. Indeed, in this paper the authors consider non-parametric family of distributions for which KFF can be expressed very analogous way to Equation (4).
17

---

B.2 Proof of Theorem 1
We introduce the notation (t. = inffs & t: Na(s) = (x) which is simply the time step corresponding the last pull of arm before time i, and k- (+) argmax(r:(t) We recall Theorem 1.
kE(K)
Theorem (Regret bound for fast MED). Consider (F1,.... Fk) FK and p² ma Pk- Then, for any time horizon N and ε > 0, MED, IKED, FMED and FIKED all satisfy
E [T) < log(T) + os (log(T))
(12)
in (())
where (log(T)) denotes term that is asymptotically dominated by log(T) for fixed but with polynomial dependency in Furthermore, all the algorithms are asymptotically optimal.
Proof. Equation (12) be proved for all the algorithms with the same general proof scheme. Hence, we propose a proof that tackle them all at once, explicitly mentioning which parts are specific to given algorithm. We start proving first general upper bound.
Lemma 3 (Generic regret upper bound). For each sub-optimal arm and any >> 0, FMED and FIMED both satisfy
T-1
B[N&(T)) < (T) + E
= (TT))
Post-CV
E
T(A441 k No(()) u, (t) EM Eo) +0.(1),
Pre-CV
where (T)
log T
and using the notation Eo B-u and E1 62 we define
(F
Te(t) (Fx -cv) > >>> (F -
and
For MED and IMED, (t) {1²(() #1 -co-
For FHED and FIMED, Gz(() = { (t()) > #1 - -rt, (sx((tt) > #n
> -22 ) (ox
Proof. Following for instance the regret analysis the vanilla MED presented [Baudry al., 2023], upper bound the number of pulls by distinguishing several cases,
18

---

[[N+(T) & (T) +
us (())),
Prst-CV
+ E
11 - N, > <) 50)
-
1 1n
2o)
Pro-CV
E
x
CV-Emp
A1t1 A4t1 - Eu: (²) - / (s(((t))
E
$ -E2
B - μ (sx(t))
Var Best (FMED and PINED only)
+ E
= k t
11
4 (sx(tt < p1 - -60)
Transition- (FMED and PINED only)
This upper bound already exhibits u. (T). Post-CV and Pre-CV, It remains to prove that the additional terms are upper bounded by constants depending on s. The term CV-Emp is necessary for all algorithms, while the two last terms are specific FMED and FIMED, Indeed, they tackle the cases where the sub-optimal arm & is pulled due to value of μz (sx(t)) that deviates from μn and/or μ (t). We start by upper bounding CV-Emp, writing
CV-Emp &
Σ
Σ
E (Ate1 n, JTn)]
t=l (T)
P (F -60) & KiTTe PR, M1) - -11)
PP (Fam & & (Fe, +
E0
E1
B 141
(T)
where the last line comes from Lemma 4 of Cappé al. [2013]. We choose 81 = 2 - and obtain
that CV-Emp= Ozo (1) thanks to property 2. of Lemma 2. This concludes the proof Lemma regarding MED and IMED. We now consider the terms specific to FMED and FIMED.
We start with Var-Best, and analyse more precisely the implications of the event
n² (t) 11" (Sk (1))
(1) 1 (1) > i
-82 }
B PM (sx (t))
We first prove that the combination of these two events ensure that 1r¹ (sx(1)) > in with a proper tuning of Eo and 22, since
(1) 1 (8)
& - - 4r (t) 1² (sx(t)) < - (sx(t))
B (sn(())
4 (t) + E
#1 - Eo + B
+ **)(st()) >
1 82
1 62
82 B 11) E3
+ =*((s((1)) > μ1
62
19

---

3 if holds that EU < - f1. Then, also remark that this event also implies some variation of the best empirical mean between sxx() and t. Hence, only two scenarios can make B& (t) hold:
Hence, we choose E2 = B-11 to obtain μ² (sx()tt) > μl +
-
(*(s (t)) is pulled between sx(() and t, and μ (sx(tt)) > P1 + 3.
(sx (t)) not pulled between 8i: (1) and t, k- (t) = j for some j + k- (t) In that
case, j has been pulled between (t) and t and it holds that 21 = μ (t) 2 1 (sx(t)) > μ1 + tn 3
As each of these scenario can cause at most one pull of arm k, we can upper bound Var-Best by simply counting the number of times an arm j E [K] is pulled (at time f) and either (15(t) > in Co or 11 (t 1) μl + Ep. We hence obtain that
K
T
(A++1 = jA {15(1) > 3 + ED
3 u (1s + 2 pn + = ]
Var-Best
<
E
T A141 = N, n, [ugn 3 p1 11 +
80
} u (fjtat pr 4 + 60 3 ]]
3
ΣΣ
Mij 2
M1 M1+ + 5o
3
j=ln=1
(1)
We apply the exact same arguments for transition-best, except that this time we deduce that ke (t) was pulled between s (t) and t, and that (if (a) = n) My.. & #1 - Ey and Pj.n+1 è fi + Eg- Depending on the identity of k (t) one of these two events has exponentially decreasing probability. Formally, obtain that
Transition-best
< Σ
Σ
P( > p1 - Eu) +
Σ j:ps nml
P(paa E -E0)
jipy nml
=O. (1)
This concludes the proof of Lemma 3 by choosing = B 1B-11.
Building on Lemma 3, we finish to prove Theorem by upper bounding the post-convergence and pre-convergence terms for all algorithms.
Upper bounding the post-convergence terms Under G& (t) and (1). it holds thanks to property 1. of Lemma that K ( (1)) > K-f (F,, Hence, MED satisfies
Post-CV HED <
E
I(N&(t) (T)) pa(t) Σ
E
I(Nx(t) > (.) (x- (-07
< T exp
-1) 1
20

---

by definition of ue (T)
Similarly, the design of (x(() for FMED also ensure that & and Post-CVFEED FRED E by the same arguments. For IMED, we obtain that
[T
R (F. )-
(x(t)= 2 K 11)
Post-CV IMED
<
E
[(txtt) & (,,0))))
E
I(N((t))C(() log(Nxx Nx (.(1), (lg))
< E
T(u (P) -) llog(T)) =0;
so arm never pulled in the post-conver regime with IMED. Again, these arguments directly translate to Post-CV FINED-
Upper bounding pre-convergence term Interestingly, the design of K& (t), satisfying K&((t) > Ke (Fe(t), yz (t)). makes FMED and FIMED more exploratory than MED and IMED. Hence, we can unify the proof for the vanilla algorithms and their fast update in this part.
We start with MED, following Baudry et al. [2023] we first that for any sampling probability (t( pa(t)
holds that (t) <
pL(t) (t( < 1-) Pı (t), and obtain that
pi(()
Pre-CV HED == E
[(Na:tt) > u, A,41 = k. (t) & #n - so)
E
> < -
(()(()) < MM -60) (pi(1) - -1)p((0)
< E
I(A++1 11) < in - -o) ( (p)(0)= - -1)
E
(1(()
Let us denote by Pi (1) the sampling probability of arm 1 under FMED. Using that ΣK (2(0)
obtain that
PWED Pi
exp (+)(()))))))
exp (-M(() = (t)
K
where (MED(t) is itself a lower bound on the sampling probability of arm 1 under MED (we use this notation with slight abuse). If follows that Pre-CV pMEd admits the same upper bound Pre-CVHED. MED- The rest of the proof can be found Baudry et al. [2023], we briefly recall it from completeness. We first obtain that
T-1
Pre-CV NEDD
& K
Σ
E
(F
- 1] + (K - 1) Σ P( & -5)
==
T-
< K
E
(F - + +0. (1)
21

---

Then using properties 3. and 4. from Lemma 2 and (Fim: < Kt log conclude that
B-b B-m
T-1
eak -1
(F, deo + log(1 + x)
Pre-CVum MED
K
IP
dr
n
-1
e e-nde
K
e(n + 2)
1 dx
n=l
B-
Kelog
n(n 2)e nn
- pn
(1),
2 with 6.. (f- As consequence, Pre-CVFRED (1) too. For FIMED the relationship with the pre-convergence term of IMED is even more straightforward.
Pre-CVFINED & E
Σ
((N(()) + (o)(N((0) > 1o)(Na(0),,N(() > (e(T),
& M 60)
(T)
T-1
E
I(M(O) log(N1(()) > (t), > ue(T). M0 & #1 - 6o)
t=
Pre-CV INED (1)
The last statement can be deduced from the regret analysis presented in [Honda and Takemura, 2015), but we now propose simpler proof of independent interest. We use that if A = k. then the index of arm is smaller than the index of arm 1, and that (t) > u. (T') first write that
Pre-CV INED
TI (Ac+1 k No(1 (T)T), > log(Na(O)))
E
Σ
Σ
[(A k, = Ni 11, > log(ne))
t= (T) (T)
E
I
-o) + llg((n)) > log(nz))
inf Fl,,, A1 (1-))) < log B-uiteo Kt To further upper bound this term, we observe that since K-F [F
B-b
the events considered above cannot happen if n₁ + log(n1) < lo)(ue(T)) < log(nz). Hence, there exists function g + N satisfying gTT) - too (g(T) would be of order log log(T) without the additional log(n1)) )) such that
T
T
Pre-CV INED & E
Σ
Σ
MI - Eo) + log(nn) > log(n=))
(T) nu (T')
22

---

Then, using again properties 3. and 4. of Lemma 2 we obtain that
Pre-CVINED INED
Σ
e(n1 + 2 (m1dep (log(n)))oog(_)))
mi ===g(u) nu=
Σ
( + 2) -m:60
Σ
(==)(T)
T
<
Σ
mi(m + 2) -a10o
log
(T)
(TT)
Oco (log(T))
where the conclusion comes from the fact that the remaining sum is the remainder of convergent series, or in other words Pre-CV INED & or log where or + 0. This is sufficient to conclude the proof, by noting that a careful tuning of Eo (for instance as log log(T") allows to obtain that (T)] lim sup [T)
C Proof of Theorem 2: regret analysis of OMED and OIMED
We first recall the theorem.
Theorem (Regret bound for online MED algorithms). Consider (Fi...., Fx) E FKK and p² max Pa Pmax for known Umax B. Assume that OMED and OIMED use a portfolio selection
algorithm ALG that satisfies for any (kc, [K] and E N the deterministic guarantee
R = o(n) (sub-linear absolute portfolio regret).
(13)
Then, both OMED and OIMED satisfy Equation (12) (with a different second-order term) and are asymptotically optimal: they enjoy the same asymptotic guarantees MED and IMED.
Proof. As for the proof of Theorem 1 we start by proving a first regret upper bound that holds for both algorithms.
Lemma (Generic upper bound). For any sub-optimal arm k. for any e > 0 holds that
[+) <ug (T)) + E
likk Act1, N,, us (T), (t) (()
Post-CV
T
+ 4 (og(44) ( E
I(1 & , 14 (1, (0:(1))))))))0)))))))))))))))))) Σ
Cv
where (T) KZ (F and Gz(t) = (x,())) > (0t))((Im(0)
(T)
Before proving this result, let us detail some intuitions. First, we remark that the two expectations need to be second order terms to make the algorithms asymptotically optimal. The first expectation corresponds to pulls of arm in a post-convereence regime, where arm 1 is the leader and the empirical distribution of arm l is close to Fk. On the contrary, the second term is the expected challenger, against a sub-optimal leader. For this reason, we name
number of duels lost by arm these two terms respectively Pox-CV and Pre-CV (where CV abbreviates convergence). Note that Lemma actually holds for any bandit algorithms that would use the same duel-based structure, independently of what they do during the non non-greedy duels.
23

---

Proof. We start the proof by introducing some notation. Due to the specific structure of the duel-based algorithm we define for challenger/leader pair (k, pseudo-count (t) and corresponding empirical edf (t)) they are computed by considering only the observations of arm k that have been collected when arm le was pulled after non-greed, duel (t) 1) performed against the leader 4. = l. Hence, (()) & (t).). In several parts of the proof we also use constants Ih (px: p1) that we arbitrarily set to Ma Finally, we introduce two ways denote the rewards: we continue to call X the 1-th reward received by arm k. but we also introduce the notation Xk,e, for the n-th reward received by arm after non-greedy duel against the leader L.
We start the analysis by considering the case when the best arm is the leader, and the alternative. For each sub-optimal arm k holds that
B N (T) =1+B E
Σ Ilk A =
+E Σ I(k A4t1, & #1
Aa
We then consider the favorable case where arm the leader, splitting the cases according to the value of (t).
A1 < E
Σ llke E
& (k(t))
+E Σ Iikk E 4 =
Bi (gready duels)
B2 (non-greedy duels)
We now upper bound B1 using that if & then N1 > t/K, and that if (a > (1()) then either (t) > 24 (t( & Ik. By starting (t) 1 we cover all possible scenarios for (t) 0 (including Pe, (t) e pmax). We then obtain
B E
Σ
I(ee = m1) < xxx)
+E
Σ Ilkk E Ac+1; vx))
+00
+00
P(
& IK)
Σ P( > xx) O(1).
n=t/K
We then consider B2. We use that for any n. {k E Ac+1, Zz(l) = 1, No. (1) = n) = ((+1)
(k. (t) n} and can happen only once. For any u. (T) E N, we hence obtaín that
+ Σ E NN ( (T))
B2 < ue (T)
We then upper bound Bg by considering separately cases when (x( holds or not,
B₂ < u E
N Ne. (1) + 1, N1, u. (t))
Pos--CV
T
+ E
(t +1) = (t) +1, 1,., u, C.()))
19/
24

---

We remark the first term is exactly the post- convergence term that we introduced in the lemma. Hence, we leave this expression as it for this first result. We then consider Biz. We use Equation (14), for any En > O it holds that
T 1.,1) (O)Kg co) Ne, (r.
(1) EO).
Hence, obtaín that
BR BK..IN (1I Eo) (t)
N,,1 K (Fe, (T)(( Eo) 2
(x)1) C max
(t)
Note that we could have stated different thresholds for each term, but we choose s/3 in each case for simplicity.
We use the first side of our assumption on the regret of the portfolio algorithm: if R, = o(n), then there exists no large enough such that for n > ne. R. < ne Hence, by defining ug (T) 2 nee we ensure that (t) is not due to a large portfolio regret.
3
We now consider the term involving (T (Fx 111 - su), which is analogous to the CV-Emp term of the proof of Theorem (Appendix B). We hence directly write that
T
[aalt =N,.),,(t))))) + 11, > (Z), Eo) & (F., - s))
KTr & KoT (FE, +
60
= =0((1)
B -- M1
3
(T)
by choosing = (B ;1) Finally, we use that B B. (0) (1) - =o) > (t)=/33 is possible only if at least empirical mean computed with "reasonable" sample size deviates. More precisely,
B (RI.Nan c0) > No.1 In (1) = (1(, & Pi -60
= An (1)) M1, & fn - EO
where used that, thanks our algorithm, any time for which the estimate Lx,1 (1) was incremented N1(s) > (s) was satisfied (check to decide that the duel is non-greedy). Interestingly, we now get an event that only depends on (1). Using Lemma 1 we finally get that
E
(c, Nx, ((, > (T), (e so) N1) (1)
(1,, ( (T), / (Nr. : M1, & m1 - 50)
PP
ne (T)
too
Σ a=u,() (T)
P
Is > (ng
: 11, E -0)
P P1 eu) Oc(1),
(T) (n))
thanks to Hoeffding's inequality. This last step allows to conclude that B - Os),,, using that f(s) > for any N.
Remark 1. We can see that this step (s) > Ne(s) was sufficient, the enforcement of (s) > f(N)(s)) is necessary only in the "pre-convergence" analysis.
25

---

Upper bounding A2, & * 1: For this part of the proof, we mainly use techniques from [Chan, 2020, Baudry et al., 2021b]. In particular, we use that if the current leader is sub-optimal arm then either has already been leader and has lost leadership or 1 has never been leader. Formally, we define the event
4, 4-1].
Dj E E 7.0)
Then, we first upper bound the term
T-1 c== Σ E A4414 # 1, 1,))
We use that if DD holds and 4 # then arm was the leader at some point between 1/4 and é and lost its leadership. Furthermore, change of leadership from to j at time can only happen if (1) arm j has been pulled at the previous round, (2) the two arms now satisfy (s) Ns)s)) for some n 2 8/K 2 1/(4K), and (3) Ml,m & Hjjn. Thanks to these properties, we obtain with some
union bounds that
K
T T-1
Σ
Σ
B. = N2(() = =1, 7 P1
1= t=1
8= [1/4]
n=|s/K]
T-1
E A,, =m)
Σ
E
Uuga (I.)
Σ
j=2 k=||/K
==1e/4
7-1
Σ
P(uja 2 m1,a)
jm2 n= [t/k]
T-1
ΣΣ Σ
(P(y) 2 x.)) + (MIn <x,)) = 0(1)
j=2 t= [=|(
We now upper bound the term
T C2 = E 41,
Following Chan [2020], we use that if arm has never been leader between t/4 and t, then it has necessarily lost at least t/4 duels in that time interval. Using Markov inequality, we hence obtain that
T-1
Σ I(1 & 10t1; > 4 1)
Σ
P
1/4
1
Σ
E [[(1 & Ast1, lo 11]
#=1/4
1 I(t E [s, 4s])
E [[I(1 & Ast1, la + 1)]
T-1
< 4log(4)
E [I & (111)111
Thank to these simple tricks, we are back to upper bounding the total number of duels lost by arm while not being the leader at the cost of a multiplicative constant, which is close to the remaining
26

---

tern in our statement. The last step of this first generic analysis consists in upper bounding the regret caused by (t) = 0 by a constant. We denote by f the function satisfying f (f())) = s for any s E N. We use that the greedy duel is caused by either pie, (t) > Mmax or (1,e.t) > (t)K),
D1 =
[ & A4t14 * (t) = 0)]
E ( (I(() & &z > (11K))))) > t/k})]
E [ (1,(1) > (em))
M M
K
E [ <2,, ((/K)) +2 Σ (1,,(())),,,,(1))) > 1/K)]
K T-1 P(ul xx)) +2 2= Ry=t/K
ΣΣ Σ
Pluja =1))=(11)
(t/K)
where we grouped upper bounded the terms corresponding to J4y (t) > Mmax by the terms correspond- ing to مe (t) > Tz for simplicity. Finally, the remaining term of our upper bound is exactly
Pre-CV == 1og((4) 4)
E II & A4+1, l * 1, (1) = 1)]
as stated in the Lemma 4. This concludes the proof of the lemma, (T)] < (T) + Post-CV + Pre-CV + O+(1).
We now prove the following lemma, that concludes the proof of Theorem 2.
Lemma 5. OKED and OIMED both satisfy
Post-CV- = (1) and Pre-CV = O(().
Proof. We need to upper bound four terms. We start with the upper bounds of the two post- convergence terms, that are straightforward thanks to the tuning of ug (T) and the definition of (t).
Upper bounding Post-CV
We start with OMED,
Post-CV OMED = E
1(k e A4t1, = 1, -u, (x(
= 1.Gx(0))
([v. > ue (T), (x)t) = 1.9((t))
< Te MAN
1
thanks to the definition of ue (T). For OIMED, we obtain
Post-CV DIA-CV
E
likk E A4t1.h =, 1, (..()) = =100)(((,(())) 1.)((t))
(NNa(t)(CH//(bb) <) No.)))
> ue()))
27

---

again thanks to the definition of Ue (T).
Upper bounding Pre-CV, OMED
We recall that
Pre-CV OXED
Σ E |
Act1 A (1) {
We use the notation p1 (t)
P1, ee,, and pı.j. e----aa las... Then, with the same arguments as for the regret analysis of the vanilla MED (Baudry et al. [2023]. Appendix B) we obtain that
Pre-CV OMED
(1 (x (1 pp))
( E 11, ( (N,(())))))
1 1 (-P)())
E
P1 (t)
E
Pijm
j=2 nm1
E
(ebi - 1]
2=2m=1
Now, thanks to Equation (14) we can relate Lignn to (Fn, for any x E R. We again choose for convenience, and obtain that
(nAE Rigin- Bi -
Pre-CV OMED
2=
To relate to the proof for MED we need the portfolio regret and bias to be small enough. We use the second side of our assumption on the regret, which is that - RRig.n = o(n) for any j, n. Hence, for large enough it holds for instance that -Rig.n
6 3 nI, with
5, inf K (T. (F,))); FEF
where 5, 0 is ensured by property 3. of Lemma 2. For the bias, we first obtain with Lemma 1 that
- BB (x,)
Σ I(py(t1ga)) > 2zz)
We then define a "good event" under which the bias is controlled,
8 Σ ((s(han) x < n
Bin
We then use similar proof as for the post-convergence term. We first consider
P
EE 11) I(BB,n)
E
n=2n=1
that can upper bounded with the same proof as the vanilla MED from [Baudry et al., 2023]. Using properties 3. and 4. of Lemma 2, obtain that
28

---

nk] + 28
-1
6j
1 + log(1 + +2)
P
IP
dx
3
n
26
en(n + +1)
k +
3 en
j=2n=1
O())
with KJ log Hjss 3 2j for some
B- b
We then tackle the case where Bj,n does not hold, which is possible only if (ndz)². Furthermore, we also use the trivial bound - g. (30g) & thanks
Lemma We then obtain
K
T
(nniiel (F P -1...--Bi.. -Bigmtss) - 1) n(B5m))
= P2
n=2m=1 n=1
(unta -1) T(ES 7 5(no5) : 14is5 3 n;²)
E
j=2
e-1(nd))
(mttallissms))tttttt) -1 ----lie 11(35)
E
j=2
We conclude at this step using that (=(++))) - O, as ensured that (n)) so it simply holds that
P. 0(1) = P. 0())
Upper bounding Pre-CV, OIMED We again consider the two cases, depending on B(t) holds or not. When this is true, we can use similar proof to the one of vanilla IMED that we propose in Appendix B,
E I (ais00aa(FFssmmm + log((V)((t)) > log(N)((t) (t) 20g N₂(() > 1/K)
Q
E
P (nKitetFissse 22) > log(t/K)-
n 20,
3 log(n))
log(t/ K)/K
E
Ken(n+ +
R=log(t/
K2e
Σ 1=1
Σ
nan + 2)
8 -n
where we again used properties 3. and 4. of Lemma 2 to upper bound the probability. The convergence of this term is ensured by the fact that the sum on n starts log(t/K) To formally prove this we can for instance use that there exists a constant C, (that typically scales O(8,²)) up to logarithm terms)
K.
such that Vn N, nn + 2) < Oye" for any n E N.
29

---

@ < c
Σ
I=1
logit/ K) /+++
SC,K2t
SKT
1=1
oct
-0
We then consider (t),, under which the bias can be up to (t), In that case, we use the same proof techniques as for OMED, with
K T-1 22 =
T(
2 log(NN(T)) (1, 2t/0))/////// B(t))
j=
K e- x e (11 -
Σ
e-11(1)))
j=2 t= loggt//K//K-
We then use that the right-hand term converges to 0, so Q1 = =1==
Remark 2. The enforcement of a sufficient sample size for the leader is justified by the analysis of the pre-comvereence term. In this regime linear bias may cost up e" for each sample size Hence, a concentration of the mean with a rate e e is not sufficient, especially if c is small (which happens if the gaps are small). Furthermore, this kind of rate cannot be avoided without actively controlling the sample size of the leader at each update.
This concludes the proof of Theorem 2.
D Accuracy of K approximation and discretization trick
In this section we provide more details on the discussion of Section In particular, we elaborate on the discretization trick proposed in Riou and Honda [2020] and on the sub-optimality of the algorithms that do not target K/ specifically.
For simplicity we assume that = and B = 1, and all results hold for general ranges [b, B] C R up
to rescaling of the rewards: X [b, B]
+ ズ E [0, 1].
Sub-optimality of 21 and kl We denote by kl [o, 11 x 1) the KL divergence between two Bernoulli distributions, expressed in terms of their expectations by
P
1 1- 14
Vp" > p:: kl(,, = log
+ +1 11) log
(16)
1
1-
Consider F E F of mean j [0, 1) and μz" [a, 1), and let us define A 1x* 1r. First, it is known (see e.g. Cappé et al. [2013]) that
(TF(F))) > kI(H,,") 242
(17)
This result (partially) explains why bandit algorithms adapted for 1/4-sub-gaussian or Bernoulli distributions work for general bounded distributions (UCB1 [Auer et al., 2002], kl-UCB [Cappé et al., 2013]), since smaller constant means a more exploratory algorithm. A natural question is to determine how sub-optimal these algorithms be in the general case. In the following assume that A is small to perform some first-order approximations.
First, a simple computation shows that kl(p, RJ
je -(Tpjj kl adapts to the true variance of the Bernouli distributions, exploiting better the geometry of F. The sub-gaussian approximation is tight
A
30

---

only if ş is close to 1/2 but not near the boundaries of the support, which is not surprising. We now investigate the gap between Tf and kl, and recall that the two quantities match for Bernoulli distributions. The following result demonstrates that the ratio between the two can be arbitrarily large the distributions are in fact "far" from being Bernoulli.
K (i((Fi))
can be Lemma 6 (kl vs ) For μ. E (0, 1) and F F10.11 of mean μ μ the scaling of klpr..)) as large as X with the maximum achieved when F is the Dirac distribution with support p A.
Proof. First, Jensen inequality and equation (4) provide that
A
(F. & log 1 1+
Kinr( (p
1-
where bg is the Dirac distribution at Then, approximating
(F, by I-
we obtain that
(5 ~
(4(1 (1)
for small A > O, kl(j p1)
x
too.
A
A
We could argue that Dirac (or highly concentrated) distributions may be unlikely in most applications, however the use-case presented in Section (Figure 1) shows that large ratios / /kl may already be observed with more natural examples. Finally, to compare the impact of the approximation on the asymptotic guarantees of an algorithm on K-armed bandits we can compare >k:A,>0 ((
and Σ k: A
Discretization trick We now detail the trick proposed by Riou and Honda [2020], and inspired for instance by the binarization trick of Agrawal and Goyal [2012]. For any . E N, we fix an arbitrary grid XM = (z)
Z2 < ... < xM = 1) E [0, Mj Then, the trick consists transforming any incoming reward X & Xs in discrete reward Y XM, follows:
Let m E N satisfy Im < X < Im+1 and define p Xmmm
2. Sample Z ~ Ber(p) and define Y 1m = 0) + 2m I[( 1).
If this procedure is used with all rewards collected, one can multinomial distributions with support X., It is easy to see that E|y = X, so the order of the arms do not change with this discretization. Furthermore, the bandit problem becomes equivalent to problem where the distributions would be exactly (Fi ..... F E JKK where, for each E [K] F. is the distribution of the discretized rewards (with reference grid Xxr) generated with i..d samples from Fk. It is hence clear that an asymptotically optimal bandit algorithm for (general bounded distributions) is guaranteed an asymptotic regret scaling in End.>0 (.(() log(T). and
bandit algorithm calibrated for
be optimal if the distributions Fi,..., Fx are already supported on X'M only.
We now discuss the performance that can be achieved with such discretization. Let assume that B-b is chosen for all m E [M 1]. First, due to the compactness constant step Im+1 Im M-T
of we can state that there exists a distribution G. satisfying K7 (F), = KI.(Fk, G.). We then denote by G.A" its corresponding discretized distribution on the grid XM. Thanks to the data processing inequality, we obtain that
(Fe, KL(FF, G.) > KL(FFMM,G G.AM)
which is itself larger than KF (FX.Fa ,1")) by definition, since E Ex~c," [X] Exxo, > n² Finally, using that F:Nss cannot be "closer" to μ² than a translation of F. by n, and Lemma 4 of Cappé et al. [2013], we obtain that
Kr (Fk, 1²*)
> Kir ,n²)
> Kin Fk, 11. - 11) 2 KF (2 (Fk,)1")
B μ
1
B - b
= (Fe,(F
x
M
B p
31

---

Hence, we see that the approximation can be good for large M. However, if (Fk, < B-b M- B-E² (which is possible since M is fixed without knowing the distributions) then the lower bound is vacuous. In fact, we can extend Lemma 6 to any discretization process: small gaps (compared to M- can make the ratio T Fk, μ²') this technique has some convenient properties, is not entirely satisfying. This justifies our quest for alternatives that would preserve the asymptotic optimality of the algorithms.
/ / (F .u) arbitrarily large. Hence, even if
E
Online K computation with portfolio optimization algorithms
In this section we provide additional details regarding OMED and OIMED. We first prove Lemma 1, that essential their regret analysis, then we detail the Soft-Bayes algorithm [Orseau et al., 2017] that we choose in our practical implementation of the algorithms.
E.1
Proof of Lemma
Lemma (Deviations (x)), Let y E (0, 1), and ser Cz.ex B- B-uelle.s.)) holds that
B
log (Celi) ((ee(tres) > p) (p)
log (Cr,e,)) ((u peltx,e,)) (15)
Proof. We introduce some notation for convenience. First, we denote Xx,e, by X; and μ² (tv,e,s) by X, Xi)=(()) X,-H and À argmax Σ log(1 - AZi).
1r (i). Then, we define Y,
B B-p Z:
B
XE(0,1]
We use two elementary analysis properties. First, 1-A2, positive and non-decreasing if Y; > Zz- XY,Y, Then, Y > Z: only if (i) < Otherwise, log(1 XZ,) log(1 - AY,) & O. Hence, it holds that
AZ, 1 - 1
B = Σ
(log(1 -Zz) - -log(1 xY:)) = Σ
log
i=1
1=
1 Zz -- Y, I(p p² (i))
log
We then plug the expression of Y; and Z, in this bound, obtaining that
X2
B BB 1( 2 p (i))
Ba (p)
Σ log
B-X,
B-a
1l (1)
Σ log
B 1
B
which gives the result. Applying the exact same steps provides the other direction.
B -
-B
log
T(a > 11)
B 1r^
1=1
E.2 Soft-Bayes
In this section detail the Soft- Soft-Bayes algorithm, proposed in Orseau et al. [2017]. We recall that the K estimation is a portfolio optimization problem of dimension 2. At each step n, the portfolio algorithm decides an allocation (1 An, A,) between two assets, that provide payoff (1, Y,). We use in this section Y, to denote for simplification B-Xa.t. (f,"'tt, that is used in our implementation of
the estimate Lx,e,. for the challenger/leader pair (k, t).
For the anytime version of the algorithm, sequence learning rates (No)eN is provided as an input of the algorithm. We then define the update rule of the anytime Soft-Bayes in Algorithm 10 below.
32

---

Algorithm 10 Anytime Soft-Bayes [Orseau et al.. 2017]
Input: Parameter An. sequence of learning rates (Mn)neN, initial parameter 1/2
Yn Return: An+1 An x 1/2 7/ Y.)
Mh+11
A1
Orseau al. [2017] prove that defining the learning rate 7) the portfolio regret
lo
ensures upper bound on
RN A (1 + (2) log(NN (N 1) + log(2))
However, they do not provide a lower bound on the regret.
F Supplementary experimental results
F.1 Detail of the costs of each algorithm
We start this section by detailing the computation of the costs of the algorithms presented in Table We first recall the results that we want to prove.
Algorithm
Run time
Memory
Optimality
KL-UCB [Cappé al., 2013]
(n log(n)))
Opt. Sub-opt. (kl)
kI-UCB
Olog(())
((1)
UCB [Auer et al., 2002]
0(1)
O(1)
Sub-opt. (24
NPTS [Riou and Honda, 2020)
Onn)
π
Opt.
MED/IMED
log(n)))
Opt.
[Honda and Takemura, 2010, 2015]
Mult. MED/IMED (M items)
O(M log(n))
((M)
Sub-opt. (Kirr mult.)
FMED/FIMED
(n log(n)) if pulled, ((1) otherwise.
Opt. (Theorem 1) Opt. assumptions
(this paper)
n
OMED/OIMED (this paper)
((1)
O(K)
of Theorem 2
Table 3: Comparison of memory and run time needed per step and for arm k with observations
In the table, n is number of observations for arm, and the costs are computed for this arm only for simplicity.
Memory cost We start with the memory, which is easier to estimate. Most optimal algorithms (KL-UCB, NPTS, MED/IMED, FMED/FIMED) require to store all the observations, for cost n. the contrary, UCB and kl-UCB require constant memory, since they just need to store the number of pulls and the empirical means of each arm. Finally, the multinomial version of the algorithms have a memory cost of M: they need to store the total number of pulls, the frequency of each item TM, on the chosen grid, and the empirical means.
Finally, K appears in the memory cost of OIMED because for each arm k we need to store (at most) K online estimates of K and pseudo-counts, in addition the total number of pulls and empirical mean of the arm. This is worst-case memory, in case each arm have been leader at least once. The total memory cost of OIMED (summing over all arms) then most O(K2), while is (TT) for the optimal algorithms that store all observations.
Computation costs First, we assume that any algorithm that use only quantities that can be updated sequentially has a cost of (()). We include this category updates of means, number of pulls, or the output of portfolio algorithm with running time independent of n. We insist that in practice the cost of these algorithms is not exactly the same, but it can be verified that they remain constant over time.
33

---

We now consider NPTS: the main cost comes from the sampling of n + 1 weights from Dirichlet distribution of parameter (1, ..... 1) (n ones). This sampling is linear n. since it can be done by sampling + i...d samples R1. ....... Rn+1 from the exponential distribution {(1), and then defining W4
R2 for any i E [n + 1]. This justifies the cost in (n) in the table. E5=t ng
The remaining algorithms (KL-UCB and MED algorithms) require to solve the optimization problem defined by (4) compute empirical Ki This be done with any search algorithm, which costs n lo/(1/e) where is the precision asked for the solution. In the implementations we always choose 1/n, so that the precision is enough to preserve the theoretical guarantees of the algorithms. This already provides the cost of the MED algorithms, that require to compute exactly one K for each arm each time step. For IEED/IIMED we precise that this computation happens only the arm wad pulled. Finally, for the discretized version of the algorithms the computation time becomes linear M instead of n, but the log(n) is kept since the precision is still 1/n.
For KL-UCB and kI-UCB, another optimization procedure is needed: for a given function f we solve max (u [b, B]: Nu (F p)) & f())}. We also set the precision of this search to 1/n. which gives the supplementary multiplicative log(n) factor compared with MED algorithms: each JC- computation costs On ln)( and we perform (log(n)) such computations for a step of KL-UCB. This is also the reason why the cost of kl-UCB is not constant: perform (llog(n)) computations of kl.
Remark 3 (Total computation time). We detailed the cost for one arm and one step of the algorithms only for simplicity, however for those depending on there are some differences when considering the total computation time. Indeed, for MED algorithms we do not compute K the best empirical arm. However, this arm is expected converge the true best arm and to be sampled linearly. Hence, Olog(T)). On
there is only one best arm the costs presented in Table 3 will be paid only for the contrury, KL-UCB and NPTS will pay their cost for all arms, including the best empirical arm, of them satisfy be necessary (see Remark 3 of Riou and Honda, 2020]), nonetheless this is how they are typically implemented in the literature.
(2TT). The analysis of these algorithms suggest that this cost may not
F.2 DSSAT distributions
The DSSAT problem was presented in Section I and the experimental results the last Section To give the reader the full picture of the problem, we plot in Figure 5 all the densities of the seven distributions.
1e-5
density
2000
4000
6000
8000
10000
value
Figure 5: DSSAT distributions
34

---

This plot visually confirms the multimodality of all distributions and the difficulty to fit this problem into a parametric framework. We complete the Table I presented the introduction by listing in Kig thus confirming the theoretical importance of using the Table 4 all ratios of the form K and 22 true / quantities over their usual relaxed versions.
4.39
5.22
12.04
10.19
11.73
11.04
(FFFF. 2A7
4.72
5.55
12.73
10.87
12.44
11.63
Table 4: List of all ratios for the DSSAT bandit problem
To ground this theoretical analysis, we plot again the regret curves and average run time of tested algorithms (Figure 6) as well Table that compiles the average regret and average run time on the DSSAT experiment at the horizon 10 000. Reading this table, it is clear that FIMED improves the run time of IMED without compromising the regret and that OIMED improves the run time even further, close to the one of UCB, but at the cost of loosing a bit in the regret term. However, of the fastest methods (those in (1) run time), OIMED clearly the smallest regret. the practitioner willing to pay a bit more time complexity and space complexity, then our proposed FIMED seems to be the best algorithmic method.
UCB
30-
IMED
Bun rine Gecondal)
200
IMED-4
OIMED
FIMED
KL UCB
000
1996
samples
1908
samples
Figure 6: Average regret (left) and run time (right) of the algorithms on the DSSAT bandit problem
Algorithm
UCB
NPTS
IMED
IMED-k1
OIMED
FIMED
k1-UCB
KL-UCB
Regret
252
49
41
148
100
40
74
60
Run time (sec.)
0.38
14
61
0.51
0.47
6
6.8
226
Table 5: Average regret and run time at horizon 10 000 DSSAT
F.3 Additional bandit experiments
Here, confirm the analysis of the previous section. First, benchmark our FIMED and OIMED algorithms against IMED using the experimental setting of the original paper by Honda and Takemura [2015] in which the IMED algorithm is introduced. Then, two of experiments: Bernouli distributions to complete our main experiment presented in Section 4, Figure 3, and another one with Beta distributions.
with
F.3.1 Original testbed of IMED
Negative exponential We consider the negative exponential setting which the law of an arm k is such that X₁ = 1 - X where X is an exponential random variable with parameter /4.- In that case, the expected reward of arm is 14 14, and its support is (-x,, 1]. Figure show simulation result of an experiment
5-armed negative exponential bandit problem
35

---

truncated where, following the setting of Honda and Takemura [2015], fpt (1/5, i.e. (uEts= = 2//3,
regret paare__linar_guaniit.eeo
time.pdf
Mean reg
time
20
samples
samples
Figure 7: Average regret (left) and run time (right) of the algorithms on 5-arms negative exponential bandit problem with means (4/5, 2/228/
On this setting, the benefit the FIMED algorithm over the original IMED can easily be read from Figure 7. FIMED enjoys the same regret as IMED while having order of magnitude smaller compu- tational time, confirming our theoretical analysis of FIMED. OIMED further reduce the computational time (and space) complexity, however the cost of larger experimental regret. The regret still ex- hibit the logarithmic shape in a reasonable experimental time and the choice is left to the practitioner whether trade regret against time and space complexity
Truncated Gaussian We continue benchmarking of Honda and Takemura [2015], we run two experiments where arms are truncated Gaus- sian distributions. In the first experiment, Figure 8, the distributions In the second experiment, Figure 9, the distributions are truncated on (-o0, 1]. In both experiments, use the same set of Gaussian distributions, of means (before truncation) {0.6, 0.5, 0.5, 0.4, 0.4] and variances {0.4, 0.2, 0.4, 0.2, 0.4). After truncation on [0, 1], the expected values (0.519, 0.5, 0.5, 0.465, 0.481). }. and after truncation on (-oo, 1], the expected values (0.319, 0.390, 0.265, 0.320, 0.206).
algorithms using the original testbed
[o, 1].
regret legret_linear linear_std.pdd std.pdf
time.pdf
Moven regitt
Rur stme
samples
samples
Figure 8: Average regret (left) and run time (right) of the algorithms a 5-arms [0, 1]-truncated Gaussian bandit problem with means {0.519, 0.5, 0.5, 0.465, 0.481).
Quite accordingly to the intuition, the regret of all algorithms are better on the [0, 1] 1|-truncated bandit problem than on the (-oo, -]-truncated one. Indeed, the variance of the former smaller than the variance on the latter and an increased variance, all things being equal, tend to decrease the divergence between distributions, increasing the need for exploration. Both on Figure 8 and Figure 9, the regret pf FIMED is on par with that of IMED while being much faster. Following our analysis of running times, OIMED indeed experimentally the fastest but does seem trade this speed for a larger regret. However, one can see that in Figure 9 that the regret gap is smaller than in Figure 9, probably because the variance larger. This variance interpretation confirmed by the experiment on Bernoulli bandit that is presented in Honda and Takemura [2015].
36

---

regret linear linear_std.pdf
time.pé pdf
20 men 3-323
regiee
run time
Number samples
number sampless
Figure 9: Average regret (left) and run time (right) of the algorithms on a 6-arms (-oo, 1 --truuncctedd Gaussian bandit problem with means {0.319, 0.390, 0.265, 0.320, 0.206).
Bernoulli In Figure 10, show simulation results for a 10-arms bandit with Bernoulli rewards with expected values {0.1, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02, 0.01, 0.01, 0.013. It can be seen that the performance gap between OIMED and IMED larger than in any the previous experiments. can be attributed to the fact that all the rewards are all very close to zero and the variance of the distributions are small. However, the learning rate of the portfolio algorithm does not take those information into account, and it takes some time for the portfolio algorithm to converge, time that can be seen in Figure 10 where the regret of OIMED close linear with no variance (pure exploration) for the 3 500 first time steps. In contrast, IMED and OIMED, which do not rely learning rate that is independent variance, have a much smaller regret.
regret_linear piiteerr_guantle..dee
500
R=70.82
FIMED
R-69.79
OIMED
R-381.99
Mean regret
2000
4000
6000
8000
10000
Number of samples
Figure 10: Average regret (left) and run time (right) of the algorithms 10-arms Bernoulli bandit problem with means {0.1, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02, 0.01, 0.01, 0.01}.
Reproducing the experiments of the original IMED Honda and Takemura [2015], we confirmed that our theoretical analysis is experimentally supported. FIMED always seem be on par with the original IMED algorithm while enjoying an order of magnitude faster numerical complexity, as proven in the analysis of running times. OIMED enjoys competítive regret, albeit experimentally larger than the original IMED. However, it has the smallest computational time complexity and its space complexity also minimal. Therefore, seems like there currently trade-off between achieving the smallest empirical computational complexity (and space complexity) and achieving the smallest cumulative regret. The original IMED lies at one extreme, OIMED the other extreme and FIMED sits in-between. The algorithms studied in this paper allows the practitioner to choose the trade-off that suit her the best. Whether one can find an algorithm as fast as OIMED with experimental regret guarantees that exactly match IMED is question for future work.
37

---

F.3.2 Bernoulli bandits
In Section 4, we studied a Bernoulli bandit problem where all the means are close to 0.5 (Figure 3), identified as a "difficult" problem because the variance of the distributions maximized among those supported in [0, 1J. Here, we explore two Bernoulli bandit problems, one where the means are located close (Figure 11, Table and another hereafter where means are located close to 0 (Figure 12, Table 7). For each experiment, we plot the regret curves, the run time curves, as well as table compiling the average regrets and run times of tested algorithms the time horizon T 10000.
344
UCB
IMED
OIMED
FIMED
KL UCB
timn
Number of samples
200
commpless
Figure 11: Average regret (left) and run time (right) of the algorithms on a 6-arms Bernoulli bandit problem with means {0.4, 0.6, 0.7, 0.85, 0.9, 0.95).
Algorithm
NPTS
IMED/IMED-BE
OIMED
FIMED
KU-UCB/KL-UCB
Regret
289
33
30
43
30
95
Run time (sec.)
0.51
15
0.74
0.67
4.2
7
Table 6: Average regret and run time at horizon 10 000 on on a 6-arms Bernoulli bandit problem with
means {0.4, 0.6, 0.7, 0.85, 0.9, 0.95)
We recall that for Bernoulli bandit, IMED and k1-IMED are the same algorithms (we assume that IMED is implemented as k1-IMED while only Os and Is are observed). For FIMED we could have done the same thing to improve its time without changing its regret in order emphasize that FIMED is always faster (or as fast as) k1-UCB, even when using the Bernoulli kl. While the regret and time values change from one experiment to another, the conclusions that be drawn from them do not, especially when considering the confidence intervals represented by the 10%-90% quantiles. Experimentally, OIMED (or OMED,
Section F.4) should be the preferred O(1) method and FIMED (or FMED, see Section F.4) should be preferred if we really target an empirically optimal regret without compromising too much on the running time.
312-
UCB
30-
IMED
OIMED
FIMED
KL UCB
time
208
Number of samples
2000
Number sammpeess
Figure 12: Average regret (left) and run time (right) of the algorithms on a 6-arms Bernoulli bandit problem with means (0.05, 0.1, 0.15, 0.2, 0.22, 0.25)
38

---

Algorithm
UCB
NPTS
IMED/IMED-KI
OIMED
FIMED
K1-UCB/KL-UC3
Regret
328
87
82
116
81
98
Run time (sec.)
0.51
15.4
0.75
0.69
5.6
5.9
Table 7: Average regret and run time horizon 10 000 on on a 6-arms Bernoulli bandit problem with means {0.05, 0.1, 0.15, 0.2, 0.22, 0.25}
F.3.3 Beta bandits
Beta distribution of given mean can have different shapes. In particular, Beta distribution can be close to Bernoulli distribution (shape parameter close zero) with most of the density located around O and I, close to Dirac distribution (shape parameter significantly larger than one) with most of the density located around the mean, and close to a truncated Gaussian distribution (shape parameter larger than one) with the characteristic bell shape distribution around the mean.
In Section we studied a Bernoulli bandit problem where all the means are close to 0.5 (Figure 3). Here, using the same set of means, {0.3, 0.4, 0.45, 0.5, 0.52, 0.55], we run two experiments, one on Beta distributions with an intermediate shape parameter of (Figure 13) and another where Beta distributions have shape parameter of 50 (Figure 15), hence with highly piked distributions. We do so illustrate the effect of changing the shape of distributions without changing the of means.
2.00
1.75
density
1.25
1.00
0.75
0.50
0.00
value
Figure 13: Beta bandit distributions with means (0.3, 0.4, 0.45, 0.5, 0.52, 0.55) and shape parameter
of 5
39

---

312
NPTS
20-
20
OIMED
K/UJC
2018
6010 samples
1808
250
4000
1800
samplles
Figure 14: Average regret (left) and run time (right) of the algorithms a 6-arms Beta bandit problem with means {0.3, 0.4, 0.45, 0.5, 0.52, 0.55] and shape parameter of
Algorithm
UCB
NPTS
IMED
IMED-K: kk1
OIMED
FIMED
k1-UCB
KL-UCB
Regret
322
35
29
103
63
30
100
49
Run time (sec.)
1.2
14.5
53.5
1.5
1.4
5.2
7.7
284
Table 8: Average regret and run time at horizon 10 000 on on a 6-arms Beta bandit problem with means (0.3, 0.4, 0.45, 0.5, 0.52, 0.55) and shape parameter of 5
Comparing the regret curves of Figure 3, Figure 14, and Figure 16, clear that the Bernoulli distributions does induce the larger variance on the regret curves as we identified while the Beta distributions with the largest shape parameter (more concentrated around their means) induce the smallest variance on the regret curve. This, once again, confirms our theoretical findings. While the order of regret curves globally preserved, one can see on Figure that, except for UCB, the Bernoulii experiment makes all curves to be very similar, which is normal since, except for UCB, all algorithms are roughly solving the same problem (all sample are Os and Is). When dealing with Beta distributions, IMED is different than kl- IMED and KL-UCB is different than k1-UCB.
density
2-
0.0
0.2
D.4
0.5
0.8
1.0
value
Figure 15: Beta bandit distributions with means (0.3, 0.4, 0.45, 0.5, 0.52, 0.55) and shape parameter
of 50
40

---

30
NPTS
2M
OIMED
KIUJCB
2068
6012
1858
200
4000
680
samples
samplles
Figure 16: Average regret (left) and run time (right) of the algorithms a 6-arms Beta bandit problem with means {0.3, 0.4, 0.45, 0.5, 0.52, 0.55] and shape parameter of
Algorithm
UCB
NPTS
IMED
IMED-K -k1
OIMED
FIMED
k1-UCB
KL-UCB
Regret
323
20
15.9
103.9
55.8
15.8
95
19.2
Run time (sec.)
1.2
14.4
70.8
1.5
1.4
7.8
303
Table 9: Average regret and run time at horizon 10 000 on a 6-arms Beta bandit problem with
means {0.3, 0.4, 0.45, 0.5, 0.52, 0.55) and shape parameter of 50
Those experiments confirm our numerical findings that OIMED (or OMED, Section F.4) should be the preferred method with (11) computation time, and FIMED (or FMED, see Section F.4), should be preferred if we really target an empirically optimal regret.
F.4 Comparison of and IMED versions
In this paper, we derived algorithmic and theoretical results for modification of both IMED and MED algorithms. In this section, we compare IMED, its modifications FIMED and OIMED, MED, and its modifications FMED and OMED. The comparison is made three experimental setting, the DSSAT bandit problem and Bernoulli bandit problem presented in the main experimental Section 4, as well Beta bandit problem with an intermediate shape parameter of 5 and centered means equal the Bernoulli setting.
FIMED
(eecommds))
MED
Kngget
OMED
Number of samples
Number of samples
Figure 17: Average regret (left) and run time (right) of the algorithms on DSSAT
Algorithm
IMED
FIMED
DIMED
MED
FMED
OMED
Regret
41.7
40.4
100.5
55,1
55.6
87
Run time (sec.)
60.8
5.9
0.5
60.8
6.6
0.6
Table 10: Average regret and run time at horizon 10 000 of the algorithms DSSAT
41

---

In Figure 17 and Table 10, we observe that IMED slightly overperforms MED. Consequently, FIMED also slightly overperforms FMED for the regret metric. Regarding the running time, the MED versions of algorithms are a bit slower than the IMED versions due to the numerical complexity of sampling, larger than that computing the argmin IMED indexes. Interestingly, OMED overperforms OIMED in terms of average regret performance. As we can see in Figure 18 and Table 11 presenting the results of the Bernoulli experiment, this is not a general rule.
305
FIMED
OIMED
Run (oecomdd))
MED FMED
100
1808
2400
samples
Number of samples
Figure 18: Average regret (left) and time (right) of the algorithms 6-arms Bernoulli bandit problem with means {0.3, 0.4, 0.45, 0.5, 0.52, 0.55)
Algorithm
IMED
FIMED
OIMED
MED
FMED
OMED
Regret
105.8
106.6
123.3
141.5
145.2
140.1
Run time (sec.)
39
6
0.7
39.3
6.8
0.8
Table 11: Average regret and run time at horizon 10 000 of the algorithms 6-arms Bernoulli bandit problem with means (0.3, 0.4, 0.45, 0.5, 0.52, 0.55)
IMED
FIMED
OIMED
MED
Regret
OMED
Number of samples
Number of complles
Figure 19: Average regret (left) and run time (right) of the algorithms on a 6-arms Beta bandit problem with means (0.3, 0.4, 0.45, 0.5, 0.52, 0.55) and shape parameter of 5
Algorithm
IMED
FIMED
OIMED
MED
FMED
OMED
Regret
30
29.7
63.7
40
41.4
64.7
Run time (sec.)
53
5.2
1.4
54
5.4
1.6
Table 12: Average regret and run time at horizon 10 000 of the algorithms on a 6-arms Beta bandit problem with means (0.3, 0.4, 0.45, 0.5, 0.52, 0.55) and shape parameter of 5
The experiment on Beta distribution, Figure 19 and Table 12, confirms that the regret loss incurred by the transition from MED to OMED is smaller than the of transitioning from IMED to OIMED. It may
42

---

be because the sampling strategy of MED is better to handle the statistical approximation of portfolio algorithms.
E. Stability OIMED with respect the learning rate
The portfolio algorithm, Soft Bayes, behind OIMED and OMED depends on hyperparameter, 7), the learning rate. learning rate scheme is prescribed in Theorem of [Orseau et al., 2017] with
log(2)
nnn)
4n
where is the number of collected samples. In section, we test the numerical stability of our OIMED algorithm with respect to the learning rate. To do so, we will replace this original by
Tr (n) (2)((2)
4n
where will range from 0.01 to 100. We illustrate the stability of OIMED on three bandit settings: the DSSAT bandit problem and Bernoulli problem that were introduced the main Section and a Beta bandit problem where all the means are centered around 0.5 and the same as in the Bernoulli bandit.
First,
the stability of OIMED algorithm the DSSAT bandit problem that we already used in the main experimental Section 4 and Appendix F. On Figure F.5, the average regret ranges from 103.5 for the smallest values of the parameter
88.5 for the largest value of with intermediate regret of 99.5 for our original value r 1. On this same plot, it is interesting to see that despite the large range of tested parameter size, the quantile tubes remain of roughly the evident bad behavior. While the effect of changing r may seem important, in the range of tested parameter, the effect of changing r would experiment, Figure 2 and Table 5. This experiment shows the stability of OIMED with respect to the learning rate, in the sense that a multiplicative constant does not seem be able to dramatically deteriorate its performance.
size with no
have affected the ranking of algorithms the original
140
OIMED
r 0.01
120
r 0.05
100
0.1
*
0.5
Regret
X r 1
+ r = 5
+ r = 10
40
r 50
100
20
0
2000
4000
6000
8000
10000
Number of samples
Figure 20: Average regret of the algorithms on DSSAT
Those findings are confirmed on second experiment performed on a Bernoulli bandit problem
with means (0.3, 0.4, 0.45, 0.5, 0.52, 0.55). The regret changes from 107 to 124 when varying the parameter from 0.01 to 100, and, while the upper quantile is larger for small value of r, we still observe a logarithmic curve which confirms the stability of OIMED.
43

---

250
OIMED
r 0.01
200
0.05
0.1
* r = 0.5
Regret
150
* r = 1
r = 5
100
+ r = 10
r 50
50
100
2000
4000 Number of samples
6000
10000
Figure 21: Average regret horizon 10 000 of the algorithms on 6-arms Bernoulli bandit problem with means (0.3, 0.4, 0.45, 0.5, 0.52, 0.55)
Finally, we check the effect of the learning rate on two Beta bandit problems where means are {0.3, 0.4, 0.45, 0.5, 0.52, 0.55) and one problem has Beta distributions with shape parameter 5 and the other with shape parameter 50. Those two Beta bandit problems are presented in Appendix F.3.3.
0.01
0.01
0.1
0.1
0.5
Wegret
Regron
50
50
280
Number of samples
Number of sammpees
Figure 22: Average regret of the algorithms on 6-arms Beta bandit problems with means (0.3, 0.4, 0.45, 0.5, 0.52, 0.55) and shape parameter of 5 (left) and 50 (right)
When the variance of the distributions is smaller (large shape parameter), we can see that regret curves better separated and the the bonus of choosing larger learning rate parameter amplified. When the variance is larger (small shape parameter), regret curves are closer to each other and more within each others quantile tubes. This last experiment confirms all our previous findings about the numerical stability of DIMED.
F66 IMED with discretized rewards
In Section of this paper we introduced known trick reduce the time and memory complex- ities of MED/IMED. It consists in using algorithms designed for multinomial rewards, by using discretization procedure pendix F,1, and proved its inevitable sub-optimality for some problems. We end this section by experimenting with multinomial IMED, comparing the empirical performance and computation time of several instances using different grids. In each case, we fix number of ticks M, and use the grid
the collected rewards. We furthermore detailed this technique Ap-
(0, W- ......., M=. 1 ((0,1) if M 2). Our objective is to identify the number of ticks needed
44

---

to get regret close to IMED, and the evolution of the computation time with the number of ticks. We first run an experiment on the DSSAT bandit problem, and then on a Beta bandit problem where means are close to zero.
30
Mult IMED 3 ticks
Mult IMED 5 ticks
Ruun time (secimda)
144
Mult
IMED
10 ticks
IMED ticks
1908
240
samples
of samples
Figure 23: Average regret (left) and run time (right) of the algorithms on DSSAT
Alg. (ticks)
IMED (2)
IMED (3)
IMED (5)
(7)
IMED (10)
IMED (20)
IMED
Regret
151.5
75.7
50.9
45.2
44.1
40.25
40.25
Run time
32.8
33.1
36.8
39.4
42.2
44.8
61.1
Table 13: Average regret and run time at horizon 10 000 of the algorithms on DSSAT
Unsurprisingly, the more ticks, the better the regret and the larger the running time, with IMED and k1-IMED providing the range for both metrics. For this problem, M 20 (intervals of length 0.05 between each tick) seems to be enough to make the algorithm using discretized rewards almost match the true IMED in terms of regret, while being 25% faster.
We remark that the evolution of the time complexity per time step not linear the number of ticks. This is likely because it is actually dependent of the "effective" number of ticks used in memory, i.e. those that contain at least 1 samples. Getting at least 1 sample for each tick/arm takes some time, that depends the shape of the distributions the [0, support.
We run a final experiments on Beta bandit problem that confirms our findings. IMED and k1-IMED again provide the range for both computation time and regret, and for this problem M 20 is also the value from which IMED and discretized IMED start to match terms of regret, while the latter approximately 20% faster.
Mult. IMED 2 ticks
30
Mult IMED ticks
Mult IMED
Mult. (MED ticks
Reggot
Mult. IMED 20 ticks
12
Number of samples
2200
Number of sammpesss
L200
Figure 24: Average regret (left) and run time (right) of the algorithms on a 6-arms Beta bandit problem with means (0.05, 0.1, 0.15, 0.2, 0.22, 0.25) and shape parameter of 5
45

---

Alg. (ticks)
INED (2)
IMED (3)
IMED (5)
IMED (7)
IMED (10)
IMED (20)
IMED
Regret
81.8
43.8
32,9
30.8
29.6
29.2
29.2
Run time
31.3
41.5
45.5
46.4
49.2
51.2
62.5
Table 14: Average regret and run time horizon 10 000 of the algorithms on a 6-arms Beta bandit problem with means {0.05, 0.1, 0.15, 0.2, 0.22, 0.25) and shape parameter of 5
46


Reviews:
[{"review_id": "V7fxS6e2uO", "reviewer": "Reviewer_gHyp", "summary": "This papers studies asymptotically optimal algorithms for regret minimization in the multi-armed bandit setting with bounded reward distributions. The main contribution is an efficient approximation of the KL constraint of the lower bound, leading to faster algorithms with (asymptotic) regret guarantees. The proposed approach extends the MED / IMED by optimizing a lower bound on the KL, and using online learning algorithms to estimate the KL constraint. The claims are corroborated with numerical experiments on real-world data for crop management.", "questions": "* The main result (Theorem 1) uses small-o-notation to suppress the lower-order terms. Are these terms controlled in the analysis? Could you provide a more detailed discussion of the finite-time performance of the algorithm, both from a theoretical and empirical point of view?", "limitations": "* The online algorithm used to approximate the KL is assumed to have a bound on the absolute value of the regret. This is in rather unusual requirement and strongly limits the choice of online learning algorithms, as the authors discuss at the end of section 3. \n* The approach requires an upper bound on the best reward, mu_max < B. It looks like this can easily be satisfied by replacing B by B + eps for small eps > 0. Does the bound depend on the gap B - mu_max? Is knowing B/mu_max a strong assumption?\n\nI also suggest to add a more detailed explanation/clarify for the following points:\n\n* eq below line 126: why do we get this equality? (How) Is N_k(t) defined?\n* line 164-168: The dueling procedure is hard to understand, i.e. what is a \"greedy duel\"?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Asymptotically instance-optimal bandit algorithms are well-studied, however existing approaches are expensive to compute because any optimal approach needs to (approximately) solve a linear program with KL constraints. Developing more efficient and practical algorithms is an import problem and this paper makes significant progress towards this direction. Both the relaxation of the KL and the use of online algorithms to compute K_inf are interesting novel ideas.\n\nThe paper is generally well-written, however fairly technical and could use some more guidance/intuition for the reader in a few places (e.g. how is the loss of the online algorithm connect to K_inf? how is the bias of the portfolio algorithm controlled?)\n\nRelated work is adequately discussed. Note that the use of online algorithms for approximating/minmizing KL objectives in bandit setting also appears in related context, e.g. [1-3].\n\n[1] Foster, Dylan, and Alexander Rakhlin. \"Beyond ucb: Optimal and efficient contextual bandits with regression oracles.\" In International Conference on Machine Learning, pp. 3199-3210. PMLR, 2020.\n\n[2] Foster, Dylan J., Sham M. Kakade, Jian Qian, and Alexander Rakhlin. \"The statistical complexity of interactive decision making.\" arXiv preprint arXiv:2112.13487 (2021).\n\n[3] Kirschner, Johannes, Tor Lattimore, Claire Vernade, and Csaba Szepesvári. \"Asymptotically optimal information-directed sampling.\" In Conference on Learning Theory, pp. 2777-2821. PMLR, 2021.", "weaknesses": "The approach appears to be tailored to bound reward distributions, whereas in general, asymptotically optimal algorithms are known for a much more general class of algorithms and reward distributions. It is unclear if the proposed techniques can be extend beyond the current setting. It would be great if the authors could comment on this point.\n\nAs a minor comment, while I appreciate the use of real-world data, the simulation of the crop-management tasks is run over 10000 rounds. Is this realistic in this type of applications? Do the algorithms perform well over much smaller horizons?\n\nCan anything be said about finite-time or worst-case performance of the algorithms?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and for proposing several ways to further improve the clarity of our paper. In the following we answer to the points raised in your review, in order. Please feel free to ask for any further clarification during the discussion phase.\n\n* **Remarks in the Strengths section:** We will move  Equation (13) in Section 2.2 in order to provide a clear summary of the link between $n \\mathcal{K}_{\\text{inf}}(F_n, \\mu)$ and the quantities of the portfolio selection algorithm in this section. \nAlso, thank you for pointing us to additional related works. We will add them to our literature review.\n\n* **Extension beyond bounded distributions:** Our approach is indeed tailored for bounded distributions, but we believe that it can be extended to other settings. Please note that in several usual settings MED/IMED are in fact easy to run and memoryless, so there is no incentive to modify their vanilla implementation: parametric families of distributions [3] (single parameter exponential families, Gaussian distributions), or Sub-Gaussian distributions (Maillard Sampling, [1]). However, as pointed out by reviewer zxKa, our approach may be interesting for some other non-parametric models presented in [3] (in which MED and TS approaches for these settings are analyzed) and [4], with families of distributions characterized by a moment condition of the form $\\mathbb{E}[h(|X|)] \\leq B$ for some known convex function $h$ and constant $B$. In such setting, $\\mathcal{K}_{\\text{inf}}$ can be expressed as the solution of an optimization problem, very similarly to the bounded case. There is hope that we can adapt our algorithms to these settings, but this is not straightforward (see our response to reviewer zxKa). This is a direction that we would like to consider in a future work. \n\n* **Real-word data:** We chose the crop yield dataset because it was available and provided realistic examples of bounded distributions for which optimal algorithms are largely superior to sub-optimal ones using $\\text{kl}$ or $2\\Delta^2$ as a proxy for $\\mathcal{K}_{\\text{inf}}$. We agree that obtaining $10^4$ points is unrealistic in that application and that our considerations of computational cost could have been better illustrated on another setting.\n\n* **Finite-time/worst-case performance/$o$ in Theorem 1:** In the revision we will detail the scaling of the $o_{\\epsilon}(.)$ term in Theorem 1, and include the following short discussion. In our proof, all its components are explicit, so the scaling in $\\epsilon$ can be recovered: we obtain $\\epsilon^{-6}$, that allows to get a sub-linear minimax bound of $\\mathcal{O}(T^{5/6})$ if e.g. $\\epsilon = \\Delta_k/2$ is chosen, though not the optimal rate of $\\mathcal{O}(\\sqrt{T})$. We can make several remarks on this result. First, the same scaling is obtained for the vanilla MED (l. 517) with the proof techniques presented in [3]. Our fast implementations don't deteriorate that bound. This result is likely to be not tight, but improving it may require a much more involved analysis. A recent paper [2] established that MED is minimax optimal for Bernoulli distributions, but the analysis is very technical. Finally, to the best of our knowledge it remains open to prove that there exists an algorithm that is both minimax and asymptotically (instance) optimal in bounded bandits (i.e. with the true $\\mathcal{K}_{\\text{inf}}$ in the instance-dependent regret, not the $2\\Delta^2$ or $\\text{kl}$ approximation as for KL-MS [2]).\n\n* **Upper bound on the best mean:** The upper bound $\\mu_{\\text{max}}< B$ is necessary so that the bias of the portfolio algorithm does not become infinite, and some of the second-order terms of the regret scale in $\\frac{1}{B-\\mu_{\\text{max}}}$. We first highlight that all existing optimal algorithms need to know the upper bound $B$, so this assumption is standard. On the other hand, deciding if knowing $\\mu_{\\text{max}}<B$ is a strong assumption or not boils down to determining if our bandit problem may contain distributions that are highly concentrated around $B$. In our example in agriculture this would be very unrealistic, and it is reasonable to expect that experts may provide quite well separated estimates of $B$ ($\\approx$ highest ever recorded yield) and $\\mu_{\\text{max}}$ (how good can the yield be on average knowing that there will inevitably be poor seasons). In absence of such expert knowledge, the solution of artificially increasing the upper bound outside of the support is indeed valid.\n\n* **Points to clarify** $N_k(t)$ is defined l. 16 as the number of pulls of arm $k$, and l. 126 is direct from the definition of  as the KL-inf as an expectation over the empirical distribution (Eq. (4)). We use ``greedy duels'' as a convenient term to call duels where the algorithm chooses (without sampling) the arm with maximum empirical average (that would be the output of the greedy algorithm). These duels are necessary to guarantee a large enough sample size for the leader when updates of the online estimate of $\\mathcal{K}_{\\text{inf}}$ are performed.\n"}, {"review_id": "sveEsalGHI", "reviewer": "Reviewer_ba7Y", "summary": "This paper studies non-parametric stochastic bandits. In particular, the author proposes algorithms named Fast (Indexed) Minimum Empirical Divergence (FMED, FIMED), and Online (Indexed) Minimum Empirical Divergence (OMED, OIMED). These algorithms are designed based on Minimum Empirical Divergence (MED). Regret guarantees comparable to that of MED is established for FMED, FIMED, OMED, and OIMED. In addition, these new algorithms have much better computational complexities. Numerical experiments have been conducted to support these claims. \n", "questions": "1. It would be great if the authors could elaborate on the result established by Theorem 1. For example, the bound is dependent on $\\epsilon$—can $o_{\\epsilon}$ be enumerated and this bound be optimized over $\\epsilon$ to get a more interpretable bound? \n2. In addition, it would be helpful to include a more detailed comparison with Honda and Takemura 2015 on both the proof techniques and the regret bound and computational complexity of the algorithms. \n3. Section 4 provides nice empirical justifications on the superior performance and computational complexity of the proposed algorithms. Is it possible to replicate the experiments conducted in Honda and Takemura and compare those algorithms there?\n\n", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This problem is well-motivated and the paper is clearly written and easy to follow. The paper also presents a complete story from motivation to algorithmic design to theoretical guarantees and empirical justifications. ", "weaknesses": "I have listed a couple questions in the “Questions” part of this review. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your questions, that we hope to address in the following.\n\n* **Second-order terms** In the revision we will detail the scaling of the $o_{\\epsilon}(.)$ term in Theorem 1, and include the following short discussion. In our proof, all its components are explicit, so the scaling in $\\epsilon$ can be recovered: we obtain $\\epsilon^{-6}$, that allows to get a sub-linear minimax bound of $\\mathcal{O}(T^{5/6})$ if e.g. $\\epsilon = \\Delta_k/2$ is chosen, though not the optimal rate of $\\mathcal{O}(\\sqrt{T})$. We can make several remarks on this result. First, the same scaling is obtained for the vanilla MED (l. 517) with the proof techniques presented in [3]. Our fast implementations don't deteriorate that bound. This result is likely to be not tight, but improving it may require a much more involved analysis. A recent paper [2] established that MED is minimax optimal for Bernoulli distributions, but the analysis is very technical. Finally, to the best of our knowledge it remains open to prove that there exists an algorithm that is both minimax and asymptotically (instance) optimal in bounded bandits (i.e. with the true $\\mathcal{K}_{\\text{inf}}$ in the instance-dependent regret, not the $2\\Delta^2$ or $\\text{kl}$ approximation as for KL-MS [2]).\n \n\n* **Comparison with Honda \\& Takemura (2015)** Comparing the steps of the analysis would be intricate since they follow a quite different path. Our analysis is more inspired by the recent works [1] and [3]. We can state that the regret bound of Honda \\& Takemura contains a $\\mathcal{O}(\\Delta^{-10})$ term (proof of their Corollary 4), so our result is tighter for small $\\Delta$. However their bound holds for a more general case than ours since semi-bounded supports are allowed ($b=-\\infty$ with our notation).\n\nRegarding the experimental aspect, in our revision we will replicate the experiments of Honda \\& Takemura and put the results in our Appendix F, already containing additional experiments.  \n"}, {"review_id": "ThSojg8Cdf", "reviewer": "Reviewer_Nc1j", "summary": "This paper consideres classic multi armed bandit problem. The focus is on developing asymptotically optimal algorithms with efficient computational and memory complexity. The results for the proposed algorithms are reported in Table 2. FMED and FIMED compute KL divergence for the armed that is pulled while using first order Taylor expansions  for the other arms. In addition an online portfolio selection algorithm is used to estimate the KL divergences that further improves the computational and memory performance. ", "questions": "Could authors provide more details on analytical challenges beyond using the results from Honda and Takemura [2010]  and online portfolio selection. This seems important as this is mainly a theoretical paper. ", "limitations": "The paper is mainly a theoretical paper, targeting the computational and memory requiremets of exisiting algorithmis. ", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper contributes to the bandit literature by improving the computational and memory requirement of asymptotically optimal algorithms with non parameteric distributions (where it is assumed that an upper bound on the rewards is known). ", "weaknesses": "Although the results are interesting, they rely on known results from Honda and Takemura [2010] on approximating KL diveregnce and results on online portfolio selection. This limits the significance of the contribution of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comment, in the following we hope to address your concern on the technical contribution of our paper. Though the results from Honda \\& Takemura (2010) and the literature on portfolio selection are the starting point of our work, we believe that we solved several significant technical challenges to obtain our results. Hence, we respectfully disagree with the opinion that the technical aspect of the paper may limit the significance of our contribution, and would be happy to discuss more precise points during the discussion phase.\n\n**Outline of our main technical contributions:** For the analysis of FMED and FIMED we had to upper bound new terms involving the variation of the best empirical arms (Var-Best and Transition-Best in the proofs). We believe that this part (l. 479-496) is non-trivial. Furthermore, we point out that our new way to upper bound the term PRE-CV$_{\\texttt{IMED}}$ is of independent interest, since it largely simplifies the original proof of Honda \\& Takemura (2015).\n\nThen, for the analysis of OMED and OIMED we use existing results on portfolio selection only through the assumption on the portfolio regret. This provides only a small part of the result, and a significant challenge remains in upper bounding the regret due to the portfolio bias. Solving this challenge led us to propose the current form of OMED and OIMED as duel-based algorithms, and their analysis is quite non-standard. Thus, the proof of Theorem 2 (Appendix C) presented a significant technical challenge.\n"}, {"review_id": "qpD5NWTyh2", "reviewer": "Reviewer_zZCp", "summary": "In this paper they provide fast optimal algorithms for (non-parametric) stochastic bandits.\nSpecifically, they consider the MED family of algorithms that require the computation of $\\mathcal{K}_{inf}$.\nBased on this family of algorithms they construct new variants that require the computation of $\\mathcal{K}_{inf}$ for one arm and approximate $\\mathcal{K}_{inf}$ for other arms. Although, these variants (FMED, FIMED) achieve computational speedups they store all the rewards in memory. To address this issue they use portfolio algorithms.\n", "questions": "- What is kl in line 78? Please clarify.\n- How coupled is your approach with the knowledge of $b$ and $B$ the lower and upper bounds for the distribution support?\nIn case we don't exactly know these bounds, does under- or overestimating this parameters lead to poor perfomance? Specifically how is perfomance affects?", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work addresses the well known issue of optimal bandit algorithms being impractical due to high computational complexity. \nI think this is an important step towards practical optimal bandit algorithms.\n- Novel (algorithmic) use of portfolio algorithms to estimate $\\mathcal{K}_{inf}$.\n- Well written\n- Experiments prove the applicability of the proposed algorithms.", "weaknesses": "Maybe you have to mention the regret assumption for the portfolio algorithms upfront, i.e. in section 2 (instead of the end of section 3).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging evaluation of our work and for your helpful questions and suggestions. \n\n* **Portfolio regret assumption** We agree that this crucial assumption should be mentioned sooner in the paper, we will follow your suggestion and introduce it already in Section 2.\n\n* **Questions -- $\\text{kl}$:** It denotes the Kullback-Leibler divergence of Bernoulli distributions, $$\\forall (p, q) \\in [0,1]\\times (0,1)\\;, \\\\text{kl}(p,q)=p\\log(p/q) + (1-p) \\log((1-p)/(1-q)).$$\nWe indeed forgot to define it, thank you for noticing. \n\n* **Questions -- knowledge of $[b,B]$:** The strength of our approach is that the performance of our algorithms does not require the knowledge of $b$, while approaches relying e.g. on re-scaling are very sensitive to it. It just needs to be finite for our analysis, and $B-b$ multiplies some of the second-order terms of our regret bounds (which would be the case with any other standard algorithm like UCB). On the other hand, the knowledge of $B$ is crucial, but this is true for any bandit algorithm working with bounded distributions. Over-estimation can lead to sub-optimality, but preserves the logarithmic regret. In fact, if the bound used by the algorithm is $B+\\gamma$ for some $\\gamma>0$ then it would be optimal if the true model was ``the distributions are supported on $[b, B+\\gamma]$''. This is a broader family of distributions than the distributions supported in $[0,B]$, which can lead to sub-optimal (but logarithmic) regret. On the other hand, under-estimation may lead to linear regret. Hence, if the practitioner does not know $B$ it is always preferable to over-estimate it."}, {"review_id": "jGiuqg7Ddx", "reviewer": "Reviewer_zxKa", "summary": "This paper considers the classical regret minimization problem in the stochastic multi-armed bandit setting with arms having distributions with support bounded from above by a known constant B, and sometimes also lower bounded by b. Typically, all the known asymptotically optimal algorithms for regret-minimization problem in the bandit setup depend on computing an optimization problem involving the KL divergences. This is known to be computationally expensive in practice. The main object of study of this paper is K-inf. In this paper, authors develop approximations for empirical version of K-inf and study the performance of algorithms using these approximations, instead of exactly computing K-inf at each step. \n\nThe first of these approximations simply uses the convexity of K-inf in the second argument, while the second one derives from exploiting a connection between K-inf and online no-regret learning.\n\nWhile using the first approximation in IMED and MED still leads to asymp. optimal algorithms, the second approximation requires assumptions on the no-regret algorithm used, and finding a no-regret algo. satisfying those assumptions remains open.\n\nNumerical evidence supporting the theory is also provided.\n\n", "questions": "1. Can the ideas be extended beyond bounded distribution class? For example, to the moment-bounded class considered in Agrawal et al., 2021 or even the centered-moment bound class considered in Baudry et al., 2023? What would the challenges be in extending?\n\n2. Could you clarify how you obtained the inequality after the data-processing inequality on Page 30, line 703?\n\n3. In Figure 3, since we are looking at performance of OIMED and FIMED, it will be good to include IMED as well.\n\n4. Also see weakness above. ", "limitations": "none", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I enjoyed reading the paper. It is generally well-written. While theory for asymptotically optimal algorithms for bandits have lately been developed in great generality, these optimal algorithms can be computationally demanding. These optimal algorithms all mostly depend on empirical K-inf. While the dual of this problem is a convex optimization problem, it is well known that its computation cost increases with number of samples (Cappé et al., 2013, Honda et al., 2015, Agrawal et al., 2021). \n\nThe paper studies an important practical problem of addressing the computational aspect of these optimal algorithms trying to avoid compromizing their optimality. \n\n\nIt is interesting to see the use of ideas from online portfolio selection algorithms in the bandit setting. As pointed by the authors, while this connection was previously observed in developing concentration inequality for K-inf by Agrawal et al. 2021, exploiting it to get fast algorithms is an interesting step in solving the computational aspect of K-inf, which, in my opinion, can be useful in other bandit settings as well. \n\n", "weaknesses": "1. The assumption on the no-regret algorithm in the second approach is a bit strange.\n\n2. The paper can be a bit hard to read for someone new in the community. \n    - Before introducing the fast MED algorithms in Section 2, it would be good to introduce the basic idea of \n    MED algorithms (both IMED and MED) or how K-inf appears in them (or point the reader to relevant \n    appendix where it is discussed, if space is a concern).\n    - 1 line justification for the re-formulation of K-inf below line 126.\n    - Details of why K-inf computations only happen for O(log T) times in line 112 of the paper. Though the \n    reader is referred to Section 3 for discussion, I couldn't find a discussion on this there either. \n\n3. In the introduction, the authors mention that KL-UCB requires several computations of K-inf per step, which I believe is not necessary - see, for example, Agrawal et. al, 2021 (Appendix D) where the index is expressed as a single 2D opt. problem. Similar approach can be used for KL-UCB algorithm in the setting considered here.\n\n4. Minor comments:\n    - Line 142: is --> are\n    - Line 143: This is, for example, ... ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and your precise questions, as well as your helpful suggestions.\n\nWe first answer to the points detailed in the weakness section of your review.\n\n* (1) In our bandit algorithm, a sub-linear upper bound on the portfolio regret avoids over-exploration while a sub-linear lower bound avoids under-exploration. The requirement for a lower bound is indeed unusual in the literature on portfolio selection, making this question an open problem for future work. \n\n* (2) We understand your point, we will follow your suggestions to make some parts of the paper easier for non-experts. We will point to Appendix A.2 where IMED (Algorithm 2) and MED (Algorithm 3) are detailed. \n\n* Still (2): KL-inf computations only happen when a (empirically) sub-optimal arm is pulled, so the upper bound on the number of pulls of Theorem 1 directly translates into an upper bound $\\mathcal{O}(\\log(T))$ on the number of KL-inf computations. We will clarify this in the revision.\n \n* (3) It is true that for our claim in the introduction we assume a naive implementation of KL-UCB using al linesearch on $\\mu$, that may be optimized e.g. using the method of [4]. However, that method makes the cost of KL-UCB similar to the one of MED or IMED, not significantly better. We will change our description l. 57 to account for that.\n\n* (4) Thank you for noticing these typos.\n\nWe now answers the questions asked in the dedicated section of your review.\n\n* (1) Extending our approach for the non-parametric families of distributions considered in [3] and [4] is indeed a natural direction for future works. Several challenges arise, making this extension non-trivial. First, the $\\mathcal{K}_{\\text{inf}}$ is not necessarily convex in its second argument in these settings (we exhibited convex then concave behavior in preliminary experiments for the centered family of [3]). As a consequence, the analysis of the pre-convergence term of FMED and FIMED would not be as simple as in the bounded case, or the algorithms may require modifications. Then, for the adaptation of OIMED and OMED the feasible set of the parameters $ (\\lambda_1, \\lambda_2)$ of the dual problem is of the form $\\mathcal{S}= \\{ (\\lambda_1, \\lambda_2) | \\forall x \\in \\mathbb{R}, \\; 1-\\lambda_1(x-\\mu) - \\lambda_2 (B-h(|x|)) \\geq 0 \\}$, which is more difficult to map to the simplex than $\\lambda \\in \\left[0, \\frac{1}{B-\\mu}\\right]$ in the bounded case. \n\n* (2) p. 30, l. 703: we skipped the following steps, and will add them in the revision to improve clarity. Denote by $G_\\star$ the distribution satisfying $$K_{\\text{inf}}(F_k, \\mu^\\star) = \\text{KL}(F_k, G_\\star),$$ \n\nand by $G_\\star^{X_M}$ its discretized counterpart. Then, data processing inequality states that \n$$K_{\\text{inf}}(F_k, \\mu^\\star) = \\text{KL}(F_k, G_\\star) \\geq \\text{KL}(F_k^{X_M}, G_\\star^{X_M}),$$ \n\nand we obtain l. 703 using that $\\text{KL}(F_k^{X_M}, G_\\star^{X_M})$ is itself larger than the KL-inf between $F_k^{X_M}$ and $\\mu^\\star$, by definition of this function.\n\n* (3) We will include IMED in Figure 3 in the revision. As in Figure 2, its curve is superposed with the one of FIMED. In all our experiments the difference between the two algorithms is negligible while FIMED is much faster, showing the strength of this approach. "}]

Author rebuttal:
We thank the reviewers for their insightful comments on the paper, and appreciate their overall positive feedback.
Following the suggestions of all reviewers, our revision will mainly serve the purpose of providing additional intuitions to some technical parts of the paper. We also thank the reviewers for pointing some typos and specific points that required clarifications.

We provide a detailed response under each individual review, and would be delighted to provide further insights if needed during the discussion phase. 

In our responses we refer to the following references: 

[1] J. Bian and K. Jun. Maillard sampling. Boltzmann exploration done optimally. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, AISTATS
2022, 2022.

[2] H. Qin, K. Jun, C. Zhang. Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards, 2023.

[3] D. Baudry, K. Suzuki, and J. Honda. A general recipe for the analysis of randomized multi-armed bandit algorithms, 2023.

[4] S. Agrawal, S. Juneja, and W. M. Koolen. Regret minimization in heavy-tailed bandits. In Conference
on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, 2021.


Meta-review: This paper makes a solid contribution for the nonparametric multi-armed bandit problem (or, noise-adaptive multi-armed bandits). The improvements on the computational efficiency is meaningful, though the guarantee on OMED/OIMED comes with an assumption.
Decision: Accept (poster)