Thompson Sampling is Asymptotically Optimal in General Environments

Jan Leike
Australian National University
jan.leike@anu.edu.au

Tor Lattimore
University of Alberta
tor.lattimore@gmail.com

Marcus Hutter
Australian National University
marcus.hutter@anu.edu.au

Abstract

We discuss two different notions of optimality: asymptotic
optimality and worst-case regret.

We discuss a variant of Thompson sampling for
nonparametric reinforcement learning in countable classes of general stochastic environments.
These environments can be non-Markov, nonergodic, and partially observable. We show that
Thompson sampling learns the environment classin the sense that (1) asymptotically its value converges to the optimal value in mean and (2) givena recoverability assumption regret is sublinear.

Asymptotic optimality requires that asymptotically theagent learns to act optimally, i.e., that the discounted
value of the agent’s policy π converges to the optimal discounted value, Vµ∗ − Vµπ → 0 for all environments µfrom the environment class. This convergence is impossible for deterministic policies since the agent has to explore infinitely often and for long stretches of time, butthere are policies that converge almost surely in Cesàroaverage [LH11]. Bayes-optimal agents are generally not
asymptotically optimal [Ors13]. However, asymptotic optimality can be achieved through an exploration component
on top of a Bayes-optimal agent [Lat13, Ch. 5] or throughoptimism [SH15].

Keywords. General reinforcement learning, Thompson
sampling, asymptotic optimality, regret, discounting, recoverability, AIXI.

1

Laurent Orseau
Google DeepMind
lorseau@google.com

INTRODUCTION

In reinforcement learning (RL) an agent interacts with an
unknown environment with the goal of maximizing rewards. Recently reinforcement learning has received asurge of interest, triggered by its success in applications
such as simple video games [MKS+ 15]. However, theory
is lagging behind application and most theoretical analyses has been done in the bandit framework and for Markov
decision processes (MDPs). These restricted environment
classes fall short of the full reinforcement learning problem
and theoretical results usually assume ergocity and visiting
every state infinitely often. Needless to say, these assumptions are not satisfied for any but the simplest applications.
Our goal is to lift these restrictions; we consider general reinforcement learning, a top-down approach to RL with theaim to understand the fundamental underlying problems intheir generality. Our approach to general RL is nonparametric: we only assume that the true environment belongs
to a given countable environment class.
We are interested in agents that maximize rewards optimally. Since the agent does not know the true environment
in advance, it is not obvious what optimality should mean.

Asymptotic optimality in mean is essentially a weaker variant of probably approximately correct (PAC) that comes
without a concrete convergence rate: for all ε > 0 andδ > 0 the probability that our policy is ε-suboptimal converges to zero (at an unknown rate). Eventually this probability will be less than δ. Since our environment class canbe very large and non-compact, concrete PAC/convergence
rates are likely impossible.
Regret is how many expected rewards the agent forfeits by
not following the best informed policy. Different problem classes have different regret rates, depending on the
structure and the difficulty of the problem class. Multiarmed bandits provide√a (problem-independent) worst-caseregret bound of Ω( KT ) where K is the number ofarms [BB12]. In Markov
decision processes (MDPs) the√lower bound is Ω( DSAT ) where S is the number ofstates, A the number of actions, and D the diameter ofthe MDP [AJO10]. For a countable class of environments
given by state representation functions that map histories
to MDP states, a regret of Õ(T 2/3 ) is achievable assuming
the resulting MDP is weakly communicating [NMRO13].
A problem class is considered learnable if there is an algorithm that has a sublinear regret guarantee.
This paper continues a narrative that started with definition

of the Bayesian agent AIXI [Hut00] and the proof that it
satisfies various optimality guarantees [Hut02]. Recently it
was revealed that these optimality notions are trivial or subjective [LH15]: a Bayesian agent does not explore enoughto lose the prior’s bias, and a particularly bad prior canmake the agent conform to any arbitrarily bad policy aslong as this policy yields some rewards. These negative results put the Bayesian approach to (general) RL into question. In this paper we remedy the situation by showing thatusing Bayesian techniques an agent can indeed be optimal
in an objective sense.
The agent we consider is known as Thompson sampling,posterior sampling, or the Bayesian control rule [Tho33].
It samples an environment ρ from the posterior, follows
the ρ-optimal policy for one effective horizon (a lookahead
long enough to encompass most of the discount function’smass), and then repeats. We show that this agent’s policy is
asymptotically optimal in mean (and, equivalently, in probability). Furthermore, using a recoverability assumption on
the environment, and some (minor) assumptions on the discount function, we prove that the worst-case regret is sublinear. This is the first time convergence and regret boundsof Thompson sampling have been shown under such general conditions.
Thompson sampling was originally proposed by Thompson as a bandit algorithm [Tho33]. It is easy to implement and often achieves quite good results [CL11].
In multi-armed bandits it attains optimal regret [AG11,
KKM12]. Thompson sampling has also been consideredfor MDPs: as model-free method relying on distributions
over Q-functions with convergence guarantee [DFR98],
and as a model-based algorithm without theoretical analysis [Str00]. Bayesian and frequentist regret bounds havealso been established [ORvR13, OR14, GM15]. PAC guarantees have been established for an optimistic variant ofThompson sampling for MDPs [ALL+ 09].
For general RL Thompson sampling was first suggested in[OB10] with resampling at every time step. The authors
prove that the action probabilities of Thompson sampling
converge to the action probability of the optimal policy almost surely, but require a finite environment class and two(arguably quite strong) technical assumptions on the behavior of the posterior distribution (akin to ergodicity) and thesimilarity of environments in the class. Our convergence
results do not require these assumptions, but we rely onan (unavoidable) recoverability assumption for our regretbound.
Appendix A contains a list of notation and Appendix B
contains omitted proofs.

