Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes

Introduction

Here $h^{\pi}$ is a closed convex function w.r.t. the policy $\pi$, i.e., there exist some $\mu\geq 0$ s.t.

where $\langle\cdot,\cdot\rangle$ denotes the inner product over the action space ${\cal A}$, $(h^{\prime})^{\pi^{\prime}}(s,\cdot)$ denotes a subgradient of $h(s)$ at $\pi^{\prime}$, and $D_{\pi^{\prime}}^{\pi}(s)$ is the Bregman’s distance or Kullback–Leibler (KL) divergence between $\pi$ and $\pi^{\prime}$ (see Subsection 1.1 for more discussion).

Clearly, if $h^{\pi}=0$, then $Q^{\pi}$ becomes the classic action-value function. If $h^{\pi}(s)=\mu D_{\pi_{0}}^{\pi}(s)$ for some $\mu>0$, then $Q^{\pi}$ reduces to the so-called entropy regularized action-value function. The incorporation of a more general convex regularizer $h^{\pi}$ allows us to not only unify these two cases, but also to greatly enhance the expression power and thus the applicability of RL. For example, by using either the indicator function, quadratic penalty or barrier functions, $h^{\pi}$ can model the set of constraints that an optimal policy should satisfy. It can describe the correlation among different actions for different states. $h^{\pi}$ can also model some risk or utility function associated with the policy $\pi$. Throughout this paper, we say that $h^{\pi}$ is a strongly convex regularizer if $\mu>0$. Otherwise, we call $h^{\pi}$ a general convex regularizer. Clearly the latter class of problems covers the regular case with $h^{\pi}=0$.

It can be easily seen from the definitions of $Q^{\pi}$ and $V^{\pi}$ that

for any $s\in{\cal S}$. Here $\Delta_{|{\cal A}|}$ denotes the simplex constraint given by

By examining Bellman’s optimality condition for dynamic programming (BellmanDreyfus1959 and Chapter 6 of PutermanBook1994), we can show the existence of a policy $\pi^{*}$ which satisfies (1.6) simultaneously for all $s\in{\cal S}$. Hence, we can formulate (1.6) as an optimization problem with a single objective by taking the weighted sum of $V^{\pi}$ over $s$ (with weights $\rho_{s}>0$ and $\textstyle\sum_{s\in S}\rho_{s}=1$):

While the weights $\rho$ can be arbitrarily chosen, a reasonable selection of $\rho$ would be the stationary state distribution induced by the optimal policy $\pi^{*}$, denoted by $\nu^{*}\equiv\nu(\pi^{*})$. As such, problem (1.8) reduces to

It has been observed recently (eg., LiuCaiYangWang2019a) that one can simplify the analysis of various algorithms by setting $\rho$ to $\nu^{*}$. As we will also see later, even though the definition of the objective $f$ in (1.9) depends on $\nu^{*}$ and hence the unknown optimal policy $\pi^{*}$, the algorithms for solving (1.6) and (1.9) do not really require the input of $\pi^{*}$.

Recently, there has been considerable interest in the development of first-order methods for solving RL problems in (1.8) -(1.9). While these methods have been derived under various names (e.g., policy gradient, natural policy gradient, trust region policy optimization), they all utilize the gradient information of $f$ (i.e., $Q$ function) in some form to guide the search of optimal policy (e.g., SuttonMcAllester1999; KakadeLangford2002; 10.2307/40538442; AgarwalKakadeLeeeMhhajan2019; DBLP:conf/aaai/ShaniEM20; 2020arXiv200706558C; Wang2020NeuralPG; 2020arXiv200506392M). As pointed out by a few authors recently, many of these algorithms are intrinsically connected to the classic mirror descent method originally presented by Nemirovski and Yudin nemyud:83; BeckTeb03-1; NJLS09-1, and some analysis techniques in mirror descent method have thus been adapted to reinforcement learning DBLP:conf/aaai/ShaniEM20; Wang2020NeuralPG; Tomar2020MirrorDP. In spite of the popularity of these methods in practice, a few significant issues remain on their theoretical studies. Firstly, most policy gradient methods converge only sublinearly, while many other classic algorithms (e.g., policy iteration) can converge at a linear rate due to the contraction properties of the Bellman operator. Recently, there are some interesting works relating first-order methods with the Bellman operator to establish their linear convergence 2020arXiv200711120B; 2020arXiv200706558C. However, in a nutshell these developments rely on the contraction of the Bellman operator, and as a consequence, they either require unrealistic algorithmic assumptions (e.g., exact line search 2020arXiv200711120B) or apply only for some restricted problem classes (e.g., entropy regularized problems 2020arXiv200706558C). Secondly, the convergence of stochastic policy gradient methods has not been well-understood in spite of intensive research effort. Due to unavoidable bias, stochastic policy gradient methods exhibit much slower rate of convergence than related methods, e.g., stochastic Q-learning.

Our contributions in this paper mainly exist in the following several aspects. Firstly, we present a policy mirror descent (PMD) method and show that it can achieve a linear rate of convergence for solving RL problems with strongly convex regularizers. We then develop a more general form of PMD, namely approximate policy mirror descent (APMD) method, obtained by applying an adaptive perturbation term into PMD, and show that it can achieve a linear rate of convergence for solving RL problems with general convex regularizers. Even though the overall problem is highly nonconvex, we exploit the generalized monotonicity DangLan12-1; LanBook2020; KotsalisLanLi2020PartI associated with the variational inequality (VI) reformulation of (1.8)-(1.9) (see FacPang03 for a comprehensive introduction to VI). As a consequence, our convergence analysis does not rely on the contraction properties of the Bellman operator. This fact not only enables us to define $h^{\pi}$ as a general (strongly) convex function of $\pi$ and thus expand the problem classes considered in RL, but also facilitates the study of PMD methods under the stochastic settings.

Secondly, we develop the stochastic policy mirror descent (SPMD) and stochastic approximate policy mirror descent (SAPMD) method to handle stochastic first-order information. One key idea of SPMD and SAPMD is to handle separately the bias and expected error of the stochastic estimation of the action-value functions in our convergence analysis, since we can usually reduce the bias term much faster than the total expected error. We establish general convergence results for both SPMD and SAPMD applied to solve RL problems with strongly convex and general convex regularizers, under different conditions about the bias and expected error associated with the estimation of value functions.

Thirdly, we establish the overall sampling complexity of these algorithms by employing different schemes to estimate the action-value function. More specifically, we present an ${\cal O}(|{\cal S}||{\cal A}|/\mu\epsilon)$ and ${\cal O}(|{\cal S}||{\cal A}|/\epsilon^{2})$ sampling complexity for solving RL problems with strongly convex and general convex regularizers, when one has access to multiple independent sampling trajectories. To the best of our knowledge, the former sampling complexity is new in the RL literature, while the latter one has not been reported before for policy gradient type methods. We further enhance a recently developed conditional temporal difference (CTD) method KotsalisLanLi2020PartII so that it can reduce the bias term faster. We show that with CTD, the aforementioned ${\cal O}(1/\mu\epsilon)$ and ${\cal O}(1/\epsilon^{2})$ sampling complexity bounds can be achieved in the single trajectory setting with Markovian noise under certain regularity assumptions.

