The Optimal Reward Baseline for Gradient-Based Reinforcement Learning

By Lex Weaver, Nigel Tao. 2001

275 citations recorded by the source corpus.

There exist a number of reinforcement learning algorithms which learn by climbing the gradient of expected reward. Their long-run convergence has been proved, even in partially observable environments with non-deterministic actions, and without the need for a system model. However, the variance of the gradient estimator has been found to be a significant practical problem. Recent approaches have discounted future rewards, introducing a bias-variance trade-off into the gradient estimate. We incorporate a reward baseline into the learning system, and show that it affects variance without introducing further bias. In particular, as we approach the zerobias, high-variance parametedzation, the optimal (or variance minimizing) constant reward baseline is equal to the long-term average expected reward. Modified policy-gradient algorithms are presented, and a number of experiments demonstrate their improvement over previous work.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research, Reinforcement Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation (2013, background): “…derivative of that expression with respect to ¯ L i , we obtain Note that a general formula for the lowest variance estimator for REINFORCE (Williams, 1992) had already been introduced in the reinforcement learning context by Weaver and Tao (2001), which includes the above result as a special case.”
Q-Prop: Sample-Efficient Policy Gradient with An Off-Policy Critic (2016, background): “Directly analyzing the above variance measure is nontrivial, for the same reason that computing the optimal baseline is difﬁcult (Weaver & Tao, 2001).”
Show, Attend and Tell: Neural Image Caption Generation with Visual Attention (2015, methodology): “In this section we discuss two alternative mechanisms for the attention model f att: stochastic attention and deterministic attention.”
Rationalizing Neural Predictions (2016, neutral): “(Weaver and Tao, 2001; Mni et al., 2014; Ba et al., 2015; Xu et al., 2015)).”
Counterfactual Multi-Agent Policy Gradients (2017, background): “In particular, Rt is replaced by any expression equivalent to Q(st, ut) − b(st), where b(st) is a baseline designed to reduce variance (Weaver and Tao 2001).”
The Mirage of Action-Dependent Baselines in Reinforcement Learning (2018, methodology): “In contrast, state-dependent baselines (Williams, 1992; Weaver & Tao, 2001) reduce variance without introducing bias.”
MuProp: Unbiased Backpropagation for Stochastic Neural Networks (2015, methodology): “…· [f(x)− f(x̄)− f ′(x̄)(x− x̄)]︸︷︷︸ ĝR + f ′(x̄)∇θµx(θ)︸︷︷︸ ĝMF (3) 1Optimal baselines are somewhat involved, as they take into account the magnitude of∇θ log pθ(x) and are different for each parameter (Weaver & Tao, 2001). where x ∼ pθ, and ĝ(µ) is an unbiased estimate of the gradient.”
Techniques for Learning Binary Stochastic Feedforward Neural Networks (2014, methodology): “Proposed Unbiased Estimator of the Gradient We propose a new gradient estimator by applying a variance reduction technique (Weaver and Tao, 2001; Mnih and Gregor, 2014) to the estimator by Tang and Salakhutdinov (2013).”
Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines (2018, methodology): “One effective method to reduce variance without introducing bias is through using a baseline, which has been widely studied (Sutton & Barto, 1998; Weaver & Tao, 2001; Greensmith et al., 2004; Schulman et al., 2016).”
Reward Design via Online Gradient Ascent (2010, methodology): “The height feature has been used in previous work as an alternative definition of objective reward [23].”
Learning to Teach (2018, methodology): “To reduce estimation variance, a moving average of the historical reward values in previous episodes is set as a reward baseline for the current episode (Weaver & Tao, 2001).”
You Impress Me: Dialogue Generation via Mutual Persona Perception (2020, methodology): “Furthermore, subtracting a baseline (Weaver and Tao, 2001), here the mean reward of a mini-batch, is applied on R ( a B n ) to reduce variance.”
Discriminability Objective for Training Descriptive Captions (2018, methodology): “jI;) (7) Here bc represents the caption sampled from (6). The baseline bis computed by a function designed to make it independent of the sample (leading to variance reduction without increasing bias [52]). In our case, folllowing [6], the baseline is the value of the reward R(c;I) on the greedy deco”
Adversarial Neural Machine Translation (2017, background): “trajectory y0to estimate the terminal reward given by D. Acting in this way brings high variance, to reduce the variance, a moving average of the historical reward values is set as a reward baseline (Weaver and Tao, 2001). One can sample multiple trajectories in each decoding step, by regarding Gas ”