Near-Bayesian Exploration in Polynomial Time

J. Zico Kolter
Andrew Y. Ng
Computer Science Department, Stanford University, CA 94305

Abstract
We consider the exploration/exploitation
problem in reinforcement learning (RL). The
Bayesian approach to model-based RL offers an elegant solution to this problem, byconsidering a distribution over possible models and acting to maximize expected reward;
unfortunately, the Bayesian solution is intractable for all but very restricted cases. In
this paper we present a simple algorithm, andprove that with high probability it is able toperform ǫ-close to the true (intractable) optimal Bayesian policy after some small (polynomial in quantities describing the system)
number of time steps. The algorithm andanalysis are motivated by the so-called PACMDP approach, and extend such results into
the setting of Bayesian RL. In this setting,
we show that we can achieve lower sample
complexity bounds than existing algorithms,
while using an exploration strategy that ismuch greedier than the (extremely cautious)
exploration of PAC-MDP algorithms.

1. Introduction
An agent acting in an unknown environment must consider the well-known exploration/exploitation tradeoff : the trade-off between maximizing rewards basedon the current knowledge of the system (exploiting)and acting so as to gain additional information about
the system (exploring). The Bayesian approach tomodel-based reinforcement learning (RL) offers a very
elegant solution to this dilemma. Under the Bayesian
approach, one maintains a distribution over possiblemodels and simply acts to maximize the expected future reward; this objective trades off very naturally
between exploration and exploitation. Unfortunately,Appearing in Proceedings of the 26 th International Conference on Machine Learning, Montreal, Canada, 2009. Copyright 2009 by the author(s)/owner(s).

kolter@cs.stanford.edu
ang@cs.stanford.edu

except for very restricted cases, computing the full
Bayesian policy is intractable. This has lead to numerous approximation methods, but, to the best of
our knowledge, there has been little work on providing any formal guarantees for such algorithms.
In this paper we present a simple, greedy approximation algorithm, and show that is is able to performnearly as well as the (intractable) optimal Bayesianpolicy after executing a “small” (polynomial is quantities describing the system) number of steps. The
algorithm and analysis are motivated by the so-called
PAC-MDP approach, typified by algorithms such as
E 3 and Rmax , but extend this paradigm to the settingof Bayesian RL. We show that by considering optimality with respect to the optimal Bayesian policy, we
can both achieve lower sample complexity than existing algorithms, and use an exploration approach thatis far greedier than the (extremely cautious) exploration required by any PAC-MDP algorithm. Indeed,
our analysis also shows that both our greedy algorithm
and the true Bayesian policy are not PAC-MDP.
The remainder of the paper is organized as follows.
In Section 2 we describe our setting formally and review the Bayesian and PAC-MDP approaches to exploration. In Section 3 we present our greedy approximation algorithm, and then state and discuss the theoretical guarantees for this method. In Section 4 weprove these results, present brief simulation results in
Section 5 and conclude in Section 6.

2. Preliminaries
A Markov Decision Process (MDP) is a tuple{S, A, P, R, H} where S is a set of states, A is a setof actions, P : S × A × S → R+ is a state transition probability function, R : S × A → [0, 1] is a(bounded) reward function, and H is a time horizon.1
We consider an agent interacting with an MDP via
1
We use the finite horizon setting for simplicity, but all
results presented here easily extend to the case of infinite
horizon discounted rewards.

