On the Convergence Rates of Policy Gradient Methods

Introduction

Markov decision process (MDP) is a fundamental model for sequential decision-making. In this paper, we consider infinite-horizon, discounted Markov decision problems (DMDPs) with finite state and action spaces. They are specified as a 5-tuple $(\mathcal{S},\mathcal{A},P,R,\gamma)$, where $\mathcal{S}$ is a finite state space with cardinality ${|\mathcal{S}|}$, $\mathcal{A}$ is a finite action space with cardinality ${|\mathcal{A}|}$, $P$ is a transition probability function with $P(s^{\prime}|s,a)$ denoting the probability of transitioning to $s^{\prime}$ when taking action $a$ from state $s$, $R:\mathcal{S}\times\mathcal{A}\to$ is a reward function with $R_{s,a}$ or $R(s,a)$ being the (expected) reward of taking action $a$ from state $s$, and finally $\gamma\in[0,1)$ is a discount factor applied to the reward one-step in the future.

Starting from an initial state $s_{0}\in\mathcal{S}$, an agent takes an action $a_{t}\in\mathcal{A}$ at each time step $t=0,1,2,\ldots$, which leads to the next state $s_{t+1}$ with probability $P(s_{t+1}|s_{t},a_{t})$, and obtains the immediate reward $r_{t}=R(s_{t},a_{t})$. Such interactions generate a trajectory

The goal of the agent is to find a policy of choosing the actions $a_{0},a_{1},a_{2},\ldots$ that maximizes the discounted cumulative reward \operatorname*{\mathbf{E}}\bigl{[}\sum_{t=0}^{\infty}\gamma^{t}r_{t}\bigr{]}. Here the expectation is taken with respect to the possible randomness in $s_{0}$, any randomness in choosing the actions $a_{t}$, and the randomness of state transitions prescribed by $P$.

In general, a policy that determines the action at time $t$ may depends on the whole history of the trajectory up to time $t$. A stationary policy $\pi$ specifies a decision rule that depends only on the current state. Specifically, we let $\pi_{s}\in\Delta(\mathcal{A})$ be the decision rule at state $s$, where $\Delta(\mathcal{A})$ denotes the probability simplex supported on $\mathcal{A}$, and $\pi_{s,a}$ denotes the probability of taking action $a$ at state $s$. The value of a stationary policy $\pi\in\Delta(\mathcal{A})^{|\mathcal{S}|}$ starting from an arbitrary state $s$ is defined as

where the expectation is taken with respect to $a_{t}\sim\pi_{s_{t}}$ and $s_{t+1}\sim P(\cdot|s_{t},a_{t})$ for all $t\geq 0$. We define $V:\Delta(\mathcal{A})^{|\mathcal{S}|}\to\mathbf{R}^{|\mathcal{S}|}$ as a vector-valued function with components $V_{s}(\pi)$. By the assumption that $R(s,a)\in$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$, we immediately have

The conventional formulation of DMDP is about maximizing the discounted total reward. In this paper, we adopt a minimization formulation in order to better align with conventions in the optimization literature. To this end, we regard each $R(s,a)\in$ as a value measuring regret rather than reward. Given a reward matrix $R$, we can reset $R(s,a)\leftarrow 1-R(s,a)$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$ to turn it into a regret matrix. Suppose $\rho\in\Delta(\mathcal{S})$ is an arbitrary initial state distribution. We consider the problem of minimizing

For infinite-horizon DMDPs with finite state and actions spaces, there exists a (deterministic) stationary policy $\pi^{\star}$ that is simultaneously optimal in minimizing $V_{s}(\cdot)$ for all $s\in\mathcal{S}$ (e.g., Puterman, 1994, Section 6.2.4). Such a solution is insensitive to the choice of $\rho$.

In this paper, we focus on policy gradient methods for minimizing the weighted value function $V_{\rho}$. These methods generate a sequence of policies $\{\pi^{(k)}\}$ through repeated evaluation of the policy gradient $\nabla V_{\mu}$, where $\mu\in\Delta(\mathcal{S})$ is not necessarily equal to $\rho$. The most straightforward variant is the projected policy gradient method,

where $\eta_{k}$ is the step size, $\Pi:=\Delta(\mathcal{A})^{{|\mathcal{S}|}}$ is the set of feasible policies, and $\mathbf{proj}_{\Pi}(\cdot)$ denotes projection onto $\Pi$ in the Euclidean norm. More generally, policy gradient methods can be derived from the mirror-descent form

where $D_{k}(\cdot,\cdot)$ is a distance-like function that may depend on $\pi^{(k)}$. For example, setting $D_{k}$ as the squared Euclidean distance yields the projected policy gradient method (4). Shani et al. (2020) showed that by setting $D_{k}$ as an appropriately weighted Kullback-Leibler (KL) divergence, one recovers the natural policy gradient (NPG) method of Kakade (2001). In general, we can think of (5) as a class of preconditioned policy gradient methods. The main results of this paper concern the convergence rates of such methods.

Many classical algorithms for DMDP are based on dynamical programming (Bellman, 1957), including value iteration, policy iteration, temporal difference learning and Q-learning (see, e.g., Puterman, 1994; Bertsekas and Tsitsiklis, 1996; Sutton and Barto, 2018). Analyses of these methods in the tabular case mostly rely on the contraction property of the Bellman operator, which are difficult to extend with nonlinear function approximation and policy parametrization. In contrast, policy gradient methods (Williams, 1992; Sutton et al., 2000; Konda and Tsitsiklis, 2000; Kakade, 2001) aim to find a local minimum of an expected value function, thus are applicable to any differentiable policy parametrization and admit easy extensions to function approximation. In particular, they appear to work well when parametrized with modern deep neural networks (Schulman et al., 2015, 2017).

Despite the long history and empirical successes of policy gradient methods, their convergence properties are not well understood until recently. For example, it was widely accepted that they converge asymptotically to a stationary point or a local minimum because the objective function is nonconvex in general. However, Fazel et al. (2018) show that for linear quadratic control problems, policy gradient methods converge to the global optimal solution despite the nonconvex cost function, thanks to a gradient dominance property (Polyak, 1963). Agarwal et al. (2021) derive a variational gradient-dominance property and use it to obtain global convergence of the projected policy gradient method (4). Bhandari and Russo (2019) identify more general structural properties of policy gradient methods to ensure gradient domination and hence convergence to global optimum.

Using direct policy parametrization (over $\pi\in\Delta(\mathcal{A})^{|\mathcal{S}|}$), Agarwal et al. (2021) show that the projected policy gradient method (4) converges to a global optimum at an $O(1/\sqrt{k})$ sublinear rate. Specifically, the number of iterations to obtain $V_{\rho}(\pi^{(k)})-V_{\rho}^{\star}\leq\epsilon$ is

where $d_{\rho}(\pi^{\star})\in\Delta(\mathcal{S})$ is a discounted state-visitation distribution and \bigl{\|}d_{\rho}(\pi^{\star})/\mu\bigr{\|}_{\infty} is a distribution mismatch coefficient (see Section 2.1 for definition and explanation). Zhang et al. (2020) develop a variational policy gradient framework and use it to show that the projected policy gradient method converges to global optimum at a faster $O(1/k)$ rate. In both cases, the constants in the iteration complexity are very large and depend on the Lipschitz constant characterizing the smoothness of the objective function.

Shani et al. (2020) show that the natural policy gradient (NPG) method (Kakade, 2001) can be cast as a special case of policy mirror descent method (5) and has an $O(1/\sqrt{k})$ convergence rate. Agarwal et al. (2021) improve the convergence rate of NPG to $O(1/k)$; more concretely, the number of iterations to obtain $V_{\rho}(\pi^{(k)})-V_{\rho}^{\star}\leq\epsilon$ is

which is independent of the dimensions ${|\mathcal{S}|}$ and ${|\mathcal{A}|}$ or any distribution mismatch coefficient. Interestingly, the step sizes that guarantee such a rate can be chosen arbitrarily large, regardless of the Lipschitz constant of the policy gradient.

