Navigating to the Best Policy
in Markov Decision Processes

Somewhat surprisingly, learning in a Markov Decision Process is most often considered under the performance criteria of consistency or regret minimization (see e.g. [SB18, Sze10, LS20] and references therein). Regret minimization (see e.g. [AJO09, FCG10]) is particularly relevant when the rewards accumulated during the learning phase are important. This is however not always the case: for example, when learning a game (whether Go, chess, Atari, or whatever), winning or losing during the learning phase does not really matter. One may intuitively think that sometimes getting into difficulty on purpose so as to observe unheard situations can significantly accelerate the learning process. Another example is the training of robot prototypes in the factory: a reasonably good policy is first searched, regardless of the losses incurred, that can serve as an initialization for a second phase regret-minimization mode that starts when the robot is deployed. It is hence also of great practical importance to study the sample complexity of learning, and to work on strategies that might improve, in this perspective, on regret minimizing algorithms.

In this work, we are interested in the best policy identification (BPI) problem for infinite-horizon discounted MDPs. This framework was introduced by [Fie94] under the name of PAC-RL. In BPI the algorithm explores the MDP until it has gathered enough samples to return an $\varepsilon$-optimal policy with probability at least $1-\delta$. Crucially, the algorithm halts at a random time step, determined by a stopping rule which guarantees that the probability of returning a wrong answer is less that $\delta$. The optimality of BPI algorithms is measured through their sample complexity, defined as their expected stopping time. Best policy identification in MDPs has been mostly investigated under the lens of minimax-optimality. The minimax framework may be overly pessimistic by accounting for the worst possible MDP, whereas an algorithm with instance-specific guarantees can adapt its exploration procedure to the hardness of the MDP instance that it faces. Recently, a few works made the first attempts towards understanding the instance-specific sample complexity of reinforcement learning. However, they typically either make simplifying assumptions such as access to a generative model [ZKB19, MP21], or restrict their attention to episodic MDPs [WSJ21]. In practice however, the samples gathered rather correspond to a single, possibly infinite, trajectory of the system that we wish to control. This motivates our study of the full online setting where observations are only obtained by navigating in the MDP, that is by sequential choices of actions and following the transitions of the MDP.

Our contributions. [MP21] recently proposed an information-theoretical complexity analysis for MDPs in the case of access to a generative model. Here we extend their results to the online setting. Our main goal is to understand how the online learning scheme affects the sample complexity compared to the easier case where we have a generative model. A natural first step consists in understanding how the first order term $T^{\star}\log(1/\delta)$ changes. Thus we only focus on the asymptotic regime $\delta\to 0$. Our key contributions can be summarized as follows:

• •

  First, we adapt the lower bound of [MP21] to the online setting (Proposition 2). The new bound also writes as the value of a zero-sum two-player game between nature and the algorithm, where the loss function remains the same, but where the set of possible strategies for the algorithm is restricted to a subset $\Omega(\mathcal{M})$ of the simplex of dimension $SA-1$. We refer to the constraints defining $\Omega(\mathcal{M})$ as the navigation constraints.

• •

  We propose MDP-NaS, the first algorithm for the online setting¹¹1Before publication of this work, but after a preprint was available online, [WSJ21] proposed another algorithm with instance-dependent guarantees. with instance-dependent bounds on its sample complexity in the asymptotic regime $\delta\to 0$ (Theorem 6). A major challenge lies in the design of a sampling rule that guarantees that the sampling frequency of state-action pairs $\big{(}N_{sa}(t)/t\big{)}_{s,a}$ converges to some target oracle allocation $\omega^{\star}\in\Omega(\mathcal{M})$. Indeed, since we can no longer choose the next state of the agent, the tracking procedure which was developed by [GK16] for multi-armed bandits and used in [MP21] for MDPs with a generative model can no longer be applied in our setting. We propose a new sampling rule which performs exploration according to a mixture of the uniform policy and a plug-in estimate of the oracle policy (the policy whose stationary state-action distribution is $\omega^{\star}$) and prove that it satisfies the requirement above. The analysis of our sampling rule relies on an ergodic theorem for non-homogeneous Markov chains of independent interest (Proposition 12).

