Indexed Minimum Empirical Divergence for Unimodal Bandits
Authors: Hassan SABER
Pierre MENARD
Odalric-Ambrym Maillard
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-Armed Bandit
Indexed Minimum Empirical Divergence
Unimodal Bandits
Optimal Algorithm
One-Dimensional Exponential Family Distributions
Regret analysis

Abstract: We consider a stochastic multi-armed bandit problem specified by a set of one-dimensional family exponential distributions endowed with a unimodal structure. The unimodal structure is of practical relevance for several applications. We introduce IMED-UB, an algorithm that exploits provably optimally the unimodal-structure, by adapting to this setting the Indexed Minimum Empirical Divergence (IMED) algorithm introduced by Honda and Takemura (2015).  Owing to our proof technique, we are able to provide a concise finite-time analysis of the IMED-UB algorithm, that is simple and yet yields asymptotic optimality. We finally provide numerical experiments showing that IMED-UB competes favorably with the recently introduced state-of-the-art algorithms.

Indexed Minimum Empirical Divergence for Unimodal Bandits
Hassan Saber
Pierre Ménard
Université de Lille, Inria, CNRS, Centrale Lille UMR 9189 CRIStAL, F-59000 Lille, France hassan www.anaaabereiiin...mmm
Otto von Guericke Universität Magdeburg pierre. menard@ovgu.de
Odalric-Ambryn Maillard
Université Lille, Inria, CNRS, Centrale Lille UMR 9189 CRIStAL, F-59000 Lille, France odalric aatariimmmillaarnniia.f.....
Abstract
We consider multi-armed bandit problem specified by set of one-dimensional family exponential distributions endowed with unimodal structure. We introduce IMED-UB, an algorithm that optimally exploits the unimodal-structure, by adapting to this setting the Indexed Minimum Empirical Divergence (IMED) algorithm introduced by Honda and Takemura (2015). Owing our proof technique, we are able to provide concise fimite- time analysis of the IMED UUB algorithm. Numerical experiments show that IMED UUB competes with the state-of-the of-the-art algorithms.
Introduction
The multi-armed bandit problem is a popular framework to formalize sequential decision making problems. was first introduced in the context of medical trials [Thompson] 1933] 1935) and later formalized by Robbins [1952] A bandit is specified by configuration, that set of unknown probability distributions, // = (Pa)aEA with means (Pa)aeA- At each time t N, the learner chooses an arm a; A., based only on the past, the learner then receives and observes reward X₁, conditionally independent, sampled according to Pa.- The goal of the learner is to maximize the expected sum of rewards received over time (up to some unknown horizon T), or equivalently minimize the regres with respect to the algorithm constantly receiving the highest mean reward
T Xe where p = max Pla aE.A
R(v, T) = E
Σ
1
Both means and distributions are unknown, which makes the problem non trivial, and the learner only knows that v 'D where is a given set of bandit configurations. This problem received increased attention in the middle of the 20th century, and the seminal paper[Lai and Robbins 1985 established the first lower bound on the cumulative regret, showing that designing an algorithm that optimal uniformly over given set of configurations D comes with a price. The study of the lower performance bounds in multi-armed bandits successfully lead to the development of asymptotically optimal algorithms for specific configuration sets, such the KLUCB algorithm [Lai] 1987 Cappé et al. 2013 Maillard 2018) for exponential families, or alternatively the DMED and IMED algorithms from Honda and Takemura [011 2015]. The lower bounds from Lai and Robbins [1885] later extended by |Brrnetas and Katehakis [997] did not cover all possible config configurations, and in particular structured configuration sets not handled until AAgrwall al. [1989] and then Graves and
Lai 1997 established generic lower bounds. Here, structure refers to the fact that pulling an arm
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

