PaperlayerView exact revision on arXiv

Source-linked AI summary

Discovering Reinforcement Learning Algorithms

Junhyuk Oh, Matteo Hessel, Wojciech M. Czarnecki, Zhongwen Xu, Hado van Hasselt, Satinder Singh, David Silver

arXiv:2007.08794v3cs.LGcs.AI

TL;DR

RL research has not established whether fundamental concepts such as value functions and temporal-difference learning can be discovered from data. This paper meta-learns LPG, an entire update rule that jointly discovers what to predict and how to use predictions; it discovers value-like predictions and bootstrapping, then generalises from toy environments to complex Atari games.

  • Problem

    It remains an open question whether RL can discover fundamental concepts such as value functions and temporal-difference learning entirely from scratch.

  • Method

    LPG meta-learns an entire RL update rule across environments, jointly discovering what the agent should predict and how to use those predictions for policy improvement.

  • Results

    LPG discovers predictions converging toward a value-function encoding, maintains them through bootstrapping, and generalises from toy environments to complex Atari games.

  • Takeaways & Limitations

    The results suggest that general RL algorithms may be discoverable directly from environment interactions rather than designed entirely by hand.

  • Takeaways & Limitations

    Unlike temporal-difference learning in tabular settings, LPG has no convergence guarantee because its prediction semantics are meta-learned solely to improve agent performance.

Abstract

from arXiv · show

Reinforcement learning (RL) algorithms update an agent's parameters according to one of several possible rules, discovered manually through years of research. Automating the discovery of update rules from data could lead to more efficient algorithms, or algorithms that are better adapted to specific environments. Although there have been prior attempts at addressing this significant scientific challenge, it remains an open question whether it is feasible to discover alternatives to fundamental concepts of RL such as value functions and temporal-difference learning. This paper introduces a new meta-learning approach that discovers an entire update rule which includes both 'what to predict' (e.g. value functions) and 'how to learn from it' (e.g. bootstrapping) by interacting with a set of environments. The output of this method is an RL algorithm that we call Learned Policy Gradient (LPG). Empirical results show that our method discovers its own alternative to the concept of value functions. Furthermore it discovers a bootstrapping mechanism to maintain and use its predictions. Surprisingly, when trained solely on toy environments, LPG generalises effectively to complex Atari games and achieves non-trivial performance. This shows the potential to discover general RL algorithms from data.

1 Introduction

The paper asks whether RL can discover fundamental concepts such as value functions from data, and introduces LPG to jointly learn what to predict and how to use predictions. LPG discovers useful prediction functions, bootstrapping, and generalises from toy environments to complex Atari games.

  • 1 Introduction: The paper addresses whether fundamental RL concepts, including value functions, can be discovered entirely from scratch.The challenge involves learning both what to predict and how predictions affect policy updates over multiple learning steps.
  • 1 Introduction: LPG jointly discovers what an agent should predict and how to use those predictions for policy improvement across multiple environments.Its meta-learner imposes no semantics on the agent’s vector-valued outputs and determines their predictive role.
  • 1 Introduction: LPG discovers useful functions, uses them to update policies, and learns prediction semantics that converge toward value functions maintained through bootstrapping.These findings support discovery of both predictive content and a mechanism for using predictions.
  • 1 Introduction: LPG trained only on a small set of toy environments generalises to complex Atari games and achieves competitive performance with human-designed algorithms.The paper presents this as evidence that an entire RL update rule can be discovered from toy-domain interactions.

2 Related Work

