TCS -TR-A-05-7

TCS Technical Report

FPL Analysis for Adaptive Bandits

byJ. Poland

Division of Computer Science
Report Series A
July 26, 2005

Hokkaido University

Graduate School ofInformation Science and Technology
Email:

jan@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7675+81-011-706-7675

1

FPL Analysis for Adaptive Bandits

TCS-TR-A-05-4

July 26, 2005

FPL Analysis for Adaptive Bandits
Jan Poland∗
Grad. School of Inf. Sci. and Tech.
Hokkaido University, Japan
jan@ist.hokudai.ac.jp
www-alg.ist.hokudai.ac.jp/∼jan

Abstract
A main problem of “Follow the Perturbed Leader” strategies for online
decision problems is that regret bounds are typically proven against oblivious adversary. In partial observation cases, it was not clear how to obtain
performance guarantees against adaptive adversary, without worsening thebounds. We propose a conceptually simple argument to resolve this prob2
lem. Using this, a regret bound of O(t 3 ) for FPL in the adversarial multiarmed bandit problem is shown. This bound holds for the common FPL
variant using only the observations from designated exploration rounds.
√
Using all observations allows for the stronger bound of O( t), matching
the best bound known so far (and essentially the known lower bound) for
adversarial bandits. Surprisingly, this variant does not even need explicit
exploration, it is self-stabilizing. However the sampling probabilities haveto be either externally provided or approximated to sufficient accuracy,
using O(t2 log t) samples in each step.
Keywords: expert advice, online algorithms, partial observations, adaptive adversary, bandit problems, FPL

1Introduction“Expert Advice” stands for an active research area which studies online algorithms.
In each time step t = 1, 2, 3, . . . the master algorithm, henceforth called master for
brevity, is required to commit to a decision, which results in some cost. The masterhas access to a class of experts, each of which suggests a decision at each time step.
The goal is to design master algorithms such that the cumulative regret (which isjust the cumulative excess cost) with respect to any expert is guaranteed to be small.
Bounds on the regret are typically proven in the worst case, i.e. without any statistical∗

This work was supported by JSPS 21st century COE program C01.

2

J. Polandassumption on the process assigning the experts’ costs. In particular, this might be an
adaptive adversary which aims at maximizing the master’s regret and also knows themaster’s internal algorithm. This implies that (unless the decision space is continuousand the cost function is convex) the master must randomize in order to protect against
this danger.
In the recent past, a growing number of different but related online problems havebeen considered. Prediction of a binary sequence with expert advice has been popularsince the work of Littlestone and Warmuth in the early 1990’s. Freund and Schapire[FS97] removed the structural assumption on the decision space and gave a very
general algorithm called Hedge which in each time step randomly picks one expert
and follows its recommendation. We will refer to this setup as the online decision
problem. Auer et al. [ACBFS95, ACBFS03] considered the first partial observationcase, namely the bandit setup, where in each time step the master algorithm only
learns its own cost, i.e. the cost of the selected expert. All these and many otherpapers are based on weighted forecasting algorithms.
A different approach, Follow the Perturbed Leader (FPL), was pioneered as early
as 1957 by Hannan [Han57] and rediscovered recently by Kalai and Vempala [KV03].
Compared to weighted forecasters, FPL has two main advantages and one major
drawback. First, it applies to the online decision problem and admits a much moreelegant analysis for adaptive learning rate [HP05]. Even infinite expert classes do
not cause much complication. (However, the leading constant of the regret bound is√generically a factor of 2 worse than that for weighted forcasters.) Adaptive learning
rate is necessary unless the total number of time steps to be played is known inadvance.
As a second advantage, FPL also admits efficient treatment of cases where theexpert class is potentially huge but has a linear structure [MB04, AK04]. We willrefer to such problems as geometric online optimization. An example is the online
shortest path problem on a graph, where the set of admissible paths = experts is
exponential in the number of vertices, but the cost of each path is just the sum of thecosts of the vertices.
FPL’s main drawback is that its general analysis only applies against an oblivious
adversary, that is an adversary that has to decide on all cost vectors before the gamestarts – as opposed to an adaptive one that before each time step t just needs tocommit to the current cost vector. For the full information game, one can showthat a regret bound against oblivious adversary implies the same bound against an
adaptive one [HP05]. The intuition is that FPL’s current decision at time t does notdepend on its past decisions. Therefore, the adversary may well decide on the current
cost vector before knowing FPL’s previous decisions. This argument does not apply inpartial observation cases, as there FPL’s behavior does depend on its past decisions(because the observations do so). As a consequence, authors started to explicitly
distinguish between oblivious and adaptive adversary, sometimes restricting to theformer, sometimes obtaining bounds of lower quality for the latter. E.g. McMahan

3

FPL Analysis for Adaptive Bandits

and Blum [MB04] suggest a workaround, proving sublinear regret bounds against an
3√
2
adaptive bandit, however of worse order (t 4 log t instead of t 3 , for both, geometriconline optimization and online decision problem). This is not satisfactory, since incase of the bandit online decision problem for a suitable weighted forecaster, even a√O( t) bound against adaptive adversary is known [ACBFS03].
In this work, we remove FPL’s major drawback. We give a simple argument(Section 2) which shows that also in case of partial observation, a bound for FPL
against an oblivious adversary implies the same bound for adaptive adversary. This¡ √2¢will allow in particular to prove a O (tn log n) 3 bound for the bandit online decision
problem (Section 3). This bound is shown for the common construction where only
the observations of designated exploration rounds are used. As this master algorithm
is label efficient, the bound is essentially sharp. In contrast, using all informations√
will enable us to prove a stronger O( tn log n) bound (Section 4). This matches
the best bound known so far for the adversarial bandit problem [ACBFS03], which√is sharp within log n. The downside of this algorithm is that either the sampling
probabilities have to be given by an oracle, or they have to be approximated with tosufficient accuracy, using O(t2 log t) samples. The case of an infinite expert class isbriefly discussed in Section 5.

2

FPL: oblivious ⇒ adaptive

Assume that c1 , c2 , . . . ∈ [0, 1]n is a sequence of cost vectors. There are n ≥ 1 experts.
(We will give an example with infinitely many experts Section 5, but for simplicity
of presentation, we restrict our main exposition to finite expert classes). That is, cit
is expert i’s cost at time t, and the costs are bounded (w.l.o.g. in [0, 1]). In the fullobservation game, at time t the master would know the past cumulative costs c<t =P
c1:t−1 = t−1
s=1 cs (observe that we have introduced some notation here). However, ourfocus are partial observations where this is not the case. Hence, assume that there
are estimates ĉt (to be specified later) for the cost vectors ct . Then at time t, FPL(t)samples a perturbation vector qt ∈ [0, ∞)n the components of which are independently
exponentially distributed, that is, P(qti ≥ x) = e−x . Afterwards, the expert with thebest (minimum) score ĉ<t − ηqtt is selected, where ηt > 0 is the learning rate:n
FPL(t, ĉ<t ) = arg min

1≤i≤n

qi
ĉi<t − ηttod.

where qti ∼ Exp independently.

(1)

Denote the expert FPL chooses at time t by It = FPL(t, ĉ<t ). Then an adaptive
adversary is a function A : [0, 1]n×t−1 × {1 . . . n}t−1 → [0, 1]n . (We assume A to
be deterministic but remark that all our results and proofs hold for randomized A
without major modification.) The complete game between FPL and A is specified by
ct = A(c1 c2 . . . ct−1 , I1 I2 . . . It−1 ) and It = FPL(t, ĉ<t ) for t = 1, 2, . . . The estimatedcost vector ĉt is revealed to FPL after time t and specified by a mechanism “outside”
this game which is defined later (this is the exploration).

4

J. Poland