Near-Bayesian Exploration in Polynomial Timea single continuous thread of experience, and we assume that the transition probabilities P are unknown
to the agent. For simplicity of notation, we will assume
that the reward is known, but this does not sacrificegenerality, since an MDP with unknown (bounded) rewards and unknown transitions can be represented as
an MDP with known rewards and unknown transitions
by adding additional states to the system. In this work
we will focus on the case of discrete states and actions.
A policy π is a mapping from states to actions. The
value of a policy for a given state is defined as theπsumhPof rewards over the nexti H time steps VH (s) =H
E
The value function
t=1 R(st , π(s))|s1 = s, π .
can also be written in terms of Bellman’s equationXπ
P (s′ |s, a)VH−1(s′ ).
VHπ (s) = R(s, π(s)) +s′Finally, when the transitions of the MDP are known,
we can find the optimal policy π ⋆ and optimal valuefunction V ⋆ by solving Bellman’s optimality equation
)
(
X
′
⋆
′
⋆
P (s |s, a)VH−1 (s )VH (s) = max R(s, a) +as′where π ⋆ (s) is simply the action a that maximizes theright hand side; we can apply classical algorithms such
as Value Iteration or Policy Iteration to find a solution
to this equation (Putterman, 2005).
2.1. Bayesian Reinforcement Learning
Of course, in the setting we consider, the transitionsof the MDP are not known, so we must adopt different methods. The Bayesian approach to model-based
RL, which has its roots in the topic of Dual Control(Fel’dbaum, 1961; Filatov & Unbehauen, 2004), explicitly represents the uncertainty over MDPs by maintaining a belief state b. Since we are concerned withthe setting of discrete states and actions, a natural
means of representing the belief is to let b consist of aset of Dirichlet distributions that describe our uncertainty over the state transitionsb = {α(s, a, s′ )},P (s′ |b, s, a) =α(s, a, s′ )α0 (s, a)P′
where α0 (s, a) =s′ α(s, a, s ). In this setting, the“state” now consists of both the system state and thebelief state; policies and value functions now dependon both these elements. The value of a policy π for abelief and state is again given by Bellman’s equationZπ
VHπ (b, s) = R(s, a) +P (b′ , s′ |b, s, a)VH−1(b′ , s′ )b′ ,s′= R(s, a) +Z

b′ ,s′= R(s, a) +Xs′P (b′ |s′ , b, s, a)π(b′ , s′ )P (s′ |b, s, a)VH−1π
P (s′ |b, s, a)VH−1(b′ , s′ )where a = π(s, b) and where on the third line the beliefb′ is equal to b except that we increment α(s, a, s′ ).
The simplified form on this third line results from thefact that P (b′ |s′ , b, s, a) is deterministic: if we are instate s, take action a, and end up in state s′ , then weknow how to update b (by incrementing α(s, a, s′ ), as
described above). This allows us to remove the integral
over b′ , and since the states are discrete we only needto sum over s′ .
We can also use the same logic to derive a Bayesianversion of Bellman’s optimality equation, which gives
us the optimal Bayesian value function and policy
)
(
X
′
⋆
′ ′
⋆
P (s |b, s, a)VH−1 (b , s )VH (b, s) = max R(s, a) +as′

and where the optimal Bayesian policy π ⋆ (b, s) is justthe action that maximizes the right hand side. Since
this Bayesian policy plays a crucial role in the remainder of this paper, it is worth understanding the intuition behind this equation. The optimal Bayesianpolicy chooses actions based not only on how they willaffect the next state of the system, but also based on
how they will affect the next belief state; and, since
a better knowledge of the MDP will typically lead togreater future reward, the Bayesian policy will very
naturally trade off between exploring the system togain more knowledge, and exploiting its current knowledge of the system.
Unfortunately, while the Bayesian approach provides
a very elegant solution to the exploration/exploitation
problem, it is typically not possible to compute theBayesian policy exactly. Since the dimension of the belief state grows polynomially in the number of states
and actions, computing the Bayesian value function
using value iteration or other methods is typically not
tractable.2 This has lead to numerous methods thatapproximate the Bayesian exploration policy (Dearden
et al., 1999; Strens, 2000; Wang et al., 2005; Poupart
et al., 2006), typically by computing an approximation
to the optimal value function, either by sampling orother methods. However, little is known about these2
One exception, where the Bayesian approach is
tractable, is the domain of a k-armed bandit (i.e., an MDP
with one state and k actions, where the rewards are unknown). In this case, the Bayesian approach leads to thewell-known Gittins indices (Gittins, 1989). However, theapproach does not scale analytically to multi-state MDPs.

Near-Bayesian Exploration in Polynomial Timealgorithms from a theoretical perspective, and it is unclear what (if any) formal guarantees can be made forsuch approaches.
2.2. PAC-MDP Reinforcement Learning
An alternative approach to exploration in RL is the socalled PAC-MDP approach, exemplified by algorithms
such as E 3 , Rmax , and others (Kearns & Singh, 2002;
Brafman & Tennenholtz, 2002; Kakade, 2003; Strehl& Littman, 2008a). Such algorithms also address the
exploration/exploitation problem, but do so in a different manner. The algorithms are based on the following intuition: if an agent has observed a certain
state-action pair enough times, then we can use large
deviation inequalities, such as the Hoeffding bound,to ensure that the true dynamics are close to the empirical estimates. On the other hand, if we have notobserved a state-action pair enough times, then we assume it has very high value; this will drive the agent
to try out state-action pairs that we haven’t observed
enough times, until eventually we have a suitably accurate model of the system — this general techniqueis known as optimism in the face of uncertainty.
Although the precise formulation of the learning guarantees vary from algorithm to algorithm, using thesestrategies, one can prove theoretical guarantees of thefollowing form, or similar: with high probability, thealgorithm performs near optimally for all but a “small”
number of time steps — where “small” here means
polynomial is various quantities describing the MDP.
Slightly more formally, if At denotes the policy followed by the algorithm at time t, then with probability
greater than 1 − δ,
V At (st ) ≥ V ⋆ (st ) − ǫ

for all but m = O(poly(|S|, |A|, H, 1/ǫ, 1/δ)) time
steps. This statement does not indicate when thesesuboptimal steps will occur — the algorithm could
act near-optimally for a long period of time before
returning to sub-optimal behavior for some numberof steps — which allows us to avoid issues of mixing times or ergodicity of the MDP; this precise formulation is due to Kakade (2003). Many variations
and extensions of these results exist: to the case of
metric MDPs (Kakade et al., 2003), factored MDPs
(Kearns & Koller, 1999) to continuous linear (in statefeatures) domains (Strehl & Littman, 2008b), to a certain class of switching linear systems (Brunskill et al.,2008), and others. However, the overall intuition behind these approaches is similar: in order to perform
well, we want to explore enough that we learn an accurate model of the system.3 While this results in very3

A slightly different approach is taken by Strehl et al.

powerful guarantees, the algorithms typically requirea very large amount of exploration in practice. This
contrasts to the Bayesian approach, were we just wantto obtain high expected reward over some finite horizon (or alternatively, an infinite discounted horizon).
Intuitively, we might then expect that the Bayesian
approach could act in a greedier fashion than the PACMDP approaches, and we will confirm and formalize
this intuition in the next section. Furthermore, many
issues that present challenges in the PAC-MDP framework, such as incorporating prior knowledge or dealing
with correlated transitions, seemingly can be handledvery naturally in the Bayesian framework.

3. A Greedy Approximation Algorithm
and Theoretical Results
From the discussion above, it should be apparent thatboth the Bayesian and PAC-MDP approaches have advantages and drawbacks, and in this section we present
an algorithm and analysis that combines elements fromboth frameworks. In particular, we present a simple
greedy algorithm that we show to perform “nearly aswell” as the full Bayesian policy, in a sense that wewill formalize shortly; this is a PAC-MDP-type result, but we consider optimality with respect to theBayesian policy for a given belief state, rather thanthe optimal policy for some fixed MDP. As we willshow, this alternative definition of optimality allows us
to both achieve lower sample complexity than existing
PAC-MDP algorithms and use a greedier exploration
method.
The algorithm we propose is itself very straightforward
and similar to many previously proposed exploration
heuristics. We call the algorithm Bayesian Exploration
Bonus (BEB), since it chooses actions according to
the current mean estimate of the state transitions plus
an additional reward bonus for state-action pairs thathave been observed relatively little. Specifically, theBEB algorithm, at each time step, chooses actions
greedily with respect to the value functionβ⋆ṼH (b, s) = max R(s, a) +a
1 + α0 (s, a)
) (1)
X
′
⋆
′
P (s |b, s, a)ṼH−1 (b, s )+s′where β is a parameter of the algorithm that we will
discuss shortly. In other words, the algorithm acts
by solving the an MDP using the mean of the cur(2006), where they do not build an explicit model of thesystem. However, the overall idea is the same, only here
they want to explore enough until they obtain an accurate
estimate of the state-action value function.

