DualSMC: Tunneling Differentiable Filtering and Planning under Continuous POMDPs

1 Introduction

Partially Observable Markov Decision Processes (POMDPs) formulate reinforcement learning problems where the agent's instant observation is insufficient for optimal decision making [Kaelbling et al., 1998]. Decision making with partial observations requires taking the history into account, which brings a high computation cost. It is a known result that finding the optimal policy in finite-horizon POMDPs is PSPACEcomplete [Papadimitriou and Tsitsiklis, 1987], which makes POMDPs difficult to solve in moderately large discrete spaces, let alone continuous domains.

Approximate solutions to POMDPs based on deep reinforcement learning can directly encode the history of past observations with deep models like RNNs [Hausknecht and Stone,

∗Equal contribution

†Code available at https://github.com/Cranial-XIX/DualSMC

2015; Karkus et al., 2017; Zhu et al., 2018; Igl et al., 2018; Hafner et al., 2019]. Learning is done in an end-to-end fashion and the resulting models can handle complex observations including visual inputs. However, since conventional POMDP problems usually present an explicit state formulation, executing the planning algorithm in a latent space makes it difficult to adopt any useful prior knowledge. Besides, whenever these models fail to perform well, it is difficult to analyze which part causes the failure as they are less interpretable.

In this work, we present a simple but effective model named Dual Sequential Monte Carlo (DualSMC). It preserves high interpretability since the state belief is represented by particles in real state spaces. It is also flexible for solving continuous POMDPs with complex observations and unknown dynamics. The idea of DualSMC is inspired by the recent successes on differentiable particle filters [Jonschkowski et al., 2018; Karkus et al., 2018] and the control as inference framework [Kappen et al., 2012; Levine, 2018; Piche et al., 2018]. In particular, DualSMC solves continuous POMDPs by connecting a SMC filter for state estimation with a SMC planner that samples in the optimal future trajectory space∗ .

Since the performance of the planner significantly depends on that of the filter, we introduce a novel adversarial training method to enhance the filter. Moreover, to connect the two parts and reduce the computational burden, we feed the top candidates of the state particles into the planner as the initial belief for uncertainty-aware action selection. The planner also takes as input the mean of the top state particles. To further improve robustness, we perform the model predictive control where only the first action of the plan is selected and we replan at each step. Notably, the learned dynamics is efficiently shared between filtering and model-based planning.

Our contributions to continuous POMDPs with DualSMC can be summarized as follows:

• It proposes a new differentiable particle filter (DPF) that leverages the adversarial relationship between the internals of the original DPF [Jonschkowski et al., 2018].

∗To distinguish the two SMCs, we call the first state estimation SMC the filter and its particles the state particles, and the second planning SMC the planner and its particles the trajectory particles.

• It introduces a new POMDP planning algorithm in forms of neural networks that extends the original sequential Monte Carlo planning [Piche et al., 2018] from fully observable scenarios to partially observable ones. The algorithm ties the transition model between the filter and the planner, bridges them via particle-based belief states, and learns the uncertainty-aware policy from the belief.
• It provides new benchmarks for continuous POMDPs: the floor positioning for explanatory purposes, the 3D light-dark navigation with rich visual inputs, and a control task in the Mujoco environment [Todorov et al., 2012]. DualSMC achieves the best results consistently.

2 Problem Setup

A continuous POMDP can be usually specified as a 7-tuple (S, A, T , R, Ω, Z, γ), where S, A and Ω are continuous state, action and observation spaces. We denote st ∈ S as the underlying state at time t. When the agent takes an action at ∈ A according to a policy π(at|o≤t, a<t), the state changes to st+1 with probability T (st+1|st, at). The agent will then receive a new observation ot+1 ∼ Z(ot+1|st+1) and a reward rt ∼ R(st, at). Assuming the episodes are of fixed length L, the agent's objective is then to maximize the expected cumulative future reward G = Eτ∼π [∑Lt=1 γ t-1 rt ], where τ = (s1, a1, . . . , aL, sL+1) are trajectories induced by π, and 0 ≤ γ < 1 is the discount factor. Since observations generally do not reveal the full state of the environment, the classical methods often maintain a belief over possible states, bel(st) ≜ p(st|o≤t, a<t), and update the belief according to

