Varieties of Regret in Online Prediction

We present a general framework for analyzing regret in the online prediction prob- lem. 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 algo- rithms. 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.