Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning

Introduction

The recent empirical successes of deep reinforcement learning (RL) are tremendously exciting, but the performance of these approaches still varies significantly across domains, each of which requires the user to solve a new tuning problem . Ultimately we would like reinforcement learning algorithms that simultaneously perform well empirically and have strong theoretical guarantees. Such algorithms are especially important for high stakes domains like health care, education and customer service, where non-expert users demand excellent outcomes.

We propose a new framework for measuring the performance of reinforcement learning algorithms called Uniform-PAC. Briefly, an algorithm is Uniform-PAC if with high probability it simultaneously for all $\varepsilon>0$ selects an $\varepsilon$-optimal policy on all episodes except for a number that scales polynomially with $1/\varepsilon$. Algorithms that are Uniform-PAC converge to an optimal policy with high probability and immediately yield both PAC and high probability regret bounds, which makes them superior to algorithms that come with only PAC or regret guarantees. Indeed,

Neither PAC nor regret guarantees imply convergence to optimal policies with high probability;

$(\varepsilon,\delta)$-PAC algorithms may be $\varepsilon/2$-suboptimal in every episode;

Algorithms with small regret may be maximally suboptimal infinitely often.

Uniform-PAC algorithms suffer none of these drawbacks. One could hope that existing algorithms with PAC or regret guarantees might be Uniform-PAC already, with only the analysis missing. Unfortunately this is not the case and modification is required to adapt these approaches to satisfy the new performance metric. The key insight for obtaining Uniform-PAC guarantees is to leverage time-uniform concentration bounds such as the finite-time versions of the law of iterated logarithm, which obviates the need for horizon-dependent confidence levels.

We provide a new optimistic algorithm for episodic RL called UBEV that is Uniform PAC. Unlike its predecessors, UBEV uses confidence intervals based on the law of iterated logarithm (LIL) which hold uniformly over time. They allow us to more tightly control the probability of failure events in which the algorithm behaves poorly. Our analysis is nearly optimal according to the traditional metrics, with a linear dependence on the state space for the PAC setting and square root dependence for the regret. Therefore UBEV is a Uniform PAC algorithm with PAC bounds and high probability regret bounds that are near optimal in the dependence on the length of the episodes (horizon) and optimal in the state and action spaces cardinality as well as the number of episodes. To our knowledge UBEV is the first algorithm with both near-optimal PAC and regret guarantees.

We consider episodic fixed-horizon MDPs with time-dependent dynamics, which can be formalized as a tuple $M=(\mathcal{S},\mathcal{A},p_{R},P,p_{0},H)$. The statespace $\mathcal{S}$ and the actionspace $\mathcal{A}$ are finite sets with cardinality $S$ and $A$. The agent interacts with the MDP in episodes of $H$ time steps each. At the beginning of each time-step $t\in[H]$ the agent observes a state $s_{t}$ and chooses an action $a_{t}$ based on a policy $\pi$ that may depend on the within-episode time step ($a_{t}=\pi(s_{t},t)$). The next state is sampled from the $t$th transition kernel $s_{t+1}\sim P(\cdot|s_{t},a_{t},t)$ and the initial state from $s_{1}\sim p_{0}$. The agent then receives a reward drawn from a distribution $p_{R}(s_{t},a_{t},t)$ which can depend on $s_{t},a_{t}$ and $t$ with mean $r(s_{t},a_{t},t)$ determined by the reward function. The reward distribution $p_{R}$ is supported on $$.The reward may be allowed to depend on the next-state with no further effort in the proofs. The boundedness assumption could be replaced by the assumption of subgaussian noise with known subgaussian parameter. The value function from time step$t$for policy$\pi$ is defined as

and the optimal value function is denoted by $V^{\star}_{t}$. In any fixed episode, the quality of a policy $\pi$ is evaluated by the total expected reward or return

Uniform PAC and Existing Learning Frameworks

We briefly summarize the most common performance measures used in the literature.

$(\varepsilon,\delta)$-PAC: There exists a polynomial function $F_{\textrm{PAC}}(S,A,H,1/\varepsilon,\log(1/\delta))$ such that

High Probability Regret: There exists a function $F_{\textrm{HPR}}(S,A,H,T,\log(1/\delta))$ such that

Uniform High Probability Regret: There exists a function $F_{\textrm{UHPR}}(S,A,H,T,\log(1/\delta))$ such that

In all definitions the function $F$ should be polynomial in all arguments. For notational conciseness we often omit some of the parameters of $F$ where the context is clear. The different performance guarantees are widely used (e.g. PAC: , (uniform) high-probability regret: ; expected regret: ). Due to space constraints, we will not discuss Bayesian-style performance guarantees that only hold in expectation with respect to a distribution over problem instances. We will shortly discuss the limitations of the frameworks listed above, but first formally define the Uniform-PAC criteria

An algorithm is Uniform-PAC for $\delta>0$ if

where $F_{\textrm{UPAC}}$ is polynomial in all arguments.

Since regret guarantees only bound the integral of $\Delta_{k}$ over $k$, it does not distinguish between making a few severe mistakes and many small mistakes. In fact, since regret bounds provably grow with the number of episodes $T$, an algorithm that achieves optimal regret may still make infinitely many mistakes (of arbitrary quality, see proof of Theorem 2 below). This is highly undesirable in high-stakes scenarios. For example in drug treatment optimization in healthcare, we would like to distinguish between infrequent severe complications (few large $\Delta_{k}$) and frequent minor side effects (many small $\Delta_{k}$). In fact, even with an optimal regret bound, we could still serve infinitely patients with the worst possible treatment.

Limitations of PAC.

PAC bounds limit the number of mistakes for a given accuracy level $\varepsilon$, but is otherwise non-restrictive. That means an algorithm with $\Delta_{k}>\varepsilon/2$ for all $k$ almost surely might still be $(\varepsilon,\delta)$-PAC. Worse, many algorithms designed to be $(\varepsilon,\delta)$-PAC actually exhibit this behavior because they explicitly halt learning once an $\varepsilon$-optimal policy has been found. The less widely used TCE (total cost of exploration) bounds and KWIK guarantees suffer from the same issueand for conciseness are not discussed in detail.

Advantages of Uniform-PAC.

