PAC Bounds for Discounted MDPs

Introduction

The goal of reinforcement learning is to construct algorithms that learn to act optimally, or nearly so, in unknown environments. In this paper we restrict our attention to finite state discounted MDPs with unknown transitions. The performance of reinforcement learning algorithms in this setting can be measured in a number of ways, for instance by using regret or PAC bounds [Kakade, 2003]. We focus on the latter, which is a measure of the number of time-steps where an algorithm is not near-optimal with high probability. Many previous algorithms have been shown to be PAC with varying bounds [Kakade, 2003, Strehl and Littman, 2005, Strehl et al., 2006, 2009, Szita and Szepesvári, 2010, Auer, 2011].

We modify the Upper Confidence Reinforcement Learning (UCRL) algorithm of Auer et al. , Auer , Strehl and Littman and, under the assumption that there are at most two possible next-states for each state/action pair, prove a PAC bound of

This bound is an improvementIn this slightly restricted setting. on the previous best [Auer, 2011] and published best [Szita and Szepesvári, 2010], which are

respectively. The additional assumption is unfortunate and is probably unnecessary as discussed in Section 6.

We also present a matching (up to logarithmic factors) lower bound that is both larger and more general than the previous best given by Strehl et al. . The class of MDPs used in the counter-example satisfy the assumption used in the upper bound.

Notation

Unfortunately, we found it impossible to reduce the amount of notation and number of constants. While we have endeavoured to define everything before we use it, readers are encouraged to consult the tables of notation and constants found in the appendix.

Estimation

In the next section we will introduce the new algorithm, but first we give an intuitive introduction to the type of parameter estimation required to prove sample-complexity bounds for MDPs. The general idea is to use concentration inequalities to show the empiric estimate of a transition probability approaches the true probability exponentially fast in the number of samples gathered. There are a wide variety of concentration inequalities, each catering to a slightly different purpose. We improve on previous work by using Bernstein’s inequality, which takes variance into account (unlike Hoeffding). The following example demonstrates the need for Bernstein’s inequality when estimating the value functions of MDPs. It also gives insight into the workings of the proof in the next two sections.

Consider the Markov reward process on the right with two states where rewards are shown inside the states and transition probabilities on the edges. Note this is not an MDP because there are no actions. We are only concerned with how well the value can be approximated. Assume $p>\gamma$, $q$ arbitrarily large (but not $1$) and let $\hat{p}$ be the empiric estimate of $p$ and consider the error in our estimated value and the true value while in state $s_{0}$. One can show that

Therefore if $V-{\widehat{V}}$ is to be estimated to within $\epsilon$ accuracy, we need $|\hat{p}-p|<\epsilon(1-\gamma)^{2}$. Now suppose we bound $|\hat{p}-p|$ via a standard Hoeffding bound, then with high probability $|\hat{p}-p|\lesssim\sqrt{L/n}$ where $n$ is the number of visits to state $s_{0}$ and $L=\log(1/\delta)$. Therefore to obtain an error less than $\epsilon(1-\gamma)^{2}$ we need $n>{L\over\epsilon^{2}(1-\gamma)^{4}}$ visits to state $s_{0}$, which is already too many for a bound in terms of $1/(1-\gamma)^{3}$. If Bernstein’s inequality is used instead, then $|\hat{p}-p|\lesssim\sqrt{Lp(1-p)/n}$ and so $n>{Lp(1-p)\over\epsilon^{2}(1-\gamma)^{4}}$ is required, but Equation (1) depends on $p>\gamma$. Therefore $n>{L\over\epsilon^{2}(1-\gamma)^{3}}$ visits are sufficient. If $p<\gamma$ then Equation (1) can be improved.

Upper Confidence Reinforcement Learning Algorithm

UCRL is based on the optimism principle for solving the exploration/exploitation dilemma. It is model-based in the sense that at each time-step the algorithm acts according to a model (in this case an MDP, ${\widetilde{M}}$) chosen from a model class. The idea is to choose the smallest model class guaranteed to contain the true model with high probability and act according to the most optimistic model within this class. With a good choice of model class this guarantees a policy that biases its exploration towards unknown states that may yield good rewards while avoiding states that are known to be bad. The approach has been successful in obtaining uniform sample complexity (or regret) bounds in various domains where the exploration/exploitation problem is an issue [Lai and Robbins, 1985, Agrawal, 1995, Auer et al., 2002, Strehl and Littman, 2005, Auer and Ortner, 2007, Auer et al., 2010, Auer, 2011].

