The Optimal Reward Baseline for Gradient-Based Reinforcement Learning

Lex Weaver, Nigel TaoUAI 2001

TL;DR

This paper introduces a principled way to choose a "reward baseline" in gradient-based reinforcement learning, showing that the optimal baseline that minimizes gradient variance converges to the long-term average reward as the discount factor approaches 1. This leads to more stable and efficient learning, especially in scenarios requiring high discount factors.

What Problem Does This Paper Address?

Reinforcement learning (RL) algorithms that learn by climbing the gradient of expected reward (policy-gradient methods) are powerful because they can handle complex environments without needing a model of the system. However, a major practical hurdle is the high variance of the gradient estimator, which can make learning slow and unstable. A common technique to combat this is "discounting" future rewards, but this introduces a bias-variance trade-off: heavily discounting reduces variance but increases bias, while less discounting increases variance. This paper tackles the question of how to optimally reduce variance without introducing bias, specifically by investigating the role of a "reward baseline."

Methods

The authors extend existing policy-gradient algorithms, particularly the GPOMDP and OLPOMDP algorithms, by incorporating a constant reward baseline. They mathematically analyze the effect of this baseline on the variance of the gradient estimator. A key contribution is Theorem 1, which proves that the optimal constant reward baseline that minimizes gradient variance converges to the long-term average expected reward as the discount factor ($\gamma$) approaches 1.

To make this practical, they propose an adaptive estimate of the average reward as a baseline. This leads to two new algorithms:

  • GARB (Gradient-based Average Reward Baseline): A variation of GPOMDP that uses an online estimate of the average reward as a baseline.
  • OLGARB (On-Line GARB): An online learning version of GARB, similar to OLPOMDP, that directly updates policy parameters without explicitly storing gradient estimates.

Datasets

The paper evaluates its methods on three benchmark systems:

  • 3-State System: A simple, well-established system used to demonstrate gradient estimate convergence and the bias-variance trade-off.
  • Puckworld: A continuous control task where a robot needs to navigate a puck to a target. This system is noted to benefit from high discount factors.
  • Acrobot: A simulated two-link robot arm, analogous to a gymnast on a high bar, used to demonstrate the OLGARB algorithm.

No new datasets or benchmarks were introduced.

Key Insights and Ideas

  • The Optimal Baseline is the Average Reward (as $\gamma \to 1$): The most significant insight is the theoretical justification for using the long-term average reward as the optimal baseline for minimizing gradient variance, especially in the limit of $\gamma \to 1$. This provides a principled reason for a heuristic that had some empirical backing.
  • Variance Reduction Without Bias: The reward baseline, when chosen optimally, reduces variance without introducing bias into the gradient estimate. This is crucial for stable learning in high-variance environments.
  • Adaptive Baseline for Practicality: Since the true average reward might be unknown, an adaptive estimate (like the one used in GARB) is a practical solution that approximates the optimal baseline.
  • Benefit in High Discount Factor Scenarios: The paper highlights that the proposed methods are particularly beneficial in POMDPs that require high discount factors (close to 1) to avoid unacceptable levels of bias.

Key Results

  • Theoretical Proof: Theorem 1 establishes that the optimal constant reward baseline converges to the long-term average reward as $\gamma \to 1$.
  • Empirical Variance Reduction: Experiments on the 3-state system show that GARB (using an adaptive average reward baseline) exhibits slightly lower variance compared to GPOMDP, especially at high discount factors ($\gamma = 0.99$).
  • Consistent Learning: In the Puckworld experiment, controllers trained with GARB and OLGARB showed more consistent learning and converged to better policies compared to their counterparts without the average reward baseline (GPOMDP and OLPOMDP). Figure 7 specifically shows a statistically significant separation in average rewards between GARB and GPOMDP groups in the early stages of training.
  • Acrobot Performance: The OLGARB algorithm demonstrated reliable convergence to good policies on the Acrobot task, outperforming OLPOMDP in terms of consistency and lower variance in average rewards.

Limitations and Future Work

  • Theoretical Limit: Theorem 1 holds in the limit as $\gamma \to 1$. While experiments show benefits even for $\gamma = 0.4$, the theoretical guarantee is for the asymptotic case.
  • Unknown Average Reward: The paper acknowledges that the true average reward might not be analytically determinable and proposes an adaptive estimate as a practical solution. The performance of this adaptive estimate is demonstrated empirically.
  • Generalizability: While the results are promising, the paper notes that the claim for GARB's advantage is not made "in general" but observed for "some systems." Further research could explore the conditions under which GARB consistently outperforms standard methods.
  • Future Work: The paper implicitly suggests exploring more sophisticated adaptive baseline strategies and applying these methods to a wider range of complex POMDP problems.

Summary updated

BibTeX
@inproceedings{weaver2001optimal,
  author = {Lex Weaver and Nigel Tao},
  title = {{The Optimal Reward Baseline for Gradient-Based Reinforcement Learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2001},
}
Figure