Journal of Machine Learning Research 1–15, 2017

Algorithmic Learning Theory 2017

A minimax and asymptotically optimal algorithm for stochastic
bandits
Pierre Ménard

PIERRE . MENARD @ MATH . UNIV- TOULOUSE . FR

arXiv:1702.07211v2 [stat.ML] 20 Sep 2017

Aurélien Garivier

AURELIEN . GARIVIER @ MATH . UNIV- TOULOUSE . FR

Institut de Mathématiques de Toulouse; UMR5219
Université de Toulouse; CNRS
UPS IMT, F-31062 Toulouse Cedex 9, France

Editors: Steve Hanneke and Lev Reyzin

Abstract
We propose the kl-UCB++ algorithm for regret minimization in stochastic bandit models with
exponential families of distributions. We prove that it is simultaneously asymptotically optimal
(in the sense of Lai and Robbins’ lower bound) and minimax optimal. This is the first algorithm
proved to enjoy these two properties at the same time. This work thus merges two different lines of
research with simple and clear proofs.
Keywords: Stochastic multi-armed bandits, regret analysis, upper confidence bound (UCB), minimax optimality, asymptotic optimality.

1. Introduction
For regret minimization in stochastic bandit problems, two notions of time-optimality coexist. On
the one hand, one may consider a fixed model: the famous lower bound by Lai and Robbins (1985)
showed that the regret of any consistent strategy should grow at least as C(µ) log(T ) 1−o(1) when
the horizon T goes to infinity. Here, C(µ) is a constant depending solely on the model. A strategy
with a regret upper-bounded by C(µ) log(T ) 1 + o(1) will be called in this paper asymptoticallyoptimal. Lai and Robbins provided a first example of such a strategy in their seminal work. Later,
Garivier and Cappé (2011) and Maillard et al. (2011) provided finite-time analysis for variants of
the UCB algorithm (see Agrawal (1995); Burnetas and Katehakis (1996); Auer et al. (2002a)) which
imply asymptotic optimality. Since then, other algorithms like Bayes-UCB (Kaufmann et al., 2012)
and Thompson Sampling (Korda et al., 2013) have also joined the family.
On the other hand, for a fixed horizon T one may assess the quality of a strategy by the greatest
regret
√ suffered in all possible bandit models. If the regret of a bandit strategy is upper-bounded by
C ′ KT (the optimal rate: see Auer et al. (2002b) and Cesa-Bianchi and Lugosi (2006)) for some
numeric constant C ′ , this strategy is called minimax-optimal. The PolyINF and the MOSS strategies
by Audibert and Bubeck (2009) were the first proved to be minimax-optimal.
Hitherto, as far as we know, no algorithm was proved to be at the same time asymptoticallyand minimax-optimal. Two limited exceptions may be mentioned: the case of two Gaussian arms
is treated in Garivier et al. (2016a); and the OC-UCB algorithm of Lattimore (2015) is proved to
be minimax-optimal and almost problem-dependent optimal for Gaussian multi-armed bandit prob-

c 2017 P. Ménard & A. Garivier.

M ÉNARD G ARIVIER

lems. Notably, the OC-UCB algorithm satisfies another worthwhile property of finite-time instance
near-optimality, see Section 2 of Lattimore (2015) for a detailed discussion.
Contributions. In this work, we put forward the kl-UCB++ algorithm, a slightly modified version
of kl-UCB+ algorithm discussed in Garivier et al. (2016a) as an empirical improvement of UCB,
and analyzed in Kaufmann (2016). This bandit strategy is designed for some exponential distribution families, including for example Bernoulli and Gaussian laws. It borrows from the MOSS
algorithm of Audibert and Bubeck (2009) the idea to divide the horizon by the number of arms
in order to reach minimax optimality. We prove that it is at the same time asymptotically- and
minimax-optimal. This work thus merges the progress which has been made in different directions towards the understanding of the optimism principle, finally reconciling the two notions of
time-optimality.
Insofar, our contribution answers a very simple and natural question. The need for simultaneous
minimax- and problem-dependent optimality could only be addressed in very limited settings by
means that could not be generalized to the framework adopted in our paper. Indeed, forp
a given
horizon T , the worst problem depends on T : it involves arms separated by a gap of order K/T .
Treating the T -dependent problems correctly for all T appears as a quite different task than catching
the optimal, problem-dependent speed of convergence for every fixed bandit model. We show in
this paper that the two goals can indeed be achieved simultaneously.
Combining the two notions of optimality requires a modified exploration rate. We stick as much
as possible to existing algorithms and methods, introducing just what is necessary to obtain the
desired results. Starting from that of kl-UCB (so as to have a tight asymptotic analysis), one has
to completely cancel the exploration bonus of the arms that have been drawn roughly T /K times.
The consequence is very slight and harmless in the case where the best arm is much better than the
others, but essential in order to minimize the regret in the worst case where the best arm ispbarely
distinguishable from the others. Indeed, when the best arm is separated by a gap of order K/T
from the suboptimal arms,
√ we can not afford to draw more than T /K times a suboptimal arm so as
to get a regret of order KT .
We present a general yet simple proof, combining the best elements of the above-cited sources
which are simplified as much as possible and presented in a unified way. To this end, we develop
new deviation inequalities, improving the analysis of the different terms contributing to the regret.
This analysis is made in the framework which we believe is the best compromise between simplicity
and generality (simple exponential families). This permits us to treat, among others, the Bernoulli
and the Gaussian case at the same time. More fundamentally, this appears to us as the right, simple
framework for the analysis, which emphasizes what is really required to have simple lower- and
upper-bounds (the possibility to make adequate changes of measure, and Chernoff-type deviation
bounds).
The paper is organized as follows. In Section 2, we introduce the setting and assumptions
required for the main results, Theorems 1 and 2, which are presented in Section 3. We give the
entire proofs of these results in Sections 4 and 5, with only a few technical lemmas proved in
Appendix A. We conclude in Section 6 with some brief references to possible future prospects.

