Ajout d'une bibliographie. Nombreux ajouts :

- Algorithme UCB
- Prédiction convexe avec info totale

1 files changed, 576 insertions, 181 deletions

diff --git a/rapport.tex b/rapport.tex
index c40dae6..2e9efda 100644
--- a/rapport.tex
+++ b/rapport.tex
@@ -3,6 +3,7 @@
 \usepackage[utf8x]{inputenc}
 \usepackage[T1]{fontenc}
 \usepackage{calc,amsmath,amssymb,amsthm}
+\usepackage{mathrsfs}
 \usepackage[hmargin=3.5cm]{geometry}
 \usepackage{}
 \newcommand{\trib}[1]{\mathcal{#1}}
@@ -12,11 +13,22 @@
 \newcommand{\prob}[1]{\mathbb{P}\left[#1\right]}
 \renewcommand{\geq}{\geqslant}
 \renewcommand{\leq}{\leqslant}
+\DeclareMathOperator*{\argmax}{arg\,max}
 \newsavebox{\fmbox}
-\newenvironment{encadre}[1]{\begin{lrbox}{\fmbox}%
-\begin{minipage}{\textwidth-3em}\vspace{\baselineskip}}{\vspace{0.5\baselineskip
-} \end{minipage} \end{lrbox} \begin{center}
-\fbox{\hspace{1em}\usebox{\fmbox}\hspace{1em}}\end{center}}
+\newenvironment{encadre}[1]
+{
+\begin{lrbox}{\fmbox}
+\begin{minipage}{\textwidth-3em}
+\vspace{0.3\baselineskip}\setlength{\parskip}{0.5em}
+}
+{
+\vspace{\baselineskip}
+\end{minipage}\end{lrbox}
+\begin{center}
+\fbox{\hspace{1em}\usebox{\fmbox}\hspace{1em}}
+\end{center}
+\vspace{0.5\baselineskip}
+}
 
 \author{Thibaut Horel}
 \title{Prédiction de suites individuelles}
@@ -46,57 +58,252 @@
 
 \maketitle
 
-\section{Prédiction randomisée dans un univers fini}
+\section{Introduction : Jeu répété de prévision et regret}
+
+\section{Prévision dans un univers fini}
+Dans cette partie on souhaite choisir un action parmi un ensemble fini
+$\mathcal{A}$ d'actions. On distingue plusieurs problèmes suivant l'information
+dont on dispose  :
+\begin{itemize}
+\item On parle de \emph{bandit à N bras} si à la fin de chaque tour
+on observe uniquement la perte correspondant à l'action choisie. 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 en même temps, en choisissant une seule machine à
+chaque tour. On ne reçoit donc que la perte de la machine sur laquelle on a
+joué.
+\item Par opposition, on parle de problème à information parfaite si on a accès
+à la perte de toutes les actions (même celles que l'on n'a pas choisies) à la
+fin de chaque tour.
+\end{itemize}
 
-\subsection{Introduction (A DETAILLER)}
-$N$ le nombre d'actions.
+Le comportement de l'environnement influe également sur la nature du problème :
+\begin{itemize}
+\item On parle d'\emph{environnement stochastique} si les pertes reçues sont
+distribuées suivant une loi fixée à l'avance.
+\item Si l'environnement choisit de façon déterministe (et sans faire appel à
+une randomisation externe) les pertes en fonction des actions passées et de
+notre stratégie, il est dit \emph{adversaire déterministe}.
+\end{itemize}
 
-Une stratégie est une suite de lois de probabilités
-$(\mathbf{p_t})_{t\in\set{N}^*}$ avec $\mathbf{p_t}\in\set{R}^N$.
+\subsection{Bandits stochastiques}
+On joue ici sur $N$ machines à sous régies par une famille de lois de
+probabilités $(P_1,\ldots,P_N)$. Au tour $t$, le gain donné par la machine $i$
+est donc une variable aléatoire $G_{i,t}$ à valeurs dans $[0,1]$. La famille
+$(G_{1,t},\ldots,G_{N,t})$ suit la loi $P_1\otimes\ldots\otimes P_N$. Le jeu a
+donc la forme suivante :
 
-La stratégie de l'adversaire est une suite de vecteur de pertes
-$(\mathbf{l_t})_{t\in\set{N}^*}$ avec $\mathbf{l_t}\in\set{R}^N$.
+\begin{encadre}{\textwidth}
+\begin{center}
+\textbf{Jeu contre des bandits stochastiques}
+\end{center}
 
-À chaque tour, on tire $I_t$ suivant la loi $\mathbf{p_t}$.
+À 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 Le joueur reçoit (et observe) le gain $G_{I_t,t}$. 
+\end{enumerate}
+\end{encadre}
 
-On définit le regret pour la stratégie $\mathbf{p}$ contre la stratégie
-$\mathbf{l}$ :
+La stratégie du joueur est donc une fonction $S$ :
 \[
-R_T(\mathbf{p},\mathbf{l})=\sum_{t=1}^T l_{I_t,t}-\min_{1\leq i\leq N}L_{i,T}
+S : \bigsqcup_{t\geq
+1}\big(\mathcal{A}\times[0,1]\big)^t\longrightarrow\mathcal{A}
 \]
-et le regret espéré :
+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
+à 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
+$\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 :
 \[
-R_T^*(\mathbf{p},\mathbf{l}) =
-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}l_{i,t}
--\min_{1\leq i\leq N}L_{i,T}
+\Delta_i = \mu^*-\mu_i
 \]
 
-Si l'on souhaite raisonner avec les gains, en posant $g_{i,t}=1-l_{i,t}$, on
-définit le regret en terme de gains :
+
+On souhaite avoir une borne sur le regret défini par :
 \[
-R_T(\mathbf{p},\mathbf{g})=
-\max_{1\leq i\leq N}G_{i,T}
--\sum_{t=1}^T g_{I_t,t}
+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
 \]
-et le regret espéré en termes de gains :
+où $N_i(T)$ désigne le nombre de fois que le bras $i$ a été joué jusqu'à
+l'instant $t$ :
 \[
-R_T^*(\mathbf{p},\mathbf{g}) =
-\max_{1\leq i\leq N}G_{i,T}
--\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}
+N_i(T)=\sum_{t=1}^T \mathbf{1}_{\{I_t=i\}}
+\]
+
+On utilise la stratégie de prévision suivante :
+
+\begin{encadre}{\textwidth}
+\begin{center}
+\textbf{Stratégie \textsc{ucb} pour les bandits stochastiques}
+\end{center}
+
+\textbf{Initialisation :} On joue chaque bras une fois au cours des $N$
+premiers tours.
+
+À chaque tour $t> N$ :
+\begin{enumerate}
+\item On estime $\mu_i$ à l'aide des données passées :
+\[
+\widehat{\mu}_{i,t-1} = \frac{1}{N_i(t-1)}
+\sum_{k=1}^{t-1}G_{I_k,k}\mathbf{1}_{\{I_k=i\}}
+\]
+\item On choisit un bras $I_t$ qui vérifie :
+\[
+I_t= \argmax_{1\leq i\leq N}
+\left(\widehat{\mu}_{i,t-1}+\sqrt{\frac{2\ln (t-1)}{N_i(t-1)}}\;\right)
 \]
+\item On observe $G_{I_t,t}$. 
+\end{enumerate}
+\end{encadre}
 
-\begin{rem}
-Les symboles $R_T$ et $R_T^*$ n'ont pas la même définition suivant que l'on
-parle de gains et de pertes. Si $\mathbf{g}$ est la suite de gains associée à
-la suite de pertes $\mathbf{l}$, on a les égalités :
+\begin{thm}
+Si les lois $(P_1,\ldots,P_N)$ des machines sont à support dans $[0,1]$, le
+regret au temps T vérifie :
 \[
-R_T(\mathbf{p},\mathbf{l})=R_T(\mathbf{p},\mathbf{g})
+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)
+\]
+\end{thm}
+
+\begin{proof}On note :
+\[
+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 :
+\[
+\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}
+\left\{\bar{X}^*_{s}+c_{t-1,s}
+\leq\bar{X}_{i,s'}+c_{t-1,s'}\right\}
+\end{split}
+\]
+où on a noté :
+\[
+\bar{X}_{i,s}=\frac{1}{s}\sum_{k=1}^s X_{i,k}
 \quad\mathrm{et}\quad
-R_T^*(\mathbf{p},\mathbf{l})=R_T^*(\mathbf{p},\mathbf{g})
+\bar{X}^*_{s}=\frac{1}{s}\sum_{k=1}^s X^*_{k}
+\]
+avec $(X_{i,k})_{k\geq 1}$ une suite iid de variables aléatoires de loi $P_i$
+et $(X^*_{k})_{k\geq 1}$ une suite iid de variables aléatoires de loi $P^*$.
+Le dernier évènement qui apparaît dans la somme est inclus dans l'union des
+trois événements suivants :
+\begin{equation}\label{ev1}
+\bar{X}^*_{s}\leq\mu^*-c_{t-1,s}
+\end{equation}
+\begin{equation}\label{ev2}
+\bar{X}_{i,s}\geq\mu_i+c_{t-1,s'}
+\end{equation}
+\begin{equation}\label{ev3}
+\mu^*<\mu_i + 2 c_{t-1,s'}
+\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
+$\ell=\lceil (8\ln T)/\Delta_i^2\rceil$, l'événement \eqref{ev3} est de
+probabilité nulle. En effet, on a alors :
+\[
+2c_{t-1,s'}\leq 2\sqrt{\frac{2\Delta_i^2\ln (t-1)}{8\ln T}}\leq\Delta_i =
+\mu^*-\mu_i
+\]
+
+On a donc :
+\[
+\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}
+\]
+
+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{encadre}{\textwidth}
+\begin{center}
+\textbf{Jeu de prévision contre un adversaire déterministe}
+\end{center}
+À chaque tour $t\geq 1$ :
+\begin{enumerate}
+\item Le joueur choisi un loi de probabilité sur $\mathcal{A}$,
+$P_t=(p_{1,t},\ldots,p_{N,t})$
+\item Simultanément, l'adversaire choisi 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
+$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
+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$).
+
+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}
+\longrightarrow\Delta(\mathcal{A})
+\]
+qui donne la loi $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
+\]
+qui donne le vecteur de perte $\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
+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 :
+\[
+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}
+\]
+et le regret espéré :
+\[
+\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}
 \]
