summaries: This paper proposes a sequential Monte Carlo Planning algorithm that depicts planning as an inference problem solved by SMC. The problem is interesting and the paper has a nice description of the related work. In terms of the connection between the the problem and Bayesian filtering as well as smoothing, the paper has novelty there. But it is unclear to me how the algorithm proposed is applicable in complex continuous tasks as claimed. Sequential Monte Carlo (SMC) has since its inception some 25 years ago proved to be a powerful and generally applicable tool. The authors of this paper continue this development in a very interesting and natural way by showing how SMC can be used to solve challenging planning problems. This is a enabled by reformulating the planning problem as an inference problem via the recent trend referred to as "control as inference". While there is unfortunately no real world experiments, the simulations clearly illustrate the potential of the approach.
abstractText: In this work, we propose a novel formulation of planning which views it as a probabilistic inference problem over future optimal trajectories. This enables us to use sampling methods, and thus, tackle planning in continuous domains using a fixed computational budget. We design a new algorithm, Sequential Monte Carlo Planning, by leveraging classical methods in Sequential Monte Carlo and Bayesian smoothing in the context of control as inference. Furthermore, we show that Sequential Monte Carlo Planning can capture multimodal policies and can quickly learn continuous control tasks.
authors.name: Alexandre Piché
authors.name: Valentin Thomas
authors.name: Cyril Ibrahim
authors.name: Yoshua Bengio
authors.name: Chris Pal
references.authors: Abbas Abdolmaleki Jost Tobias Springenberg Yuval Tassa Remi Munos Nicolas Heess Martin Riedmiller
references.title: Maximum a posteriori policy optimisation
references.venue: arXiv preprint arXiv:1806.06920,
references.authors: Christophe Andrieu Arnaud Doucet Sumeetpal S Singh Vladislav B Tadic
references.title: Particle methods for change detection, system identification, and control
references.venue: Proceedings of the IEEE,
references.authors: Hagai Attias
references.title: Planning by probabilistic inference
references.venue: In AISTATS. Citeseer,
references.authors: Matthew Botvinick Marc Toussaint
references.title: Planning as inference
references.venue: Trends in cognitive sciences,
references.authors: Yoram Bresler
references.title: Two-filter formulae for discrete-time non-linear bayesian smoothing
references.venue: International Journal of Control,
references.authors: Jacob Buckman Danijar Hafner George Tucker Eugene Brevdo Honglak Lee
references.title: Sample-efficient reinforcement learning with stochastic ensemble value expansion
references.venue: arXiv preprint arXiv:1807.01675,
references.authors: Lars Buesing Theophane Weber Sébastien Racanière S.M. Ali Eslami Danilo Jimenez Rezende David P. Reichert Fabio Viola Frederic Besse Karol Gregor Demis Hassabis Daan Wierstra
references.title: Learning and querying fast generative models for reinforcement learning
references.venue: CoRR, abs/1802.03006,
references.authors: Kurtland Chua Roberto Calandra Rowan McAllister Sergey Levine
references.title: Deep reinforcement learning in a handful of trials using probabilistic dynamics models
references.venue: arXiv preprint arXiv:1805.12114,
references.authors: Cédric Colas Olivier Sigaud Pierre-Yves Oudeyer
references.title: How many random seeds? statistical power analysis in deep reinforcement learning experiments
references.venue: arXiv preprint arXiv:1806.08295,
references.authors: Peter Dayan Geoffrey E Hinton
references.title: Using expectation-maximization for reinforcement learning
references.venue: Neural Computation,
references.authors: Chelsea Finn Sergey Levine
references.title: Deep visual foresight for planning robot motion
references.venue: In Robotics and Automation (ICRA),
references.authors: Ian Goodfellow Jean Pouget-Abadie Mehdi Mirza Bing Xu David Warde-Farley Sherjil Ozair Aaron Courville Yoshua Bengio
references.title: Generative adversarial nets
references.venue: In Advances in neural information processing systems,
references.authors: Neil J Gordon David J Salmond Adrian FM Smith
references.title: Novel approach to nonlinear/non-gaussian bayesian state estimation
references.venue: In IEE Proceedings F-radar and signal processing,
references.authors: Shixiang Gu Zoubin Ghahramani Richard E Turner
references.title: Neural adaptive sequential monte carlo
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Arthur Guez Théophane Weber Ioannis Antonoglou Karen Simonyan Oriol Vinyals Daan Wierstra Rémi Munos David Silver
references.title: Learning to search with mctsnets
references.venue: arXiv preprint arXiv:1802.04697,
references.authors: Tuomas Haarnoja Aurick Zhou Pieter Abbeel Sergey Levine
references.title: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor
references.venue: arXiv preprint arXiv:1801.01290,
references.authors: Peter Henderson Riashat Islam Philip Bachman Joelle Pineau Doina Precup David Meger
references.title: Deep reinforcement learning that matters
references.venue: arXiv preprint arXiv:1709.06560,
references.authors: Sepp Hochreiter Jürgen Schmidhuber
references.title: Long short-term memory
references.venue: Neural computation,
references.authors: Rudolf Emil Kalman
references.title: When is a linear control system optimal
references.venue: Journal of Basic Engineering,
references.authors: Rudolf Emil Kalman
references.title: Contributions to the theory of optimal control
references.venue: Bol. Soc. Mat. Mexicana,
references.authors: Nikolas Kantas JM Maciejowski A Lecchini-Visintini
references.title: Sequential monte carlo for model predictive control
references.venue: In Nonlinear Model Predictive Control,
references.authors: Michael Kearns Yishay Mansour Andrew Y Ng
references.title: A sparse sampling algorithm for near-optimal planning in large markov decision processes
references.venue: Machine learning,
references.authors: Diederik P Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: arXiv preprint arXiv:1412.6980,
references.authors: Diederik P Kingma Max Welling
references.title: Auto-encoding variational bayes
references.venue: arXiv preprint arXiv:1312.6114,
references.authors: Genshiro Kitagawa
references.title: The two-filter formula for smoothing and an implementation of the gaussian-sum smoother
references.venue: Annals of the Institute of Statistical Mathematics,
references.authors: Genshiro Kitagawa
references.title: Monte carlo filter and smoother for non-gaussian nonlinear state space models
references.venue: Journal of computational and graphical statistics,
references.authors: Thanard Kurutach Aviv Tamar Ge Yang Stuart Russell Pieter Abbeel
references.title: Learning plannable representations with causal infogan
references.venue: arXiv preprint arXiv:1807.09341,
references.authors: Tuan Anh Le Maximilian Igl Tom Rainforth Tom Jin Frank Wood
references.title: Auto-encoding sequential monte carlo
references.venue: arXiv preprint arXiv:1705.10306,
references.authors: Sergey Levine
references.title: Reinforcement learning and control as probabilistic inference: Tutorial and review
references.venue: arXiv preprint arXiv:1805.00909,
references.authors: Sergey Levine Vladlen Koltun
references.title: Variational policy search via trajectory optimization
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Fredrik Lindsten Michael I Jordan Thomas B Schön
references.title: Particle gibbs with ancestor sampling
references.venue: The Journal of Machine Learning Research,
references.authors: Chris J Maddison Dieterich Lawson George Tucker Nicolas Heess Arnaud Doucet Andriy Mnih Yee Whye Teh
references.title: Particle value functions
references.venue: arXiv preprint arXiv:1703.05820,
references.authors: Chris J Maddison John Lawson George Tucker Nicolas Heess Mohammad Norouzi Andriy Mnih Arnaud Doucet Yee Teh
references.title: Filtering variational objectives
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Ofir Nachum Mohammad Norouzi Kelvin Xu Dale Schuurmans
references.title: Bridging the gap between value and policy based reinforcement learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Christian A Naesseth Scott W Linderman Rajesh Ranganath David M Blei
references.title: Variational sequential monte carlo
references.venue: arXiv preprint arXiv:1705.11140,
references.authors: Anusha Nagabandi Gregory Kahn Ronald S Fearing Sergey Levine
references.title: Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning
references.venue: arXiv preprint arXiv:1708.02596,
references.authors: Brendan O’Donoghue Remi Munos Koray Kavukcuoglu Volodymyr Mnih
references.title: Combining policy gradient and q-learning
references.venue: arXiv preprint arXiv:1611.01626,
references.authors: Michael K Pitt Neil Shephard
references.title: Filtering via simulation: Auxiliary particle filters
references.venue: Journal of the American statistical association,
references.authors: Konrad Rawlik Marc Toussaint Sethu Vijayakumar
references.title: An approximate inference approach to temporal optimization in optimal control. In Advances in neural information processing
references.authors: Konrad Rawlik Marc Toussaint Sethu Vijayakumar
references.title: On stochastic optimal control and reinforcement learning by approximate inference
references.venue: In Robotics: science and systems,
references.authors: RY Rubinstein DP Kroese
references.title: A unified approach to combinatorial optimization, monte-carlo simulation, and machine learning
references.authors: John Schulman Xi Chen Pieter Abbeel
references.title: Equivalence between policy gradients and soft q-learning
references.venue: arXiv preprint arXiv:1704.06440,
references.authors: David Silver Julian Schrittwieser Karen Simonyan Ioannis Antonoglou Aja Huang Arthur Guez Thomas Hubert Lucas Baker Matthew Lai Adrian Bolton
references.title: Mastering the game of go without human knowledge
references.authors: Alec Solway Matthew M Botvinick
references.title: Goal-directed decision making as probabilistic inference: a computational framework and potential neural correlates
references.venue: Psychological review,
references.authors: Leland Stewart Perry McCarty
references.title: Use of bayesian belief networks to fuse continuous and discrete information for target recognition, tracking, and situation assessment
references.venue: In Signal Processing, Sensor Fusion, and Target Recognition,
references.authors: István Szita András Lörincz
references.title: Learning tetris using the noisy cross-entropy method
references.venue: Neural computation,
references.authors: Yuval Tassa Tom Erez Emanuel Todorov
references.title: Synthesis and stabilization of complex behaviors through online trajectory optimization
references.venue: In Intelligent Robots and Systems (IROS),
references.authors: Emanuel Todorov Weiwei Li
references.title: A generalized iterative lqg method for locally-optimal feedback control of constrained nonlinear stochastic systems
references.venue: In American Control Conference,
references.authors: Emanuel Todorov Tom Erez Yuval Tassa
references.title: Mujoco: A physics engine for model-based control
references.venue: In Intelligent Robots and Systems (IROS),
references.authors: Marc Toussaint
references.title: Robot trajectory optimization using approximate inference
references.venue: In Proceedings of the 26th annual international conference on machine learning,
references.authors: Marc Toussaint Christian Goerick
references.title: Probabilistic inference for structured planning in robotics
references.venue: In Intelligent Robots and Systems,
references.authors: Marc Toussaint Amos Storkey
references.title: Probabilistic inference for solving discrete and continuous state markov decision processes
references.venue: In Proceedings of the 23rd international conference on Machine learning,
references.authors: Théophane Weber Sébastien Racanière David P Reichert Lars Buesing Arthur Guez Danilo Jimenez Rezende Adria Puigdomènech Badia Oriol Vinyals Nicolas Heess Yujia Li
references.title: Imagination-augmented agents for deep reinforcement learning
references.venue: arXiv preprint arXiv:1707.06203,
references.authors: Brian D Ziebart
references.title: Modeling purposeful adaptive behavior with the principle of maximum causal entropy
sections.heading: 1 INTRODUCTION
sections.text: To exhibit intelligent behaviour machine learning agents must be able to learn quickly, predict the consequences of their actions, and explain how they will react in a given situation. These abilities are best achieved when the agent efficiently uses a model of the world to plan future actions. To date, planning algorithms have yielded very impressive results. For instance, Alpha Go (Silver et al., 2017) relied on Monte Carlo Tree Search (MCTS) (Kearns et al., 2002) to achieve super human performances. Cross entropy methods (CEM) (Rubinstein & Kroese, 2004) have enabled robots to perform complex nonprehensile manipulations (Finn & Levine, 2017) and algorithms to play successfully Tetris (Szita & Lörincz, 2006). In addition, iterative linear quadratic regulator (iLQR) (Kalman et al., 1960; Kalman, 1964; Todorov & Li, 2005) enabled humanoid robots tasks to get up from an arbitrary seated pose (Tassa et al., 2012).
  Despite these successes, these algorithms make strong underlying assumptions about the environment. First, MCTS requires a discrete setting, limiting most of its successes to discrete games with known dynamics. Second, CEM assumes the distribution over future trajectories to be Gaussian, i.e. unimodal. Third, iLQR assumes that the dynamics are locally linear-Gaussian, which is a strong assumption on the dynamics and would also assume the distribution over future optimal trajectories to be Gaussian. For these reasons, planning remains an open problem in environments with continuous actions and complex dynamics. In this paper, we address the limitations of the aforementioned planning algorithms by creating a more general view of planning that can leverage advances in deep learning (DL) and probabilistic inference methods. This allows us to approximate arbitrary complicated distributions over trajectories with non-linear dynamics.
  We frame planning as density estimation problem over optimal future trajectories in the context of control as inference (Dayan & Hinton, 1997; Toussaint & Storkey, 2006; Toussaint, 2009; Rawlik et al., 2010; 2012; Ziebart, 2010; Levine & Koltun, 2013). This perspective allows us to make use of tools from the inference research community and, as previously mentioned, model any distribution over future trajectories. The planning distribution is complex since trajectories consist of an intertwined sequence of states and actions. Sequential Monte Carlo (SMC) (Stewart & McCarty, 1992; Gordon et al., 1993; Kitagawa, 1996) methods are flexible and efficient to model such a
  ∗both authors contributed equally.
  distribution by sequentially drawing from a simpler proposal distribution. From the SMC perspective, the policy can be seen as the proposal and a learned model of the world as the propagation distribution. This provides a natural way to combine model-free and model-based RL.
  Contribution. We depict the problem of planning as one of density estimation that can be estimated using SMC methods. We introduce a novel planning strategy based on the SMC class of algorithms, in which we treat the policy as the proposed distribution to be learned. We investigate how our method empirically compares with existing model-based methods and a strong model-free baseline on the standard benchmark Mujoco (Todorov et al., 2012).
