TCS -TR-A-05-4

TCS Technical Report

Defensive Universal Learning with Experts

byJ. Poland and M. Hutter

Division of Computer Science
Report Series A
July 14, 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

TCS-TR-A-05-4

July 14, 2005

Defensive Universal Learning with
Experts
Jan Poland
Grad. School of Inf. Sci. and Tech.
Hokkaido University, Japan
jan@ist.hokudai.ac.jp
www-alg.ist.hokudai.ac.jp/~janMarcus Hutter
IDSIA, Galleria 2CH-6928 Manno (TI), Switzerland
marcus@idsia.ch
www.idsia.ch/~marcus

Abstract
This paper shows how universal learning can be achieved with expert advice. To this aim, we specify an experts algorithm with the following
characteristics: (a) it uses only feedback from the actions actually chosen(bandit setup), (b) it can be applied with countably infinite expert classes,and (c) it copes with losses that may grow in time appropriately slowly.
We prove loss bounds against an adaptive adversary. From this, we obtaina master algorithm for “reactive” experts problems, which means that themaster’s actions may influence the behavior of the adversary. Our algorithm can significantly outperform standard experts algorithms on suchproblems. Finally, we combine it with a universal expert class. The resulting universal learner performs – in a certain sense – almost as well as
any computable strategy, for any online decision problem. We also specify
the (worst-case) convergence speed, which is very slow.

1

Introduction

Expert advice has become a well-established paradigm of machine learning in the last
decade, in particular for prediction. It is very appealing from a theoretical point ofview, as performance guarantees usually hold in the worst case, without any (statistical) assumption on the data. Such assumptions are generally required for otherstatistical learning methods, often however not resulting in stronger guarantees.
Using expert advice in the standard way seems a rather bad idea in some cases
where the decisions of the learner or master algorithm influence the behavior of theenvironment or adversary. One example is the repeated prisoner’s dilemma when the
opponent plays “tit for tat” (see Section 4). This was noted and resolved by [dFM04],
who introduced a “strategic expert algorithm” for so-called reactive environments.

2

J. Poland and M. Hutter

Their algorithm works with a finite class of experts and attains asymptotically optimal
behavior. No convergence speed is asserted, and the analysis is quite different fromthat of standard experts algorithms.
In this paper, we show how the more general task with a countably infinite expert
class can be accomplished, building on standard experts algorithms, and simultane1
ously also bounding the convergence rate (t− 10 , which can be actually improved to1
t− 3 +ε ). To this aim, we will combine techniques from [Han57, KV03, MB04, HP04]
and obtain a master algorithm which performs well on loss functions that may increase in time. Then this is applied to (possibly) reactive problems by yielding thecontrol to the selected expert for an increasing period of time steps. Using a universal expert class defined by the countable set of all programs on some fixed universal
Turing machine, we obtain an algorithm which is in a sense asymptotically optimal
with respect to any computable strategy. An easy additional construction guarantees
that our algorithm is computable, in contrast to other universal approaches which are
non-computable [Hut04]. To our knowledge, we also propose the first algorithm fornon-stochastic bandit problems with countably many arms.
The paper is structured as follows. Section 2 introduces the problem setup, thenotation, and the algorithm. In Sections 3, we give the (worst-case) analysis of themaster algorithm. The implications to active experts problems and a universal master
algorithms are given in Section 4. We discuss our results in Section 5.

2

The master algorithm

Setup. We are acting in an online decision problem. “We” is here an abbreviation
for the master algorithm which is to be designed. An “online decision problem” isto be understood in a very general sense, it is just a sequence of decisions each ofwhich results in some loss. This could be e.g. a prediction task, a repeated game, etc.
In each round, that is at each time step t, we have access to the recommendationsof countably infinitely many “experts” or strategies. (For simplicity, we restrict ournotation to a countably infinite expert class, all results also hold for finite classes.)
We do not specify what exactly a “recommendation” is – we just follow the advice of
one expert. Before we reveal our move, the adversary has to assign losses `it ≥ 0 to all
experts i. There is an upper bound Bt ≥ k`t k∞ on the maximum loss the adversary
may use. This quantity may depend on t and is not controlled by the adversary. Afterthe move, only the loss of the selected expert i is revealed. Our goal is to performnearly as well as the best available strategy (expert) in terms of cumulative loss, after
any number T of time steps which is not known in advance. The difference between
our loss and the loss of some expert is also termed regret. We consider the general caseof an adaptive adversary, which may assign losses depending on our past decisions.
If there are only finitely many experts or strategies, then it is common to giveno prior preferences to any of them. Formally, this is realized by defining uniform

Defensive Universal Learning with Experts

3

For t = 1, 2, 3, . . .
set `ˆit = B̂t for i 6∈ {t ≥ τ } (see (2))
sample rt ∈ {0, 1} independently s.t. P [rt = 1] = γt
If rt = 0 Then
invoke FPL(t) and play its decision
set `ˆit = 0 for i ∈ {t ≥ τ }Elsesample ItFoE := ut “uniformly”, (1), and play I := ItFoE
set `ˆIt = `It /(uIt γt ) and `ˆit = 0 for i ∈ {t ≥ τ } \ {I}Figure 1: The algorithm FoE . The exploration rate γt will be specified in Corollary8.
d.

Sample qti ∼ Exp independently ∀i ∈ {t ≥ τ }select and play ItFPL = arg min{ηt `ˆi<t + k i − qti }i:t≥τFigure 2: The algorithm FPL. The learning rate ηt will be specified in Corollary 8.

