Learning values across many orders of magnitude

Hado van Hasselt; Arthur Guez; Matteo Hessel; Volodymyr Mnih; David Silver

Source-linked AI summary

Learning values across many orders of magnitude

Hado van Hasselt, Arthur Guez, Matteo Hessel, Volodymyr Mnih, David Silver

arXiv:1602.07714v2Feb 24, 2016cs.LGcs.AIcs.NEstat.ML

TL;DR

Learning algorithms often depend on the scale of the function they approximate, while reward clipping in Atari can change the optimized objective and behavior. The paper adaptively normalizes learning targets, using Pop-Art to preserve unnormalized outputs while adjusting scale and shift. In Atari, Pop-Art replaces reward clipping without diminishing overall performance, although behavior and scores can diverge under myopic agents.

Problem
Learning algorithms are not invariant to target scale, and Atari reward clipping handles differing magnitudes by changing the objective and sometimes producing qualitatively different policies.
Method
Pop-Art adaptively learns target scale and shift while preserving the unnormalized function outputs, separating normalization from learning the function’s shape.
Results
Pop-Art removes reward clipping while retaining overall performance; on 32 of 57 games, performance was at least as good as clipped Double DQN, with median and mean differences of +0.4% and +34%.
Takeaways & Limitations
Adaptive normalization exposes true unclipped rewards while handling target magnitudes that vary across games and change during learning.
Takeaways & Limitations
In Time Pilot, myopic agents can favor quickly advancing by shooting a mothership, although the safer clipped strategy scores more points over the long run.

Abstract

from arXiv · show

Most learning algorithms are not invariant to the scale of the function that is being approximated. We propose to adaptively normalize the targets used in learning. This is useful in value-based reinforcement learning, where the magnitude of appropriate value approximations can change over time when we update the policy of behavior. Our main motivation is prior work on learning to play Atari games, where the rewards were all clipped to a predetermined range. This clipping facilitates learning across many different games with a single learning algorithm, but a clipped reward function can result in qualitatively different behavior. Using the adaptive normalization we can remove this domain-specific heuristic without diminishing overall performance.

1 Introduction

The paper targets learning methods whose updates depend on target scale, especially when reward magnitudes vary across tasks or change during reinforcement learning. It proposes adaptive target normalization to avoid domain-specific reward clipping while preserving the ability to use shared learning systems.

Motivation: DQN clips rewards and temporal-difference errors to [−1, 1] so one algorithm can operate across Atari games with widely varying reward magnitudes.For example, Ms. Pac-Man can give up to +1600 for eating a ghost, whereas Pong rewards are bounded by −1 and +1.
Problem: Reward clipping introduces domain knowledge and can make agents optimize reward frequency rather than reward sum.This heuristic suits Atari but may not generalize to other domains.
Problem: Clipping changes the objective and can produce qualitatively different behavior policies.Thus, stabilizing learning through clipping may alter what the agent is trying to optimize.
Contribution: The proposed method adaptively normalizes learning targets, making suitable hyperparameters easier to find across differing and changing natural magnitudes.The approach is presented as applicable to supervised learning and reinforcement learning, including non-stationary value magnitudes as policies change.
Contribution: Adaptive normalization can separate each component’s natural magnitude from its relative importance in a multivariate loss.This is useful when predicted signals have different units, such as sensor modalities.
Context: Learning from data streams is difficult when function magnitudes are unknown beforehand or change over time, unlike settings with a priori data for hyperparameter tuning.The paper identifies improving policies and changing value distributions as a reinforcement-learning example.

2 Adaptive normalization with Pop-Art

Pop-Art adaptively normalizes learning targets while preserving the outputs of the unnormalized function. It separates learning normalization from learning the function’s shape, supporting bounded normalized errors and scale-adjusted updates.

Adaptive target normalization: Pop-Art learns target scale and shift separately from the approximating function, using an affine normalization of targets.The unnormalized approximation is reconstructed as f(x) = Σg(x) + µ.
Pop-Art design: The method combines adaptive rescaling of targets with output-preserving updates to the normalized function.These properties are called ART and POP, respectively, and together define Pop-Art.
Preserving outputs: Changing scale and shift parameters can preserve the unnormalized function’s outputs precisely by simultaneously updating the final linear parameters.For scalar normalization, Wnew = (σ/σnew)W and bnew = (σb + µ −µnew)/σnew.
Implementation: Algorithm 1 first rescales W and b to preserve outputs, then updates normalization parameters and performs the subsequent SGD update.The order matters because the new normalization is used immediately in the next SGD update.
Adaptive updates: Incremental normalization can use exponential moving averages, which place more weight on recent data in non-stationary settings.With constant β, the updates become exponential moving averages; βt = 1/t gives full equivalence to the batch-style update.
Theoretical properties: 10^-4 guarantees normalized targets in (−100, 100) without assumptions about the target distribution.This bounds potential normalized errors before learning begins, while the corresponding lower-layer updates scale with σt^-2.