Unfortunately, to prove our new bound we needed to make an assumption about the transition probabilities of the true MDP. We do not believe this assumption is crucial, but it substantially eases the analysis by removing some dependencies in the more general problem. In Section 6 we present an approach to remove the assumption as well as some intuition into why this ought to be possible, but non-trivial.

The true unknown MDP, $M$, satisfies $p_{s,a}^{s^{\prime}}=0$ for all but two $s^{\prime}\in S$ denoted $s\!a^{\!+},s\!a^{\!-}\in S$.Note that $s\!a^{\!+}$ and $s\!a^{\!-}$ are dependent on $(s,a)$ and are known to the algorithm.

The pseudo-code of UCRL can be found below, but first we define a knownness index, $\kappa$. If $n$ is the number of times a state/action pair has been visited then $\kappa(\iota,n)$ is the knownness of that state/action pair at level $\iota$. The knownness of a state increases with the number of visits, is bounded by $|S|$ and is always a natural number. The reason for defining these now is that UCRL will only perform an update when the knownness index of some states would be changed by an update. Unfortunately, the definition below is unlikely to be very intuitive. A more thorough explanation of knownness is given in Section 5.

Note that the existence of the function ExtendedValueIteration is proven and an algorithm given by Strehl and Littman .

Upper PAC Bounds

We present two new PAC bounds. The first improves on all previous analysis, but relies on Assumption 1. The second is completely general, but gains an additional dependence on $|S|$ leading to a PAC bound in terms of $|S|^{2}$ and $1/(1-\gamma)^{3}$. This bound is worse than the previous best in terms of $|S|$, but better in terms $1/(1-\gamma)$.

Let $M$ be the true MDP satisfying Assumption 1. Let $\pi$ be the actual (non-stationary) policy of UCRL (Algorithm 1), then $V^{*}(s_{t})-V^{\pi}(s_{t})>\epsilon$ for at most

time-steps with probability at least $1-\delta$. ($U_{\operatorname{max}}$ and $E_{\operatorname{{max}}}$ are defined in Appendix D.)

Note that although $\pi_{k}$ is stationary, the global policy of UCRL is non-stationary. Despite this, we will abuse notation by allowing ourselves to write $V^{\pi}(s_{t})$, whereas really $V^{\pi}$ should depend on the entire history. Fortunately, when UCRL is not delaying, the policy $\pi$ is nearly stationary in the sense that it will be so for the next $H$ time-steps. This allows us to work almost entirely with stationary policies and so discard the cumbersome notation required for non-stationary policies.

Let $M$ be the true MDP (possibly not satisfying Assumption 1) then there exists a policy $\pi$ such that $V^{*}(s_{t})-V^{\pi}(s_{t})>\epsilon$ for at most $|S|\log^{3}|S|(E_{\operatorname{{max}}}H+U_{\operatorname{max}}H)$ time-steps with probability at least $1-\delta$.

The proof of Theorem 4 is omitted, but follows easily by converting an arbitrary MDP with $|S|$ states into a functionally equivalent MDP with $O(|S|^{2})$ states that satisfies Assumption 1. This is done by adding a tree of $2|S|$ states for each state/action pair and rescaling $\gamma$.

Proof Overview. The proof of Theorem 3 borrows components from the work of Auer et al. , Strehl and Littman and Szita and Szepesvári .

Show that the true MDP remains in the model class $\mathcal{M}_{k}$ for all $k$.

Use the optimism principle to show that if $M\in\mathcal{M}_{k}$ and $V^{*}-V^{\pi}>\epsilon$ then $|{\widetilde{V}}^{\pi_{k}}-V^{\pi_{k}}|>\epsilon/2$. This key fact shows that if $\pi$ is not nearly-optimal at some time-step $t$ then the true value and model value of $\pi_{k}$ differ and so some information is (probably) gained by following this policy.

The final component is to bound the number of time-steps when $\pi$ is not nearly-optimal.

Episodes and phases. UCRL operates in episodes, which are blocks of time-steps ending when update is called. The length of each episode is not fixed, instead, an episode ends when the knownness of a state changes. We often refer to time-step $t$ and episode $k$ and unless there is ambiguity we will not define $k$ and just assume it is the episode in which $t$ resides. A delay phase is the period of $H$ contiguous time-steps where UCRL is in the function delay, which happens immediately before an update. An exploration phase is a period of $H$ time-steps starting at $t$ where $t$ is not in a delay phase and where ${\widetilde{V}}^{\pi_{k}}(s_{t})-V^{\pi_{k}}(s_{t})\geq\epsilon/2$. Exploration phases do note overlap. More formally, the starts of exploration phases, $t_{1},t_{2},\cdots$, are defined inductively