Prior work meta-learned components such as update rules, objectives, rewards, and exploration, but generally remained within related task domains. LPG instead targets an update rule that discovers its own bootstrapping mechanism and supports radical generalisation across domains.

  • 2 Related Work: Earlier learning-to-learn research learned optimisation procedures, update rules, learning-rate adaptations, self-modifying networks, and domain-invariant knowledge.These studies established that meta-learning can improve how objectives are optimised, not only optimise fixed objectives.
  • 2 Related Work: Meta-learning for RL has addressed discount factors, intrinsic rewards, auxiliary tasks, returns, policy updates, off-policy corrections, and update targets.These approaches typically focus on algorithmic components rather than discovering a complete RL update rule.
  • 2 Related Work: Prior RL-algorithm discovery methods include evolutionary policy updates, learned exploration rewards, and meta-learned loss functions, but generally generalise only to similar tasks within one domain.MetaGenRL is identified as an exception, though it targets continuous control and is based on DDPG.
  • 2 Related Work: Unlike approaches that supply a value function or learn only policy updates, LPG meta-learns its own bootstrapping mechanism while targeting generalisation across different domains.The paper reports radical generalisation from toy environments to a challenging benchmark as a distinguishing result.

3 Meta-Learning Framework for Learned Policy Gradient

The framework meta-learns an environment-agnostic Learned Policy Gradient update rule that jointly discovers what agents should predict and how predictions improve policies. It adapts training across environments through agent updates, regularisation, and environment-specific hyperparameter sampling.

  • 3 Meta-Learning Framework for Learned Policy Gradient: LPG meta-learns an update rule that determines both the agent’s prediction targets and how those predictions drive policy improvement.The framework optimises the update rule across agents interacting with different environments, without enforcing semantics on the prediction vector.
  • 3.1 LPG Architecture: The backward LSTM receives rewards, termination indicators, discounting, action probabilities, and consecutive predictions, then outputs policy and prediction updates.Because it uses the probability of the chosen action rather than observation or action representations, LPG is invariant to observation and action spaces.
  • 3.2 Agent Update (θ): Predictions affect policy behaviour only after LPG discovers useful semantics for them, such as a value function, and uses them through bootstrapping.This indirect pathway makes discovering prediction semantics challenging because predictions initially have no direct policy effect.
  • 3 Meta-Learning Framework for Learned Policy Gradient: Meta-training updates LPG by differentiating final-lifetime returns through repeated agent updates, using truncated backpropagation when full unrolling is impractical.The procedure applies the learned rule for N updates in principle, but computes meta-gradients over a smaller sliding window of K < N updates in practice.
  • 3.3 LPG Update (η): Entropy and L2 regularisers stabilise discovery by discouraging deterministic predictions and overly aggressive policy or prediction updates.These regularisers are applied to LPG’s outputs rather than directly to the agent, shaping the resulting update rule.
  • 3.4 Balancing Agent Hyperparameters for Stabilisation (α): Environment-specific bandit sampling of learning-rate and prediction-update hyperparameters reduces conflicting meta-gradients across environments.The sampling distribution adapts from lifetime returns during meta-training, balancing hyperparameters across environments while keeping LPG itself environment-agnostic.

4 Experiment

Experiments test LPG’s discovered prediction semantics, training stability, ablations, and generalisation from toy environments to Atari games. LPG often outperforms A2C on training environments, discovers value-like bootstrapped predictions, and transfers to complex games despite lacking theoretical convergence guarantees.

  • 4.2 Specialising in Training Environments: LPG outperforms A2C on most training environments, while LPG-V is much worse than LPG and not clearly better than A2C.This supports discovering prediction semantics rather than only a policy update rule.
  • 4.3 Analysis of Learned Policy Gradient: Predictions propagate around rewarding states like true values, indicating that LPG predicts future rewards and uses them for bootstrapping.The analysis fixes policy parameters and updates only y, analogous to policy evaluation.
  • 4.3 Analysis of Learned Policy Gradient: Value regression from y is almost as good as TD(λ) at discount factor 0.995 and captures true values at lower discount factors that scalar TD(λ) values miss.The regression uses predictions generated at discount factor 0.995 and is evaluated on held-out grid worlds.
  • 4.3 Analysis of Learned Policy Gradient: Two independently initialised prediction vectors converge to almost the same values, although LPG has no theoretical convergence guarantee.The convergence analysis averages D_KL(y0||y1) over 128 grid-world instances.
  • 4.4 Ablation Study: Removing entropy or L2 regularisation, or fixing hyperparameters per environment, makes meta-training unstable; LPG-V remains stable but converges to a sub-optimal rule.The ablation attributes LPG’s better eventual rule to discovering what to predict, at the cost of harder optimisation.
  • 4.5 Generalising from Toy Environments to Atari Games: Trained only on toy environments, LPG achieves super-human performance on 14 Atari games, while delayed-chain training environments significantly improve generalisation.LPG remains behind advanced RL algorithms overall, but outperforms A2C on some Atari games and improves as the number of training environments grows.

