Dernière version du rapport.

Trop de changements pour êre listés.

3 files changed, 1156 insertions, 270 deletions

diff --git a/biblio.bib b/biblio.bib
index a8ecc26..437e402 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -24,6 +24,23 @@ Learning Theory",
   month="Juillet",
 }
 
+@conference{multi,
+  title="Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback",
+  author="Alekh Agarwal and Ofer Dekel and Lin Xiao",
+  booktitle="Proceedings of The 23rd Annual Conference on
+Learning Theory",
+  year="2010",
+  month="Juillet",
+
+}
+
+@conference{conv,
+  title="Online Convex Optimization in the Bandit Setting: Gradient Descent Without a Gradient",
+  author="Abie Flaxman and Adam Tauman Kalai and Brendan McMahan",
+  booktitle="Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms",
+  year="2005",
+}
+
 @unpublished{exp4,
   title="An Optimal High Probability Algorithm for the Contextual Bandit
 Problem",
@@ -61,15 +78,6 @@ Schapire",
   year="2002"
 }
 
-@conference{multi,
-  title="Optimal Algorithms for Online Convex Optimization with Multi-Point
-Bandit Feedback",
-  author="Alekh Agarwal and Ofer Dekel and Lin Xiao",
-  booktitle="Proceedings of The 23rd Annual Conference on
-Learning Theory",
-  year="2010"
-}
-
 @article{label,
   title="Minimizing regret with label efficient prediction",
   author="Cesa-Bianchi, Nicoló and Lugosi, Gàbor and Gilles Stoltz",
diff --git a/rapport.pdf b/rapport.pdf
index cfdf0b0..fc1d54c 100644
--- a/rapport.pdf
+++ b/rapport.pdf
diff --git a/rapport.tex b/rapport.tex
index e43277e..da63ccc 100644
--- a/rapport.tex
+++ b/rapport.tex
@@ -1,11 +1,21 @@
-\documentclass[titlepage,11pt]{article}
+\documentclass[titlepage,11pt,twoside]{article}
 \usepackage[french]{babel}
 \usepackage[utf8x]{inputenc}
 \usepackage[T1]{fontenc}
 \usepackage{calc,amsmath,amssymb,amsthm}
 \usepackage{mathrsfs}
-\usepackage[hmargin=3.5cm]{geometry}
-\usepackage{}
+\usepackage[hmargin=3.45cm,vmargin=3cm]{geometry}
+\setlength{\headheight}{13.6pt}
+\usepackage{fancyhdr}
+\pagestyle{fancy}
+\fancyhead{}
+\fancyfoot{}
+\fancyhead[LE,RO]{\thepage}
+\fancyhead[RE]{Prédiction de suites individuelles}
+\fancyhead[LO]{\leftmark}
+\renewcommand{\headrulewidth}{0.5pt}
+\renewcommand{\sectionmark}[1]{\markboth{#1}{}}
+
 \newcommand{\trib}[1]{\mathcal{#1}}
 \newcommand{\set}[1]{\mathbf{#1}}
 \newcommand{\esp}[1]{\mathbb{E}\left[#1\right]}
@@ -13,6 +23,7 @@
 \newcommand{\prob}[1]{\mathbb{P}\left[#1\right]}
 \renewcommand{\geq}{\geqslant}
 \renewcommand{\leq}{\leqslant}
+\newcommand{\bs}{\boldsymbol}
 \DeclareMathOperator*{\argmax}{arg\,max}
 \newsavebox{\fmbox}
 \newenvironment{encadre}[1]
@@ -62,13 +73,19 @@
 \newpage
 
 \section{Introduction}
-On s'intéresse ici à la prédiction séquentielle. Dans ce problème, une suite $(y_t)_{t\in\set{N}^*}$ est dévoilée progressivement. À chaque instant discret $t\in\set{N}^*$, on fait une prévision $x_t$, puis cette prévision est confrontée à la valeur réelle $y_t$ qui nous est révélée. 
+On s'intéresse ici à la prédiction séquentielle. Dans ce problème, une suite $(y_t)_{t\in\set{N}^*}$ est dévoilée progressivement. À chaque instant discret $t\in\set{N}^*$, on fait une prévision $x_t$, puis celle-ci est confrontée à la valeur réelle $y_t$ qui nous est révélée. 
 
-La qualité de notre prévision est pénalisée par une fonction de perte $\ell_t$, c'est à dire que l'on reçoit à chaque tour la perte $\ell_t(x_t,y_t)$\footnote{On peut aussi adopter un point de vue plus optimiste et considérer que l'on reçoit à chaque tour le gain $g(x_t,y_t)$ pour une certaine fonction de gain $g$. Mais quitte à considérer des fonctions de perte pouvant prendre des valeurs positives ou négatives, le problème reste le même.}. 
+La qualité de notre prévision est pénalisée par une fonction de perte $\ell$,
+c'est à dire que l'on reçoit à chaque tour la perte\footnote{On peut aussi
+adopter un point de vue plus optimiste
+et considérer que l'on reçoit à chaque tour le gain $g(x_t,y_t)$ pour une
+certaine fonction de gain $g$. Mais quitte à considérer des fonctions de perte
+pouvant prendre des valeurs positives ou négatives, le problème reste le
+même.} $\ell(x_t,y_t)$. 
 
-L'origine de la suite $(y_t)$ peut être très variable : elle peut être générée suivant un processus aléatoire indépendant, tout comme elle peut être choisie par un adversaire qui cherche à nous nuire. Il est donc intéressant d'adopter le modèle d'un jeu entre deux entités : la personne qui fait les prévisions, que l'on appellera simplement \emph{le joueur} ; et l'origine de la suite $(y_t)$, \emph{l'environnement}.
+On ne fait aucune hypothèse sur l'origine de la suite $(y_t)$ : elle peut être générée suivant un processus aléatoire indépendant, tout comme elle peut être choisie par un adversaire qui cherche à nous nuire. Il est donc intéressant d'adopter le modèle d'un jeu entre deux entités : la personne qui fait les prévisions, que l'on appellera simplement \emph{le joueur} ; et l'origine de la suite $(y_t)$, \emph{l'environnement}.
 
-Une fois la valeur de $y_t$ fixée par l'environnement, la seule donnée qui nous intéresse est la fonction partielle $\ell(\cdot,y_t)$. On peut donc considérer indifféremment que l'environnement choisit à chaque tour une valeur $y_t$ ou une fonction de perte $\ell_t$. Le jeu prend donc la forme suivante.
+Une fois la valeur de $y_t$ fixée par l'environnement, la seule donnée qui nous intéresse est la fonction partielle $\ell(\cdot,y_t)$. On peut donc considérer indifféremment que l'environnement choisit à chaque tour une valeur $y_t$ ou une fonction de perte $\ell_t$. Le jeu prend donc la forme suivante :
 
 \begin{encadre}{\textwidth}
 À chaque tour $t$ : 
@@ -79,32 +96,99 @@ Une fois la valeur de $y_t$ fixée par l'environnement, la seule donnée qui nou
 \end{enumerate}
 \end{encadre}
 
-On distingue principalement deux problèmes suivant la nature de l'information $I_t$ révélée : 
+On distingue principalement deux problèmes suivant la nature de l'information
+$I_t$ révélée : 
 \begin{itemize}
 \item Si on observe la fonction de perte $\ell_t$, on parlera de problème à information parfaite : on connaît notre perte, mais aussi la perte que l'on aurait eue en faisant un autre choix.
-\item Si on observe seulement notre perte $\ell_t(x_t)$, on parlera de problème de type \emph{bandit}. Quand le cardinal de $\mathcal{A}$ est fini et égal à $N$, on parle du problème de \emph{bandits à N bras}. L'appellation provient du monde des casinos où le terme \emph{bandit manchot} est synonyme de machine à sous. Un exemple de problème de \emph{bandit à N bras} consiste donc à jouer sur $N$ machines à sou, en choisissant à chaque tour une machine à sous à actionner. Dans ce cas, on observe uniquement la perte de la machine choisie.
+\item Si on observe seulement notre perte $\ell_t(x_t)$, on parlera de problème de type \emph{bandit}. Quand le cardinal de $\mathcal{A}$ est fini et égal à $N$, on parle du problème de \emph{bandits à N bras}. L'appellation provient du monde des casinos où le terme \emph{bandit manchot} est synonyme de machine à sous. Un exemple de problème de \emph{bandit à N bras} consiste donc à jouer sur $N$ machines à sous, en choisissant à chaque tour une machine à sous à actionner. Dans ce cas, on observe uniquement la perte de la machine choisie.
 \end{itemize}
 
-Dans la suite, toutes les fonctions de perte seront bornées par une constante $K$ et le but du joueur est de minimiser sa perte. Cependant, si l'environnement choisit à chaque tour la fonction de perte constante égale à $K$, le joueur n'a plus aucun choix stratégique à faire. Dans ce cas, la quantité significative est le \emph{regret cumulé}, qui mesure l'écart entre la perte du joueur et la perte qu'il aurait eue en choisissant une autre stratégie sur une période de temps $T$. La plupart du temps, on définit le regret par rapport à une stratégie fixe (c'est à dire une suite ($x_t$) constante), dans ce cas, le regret s'écrit :
+L'ensemble $\mathcal{A}$ est appelé l'ensemble de décision. Quand celui-ci est
+de cardinal fini, choisir un élément de $\mathcal{A}$ revient à choisir une
+action parmi une nombre fini de possibilités. La fonction de perte $\ell_t$
+définie sur $\mathcal{A}$ devient alors un \emph{vecteur de perte} que l'on note
+$\bs{\ell}_t$ : on ordonne arbitrairement $\mathcal{A}$ de cardinal $K$, et
+l'environnement choisi pour chaque action la perte correspondante, on a alors
+$\bs{\ell}_t= (\ell_ {1,t},\ldots,\ell_{K,t})$.
+
+Par la suite, toutes les fonctions de perte seront bornées par une constante
+$B$ et le but du joueur est de minimiser sa perte. Cependant, si l'environnement
+choisit à chaque tour la fonction de perte constante égale à $B$, le joueur n'a
+plus aucun choix stratégique à faire. Il apparaît alors que la quantité
+significative est le \emph{regret cumulé}. Celui-ci mesure l'écart entre
+deux quantités
+\begin{enumerate}
+\item la perte accumulée par le joueur jusqu'à l'instant $T$ : c'est
+tout simplement la somme des pertes obtenues à chaque tour pour l'action
+choisie
+\item la perte accumulée d'une stratégie considérée comme « optimale ». Pour un
+ensemble de décision fini ou infini, cette stratégie optimale est simplement le
+choix constant de l'action de plus faible perte cumulée jusqu'à l'instant $T$.
+Dans le cas de la prévision avec experts (section \ref{sec:banditsexp}), on
+étend la notion de perte pour les experts, et la stratégie optimale est l'expert
+de plus faible perte.
+\end{enumerate}
+
+Comme on le voit, la notion de regret varie un peu suivant le problème et
+suivant ce que l'on souhaite mesurer. Elle sera précisée à chaque fois dans les
+différents cadres étudiés, on peut toutefois retenir la forme générale suivante
+pour le regret jusqu'à l'instant $T$, que l'on note $R_T$ :
 \[
-R_T=\sum_{t=1}^T \ell_t(x_t) - \min_{x\in\mathcal{A}}\sum_{t=1}^T\ell_t(x)
+\begin{split}
+R_T &= \text{Perte accumulée par le joueur jusqu'à l'instant T}\\
+&\qquad- \text{Perte accumulée d'une stratégie considérée comme optimale}
+\end{split}
 \]
 
+
 La borne sur les fonctions de perte nous assure que $R_T=O(T)$. On cherche des bornes qui assurent que le regret rapporté au nombre de tour tend vers 0, c'est à dire $R_T=o(T)$. Pour cela, on utilise une stratégie qui dépend de l'ensemble $\mathcal{A}$, de l'information révélée, et du comportement de l'environnement. Ces stratégies seront définies et étudiées dans les sections suivantes.
 
+\subsection*{Remerciements}
+
+Je tiens à remercier vivement Gilles Stoltz pour m'avoir encadré tout au long
+de ce mémoire. Son soutien dynamique, ses remarques pertinentes et sa patience
+dans une période pourtant très chargée pour lui, m'ont été précieux pour mener à
+bien ce travail et je suis persuadé que ses conseils me seront très utiles dans
+la suite de mes études.
+
 \newpage
 
 \section{Prévision dans un univers fini}
 
-Dans cette partie le cardinal de $\mathcal{A}$ est fini égal à $N$. On étudiera d'une part le problème des \emph{bandits à $N$ bras stochastiques}, pour lequel la fonction de perte est choisie suivant une loi fixée à l'avance ; et d'autre part, le problème des \emph{bandits à $N$ bras déterministes}. Pour ce dernier problème, on commence par une étude du cas de l'information totale. 
+Dans cette partie l'ensemble de décision $\mathcal{A}$ est de cardinal fini égal
+à $K$. Ceci permet de modéliser les jeux où le joueur doit choisir à chaque
+tour parmi un nombre fini d'actions. On étudie tout d'abord le problème des
+\emph{bandits stochastiques} pour lequel les gains de chaque action sont choisis
+suivant une loi de probabilité fixée à l'avance et inconnue du joueur. Le
+regret est alors défini par rapport à l'action de plus grande espérance
+de gain, et on cherche à obtenir une borne sur l'espérance du regret.
+
+On étudie ensuite le problème des \emph{bandits déterministes}, pour lequel on
+ne fait pas d'hypothèses sur l'origine de la fonction de perte. On introduit
+alors la notion de \emph{prédiction randomisée} : on choisit à chaque tour
+une loi de probabilité sur l'ensemble des actions et l'action à jouer est tirée
+aléatoirement suivant cette loi. Suivant que l'on est aidé ou non par des
+\emph{experts} (sections \ref{sec:bandits} et \ref{sec:banditsexp}), le regret
+est défini ou bien par rapport à l'action la plus performante ou l'expert le
+plus performant. On obtient dans les deux cas une borne sur le regret
+valable en grande probabilité. L'étude du problème des \emph{bandits
+déterministes} est précédée par l'étude du cas de l'information parfaite. 
 
 \subsection{Bandits stochastiques}
 
 La référence principale pour ce problème est \cite{bandsto} qui contient la stratégie $\textsc{ucb}$ étudiée ci-dessous. Celle-ci assure un regret en $O(\ln T)$.
 
-Considérons pour fixer les idées que l'on joue sur $N$ machines à sous, numérotées $\mathbf\{1,\ldots,N\}$. Conformément au monde des casinos, on raisonnera en terme de gains. Ceux-ci sont régis par une famille de lois de probabilité $(P_1,\ldots,P_N)$, qui nous est bien sûr inconnue.  La fonction de gain $G_t$ est donc une variable aléatoire à valeur dans $\mathbf\{1,\ldots,N\}$, que l'on représente par une famille de variable aléatoire $(G_{1,t},\ldots,G_{N,t})$ : $G_{i,t}$, la i-ème marginale de $G_t$ est le gain de la machine $i$ au tour $t$. C'est une variable aléatoire de loi $P_i$. On suppose que les machines sont indépendantes, c'est à dire que $G_t$ suit la loi $P_1\otimes\ldots\otimes P_N$.
+Considérons pour fixer les idées que l'on joue sur $K$ machines à sous,
+numérotées $\mathbf\{1,\ldots,K\}$. Conformément au monde des casinos, on
+raisonnera en terme de gains. Ceux-ci sont régis par une famille de lois de
+probabilité $(P_1,\ldots,P_K)$, qui nous est bien sûr inconnue.  La fonction de
+gain $G_t$ est donc une variable aléatoire à valeur dans $[0,1]^K$, que l'on
+représente par une famille de variable aléatoire $(G_{1,t},\ldots,G_{K,t})$ :
+$G_{i,t}$, la i-ème composante de $G_t$ est le gain de la machine $i$ au tour
+$t$. C'est une variable aléatoire de loi $P_i$. On suppose que les machines sont
+indépendantes, c'est à dire que $G_t$ suit la loi $P_1\otimes\ldots\otimes P_K$.
 
-On résume si dessous le déroulement du jeu.
+On résume ci-dessous le déroulement du jeu.
 
 \begin{encadre}{\textwidth}
 \begin{center}
@@ -114,13 +198,14 @@ On résume si dessous le déroulement du jeu.
 À chaque tour $t\geq 1$ :
 \begin{enumerate}
 \item Le joueur choisit un bras $I_t$.
-\item Les gains $(G_{1,t},\ldots,G_{N,t})$ sont tirées suivant la loi
-$P_1\otimes\ldots\otimes P_N$.
+\item Les gains $(G_{1,t},\ldots,G_{K,t})$ sont tirées suivant la loi
+$P_1\otimes\ldots\otimes P_K$.
 \item Le joueur reçoit (et observe) le gain $G_{I_t,t}$. 
 \end{enumerate}
 \end{encadre}
 
-La stratégie du joueur est donc une fonction $S$ :
+La stratégie du joueur est donc la donnée d'un bras initial est d'une une
+fonction $S$ :
 \[
 S : \bigsqcup_{t\geq
 1}\big(\mathcal{A}\times[0,1]\big)^t\longrightarrow\mathcal{A}
@@ -128,32 +213,47 @@ S : \bigsqcup_{t\geq
 qui donne le bras à jouer en fonction du passé : $I_{t+1} =
 S\big((I_1,G_{I_1,1}),\ldots,(I_t,G_{I_t,t})\big)$.
 
-La stratégie est donc déterministe, c'est à dire que le joueur choisit le bras
+La stratégie est déterministe, c'est à dire que le joueur choisit le bras
 à jouer à l'instant $t$ de façon déterministe en fonction du passé, sans faire
 appel à une randomisation externe.
 
 Si on note $\trib{F}_t$ la tribu engendrée par $(G_{I_1,1},\ldots,G_{I_t,t})$,
-on voit facilement que $I_t$ est mesurable par rapport à la tribu
+on montre par récurrence que $I_t$ est mesurable par rapport à la tribu
 $\trib{F}_{t-1}$.
 
-On note $\mu_i$ l'espérance de $P_i$, et $\mu^*=\max_{1\leq i\leq N} \mu_i$
-(plus généralement on notera avec un exposant étoile toute grandeur rattachée à
-un bras d'espérance maximale). Enfin on note :
+On note $\mu_i$ l'espérance de $P_i$. On choisit $j^*$ l'indice d'un bras
+d'espérance maximale, et on note $\mu^*=\mu_{j^*}$, on a donc :
+\[\mu^*=\mu_{j^*}=\max_{1\leq i\leq K} \mu_i\]
+Plus généralement on notera avec un exposant étoile toute grandeur rattachée au
+bras $j^*$ d'espérance maximale. Enfin on note :
 \[
 \Delta_i = \mu^*-\mu_i
 \]
 
-On souhaite avoir une borne sur le regret défini par :
+On défini le regret par rapport à la machine la plus performante :
 \[
-R_T = \esp{T\mu^* - \sum_{t=1}^T G_{I_t,t}}
-=T\mu^* - \sum_{i=1}^N \mu_i \esp{N_i(T)}
-=\sum_{i=1}^N \esp{N_i(T)}\Delta_i
+R_T=\sum_{t=1}^T G_{j^*,t}-\sum_{t=1}^T G_{I_t,t}
 \]
-où $N_i(T)$ désigne le nombre de fois que le bras $i$ a été joué jusqu'à
-l'instant $t$ :
+et on souhaite obtenir une borne sur l'espérance du regret :
+\[
+\esp{R_T}=\sum_{t=1}^T \esp{G_{j^*,t}}-\sum_{t=1}^T
+\esp{G_{I_t,t}}=T\mu^*-\sum_{t=1}^T \esp{G_{I_t,t}}
+\]
+on peut réordonner la dernière somme en fonction des valeurs prises par $I_t$ :
+si $I_t=i$, alors $\esp{G_{I_t,t}}=\mu_i$. Notons alors $N_i(T)$ le
+nombre de fois que le bras $i$ a été joué jusqu'à l'instant $t$ :
 \[
 N_i(T)=\sum_{t=1}^T \mathbf{1}_{\{I_t=i\}}
+,\]
+l'espérance du regret devient alors :
+\[
+\esp{R_T}=T\mu^*-\sum_{i=1}^K \mu_i \esp{N_i(T)}
 \]
+puis en utilisant que $\sum_{i=1}^T\esp{N_i(T)}=T$ et on obtient finalement
+l'expression suivante pour l'espérance du regret :
+\begin{equation}\label{eq:regretsto}
+ \esp{R_T}=\sum_{i=1}^K \Delta_i \esp{N_i(T)}
+\end{equation}
 
 On utilise la stratégie de prévision suivante :
 
@@ -162,10 +262,10 @@ On utilise la stratégie de prévision suivante :
 \textbf{Stratégie \textsc{ucb} pour les bandits stochastiques}
 \end{center}
 
-\textbf{Initialisation :} On joue chaque bras une fois au cours des $N$
+\textbf{Initialisation :} On joue chaque bras une fois au cours des $K$
 premiers tours.
 
-À chaque tour $t> N$ :
+À chaque tour $t> K$ :
 \begin{enumerate}
 \item On estime $\mu_i$ à l'aide des données passées :
 \[
@@ -174,7 +274,7 @@ premiers tours.
 \]
 \item On choisit un bras $I_t$ qui vérifie :
 \[
-I_t= \argmax_{1\leq i\leq N}
+I_t\in \argmax_{1\leq i\leq K}
 \left(\widehat{\mu}_{i,t-1}+\sqrt{\frac{2\ln (t-1)}{N_i(t-1)}}\;\right)
 \]
 \item On observe $G_{I_t,t}$. 
@@ -182,12 +282,12 @@ I_t= \argmax_{1\leq i\leq N}
 \end{encadre}
 
 \begin{thm}
-Si les lois $(P_1,\ldots,P_N)$ des machines sont à support dans $[0,1]$, le
-regret au temps T vérifie :
+Si les lois $(P_1,\ldots,P_K)$ des machines sont à support dans $[0,1]$, alors
+pour la stratégie UCB, on a :
 \[
-R_T\leq
+\esp{R_T}\leq
 \left(8\sum_{\mu_i<\mu^*}\frac{1}{\Delta_i}\right) \ln T
-+\left(1+\frac{\pi^2}{3}\right)\left(\sum_{i=1}^N \Delta_i\right)
++\left(1+\frac{\pi^2}{3}\right)\left(\sum_{i=1}^K \Delta_i\right)
 \]
 \end{thm}
 
@@ -196,17 +296,30 @@ R_T\leq
 c_{t,s}=\sqrt{\frac{2\ln t}{s}}
 \]
 
-Vu la forme du regret, on va majorer $\esp{N_i(T)}$. Dans cette preuve, on
-notera $\{A\}$ au lieu de $\mathbf{1}_A$. Pour tout entier $\ell\geq 1$, on a :
+Vu la forme du regret obtenu en \eqref{eq:regretsto}, on va majorer
+$\esp{N_i(T)}$. Dans cette preuve, on
+notera $\{A\}$ au lieu de $\mathbf{1}_A$. Soit $\ell$ un entier avec
+$\ell\geq 1$. Notons $T_0$ l'instant tel que $N_i(T_0)=\ell$, puisqu'on
+commence par jouer chaque bras une fois, on a $T_0\geq K$. En découpant le
+temps par rapport à $T_0$, on obtient :
+
 \[
 \begin{split}
-N_i(T)&\leq \ell + \sum_{t=N+1}^T \left\{I_t=i,\ N_i(t-1)\geq l\right\}\\
-&\leq\ell + \sum_{t=N+1}^T\left\{\widehat{\mu}^*_{t-1}+c_{t-1,N^*(t-1)}
-\leq \widehat{\mu}_{i,t-1}+c_{t-1,N_i(t-1)},\ N_i(t-1)\geq l\right\}\\
-&\leq\ell + \sum_{t=N+1}^{T}\sum_{s=1}^{t-1}\sum_{s'=l}^{t-1}
+N_i(T)&\leq N_i(T_0)
++\sum_{t=T_0+1}^T\left\{I_t=i,\ N_i(t-1)\geq\ell\right\}\\
+&\leq \ell
++\sum_{t=K+1}^T \left\{I_t=i,\ N_i(t-1)\geq \ell\right\}\\
+&\leq\ell
++\sum_{t=K+1}^T\left\{\widehat{\mu}^*_{t-1}+c_{t-1,N^*(t-1)}
+\leq \widehat{\mu}_{i,t-1}+c_{t-1,N_i(t-1)},\ N_i(t-1)\geq \ell\right\}\\
+\end{split}
+\]
+Puis en découpant suivant les valeurs possibles de $N_i(t-1)$ et $N^*(t-1)$, on
+obtient:
+\[N_i(T)\leq\ell
++\sum_{t=K+1}^{T}\sum_{s=1}^{t-1}\sum_{s'=\ell}^{t-1}
 \left\{\bar{X}^*_{s}+c_{t-1,s}
 \leq\bar{X}_{i,s'}+c_{t-1,s'}\right\}
-\end{split}
 \]
 où on a noté :
 \[
@@ -229,7 +342,7 @@ trois événements suivants :
 \end{equation}
 
 L'inégalité de Hoeffding permet de majorer les probabilités des événements
-\eqref{ev1} et \eqref{ev2} par $\exp(-4\ln t)=t^{-4}$. Enfin, si
+\eqref{ev1} et \eqref{ev2} par $\exp\big(-4\ln(t-1)\big)=(t-1)^{-4}$. Enfin, si
 $\ell=\lceil (8\ln T)/\Delta_i^2\rceil$, l'événement \eqref{ev3} est de
 probabilité nulle. En effet, on a alors :
 \[
@@ -237,23 +350,95 @@ probabilité nulle. En effet, on a alors :
 \mu^*-\mu_i
 \]
 
-On a donc :
+En utilisant les différentes majoration précédentes et en utilisant la valeur
+de $\ell$ ci-dessus :
 \[
-\esp{N_i(T)}\leq \left\lceil \frac{8\ln T}{\Delta_i^2}\right\rceil
-+\sum_{t=1}^{\infty}t^2\frac{2}{t^4}
+\begin{split}
+\esp{N_i(T)}
+&\leq \left\lceil \frac{8\ln T}{\Delta_i^2}\right\rceil
++\sum_{t=2}^{\infty}\sum_{s=1}^{t-1}\sum_{s'=1}^{t-1}\frac{2}{(t-1)^4}\\
+&\leq \left\lceil \frac{8\ln T}{\Delta_i^2}\right\rceil
++\sum_{t=2}^{\infty}\frac{2}{(t-1)^2}
+=\leq \left\lceil \frac{8\ln T}{\Delta_i^2}\right\rceil+\frac{\pi^2}{3}
+\end{split}
 \]
 
 On multiplie alors par $\Delta_i$ et on somme sur $1\leq i \leq N$ pour avoir
 le résultat.
 \end{proof}
 
-\subsection{Adversaire déterministe et information totale}
-Maintenant, l'environnement se comporte comme un adversaire : il connaît notre
-stratégie, observe nos actions passées, et peut donc choisir les pertes de façon
-à maximiser notre regret. Face à un tel adversaire, on s'autorise à faire
-appel à une randomisation externe dans notre stratégie. Ceci rétablit une
-certaine forme d'équilibre car l'adversaire n'a pas de contrôle sur l'aléa. La
-prévision prend alors la forme du jeu répété suivant :
+\begin{rem}
+L'inégalité de Bernstein peut sembler plus adaptée pour majorer des
+probabilités d'événements du type $\left\{\widehat{\mu}_{i,t-1}\geq\mu_i
++c_{t-1,N_i(t-1)}\right\}$ et ainsi éviter le découpage suivant les valeurs de
+$N_i(t-1)$ effectué dans la preuve précédente. Par exemple réécrivons :
+\[
+\widehat{\mu}_{i,t-1} -\mu_i
+=\frac{1}{N_i(t-1)}\sum_{k=1}^{t-1}\big(G_{i,k}-\mu_i\big)\mathbf{1}_{I_k=i}
+\]
+d'où :
+\[
+\prob{\widehat{\mu}_{i,t-1} -\mu_i\geq c_{t-1,N_i(t-1)}}
+=\prob{\sum_{k=1}^{t-1}\big(G_{i,k}-\mu_i\big)\mathbf{1}_{I_k=i}
+\geq\sqrt{2\ln(t-1)N_i(t-1)}}
+\]
+
+Si on note $X_k=\big(G_{i,k}-\mu_i\big)\mathbf{1}_{I_k=i}$, $X_k$ est une suite
+d'accroissement de martingale pour la filtration $\trib{F}_t$ et on a avec les
+notations de la section \ref{inegmart} : $V_{t-1}=\sigma_i^2N_i(t-1)$ où
+$\sigma_i^2$ représente la variance du $i$-ième bras. La probabilité à majorer
+s'écrit donc :
+\[
+\prob{\sum_{k=1}^{t-1}X_k\geq\sqrt{2\frac{\ln(t-1)}{\sigma_i^2}V_{t-1}}}
+\]
+On sait que $\ell\sigma_i^2\leq V_{t-1}\leq \sigma_i^2 (t-1)$, donc on peut
+appliquer le lemme \ref{megabernstein} :
+\[
+\prob{\frac{S_{t-1}}{\sqrt{V_{t-1}}}
+\geq \sqrt{3\ln\left(\frac{\ln \big((t-1)/\ell\big)}{\delta/4}\right)}
++\frac{2}{3\sqrt{V_{t-1}}}\ln\left(\frac{\ln
+\big((t-1)/\ell\big)}{\delta/4}\right)}
+\leq \delta
+\]
+d'où :
+\[
+\prob{\frac{S_{t-1}}{\sqrt{V_{t-1}}}
+\geq \sqrt{3\ln\left(\frac{\ln \big((t-1)/\ell\big)}{\delta/4}\right)}
++\frac{2}{3\sqrt{\sigma_i^2 \ell}}\ln\left(\frac{\ln
+\big((t-1)/\ell\big)}{\delta/4}\right)}
+\leq \delta
+\]
+Vu l'ordre de grandeur de $\ell$, le premier terme de la borne ci-dessus est le
+plus grand, d'où :
+\[
+\prob{\frac{S_{t-1}}{\sqrt{V_{t-1}}}
+\geq 3\sqrt{\ln\left(\frac{\ln \big((t-1)/\ell\big)}{\delta/4}\right)}}
+\leq \delta
+\]
+On voit qu'il faut alors prendre $\delta$ de l'ordre de :
+\[
+\frac{\ln \big((t-1)/l\big)}{t-1}=\frac{\ln \big((t-1)/\ln T\big)}{t-1}
+\]
+Cependant en sommant de $1$ à $T$, on obtient une borne supérieure à $\ln T$.
+Il semble que ce qui empêche ici d'appliquer l'inégalité de Bernstein est que
+le contrôle que nous avons sur la variance $V_T$ c'est à dire sur $N_i(T)$
+n'est pas assez précis pour autoriser un traitement général
+\end{rem}
+
+\subsection{Adversaire déterministe et information parfaite}\label{fullinfo}
+
+On ne fait plus maintenant d'hypothèse sur l'origine des pertes. Elles peuvent
+par exemple être choisies de façon déterministe par l'environnement de façon à
+maximiser notre regret. Il peut par exemple, en observant les tours passés,
+deviner et s'adapter à notre stratégie. Face à un tel adversaire, on s'autorise
+à faire appel à une randomisation externe pour choisir l'action à jouer : au
+lieu de choisir directement l'action à jouer, celle-ci est tirée aléatoirement
+suivant une loi que l'on choisit au début du tour. Même en observant la loi
+choisie, le simple fait pour l'adversaire de n'avoir aucun contrôle sur l'issu
+du tirage aléatoire, rétablit une certaine forme d'équilibre et permet
+d'obtenir avec une bonne stratégie une borne satisfaisante sur le regret.
+
+On résume ci-dessus le déroulement du jeu :
 
 \begin{encadre}{\textwidth}
 \begin{center}
@@ -262,59 +447,69 @@ prévision prend alors la forme du jeu répété suivant :
 À chaque tour $t\geq 1$ :
 \begin{enumerate}
 \item Le joueur choisit un loi de probabilité sur $\mathcal{A}$,
-$P_t=(p_{1,t},\ldots,p_{N,t})$
+$\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$
 \item Simultanément, l'adversaire choisit un vecteur de perte,
-$\ell_t=(\ell_{1,t},\ldots,\ell_{N,t})$
-\item Le joueur tire $I_t$ suivant la loi $P_t$ et choisit l'action
+$\bs{\ell}_t=(\ell_{1,t},\ldots,\ell_{K,t})$
+\item Le joueur tire $I_t$ suivant la loi $\bs{p}_t$ et choisit l'action
 $I_t$. Il reçoit la perte $\ell_{I_t,t}$.
-\item Le joueur et l'adversaire observent le vecteur de perte $\ell_t$ et
+\item Le joueur et l'adversaire observent le vecteur de perte $\bs{\ell}_t$ et
 l'action $I_t$.
 \end{enumerate}
 \end{encadre}
 
-On note $\Delta(\mathcal{A})$ l'ensemble des lois de probabilités sur
-$\mathcal{A}$ (qui s'injecte canoniquement dans $\mathcal{A}^N$).
+Le joueur choisit une loi de probabilité sur $\mathcal{A}$, mais observe une réalisation de cette loi, ceci oblige à étendre la notion de stratégie introduite dans la section précédente. On note $\Delta(\mathcal{A})$ l'ensemble des lois de probabilités sur $\mathcal{A}$ (qui s'injecte canoniquement dans $\mathcal{A}^K$).
 
 La stratégie de prévision du joueur est donc la donnée d'une loi initiale
 $P_1$, et d'une fonction $P$ :
 \[
-P : \bigsqcup_{t\geq 1}\left(\mathcal{A}\times\set{R}^N\right)^{t}
+P : \bigsqcup_{t\geq 1}\left(\mathcal{A}\times\set{R}^K\right)^{t}
 \longrightarrow\Delta(\mathcal{A})
 \]
-qui donne la loi $P_t$ en fonction des actions et des pertes passées.
+qui donne la loi $\bs{p}_t$ en fonction des actions et des pertes passées.
 
 La stratégie de l'adversaire est une fonction $E$ :
 \[
-\ell : \bigsqcup_{t\geq 1}\left(\mathcal{A}\times\set{R}^N\right)^{t}
-\longrightarrow\mathcal{A}^N
+E : \bigsqcup_{t\geq 1}\left(\mathcal{A}\times\set{R}^K\right)^{t}
+\longrightarrow\mathcal{A}^K
 \]
-qui donne le vecteur de perte $\ell_t$ en fonction du passé.
+qui donne le vecteur de perte $\bs{\ell}_t$ en fonction du passé.
 
 Si on note $\trib{F}_t$ la tribu engendrée par $(I_1,\ldots,I_t)$,
 l'information disponible au début du tour $t$ est donc la tribu
-$\trib{F}_{t-1}$ et les variables $P_t$ et $\ell_t$ sont
+$\trib{F}_{t-1}$ et les variables $\bs{p}_t$ et $\bs{\ell}_t$ sont
 mesurables par rapport à cette tribu.
 
-Le regret jusqu'au temps $T$ de la stratégie $P$ contre la stratégie $\ell$ est
-défini par :
+Le regret jusqu'au temps $T$ de la stratégie $P$ contre la stratégie $E$ est
+défini par rapport à la meilleure action, c'est à dire celle de plus faible
+perte cumulée.
+
+On note $L_{i,T}$ la perte cumulée de l'action $i$ jusqu'à l'instant T :
+\[
+L_{i,T}=\sum_{t=1}^T\ell_{i,t}
+\]
+le regret est donc défini par : 
 \[
-R_T(P,\ell)
-=\sum_{t=1}^T \ell_{I_t,t}-\min_{1\leq i\leq N}L_{i,T}
-=\sum_{t=1}^T \ell_{I_t,t}-\min_{1\leq i\leq N}\sum_{t=1}^T \ell_{i,t}
+R_T
+=\sum_{t=1}^T \ell_{I_t,t}-\min_{1\leq i\leq K}L_{i,T}
+=\sum_{t=1}^T \ell_{I_t,t}-\min_{1\leq i\leq K}\sum_{t=1}^T \ell_{i,t}
 \]
-et le regret espéré :
+le \emph{regret espéré} s'éloigne légèrement de la notion habituelle de regret
+car il ne fait pas intervenir directement la perte du joueur, mais l'espérance
+de
+cette perte : 
 \[
-\bar{R}_T(P,\ell) = \esp{R_T} =
-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\ell_{i,t}
--\min_{1\leq i\leq N}L_{i,T}
+\bar{R}_T = 
+\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\ell_{i,t}
+-\min_{1\leq i\leq K}L_{i,T}
 \]
 
 Par la suite, on raisonnera plutôt en termes de gains : on pose
-$g_{i,t}=1-\ell_{i,t}$, on a donc :
+$g_{i,t}=1-\ell_{i,t}$, on a donc, en notant $G_{i,T}$ le gain cumulé jusqu'à
+l'instant $T$ :
 \[
-\bar{R}_T(P,\ell) = 
-\max_{1\leq i\leq N}\sum_{t=1}^T g_{i,t}
--\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}
+\bar{R}_T = 
+\max_{1\leq i\leq K}\sum_{t=1}^T g_{i,t}
+-\sum_{t=1}^T\sum_{i=1}^K p_{i,t}g_{i,t}
 \]
 
 \begin{encadre}{\textwidth}
@@ -322,32 +517,43 @@ $g_{i,t}=1-\ell_{i,t}$, on a donc :
 \textbf{Stratégie par poids exponentiels}
 \end{center}
 
-\textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/N$ pour
-$i\in\{1,\ldots,N\}$.
+\textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/K$ pour
+$i\in\{1,\ldots,K\}$.
 
 À chaque tour $t\geq 1$ :
 
 \begin{enumerate}
-\item On tire $I_t\in\{1,\ldots,N\}$ suivant la loi
-$P_t=(p_{1,t},\ldots,p_{N,t})$.
-\item On observe les gains $g_t=(g_{1,t},\ldots,g_{N,t})$.
+\item On tire $I_t\in\{1,\ldots,K\}$ suivant la loi
+$\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$.
+\item On observe les gains $\bs{g}_t=(g_{1,t},\ldots,g_{K,t})$.
 \item On met à jour les poids exponentiels :
 $w_{i,t}=w_{i,t-1}\exp(\eta g_{i,t})$.
 \item On calcule la distribution pour le tour suivant :
 \[
 p_{i,t+1}=w_{i,t}/W_t
-\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{N}w_{i,t}\bigg)
+\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{K}w_{i,t}\bigg)
 .\]
 \end{enumerate}
 \end{encadre}
 
-\begin{thm}\label{infototale}
-On suppose que les gains sont à valeurs dans $]-\infty, K]$, alors, pour
+Le théorème suivant donne une borne sur le regret espéré de la
+stratégie exponentielle. Ce théorème est important pour l'étude du problèmes
+des bandits déterministes (section \ref{sec:bandits}), dans lequel le regret
+espéré apparaît naturellement. Au lieu de l'étude habituelle du cas de
+l'information parfaite utilisant l'inégalité de Hoeffding, on utilise ici une
+majoration de l'exponentielle par un polynôme d'ordre 2 (lemme \ref{espexp}). On
+fait ainsi apparaître un terme de type variance qui sera crucial dans la preuve
+du théorème \ref{thm:exp3}.
+
+\begin{thm}\label{thm:exp}
+On suppose que les gains sont à valeurs dans $]-\infty, B]$, alors, pour
 tout $\eta$ tel
-que $\eta K\leq 1$ :
+que $\eta B\leq 1$ :
 \[
-\bar{R}_T \leq\frac{\ln N}{\eta}
-+\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2
+\bar{R}_T =\max_{1\leq i\leq K}\sum_{t=1}^T g_{i,t}
+-\sum_{t=1}^T\sum_{i=1}^K p_{i,t}g_{i,t}
+\leq\frac{\ln K}{\eta}
++\eta\sum_{t=1}^T\sum_{i=1}^K p_{i,t}g_{i,t}^2
 \]
 \end{thm}
 
@@ -355,60 +561,98 @@ que $\eta K\leq 1$ :
 On minore puis on majore le log-rapport :
 \[
 \ln\left(\frac{W_T}{W_{0}}\right)
-=\ln\left(\sum_{i=1}^N\exp(\eta G_{i,T})\right)-\ln N \\
-\geq \eta \max_{1\leq i\leq N}G_{i,T}-\ln N
+=\ln\left(\sum_{i=1}^K\exp(\eta G_{i,T})\right)-\ln K \\
+\geq \eta \max_{1\leq i\leq K}G_{i,T}-\ln K
 \]
 
 Pour la majoration, on remarque que :
 \[
 \ln\left(\frac{W_t}{W_{t-1}}\right)
-=\ln\left(\sum_{i=1}^N
+=\ln\left(\sum_{i=1}^K
 \frac{w_{i,t-1}}{W_{t-1}}\exp(g_{i,t})\right)
-=\ln\esp{\exp(\eta X)}
+=\ln\mathbb{E}_t\big[\exp(\eta X)\big]
 \]
 où $X$ est une variable aléatoire qui vaut $g_{i,t}$ avec
 probabilité $p_{i,t}$. On peut donc appliquer le lemme
 \ref{espexp}, on obtient :
 \[
 \ln\left(\frac{W_t}{W_{t-1}}\right)
-\leq\eta\sum_{i=1}^N p_{i,t}g_{i,t}
-+\eta^2\sum_{i=1}^N p_{i,t}g_{i,t}^2
+\leq\eta\sum_{i=1}^K p_{i,t}g_{i,t}
++\eta^2\sum_{i=1}^K p_{i,t}g_{i,t}^2
 \]
 
-On somme pour $t\in\{1,\ldots,N\}$ et on combine avec la minoration :
+On somme pour $t\in\{1,\ldots,K\}$ et on combine avec la minoration :
 \[
-\eta \max_{1\leq i\leq N}G_{i,T}-\ln N 
-\leq \eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}
-+\eta^2 \sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2
+\eta \max_{1\leq i\leq K}G_{i,T}-\ln K 
+\leq \eta\sum_{t=1}^T\sum_{i=1}^K p_{i,t}g_{i,t}
++\eta^2 \sum_{t=1}^T\sum_{i=1}^K p_{i,t}g_{i,t}^2
 .\]
 
 Enfin on réordonne et on divise par $\eta$.
 \end{proof}
 
-\subsection{Bandits à $N$ bras}
+\begin{rem}
+On peut majorer le terme d'ordre 2 par $\eta B^2 T$. Le choix optimal pour $\eta$, $\eta=\sqrt{\ln K}/B\sqrt{T}$, conduit à la borne suivante pour le regret :
+\[
+\esp{R_T}\leq 2B\sqrt{T\ln K}
+\]
+
+On retrouve donc à un facteur multiplicatif près, la borne optimale dans le cas de l'information parfaite (cf. par exemple \cite{plg}).
+\end{rem}
+
+\subsection{Bandits déterministes}\label{sec:bandits}
 
 Contrairement au paragraphe précédent, on observe à la fin de chaque tour
-uniquement le gain correspondant à l'action choisie. On ne peut donc pas
-utiliser directement la stratégie par poids exponentiels, car on ne peut plus
-évaluer la perte cumulée de chaque action. L'idée est donc d'estimer les pertes
-qui ne nous sont pas révélées. On utilise pour cela un estimateur biaisé (grâce
-au paramètre $\beta$) : 
+uniquement le gain correspondant à l'action choisie. La stratégie par poids exponentiels
+ne s'applique pas directement car les gains cumulés de chaque action ne sont
+plus disponibles.
+
+L'idée naturelle pour contourner cette difficulté consiste à estimer à chaque
+tour les gains qui nous sont inconnus et d'appliquer la stratégie du problème
+à information parfaite en utilisant les gains estimés.
+
+On obtient alors une borne sur le regret en appliquant, pour les gains
+estimés, un résultat d'information parfaite, puis en contrôlant l'écart
+entre les gains estimés et les gains réels par concentration. Cette méthode est
+générale et sera également utilisée dans la section \ref{conv}.
+
+L'estimateur naturel du gain pour l'action $i$ au tour $t$ serait, avec les
+mêmes notations que dans la section \ref{fullinfo} :
+\[
+\widetilde{h}_{i,t}=\frac{g_{i,t}\mathbf{1}_{\{I_t=i\}}}{p_{i,t}}
+\]
+Cet estimateur est conditionnellement sans biais, c'est à dire
+que :
+\[
+\espc{\widetilde{h}_{i,t}-g_{i,t}}{\trib{F}_{t-1}}=0.
+\]
+Toutefois, il n'est pas possible pour cet estimateur de contrôler de façon
+satisfaisante l'écart entre les gains estimés et les gains réels. On lui
+préfère donc l'estimateur biaisé suivant :
+\[
+\widetilde{g}_{i,t}=\frac{g_{i,t}\mathbf{1}_{\{I_t=i\}}}{p_{i,t}}+\frac{\beta}{
+p_{i,t}}
+\]
+ceci conduit à l'algorithme Exp3.P (pour algorithme par poids Exponentiels pour
+l'Exploration et l'Exploitation en grande Probabilité). Cet
+algorithme a été présenté pour la première fois dans \cite{bandet} et donne une
+borne pour le regret en $O\big(\sqrt{KT\ln(K/\delta)}\big)$.
 
 \begin{encadre}{\textwidth}
 \begin{center}
 \textbf{Algorithme Exp3.P}
 \end{center}
 
-\textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/N$ pour
-$i\in\{1,\ldots,N\}$.
+\textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/K$ pour
+$i\in\{1,\ldots,K\}$.
 
 À chaque tour $t\geq 1$ :
 
 \begin{enumerate}
-\item On tire $I_t\in\{1,\ldots,N\}$ suivant la loi
-$P_t=(p_{1,t},\ldots,p_{N,t})$.
+\item On tire $I_t\in\{1,\ldots,K\}$ suivant la loi
+$\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$.
 \item On estime les gains
-$\widetilde{g}=(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{N,t})$ à
+$\widetilde{\bs{g}}_t=(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{K,t})$ à
 partir du gain observé $g_{I_t,t}$
 \[
 \widetilde{g}_{i,t}=\frac{1}{p_{i,t}}\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}
@@ -418,109 +662,114 @@ partir du gain observé $g_{I_t,t}$
 \item On met à jour les poids exponentiels :
 $w_{i,t}=w_{i,t-1}\exp(\eta\widetilde{g}_{i,t})$.
 \item On calcule la distribution pour le tour suivant :
-\[p_{i,t+1}=(1-\gamma)\frac{w_{i,t}}{W_t}+\frac{\gamma}{N}
-\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{N}w_{i,t}\bigg)\]
+\[p_{i,t+1}=(1-\gamma)\frac{w_{i,t}}{W_t}+\frac{\gamma}{K}
+\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{K}w_{i,t}\bigg)\]
 \end{enumerate}
 \end{encadre}
 
-\begin{thm}
-Avec  :
+\begin{rem}
+On voit apparaître un compromis entre exploitation (utilisation des poids
+exponentiels) et exploration (utilisation des poids uniformes en $1/K$). Le
+paramètre $\gamma$ que l'on doit régler en fonctions des contraintes de jeu
+assure ce compromis.
+\end{rem}
+
+\begin{thm}\label{thm:exp3}
+Soit $\delta\in]0,1[$. On suppose que les gains sont à valeurs dans $[0,1]$ ($\bs{g}_t\in [0,1]^K$). Si les paramètres de la stratégie Ex3.P vérifient :
 \[\beta\leq 1,\quad
 \gamma\leq \frac{1}{2},\quad
-\eta\leq \frac{\gamma}{2N}
+\eta\leq \frac{\gamma}{2K}
+,\]
+alors on a avec probabilité supérieure à $1-\delta$ :
+\[
+R_T=\sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i \leq K}\sum_{t=1}^T\ell_{i,t}
+\leq \frac{\ln K}{\eta}
++\frac{1}{\beta}\ln\left(\frac{K}{\delta}\right)
++TK\beta+\big(\gamma+\eta(1+\beta)K\big)T
 \]
-\end{thm}
-
-\newpage
 
-\subsection{Preuve}
-On a une information totale sur les gains estimés, donc en notant
-$q_{i,t}=w_{i,t-1}/W_{t-1}$ et en appliquant le résultat du théorème
-\ref{infototale} : 
+En particulier, en prenant:
 \[
-\bar{R}_T(Q,\widetilde{g})
-=\max_{1\leq i\leq N}\sum_{t=1}^T \widetilde{g}_{i,t}
--\sum_{t=1}^T\sum_{i=1}^N q_{i,t}g_{i,t}
-\leq\frac{\ln N}{\eta}
-+\eta\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}^2
+\eta=\frac{1}{2}\sqrt{\frac{\ln K}{KT}},\quad
+\gamma=\sqrt{\frac{K\ln K}{T}},\quad
+\beta=\sqrt{\frac{\ln K}{KT}},
 \]
-
-puis en multipliant par $1-\gamma$ et en remarquant que 
-$p_{i,t}\geq q_{i,t}(1-\gamma)$ :
+si $T\geq 4K\ln K$, on obtient avec probabilité supérieure à $1-\delta$ :
 \[
-(1-\gamma)\max_{1\leq i\leq N}\sum_{t=1}^T \widetilde{g}_{i,t}
--\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
-\leq\frac{\ln N}{\eta}
-+\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
+R_T=\sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i \leq K}\sum_{t=1}^T\ell_{i,t}
+\leq \frac{9}{2}\sqrt{KT\ln K}+\sqrt{\frac{KT}{\ln K}}\ln\left(\frac{K}{\delta}\right)
++\frac{\ln K}{2}
 \]
-d'où en réordonnant et en utilisant la définition du regret :
-\begin{equation}\label{base}
-\bar{R}_T(P,\widetilde{g})
-=\max_{1\leq i\leq N}\sum_{t=1}^T \widetilde{g}_{i,t}
--\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
-\leq\frac{\ln N}{\eta}
-+\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
-+\gamma\max_{1\leq i\leq N}\widetilde{G}_{i,T}
+\end{thm}
+
+\begin{proof}
+On a une information parfaite sur les gains estimés, donc en notant
+$q_{i,t}=w_{i,t-1}/W_{t-1}$ et en appliquant le résultat du théorème
+\ref{thm:exp} : 
+\begin{equation}\label{eq:exp3-fullinfo}
+\max_{1\leq i\leq K}\sum_{t=1}^T \widetilde{g}_{i,t}
+-\sum_{t=1}^T\sum_{i=1}^K q_{i,t}\widetilde{g}_{i,t}
+\leq\frac{\ln K}{\eta}
++\eta\sum_{t=1}^T\sum_{i=1}^K q_{i,t}\widetilde{g}_{i,t}^2
+\end{equation}
+on relie $q_{i,t}$ à $p_{i,t}$ en multipliant par $1-\gamma$ et en
+remarquant que $p_{i,t}\geq q_{i,t}(1-\gamma)$ :
+\begin{equation}\label{eq:exp3-base}
+(1-\gamma)\max_{1\leq i\leq K}\sum_{t=1}^T \widetilde{g}_{i,t}
+-\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\widetilde{g}_{i,t}
+\leq\frac{\ln K}{\eta}
++\eta\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\widetilde{g}_{i,t}^2
 \end{equation}
 
 Vu le choix de l'estimateur de gain, on a :
-\begin{equation}\label{estimation}
-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
-=\sum_{t=1}^T\sum_{i=1}^N
+\begin{equation}\label{eq:exp3-maj1}
+\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\widetilde{g}_{i,t}
+=\sum_{t=1}^T\sum_{i=1}^K
 \left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}+\beta\right)=\sum_{t=1}^T g_{I_t,t}
-+TN\beta
++TK\beta
 \end{equation}
 et :
-\begin{equation}\label{estimation2}
-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
-\leq\sum_{i=1}^N\sum_{t=1}^T\widetilde{g}_{i,t}\left(g_{I_t,t}\mathbf{1}_{\{
+\begin{equation}\label{eq:exp3-maj2}
+\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\widetilde{g}_{i,t}^2
+\leq\sum_{i=1}^K\sum_{t=1}^T\widetilde{g}_{i,t}\left(g_{I_t,t}\mathbf{1}_{\{
 I_t=i\}}+\beta\right)
-\leq(1+\beta)\sum_{i=1}^N\widetilde{G}_{i,t}
-\leq(1+\beta)N\max_{1\leq i\leq N}\widetilde{G}_{i,t}
+\leq(1+\beta)\sum_{i=1}^K\widetilde{G}_{i,t}
+\leq(1+\beta)K\max_{1\leq i\leq K}\widetilde{G}_{i,t}
 \end{equation}
 
-En utilisant \eqref{estimation}, on a :
+On injecte \eqref{eq:exp3-maj1} et \eqref{eq:exp3-maj2} dans \eqref{eq:exp3-base} :
 \[
-\bar{R}_T(P,\widetilde{g})
-=\max_{1\leq i\leq N}\widetilde{G}_{i,T}
--\sum_{t=1}^T g_{I_t,t} - TN\beta
-=R_T(P,g)
-+\max_{1\leq i\leq N}\widetilde{G}_{i,T}
--\max_{1\leq i\leq N}G_{i,T}
--TN\beta
-\]
-On injecte dans\eqref{base} et on utilise la majoration \eqref{estimation2} :
-\[
-R_T(P,g)
-+\max_{1\leq i\leq N}\widetilde{G}_{i,T}
--\max_{1\leq i\leq N}G_{i,T}
-\leq \frac{\ln N}{\eta}
-+\big(\gamma+\eta(1+\beta) N\big)\max_{1\leq i\leq N}\widetilde{G}_{i,t}
-+TN\beta
+(1-\gamma)\max_{1\leq i\leq K}\sum_{t=1}^T \widetilde{g}_{i,t}
+-\sum_{t=1}^T g_{I_t,t}
+\leq\frac{\ln K}{\eta}+TK\beta
++\eta(1+\beta)K\max_{1\leq i\leq K}\widetilde{G}_{i,t}
 \]
 \[
 \begin{split}
-R_T(P,g)
-&\leq \frac{\ln N}{\eta}
-+\big(1-\gamma-\eta(1+\beta) N\big)\left(\max_{1\leq i\leq N}G_{i,T}
--\max_{1\leq i\leq N}\widetilde{G}_{i,t}\right)\\
-&\qquad+\big(\gamma+\eta(1+\beta) N\big)\max_{1\leq i\leq N}G_{i,T}+TN\beta
+\max_{1\leq i\leq K}G_{i,t}
+-\sum_{t=1}^T g_{I_t,t}
+&\leq\frac{\ln K}{\eta}+TK\beta
++\max_{1\leq i\leq K}G_{i,t}
+-\big(1-\gamma-\eta(1+\beta)K\big)\max_{1\leq i\leq K}\widetilde{G}_{i,t}\\
+&\leq \frac{\ln K}{\eta}+TK\beta
++\big(1-\gamma-\eta(1+\beta) K\big)\left(\max_{1\leq i\leq K}G_{i,T}
+-\max_{1\leq i\leq K}\widetilde{G}_{i,t}\right)\\
+&\qquad+\big(\gamma+\eta(1+\beta) K\big)\max_{1\leq i\leq K}G_{i,T}
 \end{split}
 \]
-
-puis vu que $1-\gamma-\eta(1+\beta) N\leq 1$ et $\max_{1\leq i\leq N}
-G_{i,T}\leq T$
-
-\begin{equation}\label{etape2}
-R_T(P,g)
-\leq \frac{\ln N}{\eta}
-+\left(\max_{1\leq i\leq N}G_{i,T}
--\max_{1\leq i\leq N}\widetilde{G}_{i,t}\right)
-+\big(\gamma+\eta(1+\beta)N\big)T+TN\beta
+puis vu que $1-\gamma-\eta(1+\beta) K\leq 1$, et que $\max_{1\leq i\leq K}  
+G_{i,T}\leq T$ :
+\begin{equation}\label{eq:exp3-key}
+\max_{1\leq i\leq K}G_{i,t}
+-\sum_{t=1}^T g_{I_t,t}
+\leq \frac{\ln K}{\eta}+TK\beta
++\left(\max_{1\leq i\leq K}G_{i,T}
+-\max_{1\leq i\leq K}\widetilde{G}_{i,t}\right)
++\big(\gamma+\eta(1+\beta)K\big)T
 \end{equation}
 
-Il nous reste à majorer l'écart entre les gains et les gains estimés. On
-souhaite appliquer le corollaire \ref{megabernstein} pour la suite
+Il nous reste à majorer l'écart entre les gains et les gains estimés. Pour cela, on
+souhaite appliquer le corollaire \ref{semibernstein} pour la suite
 d'accroissement de martingale $(X_{i,t})_{1\leq t\leq T}$ définie par :
 \[
 X_{i,t}=g_{i,t}-\widetilde{g}_{i,t}+\frac{\beta}{p_{i,t}}
@@ -534,48 +783,324 @@ retranché le terme de biais. La variance conditionnelle vaut :
 &=g_{i,t}^2\,\mathbb{E}_t\Bigg[\bigg(1-\frac{\mathbf{1}_{\{I_t=i\}}}{p_{i,t}}
 \bigg)^2\Bigg]\\
 &=g_{i,t}^2\left(\frac{1}{p_{i,t}}-1\right)
+\leq \frac{1}{p_{i,t}}
 \end{split}
 \]
-On applique le corollaire \ref{megabernstein} avec $K=1$ et
-$\sigma_T^2=NT/\gamma$. On a donc avec probabilité supérieure à $1-\delta/N$ :
+On applique le corollaire \ref{semibernstein}. On a donc avec probabilité supérieure à $1-\delta/K$, pour tout $\theta\leq 1$ :
 \[
 G_{i,T}-\widetilde{G}_{i,T} + \beta\sum_{t=1}^T\frac{1}{p_{i,t}}
-\leq \sqrt{3\sum_{t=1}^T\frac{1}{p_{i,t}}\ln\left(\frac{N\ln
-(NT/\gamma)}{\delta/4}\right)}
-+\frac{2}{3}\ln\left(\frac{N\ln(NT/\gamma)}{\delta/4}\right)
+\leq \theta\sum_{t=1}^T\frac{1}{p_{i,t}}
++\frac{1}{\theta}\ln\left(\frac{K}{\delta}\right)
 \]
-puis en majorant l'intersection des évènements précédents, on a avec
-probabilité supérieure à $1-\delta/N$ :
+On choisit alors $\theta=\beta$, ce qui permet d'annuler le terme de variance. Puis en majorant l'intersection des évènements précédents, on a avec probabilité supérieure à $1-\delta$ :
 \[
-a
+\max_{1\leq i\leq K}G_{i,T}-\max_{1\leq i\leq K}\widetilde{G}_{i,t}
+\leq\frac{1}{\beta}\ln\left(\frac{K}{\delta}\right)
 \]
-
-en injectant cette dernière majoration dans \eqref{etape2}, on obtient
+en injectant cette dernière majoration dans \eqref{eq:exp3-key}, on obtient
 finalement :
 \[
-R_T(P,g)
-\leq \frac{\ln N}{\eta}
-+\beta T(N-1)+\big(\gamma+\eta(1+\beta)\big)T
-+\sqrt{2\frac{NT}{\gamma}\ln\left(\frac{1}{\delta}\right)}
-+\frac{2}{3}\ln\left(\frac{1}{\delta}\right)
+\max_{1\leq i\leq K}G_{i,t}
+-\sum_{t=1}^T g_{I_t,t}
+\leq \frac{\ln K}{\eta}+TK\beta
++\frac{1}{\beta}\ln\left(\frac{K}{\delta}\right)
++\big(\gamma+\eta(1+\beta)K\big)T
+\]
+
+La deuxième inégalité du théorème s'obtient par simple injection des valeurs précisées pour les différents paramètres.
+\end{proof}
+
+\begin{rem}
+La preuve diffère de celle donnée dans \cite{plg} :
+\begin{itemize}
+\item Tout d'abord, l'accent est mis sur le lien avec le cas de l'information
+totale, en appliquant directement le théorème \ref{thm:exp}. À ce sujet, on
+peut se demander l'intérêt d'utiliser une borne d'ordre 2 pour le regret,
+plutôt que la borne habituelle pour l'information parfaite :
+\[
+R_T\leq \frac{\ln K}{\eta} +\eta\frac{TB^2}{8}
+\]
+où $B$ est un majorant des gains. La raison en est que pour les gains estimés,
+le meilleur majorant dont on dispose est $(1+\beta)K/\gamma$. Cette majoration
+est très grossière car, sauf dans le cas où $i=I_t$, $\widetilde{g}_{i,t}$ est
+majoré par $\beta K/\gamma$. La borne du théorème \ref{thm:exp} permet un
+traitement plus adapté à la nature de l'estimateur choisi.
+\item Le contrôle de l'écart entre les gains estimés et les gains réels est
+obtenu grâce à l'inégalité de Bernstein (corollaire \ref{semibernstein}), ce
+qui permet d'éviter l'emploi d'un lemme ad hoc. Cette étape de la preuve fait
+d'ailleurs apparaître le rôle crucial joué par le paramètre $\beta$ de biais :
+il permet de compenser le terme de variance introduit par l'inégalité de
+Bernstein. Le terme $TK\beta$ qui apparaît dans la borne du théorème montre
+toutefois que ce paramètre introduit un compromis supplémentaire et ne doit pas
+être choisi trop grand.
+\end{itemize}
+\end{rem}
+
+\subsection{Bandits déterministes avec experts}\label{sec:banditsexp}
+
+Dans le problème de prédiction avec experts, on joue au même jeu que
+précédemment : on doit choisir une action parmi un ensemble fini $\mathcal{A}$
+de cardinal $K$. Cependant, au début de chaque tour, un ensemble d'experts nous
+conseille sur l'action à prendre : chaque expert $i$ fournit un vecteur de
+conseil $\bs{\xi}^i_t\in\Delta(\mathcal{A})$. Après l'observation de ces
+vecteurs, on choisit la loi de probabilité de l'action à joueur. Le jeu prend
+donc la forme suivante.
+
+\begin{encadre}{\textwidth}
+\begin{center}
+\textbf{Jeu de prévision avec expert}
+\end{center}
+À chaque tour $t\geq 1$ :
+\begin{enumerate}
+\item Le joueur observe les vecteurs des experts : $\bs{\xi}^1_t,\ldots,\bs{\xi}^N_t$
+\item Le joueur choisit une loi de probabilité sur $\mathcal{A}$ : $\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$
+\item Simultanément, l'adversaire choisit un vecteur de perte,
+$\bs{\ell}_t=(\ell_{1,t},\ldots,\ell_{K,t})$
+\item Le joueur tire $I_t$ suivant la loi $\bs{p}_t$ et choisit l'action
+$I_t$. Il reçoit la perte $\ell_{I_t,t}$.
+\item Le joueur et les experts observent la perte $\ell_{I_t,t}$.
+\end{enumerate}
+\end{encadre}
+
+La prédiction avec experts généralise donc le problème des bandits
+déterministes étudié précédemment (on peut considérer chaque action
+comme un expert constant) et apparaît comme un problème de « méta-prédiction » :
+on dispose d'un certain nombre de stratégies de prédiction dont on ne connaît
+pas a priori la qualité. Au bout d'un certain nombre de tours, on souhaiterait
+avoir un gain proche de la meilleure stratégie. Le regret n'est donc pas défini
+ici par rapport à la meilleure action, mais par rapport au meilleur expert. On
+définit la perte cumulée de l'expert $i$ jusqu'à l'instant $T$ par :
+\[
+L_{i,T}=\sum_{t=1}^T \bs{\xi}^i_t\cdot\bs{\ell}_t
+\]
+
+La quantité que l'on souhaite majorer est donc le regret :
+\[
+R_T = \sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i\leq N}\sum_{t=1}^T \bs{\xi}^i_t\cdot\bs{\ell}_t
+\]
+
+Comme précédemment, on suppose que les pertes appartiennent à l'intervalle $[0,1]$, on pose $g_{i,t}=1-\ell_{i,t}$. Le regret s'écrit également :
+\[
+R_T = \max_{1\leq i\leq N}\sum_{t=1}^T\bs{\xi}^i_t\cdot\bs{g}_t - \sum_{t=1}^T g_{I_t,t}
+\]
+
+On pourrait appliquer directement l'algorithme Exp3.P en considérant chaque
+expert $i$ comme une action de gain associé $\bs{\xi}^i_t\cdot\bs{g}_t$. On
+obtient alors avec le théorème \ref{thm:exp3} une borne pour le regret en
+$O(\sqrt{NT\ln N})$. Dans certains cas les experts sont très nombreux par
+rapport au nombre d'actions ($N$ peut devenir exponentiel en $K$), on
+souhaiterait donc avoir une borne dont la dépendance en $N$ est au plus en
+$O(\ln N)$.
+
+L'algorithme présenté ici est l'algorithme Exp4.P (algorithme par poids
+Exponentiels pour l'Exploitation et l'Exploration avec Experts en grande
+Probabilité). Il s'agit d'un mélange entre les algorithmes Ex3.P et Exp4 comme
+présenté dans \cite{exp4}, et permet d'obtenir une borne en $O(\sqrt{KT\ln N})$.
+
+\begin{encadre}{\textwidth}
+\begin{center}
+\textbf{Algorithme Exp4.P}
+\end{center}
+
+\textbf{Paramètres :} $\beta,\eta,\gamma>0$
+
+\textbf{Initialisation :} On pose $w_{j,0}=1$ et $p_{j,1}=1/K$ pour
+$j\in\{1,\ldots,K\}$.
+
+À chaque tour $t\geq 1$ :
+
+\begin{enumerate}
+\item On tire $I_t\in\{1,\ldots,K\}$ suivant la loi
+$\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$ et on observe le gain $g_{I_t,t}$.
+\item On estime les gains
+$\widetilde{\bs{g}}=(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{K,t})$ à
+partir du gain observé :
+\[
+\forall j\in\{1,\ldots,K\},\quad
+\widetilde{g}_{j,t}=\frac{1}{p_{j,t}}\left(g_{I_t,t}\mathbf{1}_{\{I_t=j\}}
++\beta\right)
+\]
+\item On calcule les gains estimés de chaque expert :
+\[
+\forall i\in\{1,\ldots,N\},\quad
+\widetilde{y}_{i,t} = \bs{\xi}^i_t\cdot\widetilde{\bs{g}}_t
+\]
+
+\item On met à jour les poids exponentiels :
+\[
+\forall i\in\{1,\ldots,N\},\quad
+w_{i,t}=w_{i,t-1}\exp(\eta\widetilde{y}_{i,t})
+\]
+\item On calcule la distribution pour le tour suivant :
+\[
+\forall j\in\{1,\ldots,K\},\quad
+p_{j,t+1}=(1-\gamma)\sum_{i=1}^N\frac{w_{i,t}\xi^i_{j,t}}{W_t}+\frac{\gamma}{K}
+\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{N}w_{i,t}\bigg)\]
+\end{enumerate}
+\end{encadre}
+
+\begin{thm}\label{thm:exp4}
+Soit $\delta\in]0,1[$. On suppose que l'ensemble des experts contient l'expert « uniforme », pour lequel $\bs{\xi}_t=(1/K,\ldots,1/K)$. Si les paramètres de la stratégie Ex4.P vérifient :
+\[\beta\leq 1,\quad
+\gamma\leq \frac{1}{2},\quad
+\eta\leq \frac{\gamma}{2K}
+,\]
+alors on a avec probabilité supérieure à $1-\delta$ :
+\[
+\sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i\leq N}\sum_{t=1}^T \bs{\xi}^i_t\cdot\bs{\ell}_t
+\leq \frac{\ln N}{\eta} + \beta KT
++\frac{1}{\beta}\ln\left(\frac{N}{\delta}\right)
++\big(\gamma+\eta(1+\beta)K\big)T
+\]
+
+En particulier, en prenant:
+\[
+\eta=\frac{1}{2}\sqrt{\frac{\ln N}{KT}},\quad
+\gamma=\sqrt{\frac{K\ln N}{T}},\quad
+\beta=\sqrt{\frac{\ln N}{KT}},
+\]
+si $T\geq 4K\ln N$, on obtient avec probabilité supérieure à $1-\delta$ :
+\[
+\sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i\leq N}\sum_{t=1}^T \bs{\xi}^i_t\cdot\bs{\ell}_t
+\leq \frac{9}{2}\sqrt{KT\ln N}+\sqrt{\frac{KT}{\ln
+N}}\ln\left(\frac{N}{\delta}\right)
++\frac{\ln N}{2}
+\]
+\end{thm}
+
+\begin{proof}
+On suit pas à pas la preuve du théorème \ref{thm:exp3} en faisant correspondre
+à chaque étape les équations obtenues. On pose $q_{i,t}=w_{i,t-1}/W_{t-1}$. On a
+une information parfaite sur les gains estimés des experts, donc en appliquant
+le théorème~\ref{thm:exp}, on obtient comme en \eqref{eq:exp3-fullinfo} :
+\begin{equation}\label{eq:exp4-fullinfo}
+\max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}
+-\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{y}_{i,t}
+\leq\frac{\ln N}{\eta}
++\eta\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{y}_{i,t}^2
+\end{equation}
+
+On relie les $q_{i,t}$ aux $p_{j,t}$ en remarquant que
+$(1-\gamma)\sum_{i=1}^Nq_{i,t}\xi^i_{j,t}\leq p_{j,t}$.
+
+On a :
+\[
+\sum_{i=1}^N q_{i,t}\widetilde{y}_{i,t}
+=\sum_{i=1}^Nq_{i,t}\sum_{j=1}^K \xi^i_{j,t}\widetilde{g}_{j,t}
+=\sum_{j=1}^K\widetilde{g}_{j,t}\sum_{i=1}^N q_{i,t}\xi^i_{j,t}
+\leq\frac{1}{1-\gamma}\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}
+\]
+et, en appliquant l'inégalité de Jensen à la fonction $x\mapsto x^2$ :
+\[
+\begin{split}
+\sum_{i=1}^N q_{i,t}(\widetilde{y}_{i,t})^2
+=\sum_{i=1}^Nq_{i,t}\left(\sum_{j=1}^K \xi^i_{j,t}\widetilde{g}_{j,t}\right)^2
+&\leq\sum_{i=1}^Nq_{i,t}\sum_{j=1}^K\xi^i_{j,t}\widetilde{g}_{j,t}^2\\
+&=\sum_{j=1}^K\widetilde{g}_{j,t}^2\sum_{i=1}^Nq_{i,t}\xi^i_{j,t}
+\leq\frac{1}{1-\gamma}\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}^2
+\end{split}
+\]
+on injecte les deux inégalités précédentes dans \eqref{eq:exp4-fullinfo}, et
+après multiplication par $1-\gamma$, on obtient comme en \eqref{eq:exp3-base}
+: 
+\begin{equation}\label{eq:exp4-base}
+(1-\gamma)\max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}
+-\sum_{t=1}^T\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}
+\leq\frac{\ln N}{\eta}
++\eta\sum_{t=1}^T\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}^2
+\end{equation}
+
+On a de même qu'en \eqref{eq:exp3-maj1} :
+\begin{equation}\label{eq:exp4-maj1}
+\sum_{t=1}^T\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}=
+\sum_{t=1}^T g_{I_t,t}+TK\beta
+\end{equation}
+et on montre l'analogue de \eqref{eq:exp3-maj2} :
+\begin{equation}\label{eq:exp4-maj2}
+\sum_{t=1}^T\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}^2
+\leq(1+\beta)\sum_{t=1}^T \sum_{j=1}^{K}\widetilde{g}_{j,t}
+=(1+\beta) K \sum_{t=1}^T \sum_{j=1}^{K}\frac{\widetilde{g}_{j,t}}{K}
+\leq (1+\beta)K \max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}
+\end{equation}
+En effet, on voit apparaître le gain estimé de l'expert « uniforme », que l'on
+sait appartenir à l'ensemble des experts.
+
+On injecte \eqref{eq:exp4-maj1} et \eqref{eq:exp4-maj2} dans
+\eqref{eq:exp4-base}, et en réordonnant de la même manière que dans la preuve
+du théorème \ref{thm:exp3}, il vient comme en \eqref{eq:exp3-key} :
+\[
+\max_{1\leq i\leq N}\sum_{t=1}^T y_{i,t}
+-\sum_{t=1}^Tg_{I_t,t}
+\leq \frac{\ln N}{\eta} + \beta KT
++\left(\max_{1\leq i\leq N}\sum_{t=1}^T y_{i,t}
+-\max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}\right)
++\big(\gamma+\eta(1+\beta)K\big)T
+\]
+
+Il reste à majorer l'écart entre les gains estimés et les gains réels. On définit la suite d'accroissements de martingale : 
+\[
+X_{i,t}=y_{i,t}-\widetilde{y}_{i,t}+\sum_{j=1}^K\frac{\xi^i_{j,t}\beta}{p_{j,t}}
+= \sum_{j=1}^K \xi^i_{j,t} g_{j,t}\left(1-\frac{\bs{1}_{\{I_t=j\}}}{p_{j,t}}\right)
+\]
+
+On a :
+\[
+\begin{split}
+\mathbb{E}_t[X_{i,t}^2]
+&=\mathbb{E}_t\left[\left(\sum_{j=1}^K \xi^i_{j,t} g_{j,t}\frac{\bs{1}_{\{I_t=j\}}}{p_{j,t}}\right)^2\right]
+-\left(\sum_{j=1}^K \xi^i_{j,t} g_{j,t}\right)^2\\
+&=\mathbb{E}_t\left[\sum_{j=1}^K \left(\xi^i_{j,t} g_{j,t}\right)^2\frac{\bs{1}_{\{I_t=j\}}}{p_{j,t}^2}
+\right]-\left(\sum_{j=1}^K \xi^i_{j,t} g_{j,t}\right)^2
+\leq \sum_{j=1}^K\frac{\xi^i_{j,t}}{p_{j,t}}
+\end{split}
+\]
+
+On applique le corollaire \ref{semibernstein} de la même façon que dans la preuve du théorème \ref{thm:exp3}, on obtient avec probabilité supérieure à $1-\delta$ :
+\[
+\max_{1\leq i\leq N}\sum_{t=1}^T y_{i,t}-\max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}
+\leq \frac{1}{\beta}\ln\left(\frac{N}{\delta}\right)
 \]
 
