PaperlayerView exact revision on arXiv

Source-linked AI summary

Meta-learning of Sequential Strategies

Pedro A. Ortega, Jane X. Wang, Mark Rowland, Tim Genewein, Zeb Kurth-Nelson, Razvan Pascanu, Nicolas Heess, Joel Veness, Alex Pritzel, Pablo Sprechmann, Siddhant M. Jayakumar, Tom McGrath, Kevin Miller, Mohammad Azar, Ian Osband, Neil Rabinowitz, András György, Silvia Chiappa, Simon Osindero, Yee Whye Teh, Hado van Hasselt, Nando de Freitas, Matthew Botvinick, Shane Legg

arXiv:1905.03030v2cs.LGcs.AIstat.ML

TL;DR

The report asks how memory-based meta-learning can build sample-efficient strategies that adapt across tasks without requiring explicit probabilistic inference. It presents templates and a Bayesian account of how these strategies operate, while noting the demands of meta-training and the assumptions behind its analysis.

  • Problem

    Model-free reinforcement-learning algorithms are sample-inefficient, while full probabilistic model-based approaches can be unwieldy because models may be hand-crafted or exact posteriors intractable.

    Source: B. Sample complexity of strategies · p. 10

  • Method

    The report presents memory-based meta-learning templates for predictors, Thompson samplers, and Bayes-optimal agents, interpreting their memory as implementing Bayesian sufficient statistics.

    Source: §I · p. 2, F. Conclusions · p. 12

  • Results

    Meta-learning finds sequential algorithms that perform near-optimally and minimize test-time sample complexity, though meta-training can be expensive.

    Source: B. Sample complexity of strategies · p. 10

  • Takeaways & Limitations

    Memory-based meta-learning turns probabilistic inference into regression by preconditioning a learning system on trajectories from a broad task class.

    Source: F. Conclusions · p. 12

    The analysis assumes the meta-learning objective's minimizer is found, a strong assumption; strategy complexity can grow exponentially with trajectory length when invariances are absent.

    Source: D. Capacity limitations · p. 11

Abstract

from arXiv · show

In this report we review memory-based meta-learning as a tool for building sample-efficient strategies that learn from past experience to adapt to any task within a target class. Our goal is to equip the reader with the conceptual foundations of this tool for building new, scalable agents that operate on broad domains. To do so, we present basic algorithmic templates for building near-optimal predictors and reinforcement learners which behave as if they had a probabilistic model that allowed them to efficiently exploit task structure. Furthermore, we recast memory-based meta-learning within a Bayesian framework, showing that the meta-learned strategies are near-optimal because they amortize Bayes-filtered data, where the adaptation is implemented in the memory dynamics as a state-machine of sufficient statistics. Essentially, memory-based meta-learning translates the hard problem of probabilistic sequential inference into a regression problem.

I. INTRODUCTION

The report examines memory-based meta-learning as a way to learn sequential strategies from task experience, then frames their behavior through Bayesian inference. It introduces sequential prediction as a foundation and specifies a finite-observation setup.

I. INTRODUCTION

  • Meta-learning trains across a task distribution so systems acquire inductive biases that help them adapt efficiently and generalize to new tasks.The report focuses on memory-based methods that learn sequential strategies from experience.Source: §I · p. 1
  • Memory-based meta-learning can behave as if it had a probabilistic model by regressing strategies on samples implicitly filtered according to Bayes rule.The strategy's memory dynamics track Bayesian sufficient statistics; Bayesian updates need not be computed explicitly.Source: §I · pp. 1–2

II. SEQUENTIAL PREDICTION

  • The report reviews sequential prediction before sequential decision-making, using prediction to ground later analyses of Thompson sampling and Bayes-optimal agents.It also discusses scaling, applications, Bayesian connections, and future challenges.Source: §I · p. 2, §II · p. 2
  • In sequence prediction, inductive biases help narrow possible explanations and judge their plausibility; meta-learning can capture relevant data statistics through exposure to varied tasks.The report first reviews Bayesian prediction, then numerical approximation of that strategy through meta-learning.Source: §II · p. 2

A. Problem setup

  • The setup generates trajectories from a class of generators, with a loss specifying the task and encouraging the system to consider those generators as hypotheses.The analysis limits observations to finite spaces and discrete time; continuous domains typically require additional geometric assumptions beyond the report's scope.Source: A. Problem setup · p. 2, 1) Sequences · p. 2