2. Notation and Setting
Exponential families. We consider a simple stochastic bandit problem with K arms indexed by
a ∈ {1, . . . , K}, with K > 2. Each arm is assumed to be a probability distribution of some
2

KL -UCB

++

ALGORITHM

canonical one-dimensional exponential family νθ indexed by θ ∈ Θ. The probability law νθ is
assumed to be absolutely continuous with respect to a dominating measure ρ on R, with a density
given by
Z

dνθ
(x) = exp(xθ − b(θ)), where b(θ) = log exθ dρ(x) and Θ = θ ∈ R : b(θ) < +∞ .
dρ
R

It is well-known that b is convex, twice differentiable on Θ, that b′ (θ) = E(νθ ) and b′′ (θ) =
V (νθ ) > 0 are respectively the mean and the variance of the distribution νθ . The family can thus
be parametrized by the mean µ = b′ (θ), for µ ∈ I = b′ (Θ) := (µ̄− , µ̄+ ). The Kullback-Leibler
divergence between two distributions is KL(νθ , νθ′ ) = b(θ ′ ) − b(θ) − b′ (θ)(θ ′ − θ). This permits
to define the following divergence on the set of arm expectations: for µ = E(νθ ) and µ′ = E(νθ′ ),
we write
kl(µ, µ′ ) := KL(νθ , νθ′ ) .
For a minimax analysis, we need to restrict the set of means to bounded interval: we suppose
that each arm νθ satisfies µ = b′ (θ) ∈ [µ−, µ+] ⊂ I for two fixed real numbers µ+ , µ− . Our
analysis requires a Pinsker-like inequality; we therefore assume that the variance is bounded in the
exponential family: there exists V > 0 such that


−1
sup b′′ b′ (µ) = sup V νb′ −1 (µ) 6 V < +∞ .
µ∈I

µ∈I

This implies that for all µ, µ′ ∈ I,

kl(µ, µ′ ) >

1
(µ − µ′ )2 .
2V

(1)

In the sequel, we denote by F the set of bandit problems ν satisfying these assumptions. By the
usual Pinsker inequality, this setting includes in particular
 Bernoulli bandits with V = 1/4 and
′
′
′
kl(µ, µ ) = µ log(µ/µ ) + (1 − µ) log (1 − µ)/(1 − µ ) (by convention, 0 log 0 = 0 log 0/0 = 0).
This also includes (bounded) Gaussian bandits with known variance σ 2 , with the choice V = σ 2
and kl(µ, µ′ ) = (µ − µ′ )2 /(2σ 2 ).
Regret. The K arms are denoted νθ1 , . . . νθK , and the expectation of arm a ∈ {1, . . . , K} is
denoted by µa . At each round 1 6 t 6 T , the player pulls an arm At and receives an independent
draw Yt of the distribution νθAt . This reward is the only piece of information available to the player.
PT
The best mean is µ⋆ = maxa=1,...,K µa . We denote by Na (T ) =
t=1 I{At =a} the number of
draws of arm a up to and including time T . In this work, the goal is to minimize the expected regret
#
" T
" T
#
K
X
X
X
 


⋆
⋆
Yt = E
RT = T µ − E
µ − µ At =
µ⋆ − µa E Na (T ) .
t=1

t=1

a=1

Lai and Robbins (1985) proved that if a strategy is uniformly efficient, that is if it is such that under
any bandit model of a sufficiently rich family (such as an exponential family described above)
RT = o(T α ) holds for every α > 0, then it needs to draw any suboptimal arm a at least as often as