The new criterion overcomes the limitations of PAC and regret guarantees by measuring the number of $\varepsilon$-errors at every level simultaneously. By definition, algorithms that are Uniform-PAC for a $\delta$ are $(\varepsilon,\delta)$-PAC for all $\varepsilon>0$. We will soon see that an algorithm with a non-trivial Uniform-PAC guarantee also has small regret with high probability. Furthermore, there is no loss in the reduction so that an algorithm with optimal Uniform-PAC guarantees also has optimal regret, at least in the episodic RL setting. In this sense Uniform-PAC is the missing bridge between regret and PAC. Finally, for algorithms based on confidence bounds, Uniform-PAC guarantees are usually obtained without much additional work by replacing standard concentration bounds with versions that hold uniformly over episodes (e.g. using the law of the iterated logarithms). In this sense we think Uniform-PAC is the new ‘gold-standard’ of theoretical guarantees for RL algorithms.

1 Relationships between Performance Guarantees

Existing theoretical analyses usually focus exclusively on either the regret or PAC framework. Besides occasional heuristic translations, Proposition 4 in and Corollary 3 in are the only results relating a notion of PAC and regret, we are aware of. Yet the guarantees there are not widely usedThe average per-step regret in is superficially a PAC bound, but does not hold over infinitely many time-steps and exhibits the limitations of a conventional regret bound. The translation to average loss in comes at additional costs due to the discounted infinite horizon setting. unlike the definitions given above which we now formally relate to each other. A simplified overview of the relations discussed below is shown in Figure 1.

a sub-linear expected regret bound for all $T$ and

a finite $(\varepsilon,\delta)$-PAC bound for a small enough $\varepsilon$

simultaneously for all two-armed multi-armed bandits with Bernoulli reward distributions. This implies that such guarantees also cannot be satisfied simultaneously for all episodic MDPs.

A full proof is in Appendix A.1, but the intuition is simple. Suppose a two-armed Bernoulli bandit has mean rewards $\nicefrac{{1}}{{2}}+\varepsilon$ and $\nicefrac{{1}}{{2}}$ respectively and the second arm is chosen at most $F<\infty$ times with probability at least $1-\delta$, then one can easily show that in an alternative bandit with mean rewards $\nicefrac{{1}}{{2}}+\varepsilon$ and $\nicefrac{{1}}{{2}}+2\varepsilon$ there is a non-zero probability that the second arm is played finitely often and in this bandit the expected regret will be linear. Therefore, sub-linear expected regret is only possible if each arm is pulled infinitely often almost surely.

The following statements hold for performance guarantees in episodic MDPs:

If an algorithm satisfies a $(\varepsilon,\delta)$-PAC bound with $F_{\textrm{PAC}}=\Theta(1/\varepsilon^{2})$ then it satisfies for a specific $T=\Theta(\varepsilon^{-3})$ a $F_{\textrm{HPR}}=\Theta(T^{2/3})$ bound. Further, there is an MDP and algorithm that satisfies the $(\varepsilon,\delta)$-PAC bound $F_{\textrm{PAC}}=\Theta(1/\varepsilon^{2})$ on that MDP and has regret $R(T)=\Omega(T^{2/3})$ on that MDP for any $T$. That means a $(\varepsilon,\delta)$-PAC bound with $F_{\textrm{PAC}}=\Theta(1/\varepsilon^{2})$ can only be converted to a high-probability regret bound with $F_{\textrm{HPR}}=\Omega(T^{2/3})$.

For any chosen $\varepsilon,\delta>0$ and $F_{\textrm{PAC}}$, there is an MDP and algorithm that satisfies the $(\varepsilon,\delta)$-PAC bound $F_{\textrm{PAC}}$ on that MDP and has regret $R(T)=\Omega(T)$ on that MDP. That means a $(\varepsilon,\delta)$-PAC bound cannot be converted to a sub-linear uniform high-probability regret bound.

For any $F_{\textrm{UHPR}}(T,\delta)$ with $F_{\textrm{UHPR}}(T,\delta)\rightarrow\infty$ as $T\rightarrow\infty$, there is an algorithm that satisfies that uniform high-probability regret bound on some MDP but makes infinitely many mistakes for any sufficiently small accuracy level $\varepsilon>0$ for that MDP. Therefore, a high-probability regret bound (uniform or not) cannot be converted to a finite $(\varepsilon,\delta)$-PAC bound.

For most interesting RL problems including episodic MDPs the worst-case expected regret grows with $O(\sqrt{T})$. The theorem shows that establishing an optimal high probability regret bound does not imply any finite PAC bound. While PAC bounds may be converted to regret bounds, the resulting bounds are necessarily severely suboptimal with a rate of $T^{2/3}$. The next theorem formalises the claim that Uniform-PAC is stronger than both the PAC and high-probability regret criteria.

is $(\varepsilon,\delta)$-PAC with bound $F_{\textrm{PAC}}=F_{\textrm{UPAC}}$ for all $\varepsilon$.

Observe that stronger uniform PAC bounds lead to stronger regret bounds and for RL in episodic MDPs, an optimal uniform-PAC bound implies a uniform regret bound. To our knowledge, there are no existing approaches with PAC or regret guarantees that are Uniform-PAC. PAC methods such as MBIE, MoRMax, UCRL-$\gamma$, UCFH, Delayed Q-Learning or Median-PAC all depend on advance knowledge of $\varepsilon$ and eventually stop improving their policies. Even when disabling the stopping condition, these methods are not uniform-PAC as their confidence bounds only hold for finitely many episodes and are eventually violated according to the law of iterated logarithms. Existing algorithms with uniform high-probability regret bounds such as UCRL2 or UCBVI also do not satisfy uniform-PAC bounds since they use upper confidence bounds with width $\sqrt{\log(T)/n}$ where $T$ is the number of observed episodes and $n$ is the number of observations for a specific state and action. The presence of $\log(T)$ causes the algorithm to try each action in each state infinitely often. One might begin to wonder if uniform-PAC is too good to be true. Can any algorithm meet the requirements? We demonstrate in Section 4 that the answer is yes by showing that UBEV has meaningful Uniform-PAC bounds. A key technique that allows us to prove these bounds is the use of finite-time law of iterated logarithm confidence bounds which decrease at rate $\sqrt{(\log\log n)/n}$.

The UBEV Algorithm

where $(P^{\prime}-\hat{P}_{k})(s,a,t)$ is short for $P^{\prime}(s,a,t)-\hat{P}_{k}(s,a,t)=P^{\prime}(\cdot|s,a,t)-\hat{P}_{k}(\cdot|s,a,t)$ and

is the width of a confidence bound with $e=\exp(1)$ and $\hat{P}_{k}(s^{\prime}|s,a,t)=\frac{m(s^{\prime},s,a,t)}{n(s,a,t)}$ are the empirical transition probabilities and $\hat{r}_{k}(s,a,t)=l(s,a,t)/n(s,a,t)$ the empirical immediate rewards (both at the beginning of the $k$th episode). Our algorithm is conceptually similar to other algorithms based on the optimism principle such as MBIE , UCFH , UCRL2 or UCRL-$\gamma$ but there are several key differences:

Instead of using confidence intervals over the transition kernel by itself, we incorporate the value function directly into the concentration analysis. Ultimately this saves a factor of $S$ in the sample complexity, but the price is a more difficult analysis. Previously MoRMax also used the idea of directly bounding the transition and value function, but in a very different algorithm that required discarding data and had a less tight bound. A similar technique has been used by Azar et al. .

Many algorithms update their policy less and less frequently (usually when the number of samples doubles), and only finitely often in total. Instead, we update the policy after every episode, which means that UBEV immediately leverages new observations.

Confidence bounds in existing algorithms that keep improving the policy (e.g. Jaksch et al. , Azar et al. ) scale at a rate $\sqrt{\log(k)/n}$ where $k$ is the number of episodes played so far and $n$ is the number of times the specific ($s,a,t$) has been observed. As the results of a brief empirical comparison in Figure 2 indicate, this leads to slow learning (compare UCBVI_1 and UBEV’s performance which differ essentially only by their use of different rate bounds). Instead the width of UBEV’s confidence bounds $\phi$ scales at rate $\sqrt{\ln\ln(\max\{e,n\})/n}\approx\sqrt{(\log\log n)/n}$ which is the best achievable rate and results in significantly faster learning.

Uniform PAC Analysis

We now discuss the Uniform-PAC analysis of UBEV which results in the following Uniform-PAC and regret guarantee.

Let $\pi_{k}$ be the policy of UBEV in the $k$th episode. Then with probability at least $1-\delta$ for all $\varepsilon>0$ jointly the number of episodes $k$ where the expected return from the start state is not $\varepsilon$-optimal (that is $\Delta_{k}>\varepsilon$) is at most

Therefore, with probability at least $1-\delta$ UBEV converges to optimal policies and for all episodes $T$ has regret

Here $\operatorname{polylog}(x\dots)$ is a function that can be bounded by a polynomial of logarithm, that is, $\exists k,C:\operatorname{polylog}(x\dots)\leq\ln(x\dots)^{k}+C$. In Appendix C we provide a lower bound on the sample complexity that shows that if $\varepsilon<1/(S^{2}A)$, the Uniform-PAC bound is tight up to log-factors and a factor of $H$. To our knowledge, UBEV is the first algorithm with both near-tight (up to $H$ factors) high probability regret and $(\varepsilon,\delta)$ PAC bounds as well as the first algorithm with any nontrivial uniform-PAC bound.

Using Theorem 3 the convergence and regret bound follows immediately from the uniform PAC bound. After a discussion of the different confidence bounds allowing us to prove uniform-PAC bounds, we will provide a short proof sketch of the uniform PAC bound.

To have a PAC bound for all $\varepsilon$ jointly, it is critical that UBEV continually make use of new experience. If UBEV stopped leveraging new observations after some fixed number, it would not be able to distinguish with high probability among which of the remaining possible MDPs do or do not have optimal policies that are sufficiently optimal in the other MDPs. The algorithm therefore could potentially follow a policy that is not at least $\varepsilon$-optimal for infinitely many episodes for a sufficiently small $\varepsilon$. To enable UBEV to incorporate all new observations, the confidence bounds in UBEV must hold for an infinite number of updates. We therefore require a proof that the total probability of all possible failure events (of the high confidence bounds not holding) is bounded by $\delta$, in order to obtain high probability guarantees. In contrast to prior $(\varepsilon,\delta)$-PAC proofs that only consider a finite number of failure events (which is enabled by requiring an RL algorithm to stop using additional data), we must bound the probability of an infinite set of possible failure events.

Some choices of confidence bounds will hold uniformly across all sample sizes but are not sufficiently tight for uniform PAC results. For example, the recent work by Azar et al. uses confidence intervals that shrink at a rate of $\sqrt{\frac{\ln T}{n}}$, where $T$ is the number of episodes, and $n$ is the number of samples of a $(s,a)$ pair at a particular time step. This confidence interval will hold for all episodes, but these intervals do not shrink sufficiently quickly and can even increase. One simple approach for constructing confidence intervals that is sufficient for uniform PAC guarantees is to combine bounds for fixed number of samples with a union bound allocating failure probability $\delta/n^{2}$ to the failure case with $n$ samples. This results in confidence intervals that shrink at rate $\sqrt{\nicefrac{{1}}{{n}}\ln n}$. Interestingly we know of no algorithms that do such in our setting.

We follow a similarly simple but much stronger approach of using law-of-iterated logarithm (LIL) bounds that shrink at the better rate of $\sqrt{\nicefrac{{1}}{{n}}\ln\ln n}$. Such bounds have sparked recent interest in sequential decision making but to the best of our knowledge we are the first to leverage them for RL. We prove several general LIL bounds in Appendix F and explain how we use these results in our analysis in Appendix E.2. These LIL bounds are both sufficient to ensure uniform PAC bounds, and much tighter (and therefore will lead to much better performance) than $\sqrt{\nicefrac{{1}}{{n}}\ln T}$ bounds. Indeed, LIL have the tightest possible rate dependence on the number of samples $n$ for a bound that holds for all timesteps (though they are not tight with respect to constants).

2 Proof Sketch

where $\phi_{k}(s,a,t)$ is the value of $\phi(s,a,t)$ and $n_{tk}(s,a)$ the value of $n(s,a,t)$ right before episode $k$. Further we decompose

where the second inequality follows from a standard concentration bound used in the definition of the failure event $F$ (see below). Substituting this and (8) into (7) leads to

On $F^{C}$ it also holds that $n_{tk}(s,a)\geq\frac{1}{2}\sum_{i<k}w_{ti}(s,a)-\ln\frac{9SAH}{\delta}$ and so on nice episodes where each $(s,a)\in L_{tk}$ with significant probability $w_{tk}(s,a)$ also had significant probability in the past, i.e., $\sum_{i<k}w_{ti}(s,a)\geq 4\ln\frac{9SA}{\delta}$, it holds that $n_{tk}(s,a)\geq\frac{1}{4}\sum_{i<k}w_{ti}(s,a)$. Substituting this into (10), we can use a careful pidgeon-hole argument laid out it Lemma E.3 in the appendix to show that this term is bounded by $\varepsilon/3$ on all but $O(AS^{2}H^{4}/\varepsilon^{2}\operatorname{polylog}(A,S,H,1/\varepsilon,1/\delta))$ nice episodes. Again using a pidgeon-hole argument, one can show that all but at most $O(S^{2}AH^{3}/\varepsilon\ln(SAH/\delta))$ episodes are nice. Combining both bounds, we get that on $F^{C}$ the optimality gap $\Delta_{k}$ is at most $\varepsilon$ except for at most $O(AS^{2}H^{4}/\varepsilon^{2}\operatorname{polylog}(A,S,H,1/\varepsilon,1/\delta))$ episodes.