sections.heading: 2 BACKGROUND
sections.heading: 2.1 CONTROL AS INFERENCE
sections.text: We consider the general case of a Markov Decision Process (MDP) {S,A, penv, r, γ, µ} where S and A represent the state and action spaces respectively. We use the letters s and a to denote states and actions, which we consider to be continuous vectors. Further notations include: penv(s′|s,a) as the state transition probability of the environment, r(s,a) as the reward function, and γ ∈ [0, 1) as the discount factor. µ denotes the probability distribution over initial states.
  This work focuses on an episodic formulation, with a fixed end-time of T . We define a trajectory as a sequence of state-action pairs xt:T = {(st,at), . . . , (sT ,aT )}, and we use the notation π for a policy which represents a distribution over actions conditioned on a state. Here π is parametrized by a neural network with parameters θ. The notation qθ(x1:T ) = µ(s1) ∏T−1 t≥1 penv(st+1|st,at) ∏T t≥1 πθ(at|st) denotes the probability of a trajectory x1:T under policy πθ.
  Traditionally, in reinforcement learning (RL) problems, the goal is to find the optimal policy that maximizes the expected return Eqθ [ ∑T t=1 γ
  trt]. However, it is useful to frame RL as an inference problem within a probabilistic graphical framework (Rawlik et al., 2012; Toussaint & Storkey, 2006; Levine, 2018). First, we introduce an auxiliary binary random variable Ot denoting the “optimality“ of a pair (st,at) at time t and define its probability1 as p(Ot = 1|st,at) = exp(r(st,at)). O is a convenience variable only here for the sake of modeling. By considering the variables (st,at) as latent and Ot as observed, we can construct a Hidden Markov Model (HMM) as depicted in figure 2.1. Notice that the link s→ a is not
  present in figure 2.1 as the dependency of the optimal action on the state depends on the future observations. In this graphical model, the optimal policy is expressed as p(at|st,Ot:T ). The posterior probability of this graphical model can be written as2:
  p(x1:T |O1:T ) ∝ p(x1:T ,O1:T ) = µ(s1) T−1∏ t=1 penv(st+1|at, st) exp ( T∑ t=1 r(st,at) + log p(at) ) .
  (2.1)
  It appears clearly that finding optimal trajectories is equivalent to finding plausible trajectories yielding a high return.
  1as in Levine (2018), if the rewards are bounded above, we can always remove a constant so that the probability is well defined.
  2Notice that in the rest of the paper, we will abusively remove the product of the action priors ∏T
  t=1 p(at) = exp (∑T t=1 log p(at) )
  from the joint as in Levine (2018). We typically consider this term either constant or already included in the reward function. See Appendix A.2 for details.
  Many control as inference methods can be seen as approximating the density by optimizing its variational lower bound: log p(O1:T ) ≥ Ex1:T∼qθ [ ∑T t=1 r(st,at) − log πθ(at|st)] (Rawlik et al., 2012; Toussaint, 2009). Instead of directly differentiating the variational lower bound for the whole trajectory, it is possible to take a message passing approach such as the one used in Soft Actor-Critic (SAC) (Haarnoja et al., 2018) and directly estimate the optimal policy p(at|st,Ot:T ) using the backward message, i.e a soft Q function instead of the Monte Carlo return.