Near-Bayesian Exploration in Polynomial Timerent belief state for the transition probabilities, andan additional exploration bonus of β/(1 + α0 (s, a)) at
each state. Note that the belief b is not updated inthis equation, meaning we can solve the equation using
the standard Value Iteration or Policy Iteration algorithms. To simplify the analysis that follows, we also
take a common approach and cease updating the belief
states after a certain number of observations, which wewill describe more fully below. The following theorem
gives a performance guarantee for the BEB algorithm
for a suitably large value of β.
Theorem 1. Let At denote the policy followed by the
BEB algorithm (with β = 2H 2 ) at time t, and let st
and bt be the corresponding state and belief. Also suppose we stop updating the belief for a state-action pairwhen α0 (s, a) > 4H 3 /ǫ. Then with probability at least
1 − δ,
VHAt (bt , st ) ≥ VH⋆ (bt , st ) − ǫ— i.e., the algorithm is ǫ-close to the optimal Bayesianpolicy — for all but

|S||A|H 6|S||A|
m=O
log
ǫ2
δtime steps.
In other words, BEB acts sub-optimality (where optimality is defined in the Bayesian sense), for only apolynomial number of time steps. Like the PAC-MDP
results mentioned above, the theorem makes no claims
about when these sub-optimal steps occur, and thus
avoids issues of mixing times, etc.
In terms of the polynomial degree on the various quantities, this bound is tighter than the standard PACMDP bounds, which to the best of our knowledge havesample complexity of 2|S| |A|H 6
m = Õ
ǫ3time steps.4
Intuitively, this smaller bound results from the fact that in order to approximate theBayesian policy, we don’t need to learn the “true” dynamics of an MDP, we just need to ensure that theposterior beliefs are sufficiently peaked so that further
updates cannot lead to very much additional reward.
However, as mentioned above, the two theorems are
not directly comparable, since we define optimality
with respect to the Bayesian policy for a belief state,
whereas the standard PAC-MDP framework defines
4

The Õ(·) notation suppresses logarithmic factors. In
addition, the model-free“algorithm” of (Strehl et al., 2006)
obtains a bound of Õ
bound.

|S||A|H 8
ǫ4, also larger than our

