PaperlayerView exact revision on arXiv

Source-linked AI summary

Surprise-Based Intrinsic Motivation for Deep Reinforcement Learning

Joshua Achiam, Shankar Sastry

arXiv:1703.01732v1cs.LG

TL;DR

Sparse-reward exploration remains difficult because simple action-noise heuristics can fail in complex environments. The paper learns an MDP transition model alongside the policy and derives intrinsic rewards from transition surprise. Across hard deep reinforcement learning benchmarks, surprisal and one-step learning progress enable efficient exploration, with surprisal robust across tasks and competitive with state-of-the-art intrinsic motivation.

  • Problem

    Simple exploration heuristics such as ϵ-greedy action selection and Gaussian control noise can be inadequate for especially sparse rewards.

  • Method

    The paper learns a transition model concurrently with the policy and approximates KL-based surprise using surprisal and k-step learning progress rewards.

  • Results

    Surprisal and 1-step learning progress produced efficient exploration on several hard benchmarks, while surprisal outperformed other heuristics across many tasks and was competitive with state-of-the-art intrinsic motivation.

  • Takeaways & Limitations

    Surprise-based incentives provide scalable, computationally inexpensive exploration for high-dimensional and continuous-control tasks.

  • Takeaways & Limitations

    Surprisal does not necessarily vanish when the learned model converges and may incentivize seeking transitions with the noisiest dynamics.

Abstract

from arXiv · show

Exploration in complex domains is a key challenge in reinforcement learning, especially for tasks with very sparse rewards. Recent successes in deep reinforcement learning have been achieved mostly using simple heuristic exploration strategies such as $ε$-greedy action selection or Gaussian control noise, but there are many tasks where these methods are insufficient to make any learning progress. Here, we consider more complex heuristics: efficient and scalable exploration strategies that maximize a notion of an agent's surprise about its experiences via intrinsic motivation. We propose to learn a model of the MDP transition probabilities concurrently with the policy, and to form intrinsic rewards that approximate the KL-divergence of the true transition probabilities from the learned model. One of our approximations results in using surprisal as intrinsic motivation, while the other gives the $k$-step learning progress. We show that our incentives enable agents to succeed in a wide range of environments with high-dimensional state spaces and very sparse rewards, including continuous control tasks and games in the Atari RAM domain, outperforming several other heuristic exploration techniques.

1 INTRODUCTION

The paper addresses exploration in continuous, high-dimensional environments where simple heuristics can fail under sparse rewards. It develops scalable surprise-based intrinsic rewards and evaluates them across diverse deep reinforcement learning tasks.

  • Poor exploration can prevent agents from finding rewards, while excessive exploitation can prematurely lock them into suboptimal behavior.
  • ϵ-greedy exploration and Gaussian control noise can be inadequate when rewards are especially sparse, as illustrated by failures on Montezuma’s Revenge.
  • Intrinsic motivation adds task-independent rewards based on concepts such as empowerment, surprise, or novelty alongside environmental rewards.
  • The paper models surprise as the KL-divergence between true and concurrently learned transition probabilities, approximated by surprisal or k-step learning progress.
  • The study investigates both incentives across many environments, evaluates sparse-reward continuous-control benchmarks, and introduces a complementary task.
  • The proposed incentives perform on the level of VIME while requiring lower computational cost.

2 PRELIMINARIES

The paper formulates reinforcement learning with Markov decision processes, policies, and finite-horizon return maximization. A policy selects action distributions conditioned on states.

  • An MDP is defined by states, actions, rewards, transition probabilities, and a starting-state distribution.
  • A policy is a distribution over actions for each state, with π(a|s) denoting the probability of selecting action a in state s.
  • The objective is to select a policy maximizing expected finite-horizon total return in this paper.

3 SURPRISE INCENTIVES