sections.heading: 2.2 SEQUENTIAL MONTE CARLO METHODS
sections.text: Since distributions over trajectories are complex, it is often difficult or impossible to directly draw samples from them. Fortunately in statistics, there are successful strategies for drawing samples from complex sequential distributions, such as SMC methods.
  For simplicity, in the remainder of this section we will overload the notation and refer to the target distribution as p(x) and the proposal distribution as q(x). We wish to draw samples from p but we only know its unnormalized density. We will use the proposal q to draw samples and estimate p. In the next section, we will define the distributions p and q in the context of planning.
  Importance sampling (IS): When x can be efficiently sampled from another simpler distribution q i.e. the proposal distribution, we can estimate the likelihood of any point x under p straightforwardly by computing the unnormalized importance sampling weights w(x) ∝ p(x)q(x) and using the identity p(x) = w̄(x)q(x) where w̄(x) = w(x)∫
  w(x)q(x)dx is defined as the normalized importance sampling
  weights. In practice, one draws N samples from q: {x(n)}Nn=1 ∼ q; these are referred to as particles. The set of particles {x(n)}Nn=1 associated with their weights {w(n)}Nn=1 are simulations of samples from p. That is, we approximate the density p with a weighted sum of diracs from samples of q:
  p(x) ≈ N∑ n=1 w̄(n)δx(n)(x), withx (n) sampled from q
  where δx0(x) denotes the Dirac delta mass located as x0.
  Sequential Importance Sampling (SIS): When our problem is sequential in nature x = x1:T , sampling x1:T at once can be a challenging or even intractable task. By exploiting the sequential structure, the unnormalized weights can be updated iteratively in an efficient manner: wt(x1:t) = wt−1(x1:t−1)
  p(xt|x1:t−1) q(xt|x1:t−1) . We call this the update step. This enables us to sample sequentially
  xt ∼ q(xt|x1:t−1) to finally obtain the set of particles {x(n)1:T } and their weights {w (n) T } linearly in the horizon T .
  Sequential Importance Resampling (SIR): When the horizon T is long, samples from q usually have a low likelihood under p, and thus the quality of our approximation decreases exponentially with T . More concretely, the unnormalized weights w(n)t converge to 0 with t→∞. This usually causes the normalized weight distribution to degenerate, with one weight having a mass of 1 and the others a mass of 0. This phenomenon is known as weight impoverishment.
  One way to address weight impoverishment is to add a resampling step where each particle is stochastically resampled to higher likelihood regions at each time step. This can typically reduce the variance of the estimation from growing exponentially with t to growing linearly.