optimality with respect to the optimal policy for somegiven MDP. Indeed, one of the chief insights of thiswork is that by considering the Bayesian definition of
optimality, we can achieve these smaller bounds.
To gain further insight into the nature of Bayesian
exploration, BEB, and the PAC-MDP approach, we
compare our method to a very similar PAC-MDP algorithm known as Model Based Interval Estimation with
Exploration Bonus (MBIE-EB) (Strehl & Littman,
2008a). Like BEB, this algorithm at each time stepsolves an MDP according to the mean estimate of
the transitions, plus an exploration bonus. However,MBIE-EB uses an exploration bonus of the formβpn(s, a)where n(s, a) denotes the number of times that thestate-action pair s, a has been observed; this contrasts
with the BEB algorithm, which has an exploration
bonus ofβ
1 + n(s, a)where here n(s, a) also
√ includes the “counts” impliedby the prior. Since 1/ n decays much slower than 1/n,
MBIE-EB consequently explores a great deal morethan the BEB algorithm. Furthermore, this is not
an artifact of the MBIE-EB algorithm alone: as we
formalize in the next theorem, any algorithm√
with an
exploration bonus that decays faster than 1/ n cannot be PAC-MDP.
Theorem 2. Let At denote the policy followed analgorithm using any (arbitrary complex) exploration
bonus that is upper bounded by
βn(s, a)pfor some constant β and p > 1/2. Then there exists
some MDP M and ǫ0 (β, p), such that with probability
greater than δ0 = 0.15,
VHAt (st ) < VH⋆ (st ) − ǫ0will hold for an unbounded number of time steps.
In other words, the BEB algorithm (and Bayesian exploration itself), are not PAC-MDP, and may in fact
never find the optimal policy for some given MDP.
This result is fairly intuitive: since the Bayesian algorithms are trying to maximize the reward over somefinite horizon, there would be no benefit to excessive
exploration if it cannot help over this horizon time.
To summarize, by considering optimality with respect
to the Bayesian policy, we can obtain algorithms with

Near-Bayesian Exploration in Polynomial Timelower sample complexity and greedier exploration policies than PAC-MDP approaches. Although the resulting algorithms may fail to find the optimal policy forcertain MDPs, they are still close to optimal in theBayesian sense.

4. Proofs of the Main Results
Before presenting the proofs in this section, we want
to briefly describe their intuition. Due to space constraints, the proofs of the technical lemmas are deferred to the appendix, available in the full version of
the paper (Kolter & Ng, 2009). The key condition thatallows us to prove that BEB quickly performs ǫ-close
to the Bayesian policy is that at every time step, BEB
is optimistic with respect to the Bayesian Policy, andthis optimism decays to zero given enough samples —that is, BEB acts according to an internal model thatalways overestimates the values of state-action pairs,
but which approaches the true Bayesian value estimate
at a rate of O(1/n(s, a)). The O(1/n) term itself arises
from the L1 divergence between particular Dirichlet
distributions.
Given these results, Theorem 1 follows by adapting
standard arguments from previous PAC-MDP results.
In particular, we define the “known” state-action pairs
to be all those state-action pairs that have been observed more than some number of times and use theabove insights to show, similar to the PAC-MDP
proofs, that VHAt (b, s) is close to the value of acting
according to the optimal Bayesian policy, assuming
the probability of leaving the known state-action set
is small. Finally, we use the Hoeffding bound to showthat this “escape probability” can be large only for apolynomial number of steps.
To prove Theorem 2, we use Slud’s inequality (Slud,1977) to show that any algorithm with exploration rate
O(1/np ) for p > 1/2 may not be optimistic with respect to the optimal policy for a given MDP. The domain to consider here is a simple two-armed bandit,
where one of the arms results in a random Bernoulli
payoff, and the other results in a fixed known payoffwith slightly lower mean value; we can show that withsignificant probability, any such exploration bonus algorithm may prefer the suboptimal arm at some point,
resulting in a policy that is never near-optimal.
4.1. Proof of Theorem 1
We begin with a series of lemmas used in the proof.
The first lemma states that if one has a sufficient number of counts for a Dirichlet distribution, then incrementing one of the counts won’t change the probabilities very much. The proof just involves algebraic

manipulation.
Lemma 3. Consider two Dirichlet distributions withparameters α, α′ ∈ Rk . Further, suppose αi′ = αi for
all i, except αj′ = αj + 1. ThenXi

P (xi |α) − P (xi |α′ ) ≤2.
1 + α0

