Introduction, quelques correction

2 files changed, 46 insertions, 31 deletions

diff --git a/rapport.pdf b/rapport.pdf
index d74f1c2..cfdf0b0 100644
--- a/rapport.pdf
+++ b/rapport.pdf
diff --git a/rapport.tex b/rapport.tex
index 2e9efda..e43277e 100644
--- a/rapport.tex
+++ b/rapport.tex
@@ -58,40 +58,53 @@
 
 \maketitle
 
-\section{Introduction : Jeu répété de prévision et regret}
+\tableofcontents
+\newpage
 
-\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}
+\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. 
+
+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.}. 
+
+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}.
+
+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.
 
-Le comportement de l'environnement influe également sur la nature du problème :
+\begin{encadre}{\textwidth}
+À chaque tour $t$ : 
+\begin{enumerate}
+\item Le joueur choisit un élément $x_t$ d'un ensemble $\mathcal{A}$.
+\item Indépendamment l'environnement choisit une fonction de perte $\ell_t$ définie sur $\mathcal{A}$.
+\item Le joueur observe l'information $I_t$.
+\end{enumerate}
+\end{encadre}
+
+On distingue principalement deux problèmes suivant la nature de l'information $I_t$ révélée : 
 \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}.
+\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.
 \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 :
+\[
+R_T=\sum_{t=1}^T \ell_t(x_t) - \min_{x\in\mathcal{A}}\sum_{t=1}^T\ell_t(x)
+\]
+
+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.
+
+\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. 
+
 \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 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$.
+
+On résume si dessous le déroulement du jeu.
 
 \begin{encadre}{\textwidth}
 \begin{center}
@@ -130,7 +143,6 @@ un bras d'espérance maximale). Enfin on note :
 \Delta_i = \mu^*-\mu_i
 \]
 
-
 On souhaite avoir une borne sur le regret défini par :
 \[
 R_T = \esp{T\mu^* - \sum_{t=1}^T G_{I_t,t}}
@@ -249,9 +261,9 @@ prévision prend alors la forme du jeu répété suivant :
 \end{center}
 À chaque tour $t\geq 1$ :
 \begin{enumerate}
-\item Le joueur choisi un loi de probabilité sur $\mathcal{A}$,
+\item Le joueur choisit 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,
+\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
 $I_t$. Il reçoit la perte $\ell_{I_t,t}$.
@@ -1079,4 +1091,7 @@ puis en appliquant l'inégalité de Cauchy-Schwarz :
 \]
 \end{proof}
 
+\bibliographystyle{plain-fr}
+\bibliography{biblio}
+
 \end{document}