With entropy regularization (added to the DMDP objective), Cen et al. (2020) show that the NPG method has linear (geometric) convergence. Their approach rely on the contraction property of a generalized Bellman operator and the convergence guarantees are in terms of the infinity norm of the “soft” $Q$-functions. With appropriate choice of the regularization parameter and step size, they obtain iteration complexity on the order of

Lan (2021) proposes a general policy mirror descent method that is similar to (5) with either convex or strongly convex regularizations. He focuses on the case of minimizing $V_{\rho^{\star}}$ where $\rho^{\star}$ is the stationary distribution of the MDP under the optimal policy $\pi^{\star}$, which avoids any distribution mismatch coefficient in the analysis. In order to guarantee $V_{\rho^{\star}}(\pi^{(k)})-V_{\rho^{\star}}^{\star}\leq\epsilon$, Lan (2021) obtains iteration complexity on the orders of (7) and (8) for the settings without and with entropy regularization, respectively. More interestingly, Lan (2021) also obtained linear convergence for the un-regularized DMDP using diminishing regularization combined with increasing step sizes (while maintaining a constant product of the two).

More recently, Zhan et al. (2021) extend the framework of Lan (2021) to accommodate a broader class of convex regularizers including those that are nonsmooth. For un-regularized DMDP, Khodadadian et al. (2021) show that the NPG method can obtain linear convergence with an adaptive step-size rule, and Bhandari and Russo (2021) show that several variants of policy gradient methods has linear convergence with exact line search.

For the exact policy gradient method with softmax parametrization, Agarwal et al. (2021) show that it converges asymptotically to a global optimum, and attains an $O(1/\sqrt{k})$ rate with log barrier regularization. Mei et al. (2020) derive an $O(1/k)$ convergence rate and Mei et al. (2021) further improve it to linear convergence by exploiting non-uniform variants of the smoothness and gradient dominance properties. However, these fast rates are associated with problem-dependent constants that can be very large (Li et al., 2021).

2 Contributions and Outline

In this paper, we present a systematic study of policy gradient methods with direct policy parametrization, focusing on their convergence rates for minimizing $V_{\rho}$ over $\pi\in\Delta(\mathcal{A})^{|\mathcal{S}|}$.

Section 2 contains an overview of structural properties of DMDP that are well-known but essential for the main results of the paper.

In Section 3, we develop a theory of weak gradient-mapping domination for general nonconvex composite optimization, and use it to obtain an $O(1/k)$ convergence rate for the projected policy gradient method. Concretely, our result on iteration complexity replaces $\epsilon^{-2}$ in (6) with $\epsilon^{-1}$ and $(1-\gamma)^{-6}$ with $(1-\gamma)^{-5}$. Although this result is the same as the one obtained by Zhang et al. (2020), our analysis are quite different. Zhang et al. (2020) exploit the bijection structure of the primal-dual DMDP formulations, while we derive this result as a special case of nonconvex optimization with weak gradient-mapping domination which, to our best knowledge, is new and of independent interest.

In Section 4, we study exact policy mirror descent methods of the form (5). First, we show that with a constant step size (which can be arbitrarily large), they obtain the same dimension-free iteration complexity (7). This result extend the one of Agarwal et al. (2021) on NPG with KL-divergence to a general class of Bregman divergences, including a projected $Q$-descent method derived with squared Euclidean distance. Second, we show that with geometrically increasing step sizes, as simple as $\eta_{k+1}=\eta_{k}/\gamma$, policy mirror descent methods enjoy linear convergence without relying on any regularization. Specifically, their iteration complexity for reaching $V_{\rho}(\pi^{(k)})-V_{\rho}^{\star}\leq\epsilon$ is

If $\rho$ is set to be the stationary distribution under the optimal policy $\pi^{\star}$, then the distribution mismatch coefficient \bigl{\|}d_{\rho}(\pi^{\star})/\rho\bigr{\|}_{\infty}=1 and we recover (8). In addition, we discuss conditions for superlinear convergence and make connections with the classical Policy Iteration method.

In Section 5, we investigate the iteration complexity of inexact policy mirror descent methods and show that the geometrically increasing step sizes do not cause instability even with errors in evaluating the policy gradients or $Q$-functions. They converge with the same linear rate up to an asymptotic error floor. With a simple $Q$-estimator by repeated simulation of truncated trajectories, we obtain a sample complexity of

where the notation $\widetilde{O}(\cdot)$ hides poly-logarithmic factors of ${|\mathcal{S}|}{|\mathcal{A}|}$, $1/(1-\gamma)$ and $1/\epsilon$.

Finally, in Section 6, we discuss the limitations of our work and possible extensions.

Preliminaries on DMDP

In this section, we overview the structural properties of DMDP that are essential for the developments in later sections. We start with a few definitions. Let $\Delta(\mathcal{S})$ denote the probability simplex defined over the state space $\mathcal{S}$, i.e.,

Similarly, $\Delta(\mathcal{A})$ denotes the probability simplex over the action space $\mathcal{A}$. The set of admissible policies for DMDP is defined as

With slight abuse of notation, we define the following functions of $\pi\in\Pi$:

$P:\Pi\to\mathbf{R}^{{|\mathcal{S}|}\times{|\mathcal{S}|}}$: a matrix function with entries $P_{s,s^{\prime}}(\pi)=\sum_{a\in\mathcal{A}}\pi_{s,a}P(s^{\prime}|s,a)$;

$r:\Pi\to\mathbf{R}^{|\mathcal{S}|}$: a vector function with components $r_{s}(\pi)=\sum_{a\in\mathcal{A}}\pi_{s,a}R_{s,a}$.

Using the definitions above, the value function $V:\Pi\to\mathbf{R}^{|\mathcal{S}|}$, whose components $V_{s}$ are defined in (1), admits the following analytic form (see, e.g., Puterman, 1994, Section 6.1)

Since $P(\pi)$ is a row stochastic matrix and $0\leq\gamma<1$, the spectral norm of $\gamma P(\pi)$ is strictly less than one (by the Perron-Frobenius theorem) and thus $I-\gamma P(\pi)$ is always invertible. Given $\rho\in\Delta(\mathcal{S})$, the weighted value function $V_{\rho}$ defined in (3) can be written as

Here we treat $\rho$ as a column vector and use matrix multiplication conventions.

Starting from $s\in\mathcal{S}$, the discounted state-visitation distribution under a policy $\pi$ is a vector $d_{s}(\pi)\in\Delta(\mathcal{S})$ whose components are defined as

The coefficient $1-\gamma$ ensures that $\sum_{s^{\prime}\in\mathcal{S}}d_{s,s^{\prime}}(\pi)=1$. In fact, $d_{s,s^{\prime}}(\pi)$ is the $(s,s^{\prime})$ entry of the matrix $(1-\gamma)(I-\gamma P(\pi))^{-1}$. In other words, if we define $e_{s}\in\mathbf{R}^{|\mathcal{S}|}$ with components $e_{s,s^{\prime}}=1$ if $s=s^{\prime}$ and otherwise, then we have

Given an initial state distribution $\rho\in\Delta(\mathcal{S})$, we define $d_{\rho}(\pi)\in\Delta(\mathcal{S})$ with components

Some useful facts from the above definitions are:

For any $\rho,\mu\in\Delta(\mathcal{S})$, we define the distribution mismatch of $\rho$ from $\mu$ as

with the convention $0/0=1$. This is an asymmetric measure of mismatch and it is finite if and only if the support (set of indices with nonzero entries) of $\mu$ contains that of $\rho$. If $\mu$ is the uniform distribution, then the mismatch is bounded by ${|\mathcal{S}|}$.

The convergence properties of policy gradient methods often depend on the distribution mismatch coefficients between two discounted state-visitation distributions (e.g., Kakade and Langford, 2002; Agarwal et al., 2021). According to (13), we have for any $\rho,\mu\in\Delta(\mathcal{S})$ and $\pi,\pi^{\prime}\in\Pi$,