3 Binary regression experiments

The binary regression experiment tests how normalization handles rare, very large targets. Pop-Art combines faster learning with protection from spikes while preserving outputs for smaller targets.

Setup: The experiment compares SGD, adaptive normalization without output preservation (‘Art’), and Pop-Art under infrequent large target spikes.Every 1000 samples, the network receives target 65,535 after training mostly on integers from 0 to 2^10−1.
Results: Art learns faster with α = 10−2.5, but changing normalization increases errors on smaller inputs after spikes.Because Art does not preserve outputs precisely, normalization changes the outputs associated with smaller targets.
Results: Pop-Art performs much better, using α = 10−2.5 and β = 10−0.5 to track statistics quickly while preserving smaller-target outputs.Art performs best with β = 10−4, whereas Pop-Art benefits from the faster statistics rate.
Results: RMSprop results were similar to SGD and were omitted from the figure.

4 Atari 2600 experiments

The Atari experiments test whether Pop-Art can replace reward clipping in Double DQN. Without clipping, Pop-Art narrows gradient scales and retains overall performance, while also changing behavior substantially across games.

Experimental setup: Double DQN is evaluated without changes, without clipping rewards and temporal-difference errors, and without clipping while using Pop-Art.The targets combine an immediate reward with the discounted value at the next state.
Gradient scales: Without clipping, Pop-Art confines 95% of median gradient norms to roughly 1–20, versus almost four orders of magnitude for clipped Double DQN and more than six for unclipped Double DQN.The comparison uses gradient norms across games, with bands covering 50%, 90%, and 95% of games.
Behavioral effects: The performance distribution changes drastically: Pop-Art improves some games, including Gopher and Centipede, but substantially decreases performance on others, including Video Pinball and Star Gunner.In Ms. Pac-Man, Pop-Art leads the agent to hunt ghosts rather than treating them like pellets; Frostbite rises from below 50% to near-human performance.
Behavioral effects: In Time Pilot, Pop-Art favors quickly shooting the mothership, while clipping favors a safer strategy that earns more points over the long run.Both agents use γ = 0.99, optimizing rewards only roughly a dozen seconds into the future.
Performance: 32 out of 57 games perform at least as well as clipped Double DQN with Pop-Art, with median differences of +0.4% and mean differences of +34%.The scores are normalized using human and random scores after evaluation over 100 episodes per game.

5 Discussion

The discussion presents Pop-Art as a way to handle target magnitudes that vary across tasks and over time. It replaces reward clipping in DQN while exposing unclipped rewards to learning and exploration.

Discussion: Pop-Art adapts to different and non-stationary target magnitudes, a challenge made especially difficult when reinforcement-learning policies and values repeatedly change.
Discussion: Pop-Art can replace DQN reward clipping while allowing the learning algorithm to use the true unclipped rewards.The authors suggest this can inform future exploration improvements.

Appendix

The appendix introduces extensions and variations of the normalization approach and provides proofs for the paper’s propositions.

Appendix: The appendix analyzes normalization based on percentiles or minibatches and proves all propositions from the main text and appendix.

Experiment setup

The experiments follow prior Double DQN setups and evaluate trained agents through repeated simulated play, with scores normalized relative to random and human agents.

Agents were evaluated for 30 minutes of simulated play, corresponding to 108,000 frames.
The evaluation was repeated 100 times, with run diversity induced by a small probability of epsilon-greedy exploration on each step.
Results in Figure 2 normalize raw scores by subtracting random-agent performance and dividing by the absolute human–random score difference.
The raw scores underlying the normalized results are reported in Table 1.

Generalizing normalization by variance

The method introduces an explicit scale parameter s to control normalized-target variance independently of the normalization step size β, preserving target distributions while controlling update magnitudes.

A desired normalized-target standard deviation s > 0 can be specified through an additional scaling parameter.This parameter generalizes the normalization procedure while retaining the usual updates for ν_t and μ_t.
The scaling parameter is useful for fast tracking in non-stationary problems because it permits a large step size α without overly large updates.
Figure 2 compares target histograms and normalized-target variance while varying β or the upper bound s.
Varying β with s = 1 can make normalized-target variance fall far below one and produce a strongly non-normal distribution, whereas varying s with β = 0.01 keeps variance approximately at s.
Separating target magnitude, controlled by s, from update magnitude can be easier when using adaptive step-size algorithms.