-\section{Prévision dans un univers convexe}
+On conclut alors de la même manière que, avec probabilité supérieure à $1-\delta$ :
+\[
+\max_{1\leq i\leq N}\sum_{t=1}^T y_{i,t}
+-\sum_{t=1}^Tg_{I_t,t}
+\leq \frac{\ln N}{\eta} + \beta KT
++\frac{1}{\beta}\ln\left(\frac{N}{\delta}\right)
++\big(\gamma+\eta(1+\beta)K\big)T
+\]
 
-Soit $C$ un convexe compact de $\set{R}^n$. On joue au même jeu que
-précédemment, mais au lieu de choisir une action parmi un ensemble fini, on
-choisit un élément de $C$. L'environnement ne choisit donc pas un vecteur de
-perte, mais une fonction de perte définie sur $C$ tout entier.
+Il reste à injecter les valeurs des différents paramètres pour obtenir la deuxième inégalité du théorème.
+\end{proof}
+
+\section{Prévision dans un univers convexe}\label{conv}
+
+Dans les cas où l'ensemble de décision est infini, les algorithmes précédents
+tombent en défaut. Le cadre naturel pour étendre le problème précédent est de
+prendre pour ensemble de décision un convexe compact de $\mathbf{R}^d$.
 
-On note $\Pi_C$ la projection sur le convexe $C$ définie comme au paragraphe
-\ref{projection}.
+Dans l'étude des algorithmes qui suivent, on fera fréquemment des
+considérations de distance. On munit donc $\mathbf{R}^d$ de la métrique usuelle
+induite par la norme euclidienne. On note $\|x\|$ la norme euclidienne d'un
+vecteur $x$ et $x\cdot y$ le produit scalaire canonique entre
+deux vecteurs. Enfin, on choisit $C$ un convexe compact de
+$\mathbf{R^d}$, et on note $\Pi_C$ la projection sur le convexe $C$ définie
+comme au paragraphe \ref{projection}.
 