sections.heading: 3 PLANNING AS PROBABILISTIC INFERENCE
sections.text: In the context of control as inference, it is natural to see planning as the act of approximating a distribution of optimal future trajectories via simulation. In order to plan, an agent must possess a model of the world that can accurately capture consequences of its actions. In cases where multiple trajectories have the potential of being optimal, the agent must rationally partition its computational resources to explore each possibility. Given finite time, the agent must limit its planning to a finite horizon h. We, therefore, define planning as the act of approximating the optimal distribution over
  trajectories of length h. In the control-as-inference framework, this distribution is naturally expressed as p(a1, s2, . . . sh,ah|O1:T , s1), where s1 represents our current state.
sections.heading: 3.1 PLANNING AND BAYESIAN SMOOTHING
sections.text: As we consider the current state s1 given, it is equivalent and convenient to focus on the planning distribution with horizon h: p(x1:h|O1:T ). Bayesian smoothing is an approach to the problem of estimating the distribution of a latent variable conditioned on all past and future observations. One method to perform smoothing is to decompose the posterior with the two-filter formula (Bresler, 1986; Kitagawa, 1994):
  p(x1:h|O1:T ) ∝ p(x1:h|O1:h) · p(Oh+1:T |xh) (3.1)
  This corresponds to a forward-backward messages factorization in a Hidden Markov Model as depicted in figure 3.1. We broadly underline in orange forward variables and in blue backward variables in the rest of this section.
  Filtering is the task of estimating p(x1:t|O1:t): the probability of a latent variable conditioned on all past observations. In contrast, smoothing estimates p(x1:t|O1:T ): the density of a latent variable conditioned on all the past and future measurements.
  In the belief propagation algorithm for HMMs, these probabilities correspond to the forward message αh(xh) = p(x1:h|O1:h) and backward message βh(xh) = p(Oh+1:T |xh) , both of which are computed recursively. While in discrete spaces these forward and backward messages can be estimated using the sumproduct algorithm, its complexity scales with the square of the space dimension making it unsuitable for continuous tasks. We will now devise efficient strategies for estimating reliably
  the full posterior using the SMC methods covered in section 2.2.
sections.heading: 3.2 THE BACKWARD MESSAGE AND THE VALUE FUNCTION
sections.text: The backward message p(Oh+1:T |xh) can be understood as the answer to: “What is the probability of following an optimal trajectory from the next time step on until the end of the episode, given my current state?”. Importantly, this term is closely related to the notion of value function in RL. Indeed, in the control-as-inference framework, the state- and action-value functions are defined as V (sh) , log p(Oh:T |sh) and Q(sh,ah) , log p(Oh:T |sh,ah) respectively. They are solutions of a soft-Bellman equation that differs a little from the traditional Bellman equation (O’Donoghue et al., 2016; Nachum et al., 2017; Schulman et al., 2017; Abdolmaleki et al., 2018). A more in depth explanation can be found in (Levine, 2018). We can show subsequently that:
  p(Oh+1:T |xh) = Esh+1|xh [ exp ( V (sh+1) )] (3.2)
  Full details can be found in Appendix A.3. Estimating the backward message is then equivalent to learning a value function. This value function as defined here is the same one used in Maximum Entropy RL (Ziebart, 2010).