Fourthly, observe that unless $h^{\pi}$ is relatively simple (e.g., $h^{\pi}$ does not exist or it is given as the KL divergence), the subproblems in the SPMD and SAPMD methods do not have an explicit solution in general and require an efficient solution procedure to find some approximate solutions. We establish the general conditions on the accuracy for solving these subproblems, so that the aforementioned linear rate of convergence and new sampling complexity bounds can still be maintained. We further show that if $h^{\pi}$ is a smooth convex function, by employing an accelerated gradient descent method for solving these subproblems, the overall gradient computations for $h^{\pi}$ can be bounded by ${\cal O}\{(\log_{\gamma}\epsilon)\sqrt{(1-\gamma)L/\mu}\log(1/\epsilon)\}$ and ${\cal O}\{(\log_{\gamma}\epsilon)\sqrt{L/\epsilon}\}$, respectively, for the case when $h^{\pi}$ is a strongly convex and general convex function. To the best of our knowledge, such gradient complexity has not been considered before in the RL and optimization literature.

This paper is organized as follows. In Section 2, we discuss the optimality conditions and generalized monotonicity about RL with convex regularizers. Sections 3 and 4 are dedicated to the deterministic and stochastic policy mirror descent methods, respectively. In Section 5 we establish the sampling complexity bounds under different sampling schemes, while the gradient complexity of computing $\nabla h^{\pi}$ is shown in Section 6. Some concluding remarks are made in Section 7.

For any two points $\pi(\cdot|s),\pi^{\prime}(\cdot|s)\in\Delta_{|{\cal A}|}$, we measure their Kullback–Leibler (KL) divergence by

Observe that the KL divergence can be viewed as is a special instance of the Bregman’s distance (or prox-function) widely used in the optimization literature. Let the distance generating function $\omega(\pi(\cdot|s)):=\textstyle\sum_{a\in{\cal A}}\pi(a|s)\log\pi(a|s)$ It is worth noting that we do not enforce $\pi(a|s)>0$ when defining $\omega(\pi(\cdot|s))$ as all the search points generated by our algorithms will satisfy this assumption.. The Bregman’s distance associated with $\omega$ is given by

where the last equation follows from the fact that $\textstyle\sum_{a\in{\cal A}}(\pi(a|s)-\pi^{\prime}(a|s))=0$. Therefore, we will use the KL divergence ${\rm KL}(\pi(\cdot|s)\parallel\pi^{\prime}(\cdot|s))$ and Bregman’s distance $D_{\pi^{\prime}}^{\pi}(s)$ interchangeably throughout this paper. It should be noted that our algorithmic framework allows us to use other distance generating functions, such as $\|\cdot\|_{p}^{2}$ for some $p>1$, which, different from the KL divergence, has a bounded prox-function over $\Delta_{|{\cal A}|}$.

Optimality Conditions and Generalized Monotonicity

It is well-known that the value function $V^{\pi}(s)$ in (1.3) is highly nonconvex w.r.t. $\pi$, because the components of $\pi(\cdot|s)$ are multiplied by each other in their definitions (see also Lemma 3 of AgarwalKakadeLeeeMhhajan2019 for an instructive counterexample). However, we will show in this subsection that problem (1.9) can be formulated as a variational inequality (VI) which satisfies certain generalized monotonicity properties (see DangLan12-1, Section 3.8.2 of LanBook2020 and KotsalisLanLi2020PartI).

Let us first compute the gradient of the value function $V^{\pi}(s)$ in (1.3). For simplicity, we assume for now that $h^{\pi}$ is differentiable and will relax this assumption later. For a given policy $\pi$, we define the discounted state visitation distribution by

where ${\rm Pr}^{\pi}(s_{t}=s|s_{0})$ denotes the state visitation probability of $s_{t}=s$ after we follow the policy $\pi$ starting at state $s_{0}$. Let ${\cal P}^{\pi}$ denote the transition probability matrix associated with policy $\pi$, i.e., ${\cal P}^{\pi}(i,j)=\textstyle\sum_{a\in{\cal A}}\pi(a|i){\cal P}(j|i,a)$, and $e_{i}$ be the $i$-th unit vector. Then ${\rm Pr}^{\pi}(s_{t}=s|s_{0})=e_{s_{0}}^{T}({\cal P}^{\pi})^{t}e_{s}$ and

For any $(s_{0},s,a)\in{\cal S}\times{\cal S}\times{\cal A}$, we have

where $\nabla h^{\pi}(s,\cdot)$ denotes the gradient of $h^{\pi}(s)$ w.r.t. $\pi$.

Combining the above two relations, we obtain

where the second equality follows by expanding $\tfrac{\partial V^{\pi}(s^{\prime})}{\partial\pi(a|s)}$ recursively, and the third equality follows from the definition of $d_{s_{0}}^{\pi}(s)$ in (2.1), and the last identity follows from $\tfrac{\partial\pi(a^{\prime}|x)}{\partial\pi(a|s)}=0$ for $x\neq s$ or $a^{\prime}\neq a$, and $\tfrac{\partial h^{\pi}(x)}{\partial\pi(a|s)}=0$ for $x\neq s$.

In view of Lemma 1, the gradient of the objective $f(\pi)$ in (1.9) at the optimal policy $\pi^{*}$ is given by

where the third identity follows from (2.2) and the last one follows from the fact that $(\nu^{*})^{T}({\cal P}^{\pi^{*}})^{t}=(\nu^{*})^{T}$ for any $t\geq 0$ since $\nu^{*}$ is the steady state distribution of $\pi^{*}$. Therefore, the optimality condition of (1.9) suggests us to solve the following variational inequality

However, the above VI requires $h^{\pi}$ to be differentiable. In order to handle the possible non-smoothness of $h^{\pi}$, we instead solve the following problem

It turns out this variational inequality satisfies certain generalized monotonicity properties thanks to the following performance difference lemma obtained by generalizing some previous results (e.g., Lemma 6.1 of KakadeLangford2002).

For any two feasible policies $\pi$ and $\pi^{\prime}$, we have

For simplicity, let us denote $\xi^{\pi^{\prime}}(s_{0})$ the random process $(s_{t},a_{t},s_{t+1})$, $t\geq 0$, generated by following the policy $\pi^{\prime}$ starting with the initial state $s_{0}$. It then follows from the definition of $V^{\pi^{\prime}}$ that

We are now ready to prove the generalized monotonicity for the variational inequality in (2.5).

It follows from Lemma 2 (with $\pi^{\prime}=\pi^{*}$) that

Let $e$ denote the vector of all $1$’s. Then, we have

where the first identity follows from the definition of $A^{\pi}(s^{\prime},\cdot)$ in (2.6), the second equality follows from the fact that $\langle e,\pi^{*}(\cdot|s^{\prime})\rangle=1$, and the third equality follows from the definition of $V^{\pi}$ in (1.3). Combining the above two relations and taking expectation w.r.t. $\nu^{*}$, we obtain

where the second identity follows similarly to (2.3) since $\nu^{*}$ is the steady state distribution induced by $\pi^{*}$. The result then follows by rearranging the terms.

Since $V^{\pi}(s)-V^{\pi^{*}}(s)\geq 0$ for any feasible policity $\pi$, we conclude from Lemma 3 that

Therefore, the VI in (2.5) satisfies the generalized monotonicity. In the next few sections, we will exploit the generalized monotonicity and some other structural properties to design efficient algorithms for solving the RL problem.

Deterministic Policy Mirror Descent

In this section, we present the basic schemes of policy mirror descent (PMD) and establish their convergence properties.

In the proposed PMD methods, we will update a given policy $\pi$ to $\pi^{+}$ through the following proximal mapping:

Here $\eta>0$ denotes a certain stepsize (or learning rate), and $G^{\pi}$ can be the operator for the VI formulation, e.g., $G^{\pi}(s,\cdot)=Q^{\pi}(s,\cdot)$ or its approximation.