+Le jeu consiste donc à choisir à chaque tour un élément de $C$, l'adversaire
+choisit non pas un vecteur de perte mais une fonction de perte définie sur le
+convexe tout entier. On impose que les fonctions de perte soient convexes. 
+
+Le plan de cette partie est le même que celui de la partie précédente : on
+commence par étudier le cas de l'information parfaite. L'étude du cas de
+l'information partielle consiste à estimer l'information que l'on ne connaît
+pas et à se ramener au cas précédent.
 
 \subsection{Cas de l'information parfaite}
 
 Ici, le joueur et l'environnement choisissent leurs actions de façon
-déterministe
-en fonction du passé :
+déterministe en fonction du passé. On étudie un algorithme de descente de
+gradient tiré de \cite{zink}.
 
 \begin{encadre}{\textwidth}
 \begin{center}
@@ -586,9 +1111,8 @@ en fonction du passé :
 \item Le joueur choisit un vecteur $x_t\in C$.
 \item Simultanément, l'adversaire choisit une fonction de perte convexe $\ell_t
 : C\to\set{R}^+$.
-\item Le joueur et l'environnement observent la fonction $\ell_t$ et reçoit la
-perte
-$\ell_t(x_t)$.
+\item Le joueur et l'environnement observent la fonction $\ell_t$ et le
+joueur reçoit la perte $\ell_t(x_t)$.
 \end{itemize}
 \end{encadre}
 
@@ -613,12 +1137,25 @@ E : \bigsqcup_{t\geq 1}(C\times\mathscr{C})^t
 \]
 avec $\ell_t = E(H_t)$.
 
-On définit alors le regret pour la stratégie $S$ contre la stratégie $E$ par :
+Le regret pour la stratégie $S$ contre la stratégie $E$ est
+défini par rapport au meilleur choix constant d'un élément de $C$ :
 \[
-R_T(S,E)=\sum_{t=1}^T \ell_t(x_t)-\min_{x\in C}\sum_{t=1}^T\ell_t(x)
+R_T=\sum_{t=1}^T \ell_t(x_t)-\min_{x\in C}\sum_{t=1}^T\ell_t(x)
 =\max_{x\in C}\left(\sum_{t=1}^T \ell_t(x_t)-\ell_t(x)\right)
 \]
 
+Dans le cas où la fonction de perte $\ell_t$ ne varie pas dans le temps, on
+voit que minimiser le regret revient à trouver le minimum d'une fonction
+convexe. Dans ce cas, on sait que les algorithmes de descente de gradient
+fournissent une méthode efficace pour converger vers le minimum.
+
+On cherche une borne sur le regret valable pour tous choix de suite $(\ell_t)$,
+et donc notamment lorsque l'adversaire choisit une suite constante de fonctions
+de perte. Ceci motive l'emploi d'un algorithme de descente de gradient pour
+étudier le problème de prévision dans un ensemble convexe. Auparavant on montre
+que dans le cas de l'information totale, on peut réduire le problème aux
+fonctions de perte linéraires.
+
 \begin{prop}
 Soit $(\ell_1,\ldots,\ell_T)$ une famille de fonctions de pertes convexes et
 différentiables, alors on a :
