Minimax Regret Bounds for Reinforcement Learning

Introduction

We consider the reinforcement learning (RL) problem of an agent interacting with an environment in order to maximize its cumulative rewards through time (Burnetas & Katehakis, 1997; Sutton & Barto, 1998). We model the environment as a Markov decision process (MDP) whose transition dynamics are unknown from the agent. As the agent interacts with the environment it observes the states, actions and rewards generated by the system dynamics. This leads to a fundamental trade off: should the agent explore poorly-understood states and actions to gain information and improve future performance, or exploit its knowledge to optimize short-run rewards.

The most common approach to this learning problem is to separate the process of estimation and optimization. In this paradigm, point estimates of the unknown quantities are used in place of the unknown parameters and a plan is made with respect to these estimates. Naive optimization with respect to these point estimates can lead to premature exploitation and so may never learn the optimal policy. Dithering approaches to exploration (e.g., $\epsilon$-greedy) address this failing through random action selection. However, as this exploration is not directed the resultant algorithms may take exponentially long to learn (Kearns & Singh, 2002). In order to learn efficiently it is necessary that the agent prioritizes potentially informative states and actions. To do this, it is important that the agent maintains some notion of its own uncertainty. In some sense, given any prior belief, the optimal solution to this exploration/exploitation dilemma is given by the dynamic programming in the extended Bayesian belief state (Bertsekas, 2007). However, the computational demands of this method become intractable for even small problems (Guez et al., 2013) while finite approximations can be arbitrarily poor (Munos, 2014).

To combat these failings, the majority of provably efficient learning algorithms employ a heuristic principle known as optimism in the face of uncertainty (OFU). In these algorithms, each state and action is afforded some “optimism” such that its imagined value is as high as statistically plausible. The agent then chooses a policy under this optimistic view of the world. This allows for efficient exploration since poorly-understood states and actions are afforded higher optimistic bonus. As the agent resolves its uncertainty, the effects of optimism will reduce and the agent’s policy will approach optimality. Almost all reinforcement learning algorithms with polynomial bounds on sample complexity employ optimism to guide exploration (Kearns & Singh, 2002; Brafman & Tennenholtz, 2002; Strehl et al., 2006; Dann et al., 2017).

An alternative principle motivated by the Thompson sampling (Thompson, 1933) has emerged as a practical competitor to optimism. The algorithm posterior sampling reinforcement learning (PSRL) maintains a posterior distribution for MDPs and, at each episode of interaction, follows a policy which is optimal for a single random sample (Strens, 2000).

Previous works have argue for the potential benefits of such PSRL methods over existing optimistic approaches (Osband et al., 2013; Osband & Van Roy, 2016b) but they come with guarantees on the Bayesian regret only.

However a very recent work Agrawal & Jia (2017) have shown that an optimistic version of posterior sampling (using a max over several samples) achieves a frequentist regret bound $\widetilde{O}(H\sqrt{SAT})$ (for large $T$) in the more general setting of weakly communicating MDPs.

In this paper we present a conceptually simple and computationally efficient approach to optimistic reinforcement learning in finite-horizon MDPs and report results for the frequentist regret. Our algorithm, upper confidence bound value iteration (UCBVI) is similar to model-based interval estimation (MBIE-EB) (Strehl & Littman, 2005) with a delicate alteration to the form of the “exploration bonus”. In particular UCBVI replaces the universal scalar of the bonus in MBIE-EB with the empirical variance of the next-state value function of each state-action pair. This alteration is essential to improve the regret bound from $\widetilde{O}(H)$ to $\widetilde{O}(\sqrt{H})$.

Our key contribution is to establish a high probability regret bound $\widetilde{O}(\sqrt{HSAT}+H^{2}S^{2}A+H\sqrt{T})$ where $S$ is the number of states, $A$ is the number of actions, $H$ is the episode length and $T$ is the total number of time-steps (and where $\widetilde{O}$ ignores logarithmic factors). Importantly, for $T>H^{3}S^{3}A$ and $SA\geq H$ this bound is $\widetilde{O}(\sqrt{HSAT})$, which matches the established lower bound for this problem, up to logarithmic factors (Osband & Van Roy, 2016a).In fact the lower bound of (Jaksch et al., 2010) is for the more general setting of the weakly communicating MDPs and it doesn’t directly apply to our setting. But a similar approach can be used to prove a lower bound of same order for the finite-horizon MDPs, as it is already used in (Osband & Van Roy, 2016a). This positive result is the first of its kind and helps to address an ongoing question about where the fundamental lower bounds lie for reinforcement learning in finite horizon MDPs (Bartlett & Tewari, 2009; Dann & Brunskill, 2015; Osband & Van Roy, 2016a). Our refined analysis contains two key ingredients:

We use careful application of Bernstein and Freedman inequalities (Bernstein, 1927; Freedman, 1975) to the concentration of the optimal value function directly, rather than building confidence sets for the transitions probabilities and rewards, like in UCRL2 (Jaksch et al., 2010) and UCFH (Dann & Brunskill, 2015).

We use empirical-variance exploration bonuses based on Bernstein’s inequality, which together with a recursive Bellman-type Law of Total Variance (LTV) provide tight bounds on the expected sum of the variances of the value estimates, in a similar spirit to the analysis from Azar et al. (2013); Lattimore & Hutter (2012).

At a high level, this work addresses the noted shortcomings of existing RL algorithms (Bartlett & Tewari, 2009; Jaksch et al., 2010; Osband & Van Roy, 2016b), in terms of dependency on $S$ and $H$. We demonstrates that it is possible to design a simple and computationally efficient optimistic algorithm that simultaneously address both the loose scaling in $S$ and $H$ to obtain the first regret bounds that match the $\Omega(\sqrt{HSAT})$ lower bounds as $T$ becomes large.

We should be careful to mention the current limitations of our work, each of which may provide fruitful ground for future research. First, we study the setting of episodic, finite horizon MDPs and not the more general setting of weakly communicating systems (Bartlett & Tewari, 2009; Jaksch et al., 2010). Also we assume that the horizon length $H$ is known to the learner. Further, our bounds only improve over previous scaling $\widetilde{O}(HS\sqrt{AT})$ for $T>H^{3}S^{3}A$.

We hope that this work will serve to elucidate several of the existing shortcomings of exploration in the tabular setting and help further the direction of research towards provably optimal exploration in reinforcement learning.