sections.heading: 3.3 SEQUENTIAL WEIGHT UPDATE
sections.text: Using the results of the previous subsections we can now derive the full update of the sequential importance sampling weights. To be consistent with the terminology of section 2.2, we call p(x1:h|O1:T )
  the target distribution and qθ(x1:h) the proposal distribution. The sequential weight update formula is in our case:
  wt = wt−1 · p(xt|x1:t−1,O1:T ) qθ(xt|x1:t−1)
  ∝ wt−1 1 qθ(xt|x1:t−1) p(x1:t|O1:t) p(x1:t−1|O1:t−1) p(Ot+1:T |xt) p(Ot:T |xt−1)
  ∝ wt−1 · Est+1|st,at [exp ( A(st,at, st+1) ) ]
  Where A(st,at, st+1) = rt − log πθ(at|st) + V (st+1)− logEst|st−1,at−1 [exp ( V (st) ) ] (3.3) is akin to a maximum entropy advantage function. The change in weight can be interpreted as sequentially correcting our expectation of the return of a trajectory.
  The full derivation is available in Appendix A.4. Our algorithm is similar to the Auxilliary Particle Filter (Pitt & Shephard, 1999) which uses a one look ahead simulation step to update the weights. Note that we have assumed that our model of the environment was perfect to obtain this slightly simplified form. This assumption is made by most planning algorithms (LQR, CEM . . . ): it entails that our plan is only as good as our model is. A typical way to mitigate this issue and be more robust to model errors is to re-plan at each time step; this technique is called Model Predictive Control (MPC) and is commonplace in control theory.
sections.heading: 3.4 SEQUENTIAL MONTE CARLO PLANNING ALGORITHM
sections.text: We can now use the computations of previous subsections to derive the full algorithm. We consider the root state of the planning to be the current state st. We aim at building a set of particles {x(n)t:t+h}Nn=1 and their weights {w(n)t+h}Nn=1 representative of the planning density p(xt:t+h|O1:T ) over optimal trajectories. We use SAC (Haarnoja et al., 2018) for the policy and value function, but any other Maximum Entropy policy can be used for the proposal distribution. Note that we used the value function estimated by SAC as a proxy the optimal one as it is usually done by actor critic methods.
  Algorithm 1 SMC Planning using SIR 1: for t in {1, . . . , T} do 2: {s(n)t = st}Nn=1 3: {w(n)t = 1}Nn=1 4: for i in {t, . . . , t+ h} do 5: // Update 6: {a(n)i ∼ π(a (n) i |s (n) i )}Nn=1
  7: {s(n)i+1, r (n) i ∼ pmodel(·|s (n) i ,a (n) i )}Nn=1 8: {w(n)i ∝ w (n) i−1 · exp ( A(s (n) i ,a (n) i , s (n) i+1) ) }Nn=1
  9: // Resampling 10: {x(n)1:i }Nn=1 ∼ Mult(n;w (1) i , . . . , w (N) i ) 11: {w(n)i = 1}Nn=1 12: end for 13: Sample n ∼ Uniform(1, N). 14: // Model Predictive Control 15: Select at, first action of x (n) t:t+h 16: st+1, rt ∼ penv(·|st,at) 17: Add (st,at, rt, st+1) to buffer B 18: Update π, V and pmodel with B 19: end for We summarize the proposed algorithm in Algorithm 1. At each step, we sample from the proposal distribution or model-free agent (line 6) and use our learned model to sample the next state and reward (line 7). We then update the weights (line 8). In practice we only use one sample to estimate the expectations, thus we may incur a small bias. The resampling step is then performed (line 10-11) by resampling the trajectories according to their weight. After the planning horizon is reached, we sample one of our trajectories (line 13) and execute its first action into the environment (line 15-16). The observations (st,at, rt, st+1) are then collected and added to a buffer (line 17) used to train the model as well as the policy and value function of the model-free agent. An alternative algorithm that does not use the resampling step (SIS) is highlighted in Algorithm 2 in Appendix A.6.
  A schematic view of the algorithm can also be found on figure 3.2.
sections.heading: 3.5 OPTIMISM BIAS AND CONTROL AS INFERENCE
sections.text: We now discuss shortcomings our approach to planning as inference may suffer from, namely encouraging risk seeking policies.
  1
  1
  1
  Bias in the objective: Trajectories having a high likelihood under the posterior defined in Equation 2.1 are not necessarily trajectories yielding a high mean return. Indeed, as logEp [ expR(x) ] ≥
  Ep [ R(x) ] we can see that the objective function we maximize is an upper bound on the quantity of interest: the mean return. This can lead to seeking risky trajectories as one very good outcome in logE exp could dominate all the other potentially very low outcomes, even if they might happen more frequently. This fact is alleviated when the dynamics of the environment are close to deterministic (Levine, 2018). Thus, this bias does not appear to be very detrimental to us in our experiments 4 as our environments are fairly close to deterministic. The bias in the objective also appears in many control as inference works such as Particle Value Functions (Maddison et al., 2017a) and the probabilistic version of LQR proposed in Toussaint (2009).
  Bias in the model: A distinct but closely related problem arises when one trains jointly the policy πθ and the model pmodel, i.e if q(x1:T ) is directly trained to approximate p(x1:T |O1:T ). In that case, pmodel(st+1|st,at) will not approximate penv(st+1|st,at) but penv(st+1|st,at,Ot:T ) (Levine, 2018). This means the model we learn has an optimism bias and learns transitions that are overly optimistic and do no match the environment’s behavior. This issue is simply solved by training the model separately from the policy, on transition data contained in a buffer as seen on line 18 of Algorithm 1.