@@ -648,13 +1185,15 @@ On prend alors le maximum sur $x\in C$ pour obtenir le résultat.
 \end{proof}
 
 Le terme de droite de l'inégalité de la proposition précédente est un terme de
-regret pour la suite de fonctions de perte $(\nabla \ell_t(x_t)$. À partir
+regret pour la suite de fonctions de perte $\nabla \ell_t(x_t)$. À partir
 d'une borne sur le regret valable pour toutes fonctions de perte linéaires, on
-peut donc obtenir une borne valable pour des fonctions de perte convexes.
+peut obtenir une borne valable pour des fonctions de perte convexes.
 
 On supposera donc par la suite que les fonctions de pertes sont linéaires, on
-peut donc les assimiler au produit scalaire par un vecteur de $\set{R}^N$, que
-l'on notera également $\ell_t$ par abus.
+peut les assimiler au produit scalaire par un vecteur de $\set{R}^d$, que
+l'on notera également $\ell_t$ par abus. Le gradient de la fonction $x\mapsto
+\ell_t\cdot x$ est $\ell_t$, donc l'algorithme ci-dessous est effectivement un
+algorithme de descente de gradient.
 
 \begin{encadre}{\textwidth}
 \begin{center}
@@ -673,7 +1212,7 @@ strictement positifs.
 \end{itemize}
 \end{encadre}
 
-\begin{thm}
+\begin{thm}\label{thm:simplezink}
 On note $D$ le diamètre de $C$ pour la norme euclidienne. On suppose que les
 vecteurs de perte $\ell_t$ sont bornés par une constante $K$ pour cette même
 norme. Alors, pour la stratégie de descente de gradient :
@@ -683,11 +1222,9 @@ R_T=\sum_{t=1}^T\ell_t\cdot x_t - \min_{x\in C}\sum_{t=1}^T\ell_t\cdot x
 +\frac{K^2}{2}\sum_{t=1}^T \eta_t
 \]
 