Note there need not, and with high probability will not, be infinitely many such $t_{i}$. The exploration phases are only used in the analysis, they are not known to UCRL.

Weights and variances. We define the weightAlso called the discounted future state distribution in Kakade . of state/action pair $(s,a)$ as follows.

The active set. We will shortly see that states with small $w_{t}(s)$ cannot influence the differences in value functions. Thus we define an active set of states where $w_{t}(s)$ is not tiny. At each time-step $t$ define the active set $X_{t}$ by

Knownness. We now expand on the concept of knownness and explain its purpose. We write $n_{t}(s,a)$ for the value of $n(s,a)$ at time-step $t$ and $n_{t}(s):=n_{t}(s,\pi_{k}(s))$ where $k$ is the episode associated with time-step $t$. Let $t$ be some non-delaying time-step and suppose $s$ is active ($s\in X_{t}$). Now let $\iota_{t}(s):=\operatornamewithlimits{arg\,min}_{\iota}{w_{t}(s)>w_{\iota}}$ and note that $\iota_{t}(s)\in\mathcal{I}$. We define a partition of the active set $X_{t}$ by

The set $K_{t}({\kappa,\iota})$ represents a set of states that have comparable weights and visit counts. We will show that if $|K_{t}({\kappa,\iota})|\leq\kappa$ for all ${\kappa,\iota}$ then the values ${\widetilde{V}}$ and $V$ are reasonably close. This result forms a key stage in the proof of Theorem 3 because it shows that if $\pi$ is not nearly-optimal at time-step $t$ then there exists a $K_{t}({\kappa,\iota})$ that is quite large and where states have not been visited sufficiently. Furthermore, the weights $w_{t}(s)$ where $s\in K_{t}({\kappa,\iota})$ are large enough that some learning is expected to occur.

Analysis. The proof of Theorem 3 follows easily from three key lemmas.

The total number of updates is bounded by $U_{\operatorname{max}}:=|{S\times A}|\log{|{S\times A}|\over|{{\mathcal{K}}\times{\mathcal{I}}}|}$.

If $M\in\mathcal{M}_{k}$ and $t$ is not in a delay phase and $V^{*}(s_{t})-V^{\pi}(s_{t})>\epsilon$ then

$M\in{\mathcal{M}}_{k}$ for all $k$ with probability at least $1-\delta/2$.

The number of exploration phases is bounded by $E_{\operatorname{{max}}}$ with probability at least $1-\delta/2$.

The proofs of the lemmas are delayed while we apply them to prove Theorem 3.

Proof of Theorem 3. By Lemma 6, $M\in M_{k}$ for all $k$ with probability $1-\delta/2$. By Lemma 7 we have that the number of exploration phases is bounded by $E_{\operatorname{{max}}}$ with probability $1-\delta/2$. Now if $t$ is not in a delaying or exploration phase and $M\in{\mathcal{M}}_{k}$ then by Lemma 5, $\pi$ is nearly-optimal. Finally note that the number of updates is bounded by $U_{\operatorname{max}}$ and so the number of time-steps in delaying phases is at most $HU_{\operatorname{max}}$. Therefore UCRL is nearly-optimal for all but $HU_{\operatorname{max}}+HE_{\operatorname{{max}}}$ time-steps with probability $1-\delta$. $\blacksquare$

We now turn our attention to proving Lemmas 5, 6 and 7. Of these, only Lemma 7 presents a substantial challenge.

Proof of Lemma 5. For part 1 we note that for $\iota\in\mathcal{I}$ the knownness of a state/action pair at level $\iota$ satisfies $\kappa\in{\mathcal{K}}$. Since the knownness index for each $\iota$ is non-decreasing and an update only occurs when an index is increased, the total number of updates is bounded by $U_{\operatorname{max}}:=|{S\times A}||{{\mathcal{K}}\times{\mathcal{I}}}|$.

