Optimal Sample Complexity of Reinforcement Learning for
Mixing Discounted Markov Decision Processes

Reinforcement learning (RL) (Sutton and Barto,, 2018) has witnessed substantial empirical successes in a wide range of applications, including robotics (Kober et al.,, 2013), computer vision (Sadeghi and Levine,, 2016), and finance (Deng et al.,, 2017). This has sparked substantial research of RL theory and applications in operations research and management sciences. This paper provides a theoretical contribution to this area by considering a tabular RL environment in which a controller wishes to maximize an infinite horizon discounted reward governed by a Markov decision process (MDP). In many applications, due to engineering and managerial considerations, the underlying MDP is naturally constrained to an environment in which good policies must be stable, c.f. Bramson, (2008). In these settings, the controlled Markov chain induced by a reasonable policy will converge in distribution to a unique steady state behavior, regardless of the initial condition. This phenomenon is known as mixing. In cases where the mixing rate of a system is rapid, a finite-time observation of the state process can provide a more accurate statistical depiction of its long-term behavior. Consequently, it is reasonable to expect that for such systems, the development of a lower-complexity algorithm for policy learning is feasible, even in the presence of small discount rates, provided that an optimal policy displays fast mixing. This intuition serves as the motivation and driving force for this paper.

In addition, an optimal algorithm and analysis for discounted mixing MDPs can serve as valuable algorithmic and theoretical tools for achieving optimal sample complexity results for long-run average reward MDPs through the reduction method proposed in Jin and Sidford, (2021). While the worst case sample complexities of discounted tabular RL algorithms have been studied extensively in recent years (Azar et al.,, 2013; Agarwal et al.,, 2020; Li et al.,, 2022), we are unaware of a complexity theory and algorithm that is optimized for discounted mixing MDPs. Therefore, it is of significant practical and theoretical value to develop a satisfactory complexity theory for discounted mixing MDPs.

This paper contributes to the existing literature in the following ways. First, we adapt the regeneration idea and the split chain technique (Athreya and Ney,, 1978; Nummelin,, 1978) for analyzing stable Markov chain to the RL context. This framework naturally leads to measuring the mixing rate of the system by the minorization time (Definition 3), which is the expected amount of time between successive Markov chain regenerations. The drift and minorization formulation have been widely used in modeling and analyzing stable queuing systems (Meyn and Down,, 1994; Bramson,, 2008). In Theorem 1, we prove that in the setting of uniformly ergodic Markov chains with finite state space, the minorization time is equivalent to the total variation mixing time that is used in the sample complexity of mixing MDP literature (Wang,, 2017; Jin and Sidford,, 2021). Moreover, this formulation directly generalizes to infinite state spaces, foreshadowing a generalization our results to general state space MDPs.

Secondly, we establish algorithms and worst case sample complexity upper bounds under three different mixing assumptions using Wainwright’s variance-reduced Q-learning (Wainwright, 2019b, ) algorithmic framework. We begin with a general setting where there exists an optimal policy such that an upper bound on the minorization time is available. Next, we require that there is a uniform upper bound on the minorization times of the class of optimal policies. Finally, we consider the case where the minorization time of all policy has a uniform upper bound. Our worst case sample complexity guarantees in these three contexts are summarized in Table 1. Note that in all three cases the dependence on the effective horizon is $(1-\gamma)^{-2}$.

Thirdly, we introduce the non-asymptotic minimax risk of the class of MDPs with a uniform minorization time upper bound (Definition 4). We compare this definition of minimax risk to the instance dependent version in Khamaru et al., 2021b and find ours easier to interpret. Moreover, we prove the same lower bounds in Table 1 for these two definitions of the non-asymptotic minimax risks by constructing a family of hard MDP instances (Definition 5) indexed by the discount and the minorization time. This allows us to conclude that our sample complexity upper bounds are optimal up to log factors.

