Title: PROBABILISTIC PLANNING WITH SEQUENTIAL MONTE CARLO METHODS

Abstract: 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. * both authors contributed equally.

1. INTRODUCTION:

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 & Lö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) x t = (s t , a t ) are the state-action pair variables considered here as latent.

Traditionally, in reinforcement learning (RL) problems, the goal is to find the optimal policy that maximizes the expected return

E q θ [ T t=1 γ t r t ]

. 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 O t denoting the "optimality" of a pair (s t , a t ) at time t and define its probability1 as p(O t = 1|s t , a t ) = exp(r(s t , a t )). O is a convenience variable only here for the sake of modeling. By considering the variables (s t , a t ) as latent and O t 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(a t |s t , O t:T ).

The posterior probability of this graphical model can be written as2 :

p(x 1:T |O 1:T ) ∝ p(x 1:T , O 1:T ) = µ(s 1 ) T -1 t=1 p env (s t+1 |a t , s t ) exp T t=1 r(s t , a t ) + log p(a t ) .

(2.1) It appears clearly that finding optimal trajectories is equivalent to finding plausible trajectories yielding a high return.

Many control as inference methods can be seen as approximating the density by optimizing its variational lower bound: (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(a t |s t , O t:T ) using the backward message, i.e a soft Q function instead of the Monte Carlo return.

log p(O 1:T ) ≥ E x 1:T ∼q θ [ T t=1 r(s t , a t ) -log π θ (a t |s t )]

2.2. SEQUENTIAL MONTE CARLO METHODS:

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) } N n=1 ∼ q; these are referred to as particles. The set of particles {x (n) } N n=1 associated with their weights {w (n) } N n=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), with x (n) sampled from q

where δ x0 (x) denotes the Dirac delta mass located as x 0 .

