Adaptive Sampling for Best Policy Identification in Markov Decision Processes

INTRODUCTION

Reinforcement Learning (RL) algorithms are designed to interact with an unknown stochastic dynamical system, and through this interaction, to identify, as fast as possible, an optimal control policy. The efficiency of these algorithms is usually measured through their sample complexity, defined as the number of samples (the number of times the algorithm interacts with the system) required to identify an optimal policy with some prescribed levels of accuracy and certainty. This paper, as most related work in this field, focuses on systems and control objectives that are modelled as a standard discounted Markov Decision Processes (MDPs) with finite state and action spaces. Various interaction models have been investigated, but sample complexity analyses have been mainly conducted under the so-called generative model, where in each step, the algorithm may sample a transition and a reward from any given (state, action) pair. We also restrict our attention to this model.

We investigate the design of RL algorithms with minimal sample complexity. This problem has attracted a lot of attention over the last two decades. Most studies follow a minimax approach. For example, it is known Gheshlaghi Azar et al., (2013) that for the worst possible MDP, identifying an $\varepsilon$-optimal policy with probability $1-\delta$ requires at least ${SA\over\varepsilon^{2}(1-\gamma)^{3}}\log({SA\over\delta})$ samples, where $S$ and $A$ are the number of states and actions, respectively, and $\gamma$ is the discount factor. Note that to obtain this sample complexity lower bound, one needs to design a very specific worst-case MDP (in particular, its transition probabilities must depend on $\varepsilon$ and $\gamma$). Since the aforementioned minimax lower bound appeared, most researchers have been aiming at devising algorithms matching this bound. In contrast, we are interested in analyzing the minimal problem-specific sample complexity. Specifically, we seek to understand the dependence of the sample complexity on the MDP that has to be learnt. Problem-specific performance metrics are much more informative than their minimax counterparts, because they encode and express the inherent hardness of the MDP. Minimax metrics just represent the hardness of the worst MDP. In particular, establishing that the sample complexity of an algorithm does not exceed the minimax lower bound just reveals that the algorithm performs well for this worst MDP. However, it does not indicate whether the algorithm adapts to the hardness of the MDP, i.e., whether the optimal policy of a very easy MDP would be learnt very quickly. As a matter of fact, an algorithm with sample complexity matching the minimax lower bound just consists in sampling (state, action) pairs uniformly at random, and is not adapting to the MDP.

The problem-specific sample complexity of identifying the best arm in stochastic Multi-Armed Bandit (MAB) problems is now well understood Garivier and Kaufmann, (2016). In this work, we explore whether the methodology used in Garivier and Kaufmann, (2016) for MAB problems can be extended to RL problems. This methodology consists in first deriving a problem-specific sample complexity lower bound. The latter should reveal the sample allocation leading to the minimal sample complexity. One may then devise a track-and-stop algorithm that (i) tracks the optimal sample allocation identified in the lower bound, and (ii) stops when the information gathered is judged sufficient to get the desired PAC guarantees. As it turns out, extending this methodology to RL problems raises fundamental issues, mainly due to the difficulty of computing the sample allocation leading to the minimal problem-specific sample complexity. We propose a set of tools to solve these issues. Our contributions are as follows:

1. We derive a problem-specific sample complexity lower bound for identifying an optimal policy in a given MDP $\phi$. This bound is expressed as $T^{*}(\phi)\log(1/\delta)$, where the characteristic time $T^{*}(\phi)$ encodes the hardness of the MDP $\phi$. $T^{*}(\phi)$ is the value of a complex non-convex optimization problem. This complexity makes the design of a track-and-stop algorithm similar to that proposed in Garivier and Kaufmann, (2016) and achieving the sample complexity lower bound elusive. To circumvent this difficulty, we derive an explicit upper bound $U(\phi)$ of $T^{*}(\phi)$. The advantage of $U(\phi)$ is two-fold: (i) $U(\phi)$ remains problem-specific, and explicitly depends on functionals of the MDP characterizing its hardness. (ii) $U(\phi)$ corresponds to an explicit and simple sample allocation. This allows us to devise a procedure that tracks this allocation.

2. Based on our upper bound analysis, we devise KLB-TS (KL Ball Track-and-Stop), an algorithm whose sample complexity is at most $U(\phi)\log(1/\delta)$. Our algorithm relies on a procedure tracking the sample allocation leading to $U(\phi)$, and a stopping rule that we refer to as KL Ball Stopping rule because of its analogy to the way we derive the upper bound $U(\phi)$.

3. We highlight the differences of our design approach compared to that leading to BESPOKE Zanette et al., (2019), a recently proposed adaptive algorithm. As it turns out, the adaptive part of BESPOKE is very limited in practice (see related work and Appendix H for details), and KLB-TS exhibits a much better performance numerically.

RELATED WORK

Most work on the best policy identification in MDPs with a generative model adopt a minimax approach Kearns and Singh, (1999), Kakade, (2003), even2006action, Gheshlaghi Azar et al., (2013), NIPS2018_7765, pmlr-v125-agarwal20b, Li et al., (2020). In the most recent of these papers Li et al., (2020), the authors propose an algorithm whose sample complexity achieves the minimax lower bound of Gheshlaghi Azar et al., (2013) for a wide range of values of $\varepsilon$, namely for $\varepsilon\in(0,\frac{1}{1-\gamma}]$. Refer to the appendix for a detailed account on the minimax framework.

PRELIMINARIES AND NOTATION

We investigate the optimal control of dynamical systems modelled as an infinite time-horizon MDP with finite state space ${\cal S}$ and finite action spaces ${\cal A}_{s}$ for any $s\in{\cal S}$. Let $\mathcal{A}=\cup_{s\in\mathcal{S}}\mathcal{A}_{s}$. The MDP is defined by its kernels: $\phi=(p_{\phi},q_{\phi})$, where $p_{\phi}$ captures the system dynamics and $q_{\phi}$ the random collected rewards. Specifically, $p_{\phi}(s^{\prime}|s,a)$ denotes the probability of the system to be in state $s^{\prime}$ after taking the action $a\in{\cal A}_{s}$ in state $s$. Let $p_{\phi}(s,a)=(p_{\phi}(s^{\prime}|s,a))_{s^{\prime}}$. $q_{\phi}(\cdot|s,a)$ or simply $q_{\phi}(s,a)$ is the density of the distribution of the reward collected in state $s$ when action $a$ is selected, w.r.t. some positive measure $\lambda$ with support included in $$. Let$r_{\phi}(s,a)$denote the expected reward collected in state$s$when action$a$is selected,$r_{\phi}(s,a)=\int_{0}^{1}Rq_{\phi}(R|s,a)\lambda(dR)$.