where η is a normalization factor. In this work, we make the true states available during training only as a supervised signal for the filter and keep them unobserved during testing. The key to solve continuous POMDPs is to perceive the state uncertainty and make decisions under such uncertainty.

3 RelatedWork

Planning under uncertainty. Due to the high computation cost of POMDPs, many previous approaches used samplingbased techniques for either belief update or planning, or both. For instance, a variety of Monte Carlo tree search methods have shown success in relatively large POMDPs by constructing a search tree of history based on rollout simulations [Silver and Veness, 2010; Somani et al., 2013; Seiler et al., 2015; Sunberg and Kochenderfer, 2018]. Later work further improved the efficiency by limiting the search space or reusing plans [Somani et al., 2013; Kurniawati and Yadav, 2016]. Although considerable progress has been made to enlarge the set of solvable POMDPs, it remains hard for pure sampling-based methods to deal with unknown dynamics and complex observations like visual inputs. Therefore, in this work, we provide one approach to combine the efficiency and interpretability of conventional sampling-based methods with the flexibility of deep learning networks for complex POMDP modeling.

Differentiable particle filter. Ever since its invention [Gordon et al., 1993], the Particle Filter (PF), or Sequential Monte Carlo (SMC), has become a well-suited method for sequential estimation in complex non-linear scenarios. A large number of research has made progress on learning a flexible proposal distribution for SMC† . Gu et al. [2015] was one of the earliest that use a recurrent neural network to model the proposal distribution. Naesseth et al. [2018] and Maddison et al. [2017] further provided a variational framework that learns a good parameterized proposal distribution by optimizing the log estimator. Recently, Karkus et al. [2018] and Jonschkowski et al. [2018] introduced differentiable particle filters independently and applied them to localization problems with rich visual input. These approaches explicitly treat the proposal distribution as three interleaved neural modules: a proposer that generates plausible states, a transition model that simulates dynamics, and an observation model that does Bayesian belief update. The filter in our model is based on [Jonschkowski et al., 2018], with an additional adversarial objective. Kempinska and Shawe-Taylor [2017] also proposed an adversarial training objective for SMC. But their objective is for learning the proposal distribution, while our method focuses more on mutually enhancing the proposer and observation model.

Planning as inference. The framework of control as probabilistic inference considers that selecting the optimal action is equivalent to finding the maximum posterior over actions conditioned on an optimal future [Todorov, 2008; Toussaint, 2009; Kappen et al., 2012; Levine and Koltun, 2013]. We refer to [Levine, 2018] as an explanatory review of these methods. Piche et al. [2018] extended this idea further to planning problems and propose the sequential Monte Carlo planning (SMCP), where the inference is done over optimal future trajectories. While most previous work focused on Markov Decision Processes (MDP) with full observation, we take one step further and apply the planning as inference framework to POMDP problems. On the other hand, compared with the existing Bayesian reinforcement learning literature on POMDPs [Ross et al., 2008], our work focuses more on deep reinforcement learning solutions to continuous POMDPs.

4 Dual Sequential Monte Carlo Network

In this section, we first introduce the adversarial particle filter that aims to mutually enhance the particle proposer model and the observation model. Then, we illustrate the design choice of our main algorithm and describe in detail how our method connects the two SMCs, during which we also introduce an alternative simpler formulation for SMCP [Piche et al., 2018].

4.1 Adversarial Particle Filtering

A particle filter represents a belief distribution bel(st) of the true state st with a set of weighted particles {(s(k) t ,w(k) t )}Kk=1 , where ∑Kk=1 w(k) t = 1. To perform Bayesian update when action is applied and a new observation comes in, it first transits

†The proposal distribution refers to the posterior distribution over the latent variables in an SMC. This should not be confused with the particle proposer model in this paper, which is a separate model that proposes possible state particles given observations.

Algorithm 1 Overall DualSMC algorithm