The proof of part 2 is closely related to the approach taken by Strehl and Littman . Recall that ${\widetilde{M}}$ is chosen optimistically by extended value iteration. This generates an MDP, ${\widetilde{M}}$, such that $V^{*}_{{\widetilde{M}}}(s)\geq V^{*}_{{\widetilde{M}}^{\prime}}(s)$ for all ${\widetilde{M}}^{\prime}\in\mathcal{M}_{k}$. Since we have assumed $M\in\mathcal{M}_{k}$ we have that ${\widetilde{V}}^{\pi_{k}}(s)\equiv V^{*}_{{\widetilde{M}}}(s)\geq V_{M}^{*}(s)$. Therefore ${\widetilde{V}}^{\pi_{k}}(s_{t})-V^{\pi}(s_{t})>\epsilon$. Finally note that $t$ is a non-delaying time-step and so policy $\pi$ will remain stationary and equal to $\pi_{k}$ for at least $H$ time-steps. Using the definition of the horizon, $H$, we have that $|V^{\pi}(s_{t})-V^{\pi_{k}}(s_{t})|<\epsilon/2$. Therefore ${\widetilde{V}}^{\pi_{k}}(s_{t})-V^{\pi_{k}}(s_{t})>\epsilon/2$ as required. $\blacksquare$

Proof of Lemma 6. In the previous lemma we showed that there are at most $U_{\operatorname{max}}$ updates. Therefore we only need to check $M\in{\mathcal{M}}_{k}$ for each $k$ up to $U_{\operatorname{max}}$. Fix an $(s,a)$ pair and apply the best of either Bernstein or Hoeffding inequalities to show that $|{\hat{p}}_{s,a}^{s\!a^{\!+}}-p_{s,a}^{s\!a^{\!+}}|\leq\textsc{ConfidenceInterval}({\hat{p}}_{s,a}^{s\!a^{\!+}}-p_{s,a}^{s\!a^{\!+}},n(s,a)))$ with probability $1-\delta_{1}$. Setting $\delta_{1}:={\delta\over 2|{S\times A}|U_{\operatorname{max}}}\equiv{\delta\over 2|{S\times A}|^{2}|{{\mathcal{K}}\times{\mathcal{I}}}|}$ and applying the union bound completes the proof. $\blacksquare$

We are now ready to work on Lemma 7. The proof follows from two lemmas:

If $t$ is the start of an exploration phase then there exists a $({\kappa,\iota})$ such that $|K_{t}({\kappa,\iota})|>\kappa$.

If $|K_{t}({\kappa,\iota})|>\kappa$ for sufficiently many $t$ then sufficient information is gained that some state/action pair must have an increase in knownness.

Let $t$ be a non-delaying time-step and assume $M\in{\mathcal{M}}_{k}$. If $|K_{t}({\kappa,\iota})|\leq\kappa$ for all ${\kappa,\iota}\in{\mathcal{K}}$ then $|{\widetilde{V}}^{\pi_{k}}(s_{t})-V^{\pi_{k}}(s_{t})|\leq\epsilon/2$.

The full proof is long, technical and has been relegated to Appendix B. We provide a sketch, but first we need some useful results about MDPs and the differences in value functions.

Let $M$ and ${\widetilde{M}}$ be two Markov decision processes differing only in transition probabilities and $\pi$ be a stationary policy then

If $M\in{\mathcal{M}}_{k}$ at time-step $t$ and ${\widetilde{V}}:={\widetilde{V}}^{\pi_{k}}$ then

The idea is to note that $M,{\widetilde{M}}$ are in ${\mathcal{M}}_{k}$ and apply the definition of the confidence intervals. The full proof is subsumed in the proof of the more general Lemma 33 in Appendix C. The following lemma bounds the expected total discounted local variance.

The following lemmas are used to show that $|K_{t}({\kappa,\iota})|$ cannot be larger than $\kappa$ for too many time-steps with high probability. Combined with Lemma 8 above this will be sufficient to bound the number of exploration phases. Let $t$ be the start of an exploration phase and define $\nu_{t}(s)$ to be the number of visits to state $s$ within the next $H$ time-steps. Formally, $\nu_{t}(s):=\sum_{i=t}^{t+H-1}[\![s_{t}=s]\!]$.

Let $t$ be the start of an exploration phase and $w_{t}(s)\geq w_{\operatorname{{min}}}$ then $\mathbf{E}\nu_{t}(s)\geq w_{t}(s)/2$.

Proof sketch. Use the definition of the horizon to show that $w_{t}(s)$ is not much larger than a bounded-horizon version. Compare $\mathbf{E}\nu_{t}(s,\pi_{t}(s))$ and the definition of $w_{t}(s)$. $\blacksquare$