-En particulier, en prenant $\eta_t=\frac{1}{\sqrt{t}}$, on obtient :
+En particulier, en prenant $\eta_t=\eta=\frac{D}{K\sqrt{T}}$, on obtient :
 \[
-R_T
-\leq\frac{D^2}{2}\sqrt{T}
-+K^2\left(\sqrt{T}-\frac{1}{2}\right)
+R_T\leq DK\sqrt{T}
 \]
 \end{thm}
 
@@ -730,36 +1267,319 @@ télescopique :
 \]
 
 On obtient la première inégalité du théorème en prenant le maximum sur $x\in
-C$. Pour la seconde inégalité, il suffit de majorer $\sum_{t=1}^T 1/\sqrt{t}$ :
-\[
-\sum_{t=1}^T \frac{1}{\sqrt{t}}
-\leq 1+\int_{1}^T \frac{\mathrm{d}t}{\sqrt t}
-=2\sqrt T -1
-\qedhere\]
+C$. Pour la seconde inégalité, le choix de $\eta_t$ constant indiqué donne immédiatement la borne voulue.
 \end{proof}
 
-Dans le théorème précédent, le choix du $\eta_t$ est arbitraire. Le choix
-optimal pour $\eta_t$ dépend bien sûr des constantes $K$ et $D$. Cependant,
-si le diamètre $D$ est généralement connu, ce n'est pas toujours le cas de
-$K$, la borne des fonctions de perte. Pour un bon choix des paramètres $\eta_t$,
-on peut toutefois avoir une borne satisfaisante pour le regret :
+Le choix optimal pour la suite $(\eta_t)$ dépend bien sûr des constantes $K$ et
+$D$. Cependant, si le diamètre $D$ est généralement connu, ce n'est pas toujours
+le cas de $K$, la borne des fonctions de perte. Pour un choix adaptatif des
+paramètres $\eta_t$, on peut toutefois avoir une borne satisfaisante pour le
+regret :
 