• 1: {s(k) 1 ∼ Priori(s1)}Kk=1, {w(k) 0 = 1}Kk=1 2: for t = 1 : L do 3: // At each filtering and control step 4: {w(k) t ∝ w(k) t-1 · Zθ(s(k) t , ot)}Kk=1 5: belt = ∑k w(k) t s(k) t 6: {˜ s(m) t , ˜w(m) t }Mm=1 = Top-M({s(k) t ,w(k) t }Kk=1),w.r.t.{w(k) t }k 7: at = DualSMC-P(belt, {˜ s(m) t , ˜w(m) t }Mm=1; πρ,Qω) 8: ot+1, rt ∼ penv(at) 9: if resample then 10: {s(k) t }K′ k=1 ∼ Multinomial({s(k) t }Kk=1),w.r.t.{w(k) t }k 11: {s(k) t ∼ Pφ(ot)}Kk=K′+1 , {w(k) t = 1}Kk=1 12: end if 13: {s(k) t+1 ∼ Tψ(s(k) t , at)}Kk=1 14: Add (st, st+1, at, rt, ot, belt, {˜ s(m) t , ˜w(m) t }Mm=1) to a buffer 15: Sample a batch from the buffer and update (ρ, ω, θ, ψ, φ)
• 16: end for

et al., 2018], we train the filter in an on-policy way so that it can take advantage of the gradually more powerful planner.

4.2 DualSMC Planning on Explicit Belief States

A straightforward solution to POMDP planning is to train the planning module separately from the filtering module. At inference time, plans are made independently based on each particle state. We thus name this planning algorithm the Particle-Independent SMC Planning (PI-SMCP) and use it as a baseline method. More details on PI-SMCP can be found in Appendix A. Although PI-SMCP is unbiased, it does not perform well in practice because it cannot generate policies based on dynamically varying state uncertainties.

We thus propose the DualSMC algorithm to explicitly consider the belief distribution by planning directly on an approximated belief representation, i.e., a combination of the top candidates from the filter (for computation efficiency) as well as the weighted mean estimate. We show the modules in DualSMC and how they relate to each other in Figure 1.

The overall algorithmic framework of DualSMC is shown in Alg 1. At time step t, when a new observation comes, we first use the observation model Zθ to update the particle weights

all particles according to a transition model and then update corresponding weights according to an observation model:

In practice, when the true dynamics T and Z are not known a priori, they can be approximated by the parameterized functions Tψ(·) and Zθ(·). Similar to [Jonschkowski et al., 2018], our differentiable particle filter contains three neural modules (Figure 1): the proposer Pφ(ot, ϵP ), the transition model Tψ(s(k) t-1 , at-1, ϵT ), and the observation model Zθ(ot, s(k) t ), where φ, ψ, θ are parameters. ϵP and ϵT are the Gaussian noises for stochastic models. To avoid the particle degeneracy problem [Doucet and Johansen, 2009], we perform Sequential Importance Resampling (SIR) together with the proposer model. Specifically, after the Bayesian update at time t, we sample K′ old particles {s(k) old }K′ k=1 with replacement based on the updated weight and combine them with (K - K′ ) newly proposed particles {s(k) new}Kk=K′+1 , and assign uniform weights for all particles. Depending on the task, we keep K′ constant or make (K -K′ ) follow an exponential decay.

The major difference between our filtering approach and [Jonschkowski et al., 2018] comes in by noticing that Pφ and Zθ are naturally opposite to yet dependent on each other. Following this intuition, instead of regressing the output of the proposer to the true state, we propose the adversarial proposing strategy. In particular, we train Zθ to differentiate the true state from all particle states and train Pφ to fool Zθ. Formally, denote preal(o≤t), preal(s|o≤t) as the real distributions over observations and the real posterior over s, Zθ and Pφ play the following two-player minimax game with function F (Zθ , Pφ):

