Sequential Prediction Protocols and Filtrations

Why Timing and Information Matter

A sequential prediction problem is not described only by the actions available to a learner and the losses eventually recorded. It also matters when each quantity becomes known. A prediction based on yesterday’s feedback is different from one that uses today’s outcome, even if both produce the same numerical action in a particular data set. Filtrations provide a precise language for this information boundary.

We use rounds \(t=1,\ldots,T\). On each round the learner first chooses an action, then an outcome or loss is generated, and then the learner receives feedback. The feedback may be the outcome itself, the learner’s loss, or additional information such as the losses of all available actions. These distinctions determine which decisions are admissible and how randomized actions should be analyzed.

Protocol and Filtrations

The information sets \(\mathcal H_t=\sigma(H_t)\) form a filtration: \(\mathcal H_t\subseteq\mathcal H_{t+1}\). A filtration is an increasing sequence of sigma-fields, each representing information available at a specified time. In this convention \(\mathcal H_t\) is the public information before prediction \(t\); the feedback from round \(t\) enters \(\mathcal H_{t+1}\). This indexing makes it explicit that the learner cannot use feedback that has not arrived yet.

The protocol must also say what the environment can use. In an outcome-first or non-anticipating protocol, the outcome or loss information for round \(t\) is fixed before the current action is drawn, though it may depend on the past. In an action-responsive protocol, the environment may choose \(Y_t\) after observing \(A_t\). The latter is common when a learner’s action affects what happens next. Neither convention is implied by the word “online”; it must be specified.

For a history-based strategy, the condition means that there is a measurable rule \(g_t\) such that \(A_t=g_t(H_t)\). If the action space and history space are standard Borel spaces, the Doob–Dynkin lemma gives this representation for any \(\mathcal H_t\)-measurable action. Predictability is a timing condition, not a claim that the action is accurate or optimal.

Worked Examples: What Counts as Past Information?

Randomized Strategies

A randomized strategy does not commit to a single action as a function of the public history. Instead, at each history it specifies a probability distribution over actions. For a finite action set \(A\), write this conditional distribution as \(\pi_t(a\mid H_t)\), where \(\pi_t(a\mid H_t)\geq 0\) and \(\sum_{a\in A}\pi_t(a\mid H_t)=1\). The learner draws \(A_t\) from this distribution after observing \(H_t\).

For example, on a finite action set the learner can use a fresh uniform random variable \(U_t\) on \([0,1]\) to sample from the probabilities in \(\pi_t(\cdot\mid H_t)\), by partitioning \([0,1]\) into intervals of those lengths. The private draw is available when the action is selected, but it is not part of the public history before the draw. Once the action is made, it may become visible to the environment, depending on the protocol.

A randomized action is not generally measurable with respect to the public-history sigma-field alone: the same public history can lead to different actions on different draws. Conditional on the history, however, its distribution is specified. This is the useful sense in which the strategy is non-anticipating: its distribution depends on past information, not on future feedback.

Conditional Expected Loss and Timing

The following calculation makes the role of timing precise. Assume a finite action set, a bounded loss, and a randomized strategy with conditional probabilities \(\pi_t(a\mid H_t)\). In an outcome-first protocol, suppose the round-\(t\) outcome \(Y_t\) is fixed given the past before the action is drawn, and the loss is \(\ell_t(A_t,Y_t)\).

Proof. Conditional on \(\mathcal H_t\) and \(Y_t\), the loss equals \(\ell_t(a,Y_t)\) on the event \(A_t=a\). Since the action has conditional probability \(\pi_t(a\mid H_t)\), the conditional expectation over the finite partition \(\{A_t=a:a\in A\}\) is

The last equality uses the outcome-first condition: once the past is given, \(Y_t\) is fixed before the learner’s fresh action draw, so conditioning on \(Y_t\) does not change the action probabilities. Boundedness ensures the conditional expectations exist. \(\square\)

If the outcome can respond to the action, the appropriate calculation instead conditions on the action-specific outcome distribution. For finite \(A\), with integrable losses, the tower property gives

To derive this identity, partition according to \(A_t=a\), apply conditional expectation on each event, and use \(P(A_t=a\mid\mathcal H_t)=\pi_t(a\mid H_t)\). Unlike the outcome-first formula, the conditional outcome law may vary with \(a\). One cannot generally replace every conditional loss in this expression by a loss against a single outcome fixed before prediction.

Worked Example: Computing a Randomized Prediction

Common Pitfall: Treating “Past” as All Recorded Data

A data file may contain actions, outcomes, and losses for every round, but the completed file is not the information available when the earlier actions were chosen. It is incorrect to call a strategy predictable merely because its action can be written as a function of the full completed data set. Predictability requires measurability with respect to the information available at the decision time.

A second mistake is to assume that randomization makes a strategy anticipative. It does not: a draw from \(\pi_t(\cdot\mid H_t)\) uses a new private random variable, but the distribution itself is determined by the past. Conversely, calling an environment “adversarial” does not specify whether it sees the current action before choosing the outcome. That timing must be included in the protocol.