2

PRELIMINARIESS∞The set X ∗ := n=0 X n is the set of all finite strings over
the alphabet X and the set X ∞ is the set of all infinite
strings over the alphabet X . The empty string is denotedby , not to be confused with the small positive real number ε. Given a string x ∈ X ∗ , we denote its length by |x|.
For a (finite or infinite) string x of length ≥ k, we denotewith x1:k the first k characters of x, and with x<k the firstk − 1 characters of x.
The notation ∆Y denotes the set of probability distributions over Y.
In reinforcement learning, an agent interacts with an environment in cycles: at time step t the agent chooses anaction at ∈ A and receives a percept et = (ot , rt ) ∈ E
consisting of an observation ot ∈ O and a real-valued reward rt ; the cycle then repeats for t + 1. We assume thatrewards are bounded between 0 and 1 and that the set ofactions A and the set of percepts E are finite.
We
P∞fix a discount function γ : N → R with γt ≥ 0 andt < ∞. Our goal is to maximize discounted ret=1 γ
P∞wards t=1 γt rP
t . The discount normalization factor is de∞fined as Γt := k=t γk . The effective horizon Ht (ε) is ahorizon that is long enough to encompass all but an ε of the
discount function’s mass:
Ht (ε) := min{k | Γt+k /Γt ≤ ε}(1)

A history is an element of (A × E)∗ . We use æ ∈ A × E
to denote one interaction cycle, and æ <t to denote a history of length t − 1. We treat action, percepts, and histories
both as outcomes and as random variables. A policy is afunction π : (A × E)∗ → ∆A mapping a history æ <t to a
distribution over the actions taken after seeing this history;
the probability of action a is denoted π(a | æ <t ). An environment is a function ν : (A × E)∗ × A → ∆E mapping ahistory æ <t and an action at to a distribution over the percepts generated after this history; the probability of percept
e is denoted ν(e | æ <t at ).
A policy π and an environment ν generate a probability
measure ν π over infinite histories (A × E)∞ , defined by its
values on the cylinder sets {h ∈ (A × E)∞ | h<t = æ <t }:πν (æ <t ) :=t−1
Yπ(ak | æ <k )ν(ek | æ <k ak )k=1

When we take an expectation Eπν of a random variable
Xt (æ <t ) this is to be understood as the expectation of thehistory æ <t for a fixed time step t drawn from ν π , i.e.,XEπν [Xt (æ <t )] :=ν π (æ <t )Xt (æ <t ).
æ <tWe often do not explicitly add the subscript t to timedependent random variables.

Definition 1 (Value Function). The value of a policy π inan environment ν given history æ <t is defined as
"∞
#
1 π X
π
Vν (æ <t ) := Eν
γk rk æ <t ,Γt
k=t

if Γt > 0 and Vνπ (æ <t ) := 0 if Γt = 0. The optimal value
is defined as Vν∗ (h) := supπ Vνπ (h).
The normalization constant 1/Γt ensures that values arebounded between 0 and 1. We also use the truncated valuefunction
"m
#
1 π X
π,m
γk rk æ <t .
Vν (æ <t ) := Eν
Γt
k=t

3

THOMPSON SAMPLING IS
ASYMPTOTICALLY OPTIMAL

Strens proposes following the optimal policy for one
episode or “related to the number of state transitions theagent is likely to need to plan ahead” [Str00]. We follow
Strens’ suggestion and resample at the effective horizon.
Let εt be a monotone decreasing sequence of positive reals
such that εt → 0 as t → ∞. We define our Thompsonsampling policy πT in Algorithm 1.
Algorithm 1 Thompson sampling policy πT
1: while true do2:
sample ρ ∼ w( · | æ <t )3:follow πρ∗ for Ht (εt ) steps

For each environment µ there is an optimal policy πµ∗ thattakes an optimal action for each history [LH14, Thm. 10]:πµ∗ (at | æ <t ) > 0 =⇒ at ∈ arg max Vµ∗ (æ <t a)Note that πT is a stochastic policy since we occasionallysample from a distribution. We assume that this samplingis independent of everything else.

Let M denote a countable class of environments. We assume that M is large enough to contain the true environment (e.g. the class of all computable environments). Letw ∈ ∆M be a prior probability distribution on M and let
X
ξ :=
w(ν)ν

Definition 3 (Asymptotic Optimality). A policy π is
asymptotically optimal in an environment class M iff forall µ ∈ Madenote the corresponding Bayesian mixture over the class
M. After observing the history æ <t the prior w is updated
to the posteriorν(æ <t ).
ξ(æ <t )P
We also use the notation w(M0 | æ <t ) := ν∈M0 w(ν |æ <t ) for a set of environments
M0 ⊆ M. Likewise weP
define ν(A | æ <t ) := h∈A ν(h | æ <t ) for a prefix-free
set of histories A ⊆ (A × E)∗ .
Let ν, ρ ∈ M be two environments, let π1 , π2 be two policies, and let m ∈ N be a lookahead time step. The total
variation distance is defined as
Dm (ν π1 , ρπ2 | æ <t ) :=sup