During training, instead of using trajectories sampled from a random or heuristic policy [Jonschkowski et al., 2018; Karkus

Algorithm 2 DualSMC planner on estimated belief states

Input: belt, {˜ s(m) t , ˜w(m) t }Mm=1 Output: at 1: { ˜w(m) t }Mm=1 = Normalize({ ˜w(m) t }Mm=1) 2: {{ˆ s(m)(n) t = ˜ s(m) t }Mm=1, ˆw(n) t-1 = 1, bel(n) t = belt}Nn=1 3: for i = t : t +H do 4: // At each planning time step 5: {a(n) i ∼ πρ({ˆ s(m)(n) i }Mm=1, bel(n) i )}Nn=1 6: {ˆ s(m)(n) i+1 , r(m)(n) i ∼ Tψ(ˆ s(m)(n) i , a(n) i )}M,N m=1,n=1 7: {bel(n) i+1 = ∑m ˜w(m) t ˆ s(m)(n) i+1 }Nn=1 8: { ˆw(n) i ∝ ˆw(n) i-1 · exp (∑m ˜w(m) t A(m)(n) )}Nn=1 9: {x(n) i = ({ˆ s(m)(n) i+1 , ˆ s(m)(n) i }Mm=1, bel(n) i+1, a(n) i )}Nn=1 10: if resample then 11: {x(n) t:i }Nn=1 ∼Multinomial({x(n) t:i }Nn=1),w.r.t.{ ˆw(n) i }n 12: { ˆw(n) i = 1}Nn=1 13: end if 14: end for 15: at = first action of x(n) t:t+H , where n ∼ Uniform(1, . . . , N)

(line 4 in Alg 1), and then perform the DualSMC planning algorithm in Alg 2. We duplicate the top-M particles (for computation efficiency) and the mean belief state N times as the root states of N planning trajectories (line 1-2 in Alg 2). Different from the previous SMCP [Piche et al., 2018] method under full observations, the policy network πρ perceives the belief states and predicts an action based on the top-M particle states as well as the mean belief state (line 5 in Alg 2). We then perform N actions to M ×N states and use Tψ to predict the next states and rewards (line 6 in Alg 2). Since future observations o>t are not available at current time step, inspired by QMDP [Littman et al., 1995], we assume the uncertainty disappears at the next step, and thus approximate bel(n) i>t using the top-M transition states as well as a set of fixed filtering weights (line 7 in Alg 2). We update the planning weight of each planning trajectory by summarizing the advantages of each state using the initial M belief weights (line 8 in Alg 2). Here, we introduce an alternative advantage formulation that is equivalent to the one used in [Piche et al., 2018]:

At time t, Qω(ˆ s(m)(n) i-1 , a(n) i-1 ) and r(m)(n) i-1 are set to 0. It is a benefit, because according to Eq. (3.3) in the SMCP paper [Piche et al., 2018], the advantage in SMCP depends on both Q and the log expectation of V , which can be difficult to estimate accurately, while our approach only requires Q, which is much simpler. We leave the full derivation to Appendix B.

At the end of each planning time step, we may apply resampling when necessary over N planning trajectories‡ (line 11-12 in Alg 2.). When the planning horizon is reached, where i = t + H, we sample one planning trajectory (line 15 in Alg

‡The resampling steps in both filtering and planning algorithms may not be performed at every time step (more details in Table 1).

2) and feed its first action to the environment. We then go back to the filtering part and update the belief states by resampling, proposing, and predicting the next-step particle states (line 9-13 in Alg 1). Lastly, we train all modules of DualSMC, including the policy network, the critic network, and the three modules of the adversarial particle filter (line 14-15 in Alg 1).

5 Experiment

Our experiments are designed in the following way. First, we use a 2D Floor Positioning task to illustrate the effectiveness of both the adversarial proposing and that of the uncertainty-dependent planning. Next, we test the DualSMC network on a much harder navigation task with both high uncertainty and visual input. At least, we present a modified Reacher environment to further test DualSMC's performance beyond the navigation domain. All models are trained with the Adam optimizer [Kingma and Ba, 2015]. The training hyper-parameters are shown in Table 1. We tuned the number of filtering particles as it largely determines the quality of belief state estimation, which is the foundation of the subsequent DualSMC planning algorithm. After many trials, we finally set it to 100 for a balance between planning results and efficiency. All experimental results are averaged over 5 runs of training. Network details can be found in Appendix C.

5.1 Floor Positioning

Suppose there is a robot in a two-floor building as shown in Figure 2, who doesn't know which floor it resides on. It can only distinguish different floors by observation.

• State: It is defined as the robot's position in world coordinates (sx, sy), i.e., the axes in Figure 2.

• Action: It is defined as a = (∆sx, ∆sy) with a maximum magnitude of 0.05.
• Observation: It is defined as the robot's horizontal distances to the nearest left/right walls, and the vertical distances to ceiling/ground ot = (dx-, dx+, dy-, dy+)t . In the case of Figure 2, it starts with an observation of (0.95, 1.05, 0.3, 0.2), whatever floor it is on.
• Goal: The robot starts from a random position and is headed to different regions according to different floors. If it is on the first floor, the target area is around (2, 0.25) orange semicircle area); If the robot is on the second floor, the target area is around (0, 0.75). Only at training time, a reward of 100 is given at the end of each episode if the robot reaches the correct target area.