Our results in this paper mostly concern the case with $\rho=\mu$ and $\pi=\pi^{\star}$, i.e.,

In order for $C^{\star}_{\rho}$ to be finite, it suffices to assume $\rho>0$, which means $\rho_{s}>0$ for all $s\in\mathcal{S}$.

The distribution mismatch coefficient is closely related to the concentrability coefficients in the analysis of approximate dynamic programming algorithms (Munos, 2003, 2005; Szepesvári and Munos, 2008). In fact, $C_{\rho}^{\star}$ is considered the “best” one among all concentrability coefficients in the sense that it does not impose any restrictions on the MDP dynamics and it can be finite when other concentrability coefficients are infinite (Scherrer, 2014). See Agarwal et al. (2021, Section 2) for further discussions.

If $\rho$ is chosen as the stationary distribution of the MDP under the optimal policy $\pi^{\star}$, denoted as $\rho^{\star}$, then we have $d_{\rho^{\star}}(\pi^{\star})=\rho^{\star}$ and hence $C^{\star}_{\rho^{\star}}=1$. This is the setting adopted by Liu et al. (2019) and Lan (2021), which leads to simplified analysis for minimizing $V_{\rho^{\star}}$. For DMDP with entropy regularization (Lan, 2021; Cen et al., 2020), the resulting $\rho^{\star}$ always have full support over $\mathcal{S}$. However, in general $\rho^{\star}$ may not have full support over $\mathcal{S}$ unless the underlying MDP is ergodic (Puterman, 1994, Section A.2).

2 Q𝑄Q-functions, Policy Gradient and Performance Difference Lemma

For each pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, the state-action value function $Q_{s,a}:\Pi\to\mathbf{R}$ is defined as

where the expectation is taken with respect to $a_{t}\sim\pi_{s_{t}}$ and $s_{t+1}\sim P(\cdot|s_{t},a_{t})$ for all $t\geq 0$. It is straightforward to verify that

Let $Q_{s}(\pi)\in\mathbf{R}^{|\mathcal{A}|}$ denote the vector with components $Q_{s,a}(\pi)$ for all $a\in\mathcal{A}$. Then,

where $\langle\cdot,\cdot\rangle$ denotes the inner product of two vectors.

Policy gradients refer to the gradients of the value functions $V_{s}(\pi)$ and $V_{\rho}(\pi)$. We can obtain their expressions as special cases of the policy gradient theorem (Sutton et al., 2000) which covers the general case with policy parametrization. For easy reference, we give a simple, self-contained derivation in the Appendix (Section A.1). Specifically, we have

and $\nabla V_{\rho}$ is the concatenation of $\nabla_{\!s}V_{\rho}$ for all $s\in\mathcal{S}$. In other words, policy gradients are weighted $Q$-functions where the weights are block-diagonal and proportional to the discounted state-visitation probabilities.

A fundamental result for analyzing DMDP and related algorithms is the performance difference lemma of Kakade and Langford (2002). In this paper, we mostly rely on the following variant, which has appeared in Liu et al. (2019) and Lan (2021). For completeness, here we provide an alternative proof.

Using the expression of $d_{s,s^{\prime}}(\pi)$ in (12), we write the above equality component-wise as

The weighted version of the performance difference lemma is,

Projected Policy Gradient Method

In this section, we analyze the projected policy gradient method for solving the problem

where $V_{\rho}(\pi)$ is defined in (3) or equivalently (10). We assume that the policy gradients are computed with respect to an initial state distribution $\mu$, which may be different from the performance evaluation distribution $\rho$.

Starting from an initial policy $\pi^{(0)}\in\Pi$, the projected policy gradient method generates a sequence $\pi^{(k)}$ for $k=1,2,\ldots$ as follows:

where $\eta_{k}$ is the step size and $\mathbf{proj}_{\Pi}(\cdot)$ denotes projection onto $\Pi$ in Euclidean norm, i.e., $\mathbf{proj}_{\Pi}(\pi)=\operatorname*{arg\,min}_{\pi^{\prime}\in\Pi}\|\pi^{\prime}-\pi\|_{2}^{2}$. Since $\Pi=\Delta(\mathcal{A})^{|\mathcal{S}|}$ is a Cartesian product, the projections associated with different states can be done separately:

where $\nabla_{\!s}V_{\mu}$ is given by (18) with $\rho$ replaced by $\mu$.

Agarwal et al. (2021, Theorem 5) show that with a constant step size $\eta_{k}=\frac{(1-\gamma)^{3}}{2\gamma{|\mathcal{A}|}}$ for all $k\geq 0$, the projected policy gradient method converges at an O\bigl{(}1/\sqrt{k}\bigr{)} rate. More precisely,

The following two ingredients are key to their analysis.

Smoothness (Agarwal et al., 2021, Lemma 54): For any $\pi,\pi^{\prime}\in\Pi$, it holds that

Variational gradient domination (Agarwal et al., 2021, Lemma 4): For any $\pi\in\Pi$,

Here “variational” refers to the term $\max_{\pi^{\prime}\in\Pi}\langle\nabla V_{\mu}(\pi),\pi-\pi^{\prime}\rangle$, which is different from $\|\nabla V_{\mu}(\pi)\|$ as in gradient dominance conditions for unconstrained optimization.

Based on the same two results above, we show that the projected policy gradient method enjoys a faster $O(1/k)$ convergence rate. The following theorem holds for the case $\rho=\mu$.

Suppose $\rho=\mu$ and the step size $\eta_{k}=\frac{(1-\gamma)^{3}}{2\gamma{|\mathcal{A}|}}$ for all $k\geq 0$. Then the projected policy gradient method (22) generates a sequence of policies $\pi^{(k)}$ satisfying

The general case with $\rho\neq\mu$ can be handled with an additional distribution mismatch coefficient. Concretely,

Then applying Theorem 2 with $\rho$ replaced by $\mu$ yields

Comparing with (24), in addition to improving the rate from $O(1/\sqrt{k})$ to $O(1/k)$, our bound also has better dependence on the discount factor: $1/(1-\gamma)^{5}$ as opposed to $1/(1-\gamma)^{6}$. However, our bound uses a different distribution mismatch coefficient and has an additional factor of $\|\rho/\mu\|_{\infty}$.

We prove Theorem 2 as a special case of a more general result on gradient-mapping domination, which we present next.

In this section, we consider the following composite optimization problem

where $f$ is smooth and $\Psi$ is convex and lower semi-continuous. More specifically, we assume that there exists a constant $L>0$ such that

The MDP formulation in (21) is a special case of (27) with the mappings $x\leftarrow\pi$, $f\leftarrow V_{\rho}$ and $\Psi$ as the indicator function of $\Pi$, i.e., $\Psi(\pi)=0$ if $\pi\in\Pi$ and $\infty$ otherwise.

For any convex function $\phi$, the $\operatorname{\mathbf{prox}}$ operator is defined as

A generic algorithm for solving problem (27) is the proximal gradient method:

where $\eta_{k}$ is the step size. If $\Psi$ is the indicator function of $\Pi$, then $\operatorname{\mathbf{prox}}_{\eta_{k}\Psi}$ becomes the projection operator $\mathbf{proj}_{\Pi}$ for any $\eta_{k}>0$. In this section, we focus on the proximal gradient method with the constant step size $\eta_{k}=1/L$. To simplify presentation, we define

thus the proximal gradient method (29) can be written simply as $x^{(k+1)}=T_{L}(x^{(k)})$. The gradient mapping associated with problem (27) is defined as

In the special case $\Psi\equiv 0$, we have $G_{L}(x)=\nabla f(x)$ for any $L>0$. The norm of the gradient mapping, $\|G_{L}(x^{(k)})\|$, can serve as a measure of closeness to a first-order stationary point.

Key to the convergence analysis of the proximal gradient method is the following descent property (Nesterov, 2013, Theorem 1),