E Na (T ) >


log(T )
1 − o(1) .
⋆
kl(µa , µ )
3

M ÉNARD G ARIVIER

In light of the previous equality, this directly implies an asymptotic lower bound on RT / log(T ).
On the other side, a straightforward adaptation of the the proof of Theorem A.2 of Auer et al.
(2002b) shows that there exists a constant C ′ depending only on the considered family F of distributions such that
√

sup RT > C ′ min KT , T ,
ν∈F

where the supremum is taken over all bandit problems ν in F. Note that the notion of minimaxoptimality is defined here up to a multiplicative constant, in contrast to the definition of (problemdependent) asymptotic optimality. For a discussion on the minimax and asymptotic lower bounds,
we refer to Garivier et al. (2016b) and references therein.

3. The kl-UCB++ Algorithm
We denote by µ
ba,n the empirical mean of the first n rewards from arm a. The empirical mean of
arm a after t rounds is
t
1 X
Ys I{As =a} .
µ
ba (t) = µ
ba,Na (t) =
Na (t)
s=1

Parameters: The horizon T and an exploration function g : N 7→ R+ .
Initialization: Pull each arm of {1, .., K} once.

For t = K to T − 1, do

1. Compute for each arm a the quantity
(

)
g Na (t)
Ua (t) = sup µ ∈ I : kl µ
ba (t), µ 6
.
Na (t)


(2)

2. Play At+1 ∈ arg maxa∈{1,..,K} Ua (t).

The kl-UCB++ algorithm is a slight modification of algorithm kl-UCB+ of Garivier and Cappé
(2011) and of the kl-UCB-H+ analyzed in Kaufmann (2016). It uses the exploration function g
given by
!
!!
T
T
2
log+
+1
,
(3)
g(n) = log+
Kn
Kn

where log+ (x) := max log(x), 0 . The exploration function g borrows the general form with
the extra exploration rate from the kl-UCB algorithm, the division by the number of draws from
kl-UCB+ , and the division by the number of arm from MOSS.
The following results state that the kl-UCB++ algorithm is simultaneously minimax- and asymptotically-optimal.
Theorem 1 (Minimax optimality) For any family F satisfying the assumptions detailed in Section 2, and for any bandit model ν ∈ F, the expected regret of the kl-UCB++ algorithm is upperbounded as
√
(4)
RT 6 76 V KT + (µ+ − µ− )K .
4

KL -UCB

++

ALGORITHM

Theorem 2 (Asymptotic
optimality) For any bandit model ν ∈ F, for any suboptimal arm a and
p
any δ such that 22V K/T 6 δ 6 (µ⋆ − µa )/3,




loglog(T )
log(T )
+O
(5)
E Na (T ) 6
kl(µa + δ, µ⋆ − δ)
δ2
which implies the asymptotic optimality (see the end of the proof in Section 5 for an explicit bound).

Theorems 1 and 2 are proved in Sections 4 and 5 respectively. The main differences between the two
proofs are discussed at the beginning of Section 5. Note that the two regret bounds of Theorems 1
and 2 also apply to all [0, 1]-valued bandit models, with the value V = 1/4, as the deviations of
[0, 1]-valued random variables are dominated by those of a Bernoulli distribution with the same
mean (this is discussed for example in Cappé et al. (2013)). However, the kl-UCB++ algorithm is
not asymptotically optimal then: the regret bound in log(T )/kl(µa , µ∗ ) is not optimal in that case.
Asymptotic optimality would require tight distribution-dependent, non-parametric upper confidence
bounds (for example based on the empirical-likelihood method, as in the above cited paper). This
is out of the scope of this work (and would require a lot more space).

4. Proof of Theorem 1
This proof merges merges ideas presented in Bubeck and Liu (2013) for the analysis of the MOSS
algorithm and from the analysis of kl-UCB in Cappé et al. (2013) (see also Kaufmann (2016)). It is
divided into the following steps:
Decomposition of the regret. Let a∗ be the index of an optimal arm. Since by definition of the
strategy Ua∗ (t) 6 UAt+1 (t) for all t > K − 1, the regret can be decomposed as follows:
+

−

RT 6 K(µ − µ ) +

T
−1
X

t=K

|

−1


 TX
E UAt+1 (t) − µAt+1 .
E µ − U (t) +



⋆

a∗

{z

}

A

t=K

|

{z
B

(6)

}

