When is Particle Filtering Efficient for Planning in Partially Observed
  Linear Dynamical Systems?
  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.
