13 Online prediction and decision problems

Everything so far has assumed the data were generated by an HMM, or at least that a best-approximating HMM exists in the sense of Chapter 8. This chapter drops that assumption in two directions.

The first is adversarial: suppose nothing at all about how the data arise, and ask how well a forecaster using HMMs performs relative to the best HMM chosen with hindsight. The answer is a regret bound, and it holds for every sequence, including sequences constructed to defeat the forecaster.

The second is decision-theoretic: suppose the point is not to infer the state but to act on it. An HMM is then a partially observable Markov decision process without actions, and the filtering distribution acquires a new role as a sufficient statistic for control.

Neither perspective is standard in the HMM literature, and both clarify what the model is doing.

By the end of this chapter you will be able to

express cumulative log-loss as a negative log-likelihood, and define regret against a model class;
prove that a Bayesian mixture over HMMs has logarithmic regret, with no assumption about the data;
say what that guarantee licenses and what it does not;
explain why the belief state is a sufficient statistic, and how filtering becomes the belief update in a POMDP.

13.1 Prediction without a model

13.1.1 The protocol

At each round \(t = 1, 2, \dots\) a forecaster issues a distribution \(q_t\) over the next observation, based only on \(y_{1:t-1}\); then \(y_t\) is revealed and the forecaster suffers the logarithmic loss \(-\log q_t(y_t)\). Cumulative loss after \(T\) rounds is \[ L_T(q) = \sum_{t=1}^{T} -\log q_t(y_t) . \] No probabilistic assumption is made about the sequence \(y_1, y_2, \dots\). It may be generated by an adversary who sees the forecaster’s strategy.

Log-loss is the natural currency here. By the chain rule, \(L_T(q) = -\log q(y_{1:T})\) for the joint distribution implied by the sequence of conditionals, so cumulative log-loss is exactly negative log-likelihood, and a forecaster is nothing other than a probabilistic model of the sequence. The connection to coding is immediate: \(L_T(q)\) is the code length in nats of the sequence under an optimal code for \(q\).

13.1.2 Regret

Definition 13.1 (Regret against a model class) For a class \(\{p_\theta : \theta \in \Theta\}\) of HMMs, the regret of a forecaster \(q\) is \[ R_T(q) = L_T(q) - \inf_{\theta \in \Theta} L_T(p_\theta) = \log \frac{\sup_{\theta} p_\theta(y_{1:T})}{q(y_{1:T})} . \]

The benchmark is the best HMM in the class for this particular sequence, selected with full knowledge of it. Sublinear regret — \(R_T/T \to 0\) — means the forecaster’s average loss matches that unattainable benchmark asymptotically, whatever the sequence.

13.1.3 Bayesian mixtures achieve it

Definition 13.2 (Mixture forecaster) Given a prior \(\Pi\) on \(\Theta\), define \(\ q(y_{1:T}) = \int_\Theta p_\theta(y_{1:T}) \, \Pi(d\theta)\), with conditionals \(q_t(\cdot) = q(\cdot \mid y_{1:t-1})\).

Proposition 13.1 (Regret of the mixture forecaster) For any set \(A \subseteq \Theta\) with \(\Pi(A) > 0\), \[ R_T(q) \;\le\; \log \frac{1}{\Pi(A)} \;+\; \sup_{\theta \in A} \, \log \frac{\sup_{\theta'} p_{\theta'}(y_{1:T})}{p_\theta(y_{1:T})} . \]

Proof. Restricting the integral to \(A\) and bounding the integrand below by its infimum, \[ q(y_{1:T}) \ge \int_A p_\theta(y_{1:T}) \Pi(d\theta) \ge \Pi(A) \inf_{\theta \in A} p_\theta(y_{1:T}) . \] Taking negative logarithms and comparing with \(\sup_{\theta'} p_{\theta'}(y_{1:T})\) gives the bound.

The two terms are a prior penalty and an approximation term. Choosing \(A\) to be a small neighbourhood of the best \(\theta\) makes the second term small; the first then measures how much prior mass that neighbourhood carries. For a \(d\)-dimensional parameter space with a prior having a positive continuous density, a ball of radius \(T^{-1/2}\) has mass of order \(T^{-d/2}\), giving the classical rate \[ R_T(q) \;\lesssim\; \frac{d}{2}\log T + \mathcal{O}(1) . \]

So a Bayesian mixture over HMMs, with any reasonable prior, has regret growing logarithmically in \(T\) against the best HMM chosen in hindsight — for every sequence, with no assumption that the data are generated by an HMM or by anything at all. The \(\frac{d}{2}\log T\) term is the same quantity that appears in BIC, which is not a coincidence: both come from integrating a likelihood against a prior over a \(d\)-dimensional space. Merhav and Feder (1998) survey the universal prediction literature and Cesa-Bianchi and Lugosi (2006) give the general theory of prediction with expert advice.

What this justifies, and what it does not

The result licenses using an HMM as a forecasting device without believing the model. Whatever the world does, you will predict about as well as the best HMM would have.

