When is particle filtering efficient for planning in partially observed linear dynamical systems?

Simon S. Du, Wei Hu, Zhiyuan Li, Ruoqi Shen, Zhao Song, Jiajun Wu

Abstract

Particle filtering is a cornerstone method for state estimation in dynamical systems, yet its theoretical guarantees when integrated into sequential planning frameworks have remained largely unexplored. This paper establishes the first rigorous particle complexity bounds for planning in Partially Observed Linear Dynamical Systems (POLDS). We demonstrate that for stable systems, a polynomial number of particles is sufficient to achieve long-term rewards comparable to those obtained via exact, computationally intractable inference. However, we also identify a fundamental bottleneck: the required particle count scales inversely with the likelihood of the observation sequence, a dependency that can become problematic in certain regimes.

Introduction

In many real-world control scenarios, such as autonomous robot navigation or industrial process control, agents operate under partial observability. These systems are often modeled as Partially Observed Linear Dynamical Systems (POLDS), where the underlying "latent" state must be inferred from noisy, incomplete observations.

Unless the system's noise is strictly Gaussian—allowing for the use of the Kalman filter—calculating the exact posterior distribution of the latent state is computationally infeasible. To circumvent this, practitioners typically rely on Particle Filtering (PF), which uses a set of discrete samples (particles) to approximate the state distribution. While the statistics community has extensively studied PF for inference, its application to sequential planning introduces a new layer of complexity: approximation errors in inference lead to suboptimal actions, which in turn alter the system's future states. This paper addresses the fundamental question: How many particles are required to ensure that a policy guided by particle filtering performs nearly as well as one guided by exact inference?

Methodology: The Coupling Technique

Analyzing sequential planning is challenging because particles are not independent; the actions taken at each step depend on the previous state of the particles, creating complex correlations over time. To address this, the authors employ a coupling technique. They compare the approximate PF-based planning process with an ideal exact-inference process by subjecting both to the identical sequence of simulated transition and observation noise.

The core innovation lies in decoupling the noise. Instead of tracking the joint distribution of particles, the authors isolate the particle approximation of the noise at each individual round. Since the simulated noise within each particle is independent, it can be bounded using standard concentration inequalities. The researchers then calculate how these single-step errors propagate and accumulate through the planning horizon for both general Lipschitz (non-linear) policies and specialized linear policies.

Key Theoretical Insights

1. Polynomial Sufficiency for Stable Systems

The research proves that if a dynamical system is "stable"—meaning its growth rate is bounded and small deviations in actions do not cause catastrophic divergence—the number of particles required does not explode. Specifically, the complexity scales polynomially with the planning horizon ($T$), the system dimensions ($d$), and the sensitivity of the reward function.

2. The Observation Likelihood Bottleneck

A critical finding is that the required number of particles scales linearly with $1/p$, where $p$ represents the likelihood of the actual sequence of observations. The authors demonstrate that this is not merely a loose bound but a fundamental limitation of standard particle filtering. They construct a 1D mathematical process showing that if the number of particles $N$ falls below $1/(2kp)$, the weights of all particles will likely drop to zero, rendering the filter ineffective.

Results and Complexity Bounds

The paper provides non-asymptotic upper bounds for two classes of policies:

  • Non-linear (Lipschitz) Policies: To achieve a reward within $\epsilon$ of the ideal policy with high probability, the number of particles $N$ must scale as $\tilde{O}(T^2 \Delta_T^2 d m^{-1} \epsilon^{-2} p^{-1})$. Here, $\Delta_T$ represents the system's stability constant and $m$ relates to the noise distribution.
  • Linear Policies: For policies of the form $g(x) = Gx$, the authors provide a tighter bound by exploiting the mathematical structure of linearity to refine the stability constants.

Limitations and Future Outlook

While this work provides a foundational theoretical framework, it highlights a significant challenge: in some processes, the observation likelihood $p$ can decrease exponentially as the time horizon $T$ grows. This implies that standard particle filtering may still require an exponential number of particles for very long horizons in specific system configurations.

Future research directions include:

  • Advanced Algorithms: Analyzing Particle Filtering with Resampling, which may offer more robust complexity bounds and potentially mitigate the $1/p$ dependency.
  • Nonlinear Dynamics: Extending the current linear framework to nonlinear systems, perhaps by utilizing Koopman operator theory to linearize complex dynamics.

By establishing these first-of-their-kind bounds, this paper provides a theoretical justification for the use of particle filters in control and sets the stage for more efficient algorithm design in partially observed environments.

Summary updated

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.
BibTeX
@inproceedings{du2021when,
  author = {Simon S. Du and Wei Hu and Zhiyuan Li and Ruoqi Shen and Zhao Song and Jiajun Wu},
  title = {{When is particle filtering efficient for planning in partially observed linear dynamical systems?}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
}
Figure