ν π1 (A | æ <t ) − ρπ2 (A | æ <t ) .

A⊆(A×E)m

with D∞ (ν π1 , ρπ2 | æ <t ) := limm→∞ Dm (ν π1 , ρπ2 |æ <t ).
Lemma 2 (Bounds on Value Difference). For any policies
π1 , π2 , any environments ρ and ν, and any horizon t ≤m ≤ ∞,|Vνπ1 ,m (æ<t ) − Vρπ2 ,m (æ<t )| ≤ Dm (ν π1 , ρπ2 | æ<t )Proof. See Appendix B.

(2)on histories drawn from µπ .

ν∈Mw(ν | æ <t ) := w(ν)

Vµ∗ (æ <t ) − Vµπ (æ <t ) → 0 as t → ∞There are different types of asymptotic optimalities basedon the type of stochastic convergence in (2). If this convergence occurs almost surely, it is called strong asymptotic optimality [LH11, Def. 7]; if this convergence occurs
in mean, it is called asymptotic optimality in mean; if thisconvergence occurs in probability, it is called asymptotic
optimality in probability; and if the Cesàro averages converge almost surely, it is called weak asymptotic optimality [LH11, Def. 7].
3.1

ASYMPTOTIC OPTIMALITY IN MEAN

This subsection is dedicated to proving the following theorem.
Theorem 4 (Thompson Sampling is Asymptotically Optimal in Mean). For all environments µ ∈ M,
EπµT Vµ∗ (æ<t ) − VµπT (æ<t ) → 0 as t → ∞.
This theorem immediately implies that Thompson sampling is also asymptotically optimal in probability: Theconvergence in mean of the random variables Xt :=Vµ∗ (æ <t ) − VµπT (æ <t ) stated in Theorem 4 is equivalent
to convergence in probability in the sense that µπT [Xt >ε] → 0 as t → ∞ for all ε > 0 because the random variables Xt are nonnegative and bounded. However, this does
not imply almost sure convergence (see Section 3.3).

Define the Bayes-expected total variation distanceπFm(æ <t ) :=Xw(ρ | æ <t )Dm (ρπ , ξ π | æ <t )ρ∈M

for m ≤ ∞.
If we replace the distance measure Dm by cross-entropy,πthen the quantity Fm(æ <t ) becomes the Bayes-expected
information gain [Lat13, Eq. 3.5].
For the proof of Theorem 4 we need the following lemma.
Lemma 5 (F Vanishes On-Policy). For any policy π andany environment µ,πEπµ [F∞(æ<t )] → 0 as t → ∞.

Proof. See Appendix B.

where wmin := inf{w(ν | æ <k ) | k ∈ N, ν ∈ M0 }, whichis positive by (i).
(i) and (ii) are satisfied eventually because the posteriorw( · | æ <t ) converges µπT -almost surely. Note that theset M0 is random: the limit of w(ν | æ <t ) as t → ∞ depends on the history æ 1:∞ . Without loss of generality, we
assume the true environment µ is contained in M0 sincew(µ | æ <t ) 6→ 0 µπT -almost surely. (iii) follows from
Lemma 5 since convergence in mean implies convergencein probability.
Moreover, we define the horizon m := t + Ht (εt ) as thetime step of the effective horizon at time step t. Let æ <t bea fixed history for which (i-iii) is satisfied. Then we have2πTδβwmin> F∞(æ <t )
X=w(ν | æ <t )D∞ (ν πT , ξ πT | æ <t )ν∈MProof of Theorem 4. Let β, δ > 0 and let εt > 0 denotethe sequence used to define πT in Algorithm 1. We assume
that t is large enough such that εk ≤ β for all k ≥ t andthat δ is small enough such that w(µ | æ <t ) > 4δ for allt, which holds since w(µ | æ <t ) 6→ 0 µπ -almost surely forany policy π [Hut09, Lem. 3i].
The stochastic process w(ν | æ <t ) is a ξ πT -martingale
sinceEπξ T [w(ν | æ 1:t ) | æ <t ]X
ν πT (æ 1:t )=ξ πT (æ t | æ <t )w(ν) πTξ (æ 1:t )a et tν πT (æ t | æ <t )=
ξ (æ t | æ <t )w(ν | æ <t ) πT
ξ (æ t | æ <t )at etX= w(ν | æ <t )
ν πT (æ t | æ <t )XπTa t et= w(ν | æ <t ).
By the martingale convergence theorem [Dur10,
Thm. 5.2.8] w(ν | æ <t ) converges ξ πT -almost surely andbecause ξ πT ≥ w(µ)µπT it also converges µπT -almost
surely.
We argue that we can choose t0 to be one of πT ’s resampling time steps large enough such that for all t ≥ t0
the following three events hold simultaneously with µπT probability at least 1 − δ.
(i) There is a finite set M0 ⊂ M with w(M0 | æ <t ) >1−δ and w(ν | æ <k ) 6→ 0 as k → ∞ for all ν ∈ M0 .
(ii) |w(M00 | æ <t ) − w(M00 | æ <t0 )| ≤ δ for all M00 ⊆M0 .