Next we use this lemma to show that if we solve the
MDP using the current mean of the belief state, with2
an additional exploration bonus of 1+α2H, this will
0 (s,a)lead to a value function that is optimistic with respect
to the Bayesian policy. The proof involves showingthat the potential “benefit” of the true Bayesian policy (i.e., how much extra reward we could obtain by
updating the beliefs), is upper bounded by the exploration bonus of BEB. The proof is deferred due tospace constraints, but since this result is the key toproving Theorem 1, this lemma is one of the key technical results of the paper.
Lemma 4. Let ṼH⋆ (b, s) be the value function used by
BEB, defined as in (1), with β = 2H 2 ; that is, it is
the optimal value function for the mean MDP of beliefb, plus the additional reward term. Then for all s,ṼH⋆ (b, s) ≥ VH⋆ (b, s).
Our final lemma is a trivial modification of the“Induced Inequality” used by previous PAC-MDP
bounds, which extends this inequality to the Bayesiansetting. The lemma states that if we execute a policy
using two different rewards and belief states R, b andR′ , b′ , where b = b′ and R = R′ on a “known” setof state-action pairs K, then following a policy π willobtain similar rewards for both belief states, provided
the probability of escaping from K is small. The proof
mirrors that in (Strehl & Littman, 2008a).
Lemma 5. Let b, R and b′ , R′ be two belief states overtransition probabilities and reward functions that are
identical on some set of state-action pairs K — i.e.,αb (s, a, s′ ) = αb′ (s, a, s′ ) and R(s, a) = R′ (s, a) for alls, a ∈ K. Let AK be the probability that a state-action
pair not in K is generated when starting from state s
and following a policy π for H steps. Assuming the
rewards R′ are bounded in [0, Rmax ] then,VHπ (R, b, s) ≥ VHπ (R′ , b′ , s) − HRmax P (AK )where we now make explicit the dependence of the valuefunction on the reward.
We are now ready to prove Theorem 1.
Proof. (of Theorem 1) Define R̃ as the reward functionused by the BEB algorithm (i.e., the reward plus theNear-Bayesian Exploration in Polynomial Time

exploration bonus). Let K be the set of all states thathave posterior counts α0 (s, a) ≥ m ≡ 4H 3 /ǫ. Let R′
be a reward function equal to R on K and equal to R̃
elsewhere. Furthermore, let π̃ be the policy followed by
the BEB at time t— i.e., the greedy policy with respect
to the current belief bt and the reward R̃. Letting AK
be the event that π̃ escapes from K when starting inand acting for H steps. Then
VHAt (R, bt , st ) ≥ VHπ̃ (R′ , bt , st ) − H 2 P (AK )(2)

by Lemma 5 where we note that we can limit
the “exploration bonus” to H (i.e., use a bonus of2min{ 1+α2H, H}), and still maintain optimism, and
0 (s,a)by noticing that At equals π̃ unless AK occurs.
In addition, note that since R′ and R̃ differ by at most2H 2 /m = ǫ/(2H) at each state,|VHπ̃ (R′ , bt , st ) − VHπ̃ (R̃, bt , st )| ≤

ǫ
.
2

(3)

Finally, we consider two cases. First, suppose that
P (AK ) > ǫ/(2H 2 ). By the Hoeffding inequality, withprobability 1 − δ this will occur no more thanm|S||A|H 3|S||A|H 6O=Oǫǫ2times before all the states become “known”. Now suppose P (AK ) ≤ ǫ/(2H 2 ). Then
VHAt (R, bt , st )≥ VHπ̃ (R′ , bt , st ) − H 2 P (Ak )ǫ≥ VHπ̃ (R′ , bt , st ) −2≥ VHπ̃ (R̃, bt , st ) − ǫ= ṼH⋆ (R̃, bt , st ) − ǫ≥ VH⋆ (R, bt , st ) − ǫi.e., the policy is ǫ-optimal. In this derivation the firstline follows from (2), the second line follows from ourassumption that P (AK ) ≤ ǫ/(2H 2 ), the third line follows from (3), the fourth line follows from the fact thatπ̃ is precisely the optimal policy for R̃, bt , and the lastline follows from Lemma 4.
4.2. Proof of Theorem 2
We make use of the following inequality, due to Slud(1977), which gives a lower bound on the probabilityof large deviations from the mean in a binomial distribution.
Lemma 6. (Slud’s inequality) Let X1 , . . . , Xn be i.i.d.
Bernoulli random variables, with mean µ ≥ 3/4. Then
!
!
√
n
1X
ǫ n
P µ−
Xi > ǫ ≥ 1 − Φ pn i=1µ(1 − µ)where Φ(x) is the cumulative distribution function ofa standard Gaussian random variable
Z x
1 −x2
√ e 2 dx.
Φ(x) =
2π−∞
Using this lemma, we now prove the theorem.
Proof. (of Theorem 2) As mentioned in the preceding text, the scenario we consider for this proof is a
two-armed bandit: action a1 gives a Bernoulli random
reward, with true payoff probability (unknown to thealgorithm) of 3/4; action a2 gives a fixed (known) payoff of 3/4−ǫ0 (we will define ǫ0 shortly). Therefore, theoptimal policy is to always pick action a1 . Since thisis a setting with only one state (and therefore known
transition dynamics) but unknown rewards, later inthe proof we will transform this domain into one withunknown transitions but known rewards; however, thebandit formulation is more intuitive for the time being.
Since the reward for action a2 is known, the only “exploratory” action in this case is a1 , and we let n denotethe number of times that the agent has chosen action
a1 , where at each trial it receives reward ri ∈ {0, 1}.
Let f (n) be an exploration bonus for some algorithm
attempting to learn this domain, and suppose it is upper bounded byβf (n) ≤ pn
for some p > 1/2. Then we can lower bound the probability that the algorithm’s estimate of the reward,
plus its exploration bonus, is pessimistic by more thanβ/np :!
nβ1Xri − f (n) ≥ p
P 3/4 −
n i=1
n
!
n
1X
2β
≥ P 3/4 −ri ≥ p
n i=1
n