Summing up over $k=0,1,\ldots,K$, we obtain

which, together with the fact $F(x^{(K+1)})\geq F^{\star}$, implies (Beck, 2017, Theorem 10.15)

The $O(1/\sqrt{k})$ convergence rate stated in (24) is obtained by combining (33) with (26), which is the approach taken by Agarwal et al. (2021) and Bhandari and Russo (2019).

We show that under similar conditions, the proximal gradient method actually enjoy a faster $O(1/k)$ rate of convergence. To this end, the following notion of (weak) gradient-mapping domination is a proper extension of (weak) gradient domination.

Suppose $F:=f+\Psi$ where $f$ is $L$-smooth and $\Psi$ is proper, convex and closed. We say that $F$ satisfies a weak gradient-mapping dominance condition if there exists $\omega>0$ such that

where $F^{\star}=\min_{x}F(x)$ and $T_{L}$ and $G_{L}$ are defined in (30) and (31) respectively.

This weak version of gradient-mapping domination corresponds to the Kurdyka-Łojasiewicz (KŁ) condition with KŁ exponent $1$, instead of the usual exponent $1/2$ that leads to linear convergence (Kurdyka, 1998; Karimi et al., 2016; Li and Pong, 2018). We discuss the stronger notion of gradient-mapping dominance in Appendix A.2.

In the following theorem, we prove the $O(1/k)$ convergence rate for problems satisfying weak gradient-mapping domination.

Consider the problem of minimizing $F:=f+\Psi$ where $f$ is $L$-smooth and $\Psi$ is proper, convex and closed. Suppose $F$ is weakly gradient-mapping dominant with parameter $\omega$ and let $F^{\star}=\min_{x}F(x)$. Then the proximal gradient method (29) with a constant step size $\eta_{k}=1/L$ generates a sequence $\{x^{(k)}\}$ that satisfies, for all $k\geq 0$,

Proof Combining the descent property (32) with the inequality (34) yields

Let $\delta_{k}=F(x^{(k)})-F^{\star}\geq 0$ Then we have

We divide both sides of the above inequality by $\delta_{k}\delta_{k+1}$ to obtain

Then telescoping sum over iterations $0,1,\ldots,k-1$ yields

Notice that due to the descent property, we always have $\delta_{i+1}\leq\delta_{i}$ and thus $\delta_{i+1}/\delta_{i}\leq 1$.

For any two constant $r,c\in(0,1)$, let’s define $n(k,r)$ be the number of times that the ratio $\delta_{i+1}/\delta_{i}$ is at least $r$ among the first $k$ iterations. If $n(k,r)\geq ck$, then $\delta_{i+1}/\delta_{i}\geq r$ at least $\lceil ck\rceil$ times, thus

Otherwise, we must have $n(k,r)<ck$, which means that $\delta_{i+1}/\delta_{i}<r$ at least $\lceil(1-c)k\rceil$ times. Noticing that $\delta_{i+1}/\delta_{i}\leq 1$ for all $i$, we arrive at

Combining the above two cases and using the fact that $r,c\in(0,1)$ can be chosen arbitrarily, we conclude that

Simply setting $r=c=1/2$ gives the desired result (35).

2 Proof of Theorem 2

In order to prove Theorem 2, we only need to verify that the weak gradient-mapping domination holds for the weighted value function $V_{\rho}$. This is the result of the next lemma.

Consider the problem of minimizing $V_{\rho}$ over $\Pi$ and suppose that $V_{\rho}$ is $L$-smooth. We have

Proof Applying a result of Nesterov (2013, Theorem 1) to our setting yields

Using the facts $T_{L}(\pi)\in\Pi$ and $\|\pi^{\prime\prime}-\pi^{\prime}\|_{2}\leq\sqrt{2{|\mathcal{S}|}}$ for any $\pi^{\prime\prime},\pi^{\prime}\in\Pi$, we obtain

Combining the above bound with (26) yields the desired result.

An argument equivalent to Lemma 5 was used by Agarwal et al. (2021) which relies on a result of Ghadimi and Lan (2016). Combining (36) with (33) gives the result in (24). On the other hand, we recognize that with $\rho=\mu$, inequality (36) implies (34) with

Now we can apply Theorem 4. Notice that in this case, the exponential decay part in (35) is always smaller than the sublinear part, which leads to $V_{\rho}(\pi^{(k)})-V_{\rho}^{\star}\leq 4L/(\omega k)$, i.e.,

Zhang et al. (2020, Theorem 5) have also established the $O(1/k)$ rate of the projected policy gradient method with direct parametrization. However, their proof appears to be quite different from ours, which leverages the dual linear programming parametrization (Puterman, 1994, Section 6.9). In contrast, our approach is based on a novel notion of weak gradient-mapping domination and applies to general nonconvex composite optimization problems.

Exact Policy Mirror Descent Methods

Mirror descent (Nemirovski and Yudin, 1983) is a general framework for the construction and analysis of optimization algorithms, which covers the projected gradient method as a special case. Here we adopt the form of mirror descent based on proximal minimization with respect to a Bregman divergence (Beck and Teboulle, 2003).

Let $h:\Delta(\mathcal{A})\to\mathbf{R}$ be a strictly convex function and continuously differentiable on the relative interior of $\Delta(\mathcal{A})$, denoted as $\operatorname{rint}\Delta(\mathcal{A})$. The Bregman divergence generated by $h$ is a distance-like function defined as

Two most popular examples of Bregman divergence are:

Squared Euclidean distance, generated by the squared $2$-norm:

Kullback-Leibler (KL) divergence, generated by the negative entropy:

Notice that the gradient of negative entropy vanishes on the boundary of the simplex. Therefore we need to restrict the second argument $p^{\prime}$ to lie within the relative interior of $\Delta(\mathcal{A})$. We shall address such subtleties later in the convergence analysis.

Recall that the set of feasible policies is $\Pi=\Delta(\mathcal{A})^{|\mathcal{S}|}$, which is a Cartesian product of ${|\mathcal{S}|}$ copies of $\Delta(\mathcal{A})$. For any $\rho\in\Delta(\mathcal{S})$, we define a weighted divergence function

This function satisfies the basic properties of a Bregman divergence; in particular, it is nonnegative and equals to if and only if $\pi=\pi^{\prime}$.

Following the derivations of Shani et al. (2020), we consider policy mirror descent (PMD) methods with dynamically weighted divergences:

where $\eta_{k}$ is the step size, $\mu\in\Delta(\mathcal{S})$ is an arbitrary state distribution and $d_{\mu}(\pi^{(k)})$ is the discounted state-visitation distribution under the policy $\pi^{(k)}$. Using the fact

and plugging in the policy gradient formula (18), we obtain

which can be written separately for each state as

Notice that the above update rule is independent of the choice of $\mu$. This is the result of adaptive preconditioning with a dynamically weighted divergence: the weight for each state in $D_{d_{\mu}(\pi^{(k)})}$ matches the coefficient of $Q_{s}(\pi^{(k)})$ in the policy gradient $\nabla V_{\mu}(\pi^{(k)})$.

For the two prominent examples of Bregman divergence listed before, the corresponding PMD methods have closed-form update rules:

Projected $Q$-descent. If $D(\cdot,\cdot)$ is the squared Euclidean distance, then (37) becomes

Compared with the projected policy gradient method (23), we replaced the policy gradient $\nabla_{s}V_{\mu}(\pi^{(k)})$ by $Q_{s}(\pi^{(k)})$ as the result of adaptive preconditioning.

Exponentiated $Q$-descent. If $D(\cdot,\cdot)$ is the KL-divergence, then (37) takes the form

This is exactly the Natural Policy Gradient (NPG) method (Kakade, 2001) expressed in the policy space (Agarwal et al., 2021).

In the rest of this section, we investigate the convergence rate of the PMD method (37). We show that with a constant step size, it has $O(1/k)$ convergence rate. When the step size increases exponentially as $\eta_{k}=\eta_{0}/\gamma^{k}$, we have linear convergence and the convergnece rate depends on the distribution mismatch coefficient $\|d_{\rho}(\pi^{\star})/\rho\|_{\infty}$. In addition, we discuss situations of super-linear convergence and connections to policy iteration.

