1 Introduction↩︎

Policy gradient (PG) methods have emerged as a popular class of algorithms for reinforcement learning. Unlike classical methods based on (approximate) dynamic programming [1]–[4], PG methods update directly the policy and its parametrization along the gradient direction of the value function [5]–[8]. An important variant of PG is the natural policy gradient (NPG) method [9], which is a direct application of natural gradient method [10] for RL. NPG uses the Fisher information matrix of the policy distribution as a preconditioner to improve the policy gradient direction, similar to quasi-Newton methods in classical optimization [11]. Variants of NPG with policy parametrization through deep neural networks were shown to have impressive empirical successes [12]–[17].

Motivated by the success of NPG in practice, there is now a concerted effort to develop convergence theories for the NPG method. [18] provide the first interpretation of NPG as a mirror descent (MD) method [19], [20]. By leveraging different techniques for analyzing MD, it has been established that NPG converges to the global optimum in the tabular case [21]–[23] and some more general settings [24]–[27]. In order to get a fast linear convergence rate for NPG, several recent works consider the regularized NPG methods, such as the entropy-regularized NPG [28] and other convex regularized NPG methods [29], [30]. By designing appropriate step sizes, [22] and [23] obtain linear convergence of NPG without regularization (See Section 6 for a thorough review. In particular, Table [tab:full32picture] provides a complete overview of our results.). However, all these linear convergence results are limited in the tabular setting (direct parametrization). It remains unclear whether this same linear convergence rate can be established in the function approximation regime.

In this paper we provide an affirmative answer to this question for the log-linear policy class. Our approach is based on the framework of compatible function approximation [6], [9], which was extensively developed by [21]. Using this framework, variants of NPG with log-linear policies can be written as policy mirror descent (PMD) methods with inexact evaluations of the advantage function or Q-function (giving rise to NPG or Q-NPG respectively). Then by extending a recent analysis of PMD [23], we obtain a non-asymptotic linear convergence of both NPG and Q-NPG with log-linear policies. A distinctive feature of this approach is the use of a simple, non-adaptive geometrically increasing step size, without resorting to entropy or other (strongly) convex regularization.

1.1 Outline and Contributions↩︎

In Section 2 we review the fundamentals of Markov decision processes (MDP), and describe the log-linear policy class and the general NPG method. In Section 3 we explain the compatible function approximation framework and show that both NPG and Q-NPG can be expressed as inexact versions of the PMD method.

Our main contributions start from Section 4, which contains our results on Q-NPG. We present convergence results of Q-NPG in two different settings: one assuming bounded transfer error and a relative condition number (Section 4.1) and the other assuming bounded approximation error (Section 4.2). In both cases, we obtain linear convergence up to an error floor towards the global optima. The extensions of the analysis of PMD [23] are highly nontrivial and require quite different techniques (see Section 6.1 for more details). Compared with the sublinear convergence results of [21], we do not need a projection step nor the assumption of bounded feature maps. However, our results depends on some distribution mismatch coefficients and has larger error floors. In Section 4.3, by further assuming that the feature maps are bounded and have a non-singular covariance matrix, we obtain an \(\tilde{{\cal O}}(1/\epsilon^2)\) sample complexity for Q-NPG with log-linear policies. In particular, our sample complexity analysis also fixes errors of previous work.

In Section 5, we analyze the NPG method under the assumption of bounded approximation error, and show that it also enjoys linear convergence up to an error floor as well as an \(\tilde{{\cal O}}(1/\epsilon^2)\) sample complexity. As a by product of our analysis, we also obtain sublinear an \({\cal O}(1/k)\) convergence rate for both NPG and Q-NPG with unconstrained constant step sizes and no projection step.

2 Preliminaries on Markov Decision Processes↩︎

We consider an MDP denoted as \({\cal M}= \{{\cal S}, {\cal A}, {\cal P}, c, \gamma\}\), where \({\cal S}\) is a finite state space, \({\cal A}\) is a finite action space, \({\cal P}: {\cal S}\times {\cal A}\rightarrow {\cal S}\) is a Markovian transition model with \({\cal P}(s' \mid s, a)\) being the transition probability from state \(s\) to \(s'\) under action \(a\), \(c\) is a cost function with \(c(s, a) \in [0, 1]\) for all \((s,a)\in{\cal S}\times{\cal A}\), and \(\gamma \in [0, 1)\) is a discounted factor. Here we use cost instead of reward to better align with the minimization convention in the optimization literature.

Let \(\Delta({\cal X})\) denote the probability simplex for an arbitrary set \({\cal X}\). The agent’s behavior is modeled as a stochastic policy \(\pi \in \Delta({\cal A})^{|\cal S|}\), where \(\pi_s \in \Delta({\cal A})\) is the probability distribution over actions \({\cal A}\) in state \(s\in{\cal S}\). At each time \(t\), the agent takes an action \(a_t \in {\cal A}\) given the current state \(s_t \in {\cal S}\), following the policy \(\pi\), i.e., \(a_t \sim \pi_{s_t}\). Then the MDP transitions into the next state \(s_{t+1}\) with probability \({\cal P}(s_{t+1} \mid s_t, a_t)\) and the agent encounters the cost \(c_t = c(s_t, a_t)\). Thus, a policy induces a distribution over trajectories \(\{s_t, a_t, c_t\}_{t \geq 0}\). In the infinite-horizon discounted setting, the cost function of \(\pi\) with an initial state \(s\) is defined as \[\begin{align} \label{eq:V} V_s(\pi) \; \overset{\text{def}}{=}\; \underset{\substack{a_t \sim \pi_{s_t} \\ s_{t+1} \sim {\cal P}(\cdot \mid s_t, a_t)}}{\mathbb{E}}\left[\sum_{t=0}^\infty \gamma^t c(s_t, a_t) \mid s_0 = s\right]. \end{align}\tag{1}\] Given an initial state distribution \(\rho\in\Delta({\cal S})\), the goal of the agent is to find a policy \(\pi\) that minimizes the expected cost function \[V_\rho(\pi) \; \overset{\text{def}}{=}\; \mathbb{E}_{s \sim \rho}\left[V_{s}(\pi)\right] \; = \; \sum_{s \in {\cal S}}\rho_s V_s(\pi) \; = \; \left< V(\pi), \rho\right>.\]

A more granular characterization of the performance of a policy is the state-action cost function (Q-function). For any pair \((s,a) \in {\cal S}\times {\cal A}\), it is defined as \[\begin{align} \label{eq:Q-function} Q_{s,a}(\pi) \; \overset{\text{def}}{=}\; \underset{\substack{a_t \sim \pi_{s_t} \\ s_{t+1} \sim {\cal P}(\cdot \mid s_t, a_t)}}{\mathbb{E}} \left[\sum_{t=0}^\infty \gamma^t c(s_t, a_t) \mid s_0 = s, a_0 = a\right]. \end{align}\tag{2}\] Let \(Q_s\in\mathbb{R}^{|\cal A|}\) denote the vector \([Q_{s,a}]_{a\in{\cal A}}\). Then we have \(V_s(\pi)=\mathbb{E}_{a\sim\pi_s}\left[Q_{s,a}(\pi)\right] =\langle\pi_s, Q_s(\pi)\rangle .\) The advantage function⁶ is a centered version of the Q-function: \[\begin{align} \label{eq:Advantage} \quad \quad A_{s,a}(\pi) \; \overset{\text{def}}{=}\; Q_{s,a}(\pi) - V_s(\pi), \end{align}\tag{3}\] which satisfies \(\mathbb{E}_{a\sim\pi_s}\left[A_{s,a}(\pi)\right] =0\) for all \(s\in{\cal S}\).

2.0.0.1 Visitation probabilities.

Given a starting state distribution \(\rho\in\Delta({\cal S})\), we define the state visitation distribution \(d^\pi(\rho) \in \Delta({\cal S})\), induced by a policy \(\pi\), as \[d^\pi_s(\rho) \; \overset{\text{def}}{=}\; (1-\gamma)\, \mathbb{E}_{s_0 \sim \rho}\left[\sum_{t=0}^\infty \gamma^t \mathop{\mathrm{Pr}}^{\pi}(s_t = s \mid s_0)\right] ,\] where \(\mathop{\mathrm{Pr}}^\pi(s_t = s \mid s_0)\) is the probability that the \(t\)-th state is equal to \(s\) by following the trajectory generated by \(\pi\) starting from \(s_0\). Intuitively, the state visitation distribution measures the probability of being at state \(s\) across the entire trajectory. We define the state-action visitation distribution \(\bar{d}^{\,\pi}(\rho)\in \Delta({\cal S}\times {\cal A})\) as \[\label{eq:dbarrho} \bar{d}^{\,\pi}_{s,a}(\rho) \; \overset{\text{def}}{=}\; d^\pi_s(\rho)\pi_{s,a} \;=\; (1-\gamma)\, \mathbb{E}_{s_0\sim\rho}\left[\sum_{t=0}^\infty \gamma^t \mathop{\mathrm{Pr}}^\pi(s_t = s, a_t = a \mid s_0)\right] .\tag{4}\] In addition, we extend the definition of \(\bar{d}^{\,\pi}(\rho)\) by specifying the initial state-action distribution \(\nu\in\Delta({\cal S}\times{\cal A})\), i.e., \[\begin{align} \label{eq:dbarnu} \tilde{d}^{\,\pi}_{s,a}(\nu) \; &\overset{\text{def}}{=}\; (1-\gamma)\,\mathbb{E}_{(s_0,a_0) \sim \nu}\left[\sum_{t=0}^\infty \gamma^t \mathop{\mathrm{Pr}}^\pi(s_t = s, a_t = a \mid s_0, a_0)\right] . \end{align}\tag{5}\] The difference in the last two definitions is that for the former, the initial action \(a_0\) is sampled directly from \(\pi\), whereas for the latter, it is prescribed by the initial state-action distribution \(\nu\). We use \(\tilde{d}\) compared to \(\bar{d}\) to better distinguish the cases with \(\nu\) and \(\rho\). Without specification, we even omit the argument \(\nu\) or \(\rho\) throughout the paper to simplify the presentation as they are self-evident. From these definitions, we have for all \((s,a) \in {\cal S}\times {\cal A}\), \[\begin{align} \label{eq:d} d^\pi_s \geq (1-\gamma)\rho_s, \qquad \bar{d}^{\,\pi}_{s,a} \geq (1-\gamma) \rho_s \pi_{s,a}, \qquad \tilde{d}^{\,\pi}_{s,a} \geq (1-\gamma) \nu_{s,a}. \end{align}\tag{6}\]

2.0.0.2 Policy parametrization.

In practice, both the state and action spaces \({\cal S}\) and \({\cal A}\) can be very large and some form of function approximation is needed to reduce the dimensions and make the computation feasible. In particular, the policy \(\pi\) is often parametrized as \(\pi(\theta)\) with \(\theta \in \mathbb{R}^m\), where \(m\) is much smaller than \(|{\cal S}|\) and \(|{\cal A}|\). In this paper, we focus on the log-linear policy class. Specifically, we assume that for each state-action pair \((s,a)\), there is a feature mapping \(\phi_{s,a} \in \mathbb{R}^m\) and the policy takes the form \[\label{eq:loglinear} \pi_{s,a}(\theta) \; = \; \frac{\exp(\phi_{s,a}^\top \theta)}{\sum_{a' \in {\cal A}} \exp(\phi_{s,a'}^\top \theta)}.\tag{7}\] This setting is important since it is the simplest instantiation of the widely-used neural policy parametrization. To simplify notation in the rest of this paper, we use the shorthand \(V_\rho(\theta)\) for \(V_\rho(\pi(\theta))\) and similarly \(Q_{s,a}(\theta)\) for \(Q_{s,a}(\pi(\theta))\), \(A_{s,a}(\theta)\) for \(A_{s,a}(\pi(\theta))\), \(d^{\theta}_s\) for \(d^{\pi(\theta)}_s\), \(\bar{d}^{\,\theta}_{s,a}\) for \(\bar{d}^{\,\pi(\theta)}_{s,a}\), and \(\tilde{d}^{\,\theta}_{s,a}\) for \(\tilde{d}^{\,\pi(\theta)}_{s,a}\).