It does not license interpreting the fitted states. A guarantee about predictive loss says nothing about whether state 2 corresponds to anything real. The interpretive claims of Chapter 14 rest on the model being approximately correct, which is a separate matter entirely.

13.2 HMMs as partially observable decision problems

13.2.1 The setup

Definition 13.3 (Partially observable Markov decision process) A POMDP consists of states \(S_t \in E\), actions \(A_t \in \mathcal{A}\), observations \(Y_t \in \mathcal{Y}\), transition probabilities \(p(s' \mid s, a)\), observation probabilities \(p(y \mid s)\), a reward \(r(s,a)\), and a discount factor \(\lambda \in (0,1]\).

An HMM is a POMDP with a single action and no reward. The extension matters because in most applications the states are inferred in order to do something: inspect a machine, treat a patient, adjust a portfolio.

13.2.2 The belief state

Definition 13.4 (Belief state) The belief at time \(t\) is \(b_t(i) = \mathbb{P}(S_t = i \mid y_{1:t}, a_{1:t-1}) \in \Delta^{K-1}\).

Theorem 13.1 (Beliefs form a Markov decision process) The belief state is a sufficient statistic for the history: the optimal action at time \(t\) depends on \((y_{1:t}, a_{1:t-1})\) only through \(b_t\), and \((b_t)\) is itself a Markov decision process on \(\Delta^{K-1}\) with transition law induced by the filtering update.

This is the result of Åström (1965). Its consequence is a reduction: a control problem with a growing history becomes a control problem on a fixed continuous state space, and dynamic programming applies. The value function satisfies \[ V(b) = \max_{a \in \mathcal{A}} \Bigl\{ r(b,a) + \lambda \, \mathbb{E}\bigl[ V(b') \bigm| b, a \bigr] \Bigr\}, \qquad r(b,a) = \sum_i b(i) \, r(i,a), \] where \(b'\) is the belief after taking \(a\) and observing the next \(y\) — computed by exactly the filtering update of Chapter 5. Filtering is the belief update; there is no separate algorithm.

The remarkable structural fact is that for finite horizons the value function is piecewise linear and convex in \(b\), representable as a maximum of finitely many linear functions. Convexity has a clean reading: uncertainty is costly, so a belief spread over several states is worth less than a mixture of the certain beliefs it averages. This underpins exact solution methods, though the number of linear pieces can grow doubly exponentially in the horizon, and solving POMDPs exactly is intractable in general (Kaelbling et al. 1998).

13.2.3 Where this arises

Condition-based maintenance. Hidden state is equipment health, observations are sensor readings, actions are inspect, repair or do nothing. The decision problem is when the belief about degradation justifies the cost of intervention.
Medical decision making. Hidden state is disease stage, observations are test results, actions are test, treat or wait. Tests carry cost and information value simultaneously, and the belief formulation prices both.
Sequential design. Choosing which measurement to take next to reduce uncertainty about a latent state is a POMDP whose reward is information gain.

In all three, the value of the HMM is that it converts a history into a belief, and the belief is what the decision rule acts on.

13.2.4 Beyond expected reward

Two variants matter when the criterion is not expected total reward.

Risk sensitivity. Maximising the exponential utility \(-\lambda^{-1}\log \mathbb{E}[e^{-\lambda \sum_t r_t}]\) penalises variance as well as mean. Expanding in \(\lambda\) gives \(\mathbb{E}[\sum r_t] - \frac{\lambda}{2}\operatorname{Var}(\sum r_t) + \dots\), so \(\lambda\) is a risk-aversion parameter. The resulting recursions involve a KL-divergence penalty and connect directly to the variational structures of Chapter 1.

Robustness. Instead of trusting a single model, optimise the worst case over a set of models within some divergence of the nominal one. The resulting minimax problems are again KL-regularised, and the dual of the robust problem is a risk-sensitive one — a duality that recurs throughout this literature and gives the two variants a common origin.

13.3 Summary

Under log-loss, a forecaster is a probability model and cumulative loss is negative log-likelihood. Regret compares a forecaster with the best HMM chosen in hindsight.
A Bayesian mixture over HMMs has regret \(\mathcal{O}(\tfrac{d}{2}\log T)\) against that benchmark, for every sequence and with no generative assumption (Proposition 13.1). This justifies HMMs as forecasting devices independently of whether they are true.
Adding actions and rewards turns an HMM into a POMDP. The belief state is a sufficient statistic (Theorem 13.1), the filtering recursion is the belief update, and dynamic programming applies on the simplex.
Value functions are piecewise linear and convex in the belief; exact solution is intractable in general, but the structure supports good approximations.

13.4 Further reading

Cesa-Bianchi and Lugosi (2006) is the standard reference for prediction with expert advice and regret bounds; Merhav and Feder (1998) survey universal prediction and its coding-theoretic side, and Cover and Thomas (2006, ch. 13) gives the information-theoretic background. For POMDPs, Åström (1965) established the sufficiency of the belief state and Kaelbling et al. (1998) is the standard modern account with algorithms. Murphy (2012, ch. 17) connects HMM inference to reinforcement learning.