Technical Summary: Natural Policy Gradient as Doubly Smoothed Policy Iteration

Problem Statement

Reinforcement learning (RL) problems are typically modeled as Markov Decision Processes (MDPs). While classical dynamic programming methods like Policy Iteration (PI) and Value Iteration (VI) rely on the contraction and monotonicity properties of the Bellman operator, modern gradient-based methods like Natural Policy Gradient (NPG) and Policy Dual Averaging (PDA) are often analyzed through the lens of continuous optimization over the policy space.

A conceptual gap exists in the literature: analyses of NPG often fail to leverage the fundamental $\ell_\infty$-norm contraction of the Bellman operator, which underpins the strong convergence guarantees of classical methods. Consequently, existing theoretical results for NPG often suffer from one or more limitations:

1. Lack of global geometric convergence.
2. Dependence on initial state distributions or concentrability coefficients.
3. Requirement for additional regularization of the MDP or the algorithm to induce curvature.
4. Reliance on adaptive, trajectory-dependent step sizes.

The paper aims to bridge this gap by providing a unified framework that connects classical PI with modern gradient-based methods, enabling a distribution-free, geometric convergence analysis without modifying the MDP or requiring adaptive steps.

Methodology: Doubly Smoothed Policy Iteration (DSPI)

The authors introduce Doubly Smoothed Policy Iteration (DSPI), a unified algorithmic framework formulated as a Bellman-operator framework. DSPI updates the policy via a regularized greedy step applied to a weighted average of past Q-functions.

The core of DSPI involves two levels of smoothing:

1. Averaging Smoothing: Instead of using only the most recent Q-function, the algorithm maintains a running average ($\bar{Q}_k$) of all past Q-functions.
2. Regularization Smoothing: The greedy policy update is replaced with a regularized step (e.g., softmax) involving a concave function $\nu(\cdot)$ (such as entropy).

The update rule is defined as:
$$\pi_{k+1}(s) \in \arg\max_{\mu \in \Delta(A)} \left\{ \mu^\top \bar{Q}_{k+1}(s) + \eta_k \nu(\mu) \right\}$$
where $\bar{Q}_{k+1} = (1-\beta_k)\bar{Q}_k + \beta_k Q_{\pi_k}$, and the smoothing parameter $\eta_k$ decays geometrically based on the step sizes $\beta_k$.

Crucially, the authors demonstrate that DSPI admits a compact formulation using smoothed Bellman operators ($H_\eta$ and $H^\pi_\eta$). This allows the algorithm to be analyzed using the monotonicity and contraction properties of these operators, rather than relying solely on optimization-theoretic tools.

Key Contributions

1. Unification of Algorithms

The paper establishes that DSPI is a general framework that encompasses several major algorithms as special cases:

• Policy Iteration (PI): Recovered when the step size $\beta_k \equiv 1$ (no averaging) and regularization vanishes.
• Natural Policy Gradient (NPG): Recovered by setting $\nu(\cdot)$ to the Shannon entropy and choosing specific step size schedules.
• Policy Dual Averaging (PDA): Recovered by choosing $\nu(\cdot)$ as a shifted negative divergence-generating function.
• Dual-Averaged Policy Iteration: A new variant where the policy is updated greedily based on the averaged Q-functions ($\nu(\cdot) \equiv 0$).

2. Unified Convergence Analysis

By leveraging the properties of the smoothed Bellman operators, the authors provide a unified convergence analysis for DSPI:

• Asymptotic Convergence: Proven for any non-summable step size sequence.
• Global Geometric Convergence: Proven for constant step sizes. The error bound is given by:
  $$\|V^* - V^{\pi_k}\|_\infty \leq (1 - (1-\gamma)\beta)^{k-1} (\gamma \|V^* - V^{\pi_0}\|_\infty + \tau \nu_{\max})$$
  where $\gamma$ is the discount factor and $\beta$ is the constant step size.

3. Improved Theoretical Guarantees for NPG and PDA

Applying the DSPI framework to NPG and PDA yields the following results, which improve upon or match the state-of-the-art without requiring restrictive assumptions:

• Distribution-Free: The convergence bounds depend only on the $\ell_\infty$-norm of the value function gap, not on the initial state distribution or concentrability coefficients.
• No Additional Regularization: The analysis holds without modifying the MDP or adding extra regularizers beyond the entropy term inherent in standard NPG.
• Simple Step Sizes: The results hold for a simple, pre-specified geometrically increasing step size schedule ($\alpha_k = \beta \alpha_0 / (1-\beta)^k$), eliminating the need for adaptive stepsizes that depend on the policy trajectory or Bellman error.
• Iteration Complexity: NPG and PDA achieve an $\epsilon$-optimal policy in $O((1-\gamma)^{-1} \log((1-\gamma)^{-1}\epsilon^{-1}))$ iterations.

4. Finite Termination of Dual-Averaged PI

For the unregularized case (Dual-Averaged PI), the authors prove finite termination. The algorithm finds an optimal policy in at most $O(mn(1-\gamma)^{-1} \log((1-\gamma)^{-1}))$ iterations, where $n$ and $m$ are the sizes of the state and action spaces. This is achieved by showing that the algorithm eliminates at least one suboptimal action every $k^*$ iterations.

5. Extensions

The framework is shown to extend naturally to:

• Linear Function Approximation: DSPI with linear function approximation achieves geometric convergence up to a function approximation error term.
• Stochastic Shortest Path (SSP) Problems: The analysis extends to undiscounted SSP problems, establishing distribution-free global geometric convergence under the assumption that all stationary policies are proper.

Results and Significance

The paper claims that its primary significance lies in providing a unified perspective that connects classical dynamic programming with modern gradient-based RL. By interpreting NPG and PDA as smoothed and averaged variants of Policy Iteration, the authors are able to:

1. Recover Strong Guarantees: Establish global geometric convergence for NPG and PDA using only the intrinsic properties of the Bellman operator (monotonicity and contraction).
2. Remove Artifacts: Eliminate the need for the "curvature-inducing" regularization or adaptive stepsizes often required in previous optimization-based analyses.
3. Simplify Analysis: Provide a simpler, more principled analysis that avoids the complexities of distribution mismatch coefficients.

The authors note that while their current analysis assumes access to exact Q-functions (isolating policy improvement dynamics), the framework sets the stage for future work in model-free settings where Q-functions must be estimated. They identify the combination of DSPI with finite-time policy evaluation guarantees as a non-trivial next step to achieve sharp sample complexity results for model-free RL.