p
We define δ0 = 22V K/T ; since the bound (4) is otherwise trivial, we assume in the sequel that
δ0 6 1. For the first term A, as in the proof of MOSS algorithm, we carefully upper bound the
probability that appears inside the integral thanks to a ’peeling trick’. The second term B is easier
to handle since we can reduce the index to UCB-like-index thanks to the Pinsker inequality (1) and
proceed as in Bubeck and Liu (2013).
Step 1: Upper-bounding A. Term A is concerned with the optimal arm a∗ only. Two words of
intuition: since Ua∗ (t) is meant to be an upper confidence bound for µ⋆ , this term should not be too
large, at least as long as the the confidence level controlled by function g is large enough – but when
the confidence level is low, the number of draws is large and deviations are unlikely.
Upper-bounding term A boils down to controlling the probability that µ⋆ is under-estimated at
time t. Indeed,
Z +∞
h
 ⋆


 i
⋆
E µ − Ua∗ (t) 6 E µ − Ua∗ (t) + 6
P u < µ⋆ − Ua∗ (t) du
0
Z +∞

6 δ0 +
P Ua∗ (t) 6 µ⋆ − u du ,
(7)
δ0

5

M ÉNARD G ARIVIER

and we need to upper bound the left-deviations of the mean of arm a∗ . On the event {Ua∗ (t) 6
µ⋆ − u}, we have that µ
ba∗ (t) 6 Ua∗ (t) 6 µ⋆ − u < µ⋆ , and by definition of Ua∗ (t) it holds that

 g Na∗ (t)
⋆
kl µ
ba∗ (t), µ >
.
Na∗ (t)
Consequently,






P Ua∗ (t) 6 µ⋆ − u 6 P µ
ba∗ (t) 6 µ⋆ − u and kl µ
ba∗ (t), µ⋆ > g Na∗ (t) /Na∗ (t)

6 P ∃1 6 n 6 T, µ
ba∗ ,n 6 µ⋆ − u and kl(b
µa∗ ,n , µ⋆ ) > g(n)/n .

(8)

For small values of n, the dominant term is given by kl(b
µa∗ ,n , µ⋆ ) > g(n)/n, whereas for large
⋆
n the event µ
ba∗ ,n 6 µ − u is quite unlikely. This is why we split the probability in two terms,
proceeding as follows. Let f be the function defined, for u > δ0 , by


T u2
2V
.
f (u) = 2 log
u
2V K
Our choice of δ0 implies that f (u)K/T 6 exp(−3/2), and thus


T
T
f (u) <
and
log
> 3/2 .
K
Kf (u)

(9)

In particular, for n 6 f (u) it holds that




T
T
2
1 + log
.
g(n) = log
Kn
Kn
It appears that f (u) is the right place where to split the probability of Equation (8): defining
kl+ (p, q) := kl(p, q)I{p6q} , we write

P ∃1 6 n 6 T, µ
ba∗ ,n 6 µ⋆ − u and kl(b
µa∗ ,n , µ⋆ ) > g(n)/n 6


P ∃1 6 n 6 f (u), kl+ (b
µa∗ ,n , µ⋆ ) > g(n)/n + P ∃f (u) 6 n 6 T, µ
ba∗ ,n 6 µ⋆ − u .
|
{z
} |
{z
}
A1

A2

(10)

Controlling terms A1 and A2 is a matter of deviation inequalities.
Step 1.1: Upper-bounding A1 . The term A1 , which involves self-normalized devation probabilities, can be upper-bounded thanks to a ’peeling trick’ as in the proof of Theorem 5 from
Audibert and Bubeck (2009). We assume that f (u) > 1, for otherwise A1 = 0. We use the
grid f (u)/β ℓ+1 6 n 6 f (u)/β ℓ , where the real β > 1 will be chosen later. We write
!
+∞
X
f (u)
f (u)
A1 6
P ∃ ℓ+1 6 n 6 ℓ , kl+ (b
µa∗ ,n , µ⋆ ) > γℓ ,
(11)
β
β
ℓ=0
|
{z
}
Aℓ1

6

KL -UCB

++

ALGORITHM

where
T βℓ

log

Kf (u)

1 + log2

T
Kf (u)

!!

.
f (u)/β ℓ
Thanks to Doob’s maximal inequality (see Lemma 4 in Appendix A),
!
f
(u)
Aℓ1 6 exp − ℓ+1 γℓ = e−ℓ log(β)/β−C/β ,
β
γℓ =

where
T
T
1 + log2
C := log
Kf (u)
Kf (u)

!!!

.

(12)

Plugging this last inequality into (11), together with the numerical inequality of Lemma 3 (see
Appendix A), we get
A1 6

+∞
X

e−ℓ log(β)/β−C/β =

ℓ=0

1
1−

e− log(β)/β
6

But thanks to Equation (9),

e−C/β
e

elog(β)/β − 1

T
T
1 + log2
C = log
Kf (u)
Kf (u)


e−C/β 6 2e max β, β/(β − 1) e−C/β .

!!!

T
> log
Kf (u)

!

>

3
.
2

