Definitions

Protocol	Main constraint on algorithm design
Success Measure	sometimes impossible to practically measure. May serve as a guide for designing algorithms
Type of Analysis	what we want to prove
Data generation mechanism	Only relevant for the analysis, not for designing an algorithm
Further Restrictive Assumptions	used for designing algorithms or proving restricted results

Examples

Off-line supervised learning: training pairs are given, the goal is to produce a

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)

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.