path: root/rapport.tex

\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}