Compatible Function Approximation for Unbiased Policy Gradients

29 concepts22 papers1 proposal

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:

  1. 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)$$
  2. 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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compatible_function_approximation_affdaa61,
  title = {compatible function approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compatible-function-approximation/rdr_affdaa612bda47bf985ddedfe2305749},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_compatible_function_approximation_affdaa61_v1,
  title = {compatible function approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compatible-function-approximation/rdr_affdaa612bda47bf985ddedfe2305749/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake