Learning the Kalman Filter with Fine-Grained Sample Complexity

Xiangyuan Zhang, Bin Hu, Tamer Basar

Introduction

The Kalman Filter (KF) is a cornerstone of modern control theory and signal processing, providing optimal state estimation for linear systems subject to stochastic noise. While Reinforcement Learning (RL) has achieved significant success in the "control" domain—most notably with the Linear Quadratic Regulator (LQR)—the "estimation" domain has proven significantly more resistant to model-free approaches. This paper addresses this gap by providing the first end-to-end sample complexity analysis for learning a Kalman Filter using model-free policy gradient methods.

The Challenge of Model-Free Estimation

In the context of LQR, the objective is to learn a static gain matrix. In contrast, the Kalman Filter is itself a dynamical system. This distinction introduces a complex, non-convex optimization landscape characterized by potential suboptimal stationary points.

Historically, model-free attempts to learn the KF have relied on restrictive assumptions, such as requiring the underlying system to be open-loop stable or assuming the existence of a "stabilizing" initial filter guess. In many real-world applications, these assumptions are unrealistic. The primary hurdle is ensuring that the learning process can navigate the non-convex landscape to find the global optimum without getting trapped or requiring a high-quality initialization.

The Receding-Horizon Policy Gradient (RHPG-KF) Framework

To overcome these landscape challenges, the authors introduce the Receding-Horizon Policy Gradient (RHPG-KF) framework. This approach leverages Dynamic Programming (DP) to transform a difficult infinite-horizon problem into a manageable sequence of subproblems.

1. Decomposition and Sequential Optimization

The framework decomposes the infinite-horizon KF problem into $N$ finite-horizon subproblems. Instead of optimizing the entire filter at once, the algorithm solves these subproblems sequentially. For each step $h$, the filter parameters learned in previous steps are fixed, and only the current step's parameters are optimized. This sequential structure effectively turns a non-convex problem into a series of strongly-convex quadratic programs.

2. Model-Free Zeroth-Order Oracle

Because the system matrices ($A, C$) are unknown, the algorithm employs a two-point zeroth-order oracle. This oracle estimates the gradient by applying small perturbations to the filter parameters and observing the resulting change in the Mean Square Error (MSE) within a simulator. This allows the framework to remain entirely model-free.

3. Error Propagation and Stability

A critical contribution of the paper is the rigorous proof that errors in early stages of the receding horizon do not accumulate catastrophically. The authors demonstrate that by solving each subproblem with sufficient accuracy, the final accumulated error remains bounded within a target $\epsilon$.

Key Results and Insights

Sample Complexity

The paper establishes a fine-grained sample complexity of $\tilde{O}(\epsilon^{-2})$ to reach an $\epsilon$-optimal filter. This result is significant because it matches the best-known sample complexity for the model-free LQR problem, suggesting that estimation is not fundamentally more difficult than control when approached through the lens of receding-horizon optimization.

Handling Unstable Systems

Unlike previous methodologies, RHPG-KF does not require the system to be open-loop stable. By building the filter forward from the initial time step, the algorithm can learn to stabilize the estimation error from scratch. This was validated through synthetic experiments:

  • Scalar Example: A 1D system where the system is open-loop unstable ($A=2$).
  • Vector Example: A higher-dimensional system with a spectral radius $\rho(A) \approx 10.1$. In both cases, the algorithm successfully converged to the optimal gain.

Convergence Rates

The authors show that the finite-horizon Kalman gain converges exponentially fast to the optimal infinite-horizon gain, providing a theoretical justification for the efficiency of the receding-horizon approach.

Limitations and Future Directions

While this work represents a major step forward, several challenges remain:

  • Simulator Dependency: The current method assumes a simulator that provides exact state trajectories during training, even if the algorithm only utilizes the noisy objective value. Future work could explore relaxing this to purely offline data.
  • The LQG Bridge: Integrating this learned filter with model-free LQR to solve the full Linear-Quadratic-Gaussian (LQG) problem is complex. LQG systems lack the "guaranteed margins" found in LQR, meaning small errors in the learned filter could potentially destabilize the entire control loop.
  • Robustness: Extending this analysis to adversarial settings, such as robust $H_\infty$ filtering, remains an open area for research.

Conclusion

By reframing the Kalman Filter learning problem through a receding-horizon lens, this paper demonstrates that the estimation side of the LQG problem is as tractable as the control side. The $\tilde{O}(\epsilon^{-2})$ sample complexity and the ability to handle unstable systems without a stabilizing initial guess mark a significant advancement in the theoretical foundations of model-free reinforcement learning for dynamical systems.

Summary updated

BibTeX
@inproceedings{zhang2023learning,
  author = {Xiangyuan Zhang and Bin Hu and Tamer Basar},
  title = {{Learning the Kalman Filter with Fine-Grained Sample Complexity}},
  booktitle = {ACC},
  year = {2023},
  doi = {10.23919/acc55779.2023.10156641},
}
Figure