It is well-known that one can solve (3.1) explicitly for some interesting special cases, e.g., when $h^{p}(s)=0$ or $h^{p}(s)=\tau D_{\pi_{0}}^{p}(s)$ for some $\tau>0$ and given $\pi_{0}$. For both these cases, the solution of (3.1) boils down to solving a problem of the form

For more general convex functions $h^{p}$, problem (3.1) usually does not have an explicit solution, and one can only solve it approximately. In fact, we will show in Section 6 that by applying the accelerated gradient descent method, we only need to compute a small number of updates in the form of (3.2) in order to approximately solve (3.1) without slowing down the efficiency of the overall PMD algorithms.

2 Basic PMD method

As shown in Algorithm 1, each iteration of the PMD method applies the prox-mapping step discussed in Subsection 3.1 to update the policy $\pi_{k}$. It involves the stepsize parameter $\eta_{k}$ and requires the selection of an initial point $\pi_{0}$. For the sake of simplicity, we will assume throughout the paper that

Observe also that we can replace $Q^{\pi_{k}}(s,\cdot)$ in (3.5) with $A^{\pi_{k}}(s,a)$ defined in (2.6) without impacting the updating of $\pi_{k+1}(s,\cdot)$, since this only introduces an extra constant into the objective function of (3.5).

Below we establish some general convergence properties about the PMD method. Different from the classic policy iteration or value iteration method used in Markov Decision Processes, our analysis does not rely on the contraction properties of the Bellman’s operator, but on the so-called three-point lemma associated with the optimality condition of problem (3.5) (see Lemma 4). Our analysis also significantly differs from the one for the classic mirror descent method in convex optimization (see, e.g., Chapter 3 of LanBook2020). First, the classic mirror descent method requires the convexity of the objective function, while the analysis of PMD utilizes the generalized monotonicity in Lemma 3. Second, the classic mirror descent utilizes the Lipschitz or smoothness properties of the objective function, while in the PMD method, we show the progress made in each iteration of this algorithm (see Lemma 5) by using the performance difference lemma (c.f., Lemma 2) and the three-point lemma (c.f., Lemma 4). As a result, we make no assumptions about the smoothness properties of the objective function at all.

The following result characterizes the optimality condition of problem (3.5) (see Lemma 3.5 of LanBook2020). We add a proof for the sake of completeness.

For any $p(\cdot|s)\in\Delta_{|{\cal A}|}$, we have

where $(h^{\prime})^{\pi_{k+1}}$ denotes the subgradient of $h$ at $\pi_{k+1}$ and $\nabla D_{\pi_{k}}^{\pi_{k+1}}(s,\cdot)$ denotes the gradient of $D_{\pi_{k}}^{\pi_{k+1}}(s)$ at $\pi_{k+1}$. Using the definition of Bregman’s distance, it is easy to verify that

The result then immediately follows by combining the above two relations together with (1.2).

It follows from Lemma 2 (with $\pi^{\prime}=\pi_{k+1}$, $\pi=\pi_{k}$ and $\tau=\tau_{k}$) that

Combining the above two identities, we then obtain

Now we conclude from Lemma 4 applied to (3.5) with $p(\cdot|s^{\prime})=\pi_{k}(\cdot|s^{\prime})$ that

The previous two conclusions then clearly imply the result in (3.7). It also follows from (3.11) that

where the last inequality follows from the fact that $d_{s}^{\pi_{k+1}}(s)\geq(1-\gamma)$ due to the definition of $d_{s}^{\pi_{k+1}}$ in (2.1). The result in (3.7) then follows immediately from (3.10) and the above inequality.

Now we show that with a constant stepsize rule, the PMD method can achieve a linear rate of convergence for solving RL problems with strongly convex regularizers (i.e., $\mu>0$).

Suppose that $\eta_{k}=\eta$ for any $k\geq 0$ in the PMD method with

By Lemma 4 applied to (3.5) (with $\eta_{k}=\eta$ and $p=\pi^{*}$), we have

which, in view of (3.8), then implies that

Taking expectation w.r.t. $\nu^{*}$ on both sides of the above inequality and using Lemma 3, we arrive at

Noting $V^{\pi_{k+1}}(s)-V^{\pi_{k}}(s)=V^{\pi_{k+1}}(s)-V^{\pi^{*}}(s)-[V^{\pi_{k}}(s)-V^{\pi^{*}}(s)]$ and rearranging the terms in the above inequality, we have

which, in view of the assumption (3.13) and the definition of $f$ in (1.9)

Applying this relation recursively and using the bound in (3.4) we then conclude the result.

According to Theorem 3.1, the PMD method converges linearly in terms of both function value and the distance to the optimal solution for solving RL problems with strongly convex regularizers. Now we show that a direct application of the PMD method only achieves a sublinear rate of convergence for the case when $\mu=0$.

Suppose that $\eta_{k}=\eta$ in the PMD method. Then we have

Taking the telescopic sum of the above inequalities and using the fact that $V^{\pi_{k+1}}(s)\leq V^{\pi_{k}}(s)$ due to (3.7) , we obtain

which clearly implies the result in view of the definition of $f$ in (1.9) and the bound on $D_{\pi_{0}}^{\pi^{*}}$ in (3.4).

The result in Theorem 3.2 shows that the PMD method requires ${\cal O}(1/(1-\gamma)\epsilon)$ iterations to find an $\epsilon$-solution for general RL problems. This bound already matches, in terms of its dependence on $(1-\gamma)$ and $\epsilon$, the previously best-known complexity for natural policy gradient methods AgarwalKakadeLeeeMhhajan2019. We will further enhance the PMD method so that it can achieve a linear rate of convergence for the case when $\mu=0$ in next subsection.

3 Approximate policy mirror descent method

In this subsection, we propose to enhance the basic PMD method by adding adaptively a perturbation term into the definition of the value functions or the proximal-mapping.

For some $\tau\geq 0$ and a given initial policy $\pi_{0}(a|s)>0$, $\forall s\in{\cal S},a\in{\cal A}$, we define the perturbed action-value and state-value functions, respectively, by

Clearly, if $\tau=0$, then the perturbed value functions reduce to the usual value functions, i.e.,

The following result relates the value functions with different $\tau$.

For any given $\tau,\tau^{\prime}\geq 0$, we have

As a consequence, if $\tau\geq\tau^{\prime}\geq 0$ then

By the definitions of $V_{\tau}^{\pi}$ and $d_{s}^{\pi}$, we have

which together with the bound on $D_{\pi_{0}}^{\pi}$ in (3.4) then imply (3.19).

As shown in Algorithm 2, the approximate policy mirror descent (APMD) method is obtained by replacing $Q^{\pi_{k}}(s,\cdot)$ with its approximation $Q_{\tau_{k}}^{\pi_{k}}(s,\cdot)$ and adding the perturbation $\tau_{k}D_{\pi_{0}}^{\pi}(s_{t})$ for the updating of $\pi_{k+1}$ in the basic PMD method. As discussed in Subsection 3.1, the incorporation of the perturbation term does not impact the difficulty of solving the subproblem in (3.20). In fact, the APMD method can be viewed as a general form of the PMD method since it reduces to the PMD method when $\tau_{k}=0$. In fact, the perturbation parameter $\tau_{k}$ used to define the action-value function $Q_{\tau_{k}}^{\pi_{k}}(s,\cdot)$ is not necessarily the same as the one used in the regularization term $\tau_{k}D_{\pi_{0}}^{p}(s_{t})$, yielding more flexibility to the design and analysis for this class of algorithms.

