On Thompson Sampling and Asymptotic Optimality

1 Introduction

In reinforcement learning (RL) an agent interacts with an unknown environment with the goal of maximizing rewards. Recently reinforcement learning has received a surge of interest, triggered by its success in applications such as simple video games [Mnih et al., 2015]. However, theory is lagging behind application and most theoretical analyses have 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 ergodicity and visiting every state infinitely often. Needless to say, these assumptions are satisfied only for the simplest applications. The goal of this line of work is to lift these restrictions; we consider general reinforcement learning [Hutter, 2005; Lattimore, 2013; Leike, 2016b] with the aim to understand the fundamental underlying problems in their generality. Our approach to general RL is nonparametric: we only assume that the true environment belongs to a given countable environment class. However, to provide insightful results we need to leave computational considerations aside for now.

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. We discuss two different notions of optimality: asymptotic optimality and worst-case regret.

Asymptotic optimality in the sense of Lattimore and Hutter [2011] requires that asymptotically the agent learns to act optimally, i.e., that the discounted value of the agent's policy π converges to the optimal discounted value for every environment from the environment class. Asymptotic optimality can be achieved through an exploration component on top of a Bayes-optimal agent [Lattimore, 2013, Ch. 5] or through optimism [Sunehag and Hutter, 2015].

∗This is an abriged version of Leike et al. [2016a]

Asymptotic optimality in mean is essentially a qualitative version 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 δ forever thereafter. Since our environment class can be very large and non-compact, concrete PAC/convergence rates are likely impossible.

Regret is howmany 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. Multi-armed bandits provide a (problem-independent) worst-case regret bound of Ω(√KT) where K is the number of arms [Bubeck and Bianchi, 2012]. In Markov decision processes (MDPs) the lower bound is Ω(√DSAT) where S is the number of states, A the number of actions, and D the diameter of the MDP [Auer et al., 2010]. 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 [Nguyen et al., 2013]. 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 the definition of the universal Bayesian agent AIXI [Hutter, 2000] and the proof that it satisfies various optimality guarantees [Hutter, 2002]. Recently it was revealed that these optimality notions are subjective [Leike and Hutter, 2015]: a Bayesian agent does not explore enough to lose the prior's bias, and a particularly bad prior can make the agent conform to any arbitrarily bad policy as long as this policy yields some rewards. In particular, general Bayesian agents are not asymptotically optimal [Orseau, 2013]. These negative results put the Bayesian approach to RL into question. We remedy the situation by showing that using Bayesian techniques an agent can indeed be optimal in an objective sense.

We report recent results on a strategy called Thompson sampling, posterior sampling, or the Bayesian control rule [Thompson, 1933]. This strategy samples an environment ρ from the posterior, follows the ρ-optimal policy for a while, and then repeats. We show that this policy is asymptotically optimal in mean. 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.

Thompson sampling was originally proposed by Thompson as a bandit algorithm [Thompson, 1933]. It is easy to implement and often achieves quite good results [Chapelle and Li, 2011]. In multi-armed bandits it attains optimal regret [Agrawal and Goyal, 2011; Kaufmann et al., 2012]. Thompson sampling has also been considered for MDPs: as model-free method relying on distributions over Q-functions with convergence guarantee [Dearden et al., 1998], and as a model-based algorithm without theoretical analysis [Strens, 2000]. Bayesian and frequentist regret bounds have also been established [Osband et al., 2013; Osband and Van Roy, 2014; Gopalan and Mannor, 2015]. PAC guarantees have been established for an optimistic variant of Thompson sampling for MDPs [Asmuth et al., 2009].

For general RL, Thompson sampling was first suggested by Ortega and Braun [2010] 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 the similarity of environments in the class. Our convergence results do not require these assumptions, but we rely on an (unavoidable) recoverability assumption for our regret bound.

Thompson sampling can be viewed as inference over optimal policies [Ortega and Braun, 2012]. With each environment ν ∈ M we associate an optimal policy π∗ ν . At time step t conditional on history æ<t, the posterior belief over environment ν is w(ν | æ<t). A Bayesian agent averages over all environments by maximizing reward according to the Bayesian mixture ξ(· | æ<t) = ∑ν w(ν | æ<t)ν(· | æ<t). In contrast, Thompson sampling averages over optimal policies and we get πT = ∑ν w(ν | æ<t)π∗ ν . This way no explicit reward structure is needed, only a mapping from environment ν to optimal policy π∗ ν .

Osband and van Roy [2016] show that Thompson sampling is better than optimism because of the shape of the confidence sets in tabular MDPs. However, it can be argued that this is not an inherent flaw of the strategy of optimism, but rather of the way that confidence bounds are typically calculated.