Starting from a gray area, the robot is very uncertain about its y-axis position. In the case of Figure 2, the estimated state can be (0.95, 0.3) or (0.95, 0.8). Only when the robot goes across a dashed blue line, from the gray area to the bright one, does it become certain about its y-axis position.

Figure 5: The DualSMC planner generates different polices based on the uncertainty of the perceived belief state

Learned policies. The first two rows in Figure 3 show the planning results by applying the SMCP algorithm [Piche et al., 2018] to the top-1 estimated particle state. Training the proposer with the mean squared loss is equivalent to regressing the proposed particles to the mean values of the multi-modal state distributions under partial observations. Thus, in the first example, the robot cannot make reasonable decisions due to incorrect estimation of plausible states. The second row in Figure 3 shows the moving and planning trajectories by using an adversarial particle filter (PF), which leads the proposed particle states closer to plausible states. The robot learns an interesting policy (along a path marked by red dots): it always goes rightwards at first, being unaware of its position until it reaches the wall, and then bouncing back at the wall. However, this policy is suboptimal, as it does not fully consider the uncertainty of the belief state. In contrast, DualSMC has learned to reduce uncertainty by making short detours at first, as shown by the last row in Figure 3. We have three findings. First, the robot learns to localize itself quickly and then approach the target area in fewer steps. Second, the adversarial PF works well: once the robot steps across the dashed blue line, the belief states quickly converge to the actual values, and the observation model maintains its confidence in the converged belief even when the robot moves back to the middle areas. Third, DualSMC generates probabilistic planning trajectories of moving up/down with different advantage values.

Quantitative comparisons. From Table 2, the final DualSMC model takes 26.9 steps to reach the target area, whilst the baseline model "Adversarial PF + SMCP" uses as many as 73.3 steps on average. Besides, we can see that the adversarial PF significantly outperforms other differentiable state estimation approaches, such as (1) the existing DPFs that perform density estimation [Jonschkowski et al., 2018], and (2) the deterministic LSTMmodel that was previously used as a strong baseline in [Karkus et al., 2018; Jonschkowski et al., 2018]. Also note that DualSMC models with regressive proposers are even worse than one without any proposer, which suggests that an inappropriate proposer may cause a negative effect on solving continuous POMDPs.

Does the adversarial training improve the DPF? Given partial observations, an ideal filter should derive a complete distribution of possible states instead of point estimation. Figure 4(a) compares the average RMSE between the true states and the filtered states by different models. The adversarial PF performs best, while the PF with the regressive proposer performs even worse than that without a proposer. A natural question arises: as the filtering error is also related to different moving trajectories of different models, can we eliminate this interference? For Figure 4(b), we train different filters without a planner. All filters follow the same expert trajectories, and the adversarial PF still achieves the best performance.

How does DualSMC adapt to different uncertainties? In a fully observable scenario, we suppress the filtering part of DualSMC and assume DualSMC plans upon a converged belief on the true state (sx, sy). That is to say, we take the true state to as the top-M particles (line 7 in Alg 1) before the planning part. The robot changes its plan from taking a detour shown in Figure 5(a) to walking toward the target area directly shown in Figure 5(b). It performs equally well to the standard SMCP, with a 100.0% success rate and an averaged 21.3 steps (v.s. 20.7 steps by SMCP). We may conclude that DualSMC provides policies based on the distribution of filtered particles. We may also conclude that DualSMC trained under POMDPs generalizes well to similar tasks with less uncertainty.

5.2 3D Light-Dark Navigation

We extend the 2D light-dark navigation domain [Platt Jr et al., 2010] to a visually rich environment simulated by DeepMind Lab [Beattie et al., 2016]. At the beginning of each episode, the robot is placed randomly and uniformly on one of the four platforms at the bottom (see Figure 6). The robot's goal is to navigate toward the central cave (marked in orange) while avoiding any of the four traps (marked by crosses). The maze is divided into upper and lower parts. Within the lower part, the robot travels in darkness, receives noisy visual input of a limited range (up to a fixed depth), and therefore suffers from high state uncertainty. When the robot gets to the upper part (the blue area), it has a clear view of the entire maze. We place decals as visual hints on the top walls of the maze to help the robot figure out its position. However, it has to be very close to the upper walls to see clearly what these decals are. The robot receives a positive reward of 100 when it reaches the goal and a negative reward of -100 when in a trap. At each time step, the robot's observation includes a 64 × 64 RGB image, its current velocity, and its orientation. We force it to move forward and only control its continuous orientation.