2.0.0.3 Natural Policy Gradient (NPG) Method.

Using the notations defined above, the parametrized policy optimization problem is to minimize the function \(V_\rho(\theta)\) over \(\theta\in\mathbb{R}^m\). The policy gradient is given by [5], [6] \[\label{eq:policy-grad-Q} \nabla_\theta V_\rho(\theta) = \frac{1}{1-\gamma} \mathbb{E}_{s\sim d^{\theta},\,a\sim\pi_s(\theta)}\left[Q_{s,a}(\theta)\,\nabla_\theta\log\pi_{s,a}(\theta)\right] .\tag{8}\] For parametrizations that are differentiable and satisfy \(\sum_{a\in{\cal A}}\pi_{s,a}(\theta)=1\), including the log-linear class defined in 7 , we can replace \(Q_{s,a}(\theta)\) by \(A_{s,a}(\theta)\) in the above expression [21]. The NPG method [9] takes the form \[\label{eq:npg} \theta^{(k+1)} \;=\; \theta^{(k)} - \eta_k F_\rho\bigl(\theta^{(k)}\bigr)^\dagger \,\nabla_\theta V_\rho\bigl(\theta^{(k)}\bigr),\tag{9}\] where \(\eta_k>0\) is a scalar step size, \(F_\rho(\theta)\) is the Fisher information matrix \[\begin{align} \label{eq:fisher} F_\rho(\theta) \;\overset{\text{def}}{=}\; \mathbb{E}_{s\sim d^{\theta},\,a\sim\pi_s(\theta)}\left[\nabla_\theta \log\pi_{s,a}(\theta)\bigl(\nabla_\theta \log\pi_{s,a}(\theta)\bigr)^\top\right] , \end{align}\tag{10}\] and \(F_\rho(\theta)^\dagger\) denotes the Moore-Penrose pseudoinverse of \(F_\rho(\theta)\).

3 NPG with Compatible Function Approximation↩︎

The parametrized value function \(V_\rho(\theta)\) is non-convex in general [21]. Despite being a non-convex optimization problem, there is still additional structure we can leverage to ensure convergence. Following [21], we adopt the framework of compatible function approximation [6], [9], which exploits the MDP structure and leads to tight convergence rate analysis.