Our results hold for PMD methods constructed with general Bregman divergences, matching or improving over the best known convergence rates. In particular, the projected $Q$-descent method has the same rate of convergence as NPG. We show that the key ingredient for fast convergence of the PMD method is the adaptive preconditioning using weighted divergence functions. The adopted local Bregman divergence, being KL-divergence or squared Euclidean distance, does not make much difference.

Our analysis is based on two key ingredients: the performance difference lemma (Lemma 1) and a three-point descent lemma on proximal optimization with Bregman divergences.

In order to cover both the squared Euclidean distance and KL-divergence without loss of rigor, we need some technical conditions. Specifically, we say a function $h$ is of Legendre type (Rockafellar, 1970, Section 26) if it is essentially smooth and strictly convex in the relative interior of $\operatorname{dom}h$, denoted as $\operatorname{rint}\operatorname{dom}h$. Essential smoothness means that $h$ is differentiable and $\|\nabla h(x_{k})\|\to\infty$ for every sequence $\{x_{k}\}$ converging to a boundary point of $\operatorname{dom}h$. The following result is a slight variation of Chen and Teboulle (1993, Lemma 3.2), where we replaced the original assumption of $h$ being a Bregman function with $h$ being of Legendre type. The proof essentially follows the same arguments and thus is omitted here.

Suppose that $\mathcal{C}\subset\mathbf{R}^{n}$ is a closed convex set, $\phi:\mathcal{C}\to\mathbf{R}$ is a proper, closed convex function, $D(\cdot,\cdot)$ is the Bregman divergence generated by a function $h$ of Legendre type and $\operatorname{rint}\operatorname{dom}h\cap\mathcal{C}\neq\varnothing$. For any $x\in\operatorname{rint}\operatorname{dom}h$, let

Then $x^{+}\in\operatorname{rint}\operatorname{dom}h\cap\mathcal{C}$ and for any $u\in\mathcal{C}$,

In the context of the PMD method (37), $\mathcal{C}=\Delta(\mathcal{A})$ and $\phi$ is the linear function $\eta_{k}\langle Q_{s}(\pi^{(k)}),\,\cdot\,\rangle$. There are some subtle differences between the two Bregman divergences we consider, as explained below.

For the squared Euclidean distance, $h(\cdot)=(1/2)\|\cdot\|_{2}^{2}$ is of Legendre type with $\operatorname{rint}\operatorname{dom}h=\mathbf{R}^{|\mathcal{A}|}$ and thus $\operatorname{rint}\operatorname{dom}h\cap\mathcal{C}=\Delta(\mathcal{A})$. Therefore each iterate generated by the PMD method, specifically (38), can be on the boundary of $\Delta(\mathcal{A})$.

For the KL divergence, $h$ is the negative entropy function, which is also of Legendre type, but with $\operatorname{rint}\operatorname{dom}h\cap\mathcal{C}=\operatorname{rint}\operatorname{dom}h=\operatorname{rint}\Delta(\mathcal{A})$. Therefore, if we start with an initial point in $\operatorname{rint}\Delta(\mathcal{A})$, then every iterates will stay in $\operatorname{rint}\Delta(\mathcal{A})$.

We first use Lemma 6 to prove a descent property of PMD. This result is elementary and has appeared in various forms before (e.g., Liu et al., 2019; Lan, 2021). We present the proof for completeness as we will need to refer to some intermediate steps in it later.

Suppose the initial point $\pi^{(0)}\in\operatorname{rint}\Pi$. Then the sequences generated by the PMD method (37) satisfy

Proof Applying Lemma 6 to the update rule (37) with $\mathcal{C}=\Delta(\mathcal{A})$ and $\phi(\cdot)=\eta_{k}\langle Q_{s}(\pi^{k}),\,\cdot\,\rangle$, we obtain that for any $p\in\Delta(\mathcal{A})$,

Rearranging terms and dividing both sides by $\eta_{k}$, we get

which implies (40) since the Bregman divergence $D(\cdot,\cdot)$ is always nonnegative. By the performance difference lemma, specifically the weighted version (20), we have

The next result is a generalization of the $O(1/k)$ convergence rate of the NPG method obtained by Agarwal et al. (2021, Theorem 16), where they focused on the setting of KL-divergence and their proof also relies on specific properties of the KL-divergence. Here we extend it to more general Bregman divergence. Lan (2021, Theorem 2) derived a similar result using techniques that works for general Bregman divergence. However, he worked with the special objective function $V_{\rho^{\star}}$ where $\rho^{\star}$ is the stationary distribution of the optimal policy $\pi^{\star}$. As a result, the proof of Lan (2021, Theorem 2) avoids some subtle arguments required for the more general objective function $V_{\rho}$ where $\rho\in\Delta(\mathcal{S})$ can be arbitrary.

In order to simplify presentation, we use the following notation throughout this paper:

where $d_{\rho}(\pi^{\star})$ is the state-visitation distribution under $\pi^{\star}$ with initial state distribution $\rho$. Although $\rho$ does not appear in the notation $D^{\star}_{k}$, we hope it is clear from the context.

Consider the policy mirror descent method (37) with $\pi^{(0)}\in\operatorname{rint}\Pi$ and constant step size $\eta_{k}=\eta$ for all $k\geq 0$. For any $\rho\in\Delta(\mathcal{S})$, we have for all $k\geq 0$,

Proof Consider the inequality (42), we let $p=\pi^{\star}_{s}$ and subtract and add $\pi^{(k)}_{s}$ within the inner product term, which leads to

Notice that we dropped the nonnegative term $(1/\eta_{k})D(\pi^{(k+1)}_{s},\pi^{(k)}_{s})$ on the left side of the inequality. Taking expectation with respect to the distribution $d_{\rho}(\pi^{\star})$ on both sides of the above inequality and using the notation in (43), we obtain

For the first expectation in (44), we have

where the inequality holds because of (40) and the fact, due to (13), that

The last equality in (45) is due to the performance difference lemma. For the second expectation in (44), we again use the performance difference lemma to obtain

Substituting the two results above into (44) leads to

Setting $\eta_{k}=\eta$ for all $k\geq 0$ and summing up over $k$:

Since $V_{\rho}(\pi^{(k)})$ is monotone non-increasing in $k$ (see Lemma 7), we conclude that

Finally, bounding $V_{d_{\rho}(\pi^{\star})}(\pi^{(0)})$ by $1/(1-\gamma)$ as in (2) gives the desired result.

As a result of Theorem 8, whenever $\eta\geq(1-\gamma)D_{d_{\rho}(\pi^{\star})}(\pi^{\star},\pi^{(0)})$, we have

In other words, the number of iterations to reach $V_{\rho}(\pi^{(k)})-V_{\rho}^{\star}\leq\epsilon$ is at most

which is independent of the problem dimensions ${|\mathcal{S}|}$ and ${|\mathcal{A}|}$. More specifically,

For the projected $Q$-descent method (38), since $D(\pi_{s},\pi^{\prime}_{s})=(1/2)\|\pi_{s}-\pi^{\prime}_{s}\|^{2}\leq 1$ for any $\pi_{s},\pi^{\prime}_{s}\in\Delta(\mathcal{A})$, we have $D_{\rho}(\pi,\pi^{\prime})=\sum_{s\in\mathcal{S}}\rho_{s}D(\pi_{s},\pi^{\prime}_{s})\leq 1$ for any $\rho\in\Delta(\mathcal{S})$. Therefore in order for (47) to hold, it suffices to have $\eta\geq(1-\gamma)$.