It is now time to choose β := C/(C − 1), so that β 6 2C and β/(β − 1) = C. Together with the
definition of f , this choice yields
!!!
log

T
Kf (u)

1 + log2

T
Kf (u)

A1 6 4e2 Ce−C = 4e2

1 + log

2

T
Kf (u)

and therefore
2 Kf (u)

A1 6 4e
as, for all x > 1,

T

16e2 V K
=
log
T u2

r

!

!
T
u
2V K

Kf (u)
,
T

(13)

(14)



log x 1 + log2 (x)

6 1.
1 + log2 (x)
Step 1.2: Upper-bounding A2 . The term A2 is more simple to handle, as it does not involve selfnormalized deviations. Thanks to the maximal inequality (recalled in Equation (33) of Appendix A)
and thanks to the Pinsker-like inequality (1),
A2 6 e−u

2 f (u)/2V

7

=

2V K
.
T u2

(15)

M ÉNARD G ARIVIER

Putting Equations (7) to (15) together, we obtain that

E µ⋆ − Ua∗ (t) 6 δ0 +


Z

+∞
δ0

16e2 V K
log
T u2

r

T
u
2V K

!

+

2V K
du .
T u2

(16)

It remains only to conclude with some calculus:
!
"
!#+∞
r
r
Z +∞
16e2 V K
T
T
16e2 V K
u du = −
log e
u
log
T u2
2V K
Tu
2V K
δ0
δ0
r
√
2
√  K
16e V
= √
log e 11
.
T
22
Similarly,

Z

+∞
δ0

r r
V
K
2V K
du = 2
,
T u2
22 T

and replacing δ0 by its value we obtain from Equation (16) the following relation:
r

√ 
√
 ⋆
 √
16e2
2
K
E µ − Ua∗ (t) 6 V
.
22 + √ log e 11 + √
T
22
22
Summing over t from K to T − 1, this yields:


√
√
√ 
√
16e2
2
√
√
log e 11 +
A6 V
22 +
KT .
22
22

(17)

Step 2: Upper-bounding B. Term B is of different nature, since typically UAt+1 (t) > µAt+1 .
However, as for the term A, we first reduce the problem to the upper-bounding of a probability:
B6

T
−1
X

δ0 +

+∞

δ0

t=K

6 T δ0 +

Z

Z


P UAt+1 (t) − µAt+1 > u du

−1
+∞ T
X

δ0

t=K


P UAt+1 (t) − µAt+1 > u du .

(18)


The event UAt+1 (t) − µAt+1 > u is typical if NAt+1 (t) is small, and corresponds to a deviation
of the sample mean otherwise. In order to handle this correctly, we first get rid of the randomness
of NAt+1 (t) by the pessimistic trajectorial upper bound from Bubeck and Liu (2013)
T
−1
X

t=K

I

UAt+1 (t)−µAt+1 >u

6

T X
K
X

n=1 a=1

I

Ua,n −µa >u

.