-\end{rem}
 
-\subsection{Stratégie exponentielle et information totale}
+Par la suite, on raisonnera plutôt en termes de gains : on pose
+$g_{i,t}=1-\ell_{i,t}$, on a donc :
+\[
+\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}
+\]
 
 \begin{encadre}{\textwidth}
 \begin{center}
@@ -110,8 +317,8 @@ $i\in\{1,\ldots,N\}$.
 
 \begin{enumerate}
 \item On tire $I_t\in\{1,\ldots,N\}$ suivant la loi
-$\mathbf{p_t}=(p_{1,t},\ldots,p_{N,t})$.
-\item On observe les gains $\mathbf{g_t}=(g_{1,t},\ldots,g_{N,t})$.
+$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 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 :
@@ -123,10 +330,11 @@ p_{i,t+1}=w_{i,t}/W_t
 \end{encadre}
 
 \begin{thm}\label{infototale}
-On suppose que les gains sont bornés par $K\geq 0$, alors, pour tout $\eta$ tel
+On suppose que les gains sont à valeurs dans $]-\infty, K]$, alors, pour
+tout $\eta$ tel
 que $\eta K\leq 1$ :
 \[
-R_n^* \leq\frac{\ln N}{\eta}
+\bar{R}_T \leq\frac{\ln N}{\eta}
 +\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2
 \]
 \end{thm}