We decompose the failure event into multiple components. In addition to the events $F^{N}_{k}$ that a $(s,a,t)$ triple has been observed few times compared to its visitation probabilities in the past, i.e., $n_{tk}(s,a)<\frac{1}{2}\sum_{i<k}w_{ti}(s,a)-\ln\frac{9SAH}{\delta}$ as well as a conditional version of this statement, the failure event $F$ contains events where empirical estimates of the immediate rewards, the expected optimal value of the successor states and the individual transition probabilites are far from their true expectations. For the full definition of $F$ see Appendix E.2. $F$ also contains event $F^{L1}$ we used in Eq. (9) defined as

With a more refined analysis that avoids the use of Hölder’s inequality in (9) and a stronger notion of nice episodes called friendly episodes we obtain the bound with the first term in the $\min$. However, since a similar analysis has been recently released , we defer this discussion to the appendix.

3 Discussion of UBEV Bound

Comparing UBEV’s regret bound to the ones of UCRL2 and REGAL requires care because (a) we measure the regret over entire episodes and (b) our transition dynamics are time-dependent within each episode, which effectively increases the state-space by a factor of $H$. Converting the bounds for UCRL2/REGAL to our setting yields a regret bound of order $SH^{2}\sqrt{AHT}$. Here, the diameter is $H$, the state space increases by $H$ due to time-dependent transition dynamics and an additional $\sqrt{H}$ is gained by stating the regret in terms of episodes $T$ instead of time steps. Hence, UBEV’s bounds are better by a factor of $\sqrt{SH}$. Our bound matches the recent regret bound for episodic RL by Azar et al. in the $S$, $A$ and $T$ terms but not in $H$. Azar et al. has regret bounds that are optimal in $H$ but their algorithm is not uniform PAC, due to the characteristics we outlined in Section 2.

Conclusion

The Uniform-PAC framework strengthens and unifies the PAC and high-probability regret performance criteria for reinforcement learning in episodic MDPs. The newly proposed algorithm is Uniform-PAC, which as a side-effect means it is the first algorithm that is both PAC and has sub-linear (and nearly optimal) regret. Besides this, the use of law-of-the-iterated-logarithm confidence bounds in RL algorithms for MDPs provides a practical and theoretical boost at no cost in terms of computation or implementation complexity.

This work opens up several immediate research questions for future work. The definition of Uniform-PAC and the relations to other PAC and regret notions directly apply to multi-armed bandits and contextual bandits as special cases of episodic RL, but not to infinite horizon reinforcement learning. An extension to these non-episodic RL settings is highly desirable. Similarly, a version of the UBEV algorithm for infinite-horizon RL with linear state-space sample complexity would be of interest. More broadly, if theory is ever to say something useful about practical algorithms for large-scale reinforcement learning, then it will have to deal with the unrealizable function approximation setup (unlike the tabular function representation setting considered here), which is a major long-standing open challenge. Acknowledgements. We appreciate the support of a NSF CAREER award and a gift from Yahoo.

References

Appendix A Framework Relation Proofs

We will use two episodic MDPs, $M_{1}$ and $M_{2}$, which are essentially 2-armed bandits and hard to distinguish to prove this statement. Both MDPs have one state, horizon $H=1$, and two actions $\mathcal{A}=\{1,2\}$. For a fixed $\alpha>0$, the rewards are Bernoulli($1/2+\alpha/2$) distributed for actions $1$ in both MDPs. Playing action $2$ in $M_{1}$ gives Bernoulli($1/2$) rewards and action $2$ in $M_{2}$ gives Bernoulli($1/2+\alpha$) rewards.

the likelihood ratio of $Y_{\infty}$ is upper bounded by $(1+2\alpha)^{N}$ if the second action has been chosen at most $N$ times. Hence

A.2 Proof of Theorem 2

PAC Bound to high-probability regret bound: Consider a fixed $\delta>0$ and PAC bound with $F_{\textrm{PAC}}=\Theta(1/\varepsilon^{2})$. Then there is a $C>0$ such that the following algorithm satisfies the PAC bound. The algorithm uses the worst possible policy with optimality gap $H$ in all episodes on some event $E$ and in the first $C/\varepsilon^{2}$ episodes on the complimentary event $E^{C}$. For the remaining episodes on $E^{C}$ it follows a policy with optimality gap $\varepsilon$. The probability of $E$ is $\delta$. The regret of the algorithm on $E$ is $R(T)=TH$ and on $E^{C}$ it is $R(T)=\min\{T,C/\varepsilon^{2}\}H+\min\{T-C/\varepsilon^{2},0\}\varepsilon$. For $T\geq C/\varepsilon^{2}$, on any event the regret of this algorithm is at least

takes its minimum at $T=\frac{C(H-\varepsilon)}{\varepsilon^{3}}$ with a positive value and hence $R(T)=\Omega(T^{2/3})$. Therefore a PAC bound with rate $1/\varepsilon^{2}$ implies at best a high-probability regret bound of order $O(T^{2/3})$ and is only tight at $T=\Theta(1/\varepsilon^{3})$. Furthermore, by looking at Equation (15), we see that for any fixed $\varepsilon$, there is an algorithm that has uniform high-probability regret that is $\Omega(T)$.

PAC Bound to uniform high-probability regret bound: Consider a fixed $\delta>0$ and $\varepsilon>0$ and a PAC bound $F_{\textrm{PAC}}$ that evaluates to some value $N$ for parameter $\varepsilon$. The algorithm uses the worst possible policy with optimality gap $H$ in all episodes on some event $E$ and in the first $N$ episodes on the complimentary event $E^{C}$. For the remaining episodes on $E^{C}$ it follows a policy with optimality gap $\varepsilon$. The probability of $E$ is $\delta$. The regret of the algorithm on $E$ is $R(T)=TH$ and on $E^{C}$ it is $R(T)=\min\{T,N\}H+\min\{T-N,0\}\varepsilon$. For $T\geq N$, on any event the regret of this algorithm is at least