The method alternates dynamics-model and policy updates while using learned-model discrepancies to shape rewards for exploration. It derives surprisal and k-step learning-progress bonuses from surprise approximations.

  • Training alternates between updating a learned dynamics model and updating the policy using a performance–surprise trade-off.
  • The surprise incentive uses the on-policy KL-divergence between learned and true transition probabilities, which is higher in unfamiliar regions.
  • Because true transition probabilities are unknown, the ideal reward reshaping is approximated in practice.
  • Surprisal: Surprisal uses the negative log probability assigned by the learned model to the observed next state.
  • Learning progress: k-step learning progress compares transition-model log probabilities after and before k model updates.
  • Discussion: Surprisal may seek noisy transitions after model convergence, whereas learning progress should vanish as successive model estimates converge.
  • Discussion: The learning-progress bonus is related to Bayesian surprise, although its batch, non-Bayesian model update is only suggestively similar.
  • Algorithm: The algorithm collects rollouts, stores transitions in replay memory, computes and normalizes intrinsic rewards, updates the policy, and then updates the dynamics model.

4 EXPERIMENTS

The experiments evaluate surprise-based intrinsic rewards across sparse continuous-control and Atari RAM tasks, comparing them with naive exploration, other bonuses, and VIME. Surprisal is generally the most robust incentive, matching or exceeding VIME in several settings while requiring less computation.

  • Experimental setup: The evaluation covers sparse continuous-control tasks, the hierarchical SwimmerGather task, and Pong, BankHeist, Freeway, and Venture in Atari RAM.The benchmarks include both deterministic continuous-control dynamics and stochastic Atari RAM dynamics.
  • Continuous control results: TRPO without intrinsic rewards failed on all continuous-control tasks, while random exploration bonuses failed on most tasks.The median score and upper-quartile range for naive exploration were zero everywhere in the continuous-control evaluation.
  • Continuous control results: Surprisal achieved good results across all continuous-control domains and substantially exceeded other baselines on the more challenging tasks.Learning progress with k = 1 succeeded on CartpoleSwingup and HalfCheetah but faltered on other tasks, partly because the dynamics model converged prematurely or exploration was insufficient.
  • Continuous control results: Surprisal and learning progress with k = 1 solved HalfCheetah faster than reported VIME, while both were more susceptible to locally optimal policies on CartpoleSwingup.On SwimmerGather, surprisal performed comparably to VIME after 1000 iterations but showed greater variance.
  • Atari RAM domain results: In BankHeist, surprisal reached scores > 1000 10% sooner than naive exploration, while learning progress reached them almost 20% sooner.These results indicate faster learning under both intrinsic incentives in this Atari RAM task.
  • Atari RAM domain results: Surprisal was the most consistent incentive overall, improved exploration in difficult Atari tasks, and achieved a factor-of-3 per-iteration speedup over VIME.Its reward computation uses forward passes, while VIME computes separate backward passes for each transition tuple; the models also differ in complexity.

5 RELATED WORK

Prior exploration theory largely targets finite MDPs or continuous state spaces under additional structure, while deep-RL methods use learned dynamics and intrinsic incentives.

  • Finite-MDP exploration algorithms such as E3, R-max, and UCRL scale polynomially with MDP size but lack obvious extensions to continuous state and action spaces.
  • C-PACE provides a theoretical basis for PAC-optimal exploration with continuous states but requires a metric on the state space.
  • Deep-RL exploration methods differ in their learned dynamics models and intrinsic rewards, including deterministic Euclidean-loss models, stochastic cross-entropy models, and Bayesian dynamics models.

6 CONCLUSIONS

The paper defines surprise through divergence from a learned transition model and derives scalable intrinsic rewards. Experiments find surprisal especially effective across difficult deep-RL exploration benchmarks.

  • Surprise is formulated as the KL-divergence from true transition probabilities to learned model probabilities, approximated by surprisal and k-step learning progress.
  • The resulting incentives are scalable, computationally inexpensive, and suitable for high-dimensional and continuous control tasks.
  • Surprisal and 1-step learning progress enabled efficient exploration on several hard deep reinforcement learning benchmarks.
  • Surprisal was robust and effective, outperforming other heuristics across many tasks and remaining competitive with state-of-the-art intrinsic motivation in continuous control.
  • The optimization procedure uses local approximations, convexity assumptions, line searches, subsampled curvature estimates, and conjugate gradients instead of explicitly inverting large matrices.

