arXiv:1606.02448v1 [cs.LG] 8 Jun 2016

Multiple-Play Bandits in the Position-Based Model
Paul Lagrée
Université Paris Sud, Université Paris Saclay
paul.lagree@u-psud.fr
Claire Vernade, Olivier Cappé
Université Paris Saclay, Télécom ParisTech, CNRS
claire.vernade@telecom-paristech.fr
cappe@enst.fr
Abstract
Sequentially learning to place items in multi-position displays or lists is a task that can be cast into the
multiple-play semi-bandit setting. However, a major concern in this context is when the system cannot decide
whether the user feedback for each item is actually exploitable. Indeed, much of the content may have been
simply ignored by the user. The present work proposes to exploit available information regarding the display
position bias under the so-called Position-based click model (PBM). We first discuss how this model differs
from the Cascade model and its variants considered in several recent works on multiple-play bandits. We
then provide a novel regret lower bound for this model as well as computationally efficient algorithms that
display good empirical and theoretical performance.

1

Introduction

During their browsing experience, users are constantly provided – without having asked for it – with clickable
content spread over web pages. While users interact on a website, they send clicks to the system for a very
limited selection of the clickable content. Hence, they let every unclicked item with an equivocal answer: the
system does not know whether the content was really deemed irrelevant or simply ignored. In contrast, in
traditional multi-armed bandit (MAB) models, the learner makes actions and observes at each round the reward
corresponding to the chosen action. In the so-called multiple play semi-bandit setting, when users are presented
with L items, they are assumed to provide feedback for each of those items.
Several variants of this basic setting have been considered in the bandit literature. The necessity for the user
to provide feedback for each item has been called into question in the context of the so-called Cascade Model
[7, 13, 5] and its extensions such as the Dependent Click Model (DCM) [19]. Both models are particularly suited
for search contexts, where the user is assumed to be looking for something relative to a query. Consequently, the
learner expects explicit feedback: in the Cascade Model each valid observation sequence must be either all zeros
or terminated by a one, such that no ambiguity is left on the evaluation of the presented items, while multiple
clicks are allowed in the DCM.
In the Cascade Model, the positions of the items are not taken into account in the reward process because the
learner is assumed to obtain a click as long as the interesting item belongs to the list. Indeed, there are even
clear indications that the optimal strategy in a learning context consists in showing the most relevant items at
the end of the list in order to maximize the amount of observed feedback [13] – which is counter-intuitive in
recommendation tasks.
To overcome these limitations, [5] introduces weights – to be defined by the learner – that are attributed to
positions in the list, with a click on position l ∈ {1, . . . , L} providing a reward wl , where the sequence (wl )l is
decreasing to enforce the ranking behavior. However, no rule is given for setting the weights (wl )l that control
the order of importance of the positions. The authors propose an algorithm based on KL-UCB [9] and prove a
lower bound on the regret as well as an asymptotically optimal upper bound.
Another way to address the limitations of the Cascade Model is to consider the DCM as in [19]. Here,
examination probabilities vl are introduced for each position l: conditionally on the event that the user effectively
1

scanned the list up to position l, he/she can choose to leave with probability vl and in that case, the learner is
aware of his/her departure. This framework naturally induces the necessity to rank the items in the optimal
order.
All previous models assume that a portion of the recommendation list is explicitly examined by the user
and hence that the learning algorithm eventually has access to rewards corresponding to the unbiased user’s
evaluation of each item. In contrast, we propose to analyze multiple-play bandits in the Position-based model
(PBM) [4]. In the PBM, each position in the list is also endowed with a binary Examination variable [7, 18]
which is equal to one only when the user paid attention to the corresponding item. But this variable, that is
independent of the user’s evaluation of the item, is not observable. It allows to model situations where the user is
not explicitly looking for specific content, as in typical recommendation scenarios.
Compared to variants of the Cascade model, the PBM is challenging due to the censoring induced by the
examination variables: the learning algorithm observes actual clicks but non-clicks are always ambiguous. Thus,
combining observations made at different positions becomes a non-trivial statistical task. Some preliminary ideas
on how to address this issue appear in the supplementary material of [12]. In this work, we provide a complete
statistical study of stochastic multiple-play bandits with semi-bandit feedback in the PBM.
We introduce the model and notations in Section 2 and provide the lower bound on the regret in Section 3. In
Section 4, we present two optimistic algorithms as well as a theoretical analysis of their regret. In the last section
dedicated to experiments, those policies are compared to several benchmarks on both synthetic and realistic data.

2

Setting and Parameter Estimation

We consider the binary stochastic bandit model with K Bernoulli-distributed arms. The model parameters
are the arm expectations θ = (θ1 , θ2 , . . . , θK ), which lie in Θ = (0, 1)K . We will denote by B(θ) the Bernoulli
distribution with parameter θ and by d(p, q) := p log(p/q) + (1 − p) log((1 − p)/(1 − q)) the Kullback-Leibler
divergence from B(p) to B(q). At each round t, the learner selects a list of L arms – referred to as an action –
chosen among the K arms which are indexed by k ∈ {1, . . . , K}. The set of actions is denoted by A and thus
contains K!/(K − L)! ordered lists; the action selected at time t will be denoted A(t) = (A1 (t), . . . , AL (t)).
The PBM is characterized by examination parameters (κl )1≤l≤L , where κl is the probability that the user
effectively observes the item in position l [4]. At round t, the selection A(t) is shown to the user and the learner
observes the complete feedback – as in semi-bandit models – but the observation at position l, Zl (t), is censored
being the product of two independent Bernoulli variables Yl (t) and Xl (t), where Yl (t) ∼ B(κl ) is non null when
the user considered the item in position l – which is unknown to the learner – and Xl (t) ∼ B(θAl (t) ) represents
PL
the actual user feedback to the item shown in position l. The learner receives a reward rA(t) = l=1 Zl (t), where
Z(t) = (X1 (t)Y1 (t), . . . , XL (t)YL (t)) denotes the vector of censored observations at step t.
In the following, we will assume, without loss of generality, that θ1 > · · · > θK and κ1 > · · · > κL > 0, in
order to simplify the notations. The fact that the sequences (θl )l and (κl )l are decreasing implies that the optimal
PT
list is a∗ = (1, . . . , L). Denoting by R(T ) = t=1 ra∗ − rA(t) the regret incurred by the learner up to time T , one
has
T X
L
X
X
X
E[R(T )] =
κl (θa∗l − E[θAl (t) ]) =
(µ∗ − µa ) E[Na (T )] =
∆a E[Na (T )],
(1)
t=1 l=1

a∈A

PL

a∈A

where µa = l=1 κl θal is the expected reward of action a, µ∗ = µa∗ is the best possible reward in average,
PT
∆a = µ∗ − µa the expected gap to optimality, and, Na (T ) = t=1 1{A(t) = a} is the number of times action a
has been chosen up to time T .
In the following, we assume that the examination parameters (κl )1≤l≤L are known to the learner. These
can be estimated from historical data [4], using, for instance, the EM algorithm [8] (see also Section 5). In
most scenarios, it is realistic to assume that the content (e.g., ads in on-line advertising) is changing much more
frequently than the layout (web page design for instance) making it possible to have a good knowledge of the
click-through biases associated with the display positions.
The main statistical challenge associated with the PBM is that one needs to obtain estimates and confidence
bounds for the components θk of θ from the available B(κl θk )-distributed draws corresponding to occurrences
of arm k at various positions l = 1, . . . , L in the list. To this aim, we define the following statistics: Sk,l (t) =

2

Pt−1

PL
Pt−1
PL
Zl (s)1{Al (s) = k}, Sk (t) = l=1 Sk,l (t), Nk,l (t) = s=1 1{Al (s) = k}, Nk (t) = l=1 Nk,l (t). We further
Pt−1
PL
require bias-corrected versions of the counts Ñk,l (t) = s=1 κl 1{Al (s) = k} and Ñk (t) = l=1 Ñk,l (t).
A time t, and conditionally on the past actions A(1) up to A(t − 1), the Fisher information for θk is given by
PL
I(θk ) = l=1 Nk,l (t)κl /(θk (1 − κl θk )) (see Appendix A). We cannot however estimate θk using the maximum
likelihood estimator since it has no closed form expression. Interestingly though, the simple pooled linear
estimator
θ̂k (t) = Sk (t)/Ñk (t),
(2)
s=1