= Eν∼w( ·|æ <t ) [D∞ (ν πT , ξ πT | æ <t )]≥ Eν∼w( ·|æ <t ) [Dm (ν πT , ξ πT | æ <t )]2≥ βwminw(M \ M00 | æ <t )by Markov’s inequality where2.
M00 := ν ∈ M Dm (ν πT , ξ πT | æ <t ) < βwmin
For our fixed history æ <t we have
1 − δ < w(M00 | æ <t )(i)≤ w(M00 ∩ M0 | æ <t ) + δ(ii)≤ w(M00 ∩ M0 | æ <t0 ) + 2δ(i)

≤ w(M00 | æ <t0 ) + 3δand thus we get2
1 − 4δ < w Dm (ν πT , ξ πT | æ <t ) < βwmin
æ <t0 .
(3)
In particular, this bound holds for ν = µ since w(µ |æ <t0 ) > 4δ by assumption.
π∗

It remains to show that with high probability the value Vµ ρof the sample ρ’s optimal policy πρ∗ is sufficiently close to
the µ-optimal value Vµ∗ . The worst case is that we draw
the worst sample from M0 ∩ M00 twice in a row. From
now on, let ρ denote the sample environment we draw attime step t0 , and let t denote some time step between t0
and t1 := t0 + Ht0 (εt0 ) (before the next resampling). With
probability w(ν 0 | æ <t0 )w(ν 0 | æ <t1 ) we sample ν 0 both
at t0 and t1 when following πT . Therefore we have for allæ t:m and all ν ∈ M
ν πT (æ 1:m | æ <t )∗πT2(iii) F∞(æ <t ) < δβwmin.

≥ w(ν 0 | æ <t0 )w(ν 0 | æ <t1 )ν πν 0 (æ 1:m | æ <t ).

Thus we get for all ν ∈ M0 (in particular ρ and µ)

totic optimality. However, both notions are not so fundamentally different because they both allow an infinite number of bad mistakes (actions that lead to Vµ∗ − Vµπ being
large). Asymptotic optimality in mean allows bad mistakes
as long as their probability converges to zero; weak asymptotic optimality allows bad mistakes as long as the total
time spent on bad mistakes grows sublinearly.

Dm (µπT , ρπT | æ <t )
≥ sup

sup

ν 0 ∈M A⊆(A×E)mw(ν 0 | æ <t0 )w(ν 0 | æ <t1 )∗∗(µπν 0 (A | æ <t ) − ρπν 0 (A | æ <t ))≥ w(ν | æ <t0 )w(ν | æ <t1 )πν∗Lattimore and Hutter show that weak asymptotic optimality is possible in a countable class of deterministic environments using an MDL-agent that explores through burstsof random walks [LH11, Def. 10]. For classes of stochastic environments, BayesExp is weakly asymptotically optimal [Lat13, Ch. 5]. However, this requires the additional condition that the effective horizon grows sublinearly, Ht (εt ) ∈ o(t), while Theorem 4 does not require
this condition.

πν∗µ (A | æ <t ) − ρ (A | æ <t )supA⊆(A×E)m∗∗2≥ wminDm (µπν , ρπν | æ <t ).

For ρ ∈ M00 we get
Dm (µπT , ρπT | æ <t )≤ Dm (µπT , ξ πT | æ <t ) + Dm (ρπT , ξ πT | æ <t )
(3)

2
2
2
< βwmin+ βwmin= 2βwmin,which implies together with Lemma 2 and the fact that rewards in [0, 1]π∗π∗Vµ ν (æ <t ) − Vρ ν (æ <t )
Γt+Ht (εt )π ∗ ,mπ ∗ ,m+ Vµ ν (æ <t ) − Vρ ν (æ <t )Γt∗∗≤ εt + Dm (µπν , ρπν | æ <t )≤≤ εt + w21 Dm (µπT , ρπT | æ <t )min

< β + 2β = 3β.
Hence we get (omitting history arguments æ <t for simplicity)π∗π∗Vµ∗ = Vµ µ < Vρ µ + 3β ≤ Vρ∗ + 3β
π∗

π∗

π∗

(4)

= Vρ ρ + 3β < Vµ ρ + 3β + 3β = Vµ ρ + 6β.
With µπT -probability at least 1−δ (i), (ii), and (iii) are true,
with µπT -probability at least 1 − δ our sample ρ happens to
be in M0 by (i), and with w( · | æ <t0 )-probability at least
1 − 4δ the sample is in M00 by (3). All of these events aretrue simultaneously with probability at least 1 − (δ + δ +4δ) = 1 − 6δ. Hence the bound (4) transfers for πT suchthat with µπT -probability ≥ 1 − 6δ we have

Generally, weak asymptotic optimality and asymptotic optimality in mean are incomparable because the notions ofconvergence are incomparable for (bounded) random variables. First, for deterministic sequences (i.e. deterministic policies in deterministic environments), convergencein mean is equivalent to (regular) convergence, which implies convergence in Cesàro average, but not vice versa.
Second, convergence in probability (and hence convergence in mean for bounded random variables) does not
imply almost sure convergence of Cesàro averages [Sto13,
Sec. 14.18]. We leave open the question whether the policy
πT is weakly asymptotically optimal.
3.3