B.1 ENVIRONMENTS

The experiments cover sparse-reward continuous-control environments and Atari RAM, using task-specific state and action spaces, reward conditions, preprocessing, and policy architectures.

  • The benchmark state dimensions range from 2 to 128, with continuous or discrete action spaces across MountainCar, CartpoleSwingup, HalfCheetah, Swimmer, SwimmerGather, and Atari RAM.
  • Sparse tasks provide rewards only at specified goal conditions, such as escaping MountainCar’s valley, raising the pole, reaching a body position, or crossing a swimmer threshold.
  • Atari RAM states are mapped from raw integer values in 0–256 to the interval (−1/3, 1/3).
  • Continuous-control policies use fully factored Gaussian distributions, while Atari RAM policies use categorical distributions, with network sizes varying by task.
  • Value functions combine neural networks for some tasks with time-varying linear functions for HalfCheetah, Swimmer, and SwimmerGather.
  • All neural networks are feed-forward, fully connected, and use tanh activation units.

B.3 TRPO HYPERPARAMETERS

The experiments fix common TRPO estimation settings and document the hyperparameter table used for training.

  • The MDP discount factor γ is fixed to 0.995 and the generalized advantage estimator parameter λ is fixed to 0.95 for all tasks.
  • Table 1 reports TRPO hyperparameters, including batch size and the subsample factor used for second-order optimization.

B.4 EXPLORATION HYPERPARAMETERS

The experiments use fully factored Gaussian dynamics models, with neural-network means and variances. Network size and several optimization hyperparameters vary across task families.

  • Fully factored Gaussian distributions model the dynamics, with neural networks outputting their means and variances.
  • Sparse MountainCar and CartpoleSwingup use single-hidden-layer networks with 32 units, while other tasks use two 64-unit hidden layers.All networks use tanh activations.
  • Replay memories contain 5,000,000 entries for continuous-control tasks and 1,000,000 for Atari RAM tasks.The KL-divergence step size is κ = 0.001 for most continuous-control tasks, κ = 0.005 for SwimmerGather, and κ = 0.01 for Atari RAM.
  • Each dynamics-learning iteration samples 5,000 replay experiences, or 10,000 for SwimmerGather and Venture.The optimizer subsample factor is 1 for most tasks and 0.5 for SwimmerGather and Venture.
  • The L2 penalty coefficient is α = 1 for continuous control, α = 0.01 for most Atari RAM tasks, and α = 0.1 for Venture.
  • The η0 setting is 0.001 for most continuous-control tasks, 0.0001 for SwimmerGather, and 0.005 for Atari RAM.

C ANALYSIS OF SPEEDUP COMPARED TO VIME

The analysis compares the computational costs of the proposed bonuses with VIME, separating dynamics-model fitting from reward computation. Although fitting times were nearly equivalent in a speed test, the proposed bonus achieved an approximately twofold asymptotic speedup per available parallel group and a measured factor-of-three per-iteration speedup.

  • The analysis separates two costs for learned-dynamics bonuses: fitting the dynamics model and computing rewards.
  • The proposed method's dynamics-model fitting time was nearly equivalent to VIME's in the speed test, despite using different fitting algorithms.The comparison notes that VIME uses a more complex Bayesian neural-network dynamics model, while the proposed model is simpler.
  • Reward-computation cost depends on CPU threads, forward and backward pass times, batch size, and the number of simultaneous forward passes.These quantities are denoted n, tf, tb, N, and k, respectively.
  • VIME requires separate forward/backward passes for each transition because current deep-learning toolkits cannot efficiently parallelize its gradient calculations.
  • In the large-N limit with tf ≈ tb, the proposed method achieves an asymptotic speedup of approximately 2k over VIME.
  • The speedup analysis relies on a publication-time statement whose correctness the authors invite readers to verify.
Loading 1703.01732v1…