considered in the supplementary material to [12], is unbiased and has a (conditional) variance of υ(θk ) =
PL
PL
( l=1 Nk,l (t)κl θk (1 − κl θk ))/( l=1 Nk,l (t)κl )2 , which is close to optimal given the Cramér-Rao lower bound.
Indeed, υ(θk )I(θk ) is recognized as a ratio of a weighted arithmetic mean to the corresponding weighted harmonic
mean, which is known to be larger than one, but is upper bounded by 1/(1 − θk ), irrespectively of the values of
the κl ’s. Hence, if, for instance, we can assume that all θk ’s are smaller than one half, the loss with respect to
the best unbiased estimator is no more than a factor of two for the variance. Note that despite its simplicity,
θ̂k (t) cannot be written as a simple sum of conditionally independent increments divided by the number of terms
and will thus require specific concentration results.
It can be checked that when θk gets very close to one, θ̂k (t) is no longer close to optimal. This observation
also has a Bayesian counterpart
will be discussed in Section 5. Nevertheless, it is always preferable to the
Pthat
L
“position-debiased” estimator ( l=1 Sk,l (t)/κl )/Nk,l (t) which gets very unreliable as soon as one of the κl ’s gets
very small.

3

Lower Bound on the Regret

In this section, we consider the fundamental asymptotic limits of learning performance for online algorithms under
the PBM. These cannot be deduced from earlier general results, such as those of [10, 6], due to the censoring in
the feedback associated to each action. We detail a simple and general proof scheme – using the results of [11] –
that applies to the PBM, as well as to more general models.
Lower bounds on the regret rely on changes of measure: the question is how much can we mistake the true
parameters of the problem for others, when observing successive arms? With this in mind, we will subscript all
expectations and probabilities by the parameter value and indicate explicitly that the quantities µa , a∗ , µ∗ , ∆a ,
introduced in Section 2, also depend on the parameter. For ease of notation, we will still assume that θ is such
that a∗ (θ) = (1, . . . , L).

3.1

Existing results for multiple-play bandit problems

Lower bounds on the regret will be proved for uniformly efficient algorithms, in the sense of [15]:
Definition 1. An algorithm is said to be uniformly efficient if for any bandit model parameterized by θ and for
all α ∈ (0, 1], its expected regret after T rounds is such that Eθ R(T ) = o(T α ).
For the multiple-play MAB, [1] obtained the following bound

lim inf
T →∞

K
X
Eθ R(T )
θL − θk
≥
.
log(T )
d(θk , θL )

(3)

k=L+1

For the “learning to rank” problem where rewards follow the weighted Cascade Model with decreasing weights
(wl )l=1,...,L , [5] derived the following bound
lim inf
T →∞

K
X
Eθ R(T )
θL − θk
≥ wL
.
log T
d(θk , θL )
k=L+1

Perhaps surprisingly, this lower bound does not show any additional term corresponding to the complexity of
ranking the L optimal arms. Indeed, the errors are still asymptotically dominated by the need to discriminate
irrelevant arms (θk )k>L from the worst of the relevant arms, that is, θL .
3

3.2

Lower bound step by step

Step 1: Computing the expected log-likelihood ratio. Denoting by Fs−1 the σ-algebra generated by the
past actions and observations, we define the log-likelihood ratio for the two values θ and λ of the parameters by
`(t) :=

t
X

log

s=1

p(Z(s); θ | Fs−1 )
.
p(Z(s); λ | Fs−1 )

(4)

Lemma 2. For each position l and each item k, define the local amount of information by


p(Zl (t); θ)
Al (t) = k ,
Il (θk , λk ) := Eθ log
p(Zl (t); λ)
PL PK
and its cumulated sum over the L positions by Ia (θ, λ) :=
l=1
k=1 1{al = k}Il (θk , λk ). The expected
log-likelihood ratio is given by
X
Eθ [`(t)] =
Ia (θ, λ)Eθ [Na (t)].
(5)
a∈A

The next proposition is adapted from Theorem 17 in Appendix B of [11] and provides a lower bound on the
expected log-likelihood ratio.
Proposition 3. Let B(θ) := {λ ∈ Θ |∀l ≤ L, θl = λl and µ∗ (θ) < µ∗ (λ) } be the set of changes of measure that
improve over θ without modifying the optimal arms. Assuming that the expectation of the log-likelihood ratio may
be written as in (5), for any uniformly efficient algorithm one has
P
Ia (θ, λ)Eθ [Na (T )]
≥ 1.
∀λ ∈ B(θ),
lim inf a∈A
T →∞
log(T )
Step 2: Variational form of the lower bound. We are now ready to obtain the lower bound in a form
similar to that originally given by [10].
Theorem 4. The expected regret of any uniformly efficient algorithm satisfies
lim inf
T →∞

Eθ R(T )
≥ f (θ) ,
log T

X

where f (θ) = inf

c0

∆a (θ)ca ,

a∈A

inf

s.t.

λ∈B(θ)

X

Ia (θ, λ)ca ≥ 1.

a∈A

Theorem 4 is a straightforward consequence of Proposition 3, combined with the expression of the expected
P
|A|
regret given in (1). The vector c ∈ R+ , that satisfies the inequality a∈A Ia (θ, λ)ca ≥ 1, represents the feasible
values of Eθ [Na (T )]/ log(T ).
Step 3: Relaxing the constraints. The bounds mentioned in Section 3.1 may be recovered from Theorem 4
by considering only the changes of measure that affect a single suboptimal arm.
Corollary 5.
f (θ) ≥ inf

c0

X

∆a (θ)ca ,

s.t.

a∈A

L
XX

1{al = k}Il (θk , θL )ca ≥ 1 ,

∀k ∈ {L + 1, . . . , K}.

a∈A l=1

Corollary 5 is obtained by restricting the constraint set B(θ) of Theorem 4 to ∪K
k=L+1 Bk (θ), where Bk (θ) :=
{λ ∈ Θ|∀j 6= k, θj = λj and µ∗ (θ) < µ∗ (λ)} .

3.3

Lower bound for the PBM

Theorem 6. For the PBM, the following lower bound holds for any uniformly efficient algorithm:
lim inf
T →∞

K
X
Eθ R(T )
≥
log T

∆vk,l (θ)
,
l∈{1,...,L} d(κl θk , κl θL )
min

k=L+1

where vk,l := (1, . . . , l − 1, k, l, . . . , L − 1).
4

(6)

Proof. First, note that for the PBM one has Il (θk , λk ) = d(κl θk , κl λk ). To get the expression given in Theorem 6
from Corollary 5, we proceed as in [5] showing that the optimal coefficients (ca )a∈A can be non-zero only for the
K − L actions that put the suboptimal arm k in the position l that reaches the minimum of ∆vk,l (θ)/d(κl θk , κl θL ).
Nevertheless, this position does not always coincide with L, the end of the displayed list, contrary to the case of
[5] (see Appendix B for details).
The discrete minimization that appears in the r.h.s. of Theorem 6 corresponds to a fundamental trade-off
in the PBM. When trying to discriminate a suboptimal arm k from the L optimal ones, it is desirable to put
it higher in the list to obtain more information, as d(κl θk , κl θL ) is an increasing function of κl . On the other
hand, the gap ∆vk,l (θ) is also increasing as l gets closer to the top of the list. The fact that d(κl θk , κl θL ) is
not linear in κl (it is a strictly convex function of κl ) renders the trade-off non trivial. It is easily checked that
when (θ1 − θL ) is very small, i.e. when all optimal arms are equivalent, the optimal exploratory position is l = 1.
In contrast, it is equal to L when the gap (θL − θL+1 ) becomes very small. Note that by using that for any
PK
PL
suboptimal a ∈ A, ∆a (θ) ≥ k=L+1 l=1 1{al = k}κl (θL − θk ), one can lower bound the r.h.s. of Theorem 6
PK
by κL k=L+1 (θL − θk )/d(κL θk , κL θL ), which is not tight in general.
Remark 7. In the uncensored version of the PBM – i.e., if the Yl (t) were observed –, the expression of Ia (θ, λ)
PL PK
is simpler: it is equal to l=1 k=1 1{Al (t) = k}κl d(θk , λk ) and leads to a lower bound that coincides with (3).
The uncensored PBM is actually statistically very close to the weighted Cascade model and can be addressed by
algorithms that do not assume knowledge of the (κl )l but only of their ordering.