@@ -166,7 +374,13 @@ Enfin on réordonne et on divise par $\eta$.
 \end{proof}
 
 \subsection{Bandits à $N$ bras}
-On utilise la stratégie de prédiction suivante :
+
+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$) : 
 
 \begin{encadre}{\textwidth}
 \begin{center}
@@ -180,9 +394,9 @@ $i\in\{1,\ldots,N\}$.
 
 \begin{enumerate}
 \item On tire $I_t\in\{1,\ldots,N\}$ suivant la loi
-$\mathbf{p_t}=(p_{1,t},\ldots,p_{N,t})$.
+$P_t=(p_{1,t},\ldots,p_{N,t})$.
 \item On estime les gains
-$\mathbf{\widetilde{g}}=(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{N,t})$ à
+$\widetilde{g}=(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{N,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\}}
@@ -209,167 +423,328 @@ Avec  :
 
 \subsection{Preuve}
 On a une information totale sur les gains estimés, donc en notant
-$q_{i,t}=w_{i,t}/W_t$ et en appliquant le résultat du théorème \ref{infototale}
-: 
-\begin{equation}\label{fullinfo}
-R_T^*(\mathbf{q},\mathbf{\widetilde{g}})\leq\frac{\ln N}{\eta}
+$q_{i,t}=w_{i,t-1}/W_{t-1}$ et en appliquant le résultat du théorème
+\ref{infototale} : 
+\[
+\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
-\end{equation}
+\]
 
-puis en utilisant que $p_{i,t}\geq q_{i,t}(1-\gamma)$
+puis en multipliant par $1-\gamma$ et en remarquant que 
+$p_{i,t}\geq q_{i,t}(1-\gamma)$ :
 \[
-\begin{split}
-R_T^*(\mathbf{p},\mathbf{\widetilde{g}})
-&\leq\max_{1\leq i\leq N}\widetilde{G}_{i,T}
--(1-\gamma)\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}\\
-&=(1-\gamma)R_n^*(\mathbf{q},\mathbf{\widetilde{g}})
-+\gamma\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-\end{split}
+(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
 \]
-et en utilisant \eqref{fullinfo} :
+d'où en réordonnant et en utilisant la définition du regret :
 \begin{equation}\label{base}
-R_T^*(\mathbf{p},\mathbf{\widetilde{g}})
-\leq \frac{\ln N}{\eta}
+\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{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
 \left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}+\beta\right)=\sum_{t=1}^T g_{I_t,t}
 +TN\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}_{\{
+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}
-\]
+\end{equation}
 