sections.heading: 4 EXPERIMENTS
sections.heading: 4.1 TOY EXAMPLE
sections.text: In this section, we show how SMCP can deal with multimodal policies when planning. We believe multimodality is useful for exploring since it allows us to keep a distribution over many promising trajectories and also allows us to adapt to changes in the environment e.g. if a path is suddenly blocked.
  We applied two version of SMCP: i) with a resampling step (SIR) ii) without a resampling step (SIS) and compare it to CEM on a simple 2D point mass environment 4.1. Here, the agent can control the displacement on (x, y) within the square [0, 1]2, a = (∆x,∆y) with maximum magnitude ||a|| = 0.05. The starting position (•) of the agent is (x = 0, y = 0.5), while the goal (?) is at g = (x = 1, y = 0.5). The reward is the agent’s relative closeness increment to the goal:
  (a) Sequential Importance Resampling (SIR): when resampling the trajectories at each time step, the agent is able to focus on the promising trajectories and does not collapse on a single mode.
  (b) Sequential Importance Sampling (SIS): if we do not perform the resampling step the agent spends most of its computation on uninteresting trajectories and was not able to explore as well.
  (c) CEM: here the agent samples all the actions at once from a Gaussian with learned mean and covariance. We needed to update the parameters 50 times for the agent to find one solution, but it forgot the other one.
  Figure 4.1: Comparison of three methods on the toy environment. The agent (•) must go to the goal (?) while avoiding the wall ( | ) in the center. The proposal distribution is taken to be an isotropic gaussian. Here we plot the planning distribution imagined at t = 0 for three different agents. A darker shade of blue indicates a higher likelihood of the trajectory. Only the agent using Sequential Importance Resampling was able to find good trajectories while not collapsing on a single mode.
  rt = 1− ||st+1−g|| 2
  ||st−g||2 . However, there is a partial wall at the centre of the square leading to two optimal trajectories, one choosing the path below the wall and one choosing the path above.
  The proposal is an isotropic normal distribution for each planning algorithm, and since the environment’s dynamics are known, there is no need for learning: the only difference between the three methods is how they handle planning. We also set the value function to 0 for SIR and SIS as we do not wish to perform any learning. We used 1500 particles for each method, and updated the parameters of CEM until convergence. Our experiment 4.1 shows how having particles can deal with multimodality and how the resampling step can help to focus on the most promising trajectories.
sections.heading: 4.2 CONTINUOUS CONTROL BENCHMARK
sections.text: The experiments were conducted on the Open AI Gym Mujoco benchmark suite (Brockman et al., 2016; Todorov et al., 2012). To understand how planning can increase the learning speed of RL agents we focus on the 250000 first time steps. The Mujoco environments provide a complex benchmark with continuous states and actions that requires exploration in order to achieve state-of-the-art performances.
  The environment model used for our planning algorithm is the same as the probabilistic neural network used by Chua et al. (2018), it minimizes a gaussian negative log-likelihood model: LGauss(θ) = 12 N∑ n=1 [µθ(sn,an)−(sn+1−sn)]>Σ−1θ (sn,an)[µθ(sn,an)−(sn+1−sn)]+log detΣθ(sn,an),
  where Σθ is diagonal and the transitions (sn,an, sn+1) are obtained from the environment. We added more details about the architecture and the hyperparameters in the appendix A.5.
  We included two popular planning algorithms on Mujoco as baselines: CEM (Chua et al., 2018) and Random Shooting (RS) (Nagabandi et al., 2017). Furthermore, we included SAC (Haarnoja et al., 2018), a model free RL algorithm, since i) it has currently one of the highest performances on Mujoco tasks, which make it a very strong baseline, and ii) it is a component of our algorithm, as we use it as a proposal distribution in the planning phase.
  Our results suggest that SMCP does not learn as fast as CEM and RS initially as it heavily relies on estimating a good value function. However, SMCP quickly achieves higher performances than CEM and RS. SMCP also learns faster than SAC because it was able to leverage information from the model early in training.
  Note that our results differ slightly from the results usually found in the model-based RL literature. This is because we are tackling a more difficult problem: estimating the transitions and the reward function. We are using unmodified versions of the environments which introduces many hurdles. For instance, the reward function is challenging to learn from the state and very noisy. Usually, the environments are modified such that their reward can be computed directly from the state e.g. Chua et al. (2018) 3.
  As in Henderson et al. (2017), we assess the significance of our results by running each algorithm with multiple seeds (20 random seeds in our case, from seed 0 to seed 19) and we perform a statistical significance test following Colas et al. (2018). We test the hypothesis that our mean return on the last 100k steps is higher than the one obtained by SAC. Our results are significant to the 5% for HalfCheetah and Walker2d. See Appendix A.7 for additional details.
  We also report some additional experimental results such as effective sample size and model loss in Appendix A.8.
