On the Second-Order Convergence of Biased Policy Gradient Algorithms

In the standard reinforcement learning framework, an agent interacts with an environment according to some policy, which dictates the best actions to take given the state of the environment. The ultimate goal of the agent is to adopt a policy that maximizes some measure of cumulative reward. To efficiently search for the optimal policy, policy gradient methods optimize a policy parameter $\theta$ through updates that approximate the gradient of the objective function with respect to $\theta$. These algorithms can be fast and flexible, and under mild assumptions, they share convergence properties with mainstream gradient descent algorithms.

The policy gradient can be estimated by way of the policy gradient theorem, which enables the straightforward application of existing techniques in gradient-based optimization towards understanding PG convergence. The theorem provides a formula for the exact gradient of the objective function as the expectation of the state-action value function over the discounted state-action measure (Sutton et al., 1999). In practice, the gradient is estimated through two common approaches: the “vanilla” approach, where the gradient is approximated via Monte-Carlo sampling, or the “actor-critic” approach, where the policy parameter $\theta$, called the “actor parameter,” is updated simultaneously alongside a “critic parameter” $w$, which parametrizes the state-action value function. The critic parameter is typically updated via bootstrapping temporal difference methods such as TD(0), although the actor updates may also be bootstrapped (Konda & Tsitsiklis, 1999; Bhatnagar et al., 2009).

Although it is well-established that policy gradient converges to first-order stationary points where the norm of the gradient is approximately zero (Sutton et al., 1999; Yuan et al., 2022; Agarwal et al., 2020), it is of interest whether policy gradient algorithms yield second-order stationary points (local maxima) as opposed to saddle points. This is because the function landscape of RL problems can be highly nonconvex and features suboptimal stationary points even in very simple examples (Agarwal et al., 2020; Bhandari & Russo, 2019; Zhang et al., 2020). We can utilize seminal results in nonconvex optimization that show that stochastic gradient descent can leverage randomness to escape saddle points either with added noise (Ge et al., 2015; Jin et al., 2019) or as long as there is a component of noise in the direction of curvature (Daneshmand et al., 2018; Vlaski & Sayed, 2022).

However, unlike stochastic gradient descent, practical implementations of policy gradient are frequently biased. For the discounted infinite-horizon reward objective function, the vanilla policy gradient estimator is biased due to truncation of sampled trajectory horizons (Yuan et al., 2022). In addition, actor-critic algorithms introduce a second source of bias in the critic’s approximation of the value function. This therefore requires novel techniques for controlling and bounding the bias. In comparison, existing works on second-order convergence of policy gradient only consider unbiased gradient estimators; for example, (Zhang et al., 2020) require artificially constructing an unbiased gradient estimator via Q-sampling as well as periodic step size enlargement, and (Yang et al., 2021) assume the gradient estimator is unbiased. Both works also only consider the vanilla policy gradient algorithm and not the actor-critic scheme.

In this paper, we address the aforementioned gap by showing that biased policy gradient methods, including both vanilla policy gradient and actor-critic methods, can escape saddle points. Borrowing from the analyses of (Vlaski & Sayed, 2022) regarding unbiased stochastic gradient descent, we tackle the biased policy gradient setting by showing that the components of the bias can be sufficiently controlled to yield second-order convergence guarantees.

Related Work

Escaping Saddle Points. As referenced earlier, escaping saddle points has become a central research topic in nonconvex optimization in the last few years, with natural extensions to the policy gradient setting. In addition to the seminal works showing the second-order convergence of gradient descent and stochastic gradient descent (Ge et al., 2015; Jin et al., 2019, 2017; Daneshmand et al., 2018; Vlaski & Sayed, 2022), an additional body of work has focused on second-order methods that use Hessian information to arrive at second-order stationary points faster. Some examples of reinforcement learning approaches in this direction include (Shen et al., 2019; Wang et al., 2022; Khorasani et al., 2023). However, these works only consider unbiased gradient estimators. For an in-depth comparison of sample complexities, see Appendix A.2.

Global Convergence. Separate from our line of work, there are several “global convergence” results for policy gradient and actor-critic algorithms that ensure convergence to a global optimum for specific policy parametrization or function structure. For instance, global convergence is established for the following settings: tabular or tabular softmax policy parametrization with exact gradients (Agarwal et al., 2020; Bhandari & Russo, 2021), objective functions that satisfy the gradient domination property (Bhandari & Russo, 2019), linear quadratic and nearly linear-quadratic control systems (Yang et al., 2019; Han et al., 2022), and overparametrized neural networks (Wang et al., 2020; Fu et al., 2020). The premise of “global convergence” also requires some assumption that the proposed policy parametrization can approximate the optimal policy with arbitrary precision, i.e., the optimal policy lies within the policy class. In comparison, our second-order convergence guarantees pertain to finding the best policy parameter $\theta$ under a generic policy parametrization, for policy gradient algorithms with noisy and biased updates. For an in-depth discussion of global convergence rates, see Appendix A.1.