By considering the uncertainty, DualSMC methods outperform other baselines in success rate (see Table 3). An excessively large number of steps indicates that the robot is easy to get lost while too few steps means that it is easy to fall into a trap. From Figure 6, DualSMC is the only one that learned to go up and figure out its position first before going directly towards the goal.

5.3 Modified Reacher

We further validate our model on a continuous control task with partial observation, i.e., a modified Reacher environment from OpenAI Gym [Brockman et al., 2016]. The original observation of Reacher is a 11-D vector including (cos θ1, cos θ2, sin θ1 sin θ2, gx, gy, ω1, ω2, rx, ry, rz), where the first 4 dimensions are cos/sin values of the two joint angles θ1, θ2, gx, gy the goal position, ω1, ω2 the angular velocities and rx, ry, rz the relative distance from the end-effector to the goal. We remove gx, gy, rx, ry, rz from the original observation and include a single scalar r = ||(rx, ry, rz)||2 + ϵr, where ϵr ∼ N(0, 0.01) is a small noise (r is usually on the scale of 0.1). The observation is therefore a 7-D vector. The robot has to simultaneously locate the goal and reach it.

We provide a visualization of one sample run under DualSMC with the adversarial filter in Figure 7. As expected, initially the proposed particles roughly are in a half-cycle and as time goes on, the particles gradually concentrate around the true goal. Since the final performance of various methods is similar after long enough time of training, we provide the training curve of these methods in Figure 8, and truncate the results up to 5,000 episodes since no obvious change in performance is observed from thereon. As we can see, the DualSMC methods not only achieve similar asymptotic performance as the SMCP method with full observation but also learn faster to solve the task than baseline methods.

6 Conclusion

In this paper, we provided an end-to-end neural network named DualSMC to solve continuous POMDPs, which has three advantages. First, it learns plausible belief states for highdimensional POMDPs with an adversarial particle filter. For simplicity, we use the na¨ıve adversarial training method from the original GANs [Goodfellow et al., 2014]. One may potentially improve DualSMC with modern techniques to stabilize training and lessen mode collapse. Second, DualSMC plans future actions by considering the distributions of the learned belief states. The filter module and the planning module are jointly trained and facilitate each other. Third, DualSMC combines the richness of neural networks as well as the interpretability of classical sequential Monte Carlo methods. We empirically validated the effectiveness of DualSMC on different tasks including visual navigation and control.

Acknowledgments

This work is in part supported by ONR MURI N00014-16-12007.

A Particle-Independent SMC Planning

As shown in Alg 3, it takes the top-M particle states (for computation efficiency) and plans N future trajectories independently based on each particle state. At the end of the planning horizon H, it samples a trajectory fromM×N planning trajectories. Although PI-SMCP is unbiased, it does not perform well in practice because it cannot generate policies based on dynamically varying state uncertainties.

B A Simpler Formulation of SMC Planning

At time t, we set Qω(ˆ s(m)(n) i-1 , a(n) i-1 ) and r(m)(n) i-1 in Eq. (4) to 0. We emphasize that our formulation is much simpler than the original SMCP [Piche et al., 2018]. Because it only requires a learned Q function and more importantly, it prevents us from estimating the expectation of the value function V . To prove this, we depict the Hidden Markov Model of our planning algorithm for ease of notation. Figure 9 is borrowed from [Piche et al., 2018]. Ot is a convenience binary variable here for the sake of modeling, denoting the "optimality" (optimal policy) of a pair (st, at) at time t [Levine, 2018]. Then we present the derivation of line 8 Alg 2 as follows. Comparing with [Piche et al., 2018], our update of the planning particle weights depends only on the learned Q and πρ.

C Network Details

Table 4 shows the network details for the floor positioning domain and the 3D dark-light domain.

Algorithm 3 Particle-Independent SMC Planning

Table 4: Network details of each module in DualSMC