PaperlayerView exact revision on arXiv

Source-linked AI summary

An investigation of model-free planning

Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sébastien Racanière, Théophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, Greg Wayne, David Silver, Timothy Lillicrap

arXiv:1901.03559v2cs.LGcs.AIstat.ML

TL;DR

The paper examines whether model-free RL can learn planning behavior without explicit models or planning-specific network structure. It trains flexible neural networks and finds planning-like behavior across generalization, data efficiency, and added thinking time. The authors conclude that model-free planning may apply to combinatorial domains, while its effectiveness in real-world complexity remains open.

  • Problem

    Comprehensive demonstrations are still missing of whether general recurrent architectures can learn model-based behavior without planning-specific structure.

    Source: §1 · p. 1

  • Method

    The paper trains high-capacity, flexible neural networks with standard model-free RL, without a planning-specific inductive bias.

    Source: §1 · p. 1, §2.1.1 · p. 2

  • Results

    The agent achieves state-of-the-art performance in combinatorial domains, generalizes to harder problems, performs well with limited data, and solves more Sokoban problems with additional thinking time.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results suggest high-capacity general-purpose networks can learn domain-tailored approximate planning, with additional thinking time boosting performance.

    Source: §5 · pp. 7–8

    Whether model-free planning works in reinforcement-learning environments of real-world complexity remains unknown.

    Source: §5 · p. 8

Abstract

from arXiv · show

The field of reinforcement learning (RL) is facing increasingly challenging domains with combinatorial complexity. For an RL agent to address these challenges, it is essential that it can plan effectively. Prior work has typically utilized an explicit model of the environment, combined with a specific planning algorithm (such as tree search). More recently, a new family of methods have been proposed that learn how to plan, by providing the structure for planning via an inductive bias in the function approximator (such as a tree structured neural network), trained end-to-end by a model-free RL algorithm. In this paper, we go even further, and demonstrate empirically that an entirely model-free approach, without special structure beyond standard neural network components such as convolutional networks and LSTMs, can learn to exhibit many of the characteristics typically associated with a model-based planner. We measure our agent's effectiveness at planning in terms of its ability to generalize across a combinatorial and irreversible state space, its data efficiency, and its ability to utilize additional thinking time. We find that our agent has many of the characteristics that one might expect to find in a planning algorithm. Furthermore, it exceeds the state-of-the-art in challenging combinatorial domains such as Sokoban and outperforms other model-free approaches that utilize strong inductive biases toward planning.

1. Introduction

The paper asks whether general-purpose networks trained with model-free RL can plan without explicit models or planning-specific structure. It evaluates planning through generalization, data efficiency, and use of additional thinking time.

1. Introduction

  • Prior model-based RL learns environment dynamics before planning, while newer model-free approaches encode planning structures such as search trees or dynamic programming.The paper positions its approach beyond both explicit models and model-free architectures that mirror particular planning algorithms.Source: §1 · p. 1
  • The paper tests whether planning can emerge implicitly in a high-capacity neural network without a planning-specific inductive bias.Earlier work supported model-based behavior in general recurrent architectures, but comprehensive demonstrations of its effectiveness were still missing.Source: §1 · p. 1
  • The authors assess planning behavior through generalization, learning from relatively little data, and improved performance with additional thinking time.Extra thinking time is tested in Sokoban before the agent commits to a strategy, where wrong decisions can have irreversible consequences.Source: §1 · p. 2
  • The model-free agent achieves state-of-the-art performance in combinatorial domains, generalizes to harder problems, performs well with limited training data, and solves more Sokoban problems with extra thinking time.The harder-problem results are especially effective with larger networks.Source: §1 · p. 2
  • The results suggest that model-free agents without planning-specific network structure can exhibit many behavioral characteristics associated with planning.The authors hope these findings broaden the search for architectures that can address a wider range of planning domains.Source: §1 · p. 2

2. Methods

The methods use flexible neural architectures and standard model-free RL to learn planning behavior. The core network repeatedly applies stacked ConvLSTM modules, with convolutional encoding and an MLP for policy and value outputs.

