diff options
| -rw-r--r-- | rapport.tex | 384 |
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} |