For any \(w\in\mathbb{R}^m\), \(\theta\in\mathbb{R}^m\) and state-action distribution \(\zeta\in\Delta({\cal S}\times{\cal A})\), we define the compatible function approximation error as \[\begin{align} \label{eq:compatible-A} L_A(w, \theta, \zeta) \; \overset{\text{def}}{=}\; \mathbb{E}_{(s,a) \sim \zeta}\left[\bigl( w^\top \nabla_\theta\log\pi_{s,a}(\theta) - A_{s, a}(\theta)\bigr)^2\right] . \end{align}\tag{11}\] [9] showed that the NPG update 9 is equivalent to (up to a constant scaling of \(\eta_k\)) \[\begin{align} \label{eq:NPG-cfa} \theta^{(k+1)} \; = \; \theta^{(k)} - \eta_k w_\star^{(k)}, \qquad w_\star^{(k)} \in \mathop{\mathrm{argmin}}_{w\in\mathbb{R}^m} L_A\bigl(w, \theta^{(k)}, \bar{d}^{\,(k)}\bigr), \end{align}\tag{12}\] where \(\bar{d}^{\,(k)}\) is a shorthand for the state-action visitation distribution \(\bar{d}^{\,\pi(\theta^{(k)})}(\rho)\) defined in 4 . A derivation of 12 is provided in Appendix 8 (Lemma 1) for completeness. In other words, \(w_\star^{(k)}\) is the solution to a regression problem that tries to approximate \(A_{s,a}(\theta^{(k)})\) using \(\nabla_\theta\log\pi_{s,a}(\theta^{(k)})\) as features. This is where the term "compatible function approximation error" comes from. For the log-linear policy class defined in 7 , we have \[\begin{align} \label{eq:grad95log95linear} \nabla_\theta \log\pi_{s,a}(\theta) \;=\; \bar{\phi}_{s,a}(\theta) \;\overset{\text{def}}{=}\; \phi_{s,a} - \textstyle\sum_{a' \in {\cal A}} \pi_{s,a'}(\theta)\phi_{s,a'} \; = \; \phi_{s,a} - \mathbb{E}_{a'\sim\pi_s(\theta)}\left[\phi_{s,a'}\right] , \end{align}\tag{13}\] where \(\bar{\phi}_{s,a}(\theta)\) are called centered features vectors.

In practice, we cannot minimize \(L_A\) exactly; instead, a sample-based regression problem is solved to obtain an approximate solution \(w^{(k)}\). This leads to the following inexact NPG update rule: \[\begin{align} \label{eq:NPG-cfa-approx} \theta^{(k+1)} \; = \; \theta^{(k)} - \eta_k w^{(k)}, \qquad w^{(k)} \approx \mathop{\mathrm{argmin}}_{w} L_A\bigl(w, \theta^{(k)}, \bar{d}^{\,(k)}\bigr). \end{align}\tag{14}\]

The inexact NPG updates require samples of unbiased estimates of \(A_{s,a}(\theta)\), the corresponding sampling procedure is given in Algorithm [alg:sampler95A], and a sample-based regression solver to minimize \(L_A\) is given in Algorithm [alg:NPG-SGD] in the Appendix.

Alternatively, as proposed by [21], we can define the compatible function approximation error as \[\begin{align} \label{eq:compatible-Q} L_Q(w, \theta, \zeta) \; \overset{\text{def}}{=}\; \mathbb{E}_{(s,a) \sim \zeta}\left[\bigl( w^\top \phi_{s,a} - Q_{s, a}(\theta)\bigr)^2\right] \end{align}\tag{15}\] and use it to derive a variant of the inexact NPG update called Q-NPG: \[\begin{align} \label{eq:Q-NPG-cfa-approx} \theta^{(k+1)} \; = \; \theta^{(k)} - \eta_k w^{(k)}, \qquad w^{(k)} \approx \mathop{\mathrm{argmin}}_{w} L_Q\bigl(w, \theta^{(k)}, \bar{d}^{\,(k)}\bigr). \end{align}\tag{16}\]

For Q-NPG, the sampling procedure for estimating \(Q_{s,a}(\theta)\) is given in Algorithm [alg:sampler95Q] and a sample-based regression solver for \(w^{(k)}\) is proposed in Algorithm [alg:Q-NPG-SGD] in the Appendix.

The sampling procedure and the regression solver of NPG are less efficient than those of Q-NPG. Indeed, the sampling procedure for \(A_{s,a}(\theta)\) in Algorithm [alg:sampler95A] not only estimates \(Q_{s,a}(\theta)\), but also requires an additional estimation of \(V_s(\theta)\), and thus doubles the amount of samples as compared to Algorithm [alg:sampler95Q]. Furthermore, the stochastic gradient estimator of \(L_Q\) in Algorithm [alg:Q-NPG-SGD] only computes on a single action of the feature map \(\phi_{s,a}\). Whereas the one of \(L_A\) in Algorithm [alg:NPG-SGD] computes on the centered feature map \(\bar{\phi}_{s,a}(\theta)\) defined in 13 , which needs to go through the entire action space, thus is \(|{\cal A}|\) times more expensive to run. See Appendix 9 for more details.

Following [21], we consider slightly different variants of NPG and Q-NPG, where \(\bar{d}^{\,(k)}\) in 14 and 16 is replaced by a more general state-action visitation distribution \(\tilde{d}^{\,(k)} = \tilde{d}^{\,\pi(\theta^{(k)})}(\nu)\) defined in 5 with \(\nu\in\Delta({\cal S}\times{\cal A})\). The advantage of using \(\tilde{d}^{\,(k)}\) is that it allows better exploration than \(\bar{d}^{\,(k)}\) as \(\nu\) can be chosen to be independent to the policy \(\pi(\theta^{(k)})\). For example, it can be seen from 6 that the lower bound of \(\tilde{d}^{\,\pi}\) is independent to \(\pi\), which is not the case for \(\bar{d}^{\,\pi}\). This property is crucial in the forthcoming convergence analysis.

3.1 Formulation as Inexact Policy Mirror Descent↩︎

Given an approximate solution \(w^{(k)}\) for minimizing \(L_Q\bigl(w, \theta^{(k)}, \tilde{d}^{\,(k)}\bigr)\), the Q-NPG update rule \(\theta^{(k+1)} \; = \; \theta^{(k)} - \eta_k w^{(k)}\), when plugged in the log-linear parametrization 7 , results in a new policy \[\pi^{(k+1)}_{s,a} \;=\; \frac{1}{Z^{(k)}_s} \pi^{(k)}_{s,a} \exp\left(-\eta_k\,\phi_{s,a}^T w^{(k)}\right), \qquad \forall\,(s,a)\in{\cal S}\times{\cal A},\] where \(\pi^{(k)}\) is a shorthand for \(\pi_{s,a}(\theta^{(k)})\) and \(Z^{(k)}_s\) is a normalization factor to ensure \(\sum_{a\in{\cal A}}\pi^{(k+1)}_{s,a}=1\), for each \(s\in{\cal S}\). We note that the above \(\pi^{(k+1)}\) can also be obtained by a mirror descent update: \[\begin{align} \pi_s^{(k+1)} &= \arg\min_{p \in \Delta({\cal A})} \left\{ \eta_k\left< \Phi_sw^{(k)}, p\right> + D(p, \pi_s^{(k)}) \right\}, \quad \forall s \in {\cal S}, \label{eq:PMDinexactQ} \end{align}\tag{17}\] where \(\Phi_s \in \mathbb{R}^{|{\cal A}| \times m}\) is a matrix with rows \((\phi_{s,a})^\top\in\mathbb{R}^m\) for \(a\in{\cal A}\), and \(D(p,q)\) denotes the Kullback-Leibler (KL) divergence between two distributions \(p,q\in\Delta({\cal A})\), i.e., \[D(p,q)\overset{\text{def}}{=}\sum_{a\in {\cal A}}p_a\log\left(\frac{p_a}{q_a}\right).\] A derivation of 17 is provided in Appendix 8 (Lemma 2) for completeness.

If we replace \(\Phi_sw^{(k)}\) in 17 by the vector \(\big[Q_{s,a}(\pi^{(k)})\big]_{a\in{\cal A}} \in \mathbb{R}^{|{\cal A}|}\), then it becomes the policy mirror descent (PMD) method in the tabular setting studied by, for example, [24], [29] and [23]. In fact, the update rule 17 can be viewed as an inexact PMD method where \(Q_s(\pi^{(k)})\) is linearly approximated by \(\Phi_sw^{(k)}\) through compatible function approximation 15 . Besides, with the replacement of \(\Phi_sw^{(k)}\) by \(\big[Q_{s,a}(\pi^{(k)})\big]_{a\in{\cal A}}\), 17 can also be viewed as a special case of the mirror descent value iteration for the regularized MDP studied by [31]–[33]. Similarly, we can write the inexact NPG update rule as \[\begin{align} \pi_s^{(k+1)} &= \arg\min_{p \in \Delta({\cal A})} \left\{ \eta_k\left< \bar{\Phi}_s^{(k)}w^{(k)}, p\right> + D(p, \pi_s^{(k)}) \right\}, \quad \forall s \in {\cal S}, \label{eq:PMDinexact} \end{align}\tag{18}\] where \(w^{(k)}\) is an approximate solution for minimizing \(L_A\bigl(w,\theta^{(k)}, \tilde{d}^{\,(k)}\bigr)\) defined in 11 , and \(\bar{\Phi}_s^{(k)}\in\mathbb{R}^{|{\cal A}|\times m}\) is a matrix whose rows consist of the centered feature maps \(\big(\bar{\phi}_{s,a}(\theta^{(k)})\big)^\top\), as defined in 13 .

Reformulating Q-NPG and NPG into the mirror descent forms 17 and 18 , respectively, allows us to adapt the analysis of PMD method developed in [23] to obtain sharp convergence rates. In particular, we show that with an increasing step size \(\eta_k\propto\gamma^k\), both NPG and Q-NPG with log-linear policy parametrization converge linearly up to an error floor determined by the quality of the compatible function approximation.

4 Analysis of Q-NPG with Log-Linear Policies↩︎

In this section, we provide the convergence analysis of the following inexact Q-NPG method \[\begin{align} \label{eq:Q-NPG-nu} \theta^{(k+1)} \; = \; \theta^{(k)} - \eta_k w^{(k)}, \qquad w^{(k)} \approx \mathop{\mathrm{argmin}}_{w} L_Q\bigl(w, \theta^{(k)}, \tilde{d}^{\,(k)}\bigr), \end{align}\tag{19}\] where \(\tilde{d}^{\,(k)}\) is shorthand for \(\tilde{d}^{\,\pi(\theta^{(k)})}(\nu)\) and \(\nu\in\Delta({\cal S}\times{\cal A})\) is an arbitrary state-action distribution that does not depend on \(\rho\). The exact minimizer is denoted as \(w_\star^{(k)} \in \mathop{\mathrm{argmin}}_{w} L_Q\bigl(w, \theta^{(k)}, \tilde{d}^{\,(k)}\bigr)\).

Following [21], the compatible function approximation error can be decomposed as \[L_Q\bigl(w^{(k)},\theta^{(k)},\tilde{d}^{\,(k)}\bigr) \;=\; \underbrace{L_Q\bigl(w^{(k)},\theta^{(k)},\tilde{d}^{\,(k)}\bigr)-L_Q\bigl(w_\star^{(k)},\theta^{(k)},\tilde{d}^{\,(k)}\bigr)}_{\small Statistical error (excess risk)} +\underbrace{L_Q\bigl(w_\star^{(k)},\theta^{(k)},\tilde{d}^{\,(k)}\bigr).}_{\small Approximation error}\] The statistical error measures how accurate is our solution to the regression problem, i.e., how good \(w^{(k)}\) is compared with \(w_\star^{(k)}\). The approximation error measures the best possible solution for approximating \(Q_{s,a}(\theta^{(k)})\) using \(\phi_{s,a}\) as features in the regression problem (modeling error). One way to proceed with the analysis is to assume that both the statistical error and the approximation error are bounded for all iterations, which is the approach we take in Section 4.2 and is also the approach we take later in Section 5 for the analysis of the NPG method.

However, in Section 4.1, we first take an alternative approach proposed by [21], where the assumption of bounded approximation error is replaced by a bounded transfer error. The transfer error refers to \(L_Q\bigl(w_\star^{(k)},\theta^{(k)},\tilde{d}^{\,*}\bigr)\), where the iteration-dependent visitation distribution \(\tilde{d}^{\,(k)}\) is shifted to a fixed one \(\tilde{d}^{\,*}\) (defined in Section 4.1).

These two approaches require different additional assumptions and result in slightly different convergence rates. Here we first state the common assumption on the bounded statistical error.

By solving the regression problem with sampling based approaches, we can expect \(\epsilon_\mathrm{stat} = {\cal O}(1/\sqrt{T})\) [21] or \(\epsilon_\mathrm{stat} = {\cal O}(1/T)\) (see Corollary 1) where \(T\) is the number of iterations used to find the approximate solution \(w^{(k)}\).

4.1 Analysis with Bounded Transfer Error↩︎

Here we introduce some additional notation. For any state distributions \(p,q \in \Delta({\cal S})\), we define the distribution mismatch coefficient of \(p\) relative to \(q\) as \[\left\| \frac{p}{q} \right\|_\infty \overset{\text{def}}{=}\max_{s \in {\cal S}} \frac{p_s}{q_s}.\] Let \(\pi^*\) be an arbitrary comparator policy, which is not necessarily an optimal policy and does not need to belong to the log-linear policy class. Fix a state distribution \(\rho\in\Delta({\cal S})\). We denote \(d^{\pi^*}(\rho)\) as \(d^*\) and \(d^{\pi(\theta^{(k)})}(\rho)\) as \(d^{(k)}\), and define the following distribution mismatch coefficients: \[\begin{align} \label{eq:vartheta} \vartheta_k \; \overset{\text{def}}{=}\; \left\| \frac{d^*}{d^{(k)}} \right\|_{\infty} \; \overset{\eqref{eq:d}}{\leq} \; \frac{1}{1-\gamma} \left\| \frac{d^*}{\rho} \right\|_{\infty} \quad \quadand\quad \quad \vartheta_\rho \; \overset{\text{def}}{=}\; \frac{1}{1-\gamma} \left\| \frac{d^*}{\rho} \right\|_{\infty} \; \geq \; \frac{1}{1-\gamma}. \end{align}\tag{20}\] Thus, for all \(k \geq 0\), we have \(\vartheta_k \leq \vartheta_\rho\). We assume that \(\vartheta_\rho < \infty\), which is the case, for example, if \(\rho_s>0\) for all \(s\in{\cal S}\). This is commonly used in the literature on policy gradient methods [34], [35] and the NPG convergence analysis [23], [36]. We further relax this condition in Section 5.2.

We also introduce a weighted KL divergence given by \[D_k^* \; \overset{\text{def}}{=}\; \mathbb{E}_{s \sim d^*}\left[D(\pi_s^*, \pi_s^{(k)})\right] .\] If we choose the uniform initial policy, i.e., \(\pi^{(0)}_{s,a} = 1/|{\cal A}|\) for all \((s,a) \in {\cal S}\times {\cal A}\) (or \(\theta^{(0)} = 0\)), then \(D^*_0 \leq \log|{\cal A}|\) for all \(\rho \in \Delta({\cal S})\) and for any \(\pi^* \in \Delta({\cal A})^{{\cal S}}\). The choice of the step size will directly depend on \(D^*_0\) in our forthcoming linear convergence results.

Given a state distribution \(\rho\) and a comparator policy \(\pi^*\), we define a state-action measure \(\tilde{d}^{\,*}\) as \[\label{eq:d-rho-unif} \tilde{d}^{\,*}_{s,a} \; \overset{\text{def}}{=}\; d^*_{s}\cdotUnif_{{\cal A}}(a) \; \overset{\text{def}}{=}\; \frac{d^*_{s}}{|{\cal A}|},\tag{21}\] and use it to express the transfer error as \(L_Q\bigl(w_\star^{(k)}, \theta^{(k)}, \tilde{d}^{\,*}\bigr)\).

The \(\epsilon_\mathrm{bias}\) is often referred to as the transfer error, since it is the error due to replacing the relevant distribution \(\tilde{d}^{(k)}\) by \(\tilde{d}^{\,*}\). This transfer error bound characterizes how well the Q-values can be linearly approximated by the feature maps \(\phi_{s,a}\). It can be shown that \(\epsilon_\mathrm{bias} = 0\) when \(\pi^{(k)}\) is the softmax tabular policy [21] or the MDP has a certain low-rank structure [37]–[40]. As mentioned in [21], when \(\epsilon_\mathrm{bias} = 0\), one can easily verify that the NPG and Q-NPG are equivalent algorithms. For rich neural parametrizations, \(\epsilon_\mathrm{bias}\) can be made small [35].

The next assumption concerns the relative condition number between two covariance matrices of \(\phi_{s,a}\) defined under different state-action distributions.

The \(\kappa_\nu\) is referred to as the relative condition number, since the ratio is between two different matrix induced norm. Notice that Assumption 3 benefits from the use of \(\nu\). In fact, it is shown in [21] that \(\kappa_\nu\) can be reasonably small (e.g., \(\kappa_\nu \leq m\) is always possible) and independent to the size of the state space by controlling \(\nu\).

Our analysis also needs the following assumption, which does not appear in [21].

The concentrability coefficient is studied in the analysis of approximate dynamic programming algorithms [41]–[43]. It measures how much \(\rho\) can get amplified in \(k\) steps as compared to the reference distribution \(d_{s}^*\). Let \(\rho_{\min} = \min_{s \in {\cal S}}\rho_s\). A sufficient condition for Assumption 4 to hold is that \(\rho_{\min} > 0.\) Indeed, \[\begin{align} \label{eq:rho} \sqrt{\mathbb{E}_{s \sim d^*}\left[\biggl(\frac{d_{s}^{(k)}}{d_{s}^*}\biggr)^{\!\!2}\right] } \leq \left\| \frac{d^{(k)}}{d^*} \right\|_{\infty} \overset{\eqref{eq:d}}{\leq} \frac{1}{1-\gamma} \left\| \frac{d^{(k)}}{\rho} \right\|_\infty \leq \frac{1}{(1-\gamma)\rho_{\min}}. \end{align}\tag{22}\] In reality, \(\sqrt{C_\rho}\) can be much smaller than the pessimistic bound shown above. This is especially the case if we choose \(\pi^*\) to be the optimal policy and \(d^{(k)} \rightarrow d^*\). We further replace \(C_\rho\) by \(C_\nu\) defined in Section 4.2 that is independent to \(\rho\) and thus is more easily satisfied.

Now we present our first main result.

The main differences between our Theorem 1 and Theorem 20 of [21], which is their corresponding result on the inexact Q-NPG method, are summarized as follows.

• The convergence rate of [21] is \({\cal O}(1/\sqrt{k})\) up to an error floor determined by \(\epsilon_\mathrm{stat}\) and \(\epsilon_\mathrm{bias}\). We have linear convergence up to an error floor that also depends on \(\epsilon_\mathrm{stat}\) and \(\epsilon_\mathrm{bias}\). However, the magnitude of our error floor is worse (larger) by a factor of \(\vartheta_\rho\sqrt{C_\rho}\), due to the concentrability and the distribution mismatch coefficients used in our proof. A very pessimistic bound on this factor is as large as \(|{\cal S}|^2/(1-\gamma)^2\).

• In terms of required conditions, both results use Assumptions 1, 2 and 3. [21] further assume that the norms of the feature maps \(\phi_{s,a}\) are uniformly bounded and \(w^{(k)}\) has a bounded norm (e.g., obtained by a projected stochastic gradient descent). Due to different analysis techniques referred next, we avoid such boundedness assumptions but rely on the concentrability coefficient \(C_\rho\) defined in Assumption 4.

• [21] uses a diminishing step size \(\eta \propto 1/\sqrt{k}\) where \(k\) is the total number of iterations, but we use a geometrically increasing step size \(\eta_k\propto\gamma^{k}\) for all \(k \geq 0\). This discrepancy reflects the different analysis techniques adopted. The key analysis tool in [21] is a NPG Regret Lemma (their Lemma 34) which relies on the smoothness of the functions \(\log\pi_{s,a}(\theta)\) (thus the boundedness of \(\|\phi_{s,a}\|\)) and the boundedness of \(\|w^{(k)}\|\), and thus the classical \({\cal O}(1/\sqrt{k})\) diminishing step size in the optimization literature. Our analysis exploits the three-point descent lemma [44] and the performance difference lemma [45], without reliance on smoothness parameters. As a consequence, we can take advantage of exponentially growing step sizes and avoid assuming the boundedness of \(\|\phi_{s,a}\|\) or \(\|w^{(k)}\|\).

Using increasing step size induces fast linear convergence. The reason is that Q-NPG behaves more and more like policy iteration with large enough step size. Intuitively, when \(\eta_k \rightarrow \infty\) and \(Q_s(\theta^{(k)})\) is equal to the linear approximation \(\Phi_sw^{(k)}\) which is the case of the linear MDP [40] with \(\epsilon_\mathrm{bias} = 0\), 17 becomes \[\pi_s^{(k+1)} = \arg\min_{p \in \Delta({\cal A})} \left\{ \left< Q_s(\theta^{(k)}), p\right>\right\}, \quad \forall s \in {\cal S},\] which is exactly the classical Policy Iteration method [1], [3]. Thus, Q-NPG can match the linear convergence rate of policy iteration in this case. We refer to [23] for more discussion on the connection with policy iteration.

As a by product, we also obtain a sublinear \({\cal O}(1/k)\) convergence result while using arbitrary constant step size.

A deviation from the setting of Theorem 1 is that here we require \(\pi^*\) to be an optimal policy⁷. Compared to Theorem 20 in [21], our convergence rate is also sublinear, but with an improved convergence rate of \({\cal O}(1/k)\), as opposed to \({\cal O}(1/\sqrt{k})\). Moreover, they use a diminishing step size of order \({\cal O}(1/\sqrt{k})\) while our constant step size is unconstrained.

4.2 Analysis with Bounded Approximation Error↩︎

In this section, instead of assuming bounded transfer error, we provide a convergence analysis based on the usual notion of approximation error and a weaker concentrability coefficient.

As mentioned in [21], Assumption 5 is stronger than Assumption 2 (bounded transfer error). Indeed, \[L_Q\bigl(w_\star^{(k)}, \theta^{(k)}, \tilde{d}^{\,*}\bigr) \;\leq\; \left\| \frac{\tilde{d}^{\,*}}{\tilde{d}^{\,(k)}} \right\|_\infty L_Q\bigl(w_\star^{(k)}, \theta^{(k)}, \tilde{d}^{\,(k)}\bigr) \;\overset{\eqref{eq:d}}{\leq}\; \frac{1}{1-\gamma} \left\| \frac{\tilde{d}^{\,*}}{\nu} \right\|_{\infty} L_Q\bigl(w_\star^{(k)}, \theta^{(k)}, \tilde{d}^{\,(k)}\bigr).\]

Since we are free to choose \(\nu\) independently of \(\rho\), we can choose \(\nu_{s,a} > 0\) for all \((s,a) \in {\cal S}\times {\cal A}\) for Assumption 6 to hold. Indeed, with \(\nu_{\min}\) denoting \(\min_{(s,a)\in{\cal S}\times{\cal A}}\nu_{s,a}\), we have

\[\begin{align} \label{eq:nu} \sqrt{\mathbb{E}_{(s,a) \sim \tilde{d}^{\,(k)}}\left[\biggl(\frac{h_{s,a}^{(k)}}{\tilde{d}_{s,a}^{\,(k)}}\biggr)^{\!\!2}\right] } \; \leq \; \max_{(s,a) \in {\cal S}\times {\cal A}} \frac{h_{s,a}^{(k)}}{\tilde{d}_{s,a}^{\,(k)}} \; \overset{\eqref{eq:d}}{\leq} \; \frac{1}{(1-\gamma)\nu_{\min}}, \end{align}\tag{23}\] where the upper bound can be smaller than that in 22 if \(\rho_{\min}\) is smaller than \(\nu_{\min}\).

Compared to Theorem 1, while the approximation error assumption is stronger than the transfer error assumption, we do not require the assumption on relative condition number \(\kappa_\nu\) and the error floor does not depends on \(\kappa_\nu\) nor explicitly on \(|{\cal A}|\). Besides, we can always choose \(\nu\) so that the concentrability coefficient \(C_\nu\) is finite even if \(C_\rho\) is unbounded. However, it is not clear if Theorem 3 is better than Theorem 1.

4.3 Sample complexity of Q-NPG↩︎

The previous results focus on iteration complexity, i.e., number of iterations used for updating \(\theta\). Here we establish the sample complexity results, i.e., total number of samples of single-step interaction with the environment, of a sample-based Q-NPG method (Algorithm [alg:q-npg] in Appendix 9). Combined with a simple stochastic gradient descent (SGD) solver, Q-NPG-SGD in Algorithm [alg:Q-NPG-SGD], the following corollary shows that Algorithm [alg:q-npg] converges globally by further assuming that the feature map is bounded and has non-singular covariance matrix.

In Q-NPG-SGD, each trajectory has the expected length \(1/(1-\gamma)\) (see Lemma 4). Consequently, with \(K = {\cal O}(\log(1/\epsilon)\log(1/(1-\gamma)))\) and \(T = {\cal O}\bigl(\frac{1}{(1-\gamma)^6\epsilon^2}\bigr)\), Q-NPG requires \(K * T / (1-\gamma) = \tilde{{\cal O}} \bigl(\frac{1}{(1-\gamma)^7\epsilon^2}\bigr)\) samples such that \(\mathbb{E}\left[V_\rho(\pi^{(K)})\right] - V_\rho(\pi^*) \leq {\cal O}(\epsilon) + {\cal O}\bigl(\frac{\sqrt{\epsilon_\mathrm{approx}}}{1-\gamma}\bigr)\). The \(\tilde{{\cal O}}(1/\epsilon^2)\) sample complexity matches with the one of value-based algorithms such as Q-learning [46] and also matches with the one of model-based algorithms such as policy iteration [1], [47] .

Compared to [21] for the sampled based Q-NPG Algorithm [alg:q-npg], their sample complexity is \({\cal O}\bigl(\frac{1}{(1-\gamma)^{11}\epsilon^6}\bigr)\) with \(K = \frac{1}{(1-\gamma)^2\epsilon^2}\) and \(T = \frac{1}{(1-\gamma)^8\epsilon^4}\). Despite the improvement on the convergence rate for \(K\), they use the optimization results of [48] to obtain \(\epsilon_\mathrm{stat} = {\cal O}(1/\sqrt{T})\), while we use the one of [49] (see Theorem 6 as well) to establish faster \(\epsilon_\mathrm{stat} = {\cal O}(1/T)\)⁸. With further regularity ?? , [21] mentioned that \(\epsilon_\mathrm{stat} = {\cal O}(1/T)\) can also be achieved through [50]. In addition, [21] use the projected SGD method and require that the stochastic gradient is bounded which is incorrectly verified in their proof ⁹. In contrast, to apply Theorem 6, we avoid proving the boundedness of the stochastic gradient. Alternatively, we require a different condition ?? . A proof sketch of our corollary is provided in Appendix 10.5 for more details.

As for the condition ?? , it is shown in [36] that with \(\nu\) chosen as uniform distribution over \({\cal S}\times {\cal A}\) and \(\phi_{s,a} \sim {\cal N}(0, {\boldsymbol{I}}_m)\) sampled as Gaussian random features, ?? is guaranteed with high probability. More generally, with \(m \ll |{\cal S}||{\cal A}|\), it is easy to find \(m\) linearly independent \(\phi_{s,a}\) among all \(|{\cal S}||{\cal A}|\) features such that the covariance matrix \(\Sigma_\nu\) has full rank. This is a common requirement for linear function approximation settings [51]–[53].

5 Analysis of NPG with Log-Linear Policies↩︎

We now return to the convergence analysis of the inexact NPG method, specifically, \[\begin{align} \label{eq:NPG-nu} \theta^{(k+1)} \; = \; \theta^{(k)} - \eta_k w^{(k)}, \qquad w^{(k)} \approx \mathop{\mathrm{argmin}}_{w} L_A\bigl(w, \theta^{(k)}, \tilde{d}^{\,(k)}\bigr), \end{align}\tag{24}\] where \(\tilde{d}^{\,(k)}\) is a shorthand for \(\tilde{d}^{\,\pi(\theta^{(k)})}(\nu)\) and \(\nu\in\Delta({\cal S}\times{\cal A})\) is an arbitrary state-action distribution that does not depend on \(\rho\). Again, let \(w_\star^{(k)} \in \mathop{\mathrm{argmin}}_w L_A\bigl(w, \theta^{(k)}, \tilde{d}^{\,(k)}\bigr)\) denote the minimizer. Our analysis of NPG is analogous to that of Q-NPG shown in the previous section. That is, we again exploit the inexact PMD formulation 18 and use techniques developed in [23].

The set of assumptions we use for NPG is analogous to the assumptions used in Section 4.2. In particular, we assume a bounded approximation error instead of transfer error (c.f., Assumption 2) in minimizing \(L_A\) and do not need the assumption on relative condition number.

Under the above assumptions, we have the following result.

Compared to Theorem 3, our convergence guarantees for Q-NPG and NPG have the same convergence rate and error floor, and the same type of assumptions.

Now we compare Theorem 4 with Theorem 29 in [21] for the NPG analysis. The main differences are similar to those for Q-NPG as summarized right after Theorem 1: Their convergence rate is sublinear while ours is linear; they assume uniformly bounded \(\phi_{s,a}\) and \(w^{(k)}\) while we require bounded concentrability coefficient \(C_\nu\) due to different proof techniques; they use diminishing step sizes and we use geometrically increasing ones. Moreover, Theorem 4 requires bounded approximation error, which is a stronger assumption than the bounded transfer error used by their Theorem 29, but we do not need the assumption on bounded relative condition number.

We note that the bounded relative condition number required by [21] must hold for the covariance matrix of \(\bar{\phi}^{(k)}_{s,a}\) for all \(k\geq 0\) because the centered feature maps \(\bar{\phi}^{(k)}_{s,a}\) depends on the iterates \(\theta^{(k)}\). This is in contrast to our Assumption 3, where we use a single fixed covariance matrix for Q-NPG that is independent to the iterates, as defined in ?? .

In addition, the inequalities in ?? only involve half of the state-action visitation distributions listed in ?? , i.e., the first and the fourth terms. From 23 , the upper bound of \(C_\nu\) is obtained only through 6 , which is a property of \(\tilde{d}^{\,\pi}\) itself for all policy \(\pi \in \Delta({\cal A})^{{\cal S}}\). Thus, \(C_\nu\) in ?? can share the same upper bound in 23 independent to the use of the algorithm Q-NPG or NPG. Consequently, our concentrability coefficient assumption is weaker than Assumption 2 in [36] which studies the linear convergence of NPG with entropy regularization for the log-linear policy class. The reason is that the bound on \(C_\nu\) in 23 does not depend on the policies throughout the iterations thanks to the use of \(\tilde{d}^{\,(k)}\) instead of \(\bar{d}^{\,(k)}\) (see Remark 1 as well). See also Section 5.2 for a thorough discussion on the concentrability coefficient \(C_\nu\).

Similar to Theorem 2, we also obtain a sublinear rate for NPG while using an unconstrained constant step size.

Compared to Theorem 2, again here we require \(\pi^*\) to be an optimal policy for the same reason as indicated in Footnote 7. Furthermore our sublinear convergence guarantees for both Q-NPG and NPG are the same. Compared to Theorem 29 in [21], the main differences are also similar to those for Q-NPG as summarized right after Theorem 2: our convergence rate improves from \({\cal O}(1/\sqrt{k})\) to \({\cal O}(1/k)\); they use a diminishing step size of order \({\cal O}(1/\sqrt{k})\) while we can take any constant step size we want.

Despite the difference of using \(\tilde{d}^{\,(k)}\) instead of \(\bar{d}^{\,(k)}\) for the compatible function approximation \(L_A(w^{(k)}, \theta^{(k)}, \tilde{d}^{\,(k)})\), notice that same sublinear convergence rate \({\cal O}(1/k)\) is established by [54] for NPG with constant step size, while their step size is bounded by the inverse of a smoothness constant and they further require that the feature map is bounded and the Fisher information matrix 10 is strictly lower bounded for all parameters \(\theta \in \mathbb{R}^m\) (see this condition later in ?? ). With such additional conditions, we are able to provide a \({\cal O}(\frac{1}{(1-\gamma)^5\epsilon^2})\) sample complexity result of NPG next.

5.1 Sample complexity of NPG↩︎

Combined with a regression solver, NPG-SGD in Algorithm [alg:NPG-SGD], which uses a slight modification of Q-NPG-SGD for the unbiased gradient estimates of \(L_A\), we consider a sampled-based NPG Algorithm [alg:npg] proposed in Appendix 9 and show its sample complexity result in the following corollary.

Now we compare our Corollary 2 with Corollary 33 in [21], which is their corresponding sample complexity results for NPG. The main differences between Corollary 2 and Corollary 33 in [21] are similar to those for Q-NPG as summarized right after Corollary 1: Their sample complexity is \({\cal O}\bigl(\frac{1}{(1-\gamma)^{11}\epsilon^6}\bigr)\) while ours is \(\tilde{{\cal O}} \bigl(\frac{1}{(1-\gamma)^{5}\epsilon^2}\bigr)\); they consider a projection step for the iterates and incorrectly bound the stochastic gradient due to a similar error indicated in Footnote 9 (and see Appendix 11.4 for more details), while we assume Fisher-non-degeneracy ?? . Compared to Corollary 1, the sample complexities for both Q-NPG and NPG are the same. The assumption ?? on the Fisher information matrix is much stronger than ?? , as ?? is independent to the iterates. However, despite the difference of using \(\nu\) instead of \(\rho\), the Fisher-non-degeneracy ?? is commonly used in the optimization literature [55]–[57] and in the RL literature [54], [58], [59]. It characterizes that the Fisher information matrix behaves well as a preconditioner in the NPG update 9 . Indeed, ?? is directly assumed to be positive definite in the pioneering NPG work [9] and in the follow-up works on natural actor-critic algorithms [60], [61]. It is satisfied by a wide families of policies, including the Gaussian policy [62]–[64] and certain neural policy with log-linear policy as a special case. We refer to [54] and [58] for more discussions on the Fisher-non-degenerate setting.

To prove Corollary 2, our approach is inspired from the proof of the sample complexity analysis of [54]. That is, we require the Fisher-non-degeneracy ?? and apply Theorem 6 to the minimization of function \(L_A(w, \theta, \tilde{d}^{\,\theta})\) without relying on the boundedness of the stochastic gradient. A proof sketch is provided in Appendix 11.4. Compared to their result, they obtain worse \({\cal O}\bigl(\frac{1}{(1-\gamma)^{7}\epsilon^3}\bigr)\) sample complexity for NPG due to a slower \({\cal O}(1/k)\) convergence rate.

5.2 Discussion on the Distribution Mismatch Coefficients and the Concentrability Coefficients↩︎

We have already mentioned in the comparison with [21] right after Theorem 1 that, although we have linear convergence rates, the magnitude of our error floor is worse (larger) by a factor of \(\vartheta_\rho\sqrt{C_\rho}\) (\(\vartheta_\rho\sqrt{C_\nu}\) for Theorem 3 and 4), due to the concentrability \(C_\rho\) and the distribution mismatch coefficients \(\vartheta_\rho\) used in our proof. Such difference comes from different nature of the proof techniques. Here the distribution mismatch coefficients \(\vartheta_\rho\) and the concentrability coefficients \(C_\rho\) and \(C_\nu\) are potentially large in our convergence theories. We give extensive discussions on them, respectively.

Distribution mismatch coefficients \(\vartheta_\rho\).

Our distribution mismatch coefficient \(\vartheta_\rho\) in 20 is the same as the one in [23]. It contains both an upper bound and a lower bound. The linear convergence rate in our theories is \(1 - \frac{1}{\vartheta_\rho} > 0\). Thus, the smaller \(\vartheta_\rho\) is, the faster the resulting linear convergence rate. The best linear convergence rate is achieved when \(\vartheta_\rho\) achieves its lower bound. Here our analysis is general that it includes all the distribution mismatch coefficient \(\vartheta_\rho\) induced by any target state distribution \(\rho\). Our results generalizes and sometimes also improves with respect to prior results.

A very pessimistic and trivial upper bound on \(\vartheta_\rho\) is \[\vartheta_\rho \leq \frac{1}{(1-\gamma)\rho_{\min}}.\] However, if the target state distribution \(\rho \in \Delta({\cal S})\) does not have full support, i.e., \(\rho_s=0\) for some \(s\in{\cal S}\), then \(\vartheta_\rho\) might be infinite from this upper bound. [23] just assumes that \(\vartheta_\rho\) is finite. We further propose a solution to this particular issue. Indeed, if \(\rho\) does not have full support, consider \(\pi^*\) as an optimal policy. We can always convert the convergence guarantees for some state distribution \(\rho' \in \Delta({\cal S})\) with full support, i.e., \(\rho'_s>0\) for all \(s\in{\cal S}\) as follows: \[\begin{align} V_\rho(\pi^{(k)}) - V_\rho(\pi^*) & = \sum_{s\in{\cal S}}\rho_s\left(V_s(\pi^{(k)})-V_s(\pi^*)\right) = \sum_{s\in{\cal S}}\frac{\rho_s}{\rho'_s}\rho'_s\left(V_s(\pi^{(k)})-V_s(\pi^*)\right) \\ & \leq \left\|\frac{\rho}{\rho'}\right\|_\infty \sum_{s\in{\cal S}}\rho'_s\left(V_s(\pi^{(k)})-V_s(\pi^*)\right) = \left\|\frac{\rho}{\rho'}\right\|_\infty \left(V_{\rho'}(\pi^{(k)})-V_{\rho'}(\pi^*)\right). \end{align}\] Then we only need convergence guarantees of \(V_{\rho'}(\pi^{(k)})-V_{\rho'}(\pi^*)\) for arbitrary \(\rho'\) obtained from all our convergence analysis above. In this case, the linear convergence rate depends on \[\vartheta_{\rho'} \overset{\text{def}}{=}\frac{1}{1-\gamma} \left\| \frac{d^{\pi^*}(\rho')}{\rho'} \right\|_\infty < \infty.\]

Equation 20 provides the lower bound \(\frac{1}{1-\gamma}\) for \(\vartheta_\rho\). Such lower bound can be achieved when the target state distribution \(\rho\) satisfies that \(\rho = d^{\pi^*}(\rho)\) where \(\pi^*\) is an optimal policy. The advantage of this case is that, not only it implies the best linear convergence rate, more importantly, the fast linear convergence rate is known to be \(\gamma\). So we know the convergence rate explicitly without any estimation, even though the optimal policy or the policy iterates are unknown before training. Hence, we know when to stop running the algorithm. [29] only considers the case when \(\rho = d^{\pi^*}(\rho)\) and we are able to recover the same linear convergence rate \(\gamma\) in their result.

Furthermore, the convergence performance \(V_\rho(\pi^{(k)}) - V_\rho(\pi^*)\) depends on the target state distribution \(\rho\). If the optimal policy \(\pi^*\) is independent to the target state distribution \(\rho\) which is usually the case in RL problems, then we are always allowed to fix \(\rho = d^{\pi^*}(\rho)\) for the analysis without knowing \(\rho\) and \(\pi^*\) and derive this best linear convergence performance with rate \(\gamma\), because we use the initial state-action distribution \(\nu\) in training which is independent to \(\rho\).

Finally, from 20 , if \(d^{(k)}\) converges to \(d^*\), then \(\vartheta_k\) converges to 1. This might imply superlinear convergence results as Section 4.3 in [23]. In this case, the notion of the distribution mismatch coefficients \(\vartheta_\rho\) no longer exists for the superlinear convergence analysis. In other words, it is no longer concerned.

Concentrability coefficients \(C_\nu\).

The issue of having (potentially large) concentrability coefficients is unavoidable in all the fast linear convergence analysis of the inexact NPG that we are aware of, including even the tabular setting (e.g., [29] and [23]) and the log-linear policy setting ([36], [27] and ours).

First, in the fast linear convergence analysis of inexact NPG, the concentrability coefficients appear from the errors, including the statistical error and the approximation error. Thus, one way to avoid having the concentrability coefficients appear is to consider the exact NPG in the tabular setting (See Theorem 10 in [23]). Because the tabular setting makes no approximation error and the exact NPG makes no statistical error. We consider the inexact NPG with the log-linear policy. Consequently, we have the concentrability coefficients multiplied by both the statistical error \(\epsilon_\mathrm{stat}\) and the approximation error (\(\epsilon_\mathrm{bias}\) in Assumption 2 or \(\epsilon_\mathrm{approx}\) in Assumption 5 and 8).

To remove the concentrability coefficients, one has to make strong assumptions on the errors with the \(L_\infty\) supremum norm. In the tabular setting, [29] and [23] assume that \(\|\widehat{Q}(\pi) - Q(\pi)\|_\infty \leq \epsilon_\mathrm{stat}\). The cons of such strong assumption requires high sample complexity and is explained in details in Section 6.1 below. In the log-linear policy setting, [27] assume that \(\|Q_s(\theta^{(k)}) - \Phi w_\star^{(k)}\|_\infty \leq \epsilon_\mathrm{bias}\) for the approximation error, which is a very strong assumption in the function approximation regime. Due to the supremum norm, \(\epsilon_\mathrm{bias}\) is unlikely to be small, especially for large action spaces. Under this strong assumption, [29], [23] and [27] are able to eliminate the concentrability coefficients. To avoid assuming such strong assumptions, [36] and our paper consider the expected \(L_2\) errors in the log-linear policy setting, which are much weaker assumptions, especially much more reasonable for the approximation error \(\epsilon_\mathrm{bias}\) compared to the one in [27]. The tradeoff is that, the concentrability coefficients can not be eliminated in this case both in [36] and our results.

Furthermore, as mentioned right after Theorem 4, under the expected error assumptions (Assumption 7 and 8), our concentrability coefficient \(C_\nu\) is better presented than the one in Assumption 2 in [36] in the sense that it is independent to the policies throughout the iterations thanks to the use of \(\tilde{d}^{\,(k)}\) instead of \(\bar{d}^{\,(k)}\) (which is mentioned in Remark 1 as well) and is controllable to be finite by \(\nu\), while the one in [36] depends on the iterates, thus is unknown and is not guaranteed to be finite.

Finally, like the distribution mismatch coefficient, the upper bound of \(C_\nu\) in 23 is very pessimistic. By the definition of \(C_\nu\) in ?? , one can expect that \(C_\nu\) is closed to \(1\), when \(\pi^{(k)}\) and \(\pi^{(k+1)}\) converge to \(\pi^*\) with \(\pi^*\) the optimal policy.

So our concentrability coefficient \(C_\nu\) is the “best” one among all concentrability coefficients in the sense that, it takes the weakest assumptions on errors compared to [29], [23] and [27], it does not impose any restrictions on the MDP dynamics compared to [36] and it can be controlled to be finite by \(\nu\) when other concentrability coefficients are infinite [65].

It is still an open question whether we can obtain fast linear convergence results of the inexact NPG in the log-linear policy setting, with small error floor and a much improved concentrability coefficient, e.g., as the same magnitude as the one in [21].

6 Related work↩︎

6.1 Technical Contribution and Novelty Compared to [23]↩︎

Our technical novelty compared to [23] is summarized as follows.

• Our linear convergence results (i.e., Theorem 1, 3 and 4) are not direct applications of Theorem 10 in [23]. Indeed, [23] establishes the connection between NPG and a specific form of policy mirror descent (PMD) with the use of the weighted Bregman divergence for the tabular setting, while we show that this connection can also be established for the function approximation setting via the compatible function approximation framework 11 . We also modify the PMD framework of [23] with the linear approximation of the advantage function in 18 , inspired from the compatible function approximation framework. Thus, the approaches of deriving the PMD form update are different. Without this work of using the compatible function approximation framework to bridge NPG and PMD, it was not clear at all that the analysis of [23] could be extended in the log-linear policy setting. So our work is the first step of showing that the proof techniques used in [23] can be extended in function approximation regime. In fact, the extension is highly nontrivial and requires significant innovation (see details below). As for future work, one can extend our work to other function approximation setting through a similar compatible function approximation framework. See Section 7 for more details about the future work.

• Besides, our linear convergence results only consider the inexact NPG update. Compared to Theorem 14 in [23], which is their corresponding result on the inexact PMD method, we improve their analysis by making much weaker assumptions on the accuracy of the estimation \(Q(\pi)\). [23] requires an \(L_\infty\) supremum norm bound on the estimation error of \(Q\), i.e., \(\|\widehat{Q}(\pi) - Q(\pi)\|_\infty \leq \epsilon_\mathrm{stat}\), whereas our convergence guarantee depends on the expected \(L_2\) error of the estimate, i.e., Assumption 1 and 7. For instance, Assumption 1 from equation 44 can be written as \(\mathbb{E}\left[(\phi_{s,a}^\top w^{(k)} - \phi_{s,a}^\top w_\star^{(k)})^2\right] \leq \epsilon_\mathrm{stat}\), which can be interpreted as \(\mathbb{E}\left[(\widehat{Q}(\pi) - Q(\pi))^2\right] \leq \epsilon_\mathrm{stat}\) under the linear approximation setting. The techniques for handling \(L_\infty\) and \(L_2\) errors are very different. Not only our assumption is weaker, it also benefits from the sample complexity analysis that we explain next.

• Consequently, when considering the sample complexity results we derived for sample-based (Q)-NPG in Corollary 1 and 2, the difference between our work and Theorem 16 in [23], which corresponds to their sample complexity results, is even more significant. Corollary 1 with Algorithm Q-NPG-SGD (Algorithm [alg:Q-NPG-SGD]) satisfies Assumption 1 with a number of samples that depends only on the feature dimension \(m\) of \(\phi\) and does not depend on the cardinality of state space \(|\mathcal{S}|\) or action space \(|\mathcal{A}|\). In contrast, the assumption \(\|\widehat{Q}(\pi) - Q(\pi)\|_\infty \leq \epsilon_\mathrm{stat}\) with the \(L_\infty\) norm in [23] causes the sample complexity to depend on \(|\mathcal{S}||\mathcal{A}|\).

  Furthermore, [23] uses a Monte-Carlo approach with multiple independent rollouts per iteration, while our sample-based (Q)-NPG uses one single rollout (Algorithm [alg:sampler95Q] and [alg:sampler95A]) combined with regression solvers; [23] derives a high probability sample complexity result, while we derive the convergence of the optimality gap \(\mathbb{E}\left[V_\rho(\pi^{(K)})\right] - V_\rho(\pi^*)\) which can guarantee that the variance of \(V_\rho(\pi^{(K)})\) converges to zero. Thus, our sample-based algorithms had not been considered in [23] and our proofs of Corollary 1 and 2 require a different approach.

  In particular, our sample complexity analysis regarding to the policy evaluation is novel. Although our sample-based algorithms had been considered previously in [21] and [54], none of their analysis on the sample complexity was correct. Indeed, [21] required the boundedness of the stochastic gradient estimator, which might not hold as we extensively discussed in Appendix 10.5. We fixed this by showing that \(\mathbb{E}\left[\widehat{Q}_{s,a}(\theta)^2\right]\) is bounded. See Appendix 10.5 for all the subtleties, including a proof sketch of Corollary 1. [54] also incorrectly used an inequality where the random variables are correlated. See the detailed explanation (Footnote 11) in Appendix 11.4. We fixed this error with a careful conditional expectation argument. Please refer to Appendix 11.4 for all the details, including a proof sketch of Corollary 2. These dimensions are where an important part of the technical work was done. Therefore, outside of the tabular setting, and considering NPG methods that make use of a regression solver, our complexity analysis is currently the only analysis that is entirely correct that we are aware of.

• Finally we not only extend the work of [23] to NPG for log-linear policy, but also consider the Q-NPG method and establish its linear convergence analysis. This is a method that is unique to log-linear policy and again had not been considered in [23].

6.2 Finite-Time Analysis of the Natural Policy Gradient↩︎

6.2.0.1 NPG for the softmax tabular policies.

For the softmax tabular policies, [24] show that the unregularized NPG has a \({\cal O}(1/\sqrt{k})\) convergence rate and the regularized NPG has a faster \({\cal O}(1/k)\) convergence rate by using a decaying step size. [21] improve the convergence rate of the unregularized NPG to \({\cal O}(1/k)\) with constant step sizes. Further, [66] also achieves \({\cal O}(1/k)\) convergence rate for the off-policy natural actor-critic (NAC), and a slower sublinear result is established by [67] for the two-time-scale NAC.

By using the entropy regularization, [28] achieve a linear convergence rate for NPG. A similar linear convergence result has been obtained by rewriting the NPG update under the PMD framework with the Kullback–Leibler (KL) divergence [29] or with a more general convex regularizer [30]. Such approach is also applied in the averaged MDP setting to achieve linear convergence for NPG [68]. However, adding regularization might induce bias for the solution. Thus, [29] considers exponentially diminishing regularization to guarantee unbiased solution. Furthermore, by considering both the KL divergence and the diminishing entropy regularization, [69] establish the linear convergence rate not only for the optimality gap but also for the policy. That is, the policy will converge to the fixed high entropy optimal policy. Consequently, [69] show a local super-linear convergence of both the policy and optimality gap, as discussed in [23].

Recently, [70], [22], [71] and [23] show that regularization is unnecessary for obtaining linear convergence, and it suffices to use appropriate step sizes for NPG. In particular, [70] propose to use an exact line search for the step size (Theorem 1 (a)) or to choose an adaptive step size (Theorem 1 (c)). Similar adaptive step size is proposed by [22], [71]. Notice that such adaptive step size requires complete knowledge about the environmental model. Instead, a sufficiently large step size might be enough. In this paper, we extend the results of [23] from the tabular setting to the log-linear policies, using non-adaptive geometrically increasing step size and obtaining a linear convergence rate for NPG without regularization.

6.2.0.2 NPG with function approximation.

In the function approximation regime, there have been many works investigating the convergence rate of the NPG or NAC algorithms from different perspectives. [35] establish the \({\cal O}(1/\sqrt{k})\) convergence rate for two-layer neural NAC with a projection step. The sublinear convergence results are also established by [72] and [73] for the linear MDP [40]. [21] obtain the same \({\cal O}(1/\sqrt{k})\) convergence rate for the smooth policies with projections. This was later improved to \({\cal O}(1/k)\) by [54] by replacing the projection step with a strong regularity condition on the Fisher information matrix, and it was also improved to \({\cal O}(1/k)\) by [74] with NAC under Markovian sampling. The same \({\cal O}(1/k)\) convergence rate is established for log-linear policies by [75] when considering the off-policy NAC.

With entropy regularization and a projection step, [36] obtain a linear convergence for log-linear policies. Same entropy regularization and a projection step are applied by [76] for the neural NAC to improve the \({\cal O}(1/\sqrt{k})\) convergence rate of [35] to \({\cal O}(1/k)\). In contrast, we show that by using a simple geometrically increasing step size, fast linear convergence can be achieved for log-linear policies without any additional regularization nor a projection step. We notice that [27]¹⁰ also uses increasing step size and achieves linear convergence for log-linear policies without regularization. The main differences between our result and Theorem 3.4 in [27] are fourfold. First, they rely on the contraction property of the generalized Bellman operator, while we consider the PMD analysis approach. So the proof techniques are completely different. Second, their parameter update results in the off-policy multi-step temporal difference learning, whereas we require to solve a linear regression problem to minimize the function approximation error. Third, their step size still depends on the iterates which is thus an adaptive step size and is proportional to the total number of iterations \(K\), while ours is independent to the iterates nor to \(K\). Finally, their assumption on the modeling error requires an \(L_\infty\) supremum norm, i.e., \(\|Q_s(\theta^{(k)}) - \Phi w_\star^{(k)}\|_\infty \leq \epsilon_\mathrm{bias}\) for all states \(s\) of the state space, our convergence guarantee depends on the expected error (e.g., Assumption 2, 5 or 8) which is a much weaker assumption. After publication of our results, we are aware of the concurrent work of [77]. They only analyze the Q-NPG method and achieve similar linear convergence results as our Theorem 1. In particular, their result in Theorem 4.7 has a better concentrability coefficient compared to our Theorem 1. However, their Assumption 4.6 assumes that the relative condition number upper bounds a time-varying ratio which depends on the iterates, while our Assumption 3 is independent to the iterates, as defined in ?? . Furthermore, they only consider the case when the initial state distribution is the same as the target state distribution, while our analysis generalizes with any target state distribution, which is extensively discussed on the distribution mismatch coefficients in Section 5.2. See Table [tab:full32picture] a complete overview of NPG in the function approximation regime.

6.2.0.3 Fast linear convergence of other policy gradient methods.

Different to the PMD analysis approach, by leveraging a gradient dominance property [78], [79], fast linear convergence results have also been established for the PG methods under different settings, such as the linear quadratic control problems [80] and the exact PG method with softmax tabular policy and entropy regularization [59], [81]. Such gradient domination property is widely explored by [82] to identify more general structural MDP settings. Linear convergence of PG can also be obtained through exact line search [70] or by exploiting non-uniform smoothness [83].

Alternatively, by considering a general strongly-concave utility function of the state-action occupancy measure and by exploiting the hidden convexity of the problem, [34] also achieve the linear convergence of a variational PG method. When the object is relaxed to a general concave utility function, [84] still achieve the linear convergence by leveraging the hidden convexity of the problem and by adding variance reduction to the PG method.

7 Conclusion and Discussion↩︎

In this paper, for both NPG and Q-NPG methods applied for the log-linear policy, we establish the linear convergence results with non-adaptive geometrically increasing step sizes and the sublinear convergence results with arbitrary large constant step sizes. Our work is the first step of showing that the policy mirror descent proof techniques used in [23] can be extended in function approximation regime.

The main focus of this paper was the theoretical analysis of NPG method. The results we have obtained open up several experimental questions related to parameter settings for NPG and Q-NPG. We leave such questions as an important future work to further support our theoretical findings.

An interesting application from our work is to investigate the sample complexity of natural actor-critic with our PMD analysis. Indeed, our paper obtains \(w^{(k)}\) by a regression solver. One can also use temporal difference (TD) learning (e.g., [27], [36], [85]) with Markovian sampling to achieve similar \(O(1/\epsilon^2)\) sample complexity result. The performance analysis of TD learning will be expressed for \(\epsilon_\mathrm{stat}\), which directly imply the total sample complexity results through our theorems.

One natural question is whether we can extend our analysis to the general policy classes. Here we provide one possible way. It can be extended by using a similar compatible function approximation framework. Concretely, consider the parameterized policy \[\pi_{s,a}(\theta) = \frac{\exp(f_{s,a}(\theta))}{\sum_{a' \in \mathcal{A}} \exp(f_{s,a'}(\theta))},\] where \(f_{s,a}(\theta)\) is parameterized by \(\theta \in \mathbb{R}^m\) and is differential. As [21] mentioned, the gradient can be written as \[\nabla_\theta \log \pi_{s,a}(\theta) = g_{s,a}(\theta) \quadwhere\quad g_{s,a}(\theta) = \nabla_\theta f_{s,a}(\theta) - \mathbb{E}_{a' \sim \pi_s(\theta)} \left[ \nabla_\theta f_{s,a'}(\theta) \right].\] The NPG update is equivalent to the following compatible function approximation framework \[\theta^{(k+1)} = \theta^{(k)} - \eta_k w_\star^{(k)}, \quad \quad w_\star^{(k)} \in \arg\min_w \mathbb{E}_{(s,a) \sim \bar{d}^{\,(k)}}\left[\left(A_{s,a}(\theta^{(k)}) - w^\top g_{s,a}(\theta^{(k)})\right)^2\right].\] As [77] mentioned, if we assume that for all \((s,a) \in {\cal S}\times {\cal A}\), function \(f(\theta)\) satisfies \[f_{s,a}(\theta^{(k+1)}) = f_{s,a}(\theta^{(k)}) - \eta_k (w_\star^{(k)})^\top g_{s,a}(\theta^{(k)}),\] which is the case for the log-linear policies, then one can easily verify that the NPG update resulted in a new policy is also equivalent to the policy mirror descent update \[\pi_s^{(k+1)} = \arg\min_{p \in \Delta(\mathcal{A})} \left\{ \eta_k\left<G_s^{(k)}w^{(k)}, p\right> + D(p, \pi_s^{(k)}) \right\}, \quad \forall s \in \mathcal{S},\] where \(G_s^{(k)} \in \mathbb{R}^{|\mathcal{A}| \times m}\) is a matrix with rows \((g_{s,a}(\theta^{(k)}))^\top\in\mathbb{R}^{1 \times m}\) for \(a\in\mathcal{A}\). Consequently, one can extend our work naturally in this general setting to derive linear convergence analysis for NPG.

Perhaps one can consider the exponential tilting, a generalization of Softmax to more general probability distributions. Another interesting venue of investigation is to consider the generalized linear model instead of linear function approximation for the \(Q\) function and the advantage function.

One interesting open question is that is there a way to increase stepsize when the discount factor is unknown. So far the PMD proof techniques used in [23], [29] and ours require that the discount factor is known. Perhaps the work of [68] can help to find a way to increase stepsize when the discount factor is unknown. Indeed, [68] consider the averaged MDP setting. So there is no discount factor. They achieve linear convergence for NPG by increasing the stepsize with some regularization parameters. It will be interesting to investigate if the way of increasing stepsize in [68] can be applied in our setting.

Acknowledgment↩︎

We gratefully acknowledge Daniel Russo who pointed out that we did not cite properly [70] in the literature review in the previous version.

We also acknowledge the helpful discussion with Yanli Liu on the sample complexity analysis of both Q-NPG and NPG.

We would also like to thank the anonymous reviewers for their helpful comments.

Here we provide the missing proofs from the main paper and some additional noteworthy observations made in the main paper.

8 Standard Reinforcement Learning Results↩︎

In this section, we prove the standard reinforcement learning results used in our main paper, including the NPG updates written through the compatible function approximation 12 and the NPG updates formalized as policy mirror descent (17 and 18 ). Then, we prove the performance difference lemma [45], which is the first key ingredient for our PMD analysis. The three-point descent lemma (Lemma 11) is the second key ingredient for our PMD analysis.

9 Algorithms↩︎

9.1 NPG and Q-NPG Algorithm↩︎

Algorithm [alg:npg] combined with the sampling procedure (Algorithm [alg:sampler95A]) and the averaged SGD procedure, called NPG-SGD (Algorithm [alg:NPG-SGD]), provide the sample-based NPG methods.

Similarly, Algorithm [alg:q-npg] combined with the sampling procedure (Algorithm [alg:sampler95Q]) and the averaged SGD procedure, called Q-NPG-SGD (Algorithm [alg:Q-NPG-SGD]), provide the sample-based Q-NPG methods.

9.2 Sampling Procedures↩︎

In practice, we cannot compute the true minimizer \(w_\star^{(k)}\) of the regression problem in either 24 or 19 , since computing the expectation \(L_A\) or \(L_Q\) requires averaging over all state-action pairs \((s, a) \sim \tilde{d}^{\,(k)}\) and averaging over all trajectories \((s_0, a_0, c_0, s_1, \cdots)\) to compute the values of \(Q_{s,a}^{(k)}\) and \(A_{s,a}^{(k)}\). So instead, we provide a sampler which is able to obtain unbiased estimates of \(Q_{s,a}(\theta)\) (or \(A_{s,a}(\theta)\)) with \((s, a) \sim \tilde{d}^{\,\theta}(\nu)\) for any \(\pi(\theta)\).

To solve 19 , we sample \((s,a) \sim \tilde{d}^{\,(k)}\) and \(\widehat{Q}_{s, a}^{(k)}\) by a standard rollout, formalized in Algorithm [alg:sampler95Q]. This sampling procedure is commonly used, for example in [21].

It is straightforward to verify that \((s_h, a_h)\) and \(\widehat{Q}_{s_h, a_h}(\theta)\) obtained in Algorithm [alg:sampler95Q] are unbiased for any \(\pi(\theta)\). The expected length of the trajectory is \(\frac{1}{1-\gamma}\). We provide its proof here for completeness.

Similar to Algorithm [alg:sampler95Q], to solve 24 , we sample \((s,a) \sim \tilde{d}^{\,(k)}\) by the same procedure and estimate \(\widehat{A}_{s, a}^{\,(k)}\) with a slight modification, namely Algorithm [alg:sampler95A] [21].

Notice that the sampling procedure for estimating \(Q_{s,a}(\theta)\) in Algorithm [alg:sampler95Q] is simpler than that for estimating \(A_{s,a}(\theta)\) in Algorithm [alg:sampler95A], since Algorithm [alg:sampler95A] requires an additional estimation of \(V_s(\theta)\) and thus doubles the number of samples to estimate \(A_{s,a}(\theta)\). As in Lemma 4, we verify in the following lemma that the output \((s_h,a_h)\) is sampled from the distribution \(\tilde{d}^{\,\theta}\) and \(\widehat{A}_{s_h, a_h}(\theta)\) in Algorithm [alg:sampler95A] is an unbiased estimator of \(A_{s_h, a_h}(\theta)\) for all policy \(\pi(\theta)\).

9.3 SGD Procedures for Solving the Regression Problems of NPG and Q-NPG↩︎

Once we obtain the sampled \((s,a)\) and \(\widehat{A}_{s,a}(\theta^{(k)})\) from Algorithm [alg:sampler95A], we can apply the averaged SGD algorithm as in [49] to solve the regression problem 24 of NPG for every iteration \(k\).

Here we suppress the superscript \((k)\). For any parameter \(\theta \in \mathbb{R}^m\), recall the compatible function approximation \(L_A\) in 24 \[L_A(w, \theta, \tilde{d}^{\,\theta}) = \mathbb{E}_{(s,a) \sim \tilde{d}^{\,\theta}}\left[\left(w^\top \bar{\phi}_{s,a}(\theta) - A_{s,a}(\theta)\right)^2\right] .\] With the output \((s,a) \sim \tilde{d}^{\,\theta}\) and \(\widehat{A}_{s,a}(\theta)\) from Algorithm [alg:sampler95A] (here we suppress the subscript \(h\)), we compute the stochastic gradient estimator of the function \(L_A\) in 24 by \[\begin{align} \label{eq:NPG-SGD} \widehat{\nabla}_w L_A(w, \theta, \tilde{d}^{\,\theta}) \overset{\text{def}}{=}2\left(w^\top \bar{\phi}_{s,a}(\theta) - \widehat{A}_{s,a}(\theta)\right)\bar{\phi}_{s,a}(\theta). \end{align}\tag{28}\] Next, we show that 28 is an unbiased gradient estimator of the loss function \(L_A\).

Since 28 is unbiased shown in Lemma 6, we can use it for the averaged SGD algorithm to minimize \(L_A\), called NPG-SGD in Algorithm [alg:NPG-SGD] [21].

Similar to Algorithm [alg:NPG-SGD], once we obtain the sampled \((s,a)\) and \(\widehat{Q}_{s,a}(\theta)\) from Algorithm [alg:sampler95Q], we can apply the averaged SGD algorithm to solve 19 of Q-NPG.

Recall the compatible function approximation \(L_Q\) in 19 \[L_Q(w, \theta, \tilde{d}^{\,\theta}) = \mathbb{E}_{(s,a) \sim \tilde{d}^{\,\theta}}\left[\left(w^\top \phi_{s,a} - Q_{s,a}(\theta)\right)^2\right] .\] With the output \((s,a) \sim \tilde{d}^{\,\theta}\) and \(\widehat{Q}_{s,a}(\theta)\) from Algorithm [alg:sampler95Q], we compute the stochastic gradient estimator of the function \(L_Q\) in 19 by \[\begin{align} \label{eq:Q-NPG-SGD} \widehat{\nabla}_w L_Q(w, \theta, \tilde{d}^{\,\theta}) \overset{\text{def}}{=}2\left(w^\top \phi_{s,a} - \widehat{Q}_{s,a}(\theta)\right)\phi_{s,a}, \end{align}\tag{31}\] and use it for the averaged SGD algorithm to minimize \(L_Q\), called Q-NPG-SGD in Algorithm [alg:Q-NPG-SGD] [21]. Compared to 28 , the cost of computing 31 is \(|{\cal A}|\) times cheaper than that of computing 31 . Indeed, to compute 31 , we only need one single action for \(\phi_{s,a}\), while to compute 28 , one needs to go through all the actions to compute \(\bar{\phi}_{s,a}(\theta)\). Thus, the computational cost of Q-NPG-SGD is \(|{\cal A}|\) times cheaper than that of NPG-SGD.

The estimator \(\widehat{\nabla}_w L_Q(w, \theta, \tilde{d}^{\,\theta})\) is also unbiased following the similar argument of the proof of Lemma 6. We formalize this in the following and omit the proof.

10 Proof of Section 4↩︎

Throughout this section and the next, we use the shorthand \(V_\rho^{(k)}\) for \(V_\rho(\theta^{(k)})\) and similarly, \(Q_{s,a}^{(k)}\) for \(Q_{s,a}(\theta^{(k)})\) and \(A_{s,a}^{(k)}\) for \(A_{s,a}(\theta^{(k)})\). We also use the shorthand \(Q_{s}^{(k)}\) for the vector \(\left[Q_{s,a}^{(k)}\right]_{a\in{\cal A}} \in \mathbb{R}^{|{\cal A}|}\) and \(A_{s}^{(k)}\) for the vector \(\left[A_{s,a}^{(k)}\right]_{a\in{\cal A}} \in \mathbb{R}^{|{\cal A}|}\).

We first provide the one step analysis of the Q-NPG update, which will be helpful for proving Theorem 1, 2 and 3.

10.1 The One Step Q-NPG Lemma↩︎

The following one step analysis of Q-NPG is based on the mirror descent approach of [23].

Consequently, the convergence analysis of Q-NPG (Theorem 1, 2 and 3) will be obtained by upper bounding the absolute values of \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=.5pt] (char) {1};}\), \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=.5pt] (char) {2};}\), \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=.5pt] (char) {3};}\), \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=.5pt] (char) {4};}\), \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=.5pt] (char) {a};}\), \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=.5pt] (char) {b};}\), \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=.5pt] (char) {c};}\), \(\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=.5pt] (char) {d};}\) in ?? with different set of assumptions (assumptions in Theorem 1 or assumptions in Theorem 3) and with different step size scheme (geometrically increasing step size for Theorem 1 and 3 or constant step size for Theorem 2).