-D'où on déduit de \eqref{base}, en posant $C=\gamma+\eta(1+\beta)N$:
+En utilisant \eqref{estimation}, on a :
+\[
+\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(\mathbf{p},\mathbf{g})
+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
-+C\max_{1\leq i\leq N}\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
+\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(\mathbf{p},\mathbf{g})
+R_T(P,g)
 \leq \frac{\ln N}{\eta}
-+TN\beta
-+\max_{1\leq i\leq N}G_{i,T}
-+(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,t}
++\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
 \end{equation}
 
-% On souhaite maintenant relier les gains estimés aux gains
-% réels. On remarque que :
-% \[
-% \espc{g_{i,t}-\widetilde{g}_{i,t}}{\trib{F}_{t-1}}=-\frac{\beta}{p_{i,t}}
-% .\]
-% Donc le processus $(X_t)$ défini par
-% \[
-% X_t=g_{i,t}-\widetilde{g}_{i,t}+\frac{\beta}{p_{i,t}}
-% ,\]
-% est une suite d'accroissements de martingale.
-
-On souhaite maintenant relier les gains estimés aux gains
-réels. On choisit $\beta=\sqrt{\ln(N/\delta)/TN}$, alors avec probabilité
-supérieure à $1-\delta$ :
+Il nous reste à majorer l'écart entre les gains et les gains estimés. On
+souhaite appliquer le corollaire \ref{megabernstein} pour la suite
+d'accroissement de martingale $(X_{i,t})_{1\leq t\leq T}$ définie par :
 \[
-\max_{1\leq i\leq N} G_{i,T}-\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-\leq TN\beta = \sqrt{TN\ln\left(\frac{N}{\delta}\right)}
+X_{i,t}=g_{i,t}-\widetilde{g}_{i,t}+\frac{\beta}{p_{i,t}}
+= g_{i,t}\left(1-\frac{\mathbf{1}_{\{I_t=i\}}}{p_{i,t}}\right)
 \]
-d'où en remarquant que $0\leq 1-C\leq 1$ :
+Cette suite est clairement une suite d'accroissements de martingale car on a
+retranché le terme de biais. La variance conditionnelle vaut :
 \[
-(1-C)\max_{1\leq i\leq N} G_{i,T}
-+(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-\leq TN\beta
+\begin{split}
+\mathbb{E}_t[X_{i,t}^2]=\espc{X_{i,t}^2}{\trib{F}_{t-1}}
+&=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)
+\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$ :
+\[
+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)
 \]
-puis, vu que $\max_{1\leq i\leq N} G_{i,T}\leq T$ :
+puis en majorant l'intersection des évènements précédents, on a avec
+probabilité supérieure à $1-\delta/N$ :
 \[
-\max_{1\leq i\leq N} G_{i,T}
-+(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-\leq TN\beta+CT
+a
 \]
+
 en injectant cette dernière majoration dans \eqref{etape2}, on obtient
 finalement :
 \[
-R_T(\mathbf{p},\mathbf{g})
+R_T(P,g)
 \leq \frac{\ln N}{\eta}
-+2TN\beta+\big(\gamma+\eta(1+\beta)\big)T
++\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)
 \]
 
-\section{Prédiction dans un univers convexe}
-Soit $F$ un convexe compact de $\set{R}^n$. À chaque tour on choisit un
-élément $x_t$ dans $F$ tandis que l'adversaire choisit une fonction de perte
-convexe $l_t : F\longrightarrow \set{R}^+$.
+\section{Prévision dans un univers convexe}
+
+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.
 
-On définit le regret par rapport à une stratégie fixe :
+On note $\Pi_C$ la projection sur le convexe $C$ définie comme au paragraphe
+\ref{projection}.
+
+
+\subsection{Cas de l'information parfaite}
+
+Ici, le joueur et l'environnement choisissent leurs actions de façon
+déterministe
+en fonction du passé :
+
+\begin{encadre}{\textwidth}
+\begin{center}
+\textbf{Jeu à information parfaite dans un univers convexe}
+\end{center}
+À chaque tour $t\geq 1$ :
+\begin{itemize}
+\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)$.
+\end{itemize}
+\end{encadre}
+
+Plus précisément, notons $\mathscr{C}$ l'ensemble des fonctions de $C$ dans
+$\set{R}^+$. Le passé avant $t$, noté $H_t$, est une partie de $(C\times
+\mathscr{C})^{t-1}$ :
 \[
-R_T(\mathbf{x},\mathbf{l})=\sum_{t=1}^T l_t(x_t) - \min_{x\in F}\sum_{t=1}^T
-l_t(x)
+H_t = \big((x_1,\ell_1),\ldots,(x_{t-1},\ell_{t-1})\big)
 \]
 
-On veut obtenir des bornes sur le regret valables pour toute stratégie de
-l'adversaire.
+La stratégie du joueur est donc une fonction $S$ : 
+\[
+S : \bigsqcup_{t\geq 1}(C\times\mathscr{C})^t 
+\longrightarrow C
+\]
+et on a $x_t = S(H_t)$.
 
-\subsection{Réduction au cas des pertes linéaires}
+De même, la stratégie de l'environnement est une fonction $E$ :
+\[
+E : \bigsqcup_{t\geq 1}(C\times\mathscr{C})^t 
+\longrightarrow \mathscr{C}
+\]
+avec $\ell_t = E(H_t)$.
+
+On définit alors le regret pour la stratégie $S$ contre la stratégie $E$ par :
+\[
+R_T(S,E)=\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)
+\]
 
 \begin{prop}