For the exponentiated $Q$-descent method (39), if we choose the uniform initial policy, i.e., $\pi^{(0)}_{s,a}=1/{|\mathcal{A}|}$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$, then $D_{\rho}(\pi^{\star},\pi^{(0)})\leq\log{|\mathcal{A}|}$ for all $\rho\in\Delta(\mathcal{S})$. Therefore in order for (47) to hold, it suffices to have $\eta\geq(1-\gamma)\log{|\mathcal{A}|}$.

The above analysis indicates that the projected $Q$-descent method may have a slight advantage over the exponentiated variant (NPG) in terms of having a wider range of $\eta$ to enjoy the same dimensional independent convergence guarantee (47).

A more curious fact is that for both variants, the step size $\eta$ does not have an upper bound and can be as large as possible. This is in contrast to the classical analysis of smooth optimization, where the step size is usually upper bounded by $2/L$ with $L$ being the Lipschitz constant of the gradient; see, e.g., the approach taken in Section 3.1. Here the fact the step sizes can be arbitrarily large is due to the unique structure of DMDP. Indeed, we show next that PMD has linear convergence if the step size grows exponentially.

2 Linear Convergence

Consider again the policy mirror descent algorithm (37). In order to simplify the presentation, we define two more notations: the optimality gap

which is always nonnegative, and the per-iteration distribution mismatch coefficient

The following result is the basis for establishing the linear convergence and also for discussions on possible superlinear convergence.

Consider the policy mirror descent method (37) with $\pi^{(0)}\in\operatorname{rint}\Pi$ and $\eta_{k}>0$ for all $k\geq 0$. Then for any $\rho\in\Delta(\mathcal{S})$, we have for all $k\geq 0$,

where $\delta_{k}$, $\vartheta_{k}$ and $D^{\star}_{k}$ are defined in (48), (49) and (43), respectively.

Proof We start with the inequality (44) and bound the first expectation as follows:

where the inequality holds because of (40), and the last equality is due to the performance difference lemma, specifically (20). Substituting the above bound and (46) into (44) and dividing both sides by $1-\gamma$ yield the desired result.

The next theorem is our main result on linear convergence. The convergence rate depends on the performance evaluation distribution $\rho$ through the following quantity:

which is an upper bound on $\vartheta_{k}$ for all $k\geq 0$.

Consider the policy mirror descent method (37) with $\pi^{(0)}\in\operatorname{rint}\Pi$. Suppose the step sizes satisfy $\eta_{0}>0$ and

Proof Using (13), specifically $d_{\rho,s}(\pi^{(k)})\geq(1-\gamma)\rho_{s}$ for all $s\in\mathcal{S}$, we have $\vartheta_{k}\leq\vartheta_{\rho}$ for all $k\geq 0$. In addition, by Lemma 7, we have $\delta_{k+1}-\delta_{k}\leq 0$ for all $k\geq 0$. Therefore (50) still holds if we replace $\vartheta_{k+1}$ by its upper bound $\vartheta_{\rho}$, i.e.,

Dividing both sides by $\vartheta_{\rho}$ and rearranging terms, we obtain

If the step sizes satisfy (52), i.e., $\eta_{k+1}(\vartheta_{\rho}-1)\geq\eta_{k}\vartheta_{\rho}$, then we have

Finally, using the fact $\vartheta_{\rho}\geq 1/(1-\gamma)$, we derive

Substituting the above bound into the right side of (54), and considering the nonnegativity of $D^{\star}_{k}$ on the left side, we arrive at the desired bound (53).

The exact value of $\vartheta_{\rho}$ is hard to estimate in practice, which hinders the use of the step size rule (52). However, we can replace it with the more aggressive increasing rule

which always implies (52). To see this, we use $\vartheta_{\rho}\geq 1/(1-\gamma)$ to derive

According to Theorem 10, in order to guarantee $V_{\rho}(\pi^{(k)})-V_{\rho}^{\star}\leq\epsilon$, the required number of iterations of the PMD method is

Using the bound (2) and assuming $\eta_{0}\geq\frac{1-\gamma}{\gamma}D^{\star}_{0}$, the iteration complexity becomes

Next we discuss a special choice of the performance evaluation distribution $\rho$.

Let $\rho^{\star}\in\Delta(\mathcal{S})$ be the stationary state distribution of the MDP under the optimal policy $\pi^{\star}$. If the MDP starts with $s\sim\rho^{\star}$ and following $\pi^{\star}$, then the visit probability at every step is $\rho^{\star}$ and so is the discounted sum of them. Therefore we have $d_{\rho^{\star}}(\pi^{\star})=\rho^{\star}$, which implies

In this case, with the step size rule $\eta_{0}\geq\frac{1-\gamma}{\gamma}D^{\star}_{0}$ and $\eta_{k+1}\geq\eta_{k}/\gamma$, we have

and the iteration complexity for $V_{\rho^{\star}}(\pi^{(k)})-V_{\rho^{\star}}(\pi^{\star})\leq\epsilon$ is dimension-independent:

However, unless the MDP is ergodic, the support of $\rho^{\star}$ may not cover the full state space $\mathcal{S}$.

Several recent work studied policy mirror descent method for entropy-regularized MDP and obtained similar linear convergence rates (Cen et al., 2020; Lan, 2021; Zhan et al., 2021). With entropy regularization, the resulting MDP is always ergodic and the support of any stationary distribution covers the full state space $\mathcal{S}$, i.e., $\rho^{\star}>0$. Lan (2021) only considers $\rho^{\star}$ as the performance evaluation distribution; Cen et al. (2020) and Zhan et al. (2021) rely on the contraction properties of a generalized Bellman operator and obtain guarantees of the form $\|Q(\pi^{(k)})-Q(\pi^{\star})\|_{\infty}\leq\epsilon$ where $Q$ is the “soft” $Q$-function with regularization. Our analysis closely resembles that of Lan (2021), with the following differences:

We consider the standard DMDP and show that linear convergence can be obtained without entropy regularization. Since the support of $\rho^{\star}$ may not cover the entire state space, we give a general analysis for any $\rho\in\Delta(\mathcal{S})$ and characterize the convergence rate in terms of the distribution mismatch coefficient $\|d_{\rho}(\pi^{\star})/\rho\|_{\infty}$.

For DMDP without regularization, Lan (2021) also obtains a slower linear convergence rate ($\gamma^{k/2}$ instead of $\gamma^{k}$), through an approximate policy mirror descent (APMD) method. This method employs exponentially diminishing regularization and exponentially increasing step sizes, and the analysis is considerably more technical.

3 Superlinear Convergence

Under additional conditions, the PMD method (37) may exhibit superlinear convergence. We revisit Proposition 9 and start by rewriting the inequality (50) as

If the step sizes satisfy $\eta_{k}\geq\frac{\vartheta_{k}}{\vartheta_{k+1}-1}\eta_{k-1}$ starting with some $\eta_{-1}>0$, then we have

Therefore, we have superlinear convergence of $\delta_{k}$ if $\vartheta_{k}\to 1$.

Recall the definition of $\vartheta_{k}$ in (49), we have $\vartheta_{k}\to 1$ if and only if $d_{\rho}(\pi^{(k)})\to d_{\rho}(\pi^{\star})$. Apparently, a sufficient condition is $\pi^{(k)}\to\pi^{\star}$. However, this is hard to establish without additional assumptions, e.g., by assuming that the optimal policy $\pi^{\star}$ is unique. Alternatively, since $D^{\star}_{k}=D_{d_{\rho}(\pi^{\star})}(\pi^{\star},\pi^{k})\to 0$ implies $\pi^{k}\to\pi^{\star}$, a reasonable attempt is to show the convergence of $D^{\star}_{k}$ by further leveraging (57). In particular, we can show

at the same speed as $\delta_{k}\to 0$, which is at least linear with an uniform upper bound on $\vartheta_{k}$ as we have done in Section 4.2. However, the step-size condition $\eta_{k}\geq\frac{\vartheta_{k}}{\vartheta_{k+1}-1}\eta_{k-1}$ implies that the factor $1/(\vartheta_{k}\eta_{k-1})$ itself converges at the same rate, thus we can not guarantee $D^{\star}_{k}\to 0$.

