Incomplete information and internal regret in prediction of individual sequences
This thesis takes place within the theory of prediction of individual sequences. The latter avoids any modelling of the data and aims at providing some techniques of robust prediction and discuss their possibilities, limitations, and difficulties. It considers issues arising from the machine learning as well as from the game-theory communities, and these are dealt with thanks to statistical techniques, including martingale concentration inequalities and minimax lower bound techniques. The obtained results consist, among others, in external and internal regret minimizing strategies for label efficient prediction or in games with partial monitoring. Such strategies are valuable for the on-line pricing problem or for on-line bandwidth allocation. We then focus on internal regret for general convex losses. We consider first the case of on-line portfolio selection, for which simulations on real data are provided, and generalize later the results to show how players can learn correlated equilibria in games with compact sets of strategies.