-Pour toute stratégie convexe $\mathbf{l}$ de l'adversaire, il existe une
-stratégie linéaire $\mathbf{l'}$ de l'adversaire telle que :
+Soit $(\ell_1,\ldots,\ell_T)$ une famille de fonctions de pertes convexes et
+différentiables, alors on a :
 \[
-R_T(\mathbf{x},\mathbf{l})\leq R_T(\mathbf{x},\mathbf{l'})
+R_T\leq
+\sum_{t=1}^T \nabla \ell_t(x_t)\cdot x_t-\min_{x\in C}\sum_{t=1}^T
+\nabla \ell_t(x_t)\cdot x
 \]
 \end{prop}
 
-\begin{proof} (A PRECISER)
-Il suffit de considérer une suite de sous-gradients des fonctions $l_t$.
+\begin{proof}
+Soit $t\in\{1,\ldots,T\}$, $\ell_t$ est au-dessus de ses tangentes, d'où :
+\[
+\forall x\in C,\quad
+\ell_t(x_t)-\ell_t(x)
+\leq \nabla \ell_t(x_t)\cdot(x_t-x)
+\]
+
+En sommant sur $t$, on obtient :
+\[
+\forall x\in C,\quad
+\sum_{t=1}^T \ell_t(x_t)-\ell_t(x)
+\leq \sum_{t=1}^T \ell'_t\cdot(x_t- x)
+\]
+
+On prend alors le maximum sur $x\in C$ pour obtenir le résultat.
 \end{proof}
 
-On peut donc se restreindre à l'étude du regret pour des fonctions de perte
-linéaire. Dans ce cas on identifie la fonction de perte est représentée par un
-vecteur que l'on nomme également $l_t$. On a donc $l_t(x_t)=l_t\cdot x_t$.
+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
+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.
 
-\subsection{Cas de l'information totale}
+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.
 
-On considère ici qu'à chaque tour on observe le vecteur $l_t$ (et pas seulement
-$l_t\cdot x_t$).
-On fixe une suite $(\eta_t)_{t\in\set{N}^*}$. On utilise alors la stratégie
-suivante :
-\[
-x_{t+1}=p_F(x_t-\eta_t l_t)
-\]
-où $p_F$ est la projection sur le convexe fermé $F$ comme rappelée en
-appendice.
+\begin{encadre}{\textwidth}
+\begin{center}
+\textbf{Descente de gradient}
+\end{center}
 
-Dans le cas d'une fonction de perte linéaire, le vecteur $l_t$ s'identifie au
-gradient de la fonction de perte. La stratégie ci-dessus s'apparente donc à une
-descente de gradient gloutonne.
+\textbf{Donnée :} une suite décroissante $(\eta_t)_{t\in\set{N}^*}$ de réels
+strictement positifs.
+
+\textbf{Initialisation :} On joue $x_1$ n'importe où dans $C$.
+
+À chaque tour $t\geq 2$ :
+\begin{itemize}
+\item On calcule $y_t = x_{t-1}-\eta_{t-1} \ell_{t-1}$
+\item On joue $x_t = \Pi_C(y_t)$
+\end{itemize}
+\end{encadre}
 
 \begin{thm}
-Si toutes les fonctions de pertes sont bornées par la même constante $K$ et que
-l'on note $D$ le diamètre du compact $F$, alors on a :
+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 :
 \[
-R_T(\mathbf{x},\mathbf{l})
+R_T=\sum_{t=1}^T\ell_t\cdot x_t - \min_{x\in C}\sum_{t=1}^T\ell_t\cdot x
 \leq\frac{D^2}{2\eta_T}
 +\frac{K^2}{2}\sum_{t=1}^T \eta_t
 \]
 
 En particulier, en prenant $\eta_t=\frac{1}{\sqrt{t}}$, on obtient :
 \[
-R_T(\mathbf{x},\mathbf{l})
+R_T
 \leq\frac{D^2}{2}\sqrt{T}
 +K^2\left(\sqrt{T}-\frac{1}{2}\right)
 \]
 \end{thm}
 
-\begin{proof} (A PRECISER) majoration du corollaire \ref{projection} +
-transformation d'Abel.
+\begin{proof}
+Soit $x\in C$, d'après l'inégalité \eqref{inegprojection}, on a :
+\[
+\forall t\geq 0,\quad \| x_{t+1} -x\|^2= \| \Pi_C(y_{t+1}) -x\|^2
+\leq \|y_{t+1} -x\|^2
+\]
+D'où :
+\[
+\begin{split}
+\| x_{t+1} -x\|^2
+&\leq \| x_t-\eta_t\ell_t -x\|^2\\
+&=\| x_t -x\|^2-2\eta_t\ell_t\cdot(x_t-x)+\eta_t^2\|\ell_t\|^2
+\end{split}
+\]
+Puis en réordonnant et en majorant $\|\ell_t\|$ par $K$ :
+\[
+\ell_t\cdot(x_t-x)
+\leq \frac{1}{2\eta_t}\big(\| x_t -x\|^2-\| x_{t+1} -x\|^2\big)
++\frac{\eta_t}{2}K^2
+\]
+
+On somme pour $t\in\{1,\ldots,T\}$ :
+\[
+\sum_{t=1}^T \ell_t\cdot(x_t-x)
+\leq \frac{1}{2\eta_1}\| x_1 -x\|^2 
++\frac{1}{2}
+\sum_{t=2}^T\left(\frac{1}{\eta_t}-\frac{1}{\eta_{t-1}}\right)\| x_t-x\|^2
+-\frac{1}{2\eta_T}\| x_{T+1} -x\|^2 
++\frac{K^2}{2}\sum_{t=1}^T \eta_t
+\]
+
+En majorant $\| x_t-x\|^2$ par $D^2$, on fait apparaître une somme
+télescopique :
+\[
+ \sum_{t=1}^T \ell_t\cdot(x_t-x)
+\leq \frac{D^2}{2\eta_T}+\frac{K^2}{2}\sum_{t=1}^T \eta_t
+\]
+
+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\]
+\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 :
+
+\begin{thm}
+Avec les mêmes hypothèses que précédemment, posons :
+\[
+V_t = \sum_{k=1}^t \|l_t\|^2
+\]
+alors, pour le choix $\eta_t=D/\sqrt{V_{t-1}}$ on a :
+\[
+R_T\leq \sqrt{6} DK\sqrt{T} + \ldots
+\]
+\end{thm}
+
+\begin{proof}
+$\ldots$ est une constante dépendant de $K$. FINIR LE CALCUL
 \end{proof}
 
  
@@ -438,13 +813,19 @@ si :
 \[
 \forall t \in \set{N}^*,\quad \espc{X_t}{\trib{F}_{t-1}}=0,
 \]
-ce qui signifie également que le processus $(Y_T)$ défini par :
+ce qui signifie également que le processus $(S_T)$ défini par :
 \[
-\forall T \in \set{N}^*,\quad Y_T=\sum_{t=1}^{T}X_t
+\forall T \in \set{N}^*,\quad S_T=\sum_{t=1}^{T}X_t
 \]
 est une martingale par rapport à la filtration $(\trib{F}_T)$.
 \end{defi}
 
+On notera également :
+\[
+V_T=\sum_{t=1}^T
+\espc{X_t^2}{\trib{F}_{t-1}}
+\]
+
 \begin{lem}\label{lembernstein}
 Soient $X$ une variable aléatoire avec $X\leq 1$ et $\trib{F}$ une tribu telle
 que $\espc{X}{\trib{F}}=0$, alors :
@@ -460,7 +841,7 @@ On a $\eta X\leq \eta$, donc grâce au lemme \ref{inegexp} :
 \exp(\eta X)-\eta X-1\leq X^2(e^\eta-\eta-1)
 .\]
 
-En prenant de part et d'autre l'espérance conditionelle :
+En prenant de part et d'autre l'espérance conditionnelle :
 \[
 \espc{\exp(\eta X)}{\trib{F}}\leq 1 +(e^\eta-\eta-1)\espc{X^2}{\trib{F}}
 .\]
@@ -472,7 +853,7 @@ On conclut alors en utilisant $1+u\leq\exp(u)$ si $u\in\set{R}$.
 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
-\espc{X_t^2}{\trib{F}_{t-1}},
+\espc{X_t^2}{\trib{F}_{t-1}}
 ,\]
 et définissons, pour $\eta\in\set{R}^+$, le processus $(M_t)$ par :
 \[
@@ -508,21 +889,21 @@ ainsi l'inégalité de Bernstein :
 \begin{prop}
 Soit $(X_1,\ldots,X_T)$ une suite d'accroissements de
 martingale par rapport à la filtration $(\trib{F}_t)$. Supposons
-qu'ils existent $K>0$ tel que :
+qu'il existe $K>0$ tel que :
 \[
 \forall t \in \{1,\ldots,T\},\quad X_t\leq K,
 \]
-et $\sigma^2$ tel que $V_T\leq \sigma^2$, alors avec les mêmes notations que
-précédemment, on a:
+et $\sigma^2_T\geq 0$ tel que $V_T\leq \sigma^2_T$ presque sûrement, alors avec
+les mêmes notations que précédemment, on a:
 \[
 \forall\varepsilon>0,\quad
 \prob{\max_{1\leq t\leq T}S_t>\varepsilon}
 \leq
-\exp\left(-\frac{\varepsilon^2}{2\sigma^2+\frac{2}{3}K\varepsilon}\right)
+\exp\left(-\frac{\varepsilon^2}{2\sigma_T^2+\frac{2}{3}K\varepsilon}\right)
 \]
 \end{prop}
 
-\begin{proof} Par homogénéité, on se ramène aux cas où
+\begin{proof} Par homogénéité, on se ramène au cas où
 $K=1$. Soit $\varepsilon$ fixé, on a, pour tout
 $\eta\in\set{R}^+$ :
 \[
@@ -530,7 +911,7 @@ $\eta\in\set{R}^+$ :
 \prob{\max_{1\leq t\leq T}S_t>\varepsilon}
 &=\prob{\eta\max_{1\leq t\leq T}S_t>\eta\varepsilon} \\
 &\leq \prob{\max_{1\leq t\leq T}M_t
->\exp\left(\eta\varepsilon-\sigma^2(e^\eta-\eta-1)\right)}
+>\exp\left(\eta\varepsilon-\sigma_T^2(e^\eta-\eta-1)\right)}
 \end{split}
 \]
 