8β
≥1−Φ √
3np−1/2
where the last line follows by applying Slud’s inequality. We can easily verify numerically that 1 − Φ(1) >0.15, so for 2
8β 2p−1n≥ √3
we have that with probability greater than δ0 =0.15, the algorithm is pessimistic by more than β/np .
Therefore, after this many steps, if we let
ǫ0 (β, p) = β/



8β
√
3

2
 2p−1

Near-Bayesian Exploration in Polynomial Timethen with probability at least δ0 = 0.15, action a2 will
be preferred by the algorithm over action a1 . Once thisoccurs, the algorithm will never opt to select action a1(since a2 is known, and already has no exploration
bonus), so for any ǫ ≤ ǫ0 , the algorithm will be morethan ǫ sub-optimal for an infinite number of steps.

P (s2 |s1 , a1 ) = 3/4
P (s3 |s1 , a1 ) = 1/4
P (s1 |s1 , a2 ) = 1
P (s1 |s2:3 , a1:2 ) = 1
R(s2 , a1:2 ) = 1
R(s3 , a1:2 ) = 0
R(s1 , a2 ) = 3/4 − ǫ0 .

Figure 1. Simple chain domain, consisting of five states andtwo actions. Arrows indicate transitions and rewards forthe actions, but at each time step the agent performs the
opposite action as intended with probability 0.2. The agent
always starts in state 1, and the horizon is H = 6.

0.35
Average Total Reward

Finally, we also note that we can easily transform thisdomain to an MDP with known rewards but unknown
transitions by considering a three state MDP, withtransition probabilities and rewards

5. Simulated Domain

Figure 2 shows the average total reward versus time
step for several different algorithms. These results
illustrate several points. First, the results show, assuggested by the theory, that BEB can outperform
PAC-MDP algorithms (in this case, MBIE-EB), due
to it’s greedier exploration strategy. Second, the valueof β required by Theorem 1 is typically much larger
than what is best in practice. This is a common trend
for such algorithms, so for both BEB and MBIE-EB
we evaluated a wide range of values for β and chosethe best for each (the same evaluation strategy wasused by the authors of MBIE-EB (Strehl & Littman,
2008a)). Thus, while the constant factors in the theoretical results for both BEB and MBIE-EB are less important from a practical standpoint, the√ rates impliedby these results — i.e., the 1/n vs. 1/ n exploration
rates — do result in empirical differences. Finally, forthis domain, the possibility that BEB converges to a
sub-optimal policy is not a large concern. This is to
be expected, as Theorem 2 analyzes a fairly extreme
setting, and indeed implies only relatively little suboptimality, even in the worse case.

0.25
BEB β=2.5
MBIE-EB β=2.5
Optimal policy
BEB β=2H2
Exploit only (β=0)

0.2

0.15
0

1000

2000
3000
Time Step

4000

5000

Figure 2. Performance versus time for different algorithms
on the chain domain, averaged over 500 trials and shownwith 95% confidence intervals.

0.35
Average Total Reward

In this section we present empirical results for BEB
and other algorithms on a simple chain domain fromthe Bayesian exploration literature (Strens, 2000;
Poupart et al., 2006), shown in Figure 1. We stressthat the results here are not intended as a rigorous
evaluation of the different methods, since the domain
is extremely small-scale. Nonetheless, the results illustrate that the characteristics suggested by the theory do manifest themselves in practice, at least in thissmall-scale setting.

0.3

0.3

0.25
Small Prior, α0 = 0.001
Uniform Prior, α0 = |S|
Uniform Prior, α0 = 5|S|
Informative Prior, α0 = |S|
Informative Prior, α0 = 5|S|

0.2

0.15
0

1000

2000

3000

4000

5000

Time Step

Figure 3. Performance versus time for BEB with different
priors on the chain domain, averaged over 500 trials andshown with 95% confidence intervals.