Let $N$ be as in Appendix D. If $|K_{t_{i}}({\kappa,\iota})|>\kappa$ for $4N$ exploration phases $t_{1},t_{2},\cdots,t_{4N}$ then $\sum_{i=1}^{4N}\sum_{s\in K_{t_{i}}({\kappa,\iota})}\nu_{t_{i}}(s,\pi(s))\;\geq\;N\kappa w_{\iota}$ with probability at least $1-\delta_{1}$.

Now $|K_{i}|>\kappa$ and so by Lemma 12 we have $\mathbf{E}\nu_{i}\;\geq\;\kappa w_{\iota}/2$. We now prepare to use Bernstein’s inequality. Let $X_{i}=\nu_{i}-\mathbf{E}\nu_{i}$, $\mu:={1\over 4N}\sum_{i=1}^{4N}\mathbf{E}\nu_{i}$ and $\sigma^{2}:={1\over 4N}\sum_{i=1}^{4N}\operatorname{Var}X_{i}$ then

Setting this equal to $\delta_{1}$ and solving for $4N$ gives

Naively bounding $\sigma^{2}/\mu^{2}\leq 1/((1-\gamma)\mu)$ and noting that $\mu\geq w_{\operatorname{{min}}}/2$ leads to

Since $4N$ satisfies this, the result is complete. $\blacksquare$

Bounding the number of useful visits. A visit to state/action pair $(s,a)$ in time-step $t$ is $({\kappa,\iota})$-useful if $\kappa(\iota,n_{t}(s,a))=\kappa$. Fixing a $({\kappa,\iota})$ we bound the number of $({\kappa,\iota})$-useful visits to state/action pair $(s,a)$. Suppose $t_{1}<t_{2}$ and $\kappa(\iota,n_{t_{1}}(s,a))=\kappa$ and $n_{t_{2}}(s,a)-n_{t_{1}}(s,a)\geq mw_{\iota}(2\kappa+2)$ then $\kappa(\iota,n_{t_{3}}(s,a))>\kappa$ for all $t_{3}\geq t_{2}$. Therefore for each $({\kappa,\iota})$ pair there at most $6|{S\times A}|mw_{\iota}\kappa$ visits that are $({\kappa,\iota})$-useful.

Bounding the number of exploration phases. Let $N:={6|{S\times A}|m}$ and $t$ be the start of an exploration phase. Therefore ${\widetilde{V}}^{\pi_{k}}(s_{t})-V^{\pi_{k}}(s_{t})>\epsilon/2$ and so by Lemma 8 there exists a $({\kappa,\iota})\in{\mathcal{K}}$ such that $|S|\geq|K({\kappa,\iota})|>\kappa$. If $|K_{t_{i}}(\kappa,\iota)|>\kappa$ at the start of $4N$ exploration phases, $t_{1},t_{2},\cdots,t_{4N}$ then by Lemma 13

Therefore by the union bound there are at most $E_{\operatorname{{max}}}:=4N|{{\mathcal{K}}\times{\mathcal{I}}}|$ exploration phases with probability $1-\delta_{1}|{{\mathcal{K}}\times{\mathcal{I}}}|\equiv 1-|{{\mathcal{K}}\times{\mathcal{I}}}|{\delta\over 2|{S\times A}|U_{\operatorname{max}}}>1-\delta/2$. $\blacksquare$

Eliminating the Assumption

The last problem is that extended value iteration is no longer a trivial operation (even granting infinite computation). The problem is that the condition $(p_{s,a}-{\hat{p}}_{s,a})\cdot V^{*}$ is not local to $(s,a)$, it also depends on the choice of $p_{s^{\prime},a^{\prime}}$ for $(s^{\prime},a^{\prime})\in{S\times A}$. This complication is probably resolvable, but the formal demonstration of extended value iteration is no longer so easy.

Lower PAC Bound

We now turn our attention to proving a matching lower bound. The approach is similar to that of Strehl et al. , but we make two refinements to improve the bound to depend on $1/(1-\gamma)^{3}$ and remove the policy restrictions. The first is to add a delaying state where no information can be gained, but where an algorithm may still fail to be PAC. The second is more subtle and will be described in the proof.

A non-stationary policy is a function $\pi:S^{*}\to A$.

Let $\pi$ be a (possibly non-stationary) policy depending on $S,A,r,\gamma,\epsilon$ and $\delta$, then there exists a Markov decision process ${M_{\operatorname{hard}}}$ such that $V^{*}(s_{t})-V^{\pi}(s_{t})>\epsilon$ for at least $N$ time-steps with probability at least $\delta$ where

