From b55ea4ff22a22386d2f03c316f15c1c62e1f9534 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Fri, 28 May 2010 18:14:01 +0200 Subject: Reprise de la preuve des bandits finis. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit On dégage la première étape : encadrement du log rapport utilisant un lemme type Hoeffding ajoutté en appendice. --- rapport.tex | 97 +++++++++++++++++++++++++++++++++++-------------------------- 1 file changed, 55 insertions(+), 42 deletions(-) diff --git a/rapport.tex b/rapport.tex index 14727c4..c78a2bd 100644 --- a/rapport.tex +++ b/rapport.tex @@ -33,7 +33,9 @@ \maketitle -\section{Bandits à $n$ bras} +\section{Bandits à $N$ bras} + +\subsection{Stratégie et résultat} On utilise la stratégie de prédiction suivante : \begin{encadre}{\textwidth} @@ -64,61 +66,55 @@ $w_{i,t}=w_{i,t-1}\exp(\eta\widetilde{g}_{i,t})$. \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} -\begin{proof}Comme d'habitude, on minore puis on majore le log-rapport : +\paragraph{Étape 1}On commence comme dans le cas de l'information +totale en minorant puis en majorant 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} +=\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 \] -On remarque ensuite que : +Pour la majoration, on remarque 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} +\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)} \] -d'où : +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 : \[ -\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} +\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 alors pour $t\in\{1,\ldots,T\}$, et on combine avec la minoration -trouvée ci-dessus : +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 \] -en multipliant par $(1-\gamma)/\eta$, on obtient finalement : +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} @@ -143,14 +139,9 @@ 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 : +\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}} .\] @@ -159,7 +150,6 @@ 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} @@ -188,9 +178,32 @@ 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$. +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 @@ -230,7 +243,7 @@ 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 : +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}},$$ alors, définissons, pour $\eta\in\set{R}^+$, le processus $(M_t)$ par : -- cgit v1.2.3-70-g09d2