STRONG ASYMPTOTIC OPTIMALITY

Strong asymptotic optimality is known to be impossiblefor deterministic policies [LH11, Thm. 8.1], but whether
it is possible for stochastic policies is an open question.
However, we show that Thompson sampling is not strongly
asymptotically optimal.
Example 6 (Thompson Sampling is not Strongly Asymptotically Optimal). Define A := {α, β}, E := {0, 1/2, 1},
and assume geometric discounting, γt := γ t for γ ∈(0, 1). Consider the following class of environments M :={ν∞ , ν1 , ν2 , . . .} (transitions are labeled with action, reward):β, 12Vµ∗ (æ <t ) − VµπT (æ <t ) < 6β.
Therefore µπT [Vµ∗ (æ <t ) − VµπT (æ <t ) ≥ 6β] < 6δ andwith δ → 0 we get that Vµ∗ (æ <t ) − VµπT (æ <t ) → 0 as
t → ∞ in probability. The value function is bounded, thus
it also converges in mean by the dominated convergence
theorem.

β, 12
α, 0
s1

β, 0

∗, 0

ν∞

s3
β, 0

α, 0

β, 0

∗, 0
s2

s2

WEAK ASYMPTOTIC OPTIMALITY

It might appear that convergence in mean is more naturalthan the convergence of Cesàro averages of weak asymp-

s0

s0
s1

α, 0

3.2

t < k : α, 0t ≥ k : α, 0

α, 0

β, 0

s4
α, 1

νk

Environment νk works just like environment ν∞ except

that after time step k, the path to state s3 gets unlocked
and the optimal policy is to take action α twice from states0 . The class M is a class of deterministic weakly communicating MDPs (but as an MDP νk has more than 5 states).
The optimal policy in environment ν∞ is to always takeaction β, the optimal policy for environment νk is to takeaction β for t < k and then take action β in state s1 andaction α otherwise.
Suppose the policy πT is acting in environment ν∞ . Since
it is asymptotically optimal in the class M, it has to takeactions αα from s0 infinitely often: for t < k environmentνk is indistinguishable from ν∞ , so the posterior for νk islarger or equal to the prior. Hence there is always a constantchance of sampling νk until taking actions αα, at which
point all environments νk for k ≤ t become falsified.
If the policy πT decides to explore and take the first action
α, it will be in state s1 . Let æ <t denote the current history.
Then the ν∞ -optimal action is β and


γ
1
1
Vν∗∞ (æ <t ) = (1 − γ) 0 + γ + γ 2 + . . . = .
2
2
2
The next action taken by πT is α since any optimal policy
for any sampled environment that takes action α once, takesthat action again (and we are following that policy for anεt -effective horizon). Hence


γ2
1
1
Vνπ∞T (æ <t ) ≤ (1−γ) 0 + 0 + γ 2 + γ 3 + . . . =.
2
2
2
Therefore Vν∗∞ − Vνπ∞T ≥ (γ − γ 2 )/2 > 0. This happens
infinitely often with probability one and thus we cannot getalmost sure convergence.
♦

to having followed πν∗ from the beginning. The recoverability assumption states that switching to the optimal policy at
any time step enables the recovery of most of the value.
Note that Definition 7 demands that it becomes less costly
to recover from mistakes as time progresses. This should be
regarded as an effect of the discount function: if the (effective) horizon grows, recovery becomes easier because theoptimal policy has more time to perform a recovery. Moreover, recoverability is on the optimal policy, in contrast to
the notion of ergodicity in MDPs which demands returning
to a starting state regardless of the policy.
Remark 8 (Weakly Communicating POMDPs are Recoverable). If the effective horizon is growing, Ht (ε) → ∞ ast → ∞, then any weakly communicating finite state partially observable MDP satisfies the recoverability assumption.
Definition 9 (Regret). The regret of a policy π in environment µ is
"m #
"m #
X
X
π0
π
Rm (π, µ) := sup Eµ
rt − Eµ
rt .
π0

t=1

t=1

Note that regret is undiscounted and always nonnegative.
Moreover, the supremum is always attained by some policy (not necessarily the (Vµ -)optimal policy πµ∗ because thatpolicy uses discounting), since the space of possible different policies for the first m actions is finite since we assumed
the set of actions A and the set of percepts E to be finite.
Assumption 10 (Discount Function). Let the discountfunction γ be such that(a) γt > 0 for all t,

We expect that strong asymptotic optimality can beachieved with Thompson sampling by resampling at every
time step (with strong assumptions on the discount function).

4

REGRET

4.1

SETUP

In general environments classes worst-case regret is linear
because the agent can get caught in a trap and be unable
to recover [Hut05, Sec. 5.3.2]. To achieve sublinear regret
we need to ensure that the agent can recover from mistakes.
Formally, we make the following assumption.
Definition 7 (Recoverability). An environment ν satisfies
the recoverability assumption iffπ∗

sup Eν ν [Vν∗ (æ <t )] − Eπν [Vν∗ (æ <t )] → 0 as t → ∞.
π

