1 files changed, 55 insertions, 42 deletions
diff --git a/rapport.tex b/rapport.tex
index 14727c4..c78a2bd 100644
--- a/rapport.tex
+++ b/rapport.tex
@@ -33,7 +33,9 @@
 
 \maketitle
 
-\section{Bandits à $n$ bras}
+\section{Bandits à $N$ bras}
+
+\subsection{Stratégie et résultat}
 On utilise la stratégie de prédiction suivante :
 
 \begin{encadre}{\textwidth}
@@ -64,61 +66,55 @@ $w_{i,t}=w_{i,t-1}\exp(\eta\widetilde{g}_{i,t})$.
 \end{enumerate}
 \end{encadre}
 
+
 \begin{thm}
 Avec  :
 \[\beta\leq 1,\quad
 \gamma\leq \frac{1}{2},\quad
 \eta\leq \frac{\gamma}{2N}
 \]
-
 \end{thm}
 
+\subsection{Preuve}
 
-\begin{proof}Comme d'habitude, on minore puis on majore le log-rapport :
+\paragraph{Étape 1}On commence comme dans le cas de l'information
+totale en minorant puis en majorant le log-rapport :
 \[
-\begin{split}
 \ln\left(\frac{W_T}{W_{0}}\right)
-&=\ln\left(\sum_{i=1}^N\exp(\eta\widetilde{G}_{i,T})\right)-\ln N \\
-&\geq \eta \max_{1\leq i\leq N}\widetilde{G}_{i,T}-\ln N 
-\end{split} \]
-
-Pour la majoration, on utilise d'abord $\ln x\leq x-1$, si $x>0$
-puis $e^x\leq 1+x+x^2$, si $x\leq 1$ (qui découle du lemme \ref{inegexp}), ce
-qui permet d'écrire :
-\[
-\begin{split}
-\ln\left(\frac{W_t}{W_{t-1}}\right)
-&\leq
-\frac{W_t}{W_{t-1}}-1=\sum_{i=1}^N\frac{w_{i,t-1}}{
-W_{t-1}}\exp(\eta\widetilde{g}_{i,t})-1\\
-&\leq\sum_{i=1}^N\frac{w_{i,t-1}}{
-W_{t-1}}\left(1+\eta\widetilde{g}_{i,t}+\eta^2\widetilde{g}_{i,t}^2\right)-1
-\end{split}
+=\ln\left(\sum_{i=1}^N\exp(\eta\widetilde{G}_{i,T})\right)-\ln N \\
+\geq \eta \max_{1\leq i\leq N}\widetilde{G}_{i,T}-\ln N
 \]
 
-On remarque ensuite que :
+Pour la majoration, on remarque que :
 \[
-\sum_{i=1}^N\frac{w_{i,t-1}}{W_{t-1}}=1
-\quad\mathrm{et}\quad\frac{w_{i,t-1}}{W_{t-1}}=\frac{p_{i,t}-\frac{\gamma}{N}}{
-1-\gamma}\leq\frac{p_{i,t}}{1-\gamma}
+\ln\left(\frac{W_t}{W_{t-1}}\right)
+=\ln\left(\sum_{i=1}^N
+\frac{w_{i,t-1}}{W_{t-1}}\exp(\eta\widetilde{g}_{i,t})\right)
+=\ln\esp{\exp(\eta X)}
 \]
-d'où :
+où $X$ est une variable aléatoire qui vaut $\widetilde{g}_{i,t}$ avec
+probabilité $q_{i,t}=w_{i,t-1}/W_{t-1}$. On peut donc appliquer le lemme
+\ref{espexp}, on obtient :
 \[
-\begin{split}
 \ln\left(\frac{W_t}{W_{t-1}}\right)
-&\leq\frac{\eta}{1-\gamma}\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
-+\frac{\eta^2}{1-\gamma}\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
-\end{split}
+\leq\eta\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}
++\eta^2\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}^2
 \]
 
-On somme alors pour $t\in\{1,\ldots,T\}$, et on combine avec la minoration
-trouvée ci-dessus :
+On somme pour $t\in\{1,\ldots,N\}$ et on combine avec la minoration :
+\[
+\eta \max_{1\leq i\leq N}\widetilde{G}_{i,T}-\ln N 
+\leq \eta\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}
++\eta^2 \sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}^2
+.\]
+
+\paragraph{Étape 2} On remarque que $q_{i,t}\leq p_{i,t}/(1-\gamma)$ d'où
 \[
 \eta \max_{1\leq i\leq N}\widetilde{G}_{i,T}-\ln N
 \leq\frac{\eta}{1-\gamma}\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
 +\frac{\eta^2}{1-\gamma}\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
 \]
-en multipliant par $(1-\gamma)/\eta$, on obtient finalement :
+puis en multipliant par $(1-\gamma)/\eta$ :
 \begin{equation}\label{base}
 (1-\gamma)\max_{1\leq i\leq N}\widetilde{G}_{i,T} -\frac{1-\gamma}{\eta}\ln N
 \leq \sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
@@ -143,14 +139,9 @@ D'où on déduit de \eqref{base} :
 (1-\gamma)\max_{1\leq i\leq N}\widetilde{G}_{i,T} -\frac{1-\gamma}{\eta}\ln N
 \leq G_T + TN\beta +\eta(1+\beta)\sum_{i=1}^N\widetilde{G}_{i,T}
 \]
-où on a posé :
-\[
-G_T=\sum_{t=1}^T g_{I_t,t}\quad\mathrm{et}\quad
-\widetilde{G}_{i,T}=\sum_{t=1}^T \widetilde{g}_{i,t}
-\]
 
-On souhaite maintenant relier les gains estimés aux gains réels. On remarque
-que :
+\paragraph{Étape 3}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}}
 .\]
@@ -159,7 +150,6 @@ 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.
-\end{proof}
 
 \section{Appendice}
 
@@ -188,9 +178,32 @@ secondes, ce qui s'écrit :
 \[
 \frac{1}{1+x}\geq \left(\frac{1}{1+\frac{x}{3}}\right)^3
 \]
-que l'on sait vraie car $(1+x)^3\leq 1+3x$ si $x>0$.  
+que l'on sait vraie car $(1+x)^3\geq 1+3x$ si $x>0$.  
 \end{proof}
 
+\subsection{Inégalités de variables aléatoires}
+
+On commence avec un lemme de « type Hoeffding » où on remplace un majorant de
+la variance par la variance elle-même.
+
+\begin{lem}\label{espexp}
+Soient $X$ une variable aléatoire et $\eta\in\set{R}^+$ tels que $\eta X\leq 1$
+alors :
+\[
+\ln\esp{\exp(\eta X)}\leq \eta \esp{X} +\eta^2(e-2)\esp{X^2}
+.\]
+\end{lem}
+
+\begin{proof}
+On a $\eta X\leq 1$, donc en appliquant le lemme \ref{inegexp}, on a :
+\[
+\exp(\eta X) \leq 1 +\eta X + \eta^2(e-2)X^2
+\]
+
+On conclut alors en prenant l'espérance puis en majorant $\ln(1+x)$ par $x$.
+\end{proof}
+
+
 \subsection{Inégalités de martingale}
 
 Dans cette partie on s'intéressera toujours à un processus aléatoire
@@ -230,7 +243,7 @@ On conclut alors en utilisant $1+u\leq\exp(u)$ si $u\in\set{R}$.
 \end{proof}
 
 \begin{lem}
-Soit $(X_t)$ une suite d'accroissements de martingale. Notons :
+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}},$$
 alors, définissons, pour $\eta\in\set{R}^+$, le processus $(M_t)$ par :