Nevertheless, we list here two sufficient conditions for superlinear convergence that are weaker than directly assuming $\pi^{(k)}\to\pi^{\star}$. Both conditions have been used to establish superlinear convergence of the classical Policy Iteration algorithm (Puterman, 1994, Corollary 6.4.10 and Theorem 6.4.8, respectively).

Convergence of the transition probability matrix $P(\pi^{k})$. Specifically,

where $\|\cdot\|$ is any matrix norm. Under this condition, we have $d_{\rho}(\pi^{(k)})\to d_{\rho}(\pi^{\star})$ and thus $\vartheta_{k}\to 1$ because d_{\rho}(\pi^{(k)})=\bigl{(}I-\gamma P(\pi^{(k)})\bigr{)}^{-T}\!\rho is a continuous function.

There exists a finite constant $C>0$ such that for all $k=1,2,\ldots$

This condition is stronger than the previous one because we already established linear convergence of $V_{\rho}(\pi^{k})-V_{\rho}^{\star}$. As a result, it leads to local quadratic convergence.

Khodadadian et al. (2021) showed that under a variant of the second condition above, the NPG method converges superlinerly. With entropy regularization, the optimal policy $\pi^{\star}$ is unique and Cen et al. (2020) established local quadratic convergence of the regularized PMD method.

4 Connection with Policy Iteration

Our analysis of the PMD method does not impose any upper bound on the step sizes: they can be either arbitrarily large constant (Section 4.1) or gemmetrically increasing (Section 4.2). If we allow $\eta_{k}\to\infty$ for all iterations, the limit of the PMD method (37) becomes

which is precisely the classical Policy Iteration method (e.g., Puterman, 1994; Bertsekas, 2012). In fact, our analysis still holds in the limiting case and the result corresponding to Theorem 10 is

where $\delta_{k}=V_{\rho}(\pi^{(k)})-V_{\rho}^{\star}$. Recall the definition of $\vartheta_{\rho}$ in (51). If $\rho=\rho^{\star}$, then we have $\vartheta_{\rho^{\star}}=1/(1-\gamma)$ and

which has the same convergence rate as Policy Iteration (e.g., Puterman, 1994; Ye, 2011). In general, we have the trivial bound

This convergence rate is the same as that established for several variants of policy gradient methods by Bhandari and Russo (2021, Theorem 1), which requires exact line search. Khodadadian et al. (2021) show that the NPG method with an adaptive step size rule can also achieve linear convergence. In contrast, our results in Section 4.2 show that the simple, non-adaptive step size schedule of $\eta_{k}=\eta_{0}/\gamma^{k}$ is suffice to obtain linear convergence of a general class of policy mirror descent methods.

Inexact Policy Mirror Descent Methods

For DMDP problems with large state and action spaces, computing the exact policy gradients or $Q$-functions are very costly and infeasible in practice. In this section, we consider the following inexact PMD method

where $\widehat{Q}_{s}(\pi^{(k)})$ is an inexact evaluation of $Q_{s}(\pi^{(k)})$. We first study the convergence properties of (58) under the following assumption on the evaluation error.

The inexact $Q$-function evaluations $\widehat{Q}(\pi^{(k)})$ satisfy

The following result is the counterpart of Lemma 7 for the inexact PMD method.

Consider the inexact PMD method (58) with $\pi^{(0)}\in\operatorname{rint}\Pi$ and suppose that Assumption 1 holds. Then we have for all $k\geq 0$,

and for any $\rho\in\Delta(\mathcal{S})$,

Proof The proof of (60) follows the same arguments as in Lemma 7. However, due to the inexact $Q$-function evaluations, the objectives $V_{\rho}(\pi^{(k)})$ are no longer monotone decreasing. We use the performance difference lemma to deduct:

Notice that the first term on the right-hand side is non-positive due to (60). For the second term, we use Hölder’s inequality to obtain, for all $s\in\mathcal{S}$,

where the second inequality is due to \bigl{\|}\pi^{(k+1)}_{s}-\pi^{(k)}_{s}\bigr{\|}_{1}\leq\bigl{\|}\pi^{(k+1)}_{s}\bigr{\|}_{1}+\bigl{\|}\pi^{(k)}_{s}\bigr{\|}_{1}\leq 2, and the last inequality is due to Assumption 1. Combining (62) with the previous inequality yields (61).

We will need the following simple fact, whose proof is straightforward and thus omitted.

Suppose $0<\alpha<1$, $b>0$, and a nonnegative sequence $\{a_{k}\}$ satisfies

The following theorem characterizes the convergence of the inexact PMD method under Assumption 1. We keep using the notations $D^{\star}_{k}$ and $\vartheta_{\rho}$ defined in (43) and (51), respectively.

Consider the inexact PMD method (58) with $\pi^{(0)}\in\operatorname{rint}\Pi$ and suppose that Assumption 1 holds. If the step sizes satisfy $\eta_{0}\geq\frac{1-\gamma}{\gamma}D^{\star}_{0}$ and $\eta_{k+1}\geq\eta_{k}/\gamma$, then we have for all $k\geq 0$,

Proof Applying Lemma 6 to the update in (58) and following the same arguments in the proof of Theorem 8, we arrive at the following counterpart of (44):

For the first expectation in (64), we follow the proof of Proposition 9 to obtain

where the last inequality is due to the performance difference lemma and (62). For the second expectation in (64), we again use the performance difference lemma and Hölder’s inequality to obtain

Substituting the last two bounds into (64) and dividing both sides by $1-\gamma$, we get

where $\delta_{k}:=V_{\rho}(\pi^{(k+1)})-V_{\rho}^{\star}$. Since $\delta_{k+1}-\delta_{k}-\frac{2\tau}{1-\gamma}\leq 0$ (Lemma 11) and $\vartheta_{k+1}\leq\vartheta_{\rho}$, the above inequality still holds with $\vartheta_{k+1}$ replaced by $\vartheta_{\rho}$, which leads to

Dividing both sides by $\vartheta_{\rho}$ and rearranging terms, we get

If the step sizes satisfy $\eta_{k+1}(\vartheta_{\rho}-1)\geq\eta_{k}\vartheta_{\rho}$, which is implied by $\eta_{k+1}\geq\eta_{k}/\gamma$, then

where we also used $1+1/\vartheta_{\rho}<2$ because $\vartheta_{\rho}>1$. Next we invoke Lemma 12 with

Finally applying (55) and $\eta_{0}\geq\frac{1-\gamma}{\gamma}D^{\star}_{0}$ gives the desired result (63).

As a result of Theorem 13, we have the following asymptotic error bound:

which agrees with that of conservative policy iteration (CPI) of Kakade and Langford (2002, Theorem 6.2). It is also similar to the asymptotic error bound of many approximate dynamical programming algorithms (e.g., Bertsekas, 2012), with the additional factor of distribution mismatch coefficient.

One way to ensure Assumption 1 hold with high probability is through multiple independent simulations (rollouts) of the MDP under a fixed policy. In this section, we analyze the sample complexity of this approach.

Suppose that for a given policy $\pi^{(k)}$ and any state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, we can generate a set of $M_{k}$ independent, truncated trajectories of horizon $H$, i.e.,

We construct $\widehat{Q}_{s,a}(\pi^{(k)})$ with the trajectories $\mathcal{T}_{s,a}^{(k,i)}$, $i=1,\ldots,M_{k}$, as follows:

The following lemma gives a high-probability bound on the error $\|\widehat{Q}(\pi^{(k)})-Q(\pi^{(k)})\|_{\infty}$.

Consider the $Q$-estimator given in (65). For any $\delta\in(0,1)$, if $M_{k}$ satisfies

then we have with probability at least $1-\delta$,

Proof We first define the expectation of the $Q$-estimator in (65):

which holds for any $i=1,\ldots,M_{k}$. Recall the definition of $Q_{s,a}$ in (15). Since $R(s,a)\geq 0$, we always have $Q_{s,a}(\pi^{(k)})-\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{Q}_{s,a}(\pi^{(k)})\geq 0$. On the other hand,