and $c_{1},c_{2}>0$ are independent of the policy $\pi$ as well as all inputs $S,A,\epsilon,\delta,\gamma$.

The proof can found in Appendix A, but we give the counter-example MDP and intuition.

Counter Example. We prove Theorem 15 for a class of MDPs where $S=\left\{0,1,\oplus,\ominus\right\}$ and $A=\left\{1,2,\cdots,|A|\right\}$. The rewards and transitions for a single action are depicted in the diagram on the right where $\epsilon(a^{*})=16\epsilon(1-\gamma)$ for some $a^{*}\in A$ and $\epsilon(a)=0$ for all other actions. Some remarks: {enumerate*}

States $\oplus$ and $\ominus$ are almost completely absorbing and confer maximum/minimum rewards respectively.

The transitions are independent of actions for all states except state $1$. From this state, actions lead uniformly to $\oplus$/$\ominus$ except for one action, $a^{*}$, which has a slightly higher probability of transitioning to state $\oplus$. Thus $a^{*}$ is the optimal action in state $1$.

State has an absorption rate such that, on average, a policy will stay there for $1/(1-\gamma)$ time-steps.

Intuition. The MDP above is very bandit-like in the sense that once a policy reaches state $1$ it should choose the action most likely to lead to state $\oplus$ whereupon it will either be rewarded or punished (visit state $\oplus$ or $\ominus$). Eventually it will return to state $1$ when the whole process repeats. This suggests a PAC-MDP algorithm can be used to learn the bandit with $p(a):=p_{1,a}^{\oplus}$. We can then make use of a theorem of Mannor and Tsitsiklis on bandit sample-complexity to show that the number of times $a^{*}$ is not selected is at least

Improving the bound to depend on $1/(1-\gamma)^{3}$ is intuitively easy, but technically somewhat annoying. The idea is to consider the value differences in state as well as state $1$. State has the following properties: {enumerate*}

The absorption rate is sufficiently large that any policy remains in state for around $1/(1-\gamma)$ time-steps.

The absorption rate is sufficiently small that the difference in values due to bad actions planned in state $1$ still matter while in state . While in state an agent cannot make an error in the sense that $V^{*}(0)-Q^{*}(0,a)=0$ for all $a$. But we are measuring $V^{*}(0)-V^{\pi}(0)$ and so an agent can be penalised if its policy upon reaching state $1$ is to make an error. Suppose the agent is in state at some time-step before moving to state $1$ and making a mistake. On average it will stay in state for roughly $1/(1-\gamma)$ time-steps during which time it will plan a mistake upon reaching state $1$. Thus the bound in Equation (5) can be multiplied by $1/(1-\gamma)$. The proof is harder because an agent need not plan to make a mistake in all future time-steps when reaching state $1$ before eventually doing so in one time-step. Note that Strehl et al. proved their theorem for a specific class of policies while Theorem 15 holds for all policies.

Conclusion

Summary. We presented matching upper and lower bounds on the number of time-steps when a reinforcement learning algorithm can be nearly-optimal with high probability. While the lower bound is completely general, the upper bound depends on the assumption that there are at most two next-states for each state/action pair. This assumption aside, the new upper bound improves on the previously best known bound of Auer . If the assumption is dropped then the new proof can be used to construct an algorithm that is better than the bound of Auer in terms of $1/(1-\gamma)$, but worse in $|S|$. The lower bound, which comes without assumptions, improves on the work of Strehl et al. by being both larger and more general. The class of MDPs used for the counter-example do satisfy Assumption 1 and so the upper and lower bounds now match in this restricted case.

Running Time. We did not analyze the running time of our version of UCRL, but expect analysis similar to that of Strehl and Littman can be used to show that UCRL can be approximated to run in polynomial time with no cost to sample-complexity.

Acknowledgements. Thanks to Peter Sunehag for his careful reading and useful suggestions.

References

Appendix A Proof of Lower PAC Bound

The proof makes use of a simple form of bandit and Theorem 16, which lower bounds the sample-complexity of bandit algorithms. We need some new notation required for non-stationary policies and bandits.

History Sequences. We write $s_{1:t}=s_{1},s_{2},\cdots,s_{t}$ for the history sequence of length $t$. Histories can be concatenated, so $s_{1:t}\oplus=s_{1},s_{2},\cdots,s_{t},\oplus$ where $\oplus\in S$.