2.1. Model architectures

  • The architecture uses high-capacity CNNs and LSTMs with common inductive biases, rather than encoding a particular planning algorithm.The authors rely on model-free RL to discover whether these flexible networks can learn to plan.Source: §2.1 · p. 2

2.1.1. BASIC ARCHITECTURE

  • The DRC network stacks ConvLSTM modules and repeats their computation N times per time-step, with unshared weights across stack depth.Each ConvLSTM has a 3D hidden state and convolutional operations; the recurrent state contains each module’s cell state and output.Source: §2.1.1 · pp. 2–3
  • A convolutional encoder feeds the recurrent network, whose output is combined with the encoded input before an MLP produces policy and value estimates.The recurrent elements preserve the input’s spatial dimensions, and the final recurrent output comes from the deepest module after N ticks.Source: §2.1.1 · p. 3

2.1.2. ADDITIONAL DETAILS

  • Additional design choices include encoded-observation and top-down skip connections, pooled lateral inputs, and boundary feature maps for convolutions.Pooling helps information propagate faster across spatial dimensions; the authors describe these choices as nonessential but marginally beneficial.Source: §2.1.2 · p. 3

2.2. Reinforcement Learning

  • The agent outputs a policy and value estimate and is trained with actor-critic updates using truncated, bootstrapped returns and off-policy importance corrections.The experiments use IMPALA V-trace; the architecture was also trained effectively with A3C.Source: §2.2 · p. 3

3. Planning Domains

The paper evaluates agents in procedurally generated, combinatorial RL domains, where episode configurations vary and memorizing observation-to-action mappings is insufficient. The domains include navigation, box-pushing, key-and-box planning, and maze exploration.

3. Planning Domains

  • Procedural configurations in combinatorial domains emphasize planning and generalization because a fixed observation-to-action mapping cannot simply be memorized.Most domains are fully observable with simple 2D visual features; Atari games serve as control experiments.Source: §3 · p. 4
  • Gridworld tests navigation through obstacles with the agent, goal, and obstacles placed randomly in each episode.Source: §3 · p. 4
  • Sokoban requires pushing boxes onto goals, and irreversible wrong moves can make levels unsolvable.Levels are generated for 10x10 boards with four boxes and grouped into unfiltered, medium, and hard difficulty sets.Source: §3 · p. 4
  • In Boxworld, agents must choose a sequence of colored boxes to open so they collect keys that lead to the target.Keys are visible inside boxes and can be used only once, so opening an incorrect box can create an unrecoverable dead end.Source: §3 · p. 4
  • MiniPacman tests maze exploration, requiring the player to collect food while pursued by ghosts and using power pills to attack them briefly.Power pills can yield a large reward.Source: §3 · p. 4

4. Results

Across tested domains, DRC performed strongly with modest hyperparameter tuning, and DRC(3,3) was almost always best in learning efficiency and asymptotic performance. The results examine benchmark comparisons, architecture, data efficiency and generalization, and iterative computation.

4.1. Performance & Comparisons

  • On 32×32 Gridworld, VIN improved faster early in training, but DRC reached better final accuracy; DRC also learned more efficiently than a similar-capacity CNN on larger grids.VIN has fewer parameters and a well-matched inductive bias for this setting.Source: §4.1 · p. 4, Table 1 · p. 5
  • 1% of unfiltered Sokoban test levels remained unsolved by DRC(3,3) after 1e9 steps; the second-best large ResNet left four times as many unsolved.The comparison covers methods evaluated on test performance in unfiltered Sokoban.Source: Table 2 · p. 5, §4.1 · p. 5
  • ≈80% success after 2e8 steps in Boxworld exceeded the best ResNet's ≈50% and Zambaldi et al. (2018)'s <10%; DRC also beat ResNets in MiniPacman and achieved state-of-the-art scores on three Atari games.On the other two Atari games, DRC scores were competitive.Source: §4.1 · p. 5