• •

  We investigate, depending on the communication properties of the ground-truth instance $\mathcal{M}$, what is the minimal forced-exploration rate in our sampling rule that guarantees the consistency of the plug-in estimator of the oracle policy. Our findings imply that when $\mathcal{M}$ is ergodic, an exploration rate as low as $1/\sqrt{t}$ is sufficient. However, when $\mathcal{M}$ is only assumed to be communicating, one is obliged to resort to a much more conservative exploration rate of $t^{-\frac{1}{m+1}}$, where $m$ is a parameter defined in Lemma 4 that may scales as large as $S-1$ in the worst case.

• •

  Finally, our stopping rule represents the first implementation of the Generalized Likelihood Ratio test for MDPs. Notably, we circumvent the need to solve the max-min program of the lower bound exactly, and show how an upper bound of the best-response problem, such as the one derived in [MP21], can be used to perform a GLR test. This improves upon the sample complexity bound that one obtains using the KL-Ball stopping rule of [MP21] by at least a factor of $2$²²2Note that the stopping rule is independent of the sampling rule and thus can be used in both the generative and the online settings. Furthermore, one may even obtain an improved factor of $4$ by using a deviation inequality for the full distribution of (reward, next-state) instead of a union bound of deviation inequalities for each marginal distribution..

Discounted MDPs. We consider infinite horizon MDPs with discount and finite state and action spaces ${\cal S}$ and ${\cal A}$. Such an MDP ${\cal M}$ is defined through its transition and reward distributions $p_{\cal M}(\cdot|s,a)$ and $q_{\cal M}(\cdot|s,a)$ for all $(s,a)$. For simplicity, $q_{\cal M}(\cdot|s,a)$ will denote the density of the reward distribution w.r.t. a positive measure $\lambda$ with support included in $[0,1]$. Specifically, $p_{\cal M}(s^{\prime}|s,a)$ denotes the probability of transitioning to state $s^{\prime}$ after playing action $a$ at state $s$ while $R(s,a)$ is the random instantaneous reward that is collected. Finally, $\gamma\in[0,1)$ is a discounting factor. We look for an optimal control policy $\pi^{\star}:\mathcal{S}\to\mathcal{A}$ maximizing the long-term discounted reward: $V_{\cal M}^{\pi}(s)=\mathbb{E}_{{\cal M},\pi}[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},\pi(s_{t}))]$, where $\mathbb{E}_{{\cal M},\pi}$ denotes the expectation w.r.t the randomness in the rewards and the trajectory when the policy $\pi$ is used. Classically, we denote by $V_{\cal M}^{\star}$ the optimal value function of ${\cal M}$ and by $Q^{\star}_{\mathcal{M}}$ the optimal $Q$-value function of ${\cal M}$. $\Pi^{\star}(\mathcal{M})=\{\pi:\mathcal{S}\to\mathcal{A},\ V_{\cal M}^{\pi}=V_{\cal M}^{\star}\}$ denotes the set of optimal policies for $\mathcal{M}$.

Problem-dependent quantities. The sub-optimality gap of action $a$ in state $s$ is defined as $\Delta_{sa}=V_{\mathcal{M}}^{\star}(s)-Q_{\mathcal{M}}^{\star}(s,a)$. Let $\Delta_{\min}=\min_{s,a\neq\pi^{\star}(s)}\Delta_{sa}$ be the minimum gap and $\operatorname{sp}(V_{\mathcal{M}}^{\star})=\max_{s,s^{\prime}}|V_{\mathcal{M}}^{\star}(s)-V_{\mathcal{M}}^{\star}(s^{\prime})|$ be the span of $V_{\mathcal{M}}^{\star}$. Finally, we introduce the variance of the value function in $(s,a)$ as $\mathrm{Var}_{p(s,a)}[V_{\mathcal{M}}^{\star}]=\mathrm{Var}_{s^{\prime}\sim p_{\mathcal{M}}(.|s,a)}[V_{\mathcal{M}}^{\star}(s^{\prime})]$.