Assumption 1. To simplify notation and the analysis, we assume that $\phi$ admits a unique optimal control policy denoted by $\pi_{\phi}^{\star}$. This means that $\phi\in\Phi=\{\phi:|\Pi_{\phi}^{\star}|=1\}$.

2 Best-policy identification

Sampling rule. In round $t$, the algorithm $\chi$ selects a (state, action) pair $(s_{t},a_{t})$ to explore, depending on past observations. $(s_{t},a_{t})$ is ${\cal F}_{t-1}^{\chi}$-measurable. $\chi$ observes the next state denoted by $s_{t}^{\prime}$ and a random reward $R_{t}$. Note that any admissible (state, action) pair may be selected (we consider a generative model).

Stopping and decision rules. After gathering enough information, $\chi$ may decide to stop sampling and to return an estimated best policy. The algorithm stops after collecting $\tau$ samples, and $\tau$ is a stopping time w.r.t. the filtration $({\cal F}_{t}^{\chi})_{t\geq 1}$. The estimated best policy $\hat{\pi}$ is then ${\cal F}_{\tau}^{\chi}$-measurable. $\tau$ is referred to as the sample complexity of $\chi$.

3 Additional notation

PROBLEM-SPECIFIC SAMPLE COMPLEXITY LOWER BOUND

To derive a problem-specific sample complexity lower bound, we use classical change-of-measure arguments as those leveraged towards regret and sample complexity lower bounds Lai and Robbins, (1985); Garivier and Kaufmann, (2016) in bandit problems. These arguments lead to constraints on the expected numbers of times each (state, action) pair should be explored under any $\delta$-PAC algorithm.

Let $\psi\in\operatorname{Alt}(\phi)$ be an alternative MDP and consider a $\delta$-PAC algorithm. We denote by $O_{\tau}$ the set of observations made under the algorithm until it stops. Further consider $L_{\tau}$ the log-likelihood ratio of $O_{\tau}$ under the MDPs $\phi$ and $\psi$. Using similar techniques as those used in the proof of Wald’s first lemma, we get (all proofs are detailed in the appendix):

From the above lemma, and using the same arguments as in Kaufmann et al., (2016), one may derive the following data processing inequality, valid for any ${\cal F}_{\tau}$-measurable event $E$:

Combining the above constraints with the fact that $\tau=\sum_{s,a}n_{\tau}(s,a)$, we obtain the following sample complexity lower bound.

The sample complexity of any $\delta$-PAC algorithm satisfies: for any $\phi\in\Phi$,

In the above proposition, $\omega_{sa}\textnormal{kl}(\delta,1-\delta)$ can be interpreted as the expected proportion of times the pair $(s,a)$ is explored under the algorithm. Taking the supremum over $\omega$ then corresponds to selecting an optimal sampling rule. In the following, $\omega$ is referred to as the allocation vector.

We now provide useful properties of the optimization problem (3). Additional properties of the problem are presented in Appendix B.

(i) The set of alternative MDPs. To simplify the notation we use $\pi^{\star}$ instead of $\pi_{\phi}^{\star}$. Our first result concerns the set $\operatorname{Alt}(\phi)$ of alternative MDPs:

The above lemma states that an alternative MDP $\psi$ is such that $\pi^{\star}$, the optimal policy of $\phi$, can be improved under $\psi$ locally at some state $s$, by selecting in $s$ some previously sub-optimal action $a$, instead of $\pi^{\star}(s)$. Using this lemma, we can simplify the expression of the characteristic time appearing in Proposition 1. Indeed, (3) is equivalent to:

Next, we rewrite the problem in an analytic manner. To this aim, we parametrize $\psi$ by its transition probabilities and rewards $u=(q_{\psi}(s,a),p_{\psi}(s,a))_{s,a\in\mathcal{S}\times\mathcal{A}}$ and introduce the following notations: for all $(s,a)$, $dr(s,a)=(r_{\psi}-r_{\phi})(s,a)$ and $dp(s,a)=(p_{\psi}-p_{\phi})(s,a)$. Further define $dV^{\pi^{\star}}=\left([V_{\psi}^{\pi^{\star}}-V_{\phi}^{\pi^{\star}}](s)\right)_{s\in\mathcal{S}}$.

(ii) Non-convexity of the problem (3). The characteristic time $T^{*}(\phi)$, as well as the optimal sampling rule are characterized by the solution of (3) or that of (4). If we think of a track-and-stop algorithm to identify the best policy (as proposed in Garivier and Kaufmann, (2016) for the simple MAB problem), one would need to repeatedly solve these optimization problems. It is then important to be able to do it in a computationally efficient way. Unfortunately, these problems are probably very hard to solve. This is well illustrated by the fact that the following sub-problem is not convex:

Consider $\phi,\psi,\overline{\psi}$ belonging to the class of MDPs specified in Fig. 1, each defined by the vector $(r_{2},r_{1},p_{1})$ (all other parameters values are fixed as in the figure):

We use the analytic version (6) of the optimization problem that defines the sample complexity lower bound to derive a simple (but still problem-specific) upper bound of the characteristic time $T^{*}(\phi)$. The upper bound actually corresponds to a sampling rule that is explicit, i.e., we do not need to solve any optimization problem to get it. Using this upper bound and the corresponding sampling rule, we will be able to devise a simple track-and-stop algorithm with provable performance guarantees. In addition, the upper bound has the right dependence in the sub-optimality gaps, and we also prove that it remains smaller than existing minimax sample complexity lower bounds.