In addition, we simplify the upper bound thanks to our assumption (1) that some Pinsker type
inequality is available:
)
(
r
 g(n)
g(n)
6 Ba,n := µ
ba,n + 2V
.
(19)
Ua,n := sup µ ∈ I : kl µ
ba,n , µ 6
n
n
8

KL -UCB

++

ALGORITHM

Hence, B can be upper-bounded as
B 6 T δ0 +

K Z
X
a=1

T
+∞ X

δ0

n=1

P(Ba,n − µa > u)du .

(20)

P
Then, we need only to upper bound Tn=1 P(Ba,n − µa >u) for each arm a ∈ {1, . . . , K}. We cut
the sum at the critical sample size n(u) where the event Ba,n − µa > u becomes atypical: for
u > δ0 , let n(u) be the integer such that



8V
T u2
n(u) =
log
.
u2
8V K
For n > n(u) it holds that

r

2V

u
g(n)
6√ .
n
2

(21)

Indeed, as log(1 + x2 ) 6 x for all x > 0, we have


g(n)
T
4V
2V
6
log+
,
n
n
Kn

also observe that h(x) := log x/ log(x) / log(x) is such that h(x) 6 1 for x > 11/4, and thus for
n > n(u) and u > δ0




T u2
T
4V
g(n)
u2
u2
6
log+
h
.
2V
6
6
n
n(u)
Kn(u)
2
8V K
2
Therefore, cutting the sum in (20) at n(u), we obtain:
T
X

n=1

P(Ba,n − µa > u) 6 n(u) − 1 +
6 n(u) − 1 +

T
X

n=n(u)
T
X

n=n(u)

P µ
ba,n − µa > u −

p

2V g(n)/n


√ 
P µ
ba,n − µa > u 1 − 1/ 2



T
X
T u2
8V
P(b
µa,n − µa > cu) ,
+
6 2 log
u
8V K



(22)

n=n(u)

√
where c := 1 − 1/ 2. It remains to integrate Inequality (22) from u = δ0 to infinity. The first
summand involves the same integral as we have already met in the upper bound of term A1 :
r
r !r


Z +∞
T u2
8V
V
11
T
log e
.
log
du = 16
2
u
8V K
22
4
K
δ0
For the remaining summand, Inequality (33) yields
T
X

n=n(u)

P(b
µa,n − µa > cu) 6

T
X

n=n(u)

9

e−

u 2 c2 n
2V

1

6
e

u 2 c2
2V

.
−1

M ÉNARD G ARIVIER

Thus, as ex − 1 > x for all x > 0,
Z +∞
1
δ0

e

u 2 c2
2V

du 6
−1

Z

+∞

δ0

2V
2
du = 2
2
2
u c
c

r

V
22

r

T
,
K

Putting everything together starting from Inequality (22), we have proved that
!r
r
r !
Z +∞ X
T
2
V
11
T
P(Ba,n − µa > u)du 6
16 log e
+ 2
.
22
4
c
K
δ0
n=1
By Equation (20), replacing δ0 by its value finally yields
!
r !
√
√
√
2
11
16
+√
B6 V
22 + √ log e
KT .
4
22
22c2

(23)

Conclusion of the proof.
A+B 6

√

V

It just remains to plug Inequalities (17) and (23) into Equation (6):
!
r !
√
√ 
√
16e2
2
2
16
11
KT
+√
2 22 + √ log e 11 + √ + √ log e
2
4
22
22
22
22c

√
6 76 V KT ,

which concludes the proof.

5. Proof of Theorem 2
The analysis of asymptotic optimality shares many elements with the minimax analysis, with some
differences however. The decomposition of the regret into two terms A and B is similar, but localized on a fixed sub-optimal arm a ∈ {1, . . . , K}: we analyze the number of draws of a and not
directly the regret (and we do not need to integrate the deviations at the end). We proceed roughly as
in the proof of Theorem 1 for term A, which involves the deviations of an optimal arm. For term B,
which stands for the behavior of the sub-optimal arm a, a different (but classical) argument is used,
as one cannot simply use the Pinsker-like Inequality (1) if one wants to obtain the correct constant
(and thus asymptotic optimality).


Decomposition of E Na (T ) . If arm a is pulled at time t + 1, then by definition of the strategy
Ua∗ (t) 6 Ua (t) for any index a∗ of an optimal arm. Thus, for any fixed δ to be chosen later,


At+1 = a ⊆ µ∗ − δ > Ua (t) ∪ {µ∗ − δ < Ua (t) and At+1 = a

⊆ µ∗ − δ > Ua∗ (t) ∪ {µ∗ − δ < Ua (t) and At+1 = a .
As a consequence,

T
−1
−1
X
 TX



P Ua∗ (t) 6 µ∗ − δ +
P µ∗ − δ < Ua (t) and At+1 = a ,
E Na (T ) 6 1 +
t=K

|

{z
A

and it remains to bound each of these terms.

}

t=K

|

10

{z
B

}

(24)

KL -UCB

Step 1: Upper-bounding A.

P Ua∗ (t) 6 µ∗ − δ 6

++

ALGORITHM

As in the proof of Theorem 1, we write



ba∗ ,n 6 µ⋆ − δ ,
P ∃1 6 n 6 f (δ), kl+ (b
µa∗ ,n , µ⋆ ) > g(n)/n + P ∃f (δ) 6 n 6 T, µ
{z
} |
{z
}
|
A1

A2

(25)

where we use the same function


2V
T δ2
f (δ) = 2 log
.
δ
2KV
Thanks to the Inequality (13) that we saw in the proof of Theorem 1, we obtain that
!!!
log

T
Kf (δ)

1 + log2

A1 6 4e2

log

T
Kf (δ)

T
Kf (δ)

f (δ)

!

log

T
Kf (δ)

!

K
16e2 2V K
6 2
.
T
δ
T

Here, we used that for all x > e3/2 , since the condition δ2 > 22V K/T implies that f (δ)K/T 6
e−3/2 ,


log x 1 + log2 (x)
log(x)
 6 2,
62
and
log(x)
log x/ log(x)
and that



T δ2
log 2V K

f (δ)
2V


= 2
δ
T
T δ2
log Kf (δ)
log 2V
K

1

log T δ2 /(2V K)

.

Thanks to the maximal inequality recalled in Appendix A as Equation (33), it holds that
A2 6 e−δ

2 f (δ)/(2V

)

=

2V K
.
T δ2

(26)

Putting Equations (25) to (26) together yields:
A 6 (16e2 + 1)

Step 2: Upper-bounding B.


µ∗ − δ < Ua (t) and At+1

2V K
.
δ2

(27)

Thanks to the definition of Ua (t) it holds that
n
o


= a ⊆ kl µ
ba (t), µ∗ − δ 6 g Na (t) /Na (t) and At+1 = a
11

M ÉNARD G ARIVIER

Together with the following classical argument for regret analysis in bandit models, this yields:
B6

6

6

T
−1
X

t=K
T
X

n=1
T
X

n=1




P kl µ
ba (t), µ∗ − δ 6 g Na (t) /Na (t) and At+1 = a

P kl(b
µa,n , µ∗ − δ) 6 g(n)/n







P kl(b
µa,n , µ∗ − δ) 6 log T /K 1 + log2 (T /K) /n ,

(28)

as it holds g(n) 6 g(1). Now, let n(δ) be the integer defined as


 
log T /K 1 + log2 (T /K)
.
n(δ) = 


kl(µa + δ, µ∗ − δ)


Then, for n > n(δ),



log T /K 1 + log2 (T /K) /n 6 kl(µa + δ, µ∗ − δ) .

We cut the sum in (28) at n(δ), so that
B 6 n(δ) − 1 +

6

T
X

n=n(δ)


P kl(b
µa,n , µ∗ − δ) 6 kl(µa + δ, µ∗ − δ)



log T /K 1 + log2 (T /K)
kl(µa +

δ, µ∗

− δ)

(µ⋆

+

T
X

n=n(δ)


P kl(b
µa,n , µ∗ − δ) 6 kl(µa + δ, µ∗ − δ) .

(29)

Recall that by assumption δ <
− µa )/3, using the inclusion

kl(b
µa,n , µ∗ − δ) 6 kl(µa + δ, µ∗ − δ) ⊆ {b
µa,n > µa + δ} ,

together with Inequality (33), we obtain that
T
X

n=n(δ)

T
X


P µ
ba,n > µa + δ
P kl(b
µa,n , µ∗ − δ) 6 kl(µa + δ, µ∗ − δ) 6
n=n(δ)
∞
X

e−nδ

6

2 /(2V

)

=

n=1

and Equation (29) yields
B6

log(T )
+
kl(µa + δ, µ∗ − δ)



2
log 1/K 1 + log (T /K)
kl(µa +

δ, µ∗

− δ)

1

eδ2 /(2V )

+

2V
.
δ2

−1

6

2V
,
δ2

(30)

Conclusion of the proof. It just remains to plug Inequalities (27) and (30) into Equation (24):


2
log
1/K
1
+
log
(T
/K)


2V K
log(T )
+
+ (16e2 + 2) 2 + 1 ,
E Na (T ) 6
kl(µa + δ, µ∗ − δ)
kl(µa + δ, µ∗ − δ)
δ

and we obtain Equation (5). Choosing δ of order 1/ loglog(T )1/2 yields the asymptotic optimality.
12

KL -UCB

++

ALGORITHM

6. Conclusion and Perspectives
We have proved that the kl-UCB++ algorithm is both minimax- and asymptotically-optimal for the
exponential distribution families described in Section 2. So far, this algorithm requires the horizon
T as a parameter: to keep the proofs clear and simple, we have deferred to future work the analysis
of an anytime variant. We believe, though, that obtaining such an extension should be possible by
using the tools developed in Degenne and Perchet (2016). In addition, we have focused in this paper
on asymptotic optimality without trying to derive explicit finite-time bounds: we believe that this
would have impaired the clarity and simplicity of the reasoning. But it is certainly a challenging and
important objective to design a general strategy that would, in addition to minimax- and asymptotic
optimality, would also reach the important notion of finite-time instance near optimality of Lattimore
(2015).
From a more technical point of view, it may be possible to suppress the extra log2 exploration
term in the definition of the confidence bonus g in Equation (3). This is carried out in Garivier et al.
(2016a) using some particularities of the Gaussian distributions; using an improved Chernoff bound
such as Talagrand (1995) may allow considering more general cases. Finally, we defer the consideration of general bounded probability distributions (with non-parametric upper-confidence bounds)
to future work.

Acknowledgments
This work was partially supported by the CIMI (Centre International de Mathématiques et d’Informatique) Excellence program. The authors acknowledge the support of the French Agence Nationale de la Recherche (ANR), under grants ANR-13-BS01-0005 (project SPADRO) and ANR-13CORD-0020 (project ALICIA).

Appendix A. Some Technical Lemmas
Lemma 3 For all β > 1 we have
1
elog(β)/β

−1


6 2 max β, β/(β − 1) .

Proof Inequality (31) is equivalent to
elog(β)/β − 1 >

1
min(1, β − 1) .
2β

If β > 2, then
log(2)
1
>
.
β
2β
Otherwise, if 1 < β < 2, as the function β 7→ log(β)/(β − 1) is non-increasing one gets
 log(β)
β  log(β)/β
e
−1 >
> log(2) > 1/2 .
β−1
β−1
elog(β)/β − 1 > elog(2)/β − 1 >

13

(31)

M ÉNARD G ARIVIER

Lemma 4 (Maximal Inequality) Let N and M be two real numbers in R+ × R+ , let γ be a real
number in R+∗ , and let µ
bn be the empirical mean of n random variables i.i.d. according to the
distribution νb′ −1 (µ) . Then

P ∃N 6 n 6 M, kl+ (b
µn , µ) > γ 6 e−N γ .

(32)

Proof If γ > kl(µ̄− , µ) or µ
bn > µ the Inequality (32) is trivial. Else, there exist two real numbers
z < µ and λ < 0 such that
γ = kl(z, µ) = λz − ϕµ (λ) ,

where ϕµ denotes the the log-moment generating function of νb′ −1 (µ) . Since on the event ∃N 6
n 6 M, kl+ (b
µn , µ) > γ one has at the same time
µ
bn 6 µ ,

λb
µn − ϕµ (λ) > λz − ϕµ (λ) = γ

and

λnb
µn − nϕµ (λ) > N γ ,

we can write that



P ∃N 6 n 6 M, kl+ (b
µn , µ) > γ 6 P ∃N 6 n 6 M, λnb
µn − nϕµ (λ) > N γ
6 exp(−N γ) ,


by Doob’s maximal inequality for the exponential martingale exp λnb
µn − nϕµ (λ) .

As a simple consequence of this Lemma 4 and Inequality (1), it holds that:
for every x 6 µ,
for every x > µ,

References

2 /(2V

)

,

(33)

−N (x−µ)2 /(2V

)

.

(34)

P(∃N 6 n 6 M, µ
bn 6 x) 6 e−N (x−µ)

P(∃N 6 n 6 M, µ
bn > x) 6 e

Rajeev Agrawal. Sample mean based index policies with o(log n) regret for the multi-armed bandit
problem. Advances in Applied Probability, 27(4):1054–1078, 1995. ISSN 00018678. URL
http://www.jstor.org/stable/1427934.
Jean-Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits.
In COLT, pages 217–226, 2009.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit
problem. Machine learning, 47(2-3):235–256, 2002a.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48–77, 2002b.
Sébastien Bubeck and Che-Yu Liu. Prior-free and prior-dependent regret bounds for thompson
sampling. In Advances in Neural Information Processing Systems, pages 638–646, 2013.
Apostolos N Burnetas and Michael N Katehakis. Optimal adaptive policies for sequential allocation
problems. Advances in Applied Mathematics, 17(2):122–142, 1996.

14

KL -UCB

++

ALGORITHM

Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, Gilles Stoltz, et al.
Kullback–leibler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, 41(3):1516–1541, 2013.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university
press, 2006.
Rémy Degenne and Vianney Perchet. Anytime optimal algorithms in stochastic multi-armed
bandits. In Proceedings of the 33rd International Conference on International Conference
on Machine Learning - Volume 48, ICML’16, pages 1587–1595. JMLR.org, 2016. URL
http://dl.acm.org/citation.cfm?id=3045390.3045558.
Aurélien Garivier and Olivier Cappé. The kl-ucb algorithm for bounded stochastic bandits and
beyond. In COLT, pages 359–376, 2011.
Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-commit strategies. In
Advances in Neural Information Processing Systems, pages 784–792, 2016a.
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of
regret in bandit problems. arXiv preprint arXiv:1602.07182, 2016b.
Emilie Kaufmann. On bayesian index policies for sequential resource allocation. arXiv preprint
arXiv:1601.01190, 2016.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On bayesian upper confidence bounds for
bandit problems. In AISTATS, pages 592–600, 2012.
Nathaniel Korda, Emilie Kaufmann, and Remi Munos. Thompson sampling for 1-dimensional
exponential family bandits. In Advances in Neural Information Processing Systems, pages 1448–
1456, 2013.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances
in applied mathematics, 6(1):4–22, 1985.
Tor Lattimore. Optimally confident ucb: Improved regret for finite-armed bandits. arXiv preprint
arXiv:1507.07880, 2015.
O-A. Maillard, R. Munos, and G. Stoltz. A finite-time analysis of multi-armed bandits problems
with Kullback-Leibler divergences. In Proceedings of the 23rd Annual Conference on Learning
Theory, Budapest, Hungary, 2011.
Michel Talagrand. The missing factor in hoeffding’s inequalities. In Annales de l’IHP Probabilités
et statistiques, volume 31, pages 689–702, 1995.

15

