\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 déterministes} \subsection{Stratégie et résultat} 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} \subsection{Preuve} \paragraph{Étape 1}On commence comme dans le cas de l'information totale en minorant puis en majorant le log-rapport : \[ \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 \] Pour la majoration, on remarque que : \[ \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)} \] 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 : \[ \ln\left(\frac{W_t}{W_{t-1}}\right) \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 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 \] 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} +\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} \] \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}} .\] 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. \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\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 $(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 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}}, ,\] et 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) ,\] alors $(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}