The proof of the theorem relies on writing each of the difference terms $dr(s,a)$, $dp(s,a)$, $dr^{\pi^{\star}}$ and $dp^{\pi^{\star}}$ involved in the constraint (5) as a proportion of the sub-optimality gap $\Delta_{sa}$. Then, using classical f-divergences inequalities, as well as a variance inequality from Gheshlaghi Azar et al., (2013), we relate each difference term to the KL divergences appearing in the objective function of the problem (6). With this perspective in mind, the terms $T_{1}(s,a;\phi)$ and $T_{2}(s,a;\phi)$ can be interpreted as the sample complexity costs to learn the reward of (state,action) pair $(s,a)$ and the corresponding transition probabilities, respectively. Similarly, the terms $T_{3}(\phi)$ and $T_{4}(\phi)$ are interpreted as the sample complexity costs to estimate the future rewards collected from the next state and the transitions from the next state.

Let $H_{sa}\triangleq T_{1}(s,a;\phi)+T_{2}(s,a;\phi)$ and $H^{\star}\triangleq S(T_{3}(\phi)+T_{4}(\phi))$. Then the solution of the problem (8) is given by the unique allocation vector $\overline{\omega}\in\Sigma$ defined by ($\sim$ means proportional to): for all $s\in{\cal S}$,

This allocation yields the following upper bound:

In the previous corollary, $\overline{\omega}_{s,a}$ is the optimal proportion of times $(s,a)$ should be sampled, and hence for $s,a\neq\pi^{\star}(s)$, $H_{sa}$ corresponds to the hardness of learning that $(s,a)$ is sub-optimal. It scales as the inverse of the square of the gap $\Delta_{sa}$ and is proportional to the variance of future rewards after taking $(s,a)$.

We have: $U(\phi)=\mathcal{O}\left(\frac{SA}{\Delta_{\min}^{2}(1-\gamma)^{3}}\right).$

ALGORITHM

In this section, we present KLB-TS (KL-Ball Track-and-Stop), an algorithm that selects the successive (state, action) pairs so as to track the allocation $\overline{\omega}$, the problem-specific allocation (14) that leads to the upper bound (15). The algorithm is a track-and-stop, whose stopping rule does not follow a generic Generalized Likelihood Ratio Test as that used Garivier and Kaufmann, (2016) for MAB problems (refer to Subsection 5.2 for detail).

The algorithm takes as input the confidence parameter $\delta$ and any black-box planner MDP-SOLVER. The latter takes as input an MDP $\phi$, and returns an optimal policy $\pi^{\star}_{\phi}\in\Pi^{\star}_{\phi}$. For practical implementations, we use the Policy Iteration algorithm.

KLB-TS starts exploring each (state, action) pair once, to construct an initial estimate $\widehat{\phi}$ of the true MDP $\phi$. The algorithm maintains, after $t$ collected observations, an estimate $\widehat{\phi}_{t}$ of the true MDP. Based on this estimate, KLB-TS computes an estimate of the allocation $\overline{\omega}$, and selects the next (state, action) pair to track it. After each observation, the estimated MDP $\widehat{\phi}_{t}$ is updated. Finally, the algorithm checks if a stopping condition is satisfied, in which case the algorithm stops and returns the empirical optimal policy $\widehat{\pi}^{\star}_{\tau}$. The stopping condition is referred to as the KL-Ball stopping rule since it is inspired by the derivation of the upper bound of $T^{*}(\phi)$. There, the various terms involved in the exploration constraints are upper bounded by KL divergences, i.e., are in a KL ball.

The pseudo-code of KLB-TS is presented in Algorithm 12. Its sampling and stopping rule are described in detail in the next two sub-sections.

To build an algorithm with sample complexity matching the upper-bound of Corollary 15, the sampling proportions of (state,action) pairs should be as close as possible to the near-optimal weights defined in (14). To this aim, we simply use the C-tracking rule defined in Garivier and Kaufmann, (2016), which we recall below.

Define $\overline{\omega}^{\varepsilon}(\phi)$ as the $L^{\infty}$ projection of $\overline{\omega}(\phi)$ onto $\Sigma^{\varepsilon}=\{\omega\in[\varepsilon,1]^{SA}:\underset{s,a}{\sum}\ \omega_{s,a}=1\}.$ Further define $\varepsilon_{t}=(S^{2}A^{2}+t)^{-1/2}/2$. Then the (state, action) pair to be sampled in round $t+1$ is defined as:

with ties broken arbitrarily. The projection onto $\Sigma^{\varepsilon}$ forces a minimal amount of exploration so that no pair is left under-explored because of bad initial estimates. The same analysis of the sampling rule given in Garivier and Kaufmann, (2016) holds in the MDP case and guarantees that:

2 Stopping rule

(17) suggests that to design a PAC stopping condition, it is sufficient to check that the event

or equivalentlyHence the name KL-Ball stopping rule.:

We finally define $\widehat{T}_{1}(s,a)=T_{1}(s,a;\widehat{\phi}_{t})$, $\widehat{T}_{2}(s,a)=T_{2}(s,a;\widehat{\phi}_{t})$, $\widehat{T}_{3}=T_{3}(\widehat{\phi}_{t})$, $\widehat{T}_{4}=T_{4}(\widehat{\phi}_{t})$ and $\delta^{\prime}=\frac{\delta}{4S^{3}A}$. The KL-Ball stopping condition, which guarantees that the event $\mathcal{E}$ above holds with probability $1-\delta$, is:

SAMPLE COMPLEXITY ANALYSIS

Our main results take the form of asymptotic (when $\delta$ goes to 0) upper bounds on the sample complexity of KLB-TS. These bounds are proved as follows. First, the use of the C-tracking rule makes it possible to establish the convergence of the vector $(n_{t}(s,a))_{s,a}/t$ (the (state, action) pair visit frequencies) to the nearly-optimal allocation vector $\overline{\omega}$, as well as the convergence of the empirical MDP $\widehat{\phi}_{t}$ to the true MDP $\phi$. Then, plugging these convergence results in the definition of the stopping rule (19), and combining the obtained results with the asymptotic shape of the threshold function $x(\delta^{\prime},n,m)\underset{\delta\to 0}{\sim}\log(1/\delta)$, we obtain (refer to Appendix G for a detailed description of these arguments):

