Source-linked AI summary
Fast Exploration with Simplified Models and Approximately Optimistic Planning in Model Based Reinforcement Learning
Ramtin Keramati, Jay Whang, Patrick Cho, Emma Brunskill
TL;DR
The paper addresses how model-based RL can learn and explore efficiently in large domains when exact planning is infeasible and complex models are costly to learn. It combines optimistic MCTS with object-oriented, approximately deterministic model selection in SOORL. More than 80% of runs got positive reward in 50 episodes on Pitfall!, though the authors characterize this result as a case study.
Problem
Large-domain model-based RL faces data demands for accurate deep models and computationally expensive perfect planning, while human learners can learn Atari games within a few episodes.
Source: §1 · p. 1Method
SOORL combines optimistic MCTS for exploration with object representation and automatic selection among candidate models that favor simple deterministic predictions.
Source: §4.1 · p. 5, §4.2 · p. 5, §8 · p. 10Results
More than 80% of runs got a positive reward in 50 episodes on Pitfall!, and the authors report this as the first approach to do so without human demonstrations.
Source: §6.2 · p. 9Takeaways & Limitations
The authors describe lookahead planning with object representation as a promising path toward more sample-efficient RL, while noting that SOORL’s engineering burden remains.
Source: §8 · p. 10The Pitfall! result should be viewed mostly as a case study, and unaccounted model bias could limit asymptotic performance.
Source: §1 · p. 2
Abstract
from arXiv · showhide
Humans learn to play video games significantly faster than the state-of-the-art reinforcement learning (RL) algorithms. People seem to build simple models that are easy to learn to support planning and strategic exploration. Inspired by this, we investigate two issues in leveraging model-based RL for sample efficiency. First we investigate how to perform strategic exploration when exact planning is not feasible and empirically show that optimistic Monte Carlo Tree Search outperforms posterior sampling methods. Second we show how to learn simple deterministic models to support fast learning using object representation. We illustrate the benefit of these ideas by introducing a novel algorithm, Strategic Object Oriented Reinforcement Learning (SOORL), that outperforms state-of-the-art algorithms in the game of Pitfall! in less than 50 episodes.
1 INTRODUCTION
The paper investigates approximate planning for exploration and model selection for tractable learning, motivated by the gap between human and RL sample efficiency. It introduces SOORL and reports positive reward on Pitfall! within 50 episodes, while treating that result as a case study.
1 INTRODUCTION
- Deep neural network models can require substantial data, and perfect planning with them can be computationally expensive in large environments.The introduction contrasts these challenges with theoretical sample-efficiency results for tabular model-based RL.Source: §1 · p. 1
- Optimistic MCTS outperforms other approaches in simulation experiments when planning is approximate, addressing settings where exact planning is computationally prohibitive.The paper introduces optimism within Monte Carlo Tree Search to support exploration using learned models.Source: §1 · pp. 1–2
- SOORL learns object-oriented deterministic models by selecting among candidate transition models and temporal abstractions.The authors argue that pooling data across similar objects and reducing next-state branching can support learning and planning.Source: §1 · p. 2
- SOORL achieves positive reward on Pitfall! within 50 episodes, using prior knowledge of object representation and candidate model classes.The paper says the candidate-model-class assumption is stronger, though a large model set can be defined at cost quadratic in the number of features.Source: §1 · p. 2
- The Pitfall! result is primarily a case study; the authors identify investigating approximate exploration and model representation as the paper’s key contributions.They describe model selection as a bias/variance tradeoff and leave identifying and accounting for model bias to future work.Source: §1 · p. 2
2 PRELIMINARIES
The preliminaries formulate the task as maximizing expected discounted reward in a finite-horizon Markov decision process.
2 PRELIMINARIES
- The agent’s objective is to maximize expected discounted reward under a policy in a finite-horizon MDP.The passage defines the state and action spaces, transition and reward functions, and discount factor.Source: §2 · p. 2
3 APPROXIMATE MODEL-BASED PLANNING TO SUPPORT EXPLORATION
The section studies deep exploration when exact planning is infeasible, using approximate planning with learned models. Experiments compare exploration methods in Pong Prime and mini-Pitfall!, where optimistic MCTS performs strongly under limited computation.
3 APPROXIMATE MODEL-BASED PLANNING TO SUPPORT EXPLORATION
- Large state spaces make optimal planning computationally expensive, motivating approximate planning that remains tractable as learned models change and require frequent replanning.The section addresses deep exploration in large domains where exact planning is not possible, unlike settings where exact planning is feasible.Source: §3 · pp. 2–3
3.1 EXPERIMENTS
- The experiments compare optimistic MCTS, Thompson Sampling, and BAMCP in Pong Prime and mini-Pitfall!, using a known model class to isolate exploration from model mismatch.Pong Prime uses 500 total tree searches; mini-Pitfall! evaluates consistent achievement of the reward at the right end of room 0.Source: §3 · p. 3, Table 1 · p. 3, §3.1 · p. 4
- Pong Prime is a hard-exploration game in which the optimal policy hits the ball with the paddle’s lower region, while epsilon-greedy model-free methods consistently lose across 5,000 episodes.Mini-Pitfall! restricts play to rooms 0 and -1, with a dummy reward at the right end of room 0 and terminal states at the left end of room -1 and underground connection.Source: §3.1 · pp. 3–4
3.2 DISCUSSION
- Both BAMCP and Thompson Sampling perform worse than the MLE model when planning uses limited simulations and may not reach a local reward.Thompson Sampling can miss optimistic branches because it samples one model; limited UCT rollouts may therefore produce non-optimistic root Q estimates.Source: §3.2 · p. 4
- In deterministic environments, BAMCP potentially builds a tree of size O((|A|M)^H), versus at most O(|A|^H) for the other methods.BAMCP samples a different deterministic model at each rollout, which can create multiple next states for the same action node.Source: §3.2 · p. 4
- Optimism-based exploration significantly outperforms other approaches, with optimism available at every tree node to identify actions for exploration without observing delayed rewards.With more simulations, optimistic exploration’s performance increases; with sufficient computation, optimistic MCTS should learn the optimal Pong Prime policy.Source: §3.2 · pp. 4–5
4 APPROXIMATELY DETERMINISTIC MODEL TO SUPPORT FAST LEARNING
This section develops simple, approximately deterministic object models to support efficient learning and tractable planning. It selects models by prediction entropy and uses action-then-wait macro actions to make transitions more predictable.
4 APPROXIMATELY DETERMINISTIC MODEL TO SUPPORT FAST LEARNING
- Object models can pool data across similar objects, and deterministic models reduce the planning tree’s branching factor.The paper assumes objects are given, with their bounding boxes, and motivates object-level representations as a way to factor high-dimensional states into lower-dimensional object states.Source: §4 · p. 5
4.1 REVIEW OF OBJECT ORIENTED MDP
- The object-oriented MDP represents each state as objects from classes with attributes, and the underlying MDP state is the union of object states.The interaction function indicates whether two objects interact; the model assumes it is known, same-class objects share transition functions, and each next state depends on at most pairwise interactions and action.Source: §4.1 · p. 5
4.2 MODEL LEARNING
- The model learner chooses the simplest count-based model whose observed-data entropy falls below a threshold, increasing history length by powers of two if needed.The same model-selection approach and model class are used for reward functions.Source: §4.2 · pp. 5–6
- For Pitfall!, the model features combine object size, location, and intersection; with sufficient history, the entropy of all models eventually reaches zero.Ignoring null input, the Cartesian product produces seven feature sets.Source: §4.2 · p. 6
4.3 TEMPORAL ABSTRACTION
- “Act and then wait” macro actions address nonlinear, history-dependent transitions by adding no-op steps and greedily reducing them while retaining deterministic predictions.In Pitfall!, Jump Right requires 8 no-ops, Down requires 4, and Right requires none; Pong Prime requires two no-ops after each action.Source: §4.3 · pp. 6–7
5 SOORL: STRATEGIC OBJECT ORIENTED REINFORCEMENT LEARNING
SOORL combines object-oriented deterministic models with optimism-based exploration and UCT lookahead planning. It assumes an object detector, an interaction function, and macro actions that can be learned.
5 SOORL: STRATEGIC OBJECT ORIENTED REINFORCEMENT LEARNING
- SOORL combines UCT lookahead planning, learning and selecting object transition and reward models, and optimism-based exploration.The algorithm assumes an object detector that returns objects and attributes, an interaction function, and macro actions.Source: §5 · p. 7
- SOORL represents model inputs with object size, location, and intersection features, yielding seven feature sets when null input is ignored.Its exploration treats previously unseen model inputs and object interactions as Rmax reward and updates reward models using model-based interval estimation.Source: §5 · p. 7
- At each episode’s start, SOORL trains a value function on previously seen transitions and rewards, then uses UCT rollouts to predict rewards and next object states.Planning selects models based on object states and interactions, using the value of the depth-d object state at the planning horizon.Source: §5 · p. 8
6 EMPIRICAL EVALUATION
SOORL is evaluated on Pitfall!, where it achieves positive rewards without human demonstrations. The evaluation reports room discovery, reward comparisons, and the share of runs with positive rewards.
6.1 DETAILS
- SOORL assumes an object detector, predefined function classes, and macro actions; its object attributes include location and bounding-box size, with collisions defining interactions.The model features combine object size, location, and intersections into seven feature sets.Source: §6 · p. 8, §6.1 · p. 8
6 EMPIRICAL EVALUATION
- The evaluation focuses on Pitfall!, a sparse-reward, hard-exploration game where prior methods without demonstrations had failed to achieve positive reward.Object information was extracted from Atari RAM and screen data; the need for an object detector made testing across all Atari games prohibitively burdensome.Source: §6 · p. 8
6.2 PERFORMANCE AND DISCUSSION
- SOORL’s average score was −193.5 ± 595.8, and its best-episode score was 606.6 ± 1254.5, higher than all scores reported for comparison algorithms at evaluation.Figure 4 presents SOORL’s Pitfall! performance, including the cumulative-reward comparison in panel (b).Source: Figure 4 · p. 9, §6.2 · p. 9
6.1 DETAILS
- For exploration, SOORL assigns Rmax to unseen interactions and transitions, updates models using interval estimation, and adds a visit-count bonus.The agent splits the screen into grids and assigns a bonus βn(s)^−1/2 based on visit count.Source: §6.1 · p. 9
- The value function uses discrete object locations and empirical transitions and rewards with an optimism bonus, followed by value iteration at each episode’s start.The discrete locations use the same screen split as the optimism bonus.Source: §6.1 · p. 9
6.2 PERFORMANCE AND DISCUSSION
- The agent discovered 21 rooms on average within 50 episodes and 27 different rooms across 20 runs, supporting the reported deep-exploration behavior.Figure 4(a) tracks rooms discovered across episodes.Source: §6.2 · p. 9
- More than 80% of SOORL runs achieved positive reward within 50 episodes, indicating consistency across runs.The paper notes that direct comparison with end-to-end deep RL is unfair because those methods use substantially less prior knowledge.Source: §6.2 · p. 9
- Macro actions are provided for SOORL but can be learned online; integrating temporal abstraction can increase sample complexity by O(|A|K), where K is the maximum number of no-ops.Source: §6.2 · p. 9
7 RELATED WORK
The related work spans model-based planning, exploration, and object-oriented RL. The paper distinguishes its approach by combining scalable planning, strategic exploration, and simple object-based dynamics models.
7 RELATED WORK
- Prior model-based RL has used known simulators with MCTS or learned deep models online, whereas this work seeks simple models based on object representations.Source: §7 · p. 10
- Tabular exploration methods often require exact planning and do not scale well, while large-MDP count-based methods can need orders of magnitude more samples than humans.Source: §7 · p. 10
- Bayesian RL offers guarantees when exact planning is possible, but remains computationally intractable in large state spaces and has not substantially improved hard exploration in sparse-reward environments.Source: §7 · p. 10
- Earlier finite-horizon work studied planning loss and the effects of horizon choice under model inaccuracy; this paper instead studies how imperfect planning affects exploration.Source: §7 · p. 10
- Unlike prior object-oriented approaches described here, this work uses objects to learn simple dynamics models for scalable planning with strategic exploration.The passage contrasts this with object-representation model-free methods that do not leverage objects for deep exploration.Source: §7 · p. 10
8 CONCLUSION AND FUTURE WORK
The paper presents optimistic MCTS and object-based simple models as approaches to sample-efficient RL with object priors. It also identifies model bias and engineering burden as concerns for future work.
8 CONCLUSION AND FUTURE WORK
- The paper proposes optimistic MCTS for deep exploration when exact planning is impossible and reports that it outperforms posterior-sampling methods.Source: §8 · p. 10
- SOORL combines object representations, optimistic MCTS, and automatic model selection biased toward simple deterministic models, achieving state-of-the-art results on Pitfall!.The authors describe the result as a case study and note that reducing SOORL’s engineering burden remains future work.Source: §8 · p. 10
- A wrong model class can cause catastrophic long-horizon prediction error that prevents using tree-search algorithms such as UCT, motivating robust planning research.Source: §8 · p. 10