Our goal in the remaining part of this subsection is to show that the APMD method, when employed with proper selection of $\tau_{k}$, can achieve a linear rate of convergence for solving general RL problems. Note that in the classic mirror descent method, adding a perturbation term into the objective function usually would not improve its rate of convergence from sublinear to linear. However, the linear rate of convergence in PMD depends on the discount factor rather than the strongly convex modulus of the regularization term, which makes it possible for us to show a linear rate of convergence for the APMD method.

First we observe that Lemma 3 can still be applied to the perturbed value functions. The difference between the following result and Lemma 3 exists in that the RHS of (3.21) is no longer nonnegative, i.e., $V_{\tau}^{\pi}(s)-V_{\tau}^{\pi^{*}}(s)\ngeqslant 0$. However, this relation will be approximately satisfied if $\tau$ is small enough.

The proof is the same as that for Lemma 3 except that we will apply the performance difference lemma (i.e., Lemma 2) to the perturbed value function $V_{\tau}^{\pi}$.

Next we establish some general convergence properties about the APMD method. Lemma 8 below characterizes the optimal solution of (3.20) (see, e.g., Lemma 3.5 of LanBook2020).

Let $\pi_{k+1}(\cdot|s)$ be defined in (3.20). For any $p(\cdot|s)\in\Delta_{|{\cal A}|}$, we have

Lemma 9 below is similar to Lemma 5 for the PMD method.

By applying Lemma 2 to the perturbed value function $V_{\tau}^{\pi}$ and using an argument similar to (3.10), we can show that

Now we conclude from Lemma 8 with $p(\cdot|s^{\prime})=\pi_{k}(\cdot|s^{\prime})$ that

where the last inequality follows from the fact that $d_{s}^{\pi_{k+1}}(s)\geq(1-\gamma)$ due to the definition of $d_{s}^{\pi_{k+1}}$ in (2.1). The result in (3.22) then follows immediately from (3.23) and the above inequality.

The following general result holds for different stepsize rules for APMD.

Suppose $1+\eta_{k}\tau_{k}=1/\gamma$ and $\tau_{k}\geq\tau_{k+1}$ in the APMD method. Then for any $k\geq 0$, we have

Combining the above two relations, we obtain

Taking expectation w.r.t. $\nu^{*}$ on both sides of the above inequality and using Lemma 7, we arrive at

Noting $V_{\tau_{k}}^{\pi_{k+1}}(s)-V_{\tau_{k}}^{\pi_{k}}(s)=V_{\tau_{k}}^{\pi_{k+1}}(s)-V_{\tau_{k}}^{\pi^{*}}(s)-[V_{\tau_{k}}^{\pi_{k}}(s)-V_{\tau_{k}}^{\pi^{*}}(s)]$ and rearranging the terms in the above inequality, we have

Using the above inequality, the assumption $\tau_{k}\geq\tau_{k+1}$ and (3.19), we have

which implies the result by the assumption $1+\eta_{k}\tau_{k}=1/\gamma$.

We are now ready to establish the rate of convergence of the APMD method with dynamic stepsize rules to select $\eta_{k}$ and $\tau_{k}$ for solving general RL problems.

Suppose that $\tau_{k}=\tau_{0}\gamma^{k}$ for some $\tau_{0}\geq 0$ and that $1+\eta_{k}\tau_{k}=1/\gamma$ for any $k\geq 0$ in the APMD method. Then for any $k\geq 0$, we have

Applying the result in Lemma 10 recursively, we have

Noting that $V_{\tau_{k}}^{\pi_{k}}(s)\geq V^{\pi_{k}}(s)$, $V_{\tau_{k}}^{\pi^{*}}(s)\leq V^{\pi^{*}}(s)+\tfrac{\tau_{k}}{1-\gamma}\log|{\cal A}|$, and $V_{\tau_{0}}^{\pi^{*}}(s)\geq V^{\pi^{*}}(s)$ due to (3.18), and that $V_{\tau_{0}}^{\pi_{0}}(s)=V^{\pi_{0}}(s)$ due to $D_{\pi_{0}}^{\pi_{0}}(s)=0$, we conclude from the previous inequality that

The result in (3.29) immediately follows from the above relation, the definition of $f$ in (1.9), and the selection of $\tau_{k}$.

According to (3.29), if $\tau_{0}$ is a constant, then the rate of convergence of the APMD method is ${\cal O}(k\gamma^{k})$. If the total number of iterations $k$ is given a priori, we can improve the rate of convergence to ${\cal O}(\gamma^{k})$ by setting $\tau_{0}=1/k$. Below we propose a different way to specify $\tau_{k}$ for the APMD method so that it can achieve this ${\cal O}(\gamma^{k})$ rate of convergence without fixing $k$ a priori.

We first establish a technical result that will also be used later for the analysis of stochastic PMD methods.

Assume that the nonnegative sequences $\{X_{k}\}_{k\geq 0},\{Y_{k}\}_{k\geq 0}$ and $\{Z_{k}\}_{k\geq 0}$ satisfy

Let us denote $l=\left\lceil\log_{\gamma}\tfrac{1}{4}\right\rceil$. If $Y_{k}=Y\cdot 2^{-(\lfloor k/l\rfloor+1)}$ and $Z_{k}=Z\cdot 2^{-(\lfloor k/l\rfloor+2)}$ for some $Y\geq 0$ and $Z\geq 0$, then

Let us group the indices $\{0,\ldots,k\}$ into $\bar{p}\equiv\lfloor k/l\rfloor+1$ epochs with each of the first $\bar{p}-1$ epochs consisting of $l$ iterations. Let $p=0,\ldots,\bar{p}$ be the epoch indices. We first show that for any $p=0,\ldots,\bar{p}-1$,

This relation holds obviously for $p=0$. Let us assume that (3.33) holds at the beginning of epoch $p$ ad examine the progress made in epoch $p$. Note that for any indices $k=pl,\ldots,(p+1)l-1$ in epoch $p$, we have $Y_{k}=Y\cdot 2^{-(p+1)}$ and $Z=Z\cdot 2^{-(p+2)}$. By applying (3.31) recursively, we have

where the second inequality follows from the definition of $Z_{pl}$ and $\gamma^{l}\geq 0$, the third one follows from $\gamma^{l}\leq 1/4$, the fourth one follows by induction hypothesis, and the last one follows by regrouping the terms. Since $k=(\bar{p}-1)l+k\pmod{l}$, we have

We are now ready to present a more convenient selection of $\tau_{k}$ and $\eta_{k}$ for the APMD method.

Let us denote $l:=\left\lceil\log_{\gamma}\tfrac{1}{4}\right\rceil.$ If $\tau_{k}=2^{-(\lfloor k/l\rfloor+1)}$ and $1+\eta_{k}\tau_{k}=1/\gamma$, then

Noting that $V_{\tau_{k}}^{\pi_{k}}(s)\geq V^{\pi_{k}}(s)$, $V_{\tau_{k}}^{\pi^{*}}(s)\leq V^{\pi^{*}}(s)+\tfrac{\tau_{k}}{1-\gamma}\log|{\cal A}|$, $V_{\tau_{0}}^{\pi^{*}}(s)\geq V^{\pi^{*}}(s)$ due to (3.18), and that $V_{\tau_{0}}^{\pi_{0}}(s)=V^{\pi_{0}}(s)$ due to $D_{\pi_{0}}^{\pi_{0}}(s)=0$, we conclude from the previous inequality and the definition of $\tau_{k}$ that