Adaptive normalization by percentiles

Percentile normalization adaptively places a chosen proportion of targets inside a fixed interval, offering an alternative to mean-and-variance normalization with explicit distributional scope.

Percentile normalization chooses lower and upper target values so that a proportion p of normalized targets lies inside a predetermined interval.
For normally distributed targets, percentile normalization has a direct correspondence to normalization by mean and variance.
p = 0.99 and p = 0.95 correspond to s ≈0.4 and s ≈0.5, respectively, while s = 1 corresponds to p ≈0.68 for normal targets.
Using p = 1 based on observed extrema guarantees normalized targets in [−1, 1] but can be conservative, outlier-sensitive, and slow learning through very small updates.
The online percentile procedure tracks ymin_t and ymax_t using memory-efficient updates rather than storing all previous targets.
Under stationary target distributions, the percentile updates converge asymptotically to values satisfying the desired proportion condition.
If β_t is too small, convergence is slow; asymmetrical least-squares updates can instead make step magnitudes depend on actual errors.

Online learning with minibatches

Minibatch-based normalization is connected to percentile normalization: under stated assumptions, its effective covered proportion increases with batch size, trading robustness against update magnitude.

Online normalization by mean and variance can be implemented with minibatches of targets of size B.
Non-integer order statistics can be defined by rounding to a neighboring integer or linearly interpolating between neighboring values.
Minibatch updates can move tracked lower and upper values toward the minibatch extremes.
For i.i.d. uniform minibatches of size B ≥ 2, the updates converge to percentile normalization with p = (B − 1)/(B + 1).
B = 20 corresponds roughly to p = 19/21 ≈ 0.9 and, via the normal-target correspondence, to s ≈0.6.
Although the exact proposition assumes uniform targets, larger minibatches generally increase interval coverage, potentially improving outlier robustness at the expense of slower learning.

A note on initialization

The initialization of a recency-weighted average can be handled so that observed data receive the intended relative weights without dependence on the initial value. The paper contrasts in-place correction with safe high initialization when early targets are small and noisy.

Initialization: The proposed step size makes a recency-weighted average independent of its initial value while preserving the relative weights induced by constant step size β.This correction is applied in place rather than by storing an auxiliary exponentially weighted average.
Initialization: Adam similarly removes initialization effects by computing and renormalizing an exponentially weighted average using a term analogous to 1−(1−β)^t.The paper distinguishes that approach from its in-place correction, which does not require auxiliary variables.
Initialization: High initial normalization, such as ν0 = 10^4 or ν0 = 10^6, reduces the influence of small, noisy early targets on learning updates.Using the initialization-correcting step size instead could make those early observations overly influential and fit the approximating function to noise.

Deep Pop-Art

Deep Pop-Art extends adaptive normalization beyond network outputs to internal levels of hierarchical nonlinear functions while preserving the represented unnormalized function. Its theoretical results establish update equivalence and convergence under stated stochastic-approximation conditions.

Deep Pop-Art: Normalization can be applied below a soft-max or at any level of a hierarchical nonlinear function, rather than only to final network outputs.Targets may be identified by back-propagating the loss gradient through the soft-max or by inverting the function.
Deep Pop-Art: Normalizing gradients from separate sources before merging can prevent one source from drowning out the others and support weighting by relative importance.This addresses gradient combination in network graphs more complex than standard feedforward multilayer networks.
Deep Pop-Art: The transformation preserves the outputs of the unnormalized function exactly when scale, shift, and final-layer parameters are changed together.The displayed parameter relation maintains the same function values after normalization changes.
Deep Pop-Art: For any sequence of nonsingular scales, Algorithms 1 and 2 produce identical parameter sequences for the shared representation and identical function outputs for every input.The equivalence assumes identical initialization, including Σ0 = I and µ0 = 0, and the same initial network parameters.
Deep Pop-Art: Under stationary target distributions and suitable step sizes, the normalization updates converge to an attracting fixed point with finite stochastic-update variance.The expected update direction points toward the fixed point, while the step-size conditions ensure reachability and convergence in the limit.
Deep Pop-Art: The paper notes that normalization by mean and variance is not known to be uniformly best, and discusses percentile- and minibatch-based alternatives.The proof for the minimum-target update is stated to be analogous, while broader stochastic-approximation conditions are left to the literature.