4

Algorithms

In this section we introduce two algorithms for the PBM. The first one uses the CUCB strategy of [3] and
requires an simple upper confidence bound for θk based on the estimator θ̂k (t) defined in (2). The second
algorithm is based on the Parsimonious Item Exploration – PIE(L) – scheme proposed in [5] and aims at reaching
asymptotically optimal performance. For this second algorithm, termed PBM-PIE, it is also necessary to use a
multi-position analog of the well-known KL-UCB index [9] that is inspired by a result of [16]. The analysis of
PBM-PIE provided below confirms the relevance of the lower bound derived in Section 3.
PBM-UCB The first algorithm simply consists in sorting optimistic indices in decreasing order and pulling
the corresponding first L arms [3]. To derive the expression of the required “exploration bonus” we use an upper
confidence for θ̂k (t) based on Hoeffding’s inequality:
s
s
Sk (t)
Nk (t)
δ
U CB
Uk
(t, δ) =
+
,
Ñk (t)
Ñk (t) 2Ñk (t)
for which a coverage bound is given by the next proposition, proven in Appendix C.
Proposition 8. Let k be any arm in {1, . . . , K}, then for any δ > 0,

P UkU CB (t, δ) ≤ θk ≤ eδ log(t)e−δ .
Following the ideas of [6], it is possible to obtain a logarithmic regret upper bound for this algorithm. The
proof is given in Appendix D.
PL
Pl
Theorem 9. Let C(κ) = min1≤l≤L [( j=1 κj )2 /l + ( j=1 κj )2 ]/κ2L and ∆ = mina∈σ(a∗ )\a∗ ∆a , where σ(a∗ )
denotes the permutations of the optimal action. Using PBM-UCB with δ = (1 + ) log(t) for some  > 0, there
exists a constant C0 () independent from the model parameters such that the regret of PBM-UCB is bounded
from above by
!
X
L
1
E[R(T )] ≤ C0 () + 16(1 + )C(κ) log T
+
.
∆
κL (θL − θk )
∗
k∈a
/

The presence of the term L/∆ in the above expression is attributable to limitations of the mathematical
analysis. On the other hand, the absence of the KL-divergence terms appearing in the lower bound (6) is due to
the use of an upper confidence bound based on Hoeffding’s inequality.
5

PBM-PIE We adapt the PIE(l) algorithm introduced by [5] for the Cascade Model to the PBM in Algorithm 1
below. At each round, the learner potentially explores at position L with probability 1/2 using the following
upper-confidence bound for each arm k
( L
)