In view of Theorem 3.4, a policy $\bar{\pi}$ s.t. $f(\bar{\pi})-f(\pi^{*})\leq\epsilon$ will be found in at most ${\cal O}(\log(1/\epsilon))$ epochs and hence at most ${\cal O}(l\log(1/\epsilon))={\cal O}(\log_{\gamma}(\epsilon))$ iterations, which matches the one for solving RL problems with strongly convex regularizers. However, for general RL problems, we cannot guarantee the linear convergence of $D_{\pi_{k+1}}^{\pi^{*}}(s)$ since its coefficient $\tau_{k}$ will become very small eventually. By using the continuity of the objective function and the compactness of the feasible set, we can possibly show that the solution sequence converges to the true optimal policy asymptotically as the number of iterations increases. On the other hand, the rate of convergence associated with the solution sequence of the PMD method for general RL problems cannot be established unless more structural properties of the RL problems can be further explored.

Stochastic Policy Mirror Descent

The policy mirror descent methods described in the previous section require the input of the exact action-value functions $Q^{\pi_{k}}$. This requirement can hardly be satisfied in practice even for the case when ${\cal P}$ is given explicitly, since $Q^{\pi_{k}}$ is defined as an infinite sum. In addition, in RL one does not know the transition dynamics ${\cal P}$ and thus only stochastic estimators of action-value functions are available. In this section, we propose stochastic versions for the PMD and APMD methods to address these issues.

In this subsection, we assume that for a given policy $\pi_{k}$, there exists a stochastic estimator ${\cal Q}^{\pi_{k},\xi_{k}}$ s.t.

for some $\sigma_{k}\geq$ and $\varsigma_{k}\geq 0$, where $\xi_{k}$ denotes the random vector used to generate the stochastic estimator ${\cal Q}^{\pi_{k},\xi_{k}}$. Clearly, if $\sigma_{k}=0$, then we have exact information about $Q^{\pi_{k}}$. One key insight we have for the stochastic PMD methods is to handle separately the bias term $\varsigma_{k}$ from the overall expected error term $\sigma_{k}$, because one can reduce the bias term much faster than the total error. This makes the analysis of the stochastic PMD method considerably different from that of the classic stochastic mirror descent method. While in this section we focus on the convergence analysis of the algorithms, we will show in next section that such separate treatment of bias and total error enables us to substantially improve the sampling complexity for solving RL problems by using policy gradient type methods.

The stochastic policy mirror descent (SPMD) is obtained by replacing $Q^{\pi_{k}}$ in (3.5) with its stochastic estimator ${\cal Q}^{\pi_{k},\xi_{k}}$, i.e.,

In the sequel, we denote $\xi_{\lceil k\rceil}$ the sequence of random vectors $\xi_{0},\ldots,\xi_{k}$ and define

By using the assumptions in (4.1) and (4.3) and the decomposition

Similar to Lemma 5, below we show some general convergence properties about the SPMD method. Unlike PMD, SPMD does not guarantee the non-increasing property of $V^{\pi_{k}}(s)$ anymore.

Observe that (3.10) still holds, and hence that

where the first inequality follows from Young’s inequality and the second one follows from the strong convexity of $D_{\pi_{k+1}}^{\pi_{k}}$ w.r.t. to $\|\cdot\|_{1}$. Moreover, we conclude from Lemma 4 applied to (4.4) with $Q^{\pi_{k}}$ replaced by ${\cal Q}^{\pi_{k},\xi_{k}}$ and $p(\cdot|s^{\prime})=\pi_{k}(\cdot|s^{\prime})$ that

where the last inequality follows from the fact that $d_{s}^{\pi_{k+1}}(s)\geq 1-\gamma$ due to the definition of $d_{s}^{\pi_{k+1}}$ in (2.1). The result in (4.7) then follows immediately from (4.8) and the above inequality.

We now establish an important recursion about the SPMD method.

By applying Lemma 4 to (3.5) (with $Q^{\pi_{k}}$ replaced by ${\cal Q}^{\pi_{k},\xi_{k}}$ and $p=\pi^{*}$), we have

which, in view of (4.7), then implies that

Taking expectation w.r.t. $\xi_{\lceil k\rceil}$ and $\nu^{*}$ on both sides of the above inequality, and using Lemma 3 and the relation in (4.6), we arrive at

Noting $V^{\pi_{k+1}}(s)-V^{\pi_{k}}(s)=V^{\pi_{k+1}}(s)-V^{\pi^{*}}(s)-[V^{\pi_{k}}(s)-V^{\pi^{*}}(s)]$, rearranging the terms in the above inequality, and using the definition of $f$ in (1.9), we arrive at the result.

We are now ready to establish the convergence rate of the SPMD method. We start with the case when $\mu>0$ and state a constant stepsize rule which requires both $\varsigma_{k}$ and $\sigma_{k}$, $k\geq 0$, to be small enough to guarantee the convergence of the SPMD method.

Suppose that $\eta_{k}=\eta=\tfrac{1-\gamma}{\gamma\mu}$ in the SPMD method. If $\varsigma_{k}=2^{-(\lfloor k/l\rfloor+2)}$ and $\sigma_{k}^{2}=2^{-(\lfloor k/l\rfloor+2)}$ for any $k\geq 0$ with $l:=\left\lceil\log_{\gamma}(1/4)\right\rceil$, then

By Lemma 13 and the selection of $\eta$, we have

We now turn our attention to the convergence properties of the SPMD method for the case when $\mu=0$.

Suppose that $\eta_{k}=\eta$ for any $k\geq 0$ in the SPMD method. If $\varsigma_{k}\leq\varsigma$ and $\sigma_{k}\leq\sigma$ for any $k\geq 0$, then we have

where $R$ denotes a random number uniformly distributed between $1$ and $k$. In particular, if the number of iterations $k$ is given a priori and $\eta=(\tfrac{2(1-\gamma)\log|{\cal A}|}{k\sigma^{2}})^{1/2}$, then

By Lemma 13 and the fact that $\mu=0$, we have

Taking the telescopic sum of the above relations, we have

Dividing both sides by $(1-\gamma)k$ and using the definition of $R$, we obtain the result in (4.10).

We add some remarks about the results in Theorem 4.2. In comparison with the convergence results of SPMD for the case $\mu>0$, there exist some possible shortcomings for the case when $\mu=0$. Firstly, one needs to output a randomly selected $\pi_{R}$ from the trajectory. Secondly, since the first term in (4.11) converges sublinearly, one has to update $\pi_{k+1}$ at least ${\cal O}(1/\epsilon)$ times, which may also impact the gradient complexity of computing $\nabla h^{\pi}$ if $\pi_{k+1}$ cannot be computed explicitly. We will address these issues by developing the stochastic APMD method in next subsection.

2 Stochastic approximate policy mirror descent

The stochastic approximate policy mirror descent (SAPMD) method is obtained by replacing $Q_{\tau_{k}}^{\pi_{k}}$ in (3.20) with its stochastic estimator ${\cal Q}_{\tau_{k}}^{\pi_{k},\xi_{k}}$. As such, its updating formula is given by

With a little abuse of notation, we still denote $\delta_{k}:={\cal Q}_{\tau_{k}}^{\pi_{k},\xi_{k}}-Q_{\tau_{k}}^{\pi_{k}}$ and assume that

for some $\sigma_{k}\geq$ and $\varsigma_{k}\geq 0$. Similarly to (4.6) we have

Lemma 14 and Lemma 15 below show the improvement for each SAPMD iteration.

The proof is similar to the one for Lemma 12 except that we will apply Lemma 2 to the perturbed value functions $V_{\tau_{k}}^{\pi}$ instead of $V^{\pi}$.