10.2 Proof of Theorem 1↩︎

10.3 Proof of Theorem 2↩︎

10.4 Proof of Theorem 3↩︎

10.5 Proof of Corollary 1↩︎

In order to better understand our proof, we first identify an issue appeared in the sample complexity analysis of Q-NPG in [21]. [21] adopts the optimization results of [48] where the stochastic gradient \(\widehat{\nabla} L_Q(w, \theta, \tilde{d}^{\,\theta})\) in 31 needs to be bounded. However, although they consider a projection step for the iterate \(w_t\) and assume that the feature map \(\phi_{s,a}\) is bounded, \(\widehat{\nabla} L_Q(w, \theta, \tilde{d}^{\,\theta})\) is still not guaranteed to be bounded. Indeed, recall the stochastic gradient of the function \(L_Q\) in 31 \[\widehat{\nabla}_w L_Q(w, \theta, \tilde{d}^{\,\theta}) = 2\left(w^\top \phi_{s,a} - \widehat{Q}_{s,a}(\theta)\right)\phi_{s,a}.\] They incorrectly use the argument that \(w, \phi_{s,a}\) and \(\widehat{Q}_{s,a}(\theta)\) are bounded to imply that \(\left\| \widehat{\nabla}_w L_Q(w, \theta, \tilde{d}^{\,\theta}) \right\|\) is bounded. In fact, \(\widehat{Q}_{s,a}(\theta)\) can be unbounded even though \(\mathbb{E}\left[\widehat{Q}_{s,a}(\theta)\right] = Q_{s,a}(\theta) \in \left[0, \frac{1}{1-\gamma}\right]\) is bounded. To see this, we can rewrite \(\widehat{Q}_{s,a}(\theta)\) from 27 as \[\widehat{Q}_{s,a}(\theta) = \sum_{t=0}^Hc(s_t,a_t),\] with \((s_0,a_0) = (s,a) \sim \tilde{d}^{\,\theta}\) and \(H\) is the length of the sampled trajectory for estimating \(Q_{s,a}(\theta)\) in Algorithm [alg:sampler95Q]. From Algorithm [alg:sampler95Q] and from the proof of Lemma 4, we know that the probability of \(H = k + 1\) is that \[\Pr(H=k+1) = (1-\gamma)\gamma^k.\] So, with exponentially decreasing low probability, \(H\) can be unbounded. Consequently, \(|\widehat{Q}_{s,a}(\theta)|\) upper bounded by \(H\) is not guaranteed to be bounded.