4.1.1. INFLUENCE OF NETWORK ARCHITECTURE

  • On medium-difficulty Sokoban, DRC(9,1) reached 94% versus DRC(3,3)'s 91.5% after 1e9 steps; on hard levels, DRC(9,1) solved 80% in under 48 minutes, versus search's 94% in 10 hours.The search comparison used Levin Tree Search with a DRC(1,1) policy prior.Source: §4.1.1 · p. 5
  • Across architecture tests, greater capacity and iterative computation generally improved performance; spatial recurrent states contributed, while deep ResNets and flat 1D LSTMs underperformed the best recurrent models.With nine modules, repeating without stacking was less effective, while stacking alone trained more slowly early but reached similar final performance.Source: §4.1.1 · pp. 5–6

4.2. Data Efficiency & Generalization

  • Across 900k-, 10k-, and 1k-level regimes, DRC(3,3) generalized better than DRC(1,1); in the medium regime, their generalization gaps were 6.5% and 33.5%, respectively.Larger networks also generalized better in supervised imitation learning, despite similar training errors on small datasets.Source: §4.2 · p. 6
  • Performance degradation when extrapolating to seven boxes was 3.5% for DRC(3,3) and 18.5% for DRC(1,1), compared with the 34% loss reported by Racanière et al. (2017) in the same setup.The test levels had more boxes than those in training, with grid size fixed.Source: §4.2 · p. 7

4.3. Iterative Computation

  • About 5% improvement on medium-difficulty Sokoban followed up to 10 forced no-op computation steps for DRC networks; the fully connected LSTM did not show such gains.The no-ops gave the network extra computation on the same inputs before acting.Source: §4.3 · p. 7

5. Discussion

The discussion argues that general-purpose recurrent convolutional networks trained with model-free RL learn planning-like behavior and achieve state-of-the-art results in several tested domains. Generalization and extra-thinking-time analyses support the interpretation that these networks compute domain-tailored approximate plans dynamically.

5. Discussion

  • Model-free recurrent convolutional networks achieve state-of-the-art results in several domains, outperforming all specialized planning architectures tested.The authors describe these results as evidence that general-purpose, high-capacity networks can learn to plan.Source: §5 · p. 7
  • Figure 5 summarizes generalization across Large, Medium, and Small training subsets on Sokoban test sets and in Boxworld.The Sokoban evaluations use both the unfiltered and medium-difficulty test sets.Source: Figure 5 · p. 8
  • Forcing extra computation steps after training improves DRC performance on Sokoban’s medium-difficulty set.The figure caption says the extra steps are induced with no-op actions at episode start and includes an LSTM(1,1) comparison.Source: Figure 6 · p. 8
  • The authors interpret their generalization and scaling analyses as evidence that these networks learn domain-tailored approximate-planning algorithms computed dynamically over multiple steps.They suggest additional thinking time can boost performance.Source: §5 · pp. 7–8
  • Whether model-free planning works in reinforcement-learning environments of real-world complexity remains unresolved.The authors also argue that theories of generalization should account for algorithmic function approximation, not only simplistic measures of model complexity.Source: §5 · p. 8

Appendix

The appendix gathers environment, dataset, architecture, training, and additional experimental details, including comparisons with several baseline agents.

Appendix

  • The appendix describes the five environments used in the paper and the generation process for released Sokoban levels.Source: Appendix · p. 11
  • It documents the DRC architecture, memory choices, implementation details, model parameters, and RL training hyperparameters.Source: Appendix · p. 11
  • Additional experiments include DRC ablations, extended generalization analyses, and comparisons with VIN, ATreeC, and ResNet.Source: Appendix · p. 11

6. Domains

The domains are procedurally generated tasks with distinct observation formats, reward rules, and episode constraints; the appendix figures illustrate sample starting observations.

6. Domains

  • Sample observations show each planning environment at the beginning of an episode.Source: Figure 7 · p. 11

6.1. Sokoban

  • Sokoban uses sprite-based RGB inputs, a 120-frame episode cap, and rewards for completing levels and moving boxes onto or off targets.The per-step cost is -0.01; experiments generally use levels from the unfiltered dataset unless otherwise noted.Source: §6.1 · p. 11

