Tech Report CS-04-09
Varieties of Regret in Online Prediction
Casey Marks, Amy Greenwald, David Gondek
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.