which holds for all $(s,a)\in\mathcal{S}\times\mathcal{A}$. Therefore,

Next that we can decompose the estimation error into two parts:

The last term is bounded by (67), so we need to bound \bigl{\|}\widehat{Q}(\pi^{(k)})-\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{Q}(\pi^{(k)})\bigr{\|}_{\infty}. To this end, we notice that the random variables $\widehat{Q}_{s,a}^{(i)}(\pi^{(k)})$ are bounded in the interval $[0,1/(1-\gamma)]$. Therefore Hoeffding’s inequality (Hoeffding, 1963) implies that for any $\sigma_{k}>0$,

Applying the union bound across all $(s,a)\in\mathcal{S}\times\mathcal{A}$, we obtain

Therefore, for any $\delta\in(0,1)$, if we choose $M_{k}$ large enough, i.e.,

then \bigl{\|}\widehat{Q}(\pi^{(k)})-\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{Q}(\pi^{(k)})\bigr{\|}_{\infty}<\sigma_{k} with probability at least $1-\delta$. Combining with (67) and (68), we conclude that with probability at least $1-\delta$,

Finally setting $\sigma_{k}=\gamma^{H}/(1-\gamma)$ gives the desired result.

The next theorem characterizes the sample complexity of the inexact PMD method with the simple $Q$-estimator.

Consider using the $Q$-estimator (65) in the inexact PMD method (58), with the step sizes satisfying $\eta_{0}\geq\frac{1-\gamma}{\gamma}D^{\star}_{0}$ and $\eta_{k+1}\geq\frac{1}{\gamma}\eta_{k}$ for all $k\geq 0$. For any $\delta\in(0,1)$ and integers $H>0$ and $K>0$, suppose the batch sizes $M_{k}$ satisfy

Then we have with probability at least $1-\delta$,

In addition, for any $\epsilon>0$, we have $V_{\rho}(\pi^{(K)})-V_{\rho}^{\star}\leq\epsilon$ with probability at least $1-\delta$ if

The corresponding sample complexity of state-action pairs is

where the notation $\widetilde{O}(\cdot)$ hides poly-logarithmic factors of $1/(1-\gamma)$, $1/\epsilon$ and ${|\mathcal{S}|}{|\mathcal{A}|}/\delta$.

Proof Suppose the total number of iterations is $K$. In order to have (66) hold for all $k=0,1,\ldots,K-1$, we need to apply the union bound across all $K$ iterations, which imposes an additional factor $K$ on the right-hand side of (69). Consequently, we can extend Lemma 14 to ensure that the event

occurs with probability at least $1-\delta$ provided that (71) holds. Then (72) follows directly from Theorem 13 with $\tau=2\gamma^{H}/(1-\gamma)$.

In order to have $V_{\rho}(\pi^{(k)})-V_{\rho}^{\star}\leq\epsilon$ within $K$ iterations, it suffices to have each of the two terms on the right-hand side of (72) less than $\epsilon/2$, i.e.,

which translate into the conditions on $K$ and $H$ in (73). Correspondingly, the batch sizes need to satisfy $M_{k}\geq M$ where

The total number of state-action samples can be estimated as

Finally, plugging in the definition $\vartheta_{\rho}=\frac{1}{1-\gamma}\left\|\frac{d_{\rho}(\pi^{\star})}{\rho}\right\|_{\infty}$ gives the estimate in (74).

The sample complexity obtained in Theorems 15 has $O(\epsilon^{-2})$ dependence on $\epsilon$. This is better than that of $O(\epsilon^{-4})$ obtained by Shani et al. (2020) and Agarwal et al. (2021) and $O(\epsilon^{-3})$ by Liu et al. (2020) for policy gradient type of methods (without regularization). Cen et al. (2020) remarked that $O(\epsilon^{-2})$ sample complexity can be obtained with entropy regularization. Their approach leads to a result without the factor of the distribution mismatch coefficient, but with the same $1/(1-\gamma)^{8}$ factor. Lazaric et al. (2016) derived an $O(\epsilon^{-2})$ sample complexity for a variant of the policy iteration method, with a factor of at least $1/(1-\gamma)^{7}$. Lan (2021) studies sample complexity in expectation instead of with high probability and obtains similar results with weaker dependence on $1/(1-\gamma)$. Yuan et al. (2021) characterize the sample complexity of vanilla policy gradient method (such as REINFORCE (Williams, 1992)) under a variety of different assumptions on the parametrized value function.

Much progresses have been made for understanding the sample complexity of DMDP in the tabular setting. Azar et al. (2013) established a lower bound of $\widetilde{\Omega}\left(\frac{{|\mathcal{S}|}{|\mathcal{A}|}}{(1-\gamma)^{3}\epsilon^{2}}\right)$ for DMDP under a generative model, which allows drawing random state-transitions repeatedly under any policy. The simple Q-estimator we use in this section fits this sample oracle model, but the dependence of our results on $1/(1-\gamma)$ is much worse than the lower bound. On the other hand, this lower bound has been matched or nearly matched by several recent work based on variance-reduced Value Iteration (Sidford et al., 2018) and $Q$-learning (Wainwright, 2019). There are interesting work to be done for improving the sample complexity of stochastic policy gradient methods.

Conclusion and Discussion

We developed a general theory of weak gradient-mapping dominance and used it to obtain an improved sublinear convergence rate of the projected policy gradient methods. By exploiting additional structure of discounted Markov decision problem (DMDP), we show that with a simple, non-adaptive rule of geometrically increasing the step sizes, policy mirror descent methods enjoy linear convergence without relying on entropy or other strongly convex regularizations. In fact, the convergence rates obtained with strongly convex regularizations (Cen et al., 2020; Lan, 2021; Zhan et al., 2021) are no better than $\gamma^{k}$ regardless of the regularization strength.

Our results on policy mirror descent methods show that dynamic preconditioning using discounted state-visitation distributions is critical for obtaining fast convergence rates that are (almost) independent of problem dimensions. The adopted local Bregman divergence, being KL-divergence or squared Euclidean distance, does not make much difference. Indeed, when the step sizes grow to infinity, preconditioned policy mirror descent methods derived with different Bregman divergences all reduce to the classical Policy Iteration algorithm. Essentially, such methods with finite step sizes can be viewed as inexact Policy Iteration methods, much like many approximate dynamic programming algorithms.

The major limitation of this work is our restriction to direct policy parametrization. (We note that the NPG method with tabular softmax parametrization has an equivalent mirror-descent form expressed in the policy space, therefore is included in our study.) A natural extension is to consider general policy parametrizations of the form $\pi(\theta)$ where the dimension of $\theta$ is much smaller than ${|\mathcal{S}|}{|\mathcal{A}|}$. There are two ways to proceed. The first approach is to simply treat it as a nonlinear optimization problem of minimizing the composite objective $J_{\rho}(\theta)=V_{\rho}(\pi(\theta))$. This approach may lose some important structure of DMDP. In particular, the parametrized objective function $J_{\rho}(\theta)$ may no longer be quasi-convex or quasi-concave. As a result, it will be hard to establish convergence to global optimum and we may have to rely on standard theory of smooth nonconvex optimization, which imposes bounded step sizes and leads to relatively slow convergence rates.

The second approach is to follow the framework of compatible function approximation (Sutton et al., 2000; Kakade, 2001), which is extensively developed by Agarwal et al. (2021). This approach facilitates the extension of our results on inexact policy mirror descent to general policy parametrization. In particular, our results in Section 5 show that geometrically increasing step sizes do not cause instability even if the $Q$-functions are evaluated inaccurately. In fact, inexact policy mirror descent methods converge linearly up to an asymptotic error floor, which immediately leads to an $O(\epsilon^{-2})$ sample complexity as we have shown. It is of great interest to reduce the dependence of sample complexity on $1/(1-\gamma)$ and the distribution mismatch coefficient.