Finally, we show that the condition in the ’$\inf$’ above holds as soon as $t\geq 4U(\phi)\log(1/\delta)$ (see Lemma 11). The above arguments lead to an upper bound of the sample complexity of KLB-TS, valid almost surely (Proposition 2) and in expectation (Theorem 3).

The proof of the theorem above is similar to that of Theorem 14 in Garivier and Kaufmann, (2016) with a few notable differences. First, we defined a distance on MDPs through the $L^{\infty}$-norm of their reward and transition kernels. Then, we adapted Lemma 19 from Garivier and Kaufmann, (2016), which gives a concentration inequality of the empirical average-rewards in the MAB setting, to include the concentration of transition probabilities of the empirical MDP.

EXPERIMENTS

In this section, we run numerical experiments to compare the performances of KLB-TS and BESPOKE (these are so far the two algorithms with problem-specific sample complexity guarantees). We refer the reader to Appendix H for a detailed description of the differences between KLB-TS and BESPOKE, as well as a comparison of their theoretical guarantees. To compare the two algorithms, we generated two MDPs randomly: a first small MDP with two states and two actions, and a second larger and more realistic MDP with five states and ten actions per state. We used BESPOKE with an accuracy parameter $\epsilon=0.9\Delta_{\min}$ (note that $\Delta_{\min}$ is revealed to BESPOKE). For each value of the confidence level $\delta$, we run 10 simulations for the first MDP under both algorithms. To save computation time in the case of the second MDP, we run 5 simulations for each $\delta$ and only compare KLB-TS’s sample complexity with BESPOKE’s initial number of samples $n_{\min}$ which, as noted in Appendix H, contributed for more than 99% of its sample complexity.

Figure 2 shows the mean sample complexity along with its 2-standard-deviations interval (which seems very small due to the use of a log-scale). The red curve (referred to as ’asymptotic bound’) shows the upper bound $4U(\phi)\log(1/\delta)$ guaranteed by Theorem 3. Note that KLB-TS sample complexity is greater than $4U(\phi)\log(1/\delta)$ for moderate values of $\delta$ and only matches it for $\delta=10^{-14}$. For both MDPs, KLB-TS clearly outperforms BESPOKE.

CONCLUSION

In this work, we have investigated the design of RL algorithms with minimal problem-specific sample complexity. To this aim, we first derived the information-theoretical sample complexity limit (a lower bound on the sample complexity satisfied by any algorithm) and the corresponding optimal sample allocation. Our hope was that, as for the MAB problem, this allocation would be easy to compute and could then lead to a simple and optimal track-and-stop algorithm. Unfortunately, for RL problems, it turns out that the optimal allocation solves an involved non-convex program. Approaching the fundamental sample complexity limit seems possible only if one could solve this program. To circumvent this issue, we derived a tight upper bound of the characteristic time. Remarkably, this bound corresponds to a sample allocation that is explicit, and hence can be easily plugged in into a track-and-stop algorithm. Based on this upper bound, we proposed KLB-TS, an algorithm whose sample complexity matches this upper bound.

This work opens up interesting research directions. First, the computational complexity of the sample complexity lower bound strongly suggests the existence of a fundamental trade-off between sample and computational complexities. Investigating this trade-off is intriguing. Then, we restricted our attention to the generative model, where one can sample any (state, action) pair at any step. In most practical cases however, one needs to learn an optimal policy by observing a single trajectory of the system. Hence, the numbers of times one observes the various (state, action) pairs are correlated, inducing some additional constraints in the optimization problem leading to the sample complexity lower bound. It is worth studying the impact of these navigation constraints on the sample complexity. Finally, we plan to extend our results to the framework of RL with function approximation.

Appendix A Related work: The minimax approach

Appendix B Additional Proprerties of the lower bound program

Most alternative MDPs. We refer to an MDP $\psi\in\overline{\operatorname{Alt}(\phi)}$We use $\overline{E}$ to denote the closure of a set $E$. solving the problem (7) as most alternative, since for a given allocation $\omega$, the sample complexity lower bound is determined by the number of samples needed to distinguish $\phi$ from $\psi$.

This means that to design a most alternative MDP, one should change the rewards and transitions of optimal (state, action) pairs and only one sub-optimal pair $(s,a)$ and those changes should be just enough to fill sub-optimality gap $\Delta_{sa}$. The next lemma formalizes these findings.

Denote by $\mathcal{O}(\phi)=\{(s,a):\ Q^{\star}_{\phi}(s,a)=V^{\star}_{\phi}(s)\}$ the set of optimal (state,action) pairs in the MDP $\phi$ and let $\psi\in\overline{\operatorname{Alt}(\phi)}$ solve (7). Then: (i) For all $(s,a)\in\mathcal{S}\times\mathcal{A}$, $\left(p_{\psi}(.|s,a),q_{\psi}(.|s,a)\right)\neq\left(p_{\phi}(.|s,a),q_{\phi}(.|s,a)\right)\ \implies\ (s,a)\in\mathcal{O}(\psi)\setminus\mathcal{O}(\phi)$ or $a=\pi^{\star}(s)$; (ii) $\mathcal{O}(\phi)\subset\mathcal{O}(\psi)$.

First we recall the following facts which we will make use of.

Fact 1. $Q^{\star}$ is Liptschitz w.r.t rewards and transitions (by simple bounds on Bellman operator):

Fact 2. If we change only the kernels $\left(p_{\phi}(s,a),q_{\phi}(s,a)\right)\to\left(p_{\psi}(s,a),q_{\psi}(s,a)\right)$ of some sub-optimal (state, action) pair $s,a\neq\pi^{\star}(s)$ and the action $a$ doesn’t become strictly optimal $(s,a)\notin\mathcal{O}(\psi)$, then the value function remains unchanged $V^{\star}_{\psi}=V^{\star}_{\phi}$.

