Technical Summary: Refined Analysis of Entropy-Regularized Actor-Critic

Problem Statement

This paper investigates the theoretical role of the critic in Actor-Critic (AC) algorithms within the context of entropy-regularized, finite, discounted Markov Decision Processes (MDPs). While AC methods are empirically dominant in modern Reinforcement Learning (RL), the specific mechanism by which the value function (critic) acts as a stabilizer remains theoretically under-explored. Specifically, the authors aim to distinguish between two types of variance reduction:

1. Weak variance reduction: The update variance is reduced by a multiplicative constant (e.g., via tail averaging).
2. Strong variance reduction: The variance of the gradient estimator vanishes as the iterates approach the optimum, enabling linear convergence rates similar to deterministic methods.

The central question is whether AC methods achieve strong variance reduction, particularly when the critic is either exact or learned online alongside the actor.

Methodology

The authors analyze the Entropy-Regularized Actor-Critic (Ent-AC) algorithm, which alternates between actor and critic updates. The setting involves a finite state space $S$ and action space $A$, with a discount factor $\gamma \in (0, 1)$. The objective is to maximize the regularized value function $\tilde{J}_\lambda(\theta)$, which includes an entropy penalty term $\lambda \log(\pi(a|s))$.

The analysis proceeds in two distinct phases:

1. Exact Critic Case

The authors first assume an "oracle" scenario where the critic $\hat{q}_k$ is perfectly known (i.e., $\hat{q}_k \equiv \tilde{q}^\lambda_{\theta_k}$, the true regularized Q-function).

• Variance Analysis: They prove that when the critic is exact, the variance of the stochastic actor gradient is bounded by the norm of the deterministic gradient up to a multiplicative constant. Crucially, as the algorithm converges and the deterministic gradient approaches zero, the stochastic variance vanishes entirely.
• Projection Operator: To ensure the policy probabilities do not vanish (which would break the variance bounds), the authors introduce a novel projection operator $T_\tau$ (based on $U_\tau$). This operator projects policies onto a subspace where every action has a probability of at least $\tau_\lambda$, ensuring the policy remains sufficiently stochastic without aggressively shifting the policy distribution.

2. Inexact Critic Case (Online Learning)

In the practical setting, the critic is learned via Temporal Difference (TD) updates alongside the actor.

• Bias-Variance Decomposition: The authors demonstrate that when the critic is inexact, the bias and variance of the actor's gradient estimator are directly induced by the critic's estimation error.
• Recursion Analysis: They derive separate recursions for the actor and critic. The critic is updated $H$ times (TD steps) for every single actor update.
• Convergence Bound: By combining the actor and critic recursions, they establish that the actor's convergence rate is governed by the critic's bias and variance. If the number of critic updates $H$ is sufficiently large, the critic bias becomes negligible, and the algorithm behaves similarly to the exact critic case, limited only by the critic's stochastic noise floor.

Key Contributions

1. Proof of Strong Variance Reduction: The paper provides the first proof that Ent-AC with an exact critic acts as a strong variance reduction method. Unlike previous analyses that only showed weak variance reduction, this work demonstrates that the variance of the gradient estimator vanishes as the optimum is approached, matching the convergence properties of deterministic gradient methods.
2. Sample Complexity with Exact Critic: The authors establish that Ent-AC with an exact critic achieves a sample complexity of $\tilde{O}(\log(1/\epsilon))$ to reach an $\epsilon$-optimal regularized value. This matches the iteration complexity of deterministic policy gradient methods.
3. Sample Complexity with Inexact Critic: For the general case where the critic is learned online, the paper derives a sample complexity of $\tilde{O}(1/\epsilon)$. This result highlights that the dominant factor in the algorithm's complexity is the learning of the critic.
4. Role of Critic Updates ($H$): The analysis quantifies the trade-off of the number of critic updates $H$. It shows that $H$ needs to be $\tilde{O}(\log(1/\epsilon))$ to reduce the critic's bias below the $\epsilon$ threshold. Beyond this point, additional critic steps primarily improve transient performance rather than the asymptotic rate.

Results

• Theoretical Guarantees:
  • Exact Critic: Linear convergence to the optimal policy with $\tilde{O}(\log(1/\epsilon))$ sample complexity.
  • Inexact Critic: Convergence to an $\epsilon$-optimal solution with $\tilde{O}(1/\epsilon)$ sample complexity. The error is decomposed into initialization error (geometrically forgotten), critic bias (controlled by $H$), and critic variance (the asymptotic noise floor).
• Empirical Validation:
  • Experiments were conducted on tabular Gridworld environments (varying sizes) and synthetic MDPs.
  • The results confirm that the performance of the learned policy is strictly monotonic with respect to the number of critic steps $H$. Increasing $H$ from 8 to 64 consistently reduces the approximation gap relative to the "Exact Critic" oracle, leading to faster convergence and higher objective values.
  • The experiments validate the theoretical claim that "learning the critic pays off," as insufficient critic updates lead to significant performance gaps compared to the oracle.

Significance and Claims

The paper claims to resolve a long-standing theoretical gap regarding the variance reduction properties of Actor-Critic methods.

• Theoretical Insight: It establishes that the "advantage" function (derived from the critic) does not merely reduce variance by a constant factor but can eliminate it entirely in the limit, provided the critic is accurate. This explains the empirical success of AC methods over vanilla policy gradients.
• Practical Implication: The findings underscore the critical importance of accurate critic estimation. The authors argue that in practice, significant computational effort should be dedicated to learning the critic (via multiple TD updates) before updating the actor. This aligns with recent empirical observations (e.g., Wang et al., 2025) but provides the rigorous theoretical justification for why this strategy is necessary.
• Limitations and Scope: The authors note that their results are currently specific to the tabular setting with entropy regularization. They explicitly state that it remains unknown whether these strong variance reduction properties hold in the unregularized case or in function approximation settings (e.g., deep neural networks), identifying these as promising directions for future research.

In summary, this work provides a rigorous foundation for the "strong variance reduction" hypothesis in AC methods, proving that with a sufficiently accurate critic, the algorithm achieves convergence rates comparable to deterministic optimization, and that the cost of learning the critic is the primary determinant of the algorithm's overall efficiency.