prior weights wi = n1 for each expert i. This is not possible for countably infinite
expert classes, as there is no uniform distribution on the natural numbers. In thiscase, we need some non-uniform prior (wi )i∈N and require wi > 0 for all experts i andP iiii w ≤ 1. We also define the complexity of expert i as k = − ln w . This quantity
is important since in the full observation game (i.e. after our decision we get to know
the losses of all experts), the regret can usually be bounded by some function of thebest expert’s complexity.
Our algorithm “Follow or Explore” (FoE , specified in Fig. 1) builds on McMahan
and Blum’s online geometric optimization algorithm [MB04]. It is a bandit version of a“Follow the Perturbed Leader” experts algorithm. This approach to online prediction
and playing repeated games has been pioneered by Hannan [Han57]. For the fullobservation game and uniform prior, [KV03] gave a very elegant analysis which isclearly different from the standard analysis of exponential weighting schemes. It
has one advantage over other aggregating algorithms such as exponential weighting
schemes: the analysis is not complicated if the learning rate is dynamic rather than
fixed in advance. A dynamic learning rate is necessary if there is no target time T
known in advance. For non-uniform prior, an analysis was given in [HP04]. The
following issues are important for FoE ’s design.
Exploration. Since we are playing the bandit game (as opposed to the full information game), we need to explore sufficiently [ACBFS95, MB04]. At each time step t,
we decide randomly according to some exploration rate γt ∈ (0, 1) whether to explore
or not. If so, we would like to choose an expert according to the prior distribution.
There is a caveat: In order to make the analysis go through, we have to assure that
we are working with unbiased estimates of the losses. This is achieved by dividing the

4

J. Poland and M. Hutter

observed loss by the probability of choosing the expert. But this quantity could become arbitrarily large if we admit arbitrarily small weights. We address this problem
by finitizing the expert pool at each time t. For each expert i, we define an entering
time τ i , that is, expert i is active only for t ≥ τ i . We denote the set of active experts
at time t by {t ≥ τ } = {i : t ≥ τ i }. For exploration, the prior is then replaced by thefinitized prior distribution ut ,wi 1t≥τ iP(ut = i) = P j.
j w 1t≥τ j(1)Consequently, the maximum unbiasedly estimated instantaneous loss is (note that the
exploration probability also scales with the exploration rate γt )
B̂t =

Bt
.
γt min{wi : t ≥ τ i }(2)

It is convenient for the analysis to assign estimated loss of B̂t to all currently inactive
experts. Observe finally that in this way, our master algorithm FoE always deals witha finite expert class and is thus computable.
Follow the perturbed leader (FPL, specified in Fig. 2) is invoked if FoE does
not explore. Just following the “leader” (the best expert so far) may not be a goodstrategy [KV03]. Instead we subtract an exponentially distributed perturbation qt(that is, P(qti ≥ x) = e−x for x ≥ 0) from the current score (the complexity penalized
past loss) of the experts. An important detail of the FPL subroutine is the learning
rate ηt > 0, which should be adaptive if the total number of steps T is not known inadvance. Please see e.g. [KV03, HP04] for more details. Also the variant of FPL weuse (specified in Fig. 2) works on the finitized expert pool.
Note that each time randomness is used, it is assumed to be independent of thepast randomness. Performance is evaluated in terms of true or estimated cumulative
loss, this is specified in the notation. E.g. for the true loss of FPL up to and includingtime T we write `FPL
1:T , while the estimated loss of FoE and not including time T is
FoE
ˆ
`<T .

3

Analysis on the master’s time scale