If $1+\eta_{k}\tau_{k}=1/\gamma$ and $\tau_{k}\geq\tau_{k+1}$ in the SAPMD method, then for any $k\geq 0$,

By Lemma 8 with $p=\pi^{*}$ and $Q_{\tau_{k}}^{\pi_{k}}$ replaced by ${\cal Q}_{\tau_{k}}^{\pi_{k},\xi_{k}}$, we have

Taking expectation w.r.t. $\xi_{\lceil k\rceil}$ and $\nu^{*}$ on both sides of the above inequality, and using Lemma 7 and the relation in (4.16), we arrive at

Noting $V_{\tau_{k}}^{\pi_{k+1}}(s)-V_{\tau_{k}}^{\pi_{k}}(s)=V_{\tau_{k}}^{\pi_{k+1}}(s)-V_{\tau_{k}}^{\pi^{*}}(s)-[V_{\tau_{k}}^{\pi_{k}}(s)-V_{\tau_{k}}^{\pi^{*}}(s)]$ and rearranging the terms in the above inequality, we have

which, in view of the assumption $\tau_{k}\geq\tau_{k+1}$ and (3.19), then implies that

The result then immediately follows from the assumption that $1+\eta_{k}\tau_{k}=1/\gamma$.

We are now ready to establish the convergence of the SAPMD method.

Suppose that $\eta_{k}=\tfrac{1-\gamma}{\gamma\tau_{k}}$ in the SAPMD method. If $\tau_{k}=\tfrac{1}{\sqrt{\gamma\log|{\cal A}|}}2^{-(\lfloor k/l\rfloor+1)}$, $\varsigma_{k}=2^{-(\lfloor k/l\rfloor+2)}$, and $\sigma_{k}^{2}=4^{-(\lfloor k/l\rfloor+2)}$ with $l:=\left\lceil\log_{\gamma}(1/4)\right\rceil$, then

By Lemma 15 and the selection of $\tau_{k},\varsigma_{k}$ and $\sigma_{k}$, we have

Noting that $V_{\tau_{k}}^{\pi_{k}}(s)\geq V^{\pi_{k}}(s)$, $V_{\tau_{k}}^{\pi^{*}}(s)\leq V^{\pi^{*}}(s)+\tfrac{\tau_{k}}{1-\gamma}\log|{\cal A}|$, $V_{\tau_{0}}^{\pi^{*}}(s)\geq V^{\pi^{*}}(s)$ due to (3.18), and that $V_{\tau_{0}}^{\pi_{0}}(s)=V^{\pi_{0}}(s)$ due to $D_{\pi_{0}}^{\pi_{0}}(s)=0$, we conclude from the previous inequality and the definition of $\tau_{k}$ that

from which the result immediately follows.

A few remarks about the convergence of the SAPMD method are in place.

First, in view of Theorem 4.3, the SAPMD method does not need to randomly output a solution as most existing nonconvex stochastic gradient descent methods did. Instead, the linear rate of convergence in (4.20) has been established for the last iterate $\pi_{k}$ generated by this algorithm. The convergence for the last iterate indicates that the SAMPD method will continuously improve the policy deployed by the system for implementation and evaluation. This is not the case for the convergence of the average or random iterate, since the average iterate will not be implemented and evaluated, and the convergence of the random iterate does not warrant continuous improvement of the generated policies.

Second, both Theorems 4.1 and 4.3 allow us to establish some strong large-deviation properties associated with the convergence of SPMD and SAPMD. Let us focus on the SAPMD method. For a given confidence level $\lambda\in(0,1)$ and accuracy level $\epsilon>0$, if the number of iterations $k$ satisfies

then by (4.20) and Markov’s inequality, we have

In other words, with probability greater than $1-\lambda$, we have $f(\pi_{k})-f(\pi^{*})\leq\epsilon$. On the other hand, it is more difficult to derive a similar large deviation result for SPMD directly applied to unregularized problems (c.f. Theorem 4.2). Due to the sublinear rate of convergence and random selection of output, we need to run the algorithm for a few times to general several candidate solutions and apply a post-optimization procedure to choose from these candidate solutions in order to improve the the reliability of the algorithm (see Chapter 6 of LanBook2020 for more discussions).

Stochastic Estimation for Action-value Functions

In this section, we discuss the estimation of the action-value functions $Q^{\pi}$ or $Q^{\pi}_{\tau}$ through two different approaches. In Subsection 5.1, we assume the existence of a generative model for the Markov Chains so that we can estimate value functions by generating multiple independent trajectories starting from an arbitrary pair of state and action. In Subsection 5.2, we consider a more challenging setting where we only have access to a single trajectory observed when the dynamic system runs online. In this case, we employ and enhance the conditional temporal difference (CTD) method recently developed in KotsalisLanLi2020PartII to estimate value functions. Throughout the section we assume that

In the multiple trajectory setting, starting from state-action pair $(s,a)$ and following policy $\pi_{k}$, we can generate $M_{k}$ independent trajectories of length $T_{k}$, denoted by

Let $\xi_{k}:=\{\zeta_{k}^{i}(s,a),i=1,\ldots,M_{k},s\in{\cal S},a\in{\cal A}\}$ denote all these random variables. We can estimate $Q^{\pi_{k}}$ in the SPMD method by

We can show that ${\cal Q}^{\pi_{k},\xi_{k}}$ satisfy (4.1)-(4.3) with

for some absolute constant $\kappa>0$ (see Proposition 7 in the Appendix). By choosing $T_{k}$ and $M_{k}$ properly, we can show the convergence of the SPMD method employed with different stepsize rules as stated in Theorems 4.1 and 4.2.

Suppose that $\eta_{k}=\tfrac{1-\gamma}{\gamma\mu}$ in the SPMD method. If $T_{k}$ and $M_{k}$ are chosen such that

Using the fact that $\gamma^{l}\leq 1/4$, we can easily check from (5.3) and the selection of $T_{k}$ and $M_{k}$ that (4.1)-(4.3) hold with $\varsigma_{k}=2^{-(\lfloor k/l\rfloor+2)}$ and $\sigma_{k}^{2}=2^{-(\lfloor k/l\rfloor+2)}$. Suppose that an $\epsilon$-solution $\bar{\pi}$ will be found at the $\bar{k}$ iteration. By (4.9), we have

which implies that the number of iterations is bounded by ${\cal O}(l\lfloor\bar{k}/l\rfloor)={\cal O}(\log_{\gamma}\epsilon)$. Moreover by the definition of $T_{k}$ and $M_{k}$, the total number of samples is bounded by

Below we discuss the sampling complexities of SPMD and SAPMD for solving RL problems with general convex regularizers.

We can easily check from (5.3) and the selection of $T_{k}$ and $M_{k}$ that (4.1)-(4.3) holds with $\varsigma_{k}=\epsilon/3$ and $\sigma_{k}^{2}=2(\tfrac{\epsilon^{2}}{3^{2}}+\tfrac{2(\bar{c}+\bar{h})^{2}}{(1-\gamma)^{2}})$. Using these bounds in (4.10), we conclude that an $\epsilon$-solution will be found in at most

iterations. Moreover, the total number of samples is bounded by $|{\cal S}||{\cal A}|T\bar{k}$ and hence by (5.5).

We can also establish the iteration and sampling complexities of the SAPMD method, in which we estimate $Q_{\tau_{k}}^{\pi_{k}}$ by

Since $\tau_{0}\geq\tau_{k}$, similar to (5.3), we can show that ${\cal Q}_{\tau_{k}}^{\pi_{k},\xi_{k}}$ satisfy (4.13)-(4.15) with