After the game has proceeded for a number of time steps T , we want to evaluate FPL’s performance. Actually, the expected performance is the right quantity toaddress. If we are rather interested in high probability bounds on the actual performance, then they are easily obtained by observing that the difference of actual
to expected performance is a martingale with bounded differences (all instantaneous
costs cit are in [0, 1]). Thus, high probability bounds follow by Azuma’s inequality, as
we will demonstrate in Proposition 3.
PT It
How can we compute FPL’s expected costs EcFPL
1:T = Et=1 ct ? The key observation is that – on the cost vectors generated by FPL and A and with the given
estimated costs ĉt – FPL’s expected costs at time t are the same as another algorithm
g expected costs. FPL
g is defined by
FPL’s
n
o
g ĉ<t ) = arg min ĉi − q∗i ,FPL(t,
(2)
<t
ηt
1≤i≤n

where q∗ is a single fixed vector with independently exponentially distributed components. Since we have to be careful to take expectations w.r.t. the appropriate
randomness, we explicitely refer to the randomness in the notation by writing e.g.
EcFPL
= Eqt cFPLtt . Then the following statement trivially holds, as qt and q∗ have thesame distribution.
g= Eq∗ cFPL
Proposition 1 At each time t ≤ T , we have Eqt cFPLtt .
This means that in order to analyze FPL, we may now proceed by considering the
g instead. We can use the standard analysis based on the tools
expected costs of FPL
g is executed on a sequence ofby Kalai and Vempala [KV03], which requires that FPL
cost vectors that is fixed and not known in advance. Actually, in contrast to the fullobservation game analysis, the bandit analysis will never require the true cost vectors
to be revealed, but rather the estimated cost vectors. For the cost vectors generated
g is satisfied – just consider FPL
g as
by A in response to FPL, the prerequisite for FPL
a virtual or hypothetic algorithm which is not actually executed. Therefore it does
not make any decisions or cause any response from the adversary. Just for the sakeof analysis we pretend that it runs and evaluate the expected cost it incurs, which isthe same as FPL.
Since our key argument and the way it is used in the analysis appears quite subtle
at the first glance, we encourage the reader to thoroughly verify each of the subsequent
formal steps.

3

The standard strategy against adversarial bandits

The first algorithm we consider, bandit-FPL (bFPL), is specified in Figure 1 and proceeds as follows. At time t, it decides if to perform an exploration or an exploitation

FPL Analysis for Adaptive Bandits

5

For t = 1, 2, 3, . . .
set ĉit = 0 for all isample rt ∈ {0, 1} independently s.t. P [rt = 1] = γt
If rt = 0 Then set Itb = FPL(t, ĉ<t ) according to (1)If rt = 1 Then sample Itb from {1 . . . n} uniformly (Itb =ut )Ib
play decision Itb and observe cost ct t
Ib
Ib
If rt = 1 Then set ĉt t = n · ct t /γtFigure 1: The algorithm bFPL. The exploration rate γt and the learning rate ηt (usedby subroutine FPL) will be specified in Theorem 2.

step according to some exploration probability γt ∈ (0, 1). This is realized by samplingrt ∈ {0, 1} independently from all other randomness with P [rt = 1] = γt . In case of exploration (rt = 1), the decision Itb is uniformly sampled from {1 . . . n}, independently
from all other randomness. We denote this choice by ut . (For notational convenience,
we will also refer to the irrelevant ut ’s in the exploitations steps later.) In case of
exploitation (rt = 0), bFPL obtains its decision Itb by invoking FPL according to (1).
Ib
After bFPL has played its decision, it observes its own costs ct t . Finally, only in caseof exploration (rt = 1), the estimated cost vector is set to something different from
0. This is the standard way of constructing an FPL variant against an adversarial
bandit [MB04, AK04]. We will discuss how to make use of all observations in thenext section. Here is the formal specification of the algorithm again.
( i
½
nct
u
if
r
=
1
if rt = 1 ∧ i = Itbttγt
Itb = bFPL(t, ĉ<t ) =ĉit =
FPL(t, ĉ<t ) otherwise,0otherwise.
Consequently, the estimated cost vector is chosen unbiasedly, i.e. Ert ,ut ĉit = cit . This
technique was introduced in [ACBFS95].
©
¢2 ª
¢2
1¡ √
1¡ √
Theorem 2 Let γt = min 1, t− 3 n log n 3 and ηt = nγ2t t− 3 n log n 3 . Then, for
any T ≥ (n log n)2 , each expert i ∈ {1 . . . n}, and any adaptive assignment of thecosts c1 , c2 , . . ., bFPL satisfies the regret bound
EcbFPL
1:T³− ci1:T ≤ 4´ 23p
T n log n .

(3)(For T < (n log n)2 , the regret is clearly at most (n log n)2 .)Proof. All computations we use in the subsequent proof have been taken or adaptedfrom other work. Our point is to bring them into the right order and to carefully
check that in this context, against an adaptive adversary, all operations are legitimate. In particular we have to take care that all expectations are w.r.t. the appropriate randomness. Again, we make this explicit in the notation and write e.g.

6

J. Poland

EcbFPL= Eqt ,r1:t ,u1:t cbFPL. Note that according to the definition of bFPL, EcbFPL
intttfact does not depend on q<t . During the proof, we will avoid the use of unspecified
expectation (without subscripts). Let’s introduce abbreviation h<t = (r<t , u<t , q<t )for the randomization history, i.e. the tuple containing all past random variables.
Moreover, we will use conditional expectation. For instance, Eqt [cFPL
t |h<t ] denotes arandom variable depending on the randomization history h<t , where for each possible
history the expectation is taken w.r.t. qt . Since we admit adaptive assignments, wemust be aware that they may depend on bFPL’s past randomness. To make thisexplicit, we use the notation E[cit |h<t ] for the adversary’s decisions and rewrite ourbound to show (3) asTX

Eqt ,rt ,ut [cbFPL|h<t ] −
t

t=1

T
X

³ p
´ 23
E[cit |h<t ] ≤ 4 T n log n .

(4)

t=1

In order to keep the presentation simple, we assume the adversary to be deterministic.
Then for given randomization history, cit is constant. The same proof (and hence thetheorem) remains valid if we admit randomized adversaries.
First note that Eqt ,rt ,ut [cbFPL|h<t ] ≤ Eqt [cFPLtt |h<t ] + γt holds in each time step t by
¢2
1¡ √
Itb
definition of bFPL and ct ≤ 1. Since γt ≤ t− 3 n log n 3 , we have
T
X

γt ≤

t=1

T
X

t

− 13

³ p
´ 23
¡ p
¢ 23
3
n log n ≤ 2 T n log n .

(5)

t=1

Therefore, (4) follows fromTX

Eqt [cFPL
t |h<t ] −

t=1

T
X

³ p
´ 23
E[cit |h<t ] ≤ 25 T n log n .

(6)

t=1

Consider this form of FPL (i.e. FPL executed in each time step) as a virtual algorithm:
It does not run in that way on the inputs. Rather, for the sake of analysis, wepretend that it runs with the ĉt obtained from bFPL and try to evaluate its (virtual)performance.
We then use Proposition 1 to bring into the play another virtual algorithm, namelyg
FPL. Since for given randomization history, the expected performance of FPL andg coincide, (6) is proven if we can show
FPL
T
X

g
Eq∗ [cFPL
t |h<t ] −TX

E[cit |h<t ] ≤ 52

³
Tn

p

log n

´ 23

.

(7)

t=1

t=1

Next, we perform the transition from real to estimated costs. Since the estimate ĉwas defined to be unbiased, we have E[cit |h<t ] = Ert ,ut [ĉit |h<t ]. By the same argugg actually does not depend on rt and ut , Eq∗ [cFPL
ment, since the choice of FPL
t |h<t ] =gEq∗ ,rt ,ut [ĉFPLt |h<t ] holds. Hence, (7) follows from
T
X
t=1

g

|h<t ] −Eq∗ ,rt ,ut [ĉIFPL
t

T
X
t=1

³ p
´ 32
Ert ,ut [ĉit |h<t ] ≤ 52 T n log n .

(8)

7

FPL Analysis for Adaptive Bandits

g (like FPL) only incurs estimated costs in case
Note that, somewhat curiously, FPL
of exploration, i.e. where it actually did not decide the action. We need yet anotherg or IFPL,] defined as
virtual algorithm, infeasible FPLno] ĉ1:t ) = arg min ĉi1:t − q∗i ,IFPL(t,
(9)
ηt
1≤i≤n

g It is not feasible because at time twhich uses the same perturbation q∗ as FPL.
it makes use of the information ĉt , which is only available afterwards. As it is avirtual algorithm, this does not cause any problems. By [HP05, Theorem 4], which
is proven by an argument very similar to (13) below, in case of exploration (i.e.
¡ ¢2
g
g
IFPL
rt = 1) it holds that Eq∗ [ĉFPL|h<t , rt = 1] + ηt γnt . We
t |h<t , rt = 1] ≤ Eq∗ [ĉtremark that this step is valid also for independently sampled perturbations qt . Clearly,gg
IFPL
Eq∗ [ĉFPL|h<t , rt = 0] in case of exploitation (rt = 0). Thus int |h<t , rt = 0] = Eq∗ [ĉtexpectation w.r.t. q∗ and rt , and for any ut ,
g

g

g

2

FPL
IFPL
Eq∗ [ĉFPL|h<t ] + ηtγnt .
t |h1:T ] = Eq∗ ,rt [ĉt |h<t ] ≤ Eq∗ ,rt [ĉt

¢2
2
1¡ √
The sum over ηtγnt ≤ t− 3 n log n 3 is bounded as in (5), and we see that (8) holds
if we can showTXgEq∗ ,rt ,ut [ĉIFPL|h<t ] −
t

t=1

T
X

Ert ,ut [ĉit |h<t ] ≤

³
Tn

p

log n

´ 23

.

(10)

t=1

The rest of the proof now follows as in [KV03] or [HP05]. In order to maintain selfcontainedness, we give it here. Actually we verify (10) for any choice of r1:T , u1:T ,then it also holds in expectation.
In the following, we suppress the dependency on r1:T , u1:T in the notation. Then all
expectations are w.r.t. q∗ . We use the following convenient notation from [KV03]: Fora vector x ∈ Rn , let M (x) be the unit vector which has a 1 at the index arg mini {xi }and 0’s at all other places. Then the process of selecting a minimum can be written as
scalar product: mini {xi } = M (x) ◦ x. For convenience, let η0 = ∞ and c̃1:t = ĉ1:t − qη∗t .
Then it is easy to prove by induction [KV03, HP05] thatgĉIFPL
1:t −

T
X

³
M (c̃1:t ) ◦ q∗

t=1

1
1
− ηt−1
ηt

´
=

T
X

M (c̃1:t ) ◦ c̃t ≤ M (c̃1:T ) ◦ c̃1:T .

(11)

t=1
g

Then observe
In order to estimate EĉIFPL
1:t , we take expectations on both sides.
EM (ĉ1:T ) ◦ q∗
j
1
i
◦
◦
EM (c̃1:T ) c̃1:T ≤ EM (ĉ1:T ) c̃1:T = minj {ĉ1:T } −≤ ĉ1:T − ηT by definition
ηT³
Pof M . The negative term on the l.h.s. of (11) may be bounded by Tt=1 M (c̃1:t ) ◦ q∗ η1t −
³
´ P
´
i
T
n
1
1
1
◦q
M
(−q
)
≤
−
= maxηiT{q∗ } ≤ 1+log(see [KV03] or [HP05] for the
∗
∗
t=1
ηt−1
ηt
ηt−1
ηT
1
last estimate). Plugging these estimates back into (11) while observing η1t − ηt−1
≥0
2
¡
¢
2
and ηT = T − 3 logn n 3 (which holds because of T ≥ (n log n)2 ), finally shows (10) andconcludes the proof of the theorem.
2

8

J. Poland

Proposition 3 (High probability bound) For each T ≥ 1 and 0 ≤ δ ≤ 1, the actual
costs of bFPL are bounded with probability at least 1 − δ by
q
bFPL
+
≤
Ec
2T log 2δ .
cbFPL
1:T
1:T
Proof. Again we use the explicit notation from the proof of the previous theoP ¡rem. It is easy to see that the sequence of random variables XT = Tt=1 cbFPL
−
t
¢
bFPL
Ert ,ut ,qt [ct|h<t ] is a martingale w.r.t. the filter of sigma-algebras generated by the
randomization history h1:t . Moreover, its differences are bounded by |Xt − Xt−1 | ≤ 1.
Consequently, by Azuma’s inequality, the probability that Xt exceeds some λ > 0 is
¡ λ2 ¢. Solve this for λ to obtain the assertion.
2
bounded by δ = 2 exp − 2T

4

Using all observations

The algorithm bFPL considered so far does only uses a γ-fraction of all the input.
It is thus a label efficient decision maker [CBLS04a, CBLS04b]. One possible way
to specify a label efficient problem setup is to require that the master usually does
not observe anything, and it incurs maximal cost if it decides to observe something[CBLS04b]. Since just before (5), we upper bounded the costs in case of exploration
by 1, it is immediate that the same analysis and hence also Theorem 2 transfer to thelabel efficient case. [CBLS04b, Sec. 5] prove that there is a label efficient prediction
2
problem such that any forecaster incurs a regret proportional to t 3 . Hence the boundin Theorem 2 is essentially sharp for bFPL.
Of course, the usual bandit setup does not require the master to make use of only
a tiny fraction of all information available. For weighted forecasters, it is very easy to
produce an unbiased cost estimate if each round’s inputs are used. It turns out that√then regret bound proportional to t can be obtained [ACBFS03]. Unfortunately thisis different for FPL, as here the sampling probabilities are not explicitely available. In
the following, we will first discuss the computationally infeasible case assuming that
we know the sampling probabilities. After that, we show how to approximate themby a Monte Carlo simulation to sufficient accuracy.
Surprisingly, it is possible to work with the plain FPL algorithm from (1), without
exploration. We just have to use the correct estimated cost vectors,½ i
ct /P(ItFPL = i) if i = ItFPL
i
(12)
ĉt =
0
otherwise,
where ItFPL was FPL’s choice at time t. We assume that the values P(ItFPL = i) areprovided by some oracle.
It is not hard to adapt the proof of Theorem 2 to analyze FPL under these conditions. As in the steps up to (8),
g

g ∗)
FPL(q

FPL
Eqt [cFPL
t |h<t ] = Eq∗ ,qt ,rt ,ut [ĉt |h<t ] = Eq∗ ,qt ,rt ,ut [ĉt(qt )|h<t ].

9

FPL Analysis for Adaptive Bandits
g
FPL(q
)

∗
The overly explicit notation ĉt(qt ) serves to remind that the cost vector estimatedg
is obtained using qt , while FPL’s choice incurring cost stems from q∗ . It is essential
g ∗)
FPL(q
that qt and q∗ are independent. Observe that in general, Eq∗ ,qt ,rt ,ut [ĉt(qt )|h<t ] 
g t)
FPL(q
g
Eqt ,rt ,ut [ĉt(qt )|h<t ]: the latter quantity, which is the actual estimated cost of FPL’s

choice, is biased and too large.
gg

Abbreviate pi = P(ItFPL = i) and π i = P(ItIFPL = i). Denote the exponential
distribution by µ and integration with respect to q 1 . . . q n without the ith coordinateRby . . . dµ(q 6=i ). Moreover, for x ∈ R, let x+ = max{x, 0}. Then, similarly to theproof of [HP05, Theorem 4],
Z Z∞

Z
i

pi =

6=i

dµ(q )dµ(q ) =Z−(max{ηt (ĉi<t −ĉj<t )+q j })+edµ(q 6=i )

j6=i

(13)

max {ηt (ĉi<t −ĉj<t )+q j }
j6=i

ηt

η

−(max{ηt (ĉi<t −ĉj<t )+q j }+ ti )+pdµ(q 6=i )e pi e j6=iZ
ηt
ηt−(max{ηt (ĉi1:t −ĉj1:t )+q j })+ipdµ(q 6=i ) = e pi π i .
≤ ee j6=i

≤

³
´
η
− t
Hence, π i ≥ pi e pi ≥ pi 1 − ηpti = pi − ηt , which impliesgEq∗ ,qt ,rt ,ut [ĉFPLt |h<t ]nXn
cit X i i=pp 1i=j i =
p ct
p
i=1
j=1
i=1

≤

n
X

i

n
X

j

g

π i cit + nηt = Eq∗ ,qt ,rt ,ut [ĉIFPL|h<t ] + nηt .
ti=1This shows the step from feasible to infeasible FPL. The last step from infeasible
FPL to the best decision in hindsight proceeds as shown already above and in [KV03,
HP05]. Like before, it causes the upper bound of the cumulative regret to increase bylog n. This is true for any (q1:T , r1:T , u1:T ), hence also in expectation. The total regretηTPnis thus upper bounded by log+ n Tt=1 ηt , and we have just proved:
ηT
Theorem 4 The algorithm
q FPL (1), obtaining cost estimates according to (12) andwith learning rate ηt =log nachieves a regret of at most
2nt

p
i
EcFPL
1:T − c1:T ≤ 2 2T n log n

for any i ∈ {1 . . . n}.

(14)

We would like to point to a quite remarkable symmetry break here. It is straightforward to formulate FPL and the analysis from Section 3 for reward maximization
instead of cost minimization. Then the (perturbed) leader is the expert with thehighest (perturbed) reward, and perturbations are added to the scores. In the full
information game, this reward maximization is perfectly symmetric to cost minimization by just setting reward it = 1 − cit : all probabilities, distributions, and outcomes10

J. Poland

will be exactly the same. This is different in the partial observation case: There,in case of reward, the expert by FPL is the only one which can gain score. Thisis an advantage, in contrast to the disadvantage in case of loss minimization: Here,the selected expert is the only one to worsen its score. Put it differently, there is an
automatic exploration or self-stabilization in the cost minimization case. With thisintuition, it is less surprising that we did not need explicit exploration in Theorem 4.
The corresponding result for reward maximization would not hold, as simple counterexamples show. Formally, it is the step from ηFPL to infeasible FPL which fails: Atcomputation similar to (13) only shows π i ≤ pi e pi , which does not imply a sufficiently
strong assertion in general. However, reintroducing the exploration rate γt , q
we mayηtset ηt = γnt . This implies ηpti ≤ 1 for all i, hence e pi ≤ 1 + 2 ηpti . Letting γt =we can conclude a bound like (14).

4.1

n log n,t

A computationally feasible algorithm

We conclude this section by discussing a computationally feasible variant of FPL using
all observations. This algorithm is constructed in a straightforward way: Select thecurrent action i = ItFPL according to FPL and substitute the estimate ĉit from (12) byci
ĉit = p̂ti . It remains to estimate p̂it by a Monte Carlo simulation.
t

There are two possibilities of error: either p̂it overestimates pit , or it underestimates
pit . The respective consequences are different: If p̂it > pit , then the instantaneous costof the selected expert is just underestimated. We can account for this by adding asmall correction to the instantaneous regret. At the end of the game, we perform wellwith respect to the underestimated costs, which are upper bounded by the true costs.
This does not cause any further problems. The case p̂it < pit is more critical, since thenat the end of the game we perform well only w.r.t. overestimated costs. We therefore
have to treat this case more carefully.
Problems arise if the true probability pit is very close to 0, as then the Monte Carlosample might contain very few or no hits and the variance of the estimated cost is
high. Since FPL does not prevent this case, we reintroduce γt as an “exploration1
threshold”. Let γt = 2√
≤ 12 . We first assume that pit ≥ γt . If this assumption is falset
but we use p̂it ≥ γt , then p̂it is an overestimate and we have to consider an additional
instantaneous regret. This case has probability at most γt . Consequently, as (true)
instantaneous costs are always bounded by 1, the additional instantaneous regret is
at most γt .
We sample the perturbed leader k ∈ N times and denote by ai (k) the numberof times the leader happens to be expert i. Recall that expert i is the one alreadyiselected by FPL. By Hoeffding’s inequality, the distribution of a k(k) is sharply peakedaround its mean pi :
h i
i
i
h i
4
4
γ2
γ2
P a k(k) − pi ≥ √t2 ≤ e−γt k and P a k(k) − pi ≤ − √t2 ≤ e−γt k .

11

FPL Analysis for Adaptive Bandits
4

We choose k such that the probability bounds on the r.h.s. are at most γt , i.e. e−γt k ≤
√ ¨
¨ §
§
γt . Consequently we should sample k = γt−4 log(γt−1 ) = 2t2 log(2 t) times. Hencethe sampling complexity of the algorithm is O(t2 log t). Let©
iγ2 ªp̂it := max γt , a k(k) − √t2 ,then p̂it ≤ pit with probability at least 1 − γt (recall the assumption pit ≥ γt ). Hencethe possibility of overestimate p̂it > pit causes an additional regret of γt .
Finally we need to deal with possible
underestimates. For some integer m ≥ 1, the√( m+1)γt2ii√
probability that p̂t falls below pt −is at most
2
h i
i
√
4
mγ 2
P a k(k) − pi ≤ − √2 t ≤ e−mγt k ≤ γtm(15)

by Hoeffding’s inequality. We partition the interval [γt , pti ) of all possible underesti£¢
2γ 2mates into subintervals A1 = pit − √2t , pit and´h√√( m−1+1)γt2( m+1)γt2
i
√
√
,
p
−
,
Am = pit −t22m ≥ 2.

We do not need to consider m with theAm ∩ [γt , pti )q= ∅. That is, we canq property√
restrict to m small enough that pti − 12 ( m + 1)γt2 ≥ γt − 12 γt2 . Let M be the√largest m for which thisqcondition is satisfied, then one can easily see m + 1 ≤√√M + 1 ≤ 2(p − γt + 12 γt2 )/γt2 .
√
cit
cit
√
m + 1).
Claim 5 If m ≤ M , then pi −(√m+1)γ2 / 2 ≤ pi + γt (tttThis follows by a simple algebraic manipulation. Consequently, for p̂ti ∈ Am , we√have Eĉit ≤ cit + ( m + 1)γt . Moreover, p̂it ∈ Am occurs with probability at mostγtm−1 according to (15). By bounding the expectation over all Am , we thus obtain an
additional regret of at most
M
∞
X
X
√
2γt
γt2
m
(m + 2)γtm ≤+≤ 5γt ,
( m + 1)γt ≤ γt
1 − γt (1 − γt )2m=0
m=1

since γt ≤ 12 . Altogether, this proves the following theorem.
1
Theorem 6 Let γt = 2√
be the exploration threshold. In each time step, after selectt©
i
γ2 ª
ing one expert i, let FPL obtain an estimate p̂it = max γt , a k(k) − √t2 for P(ItFPL = i),√ ¨§
by sampling the perturbed leader k = 2t2 log(2 t) times and counting the numberof hits ai (k). Let the estimated cost of the selected expert be ĉit = cit /p̂it , and the estimated cost
q of all other experts be zero. Then the algorithm FPL (1) with learning

rate ηt =log nachieves a regret of at most
2nt

p
√
i
EcFPL
−
c
≤
2
2T
n
log
n
+
7
T
1:T
1:T

for any i ∈ {1 . . . n}.

(16)

12

J. Poland

For t = 1, 2, 3, . . .
¡¢−1
set ĉit = 0 for i ∈ {i : t ≥ τ i } and ĉit = γt min{wi : t ≥ τ i } for i ∈/ {i : t ≥ τ i }sample rt ∈ {0, 1} independently s.t. P [rt = 1] = γt©
log wi −q i ª
If rt = 0, set Itb = arg mini:t≥τ i ĉi<t + ηt t (FPL on the active experts)i

If rt = 1, sample Itb ∈ {i : t ≥ τ i } according to the weights P w i wi
i:t≥τ

Ib
play decision Itb and observe cost ct t
£ Ib P¤ £b¤
Ib
If rt = 1, set ĉt t = ct t i:t≥τ i wi / γt wIt

Figure 2: The algorithm bFPL for infinite expert class. The entering times τ i , theexploration rate γt , and the learning rate ηt , will be specified in Theorem 7.

5

Infinite expert classes

Here, we sketch a variant of bFPL, taken from [PH05], with guaranteed worst-caseperformance against a bandit with countably infinitely many arms. So we consider
the following setup: The adversary subsequently generates cost vectors ct ∈ [0, 1]∞ ,and at each time t we have to select one index or expert i and incur its cost cit . We
learn only the cost of the selected expert.
As a prerequisite, we need that each of the infinitely many experts is associatedPwith a prior weight wi such that i ≤ 1. Since in order to obtain a cost estimate ĉ,the observed cost is divided by the weight of the sampled expert, we have to be careful
not to admit too small weights. We need to keep control of the maximum possible
expected cost, since otherwise the step from FPL to IFPL would be problematic. One
possibility to do so is defining an entering time τ i ≥ 1 for each expert.
tol¡ ¢ 1Priorm1ατ i , the expert is not active and cannot be chosen. We choose τ i =, withwi
0 < α < 1 to be defined later. Then it is not hard to see that the minimum weightof any active expert at time t is lower bounded: min{wi : t ≥ τ i } ≥ t−α . Letting
the exploration rate be γt = t−β with 0 < β < 1 to be defined later, the maximum
unbiasedly estimated cost is at most tα+β . For the step from FPL to IFPL to go
through, we thus may choose ηt = t−2α−2β . Then both steps from bFPL to FPL
P
1
and from FPL to IFPL each cause a regret of at most Tt=1 t−β ≤ 1−β
T 1−β . On theother hand, η1T causes a regret of at most T 2α+2β . In order to minimize these bounds.
simultaneously, we choose β = 1−2α3In order to guarantee that the step from IFPL to some fixed expert holds, we haveto correctly assign estimated costs to inactive experts. For example, if an expert enters
the game and previously has been assigned no estimated cost at all, then a boundw.r.t. this expert may be difficult to obtain. We therefore assign maximum possible
estimated costs to all inactive experts. Then one can show [PH05] that, evaluating
the expected costs, the step IFPL to some fixed reference expert holds almost without
modification. Clearly, the reference expert’s estimated costs now exceed its true costs¡ ¢1+ α1 + αβ
P i −1 α+β
t , which is easily shown to be upper bounded by w1i.
by at most τt=1

FPL Analysis for Adaptive Bandits

13

This gives another additive bound to the regret in terms of the weight of the reference
expert – there is not multiplicative factor of w1i any more. This is an artifact of thedesign of the algorithm and proof technique and does not mean that the new variant¡ 2 2α ¢performs better than the old one. Actually, since α > 0, the bound is now O t 3 + 3¡ 2¢¡ ¢as opposed to O t 3 before. Choosing a large α results in a small w1i term, but theorder in t gets large, while a small α has the opposite effect.
The complete algorithm is specified in Figure 2. The following statement, which
improves on the bounds given in [PH05] (they are based on the workaround from
[MB04]) is an example where we select α = 81 .
Theorem 7 Consider a bandit problem with countably many arms/experts, each expert i having a prior weight wi such that the weights sumlup to mat most 1. Then¡ ¢8
the above described bFPL variant with entering times τ i = w1i, exploration rate
13γt = t− 4 , and learning rate ηt = t− 4 , satisfies the regret bound
µ³ ´
¶
11
3
bFPL
i
i
1
Ec1:T − c1:T ≤ O+ T 4 log w
wi
for all T ≥ 1, any adaptive assignment of the cost vectors and any reference expert i.
The formal proof is omitted. It follows the outline of Theorem 2, using the arguments discussed above. Many of the arguments, including the step from IFPL to thereference expert, are formally carried out in [PH05].

6

Discussion

The main statement of this paper is the following:
If we have a regret minimization algorithm with a bound guaranteed against an oblivious adversary, and if the algorithm chooses thecurrent action/expert by some independent random sampling basedon past cumulative scores (e.g. FPL or weighted majority), then thesame bound also holds against an adaptive adversary. This is true
both for full and partial observations.
We have used this argument for showing bounds for FPL in the adversarial bandit
problem. The strategy to use only feedback from exploration rounds which is common
2for FPL achieves a regret bound of O(t 3 ). As the algorithm is label efficient, this√bound is sharp. Using all observations allows to push the regret down to O( t).
Then however the sampling probabilities have to be approximated.
In the same way, it is possible to use our argument for the general geometric2
online optimization problem [MB04, AK04], also resulting in a O(t 3 ) regret boundagainst adaptive adversary. An interesting open problem is the following: Under

14

J. Poland

which conditions and how is it possible to use all observations in the geometric online√
optimization problem, hopefully arriving at a O( t) bound?
We conclude with a note on regret against an adaptive adversary. We considered
the external regret w.r.t. the best action/strategy/expert from a pool. There are two
directions from here. One is to go to different regret definitions, such as internal regret.
The other one is to change the reference and compare to the hypothetical performanceof the best strategy, in this way accepting a stronger type of dependency of the future
costs from the currently selected action (see e.g. [PH05] and the references therein).
It is one of the major open problems to propose refined algorithms and prove betterbounds in this model.

References[ACBFS95] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in arigged casino: The adversarial multi-armed bandit problem. In Proc. 36th
Annual Symposium on Foundations of Computer Science (FOCS 1995),
pages 322–331, Los Alamitos, CA, 1995. IEEE Computer Society Press.
[ACBFS03] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing,32(1):48–77, Feb. 2003.
[AK04]

B. Awerbuch and R. D. Kleinberg. Adaptive routing with end-to-end
feedback: distributed learning and geometric approaches. In STOC ’04:
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 45–53, 2004.

[CBLS04a] N. Cesa-Bianchi, G. Lugosi, and G. Stoltz. Minimizing regret with label efficient prediction. In 17th Annual Conference on Learning Theory(COLT), volume 3120 of Lecture Notes in Computer Science, pages 77–
92. Springer, 2004.
[CBLS04b] N. Cesa-Bianchi, G. Lugosi, and G. Stoltz. Regret minimization underpartial monitoring. Technical report, 2004.
[FS97]

Y. Freund and R. E. Schapire. A decision-theoretic generalization of online learning and an application to boosting. Journal of Computer and
System Sciences, 55(1):119–139, 1997.

[Han57]

J. Hannan. Approximation to Bayes risk in repeated plays. In M. Dresher,
A. W. Tucker, and P. Wolfe, editors, Contributions to the Theory ofGames 3, pages 97–139. Princeton University Press, 1957.

[HP05]

M. Hutter and J. Poland. Adaptive online prediction by following the perturbed leader. Journal of Machine Learning Research, 6:639–660, 2005.

FPL Analysis for Adaptive Bandits

15[KV03]

A. Kalai and S. Vempala. Efficient algorithms for online decision. In
Proc. 16th Annual Conference on Learning Theory (COLT-2003), Lecture
Notes in Artificial Intelligence, pages 506–521, Berlin, 2003. Springer.

[MB04]

H. B. McMahan and A. Blum. Online geometric optimization in thebandit setting against an adaptive adversary. In 17th Annual Conference
on Learning Theory (COLT), pages 109–123. Springer, 2004.

[PH05]

J. Poland and M. Hutter. Defensive universal learning with experts.
2005. International Conference on Algorithmic Learning Theory (ALT),
to appear.