When is Particle Filtering Efficient for Planning in Partially Observed Linear Dynamical Systems?
arXiv:2006.05975
Abstract
Particle filtering is a popular method for inferring latent states in stochastic dynamical systems, whose theoretical properties have been well studied in machine learning and statistics communities. In many control problems, e.g., partially observed linear dynamical systems (POLDS), oftentimes the inferred latent state is further used for planning at each step. This paper initiates a rigorous study on the efficiency of particle filtering for sequential planning, and gives the first particle complexity bounds. Though errors in past actions may affect the future, we are able to bound the number of particles needed so that the long-run reward of the policy based on particle filtering is close to that based on exact inference. In particular, we show that, in stable systems, polynomially many particles suffice. Key in our proof is a coupling of the ideal sequence based on the exact planning and the sequence generated by approximate planning based on particle filtering. We believe this technique can be useful in other sequential decision-making problems.
References in corpus (14)
- Koopman invariant subspaces and finite linear representations of nonlinear dynamical systems for control
- On the role of interaction in sequential Monte Carlo algorithms
- Improper Learning for Non-Stochastic Control
- Online Control with Adversarial Disturbances
- Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis
- Logarithmic Regret for Online Control
- Robust Guarantees for Perception-Based Control
- Logarithmic Regret for Adversarial Online Control
- Sequential Monte Carlo as Approximate Sampling: bounds, adaptive resampling via -ESS, and an application to Particle Gibbs
- Making Non-Stochastic Control (Almost) as Easy as Stochastic
- Analysis of error propagation in particle filters with approximation
- DualSMC: Tunneling Differentiable Filtering and Planning under Continuous POMDPs
- Fast rates for online learning in Linearly Solvable Markov Decision Processes
- Integrating Algorithmic Planning and Deep Learning for Partially Observable Navigation