Active pure exploration with fixed confidence. When ${\cal M}$ is unknown, we wish to devise a learning algorithm $\mathbb{A}$ identifying, from a single trajectory, an optimal policy as quickly as possible with some given level of confidence. Formally, such an algorithm consists of (i) a sampling rule, selecting in each round $t$ in an adaptive manner the action $a_{t}$ to be played; $a_{t}$ depends on past observations, it is ${\cal F}_{t}^{\mathbb{A}}$-measurable where ${\cal F}_{t}^{\mathbb{A}}=\sigma(s_{0},a_{0},R_{0}\ldots,s_{t-1},a_{t-1},R_{t-1},s_{t})$ is the $\sigma$-algebra generated by observations up to time $t$; (ii) a stopping rule $\tau_{\delta}$, a stopping time w.r.t. the filtration $({\cal F}_{t}^{\mathbb{A}})_{t\geq 0}$, deciding when to stop collecting observations; (iii) a decision rule returning $\hat{\pi}^{\star}_{\tau_{\delta}}$ an estimated optimal policy.

An algorithm $\mathbb{A}$ is $\delta$-Probably Correct ($\delta$-PC) over some set $\mathbb{M}$ of MDPs, if for any ${\cal M}\in\mathbb{M}$, it returns (in finite time) an optimal policy with probability at least $1-\delta$. In this paper, we aim to devise a $\delta$-PC algorithm $\mathbb{A}$ with minimal sample complexity $\mathbb{E}_{{\cal M},\mathbb{A}}[\tau_{\delta}]$. We make the following assumption.

We justify the above assumption as follows. (i) We restrict our attention to the case where ${\cal M}$ is communicating, for otherwise, if it is Multichain there would be a non-zero probability that the algorithm enters a subclass of states from which there is no possible comeback. In this case it becomes impossible to identify the global optimal policy⁴⁴4Unless we modify the objective to finding the optimal policy in this subchain.. (ii) About the uniqueness of the optimal policy, treating the case of MDPs with multiple optimal policies, or that of $\varepsilon$-optimal policy identification, requires the use of more involved Overlapping Hypothesis tests, which is already challenging in multi-armed bandits (MDPs with a single state) [GK19]. We will analyze how to remove this assumption in future work.

Notation. $\mathcal{Z}\triangleq\mathcal{S}\times\mathcal{A}$ is the state-action space. $\Sigma\triangleq\{\omega\in\mathbb{R}_{+}^{S\times A}:\ \sum_{s,a}\omega_{sa}=1\}$, the simplex of dimension $SA-1$. $N_{sa}(t)$ denotes the number of times the state-action pair $(s,a)$ has been visited up to the end of round $t$. We also introduce $N_{s}(t)=\sum_{a\in\mathcal{A}}N_{sa}(t)$. Similarly, for a vector $\omega\in\Sigma$ we will denote $\omega_{s}\triangleq\sum_{a\in\mathcal{A}}\omega_{sa}$. For a matrix $A\in\mathbb{R}^{n\times m}$, the infinity norm is defined as $\left\lVert A\right\rVert_{\infty}\triangleq\max_{1\leq i\leq n}\sum_{j=1}^{m}|a_{i,j}|$. The KL divergence between two probability distributions $P$ and $Q$ on some discrete space $\mathcal{S}$ is defined as: $KL(P\|Q)\triangleq\sum_{s\in\mathcal{S}}P(s)\log(\frac{P(s)}{Q(s)})$. For Bernoulli distributions of respective means $p$ and $q$, the KL divergence is denoted by $\operatorname{kl}(p,q)$. For distributions over $[0,1]$ defined through their densities $p$ and $q$ w.r.t. some positive measure $\lambda$, the KL divergence is: $KL(p\|q)\triangleq\int_{-\infty}^{\infty}p(x)\log\left(\frac{p(x)}{q(x)}\right)\,\lambda(dx)$. $\mathbb{M}$ denotes the set of communicating MDPs with a unique optimal policy. For two MDPs ${\cal M},{\cal M}^{\prime}\in\mathbb{M}$, we say that $\mathcal{M}\ll\mathcal{M}^{\prime}$ if for all $(s,a)$, $p_{\mathcal{M}}(\cdot|s,a)\ll p_{\mathcal{M}^{\prime}}(\cdot|s,a)$ and $q_{\mathcal{M}}(\cdot|s,a)\ll q_{\mathcal{M}^{\prime}}(\cdot|s,a)$. In that case, for any state (action pair) $(s,a)$, we define the KL divergence of the distributions of the one-step observations under ${\cal M}$ and ${\cal M}^{\prime}$ when starting at $(s,a)$ as $\textrm{KL}_{\mathcal{M}|\mathcal{M}^{\prime}}(s,a)\triangleq KL(p_{\mathcal{M}}(\cdot|s,a)\|p_{\mathcal{M}^{\prime}}(\cdot|s,a))+KL(q_{\mathcal{M}}(\cdot|s,a)\|q_{\mathcal{M}^{\prime}}(\cdot|s,a))$.