Vanilla Policy Gradient. In this work, we refer to policy gradient algorithms that estimate the gradient via Monte-Carlo sampling of trajectories as “vanilla policy gradient.” Early formulas include REINFORCE (Williams, 2004) as well as GPOMDP (Baxter & Bartlett, 2001), a version of REINFORCE that enjoys reduced variance (Peters & Schaal, 2008) by employing the ”reward-to-go” trick. Our work pertains to the GPOMDP estimator. Both REINFORCE and GPOMDP are unbiased estimators of objectives with deterministic, fixed horizons, but they are biased estimators of the infinite-horizon discounted reward due to truncation (Yuan et al., 2022).

Actor-critic Algorithms. The asymptotic convergence of actor-critic algorithms was first established in (Konda & Tsitsiklis, 1999) for gradient actor updates and bootstrapped critic updates, and in (Bhatnagar et al., 2009) for bootstrapped actor and critic updates. Since then, finite-time convergence has been established for a variety of actor-critic frameworks, although to the best of our knowledge no second-order convergence result exists. In this work we consider double-loop actor-critic algorithms where the critic parameter undergoes TD(0) updates in the inner loop and the actor parameter undergoes gradient updates in the outer loop. Several works have shown first-order convergence of these algorithms with various additional settings; (Yang et al., 2018) consider i.i.d sampling in the actor and the critic, (Qiu et al., 2021) consider i.i.d. policy samples and critic sampling from a stationary Markov chain, and (Xu et al., 2020b) study mini-batch Markovian sampling for controlling the bias error. Separately, (Wang et al., 2020) establish global convergence for double-loop algorithms where the actor and critic functions are compatible overparametrized neural networks. In comparison, we consider linear critic parametrization and arbitrary actor parametrization with Markovian sampling, and we do not require the Markov chain to be stationary.

Recently, two-timescale (Xu et al., 2020a; Wu et al., 2020) and single-timescale (Fu et al., 2020; Olshevsky & Gharesifard, 2023) actor-critic algorithms have shown a slight performance advantage over double-loop algorithms, although existing works still only analyze their first-order or global convergence under specific function parametrizations, while we focus on second-order convergence.

Temporal Difference Algorithms. Actor-critic algorithms typically feature some bootstrapping element; in particular, we consider actor-critic algorithms where the critic updates via TD(0) learning. The finite-time convergence of TD(0) has been established recently under independent and identically distributed sampling (Dalal et al., 2018; Kumar et al., 2019) as well as under Markovian sampling (Liu & Olshevsky, 2020; Bhandari et al., 2018). The latter is more relevant to the RL setting; however, both (Bhandari et al., 2018) and (Liu & Olshevsky, 2020) assume the Markov chain begins in the stationary distribution, which is unrealistic for practical implementations such as in actor-critic algorithms.

Our Contributions

Our contributions are as follows.

• •

  We provide the first finite-time convergence analysis of vanilla policy gradient with biased gradient estimator to $\epsilon$-second-order stationary points. This results in a sample complexity of $\tilde{O}(\epsilon^{-6.5})$ iterations, where $\tilde{O}(\cdot)$ hides logarithmic dependencies. We note that this is a stronger result than $\tilde{O}(\epsilon^{-9})$ from (Zhang et al., 2020) and a weaker result than $\tilde{O}(\epsilon^{-4.5})$ from (Yang et al., 2021), both of which only analyze unbiased gradient estimators.

• •

  We provide the first finite-time convergence analysis of an actor-critic policy gradient algorithm to $\epsilon$-second-order stationary points. We show that our double-loop actor-critic algorithm, where the critic updates via $TD(0)$ and the actor updates via policy gradient, arrives at an $\epsilon$-second-order stationary point in $\tilde{O}(\epsilon^{-6.5})$ outer loop iterations with $\tilde{O}(\epsilon^{-8})$ inner-loop TD(0) steps. In contrast to existing first-order analyses of actor-critic algorithms, we allow for Markovian sampling in both the actor and the critic.