6.2. MiniPacman

  • MiniPacman is stochastic: each ghost moves at each time-step with probability 0.95, and the game includes food, power pills, and ghosts that can become edible.The appendix describes five available reward modes.Source: §6.2 · pp. 11–12, Figure 8 · p. 11

6.3. Boxworld

  • Boxworld episodes are capped at 120 frames, with branch length 3 and maximum solution length 4; states are supplied as 14 x 14 x 3 tensors.Levels are generated by the game engine rather than represented as sprite-based images.Source: §6.3 · p. 12

6.4. Atari

  • Atari experiments use the standard setup with up to 30 random no-ops, four-frame action repeats, and all 18 actions.Episodes are capped at 30 minutes, and hyperparameter tuning was limited.Source: §6.4 · p. 12

6.5. Gridworld

  • Gridworld levels are 32 x 32, with 12–24 randomly sampled square obstacles and randomly placed player and goal locations.Rejection sampling ensures the player can reach the goal; reaching the goal or stepping on an obstacle ends the episode.Source: §6.5 · p. 12

7. Dataset generation details

The dataset details explain how Sokoban difficulty sets are constructed and identify the scope of two appendix tables.

7. Dataset generation details

  • Medium Sokoban levels are freshly sampled and retained when a DRC(1,1) policy fails to solve them within 10 attempts; hard levels are selected when a DRC(3,3) policy fails within 10 attempts.The hard set is selected from a separate medium dataset, with no overlap between the hard and medium sets.Source: §7 · p. 12
  • Table 3 reports the best test-set results across difficulty levels for RL agents trained within 2e9 steps, averaged over five independent runs.The caption directs readers to Figure 9 for training curves.Source: Table 3 · p. 12
  • Table 4 lists the number of levels in each dataset subset and the number of overlaps between subsets.Source: Table 4 · p. 12

8. Model

The DRC stacks recurrent memory modules and repeats their computation within each time-step, using ConvLSTMs by default. Top-down feedback and pooled summaries provide additional information paths, while simpler recurrent modules are alternatives.

8. Model

  • The DRC repeats computation across N ticks and stacks D memory modules, with encoded observations supplied throughout the grid.The network uses the deepest module’s hidden state after N ticks as its output.Source: §8 · p. 13

8.2.1. CONVLSTM

  • ConvLSTM is the default memory module, with its parameters unshared across stack depth.The paper also evaluates gated and ungated convolutional recurrent alternatives.Source: §8 · p. 13, §8.2.1 · p. 14

8.1.1. TOP-DOWN SKIP CONNECTION

  • A top-down skip connection feeds the last layer’s hidden state at one time-step to the first layer of the next.This adds feedback to the otherwise upward-and-forward information flow.Source: §8.1.1 · p. 13

8.1.2. POOL-AND-INJECT

  • Pool-and-inject spatially aggregates hidden states, projects and tiles their summaries, then supplies them as inputs at the next tick.The summaries are produced separately for each depth and match the hidden states’ shapes.Source: §8.1.2 · p. 13

8.2.2. GATEDCONVRNN

  • GatedConvRNN is a simpler alternative without a cell state and has half as many parameters as ConvLSTM.Its parameters cover the output and hidden transformations and biases.Source: §8.2.2 · p. 14

8.2.3. SIMPLECONVRNN

  • SimpleConvRNN is a classic ungated RNN with half as many parameters as GatedConvRNN and one quarter as many as ConvLSTM.The paper uses ConvLSTM for its experiments except when comparing memory types.Source: §8.2.3 · p. 14

9. Hyper-Parameters

The DRC hyperparameters were tuned on Sokoban and then reused across domains, with encoder architectures adjusted for each observation format.

9. Hyper-Parameters

  • The DRC hyperparameters were tuned on Sokoban and reused unchanged for other domains.Only the encoder architecture was changed to fit each domain’s observation format.Source: §9 · p. 14

9.1. Network parameters

  • Encoder architectures were adjusted for each domain’s observation format.The rest of the DRC settings were shared across domains.Source: §9 · p. 14
  • ReLU is the default activation function unless otherwise specified.Source: §9.1 · p. 14