10.5.0.1 Proof sketch.

Instead, we adopt the optimization results of [49] (see also Theorem 6), which does not require the boundedness of the stochastic gradient. However, in our following proof, we can verify that \(\mathbb{E}\left[\widehat{Q}_{s,a}(\theta)^2\right]\) is bounded even though \(\widehat{Q}_{s,a}(\theta)\) is unbounded. As to verify the condition [itm:variance] in Theorem 6 in our proof, i.e., the covariance of the stochastic gradient at the optimum is upper bounded by the covariance of the feature map up to a finite constant, we use a conditional expectation argument to separate the correlated random variables \(\widehat{Q}_{s,a}(\theta)\) and \(\phi_{s,a}\) with \((s,a) \sim \tilde{d}^{\,\theta}\) appeared in the stochastic gradient.

11 Proof of Section 5↩︎

11.1 The One Step NPG Lemma↩︎

To prove Theorem 4 and 5, we start from providing the one step analysis of the NPG update.

11.2 Proof of Theorem 4↩︎

11.3 Proof of Theorem 5↩︎

11.4 Proof of Corollary 2↩︎

There is a similar remark for the proof of Corollary 2 to the one right before the proof of Corollary 1 in Appendix 10.5. We notice that there is the same error occurred for the proof of NPG sample complexity analysis in [21]. Recall the stochastic gradient of \(L_A\) in 28 \[\widehat{\nabla}_w L_A(w, \theta, \tilde{d}^{\,\theta}) = 2\left(w^\top \bar{\phi}_{s,a}(\theta) - \widehat{A}_{s,a}(\theta)\right)\bar{\phi}_{s,a}(\theta).\] It turns out that \(\widehat{\nabla}_w L_A(w, \theta, \tilde{d}^{\,\theta})\) is unbounded, since the estimate \(\widehat{A}_{s,a}(\theta)\) of \(A_{s,a}(\theta)\) can be unbounded due to the unbounded length of the trajectory sampled in the sampling procedure, Algorithm [alg:sampler95A]. Thus, [21] incorrectly verify \(\widehat{\nabla} L_A(w, \theta, \tilde{d}^{\,\theta})\) bounded by claiming that \(\widehat{A}_{s,a}(\theta)\) is bounded by \(\frac{2}{1-\gamma}\).