Recoverability compares following the worst policy π fort − 1 time steps and then switching to the optimal policy πν∗(b) γt is monotone decreasing in t, and(c) Ht (ε) ∈ o(t) for all ε > 0.
This assumption demands that the discount function issomewhat well-behaved: the function has no oscillations,does not become 0, and the horizon is not growing too fast.
Assumption 10 is satisfied by geometric discounting: γt :=γ t > 0 (a) for some fixed constant γ ∈ (0, 1) is monotone
decreasing (b), Γt = γ t /(1 − γ), and Ht (ε) = dlogγ εe ∈o(t) (c).
The problem with geometric discounting is that it makes
the recoverability assumption very strong: since the horizon is not growing, the environment has to enable fasterrecovery as time progresses; in this case weakly communicating partially observable MDPs are not recoverable.
A choice with
H (ε) → ∞ that satisfies Assumption 10
√ √t
− t
/ t√
[Lat13, Sec. 2.3.1]. For this discountis γt := e√function Γt ≈ 2e− t , Ht (ε) ≈ − t log ε + (log ε)2 ∈o(t), and thus Ht (ε) → ∞ as t → ∞.

4.2

(m)

we have −1 ≤ dk ≤ 1 since we assumed rewards tobe bounded between 0 and 1. Because the environment µsatisfies the recoverability assumption we have

SUBLINEAR REGRETThis subsection is dedicated to the following theorem.
Theorem 11 (Sublinear Regret). If the discount function
γ satisfies Assumption 10, the environment µ ∈ M satisfies the recoverability assumption, and π is asymptotically
optimal in mean, i.e.,Eπµ Vµ∗ (æ<t ) − Vµπ (æ<t ) → 0 as t → ∞,π∗

Eµµ [Vµ∗ (æ <t )] − Eπµ [Vµ∗ (æ <t )] → 0 as t → ∞, andπ∗

sup Eµµ [Vµ∗ (æ <t )] − Eπµm [Vµ∗ (æ <t )] → 0 as t → ∞,mso we conclude that
sup Eπµ [Vµ∗ (æ <t )] − Eπµm [Vµ∗ (æ <t )] → 0then Rm (π, µ) ∈ o(m).

m

If the items in Assumption 10 are violated, Theorem 11 canfail:by the triangle inequality and thus
sup Eπµm [Vµ∗ (æ <t )] − Eπµ [Vµ∗ (æ <t )] → 0 as t → ∞. (7)m• If γt = 0 for some time steps t, our policy does notcare about those time steps and might take actions thathave large regret.
• Similarly if γ oscillates between high values and very
low values: our policy might take high-regret actions
in time steps with comparatively lower γ-weight.
• If the horizon grows linearly, infinitely often our policy might spend some constant fraction of the current
effective horizon exploring, which incurs a cost that isa constant fraction of the total regret so far.

By assumption the policy π is asymptotically optimal inmean, so we haveEπµ [Vµ∗ (æ <t )] − Eπµ [Vµπ (æ <t )] → 0 as t → ∞,and with (7) this combines to
sup Eπµm [Vµ∗ (æ <t )] − Eπµ [Vµπ (æ <t )] → 0 as t → ∞.
m

From Vµ∗ (æ <t ) ≥ Vµπm (æ <t ) we get


π
π
πm
πm
lim sup sup Eµ [Vµ (æ <t )] − Eµ [Vµ (æ <t )] ≤ 0.
t→∞

To prove Theorem 11, we apply the following technicallemma.
Lemma 12 (Value and Regret). Let ε > 0 and assume thediscount function γ satisfies Assumption 10. Let (dt )t∈N be
a sequence of numbers with |dt | ≤ 1 for all t. If there is atime step t0 with∞

1 X
γk dk < ε ∀t ≥ t0
Γt

m

(8)
For π 0 ∈ {π, π1 , π2 , . . .} we have
"∞
##
"
X
0
0
0
0
1
Eπµ [Vµπ (æ <t )] = EπµEπγk rk æ <t
Γt µ
k=t
#
"
∞
1 X
π0
γk rk
= Eµ
Γt
k=t

(5)
=

k=t

∞
1 X

Γt

then

0

γk Eπµ [rk ],k=t

so from (6) and (8) we get

m
X

1+ε
dt ≤ t0 + ε(m − t0 + 1) +Hm (ε)
1−ε
t=1

∞

t→∞

Proof. This proof essentially follows the proof of [Hut06,
Thm. 17]; see Appendix B.
Proof of Theorem 11. Let (πm )m∈N denote any sequenceof policies, such as a sequence of policies that attain thesupremum in the definition of regret. We want to show that
"m #
"m #
X
X
πm
π
Eµ
rt − Eµrt ∈ o(m).
t=1

t=1

For
(m)
dk := Eπµm [rk ] − Eπµ [rk ]1 X(m)γk dk ≤ 0.
Γmt

lim sup sup

(6)

k=t

Let ε > 0 and choose t0 independent of m and largeP∞(m)enough such that supm k=t γk dk /Γt < ε for all t ≥t0 . Now we let m ∈ N be given and apply Lemma 12 toget
Pm (m)dRm (π, µ)= k=1 kmm
1+εHm (ε)
t0 + ε(m − t0 + 1) + 1−ε≤.
mSince Ht (ε) ∈ o(t) according to Assumption 10c we get
lim supm→∞ Rm (π, µ)/m ≤ 0.