We also evaluated the significance of the prior distribution on BEB. In Figure 3 we show performance for
BEB with a very small prior, for uniform priors ofvarying strength, and for informative priors consistingof the true transition probabilities. As can be seen,
BEB is fairly insensitive to either small priors, but canbe negatively impacted by a large misspecified prior.
These results are quite intuitive, as such as prior will
greatly decrease the exploration bonus, while providing a poor model of the environment.

Near-Bayesian Exploration in Polynomial Time

6. Conclusion
In this paper we presented a novel algorithm andmode of analysis that allows an agent acting in an
MDP to perform ǫ-close to the (intractable) optimal
Bayesian policy after a polynomial number of time
steps. We bring PAC-MDP-type results to the setting of Bayesian RL, and we show that by doing so,
we can both obtain lower sample complexity bounds,
and use exploration techniques that are greedier thanthose required by any PAC-MDP algorithm.
Looking forward, the same mode of analysis that we
use to derive the bounds in this paper (which involves
bounding divergences between updates of the belief
distributions) can also be applied to more structured
domains, such as finite MDPs with correlated transitions or continuous state MDPs with smooth dynamics; it will be interesting to see how the resulting algorithms perform in such domains. An alternative meansof analyzing the efficiency of reinforcement learning algorithms is the notion of regret in infinite-horizon settings (Auer & Ortner, 2007), and it remains an open
question whether the ideas we present here can be extended to this infinite-horizon case. Finally, very recently Asmuth et al. (2009) have independently developed an algorithm that also combines Bayesian and
PAC-MDP approaches. The actual approach is quite
different — they use Bayesian sampling to achieve a
PAC-MDP algorithm — but it would be very interesting to compare the algorithms.

Acknowledgments
This work was supported by the DARPA Learning Locomotion program under contract number FA8650-05C-7261. We thank the anonymous reviews and Lihong
Li for helpful comments. Zico Kolter is supported by
an NSF Graduate Research Fellowship.

References
Asmuth, J., Li, L., Littman, M. L., Nouri, A., & Wingate,
D. (2009). A Bayesian sampling approach to explorationin reinforcement learning. (Preprint).
Auer, P., & Ortner, R. (2007). Logarithmic online regretbounds for undiscounted reinforcement learning. Neural
Information Processing Systems.

Dearden, R., Friedman, N., & Andre, D. (1999). Model
based Bayesian exploration. Proceedings of the International Conference on Uncertainty in Artificial Intelligence.
Fel’dbaum, A. A. (1961). Dual control theory, parts I–
IV. Automation and Remote Control, 21 874–880, 21
1033–1039, 22 1–12, 22 109–121.
Filatov, N., & Unbehauen, H. (2004). Adaptive dual control: Theory and applications. Springer.
Gittins, J. C. (1989). Multiamred bandit allocation indices.
Wiley.
Kakade, S., Kearns, M., & Langford, J. (2003). Exploration
in metric state spaces. Proceedings of the International
Conference on Machine Learning.
Kakade, S. M. (2003). On the sample complexity of reinforcement learning. Doctoral dissertation, Gatsby Computational Neuroscience Unit, University College, London.
Kearns, M., & Koller, D. (1999). Efficient reinforcement
learning in factored MDPs. Proceedings of the International Joint Conference on Artificial Intelligence.
Kearns, M., & Singh, S. (2002). Near-optimal reinforcement learning in polynomial time. Machine Learning,
49.
Kolter, J. Z., & Ng, A. Y. (2009). Near-Bayesian exploration in polynomial time (full version). Available at
http://ai.stanford.edu/˜kolter.
Poupart, P., Vlassis, N., Hoey, J., & Regan, K. (2006).
An analytic solution to discrete Bayesian reinforcement
learning. Proceedings of the International Conference on
Machine Learning.
Putterman, M. L. (2005). Markov decision processes: Discrete stochastic dynamic programming. Wiley.
Slud, E. V. (1977). Distribution inequalities for the binomial law. The Annals of Probability, 5, 404–412.
Strehl, A. L., Li, L., Wiewiora, E., Langford, J., &Littman, M. L. (2006). Pac model-free reinforcement
learning. Proceedings of the International Conference
on Machine Learning.
Strehl, A. L., & Littman, M. L. (2008a). An analysis ofmodel-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74,
1209–1331.
Strehl, A. L., & Littman, M. L. (2008b). Online linear
regression and its application to model-based reinforcement learning. Neural Information Processing Systems.

Brafman, R. I., & Tennenholtz, M. (2002). R-MAX –a general polynomial time algorithm for near-optimal
reinforcement learning. Journal of Machine Learning
Research, 3, 213–231.

Strens, M. J. (2000). A Bayesian framework for reinforcement learning. Proceedings of the International Conference on Machine Learning.

Brunskill, E., Leffler, B. R., Li, L., Littman, M. L., & Roy,N. (2008). CORL: A continuous-state offset-dynamics
reinforcement learner. Proceedings of the International
Conference on Uncertainty in Artificial Intelligence.