Observation size

The paper specifies domain-specific observation encoders and recurrent-network sizes, alongside shared actor-critic training settings. Learning curves also compare DRC training on medium-difficulty Sokoban data with training on the unfiltered set.

Observation size

  • The encoder is a multilayer CNN, with input formats ranging from 32 × 32 × 1 for Gridworld to 210 × 160 × 3 for Atari.Sokoban uses 80 × 80 × 3, Boxworld 14 × 14 × 3, and MiniPacman 15 × 19 × 3 observations.Source: Observation size · pp. 14–15
  • DRC modules use 128-channel convolutions with 3 × 3 kernels, while hidden and cell states have 32 channels.The LSTM baselines use hidden size 200.Source: Observation size · p. 15

9.2. RL training setup

  • The V-trace actor-critic setup uses 4 GPUs per learner, 200 actors, λ-returns with λ = 0.97, and a discount factor γ = 0.97.Training uses length-20 BPTT, batch size 32, and Adam; the learning rate decays to zero over 1.5e9 environment steps.Source: §9.2 · p. 15
  • Sokoban learning curves compare DRC architectures trained on the medium-difficulty set with curves for the unfiltered dataset.The unfiltered-data DRC(3,3) curve is dashed; medium-set curves are solid.Source: Figure 9 · p. 16

10. Extra experiments

Across the extra experiments, DRC(3,3) shows stronger Sokoban generalization than DRC(1,1), while Atari results vary by game and ablations expose differing effects of architectural components. Comparisons with planning-inspired and standard baselines also include important evaluation-setting qualifications.

10.2. Atari

  • DRC(3,3) significantly outperformed LSTM baselines on Asteroid and Up’n Down, performed comparably on the other tested Atari games, and used fewer parameters.The (3,3) configuration also improved on (1,1) for both DRC and LSTM; the authors call for further study of when DRC has an Atari advantage.Source: §10.2 · p. 16, Figure 10 · p. 17

11.1. Memory type

  • ConvLSTM was the top-performing tested memory module, while Gated ConvRNN came close with half as many parameters.Simple ConvRNN showed instability and high variance; the authors infer that some gating is essential for DRC performance.Source: §11.1 · p. 16

11.2. Additional improvements

  • Removing pool-and-inject slowed early learning but reached baseline performance; removing the top-down skip increased variance and slightly lowered final performance.The vision shortcut had little influence, and the authors conclude none of these additions is critical to performance.Source: Figure 11 · p. 17, §11.2 · p. 18

12. Generalization

  • Above 90% of Sokoban levels with 7 boxes were solved by DRC(3,3), while DRC(1,1) fell below 80%.Both models were trained on levels with 4 boxes; DRC(1,1)’s train-test generalization gap also grew more as training-set size decreased.Source: §12 · p. 18, Figure 13 · p. 19

13.1. Value Iteration Networks

  • The VIN comparison uses parameter sweeps, reporting the top five runs; Gridworld uses player-position knowledge for attention, unlike pixel-observation Sokoban.The Sokoban adaptation uses a learned attention mask over the state space.Source: §13.1 · pp. 18–19, Figure 14 · p. 19

13.3. ResNet

  • On Boxworld, DRC(3,3) reached nearly 100% at 1e9 steps in comparison with the best ResNet architectures.The figure also compares DRC(1,1) with those ResNets on Boxworld and MiniPacman.Source: Figure 15 · p. 20, §13.3 · p. 20

13.2. ATreeC

  • Performance curves compare DRC with ATreeC on Sokoban, using the top five runs from sweeps over tree depth, embedding size, value aggregation, and TD-lambda.The ATreeC setup uses encoded Sokoban observations and omits auxiliary reward or state-grounding losses.Source: Figure 14 · p. 19, §13.2 · p. 20

13.5. I2A

  • The I2A result at 1e9 steps was below the originally reported 90%, with train-test splitting and online rather than pre-trained environment models identified as differences.The paper reports 88% test performance at 1e9 steps in its setup.Source: §13.5 · p. 21
Loading 1901.03559v2…