1) Sequences:

  • Sequences are strings over a finite observation alphabet, with time indices used for symbols and substrings.The notation also uses x<t for the observations preceding time t.Source: 1) Sequences · p. 2

2) Generators/Hypotheses:

The setup represents possible ground truths as generators and assigns them prior probabilities. Strategies are evaluated by expected loss over trajectories produced by a prior-sampled hypothesis.

2) Generators/Hypotheses:

  • A hypothesis is a distribution over infinite observation sequences specified by the conditional probability of each next symbol given the past.The class of generators is denoted P, and defining the conditionals determines the sequence distribution.Source: 2) Generators/Hypotheses · p. 3
  • A prior over the parameterized generators expresses the inductive bias, assigning more prior mass to simpler hypotheses.The report illustrates the setup with dice-roll prediction and a uniform prior, and with an algorithmic prior over programs.Source: 2) Generators/Hypotheses · p. 3

3) Strategies:

  • A strategy is the system's output distribution over sequences, with π(xt|x<t) denoting its prediction of the next symbol from the past.The available candidate strategies are denoted Π.Source: 3) Strategies · p. 3

4) Losses:

  • A loss maps a strategy and trajectory to a real-valued cost; prediction can use log-loss, while decision-making can use negative discounted cumulative reward.The objective minimizes expected trajectory loss when the generating hypothesis is sampled from the prior, assuming the true distribution belongs to the hypothesis class.Source: 4) Losses · p. 3, 5) Goal · p. 3

B. Universality: Bayesian answer

The Bayesian mixture predicts by weighting hypotheses according to their prior probabilities and updating those weights with observed data. Its predictions converge to the true distribution, and average excess compression loss decreases at an O(1/t) rate depending on the task-prior.

B. Universality: Bayesian answer

  • The mixture predictor is adaptive: it averages hypotheses using posterior probabilities updated by the observed past.The prior probabilities supply the initial inductive biases.Source: B. Universality: Bayesian answer · p. 4
  • With more data, Bayesian predictions converge almost surely to the true distribution.The average excess compression loss, or regret, converges to zero at O(1/t), depending on the task-prior.Source: B. Universality: Bayesian answer · p. 4
  • The posterior distribution over hypotheses need not converge in general.Posterior convergence requires stricter conditions.Source: B. Universality: Bayesian answer · p. 4
  • Minimizing expected log-loss over trajectory distributions yields the Bayesian mixture as the cross-entropy minimizer.The chosen loss is ℓ(π; τ) = −log π(τ).Source: B. Universality: Bayesian answer · p. 4

C. Universality: meta-learning answer

Memory-based meta-learning trains a sequential predictor by regressing on trajectories sampled from task generators, implicitly marginalizing over their parameters. Under the stated realizability and sample-size conditions, the resulting predictor amortizes Bayesian updating in its memory dynamics.

C. Universality: meta-learning answer

  • Because loss depends on trajectories rather than generator parameters, the Monte Carlo objective implicitly marginalizes over generators.The computation graph depicts this trajectory-based objective.Source: C. Universality: meta-learning answer · p. 4, Figure 1 · p. 5
  • Sequential prediction requires a causal interface that maps each history to a prediction of the next observation.A memory-based architecture can implement this interface using the preceding observation and memory state.Source: C. Universality: meta-learning answer · pp. 4–5
  • The report flags approximation quality as dependent on the learning model, including whether the optimum is realizable and the model’s smoothness near it.Realizability means the Monte Carlo loss minimizer belongs to the function class.Source: C. Universality: meta-learning answer · pp. 4–5
  • With a realizable minimizer and sufficiently large N, the learned function implements optimal sequential prediction with Bayesian updating amortized in its recursive memory.The report notes that approximation quality depends on the learning model and its smoothness near the optimum.Source: C. Universality: meta-learning answer · pp. 4–5

D. Anatomy of meta-learned agents

A meta-learned agent can be viewed as a state machine: its memory summarizes past inputs, transitions update that memory, and outputs are predictions. The objective does not require a minimal state machine, and generalization matters for transitions not seen in training.