This is because there exists $(\pi_{1},\pi_{2})\in\Pi_{\phi}^{\star}\times\Pi_{\psi}^{\star}$ such that $\pi_{2}(a|s)=\pi_{1}(a|s)=0$ (where we recall that $\pi(a|s)$ denotes the probability that $\pi$ selects $a$ in state $s$) which implies:

Fact 3: We can restrict our attention to allocation vectors $\omega$ with zero-null entries: $\forall(s,a)\in\mathcal{S}\times\mathcal{A}:\ \omega_{sa}>0$.

In fact, any allocation vector $\omega$ such that $\omega_{sa}=0$ is suboptimal. Indeed, consider $\psi$ obtained from $\phi$ by changing the kernels in $(s,a)$ so that they become equal to the kernels in $(s,\pi^{\star}(s))$, while keeping everything else unchanged. Then by definition of $\psi$: $\underset{s^{\prime},a^{\prime}}{\sum}\omega_{s^{\prime},a^{\prime}}KL_{\phi|\psi}(s^{\prime},a^{\prime})=0$. Furthermore one can easily show that $\psi\in\overline{\operatorname{Alt}(\phi)}$ which implies that $K(\phi,\omega)^{-1}=0$.

By contradiction: Suppose there exists $(s,a)$ such that: $\left(p_{\psi}(s,a),q_{\psi}(s,a)\right)\neq\left(p_{\phi}(s,a),q_{\phi}(s,a)\right)$ and $(s,a)\in\mathcal{O}(\psi)^{c}\cup\mathcal{O}(\phi)$ and $a\neq\pi^{\star}(s)$. Combined together, the latter two conditions imply that:

We will use the following operator ($\varepsilon$-transform) where we move the rewards and transitions of $\psi$ at $(s,a)$ in the direction of $\phi$ by $\varepsilon\geq 0$: $T_{\phi,\varepsilon}^{s,a}(\psi)\triangleq\psi_{\varepsilon}$ where

Note that the objective function of the infimum problem takes a smaller value at $\psi_{\varepsilon}$ than at $\psi$:

where the first inequality stems from the convexity of KL-function and the second from the property $p\neq q\implies KL(p\|q)>0$. We will prove that there exists $\varepsilon>0$ such that $\psi_{\varepsilon}$ is the limit of a sequence of elements in $\operatorname{Alt}(\phi)$, which clearly contradicts the optimality of $\psi$ (see equation 20).

Consider $a^{\star}$ an optimal action at state $s$ in $\psi$, ie such $(s,a^{\star})\in\mathcal{O}(\psi)$. Since $(s,a)\notin\mathcal{O}(\psi)$ (21), then for $\varepsilon=0$, we have: $\psi_{0}=\psi$ and $\delta\triangleq\delta_{\psi}(s,a)=Q^{\star}_{\psi}(s,a^{\star})-Q^{\star}_{\psi}(s,a)>0$. By continuity of $Q^{\star}$ w.r.t the rewards and transitions (Fact 1), there exists $\varepsilon>0$ small enough such that:

This implies, by Fact 2 on $\psi_{n}$ and $\theta_{n}$, that: $\forall n\geq N_{0}\ V^{\star}_{\theta_{n}}=V^{\star}_{\psi_{n}}$. Since, we only changed kernels of $\psi_{n}$ at $(s,a)$ to obtain $\theta_{n}$, then this also implies that for all $n\geq N_{0}$:

Proof of (ii): 𝒪​(ϕ)⊂𝒪​(ψ)𝒪italic-ϕ𝒪𝜓\mathcal{O}(\phi)\subset\mathcal{O}(\psi)

We proceed in the same way, i.e., we suppose that there exists $(s,a)\in\mathcal{O}(\phi)\setminus\mathcal{O}(\psi)$. Only this time, we consider $\psi_{\varepsilon}\triangleq\underset{s^{\prime},a^{\prime}}{\prod}\ T_{\phi,\varepsilon}^{s^{\prime},a^{\prime}}(\psi)$ where the product sign stands for composition of operators. It’s straightforward to show, using continuity of $Q^{\star}$ w.r.t rewards and transitions, that there exists $\varepsilon>0$ such that $(s,a)$ is still not optimal: $a\notin\mathcal{O}(\psi_{\varepsilon})$. Hence $\psi_{\varepsilon}\in\operatorname{Alt}(\phi)$, which contradicts the optimality of $\psi$. ∎

Let $\tau$ be a stopping time w.r.t. the filtration $({\cal F}_{t})_{t\geq 1}$. The observations made up to the beginning of round $t$ are ${\cal O}_{t}=(s_{1},a_{1},R_{1},s^{\prime}_{1}\ldots,s_{t},a_{t},R_{t},s^{\prime}_{t})$. Let $p(\cdot)$ denote the distribution of the first state. We have:

The log-likelihood ratio of the observations up to the end of round $t$ under $\phi$ and $\psi$ is then:

Next we study $L_{t}^{s,a}$ for a given pair $(s,a)$. Introduce the following random variables: $Y_{k}$ and $Z_{k}$ denote the next state and the collected reward after the $k$-th time $(s,a)$ has been visited. We can re-write $L_{t}^{s,a}$ as:

Summing over all pairs $(s,a)$ completes the proof. ∎

Appendix D Main properties of the problem (3)

To simplify the notation, we denote $\pi=\pi_{\phi}^{\star}$. First part: $\operatorname{Alt}(\phi)\subset\underset{s,a\neq\pi^{\star}(s)}{\bigcup}\{\psi:Q_{\psi}^{\pi}(s,a)>V_{\psi}^{\pi}(s)\}$ By contradiction: Suppose there exists $\psi\in\operatorname{Alt}(\phi)$ such that $\forall s,a\neq\pi^{\star}(s),\ Q_{\psi}^{\pi}(s,a)\leq V_{\psi}^{\pi}(s)$. Since $Q_{\psi}^{\pi}(s,\pi(s))=V_{\psi}^{\pi}(s)$ then the inequality is valid for all pairs:

Let $\pi_{\psi}^{\star}$ be an optimal policy under $\psi$. Then:

Using the Bellman operator of the policy $\pi_{\psi}^{\star}$ under $\psi$, we rewrite the inequalities above:

By monotonicity of Bellman operator, this implies that: \forall n\geq 1,\ \bigg{(}\mathcal{B}_{\psi}^{\pi_{\psi}^{\star}}\bigg{)}^{n}\ V_{\psi}^{\pi}\leq V_{\psi}^{\pi}. Hence:

i.e., the policy $\pi$ is optimal under $\psi$. This is a contradiction.

Second part: $\underset{s,a\neq\pi^{\star}(s)}{\bigcup}\{\psi:Q_{\psi}^{\pi}(s,a)>V_{\psi}^{\pi}(s)\}\subset\operatorname{Alt}(\phi)$ By contradiction: Let $s,a\neq\pi^{\star}(s)$ and suppose there exists $\psi\in\{\psi:Q_{\psi}^{\pi}(s,a)>V_{\psi}^{\pi}(s)\}$ such that $\pi=\pi_{\phi}^{\star}$ is optimal under $\psi$. Define the modified policy $\pi_{1}$ as:

Then the fact that $Q_{\psi}^{\pi}(s,a)>V_{\psi}^{\pi}(s)$ translates to:

where the equality comes from the assumption that $\pi$ is an optimal policy in $\psi$. Therefore, by monotonicity of Bellman operator, we have:

Appendix E Upper bound U​(ϕ)𝑈italic-ϕU(\phi) and the near-optimal sampling allocation ω¯¯𝜔\overline{\omega}

We will need the following technical lemma which relates the change in the future discounted rewards between $\phi$ and $\psi$ due to different transitions $dp(s,a)^{\top}V^{\star}_{\phi}$ to the Kullback-Leibler divergence of the transition kernels as well as the variance and maximum-deviation of the next-state value.

Using the notations of Sections 4.1 and 4.2, we have:

where we have used $(a+b)^{2}\leq 2(a^{2}+b^{2})$ and $d_{H}(p,q)=\left[\frac{1}{2}\sum_{i}(\sqrt{p_{i}}-\sqrt{q_{i}})^{2}\right]^{1/2}$ is the Hellinger distance between two probability distributions. Therefore:

We conclude the proof using Pinsker’s inequality $\left\lVert p-q\right\rVert_{1}\leq\sqrt{2KL(p\|q)}$ along with the inequality $d_{H}(p,q)^{2}\leq KL(p\|q)$ (see Reiss, (1989)). ∎

E.2 Proof of Theorem 1

We fix $s,a\neq\pi^{\star}(s)$ and derive a lower bound of $\underset{u\in\mathcal{U}_{sa}}{\inf}\omega_{sa}\textrm{KL}_{\phi|\psi}(s,a)+\underset{s^{\prime}}{\sum}\ \omega_{s^{\prime},\pi^{\star}_{\phi}(s^{\prime})}\textrm{KL}_{\phi|\psi}(s^{\prime},\pi^{\star}_{\phi}(s^{\prime}))$. To do so, we rewrite the condition (5) by expanding the expression of $dV^{\pi^{\star}}$as follows:

We then write each of the four terms on the left-hand side as a ”fraction” of $\Delta_{sa}$:

We use Pinsker’s inequality and Lemma 4 to lower bound each term.

$1^{\textrm{st}}$ term. By Pinsker’s inequality:

$2^{\textrm{nd}}$ term. By Lemma 4, we have:

which, following the same reasoning as the first term, implies:

$4^{\textrm{th}}$ term (first bound). We have:

where $B=\left[\left(I-\gamma P_{\psi}^{\pi^{\star}}\right)^{-1}-\left(I-\gamma P_{\phi}^{\pi^{\star}}\right)^{-1}\right]r_{\phi}^{\pi^{\star}}$. Hence:

$4^{\textrm{th}}$ term (second bound): We will now derive a second bound for the 4th term. Using Lemma 5, we get:

where $\textrm{KL}=\underset{s\in\mathcal{S}}{\max}\ KL(p_{\phi}\left(s,\pi^{\star}_{\phi}(s))\|p_{\psi}(s,\pi^{\star}_{\phi}(s))\right)$. This means one of the three terms on the right-hand side is greater than $\frac{|\alpha_{4}|\Delta_{sa}}{3}$, which implies:

Putting the individual lower bounds together: Summing up all inequalities from (24), (25), (26), (29) and (28), we deduce:

Notice that if $\alpha$ verifies the inequalities above, and $\sum_{i=1}^{4}\alpha_{i}>1$, then the vector whose entries are \displaystyle{\bigg{(}\frac{|\alpha_{i}|}{\sum_{j=1}^{4}|\alpha_{j}|}\bigg{)}}_{1\leq i\leq 4} also verifies these inequalities. Therefore we can restrict our attention to vectors $\alpha$ in the simplex $\Sigma_{4}$. In particular, we have $\alpha_{i}^{2}\leq\alpha_{i}^{4/3}\leq\alpha_{i}$. Furthermore, we lower bound $\Delta_{sa}$ by $\Delta_{\min}$ in the terms $(B_{j})_{3\leq j\leq 5}$. This simplifies the bound to:

Solving the left-hand side problem above in $\alpha$, we get:

E.3 Second technical lemma: Contributions of transitions at optimal pairs to the sample complexity

Let us further develop the expression of $B$:

Notice that the quantity $\gamma\left(I-\gamma P_{\phi}^{\pi^{\star}}\right)^{-1}\left[P_{\psi}^{\pi^{\star}}-P_{\phi}^{\pi^{\star}}\right]V^{\star}_{\phi}$ is similar to the one that appears in Lemma 3 of Gheshlaghi Azar et al., (2013), with $\psi$ playing the role of $\widehat{\phi}$ in this case. We will try to relate it to the variances of the value function in the $\phi$. Define:

Using Lemma 4 and $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$, we can write: $\forall s\in\mathcal{S}$,

where the last inequality comes from Total Variance theorem:

Denote $\sqrt{\sigma^{\pi^{\star}}}\triangleq\left(\sqrt{\sigma^{\pi^{\star}}(s)}\right)_{s\in\mathcal{S}}$. Then from (32) and (33), we deduce:

where the last inequality stems from Pinsker’s inequality. Next we recall a variance inequality from Gheshlaghi Azar et al., (2013):

(Lemma 8, Gheshlaghi Azar et al., (2013))

Summing up equations (34), (35) and Lemma 6, we get:

E.4 Third technical lemma: The minimum gap is smaller than 1

By contradiction, suppose $\Delta_{\min}>1$, then:

This means that for all policies $\pi\in\{\pi\>\forall s\in\mathcal{S},\ \pi(s)\neq\pi^{\star}(s)\}$, we have:

Using Bellman operator, the above inequality becomes:

By induction, using that the monotonicity of Bellman operator:

We obtained a contradiction. Thus, $\Delta_{\min}\leq 1$. ∎

E.5 Proof of Corollary15

The $\omega$ solving the problem in the right-hand side of (8) clearly verifies:

The problem of Theorem 1 then rewrites as:

where $H_{sa}=T_{1}(s,a;\phi)+T_{2}(s,a;\phi)$ and $H^{\star}=S(T_{3}(\phi)+T_{4}(\phi))$. We reformulate (38) as a convex program:

Using KKT conditions, one can easily derive the expression of the solution:

Appendix F PAC Guarantee:

First we recall two concentration inequalities and a technical lemma that we will be using. The first two lemmas are taken from Jonsson et al., (2020). The third lemma is immediate. Define the threshold function x(n,\delta,m)=\log(1/\delta)+(m-1)\log\bigg{(}e(1+n/(m-1))\bigg{)}

(Proposition 2, Jonsson et al., (2020)) For all distributions $q$ of mean $r$ supported on the unit interval, for all $\delta\in$:

where we used $S$ as a shorthand for $|\mathcal{S}|$.

Recall the definition of the ”correctness” event:

Applying Lemma 10, we can simplify the event $\mathcal{E}_{t}$:

where the last equality stems from the fact that both $n\to\frac{\sqrt{\widehat{T_{3}}x(\delta^{\prime},n,2)}}{\sqrt{n}}$ and $n\to\frac{\sqrt{\widehat{T_{4}}x(\delta^{\prime},n,S)}}{\sqrt{n}}$ are decreasing as soon as $n\geq 7(\mathcal{S}-1)$, therefore reaching their maximum at the same point. From the proof of Theorem 1 (refer to Equations (24)-(25)-(26)-(29)-(28)), we have the following ”correctness’ property:

where $\mathcal{E}_{t}^{c}$ stands for the complement of event $\mathcal{E}$. Therefore:

where in the second inequality we have used the concentration inequalities (44), (45), (46) and (47). We detail the derivation of this second inequality below:

First term. Using Lemma 8, for $\delta^{\prime}=\frac{\delta}{4S^{3}A}$, we have:

Third term. Following the same reasoning as in the first term we get:

Fourth term. Following the same reasoning as in the second term we get:

Appendix G Sample complexity of KLB-TS

In the following, we use the notation: $y(n,m)\triangleq(m-1)+(m-1)\log(1+n/(m-1))$. Hence the threshold function can be rewritten as: $x(\delta,n,m)=\log(1/\delta)+y(n,m)$.

We start this section by a technical lemma that is later used in the proof of Proposition 2 and Theorem 3.

where the last inequality comes from Corollary 15. ∎

where $n_{t}=(n_{t}(s,a))_{(s,a)\in\mathcal{S}\times\mathcal{A}}$ denotes the number of visits vector. Note that when the terms $(\widehat{T}_{i})_{1\leq i\leq 4}$ are bounded and $\underset{t\to\infty}{\lim}\ n_{t}(s,a)=\infty$ , which we will soon establish, then we have $\underset{t\to\infty}{\lim}\ f(n_{t},\widehat{\phi}_{t})=0$.

Thus when $t\geq t_{1}(\varepsilon)$, inequality (48) implies:

Combining (49) and (50), we have for $t\geq\max(t_{1}(\varepsilon),t_{2}(\delta,\varepsilon))$, $LHS_{t}\leq 1$. Therefore:

Thus $\forall\delta\in(0,1),\ \tau_{\delta}$ is finite on $\mathcal{C}$ and we have:

Taking the limit when $\varepsilon\to 0$, we get:

G.2 Proof of Theorem 3

Based on this distance, we can define balls on the set of MDPs:

Let $\varepsilon>0$. By recursively bounding Bellman operator, one can prove that $Q^{\star}$ is Liptschitz w.r.t. rewards and transitions:

Thus, there exists $\xi=\xi(\varepsilon)>0$ such that:

We will be using the following technical lemmas. The first corresponds to Lemma 20 in Garivier and Kaufmann, (2016), which we reformulate in our case by replacing the number of arms of the bandit by the number of (state, action) pairs of the MDP.

There exists a constant $T_{\varepsilon}$ such that for $T\geq T_{\varepsilon}$, it holds on $\mathcal{E}_{T}$, for C-Tracking:

The second lemma is a concentration inequality similar to that of Lemma 19 in Garivier and Kaufmann, (2016) (we defer its proof to the end of this appendix).

Denote by $\mathcal{E}_{T}^{c}$ the complementary of the event $\mathcal{E}_{T}$. There exists two constants $B,C$ (that depend on $\phi$ and $\varepsilon$) such that:

Recall inequality (48), which gives an upper bound of the left-hand-side of the stopping condition:

where $f(.,.)$ is a continuous function in both arguments. Define:

For $T\geq T_{\varepsilon}$, on the event $\mathcal{E}_{T}$, we have: $\forall t\geq T^{1/4},\quad\widehat{\pi}_{t}^{\star}=\pi^{\star}$, and using Lemma 12, $\left\lVert\frac{n_{t}(s,a)}{t}-\overline{\omega}_{s,a}\right\rVert_{\infty}\leq 3(SA-1)\varepsilon$. Therefore, for the stopping condition $\textrm{LHS}_{t}\leq 1$ to be satisfied, it is sufficient to have:

By Lemma 14, $\underset{t\to\infty}{\lim}F(\phi,\varepsilon,t)=0$. Hence, we can define the following times :