sections.heading: 5 RELATED WORK
sections.text: Planning as inference: Seeing planning as an inference problem has been explored in cognitive neuroscience by Botvinick & Toussaint (2012) and Solway & Botvinick (2012). While shedding light on how Bayesian inference could be used in animal and human reasoning, it does not lead to a practical algorithm usable in complex environments. In the reinforcement learning literature, we are only aware of Attias (2003) and Toussaint & Goerick (2007) that initially framed planning as an inference problem. However, both works make simplifying assumptions on the dynamics and do not attempt to capture the full posterior distribution.
  Control and planning: In the control theory literature, particle filters are usually used for inferring the true state of the system which is then used for control (Andrieu et al., 2004). Kantas et al. (2009) also combined SMC and MPC methods. While their algorithm is similar to ours, the distribution they approximate is not the Bayesian posterior, but a distribution which converges to a Dirac on the best trajectory. More recently, Kurutach et al. (2018) achieved promising results on a rope manipulation task using generative adversarial network (Goodfellow et al., 2014) to generate future trajectories.
  Model based RL: Recent work has been done in order to improve environment modeling and account for different type of uncertainties. Chua et al. (2018) compared the performance of models that account for both aleatoric and epistemic uncertainties by using an ensemble of probabilistic models. Ha & Schmidhuber (2018) combined the variational autoencoder (Kingma & Welling, 2013) and a LSTM (Hochreiter & Schmidhuber, 1997) to model the world. Buckman et al. (2018) used a model to improve the target for temporal difference (TD) learning. Note that this line of work is
  3https://github.com/kchua/handful-of-trials/tree/e1a62f217508a384e49ecf7d16a3249e187bcff9/ dmbrl/env
  complementary to ours as SMCP could make use of such models. Other works have been conducted in order to directly learn how to use a model (Guez et al., 2018; Weber et al., 2017; Buesing et al., 2018).
  Particle methods and variational inference: Gu et al. (2015) learn a good proposal distribution for SMC methods by minimizing the KL divergence with the optimal proposal. It is conceptually similar to the way we use SAC (Haarnoja et al., 2018) but it instead minimizes the reverse KL to the optimal proposal. Further works have combined SMC methods and variational inference (Naesseth et al., 2017; Maddison et al., 2017b; Le et al., 2017) to obtain lower variance estimates of the distribution of interest.
sections.heading: 6 CONCLUSION AND FUTURE WORK
sections.text: In this work, we have introduced a connection between planning and inference and showed how we can exploit advances in deep learning and probabilistic inference to design a new efficient and theoretically grounded planning algorithm. We additionally proposed a natural way to combine model-free and model-based reinforcement learning for planning based on the SMC perspective. We empirically demonstrated that our method achieves state of the art results on Mujoco. Our result suggest that planning can lead to faster learning in control tasks.
  However, our particle-based inference method suffers some several shortcomings. First, we need many particles to build a good approximation of the posterior, and this can be computationally expensive since it requires to perform a forward pass of the policy, the value function and the model for every particle. Second, resampling can also have adverse effects, for instance all the particles could be resampled on the most likely particle, leading to a particle degeneracy. More advanced SMC methods dealing with this issue such as backward simulation (Lindsten et al., 2013) or Particle Gibbs with Ancestor Sampling (PGAS) (Lindsten et al., 2014) have been proposed and using them would certainly improve our results.
  Another issue we did not tackle in our work is the use of models of the environment learned from data. Imperfect model are known to result in compounding errors for prediction over long sequences. We chose to re-plan at each time step (Model Predictive Control) as it is often done in control to be more robust to model errors. More powerful models or uncertainty modeling techniques can also be used to improve the accuracy of our planning algorithm. While the inference and modeling techniques used here could be improved in multiple ways, SMCP achieved impressive learning speed on complex control tasks. The planning as inference framework proposed in this work is general and could serve as a stepping stone for further work combining probabilistic inference and deep reinforcement learning.
sections.heading: ACKNOWLEDGMENTS
sections.text: The authors would like to thank Julien Cornebise, Philippe Beaudoin and Alexandre Bouchard-Côté for their interest and useful discussions. The authors would like to thank Stephanie Long, Anqi Xu, Kris Sankaran, Adrien Ali-Taı̈ga, Rémi Le Priol, and Christian Rupprecht for reviewing an earlier version of the paper. The authors want to thank the Open Philanthropy Project, NSERC, Canada Research Chairs, CIFAR AI Chairs, National Science Foundation awards EHR-1631428 and SES-1461535 as well as NVIDIA for equipment.
sections.heading: A APPENDIX
sections.heading: A.1 ABBREVIATION AND NOTATION
sections.heading: A.2 THE ACTION PRIOR
sections.text: The true joint distribution 2.1 in section 2.1 should actually be written:
  p(x1:T ,O1:T ) = µ(s1) T−1∏ t=1 penv(st+1|at, st) T∏ t=1 p(at) exp ( T∑ t=1 r(st,at) )
  = µ(s1) T−1∏ t=1 penv(st+1|at, st) exp ( T∑ t=1 r(st,at) + log p(at) )
  In Mujoco environments, the reward is typically written as
  r(st,at) = f(st)− α||at||22
  where f is a function of the state (velocity for HalfCheetah on Mujoco for example). The part α||at||22 can be seen as the contribution from the action prior (here a gaussian prior). One can also consider the prior to be constant (and potentially improper) so that is does not change the posterior p(x1:T |O1:T ).
  A.3 VALUE FUNCTION: BACKWARD MESSAGE p(Ot+1:T |xt) = ∫ xt+1 p(Ot+1:T ,xt+1|xt)dxt+1
  = ∫ xt+1 p(xt+1|xt,Ot+1:T )p(Ot+1:T |xt+1)dxt+1
  = ∫ st+1 penv(st+1|st,at) [∫ at+1 p(at+1|st+1,Ot+1:T ) expQ(st+1,at+1)dat+1 ] dst+1
  = ∫ st+1 penv(st+1|st,at) exp ( V (st+1) ) dst+1
  = Est+1|st,at [exp ( V (st+1) ) ] (A.1)
  By definition of the optimal value function in (Levine, 2018).
  A.4 RECURSIVE WEIGHTS UPDATE
  wt = p(x1:t|O1:T ) q(x1:t)
  = p(x1:t−1|O1:T ) q(x1:t−1) p(xt|x1:t−1,O1:T ) q(xt|x1:t−1) = wt−1 · p(xt|x1:t−1,O1:T ) q(xt|x1:t−1)
  = wt−1 1 q(xt|x1:t−1) p(x1:t|O1:T ) p(x1:t−1|O1:T )
  We use there the forward-backward equation 3.1 for the numerator and the denominator
  ∝ wt−1 1 q(xt|x1:t−1) p(x1:t|O1:t) p(x1:t−1|O1:t−1) p(Ot+1:T |xt) p(Ot:T |xt−1) = wt−1 p(xt|x1:t−1) q(xt|x1:t−1) p(Ot|xt) p(Ot+1:T |xt) p(Ot:T |xt−1)
  = wt−1 penv(st|st−1,at−1) pmodel(st|st−1,at−1) exp(rt) πθ(at|st) Est+1|st,at [exp
  ( V (st+1) ) ]
  Est|st−1,at−1 [exp ( V (st) ) ]
  = wt−1 penv(st|st−1,at−1) pmodel(st|st−1,at−1)
  Est+1|st,at [exp ( rt − log πθ(at|st) + V (st+1)− logEst|st−1,at−1 [exp ( V (st) ) ] ) ]
  (A.2)