X
Sk,l (t)
Uk (t, δ) =
sup
q
Nk,l (t)d
, κl q ≤ δ ,
(7)
Nk,l (t)
min (t),1]
q∈[θk
l=1

PL
where θkmin (t) is the minimum of the convex function Φ : q 7→
l=1 Nk,l (t)d(Sk,l (t)/Nk,l (t), κl q). In other
positions, l = 1, . . . , L − 1, PBM-PIE selects the arms with the largest estimates θ̂k (t). The resulting algorithm is
presented as Algorithm 1 below, denoting by L(t) the L-largest empirical estimates, referred to as the “leaders”
at round t.
Algorithm 1 – PBM-PIE
Require: K, L, observation probabilities κ,  > 0
Initialization: first K rounds, play each arm at every position
for t = K + 1, . . . , T do
Compute θ̂k (t) for all k
L(t) ← top-L ordered arms by decreasing θ̂k (t)
Al (t) ← Ll (t) for each position l < L
B(t) ← {k|k ∈
/ L(t), Uk (t, (1 + ) log(T )) ≥ θ̂LL (t) (t)
if B(t) = ∅ then
AL (t) ← LL (t)
else
With probability 1/2, select AL (t) uniformly at random from B(t), else AL (t) ← LL (t)
end if
Play action A(t) and observe feedback Z(t); Update Nk,l (t + 1) and Sk,l (t + 1).
end for

The Uk (t, δ) index defined in (7) aggregates observations from all positions – as in PBM-UCB – but allows
to build tighter confidence regions as shown by the next proposition proved in Appendix E.
Proposition 10. For all δ ≥ L + 1,
P (Uk (t, δ) < θk ) ≤ eL+1



dδ log(t)e δ
L

L

e−δ .

We may now state the main result of this section that provides an upper bound on the regret of PBM-PIE.
Theorem 11. Using PBM-PIE with δ = (1 + ) log(t) and  > 0, for any η < mink<K (θk − θk+1 )/2, there exist
problem-dependent constants C1 (η), C2 (, η), C3 () and β(, η) such that
E[R(T )] ≤ (1 + )2 log(T )

K
X

κL (θL − θk )
C2 (, η)
+ C1 (η) + β(,η) + C3 ().
d(κL θk , κL (θL − η))
T
k=L+1

The proof of this result is provided in Appendix E. Comparing to the expression in (6), Theorem 11 shows
that PBM-PIE reaches asymptotically optimal performance when the optimal exploring position is indeed located
at index L. In other case, there is a gap that is caused by the fact the exploring position is fixed beforehand and
not adapted from the data.
We conclude this section by a quick description of two other algorithms that will be used in the experimental
section to benchmark our results.
Ranked Bandits (RBA-KL-UCB) The state-of-the-art algorithm for the sequential “learning to rank”
problem was proposed by [17]. It runs one bandit algorithm per position, each one being entitled to choose the
best suited arm at its rank. The underlying bandit algorithm that runs in each position is left to the choice of
the user, the better the policy the lower the regret can be. If the bandit algorithm at position l selects an arm
already chosen at a higher position, it receives a reward of zero. Consequently, the bandit algorithm operating
at position l tends to focus on the estimation of l-th best arm. In the next section, we use as benchmark the
Ranked Bandits strategy using the KL-UCB algorithm [9] as the per-position bandit.
6

1400

Regret R(T )

1000

250

Regret R(T )

1200

300
Lower Bound
BC-MP-TS
PBM-TS

800
600
400

150
100
50

200
0
102

200

Lower Bound
PBM-TS
PBM-UCB
PBM-PIE
RBA-KLUCB

103

Round t

104

0
100

105

(a) Average regret of PBM-TS and BC-

101

102
103
Round t

104

105

(b) Average regret of various algorithms on
synthetic data under the PBM.

MP-TS compared for high parameters.
Shaded areas: first and last deciles.

Figure 1: Simulation results for the suggested strategies.

PBM-TS The observations Zl (t) are censored Bernoulli which results in a posterior that does not belong to a
standard family of distribution. [12] suggest a version of Thompson Sampling called “Bias Corrected Multiple Play
TS” (or BC-MP-TS) that approximates the true posterior by a Beta distribution. We observed in experiments
that for parameter values close to one, this algorithm does not explore enough. In Figure 1(a), we show this
phenomenon for θ = (0.95, 0.85, 0.75, 0.65, 0.55). The true posterior for the parameter θk at time t may be written
as a product of truncated scaled beta distributions
Y α (t)
πt (θk ) ∝
θk k,l (1 − κl θk )βk,l (t) ,
l

where αk,l (t) = Sk,l (t) and βk,l (t) = Nk,l (t) − Sk,l (t). To draw from this exact posterior, we use rejection sampling
with proposal distribution Beta(αk,m (t), βk,m (t))/κm , where m = arg max1≤l≤L (αk,l (t) + βk,l (t)).

5

Experiments

5.1

Simulations

In order to evaluate our strategies, a simple problem is considered in which K = 5, L = 3, κ = (0.9, 0.6, 0.3)
and θ = (0.45, 0.35, 0.25, 0.15, 0.05). The arm expectations are chosen such that the asymptotic behavior can
be observed after reasonable time horizon. All results are averaged based on 10, 000 independent runs of the
algorithm. We present the results in Figure 1(b) where PBM-UCB, PBM-PIE and PBM-TS are compared to
RBA-KL-UCB. The performance of PBM-PIE and PBM-TS are comparable, the latter even being under the
lower bound (it is a common observation, e.g. see [12], and is due to the asymptotic nature of the lower bound).
The curves confirm our analysis for PBM-PIE and lets us conjecture that the true Thompson Sampling policy
might be asymptotically optimal. As expected, PBM-PIE shows asymptotically optimal performance, matching
the lower bound after a large enough horizon.

5.2

Real data experiments: search advertising

The dataset was provided for KDD Cup 2012 track 2 1 and involves session logs of soso.com, a search engine
owned by Tencent. It consists of ads that were inserted among search results. Each of the 150M lines from the
log contains the user ID, the query typed, an ad, a position (1, 2 or 3) at which it was displayed and a binary
reward (click/no-click). First, for every query, we excluded ads that were not displayed at least 1, 000 times
at every position. We also filtered queries that had less than 5 ads satisfying the previous constraints. As a
1 http://www.kddcup2012.org/

7

800

#records

min θ

max θ

5
5
6
6
6
8
11
11

216, 565
68, 179
435, 951
110, 071
147, 214
122, 218
1, 228, 004
391, 951

0.016
0.031
0.025
0.023
0.004
0.108
0.022
0.022

0.077
0.050
0.067
0.069
0.148
0.146
0.149
0.084

700
600
Regret R(T )

#ads (K)

500

PBM-TS
PBM-UCB
PBM-PIE
RBA-KLUCB

400
300
200
100
0
100

Table 1: Statistics on the queries: each line corresponds to
the sub-dataset associated with a query.

101

102
103
Round t

104

105

Figure 2: Performance of the proposed algorithms
under the PBM on real data.

result, we obtained 8 queries with at least 5 and up to 11 ads. For each query q, we computed the matrix of the
average click-through rates (CTR): Mq ∈ RK×L , where K is the number of ads for the query q and L = 3 the
number of positions. It is noticeable that the SVD of each Mq matrix has a highly dominating first singular value,
therefore validating the low-rank assumption underlying in the PBM. In order to estimate the parameters of the
problem, we used the EM algorithm suggested by [4, 8]. Table 1 reports some statistics about the bandit models
reconstructed for each query: number of arms K, amount of data used to compute the parameters, minimum
and maximum values of the θ’s for each model.
We conducted a series of 2, 000 simulations over this dataset. At the beginning of each run, a query was
randomly selected together with corresponding probabilities of scanning positions and arm expectations. Even if
rewards were still simulated, this scenario is more realistic since the values of the parameters were extracted
from a real-world dataset. We show results for the different algorithms in Figure 2. It is remarkable that
RBA-KL-UCB performs slightly better than PBM-UCB. One can imagine that PBM-UCB does not benefit
enough from position aggregations – only 3 positions are considered – to beat RBA-KL-UCB. Both of them are
outperformed by PBM-TS and PBM-PIE.

Conclusion
This work provides the first complete analysis of the PBM in an online context. The proof scheme used to obtain
the lower bound on the regret is interesting on its own, as it can be generalized to various other settings. The
tightness of the lower bound is validated by our analysis of PBM-PIE but it would be an interesting future
contribution to provide such guarantees for more straightforward algorithms such as PBM-TS or a ‘PBM-KLUCB’
using the confidence regions of PBM-PIE. In practice, the algorithms are robust to small variations of the
values of the (κl )l , but it would be preferable to obtain some control over the regret under uncertainty on these
examination parameters.

8

References
[1] V. Anantharam, P. Varaiya, and J. Walrand. Asymptotically efficient allocation rules for the multiarmed
bandit problem with multiple plays - part I: IID rewards. Automatic Control, IEEE Transactions on,
32(11):968–976, 1987.
[2] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford, 2013.
[3] W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications.
In Proc. of the 30th Int. Conf. on Machine Learning, 2013.
[4] A. Chuklin, I. Markov, and M. d. Rijke. Click models for web search. Synthesis Lectures on Information
Concepts, Retrieval, and Services, 7(3):1–115, 2015.
[5] R. Combes, S. Magureanu, A. Proutière, and C. Laroche. Learning to rank: Regret lower bounds and
efficient algorithms. In Proc. of the 2015 ACM SIGMETRICS Int. Conf. on Measurement and Modeling of
Computer Systems, 2015.
[6] R. Combes, M. S. T. M. Shahi, A. Proutière, et al. Combinatorial bandits revisited. In Advances in Neural
Information Processing Systems, 2015.
[7] N. Craswell, O. Zoeter, M. Taylor, and B. Ramsey. An experimental comparison of click position-bias models.
In Proc. of the Int. Conf. on Web Search and Data Mining. ACM, 2008.
[8] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM
algorithm. Journal of the royal statistical society. Series B, pages 1–38, 1977.
[9] A. Garivier and O. Cappé. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proc. of
the Conf. on Learning Theory, 2011.
[10] T. L. Graves and T. L. Lai. Asymptotically efficient adaptive choice of control laws in controlled markov
chains. SIAM journal on control and optimization, 35(3):715–743, 1997.
[11] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best arm identification in multi-armed
bandit models. Journal of Machine Learning Research, 2015.
[12] J. Komiyama, J. Honda, and H. Nakagawa. Optimal regret analysis of thompson sampling in stochastic
multi-armed bandit problem with multiple plays. In Proc. of the 32nd Int. Conf. on Machine Learning, 2015.
[13] B. Kveton, C. Szepesvári, Z. Wen, and A. Ashkan. Cascading bandits : Learning to rank in the cascade
model. In Proc. of the 32nd Int. Conf. on Machine Learning, 2015.
[14] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvári. Tight regret bounds for stochastic combinatorial
semi-bandits. In Proc. of the 18th Int. Conf. on Artificial Intelligence and Statistics, 2015.
[15] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics,
6(1):4–22, 1985.
[16] S. Magureanu, R. Combes, and A. Proutière. Lipschitz bandits: Regret lower bounds and optimal algorithms.
In Proc. of the Conf. on Learning Theory, 2014.
[17] F. Radlinski, R. Kleinberg, and T. Joachims. Learning diverse rankings with multi-armed bandits. In Proc.
of the 25th Int. Conf. on Machine learning. ACM, 2008.
[18] M. Richardson, E. Dominowska, and R. Ragno. Predicting clicks: estimating the click-through rate for new
ads. In Proc. of the 16th Int. Conf. on World Wide Web. ACM, 2007.
[19] K. Sumeet, B. Kveton, C. Szepesvári, and Z. Wen. DCM bandits: Learning to rank with multiple clicks. In
Proc. of the 33rd Int. Conf. on Machine Learning, 2016.

9

Properties of θ̂k (t) (Section 2)

A

Conditionnally to the actions A(1) up to A(t − 1), the log-likelihood of the observations Z(1), . . . , Z(t − 1) may
be written as
t−1 X
K X
L
X

1{Al (t) = k} [Zl (t) log(κl θk ) + (1 − Zl (t)) log(1 − κl θk )]

s= k=1 l=1

=

K X
L
X

Sk,l (t) log(κl θk ) + (Nk,l (t) − Sk,l (t)) log(1 − κl θk ).

k=1 l=1

Differenciating twice with respect to θk and taking the expectation of (Sk,l (t))l , contional to A(1), . . . , A(t − 1),
yields the expression of I(θk ) given in Section 2.

B

Proof of Theorem 4

B.1

Proof of Lemma 2

Under the PBM, the conditional expectation of the log-likelihood ratio defined in (4) writes
" t
#
L
XX
X
pal (Xl (s)Yl (s); θ)
log
Eθ [`(t)|A(1), . . . , A(t)] = Eθ
1{A(s) = a}
A(1), . . . , A(t)
pal (Xl (s)Yl (s); λ)
s=1 a∈A
l=1


t X
L
X
X
pal (Xl (s)Yl (s); θ)
A(s) = a
=
1{A(s) = a}
E log
pal (Xl (s)Yl (s); λ)
s=1
a∈A

=

X

Na (t)

a∈A

=

X

l=1

L X
K
X

1{al = k}d(κl θk , κl λk )

l=1 k=1

Na (t)Ia (θ, λ),

a∈A

using the notation Ia (θ, λ) =

B.2

PL PK
l=1

k=1

1{al = k}d(κl θk , κl λk ).

Details on the proof of Proposition 3

Lemma 12. Let θ = (θ1 , . . . , θK ) and λ = (λ1 , . . . , λK ) be two bandit models such that the distributions of all
arms in θ and λ are mutually absolutely continuous. Let σ be a stopping time with respect to (Ft ) such that
(σ < +∞) a.s. under both models. Let E ∈ Fσ be an event such that 0 < Pθ (E) < 1. Then one has
X
Ia (θ, λ)Eθ [Na (σ)] ≥ d(Pθ (E), Pλ (E)),
a∈A

where Ia (θ, λ) is the conditional expectation of the log-likelihood ratio for the model of interest.
The proof of this lemma directly follows from the above expressions of the log-likelihood ratio and from the
proof of Lemma 1 in Appendix A.1 of [11].
We simply recall the following technical lemma for completeness.
Lemma 13. Let σ be any stopping time with respect to (Ft ). For every event A ∈ Fσ ,
Pλ (A) = Eθ [1{A} exp(−`(σ))].
A full proof of Lemma 13 can be found in the Appendix A.3 of [11] (proof of Lemma 15).

10

B.3

Lower bound proof (Theorem 4)

In order to prove the simplified lower bound of Theorem 4 we basically have two arguments:
1. a lower bound on f (θ) can be obtained by enlarging the feasible set, that is by relaxing some constraints;
2. Lemma 15 can be used to lower bound the objective function of the problem.
The constant f (θ) is defined by
f (θ) = inf

c0

s.t

X

X

inf
λ∈B(θ)

∆a (θ)ca

(8)

a6=a∗ (θ)

Ia (θ, λ)ca ≥ 1.

(9)

a∈A

We begin by relaxing some constraints: we only allow the change of measure λ to belong to the sets Bk (θ) :=
{λ ∈ Θ|∀j 6= k, θj = λj and µ∗ (θ) < µ∗ (λ)} defined in Section 3:
X
f (θ) = inf
∆a (θ)ca
(10)
c0

a6=a∗ (θ)

s.t ∀k ∈
/ a∗ (θ), ∀λ ∈ Bk (θ),

X

Ia (θ, λ)ca ≥ 1.

(11)

a∈A

The K − L constraints (11) only let one parameter move and must be true for any value satisfying the definition
of the corresponding set Bk (θ). In practice, for each k, the parameter λk must be set to at least θL . Consequently,
these constraints may then be rewritten
f (θ) = inf

c0

X

s.t ∀k ∈
/ a∗ (θ),

ca

a6=a∗ (θ)

X

∆a (θ)ca

(12)

a6=a∗ (θ)

L
X

1{al = k}d(κl θk , κl θL ) ≥ 1.

(13)

l=1

Proposition 14 tells us that coefficients ca are all zeros except for actions a ∈ A which can be written a = vk,lk
where lk = arg minl≤L

∆vk,l (θ)
d(κl θk ,κl θL ) .

Thus, we obtain the desired lower bound by rewriting (12) as
f (θ) ≥

K
X
k=L+1

∆vk,l (θ)
.
l∈{1,...,L} d(κl θk , κl θL )
min

Proposition 14. Let c = {ca : a 6= a∗ } be a solution of the linear problem (LP) in Theorem 4. Coefficients are
all zeros except for actions a which can be written as a = (1, . . . , lk − 1, k, lk , . . . , L − 1) := vk,lk where k > L and
lk = arg minl≤L

∆vk,l (θ)
d(κl θk ,κl θL ) .

Proof. We denote by πk (a) the position of item k ∈ {1, . . . , K} in action a (0 if k ∈
/ a). Let lk be the optimal
∆v

(θ)

position of item k > L for exploration: lk = arg minl≤L d(κl θk,l
. Following [5], we show by contradiction that
k ,κl θL )
ca > 0 implies that a can be written vk,lk for a well chosen k > L. Let α 6= a∗ be a suboptimal action such that
∀k > L, α 6= vk,lk and cα > 0. We need to show a contradiction. Let us introduce a new set of coefficients c0
defined as follows, for any a 6= a∗ :

if a = α

0
d(κπk (α) θk ,κπk (α) θL )
c0a = ca +
c
if
∃k > L s.t. a = vk,lk and k ∈ α
α
d(κlk θk ,κlk θL )


ca
otherwise.
11

According to Lemma 15, these coefficients satisfy the constraints of the LP. We now show that these new
coefficients yield a strictly lower value to the optimization problem:
X

c(θ) − c0 (θ) = cα ∆α (θ) −

k>L:k∈α

X

> cα

d(κπk (α) θk , κπk (α) θL )
cα ∆vk,lk (θ)
d(κlk θk , κlk θL )
X

∆vk,πk (α) (θ) −

k>L:k∈α

k>L:k∈α

!
d(κπk (α) θk , κπk (α) θL )
∆vk,lk (θ) .
d(κlk θk , κlk θL )

(14)

The strict inequality (14) is shown in Lemma 16. Let k > L be one of the suboptimal arms in α. By definition of
lk , the corresponding term of the sum in equation (14) is positive. Thus, we have that c(θ) > c0 (θ) and, hence,
by contradiction, we showed that ca > 0 iff a can be written a = vk,lk for some k > L.
Lemma 15. Let c be a vector of coefficients that satisfy constraints (13) of the optimization problem. Then,
coefficients c0 as defined in Proposition 14 also satisfy the constraints:
∀k ∈
/ a∗ (θ),

X

c0a

a6=a∗ (θ)

L
X

1{al = k}d(κl θk , κl θL ) ≥ 1.

l=1

Proof. We use the same α as introduced in Proposition 14. Let us fix k ∈
/ a∗ (θ). Let us define
L(c) =

X

ca

a6=a∗ (θ)

L
X

1{al = k}d(κl θk , κl θL ).

l=1

We have
L(c0 ) − L(c) = −cα

L
X

1{αl = k}d(κl θk , κl θL ) +

l=1

X
l:αl >L

d(κl θk , κl θL )
cα
d(κlk θk , κlk θL )
× 1{αl = k}d(κlk θk , κlk θL ).

If k ∈
/ α, clearly, L(c0 ) − L(c) = 0. Else, k ∈ α and we note p its position in α: p = πk (α). We rewrite:


d(κlk θk , κlk θL )
0
= 0.
L(c ) − L(c) = cα d(κp θk , κp θL ) −1 +
d(κlk θk , κlk θL )
Thus, the coefficients c0 satisfy the constraints from Proposition 14.
Lemma 16. Let α be as in the proof of Proposition 14.
X
∆α (θ) >
∆vk,πk (α) (θ).
k>L:k∈α

Proof. Let k1 , . . . , kp be the suboptimal arms in α by increasing position. Let v(α) be the action in A with lower
regret such that it contains all the suboptimal arms of α in the same positions. Thus, v(α) = (1, . . . , πk1 (α) −
1, k1 , πk1 (α), . . . , πk2 (α) − 2, k2 , πk2 (α)
P − 1, . . . , L − p). By definition, one has that ∆α (θ) ≥ ∆v(α) (θ). In the
following, we show that ∆v(α) (θ) ≥ k>L:k∈α ∆vk,πk (α) (θ) for p = 2 (that is to say α contains 2 suboptimal arms
k1 and k2 ).
For the sake of readability, we write πi instead of πki (α) in the following.
∆v(α) (θ) =

L
X
l=1

κl (θl − θ(vk1 ,π1 )l ) +

L
X

κl (θ(vk1 ,π1 )l − θv(α)l )

l=1

= ∆vk1 ,π1 (θ) + [κπ2 θπ2 −1 + . . . + κL θL−1 ] − [κπ2 θk2 + κπ2 +1 θπ2 −1 + . . . + κL θL−2 ]
= ∆vk1 ,π1 (θ) + ∆vk2 ,π2 (θ) + [κπ2 (θπ2 −1 − θπ2 ) + . . . + κL (θL−1 − θL )] −
[κπ2 +1 (θπ2 −1 − θπ2 ) + . . . + κL (θL−2 − θL−1 )]
12

= ∆vk1 ,π1 (θ) + ∆vk2 ,π2 (θ) + R(θ).
Thus, one has to show that R(θ) = κπ2 (θπ2 −1 −θπ2 )+κπ2 +1 (2θπ2 −θπ2 −1 −θπ2 +1 )+. . .+κL (2θL−1 −θL−2 −θL ) > 0.
In fact, using that κl ≥ κl+1 for all l < L, we have
R(θ) ≥ κπ2 +1 (θπ2 −1 − θπ2 + 2θπ2 − θπ2 −1 − θπ2 +1 ) + . . . + κL (2θL−1 − θL−2 − θL )
≥ κπ2 +2 (θπ2 +1 − θπ2 +2 ) + . . . + κL (2θL−1 − θL−2 − θL )
≥ ...
≥ κL (θL−1 − θL )
> 0.

C

Proof of Proposition 8

In this section, we fix an arm k ∈ {1, . . . , K} and obtain an upper confidence bound for the estimator θ̂k (t) :=
Sk (t)/Ñk (t). Let τi be the instant of the i-th draw of arm k (the τi are stopping times w.r.t. Ft ). We introduce
the centered sequence of successive observations from arm k
Z̄k,i =

L
X

1{Al (τi ) = k}(Xl (τi )Yl (τi ) − θk κl ).

(15)

l=1

Introducing the filtration Gi = Fτi+1 −1 , one has E[Z̄k,i |Gi−1 ] = 0, and therefore, the sequence
Mk,n =

n
X

Z̄k,i

i=1

is a martingale with bounded increments, w.r.t. the filtration (Gn )n . By construction, one has
Mk,Nk (t) = Sk (t) − Ñk (t)θk = Ñk (t)(θ̂k (t) − θk ).
We use the so-called peeling technique together with the maximal version of Azuma-Hoeffding’s inequality [2].
For any γ > 0 one has
log(t)
log(1+γ)



P Mk,Nk (t) < −

p


Nk (t)δ/2 ≤

X



p
P Mk,Nk (t) < − Nk (t)δ/2 , Nk (t) ∈ [(1 + γ)i−1 , (1 + γ)i )

i=1
log(t)
log(1+γ)

≤

X



p
P ∃i ∈ {1, . . . , (1 + γ)i } : Mk,i < − (1 + γ)i−1 δ/2

i=1
log(t)
log(1+γ)

≤

X
i=1





δ(1 + γ)i−1
log(t)
δ
exp −
=
exp
−
.
(1 + γ)i
log(1 + γ)
(1 + γ)

Choosing γ = 1/(δ − 1), gives
p
P θ̂k (t) − θk < −

D

Nk (t)δ/2
Ñk (t)

!
≤ δe log(t)e−δ .

Regret analysis for PBM-UCB (Theorem 9)

We proceed as Kveton et al. (2015) [14]. We start
p by considering separately rounds when one of the confidence
intervals is violated. We denote by Bt,k =
Nk (t)(1 + ) log t/2/Ñk (t) the PBM-UCB exploration bonus
13

p
+
and by Bt,k
= Nk (t)(1 + ) log T /2/Ñk (t) an upper bound of this bonus (for t ≤ T ). We define the event
Et = {∃k ∈ A(t) : |θ̂k (t) − θk | > Bt,k }. Then, the regret can be decomposed into
R(T ) =

T
X

∆A(t) 1Et + ∆A(t) 1Ēt .

t=1

and, similarly to [14] (Appendix A.1), the first term of this sum can be bounded from above in expectation by a
constant C0 () that does not depend on T using Proposition 8. So, it remains to bound the regret suffered even
when confidence intervals are respected, that is the sum on the r.h.s of
T
X
E[R(T )] < C0 () + E[
∆A(t) 1{Ēt , ∆A(t) > 0}].
t=1

It can be done using techniques from [6, 14]. We start by defining events Ft , Gt , Ht in order to decompose
the part of the regret at stake. Then, we show an equivalent of Lemma 2 of [14] for our case and finally we refer
to the proof of Theorem 3 in Appendix A.3 of [14].
P
2
8(1+) log T ( L
s=1 κs )
For each round t ≥ 1, we define the set of arms St = {1 ≤ l ≤ L : NAl (t) (t) ≤
} and the
κ2 ∆2
L

A(t)

related events
• Ft = {∆A(t) > 0, ∆A(t) ≤ 2

PL

l=1

+
κl Bt,A
};
l (t)

• Gt = {|St | ≥ l};
• Ht = {|St | < l , ∃k ∈ A(t), Nk (t) ≤

P
2
8(1+) log T ( ls=1 κs )
},
κ2L ∆2A(t)

where the constraint on Nk (t) only differs from

the first one by its numerator which is smaller than the previous one, leading to an even stronger constraint.
Fact 17. According to Lemma 1 in [14], the following inequality is still valid with our own definition of Ft :
T
X

∆A(t) 1{Ēt , ∆A(t) > 0} ≤

t=1

T
X

∆A(t) 1{Ft }.

t=1

Proof. Invoking Lemma 1 from [14] needs to be justified as our setting is quite different. Taking action A(t)
means that
L
L
X
X
κl UAl (t) (t) ≥
κl Ul (t).
l=1

l=1

Under event Ēt , all UCB’s are above the true parameter θk so we have
L
X

κl (θAl (t) + 2Bt,Al (t) ) ≥

l=1

L
X

κl (θl + Bt,l ) ≥

l=1

L
X

κl θl .

l=1

+
Rearranging the terms above and using Bt,l(t) ≤ Bt,l(t)
, we obtain
L
X

+
κl Bt,A
≥2
l (t)

l=1

L
X

κl Bt,Al (t) ≥ ∆A(t) .

l=1

We now have to prove an equivalent of Lemma 2 in [6] that would allow us to split the right-hand side above
in two parts. Let us show that Ft ⊂ (Gt ∪ Ht ) by showing its contrapositive: if Ft is true then we cannot have
(Ḡt ∩ H̄t ). Assume both of these events are true. Then, we have
Ft

∆A(t) ≤ 2

L
X

+
κl Bt,A
l (t)

l=1

14

L
X

s

NAl (t) (t)

s

(1 + ) log(T )
Ñ
(t)
2ÑAl (t) (t)
Al (t)
l=1
s
L
X
NAl (t) (t) (1 + ) log(T )
=2
κl
2NAl (t) (t)
ÑAl (t) (t)
l=1
p
L
2(1 + ) log T X
κl
p
≤
κL
NAl (t) (t)
l=1


p
X
X
2(1 + ) log T 
κl
κl

p
p
=
+
κL
N
(t)
N
Al (t)
Al (t) (t)
l∈St
l∈S
/ t
!
p
P
P
(Ḡt ∩H̄t )
κL ∆A(t)
2(1 + ) log T
l∈S
/ t κl
l∈St κl
p
<
+ Pl
PL
κL
2 2(1 + ) log T
s=1 κs
s=1 κs
≤2

κl

≤ ∆A(t)
which is a contradiction. The end of the proof proceeds exactly as in the end of the proof of Theorem 6 in of [6]:
events Gt and Ht are split into subevents corresponding to rounds where each specific suboptimal arm of the list
is in St or verifies the condition of Ht . We define
P
2
L
8(1 + ) log T
κ
s=1 s
Gk,t = Gt ∩ {k ∈ A(t), Nk (t) ≤
},
2
2
κL ∆A(t)
P
2
l
8(1 + ) log T
κ
s=1 s
}.
Hk,t = Ht ∩ {k ∈ A(t), Nk (t) ≤
2
2
κL ∆A(t)
The way we defined these subevents allows to write the two following bounds :
K
X

1{Gk,t } = 1{Gt }

k=1

so 1{Gt } ≤

P

k

K
X

1{k ∈ St } ≥ l1{Gt }

k=1

1{Gk,t }/l. And,
1{Ht } ≤

K
X

1{Hk,t }.

k=1

We can now bound the regret using these two results:
T
X

∆A(t) (1{Gt } + 1{Ht }) ≤

t=1

T X
K
X
∆A(t)
t=1 k=1

=

l

T X
K
X
∆A(t)
t=1 k=1

l

1{Gk,t } +

T X
K
X

∆A(t) 1{Hk,t }

t=1 k=1
∗

1{Gk,t , A(t) 6= a } +

T X
K
X

∆A(t) 1{Hk,t , A(t) 6= a∗ }.

t=1 k=1

For each arm k, there is a finite number Ck := |Ak | of actions in A containing k; we order them such that the
corresponding gaps are in decreasing order ∆k,1 ≥ . . . ≥ ∆k,Ck > 0. So we decompose each sum above on the
different actions A(t) possible:
... ≤

T X
K X
T X
K X
X
X
∆k,a
1{Gk,t , A(t) = a} +
∆k,a 1{Hk,t , A(t) = a}.
l
t=1
t=1
k=1 a∈Ak

k=1 a∈Ak

The two sums on the right hand side look alike. For arm k fixed, events Gk,t and Hk,t imply almost the same
condition on Nk (t), only Hk,t is stronger because the bounding term is smaller. We now rely on a technical result
by [6] that allows to bound each sum.
15

Lemma 18. ([6], Lemma 2 in Appendix B.4) Let k be a fixed item and |Ak | ≥ 1, C > 0, we have
T X
X

1{k ∈ A(t), Nk (t) ≤ C/∆2k,a , A(t) = a}∆k,a ≤

t=1 a∈Ak

2C
∆min,k

where ∆min,k is the smallest gap among all suboptimal actions containing arm k. In particular, when k ∈
/ a∗
∗
the smallest gap is ∆min,k = κL (θL − θk ). While, when k ∈ a it is less obvious what the minimal gap is, however
it corresponds the second best action A2 containing only optimal arms: ∆min,k = ∆A2 .
So, bounding each sum with the above lemma, we obtain

2
PL
T
κ
X
s
s=1
16(1 + ) log T 
∆A(t) (1{Gt } + 1{Ht }) ≤
+

2
κ
l
L
t=1
|

l
X

!2
κs

s=1





{z

C(l;κ)

X
1
L
+
∆A2
κ
(θ
L L − θk )
∗

!
.

k∈a
/

}

This bound can be optimized by minimizing C(l; κ) over l.

E

Regret analysis for PBM-PIE (Theorem 11)

The proof follows the decomposition of [5]. For all t ≥ 1, we denote f (t, ) = (1 + ) log t.

E.1

Controlling leaders and estimations

Define η0 = mink∈{1,...,L−1} (θk − θk+1 )/2 and let η < η0 . We define the following set of rounds
A = {t ≥ 1 : L(t) 6= (1, . . . , L)}.
Our goal is to upper bound the expected size of A. Let us introduce the following sets of rounds:
B = {t ≥ 1 : ∃k ∈ L(t), |θ̂k (t) − θk | ≥ η},
C = {t ≥ 1 : ∃k ≤ L, Uk (t) ≤ θk },
D = {t ≥ 1 : t ∈ A \ (B ∪ C), ∃k ≤ L, k ∈
/ L(t), |θ̂k (t) − θk | ≥ η}.
We first show that A ⊂ (B ∪ C ∪ D). Let t ∈ A \ (B ∪ C). Let k, k 0 ∈ L(t) such that k < k 0 . Since t ∈
/ B, we
0
0
0
0
have that |θ̂k (t) − θk | ≤ η and |θ̂k (t) − θk | ≤ η. Since η ≤ (θk − θk )/2, we conclude that θ̂k (t) ≥ θ̂k (t). This
proves that (L1 (t), . . . , LL (t) is an increasing sequence. We have that LL (t) > L otherwise L(t) = (1, . . . , L)
which is a contradiction because t ∈ A. Since LL (t) > L, there exists k ≤ L such that k ∈
/ L(t). We show by
contradiction that |θ̂k (t) − θk | ≥ η. Assume that |θ̂k (t) − θk | ≤ η. We also have that θ̂LL (t) (t) − θLL (t) ≤ η
because LL (t) ∈ L(t) and t ∈
/ B. Thus, θ̂k (t) > θ̂LL (t) (t). We have a contradiction because this would imply that
k ∈ L(t). Finally we have proven that if t ∈ A \ (B ∪ C), then t ∈ D so A ⊂ (B ∪ C ∪ D).
By a union bound, we obtain
E[|A|] ≤ [|B|] + [|C|] + [|D|].
In the following, we upper bound each set of rounds individually.
Controlling E[|B|]: We decompose B =

SK

k=1 (Bk,1

∪ Bk,2 ) where

Bk,1 = {t ≥ 1 : k ∈ L(t), LL (t) 6= k, |θ̂k (t) − θk | ≥ η}
Bk,2 = {t ≥ 1 : k ∈ L(t), LL (t) = k, |θ̂k (t) − θk | ≥ η}
Let t ∈ Bk,1 : k ∈ A(t) so E[k ∈ A(t)|t ∈ Bk,1 ] = 1. Furthermore, for all t, 1{t ∈ Bk,1 } is Ft−1 measurable.
Then we can apply Lemma 22 (with H = Bk,1 and c = 1).
−2
E[|Bk,1 |] ≤ 2(2 + κ−2
).
L η

16

Let t ∈ Bk,2 : k ∈ B(t) but because of the randomization of the algorithm, k ∈ A(t) with probability 1/2, i.e.
E[k ∈ A(t)|t ∈ Bk,2 ] ≥ 1/2. We get
−2
E[|Bk,2 |] ≤ 4(4 + κ−2
)
L η
−2
By union bound over k, we get E[|B|] ≤ 2K(10 + 3κ−2
).
L η

SL
Controlling E[|C|]: We decompose C = k=1 Ck where Ck = {t ≥ 1 : Uk (t) ≤ θk }
We first require to prove Proposition 10.
Proof. Theorem 2 of [16] implies that
L
X

P

l=1

The function Φ : x →

PL

Sk,l (t)
Nk,l (t)d(
, κl θk ) ≥ δ
Nk,l (t)

l=1 Nk,l (t)d



Sk,l (t)
Nk,l (t) , κl x



!
≤ e−δ



dδ log(t)e δ
L

L

eL+1 .

is convex and non-decreasing on [θkmin (t), 1]; the convexity is

easily checked and θkmin (t) is defined as the minimum of this convex function. By definition, we have, either,
Uk (t, δ) = 1 and then Uk (t, δ) > θk , or, Uk (t, δ) < 1 and Φ(Uk (t, δ)) = δ, consequently
P (Uk (t, δ) < θk ) = P (Φ(Uk (t, δ)) ≤ Φ(θk )) = P (δ ≤ Φ(θk )) .

Remember that Uk (t) = Uk (t, (1 + ) log(t)) = Uk (t, f (t, )). Thus, applying Proposition 10, we obtain for
arm k,

E[|Ck |] ≤

∞
X

P(Uk (t) ≤ θk ) ≤ deL+1 e +

t=1

eL+1
LL

∞
X
t=deL+1 e+1

(2 + )2L (log t)3L
≤ C3 (),
t1+

for some constant C3 ().
Controlling E[|D|]: Decompose D as D =

SL

k=1

Dk where

Dk = {t ≥ 1 : t ∈ A \ (B ∪ C), k ∈
/ L(t), |θ̂k (t) − θk | ≥ η}.
For a given k ≤ L, Dk is the set of rounds at which k is not one of the leaders, and is not accurately estimated.
Let t ∈ Dk . Since k ∈
/ L(t), we must have LL (t) > L. In turn, since t ∈
/ B, we have |θ̂LL (t) (t) − θLL (t) | ≤ η, so
that
θ̂LL (t) ≤ θLL (t) + η ≤ θL + η ≤ (θL + θL+1 )/2.
Furthermore, since t ∈
/ C and 1 ≤ k ≤ L, we have Uk (t) ≥ θk ≥ θL ≥ (θL + θL+1 )/2 ≥ θ̂LL (t) . This implies
that k ∈ B(t) thus E[k ∈ A(t)|t ∈ Dk ] ≥ 1/(2K). We apply Lemma 22 with H ≡ Dk and c = 1/(2K) to get
E[|D|] ≤

L
X

−2
E[|Dk |] ≤ 4K(4K + κ−2
).
L η

k=1

E.2

Regret decomposition

We decompose the regret by distinguishing rounds in A ∪ B and other rounds. More specifically, we introduce
the following sets of rounds for arm k > L:
Ek = {t ≥ 1 : t ∈
/ (B ∪ C ∪ D), L(t) = a∗ , A(t) = vk,L }.
The set of instants at which a suboptimal action is selected now can be expressed as follows
{t ≥ 1 : A(t) 6= a∗ } ⊂ (B ∪ C ∪ D) ∪ (∪k=L+1 Ek ).
17

Using a union bound, we obtain the upper bound
!
L
K
X
X
E[R(T )] ≤
κl E[|B ∪ C ∪ D|] +
∆vk,L (θ)E[|Ek |].
l=1

k=L+1

From previous boundaries, putting it all together, there exist C1 (η) and C3 (), such that
!
L
X
κl (E[|B|] + E[|C|] + E[|D|]) ≤ C1 (η) + C3 ().
l=1

At this step, it suffices to bound events Ek for all k > L.

E.3

Bounding event Ek

We proceed similarly to [9]. Let us fix an arm k > L. Let t ∈ Ek : arm k is pulled in position L, so by
construction of the algorithm, we have that k ∈ B(t) and thus Uk (t) ≥ θ̂LL (t) (t). We first show that this implies
that Uk (t) ≥ θL − η. Since t ∈ Ek , we know that LL (t) = L, and since t ∈
/ B, |θ̂L (t) − θL | ≤ η. This leads to
Uk (t) ≥ θ̂LL (t) (t) = θ̂L (t) ≥ θL − η.
Recall that Nk,L (t) is the number of times arm k was played in position L. By denoting d+ (x, y) = 1{x < y}d(x, y),
we have that
Nk,L (t)d+ (Sk,L (t)/Nk,L (t), κL (θL − η)) ≤ Nk,L (t)d+ (Sk,L (t)/Nk,L (t), κL Uk (t))
≤

L
X

Nk,l (t)d+ (Sk,l (t)/Nk,l (t), κl Uk (t)) ≤ f (t, ).

l=1
+

This implies that 1{t ∈ Ek } ≤ 1{Nk,L (t)d (Sk,L (t)/Nk,L (t), κL (θL − η)) ≤ f (t, )}.
L
Lemma 19. ([9], Lemma 7) Denoting by ν̂k,s
the empirical mean of the first s samples of Zk,L , we have
T
X

1{A(t) = vk,L , Nk,L (t)d+ (Sk,L (t)/Nk,L (t), κL (θL − η)) ≤ f (t, )}

t=1

≤

T
X

L
1{sd+ (ν̂k,s
, κL (θL − η)) ≤ f (T, )}.

s=1

We apply Lemma 19 which is a direct translation of Lemma 7 from [9] to our problem. This yields
|Ek | ≤

T
X

L
1{sd+ (ν̂k,s
, κL (θL − η)) ≤ f (T, )}.

s=1

Let γ > 0. We define KT =
parts.
T
X

(1+γ)f (T,)
d+ (κL θk ,κL (θL −η)) .

We now rewrite the last inequality splitting the sum in two

L
P(sd+ (ν̂k,s
,κL (θL − η)) ≤ f (T, )) ≤ KT +

s=1

∞
X

L
P(KT d+ (ν̂k,s
, κL (θL − η)) ≤ f (T, ))

s=KT +1

≤ KT +

∞
X

L
P(d+ (ν̂k,s
, κL (θL − η)) ≤ d(κL θk , κL (θL − η))/(1 + γ))

s=KT +1

≤ KT +

C2 (γ, η)
,
T β(γ,η)

where last inequality comes from Lemma 20. Fixing γ < , we obtain the desired result, which concludes the
proof.
18

Lemma 20. For each γ > 0, there exists C2 (γ, η) > 0 and β(γ, η) > 0 such that


∞
X
d(κL θk , κL (θL − η)
C2 (γ, η)
L
P d+ (ν̂k,s
, κL (θL − η)) ≤
≤ β(γ,η) .
1+γ
T
s=KT +1

d(κL θk ,κL (θL −η))
,
1+γ

L
Proof. If d+ (ν̂k,s
, κL (θL − η)) ≤
κL r(γ, η) and

L
then there exists some r(γ, η) ∈ (θk , θL − η) such that ν̂k,s
>

d(κL r(γ, η), κL (θL − η)) =

d(κL θk , κL (θL − η))
.
1+γ

Hence,


d(κL θk , κL θL )
P d (ν̂k,s , κL θL ) <
1+γ
+


≤ P (d(ν̂k,s , κL θk ) > d(κL r(γ, η), κL θk ), ν̂k,s > κL θk )
≤ P(ν̂k,s > κL r(γ, η)) ≤ exp(−sd(κL r(γ, η), κL θk )).

We obtain,
∞
X
t=KT



d(κL θk , κL θL )
exp(−KT d(κL r(γ, η), κL θk ))
C2 (γ, η)
P d+ (ν̂k,s , κL θL ) <
≤
≤ β(γ,η) ,
1+γ
1 − exp(−d(κL r(γ, η), κL θk ))
T

for well chosen C2 (γ, η) and β(γ, η).

F

Lemmas

In this section, we recall two necessary concentration lemmas directly adapted from Lemma 4 and 5 in Appendix
A of [5]. Although more involved from a probabilistic point of view, these results are simpler to establish than
proposition 8 as their adaptation to the case of the PBM relies on a crude lower bound for Ñk (t), which is
sufficient for proving Theorem 11..
Pn
Lemma 21. For k ∈ {1, . . . , K} consider the martingale Mk,n =
i=1 Z̄k,i , where Z̄k,i is defined in (15).
Consider Φ a stopping time such that either Nk (Φ) ≥ s or Φ = T + 1. Then
P[|Mk,Nk (Φ) | ≥ Nk (Φ)η, Nk (Φ) ≥ s] ≤ 2 exp(−2sη 2 ).

(16)

P[|θ̂k (Φ) − θk | ≥ η, Φ ≤ T ] ≤ 2 exp(−2sκ2L η 2 ).

(17)

As a consequence,

Proof. The first result is a direct application of Lemma 4 of [5] as (Zl (t))t with Zl (t) = Xl (t)Yl (t) is an independent
sequence of [0, 1]-valued variables.
For the second inequality, we use the fact that Ñk (t) ≥ κL Nk (t). Hence,


|Mk,Nk (Φ) |
P[|θ̂k (Φ) − θk | ≥ η, Φ ≤ T ] ≤ P
≥ η, Φ ≤ T .
κL Nk (Φ)
which is upper bounded using (16).
Lemma 22. Fix c > 0 and k ∈ {1, . . . , K}. Consider a random set of rounds H ⊂ N, such that, for all t,
1{t ∈ H} is Ft−1 measurable and such that for all t ∈ H, {k ∈ B(t)} is true.
PτsFurther assume, for all t, one
has E[1{k ∈ A(t)}|t ∈ H] ≥ c > 0. We define τs a stopping time such that t=1
1{t ∈ H} ≥ s. Consider the
random set Λ = {τs : s ≥ 1}. Then, for all k,
X
−2
P[t ∈ Λ, |θ̂k (t) − θk | ≥ η] ≤ 2c−1 (2c−1 + κ−2
)
L η
t≥0

The proof of this lemma follows that of Lemma 5 in [5] using the same lower bound for Ñk (t) as above.
19

