On-line Prediction Protocol

The simplest version of the on-line prediction protocol is where Nature outputs observations in the IID fashion. After Forecaster predicts an observation, it is added to the training set, which keeps growing. When each observation $z=(x,y)\in\mathbf{Z}=\mathbf{X}\times\mathbf{Y}$ consists of an object $x$ and its label $y$, the protocol looks as follows:

for $n=1,2,\ldots$:
Nature generates $(x_n,y_n)$ from a probability distribution $Q$ on $\mathbf{Z}$
Forecaster is shown $x_n$ and is asked to predict $y_n$
Forecaster is shown the true label $y_n$
end for

A modification is where $z_1,z_2,\ldots$ are coming from an exchangeable probability distribution.

The online prediction protocol is used widely in conformal prediction. There are four important special cases:

(Besides, there are problems of unsupervised learning with the $x_n$s missing.)