Problem formulation

In this section, we briefly review some notation, as well as some standard concepts and definitions from the theory of Markov decision processes (MDPs).

We assume $\mathcal{S}$ and $\mathcal{A}$ are finite sets with cardinalities $S$, $A$, respectively. We also assume that the immediate reward $R(x,a)$ is deterministic and belongs to the interval $$.For rewards in$[R_{\min},R_{\max}]$ simply rescale these bounds.

In this paper we focus on the setting where the reward function $R$ is known, but extending our algorithm to unknown stochastic rewards poses no real difficulty.

where $\pi_{k}$ is the control policy followed by the learner at episode $k$. Thus the regret measures the expected loss of following the policy produced by the learner instead of the optimal policy. So the goal of learner is to follow a sequence of policies $\pi_{1},\pi_{2},\dots,\pi_{K}$ such that $\text{Regret}(K)$ is as small as possible.

Upper confidence bound value iteration

In this section we introduce two variants of the algorithm that we investigate in this paper. We call the algorithm upper confidence bound value iteration (UCBVI). UCBVI is an extension of value iteration which guarantees that the resultant value function is a (high-probability) upper confidence bound (UCB) on the optimal value function. This algorithm is related to the model based interval estimation (MBIE-EB) algorithm (Strehl & Littman, 2008). Our key contribution is the precise design of the upper confidence sets, and the analysis which lead to tight regret bounds.

UCBVI, described in Algorithm 1, calls UCB-Q-values (Algorithm 2) which returns UCBs on the Q-values computed by value iteration using an empirical Bellman operator to which is added a confidence bonus bonus. We consider two variants of UCBVI depending on the structure of bonus, which we present in Algorithms 3 and 4.

The first of these UCBVI-CH is based upon Chernoff-Hoeffding’s concentration inequality, considers $\mathtt{UCBVI}$ with $\mathtt{bonus}=\mathtt{bonus\_1}$. $\mathtt{bonus\_1}$ is a very simple bound which only assumes that values are bounded in $[0,H]$. We will see in Theorem 1 that this very simple algorithm can already achieve a regret bound of $\widetilde{O}(H\sqrt{SAT})$, thus improving the best previously known regret bounds from a $S$ to a $\sqrt{S}$ dependence. The intuition for this improved $S$-dependence is that our algorithm (as well as our analysis) does not consider confidence sets on the transition dynamics $P(y|x,a)$ like UCRL2 and UCFH do, but instead directly maintains confidence intervals on the optimal value function. This is crucial as, for any given $(x,a)$, the transition dynamics are $S$-dimensional whereas the Q-value function is one-dimensional.

However, the loose form of UCB given by UCBVI-CH does not look at the value function of the next state, and just consider it as being bounded in $[0,H]$. However, much better bounds can be obtained by looking at the variance of the next state values. Our main result relies upon $\mathtt{UCBVI}$ with $\mathtt{bonus}=\mathtt{bonus\_2}$, which we refer to as UCBVI-BF as it relies on Bernstein-Freedman’s concentration inequalities to build the confidence set. UCBVI-BF builds upon the intuition for UCBVI-CH but also incorporates a variance-dependent exploration bonus. This leads to tighter exploration bonuses and an improved regret bound of $\widetilde{O}(\sqrt{HSAT})$.

Compared to UCBVI-BF here we use a bonus built from the empirical variance of the estimated next values. The idea is that if we had knowledge of the optimal value $V^{*}$, we could build tight confidence bounds using the variance of the optimal value function at the next state in place of the loose bound of $H$. Since however $V^{*}$ is unknown, here we use as a surrogate the empirical variance of the estimated values. As more data is gathered, this variance estimate will converge to the variance of $V^{*}$. Now we need to make sure our estimates $V_{k,h}$ are optimistic (i.e., that they upper bound $V^{*}_{h}$) at all times. This is achieved by adding an additional bonus (last term in $b(x,a)$), which guarantees that we upper bound the variance of $V^{*}$. Now, using an iterative -Bellman-type- Law of Total Variance, we have (see proof) that the sum of the next-state variances of $V^{*}$ (over $H$ time steps) (which is related to the sum of the exploration bonuses over $H$ steps) is bounded by the variance of the $H$-steps return. Thus the size of the bonuses built by UCBVI-BF are constrained over the $H$ steps. And we prove that the sum of those bonuses do not grow linearly in $H$ but in $\sqrt{H}$ only. This is the key for our improved dependence from $H$ to $\sqrt{H}$.

Main results

In this section we present the main results of the paper, which are upper bounds on the regret of UCBVI-CH and UCBVI-BF algorithms. We assume Assumption 1 holds.

Consider a parameter $\delta>0$. Then the regret of UCBVI-CH is bounded w.p. at least $1-\delta$, by

For $T\geq HS^{3}A$ and $SA\geq H$ this bound translates to a regret bound of $\widetilde{O}(H\sqrt{SAT})$, where $T=KH$ is the total number of time-steps at the end of episode $K$.

Theorem 1 is significant in that, for large $T$, it improves the regret dependence from $S$ to $\sqrt{S}$, compared to the best known bound of Jaksch et al. (2010). The main intuition for this improved $S$-dependence is that we bound the estimation error of the next-state value function directly, instead of the transition probabilities.

More precisely, instead of bounding the estimation error $(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})V_{k,h+1}$ by $\|\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}}\|_{1}\|V_{k,h+1}\|_{\infty}$ (as is done in Jaksch et al. (2010) for example), we bound $(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})V^{*}_{h+1}$ instead (for which a bound with no dependence on $S$ can be achieved since $V^{*}$ is deterministic) and handle carefully the correction term $(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})(V_{k,h+1}-V^{*}_{h+1})$.

Our second result, Theorem 2, demonstrates that we can improve upon the $H$-dependence by using a more refined, Bernstein-Friedman-type, exploration bonus.

Consider a parameter $\delta>0$. Then the regret of UCBVI-BF is bounded w.p. $1-\delta$, by

We note that for $T\geq H^{3}S^{3}A$ and $SA\geq H$ this bound translates to a regret bound of $\widetilde{O}(\sqrt{HSAT})$. This result is particularly significant since, for $T$ large enough (i.e., $T\geq H^{3}S^{3}A$), our bound is $\widetilde{O}(\sqrt{HSAT})$ which matches the established lower bound $\Omega(\sqrt{HSAT})$ of (Jaksch et al., 2010; Osband & Van Roy, 2016a) up to logarithmic factors.