-\begin{thm}
+\begin{thm}\label{superzink}
 Avec les mêmes hypothèses que précédemment, posons :
 \[
-V_t = \sum_{k=1}^t \|l_t\|^2
+V_t = \sum_{k=1}^t \|\ell_t\|^2
 \]
 alors, pour le choix $\eta_t=D/\sqrt{V_{t-1}}$ on a :
 \[
-R_T\leq \sqrt{6} DK\sqrt{T} + \ldots
+R_T \leq 2 DK\sqrt{T} + \frac{DK^2}{2}
+\]
+\end{thm}
+
+\begin{proof}En reprenant le début de la preuve précédente, on obtient :
+\[
+\sum_{t=1}^T \ell_t\cdot(x_t-x)
+\leq \frac{D^2}{2\eta_T}+\frac{1}{2}\sum_{t=1}^T \eta_t\|\ell_t\|^2
+\]
+
+Notons $T_0$ le premier instant où $V_{t-1}\geq K^2$. Le choix de $\eta_t$ conduit à :
+\begin{equation}\label{zinkadap}
+\sum_{t=1}^T \ell_t\cdot(x_t-x)
+\leq \frac{D^2}{2\eta_T}
++\frac{1}{2}\sum_{t=1}^{T_0-1} \eta_t\|\ell_t\|^2
++\frac{1}{2}\sum_{t=T_0}^T \frac{D}{\sqrt{V_{t-1}}}\|\ell_t\|^2
+\end{equation}
+
+En écrivant $\|\ell_t\|^2=V_t-V_{t-1}$, on voit qu'on doit majorer la quantité :
+\[
+\sum_{t=T_0}^T\frac{V_t-V_{t-1}}{\sqrt{V_{t-1}}}
+=\sum_{t=T_0}^T\frac{\sqrt{V_t}+\sqrt{V_{t-1}}}{\sqrt{V_{t-1}}}\big(\sqrt{V_t}-\sqrt{V_{t-1}}\big)
+\]
+Or, en majorant $\sqrt{V_t}$ par $\sqrt{V_{t-1}}+\|\ell_t\|$ :
+\[
+\frac{\sqrt{V_t}+\sqrt{V_{t-1}}}{\sqrt{V_{t-1}}}
+\leq 2+ \frac{\|\ell_t\|}{\sqrt{V_{t-1}}}
+\leq 3
+\]
+On a donc :
+\[
+\sum_{t=T_0}^T\frac{V_t-V_{t-1}}{\sqrt{V_{t-1}}}
+\leq 3\sqrt{V_T}\leq 3K\sqrt{T}
+\]
+
+En injectant dans \eqref{zinkadap} on obtient :
+\[
+\sum_{t=1}^T \ell_t\cdot(x_t-x)
+\leq \frac{D^2}{2\eta_T}
++\frac{3}{2}DK\sqrt{T}
++\frac{1}{2}\sum_{t=1}^{T_0-1} \eta_t\|\ell_t\|^2
+\leq\frac{1}{2}DK\sqrt{T}
++\frac{3}{2}DK\sqrt{T}
++\frac{1}{2}\sum_{t=1}^{T_0-1} \eta_t\|\ell_t\|^2
+\]
+
+En prenant le maximum pour $x\in C$ on obtient finalement :
+\[
+R_T\leq 2 DK\sqrt{T}+\frac{1}{2}\sum_{t=1}^{T_0-1} \eta_t\|\ell_t\|^2
+\leq 2 DK\sqrt{T} + \frac{D}{2}V_{T_0-1}
+\leq 2 DK\sqrt{T} + \frac{DK^2}{2}
+\]
+
+\end{proof}
+
+\subsection{Information partielle}
+
+On s'intéresse au même problème que précédemment, mais au lieu d'observer la fonction de perte $\ell_t$ à la fin du tour $t$, seule sa valeur en quelques points nous est révélée. On ne peut donc pas directement appliquer l'algorithme de descente de gradient vu précédemment, car on ne plus calculer le gradient de la fonction de perte. L'idée naturelle est donc d'estimer le gradient à partir des observations dont on dispose. 
+
+Dans \cite{conv}, un seul point est observé à chaque tour, et l'estimateur
+proposé conduit à une borne en $O(T^{3/4})$ pour le regret. Pour des fonctions
+de pertes linéaires, Abernethy, Hazan et Rakhlin (\cite{linband}) ont montré une
+borne en $O(\sqrt{T})$. Pour le cas
+général des fonctions convexes, on ne connaît pas encore d'algorithme en
+$O(\sqrt{T})$, \cite{multi} suggère que celui-ci sera sans doute assez différent
+des algorithmes de descente de gradient étudiés jusqu'ici.
+
+Ici, on étudie l'adaptation de l'estimateur de \cite{conv} dans le cas d'une
+observation de deux points comme développée dans \cite{multi}. On obtient alors
+une borne en $O(\sqrt{T})$, borne que l'on sait optimale. 
+
+On choisit comme précédemment pour ensemble de décision un convexe $C$ compact
+de $\mathbf{R^d}$ et on note $D$ son diamètre pour la norme euclidienne.
+
+On observe donc à chaque tour $t$ deux éléments de $C$ que l'on note $y_{1,t}$
+et $y_{2,t}$. On paye ce que l'on observe, c'est à dire que notre perte au tour
+$t$ est mesurée par :
+\[
+\frac{1}{2}\big(\ell_t(y_{1,t})+\ell_t(y_{2,t})\big)
+\]
+
+Comme dans la section précédente, le regret est défini par rapport au meilleur
+choix constant dans $C$ :
+\[
+R_T = \sum_{t=1}^T\frac{1}{2}\big(\ell_t(y_{1,t})+\ell_t(y_{2,t})\big)
+-\min_{x\in C}\sum_{t=1}^T \ell_t(x)
+\]
+
+Précisons maintenant les hypothèses faites sur le convexe $C$ et les fonctions
+de perte $\ell_t$.
+
+On suppose que le convexe contient $0$, et que $0$ est
+dans l'intérieur du convexe, c'est à dire qu'il existe $r$ tel que la boule de
+centre $0$ et de rayon $r$ soit contenue dans le convexe.
+
+Cette hypothèse peut sembler restrictive. En effet, si l'on considère
+l'exemple du simplexe standard de $\mathbf{R^d}$, qui est un cas fréquent en
+prédiction convexe, il est d'intérieure vide dans $\mathbf{R^d}$. En fait le
+problème n'est qu'une apparence :
+
+Tout d'abord, sauf quand le convexe est réduit à un point\footnote{auquel cas
+toute stratégie assure un regret nul}, on peut toujours supposer que le convexe
+est d'intérieur non vide quitte à réduire la dimension de l'espace ambiant
+$\mathbf{R^d}$. En effet, si on prend l'exemple du simplexe standard de
+$\mathbf{R^2}$, il s'agit d'un segment de droite, donc d'intérieur vide dans
+$\mathbf{R^2}$, mais si on le considère plongé dans $\mathbf{R}$, il est
+d'intérieur non vide. Inversement un triangle dans le plan est d'intérieur non
+vide, mais si on le plonge dans l'espace, il devient d'intérieur vide. Il faut
+donc sous-entendre que le convexe $C$ est plongé dans $\mathbf{R^d}$, avec
+\emph{$d$ la dimension minimale pour contenir $C$}. La proposition
+\ref{prop:inclusion}, précise que l'on peut toujours considérer $C$ comme
+plongé dans un espace dans lequel il est d'intérieur non vide.
+
+Soit alors $x_0$ un point dans l'intérieur de $C$, on voit que le problème de
+minimisation de contrôle du regret est invariant par isométrie du convexe, on
+peut donc effectuer une translation de vecteur $-x_0$ et ainsi obtenir que $0$
+est dans le convexe et contenu dans une boule inclue dans le convexe.
+
+Les fonctions de pertes $\ell_t$ sont convexes et vérifient la
+propriété de Lipschitz suivante :
+\[
+\exists G,\;\forall t\geq 1,\;\forall (x,y)\in C^2,\;
+\left|\ell_t(x)-\ell_t(y)\right|\leq G\|x-y\|
+\]
+Enfin on note $\mathcal{B}$ la boule unité. Si $\xi$ est un réel, on note $(1-\xi)C=\{(1-\xi)x,\; x\in C\}$. L'algorithme utilisé est le suivant :
+
+\begin{encadre}{\textwidth}
+\begin{center}
+\textbf{Descente de gradient avec information partielle}
+\end{center}
+
+\textbf{Données :} une suite $(\eta_t)$ décroissante de réels positifs, $\xi\in]0,1[$, $\delta\in[0,\xi r]$.
+
+\textbf{Initialisation :} On joue $x_1$ n'importe où dans $C$.
+
+À chaque tour $t\geq 2$ :
+\begin{enumerate}
+\item On choisit un vecteur $U_t$ uniformément dans $\mathcal{B}$
+\item On note $y_{t,1}=x_t+\delta U_t$ et $y_{t,2}=x_t-\delta
+U_t$, et on observe $\ell_t(y_{t,1})$ et $\ell_t(y_{t,2})$.
+\item On estime le gradient de la fonction en $x_t$ :
+\[
+\widetilde{g}_t = \frac{d}{2\delta}\big(\ell_t(y_{t,1})-\ell_t(y_{t,2})\big)U_t
+\]
+\item On calcule $x_{t+1}$ pour le tour suivant :
+\[
+x_{t+1}=\Pi_{(1-\xi)C}(x_t-\eta_t\widetilde{g}_t)
+\]
+\end{enumerate}
+\end{encadre}
+
+\begin{rem}
+On projette dans $(1-\xi)C$ au lieu de $C$, pour assurer que les points d'exploration $y_{t,1}$ et $y_{t,2}$ appartiennent à $C$. Un argument de convexité montre que pour que tel soit le cas, on doit avoir $\delta\in[0,\xi r]$.
+\end{rem}
+
+
+\paragraph{Notations et premiers résultats}
+On note $\trib{F}_t$ la tribu de l'information dont on dispose au début du tour
+$t$. Il s'agit de la tribu engendrée par les variables $(U_1,\ldots,U_{t-1})$.
+On notera $\mathbb{E}_t$ l'espérance conditionnellement à cette tribu.
+
+On définit une approximation régulière de $\ell_t$ définie sur $(1-\xi)C$. Si
+$V$ est une variable aléatoire uniforme à valeur dans $\mathcal{B}$ :
+\[
+\widehat{\ell}_t(x)=\mathbb{E}_V[\ell_t(x+\delta V)|\trib{F}_t]
+\]
+$\widehat{\ell}_t$ est convexe car $\ell_t$ l'est. De plus en appliquant la
+propriété du Lipschitz à $\ell_t$ sous l'intégrale, on voit que
+$\widehat{\ell}_t$ vérifie également cette propriété pour la même constante
+$G$.
+
+De plus par une application astucieuse du théorème de Stokes, \cite{multi}
+montre que $\widehat{\ell}_t$ est différentiable  en $x_t$ même quand $\ell_t$
+ne l'est pas. Plus précisément, on a :
+\begin{lem}\label{stokes}
+$\widehat{\ell}_t$ est différentiable en $x_t$ et on a :
+\[
+\nabla \widehat{\ell}_t(x_t) = \mathbb{E}_t[\widetilde{g}_t]
+\]
+\end{lem}
+
+\begin{proof}
+La preuve est dans \cite{multi} et n'est pas reproduite ici.
+\end{proof}
+
+En appliquant la propriété de Lipschitz de $\ell_t$ entre les points $y_{1,t}$
+et $y_{2,t}$ et en utilisant que $U_t$ est de norme plus petite que 1, on
+montre que :
+\[
+\widetilde{g}_t\leq Gd
+\]
+
+Enfin, définissons la fonction $h_t$ sur $(1-\xi)C$ par :
+\[
+h_t(x)=\widehat{\ell}_t(x)+\big(\widetilde{g}_t-\nabla \widehat{\ell}_t(x_t)\big)\cdot x
+\]
+$h_t$ est convexe car $\widehat{\ell}_t$ l'est. En utilisant le lemme
+\ref{stokes}, on montre que $\nabla h_t(x_t)=\widetilde{g}_t$. De
+plus, pour tous $x$ et $y$ dans $(1-\xi)C$ :
+\[
+\begin{split}
+|h_t(x)-h_t(y)|&\leq|\widehat{\ell}_t(x)-\widehat{\ell}_t(y)|
++\big(\|\widetilde{g}_t\|+\|\nabla \widehat{\ell}_t(x_t)\|\big)\|x-y\|\\
+&\leq(G+2Gd)\|x-y\|\leq 3Gd\|x-y\|
+\end{split}
+\]
+
+On est en mesure d'énoncer le théorème :
+
+\begin{thm}
+Notons : 
+\[
+V_t = \sum_{k=1}^t \|\widetilde{g}_t\|^2
+\]
+pour les choix des paramètres :
+\[
+\eta_t=\frac{D}{\sqrt{V_{t-1}}},\quad\delta=\frac{r}{T},\quad\xi=\frac{1}{T},
+\]
+alors, pour tout $x\in C$, pour tout $\varepsilon\in ]0,1[$ on a avec
+probabilité supérieure à $1-\varepsilon$ :
+\[
+\sum_{t=1}^T\frac{1}{2}\big(\ell_t(y_{t,1})+\ell_t(y_{t,2})\big)
+-\sum_{t=1}^T\ell_t(x)
+\leq 2 DGd\sqrt{T} + \frac{DG^2 d^2}{2}
++ 4GD
++4GDd\sqrt{2T\ln\left(\frac{1}{\varepsilon}\right)}
 \]
 \end{thm}
 
 \begin{proof}
-$\ldots$ est une constante dépendant de $K$. FINIR LE CALCUL
+On remarque que $\nabla h_t(x_t)=\widetilde{g}_t$, donc l'algorithme présenté s'identifie à une descente de gradient avec information complète pour la fonction $h_t$ dans l'ensemble convexe $(1-\xi)C$. Soit $x\in C$, vu que $\|\nabla h_t(x_t)\|\leq Gd$ et que $(1-\xi)x\in(1-\xi)C$, on peut appliquer le théorème \ref{superzink} :
+\begin{equation}\label{eq:multi-1}
+\sum_{t=1}^T h_t(x_t)
+-\sum_{t=1}^T h_t\big((1-\xi)x\big)
+\leq 2 DGd\sqrt{T} + \frac{DG^2 d^2}{2}
+\end{equation}
+
+Ensuite, on relie d'une part $\ell_t$ à $\widehat{\ell}_t$, puis $\widehat{\ell}_t$ à $h_t$. En utilisant la propriété de Lipschitz de $\ell_t$ on montre que :
+\[
+\frac{1}{2}\big(\ell_t(y_{t,1})+\ell_t(y_{t,2})\big)\leq\ell_t(x_t)+G\delta
+\quad\text{et}\quad
+\ell_t\big((1-\xi)x\big)\leq\ell_t(x)+GD\xi
+\]
+
+Soit $y\in(1-\xi)C$, en utilisant successivement la définition de
+$\widehat{\ell}_t$, l'inégalité de Jensen et la propriété de Lipschitz de
+$\ell_t$, on obtient :
+\[
+|\ell_t(y)-\widehat{\ell}_t(y)|
+\leq\mathbb{E}_V|\ell_t(y)-\ell_t(y+\delta V)|
+\leq G\delta
+\]
+Notamment : 
+\[
+\ell_t(x_t)\leq\widehat{\ell}_t(x_t)+G\delta
+\quad\text{et}\quad
+\widehat{\ell}_t\big((1-\xi)x\big)\leq\ell_t\big((1-\xi)x\big)+G\delta
+\]
+En combinant les inégalités précédentes, on obtient :
+\begin{equation}\label{eq:multi-2}
+\sum_{t=1}^T\frac{1}{2}\big(\ell_t(y_{t,1})+\ell_t(y_{t,2})\big)
+-\sum_{t=1}^T\ell_t(x)
+\leq \sum_{t=1}^T\widehat{\ell}_t(x_t)
+-\sum_{t=1}^T\widehat{\ell}_t\big((1-\xi)x\big)+(3G\delta+GD\xi)T
+\end{equation}
+
+Enfin, pour relier $\widehat{\ell}_t$ à $h_t$, on remarque que $\mathbb{E}_t[h_t]=\widehat{\ell}_t$, donc en posant :
+\[
+X_t=\widehat{\ell}_t(x_t)-\widehat{\ell}_t\big((1-\xi)x\big)-h_t(x_t)+h_t\big((1-\xi)x\big)
+,\]
+$X_t$ est une suite d'accroissement de martingale. De plus, en utilisant les
+remarques préliminaires :
+\[
+|X_t|\leq\big|\widehat{\ell}_t(x_t)-\widehat{\ell}_t\big((1-\xi)x\big)\big|
++\big|h_t(x_t)-h_t\big((1-\xi)x\big)\big|\leq GD+3GdD\leq 4GDd
+\]
+En appliquant l'inégalité de Hoeffding-Azuma, on obtient qu'avec probabilité
+supérieure à $1-\varepsilon$ :
+\begin{equation}\label{eq:multi-3}
+\sum_{t=1}^T X_t \leq 4GDd\sqrt{2T\ln\left(\frac{1}{\varepsilon}\right)}
+\end{equation}
+
+En combinant \eqref{eq:multi-1}, \eqref{eq:multi-2} et \eqref{eq:multi-3}, on
+obtient avec probabilité supérieure à $1-\varepsilon$ :
+\[
+\begin{split}
+ \sum_{t=1}^T\frac{1}{2}\big(\ell_t(y_{t,1})+\ell_t(y_{t,2})\big)
+-\sum_{t=1}^T\ell_t(x)
+&\leq 2 DGd\sqrt{T} + \frac{DG^2 d^2}{2}
++ (3G\delta+GD\xi)T\\
+&\qquad+4GDd\sqrt{2T\ln\left(\frac{1}{\varepsilon}\right)}
+\end{split}
+\]
+
+On obtient alors le résultat annoncé en remplaçant les paramètres par les valeurs indiquées dans l'énoncé.
 \end{proof}
 
- 
 \section{Appendice}
 
 \subsection{Quelques résultats d'analyse réelle}
@@ -813,11 +1633,9 @@ On conclut alors en prenant l'espérance puis en majorant $\ln(1+x)$ par $x$.
 \end{proof}
 
 
-\subsection{Inégalités de martingale}
+\subsection{Inégalités de martingale}\label{inegmart}
 
-Dans cette partie on s'intéressera toujours à un processus aléatoire
-$(X_t)_{t\in\set{N}^*}$ adapté à la filtration
-$(\trib{F}_t)_{t\in\set{N}}$. $\trib{F}_0$ est la tribu triviale.
+Dans cette partie on s'intéressera toujours à un processus aléatoire $(X_t)_{t\in\set{N}^*}$ adapté à la filtration $(\trib{F}_t)_{t\in\set{N}}$. $\trib{F}_0$ est la tribu triviale. Le résultat principal de cette partie est la proposition \ref{bernstein} tirée de \cite{massart}. Il s'agit d'une extension de l'inégalité de Bernstein pour les suites d'accroissements de martingale. On dérive ensuite plusieurs variantes de cette inégalité. L'idée de découpage utilisée dans le corollaire \ref{megabernstein} provient de \cite{label}.
 
 \begin{defi}
 On dit que $(X_t)$ est une suite d'accroissements de martingale si et seulement
@@ -864,12 +1682,12 @@ On conclut alors en utilisant $1+u\leq\exp(u)$ si $u\in\set{R}$.
 \begin{lem}
 Soit $(X_t)$ une suite d'accroissements de martingale majorée par 1. Notons :
 \[
-\forall T \in \set{N}^*, \quad S_T=\sum_{t=1}^T X_t, \quad V_T=\sum_{t=1}^T
+\forall T \in \set{T}^*, \quad S_T=\sum_{t=1}^T X_t, \quad V_T=\sum_{t=1}^T
 \espc{X_t^2}{\trib{F}_{t-1}}
 ,\]
 et définissons, pour $\eta\in\set{R}^+$, le processus $(M_t)$ par :
 \[
-\forall t \in \set{N}^*,\quad
+\forall t \in \set{T}^*,\quad
 M_t=\exp\big(\eta S_t-V_t\left(e^{\eta}-\eta-1\right)\big)
 ,\]
 alors $(M_t)$ est une surmartingale par rapport à la filtration $(\trib{F}_t)$
@@ -898,7 +1716,7 @@ De même qu'on peut étendre l'inégalité de Hoeffding aux suites d'accroisseme
 de martingales pour obtenir l'inégalité de Hoeffding-Azuma, on peut étendre
 ainsi l'inégalité de Bernstein :
 
-\begin{prop}
+\begin{prop}\label{bernstein}
 Soit $(X_1,\ldots,X_T)$ une suite d'accroissements de
 martingale par rapport à la filtration $(\trib{F}_t)$. Supposons
 qu'il existe $K>0$ tel que :
@@ -980,7 +1798,7 @@ directement la variance conditionnelle du processus :
 \begin{cor}\label{megabernstein}
 Soit $(X_1,\ldots,X_T)$ une suite d'accroissements de
 martingale par rapport à la filtration $(\trib{F}_t)$. Supposons que
-presque sûrement on ait : $1\leq V_T\leq \sigma_T^2$ avec $\sigma_T^2\geq 3$ et
+presque sûrement on ait : $v\leq V_T\leq V$ avec $V/v\geq e$ et
 qu'il existe $K>0$
 tel que :
 \[
@@ -990,27 +1808,27 @@ alors, avec probabilité supérieure à $1-\delta$ :
 \[
 \forall C\in\left]1 ;+\infty\right[,\quad
 S_T\leq
-\sqrt{2CV_T\ln\left(\frac{\ln \sigma_T^2}{\delta}\frac{(1+\ln C)}{\ln C}\right)}
-+\frac{2K}{3}\ln\left(\frac{\ln \sigma_T^2}{\delta}\frac{(1+\ln C)}{\ln
+\sqrt{2CV_T\ln\left(\frac{\ln (V/v)}{\delta}\frac{(1+\ln C)}{\ln C}\right)}
++\frac{2K}{3}\ln\left(\frac{\ln (V/v)}{\delta}\frac{(1+\ln C)}{\ln
 C}\right)
 .\]
 
 En particulier, en choisissant $C=3/2$, on obtient :
 \[
 S_T\leq
-\sqrt{3V_T\ln\left(\frac{\ln \sigma_T^2}{\delta/4}\right)}
-+\frac{2K}{3}\ln\left(\frac{\ln \sigma_T^2}{\delta/4}\right)
+\sqrt{3V_T\ln\left(\frac{\ln (V/v)}{\delta/4}\right)}
++\frac{2K}{3}\ln\left(\frac{\ln (V/v)}{\delta/4}\right)
 .\]
 \end{cor}
 
 \begin{proof}
-Posons $N=\lceil\ln \sigma_T^2/\ln C\rceil$
+Posons $N=\lceil\ln (V/v)/\ln C\rceil$
 D'après le corollaire précédent, pour tout $r\in\{1,\ldots,N\}$ :
 \[
 \prob{S_T\geq
-\sqrt{2C^r\ln\left(\frac{N}{\delta}\right)}
+\sqrt{2vC^r\ln\left(\frac{N}{\delta}\right)}
 +\frac{2K}{3}\ln\left(\frac{N}{\delta}\right)
-\ \mathrm{et}\ V_T\leq C^r}\leq\frac{\delta}{N}
+\ \mathrm{et}\ V_T\leq vC^r}\leq\frac{\delta}{N}
 \]
 
 D'où :
@@ -1018,29 +1836,58 @@ D'où :
 \prob{S_T\geq
 \sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}
 +\frac{2K}{3}\ln\left(\frac{N}{\delta}\right)
-\ \mathrm{et}\ C^{r-1}\leq V_T\leq C^r}\leq\frac{\delta}{N}
+\ \mathrm{et}\ vC^{r-1}\leq V_T\leq vC^r}\leq\frac{\delta}{N}
 \]
 
-Or, vu que $1\leq V_T\leq \sigma_T^2\leq C^N$, en sommant l'inégalité
+Or, vu que $v\leq V_T\leq V\leq vC^N$, en sommant l'inégalité
 précédente pour
 $r\in\{1,\ldots,N\}$, on obtient :
 \[
 \prob{S_T\geq
 \sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}
 +\frac{2K}{3}\ln\left(\frac{N}{\delta}\right)
-\leq\delta}
+}\leq\delta
 .
 \]
 
 On conclut en remarquant que :
 \[
-N\leq\frac{\ln \sigma_T^2}{\ln C}+1=\ln \sigma_T^2\frac{(1+\ln C/\ln
-\sigma_T^2)}{\ln C}
-\leq \ln \sigma_T^2\frac{(1+\ln C)}{\ln C}\qedhere
+N\leq\frac{\ln (V/v)}{\ln C}+1=\ln (V/v)\frac{\big(1+\ln C/\ln
+(V/v)\big)}{\ln C}
+\leq \ln (V/v)\frac{(1+\ln C)}{\ln C}\qedhere
+\]
+\end{proof}
+
+Dans les deux corollaires précédents, on applique directement la proposition \ref{bernstein}. Cependant, la preuve de cette proposition fait apparaître une optimisation (celle du paramètre $\eta$ dans la surmartingale $M_t$). Dans certains cas, il est préférable d'optimiser en fonction du contexte d'application. On peut ainsi énoncer une inégalité de Bernstein « non optimisée » :
+
+\begin{cor}\label{semibernstein}
+Soit $(X_1,\ldots,X_T)$ une suite d'accroissements de martingale majorée par 1. Soit $\delta\in]0,1[$, alors pour tout $\eta\in\set{R}^+$, avec probabilité supérieure à $1-\delta$ :
+\[
+S_T\leq\frac{e^{\eta}-\eta-1}{\eta}\,V_T+\frac{1}{\eta}\ln\left(\frac{1}{\delta}\right)
+\]
+
+En particulier, si $\eta\leq 1$ :
+\[
+S_T\leq\eta V_T+\frac{1}{\eta}\ln\left(\frac{1}{\delta}\right)
 \]