may reveals information that enables to refine estimation of other arms, Unfortunately, designing numerical efficient algorithms that are provably optimal remains a challenge for many structures.
Structured configurations. Motivated by the growing popularity of bandits in number of in- dustrial and societal application domains, the study of structured configuration sets has received increasing attention over the last few years: The linear bandit problem is one typical illustration Abbasi- Yadkori et al. [201T). SSinivas et al. [2010). Durand et al. [2017), for which the linear structure considerably modifies the achievable lower bound, see Lattimore and Szepesvari (2017]. The study of a unimodal structure naturally appears in many contexts, e.g. single-peak preference economics, voting theory or wireless communications, and has been first considered in Yu and Mannor [2011]
from a bandit perspective, then in Combes and Proutiere| (0014) and(Trihh et al. [2000] providing an explicit lower bound together with an algorithm exploiting this specific structure. Other structures include Lipschitz bandits Magureanu et al. (0014), and we refer to the manuscript Magureanu [2018) for other examples, such as cascading bandits that are useful in the context of recommender systems. In Combes et al. [2017]. a generic algorithm is introduced called OSSB (Optimal Structured Stochastic Bandit), stepping the path towards generic aemei bandit algorithms that are adaptive to a given structure. More recently in Degenne et al. (2020), the authors introduce an adaptation of the KLUCB strategy handle structured multi-arme aalti- bandit problems.
We assume unimodal structure similar to that considered in Yu and Mannor 2011] and Combes and Proutiere [2014]. That is, there exists an undirected graph G = (A, E) whose vertices arms A, and whose edges E characterize a partial order among means (Ha)ae This partial order is assumed unknown to the learner. We assume that there exists a unique optimal arm a" argmax Mo and that for all sub-optimal arm # a", there exists a path P. = (a1
Unimodal-structuree
a...., 0t. = a²) E A of length la > 2 such that for all i E [1, la 1], (a;, d++1) E E and Ha, < Po Lastly, we assume that v C P = {p([),, HE), where p(4) is an exponential-famil distribution probability with density f(-, (1) with respect some positive measure À on R and mean E CR P is assumed to be known to the learner. Thus, for all a E A we have Va =(pa). We denote by D(P.G) or simply D the structured set of such unimodal-
distributions characterized by (P.G), In the following, assume that P is a set of one-dimensional exponential family distributions.
Contributions. In this paper, we provide novel regret minimization results related the unimodal structure. We first revisit the Indexed Minimum Empirical Divergence (IMED) algorithm from Honda and Takemura [2015) introduced for unstructured multi-armed bandits, and adapt it to the unimodal- structured setting. We introduce in Section 3 the IMED-UP UB algorithm that is limited to the pulling of the current best arm or their no more than nearest arms each time step, with d the maximum degree of nodes in G. Being constructed from IMED, IMED- -UB does not require any optimization procedure and does not separate exploration from exploitation rounds. IMED-UB appears to be local algorithm. We prove in Theorem that IMED is asymptotically optimal. Furthermore, this novel algorithm competes with the state-of-the-at algorithms in practice. This is confirmed by numerical illustrations on synthetic data. We believe that the construction of this algorithm together with the proof techniques developed in this paper are of independent interest for the bandit community.
Notations. Let D. D. Let μ²" m Ma be the optimal mean and a* = argmax, a A Ma be the optimal arm of v. We define for an arm a E its sub-optimality gap A₂ |t- - Paa- Considering an horizon T> 1, thanks the chain rule we can rewrite the regret follows:
R(v,T) = (N.
(1)
aEA
where No(t)=Ei I(a-=a) is the number of pulls of arm at time t.
2 Regret lower bound
In this subsection, we recall for completeness the known lower bound on the regret when we assume a unimodal structure. order to obtain non trivial lower bound we consider algorithms that are consistent (aka uniformly-good),

---

Definition (Consistent algorithm) An algorithm is consistent on 'D for all configuration v D, for all sub-optimal arm a, for all 0,
(T) 0.
lim E T-000
7
We can derive from the notion of consistency an asymptotic lower bound on the regret, see Combes and Proutiere 2014].
Proposition 2 (Lower bounds on the regret) Let consider consistent algorithm. Then, for all configuration vED ED, must that
inm R(v,T) T+000 (Tg(T)
Aa
2 dv)
E aEV=.
(L(Wallr))
p () denotes the Kullback-Leible divergence between p()( and v/ = for p. pl E
where [[(el=")=
The quantity c(v) is fully explicit function of v (it does not require solving any opti- mization problem) for some set of distributions v (see Remark 4.. This useful property no longer holds in general for arbitrary structures. Also, it is noticeable that clv) does not involve all the sub- optimal arms but only the ones Va.. This indicates that sub-optimal arms outside Va- are sampled o(log(T)) which contrasts with the unstructured stochastic multi-armed bandits. See Combes and Proutiere ) for further insights.
Remark 3
Remark For Bernoulli distributions, a possible setting is to assume = 5g 51 (with do, d1 Dirac measures), θ = (0, 1) and for μ G, f(:,)) E 1) + n² 11)- Then for all μ. pl E (0, 1). (L(p))') = woggg//pp/ + (1-+) (og((L (variance o² 1), assume À to be the Lebesgue measure, - and HER, f(;, I E - (V2T) -Le -x-===>²² Then for all p. ER, (L(H)μ')= (k' For Exponential distributions, we assume À to be the Lebesgue measure, θ ==]0; -0;;0;0000 +00,, and for p f(-,)== x x>00~ 2/1 //. Then for all p >0, (L(ulp")=log(c +//p' 11
For Gaussian distributions
3 Optimal algorithm for unimodal-structuree bandits
We present in this section a novel algorithm that matches the asymptotic lower bound Proposition This algorithm is inspired by the Indexed Minimum Empirical Divergence (IMED) proposed by Honda and Takemura (201T). The general idea behind this algorithm is, following the intuition given by lower bound, narrow on the current best arm and its neighbourhood for pulling an arm at given time step.
Notations. The empirical mean of the rewards from the arm is denoted by (o(() E (a, X,/N. if (t) > 0 otherwise. We also denote by (t) max A (t)
and (+) argmax Phe (1) respectively the current best mean and the current set of optimal arms. aeA
3.1 The IMED-UB algorithm.
We first pull each arm once. For all arm A and time step t we introduce the IMED index
(t) (t) (t) (t)) + Iog(NN(t)),
with the convention 0 00 = 0. This index can be seen as transportation cost for moving sub- optimal arm to an optimal one plus an exploration term: the logarithm of the number of pulls. When an optimal arm is considered, the transportation cost is null and there is only the exploration part. Note that, as stated in Honda and Takemural [201 (I) is an index the weaker sense since cannot be determined only by samples from the arm a but also uses the empirical mean of the current optimal arm. We define IMED-UB (Indexed Minimum Empirical Divergence for Unimodal Bandits), described in Algorithm to be the algorithm consisting of pulling arm ag {āt JUV; with

---

minimum index at each time step t, where is az E a e.A Na- (t) is a current best arm. This is natural algorithm since the lower bound the regret given in Proposition 2 involves only the arms in Va., the neighbourhood of the arm a" of maximal mean.
Algorithm 1 IMED-UB
Pull each arm once
for t =
do
Choose 0j argmin Na- (t) (chosen arbitrarily) a (t)
Pull 0++1 E argmin (t) (chosen arbitrarily)
(e(a;) JUVa
end for
3.2 Asymptotic optimality of IMED-UB
In this section, we state the main theoretical result of this paper.
Theorem (Upper bounds) Let us consider set of distributions D D and let a* its optimal arm. Let Va- be the sub-optimal arms in the neighbourhood of a². Then under the IMED- UB algorithm for all 0 <EE < <vv, for all horizon time T> 1, for all a a V...
1 au(e) log(T) 2d C2CC.vlogccT) +(1+ + d(2d + +3)
20 g22/200
ENIN, (T)) <
+
KL(HalMa-))
E²
and, for all & {a" JUV..
20 e
Ex[Na(T)] & 2dC. (loglc)) + d(1 + c5.) + d(2d + 3)
1,
g²
where d the maximum degree of nodes G, eu = mina 1 M 1//.1/2 1/2
of maxx (v x-pour (X): yl E [Mva- &, [al] and ce, Cg > are the constants involved Theorem 15 aEA (.).)) is a non-negative function depending only on v such that lim or (e)==) =0 (see Section 4.1 for e
more details).
In particular one can note that the arms in the neighbourhood of the optimal one are pulled (log((T) times while the other sub-optimal arms are pulled O (log(T)) of times under IMED-UB. This coherent with the lower bound that only involves the neighbourhood of the best arm. More precisely, combining Theorem 5 and the chain rule (I) gives the asymptotic optimality IMED-UB with respect
to the lower bound of Proposition 2
Corollary 6 (Asymptotic optimality) With the same notations in Theorem IMED-UB UB algorithm
5 then under the
R(v,T)
A
limsup T log(T) < c(v)) => Σ
KLL(HalMa-)
finite time analysis of IMED-UB is provided in following Section
IMED-UB finite time analysis
At a high level, the key interesting step of the proof is to realize that the considered algorithm implies empirical lower and empirical upper bounds on the numbers of pulls (see Lemmal Lemma 8). Then, based on concentration lemmas (see Section B). the algorithm- based empirical lower bounds ensure the reliability of the estimators of interest (Lemmal 12p. Interestingly, this makes use of arguments based recent concentration of measure that enable to control the concentration without adding some log log bonus (such a bonus was required for example in the initial analysis of the KL-UCB strategy from CCppéé et al. (013)). Then, combining the reliability of these estimators with the obtained algorithm-base empirical upper bounds, we obtain upper bounds on the average numbers of pulls (Thcorem 5). The proof is concise to fit mostly in the next few pages.

---

4.1 Notations
Let us consider v E D and let us denote by a" best arm. recall that for a E A, Va =
{a' A: (a, a') E } is the neighbourhood of arm in graph G= G=(A,, E), and that
Me
pal
d= max aEA [Vl, Eu
min asæ'
(2)
2
Then, there exists a function (.) such that for all 0 < for all a + a²,
KL(Ha -E) < <(++ap(=)) (L(Hal)")
(3)
and lim + (E) = O. At each time step > 1, a is arbitrarily chosen in argmin (t) where aEAr(()
A (t) = argmax (a (t).
aEA
4.2
Algorithm-based empirical bounds
The IMED-UB algorithm implies inequalities between the indexes that can be rewritten as inequalities on the numbers of pulls. While lower bounds involving log(!) may be expected in view of the asymp- totic regret bounds, show lower bounds the numbers of pulls involving instead log ( (Na.:1 (4)) the logarithm of the number pulls of the current chosen arm. We also provide upper bounds on Na.+1 (t) involving log(t).
We believe that establishing these empirical lower and upper bounds is key element of our proof technique, that is of independent interest and not priori restricted to the unimodal structure.
Lemma (Empirical lower bounds) Under IMED-UP UB, at each step time t for all a Vat.
(og(Na.110 (1) & (a(1) (L) (1)) + log (N. (1))
(4)
and
Na (t) & Na; (t).
(5)
Proof For a A.A, by definition, we have [a(t) - ((())=NN(()KL())((( (ogg (f),, hence
log( (()) & (a).
This implies, since the arm with minimum index is pulled, log(Naets (1) < Tacts (1)
min Ia < Iay (t) log (Na; (t)). By taking the 1 the last inequality allows us
a'e(a; joDiag to conclude.
Lemma (Empirical upper bounds) Under IMED-UB UB each step time 1 AA,
Nar (1) KL (1)]7² (1)) & log(t).
(6)
Proof As above, by construction we have
Tayn (1) & Ta; (1).
remains, to conclude, to note that
Na (t)KL (t)l < Iarn (f),
and
lag (1) log( (1) < log(!).
5

---

4.3 Non-reliable current means
For all arms a, E A and for all accuracy E > O, let E a.. (E) be the set of times where the current mean of arm e-deviates from above while arm a has more pulls than the current pulled arm a',
E+ (e) [1] ar+l = a', No No(1), Pa(t) > Ma +
We similarly define
(E) = (t
[1, [
ac+1 = a', (o) & No(t), Pa(t) & Na - -
(8)
We also define
Ea (s) = E+ U
U (s).
Definition 9 (KL-log deviation) For >> O, the couple of arms (a, a') E A² shows cT-Koo deviation time step t2 1 if the following conditions are satisfied
11) 01+1 d
2 (t) & Pa -
(3) log( N. & Na (a(t) (L) + log( (N)))
For all couple of arms (a, a') A² and for all accuracy >>> 0. let Ke Ko couple of arms a') shows -K-llg deviation, that is
(E) be the set of times where
(
(1) d++1 a'
(T) (5) = LE [1]
(2) (a(t) & -a
(3) log(Nac (a)( (L( log((N
(10)
We note that
(e) C (K)
We can now resort to concentration arguments in order to control the size of these sets, which yields the following upper bounds. We defer the proof to Appendix A.l
Lemma 10 (Bounded subsets of times) For >>> 0, for (a, EA,
20
Ey | [t)
Ey 1 (e) $
x²
Ey (sar (T) & &l+c- + 20 Log(c:T))
where o² max aEA
Xxmpor (X): n'Elum ee Hul]. co Ce 0 are the constants involved in Theo-
rem 75
4.4 Non-reliable current best arm
For accuracy 0, (*) be the times t> that do not belong g+ 07 (E) and where some of the current best arm के differs from a",
t E a24s (E)
}
(* = t A
{.
(1I)
aj # a*
Lemma 11 (Relation between subsets of times)
Under IMED-UB, UB, for all accuracy 0 < <E<6, <
min Uia- 1p-pppl 1/2 afd
C U (Ev))
(12)
2l aEVar

---

Proof
Let us consider E Since 0i fa", there exists E Va such that
Pa > Par
(13)
Then, since ब Eargmax Pa(t), we have
Pa- (t) - 1 (t) > (t()).
(14)
Since tE t
& a4aa
(E). By considering empirical lower bounds (5) and Equation 7 we
have
Pa; + > Pa; (t).
(15)
By combining Equations
14 and
15
it comes
Pag + 7 (1) > (l)
(16)
Since E <EE Ma Pa; /2, Equation 13 and previous Equation (16) imply
Pa Ev > Pag (t) 2 (t)
(17)
Since E Vay, empirical lower bounds (4 imply
log( Na (t)) < (t(t) (t + log(NNatt))
(18)
The classical monotonic properties (L(.I.) and Equation
imply
{
(a(t) < EE
(19)
(ta( & (L(Pa(t))ao -6
Combining Equations 17 and 19). we get
(t) < Ma Ev Log(NNat1 (t)) (o)()))L((a(()))) + log((N
(20)
which means E KK (Ev).
4.5 Reliable current means and current best arm
In this subsection, we characterize subsets of times where both the mean of current pulled arm and the optimal mean are well-estimated. Let us consider for 0< Ev,, for a a=a".
a+41 a441 n
g+ ( (s) U (al
Eggar U 11 (e)
(21)
Then, Lemma implies
Ue (s) C U
(22)
d'E(a)uV, d'EV,r
In particular, from Lemma 10 and previous Equation 22
we have
2d(d + 1) 20 2 /20
20 E/2
(aa))
+ d
+1 +1 Col + 20c 2 Mlg(ceT)
x²
+3
20 E./20? d(2d + 33
+ d (1
[ +
+ 2C, (oooloo())TT
(23)
2²
where d= A= Val is the maximum degree of nodes in graph G.
Lemma 12 (Reliable current means) Under IMED-UB UB, for all accuracy < < Eu
min [a 1/ for all sub-optimal am a # a", for all time step & U,(E), > |A], such that aza'
a++1 =0,
a = a'
(+) > 4*
(a(t) & Ha +
7

---

4.6 Upper bounds on the numbers of pulls of sub-optimal arms
In this subsection, we now combine the different results of the previous subsections to prove Theo- rem
Proof [Proof of Theorem 5 For 0< for a a", let consider (f,,()), [A], such that
a++1 a. From empirical upper bounds (6). we have
(t) KL( (f)) & log(t).
(24)
From Lemma 12 and Algorithm 1 we have aE VA.. and (1) S - T7" (t). From classical
monotonic properties of KL(-)+) and Equation (3) we have KL(Pa (4) (1)) > (L -8) 2
(1)ax(e)) (I-(Halu"). In view of Equation 24 this implies
a Va.
vI $ ua(e), > [A], such that ac+1 a,
(1 + (x))))
(25)
Na(t) <
(L(palu*)
For all arm A.A, for all time step f. [A], we denote by
Ta (t) = max (t' E [[AA] ;t]
ar4+ = a and t' &
(26)
the last time step before time step / that does not belong Ma(e) such that we pull arm a.
Then, from Equations 25 and 26 we have
Va # a", Vt 1, Na(t)
Na(1A)+
+
Σ
4
[or+1=0}
131
1+
(aon)=a (Ell(())
I (or ugu, AA
1+ [s]s + Σ
L (ar_1=0 (e
1 [[((E)] + (ngVa.)
00+ (nEV..) x (N)(T(t))
(1 (x))) (t)(
1+ [c)( + +(EEV=))
(L(Haa(4*)
(1+ (a)))) log(t)
1 [.((s) + LUEV..1
(L(Ualur*
This implies
(1 + ax(e)) + [Ma(E))+ (L(ll()*
+1 if E Va.
Va va 1, No(t) <
(27)
(e) +1
if $ Va..
From Equation
23
averaging these incqualities allows us to conclude.
5 Numerical experiments
In this section, we compare empirically the following algorithms OSUB, UTS [Combes and Proutiere 2014 Trinh et al., 2020) and IMED-UB described in Algorithm [ We illustrate how performs the IMED UB algorithm under Bernoulli, Gaussian (variance o² = 0.25) or Exponential distribution assumption. For the experiments we consider a graph G with maximal degree d 2 and the unimodal unimodal vectors of means f (0.05, 0010. 0.15, 0.20, 0.25, 0.20, 0.15, 0010, 0.05), and average regrets over 500 runs for each distribution family. Based on these experiments (Figure TT) seems that IMED-UB UB competes with OSUB and UTS.
8

---

Unimodal means
Bernoulli distributions
0.25
75
0.2
Mean
0.15
Regret
50
0.1
IED MEDD-LS
0.05
0-
1
2
3
4
5
6
7
8
9
2000
4000
Arm
Time step
Gaussian distributions (var 0.25)
Exponential distributions
30
Regret
Regret
csus UTS
10
MED MED
NCD
0
MED UB
2000
4000
2000
4000
Time step
Time step
Figure I: Cumulative regrets averaged over 500 runs.
Conclusion
In this paper, we have revisited the setup of unimodal multi-armed bandits: We introduced novel variant based on the IMED algorithm. This algorithm does not separate exploration from exploitation rounds and is proven optimal for one-dimensional exponential family distributions. Remarkably, the IMED-UB algorithm do not require any optimization procedure, which can be interesting for practitioners. We also provided novel proof algorithm, in which make explicit empirical lower and upper bounds, before tackling the handling of bad events by specific concentration tools. This proof technique greatly simplifies and shorten the analysis of IMED-UB Last, we provided numerical experiments that show the practical effectiveness IMED-UB
Acknowledgments
This work has been supported by the French Ministry of Higher Education and Research, Inria, the French Agence Nationale de la Recherche (ANR) under grant ANR- 1AN-166CCE4000002 (the BADASS project), the MEL, the I-Site ULNE regarding project
Pierre Ménard supported by SFI Bachsen-Anhall for the project REBCI 2S/201//10//000222 by the Investitionsbank Anbalt.Anhalt.

---

References
Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
R. Agrawal, D. Teneketzis, and V. Anantharam. Asymptotically efficient adaptive allocation schemes for controlled iid processes: Finite parameter space. IEEE Transactions on Automatic Control, 34 (3), 1989.
A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for Markov decision processes. Mathematics of Operations Research, 22(1):222-25 225-222,, 1997.
O. Cappé, A. Garivier, O.-A. Maillard, R. Munos, and G. Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 4163)1111-1541, 2013.
R. Combes and A. Proutiere. Unimodal bandits: Regret lower bounds and optimal algorithms. In International Conference Machine Learning, 2014.
R. Combes, S. Magureanu, and A. Proutiere. Minimal exploration in structured stochastic bandits. In Advances in Neural Information Processing Systems, pages 1763-1771, 2017.
R. Degenne, H. Shao, and W. Koolen. Structure adaptive algorithms for stochastic bandits. In H. D. III and Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learming Research, pages 2443-2452. PMLR, 13-18 Jul 2020. httt::///////reeeeeeee
mlr ppress/v119/degnnnnee
.html
A. Durand, O.-A. Maillard, and Pineau. Streaming kernel regression with provably adaptive mean, variance, and regularization. arXiv preprint arXiv: 1eXiv:/708.000 1006.00788 2017.
T. L. Graves and T. L. Lai. Asymptotically efficient adaptive choice of control laws incontrolled markov chains. SIAM journal on control and optimization, 35(3):715-72) 15-743, 1997.
J. Honda and A. Takemura. An asymptotically optimal policy for finite support models in the multiarmed bandit problem. Machine Learning, 85(3)3361-391, 2011.
Honda and A. Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. Machine Learning, 16:3721-3756, 2015.
T. L. Lai. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, pages 1091-1114, 1987.
T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Lattimore and C. Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statistics, pages 728-737, 2017.
S. Magureanu. Efficient Online Learning under Bandit Feedback. PhD thesis, KTH Royal Institute of Technology, 2018
Magureanu, R. Combes, and A. Proutiere. Lipschitz bandits: Regret lower bounds and optimal algorithms. Machine Learning, 35:1-25, 2014.
O.-A. Maillard. Boundary crossing probabilities for general exponential families. Mathematical Methods of Statistics, 27(1):1-31, 2018.
H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematics Society, 58:527-535, 1952.
N. Srinivas. A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 1015-1022. Omnipress, 2010.
W. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-244 1933.
10

---

W. R. Thompson. On a criterion for the rejection of observations and the distribution of the ratio of deviation sample standard deviation. The Annals of Mathematical Statisties, 6(4):214-219, 1935.
C. Trinh, E. Kaufmann, C. Vernade, and R. Combes. Solving bernoulli rank-one bandits with unimodal thompson sampling. In International Conference on Algorithmic Learning Theory, 2020.
Y. Yu and S. Mannor. Unimodal bandits. In Proceedings of the 28th International Conference on International Conference Machine Learning, pages 41-48, 2011.


Reviews:
[{"review_id": "r9MdFE7aM2j", "reviewer": "Reviewer_Sby4", "summary": "The paper tackles the problem of unimodal bandits where it looks at an algorithm based on the IMED index which follows the general idea of the OSUB algorithm. The main novelty of the approach is the analysis which does not rely on distinctions between exploration and exploitation rounds and the added benefit of the IMED indexes not requiring solving an optimisation problem.\nThe paper is mostly dedicated to the regret analysis but also provides a set of experiments showcasing the numerical performance of the algorithm.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I think this paper falls short due to presentation. My main concern is the clarity of the proof, which contains the main contribution of the work and which I believe is not clearly written and I found hard to assess its correctness (please find suggestions for improvement in the Clarity section).\n\nOriginality: The problem solved here has been the target of quite some attention over the past and benefits from a rich literature of results both theoretical and empirical. The originality of the paper comes from applying the IMED index and an analysis that, although follows the same lines as previous regret bound proofs, avoids the need for incorporating dedicated exploration/exploitation rounds in the algorithm. The main architecture of the proof is similar to that of the OSUB algorithm: split all rounds when suboptimal arms are played into sets based on which means are poorly estimated and bound these sets using existing concentration inequalities. \n\nQuality: The paper seems technically sound. The proof feels correct though it is very hard to parse and verify correctness due to how the sets are defined and can probably be substantially clarified. To me it is not obvious whether the sets being bounded in the proof cover all rounds when suboptimal arms are played, though my intuition is that the algorithm should indeed be asymptotically optimal. The experiments show the competitiveness of the algorithm, though not a substantial improvement over the state-of-the-art.\n\nClarity: Given that the regret analysis constitutes the main contribution of this paper, I think clarity should be substantially improved here. As is the proof leaves a lot of work to the reader to disentangle, in my opinion. I would have liked to see a clear breakdown of how the sets of rounds when suboptimal arms are played being bounded contain all rounds when \"bad\" arms are played. I suggest this be present in the main architecture of the proof, and I would also recommend starting with the main proof architecture and moving the other supporting lemmas second. There is plenty of space for such a detailed description of how the sets being bounded tie in together. Please also improve the quality of the plots and provide higher resolution graphs - it is hard to read the name of the algorithms as is.\n\nSignificance: Overall I feel the results are significant, and could lead to more use of the IMED indexes in bandit algorithms in order to obtain regret guarantees without the extra effort needed to come up with forced exploitation mechanisms. \n\n______________\nAfter rebuttal: I have raised my score to 6 as I feel the results in the paper are significant and the clarity of the paper is not perceived as negatively by the other reviewers (which eases my main concern).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None come to mind.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "oNuNqTsh5BK", "reviewer": "Reviewer_pkQP", "summary": "The paper handles the unimodal bandit setting with reward distributions in an exponential family. The proposed algorithm, IMED-UB, is based on IMED's index and a logarithmic finite-time upper-bound of its regret is proven. The second term in IMED-UB's bound is in $\\sqrt{\\log T}$, which is worse than the second term in OSUB's and UTS's bounds. However, empirically the proposed algorithm has the same regret or a smaller regret than OSUB and UTS on a linear graph with 9 nodes.\n\nThe algorithm and the proof of its regret-bound are interesting. However, some points would benefit from a more thorough investigation.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "From an algorithmic point of view, the use of IMED's index for the unimodal setting is strait-forward, except for the removal of the exploitation rule. It's worth noting that Equation (5) in Lemma 7 highlights that IMED's index enforces the exploitation of the leader in the same proportions as OSUB's forced exploitation. However, IMED's index adapts the exploitation.\n\nThe originality of the paper lies in the proof of its upper-bound which is not a strait-forward combination of OSUB's and IMED's ones. As the corresponding bound is close from the one of state-of-the art algorithms, the paper would benefit from a thorough comparison of these bounds.\n\nMoreover, the authors mention that the proposed algorithm does not require any optimisation procedure. I guess they refer to the optimization procedure required by KL-based index. Again, a more thorough discussion would be much welcome. In the context of unimodal bandits, the index computation is preceded by the identification of the best arm (among $|A|$ arms), while the index is only computed for the $d+1 <= |A|$ arm in the neighborhood of the leader. Which one of both steps is the most costly is application dependent, and I would expect such algorithm to be used in contexts where $d << |A|$.\n\nFinally, the experimental section could include larger and more complex graphs. It could also mention the computation times to support the interest of removing the optimization procedure of KL-based index.\n\n## typos\n* L3, L12: aN algorithm\n* L31: with algorithms (remove the 'a')\n* L91: section A novel algorithm\n* L107 where $\\hat...$ (remove 'is')\n* L113: remove the mention to KLUCB-UB\n* Eq (13), Eq (14) : subscript $t$ is missing for $\\hat{a}^*$\n* L227: 'unimodal' is doubled\n\n# Post-rebuttal and discussions\nThe reviews and authors' responses strengthened my opinion with respect to this paper.\n\nHowever, as reviewer Sby4, I consider the presentation of the proof would be enhanced by presenting in the introduction of section 4 the split of iterations:\n* $U\\_a(\\\\epsilon)$ vs $[1,T]\\\\setminus U\\_a(\\\\epsilon)$\n* the split of $U\\_a(\\\\epsilon)$ as expressed in Equations (21) and (22)\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The potential negative societal impacts were not discussed in the paper, while the bandits are used to fuel recommender systems which, by identifying user's tastes, tend to lock up users in their \"bubble\". \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Y1YqvsAsHIM", "reviewer": "Reviewer_8esZ", "summary": "The authors propose a novel algorithm for unimodal bandits with stochastic i.i.d. rewards. They prove that this algorithm achieves the information theoretic upper bound derived and attained by the state of the art algorithms. Their algorithm is based on extending the idea of IMED (for classical bandits) to the unimodal settings. They also compare their algorithm with the state of the art using numerical experiments. Overall the results are interesting, the paper is well written and easy to follow, and the analysis seems elegant.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Some remarks are below.\n\n1) The authors mention OSSB, which involves computing the regret lower bound, and then attempting to match the Graves-Lai optimization program by computing its solution and then selecting an arm in order to match the constraints of this program. In fact, their algorithm does precisely this, since $I_a(t)$ quantifies the violation of the constraint $N_a(t) KL( \\hat \\mu_a,\\mu^\\star) \\ge \\log(t)$, and the arm with minimal index is selected.\n\n2) In Section 4, the authors argue that the analysis of (Cappé et al,2013) required some $\\log \\log$ terms to appear for everything to hold. However, as far as I remember, those terms we shown to be necessary, using an argument based on the law of the iterated logarithm. Perhaps the authors could expand on their statement or give a pointer to the place in the paper of (Cappé et al,2013) where the spurious $\\log \\log$ terms appear. \n\n3) The regret analysis presented in Theorem 5 features additional terms (with respect to the lower bound) and it is not completely clear how large those terms actually might be. More specifically:\n- It is understood that the most important regime is when $\\epsilon \\to 0$. The authors could perhaps explicitly state in the theorem how all the terms such as $\\sigma^2_\\epsilon$, $\\alpha_\\epsilon$ when $\\epsilon \\to 0$ scale in order to assess whether or not they can be neglected in practice. For instance  $\\sigma^2_\\epsilon \\to \\mu_a(1-\\mu_a)$ in this regime. \n- The dependency on the gap  $\\epsilon_{nu} = \\min_{a,a'} |\\mu_a - \\mu_{a'}|$ should be highlighted. In fact, when two sub-optimal arms have the same mean, this gap becomes $0$ and the upper bound of Theorem 5 becomes void. \n- The bound scales exponentially in $1/Var(X)$, and becomes uninformative whenever some sub-optimal arm has little to no variance. Is this dependency needed, and if so, why ?\n- The bound scales as the square degree $d^2$. This $d^2$ term comes from the analysis of Section 4.3, which requires summing over all pairs of arms. Is this dependency necessary ? For instance, if the graph has a degree $d = K/2$ where $K$ is the number of arms, this would imply that the algorithm has a regret scaling like $O(K^2)$ which is  worse than a simple algorithm that ignores the unimodal structure, whose regret would scale as $O(K)$.\n\n4) The numerical experiments seem to be a bit less thorough than the theoretical part, and they do not seem to answer some of the questions left open by the theoretical analysis:\n- does the regret actually scale with the square degree ?\n- does the regret actually becomes large when two sub-optimal arms have the same mean ?\nThis would be useful in assessing the link between the theoretical and actual performance. Also, there are no confidence intervals presented.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The committee has appreciated the technical value of this paper as well as its significance for the community. We strongly encourage the authors to take into account the remarks that were made on the presentation and writing for the final version of their work.
Decision: Accept (Poster)