Example 13 (Converse of Theorem 11 is False). Let µ
be a two-armed Bernoulli bandit with means 0 and 1 andsuppose we are using geometric discounting with discountfactor γ ∈ [0, 1). This environment is recoverable. If ourpolicy π pulls the suboptimal arm exactly on time steps
1, 2, 4, 8, 16, . . ., regret will be logarithmic. However, ontime steps t = 2n for n ∈ N the value difference Vµ∗ − Vµπ
is deterministically at least 1 − γ > 0.
♦
4.3

IMPLICATIONS

We get the following immediate consequence.
Corollary 14 (Sublinear Regret for the Optimal Discounted Policy). If the discount function γ satisfies Assumption 10 and the environment µ satisfies the recoverability assumption, then Rm (πµ∗ , µ) ∈ o(m).
Proof. From Theorem 11 since the policy πµ∗ is (trivially)
asymptotically optimal in µ.
If the environment does not satisfy the recoverability assumption, regret may be linear even on the optimal policy:
the optimal policy maximizes discounted rewards and thisshort-sightedness might incur a tradeoff that leads to linear
regret later on if the environment does not allow recovery.
Corollary 15 (Sublinear Regret for Thompson Sampling).
If the discount function γ satisfies Assumption 10 and theenvironment µ ∈ M satisfies the recoverability assumption, then Rm (πT , µ) ∈ o(m) for the Thompson samplingpolicy πT .
Proof. From Theorem 4 and Theorem 11.

5

DISCUSSION

In this paper we introduced a reinforcement learning policy πT based on Thompson sampling for general countableenvironment classes (Algorithm 1). We proved two asymptotic statements about this policy. Theorem 4 states that πT
is asymptotically optimal in mean: the value of πT in thetrue environment converges to the optimal value. Corollary 15 states that the regret of πT is sublinear: the difference of the expected average rewards between πT and thebest informed policy converges to 0. Both statements comewithout a concrete convergence rate because of the weak
assumptions we made on the environment class.
Asymptotic optimality has to be taken with a grain of salt.
It provides no incentive to the agent to avoid traps in the environment. Once the agent gets caught in a trap, all actions
are equally bad and thus optimal: asymptotic optimality
has been achieved. Even worse, an asymptotically optimal
agent has to explore all the traps because they might contain hidden treasure. Overall, there is a dichotomy between
the asymptotic nature of asymptotic optimality and the useof discounting to prioritize the present over the future. Ideally, we would want to give finite guarantees instead, but
without additional assumptions this is likely impossible inthis general setting. Our regret bound could be a step in theright direction, even though itself asymptotic in nature.
For Bayesians asymptotic optimality means that the posterior distribution w( · | æ <t ) concentrates on environments that are indistinguishable from the true environment(but generally not on the true environment). This is why
Thompson sampling works: any optimal policy of the environment we draw from the posterior will, with higher andhigher probability, also be (almost) optimal in the true environment.
If the Bayesian mixture ξ is inside the class M (as it is thecase for the class of lower semicomputable chronologicalsemimeasures [Hut05]), then we can assign ξ a prior probability that is arbitrarily close to 1. Since the posterior ofξ is the same as the prior, Thompson sampling will act according to the Bayes-optimal policy most of the time. Thismeans the Bayes-value of Thompson sampling can be very
good; formally, Vξ∗ () − VξπT () can be made arbitrarily
small, and thus Thompson sampling can have near-optimal
Legg-Hutter intelligence [LH07].
In contrast, the Bayes-value of Thompson sampling canalso be very bad: Suppose you have a class of (n+1)-armed
bandits indexed 1, . . . , n where bandit i gives reward 1 − εon arm 1, reward 1 on arm i + 1, and reward 0 on all otherarms. For geometric discounting and ε < (1 − γ)/(2 − γ),
it is Bayes-optimal to pull arm 1 while Thompson sampling will explore on average n/2 arms until it finds the
optimal arm. The Bayes-value of Thompson sampling is1/(n − γn−1 ) in contract to (1 − ε) achieved by Bayes. Fora horizon of n, the Bayes-optimal policy suffers a regret ofεn and Thompson sampling a regret of n/2, which is muchlarger for small ε.
The exploration performed by Thompson samplingis qualitatively different from the exploration by
BayesExp [Lat13, Ch. 5]. BayesExp performs phasesof exploration in which it maximizes the expected information gain. This explores the environment classcompletely, even achieving off-policy prediction [OLH13,
Thm. 7]. In contrast, Thompson sampling only explores
on the optimal policies, and in some environment classes
this will not yield off-policy prediction. So in this sense
the exploration mechanism of Thompson sampling is more
reward-oriented than maximizing information gain.
Possible avenues of future research are providing concrete
convergence rates for specific environment classes and results for uncountable (parameterized) environment classes.
For the latter, we have to use different analysis techniques
because the true environment µ is typically assigned a priorprobability of 0 (only a positive density) but the proofs
of Lemma 5 and Theorem 4 rely on dividing by or tak-ing a minimum over prior probabilities. We also left open
whether Thompson sampling is weakly asymptotically optimal.

[Hut00]Marcus Hutter. A theory of universal artificial
intelligence based on algorithmic complexity.
Technical report, 2000. http://arxiv.
org/abs/cs.AI/0004001.

