This paper studies the deviations of the regret in a stochastic multi-armed
bandit problem. When the total number of plays n is known beforehand by the
agent, Audibert et al. (2009) exhibit a policy such that with probability at
least 1-1/n, the regret of the policy is of order log(n). They have also shown
that such a property is not shared by the popular ucb1 policy of Auer et al.
(2002). This work first answers an open question: it extends this negative
result to any anytime policy.

This habilitation thesis presents several contributions to (1) the
PAC-Bayesian analysis of statistical learning, (2) the three aggregation
problems: given d functions, how to predict as well as (i) the best of these d
functions (model selection type aggregation), (ii) the best convex combination
of these d functions, (iii) the best linear combination of these d functions,
(3) the multi-armed bandit problems.

We consider the problem of predicting as well as the best linear combination
of d given functions in least squares regression under $L^\infty$ constraints
on the linear combination. When the input distribution is known, there already
exists an algorithm having an expected excess risk of order d/n, where n is the
size of the training data.

We develop minimax optimal risk bounds for the general learning task
consisting in predicting as well as the best function in a reference set
$\mathcal{G}$ up to the smallest possible additive term, called the convergence
rate. When the reference set is finite and when $n$ denotes the size of the
training data, we provide minimax convergence rates of the form
$C(\frac{\log|\mathcal{G}|}{n})^v$ with tight evaluation of the positive
constant $C$ and with exact $0<v\le1$, the latter value depending on the
convexity of the loss function and on the level of noise in the output
distribution.