In this paper, we assume the availability of a simulator, also known as a generative model, that can generate independent state transitions for any input state-action pair. Given the significant memory and computational demands associated with vast state and action spaces, we adopt a model-free approach in which the algorithm only maintains a state-action value function, or $q$-function. Our learning objective is to achieve an estimator of the optimal $q^{*}$ function within $\epsilon$ absolute error in the sup norm. Our algorithm and analysis achieve the optimal non-asymptotic minimax complexity in this regard. Notably, the variance bounds established in this work can be readily applied to the analysis of model-based algorithms, such as Azar et al., (2013), and the same optimal sample complexity upper bounds as in this work should follow.

Let $\mathcal{M}=(S,A,r,P,\gamma)$ be an MDP, where $S$ and $A$ are finite state and action spaces, $r:|S|\times|A|\rightarrow[0,1]$ the reward function, $P:|S|\times|A|\rightarrow\mathcal{P}(S,2^{S})$ the transition kernel. $\gamma\in(0,1)$ is the discount factor. We assume that $S,A,r,\gamma$ are known, and we can draw samples from the transition measures $\left\{{P_{s,a},s\in S,a\in A}\right\}$ independently through a sampler (generative model).

Let $\Omega=(|S|\times|A|)^{\mathbb{Z}_{\geq 0}}$ and let $\mathcal{F}$ be the product $\sigma$-field be the underlying measureable space. Define the stochastic process $\left\{{(S_{t},A_{t}),{t\geq 0}}\right\}$ by the point evaluation $S_{t}(\omega)=s_{t},A_{t}(\omega)=a_{t}$ for all $t\geq 0$ for any $\omega=(s_{0},a_{0},s_{1},a_{1},\dots)\in\Omega$. At time $t\geq 0$ and state $s_{t}\in S$, if action $a_{t}\in A$ is chosen, the decision maker will receive a reward $r(s,a)$, and then the law of the subsequent state is determined by the transition kernel $\mathcal{L}(S_{t+1}|S_{0}=s_{0},\dots,S_{t}=s_{t},A_{t}=a_{t})=P_{s_{t},a_{t}}(\cdot)$. It is well known that to achieve optimal decision making in the context of infinite horizon discounted MDPs (to be introduced), it suffices to consider policies that are stationary, Markov, and deterministic. Therefore, we will restrict ourselves to consider only this class of policies.

Let $\Pi$ denote the class of stationary Markov deterministic policies; i.e. any $\pi\in\Pi$ can be seen as a function $\pi:S\rightarrow A$. For $\pi\in\Pi$ and initial distribution $\mu\in\mathcal{P}(S,2^{S})$, there is a probability measure $Q_{\mu}^{\pi}$ on the product space s.t. the chain $\left\{{(S_{t},A_{t}),t\geq 0}\right\}$ has finite dimensional distributions

Note that this also implies that $\left\{{S_{t},t\geq 0}\right\}$ is a Markov chain under $Q_{\mu}^{\pi}$. Let $E_{\mu}^{\pi}$ denotes the expectation under under $Q_{\mu}^{\pi}$. For $\mu$ with full support $S$, the value function $v^{\pi}(s)$ is defined via

while the optimal value function is given by

$\forall s\in S$. It can be seen as a vector $v^{*}\in\mathbb{R}^{|S|}$. Let $\Pi^{*}$ denote the set of all optimal stationary Markov deterministic policies; i.e. $\pi\in\Pi$ that achieves the maximum in (1).

Let $P_{s,a}[v]$ denote the sum $\sum_{s^{\prime}\in S}P_{s,a}(s^{\prime})v(s^{\prime})$. It is well known that the optimal value function is the unique solution of the following Bellman equation:

To learn an optimal policy $\pi^{*}\in\Pi^{*}$, it is useful to introduce the $q$-function: For any policy $\pi\in\Pi$,