Uniform high-probability regret bound to PAC bound: Consider an MDP such that at least one suboptimal policy exists with optimality gap $\varepsilon>0$. Further let $L(T)$ be a nondecreasing function with $F_{\textrm{UHPR}}(T)\geq L(T)$ and $L(T)\rightarrow\infty$ as $T\rightarrow\infty$. Then the algorithm plays the optimal policy except for episodes $k$ where $\lfloor L(k-1)/\varepsilon\rfloor\neq\lfloor L(k)/\varepsilon\rfloor$. This algorithm satisfies the regret bound but makes infinitely many $\nicefrac{{\varepsilon}}{{2}}$-mistakes with probability $1$.

A.3 Proof of Theorem 3

Convergence to optimal policies: The convergence to the set of optimal policies follows directly by using the definition of limits on the $\Delta_{k}$ sequence for each outcome in the high-probability event where the bound holds. $(\varepsilon,\delta)$-PAC: Due to sub-additivity of probabilities, we have

High-Probability Regret Bound: This part is proved separately in Theorem A.1 below. ∎

Assume on some event $E$ an algorithm follows for all $\varepsilon$ an $\varepsilon$-optimal policy $\pi_{k}$, i.e., $\Delta_{k}\leq\varepsilon$, on all but at most

episodes where $C_{1}\geq C_{2}\geq 2$ and $C_{3}\geq\max\{H,e\}$ and $C_{1},C_{2},C_{3}$ do not depend on $\varepsilon$ . Then this algorithm has on this event a regret of

The mistake bound $g(\varepsilon)=\frac{C_{1}}{\varepsilon}\left(\ln\frac{C_{3}}{\varepsilon}\right)^{k}+\frac{C_{2}}{\varepsilon^{2}}\left(\ln\frac{C_{3}}{\varepsilon}\right)^{2k}\leq T$ is monotonically decreasing for $\varepsilon\in(0,H]$. For a given $T$ large enough, we can therefore find an $\varepsilon_{\min}\in(0,H]$ such that $g(\varepsilon)\leq T$ for all $\varepsilon\in(\varepsilon_{\min},H]$. The regret $R(T)$ of the algorithm can then be bounded as follows

This bound assumes the worst case where first the algorithm makes the worst mistakes possible with regret $H$ and subsequently less and less severe mistakes controlled by the mistake bound. For a better intuition, see Figure 3.

We first find a suitable $\varepsilon_{\min}$. Define $y=\frac{1}{\varepsilon}\left(\ln\frac{C_{3}}{\varepsilon}\right)^{k}$ then since $g$ is monotonically decreasing, it is sufficient to find a $\varepsilon$ with $g(\varepsilon)\leq T$. That is equivalent to $C_{1}y+C_{2}y^{2}\leq T$ for which

and then use the choice of $\varepsilon_{\min}$ from above to look at each of the terms in this bound individually. In the following bounds we extensively use the fact $\ln(a+b)\leq\ln(a)+\ln(b)=\ln(ab)$ for all $a,b\geq 2$ and that $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ which holds for all $a,b\geq 0$.

where the first inequality follows from the fact that $\frac{C_{3}(C_{1}+\sqrt{C_{1}^{2}+4TC_{2}})}{2C_{2}}\geq\frac{C_{3}2C_{1}}{2C_{2}}\geq e$. Hence, we can bound

As a result we can conclude that $R(T)\leq(\sqrt{C_{2}T}+C_{1})\operatorname{polylog}(T,C_{3},C_{1},H)=O(\sqrt{C_{2}T}\operatorname{polylog}(T,C_{3},C_{1},H))$. ∎

Appendix B Experimental Details

We generated the MDPs with $S=5,50,200$ states, $A=3$ actions and $H=10$ timesteps as follows: The transition probabilities $P(s,a,t)$ were sampled independently from $\textrm{Dirichlet}\left(\frac{1}{10},\dots\frac{1}{10}\right)$ and the rewards were all deterministic with their value $r(s,a,t)$ set to with probability $85\%$ and set uniformly at random in $$ otherwise. This construction results in MDPs that have concentrated but non-deterministic transition probabilities and sparse rewards.

Since some algorithms have been proposed assuming the rewards $r(s,a,t)$ are known and we aim for a fair comparison, we assumed for all algorithms that the immediate rewards $r(s,a,t)$ are known and adapted the algorithms accordingly. For example, in UBEV, the $\min\left\{1,\frac{l(s,a,t)}{\max\{1,n(s,a,t)\}}+\phi\right\}$ term was replaced by the true known rewards $r(s,a,t)$ and the $\delta$ parameter in $\phi$ was scaled by $9/7$ accordingly since the concentration result for immediate rewards is not necessary in this case. We used $\delta=\frac{1}{10}$ for all algorithms and $\varepsilon=\frac{1}{10}$ if they require to know $\varepsilon$ beforehand.

We adapted MoRMax, UCRL2, UCFH, MBIE, MedianPAC, Delayed Q-Learning and OIM to the episodic MDP setting with time-dependent transition dynamics by using allowing them to learn time-dependent dynamics and use finite-horizon planning. We did adapt the confidence intervals and but did not re-derive the constants for each algorithm. When in doubt we opted for smaller constants typically resulting better performance of the competitors. We further replaced the range of the value function $O(H)$ by the observed range of the optimistic next state values in the confidence bounds. We also reduced the number of episodes used in the delays by a factor of $\frac{1}{1000}$ for MoRMax and Delayed Q-Learning and by $10^{-6}$ for UCFH because they would otherwise not have performed a single policy update even for $S=5$ within the 10 million episodes we considered. This scaling violates their theoretical guarantees but at least shows that the methods work in principle.

The performance reported in Figure 2 are the expected return of the current policy of each algorithm averaged over $1000$ episodes. The figure shows a single run of the same randomly generated MDP but the results are representative. We reran this experiments with different random seeds and consistently obtained qualitatively similar results.

Source code for the experiments including concise but efficient implementations of the algorithms is available at https://github.com/chrodan/FiniteEpisodicRL.jl.

Appendix C PAC Lower Bound

There exist positive constants $c$, $\delta_{0}>0$, $\varepsilon_{0}>0$ such that for every $\varepsilon\in(0,\varepsilon_{0})$, $S\geq 4,A\geq 2$ and for every algorithm A that and $n\leq\frac{cASH^{3}}{\varepsilon^{2}}$ there is a fixed-horizon episodic MDP $M_{hard}$ with time-dependent transition probabilities and $S$ states and $A$ actions so that returning an $\varepsilon$-optimal policy after $n$ episodes is at most $1-\delta_{0}$. That implies that no algorithm can have a PAC guarantee better than $\Omega\left(\frac{ASH^{3}}{\varepsilon^{2}}\right)$ for sufficiently small $\varepsilon$.