The key insight is to apply concentration inequalities to bound the estimation errors and the exploration bonuses in terms of the variance of $V^{*}$ at the next state. We then use the fact that the sum of these variances is bounded by the variance of the return (see e.g., Munos & Moore, 1999; Azar et al., 2013; Lattimore & Hutter, 2012), which shows that the estimation errors accumulate as $\sqrt{H}$ instead of linearly in $H$, thus implying the improved $H$-dependence.

Weakly communicating MDPs

In this short paper we focus on the setting of finite horizon MDPs. By comparison, previous optimistic approaches to exploration, such as UCRL2, provide bounds for the more general setting of weakly communicating MDPs (Jaksch et al., 2010; Bartlett & Tewari, 2009).

However, we believe that much of the insight from the UCBVI algorithm (and its analysis) will carry over to this more general setting using existing techniques such as ‘the doubling trick‘ (Jaksch et al., 2010).

Proof sketch

Here we provide the sketch proof of our results. The full proof is deferred to the appendix.

Let $\Omega=\{V_{k,h}\geq V^{*}_{h},\forall k,h\}$ be the event under which all computed $V_{k,h}$ values are upper bounds on the optimal value function. Using backward induction on $h$ (and standard concentration inequalities) one can prove that $\Omega$ holds with high probability (see Lem. 18 in the appendix). To simplify notations in this sketch of proof we will not make the numerical constants explicit, and instead we will denote by $\square$ a numerical constant which can vary from line to line. The exact values of these constants are provided in the full proof. We will also make use of simplified notations, such as using $L$ to represent the logarithmic term $L=\ln(\square HSAT/\delta)$.

The cumulative regret at episode $K$ is ${\text{Regret}}(K)\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{1\leq k\leq K}V^{*}_{1}(x_{k,1})-V^{\pi_{k}}_{1}(x_{k,1})$. Define $\widetilde{\text{Regret}}(K)\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{1\leq k\leq K}V_{k,1}(x_{k,1})-V^{\pi_{k}}_{1}(x_{k,1})$. Under $\Omega$ we have ${\text{Regret}}(K)\leq\widetilde{\text{Regret}}(K)$, so we now bound $\widetilde{\text{Regret}}(K)$. Define $\Delta_{k,h}\stackrel{{\scriptstyle\rm def}}{{=}}V^{*}_{h}-V^{\pi_{k}}_{h}$ and $\widetilde{\Delta}_{k,h}\stackrel{{\scriptstyle\rm def}}{{=}}V_{k,h}-V^{\pi_{k}}_{h}$. Thus

The difficulty in bounding $(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})V_{k,h+1}$ is that both $V_{k,h+1}$ and $\widehat{P}^{\pi_{k}}_{k}$ are random variables and are not independent (the value function $V_{k,h+1}$ computed at $h+1$ may depend on the samples collected from state $x_{h,k}$), thus a straightforward application of Chernoff-Hoeffding (CH) inequality does not work here. In Jaksch et al. (2010), this issue is addressed by bounding it by $\|\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}}\|_{1}\|V_{k,h+1}\|_{\infty}$ at the price of an additional $\sqrt{S}$.

The main contribution of our $\widetilde{O}(H\sqrt{SAT})$ bound (which removes a $\sqrt{S}$ factor compared to the previous bound of Jaksch et al. (2010)) is to handle this term more properly. Instead of directly bounding $(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})V_{k,h+1}$, we bound $(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})V^{*}_{h+1}$, using straightforward application of CH (which removes the $\sqrt{S}$ factor since $V^{*}_{h+1}$ is deterministic), and deal with the correction term $(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})(V_{k,h+1}-V^{*}_{h+1})$. We have

where $e_{k,h}\stackrel{{\scriptstyle\rm def}}{{=}}(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})V^{*}_{h+1}(x_{k,h})$ is the estimation error of the optimal value function at the next state. Defining $\widetilde{\delta}_{k,h}\stackrel{{\scriptstyle\rm def}}{{=}}\widetilde{\Delta}_{k,h}(x_{k,h})$, we have

where $\epsilon_{k,h}\stackrel{{\scriptstyle\rm def}}{{=}}P^{\pi_{k}}\Delta_{k,h+1}(x_{k,h})-\Delta_{k,h+1}(x_{k,h+1})$.

where $n_{k,h}\stackrel{{\scriptstyle\rm def}}{{=}}N_{k}(x_{k,h},\pi_{k}(x_{k,h}))$. Now considering only the $y$ such that $P^{\pi_{k}}(y|x_{k,h})n_{k,h}\geq\square H^{2}L$, and since $0\leq\Delta_{k,h+1}\leq\widetilde{\Delta}_{k,h+1}$, then $(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})\Delta_{k,h+1}(x_{k,h})$ is bounded by

where \bar{\epsilon}_{k,h}\stackrel{{\scriptstyle\rm def}}{{=}}\sqrt{\frac{\square L}{n_{k,h}}}\Big{(}\sum_{y}P^{\pi_{k}}(y|x_{k,h})\frac{\widetilde{\Delta}_{k,h+1}(y)}{\sqrt{P^{\pi_{k}}(y|x_{k,h})}}-\frac{\widetilde{\delta}_{k,h+1}}{\sqrt{P^{\pi_{k}}(x_{k,h+1}|x_{k,h})}}\Big{)}.

The sum over the neglected $y$ such that $P^{\pi_{k}}(y|x_{k,h})n_{k,h}<\square H^{2}L$ contributes to an additional term

Neglecting this term (and the smaller order term $\square SHL/n_{k,h}$) for now (by the pigeon-hole principle we can prove that these terms contribute to the final regret by a constant at most $\square S^{2}AH^{2}L^{2}$), we have

We now bound those 4 terms. It is easy to check that $\sum_{k,h}\epsilon_{k,h}$ and $\sum_{k,h}\bar{\epsilon}_{k,h}$ are sums of martingale differences, which are bounded using Azuma’s inequality, and lead to a regret of $\widetilde{O}(H\sqrt{T})$ without dependence on the size of state and action space. The leading terms in the regret bound comes from the sum of the exploration bonuses $\sum_{k,h}b_{k,h}$ and the estimation errors $\sum_{k,h}e_{k,h}$.