Wang, T., Lizotte, D., Bowling, M., & Schuurmans, D.
(2005). Bayesian sparse sampling for on-line reward optimization. Proceedings of the International Conference
on Machine Learning.

Near-Bayesian Exploration in Polynomial TimeThe first line just substitutes the definitions of ṼH⋆
and VH⋆ . In the second line we use the fact that

A. Technical Proofs
A.1. Proof of Lemma 3
Proof. Using definition of the Dirichlet distribution,

max f (x) − max g(x) ≥ min (f (x) − g(x)) .
xZ

P (xi |α) =where α0 ≡Xi=

P (xi |π)p(π|α)dπ =

αi
α0

′
i αi . By the assumptions on α and α ,

i6=j

=

X

≤

X

i6=j

i

αi
αi
−
α0
α0 + 1+

αj + 1 αj−
α0 + 1 α0



s′

(

max R(s, a) +
a

≥ min

(

≥ min



a

2H
+
1 + α0 (s, a)
)

X
s′

−

≤
)

⋆
P (s |bt , s, a)VH−1(bt+1 , s′ )
′

X
2H 2
⋆
P (s′ |b, s, a)ṼH−1(b, s′ ) −+1 + α0 (s, a)
′
s
)
X
′
⋆
′
P (s |bt , s, a)VH−1 (bt+1 , s )
s′

a

X
≤

⋆
P (s |b, s, a)ṼH−1(b, s′ )Xx|p(x) − q(x)|g(x),which lets us remove these terms. In greater detail,using the triangle inequality, Lemma 3, and the factthat t ≤ H

s′

2

′

p(x)(f (x) − g(x)) −s

Proof. Consider some belief and state b and s, and let
bt be the new belief formed by updating b after takingt ≤ H steps. ThenX

xq(x)g(x)xX
2H 2
P (s|b, s, a) − P (s′ |bt , s, a)≥ (H − 1)
1 + α0 (s, a)′

A.2. Proof of Lemma 4

a

X

X

⋆
(b, s) ≤ (H − 1) for any b and s.
and note that VH−1
In the fourth line we apply Lemma 3 to show that

α0
2
αi
+
=
.
2
2
α0 + α0
α0 + α0
1 + α0= max R(s, a) +p(x)f (x) −≥αiα0 − αj+2
α0 + α0
α0 + α02ṼH⋆ (b, s) − VH⋆ (bt , s)XxP (xi |α) − P (xi |α′ )xIn the third line we use the fact that

P

X

x

2H 2
−
1 + α0 (s, a)X(H − 1)
P (s|b, s, a) − P (s′ |bt , s, a) +P (s′ |bt , s, a) − P (s′ |b, s, a)

t X
X
i=1

s′

P (s′ |bi , s, a) − P (s′ |bi−1 , s, a)

t
X

2
2H
≤
.
1
+
α
(s,
a)
+
i
1
+
α
0
0 (s, a)i=1

Since s is arbitrary in the above derivation, we havethat for any t ≤ H,nomin ṼH⋆ (b, s) − VH⋆ (bt , s)
s
n
o
⋆
⋆
≥ min ṼH−1(b, s) − VH−1
(bt+1 , s)sApplying this equation repeatedly proves the desired
lemma.

s′

X
s′

≥ min
a

(
X
s′




⋆
⋆
P (s′ |b, s, a) ṼH−1(b, s) − VH−1
(bt , s)⋆⋆P (s′ |b, s, a) ṼH−1(b, s) − VH−1
(bt , s)no⋆⋆≥ min ṼH−1(b, s) − VH−1
(bt+1 , s) .
s))

A.3. Proof of Lemma 5
Proof. Consider a sequence of beliefs, states, actions,and rewards of length t, pt = s1 a1 r1 , . . . , st , at , rt . Let
P (pt ) be the probability of this sequence under belief
b with reward function R when starting in state s, and
let P ′ (pt ) be the probability of the sequence under
belief b with reward function R. Let Kt be the set ofNear-Bayesian Exploration in Polynomial Timesequences where all s1 , . . . , st ∈ K Then
VHπ (R′ , b′ , s) − VHπ (R, b, s)
H X

X
=
P ′ (pt )rt (pt ) − P (pt )rt (pt )t=1 pt

=

H
X
t=1




X 

pt ∈KtX 

pt 6∈Kt

=

H
X

X 

t=1 pt 6∈Kt

≤

H X
X

t=1 pt 6∈Kt

P ′ (pt )rt (pt ) − P (pt )rt (pt ) +P ′ (pt )rt (pt ) − P (pt )rt (pt ) P ′ (pt )rt (pt ) − P (pt )rt (pt )P ′ (pt )rt (pt ) ≤ HRmax P (AK )where we can eliminate the terms for pt ∈ Kt , because R, b and R′ , b′ are identical on this set, and where
the last line follows since the rewards are bounded in[0, Rmax ].