11.4.0.1 Proof sketch.

Despite the difference of using either \(\tilde{d}^{\,\theta}\) or \(\bar{d}^{\,\theta}\) in the loss function \(L_A\), we use the same assumptions of [54], i.e., the Fisher-non-degeneracy ?? and the boundedness of the feature map, and verify all the conditions of Theorem 6 without relying on the boundedness of the stochastic gradient. In particular, similar to the proof of Corollary 1, we verify that \(\mathbb{E}\bigl[\widehat{A}_{s,a}(\theta)^2\bigr]\) is bounded even though \(\widehat{A}_{s,a}(\theta)\) is unbounded. To verify the condition [itm:variance] in Theorem 6 in our proof, we use the same conditional expectation argument as in the proof of Corollary 1 to separate the correlated random variables \(\widehat{A}_{s,a}(\theta)\) and \(\bar{\phi}_{s,a}(\theta)\) with \((s,a) \sim \tilde{d}^{\,\theta}\) appeared in the stochastic gradient. Thanks to this argument, we fix a flaw in the previous proof of [54] ¹¹.

12 Standard Optimization Results↩︎

In this section, we present the standard optimization results from [23], [49], [86] used in our proofs.

First, we present the closed form update of mirror descent with KL divergence on the simplex. We provide its proof for the completeness.

Now we present the three-point descent lemma on proximal optimization with Bregman divergences, which is another key ingredient for our PMD analysis. Following [23], we adopt a slight variation of Lemma 3.2 in [44]. First, we need some technical conditions.

Under the above conditions, we have the following result. We also provide its proof for self-containment. ([23] does not provide a formal proof.)

Finally, we use the following linear regression analysis for the proof of our sample complexity results, i.e., Corollary 1 and 2.

References↩︎