Using CH, w.h.p. we have $e_{k,h}=(\widehat{P}^{\pi_{k}}_{k}-P^{\pi_{k}})V^{*}_{h+1}\stackrel{{\scriptstyle(CH)}}{{\leq}}\square H\sqrt{\frac{L}{n_{k,h}}}$. Thus this bound on the estimation errors are of the same order as the exploration bonuses (which is the reason we choose those bonuses…).

Plugging Eq. 2 and Eq. 3 into Eq. 1 (and adding the smaller order term) we deduce

2 Sketch Proof of Theorem 2

The proof of Theorem 1 relied on proving by a straightforward induction over $h$ that $\Omega=\{V_{k,h}\geq V^{*}_{h},\forall k,h\}$ hold with high probability. In the case of exploration bonuses defined by:

the backward induction over $h$ is not straightforward. Indeed, if the $V_{k,h+1}$ are upper bounds on $V^{*}_{h+1}$, it is not necessarily the case that the empirical variance of $V_{k,h+1}$ are upper bound on the empirical variance of $V^{*}_{h+1}$. However we can prove by (backward) induction over $h$ that $V_{k,h+1}$ is sufficiently close to $V^{*}_{h+1}$ to guarantee that the variance of those terms are sufficiently close to each other so that the additional bonus (additional bonus in Eq. 4) will make sure that $V_{k,h}$ is still an upper-bound on $V^{*}_{h}$. More precisely, define the set of indices:

and the event $\Omega_{k,h}\stackrel{{\scriptstyle\rm def}}{{=}}\{V_{i,j}\geq V^{*}_{h},(i,j)\in[k,h]_{hist}\}$. Our induction is the following:

Assume that $\Omega_{k,h}$ holds. Then we prove that $(V_{k,h+1}-V^{*}_{h+1})(y)\leq\square H\sqrt{\frac{SAL}{N^{\prime}_{k,h+1}(y)}}$.

So in order to prove that all values computed by the algorithm are upper bounding $V^{*}$, we just need to prove that under $\Omega_{k,h}$, we have $(V_{k,h+1}-V^{*}_{h+1})(y)\leq\min(\square H^{1.5}SL\sqrt{\frac{A}{N^{\prime}_{k,h+1}(y)}},H)$, which is obtained by deriving the following regret bound on

Indeed, since $\{V_{i,h}\}_{i}$ is a decreasing sequence in $i$, we have

Once we have proven that w.h.p., all computed values are upper bounds on $V^{*}$ (i.e. event $\Omega$), then we prove that under $\Omega$, the following regret bound holds:

The proof of Eq. 5 relies on the same derivations as those used for proving Eq. 6. The only two differences being that (i) $HK$ is replaced by $N^{\prime}_{k,h+1}(y)$, the number of times a state $y$ was reached at time $h+1$, up to episode $k$, and (ii) the additional $\sqrt{H}$ factor which comes from the fact that at any episode, $N^{\prime}_{k,h+1}(y)$ can only tick once, whereas the total number of transitions from $y$ during any episode can be as large as $H$. The full proof of Eq. 5 will be given in details in the appendix. We now give a proof sketch of Eq. 6 under $\Omega$.

Similar steps used for proving Theorem 1 apply. The main difference compared to Theorem 1 is the bound on the sum of the exploration bonuses and the estimation errors (which we consider in Steps 3’ and 4’ below). This is where we can remove the $\sqrt{H}$ factor. The use of the Bernstein inequality makes it possible to bound both of those terms in terms of the expected sum of variances (under the current policy $\pi_{k}$ at any episode $k$) of the next-state values (for that policy), and then using recursively the Law of Total Variance to conclude that this quantity is nothing but the variance of the returns. This step is detailed now. For simplicity of the exposition of this sketch we neglect second order terms.

where $(i)$ holds since under $\Omega_{k,h}$, $V_{k,h}\geq V^{*}_{h}\geq V^{\pi_{k}}_{h}$ and $(ii)$ holds due to Chernoff Hoeffding.

(where $n_{k,h}\stackrel{{\scriptstyle\rm def}}{{=}}N_{k}(x_{k,h},\pi_{k}(x_{k,h}))$). Thus from the pigeon-hole principle, $\sum_{k,h}a_{k,h}\leq\square H^{2}S\sqrt{ATL}$.

where $U$ is defined as an upper-bound on the pseudo regret: $U\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{k,h}(b_{k,h}+e_{k,h})+\square H\sqrt{T}$ (an upper bound on the r.h.s. of Eq. 1).

Thus, using Eq. 8, Eq. 7 and the bounds on $\sum a_{k,h}$ and $\sum a^{\prime}_{k,h}$, we deduce that

We now use Bernstein inequality to bound the estimation errors

From Eq. 1 we see that $U\leq\square L\sqrt{(TH+H^{2}U)SA}$ thus $U\leq\square(L\sqrt{HSAT}+H^{2}SAL^{2})$. This implies Eq. 6.

So the reason we are able to remove the $\sqrt{H}$ factor from the regret bound comes from the fact that the sum, over $H$ steps, of the variances of the next state values (which define the amplitude of the confidence intervals) is at most bounded by the variance of the return. Intuitively this means that the size of the confidence intervals do not add up linearly over $H$ steps but grows as $\sqrt{H}$ only. Although the sequence of estimation errors are not independent over time, we are able to demonstrate a concentration of measure phenomenon that shows that those estimation errors concentrate as if they were independent.

Conclusion

In this paper we refine the familiar concept of optimism in the face of uncertainty. Our key contribution is the design and analysis of the algorithm UCBVI-BF , which addresses two key shortcomings in existing algorithms for optimistic exploration in finite MDPs. First we apply a concentration to the value as a whole, rather than the transition estimates, this leads to a reduction from $S$ to $\sqrt{S}$. Next we apply a recursive law of total variance to couple estimates across an episode, rather than at each time step individually, this leads to a reduction from $H$ to $\sqrt{H}$.

Theorem 2 provides the first regret bounds which, for sufficiently large $T$, match the lower bounds for the problem $\widetilde{O}(\sqrt{HSAT})$ up to logarithmic factors. It remains an open problem whether we can match the lower bound using this approach for small $T$. We believe that the higher order term can be improved from $\widetilde{O}(H^{2}S^{2}A)$ to $\widetilde{O}(HS^{2}A)$ by a more careful analysis, i.e., a more extensive use of Freedman-Bernstein inequalities. The same applies to the term of order $H\sqrt{T}$ which can be improved to $\sqrt{HT}$.