Bandits. An $A$-armed bandit is a vector $p:A\to$. A policy interacts with a bandit sequentially. In time-step $t$ some arm $a_{t}$ is played whereupon the policy receives reward $1$ with probability $p(a)$ and reward otherwise. This is repeated over all time-steps. More formally, a bandit policy is a function $\pi:\left\{0,1\right\}^{*}\to A$. The optimal arm is defined $a^{*}:=\operatornamewithlimits{arg\,max}_{a}p(a)$. A policy dependent on $\epsilon,\delta$ and $A$ has sample-complexity $T:=T(A,\epsilon,\delta)$ if for all bandits the arm chosen on time-step $T$ satisfies $p(a^{*})-p(a_{T})\leq\epsilon$ with probability at least $1-\delta$.

There exist positive constants $c_{1}$, $c_{2}$, $\epsilon_{0}$, and $\delta_{0}$, such that for every $A\geq 2$, $\epsilon\in(0,\epsilon_{0})$ and $\delta\in(0,\delta_{0})$ there exists a bandit $p\in^{A}$ such that

The bandit used in the proof of Theorem 16 satisfies $p(a)={1\over 2}$ for all $a$ except $a^{*}$ which has $p(a^{*}):={1\over 2}+\epsilon$.

We now prepare to prove Theorem 15. For the remainder of this section let $\pi$ be an arbitrary policy and ${M_{\operatorname{hard}}}$ be the MDP of Figure 2. As in previous work we write $V^{\pi}:=V^{\pi}_{{M_{\operatorname{hard}}}}$. The idea of the proof will be to use Theorem 16 to show that $\pi$ cannot be approximately correct in state $1$ too often. Then use this to show that while in state before-hand it is also not approximately correct.

Let $s_{1:\infty}\in S^{\infty}$ be the sequence of states seen by policy $\pi$ and for arbitrary history $s_{1:t}$ let

If $\gamma\in(0,1)$, $p:=1/(2-\gamma)$ and $q:=2-1/\gamma$ then

Proof sketch. Both results follow from the geometric series and easy calculus. $\blacksquare$

The following lemma lower-bounds $\Delta(s_{1:t})$ if sub-optimal action $a\neq a^{*}$ is taken in state $1$.

Let $s_{1:t}$ be a history such that $s_{t}=1$ and $a:=\pi(s_{1:t})\neq a^{*}$ then

Proof. The result essentially follows from the definition of the value function.

where we used the definition of the value function and MDP, ${M_{\operatorname{hard}}}$. $\blacksquare$

We now define time-intervals where the policy is in state . Recall we chose the absorption in this state such that the expected number of time-steps a policy remains there is approximately $1/(1-\gamma)$. We define the intervals starting when a policy arrives in state and ending when it leaves to state $1$.

$|I_{i}|$ is the number of time-steps spent in state before moving to state $1$.

The values $|I_{i}|$ are independent of $\pi$ and each other.

$\sum_{a\in A}w_{t}(a)={1\over 2}$ for all $t$ where $s_{t}=0$.

Define random variables $A_{i}$ and $X_{i}$ by

Intuitively, $X_{i}$ is the event that the $i$th phase lasts at least $1/[4(1-\gamma)]$ time-steps. $A_{i}$ is the event that the $i$th phase lasts at least $1/[16(1-\gamma)]$ time-steps and the combined weight of sub-optimal actions at the start of a phase is at least $1/4$. The following lemma shows that at least two thirds of all phases have $X_{i}=1$ with high probability.

Proof. Preparing to use Hoeffding’s bound,

where we used the definitions of $X_{i}$, $I_{i}$ and Lemma 19. Therefore $\mathbf{E}X_{i}>3/4$.

where we applied basic inequalities followed by Hoeffding’s bound. $\blacksquare$

Rearranging, setting $0\leq k\leq 1/[16(1-\gamma)]$ and using the geometric series completes the proof. $\blacksquare$

So far, none of our results have been especially surprising. Lemma 25 shows that at least two thirds of all phases have length exceeding $1/[4(1-\gamma)]$ with high probability. Lemma 26 shows that if at the start of a phase $\pi$ assigns a high weight to the sub-optimal actions, then it does so throughout the entire phase. The following lemma is more fundamental. It shows that the number of phases where $\pi$ assigns a high weight to the sub-optimal actions is of order ${1\over\epsilon^{2}(1-\gamma)^{2}}\log{1\over\delta}$ with high probability.

Let $N:={c_{1}A\over\epsilon^{2}(1-\gamma)^{2}}\log{c_{2}\over\delta}$ with constants as in Theorem 16 then