The following analysis uses McMahan and Blum’s trick [MB04] in order to provebounds against adaptive adversary. With a different argument, it is possible to circumvent Lemma 6, thus achieving better bounds [Pol05]. This will be briefly discussed
in the last section.
Let Bt ≥ 0 be some sequence of upper bounds on the instantaneous losses, γt ∈(0, 1) be a sequence of exploration rates, and ηt > 0 be a decreasing sequence oflearning rates. The analysis proceeds according to the following diagram (where L

Defensive Universal Learning with Experts

5d.

Sample qti ∼ Exp independently for all i ∈ {t ≥ τ }select and play ItFPL = arg min{ηt `ˆi1:t + k i − qti }i:t≥τFigure 3: The algorithm IFPL. The learning rate ηt will be specified in Corollary 8.

is an informal abbreviation for the loss and always refers to cumulative loss, butsometimes additionally to instantaneous loss).
< ELFoE < ELFPL < EL̂FPL < EL̂IFPL < EL̂best < Lbest
LFoE ∼
∼
∼
∼
∼
∼

(3)

< ” means that we bound the quantity on the left by the quantity on the right
Each “ ∼plus some additive term. The first and the last expressions are the losses of the FoE
algorithm and the best expert, respectively. The intermediate quantities belong todifferent algorithms, namely FoE , FPL, and a third one called IFPL for “infeasible”
FPL [KV03]. IFPL, as specified in Fig. 3, is the same as FPL except that it has accessto an oracle providing the current estimated loss vector `ˆt (hence infeasible). Then it
assigns scores of ηt `ˆi1:t + k i − qti instead of ηt `ˆi<t + k i − qti .
The randomization of FoE and FPL gives rise to two filtrations of σ-algebras. By
At we denote the σ-algebra generated by the FoE ’s randomness up to time t, meaning
only the random variables {u1:t , r1:t }. Then (At )t≥0 is a filtration (A0 is the trivial σS
algebra). We may also write A = t≥0 At . Similarly, Bt is the σ-algebra generated by
the FoE ’s and FPL’s randomness up to time t (i.e. Bt ={ub 1:t , r1:t , q1:t }). Then clearlyAt ⊂ Bt for each t.
The reader should think of the expectations in (3) as of both ordinary and conditional expectations. Conditional expectations are mostly with respect to FoE ’s past
randomness At−1 . These conditional expectations of some random variable X areabbreviated by
Et [X] := E[X|At−1 ].
Then Et [X] is an At−1 -measurable random variable, meaning that its value is determined for fixed past randomness At−1 . Note in particular that the estimated loss
vectors `ˆit are random vectors which depend on FoE ’s randomness At up to time t.
In this way, FoE ’s (and FPL’s and IFPL’s) actions depend on FoE ’s past randomness.
Note, however, that they do not depend on FPL’s randomness q1:t .
We now start with proving the diagram (3). In order to understand the analysis,
it is important to consider each intermediate algorithm as a stand-alone procedure
which is actually executed (with an oracle if necessary) on the specified inputs (e.g.
on the estimated losses) and has the asserted performance guarantees (e.g. again on
the estimated losses).

6

J. Poland and M. Hutter£¤< ELFoE For each T ≥ 1 and δT ∈ (0, 1), with probability at least
Lemma 1 LFoE ∼1 − δ2T we have
`FoE
1:T ≤

t
X

Et `FoE+tqP(2 ln δ4T ) Tt=1 Bt2 .

t=1

¤
P £
Proof. The sequence of random variables XT = Tt=1 `FoE
− Et `FoE
is a martingalettwith respect to theBt (not At !). In order to see this, observe E[`FoE
T |BT −1 ] =¯ filtration
¡ FoE
¢
FoE
FoE
¯
E E[`T |AT −1 ] BT −1 and E[`t |BT −1 ] = `t for t < T , which implies
XT ¡
¯
£ FoE
¤¢
¯
E[`FoEt |BT −1 ] − E E[`t |At−1 ] BT −1
t=1
XT −1 ¡¢=
`FoE
− E[`FoEt |At−1 ] = XT −1 .
t

E[XT |BT −1 ] =t=1

Its differences are bounded: |Xt − Xt−1 | ≤ Bt . Hence, it follows from Azuma’s
inequality (see e.g. [MR95]) that the probability that XT exceeds some λ > 0 is¢¡
2bounded by p = 2 exp − 2 Pλ B 2 . Requesting δ2T = p and solving for λ gives thet tassertion.
2£¤< E`FPL Et `FoE
Lemma 2 E`FoE ∼≤ (1 − γt )Et `FPL
+ γt Bt holds ∀t ≥ 1.
ttThis follows immediately from the specification of FoE . Clearly, a corresponding
assertion for the ordinary expectations holds by just taking expectations on bothsides. This is the case for all subsequent lemmas, except for Lemma 6.
The next lemma relating ELFPL and EL̂FPL is technical but intuitively clear. It
states that in expectation, the real loss suffered by FPL is the same as the estimatedloss. This is simply because the loss estimate is unbiased. A combination of this andthe previous lemma was shown in [MB04]. Note that `ˆFPL
is the loss `ˆIt estimated byt
FoE , but for the expert I = ItFPL chosen by FPL.
¤£
< EL̂FPL For each t ≥ 1, we have Et `FPL
= Et `ˆFPL
Lemma 3 ELFPL ∼t .
t
Proof. Let fti = P[ItFPL = i|At−1 ] be the probability distribution over actions i which
FPL uses at time t, depending on the past randomness At−1 . Let ut be the finitizedprior distribution (1) at time t. Then
Et [`ˆFPLt ] = (1 − γt ) · 0 + γt

∞
X
i=1

fti [(1 − uit ) · 0 + uit `ˆit |rt =1∧ItFoE =i ] =∞X

fti `it = Et [`FPL
t ],

i=1

where `ˆit |rt =1∧ItFoE =i = `it /(uit γt ) is the estimated loss under the condition that FoE
2
decided to explore (rt = 1) and chose action ItFoE = i.

7

Defensive Universal Learning with Experts

The following lemma relates the losses of FPL and IFPL. It is proven in [KV03]
and [HP04]. We give the full proof, since it is the only step in the analysis where
we have to be careful with the upper loss bound Bt . Let B̂t be the upper bound on
the estimated loss (2). (We remark that also for weighted averaging forecasters, losses
which grow sufficiently slowly do not cause any problem in the analysis. In this way,
it is straightforward to modify the algorithm by Auer et al. [ACBFS02] for reactive
tasks with a finite expert class.)£¤< EL̂IFPL For all t ≥ 1, Et `ˆFPL
Lemma 4 EL̂FPL ∼≤ Et `ˆIFPL+ γt ηt B̂t2 holds.
ttholds. This happens with probability= `ˆIFPL
Proof. If rt = 0, `ˆt = 0 and thus `ˆFPLtt
1 − γt . Otherwise we have
Et `ˆFPL
=
t

∞ Z
X

1ItFPL =i `ˆit dµ(x),

(4)

i=1

where µ denotes the (exponential) distribution of the perturbations, i.e. xi := qti anddensity µ(x) := e−kxk∞ . The idea is now that if action i was selected by FPL, it
is – because of the exponentially distributed perturbation – with high probability
also selected by IFPL. Formally, we write u+ = max(u, 0) for u ∈ R, abbreviateR
λ = `ˆ<t + k/ηt , and denote by . . . dµ(x6=i ) the integration leaving out the ith action.
Then, using ηt λi − xi ≤ ηt λj − xj ∀j if ItFPL = i in the first equation, and B̂t ≥ `ˆit − `ˆjt
in the last line, we get
ZZ
Z Z−(max{ηt (λi −λj )+xj })+ii`ˆt dµ(xi )dµ(x6=i ) = `ˆit e j6=idµ(x6=i )1ItFPL =i `ˆt dµ(x) =xi ≥max{ηt (λi −λj )+xj }

Z

j6=i

+

−(max{ηt (λi −λj )+xj }+ηt B̂t )`ˆit eηt B̂t e j6=idµ(x6=i )Z−(max{ηt (λi +`ˆit −λj −`ˆjt )+xj })+ηt B̂t≤e`ˆit e j6=idµ(x6=i )Zηt B̂t
1ItIFPL =i `ˆit dµ(x).
=e≤Summing over i and using the analog of (4) for IFPL, we see that if rt = 1, then≥≥ (1 − ηt B̂t )Et `ˆFPL≥ e−ηt B̂t Et `ˆFPL
holds. Thus Et `ˆIFPL≤ eηt B̂t Et `ˆIFPL
Et `ˆFPL
t
t
t
t
t
2
FPL
ˆ
2
Et `t − ηt B̂t . The assertion now follows by taking expectations w.r.t. rt .
The next lemma relates the losses of IFPL and the best action in hindsight. For
an oblivious adversary (which means that the adversary’s decisions do not depend on
our past actions), the proof is quite simple [KV03]. An additional step is necessary
for an adaptive adversary [HP05].

8

J. Poland and M. Hutter

£
¤
P −ki
< EL̂best Assume that
Lemma 5 EL̂IFPL ∼≤ 1 and τ i depends monotonicallyieon k i , i.e. τ i ≥ τ j if and only if k i ≥ k j . Assume decreasing learning rate ηt . For all
T ≥ 1 and all i ≥ 1,T
Xi
Et `ˆIFPL≤ `ˆi1:T + kη+1
.
t
T
t=1

Proof. This is a modification of the corresponding proofs in [KV03] and [HP04]. We
may fix the randomization A and suppress it in the notation. Then we only need to
show
ki +1
ˆi
E`ˆIFPL(5)
1:T ≤ min{`1:T + ηT },i≥1where the expectation is with respect to IFPL’s randomness q1:T .
Assume first that the adversary is oblivious. We define an algorithm A as a variantof IFPL which samples only one perturbation vector q in the beginning and uses thisin each time step, i.e. qt ≡ q. Since the adversary is oblivious, A is equivalent to IFPL
in terms of expected performance. This is all we need to show (5). Let η0 = ∞ and¢¡1, then λ1:t = `ˆ1:t + k−q. Recall {t ≥ τ } = {i : t ≥ τ i }. We
λt = `ˆt + (k − q) η1t − ηt−1
ηtargue by induction that for all T ≥ 1,
T
X
t=1

i
λA
t ≤ min λ1:T + max
T ≥τ

T ≥τ

© qi −ki ª
.
ηT

(6)

This clearly holds for T = 0. For the induction step, we have to show
© qi −ki ª© i iª
ITA+1
ITA+1
A
+
max
min λi1:T + max q η−k
+
λ
≤
λ
+
λ
T +1
1:T
T +1
ηT +1
T
T +1≥τ
T ≥τ
T ≥τ
©
i
iª
= min λi1:T +1 + max qηT−k.
+1
T +1≥τ

(7)

T +1≥τ

©
The inequality is obvious if ITA+1 ∈ {T ≥ τ }. Otherwise, let J = arg max q i − k i : i ∈ª{T ≥ τ } . Thenmin λi1:T + max
T ≥τ
T ≥τ

© qi −ki ªηTJJ≤ λJ1:T + q η−k
T

=

T
X

`ˆJt ≤

t=1

=

T
X

B̂t

t=1

© i iªPT ˆITA+1
ITA+1≤ λ1:T+ max qηT−kt=1 `t+1
T +1≥τ

shows (7). Rearranging terms in (6), we see
T
X
t=1

i
`ˆA
t ≤ min λ1:T +maxi
T ≥τ

T ≥τ

T
© qi −ki ª X
¡
¢
ItA 1
1
+
(q−k)
−
ηT
ηt
ηt−1
t=1

The assertion (5) – still for oblivious adversary and qt ≡ q – then follows by taking
expectations and usingiii
E min λi1:T ≤ min{`ˆi1:T + ηkT − E ηqT } ≤ min{`ˆi1:T + kη−1
} and
T

T ≥τ

T ≥τ

E

i≥1

T
X
¢
© i iªA¡1(q − k)It η1t − ηt−1
≤ E max q η−k
≤
T
t=1

T ≥τ

1
.
ηT

(8)
(9)

9

Defensive Universal Learning with Experts

The second inequality of (8) holds because τ i depends monotonically on k i , and Eq i =i
1, and maximality of `ˆ1:T
for T < τi . The second inequality of (9) can be proven bya simple application of the union bound, see e.g. [HP04, Lem.1].
Sampling the perturbations qt independently is equivalent under expectation to
sampling q only once. So assume that qt are sampled independently, i.e. that IFPL isplayed against an oblivious adversary: (5) remains valid. In the last step, we argue
that then (5) also holds for an adaptive adversary. This is true because the future
actions of IFPL do not depend on its past actions, and therefore the adversary cannot
gain from deciding after having seen IFPL’s decisions. This argument can be madeformal, as shown in [HP05, Lemma 12]. (Note the subtlety that the future actions of
FoE would depend on its past actions.)
2
Finally, we give a relation between the estimated and true losses (adapted from
[MB04]).
£¤< Lbest For each T ≥ 1, δT ∈ (0, 1), and i ≥ 1, we have
Lemma 6 EL̂best ∼qP
P i −1iiˆ(i)`1:T ≤ `1:T + (2 ln δ4T ) Tt=1 B̂t2 + τt=1
B̂t w.p. 1 − δ2T and henceqPP
P i −1ii
ˆ(ii)
E`1:T ≤ `1:T + (2 ln δ4T ) Tt=1 B̂t2 + δ2T Tt=1 B̂t + τt=1
B̂t .
Proof. For t ≥ τ i , Xt = `ˆi1:t − `i1:t is a martingale, since
E[Xt |At−1 ] = E[`ˆi1:t |At−1 ] − `i1:t = Xt−1 + E[`ˆit |At−1 ] − `it = Xt−1 .
P i −1
It is clear that Xτ i −1 ≤ τt=1
B̂t . Moreover, |Xt − Xt−1 | ≤ B̂t for t ≥ τ i , i.e. we haveboundedBy Azuma’s inequality, the actual value XT − Xτ i −1 does not
qdifferences.
PT
exceed (2 ln δ4T ) t=1 B̂t2 with probability 1 − δ2T . This proves (i). To arrive at (ii),take expectations and observe that (i) fails with probability at most δ2T , in which caseP`ˆi1:T ≤ Tt=1 B̂t holds.
2
We now combine the above results and derive an upper bound on the expected
regret of FoE against an adaptive adversary.
Pi
Theorem 7 [FoE against an adaptive adversary] Let i e−k ≤ 1, τ i depend monotonically on k i , and the learning rate ηt be decreasing. Let `t be some possibly adaptive
assignment of (true) loss vectors satisfying k`t k∞ ≤ Bt . Then for all experts i, we
have with probability at least 1 − δT
v

v
u T
u T
i −1
τX
T
T
q
uX
uX
X
X
i
ki +1
`FoE
B̂t + γt ηt B̂t2 + γt Bt + (2 ln δ4T )t B̂t + t Bt2 .
1:T ≤ `1:T + ηT +
t=1

t=1

t=1

t=1

Consequently, in expectation, we have
i

i
k +1
E`FoE
1:T ≤ `1:T + ηT +

i −1
τX

t=1

B̂t +

T
X
t=1

γt ηt B̂t2 +

T
X

v
u
T
T
u
X
X
γ B + t(2 ln 4 )B̂ + δT
B̂ .
t

t=1

t=1

t

t

δT

t=1

t

2

t=1

10

J. Poland and M. Hutter

Proof. This follows by summing up all excess terms in the above lemmas. Recall
that we only need to take expectations on both sides of the assertions of Lemmas 2–5
in order to obtain the second bound on the expectation (and we don’t need Lemma 1
there).
2
3

1

Corollary 8 Assume the conditions of Theorem 7 and choose ηt = t− 4 and γt = t− 4 .
Then√¡ 1 11¢ii 87(i) Bt ≡ 1, τ i = d(wi )−8 e ⇒ E`FoE
ln T ,
1:T ≤ `1:T + O ( wi ) + k T¡ 1 11 i 7 √¢i8(ii) Bt ≡ 1, τ i = d(wi )−8 e ⇒ `FoE
ln T w.p. 1−T −2 ,1:T ≤ `1:T + O ( wi ) +k T√
¡ 1 22¢
1ii 87
ln T , and(iii) Bt = t 16 , τ i = d(wi )−16 e ⇒ E`FoE
1:T ≤ `1:T + O ( wi ) + k T¡ 1 22 i 7 √¢1i8(iv) Bt = t 16 , τ i = d(wi )−16 e ⇒ `FoE
ln T w.p. 1−T −2 ,1:T ≤ `1:T + O ( wi ) +k T
for all i and T ≥ 1 (recall k i = − ln wi ). Moreover, in both cases (bounded andgrowing Bt ) FoE is asymptotically optimal w.r.t. each expert, i.e. for all i,`FoE − `i1:T
lim sup 1:T
≤0
T
T →∞

almost surely.

The asymptotic optimality is sometimes termed Hannan-consistency, in particular
if the limit equals zero. We only show the upper bound.
Proof. Assertions (i)-(iv) follow from the previous theorem: Set δT = T −2 , abbreviate
wTmin = min{wi : t ≥ τ i }, and observe that for τ i = d(wi )−α e and Bt = tβ , we have
11

wTmin = min{wi : T ≥ d(wi )−α e} ≥ min{wi : T − α ≤ wi e} ≥ T − α
τ i −1X(wi )−α Bτ i −1

B̂t ≤ (τ i − 1)B̂τ i −1 ≤ γ iminτ −1 wτ i −1

t=1
1

i −α

and

i −αβ

)
≤ (w ) i (wα4 i(w ) w1−ii (−α)(− α )(note wτmin). Then (i) and (ii) follow from α = 8, β = 0,i −1 ≥ (τ − 1) α ≥ (w )1and (iii) and (iv) follow from α = 16, β = 16
. The asymptotic optimality finallyfollows from the Borel-Cantelli Lemma, since according to (ii) and (iv),
· FoE
¸
√
`1:T − mini `i1:T
1
− 18
P
> CT
ln T ≤ 2TT

for an appropriate C > 0.

2

As mentioned in the first paragraph of this section, it is possible to avoid Lemma¨§
16, thus arriving at better bounds. E.g. in (i), choosing τ i = ( w1i )8 , γt = t− 4 ,¡¢33and ηt = t− 4 , a regret bound of O ( w1i )11 + k i T 4 can be shown. Of course, also a
corresponding high probability bound like (ii) holds. Likewise, for a similar statement
§
¨
1
1
3
as (iii), we may set τ i = ( w1i )16 , Bt = t 8 , γt = t− 4 , and ηt = t− 4 , arriving at a regret¡ 1 23¢¡¢
3
2
bound of O ( wi ) + k i T 4 Generally, in this way any regret bound O ( w1i )c + k i T 3 +εis possible, at the cost of increasing c where ε → 0.

11

Defensive Universal Learning with Experts

set t̃ = 1
For t = 1, 2, 3, . . .
invoke FoE (t) and play its decision for Bt basic time steps
set t̃ = t̃ + Bt
g , where Bt is specified in Corollary 9.
Figure 4: The algorithm FoE

4Reactive environments and a universal master
algorithm

Regret can become a quite subtle notion if we start considering reactive environments,
i.e. care for future consequences of a decision. An extreme case is the “heaven-hell”
example: We have two experts, one always playing 0 (“saying a prayer”), the otherone always playing 1 (“cursing”). If we always follow the first expert, we stay inheaven and get no loss in each step. As soon as we “curse” only once, we get into
hell and receive maximum loss in all subsequent time steps. Clearly, any algorithm
without prior knowledge must “fail” in this situation.
One way to get around this problem is taking into account the actual (realization ofthe) game we are playing. For instance, after “cursing” once, also the praying expert
goes to hell together with us and subsequently has maximum loss. Hence, were areinterested in a regret defined as E`1:T − `i1:T as in the previous section. So what is
missing? This becomes clear in the following example.
Consider the repeated “prisoner’s dilemma” against the tit-for-tat1 strategy [dFM04].
If we use two strategies as experts, namely “always cooperate” and “always defect”,
then it is clear that always cooperating will have the best long-term reward. However standard expert advice or bandit master algorithm will not discover this, since it
compares only the losses in one step, which are always lower for the defecting expert.
To put it differently, minimizing short-term regret is not at all a good idea here. E.g.
always defecting has no regret, while for always cooperating the regret grows linearly.
But this is only the case for short-term regret, i.e. if we restrict to time intervals oflength one.
We therefore give the control to a selected expert for periods of increasing length.
Precisely, we introduce a new time scale t̃ (the basic time scale) at which we have single
games with losses `˜t̃ . The master’s time scale t does not coincide with t̃. Instead, ateach t, the master gives control to the selected expert i for Bt ≥ 1 single games andPt̃(t)+B −1
receives loss `it = t̃=t̃(t) t `˜it̃ . (The points t̃(t) in basic time are defined recursively,
see Fig. 4.) Assume that the game has bounded instantaneous losses `˜i ∈ [0, 1].
t̃1

In the prisoner’s dilemma, two players both decide independently if thy are cooperating (C)or defecting (D). If both play C, they get both a small loss, if both play D, they get a large loss.
However, if one plays C and one D, the cooperating player gets a very large loss and the defecting
player no loss at all. Thus defecting is a dominant strategy. Tit-for-tat plays C in the first moveand afterwards the opponent’s respective preceding move.

12

J. Poland and M. Hutter

Then the master algorithm’s instantaneous losses are bounded by Bt . We denoteg . Then the following
the algorithm, which is completely specified in Fig. 4, by FoE
assertion is an easy consequence of the previous results.
g plays a repeated game with bounded instantaneous losses
Corollary 9 Assume FoE131`˜it̃ ∈ [0, 1]. Choose γt = t− 4 , ηt = t− 4 , Bt = bt 16 c and τ i = d(wi )−16 e. Then for all
experts i and all T̃ ≥ 1,¡¢g
˜i + O ( 1i )22 + k i T̃ 109 w.p. 1 − T̃ − 32
17 and
`˜FoE
≤
`
w
1:T̃
1:T̃
¡
9 ¢
g
E`˜FoE≤ `˜i1:T̃ + O ( w1i )22 + k i T̃ 10 .
1:T̃gConsequently, lim supT →∞ (`˜FoE− `˜i1:T̃ )/T̃ ≤ 0 a.s. The rate of convergence is at least
1:T̃1
1T̃ − 10 , and it can be improved to T̃ − 3 +ε at the cost of a larger power of w1i .

Proof. This follows from changing the time scale from t topt̃ in Corollary 8: t̃ is of order
¢
¡
¡
15
9 ¢
1
t1+ 16 . Consequently, the regret bound is O ( w1i )22 +k i T̃ 17 ln T̃ ≤ O ( w1i )22 +k i T̃ 10 .
2
Broadly spoken, this means that FoE T̃ performs asymptotically as well as thebest expert. Asymptotic performance guarantees for the Strategic Experts Algorithm
have been derived in [dFM04]. Our results improve upon this by providing a rate ofconvergence. One can give further corollaries, e.g. in terms of flexibility as defined in[dFM04].
Since we can handle countably infinite expert classes, we may specify a universal
experts algorithm. To this aim, let expert i be derived from the ith (valid) programpi of some fixed universal Turing machine. The ith program can be well-defined,
e.g. by representing programs as binary strings and lexicographically ordering them
[Hut04]. Before the expert is consulted, the relevant input is written to the input
tape of the corresponding program. If the program halts, an appropriate part ofthe output is interpreted as the expert’s recommendation. E.g. if the decision isbinary, then the first bit suffices. (If the program does not halt, we may for welldefinedness just fill its output tape with zeros.) Each expert is assigned a prior weightiby wi = 2−length(p ) , where length(pi ) is the length of the corresponding program andwe assume the program tape to be binary. This construction parallels the definitionof Solomonoff’s universal prior [Sol78].
g is used together with a universal expert class as specified above
Corollary 10 If FoE
and the parameters ηt , γt , Bt , δT are chosen as in Corollary 9, then it performs asymptotically at least as well as any computable expert i. The upper bound on the rate of1
convergence is exponential in the complexity k i and proportional to t̃− 10 (improvable1
to t̃− 3 +ε ).

Defensive Universal Learning with Experts

13

The universal prior has been used to define a universal agent AIXI in a quite
different way [Hut01, Hut04]. Note that like the universal prior and the AIXI agent,
our universal experts algorithm is not computable, since we cannot check if a thecomputation of an expert halts. On the other hand, if used with computable experts,
the algorithm is computationally feasible (at each time t we need to consider only
finitely many experts). Moreover, it is easy to impose an additional constraint on
the computation time of each expert and abort the expert’s computation after Ct
operations on the Turing machine. We may choose some (possibly rapidly) growing
function Ct , e.g. Ct = 2t . The resulting master algorithm is fully computable and has
small regret with respect to all resource bounded strategies.
It is important to keep in mind that Corollaries 9 and 10 give assertions relative tothe experts’ performance merely on the actual action-observation sequence. In otherg does, we have to evaluate the actual value ofwords, if we wish to assess how well FoE
the best expert [dFM05]. Note that the whole point of our increasing time construction
is to cause this actual value to coincide with the value under ideal conditions. Forg,passive tasks, this coincidence always holds with any experts algorithm. With FoE
the actual and the ideal value of an expert coincide in many further situations, suchas “finitely controllable tasks”. By this we mean cases where the best expert can drive
the environment into some optimal state in a fixed finite number of time steps. An
instance is the prisoner’s dilemma with tit-for-tat being the opponent. The following
is an example for a formalization of this statement.
g acts in a (fully or partially observable) Markov DeciProposition 11 Suppose FoEsion Process. Let there be a computable strategy which is able to reach an ideal (thatgis optimal w.r.t. reward) state sequence in a fixed number of time steps. Then FoE
performs asymptotically optimal.
This statement may be generalized to cases where only a close to optimal state
sequence is reached with high probability. However, we need assumptions on thecloseness to optimality for a given target probability, which are compatible with theg.
sampling behavior of FoE
Not all environments have this or similar nice properties. As mentioned above, any
version of FoE would not perform well in the “heaven-hell” example. The following
is a slightly more interesting variant of the heaven-hell task, where we might wish tolearn optimal behavior, however FoE will not. Consider the heaven-hell example fromthe beginning of this section, but assume that if at time t I am in hell and I “pray”
for t consecutive time steps, I will get back into heaven. Then it is not hard to seethat FoE ’s exploration is so dominant that almost surely, FoE will eventually stay inhell.
Simulations with some 2 × 2 matrix games show similar effects, depending on
the opponent. We briefly discuss the repeated game of “chicken”2 . In this game,2

This game, also known as “Hawk and Dove”, can be interpreted as follows. Two coauthors write

14

J. Poland and M. Hutter

it is desirable for the learner to become the “dominant defector”, i.e. to defect inthe majority of the cases while the opponent cooperates. Let’s call an opponent“primitive” if he agrees to cooperate after a fixed number of consecutive defecting
moves of FoE , and let’s call him “stubborn” if this number is high. Then FoE learns
to be the dominant defector against any primitive opponent, however stubborn. On
the other hand, if the opponent is some learning strategy which also tries to be
the dominant defector and learns faster (we conducted the experiment with AIXI
[Hut04]), then FoE settles for cooperating, and the opponent will be the dominant
defector. Interestingly however, AIXI would not learn to defect against a stubborn
primitive opponent. Under this point of view, it seems questionable that there issomething like a universally optimal balance of exploration vs. exploitation in active
learning at all.

5

Discussion

An alternative argument for adaptive adversary. As mentioned in the beginning of Section 3, the analysis we gave uses a trick from [MB04]. Such a trick seems
necessary, as the basic FPL analysis only works for oblivious adversary. The simple
argument from [HP05] which we used in the last paragraph of the proof of Lemma 5
works only for full observation games (note that considering the estimated losses, wewere actually dealing with full observations there). In order to obtain a similar resultin the partial observation case, we may argue as follows. We let the game proceed for
T time steps with independent randomization against an adaptive adversary. Then
we analyze FoE ’s performance in retrospective. In particular, we note that for thelosses assigned by the adversary, FoE ’s expected regret coincides with the regret ofanother, virtual algorithm, which uses (in its FPL subroutine) identical perturbations
qt ≡ q. Performing the analysis for this virtual algorithm, we arrive at the desired
assertion, however without needing Lemma 6. This results in tighter bounds as statedabove. The argument is formally elaborated in [Pol05].
Actual learning speed and lower bounds. In practice, the bounds we have
proven seem irrelevant except for small expert classes, although asserting almost sure
optimality and even a convergence rate. The exponential of the complexity w1i may
be huge. Imagine for instance a moderately complex task and some good strategy,
which can be coded with mere 500 bits. Then its prior weight is 2−500 , a constantwhich is not distinguishable from zero in all practical situations. Thus, it seems thatthe bounds can be relevant at most for small expert classes with uniform prior. Thisa paper, but each tries to spend as little effort as possible. If one succeeds to let the other do thewhole work, he has a high reward. On the other hand, if no one does anything, there will be no
paper and thus¡no reward.
Finally, if both decide to cooperate, both get some reward. We choose the¢
1 0loss matrix as 0.8,
thelearner is the column player, the opponent’s loss matrix is the transpose,
0.5choosing the fist column means to defect, the second to cooperate. Hence, in the repeated game, it
is socially optimal to take turns cooperating and defecting.

Defensive Universal Learning with Experts

15

is a general shortcoming of bandit style experts algorithms: For uniform prior a lower√
bound on the expected loss which scales with n (where n is the size of the expert
class) has been proven [ACBFS02].
In order to get a lower bound on FoE ’s regret in the time T , observe that FoE is alabel-efficient learner [CBLS04a, CBLS04b]: According to the definition in [CBLS04b],
we may assume that in each exploration step, we incur maximal loss Bt . It is immediate that the same analysis then still holds. For label-efficient prediction, Cesa-Bianchi
2
et al. [CBLS04b] have shown a lower regret bound of O(T 3 ). Since according to the¡¢2remark at the end of Section 3, we have an upper bound of O ( w1i )c + k i T 3 +ε , thisis almost tight except for the additive ( w1i )c term. It is an open problem to state alower bound simultaneously tight in both w1i and T .
Even if the bounds, in particular w1i , seem not practical, maybe FoE would learn
sufficiently quickly in practice anyway? We believe that this is not so in most cases:
The design of FoE is too much tailored towards worst-case environments, FoE is too
defensive. Assume that we have a “good” and a “bad” expert, and FoE learns this1
fact after some time. Then it still would spend a relatively huge fraction of γt = t− 4
to exploring the bad expert. Such defensive behavior seems only acceptable if we are
already starting with a class of good experts.
Acknowledgment. This work was supported by SNF grant 2100-67712.02 and JSPS
21st century COE program C01.

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.
[ACBFS02] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing,32(1):48–77, 2002.
[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.
[dFM04]

D. Pucci de Farias and N. Megiddo. How to combine expert (and novice)advice when actions impact the environment? In Sebastian Thrun,

16

J. Poland and M. Hutter

Lawrence Saul, and Bernhard Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.
[dFM05]

D. Pucci de Farias and N. Megiddo. Exploration-exploitation tradeoffs
for experts algorithms in reactive environments. In Advances in Neural
Information Processing Systems 17. 2005.

[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.

[HP04]

M. Hutter and J. Poland. Prediction with expert advice by following
the perturbed leader for general weights. In International Conference on
Algorithmic Learning Theory (ALT), pages 279–293, 2004.

[HP05]

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

[Hut01]

M. Hutter. Towards a universal theory of artificial intelligence basedon algorithmic probability and sequential decisions. Proc. 12th European
Conference on Machine Learning (ECML-2001), pages 226–238, December 2001.

[Hut04]

M. Hutter. Universal Artificial Intelligence: Sequential Decisions basedon Algorithmic Probability. Springer, Berlin, 2004.

[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.

[MR95]

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms.
Cambridge University Press, Cambridge, England, June 1995.

[Pol05]

J. Poland. FPL analysis for adaptive bandits. 2005. 3rd Symposium on
Stochastic Algorithms, Foundations and Applications (SAGA), to appear.

[Sol78]R. J. Solomonoff. Complexity-based induction systems: comparisons andconvergence theorems. IEEE Trans. Inform. Theory, 24:422–432, 1978.