Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap

Hang Wang, Sen Lin, Junshan Zhang

Introduction

In practical Reinforcement Learning (RL), agents rarely learn entirely from scratch. Instead, practitioners often employ "Warm-Start RL," initializing an agent with a policy pre-trained on offline data—such as human demonstrations or historical logs—before fine-tuning it through online interaction. While theoretically advantageous, empirical results are notoriously inconsistent. In some cases, the agent improves rapidly; in others, it stagnates in a sub-optimal plateau, particularly when using function approximation like neural networks.

This paper addresses a fundamental question: Whether and when can online learning be significantly accelerated by a warm-start policy? By rigorously quantifying how approximation errors in Actor and Critic updates propagate over time, the authors provide a theoretical framework explaining why warm-starting sometimes leads to rapid success and other times results in frustrating stagnation.

Methodology: A Newtonian Perspective

To bridge the gap between optimization theory and RL, the authors treat the Actor-Critic (A-C) algorithm as a form of "Newton’s Method with perturbation." In an ideal scenario (Abstract Dynamic Programming), policy iteration is equivalent to Newton's method, which boasts super-linear convergence. The authors model the inevitable errors arising from neural network approximations and finite data as perturbations to this ideal process.

Key methodological pillars include:

  • Finite-Time Analysis: Moving beyond asymptotic guarantees, the study analyzes the "sub-optimality gap" at specific, finite time steps.
  • Markovian Sample Handling: Recognizing that RL data consists of sequential, correlated trajectories, the authors utilize advanced Bernstein’s Inequality for Markovian samples rather than relying on standard i.i.d. assumptions.
  • Single-Time Scale: The analysis reflects realistic settings where the Actor and Critic are updated simultaneously, avoiding the common but often unrealistic two-time-scale assumption.

Key Insights: Bias, Error Propagation, and Stagnation

The Newtonian framework reveals several critical insights into the mechanics of warm-start RL:

  • Bias is the Primary Bottleneck: The paper draws a critical distinction between random noise and systematic algorithmic bias. While noise can be averaged out over time, bias—stemming from finite rollout lengths or function approximation limits—creates a hard performance floor. If updates are biased, the agent will never reach the optimal policy, regardless of the warm-start quality.
  • The "Wash-out" Phenomenon: Conversely, if algorithmic bias is kept sufficiently low, online learning can eventually "wash out" the imperfections of a mediocre starting policy. This mathematical finding explains why a "good enough" offline policy can sometimes achieve the same peak performance as a near-perfect one.
  • Error Propagation and the Stagnation Paradox: Errors in RL are compounding. A small value estimation error in the Critic bleeds into the Actor's policy improvement step, accumulating across iterations. Consequently, even with a near-optimal warm-start policy, an agent can still stagnate if approximation errors are not properly managed.

Theoretical and Empirical Results

The authors derived rigorous upper and lower bounds for the sub-optimality gap. The upper bounds demonstrate that the maximum expected distance from the optimal policy is a product of the initial policy's quality and the accumulated bias. Crucially, the lower bounds establish that if the bias term $B(t)$ is non-negligible, the performance gap remains strictly bounded away from zero.

To validate these theoretical findings, the authors conducted experiments using a Gridworld benchmark (varying complexities from 10x10 to 20x20 grids). By manually injecting bias into the value function during navigation tasks, they empirically confirmed their mathematical proofs: higher bias directly correlated with a higher "error floor," causing the agent's performance to plateau regardless of further training iterations.

Limitations and Future Directions

While the Actor analysis is highly general, the Critic analysis currently relies on linear function approximation. Extending this framework to the highly non-linear dynamics of deep neural networks remains an open challenge. Furthermore, the paper focuses primarily on the existence of a sub-optimality gap and convergence guarantees, rather than detailing exact sample complexity (the precise number of samples required to reach a specific threshold). Finally, as the current framework is specific to Actor-Critic methods, future research could explore whether similar Newtonian perturbation models apply to other popular algorithms like Q-learning or Proximal Policy Optimization (PPO).

Summary updated

Abstract

Warm-Start reinforcement learning (RL), aided by a prior policy obtained from offline training, is emerging as a promising RL approach for practical applications. Recent empirical studies have demonstrated that the performance of Warm-Start RL can be improved *quickly* in some cases but become *stagnant* in other cases, especially when the function approximation is used. To this end, the primary objective of this work is to build a fundamental understanding on ''whether and when online learning can be significantly accelerated by a warm-start policy from offline RL?''. Specifically, we consider the widely used Actor-Critic (A-C) method with a prior policy. We first quantify the approximation errors in the Actor update and the Critic update, respectively. Next, we cast the Warm-Start A-C algorithm as Newton's method with perturbation, and study the impact of the approximation errors on the finite-time learning performance with inaccurate Actor/Critic updates. Under some general technical conditions, we derive the upper bounds, which shed light on achieving the desired finite-learning performance in the Warm-Start A-C algorithm. In particular, our findings reveal that it is essential to reduce the algorithm bias in online learning. We also obtain lower bounds on the sub-optimality gap of the Warm-Start A-C algorithm to quantify the impact of the bias and error propagation.
BibTeX
@inproceedings{wang2023warm,
  author = {Hang Wang and Sen Lin and Junshan Zhang},
  title = {{Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=QlWpg5S9bq},
}
Figure