Note that this lower bound on the sample complexity of any method in episodic MDPs with time-dependent dynamics applies to the arbitrary but fixed $\varepsilon$ PAC bound and therefore immediately to the stronger uniform-PAC bounds. This theorem can be proved in the same way as Theorem 5 by Jiang et al. , which itself is a standard construction involving a careful layering of difficult instances of the multi-armed bandit problem.We here only use $H/2$ timesteps for bandits and the remaining $H/2$ time steps to accumulate a reward of $O(H)$ for each bandit For simplicity, we omitted the dependency on the failure probability $\delta$, but using the techniques in the proof of Theorem 26 by Strehl et al. , a lower bound of order $\Omega\left(\frac{ASH^{3}}{\varepsilon^{2}}\log(SA/\delta)\right)$ can be obtained. The lower bound shows for small $\varepsilon$ the sample complexity of UBEV given in Theorem 4 is optimal except for a factor of $H$ and logarithmic terms.

Appendix D Planning Problem of UBEV

The policy update in Lines 1–1 of Algorithm 1 finds an optimal solution to the optimization problem

where $\phi(s,a,t)=\sqrt{\frac{2\operatorname{llnp}(n(s,a,t))+\ln(18SAH/\delta)}{n(s,a,t)}}$ is a confidence bound and $\hat{P}_{k}(s^{\prime}|s,a,t)=m(s^{\prime},s,a,t)/n(s,a,t)$ are the empirical transition probabilities and $\hat{r}_{k}(s,a,t)=l(s,a,t)/n(s,a,t)$ the empirical average rewards.

Hence, UBEV computes an optimal solution to this problem. ∎

Appendix E Details of PAC Analysis

In the following, we provide the formal proof for Theorem 4 and then present all necessary lemmas:

Corollary E.5 ensures that the failure event has probability at most $\delta$. Outside the failure event Lemma E.2 ensures that all but at most $\frac{48A^{2}S^{3}H^{4}}{\varepsilon}\operatorname{polylog}(A,S,H,1/\varepsilon,1/\delta)$ episodes are friendly. Finally, Lemma E.8 shows that all friendly episodes except at most $\left(\frac{9216}{\varepsilon}+417S\right)\frac{ASH^{4}}{\varepsilon}\operatorname{polylog}(A,S,H,1/\varepsilon,1/\delta)$ are $\varepsilon$-optimal. The second bound follows from replacing $AS^{2}$ by $1/\varepsilon$ in the second term. Furthermore, outside the failure event Lemma E.2 ensures that all but at most $\frac{6AS^{2}H^{3}}{\varepsilon}\operatorname{polylog}(A,S,H,1/\varepsilon,1/\delta)$ episodes are nice. Finally, Lemma E.7 shows that all nice episodes except at most $\left(4+S\right)576\frac{ASH^{4}}{\varepsilon}\operatorname{polylog}(A,S,H,1/\varepsilon,1/\delta)$ are $\varepsilon$-optimal.

E.2 Failure Events and Their Probabilities

We now bound the probability of each type of failure event individually:

We can therefore apply Lemma F.1 and conclude that

Applying the union bound over all $s\in\mathcal{S},a\in\mathcal{A}$ and $t\in[H]$, we obtain the desired statement for $F^{V}$. In complete analogy using the same filtration, we can show the statement for $F^{R}$. ∎

Consider first a fix $s^{\prime},s\in\mathcal{S}$, $t\in[H]$ and $a\in\mathcal{A}$. Let $K$ denote the number of times the triple $s,a,t$ was encountered in total during the run of the algorithm. Define the random sequence $X_{i}$ as follows. For $i\leq K$, let $X_{i}$ be the indicator of whether $s^{\prime}$ was the next state when $s,a,t$ was encountered the $i$th time and for $i>K$, let $X_{i}\sim\operatorname{Bernoulli}(P(s^{\prime}|s,a,t))$ be drawn i.i.d. By construction this is a sequence of i.i.d. Bernoulli random variables with mean $P(s^{\prime}|s,a,t)$. Further the event

whose probability can be bounded by $2\delta^{\prime}/S^{2}/A/H$ using Lemma F.2. The statement now follows by applying the union bound. ∎

Using the same argument as in the proof of Corollary E.2 the statement follows from Lemma F.3. ∎

Statement follows directly from Corollary E.1, Corollary E.2, Corollary E.3, Corollary E.4 and the union bound. ∎

E.3 Nice and Friendly Episodes

We now define the notion of nice and the stronger friendly episodes. In nice episodes, all states either have low probability of occuring or the sum of probability of occuring in the previous episodes is large enough so that outside the failure event we can guarantee that

This allows us to then bound the number of nice episodes by the number of times terms of the form

can exceed a chosen threshold (see Lemma E.3 below). In the next section, we will bound the optimality gap of an episode by terms of such form and use the results derived here to bound the number of nice episodes where the algorithm can follow a $\varepsilon$-suboptimal policy. Together with a bound on the number of non-nice episodes, we obtain the sample complexity of UBEV shown in Theorem 4.

Similarly, we use a more refined analysis of the optimality gap of friendly episodes together with Lemma E.4 below to obtain the tighter sample complexity linear-polylog in $S$.

An episode $k$ is nice if and only if for all $s\in\mathcal{S}$, $a\in\mathcal{A}$ and $t\in[H]$ the following two conditions hold:

An episode $k$ is friendly if and only if it is nice and for all $s,s^{\prime}\in\mathcal{S}$, $a,a^{\prime}\in\mathcal{A}$ and $u,t\in[H]$ with $u<t$ the following two conditions hold:

If an episode $k$ is nice, i.e., $k\in N$, then on $F^{c}$ (outside the failure event) for all $s\in\mathcal{S}$, $a\in\mathcal{A}$ and $t\in[H]$ with $u<t$ the following statement holds:

If an episode $k$ is friendly, i.e., $k\in K$, then on $F^{c}$ (outside the failure event) for all $s,s^{\prime}\in\mathcal{S}$, $a,a^{\prime}\in\mathcal{A}$ and $u,t\in[H]$ with $u<t$ the above statement holds as well as

Since we consider the event ${F_{k}^{N}}^{c}$, it holds for all $s,a,t$ triples with $w_{tk}(s,a)>w_{\min}$

for $k\in N$ Further, since we only consider the event ${F_{k}^{CN}}^{c}$,we have for all $s,s^{\prime}\in\mathcal{S}$, $a,a^{\prime}\in\mathcal{A}$, $u,t\in[H]$ with $u<t$ and $w_{uk}^{t}(s,a|s^{\prime},a^{\prime})>w_{\min}$

for $k\in E$. If $n_{uk}(s^{\prime},a^{\prime})=0$ then $n_{tk}(s,a)\geq 0=\frac{1}{4}n_{uk}(s^{\prime},a^{\prime})\sum_{i<k}w_{ui}^{t}(s,a|s^{\prime},a^{\prime})$ holds trivially. Otherwise $n_{uk}(s^{\prime},a^{\prime})\geq 1$ and therefore

On the good event $F^{c}$, the number of episodes that are not friendly is at most

and the number episodes that are not nice is at most

If an episode $k$ is not nice, then there is $s,a,t$ with $w_{tk}(s,a)>w_{\min}$ and $\sum_{i<k}w_{ti}(s,a)<4\ln\frac{SAH}{\delta^{\prime}}$. Since the sum on the left-hand side of this inequality increases by at least $w_{\min}$ when this happens and the right hand side stays constant, this situation can occur at most

times in total. If an episode $k$ is not friendly, it is either not nice or there is $s,a,t$ and $s^{\prime},a^{\prime},u$ with $u<t$ and $w^{t}_{uk}(s^{\prime},a^{\prime}|s,a)>w^{\prime}_{\min}$ and $\sum_{i<k}w_{ui}^{t}(s,a|s^{\prime},a^{\prime})<4\ln\frac{S^{2}A^{2}H^{2}}{\delta^{\prime}}$. Since the sum on the left-hand side of this inequality increases by at least $w^{\prime}_{\min}$ each time this happens while the right hand side stays constant, this can happen at most $\frac{4S^{2}A^{2}H^{2}}{w^{\prime}_{\min}}\ln\frac{S^{2}A^{2}H^{2}}{\delta^{\prime}}$ times in total. Therefore, there can only be at most

Let $r\geq 1$ fix and $C>0$ which can depend polynomially on the relevant quantities and $\varepsilon^{\prime}>0$ and let $D\geq 1$ which can depend poly-logarithmically on the relevant quantities. Then

Using the property in Lemma E.1 of nice episodes as well as the fact that $w_{tk}(s,a)\leq 1$ and $\sum_{i<k}w_{ti}(s,a)\geq 4\ln\frac{SAH}{\delta^{\prime}}\geq 4\ln(2)\geq 2$, we bound

The function $\frac{\operatorname{llnp}(x)+D}{x}$ is monotonically decreasing in $x\geq 0$ since $D\geq 1$ (see Lemma E.6). This allows us to bound

Assume now $\Delta_{k}>\varepsilon^{\prime}$. In this case the right-hand side of the inequality above is also larger than $\varepsilon^{\prime r}$ and there is at least one $(s,a,t)$ with $w_{tk}(s,a)>w_{\min}$ and

Let us denote $C^{\prime}=\frac{8CASH^{r}}{\varepsilon^{\prime r}}$. Since $\frac{\operatorname{llnp}(x)+D}{x}$ is monotonically decreasing and $x=C^{\prime 2}+3C^{\prime}D$ satisfies $\frac{\operatorname{llnp}(x)+D}{x}\leq\frac{\sqrt{x}+D}{x}\leq\frac{1}{C^{\prime}}$, we know that if $\sum_{i\leq k}w_{ti}(s,a)\geq C^{\prime 2}+3C^{\prime}D$ then the above condition cannot be satisfied for $s,a,t$. Since each time the condition is satisfied, it holds that $w_{tk}(s,a)>w_{\min}$ and so $\sum_{i\leq k}w_{ti}(s,a)$ increases by at least $w_{\min}$, it can happen at most

times that $\Delta_{k}>\varepsilon^{\prime}$. Define $K=\{k:\Delta_{k}>\varepsilon^{\prime}\}\cap N$ and we know that $|K|\leq m$. Now we consider the sum

Since each element in $K$ has to contribute at least $\varepsilon^{\prime r}$ to this bound, we can conclude that

Since $\ln\left(\frac{me}{w_{\min}}\right)\left(\operatorname{llnp}\left(C^{\prime 2}+3C^{\prime}D\right)+D\right)$ is $\operatorname{polylog}(S,A,H,\delta^{-1},\varepsilon^{\prime-1})$, the proof is complete. ∎

Let $r\geq 1$ fix and $C>0$ which can depend polynomially on the relevant quantities and $\varepsilon^{\prime}>0$ and let $D\geq 1$ which can depend poly-logarithmically on the relevant quantities. Further $T\subset[H]$ is a subset of time-indices with $u<t$ for all $t\in T$. Then

The proof follows mainly the structure of Lemma E.3. For the sake of completeness, we still present all steps here. Define

Using the property in Lemma E.1 of friendly episodes as well as the fact that $w_{uk}^{t}(s,a|s^{\prime},a^{\prime})\leq 1$ and $\sum_{i<k}w_{ui}^{t}(s,a|s^{\prime},a^{\prime})\geq 4\ln\frac{S^{2}A^{2}H^{2}}{\delta^{\prime}}\geq 4\ln(2)\geq 2$, we bound

The function $\frac{\operatorname{llnp}(x)+D}{x}$ is monotonically decreasing in $x\geq 0$ since $D\geq 1$ (see Lemma E.6). This allows us to bound

where for the last line we used the first and last property in Lemma E.6. For notational convenience, we will use $D^{\prime}=D+1+\operatorname{llnp}(n_{uk}(s^{\prime},a^{\prime}))$. Assume now $\Delta_{k}>\varepsilon^{\prime}\left(\frac{D^{\prime}}{n_{uk}(s^{\prime},a^{\prime})}\right)^{1/r}$. In this case the right-hand side of the inequality above is also larger than $\varepsilon^{\prime r}\left(\frac{D^{\prime}}{n_{uk}(s^{\prime},a^{\prime})}\right)$ and there is at least one $(s,a,t)$ with $w_{uk}^{t}(s,a|s^{\prime},a^{\prime})>w_{\min}$ and

Let us denote $C^{\prime}=\frac{8CAS|T|^{r}}{\varepsilon^{\prime r}}$. Since $\frac{\operatorname{llnp}(x)+D^{\prime}}{x}$ is monotonically decreasing and $x=C^{\prime 2}+3C^{\prime}$ satisfies $\frac{\operatorname{llnp}(x)+D^{\prime}}{x}\leq\frac{\sqrt{x}+D^{\prime}}{x}\leq D^{\prime}\frac{\sqrt{x}+1}{x}\leq\frac{D^{\prime}}{C^{\prime}}$, we know that if $\sum_{i\leq k}w_{ui}^{t}(s,a|s^{\prime},a^{\prime})\geq C^{\prime 2}+3C^{\prime}$ then the above condition cannot be satisfied for $s,a,t$. Since each time the condition is satisfied, it holds that $w_{uk}^{t}(s,a|s^{\prime},a^{\prime})>w_{\min}$ and so $\sum_{i\leq k}w_{ui}^{t}(s,a|s^{\prime},a^{\prime})$ increases by at least $w_{\min}$, it can happen at most