D. Anatomy of meta-learned agents

  • The construction depends on the loss, the agent’s functional interface, and Monte Carlo marginalization over generators.With a fixed initial state, hiding generator identity leads to a numerical approximation of amortized Bayesian estimators.Source: D. Anatomy of meta-learned agents · p. 6
  • The agent’s recursive function updates memory from the latest input and prior state, producing predictions while memory serves as a sufficient statistic of the past.The state machine’s transitions are input-driven, and its outputs are predictions.Source: D. Anatomy of meta-learned agents · p. 6
  • The training objective does not enforce state-machine minimality, and performance on unseen transitions depends on generalization, especially for sequences longer than training rollouts.Different initial conditions can also produce different state machines.Source: D. Anatomy of meta-learned agents · pp. 6–7
  • For exchangeable sequences, a minimal state machine has a lattice structure; in the coin example, states record observed Heads and Tails.Figure 3 marks Head and Tail transitions differently and displays predictions from each state.Source: Figure 3 · p. 6, D. Anatomy of meta-learned agents · p. 7

III. SEQUENTIAL DECISION-MAKING

Sequential decision-making meta-learning must address the absence of an optimal policy for generating training trajectories. The Thompson-sampling approach uses expert actions as teaching signals, while the learned agent acts according to its own policy.

III. SEQUENTIAL DECISION-MAKING

  • Because the optimal policy is unavailable for generating trajectories, meta-learning must interleave amortization over task generators with policy improvement toward the optimal policy.This is the additional difficulty that distinguishes decision-making from sequential prediction.Source: §III · p. 7

A. Thompson sampling

  • Thompson-sampling meta-training turns reinforcement learning into inference when expert policies are known, by regressing expert actions with cross-entropy on agent-generated trajectories.The agent samples actions from its own policy, while expert policies provide the loss signal; this requires access to the ground-truth optimal policy for each environment.Source: A. Thompson sampling · pp. 7–8
  • Updating the posterior after every step can produce unstable policies; updating only after longer sequences, such as an episode, is offered as an alternative.The concern is that the expert policy may change at each time step.Source: A. Thompson sampling · p. 8

B. Bayes-Optimality

The Bayes-optimal approach learns action-values for a reward-based objective rather than regressing expert actions. It uses temporal-difference targets and annealed policy improvement to approach a task-distribution-specific optimal policy.

B. Bayes-Optimality

  • A Bayes-optimal policy maximizes expected cumulative future reward through dynamic programming, a harder objective than learning a Thompson-sampling strategy.The section switches from log-loss to reward and defines the global optimal policy for the given task distribution.Source: B. Bayes-Optimality · pp. 8–9
  • Because the optimal policy is unknown during training, trajectories come from the interaction of task generators with a custom policy, and action-values are one of several possible ways to infer the optimum.The resulting global policy is tailored to the task distribution.Source: B. Bayes-Optimality · pp. 8–9
  • Action-values can be amortized with a temporal-difference loss whose target adds the current reward to the next action-value and is held constant.This propagates boundary conditions backward in time; the report assumes undiscounted rewards for simplicity.Source: B. Bayes-Optimality · p. 9
  • Simulated annealing cools the softmax inverse temperature from zero toward a large value, allowing suboptimal branches to be sampled before the policy becomes nearly deterministic.The cooling schedule is typically determined empirically.Source: B. Bayes-Optimality · p. 9

A. Meta-learning and Bayesian statistics

Meta-learning trajectories are implicitly Bayes-filtered: from the system’s perspective, each next sample follows the posterior predictive distribution. Memory-based methods use this property to learn adaptive strategies.

A. Meta-learning and Bayesian statistics

  • Given the past, generated transitions look as though they were sampled from the Bayesian posterior predictive distribution.This induces an implicit update of the hypothesis.Source: A. Meta-learning and Bayesian statistics · p. 10
  • Meta-learning harvests this implicit Bayes filtering: sequential prediction regresses sample statistics, while decision-makers use the filtration to build adaptive policies.The samples are filtered according to Bayes’ rule by the trajectory-generating process.Source: A. Meta-learning and Bayesian statistics · p. 10
  • Generating Bayes-filtered samples is also a rationale behind practical Bayesian-model implementations and Monte-Carlo methods for Bayes-optimal planning.Source: A. Meta-learning and Bayesian statistics · p. 10

B. Sample complexity of strategies

The report frames meta-learning as a way to synthesize reinforcement-learning strategies tailored to a task class, while noting that meta-training can be expensive.