@@ -539,28 +920,30 @@ lemme \ref{lembernstein} :
 \[
 \begin{split}
 \prob{\max_{1\leq t\leq T}S_t>\varepsilon}
-&\leq \exp\big(\sigma^2(e^\eta-\eta-1)-\eta\varepsilon\big)\esp{M_1}\\
-&\leq \exp\big(\sigma^2(e^\eta-\eta-1)-\eta\varepsilon\big)
+&\leq \exp\big(\sigma_T^2(e^\eta-\eta-1)-\eta\varepsilon\big)\esp{M_1}\\
+&\leq \exp\big(\sigma_T^2(e^\eta-\eta-1)-\eta\varepsilon\big)
 \end{split}
 \]
 
 La borne de droite est minimale pour
-$\eta=\ln\left(1+\frac{\varepsilon}{\sigma^2}\right)$ et donne la majoration : 
+$\eta=\ln\left(1+\frac{\varepsilon}{\sigma_T^2}\right)$ et donne la majoration
+: 
 \[
 \prob{\max_{1\leq t\leq T}S_t>\varepsilon} 
-\leq \exp\left(-\sigma^2 h\left(\frac{\varepsilon}{\sigma^2}\right)\right)
+\leq \exp\left(-\sigma_T^2 h\left(\frac{\varepsilon}{\sigma_T^2}\right)\right)
 \]
 avec $h(x)=(1+x)\ln(1+x)-x$.
 
 On conclut alors en utilisant le lemme \ref{majorationh}.
 \end{proof}
 