Sequential Importance Sampling (SIS): When our problem is sequential in nature x = x 1:T , sampling x 1: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: w t (x 1:t ) = w t-1 (x 1:t-1 ) p(xt|x1:t-1) q(xt|x1:t-1) . We call this the update step. This enables us to sample sequentially x t ∼ q(x t |x 1:t-1 ) to finally obtain the set of particles {x 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.

3. PLANNING AS PROBABILISTIC INFERENCE:

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(a 1 , s 2 , . . . s h , a h |O 1:T , s 1 ), where s 1 represents our current state.

3.1. PLANNING AND BAYESIAN SMOOTHING:

As we consider the current state s 1 given, it is equivalent and convenient to focus on the planning distribution with horizon h: p(x 1:h |O 1: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(x 1:h |O 1:T ) ∝ p(x 1:h |O 1:h ) • p(O h+1:T |x h ) (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.

x

1 x h-1 x h x h+1 x T O 1 O h-1 O h O h+1 O T p(x 1:h |O 1:h ) p(O h+1:T |x h ) Figure 3

.1: Factorization of the HMM into forward (orange) and backward (blue) messages. Estimating the forward message is filtering, estimating the value of the latent knowing all the observations is smoothing.

Filtering is the task of estimating p(x 1:t |O 1:t ): the probability of a latent variable conditioned on all past observations. In contrast, smoothing estimates p(x 1:t |O 1: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 (x h ) = p(x 1:h |O 1:h ) and back- ward message β h (x h ) = p(O h+1:T |x h )

, 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.

3.2. THE BACKWARD MESSAGE AND THE VALUE FUNCTION:

The backward message p(O h+1:T |x h ) 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 (s h ) log p(O h:T |s h ) and Q(s h , a h ) log p(O h:T |s h , a h ) 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(O h+1:T |x h ) = E s h+1 |x h exp V (s h+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) .

3.3. SEQUENTIAL WEIGHT UPDATE:

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(x 1:h |O 1:T )

the target distribution and q θ (x 1:h ) the proposal distribution. The sequential weight update formula is in our case:

w t = w t-1 • p(x t |x 1:t-1 , O 1:T ) q θ (x t |x 1:t-1 ) ∝ w t-1 1 q θ (x t |x 1:t-1 ) p(x 1:t |O 1:t ) p(x 1:t-1 |O 1:t-1 ) p(O t+1:T |x t ) p(O t:T |x t-1 ) ∝ w t-1 • E st+1|st,at [exp A(s t , a t , s t+1 ) ] Where A(s t , a t , s t+1 ) = r t -log π θ (a t |s t ) + V (s t+1 ) -log E st|st-1,at-1 [exp V (s t ) ] (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.

3.4. SEQUENTIAL MONTE CARLO PLANNING ALGORITHM:

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 s t . We aim at building a set of particles {x

(n) t:t+h } N n=1

and their weights {w

(n) t+h } N

n=1 representative of the planning density p(x t:t+h |O 1: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 = s t } N n=1 3: {w (n) t = 1} N n=1 4:

for i in {t, . . . , t + h} do 5:

// Update 6: {a (n) i ∼ π(a (n) i |s (n) i )} N n=1 7: {s (n) i+1 , r (n) i ∼ p model (•|s (n) i , a (n) i )} N n=1 8: {w (n) i ∝ w (n) i-1 • exp A(s (n) i , a (n) i , s (n) i+1 ) } N n=1 9: // Resampling 10: {x (n) 1:i } N n=1 ∼ Mult(n; w (1) i , . . . , w (N ) i ) 11: {w (n) i = 1} N n=1 12:

end for 13:

Sample n ∼ Uniform(1, N ).

14: 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 (s t , a t , r t , s t+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.

// Model

A schematic view of the algorithm can also be found on figure 3.2.

3.5. OPTIMISM BIAS AND CONTROL AS INFERENCE:

We now discuss shortcomings our approach to planning as inference may suffer from, namely encouraging risk seeking policies. t .

We have one particle on the leftmost branch, two on the central branch and one on the rightmost branch. Figure 3 .2: Schematic view of Sequential Monte Carlo planning. In each tree, the white nodes represent states and black nodes represent actions. Each bullet point near a state represents a particle, meaning that this particle contains the total trajectory of the branch. The root of the tree represents the root planning state, we expand the tree downward when planning.

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 log E p exp R(x) ≥ E p 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 log E 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 p model , i.e if q(x 1:T ) is directly trained to approximate p(x 1:T |O 1:T ). In that case, p model (s t+1 |s t , a t ) will not approximate p env (s t+1 |s t , a t ) but p env (s t+1 |s t , a t , O t: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.

4. EXPERIMENTS:



4.1. TOY EXAMPLE:

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. 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.

r t = 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.

4.2. CONTINUOUS CONTROL BENCHMARK:

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:

L Gauss (θ) = 1 2 N n=1 [µ θ (s n , a n )-(s n+1 -s n )] Σ -1 θ (s n , a n )[µ θ (s n , a n )-(s n+1 -s n )]+log detΣ θ (s n , a n ),

where Σ θ is diagonal and the transitions (s n , a n , s n+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.

5. RELATED WORK:

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 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.

6. CONCLUSION AND FUTURE WORK:

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.

A APPENDIX:

A.1 ABBREVIATION AND NOTATION The true joint distribution 2.1 in section 2.1 should actually be written:

p(x 1:T , O 1:T ) = µ(s 1 ) T -1 t=1 p env (s t+1 |a t , s t ) T t=1 p(a t ) exp T t=1 r(s t , a t ) = µ(s 1 ) T -1 t=1 p env (s t+1 |a t , s t ) exp T t=1 r(s t , a t ) + log p(a t )

In Mujoco environments, the reward is typically written as

r(s t , a t ) = f (s t ) -α||a t || 2

where f is a function of the state (velocity for HalfCheetah on Mujoco for example). The part α||a t || 2 2 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(x 1:T |O 1:T ).

A 

= E st+1|st,at [exp V (s t+1 ) ] (A.1)

By definition of the optimal value function in (Levine, 2018) .

A.4 RECURSIVE WEIGHTS UPDATE w t = p(x 1:t |O 1:T ) q(x 1:t ) = p(x 1:t-1 |O 1:T ) q(x 1:t-1 ) p(x t |x 1:t-1 , O 1:T ) q(x t |x 1:t-1 ) = w t-1 • p(x t |x 1:t-1 , O 1:T ) q(x t |x 1:t-1 ) = w t-1 1 q(x t |x 1:t-1 ) p(x 1:t |O 1:T ) p(x 1:t-1 |O 1:T )

We use there the forward-backward equation 3.1 for the numerator and the denominator

∝ w t-1 1 q(x t |x 1:t-1 ) p(x 1:t |O 1:t ) p(x 1:t-1 |O 1:t-1 ) p(O t+1:T |x t ) p(O t:T |x t-1 ) = w t-1 p(x t |x 1:t-1 ) q(x t |x 1:t-1 ) p(O t |x t ) p(O t+1:T |x t ) p(O t:T |x t-1 ) = w t-1 p env (s t |s t-1 , a t-1 ) p model (s t |s t-1 , a t-1 ) exp(r t ) π θ (a t |s t ) E st+1|st,at [exp V (s t+1 ) ] E st|st-1,at-1 [exp V (s t ) ] = w t-1 p env (s t |s t-1 , a t-1 ) p model (s t |s t-1 , a t-1 ) E st+1|st,at [exp r t -log π θ (a t |s t ) + V (s t+1 ) -log E st|st-1,at-1 [exp V (s t ) ] ] (A.2)

A.5 EXPERIMENT DETAILS 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 p model to minimize the negative log likelihood of p(s t+1 |s t + ∆ t (s t , a t ), σ t (s t , a t )). 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: 

∆s t ∼ p(•

EQUATION

i , s 

:

as inLevine (2018), if the rewards are bounded above, we can always remove a constant so that the probability is well defined.

Notice 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 inLevine (2018). We typically consider this term either constant or already included in the reward function. See Appendix A.2 for details.

https://github.com/kchua/handful-of-trials/tree/e1a62f217508a384e49ecf7d16a3249e187bcff9/ dmbrl/env

Figures and Tables:

} and their weights {w

Update: New actions and states are sampled from the proposal distribution and model. The particle sizes are proportional to their importance weight wt. Resampling: after sampling with replacement the particles relatively to their weight, the less promising branch was cut while the most promising has now two particles.

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.

Figure 4.2: Training curves on the Mujoco continuous control benchmarks. Sequential Monte Carlo Planning both with resampling (SIR) (pink) and without (SIS) (orange) learns faster than the Soft Actor-Critic model-free baseline (blue) and achieves higher asymptotic performances than the planning methods (Cross Entropy Methods and Random Shooting). The shaded area represents the standard deviation estimated by bootstrap over 20 seeds as implemented by the Seaborn package.

Figure A.2: Negative log likelihood for the model on HalfCheetah. The shaded area represents the standard deviation over 20 seeds.

methods are flexible and efficient to model such a

Table content: <table><tr><td>Observed</td><td>O 1</td><td>O 2</td><td>O 3</td><td>O t</td></tr><tr><td>Latent</td><td>a 1</td><td>a 2</td><td>a 3</td><td>a t</td></tr><tr><td/><td/><td/><td>. . . . . .</td><td/></tr><tr><td/><td>s 1</td><td>s 2</td><td>s 3</td><td>s t</td></tr></table>



Table content: <table><tr><td/><td/><td>.1: Abbreviation</td></tr><tr><td/><td>SMCP:</td><td>Sequential Monte Carlo Planning.</td></tr><tr><td/><td>SAC:</td><td>Soft Actor Critic.</td></tr><tr><td/><td>CEM:</td><td>Cross Entropy Method.</td></tr><tr><td/><td>RS:</td><td>Random Shooting.</td></tr><tr><td/><td>MCTS:</td><td>Monte Carlo Tree Search.</td></tr><tr><td/><td>SMC:</td><td>Sequential Monte Carlo.</td></tr><tr><td/><td colspan="2">SIR: Sequential Importance Resampling.</td></tr><tr><td/><td>SIS:</td><td>Sequential Importance Sampling.</td></tr><tr><td/><td>IS:</td><td>Importance Sampling.</td></tr><tr><td/><td>MPC:</td><td>Model Predictive Control</td></tr><tr><td/><td/><td>Table A.2: Notation</td></tr><tr><td>x 1:T</td><td colspan="2">{s i , a i } T i=1 the state-action pairs.</td></tr><tr><td>V</td><td colspan="2">value function.</td></tr><tr><td>O t p(O t |s t , a t )</td><td colspan="2">Optimality variable. exp(r(s t , a t )) Probability of a pair state action of being optimal.</td></tr><tr><td>w t</td><td colspan="2">Importance sampling weight.</td></tr><tr><td>p(x)</td><td colspan="2">Density of interest.</td></tr><tr><td>q(x)</td><td colspan="2">Approximation of the density of interest.</td></tr><tr><td>t ∈ {1, . . . T } n ∈ {1, . . . N }</td><td colspan="2">time steps. particle number.</td></tr><tr><td>h</td><td colspan="2">horizon length.</td></tr><tr><td colspan="2">A.2 THE ACTION PRIOR</td></tr></table>

t+1 |s t+1 , O t+1:T ) exp Q(s t+1 , a t+1 )da t+1 ds t+1 = st+1 p env (s t+1 |s t , a t ) exp V (s t+1 ) ds t+1

Table content: <table><tr><td colspan="3">.3 VALUE FUNCTION: BACKWARD MESSAGE</td></tr><tr><td>p(O t+1:T |x t ) =</td><td>xt+1</td><td>p(O t+1:T , x t+1 |x t )dx t+1</td></tr><tr><td>=</td><td>xt+1</td><td>p(x t+1 |x t , O t+1:T )p(O t+1:T |x t+1 )dx t+1</td></tr><tr><td>=</td><td>st+1</td><td>p env (s t+1 |s t , a t )</td></tr></table>

|s t , a t ) (A.3)r t = g(s t , ∆s t )α 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.

Table content: <table><tr><td colspan="4">Environment</td><td colspan="2">Temperature Horizon length Number of Dense Layers Layer Dimension</td></tr><tr><td colspan="2">Hopper-v2</td><td/><td/><td/><td>1</td><td>10</td><td>3</td><td>256</td></tr><tr><td colspan="3">Walker2d-v2</td><td/><td/><td>10</td><td>20</td><td>3</td><td>256</td></tr><tr><td colspan="4">HalfCheetah-v2</td><td/><td>10</td><td>20</td><td>3</td><td>256</td></tr><tr><td/><td/><td/><td/><td/><td>Table A.3: Hyperparameters for the experiments.</td></tr><tr><td colspan="6">A.6 SEQUENTIAL IMPORTANCE SAMPLING PLANNING</td></tr><tr><td colspan="6">Algorithm 2 SMC Planning using SIS</td></tr><tr><td>2: 3: 4:</td><td>{s {w (n) t (n) t</td><td colspan="4">n=1 = s t } N = 1} N n=1</td></tr><tr><td>5:</td><td colspan="3">// Update</td><td/></tr><tr><td>6: 7:</td><td colspan="2">{a (n) i</td><td colspan="2">∼ π(a</td><td>(n) i |s (n) i )} N n=1</td></tr></table>

Peer review (iclr2019):
 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. While the idea of viewing control as inference is far from new the idea of using SMC in this context is clearly novel as far as I can see. Well, there has been some work along the same general topic before, see e.g. Andrieu, C., Doucet, A., Singh, S.S., and Tadic, V.B. (2004). Particle methods for change detection, system identification, and contol. Proceedings of the IEEE, 92(3), 423–438. However, the particular construction proposed in this paper is refreshingly novel and interesting. Hence, I view the specific idea put fourth in this paper as highly novel. The general idea of viewing control as inference goes far back and there are very nice dual relationships between LQG and the Kalman filter established and exploited long time ago. The authors interprets "control as inference" as viewing the planning problem as a simulation exercise where we aim to approximate the distribution of optimal future trajectories. A bit more specifically, the SMC-based planning proposed in the paper stochastically explores the most promising trajectories in the tree and randomly removes (via the resampling operation) the less promising branches. Importantly there are convergence guarantees via the use of SMC. The idea is significant in that it opens up for the use of the by now strong SMC body of methods and analysis when it comes to challenging and intractable planning problems. I foresee many interesting developments to follow in the direction layed out by this paper. When it comes to your SMC algorithm you will suffer from path degeneracy (as all SMC algorithms does, see e.g. Figure 1 in https://arxiv.org/pdf/1307.3180.pdf) and if h is large I think this can be a problem for you. However, this can easily be fixed via backward simulation. For an overview of backward simulation see Lindsten, F. and Schon, T. "Backward simulation methods for Monte Carlo statistical inference". Foundations and Trends in Machine Learning, 6(1):1-143, 2013. I am positive to this paper (clearly reveled by my score as well), but there are of course a few issues as well: 1. There are no theoretical results on the properties of the proposed approach. However, given the large body of literature when it comes to the analysis of SMC methods I would expect that you can provide some results via the nice bridge that you have identified. 2. Would this be possible to implement in a real-world setting with real-time requirements? 3. A very detailed question when it comes to Figure 5.2 (right-most plot), why is the performance of your method significantly degraded towards the end? It does recover indeed, but I still find this huge dip quite surprising. Minor details: * The initial references when it comes to SMC are wrong. The first papers are: N.J. Gordon, D. Salmond and A.F.M. Smith, Novel approach to nonlinear/non-Gaussian Bayesian state estimation, IEE Proc. F, 1993 L. Stewart, P. McCarty, The use of Bayesian Belief Networks to fuse continuous and discrete information for target recognition and discrete information for target recognition, tracking, and situation assessment, in Proc. SPIE Signal Processing, Sensor Fusion and Target Recognition,, vol. 1699, pp. 177-185, 1992. G. Kitagawa, Monte Carlo filter and smoother for non-Gaussian nonlinear state-space models, JCGS, 1996 * When it comes to the topic of learning a good proposal for SMC with the use of variational inference the authors provide a reference to Gu et al. (2015) which is indeed interesting and relevant in this respect. However, on this hot and interesting topic there has recently been several related papers published and I would like to mention: C. A. Naesseth, S. W. Linderman, R. Ranganath, D. M. Blei, Variational Sequential Monte Carlo. Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, Lanzarote, Spain, April 2018. C. J. Maddison, D. Lawson, G. Tucker, N. Heess, M. Norouzi, A. Mnih, A. Doucet, and Y. Whye Teh. Filtering variational objectives. In Advances in Neural Information Processing Systems, 2017. T. A. Le, M. Igl, T. Jin, T. Rainforth, and F. Wood. AutoEncoding Sequential Monte Carlo. arXiv:1705.10306, May 2017. I would like to end by saying that I really like your idea and the way in which you have developed it. I have a feeling that this will inspire quite a lot of work in this direction.