TreeQN and ATreeC: Differentiable Tree Planning for Deep Reinforcement Learning

By Gregory Farquhar, Tim Rocktaschel, Maximilian Igl, Shimon Whiteson. 2017

72 citations recorded by the source corpus.

Combining deep model-free reinforcement learning with on-line planning is a promising approach to building on the successes of deep RL. On-line planning with look-ahead trees has proven successful in environments where transition models are known a priori. However, in complex environments where transition models need to be learned from data, the deficiencies of learned models have limited their utility for planning. To address these challenges, we propose TreeQN, a differentiable, recursive, tree-structured model that serves as a drop-in replacement for any value function network in deep RL with discrete actions. TreeQN dynamically constructs a tree by recursively applying a transition model in a learned abstract state space and then aggregating predicted rewards and state-values using a tree backup to estimate Q-values. We also propose ATreeC, an actor-critic variant that augments TreeQN with a softmax layer to form a stochastic policy network. Both approaches are trained end-to-end, such that the learned model is optimised for its actual use in the planner. We show that TreeQN and ATreeC outperform n-step DQN and A2C on a box-pushing task, as well as n-step DQN and value prediction networks (Oh et al., 2017) on multiple Atari games, with deeper trees often outperforming shallower ones. We also present a qualitative analysis that sheds light on the trees learned by TreeQN.

Subfields: Artificial Intelligence, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Reinforcement Learning

Citations in the corpus

Mastering Atari, Go, chess and shogi by planning with a learned model (2019, background): “TreeQN [10] learns an abstract MDP model, such that a tree search over that model (represented by a tree-structured neural network) approximates the optimal value function.”
Relational inductive biases, deep learning, and graph networks (2018, background): “…(Socher et al., 2011a,b, 2012, 2013; Tai et al., 2015; Andreas et al., 2016), partial tree traversals in a state-action graph (Guez et al., 2018; Farquhar et al., 2018), hierarchical action policies (Andreas et al., 2017), multi-agent communication channels (Foerster et al., 2016), “capsules”…”
Learning to Drive in a Day (2018, methodology): “Other research has looked at better transformation of observations into states, typically using an RNN [39], [40], as well as methods to perform multi-step planning, as in [41].”
Iterative Value-Aware Model Learning (2018, background): “…the reward, value function, or policy is ignored in the conventional model learning approaches in MBRL (some recent exceptions are Joseph et al. [2013], Silver et al. [2017], Oh et al. [2017], Farquhar et al. [2018]; refer to the supplementary material for a detailed literature review of MBRL).”
Policy Evaluation Networks (2020, unknown): “Other works, such as TreeQN (Farquhar et al., 2018), the Predictron (Silver et al., 2017) and Value Prediction Networks (Oh et al., 2017) are examples of value functions built with inductive biases, looking to improve generalization.”
Universal Planning Networks (2018, methodology): “We next seek to answer the question: Can UPN still work for scenarios where the camera view of the task is nonorthographic? This is a common scenario for real robot tasks or more complex manipulation tasks in simulation (Finn et al., 2017b). To answer this, we consider the task of controlling a 3D 7”
An investigation of model-free planning (2019, methodology): “Sokoban: In Sokoban, we demonstrate state-of-the-art results versus prior work which targeted similar boxpushing puzzle domains (ATreeC (Farquhar et al., 2017), I2A (Racanière et al.”
Differentiable SLAM-net: Learning Particle SLAM for Visual Navigation (2021, background): “Differentiable algorithms are emerging for a wide range of learning domains, including state estimation [24; 31; 34; 42], visual mapping [23; 36], planning [55; 33; 18; 49; 22; 62] and control tasks [2; 50; 17; 6].”
Learning Particle Dynamics for Manipulating Rigid Bodies, Deformable Objects, and Fluids (2018, background): “Many recent papers have studied model-predictive control with deep networks (Lenz et al., 2015; Gu et al., 2016; Nagabandi et al., 2018; Farquhar et al., 2018; Srinivas et al., 2018).”
Propagation Networks for Model-Based Control Under Partial Observation (2018, background): “Recent work on model-predictive control with deep networks [16], [17], [18], [19], [20] often learns an abstractstate transition function, instead of an explicit account of the environment [21], [22].”
An Introduction to Deep Reinforcement Learning (2018, unknown): “TreeQN (Farquhar et al., 2017) constructs a tree by recursively applying an implicit transition model in an implicitly learned abstract state space, built by estimating Q-values.”
Decoupling Dynamics and Reward for Transfer Learning (2018, methodology): “We compare our approach with a model based baseline for the planning experiments, an asynchronous version of ATreeC (Farquhar et al., 2017), that combines model-free re-inforcement learning with on-line planning.”
Combinatorial optimization and reasoning with graph neural networks (2021, methodology): “Additionally, the model performed strongly in the low-data regime against ATreeC [36], which resorted to predicting scalar values in every node of the inferred local MDP, so that VI-style rules can be directly applied exactly according to the predictions above.”
Differentiable MPC for End-to-end Planning and Control (2018, unknown): “Farquhar et al. [2017] extends model-free approaches, such as DQN [Mnih et al.”