In reinforcement learning, policy gradient methods optimize a parameterized policy $\pi_\theta(a|s)$ by directly ascending the expected return. According to the policy gradient theorem, the exact gradient of the performance objective $J(\theta)$ is given by:
$$\nabla_\theta J(\theta) = \mathbb{E}_{s \sim d^\pi, a \sim \pi} \left[ \nabla_\theta \log \pi_\theta(a|s) Q^\pi(s,a) \right]$$
where $Q^\pi(s,a)$ is the true action-value function under policy $\pi$.
In practice, computing the true $Q^\pi(s,a)$ requires evaluating expectations over infinite horizons, which introduces massive variance if estimated via raw sample rollouts. To mitigate this, actor-critic architectures introduce a critic—a function approximator $Q_w(s,a)$ parameterized by weights $w$—to substitute for the true value function.
However, this substitution introduces a dangerous trade-off: using an approximated value function generally introduces systematic bias into the gradient estimate. As shown by Gregory Z. Grudic et al. in Rates of Convergence of Performance Gradient Estimates Using Function Approximation and Bias in Reinforcement Learning, poorly chosen basis functions or feature misalignments can introduce severe noise and bias, drastically slowing down convergence or causing the policy to diverge entirely. This raises a fundamental question: Can we use an approximated value function without biasing the policy gradient?
The Geometry of Compatibility
The answer lies in a remarkable insight established by Richard S. Sutton et al. in Policy Gradient Methods for Reinforcement Learning with Function Approximation. The authors proved that a critic does not need to be a globally accurate model of the true value function to provide an exact, unbiased policy gradient. Instead, the critic's structure simply needs to be compatible with the actor's policy parameterization.
Specifically, two conditions must be satisfied:
- Structural Compatibility: The critic $Q_w(s,a)$ must be linear in the features defined by the policy's score function: $$Q_w(s,a) = w^T \nabla_\theta \log \pi_\theta(a|s)$$
- Optimal Projection: The weights $w$ must minimize the mean squared error between the approximation and the true value function under the state-action distribution induced by the policy: $$\min_w \mathbb{E}_{s \sim d^\pi, a \sim \pi} \left[ \left( Q^\pi(s,a) - w^T \nabla_\theta \log \pi_\theta(a|s) \right)^2 \right]$$
To understand why this works, consider the geometry of the optimization space. The policy gradient update only cares about the projection of the action-value function onto the subspace spanned by the policy's score function $\nabla_\theta \log \pi_\theta(a|s)$. As analyzed by Vijay R. Konda et al. in Actor-Critic Algorithms, the critic does not need to resolve the entire state-action space; it only needs to capture the specific projection that directly influences the policy gradient.
This alignment ensures that the function approximator captures the specific information necessary for policy improvement. Indeed, Paul Wagner demonstrated in Optimistic policy iteration and natural actor-critic: A unifying view and a non-optimality result that natural actor-critic methods can be viewed as a limiting case of optimistic policy iteration, where the compatibility condition acts as the core representational bridge between the actor and the critic.
When we minimize the mean squared error using the score function as our basis, the first-order optimality condition dictates that the residual error $(Q^\pi(s,a) - Q_w(s,a))$ must be completely orthogonal to the basis functions:
$$\mathbb{E}_{s \sim d^\pi, a \sim \pi} \left[ \nabla_\theta \log \pi_\theta(a|s) \left( Q^\pi(s,a) - Q_w(s,a) \right) \right] = 0$$
Expanding this product yields:
$$\mathbb{E} \left[ \nabla_\theta \log \pi_\theta(a|s) Q^\pi(s,a) \right] = \mathbb{E} \left[ \nabla_\theta \log \pi_\theta(a|s) Q_w(s,a) \right]$$
The left side is the true policy gradient, and the right side is the gradient computed using our approximation. Because the approximation error is entirely orthogonal to the direction the actor cares about, the error vanishes during the gradient update. As a result, the policy gradient remains perfectly unbiased, even if the critic is a highly simplified linear model.
This mechanism eliminates the persistent approximation error typically found in linear value estimation, allowing the algorithm to converge precisely rather than getting stuck in an error neighborhood, a property formalized in recent non-asymptotic analyses by Yudan Wang et al. in Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation.
Direct Natural Gradient Estimation
Beyond providing unbiased standard gradients, compatible function approximation reveals an elegant connection to information geometry and Natural Policy Gradients (NPG).
Standard policy gradients follow the steepest ascent path in the parameter space, which is highly sensitive to how the policy is parameterized. In contrast, natural policy gradients follow the steepest ascent path along the manifold of probability distributions, making updates invariant to parameterization. This is achieved by pre-multiplying the standard gradient by the inverse of the Fisher Information Matrix $F(\theta)$:
$$\nabla_\theta^{\text{nat}} J(\theta) = F(\theta)^{-1} \nabla_\theta J(\theta)$$
where $F(\theta) = \mathbb{E} \left[ \nabla_\theta \log \pi_\theta(a|s) \nabla_\theta \log \pi_\theta(a|s)^T \right]$.
Computing and inverting $F(\theta)$ explicitly is computationally prohibitive in high-dimensional spaces. However, if we substitute the compatible critic $Q_w(s,a) = w^T \nabla_\theta \log \pi_\theta(a|s)$ into the policy gradient formula, we get:
$$\nabla_\theta J(\theta) = \mathbb{E} \left[ \nabla_\theta \log \pi_\theta(a|s) \left( \nabla_\theta \log \pi_\theta(a|s)^T w \right) \right] = F(\theta) w$$
By multiplying both sides by $F(\theta)^{-1}$, we find that:
$$\nabla_\theta^{\text{nat}} J(\theta) = w$$
This is a profound equivalence, first highlighted by J. Andrew Bagnell et al. in Covariant Policy Search and leveraged by Jan Peters et al. in Applying the Episodic Natural Actor-Critic Architecture to Motor Primitive Learning. The weights $w$ of a compatible critic are exactly the natural policy gradient.
Consequently, we do not need to compute or invert the Fisher Information Matrix. By simply training a linear critic on compatible features via standard least-squares regression over episodic rollouts, the resulting weights directly provide the natural gradient update direction. This insight underpins the efficiency of algorithms like the Natural Actor-Critic, as explored by Shalabh Bhatnagar et al. in Incremental Natural Actor-Critic Algorithms and Joni Pajarinen et al. in Compatible natural gradient policy search.
Extensions and Generalizations
The principle of aligning the critic's representation with the actor's update direction has been extended far beyond standard stochastic policies:
- Deterministic Policies: The authors extended the compatibility framework to deterministic settings in Deterministic Policy Gradient Algorithms, proving that a critic whose gradient matches the policy's action-gradient provides unbiased deterministic policy updates.
- Risk-Sensitive Objectives: When optimizing for variance-penalized or risk-sensitive objectives, standard value functions are insufficient. Aviv Tamar et al. in Variance Adjusted Actor Critic Algorithms and Prashanth L A et al. in Actor-Critic Algorithms for Risk-Sensitive MDPs derived compatible features for long-run variance estimation, ensuring that approximation errors do not bias risk-aware policy updates.
- Baseline Elimination: Francisco S. Melo proposed using differential basis functions that represent the difference between an action's features and its expected features under the current policy in Differential Eligibility Vectors for Advantage Updating and Gradient Methods, directly computing natural gradients without requiring an auxiliary baseline function.
- Non-parametric Policies: Guy Lever et al. generalized the concept to infinite-dimensional spaces in Modelling Policies in MDPs in Reproducing Kernel Hilbert Space by constructing compatible kernels aligned with functional policy gradients.
- Robustness to Misspecification: In online decision-making, Gi-Soo Kim et al. showed in Robust Tests in Online Decision-Making that utilizing a mathematically compatible critic ensures the validity of the policy gradient even when the underlying global reward model is an imperfect approximation.
- Trust-Region Optimization: In advanced trust-region optimization frameworks using optimal transport discrepancies, Antonio Terpin et al. demonstrated in Trust Region Policy Optimization with Optimal Transport Discrepancies: Duality and Algorithm for Continuous Actions how parameterized policies can be updated via gradient ascent to align with analytically derived targets within the constraints of function approximation.
- Theoretical Convergence: Modern non-asymptotic analyses continue to validate this framework. For instance, Rui Yuan et al. proved in Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies that natural policy gradients with compatible function approximation achieve linear convergence rates without requiring entropy regularization, viewing the process as an inexact mirror descent.
By framing policy evaluation and policy improvement as tightly coupled, gradient-consistent operations, compatible function approximation bridges the gap between value estimation and policy search (Changnan Xiao et al. in CASA: Bridging the Gap between Policy Improvement and Policy Evaluation with Conflict Averse Policy Iteration), providing a robust foundation for stable reinforcement learning.
Key Foundational Work
Policy Gradient Methods for Reinforcement Learning with Function Approximation (1999) — contributed 2 concept elements to this direction.
Actor-Critic Algorithms (1999) — contributed 2 concept elements to this direction.
A Natural Policy Gradient (2001) — contributed 1 concept elements to this direction.