sections.heading: A.5 EXPERIMENT DETAILS
sections.text: Random samples: 1000 transitions are initially collected by a random policy to pretrain the model and the proposal distribution. After which the agents start following their respective policy.
  Data preprocessing: We normalize the observations to have zero mean and standard deviation 1.
  Model Predictive Control: The model is used to predict the planning distribution for the horizon h of N particles. We then sample a trajectory according to its weight and return the first action of this trajectory. In our experiments, we fix the maximum number of particles for every method to 2500. For SMCP, the temperature and horizon length are described in Table A.3.
  Soft Actor Critic: We used a custom implementation with a Gaussian policy for both the SAC baseline and the proposal distribution used for both versions of SMCP. We used Adam (Kingma & Ba, 2014) with a learning rate of 0.001. The reward scaling suggested by Haarnoja et al. (2018) for all experiments and used an implementation inspired by Pong (2018). We used a two hidden layers with 256 hidden units for the three networks: the value function, the policy and the soft Q functions.
  Model: We train the model pmodel to minimize the negative log likelihood of p(st+1|st + ∆t(st, at), σt(st, at)). The exact architectures are detailed in Table A.3. We train the model to predict the distribution of the change in states and learn a deterministic reward function from the current state and predict the change in state. Additionally, we manually add a penalty on the action magnitude in the reward function to simplify the learning. At the end of each episode we train the model for 10 epochs. Since the training is fairly short, we stored every transitions into the buffer. The model is defined as:
  ∆st ∼ p(·|st, at) (A.3) rt = g(st,∆st)− α‖a‖2 (A.4)
  where α was taken from the Mujoco gym environments. We used Adam (Kingma & Ba, 2014) with a learning rate of 0.001 and leaky ReLU activation function.
sections.heading: A.6 SEQUENTIAL IMPORTANCE SAMPLING PLANNING
sections.text: Algorithm 2 SMC Planning using SIS 1: for t in {1, . . . , T} do 2: {s(n)t = st}Nn=1 3: {w(n)t = 1}Nn=1 4: for i in {t, . . . , t+ h} do 5: // Update 6: {a(n)i ∼ π(a (n) i |s (n) i )}Nn=1
  7: {s(n)i+1, r (n) i ∼ pmodel(·|s (n) i ,a (n) i )}Nn=1 8: {w(n)i ∝ w (n) i−1 · exp ( A(s (n) i ,a (n) i , s (n) i+1) ) }Nn=1
  9: end for 10: Sample n ∼ Categorical(w(1)t+h, . . . , w (N) t+h). 11: // Model Predictive Control 12: Select at, first action of x (n) t:t+h 13: st+1, rt ∼ penv(·|st,at) 14: Add (st,at, rt, st+1) to buffer B 15: Update π, V and pmodel with B 16: end for
sections.heading: A.7 SIGNIFICANCE OF THE RESULTS
sections.text: The significance of our results is done following guidelines from Colas et al. (2018). We test the hypothesis that the mean return of our method is superior to the one of SAC. We use 20 random seeds (from 0 to 19pro) for each method on each environment.
  For this we look at the average return from steps 150k to 250k for SIR-SAC and SAC, and conduct a Welch’s t-test with unknown variance. We report the p-value for each environment tested on Mujoco. A pval < 0.05 usually indicates that there is strong evidence to suggest that our method outperforms SAC.
  • HalfCheetah-v2: pval = 0.003. There is very compelling evidence suggesting we outperform SAC. • Hopper-v2: pval = 0.09. There is no significant evidence suggesting we outperform SAC. • Walker2d-v2: pval = 0.03. There is compelling evidence suggesting we outperform
  SAC.
sections.heading: A.8 ADDITIONAL EXPERIMENTAL RESULTS
sections.heading: A.8.1 EFFECTIVE SAMPLE SIZE
sections.text: The values reported on Figure A.1 are the harmonic mean of the ratio of the effective sample size by the actual number of particles.
  More precisely the values are
  yt = ( h∏ i=1 ESSi(t)/N )1/h
  where i is the depth of the planning, N is the number of particles and ESSi(t) = ( ∑N n=1 w (n) t+i)
  2∑N n=1(w (n) t+i) 2
  We can see that as the proposal distribution improves the ESS also increases. The ESS on HalfCheetah is representative of the one obtained on the other environments. While these values are not high, we are still around 15% thus we do not suffer heavily from weight degeneracy.
sections.heading: A.8.2 MODEL LOSS
sections.text: We also report the negative log likelihood loss of the environment’s model during the training on Figure A.2.
title: SEQUENTIAL MONTE CARLO METHODS