Acknowledgements[Hut02]

Marcus Hutter. Self-optimizing and Paretooptimal policies in general environments
based on Bayes-mixtures. In Computational
Learning Theory, pages 364–379. Springer,
2002.

[Hut05]

Marcus Hutter. Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability. Springer, 2005.

[Hut06]

Marcus Hutter. General discounting versus
average reward. In Algorithmic Learning Theory, pages 244–258. Springer, 2006.

[Hut09]Marcus Hutter. Discrete MDL predicts in total
variation. In Neural Information Processing
Systems, pages 817–825, 2009.

[KKM12]

Emilie Kaufmann, Nathaniel Korda, and Rémi
Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory, pages 199–213.
Springer, 2012.

[Lat13]

Tor Lattimore. Theory of General Reinforcement Learning. PhD thesis, Australian National University, 2013.

[LH07]

Shane Legg and Marcus Hutter. Universal
intelligence: A definition of machine intelligence. Minds & Machines, 17(4):391–444,
2007.

[LH11]Tor Lattimore and Marcus Hutter. Asymptotically optimal agents. In Algorithmic Learning
Theory, pages 368–382. Springer, 2011.

[LH14]Tor Lattimore and Marcus Hutter. Generaltime consistent discounting. Theoretical Computer Science, 519:140–154, 2014.

[LH15]Jan Leike and Marcus Hutter. Bad universal
priors and notions of optimality. In Conference on Learning Theory, pages 1244–1259,
2015.

Example 6 was developed jointly with Stuart Armstrong.
We thank Tom Everitt and Djallel Bouneffouf for proofreading.

REFERENCES[AG11][AJO10]

Shipra Agrawal and Navin Goyal. Analysis ofThompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, 2011.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning
Research, 11:1563–1600, 2010.

[ALL+ 09] John Asmuth, Lihong Li, Michael L Littman,
Ali Nouri, and David Wingate. A Bayesiansampling approach to exploration in reinforcement learning. In Uncertainty in Artificial Intelligence, pages 19–26, 2009.
[BB12][BD62][CL11][DFR98]Sébastien Bubeck and Cesa-Nicolò Bianchi.
Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations
and Trends in Machine Learning, 5(1):1–122,
2012.
David Blackwell and Lester Dubins. Merging
of opinions with increasing information. The
Annals of Mathematical Statistics, pages 882–
886, 1962.
Olivier Chapelle and Lihong Li. An empiricalevaluation of Thompson sampling. In Neural
Information Processing Systems, pages 2249–
2257, 2011.
Richard Dearden, Nir Friedman, and Stuart
Russell. Bayesian Q-learning. In AAAI, pages
761–768, 1998.

[Dur10]

Rick Durrett. Probability: Theory and Examples. Cambridge University Press, 4th edition,
2010.

[GM15]

Aditya Gopalan and Shie Mannor. Thompson
sampling for learning parameterized Markov
decision processes. In Conference on Learning Theory, pages 861–898, 2015.

[MKS+ 15] Volodymyr Mnih, Koray Kavukcuoglu, David
Silver, Andrei A Rusu, Joel Veness, Marc G
Bellemare, Alex Graves, Martin Riedmiller,
Andreas K Fidjeland, Georg Ostrovski, Stig
Petersen, Charles Beattie, Amir Sadik, Ioannis
Antonoglou, Helen King, Dharshan Kumaran,
Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529–
533, 2015.

[NMRO13] Phuong Nguyen, Odalric-Ambrym Maillard,Daniil Ryabko, and Ronald Ortner. Competing with an infinite set of models in reinforcement learning. In Artificial Intelligence andStatistics, pages 463–471, 2013.
[OB10]

Pedro A Ortega and Daniel A Braun. A minimum relative entropy principle for learningand acting. Journal of Artificial Intelligence
Research, pages 475–511, 2010.

[OLH13]Laurent Orseau, Tor Lattimore, and Marcus
Hutter. Universal knowledge-seeking agentsfor stochastic environments. In Algorithmic
Learning Theory, pages 158–172. Springer,
2013.

[OR14]

Ian Osband and Benjamin Van Roy. Modelbased reinforcement learning and the eluder
dimension. In Neural Information Processing
Systems, pages 1466–1474, 2014.

[Ors13]Laurent Orseau. Asymptotic non-learnabilityof universal agents with computable horizon
functions. Theoretical Computer Science,
473:149–156, 2013.

[ORvR13] Ian Osband, Dan Russo, and Benjamin van
Roy. (More) efficient reinforcement learning
via posterior sampling. In Neural Information
Processing Systems, pages 3003–3011, 2013.
[SH15]

Peter Sunehag and Marcus Hutter. Rationality,
optimism and guarantees in general reinforcement learning. Journal of Machine Learning
Research, 16:1345–1390, 2015.

[Sto13]

Jordan M Stoyanov. Counterexamples in
Probability. Courier Corporation, 3rd edition,
2013.

[Str00]Malcolm Strens. A Bayesian framework forreinforcement learning. In International Conference on Machine Learning, pages 943–950,
2000.

[Tho33]

William R Thompson. On the likelihoodthat one unknown probability exceeds another in view of the evidence of two samples.
Biometrika, pages 285–294, 1933.