+\end{cor}
+
+\begin{proof}
+On repart du lemme \ref{lembernstein}. En appliquant l'inégalité de Doob à la surmartingale $M_t$ du lemme, on a:
+\[
+\prob{M_t\geq \varepsilon}\leq\frac{\esp{M_1}}{\varepsilon}\leq\frac{1}{\varepsilon}
+\]
+En posant $\delta=1/\varepsilon$, on a avec probabilité supérieure à $1-\delta$ :
+\[
+\eta S_T - \big(e^{\eta}-\eta-1\big)V_T\leq\ln\left(\frac{1}{\delta}\right)
+\]
+Ce qui donne, après réarrangement et division par $\eta$ la première inégalité du corollaire.
+
+La deuxième inégalité est une application directe du lemme \ref{inegexp}.
 \end{proof}
 
-\subsection{Projection sur un convexe fermé}
+
+\subsection{Ensembles convexes}
 \label{projection}
 
 On se place dans un espace euclidien $E$. Si $x$ et $y$ sont dans $E$, on note
@@ -1091,6 +1938,37 @@ puis en appliquant l'inégalité de Cauchy-Schwarz :
 \]
 \end{proof}
 
+\begin{prop}\label{prop:inclusion}
+Soit $C$ un convexe de $\mathbf{R}^d$ non réduit à un point, alors il existe
+un sous espace de $\mathbf{R}^d$ contenant $C$ et dans lequel $C$ est
+d'intérieur non vide.
+\end{prop}
+
+\begin{proof}
+Notons $E$ l'espace engendré par le convexe $C$, celui-ci est de dimension
+finie inférieure à $d$. Notons $n$ cette dimension. Par définition, on peut
+trouver une base de $E$, $(c_1,\ldots,c_n)$ constituée d'éléments de $C$.
+
+Considérons $f$ l'application linéaire de $E$ dans $\mathbf{R}^n$ qui envoie
+la base $(c_1,\ldots,c_n)$ sur la base canonique $(e_1,\ldots,e_n)$ de
+$\mathbf{R}^n$. Cette application est bijective.
+
+Munissions $E$ de la topologie induite par la restriction de la norme
+euclidienne de $\mathbf{R^d}$, et $\mathbf{R}^n$ de la topologie euclidienne
+canonique. Puisqu'on est en dimension finie, $f$ est continue, et réalise donc
+un \emph{homéomorphisme linéaire} de $E$ dans $\mathbf{R}^n$.
+
+$C$ étant convexe, l'hyperpyramide de sommmets de $(c_1,\ldots,c_n)$ est
+contenue dans $C$. Donc l'hyperpyramide de sommets $(e_1,\ldots,e_n)$ est
+contenue dans $f(C)$. Il est facile de voir que cet hyperpyramide contient une
+boule ouverte de $\mathbf{R}^n$. L'image réciproque de cette boule ouverte par
+$f$ est donc un ouvert de $C$ (l'image réciproque d'un ouvert par une
+application continue est un ouvert), ce qui prouve que $C$ est d'intérieur non
+vide dans~$E$. 
+\end{proof}
+
+
+\newpage
 \bibliographystyle{plain-fr}
 \bibliography{biblio}