Tech Report CS-04-09

Varieties of Regret in Online Prediction

Casey Marks, Amy Greenwald, David Gondek

July 2004


We present a general framework for analyzing regret in the online prediction problem. We develop this from sets of linear transformations of strategies. We establish relationships among the varieties of regret and present a class of regret-matching algorithms. Finally we consider algorithms that exhibit the asymptotic no-regret property. Our main results are an analysis of observed regret in expectation and two regret-matching algorithms that exhibit no-observed-internal-regret in expectation.

(complete text in pdf or gzipped postscript)