It is easy to see that for $T\geq\max(T_{\varepsilon},t_{1},t_{2})$, condition (51) is verified and consequently: $\tau_{\delta}\leq T$. In other words, we just proved that:

Letting $\eta$ and $\varepsilon$ go to zero, and noting that:

G.3 Second technical lemma

Let $\pi^{\star}=\pi_{\phi}^{\star}$ and let $y(n,m)=(m-1)+(m-1)\log(1+n/(m-1))$. Define:

Then, there exists $\varepsilon_{0}$ such that: $\forall\varepsilon\leq\varepsilon_{0},\ \underset{t\to\infty}{\lim}F(\phi,\varepsilon,t)=0$.

By continuity of the functionals $(T_{i})_{1\leq i\leq 4}$ in $\phi$, there exists $\varepsilon_{0}>0$, such that for all $\varepsilon\leq\varepsilon_{0}$, the supremums defined above are upper bounded by $M=2\times\underset{s,a\neq\pi^{\star}(s)}{\max}(T_{1}(s,a;\phi),T_{2}(s,a;\phi),T_{3}(\phi),T_{4}(\phi))$. Furthermore, if $\left\lVert\omega^{\prime}-\omega(\phi)\right\rVert\leq 3(SA-1)\varepsilon$, then for all $(s,a)$: $\omega_{sa}(\phi)-3(SA-1)\varepsilon\leq\omega^{\prime}_{sa}\leq\omega_{sa}(\phi)+3(SA-1)\varepsilon$. Summing up these inequalities we get, for $\varepsilon$ small enough:

Since $\forall a>0\ \forall m\geq 2,\ \underset{x\to\infty}{\lim}\frac{\sqrt{y(ax,m)}}{\sqrt{x}}=\underset{x\to\infty}{\lim}\frac{\sqrt{(m-1)+(m-1)\log(1+ax/(m-1))}}{\sqrt{x}}=0$, and the maximums in (52) are taken over finite sets, then $\underset{t\to\infty}{\lim}F(\phi,\varepsilon,t)=0.$ ∎

G.4 Proof of Lemma 13

Let $T$ be such that $T^{1/4}\geq(SA)^{2}$. Then for $t\geq T^{1/4}$, we have $\forall(s,a),\quad n_{t}(s,a)\geq(\sqrt{t}-SA/2)_{+}-1\geq\sqrt{t}-SA$. Therefore, using a union bound and Chernoff inequality, one can write:

Using the same reasoning, we can prove that:

Thus, for the following choice of constants

Appendix H Comparison of KLB-TS and BESPOKE:

As KLB-TS, BESPOKE is an algorithm that adapts its sampling strategy to the learnt MDP. The two algorithms have however different objectives: BESPOKE aims at returning an $\varepsilon$-optimal policy. BESPOKE starts with an intialization phase where each (state, action) pair is sampled $n_{\min}=\frac{2\times 625^{2}\times\gamma^{2}\times S\times\log(1/\delta)}{(1-\gamma)^{2}}$ times. After this first phase, the algorithm enters an inner loop. Each iteration of the loop aims at halving the sub-optimality gap $\left\lVert V^{\star}_{\phi}-V_{\phi}^{\widehat{\pi}^{*}}\right\rVert_{\infty}$ of the empirical best policy. The algorithm iterates until the gap becomes smaller than $\varepsilon$. At the beginning of each iteration, the algorithm solves a convex program whose solution provides the numbers of times each (state, action) pair should be sampled in this iteration. The program minimizes a weighted sum of ”confidence intervals” of rewards and transitions estimates at each (state, action) pair, subject to a maximum budget constraint. This objective is known, thanks to the Simulation Lemmasee Lemma 2 in Zanette et al., (2019), to be an upper bound of the sub-optimality gap of the empirical optimal policy. BESPOKE uses a doubling trick to compute the maximum budget for each iteration (this budget is defined so that the gap is halved). We note the following important differences between KLB-TS and BESPOKE.

KLB-TS does not need to solve any convex program to update its sampling strategy, because given an estimate of the MDP, this strategy is explicit.

It is also worth noting that the initialization phase of BESPOKE is extremely long: $\frac{2\times 625^{2}\times\gamma^{2}\times S^{2}A\times\log(1/\delta)}{(1-\gamma)^{2}}$ samples must be gathered. During this phase, the algorithm is not adaptive at all. As we have shown in our numerical experiments, even with small state and action spaces, the initialization phase constitutes a very large proportion of the sample complexity – which makes the algorithm less adaptive than it seems, and really leads to poor performance. KLB-TS has a much smaller initialization phase and is really adaptive. On Figure 3, we see that BESPOKE’s large sample complexity is mainly due to the constant term corresponding to the minimum number of samples it allocates to each (state, action) pair in the initialization phase. Note that this minimum number of samples cannot be avoided as it is necessary to ensure that BESPOKE halves the accuracy of the empirical policy after each iterationsee Lemma 16 and the proof of Theorem 1 in Zanette et al., (2019).

BESPOKE’s stopping rule is suited to identify $\varepsilon-$optimal policies. Unless it has access an oracle revealing $\Delta_{\min}$, it cannot perform best policy identification.

H.2 Theoretical guarantees of BESPOKE and KLB-TS

In contrast, the sample complexity of KLB-TS scales as:

From the above upper bounds, we can make the following comments:

Both bounds depend on functionals of the particular MDP to be learnt, such as the minimum gap, the variance or maximum deviations of value functions. This means that BESPOKE and KLB-TS can adapt to the hardness of the problem, and in particular perform significantly better than minimax approaches when the MDP is easy (e.g. when the minimum gap is high or when the variances of the value function is low).

When the rewards have strictly positive variances, then the two upper bounds are very similar, except for the large constant term $\frac{S^{2}A\log(1/\delta)}{(1-\gamma)^{2}}$ for BESPOKE which comes from its very long initialization phase. We believe that this constant term makes BESPOKE impractical.

While BESPOKE’s bound has the advantage of being non-asymptotic, it only holds with probability $1-\delta$. In contrast, KLB-TS comes with an asymptotic bound on the expected sample complexity, which we also proved to be finite for all confidence levels $\delta$.