More generally, Lattimore and Szepesv´ari [2017] point out that there seems to be something fundamentally flawed about both Thompson sampling and optimism. This is exhibited in a linear bandit where the most efficient exploration strategy involves taking actions that can be confidently judged as suboptimal. Optimistic strategies refrain from taking actions they know to be suboptimal even if they are informative. Thompson sampling is similar in this respect: the posterior concentrates around the likely optimal actions, so sampling a policy that takes the suboptimal action is very unlikely. This has been a known effect in the context of partial monitoring problems [Bart´ok et al., 2014], that commonly involve information that can only be gained by taking suboptimal actions. However, in the most common theoretical frameworks for RL, multi-armed bandits and tabular MDPs, this problem does not exist and thus has gone unnoticed so far by the theoretical literature.

2 Preliminaries and Notation

In reinforcement learning, an agent interacts with an environment in cycles: at time step t the agent chooses an action at and receives a percept et = (ot, rt) consisting of an observation ot and a real-valued reward rt; the cycle then repeats for time step t + 1. A history is a sequence of actions and percepts: we use æ<t to denote a history of length t - 1. In the following we assume that rewards are bounded in [0, 1].

In contrast to most of the literature on reinforcement learning, we are agnostic towards the discounting strategy. Our goal is to maximize discounted rewards ∑∞t=1 γtrt for a fixed discount function γ : N → R with γt ≥ 0 and ∑∞t=1 γt < ∞. Geometric discounting (γt = γ t for some constant γ ∈ (0, 1)) is the most common form of discounting, although other forms can be used [Lattimore and Hutter, 2014]. The discount normalization factor is defined as Γt := ∑∞k=t γk.

An ε-effective horizon Ht(ε) is a horizon that is long enough to encompass all but a fraction ε of the discount function's mass:

An ε-effective horizon is a central quantity in online reinforcement learning, and has a similar role to an episode in the episodic setting. It is the amount of time that an agent needs to plan ahead while losing only a fraction ε of the possible value. It can be used to constrain the planning horizon to a finite number of steps regardless of the discount function used. For geometric discounting, the horizon is ⌈logγ ε⌉ [Leike, 2016b, Tab. 4.1].

A policy is a function π(a | æ<t) specifying the probability of taking action a after seeing the history æ<t. Likewise, an environment is a function ν(e | æ<tat) specifying the probability of emitting percept e after seeing the history æ<t and the action at. Together, a policy π and an environment ν generate a probability measure over histories denoted ν π . We use Eπν to denote the expectation over the history æ<t drawn from ν π .

The value of a policy π in an environment ν given history æ<t is defined as

The optimal value is defined as V ∗ ν (h) := supπ V π ν (h), and the optimal policy is π∗ ν ∈ argmaxπ V π ν .

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 [Hutter, 2005]. Let w be a prior probability distribution on M and let

Algorithm 1 Thompson sampling policy πT

Require: εt, a monotone decreasing sequence of positive reals with εt → 0 as t → ∞.

• 1: while true do
• 2: sample ρ ∼ w( · | æ<t)
• 3: follow π∗ ρ for Ht(εt) steps

denote the corresponding Bayesian mixture over the class M. After observing the history æ<t the prior w is updated to the posterior

Finally, the regret of a policy π in environment µ is how much reward the agent has lost at time step m by not having followed the optimal policy from the beginning:

Note that regret is undiscounted and always nonnegative. Moreover, the supremum is always attained by some policy, which is usually not by the (Vµ-)optimal policy π∗µ because that policy uses discounting.

3 Results

When introducing Thompson sampling for MDPs, Strens proposes following the optimal policy for one episode or "related to the number of state transitions the agent is likely to need to plan ahead" [Strens, 2000]. We follow Strens' suggestion and resample our policy at the effective horizon. The Thompson sampling policy πT is defined in Algorithm 1. It is a stochastic policy since it occasionally involves sampling from a distribution. We prove the following main result.

Theorem 1 (Thompson Sampling is Asymptotically Optimal in Mean [Leike et al., 2016a, Thm. 4]). The policy πT is asymptotically optimal in mean, i.e., for all environments µ from the countable class M,

Note that in contrast to previous results [Lattimore and Hutter, 2011] no assumptions on the discount function are required.

In general environments classes worst-case regret is linear because the agent can get caught in a trap and be unable to recover [Hutter, 2005, Sec. 5.3.2]. To achieve sublinear regret we need to ensure that the agent can recover from mistakes. We introduce the following technical assumption.

Definition 2 (Recoverability). An environment ν satisfies the recoverability assumption iff

Recoverability compares following the worst policy π for t - 1 time steps and then switching to the optimal policy π∗ ν 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.

Our notion of recoverability 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 the optimal policy has more time to perform a recovery. For growing effective horizons any weakly communicating finite state partially observable MDP is recoverable. Moreover, recovery is performed on the optimal policy, in contrast to the stronger notion of ergodicity in MDPs which demands returning to a starting state regardless of the policy.

Theorem 3 (Sublinear Regret [Leike et al., 2016a, Thm. 11]). Under suitable assumptions on the discount function, if the environment µ ∈ M satisfies the recoverability assumption, and π is asymptotically optimal in mean, then regret is sublinear: Rm(π, µ) ∈ o(m).

Together with Theorem 1 we get the following corollary.