times that $\Delta_{k}>\varepsilon^{\prime}\left(\frac{D^{\prime}}{n_{uk}(s^{\prime},a^{\prime})}\right)^{1/r}$. Define $K=\left\{k:\Delta_{k}>\varepsilon^{\prime}\left(\frac{D^{\prime}}{n_{uk}(s^{\prime},a^{\prime})}\right)^{1/r}\right\}\cap E$ and we know that $|K|\leq m$. Now we consider the sum

Since each element in $K$ has to contribute at least $\frac{D^{\prime}\varepsilon^{\prime r}}{n_{uk}(s^{\prime},a^{\prime})}$ to this bound, we can conclude that

Since $\ln\left(\frac{me}{w_{\min}}\right)\left(\operatorname{llnp}\left(C^{\prime 2}+3C^{\prime}\right)+1\right)$ is $\operatorname{polylog}(S,A,H,\delta^{-1},\varepsilon^{\prime-1})$, the proof is complete. ∎

Let $a_{i}$ be a sequence taking values in $[a_{\min},1]$ with $a_{\min}>0$ and $m>0$, then

Let $f$ be a step-function taking value $a_{i}$ on $[i-1,i)$ for all $i$. We have $F(t):=\int_{0}^{t}f(x)dx=\sum_{i=1}^{t}a_{i}$. By the fundamental theorem of Calculus, we can bound

where the inequality follows from $a_{1}\geq a_{\min}$ and $\sum_{i=1}^{m}a_{i}\leq m$. ∎

$\operatorname{llnp}$ is continuous and nondecreasing.

$\operatorname{llnp}(xy)\leq\operatorname{llnp}(x)+\operatorname{llnp}(y)+1$ for all $x,y\geq 0$.

For $x\leq e$ we have $\operatorname{llnp}(x)=0$ and for $x\geq e$ we have $\operatorname{llnp}(x)=\ln(\ln(x))$ which is continuous and monotonically increasing and $\lim_{x\searrow e}\ln(\ln(x))=0$.

The denominator is always positive in this range so $f$ is monotonically decreasing if and only if $\ln(nx)(D-\ln(\ln(nx)))\geq 1$. Using $D\geq 1$, we have $\ln(nx)(D+\ln(\ln(nx)))\geq 1(1+0)=1$.

First note that for $xy\leq e^{e}$ we have $\operatorname{llnp}(xy)\leq 1\leq\operatorname{llnp}(x)+\operatorname{llnp}(y)+1$ and therfore the statement holds for $x,y\leq e$.

Then consider the case that $x,y\geq e$ and $\operatorname{llnp}(x)+\operatorname{llnp}(y)+1-\operatorname{llnp}(xy)=\ln\ln x+\ln\ln y+1-\ln(\ln(x)+\ln(y))=-\ln(a+b)+1+\ln(a)+\ln(b)$ where $a=\ln x\geq 1$ and $b=\ln y\geq 1$. The function $g(a,b)=-\ln(a+b)+1+\ln(a)+\ln(b)$ is continuous and differentiable with $\frac{\partial g}{\partial a}=\frac{b}{a(a+b)}>0$ and $\frac{\partial g}{\partial b}=\frac{a}{b(a+b)}>0$. Therefore, $g$ attains its minimum on $[1,\infty)\times[1,\infty)$ at $a=1,b=1$. Since $g(1,1)=1-\ln(2)\geq 0$, the statement also holds for $x,y\geq e$.

Finally consider the case where $x\leq e\leq y$. Then $\operatorname{llnp}(xy)\leq\operatorname{llnp}(ey)=\ln(1+\ln y)\leq\ln\ln y+1\leq\operatorname{llnp}(x)+\operatorname{llnp}(y)+1$. Due to symmetry this also holds for $y\leq e\leq x$.

E.4 Decomposition of Optimality Gap

In this section we decompose the optimality gap and then bound each term individually. Finally, both rate lemmas presented in the previous section are used to determine a bound on the number of nice / friendly episodes where the optimality gap can be larger than $\varepsilon$. The decomposition in the following lemma is a the simpler version bounding the number of $\varepsilon$-suboptimal nice episodes and eventually lead to the first bound in Theorem 4.

On the good event $F^{c}$ it holds that $V^{\star}_{1}(s_{0})-V^{\pi_{k}}_{1}(s_{0})\leq\varepsilon$ on all nice episodes $k\in N$ except at most

Using optimism of the algorithm shown in Lemma E.16, we can bound

The first term is bounded by $c_{\varepsilon}\varepsilon=\frac{\varepsilon}{3}$. We now can use Lemma E.9, Lemma E.10 to bound the other terms by

We can then apply Lemma E.3 with $r=2$, $C=8(H+H\sqrt{S}+2)^{2}$, $D=\frac{1}{2}\ln\frac{6SAH}{\delta^{\prime}}$ ($\geq 1$ for any nontrivial setting) and $\varepsilon^{\prime}=2\varepsilon/3$ to bound this term by $\frac{2\varepsilon}{3}$ on all nice episodes except at most

Hence $V^{\star}_{1}(s_{0})-V_{1}^{\pi_{k}}(s_{0})\leq\varepsilon$ holds on all nice episodes except those. ∎

The lemma below is a refined version of the bound above and uses the stronger concept of friendly episodes to eventually lead to the second bound in Theorem 4.

On the good event $F^{c}$ it holds that $p_{0}^{\top}(V_{1}^{\star}-V_{1}^{\pi_{k}})\leq\varepsilon$ on all friendly episodes $E$ except at most

episodes if $\delta^{\prime}\leq\frac{3AS^{2}H}{e^{2}}$.

We can further decompose the optimality gap bound in Equation (147) in the proof of Lemma E.7 as

The second term can be bounded using Lemmas E.11, E.10 and E.9 by

which we bound by $\varepsilon/3$ using Lemma E.3 with $r=2$, $C=32(H+1)^{2}$, $D=\frac{1}{2}\ln\frac{6SAH}{\delta^{\prime}}$ and $\varepsilon^{\prime}=\varepsilon/3$ on all friendly episodes except at most

Finally, we apply Lemma E.12 bound to bound the last term in Equation 156 by $\varepsilon/3$ on all friendly epsiodes but at most

It hence follows that $p_{0}^{\top}(V_{1}^{\star}-V_{1}^{\pi_{k}})\leq\varepsilon$ on all friendly episodes but at most