B. Sample complexity of strategies

  • Model-free reinforcement-learning algorithms are sample-inefficient, while full probabilistic approaches can be unwieldy and have had limited success scaling in deep reinforcement learning.The difficulties include hand-crafted models with little structure and intractable exact posteriors.Source: B. Sample complexity of strategies · p. 10
  • Meta-learning searches algorithm space for strategies tailored to a task class, and the reported examples perform near-optimally by minimizing expected loss across generators.The report links this objective to minimizing test-time sample complexity.Source: B. Sample complexity of strategies · p. 10
  • Meta-training can be expensive because Monte-Carlo approximations converge slowly and current popular neural architectures require large amounts of training data.Source: B. Sample complexity of strategies · p. 10

C. Spontaneous meta-learning

Spontaneous meta-learning can arise when an online learner processes trajectories segmented by recurring memory states; the strategy’s complexity also depends on task structure and the learner’s capacity.

C. Spontaneous meta-learning

  • Spontaneous meta-learning can emerge in bounded-capacity online regression with data from a single generator, but what is learned is difficult to control and may include undesirable properties.Source: C. Spontaneous meta-learning · p. 10
  • Finite agent and generator state spaces ensure a recurrent memory state that segments observations into variable-length trajectories, each assigned the generator’s state at its start.The dynamics are assumed deterministic, with stochastic dynamics modeled using pseudorandom transitions.Source: C. Spontaneous meta-learning · p. 10
  • With a sufficiently large past-data window, an online learner effectively batch-updates from trajectories sampled by different generators, thereby performing meta-learning.The analysis assumes the solution is the meta-learning objective’s minimizer, a strong assumption; practical difficulty finding a near-optimal solution depends on several factors.Source: C. Spontaneous meta-learning · p. 10, D. Capacity limitations · p. 11

D. Capacity limitations

  • Finding a near-optimal solution depends on the regression model, including its inductive biases, loss-landscape smoothness, optimizer, and memory capacity.Source: D. Capacity limitations · p. 11
  • Task-class invariances reduce the mappings from past experience to strategies that must be learned; without invariances, their number can grow exponentially with maximum trajectory length T.Source: D. Capacity limitations · p. 11

E. Selected future challenges

The report identifies task structure, risk sensitivity, and continual learning as open challenges, while presenting memory-based meta-learning as a route from probabilistic inference to learned sequential strategies. Its conclusions connect Bayesian filtering to memory dynamics and identify future scope boundaries.

E. Selected future challenges

  • Task design must connect desired capabilities to properties of task classes, while a rigorous language for task structure, sufficient statistics, and task-class similarity remains lacking.An example is designing generators for out-of-distribution generalization and performance beyond sampled trajectory lengths.Source: E. Selected future challenges · p. 11
  • Expected-loss training ignores higher-order loss moments and can yield risk-insensitive strategies that are brittle under model uncertainty; changing the certainty-equivalent or generator prior offers a risk-sensitive direction.The report also notes that games may require simultaneous meta-training of multiple agents to find equilibrium strategies.Source: E. Selected future challenges · p. 11
  • Continual learning could be framed around recovery speed rather than zero-shot transfer, but non-i.i.d. task sequences make practical learning unclear, and changing task distributions remains underexplored.Source: E. Selected future challenges · pp. 11–12

F. Conclusions

  • Memory-based meta-learning offers three templates—predictors, Thompson samplers, and Bayes-optimal agents—that turn probabilistic inference into regression by training on trajectories from a task distribution.With enough data and computation, a slow learner may learn an entire reasoning procedure, not only an environmental model.Source: F. Conclusions · p. 12
  • Meta-learned strategies are near-optimal by construction because training uses a Monte Carlo approximation of expected cost over hypotheses; Bayes-filtered data is amortized in memory dynamics that encode sufficient statistics.The transition graph also encodes task-distribution symmetries: paths with the same initial and final information states are equivalent for modulating future behavior.Source: F. Conclusions · p. 12
  • Unlike one-shot meta-learning without memory, sequential meta-learning also produces an update rule; task structure, out-of-distribution generalization, and continual learning remain challenges.Some challenges may be addressed through training-process changes and hypothesis classes with special properties.Source: F. Conclusions · p. 12

Related papers

Loading 1905.03030v2…