5 Conclusion

The paper presents LPG as a full RL update rule that jointly discovers what to predict and how to bootstrap. Results on toy environments show rich predictions and generalisation to Atari games.

  • LPG jointly discovers what to predict and how to bootstrap, replacing existing RL concepts such as value functions and TD-learning.
  • Training on a small set of toy environments produced predictions containing rich information that was crucial for efficient bootstrapping.
  • LPG’s radical generalisation from toy domains to Atari games suggests that efficient RL algorithms may be discoverable from interaction data.

Broader Impact

The proposed approach could automate parts of RL algorithm discovery and assist researchers developing hand-designed algorithms. Its data-driven nature may also capture unintended bias from training environments.

  • Automating RL algorithm discovery could shift research toward constructing environments that produce efficient algorithms instead of manually designing update rules.
  • The approach can provide insights into good update rules for a supplied architecture, potentially helping researchers improve hand-designed algorithms.
  • Because discovery is data-driven, the resulting algorithm may capture unintended bias present in the training environments.

A Training Environments

The tabular grid-world environments randomise object locations between lifetimes while representing agents with tabular policy and prediction values. Episodes use object-dependent rewards, termination, respawn, and alternative action spaces.

  • Object collection gives a corresponding reward, may terminate the episode with object-specific probability, and removes the object until possible respawn.
  • Each state is represented tabularly with distinct π(a|s) and y(s) values, while randomised object locations yield p × 2m possible states per lifetime.
  • Training samples either nine movement actions plus nine collection actions or nine movement actions with automatic collection.

A.1.1 Dense

The dense grid-world configurations vary action count, grid size, object specifications, and episode length. One configuration permits longer episodes and more object types than the other.

  • The first configuration uses 9 or 18 actions, an 11 × 11 grid, three object types, and a 500-step episode limit.
  • The second configuration uses 9 or 18 actions, a 13 × 13 grid, two object types, and a 50-step episode limit.

A.1.3 Long Horizon

The long-horizon environments vary episode lengths, observation structures, and reward noise to test whether agents can learn delayed consequences while filtering irrelevant information.

  • The grid-world configurations vary object counts, board sizes, reward values, and episode limits, including horizons up to 2000 steps.
  • Random grid worlds randomise object locations each episode and after collection, creating exponentially large state spaces that require function approximation.
  • Delayed-chain tasks randomise chain lengths from 5–30 or 5–50 steps, with separate noisy- and noise-free reward variants.
  • In delayed-chain MDPs, observations contain two task-relevant bits alongside 20 independently sampled noisy bits.

B.1 Meta-Training

Meta-training uses many parallel agent lifetimes and a recurrent LPG update rule, with stability mechanisms and Atari validation guiding the final configuration.

  • Meta-training simulated 960 parallel lifetimes, while each agent update used trajectories from 64 parallel environments with 20 steps per trajectory.
  • The LPG network processes rewards, termination indicators, discount factors, action probabilities, and consecutive predictions through a shared embedding and backward LSTM.
  • A2C supplied the meta-gradient in practice, while value functions served only to reduce meta-gradient variance and were unavailable to LPG itself.
  • A bandit sampled agent hyperparameters using recent lifetime returns and an exploration bonus to improve meta-training stability.
  • Training resets a lifetime when policy entropy reaches zero, preventing early deterministic divergence and exploding meta-gradients.
  • LPG was selected using validation on Breakout and Boxing, then evaluated across all 57 Atari games with learning curves reporting episode return over frames.
Loading 2007.08794v3…