Bellman filter

This article is about the state estimation algorithm for state-space models. For the dynamic programming recurrence, see Bellman equation. For other uses, see Bellman (disambiguation).

The Bellman filter is a recursive algorithm for estimating a sequence of unobserved (latent) states in a state-space model from noisy observations. It is typically formulated for models with a linear–Gaussian state transition and a possibly nonlinear and/or non-Gaussian observation density, and it updates the state by solving a per-time-step optimisation problem involving $\log p(y_{t}|x_{t})$. Under linear–Gaussian observation models, it reduces to the standard Kalman filter update.

Bellman filter

Class	Nonlinear filter; recursive state estimator
Data structure	State-space model (latent state and observations)
Worst-case performance	Per time step: Kalman-style prediction plus numerical optimisation in the update step (model- and method-dependent)
Worst-case space complexity	Stores state estimates and covariance matrices (dimension-dependent)

Background

In a discrete-time state-space model, an unobserved state vector evolves over time and generates observations. The linear–Gaussian case admits an optimal recursive solution via the Kalman filter, and standard econometric treatments include the monographs by Harvey and by Durbin & Koopman.

For nonlinear and/or non-Gaussian observation models, exact filtering generally becomes intractable and practical methods rely on approximation (e.g. extended/iterated Kalman filtering) or simulation (e.g. particle filters). The Bellman filter is often presented as a “filtering-by-optimisation” alternative that tracks a posterior mode at each time step.

Model and notation

Although the approach is more generally applicable, a commonly used specification keeps the classic linear–Gaussian state transition while allowing a general observation density. For $t=1,\dots ,n$:

• Observation equation:

$y_{t}\sim p(y_{t}|x_{t})$

• State-transition equation:

$x_{t}=c+Tx_{t-1}+R\eta _{t}$ where $\eta _{t}\sim {\text{i.i.d. }}{\mathcal {N}}(0,Q)$.

The filter maintains predicted quantities ${\hat {x}}_{t\mid t-1}$, $P_{t\mid t-1}$ and filtered quantities ${\hat {x}}_{t\mid t}$, $P_{t\mid t}$.

Fisher information

For the observation model, Fisher information is defined as: $I(x):=\int \left[-\nabla ^{2}\log p(y|x)\right]\,p(y|x)\,dy,$ where $\nabla ^{2}$ operates on $x$.

Algorithm

Prediction step

${\hat {x}}_{t\mid t-1}=c+T{\hat {x}}_{t-1\mid t-1},$

$P_{t\mid t-1}=TP_{t-1\mid t-1}T^{\top }+RQR^{\top }.$

This is identical to the prediction step in the Kalman filter.

Updating step

${\hat {x}}_{t\mid t}=\arg \max _{x\in \mathbb {R} ^{d}}\left\{\log p(y_{t}|x)-{\tfrac {1}{2}}(x-{\hat {x}}_{t\mid t-1})^{\top }P_{t\mid t-1}^{-1}(x-{\hat {x}}_{t\mid t-1})\right\},$

$P_{t\mid t}=\left(P_{t\mid t-1}^{-1}+I({\hat {x}}_{t\mid t})\right)^{-1}.$

The update step is well defined e.g. if $\log p(y_{t}|x)$ is concave in $x$ or if $P_{t\mid t-1}^{-1}$ is sufficiently large. In some cases, the Fisher information in the formula for $P_{t\mid t}$ can be replaced by the realised negative Hessian $-\nabla ^{2}\log p(y_{t}|{\hat {x}}_{t\mid t})$.

Special cases and relationships

Linear–Gaussian observation equation

If $y_{t}=d+Zx_{t}+\varepsilon _{t}$ where $\varepsilon _{t}\sim {\text{i.i.d. }}{\mathcal {N}}(0,H)$, then the update reduces to the Kalman filter update.

Iterated (extended) Kalman filtering

A Gauss–Newton interpretation of iterated Kalman updates appears in Bell and Cathey.

Smoothing

With a linear–Gaussian state transition, standard Rauch-Tung-Striebel (RTS) fixed-interval smoothing recursions can be used to obtain smoothed estimates ${\hat {x}}_{t\mid n}$ and $P_{t\mid n}$ from the filtered output.

Further reading

• Durbin, J.; Koopman, S. J. (2012). Time Series Analysis by State Space Methods (2nd ed.). Oxford University Press. ISBN 978-0199641178.
• Harvey, A. C. (1990). Forecasting, Structural Time Series Models and the Kalman Filter. Cambridge University Press. ISBN 978-0521405737.
• Lange, R.-J. (2024). "Short and simple introduction to Bellman filtering and smoothing". arXiv:2405.12668 [stat.ME].
• Kalman, R. E. (1960). "A New Approach to Linear Filtering and Prediction Problems". Journal of Basic Engineering. 82 (1): 35–45. doi:10.1115/1.3662552.
• Rauch, H. E.; Tung, F.; Striebel, C. T. (1965). "Maximum likelihood estimates of linear dynamic systems". AIAA Journal. 3 (8): 1445–1450. doi:10.2514/3.3166.