Corollary 4 (Sublinear Regret for Thompson Sampling). Under suitable assumptions on the discount function, if the environment µ satisfies the recoverability assumption, then Rm(πT , µ) ∈ o(m) for the Thompson sampling policy πT .

The assumptions on the discount function in Theorem 3 and Corollary 4 are satisfied for geometric discounting. However, since geometric discounting has a constant horizon, it makes the recoverability assumption very strong: the environment has to enable faster recovery as time progresses; in this case weakly communicating partially observable MDPs are not recoverable. An alternative discount function choice that satisfies the aforementioned assumptions but has a growing horizon is γt := e-√t /√t [Lattimore, 2013, Sec. 2.3.1].

Our recoverability assumption is necessary: if it is not satisfied, regret may be linear even on the optimal policy: the optimal policy maximizes discounted rewards and this shortsightedness might incur a tradeoff that leads to linear regret later on if the environment does not allow for recovery.

4 Discussion

A policy is asymptotically optimal if the agent learns to act optimally in any environment from the class M. Our main result is Theorem 1, proving that Thompson sampling is asymptotically optimal in mean. Similar to BayesExp which is weakly asymptotically optimal if the effective horizon grows sublinearly [Lattimore, 2013, Ch. 5], both policies commit to exploration for several steps. This is necessary for optimality [Leike, 2016b, Ex. 5.19]:

To achieve asymptotic optimality, the agent needs to explore infinitely often for the duration of an effective horizon.

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 any trap because it could contain a hidden treasure. Concisely, with the definition of recoverability from Definition 2, we can informally state the following impossibility result for non-recoverable environment classes:

In general, either the agent gets caught in a trap or it is not asymptotically optimal.

In contrast, Corollary 4 shows Thompson sampling gets sublinear regret in recoverable environments, which implies every countable class of recoverable environments is learnable.

Note that for the notions of optimality considered here any finite initial time segment is irrelevant (optimality is a tail event): asymptotic optimality requires only convergence in the limit and sublinear regret is about the asymptotic behaviour of regret as a function of the horizon m. Hence an optimal agent can be arbitrarily lazy. Overall, there is a dichotomy between the asymptotic nature of optimality and the use of discounting to prioritize the present over the future. Ideally, we would want to give finite regret guarantees instead, but without additional assumptions this is likely impossible in this general setting.

What we presented are first and foremost theoretical results. Yet our insights from these results can help guide practical algorithms. Deep reinforcement learning (DRL) is a rapidly growing field combining general RL with deep neural networks. Yet the DRL literature has addressed partial observability and non-recoverability only sparingly, but these problems will have to be tackled eventually.

From the perspective of this paper, we also want to highlight our insights on exploration, which is still an open problem in DRL [Bellemare et al., 2016]. The exploration performed by Thompson sampling is qualitatively different from the exploration by BayesExp [Lattimore, 2013, Ch. 5]. BayesExp performs phases of exploration in which it maximizes the expected information gain. This explores the environment class completely, even achieving off-policy prediction [Orseau et al., 2013, Thm. 7]. However, off-policy prediction is too strong for reinforcement learning because it does not take the reward structure into account: it requires the agent to understand all parts of the environment, even the ones that are known to have low reward. A reward-oriented exploration strategy is information-directed sampling [Russo and Van Roy, 2014]. This bandit strategy trades off rewards with information gain about the optimal policy. However, these two quantities are measured in two different units, making the trade-off artificial. The exploration mechanism of Thompson sampling is reward-oriented and does not lead to off-policy prediction. As such, it leads to an exploration strategy that is measured on the value scale. In fact, the exploration potential proposed by Leike [2016a] is derived from Thompson sampling and measures exploration on a value scale, making it commensurable with reward.

Moreover, our results also provide the basis for new theoretical research. For example, Theorem 1 is used by Leike et al. [2016b] to prove that in an arbitrary multi-agent environment, if all players use Thompson sampling and their hypothesis class satisfies the grain of truth assumption, then they converge to a Nash equilibrium. The grain of truth assumption requires that the environment each player interacts with (the game combined with the other players) is in their hypothesis classM. However, the result is not tied to Thompson sampling; the contribution of Leike et al. is to construct a general class that satisfies the grain of truth assumption. This class can then be combined with any asymptotically optimal policy, e.g. from Lattimore and Hutter [2011]. However, the lack of additional assumptions on the discount function in Theorem 1 leads to a clean convergence theorem.

This paper only provides a brief introduction into general reinforcement learning. All proofs and further details can be found in Leike et al. [2016a]. The theory of general RL was first developed by Hutter [2000; 2005]. For a more recent introduction, in particular a longer discussion on optimality, we refer the reader to Leike [2016b]. For an empirical illustration of these and related results, see Aslanides et al. [2017] and Lamont et al. [2017].

Acknowledgements

We are grateful to Pedro Ortega for sharing his deep understanding of Thompson sampling and to Toby Ord for insightful discussions about asymptotic optimality. This work was in parts supported by ARC grant DP150104590.