Bellman filter

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)

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.

From a dynamic-programming perspective, the Bellman filter applies Bellman's principle of optimality to a mode-estimation problem, yielding a recursion for an (online) maximisation objective whose maximiser is a filtered state estimate. In contrast with grid-based maximisation (as in the Viterbi algorithm for models with discrete states), the Bellman filter keeps the state space continuous and replaces the exact Bellman value functions by parametric (typically quadratic) function-space approximations, which makes the recursion computationally feasible in moderate to high dimensions.

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 can be presented as a dynamic-programming-based alternative using function-space approximations of the value function 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+T{x}_{t-1}+R{\eta }_t$ where ${\eta }_t\sim \text{i.i.d. }{𝒩}(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 [-{\mathrm{\nabla }}^2\log p(y|x)]p(y|x)dy,$ where ${\mathrm{\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}=T{P}_{t-1\mid t-1}{T}^{\mathrm{\top }}+RQ{R}^{\mathrm{\top }}.$

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

Updating step

${\hat{x}}_{t\mid t}=\arg \underset{x\in {\mathbb{ℝ}}^d}{\max }\{\log p(y_t|x)-\frac{1}{2}(x-{\hat{x}}_{t\mid t-1}{)}^{\mathrm{\top }}{P}_{t\mid t-1}^{-1}(x-{\hat{x}}_{t\mid t-1})\},$

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

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

The maximisation can be interpreted as a maximum a posteriori (MAP) estimate of $x_t$: it combines the log-likelihood term $\log p(y_t|x_t)$ with a quadratic log-prior coming from the Gaussian prediction $x_t|y_{1:t-1}\sim {𝒩}({\hat{x}}_{t\mid t-1},P_{t\mid t-1})$. Equivalently, the update solves a regularised likelihood problem: it chooses the state that best explains $y_t$ while penalising deviation from the predicted mean ${\hat{x}}_{t\mid t-1}$ according to the precision $P_{t\mid t-1}^{-1}$.

Special cases and relationships

Linear–Gaussian observation equation

If $y_t=d+Z{x}_t+{\epsilon }_t$ where ${\epsilon }_t\sim \text{i.i.d. }{𝒩}(0,H)$, then the level update ${\hat{x}}_{t\mid t}$ and covariance update $P_{t\mid t}$ reduce to the usual Kalman filter update.

Iterated (extended) Kalman filtering

For a nonlinear observation equation with additive Gaussian noise, $y_t=h(x_t)+{\epsilon }_t,$ with ${\epsilon }_t\sim {𝒩}(0,H)$, the Bellman update objective is proportional to the (negative) nonlinear least-squares criterion $\frac{1}{2}(y_t-h(x){)}^{\mathrm{\top }}{H}^{-1}(y_t-h(x))+\frac{1}{2}(x-{\hat{x}}_{t\mid t-1}{)}^{\mathrm{\top }}{P}_{t\mid t-1}^{-1}(x-{\hat{x}}_{t\mid t-1}).$ Applying a Gauss–Newton method to this problem yields the iterated extended Kalman filter (see article on the Extended Kalman filter). Bell and Cathey show that this iterated update is a Gauss–Newton method for the corresponding maximum-likelihood problem. Equivalently, this is the special case of the Bellman filter update with $\log p(y_t|x)$ given by the Gaussian log-likelihood $-\frac{1}{2}(y_t-h(x){)}^{\mathrm{\top }}{H}^{-1}(y_t-h(x))$ (up to an additive constant).

Nonlinear/non-Gaussian state-transition equation

Although the exposition above assumes a linear–Gaussian state transition (so that the prediction step has closed form), Bellman's recursive approach applies also to state-space models with a general transition density $p(x_t|x_{t-1})$. In this more general setting, solving Bellman's equation involves a joint maximisation over $(x_t,x_{t-1})$. In this setting, degenerate state dynamics can be handled by equating some elements of $x_t$ to those of $x_{t-1}$ and optimising only over the free components.

Smoothing

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

$J_t:=P_{t\mid t}{T}^{\mathrm{\top }}{P}_{t+1\mid t}^{-1}.$

Initialise at $t=n$ with ${\hat{x}}_{n\mid n}$ and $P_{n\mid n}$.

Then for $t=n-1,\dots ,1$:

${\hat{x}}_{t\mid n}={\hat{x}}_{t\mid t}+J_t({\hat{x}}_{t+1\mid n}-{\hat{x}}_{t+1\mid t}),$

$P_{t\mid n}=P_{t\mid t}+J_t(P_{t+1\mid n}-P_{t+1\mid t})J_t^{\mathrm{\top }}.$

In the Bellman-filter setting (linear–Gaussian state transition with a general observation density), these RTS recursions still apply to the (possibly approximate) filtered quantities produced by the Bellman filter.

Parameter estimation

In many applications the model depends on unknown static parameters $\psi$ (for example, coefficients in the observation density $p(y_t|x_t)$, or elements of $c,T,R,Q$). These can be estimated by fitting $\psi$ to the observed data, typically by running the Bellman filter for each candidate $\psi$ and then maximising an (approximate) log-likelihood objective with a numerical optimiser, subject to any required constraints (e.g. positive definiteness of covariance matrices). A simple estimator of this type is:

$\hat{\psi }:=\arg \underset{\psi }{\max }\sum _{t=1}^n[\log p(y_t|{\hat{x}}_{t\mid t})-\frac{1}{2}\log \frac{\det (P_{t\mid t-1})}{\det (P_{t\mid t})}-\frac{1}{2}({\hat{x}}_{t\mid t}-{\hat{x}}_{t\mid t-1}{)}^{\mathrm{\top }}{P}_{t\mid t-1}^{-1}({\hat{x}}_{t\mid t}-{\hat{x}}_{t\mid t-1})].$

The first term $\log p(y_t|{\hat{x}}_{t\mid t})$ measures how well the Bellman-filtered (mode) estimate explains the observation $y_t$. The remaining terms form a nonnegative regularisation penalty that discourages overfitting by penalising large adjustments from ${\hat{x}}_{t\mid t-1}$ to ${\hat{x}}_{t\mid t}$, with the determinant ratio reflecting the reduction in (approximate) state uncertainty after incorporating $y_t$.

In the linear–Gaussian observation case this coincides with the maximum likelihood estimator; otherwise it can be interpreted as maximising a second-order approximation to the usual prediction-error decomposition.

Further reading

• Durbin, J.; Koopman, S. J. (2012). Time Series Analysis by State Space Methods (2nd ed.). Oxford University Press. ISBN 978-0-19-964117-8. 
• Harvey, A. C. (1990). Forecasting, Structural Time Series Models and the Kalman Filter. Cambridge University Press. ISBN 978-0-521-40573-7. 
• 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.