Suppose that $\eta_{k}=\tfrac{1-\gamma}{\gamma\tau_{k}}$ and $\tau_{k}=\tfrac{1}{\sqrt{\gamma\log|{\cal A}|}}2^{-(\lfloor k/l\rfloor+1)}$ in the SAPMD method. If $T_{k}$ and $M_{k}$ are chosen such that

Using the fact that $\gamma^{l}\leq 1/4$, we can easily check from (5.7) and the selection of $T_{k}$ and $M_{k}$ that (4.13)-(4.15) hold with $\varsigma_{k}=2^{-(\lfloor k/l\rfloor+2)}$ and $\sigma_{k}^{2}=4^{-(\lfloor k/l\rfloor+2)}$. Suppose that an $\epsilon$-solution $\bar{\pi}$ will be found at the $\bar{k}$ iteration. By (4.20), we have

which implies that the number of iterations is bounded by ${\cal O}(l\lfloor\bar{k}/l\rfloor)={\cal O}(\log_{\gamma}\epsilon)$. Moreover by the definition of $T_{k}$ and $M_{k}$, the number of samples is bounded by

2 Conditional temporal difference

In this subsection, we enhance a recently developed temporal different (TD) type method, i.e., conditional temporal difference (CTD) method, and use it to estimate the action-value functions in an online manner. We focus on estimating $Q^{\pi}$ in SPMD since the estimation of $Q^{\pi}_{\tau}$ in SAPMD is similar.

For a given policy $\pi$, we denote the Bellman operator

The action value function $Q^{\pi}$ corresponding to policy $\pi$ satisfies the Bellman equation

We make the following assumptions about policy $\pi$: (a) $\nu(\pi)(s)\geq\underline{\nu}$ for some $\underline{\nu}>0$, which holds when the Markov chain employed with policy $\pi$ has a single ergodic class with unique stationary distribution, i.e., $\nu(\pi)=\nu(\pi){\cal P}^{\pi}$; and (b) $\pi$ is sufficiently random, i.e., $\pi(s,a)\geq\underline{\pi}$ for some $\underline{\pi}>0$, which can be enforced, for example, by adding some corresponding constraints through $h^{\pi}$.

Note that Assumption 1.a) is widely accepted for evaluating policies using TD type methods in the RL literature, and that Assumption 1.b) requires that $\pi$ assigns a non-zero probability to each action. We will discuss how to possibly relax these assumptions, especially Assumption 1.b) later in Remark 1.

In view of Assumption 1 we have $M^{\pi}\succ 0$. With this weighting matrix $M^{\pi}$, we define the operator $F^{\pi}$ as

where $T^{\pi}$ is the Bellman operator defined in (5.9). Our goal is to find the root $\theta^{*}\equiv Q^{\pi}$ of $F(\theta)$, i.e., $F(\theta^{*})=0$. We can show that $F$ is strongly monotone with strong monotonicity modulus bounded from below by $\Lambda_{\min}:=(1-\gamma)\lambda_{\min}(M^{\pi}).$ Here $\lambda_{\min}(A)$ denotes the smallest eigenvalue of $A$. It can also be easily seen that $F^{\pi}$ is Lipschitz continuous with Lipschitz constant bounded by $\Lambda_{\max}:=(1-\gamma)\lambda_{\max}(M^{\pi}),$ where $\lambda_{\max}(A)$ denotes the largest eigenvalue of $A$.

The following result can be shown similarly to Lemma 4.1 of KotsalisLanLi2020PartII.

The following result has been shown in Proposition 6.2 of KotsalisLanLi2020PartII.

If the algorithmic parameters in CTD are chosen such that

with $t_{0}=8\max\{\Lambda_{\max}^{2},8(1+\gamma)^{2}\}/\Lambda_{\min}^{2}$, then

Suppose that the algorithmic parameters in CTD are set according to Lemma 17. Then we have

We are now ready to establish the convergence of the SMPD method by using the CTD method to estimate the action-value functions. We focus on the case when $\mu>0$, and the case for $\mu=0$ can be shown similarly.

Suppose that $\eta_{k}=\tfrac{1-\gamma}{\gamma\mu}$ in the SPMD method. If the initial point of CTD is set to $\theta_{1}=0$ and the number of iterations $T$ and the parameter $\alpha$ in CTD are set to

Using the fact that $\gamma^{l}\leq 1/4$, we can easily check from Lemma 17, Lemma 18, and the selection of $T$ and $\alpha$ that (4.1)-(4.3) hold with $\varsigma_{k}=2^{-(\lfloor k/l\rfloor+2)}$ and $\sigma_{k}^{2}=2^{-(\lfloor k/l\rfloor+2)}$. Suppose that an $\epsilon$-solution $\bar{\pi}$ will be found at the $\bar{k}$ iteration. By (4.9), we have

which implies that the number of iterations is bounded by ${\cal O}(l\lfloor\bar{k}/l\rfloor)={\cal O}(\log_{\gamma}\epsilon)$. Moreover by the definition of $T_{k}$ and $\alpha_{k}$, the number of samples is bounded by

The following result shows the convergence properties of the SAMPD method when the action-value function is estimated by using the CTD method.

Suppose that $\eta_{k}=\tfrac{1-\gamma}{\gamma\tau_{k}}$ and $\tau_{k}=\tfrac{1}{\sqrt{\gamma\log|{\cal A}|}}2^{-(\lfloor k/l\rfloor+1)}$ in the SAPMD method. If the initial point of CTD is set to $\theta_{1}=0$, the number of iterations $T$ is set to

The proof is similar to that of Proposition 4 except that we will show that (4.1)-(4.3) hold with $\varsigma_{k}=2^{-(\lfloor k/l\rfloor+2)}$ and $\sigma_{k}^{2}=4^{-(\lfloor k/l\rfloor+2)}$. Moreover, we will use (4.20) instead of (4.9) to bound the number of iterations.

To the best of our knowledge, the complexity result in (5.16) is new in the RL literature, while the one in (5.18) is new for policy gradient type methods. It seems that this bound significantly improves the previously best-known ${\cal O}(1/\epsilon^{3})$ sampling complexity result for stochastic policy gradient methods (see Xu2020ImprovingSC and Appendix C of Khodadadian2021 for more explanation).

In this subsection we focus on the more restrictive assumption $M^{\pi}\succ 0$ in order to compare our results with the existing ones in the literature. Here we discuss how one can possibly relax this assumption.

An alternative approach that can relax Assumption 1.b), would be to first run the enhanced CTD method to the following equation

to evaluate the state-value function $V^{\pi}$. Then we estimate the action-value function $Q^{\pi}$ by using (1.5), i.e.,

In order to use the above identity, we need to define an estimator of ${\cal P}(s^{\prime}|s,a)$ by using a uniform policy $\pi_{0}(\cdot|s):=\{1/|A|,\ldots,1/|A|\}$. The sample size required to estimate the transition kernel from a single trajectory is an active research topic (see WolferKonttorovich20 and references therein). Current research has been focused only on bounding on the total error for estimating ${\cal P}(s^{\prime}|s,a)$ for a given sample size, and there do not exist separate and tighter bounds on the bias for these estimators. Therefore, it is still not evident whether the same sampling complexity bounds in Propositions 4 and 5 can be maintained using this alternative approach to relax the assumption of non-zero probability to each action.

