Bellman filter

The Bellman filter is a recursive algorithm for estimating a sequence of unobserved 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. 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 maximisation objective whose maximiser is a filtered state estimate. In contrast with grid-based maximisation, the Bellman filter keeps the state space continuous and replaces the exact Bellman value functions by parametric 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 or simulation. 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 :Observation equation: State-transition equation:
where.
The filter maintains predicted quantities, and filtered quantities,.

Fisher information

For the observation model, Fisher information is defined as:
where operates on.

Algorithm

Prediction step

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

Updating step

The update step is well defined if is concave in or if is sufficiently large. In some cases, in the formula for can be replaced by the realised negative Hessian.
The maximisation can be interpreted as a maximum a posteriori estimate of : it combines the log-likelihood term with a quadratic log-prior coming from the Gaussian prediction. Equivalently, the update solves a regularised likelihood problem: it chooses the state that best explains while penalising deviation from the predicted mean according to the precision.

Special cases and relationships

Linear–Gaussian observation equation

If
where,
then the level update and covariance update reduce to the usual Kalman filter update.

Iterated (extended) Kalman filtering

For a nonlinear observation equation with additive Gaussian noise,
with,
the Bellman update objective is proportional to the nonlinear least-squares criterion
Applying a Gauss–Newton method to this problem yields the iterated 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 given by the Gaussian log-likelihood .

Nonlinear/non-Gaussian state-transition equation

Although the exposition above assumes a linear–Gaussian state transition, Bellman's recursive approach applies also to state-space models with a general transition density. In this more general setting, solving Bellman's equation involves a joint maximisation over. In this setting, degenerate state dynamics can be handled by equating some elements of to those of and optimising only over the free components.

Smoothing

With a linear–Gaussian state transition, the Rauch–Tung–Striebel smoother can be applied to the filtered output to obtain smoothed estimates and. Define the smoothing gain
Initialise at with and.
Then for :
In the Bellman-filter setting, these RTS recursions still apply to the filtered quantities produced by the Bellman filter.

Parameter estimation

In many applications the model depends on unknown static parameters . These can be estimated by fitting to the observed data, typically by running the Bellman filter for each candidate and then maximising an log-likelihood objective with a numerical optimiser, subject to any required constraints. A simple estimator of this type is:
The first term measures how well the Bellman-filtered estimate explains the observation. The remaining terms form a nonnegative regularisation penalty that discourages overfitting by penalising large adjustments from to, with the determinant ratio reflecting the reduction in state uncertainty after incorporating.
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.