The idea is similar to that in [Strehl et al., 2009]. Assume a policy exists that doesn’t satisfy the condition above and then use it to learn the bandit defined by $p(a):=p_{1,a}^{\oplus}$.

Proof. Let $p(a):=p_{1,a}^{\oplus}$ be a bandit and use $\pi$ to learn bandit $p$ using Algorithm 2 below, which returns an action $a_{\operatorname{best}}$ defined as

By Theorem 16, the strategy in Algorithm 2 must fail with probability at least $\delta$. Therefore with probability at least $\delta$, $a_{\operatorname{best}}\neq a^{*}$. However $a_{\operatorname{best}}$ is defined as the majority action of all the $\bar{a}_{i}$ and so for at least $N$ time-steps $\bar{a}_{i}\neq a^{*}$. Suppose $w_{t_{i}^{0}}(a)>{1\over 4}$, then by Lemma 23, $\sum_{a\neq a^{*}}w_{t_{i}^{0}}(a)<{1\over 4}$ and $\bar{a}_{i}\equiv\operatornamewithlimits{arg\,max}_{a}w_{t_{i}^{0}}(a)=a^{*}$. This implies that with probability $\delta$, for at least $N$ time-steps $\sum_{a\neq a^{*}}w_{t^{0}_{i}}(a)>{1\over 4}$ as required. $\blacksquare$

Proof of Theorem 15. Suppose $A_{i}=1$ and $0\leq k\leq 1/[16(1-\gamma)]$ then $s_{1:t_{i}^{0}+k}=s_{1:t_{i}^{0}}0^{k}$ and

where Equation (6) follows from the definition of ${M_{\operatorname{hard}}}$ and the value function. Equation (7) by Lemma 20. Equation (8) by the definition of $w_{t_{i}+k}(a)$ and Equation (8) by Lemma 26. Thus for each $i$ where $A_{i}=1$, policy $\pi$ makes at least $1/[16(1-\gamma)]$ $\epsilon$-errors. The proof is completed by showing that $A_{i}=1$ for at least $N/6$ time-steps with probability at least $\delta$, which follows easily from Lemma 27 and Lemma 25.

Dependence on $S$ is added trivially by chaining arbitrarily many such Markov decision processes together. $\blacksquare$

Dependence on $S\log S$ can possibly be added by a similar technique used by Strehl et al. , but details could be messy.

Appendix B Technical Results

Let $X_{1},\cdots,X_{n}$ be independent $$-valued random variables with probability$1$. Then

Let $X_{1},\cdots,X_{n}$ be independent real-valued random variables with zero mean and variance $\operatorname{Var}X_{i}=\sigma^{2}_{i}$. If $|X_{k}|<c$ with probability one then

where $\sigma^{2}:={1\over n}\sum_{i=1}^{n}\sigma^{2}_{i}$.

Proof. Using the first confidence interval

Appendix C Proof of Lemma 8

We need to define some higher “moments” of the value function. This is somewhat unfortunate as it complicates the proof, but may be unavoidable.

We define the space of bounded value/reward functions $\mathcal{R}$ by

Let $\pi$ be some stationary policy. For $r_{d}\in\mathcal{R}(d)$ define values $V^{\pi}_{d}$ by the Bellman equations

The following lemma generalises Lemma 10.

Let $M\in{\mathcal{M}}_{k}$ at time-step $t$ then

Assume without loss of generality that ${\widetilde{V}}_{d}(s\!a^{\!+})\geq{\widetilde{V}}_{d}(s\!a^{\!-})$. Therefore we have

where we used Assumption 1 and the fact that $V_{d}\in\mathcal{R}_{d+1}$.

Substituting into Equation (10) completes the proof. $\blacksquare$

The expressions $B_{d}$ and $C_{d}$ are substantially easier to bound than $A_{d}$. First we give a naive bound on $A_{d}$, which we use later.

Expanding the recurrence up to $\beta$ leads to

where we used the naive bound to control $A_{\beta}$. The bounds on $B_{d}$ and $C_{d}$ are somewhat easier, and follow similar lines to the naive bound on $A_{d}$.

Letting $m:={20L_{1}|{{\mathcal{K}}\times{\mathcal{I}}}||\mathcal{D}|^{2}\over\epsilon^{2}(1-\gamma)^{2+2/\beta}}$ completes the proof. $\blacksquare$

Appendix D Constants

The proof of Theorem 3 uses many constants, which can be hard to keep track of. For convenience we list them below, including approximate upper/lower bounds as appropriate.

Appendix E Table of Notation