For problems of high dimension (i.e., $n\equiv|{\cal S}|\times|{\cal A}|$ is large), one often resorts to a parametric approximation of the value function. In this case it is possible to define a more general operator $F^{\pi}(\theta):=\Phi^{T}M^{\pi}\big(\Phi\theta-T^{\pi}\Phi\theta\big)$ for some feature matrix $\Phi$ to evaluate the value functions (see Section 4 of KotsalisLanLi2020PartII for a discussion about CTD with function approximation). Unless the column space of $\Phi$ spans the true value functions, an additional bias term will be introduced into the computation of gradients, resulting into an extra error term in the overall rate of convergence of PMD methods. In other words, these methods can only be guaranteed to converge to a neighborhood of the optimal solution. Nevertheless, the application of function approximation will significantly reduce the dependence of gradient computation on the problem dimension, i.e., from $|{\cal S}|\times|{\cal A}|$ to the number of columns of $\Phi$.

Efficient Solution for General Subproblems

In this section, we study the convergence properties of the PMD methods for the situation where we do not have exact solutions for prox-mapping subprobems. Throughout this section, we assume that $h^{\pi}$ is differentiable and its gradients are Lipschitz continuous with Lipschitz constant $L$. We will first review Nesterov’s accelerated gradient descent (AGD) method Nest83-1, and then discuss the overall gradient complexity of using this method for solving prox-mapping in the PMD methods. We will focus on the stochastic PMD methods since they cover deterministic methods as certain special cases.

Let us denote $X\equiv\Delta_{|{\cal A}|}$ and consider the problem of

for some $\mu_{\chi}\geq 0$. Given $(x_{t-1},y_{t-1})\in X\times X$, the accelerated gradient method performs the following updates:

for some $q_{t}\in$, $r_{t}\geq 0$, and $\rho_{t}\in$ .

Below we slightly generalize the convergence results for the AGD method so that they depend on the distance $D_{x_{0}}^{x}$ rather than $\Phi(y_{0})-\Phi(x)$ for any $x\in X$. This result better fits our need to analyze the convergence of inexact SPMD and SAPMD methods in the next two subsections.

Let us denote $\mu_{\Phi}:=\mu_{\phi}+\mu_{\chi}$ and $t_{0}:=\lfloor 2\sqrt{L_{\phi}/\mu_{\Phi}}-1\rfloor$. If

Using the discussions in Corollary 3.5 of LanBook2020 (and the possible strong convexity of $\chi$), we can check that the conclusions in Theorems 3.6 and 3.7 of LanBook2020 hold for the AGD method applied to problem (6.1). It then follows from Theorem 3.6 of LanBook2020 that

Moreover, it follows from Theorem 3.7 of LanBook2020 that for any $t\geq t_{0}$,

where the last inequality follows from (6.7) (with $t=t_{0}$) and the facts that

for any $2\leq t\leq t_{0}$. The result then follows by combining these observations.

2 Convergence of inexact SPMD

In this subsection, we study the convergence properties of the SPMD method when its subproblems are solved inexactly by using the AGD method (see Algorithm 4). Observe that we use the same initial point $\pi_{0}$ whenever calling the AGD method. To use a dynamic initial point (e.g., $v_{k}$) will make the analysis more complicated since we do not have a uniform bound on the KL divergence $D_{v_{k}}^{\pi}$ for an arbitrary $v_{k}$. To do so probably will require us to use other distance generating functions than the entropy function.

In the sequel, we will denote $\varepsilon_{k}\equiv\varepsilon(T_{k})$ to simplify notations. The following result will take place of Lemma 4 in our convergence analysis.

It follows from Lemma 19 (with $\mu_{\Phi}=1+\mu\eta_{k}$ and $L_{\phi}=L$) that

Using the definition of $\Phi_{k}$, we have

which proves (6.9). Setting $\pi=\pi_{k}$ and $\pi=\pi_{k+1}$ respectively, in the above conclusion, we obtain

Then (6.10) follows by combining these two inequalities.

where the last inequality follows from the fact that $d_{s}^{\pi_{k+1}}(s)\geq(1-\gamma)$ due to the definition of $d_{s}^{\pi_{k+1}}$ in (2.1). The result in (6.11) then follows immediately from (6.12) and the above inequality.

We now establish an important recursion about the inexact SPMD method in Algorithm 4.

Suppose that $\eta_{k}=\eta=\tfrac{1-\gamma}{\gamma\mu}$ and $\varepsilon_{k}\leq\varepsilon_{k-1}$ for any $k\geq 0$ in the inexact SPMD method, we have

which, in view of (4.7), then implies that

Taking expectation w.r.t. $\xi_{\lceil k\rceil}$ and $\nu^{*}$ on both sides of the above inequality, and using Lemma 3 and the relation in (4.6), we arrive at

Noting $V^{\pi_{k+1}}(s)-V^{\pi_{k}}(s)=V^{\pi_{k+1}}(s)-V^{\pi^{*}}(s)-[V^{\pi_{k}}(s)-V^{\pi^{*}}(s)]$, rearranging the terms in the above inequality, and using the definition of $f$ in (1.9), we arrive at

The result then follows immediately by the selection of $\eta$ and the assumption $\varepsilon_{k}\leq\varepsilon_{k-1}$.

We now are now ready to state the convergence rate of the SPMD method with inexact prox-mapping. We focus on the case when $\mu>0$.

Suppose that $\eta_{k}=\eta=\tfrac{1-\gamma}{\gamma\mu}$ in the inexact SPMD method. If $\varsigma_{k}=(1-\gamma)2^{-(\lfloor k/l\rfloor+2)}$, $\sigma_{k}^{2}=2^{-(\lfloor k/l\rfloor+2)}$ and $\varepsilon_{k}=(1-\gamma)^{2}2^{-(\lfloor(k+1)/l\rfloor+2)}$ for any $k\geq 0$ with $l:=\left\lceil\log_{\gamma}(1/4)\right\rceil$, then

The result follows as an immediate consequence of Proposition 21 and Lemma 11.

Also observe that the condition number of the subproblem is given by

Combining these observations with Lemma 19, we conclude that the total number of gradient computations of $h$ can be bounded by

3 Convergence of inexact SAPMD

In this subsection, we study the convergence properties of the SAPMD method when its subproblems are solved inexactly by using the AGD method (see Algorithm 5).

In the sequel, we will still denote $\varepsilon_{k}\equiv\varepsilon(T_{k})$ to simplify notations. The following result has the same role as Lemma 20 in our convergence analysis.

The proof is the same as that for Lemma 20 except that Lemma 19 will be applied to problem (6.15) (with $\mu_{\Phi}=1+\tau_{k}\eta_{k}$ and $L_{\phi}=L$).

The proof is similar to that for Lemma 6 with the following two exceptions: (a) we will apply Lemma 2 (i.e., the performance difference lemma) to the perturbed value functions $V_{\tau_{k}}^{\pi}$ instead of $V^{\pi}$ to obtain a result similar to (6.12); and (b) we will use use (6.17) in place of (6.10) to derive a bound similar to (6.13).

Suppose that $1+\eta_{k}\tau_{k}=1/\gamma$ and $\varepsilon_{k}\leq\varepsilon_{k-1}$ in the SAPMD method. Then for any $k\geq 0$, we have

Taking expectation w.r.t. $\xi_{\lceil k\rceil}$ and $\nu^{*}$ on both sides of the above inequality, and using Lemma 3 (with $h^{\pi}$ replaced by $h^{\pi}+\tau_{k}D_{\pi_{0}}^{\pi}(s_{t})$ and $Q^{\pi}$ replaced by $Q_{\tau}^{\pi}$) and the relation in (4.6), we arrive at