-\begin{cor}
+\begin{cor}\label{corbernstein}
 Soit $\delta\in[0,1]$, alors avec les mêmes
 hypothèses que précédemment et probabilité supérieure à $1-\delta$ :
 \[
-S_T\leq\frac{2K}{3}\ln\left(\frac{1}{\delta}\right)+
-\sqrt{2\sigma^2\ln\left(\frac{1}{\delta}\right)}
+S_T\leq
+\sqrt{2\sigma_T^2\ln\left(\frac{1}{\delta}\right)}
++\frac{2K}{3}\ln\left(\frac{1}{\delta}\right)
 .\]
 \end{cor}
 
@@ -571,7 +954,7 @@ avec probabilité $1-\delta$ :
 \[
 S_T\leq \frac{K}{3}\ln\left(\frac{1}{\delta}\right)+
 \sqrt{\frac{K^2}{9}\ln\left(\frac{1}{\delta}\right)^2+
-2\sigma^2\ln\left(\frac{1}{\delta}\right)}
+2\sigma_T^2\ln\left(\frac{1}{\delta}\right)}
 .\]
 
 Puis on conclut en utilisant $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ si $a>0$ et
@@ -582,60 +965,71 @@ On peut également appliquer l'inégalité de Bernstein d'une autre façon, quit
 à renforcer les hypothèses, pour obtenir une inégalité faisant apparaître
 directement la variance conditionnelle du processus :
 
-\begin{cor}
+\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 $V_T\geq
-1$ et qu'il existe $K>0$ tel que :
+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
+qu'il existe $K>0$
+tel que :
 \[
-\forall t \in \{1,\ldots,T\},\quad \left|X_t\right|\leq K,
+\forall t \in \{1,\ldots,T\},\quad X_t\leq K,
 \]