which can be identified with a vector $q^{\pi}\in\mathbb{R}^{|S|\times|A|}$. Define the notation $v(q)(s)=\max_{a\in A}q(s,a)$. When $\pi=\pi^{*}$ achieves the maximum in (1), we denote the corresponding optimal $q$-function $q^{\pi^{*}}$ by $q^{*}$ and hence $v(q^{*})=v^{*}$. Note that $q^{*}$ is the unique solution to the Bellman equation for the $q$-function:

where the mapping

is known as the Bellman operator for the $q$-function. Here we list two elementary properties of the Bellman operator and the $q$-function. The proofs can be found in Puterman, (1994). First, $\mathcal{T}$ is a $\gamma$-contraction in the $\|\cdot\|_{\infty}$-norm; i.e. $\|\mathcal{T}(q)-\mathcal{T}(q^{\prime})\|_{\infty}\leq\gamma\|q-q^{\prime}\|$ for all $q,q^{\prime}\in\mathbb{R}^{|S|\times|A|}$. Then, a consequence of $\mathcal{T}$ being a $\gamma$-contraction is

A greedy policy from a $q$-function is defined as

where one action is picked if there is a tie. It is easy to see that $\Pi^{*}\ni\pi^{*}=\arg\max_{a\in A}q^{*}(\cdot,a)=\pi(q^{*})$. Therefore, policy learning can be achieved if we can learn a good estimate of $q^{*}$. For $\pi\in\Pi$, we use $P^{\pi}:\mathbb{R}^{|S||A|}\rightarrow\mathbb{R}^{|S||A|}$ to denote the linear operator

Under suitable mixing conditions as presented in Puterman, (1994), it is useful to look at the span semi-norm of the value and $q$-functions. For vector $v\in V=\mathbb{R}^{d}$, let $e$ be the vector with all entries equal to one and define

Note that $\left|\cdot\right|_{\mathrm{span}}$ is not a norm because $\left|e\right|_{\mathrm{span}}=0$, but it is an induced norm on the quotient space $V\backslash\left\{{ce:c\in\mathbb{R}}\right\}$. We also note that $\left|v\right|_{\mathrm{span}}\leq 2\|v\|_{\infty}$ for all $v\in V$. However, $\left|\cdot\right|_{\mathrm{span}}$ and $\left\|\cdot\right\|_{\infty}$ are not equivalent on $\mathbb{R}^{d}$.

Naturally, the variance of the cumulative reward induced by the optimal policy plays a key role in controlling the sample complexity of solving the MDP. Given a stationary deterministic Markov policy $\pi$, let us define and denote the variance of the cumulative reward by

Another standard deviation parameter to our interest is

We call this object the “1-sample standard deviation” of the Bellman operator. It is the sampling standard deviation of the so-called 1-sample Bellman operator, which we will introduce in equation (11) in the algorithm analysis section. To analyze $\Psi^{\pi}$ and $\sigma(q^{\pi})$, it’s useful to define

Note that for any optimal policy $\pi^{*}$, $v(q^{*})=v^{*}$. So, $\sigma(q^{*})=\sigma^{\pi^{*}}$.

Let $\mathcal{M}$ be a MDP. Given a stationary Markov deterministic policy $\pi\in\Pi$, the state process $\left\{{S_{t},t\geq 0}\right\}$ will have transition kernel $P_{\pi}(s,s^{\prime})=P_{s,\pi(s)}(s^{\prime})$. In various applications, the state process induced by a reasonable policy will converge to a unique steady state regardless of the initial condition. In this section, we will formally characterize such behavior by introducing the notion of uniform ergodicity. A uniformly ergodic Markov chain is one for which the marginal distribution of $S_{t}$ converges to its stationary distribution in total variation distance with uniform rate across all initial conditions. Recall the total variation distance between two probability measures $\mu,\nu$ on $2^{S}$ is

We use the norm notation here because it is equivalent to the $l_{1}$ norm if we view $\mu$ and $\nu$ as vectors in $\mathbb{R}^{|S|}$; i.e. $\left\|\mu-\nu\right\|_{\mathrm{TV}}=2^{-1}\|\mu-\nu\|_{1}$.