These results are particularly significant because they help to estabilish the information-theoretic lower bound of reinforcement learning at $\Omega(\sqrt{HSAT})$ Osband & Van Roy (2016a), whereas it was suggested in some previous work that lower-bound should be of $\Omega(H\sqrt{SAT})$. Moving from this big-picture insight to an analytically rigorous bound is non-trivial. Although we push many of the technical details to the appendix, our paper also makes several contributions in terms of analytical tools that may be useful in subsequent work. In particular we believe that the way we construct the exploration bonus and confidence intervals in UCBVI-CH is novel to the literature of RL. Also the constructive approach in the proof of UCBVI-CH , which bootstraps the regret bounds to prove that $V_{k,h}$s are ucbs, is another analytical contribution of this paper.

Acknowledgements

The authors would like to thank Marc Bellemare and all the other wonderful colleagues at DeepMind for many hours of discussion and insight leading to this research. We are also grateful for the anonymous reviewers for their helpful comments and for fixing several mistakes in an earlier version of this paper.

References

Appendix A Table of Notation

Appendix B Notation

In our analysis we split the episodes into 2 sets: the set of “typical” episodes in which the number of visits to the encountered state-actions are large and the rest of the episodes. We then prove a tight regret bound for the typical episodes. As the total count of other episodes is bounded this technique provides us with the desired result. The set of typical state-actions pairs for every episode $k$ is defined as follows

Based on the definition of ${[(x,a)]}_{\text{typ}}$ we define the set of typical episodes and the set of typical state-dependent episodes as follow

Also for every $(x,a)\in\mathcal{S}\times\mathcal{A}$ the set of typical next states at every episode $k$ is defined as follows

Finally let denote $[y]_{k,h}=[y]_{k,x_{k,h},\pi_{k}(x_{x_{k,h}})}$ for every $k\in[K]$ and $h\in[H]$.

B.2 Surrogate regrets

We also define the corresponding per state-step regret and upper-bound regret for every state $x\in\mathcal{X}$ and step $h\in[H]$, respectively, as follows

B.3 Martingale difference sequences

In our analysis we rely heavily on the theory of martingale sequences to prove bound on the regret incurred due to encountering a random sequence of states. We now provide some definitions and notation in that regard.

We define the following martingale operator for every $k\in[K]$, $h\in[H]$ and $F:\mathcal{S}\to\Re$. Also let $t=(k-1)H+h$ denote the time stamp at step $h$ of episode $k$ then

Let define $\Delta_{\text{typ},k,h}:\mathcal{S}\to\Re$ as follows for every $k\in[K]$ and $h\in[H]$ and $y\in\mathcal{S}$

B.4 High probability events

We now introduce the high probability events $\mathcal{E}$ and $\Omega_{k,h}$ under which the regret is small.

Let use the shorthand notation $L\stackrel{{\scriptstyle\rm def}}{{=}}\ln\left(\frac{5SAT}{\delta}\right)$. Also for every $v>0$, $p\in$ and $n>0$ let define the confidence intervals $c_{1}$, $c_{2}$ and $c_{3}$, respectively, as follow

Let $\mathcal{P}$ be the set of all probability distributions on $\mathcal{S}$. Define the following confidence set for every $k=1,\dots,K$, $n>0$ and $(x,a)\in\mathcal{S}\times\mathcal{A}$

We now define the random event $\mathcal{E}_{\widehat{P}}$ as follows

Let $t$ be a positive integer. Let $\mathcal{F}=\{f_{s}\}_{s\in[t]}$ be a set of real-value functions on $\mathcal{H}_{t+s}$, for some integer $s>0$. We now define the following random events for every $\bar{w}>0$ and $\bar{u}>0$ and $\bar{c}>0$:

We also use the short-hand notation $\mathcal{E}_{\text{az}}(\mathcal{F},\bar{u})$ and $\mathcal{E}_{\text{fr}}(\mathcal{F},\bar{w},\bar{u})$ for $\mathcal{E}_{\text{az}}(\mathcal{F},\bar{u},L)$ and $\mathcal{E}_{\text{fr}}(\mathcal{F},\bar{w},\bar{u},L)$, respectively.

Now let define the following sets of random variables for every $k\in[K]$ and $h\in[H]$:

We now define the high probability event $\mathcal{E}$ as follows

The following lemma shows that the event $\mathcal{E}$ holds with high probability:

Let $\delta>0$ be a real scalar. Then the event $\mathcal{E}$ holds w.p. at least $1-\delta$.

To prove this result we need to show that a set of concentration inequalities with regard to the empirical model $\widehat{P}_{k}$ holds simultaneously. For every $h\in[H]$ the Bernstein inequality combined with a union bound argument, to take into account that $N_{k}(x,a)\in[T]$ is a random number, leads to the following inequality w.p. $1-\delta$ (see, e.g., Cesa-Bianchi & Lugosi, 2006; Bubeck & Cesa-Bianchi, 2012, for the statement of the Bernstein inequality and the application of the union bound in similar cases, respectively.)

where we rely on the fact that $V^{*}_{h}$ is uniformly bounded by $H$. Using the same argument but this time with the Empirical Bernstein inequality (see, e.g., Maurer & Pontil, 2009), for $N_{k}(x,a)>1$, leads to

The Bernstein inequality combined with a union bound argument on $N_{k}(x,a)$ also implies the following bound w.p. $1-\delta$

which implies the following bound w.p. $1-\delta$:

We now focus on bounding the sequence of martingales. Let $n>0$ be an integer and $u,\delta>0$ be some real scalars. Let the sequence of random variables $\{X_{1},X_{2},\dots,X_{n}\}$ be a sequence of martingale differences w.r.t. to some filtration $\mathcal{F}_{n}$. Let this sequence be uniformly bounded from above and below by $u$. Then the Azuma’s inequality (see, e.g., Cesa-Bianchi & Lugosi, 2006) implies that w.p. $1-\delta$

When the sum of the variances $\sum_{i=1}^{n}\text{Var}(X_{i}|\mathcal{F}_{i})\leq w$ for some $w>0$ then the following sharper bound due to Freedman (1975) holds w.p. $1-\delta$

Let $k\in[K]$, $h\in[H]$ and $x\in\mathcal{X}$. Then the inequality of Eq. 13 immediately implies that the following events holds w.p. $1-\delta$:

Also Eq. 13 combined with a union bound argument over all $N^{\prime}_{k,h}(x)\in[T]$ (see, e.g., Bubeck et al., 2011, for the full description of the application of union bound argument in the case of martigale process with random stopping time) implies that the following events hold w.p. $1-\delta$

Similarly the inequality of Eq. 14 leads to the following events hold w.p. $1-\delta$

where $\bar{w}_{k,h}$ and $\bar{w}_{k,h,x}$ are upper bounds on $W_{k,h}$ and $W_{k,h,x}$, respectively, defined as

So to establish a value for $\bar{w}_{k,h}$ and $\bar{w}_{k,h,x}$ we need to prove bound on $W_{k,h}$ and $W_{k,h,x}$. Here we only prove this bound for $W_{k,h}$ as the proof techniques to bound $W_{k,h,x}$ is identical to the way we bound $W_{k,h}$.

Now let the sequence $\{x_{1},x_{2},\dots,x_{H}\}$ be the sequence of states encountered by following some policy $\pi$ throughout an episode $k$. Then the recursive application of LTV leads to (see e.g., Munos & Moore, 1999; Lattimore & Hutter, 2012, for the proof.)

By combining Eq. 26 into Eq. 25 we deduce

Similarly the following bound holds on $W_{k,h,x}$

Plugging the bounds of Eq. 27 and Eq. 28 in to the bounds of Eq. 21 and Eq. 22 and a union bound over all $N_{k,h}(x)\in[T]$ leads to the following events hold w.p. $1-\delta$:

Combining the results of Eq. 9, Eq. 10, Eq. 11, Eq. 12, Eq. 15, Eq. 16 Eq. 17, Eq. 18, Eq. 19, Eq. 20, Eq. 29 and Eq. 30 and taking a union bound over these random events as well as all possible $k\in[K]$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$ proves the result.

Let $k\in[K]$ and $h\in[H]$. Denote the set of steps for which the value functions are obtained before $V_{k,h}$ as

Let $\Omega_{k,h}=\{V_{i,j}\geq V^{*}_{h},\forall(i,j)\in[k,h]_{\text{hist}}\}$ be the event under which $V_{i,j}$ prior to $V_{k,h}$ computation are upper bounds on the optimal value functions. Using backward induction on $h$ (and standard concentration inequalities) we will prove that $\Omega_{k,h}$ holds under the event $\mathcal{E}$ (see Lem. 19).

B.5 Other useful notation

Here we define some other notation that we use throughout the proof. We denote the total count of steps up to episode $k\in[K]$ by $T_{k}\stackrel{{\scriptstyle\rm def}}{{=}}H(k-1)$. We first define $c_{4,k,h}$, for every $h\in[H]$ and $k\in[K]$, as follow

for every $k\in[K]$ , $h\in[H]$ and $x\in[x]$ we also introduce the following notation which we use later when we sum up the regret:

where $c_{1,k,h}$ is the shorthand-notation for $c_{1}(v^{*}_{k,h},n_{k,h})$. We also define the upper bound $U_{k,h}$ and $U_{k,h,x}$ for every $k\in[K]$ , $h\in[H]$ and $x\in\mathcal{S}$ as follows, respectively

Appendix C Proof of the Regret Bounds

Before we start the main analysis we state the following useful lemma that will be used frequently in the analysis:

The following sequence of inequalities hold

The result follows from the definition of variance. ∎

We proceed by proving the following key lemma which shows that proves bound on $\Delta_{k,h}$ under the assumption that $V_{k,h}$ is UCB w.r.t. $V^{*}_{h}$.

Let $k\in[K]$ and $h\in[H]$. Let the events $\mathcal{E}$ and $\Omega_{k,h}$ hold. Then the following bound holds on $\delta_{k,h}$ and $\widetilde{\delta}_{k,h}$:

For the ease of exposition we abuse the notation and drop the dependencies on $k$, e.g., we write $x_{1}$, $\pi$ and $V_{1}$ for $x_{k,1}$, $\pi_{k}$ and $V_{k,1}$, respectively. We proceed by bounding $\widetilde{\delta}_{h}$ under the event $\mathcal{E}$ at every step $0<h<H$:

where the last inequality follows from the fact that under the event $\mathcal{E}$ we have that $[(\widehat{P}^{\pi}_{h}-P^{\pi}_{h})V^{*}_{h+1}](x_{h})\leq c_{1,h}$. We now bound $(a)$:

where $(I)$ holds under the event $\mathcal{E}$. We proceed by bounding $(b)$:

where in the last line we rely on the definition of $[y]_{h}$. We now bound (d):

By combining Eq. 34 and Eq. 35 into Eq. 33 we deduce

By combining Eq. 36 and Eq. C into Eq. C we deduce

Let denote $\gamma_{h}=(1+1/H)^{h}$. The previous bound combined with an induction argument implies that

The inequality $\ln(1+x)\leq x$ for every $x>-1$ leads to $\gamma_{h}\leq\gamma_{H}\leq e$ for every $h\in[H]$. This combined with the assumption that $v_{h}\geq v^{*}_{h}$ under the event $\Omega_{h}$ completes the proof. ∎

Let $k\in[k]$ and $h\in[H]$. Let the events $\mathcal{E}$ and $\Omega_{k,h}$ hold. Then

The proof follows by summing up the bounds of Lem. 3 and taking into acoount the fact if $\Omega_{k,h}$ holds then $\Omega_{i,j}$ for all $(i,j)\in[k,h]_{hist}$ hold. ∎

To simplify the bound of Lem. 4 we prove bound on sum of the martingales $\varepsilon_{k,h}$ and $\bar{\varepsilon}_{k,h}$

Let $k\in[k]$ and $h\in[H]$. Let the events $\mathcal{E}$ and $\Omega_{k,h}$ hold. Then the following bound holds

Also the following bounds holds for every $x\in\mathcal{X}$ and $h\in\mathcal{H}$:

The fact that the event $\mathcal{E}$ holds implies that the events $\mathcal{E}_{\text{az}}(\mathcal{F}_{\widetilde{\Delta},k,h},H)$, $\mathcal{E}_{\text{az}}(\mathcal{F}^{\prime}_{\widetilde{\Delta},k,h},\frac{1}{\sqrt{L}})$ , $\mathcal{E}_{\text{az}}(\mathcal{F}_{\widetilde{\Delta},k,h,x},H)$ and $\mathcal{E}_{\text{az}}(\mathcal{F}^{\prime}_{\widetilde{\Delta},x,k,h},\frac{1}{\sqrt{L}})$ hold. Under these events the inequalities of the statement hold. This combined with the fact that $(H-h)k\leq T_{k}$ completes the proof.

