Initial commit tracking only the tex source file.

1 files changed, 384 insertions, 0 deletions

diff --git a/rapport.tex b/rapport.tex
new file mode 100644
index 0000000..14727c4
--- /dev/null
+++ b/rapport.tex
@@ -0,0 +1,384 @@
+\documentclass[titlepage,11pt]{article}
+\usepackage[french]{babel}
+\usepackage[utf8x]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{amsmath,amssymb,amsthm,calc}
+\usepackage[hmargin=3.5cm]{geometry}
+\newcommand{\trib}[1]{\mathcal{#1}}
+\newcommand{\set}[1]{\mathbf{#1}}
+\newcommand{\esp}[1]{\mathbb{E}\left[#1\right]}
+\newcommand{\espc}[2]{\mathbb{E}\left[#1|#2\right]}
+\newcommand{\prob}[1]{\mathbb{P}\left[#1\right]}
+\renewcommand{\geq}{\geqslant}
+\renewcommand{\leq}{\leqslant}
+\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}}
+\author{Thibaut Horel}
+
+\title{Bandits à $n$ bras}
+\date{sujet encadré par Gilles Stoltz}
+
+
+\begin{document}
+\theoremstyle{definition}
+\newtheorem{prop}{Proposition}[section]
+\newtheorem{thm}[prop]{Théorème}
+\newtheorem{cor}[prop]{Corollaire}
+\newtheorem{lem}[prop]{Lemme}
+\newtheorem*{defi}{Définition}
+
+\maketitle
+
+\section{Bandits à $n$ bras}
+On utilise la stratégie de prédiction suivante :
+
+\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\}$.
+
+À chaque tour $t\geq 1$ :
+
+\begin{enumerate}
+\item On tire $I_t\in\{1,\ldots,N\}$ suivant la loi
+$(p_{1,t},\ldots,p_{N,t})$.
+\item On estime les gains $(\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\}}
++\beta\right)
+\]
+
+\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)\]
+\end{enumerate}
+\end{encadre}
+
+\begin{thm}
+Avec  :
+\[\beta\leq 1,\quad
+\gamma\leq \frac{1}{2},\quad
+\eta\leq \frac{\gamma}{2N}
+\]
+
+\end{thm}
+
+
+\begin{proof}Comme d'habitude, on minore puis on majore 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}
+\]
+
+On remarque ensuite 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}
+\]
+d'où :
+\[
+\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}
+\]
+
+On somme alors pour $t\in\{1,\ldots,T\}$, et on combine avec la minoration
+trouvée ci-dessus :
+\[
+\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 :
+\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}
++\eta \sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
+\end{equation}
+
+Vu le choix de l'estimateur de gain, on a :
+\[
+\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
+=\sum_{i=1}^N
+\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}+\beta\right)=g_{I_t,t}+N\beta
+\]
+et :
+\[
+\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2=\sum_{i=1}^N
+\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}
+\]
+
+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 :
+\[
+\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.
+\end{proof}
+
+\section{Appendice}
+
+\subsection{Quelques résultats d'analyse réelle}
+
+\begin{lem}\label{inegexp}
+La fonction $x\longmapsto (e^x-x-1)/x^2$ est croissante sur $\set{R}$. 
+\end{lem}
+
+\begin{proof}
+Évident.
+\end{proof}
+
+\begin{lem}\label{majorationh}
+Pour tout $x\in\set{R}^+$ :
+\[
+(1+x)\ln(1+x)-x\geq \frac{x^2}{2+\frac{2}{3}x}
+\]
+\end{lem}
+
+\begin{proof}
+Les deux fonctions apparaissant de part et d'autre de l'inégalité s'éga\-lent en
+0, de même que leurs dérivées premières. Par développement de Taylor avec
+reste intégrale, il suffit donc de montrer l'inégalité pour les dérivées
+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$.  
+\end{proof}
+
+\subsection{Inégalités de martingale}
+
+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.
+
+\begin{defi}
+On dit que $(X_t)$ est une suite d'accroissements de martingale si et seulement
+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 :
+\[
+\forall T \in \set{N}^*,\quad Y_T=\sum_{t=1}^{T}X_t
+\]
+est une martingale par rapport à la filtration $(\trib{F}_T)$.
+\end{defi}
+
+\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 :
+\[
+\forall\eta\in\set{R}^+,\quad \espc{\exp(\eta X)}{\trib{F}}
+\leq \exp\left(\espc{X^2}{\trib{F}}(e^\eta-\eta-1)\right)
+\]
+\end{lem}
+
+\begin{proof}
+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 :
+$$\espc{\exp(\eta X)}{\trib{F}}\leq 1 +(e^\eta-\eta-1)\espc{X^2}{\trib{F}}.$$
+
+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 :
+$$\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 :
+\[
+\forall t \in \set{N}^*,\quad
+M_t=\exp\big(\eta S_t-V_t\left(e^{\eta}-\eta-1\right)\big),
+\]
+$(M_t)$ est une surmartingale par rapport à la filtration $(\trib{F}_t)$ et
+$\esp{M_1}\leq 1$
+\end{lem}
+
+\begin{proof}La majoration de $\esp{M_1}$ est une application directe du
+lemme \ref{lembernstein}. Pour le caractère surmartingale, soit $t\geq 2$, on
+a :
+\[\begin{split}
+\espc{M_t}{\trib{F}_{t-1}}
+&=\espc{\exp\big(\eta S_t-V_t(e^{\eta}-\eta-1)\big)}{\trib{F}_{t-1}} \\ 
+&=M_{t-1}\mathbb{E}\Big[\exp\big(\eta
+X_t-\espc{X_t^2}{\trib{F}_{t-1}}(e^{\eta}-\eta-1)\big)\big|\trib{F}_{t-1
+}\Big] \\
+&=M_{t-1} \frac{\espc{\exp\left(\eta
+X_t\right)}{\trib{F}_{t-1}}}{\exp\left(\espc
+{X_t^2}{\trib{F}_{t-1}}(e^{\eta}-\eta-1)\right)}\\
+&\leq M_{t-1}
+\end{split}
+\]
+où la dernière inégalité provient du lemme \ref{lembernstein}.
+\end{proof}
+
+De même qu'on peut étendre l'inégalité de Hoeffding aux suites d'accroissements
+de martingales pour obtenir l'inégalité de Hoeffding-Azuma, on peut étendre
+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 :
+\[
+\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:
+\[
+\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)
+\]
+\end{prop}
+
+\begin{proof} Par homogénéité, on se ramène aux cas où
+$K=1$. Soit $\varepsilon$ fixé, on a, pour tout
+$\eta\in\set{R}^+$ :
+\[
+\begin{split}
+\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)}
+\end{split}
+\]
+
+Puis en utilisant successivement l'inégalité de Doob et le
+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)
+\end{split}
+\]
+
+La borne de droite est minimale pour
+$\eta=\ln\left(1+\frac{\varepsilon}{\sigma^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)
+\]
+avec $h(x)=(1+x)\ln(1+x)-x$.
+
+On conclut alors en utilisant le lemme \ref{majorationh}.
+\end{proof}
+
+\begin{cor}
+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)}
+.\]
+\end{cor}
+
+\begin{proof}
+On pose $\delta$ égal au membre de droite de l'inégalité de
+Bernstein, puis on exprime $\varepsilon$ en fonction de $\delta$. On obtient
+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)}
+.\]
+
+Puis on conclut en utilisant $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ si $a>0$ et
+$b>0$.
+\end{proof}
+
+On peut également appliquer l'inégalité de Bernstein d'une autre façon, quitte
+à renforcer les hypothèses, pour obtenir une inégalité faisant apparaître
+directement la variance conditionnelle du processus :
+
+\begin{cor}
+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 :
+\[
+\forall t \in \{1,\ldots,T\},\quad \left|X_t\right|\leq K,
+\]
+alors, avec probabilité supérieure à $1-\delta$ :
+\[
+S_T\leq\frac{2K}{3}\ln\left(\frac{T}{\delta}\right)+
+\sqrt{2(V_T+K^2)\ln\left(\frac{T}{\delta}\right)}
+.\]
+\end{cor}
+
+\begin{proof}
+D'après le corollaire précédent, pour tout $t\in\{1,\ldots,T\}$ :
+\[
+\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{T}{\delta}\right)+
+\sqrt{2K^2t\ln\left(\frac{T}{\delta}\right)}
+\ \mathrm{et}\ V_T\leq K^2t}\leq\frac{\delta}{T}
+\]
+
+D'où :
+\[
+\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{T}{\delta}\right)+
+\sqrt{2(V_T+K^2)\ln\left(\frac{T}{\delta}\right)}
+\ \mathrm{et}\ K^2(t-1)\leq V_T\leq K^2t}\leq\frac{\delta}{T}
+\]
+
+Or, vu que $0\leq V_T\leq K^2T$, en sommant l'inégalité précédente pour
+$t\in\{1,\ldots,T\}$, on obtient :
+\[
+\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{T}{\delta}\right)+
+\sqrt{2(V_T+K^2)\ln\left(\frac{T}{\delta}\right)}}\leq\delta
+.\qedhere
+\]
+\end{proof}
+
+
+
+\end{document}