Uniform ergodicity is equivalent to the the transition kernel satisfying the Doeblin condition (Meyn et al.,, 2009). This equivalence permits the application of the split chain representation (Athreya and Ney,, 1978; Nummelin,, 1978) of the Markov chain, which exhibits favorable independence properties, as illustrated in Section 3.2. Thus, the Doeblin condition will serve as our principal assumption and theoretical tool for the analysis of the sample complexity of mixing MDPs. To characterize the rate of mixing of a uniformly ergodic Markov chain, two metrics, namely ${t_{\mathrm{mix}}}$ and $t_{\mathrm{minorize}}$, emerge naturally from the total variation and Doeblin condition characterizations. We will introduce these metrics in Section 3.3. While ${t_{\mathrm{mix}}}$ is more commonly utilized in the literature on MDP complexity (Wang,, 2017; Jin and Sidford,, 2020, 2021), we have found $t_{\mathrm{minorize}}$ to be a more suitable metric for our objectives. To facilitate the comparison of our complexity theories with those in the literature, we establish the equivalence of ${t_{\mathrm{mix}}}$ and $t_{\mathrm{minorize}}$ up to a constant factor in Section 3.3.

We have introduced uniform ergodicity and the minorization time $t_{\mathrm{minorize}}$ as an equivalent measure of mixing time and the split chain technique. Using $t_{\mathrm{minorize}}$ as the mixing criterion, in this section, we explore the worst case sample complexities of learning the optimal $q$-function under different stability assumptions of the controlled Markov chain.

MDPs can exhibit different types of mixing behavior. However, since our primary focus is on developing a complexity theory for learning the optimal $q$-function, we seek algorithms that obtain optimal policies by producing progressively more precise estimates of $q^{*}$ as the sample size increases. Consequently, the asymptotic variability of the estimator should be influenced by the mixing characteristics of the optimal policies. Therefore, it is well-motivated to make assumptions about the mixing properties of the class of optimal policies. We first consider the most general one:

In this setting, define

To obtain an optimal sample complexity result, we make further uniform assumptions on the minorization times of kernels induced by $\pi^{*}\in\Pi^{*}$. In this paper, we consider the following two settings:

If $\Pi^{*}$ is not a singleton, we instead impose a “continuity in $\pi$” assumption on $P$ which we will refer to as Lipschitzness:

In the setting of Assumption 2 and 3, we define

We note that the settings in Assumptions 2 and 3 are considered in the Q-learning literature (Khamaru et al., 2021b, ; Li et al.,, 2023). Moreover, Assumption 3 is implied by 2 with $L=4/\zeta$ where $\zeta$ is the optimality gap of the optimal policy class defined as $\zeta:=\min_{s\in S}\min_{\pi\in\Pi\backslash\Pi^{*}}|v^{*}(s)-q^{*}(s,\pi(s))|$; see Lemma B.1 of Li et al., (2023).

Even though the asymptotic performance of a convergent algorithm should only depend on the mixing characteristics of the optimal policies, for a prescribed accuracy level $\epsilon$, assumptions on mixing characteristics of non-optimal policies could potentially increase the performance as well. Moreover, in applications of MDPs, we typically have little knowledge of the class of optimal policies a priori. However, as mentioned earlier, there may be settings in which all policies will induce mixing Markov chains with a uniform bound on the minorization times. This leads to the following assumption:

In this setting, we define

Since $\Pi$ is finite, the above $\max$ is always achieved and $t_{\mathrm{minorize}}<\infty$.

In the following developments, we will demonstrate the impact of mixing Assumptions 1, 2, 3, and 4 on algorithmic performance, leading to a improvement in sample complexity by a factor of $(1-\gamma)^{-1}$ when compared to the minimax lower bound without considering mixing time assumptions ($\tilde{O}((1-\gamma)^{-3})$). In particular, the sample complexity upper bounds in Theorems 2, 3, and 4 are now enhanced to $\tilde{O}((1-\gamma)^{-2})$.