-alors, avec probabilité supérieure à $1-\delta$ et pour $T\geq 3$ :
+alors, avec probabilité supérieure à $1-\delta$ :
 \[
 \forall C\in\left]1 ;+\infty\right[,\quad
-S_T\leq\frac{2K}{3}\ln\left(\frac{\ln T}{\delta}\frac{(1+\ln C)}{\ln C}\right)+
-\sqrt{2CV_T\ln\left(\frac{\ln T}{\delta}\frac{(1+\ln C)}{\ln C}\right)}
+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
+C}\right)
 .\]
 
 En particulier, en choisissant $C=3/2$, on obtient :
 \[
-S_T\leq\frac{2K}{3}\ln\left(\frac{\ln T}{\delta/4}\right)+
-\sqrt{3V_T\ln\left(\frac{\ln T}{\delta/4}\right)}
+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)
 .\]
 \end{cor}
 
 \begin{proof}
-Posons $N=\lceil\ln T/\ln C\rceil$
+Posons $N=\lceil\ln \sigma_T^2/\ln C\rceil$
 D'après le corollaire précédent, pour tout $r\in\{1,\ldots,N\}$ :
 \[
-\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{N}{\delta}\right)+
-\sqrt{2K^2C^r\ln\left(\frac{N}{\delta}\right)}
-\ \mathrm{et}\ V_T\leq K^2C^r}\leq\frac{\delta}{N}
+\prob{S_T\geq
+\sqrt{2C^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}
 \]
 
 D'où :
 \[
-\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{N}{\delta}\right)+
+\prob{S_T\geq
 \sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}
-\ \mathrm{et}\ K^2C^{r-1}\leq V_T\leq K^2C^r}\leq\frac{\delta}{N}
++\frac{2K}{3}\ln\left(\frac{N}{\delta}\right)
+\ \mathrm{et}\ C^{r-1}\leq V_T\leq C^r}\leq\frac{\delta}{N}
 \]
 
-Or, vu que $1\leq V_T\leq K^2T\leq K^2C^N$, en sommant l'inégalité précédente
-pour
+Or, vu que $1\leq V_T\leq \sigma_T^2\leq C^N$, en sommant l'inégalité
+précédente pour
 $r\in\{1,\ldots,N\}$, on obtient :
 \[
-\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{N}{\delta}\right)+
-\sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}}\leq\delta
+\prob{S_T\geq
+\sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}
++\frac{2K}{3}\ln\left(\frac{N}{\delta}\right)
+\leq\delta}
 .
 \]
 
-On conclut en remarquant que, si $T\geq 3$ :
+On conclut en remarquant que :
 \[
-N\leq\frac{\ln T}{\ln C}+1=\ln T\frac{(1+\ln C/\ln T)}{\ln C}
-\leq \ln T\frac{(1+\ln C)}{\ln C}\qedhere
+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
 \]
 \end{proof}
 
 \subsection{Projection sur un convexe fermé}
+\label{projection}
 
 On se place dans un espace euclidien $E$. Si $x$ et $y$ sont dans $E$, on note
 $x\cdot y$ le produit scalaire entre $x$ et $y$ et $\|x\|$ la norme euclidienne
@@ -655,33 +1049,34 @@ De plus $x$ vérifie la propriété de l'angle obtus :
 \]
 
 On dit que $x$ est la projection de $y$ sur le convexe $F$, et on note
-$x=p_F(y)$.
+$x=\Pi_F(y)$.
 \end{prop}
 
-On en déduit notamment que pour tout $z\in F$, $\|y-p_F(y)\|\leq\|y-z\|$.
+On en déduit notamment que pour tout $z\in F$, $\|y-\Pi_F(y)\|\leq\|y-z\|$.
 L'inégalité de l'angle obtus permet d'obtenir une autre inégalité.
 
-\begin{cor}\label{projection}
+\begin{cor}\label{inegprojection}
 Soient $F$ une partie convexe fermée non vide de $E$ et $y\in E$. Alors :
 \[
 \forall z\in F,\quad
-\|z-p_F(y)\|\leq\|z-y\|
+\|z-\Pi_F(y)\|\leq\|z-y\|
 \]
 \end{cor}
 
 \begin{proof}
 Soit $z\in F$, on part de l'inégalité de l'angle obtus :
 \[
-(y-p_F(y))\cdot(z-p_F(y))\leq 0
+\big(y-\Pi_F(y)\big)\cdot\big(z-\Pi_F(y)\big)\leq 0
 \]
 d'où :
 \[
-(y-z+z-p_F(y))\cdot(z-p_F(y))
-=\|z-p_F(y)\|^2-(z-y)\cdot(z-p_F(y))\leq 0
+\big(y-z+z-\Pi_F(y)\big)\cdot\big(z-\Pi_F(y)\big)
+=\|z-\Pi_F(y)\|^2-(z-y)\cdot\big(z-\Pi_F(y)\big)\leq 0
 \]
 puis en appliquant l'inégalité de Cauchy-Schwarz :
 \[
-\|z-p_F(y)\|^2\leq\|z-y\|\|z-p_F(y)\|\qedhere
+\|z-\Pi_F(y)\|^2\leq\|z-y\|\|z-\Pi_F(y)\|\qedhere
 \]
 \end{proof}
+
 \end{document}