ProtocolMain constraint on algorithm design
Success Measuresometimes impossible to practically measure. May serve as a guide for designing algorithms
Type of Analysiswhat we want to prove
Data generation mechanismOnly relevant for the analysis, not for designing an algorithm
Further Restrictive Assumptionsused for designing algorithms or proving restricted results




model that predicts well

is to produce a model that predicts well

to predict well on the unlabeled examples

at a time, prediction to be performed at each step)

reinforcement learning)


General framework


Predictor receives x, takes an action y, and gets reward r.

It is possible to combine r with x.


A prediction function takes a history of pairs ((x,r), y) and a new x to predict y.





Fixed designfixediid
Random designiidiid
Sequence predictionfixedworst-case
Online learningworst-caseworst-case
Online compressionfixediid