• •

  Of separate interest, we provide the first finite-time convergence analysis of the classic TD(0) algorithm on nonstationary Markov chains; i.e., we do not assume that the initial state distribution is the stationary distribution of the Markov chain. This allows realistic analyses of the actor-critic setting, where we have no guarantee that after every policy update the new underlying Markov chain is in its stationary distribution. We show that for $K$ constant timesteps $\alpha=\frac{1}{\sqrt{K}}$ and exponential mixing, the algorithm converges at the rate of $O(\frac{1}{\sqrt{K}})+O(\frac{1}{K})$, as opposed to $O(\frac{1}{\sqrt{K}})$ when starting from the stationary distribution.

The structure of the paper is as follows. In Section 2, we formalize the problem and introduce notation used in the rest of the paper. In Section 3, we establish second-order convergence for biased policy gradient estimators and apply our results to vanilla policy gradient. In Section 4, we present our new analysis of the TD(0) algorithm, which is incorporated to bound the critic approximation bias and show second-order convergence of the actor-critic algorithm. Finally, in Section 5, we summarize our results and discuss the next steps of our work.

In this section, we establish the second-order convergence of biased policy gradient in general and apply it to vanilla policy gradient. We begin with the original policy gradient theorem (Sutton et al., 1999), which states

which is equivalent to the temporal summation

For further details on the connection between these two formulations, see Appendix F.

Through Monte-Carlo sampling of trajectories $\tau$ of fixed length $H$, we construct the GPOMDP gradient estimator (Baxter & Bartlett, 2001) as follows

This yields the “vanilla” policy gradient algorithm as outlined in Algorithm 2. We define the truncated or finite-horizon objective $J_{H}(\theta)~{}=~{}\mathbb{E}_{\pi_{\theta},\rho_{0}}[\sum_{t=0}^{H-1}\gamma^{t}\mathcal{R}(s_{t},a_{t})]$. As observed in (Yuan et al., 2022; Zhang et al., 2020; Wu et al., 2022), since we cannot practically sample infinite-horizon trajectories, $\hat{G}^{VPG}(\theta;\tau)$ is a biased gradient estimator of $J(\theta)$ and an unbiased gradient estimator of $J_{H}(\theta)$, such that

Now we consider the second-order convergence of actor-critic policy gradient algorithms. Actor-critic methods can reduce the variance of policy gradient methods by separately learning to approximate the state-action value function $Q^{\pi}$. With some algebraic manipulation, the policy gradient can be expressed as follows

This motivates the construction of the following biased gradient estimator from a trajectory $\tau$ of length $H$

where $Q_{w}(s,a)$ is a function with parameter $w$ that approximates $Q^{\pi_{\theta}}(s,a)$. Note that $\hat{G}^{AC}(\theta;\tau)$ depends on $w$, although we omit this dependency in notation. In contrast to vanilla policy gradient, the actor-critic gradient estimator has two sources of bias: bias from the horizon truncation that depends on $H$, and bias from the critic approximation $Q_{w}$. Our following analysis addresses both. Let

represent the expectation of the gradient estimator with respect to the sampled trajectory $\tau$ of length $H$. Let

represent the expectation of an infinite-horizon gradient estimator with respect to a sampled trajectory of infinite horizon. As before, we have the following noise-bias decomposition of the policy updates

where $\xi_{t+1}=\hat{G}^{AC}(\theta_{t};\tau_{t})-G_{H}(\theta_{t})$ once again represents a zero-mean noise term. Then we can further decompose the bias term $d_{t+1}$ as follows

where $p_{t+1}=G_{H}(\theta_{t})-G_{\infty}(\theta_{t})$ represents the bias component due to truncation of the infinite horizon and $q_{t+1}=G_{\infty}(\theta_{t})-\nabla J(\theta_{t})$ represents the bias component induced by the critic approximation. In order to apply Theorem 3.6, we need to bound both $p_{t+1}$ and $q_{t+1}$; although the former can be bounded using the approach of the previous section, the latter requires novel techniques.

The structure of our algorithm is as follows. We consider a double-loop actor-critic algorithm with linear function approximation of $Q^{\pi_{\theta}}$ and an arbitrary policy parametrization. In the inner loop, the critic parameter $w$ is updated via TD(0) and projected onto a convex set $\Theta$, and in the outer loop, the policy parameter $\theta$ is updated via gradient updates. The gradient estimator algorithm is outlined in Algorithm 3.

To control the actor-critic bias $q_{t+1}$ and ensure second-order convergence by Theorem 3.6, we require that for each policy parameter iterate, the inner loop converges to the global optima $w^{*}(\theta_{t})$ and that $Q_{w^{*}}(\theta_{t})$ precisely approximates the true value function $Q^{\pi_{\theta_{t}}}$. The first requirement is satisfied by linear TD, as shown in Section 4.1, and the second is formalized later in Assumption 4.9.