In this section, we first derive a lower bound on the expected sample complexity satisfied by any $\delta$-PC algorithm. The lower bound is obtained as the solution of a non-convex optimization problem, as in the case where the learner has access to a generative model [MP21]. The problem has however additional constraints, referred to as the navigation constraints, due the fact that the learner has access to a single system trajectory.
The expected sample complexity of an algorithm $\mathbb{A}$ is $\mathbb{E}_{\mathcal{M},\mathbb{A}}[\tau_{\delta}]=\sum_{s,a}\mathbb{E}_{\mathcal{M},\mathbb{A}}[N_{sa}(\tau_{\delta})].$ Lower bounds on the sample complexity are derived by identifying constraints that the various $N_{sa}(\tau_{\delta})$’s need to satisfy so as to get a $\delta$-PC algorithm. We distinguish here two kinds of constraints:

Information constraints. These are constraints on $\mathbb{E}_{\mathcal{M},\mathbb{A}}[N_{sa}(\tau_{\delta})]$, so that the algorithm can learn the optimal policy with probability at least $1-\delta$. They are the same as those derived [MP21] when the learner has access to a generative model and are recalled in Lemma 9 in Appendix C.

Navigation constraints. Observations come from a single (but controlled) system trajectory which imposes additional constraints on the $N_{sa}(\tau_{\delta})$’s. These are derived by just writing the Chapman-Kolmogorov equations of the controlled Markov chain (refer to Appendix C for a proof).

Putting all constraints together, we obtain the following sample complexity lower bound.

We propose MDP-NaS (MDP Navigate-and-Stop), a model-based algorithm that is inspired by the lower bound. The lower bound suggests that to identify the best policy in a sample-efficient manner, the algorithm must collect samples from state-action pair $(s,a)$ proportionally to ${\bm{\omega}}_{sa}^{\star}(\mathcal{M})$. We propose two sampling rules which ensure that the former statement holds in the long term (see Section 4.1 and Theorem 7 for a rigorous formulation). Our sampling rules are combined with a Generalized Likelihood Ratio (GLR) test (or rather a proxy of the GLR test, see Section 4.2 for details), that stops as soon as we are confident that $\widehat{\pi}_{t}^{\star}=\pi^{\star}$ with probability at least $1-\delta$. The pseudo-code for MDP-NaS is given in Algorithm 1.

First we state our main results, which take the form of asymptotic upper bounds on the sample complexity of MDP-NaS, under a slightly more conservative exploration rate than in Lemma 4. Then we present the most important ingredients in their proof. The complete proof is provided in Appendix F.

Recall from Lemma 3 and Theorem 6 that our sample complexity bound writes as:

Hence, in the asymptotic regime $\delta\to 0$, MDP-NaS finds the optimal way to balance exploration between state-action pairs proportionally to their hardness: $(1+\mathrm{Var}_{p(s,a)}[V_{\mathcal{M}}^{\star}])/\Delta_{sa}^{2}$ for sub-optimal pairs (resp. $1/\Delta_{\min}^{2}(1-\gamma)^{3}$ for optimal pairs).

After a preprint of this work was published, [WSJ21] proposed MOCA, an algorithm for BPI in the episodic setting. MOCA has the advantage of treating the more general case of $\varepsilon$-optimal policy identification with finite-time guarantees on its sample complexity. The two papers have different and complementary objectives but one can compare with their bound for exact policy identification, i.e when $\varepsilon<\varepsilon^{\star}$¹¹¹¹11$\varepsilon^{\star}$ is defined in their work as the threshold value for $\varepsilon$ such that the only $\varepsilon$-optimal policy is the best policy. However, when the objective is to find the optimal policy, it is not clear from their paper how one can determine such a value of $\varepsilon$ without prior knowledge of the ground truth instance., in the asymptotic regime $\delta\to 0$. In this case, by carefully inspecting the proofs of [WSJ21], we see that MOCA’s sample complexity writes as¹²¹²12The $\log^{3}(1/\delta)$ term comes from the sample complexity of their sub-routine FindExplorableSets.:

where $H$ is the horizon and $\Delta_{sa}(h)$ is the sub-optimality gap of $(s,a)$ at time step $h$. We make the following remarks about the bounds above:

1. 1.

   MOCA only pays the cost of worst-case visitation probability multiplied by the gap of the corresponding state $\underset{s,a\neq\pi^{\star}(s)}{\min}\omega_{sa}\Delta_{sa}^{2}$. Instead, MDP-NaS pays a double worst-case cost of the smallest visitation probability multiplied by the minimum gap $\min_{s}\omega_{s,\pi^{\star}(s)}\Delta_{\min}^{2}$. As pointed out by [WSJ21] the former scaling is better, especially when the state where the minimum gap is achieved is different from the one that is hardest to reach. This is however an artefact of the upper bound in Lemma 3 that MDP-NaS uses as a proxy for the characteristic time. Using a more refined bound, or an optimization oracle that solves the best-response problem, one can remove this double worst-case dependency.

2. 2.

   The sample complexity of MOCA divided by $\log(1/\delta)$ still explodes when $\delta$ goes to zero, contrary to MDP-NaS’s bound.

3. 3.

   The sample complexity of MDP-NaS is variance-sensitive for sub-optimal state-action pairs, while MOCA’s bound depends on a worst-case factor of $H^{2}$. Indeed as the rewards are in $[0,1]$, we always have $V_{\mathcal{M}}^{\star}\leq H$ and $\mathrm{Var}_{p(s,a)}[V_{\mathcal{M}}^{\star}]\leq H^{2}$ in the episodic setting.

We conclude this section by noting that MDP-NaS has a simple design and can easily be implemented.

To the best of our knowledge, this paper is the first to propose an algorithm with instance-dependent sample complexity for Best Policy identification (BPI) in the full online setting. Our results are encouraging as they show: 1) How the navigation constraints of online RL impact the difficulty of learning a good policy, compared to the more relaxed sampling schemes of Multi-Armed Bandits and MDPs with a generative model. 2) That, provided access to an optimization oracle that solves the information-theoretical lower bound (resp. some convex relaxation of the lower bound), asymptotic optimal (resp. near-optimal) sample complexity is still possible through adaptive control of the trajectory. This opens up exciting new research questions. First, it is intriguing to understand how the mixing times -and not just the stationary distributions- of Markov chains induced by policies impact the sample complexity of BPI in the moderate confidence regime. A second direction would be to extend our contributions to the problem of finding an $\varepsilon$-optimal policy, which is of more practical interest than identifying the best policy.