We now bound the sum of $\delta$s in terms of the upper-bound $U$:

Let $k\in[K]$ and $h\in[H]$. Let the events $\mathcal{E}$ and $\Omega_{k,h}$ holds. Then the following bounds hold for every $h\in[H]$ $x\in\mathcal{S}$

The proof follows by incorporating the result of Lem. 5 into Lem. 4 and taking into account that for every $h\in[H]$ the term $U_{k,h}$ ($U_{k,h,x}$) is a summation of non-negative terms which are also contained in $U_{k,1}$ ($U_{1,h,x}$). ∎

Let $k\in[K]$ and $h\in[H]$. Let the events $\mathcal{E}$ and $\Omega_{k,h}$ holds. Then the following bounds hold for every $x\in\mathcal{S}$

The proof follows by summing up the bounds of Lem. 6. ∎

We now focus on bounding the terms $C_{k,h}$ ($C_{k,h,x}$) and $B_{k,h}$ ($B_{k,h,x}$) in Lem. 11 and Lem. 12, respectively. Before we proceed with the proof of Lem. 11 and Lem. 12. we prove the following key result which bounds sum of the variances of $V^{\pi}_{k,h}$ using an LTV argument:

Let $k\in[K]$ and $h\in[H]$. Then under the events $\mathcal{E}$ and $\Omega_{k,h}$ the following hold for every $x\in\mathcal{S}$

Eq. 41 and Eq. 42 combined with Eq. 43 and Eq. 44, respectively, complete the proof.

Let $k\in[K]$ and $h\in[H]$. Then under the events $\mathcal{E}$ and $\Omega_{k,h}$ the following hold for every $x\in\mathcal{S}$

We begin by the following sequence of inequalities:

where $(I)$ is obtained from the definition of the variance as well as the fact that $V^{*}_{i,j}\geq V^{\pi}_{k,h}$. The last line also follows from the fact that $V^{\pi_{k}}\leq V^{*}_{h}\leq H$.

Using an identical argument we can also prove the following bound for state-dependent difference:

To bound $(a)$ we use the fact that under the event $\mathcal{E}$ the event $\mathcal{E}_{\text{az}}(\mathcal{F}_{\widetilde{\Delta},k,h},H)$ also holds. This combined with the fact that under the event $\Omega_{k,h}$ the inequality $\delta_{k,h}\leq\widetilde{\delta}_{k,h}$ holds implies that

where in the last line we rely on the result of Lem. 7. Similarly we can prove the following bound for $(b)$ under the events $\Omega_{k,h}$ and $\mathcal{E}_{\text{az}}(\mathcal{F}_{\widetilde{\Delta},k,h,x},H)$:

The result then follows by incorporating the results of Eq. 49 and Eq. 50 into Eq. 47 and Eq. 48, respectively.

Let $k\in[K]$ and $h\in[H]$. Then under the events $\mathcal{E}$ and $\Omega_{k,h}$ the following hold for every $x\in\mathcal{S}$

Here we only prove the bound on Eq. 51. The proof for the bound of Eq. 52 can be done in a very similar manner, as it is shown in the previous lemmas (the only difference is that $HN^{\prime}_{k,h}(x)$ and $U_{k,h,x}$ replace $T_{k}$ and $U_{k,1}$, respectively). The following sequence of inequalities hold:

where $(I)$ holds due to the fact that under $\Omega_{k,h}$, $V_{i,j}\geq V^{*}_{j}\geq V^{\pi_{i}}_{j}$ and $(II)$ holds under the event $\mathcal{E}$.

where $(I)$ holds under the event $\mathcal{E}$ and $(II)$ holds due to the pigeon-hole argument (see, e.g., Jaksch et al., 2010, for the proof).

Using an identical analysis to the one in Lem. 10 and taking into account that $V_{i,j}\geq V^{*}_{j}$ under the event $\Omega_{k,h}$ and $\mathcal{E}$ we can bound $(b)$

where $(I)$ holds since under the event $\mathcal{E}$ the event $\mathcal{E}_{az}(\mathcal{F}_{\widetilde{\Delta},k,h},H)$ holds. Another application of pigeon-hole principle leads to a bound of $6H^{2}\sqrt{SAT_{k}L}$ on $(c)$. We then combine this with the bounds on $(a)$ and $(b)$ to bound Eq. 53, which proves the result.

Let $k\in[K]$ and $h\in[H]$. Then under the events $\mathcal{E}$ and $\Omega_{k,h}$ the following hold for every $x\in\mathcal{S}$

Here we only prove the bound on Eq. 54. The proof for the bound of Eq. 55 can be done in a very similar manner, as it is shown in the previous lemmas (the only difference is that $HN^{\prime}_{k,h}(x)$ and $U_{k,h,x}$ replace $T_{k}$ and $U_{k,1}$, respectively). The Cauchy–Schwarz inequality leads to the following sequence of inequalities:

We now prove bounds on $(a)$ and $(b)$ respectively

$(c)$ and $(d)$ can be bounded under the events $\mathcal{E}$ and $\Omega_{k,h}$ using the results of Lem. 8 and Lem.9. We then deduce

where the last line follows by the fact that for the typical episodes $T_{k}\geq 250H^{2}S^{2}AL^{2}$. Thus if $T_{k}\leq H^{2}L$ the term $C_{k,h}$ trivially equals to otherwise the higher order terms are bounded by $O(HT_{k})$.

We now bound $(b)$ using a pigeon-hole argument

Plugging the bound on $(a)$ and $(b)$ into Eq. 56 and taking in to account that for the typical episodes $[k]_{\text{typ}}$ we have that $T\geq H^{2}L$ completes the proof.

Let $k\in[K]$ and $h\in[H]$. Let the bonus is defined according to Algo. 4. Then under the events $\mathcal{E}$ and $\Omega_{k,h}$ the following hold for every $x\in\mathcal{S}$,

Here we only prove the bound on Eq. 58. The proof for the bound of Eq. 59 can be done in a very similar manner, as it is shown in the previous lemmas (the only difference is that $HN^{\prime}_{k,h}(x)$ and $U_{k,h,x}$ replace $T_{k}$ and $U_{k,1}$, respectively). We first notice that the following holds:

The bound on $(d)$ is identical to the corresponding bound in Lem. 11. So we only focus on bounding $(c)$:

$(e)$ and $(f)$ can be bounded in high probability using the results of Lem. 8 and Lem.10. This implies

where the last line follows by the fact that for the typical episodes $T_{k}\geq 250H^{2}S^{2}AL$. Thus if $T_{k}\leq 250H^{2}S^{2}L$ then $B_{k,h}$ trivially equals to otherwise the higher order terms are bounded by $O(HT)$. Combining the bound on $(b)$ and $(c)$ leads to the following bound on $(a)$:

To bound $(b)$ we make use of Cauchy-Schwarz inequality again.

The term $(h)$ bounded by $2SAL$ using a pigeon-hole argument (see Lem. 11). We proceed by bounding $(g)$:

Given that the event $\mathcal{E}$ holds the term $(i)$ bounded by $2\sqrt{2}H^{2}S\sqrt{ALT_{k}}$ by using the pigeon-hole argument. Under the event $\mathcal{E}$ the event $\mathcal{E}_{az}(\mathcal{F}_{b^{\prime},k,h},H^{2})$ holds. This implies that the term $(j)$ is also bounded by $2H^{2}\sqrt{T_{k}L}$ as it is sum of the martingale differences. The term $(k)$ is also bounded by $20000H^{3}S^{3}A^{3}L^{3}$ using the pigeon-hole argument. Combining all these bounds together leads to the following bound on $(b)$

Combining this with the bound on $(a)$ and taking into account the fact that we only bound the $B_{k,h}$ for the typical episodes, in which $T_{k}\geq 250H^{2}S^{2}AL^{2}$, completes the proof.

Let the bonus is defined according to Algo. 4. Then under the events $\mathcal{E}$ and $\Omega_{K,1}$ the following hold

We first notice that $\text{Regret}(K)$ and $\text{Regret}(K)$ are bounded by $U_{k,1}$ due to Lem.6. To bound $U_{k,1}$ we sum up the regret due to $B_{k,h}$ and $C_{k,h}$ from Lem. 11 and Lem. 12. We also bound the sum $\sum_{k=1}^{K}\sum_{h=1}^{H}c_{4,k,h}$ by $2HSAL$ using a pigeon hole argument. We also note that $B_{k,h}$ and $C_{k,h}$ only account for the regret of typical episodes in which $T\geq H^{2}S^{2}A^{2}L$. The regret of those episodes which do not belong to the typical set $[k]_{\text{typ}}$, can be bounded by $O(H^{2}S^{2}A^{2}L^{2})$, trivially. ∎

The following lemma establishes an explicit bound on the regret:

Let the bonus is defined according to Algo. 4. Then under the events $\mathcal{E}$ and $\Omega_{K,1}$ the following hold

The proof follows by solving the bound of Lem. 13 in terms of $U_{k,1}$. which only contributes to the additional regret of $O(H^{2}L^{2}SA)$. ∎

Let the bonus is defined according to Algo. 3. Then under the events $\mathcal{E}$ and $\Omega_{K,1}$ the following holds

The proof up to Lem. 11 is identical to the proof of Lem. 14. The main difference is to prove bound on $C_{k,h}$ and $B_{k,h}$ here we use a loose bound of $O(H\sqrt{\frac{SAL}{n_{k,h}}})$ for both exploration bonus $b_{k,h}$ and the confidence interval $c_{1,k,h}$ and then sum these terms using a pigeon-hole argument (The proof is provided in Jaksch et al., 2010) which leads to a bound of $O(H\sqrt{SATL})$ on both $B_{K,1}$ and $C_{K,1}$. Plugging these results into the bound of Lem. 7 combined with the regret of non-typical episodes complete the proof

Let the bonus is defined according to Algo. 4. Let $k\in[K]$ and $h\in[H]$. Then under the events $\mathcal{E}$ and $\Omega_{k,h}$ the following hold for every $x\in\mathcal{S}$,

The proof is similar to the proof of total regret. Here also we use Lem. 12, Lem. 11 and a pigeon-hole argument to bound the regrets due to $B_{k,h}$, $C_{k,h}$ and $c_{4,k,h}$. We then incorporate these terms into Lem.6 to bound the regret in terms of $U_{k,h,x}$. The result follows by solving the bound w.r.t. the upper bound $U_{k,h,x}$. ∎

Let the bonus $b$ is defined according to Algo. 4. Let $k\in[K]$ and $h\in[H]$. Then under the events $\mathcal{E}$ and $\Omega_{k,h}$ the following hold for every $x\in\mathcal{S}$

where the last inequality holds due to the fact that $V_{k,h}$ by definition is monotonically non-increasing in $k$. The proof then follows by collecting terms.

Let the bonus $b$ is defined according to Algo. 3. Then under the event $\mathcal{E}$ the set of events $\{\Omega_{k,h}\}_{k\in[K],h\in H}$ hold.

We prove this result by induction. First we notice that for $h=H$ by definition $V_{k,h}=V^{*}_{h}$ thus the inequality $V_{k,h}\geq V^{*}_{h}$ trivially holds. Thus to prove this result for $h<H$ we only need to show that if the inequality $V_{k,h}\geq V^{*}_{h}$ holds for $h$ it also holds for $h-1$ for every $h<H$:

where the last line follows by the induction condition that $V_{k,h+1}\geq V^{*}_{h+1}$. The fact that the event $\mathcal{E}$ hols implies that $(P^{\pi^{*}}_{h}-\widehat{P}^{\pi^{*}}_{k,h})V^{*}_{h+1}(x)\leq c_{1}(N_{k}(x,\pi^{*}_{h}(x)))\leq b_{k}(x,\pi^{*}_{h}(x))$, which completes the proof.

Let the bonus $b$ is defined according to Algo. 4. Then under the event $\mathcal{E}$ the set of events $\{\Omega_{k,h}\}_{k\in[K],h\in H}$ hold.

We prove this result by induction. We first notice that in the case of the first episode $V_{1,h}=H\geq V^{*}_{h}$.

To prove this result by induction in the case of $1<k\in[K]$ we need to show that in the case of $h\in[H-1]$ if $\Omega_{k,h+1}$ holds then $\Omega_{k,h}$ also holds.