From 5a3533fa3f2fb02fd3cda2b546549a61b8d0407b Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Tue, 1 Jun 2010 17:14:08 +0200 Subject: Progrès pour univers fini et début pour univers convexe MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit - introduction pour la partie univers fini - traitement du cas avec information totale à part - simplification du début de la preuve du résultat principal à l'aide du cas full info - reprise de la fin de cette preuve en tenant compte des modifications sur le début - appendice sur les projections sur convexes - cas full info pour les univers convexes --- rapport.tex | 387 ++++++++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 310 insertions(+), 77 deletions(-) (limited to 'rapport.tex') diff --git a/rapport.tex b/rapport.tex index 8716905..c40dae6 100644 --- a/rapport.tex +++ b/rapport.tex @@ -2,8 +2,9 @@ \usepackage[french]{babel} \usepackage[utf8x]{inputenc} \usepackage[T1]{fontenc} -\usepackage{amsmath,amssymb,amsthm,calc} +\usepackage{calc,amsmath,amssymb,amsthm} \usepackage[hmargin=3.5cm]{geometry} +\usepackage{} \newcommand{\trib}[1]{\mathcal{#1}} \newcommand{\set}[1]{\mathbf{#1}} \newcommand{\esp}[1]{\mathbb{E}\left[#1\right]} @@ -12,18 +13,25 @@ \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} +\author{Thibaut Horel} +\title{Prédiction de suites individuelles} \date{sujet encadré par Gilles Stoltz} +\newtheoremstyle{remark} + {}% Space above, empty = `usual value' + {}% Space below + {}% Body font + {}% Indent amount (empty = no indent, \parindent = para indent) + {\scshape}% Thm head font + {.}% Punctuation after thm head + { }% Space after thm head: " " = normal interword space; + {}% Thm head spec -\begin{document} \theoremstyle{definition} \newtheorem{prop}{Proposition}[section] \newtheorem{thm}[prop]{Théorème} @@ -31,16 +39,68 @@ \newtheorem{lem}[prop]{Lemme} \newtheorem*{defi}{Définition} +\theoremstyle{remark} +\newtheorem*{rem}{Remarque} + +\begin{document} + \maketitle -\section{Bandits à $N$ bras déterministes} +\section{Prédiction randomisée dans un univers fini} -\subsection{Stratégie et résultat} -On utilise la stratégie de prédiction suivante : +\subsection{Introduction (A DETAILLER)} +$N$ le nombre d'actions. + +Une stratégie est une suite de lois de probabilités +$(\mathbf{p_t})_{t\in\set{N}^*}$ avec $\mathbf{p_t}\in\set{R}^N$. + +La stratégie de l'adversaire est une suite de vecteur de pertes +$(\mathbf{l_t})_{t\in\set{N}^*}$ avec $\mathbf{l_t}\in\set{R}^N$. + +À chaque tour, on tire $I_t$ suivant la loi $\mathbf{p_t}$. + +On définit le regret pour la stratégie $\mathbf{p}$ contre la stratégie +$\mathbf{l}$ : +\[ +R_T(\mathbf{p},\mathbf{l})=\sum_{t=1}^T l_{I_t,t}-\min_{1\leq i\leq N}L_{i,T} +\] +et le regret espéré : +\[ +R_T^*(\mathbf{p},\mathbf{l}) = +\sum_{t=1}^T\sum_{i=1}^N p_{i,t}l_{i,t} +-\min_{1\leq i\leq N}L_{i,T} +\] + +Si l'on souhaite raisonner avec les gains, en posant $g_{i,t}=1-l_{i,t}$, on +définit le regret en terme de gains : +\[ +R_T(\mathbf{p},\mathbf{g})= +\max_{1\leq i\leq N}G_{i,T} +-\sum_{t=1}^T g_{I_t,t} +\] +et le regret espéré en termes de gains : +\[ +R_T^*(\mathbf{p},\mathbf{g}) = +\max_{1\leq i\leq N}G_{i,T} +-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t} +\] + +\begin{rem} +Les symboles $R_T$ et $R_T^*$ n'ont pas la même définition suivant que l'on +parle de gains et de pertes. Si $\mathbf{g}$ est la suite de gains associée à +la suite de pertes $\mathbf{l}$, on a les égalités : +\[ +R_T(\mathbf{p},\mathbf{l})=R_T(\mathbf{p},\mathbf{g}) +\quad\mathrm{et}\quad +R_T^*(\mathbf{p},\mathbf{l})=R_T^*(\mathbf{p},\mathbf{g}) +\] +\end{rem} + +\subsection{Stratégie exponentielle et information totale} \begin{encadre}{\textwidth} \begin{center} -\textbf{Algorithme Exp3.P} +\textbf{Stratégie par poids exponentiels} \end{center} \textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/N$ pour @@ -50,97 +110,159 @@ $i\in\{1,\ldots,N\}$. \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) -\] - +$\mathbf{p_t}=(p_{1,t},\ldots,p_{N,t})$. +\item On observe les gains $\mathbf{g_t}=(g_{1,t},\ldots,g_{N,t})$. \item On met à jour les poids exponentiels : -$w_{i,t}=w_{i,t-1}\exp(\eta\widetilde{g}_{i,t})$. +$w_{i,t}=w_{i,t-1}\exp(\eta 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)\] +\[ +p_{i,t+1}=w_{i,t}/W_t +\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} +\begin{thm}\label{infototale} +On suppose que les gains sont bornés par $K\geq 0$, alors, pour tout $\eta$ tel +que $\eta K\leq 1$ : +\[ +R_n^* \leq\frac{\ln N}{\eta} ++\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2 \] \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 : +\begin{proof} +On minore puis on majore 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 +=\ln\left(\sum_{i=1}^N\exp(\eta G_{i,T})\right)-\ln N \\ +\geq \eta \max_{1\leq i\leq N}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) +\frac{w_{i,t-1}}{W_{t-1}}\exp(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 +où $X$ est une variable aléatoire qui vaut $g_{i,t}$ avec +probabilité $p_{i,t}$. 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 +\leq\eta\sum_{i=1}^N p_{i,t}g_{i,t} ++\eta^2\sum_{i=1}^N p_{i,t}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 +\eta \max_{1\leq i\leq N}G_{i,T}-\ln N +\leq \eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t} ++\eta^2 \sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2 .\] -\paragraph{Étape 2} On remarque que $q_{i,t}\leq p_{i,t}/(1-\gamma)$ d'où +Enfin on réordonne et on divise par $\eta$. +\end{proof} + +\subsection{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 +$\mathbf{p_t}=(p_{1,t},\ldots,p_{N,t})$. +\item On estime les gains +$\mathbf{\widetilde{g}}=(\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} + +\newpage + +\subsection{Preuve} +On a une information totale sur les gains estimés, donc en notant +$q_{i,t}=w_{i,t}/W_t$ et en appliquant le résultat du théorème \ref{infototale} +: +\begin{equation}\label{fullinfo} +R_T^*(\mathbf{q},\mathbf{\widetilde{g}})\leq\frac{\ln N}{\eta} ++\eta\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}^2 +\end{equation} + +puis en utilisant que $p_{i,t}\geq q_{i,t}(1-\gamma)$ \[ -\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 +\begin{split} +R_T^*(\mathbf{p},\mathbf{\widetilde{g}}) +&\leq\max_{1\leq i\leq N}\widetilde{G}_{i,T} +-(1-\gamma)\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}\\ +&=(1-\gamma)R_n^*(\mathbf{q},\mathbf{\widetilde{g}}) ++\gamma\max_{1\leq i\leq N}\widetilde{G}_{i,T} +\end{split} \] -puis en multipliant par $(1-\gamma)/\eta$ : +et en utilisant \eqref{fullinfo} : \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 +R_T^*(\mathbf{p},\mathbf{\widetilde{g}}) +\leq \frac{\ln N}{\eta} ++\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2 ++\gamma\max_{1\leq i\leq N}\widetilde{G}_{i,T} \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 +\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t} +=\sum_{t=1}^T\sum_{i=1}^N +\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}+\beta\right)=\sum_{t=1}^T g_{I_t,t} ++TN\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} +\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2 +\leq(1+\beta)\sum_{i=1}^N\widetilde{G}_{i,t} +\leq(1+\beta)N\max_{1\leq i\leq N}\widetilde{G}_{i,t} \] -D'où on déduit de \eqref{base} : +D'où on déduit de \eqref{base}, en posant $C=\gamma+\eta(1+\beta)N$: +\[ +R_T(\mathbf{p},\mathbf{g}) ++\max_{1\leq i\leq N}\widetilde{G}_{i,T} +-\max_{1\leq i\leq N}G_{i,T} +\leq \frac{\ln N}{\eta} ++TN\beta ++C\max_{1\leq i\leq N}\widetilde{G}_{i,t} +\] \begin{equation}\label{etape2} -\begin{split} -(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}\\ -&\leq G_T + TN\beta +\eta(1+\beta)N\max_{1\leq i\leq N}\widetilde{G}_{i,T} -\end{split} +R_T(\mathbf{p},\mathbf{g}) +\leq \frac{\ln N}{\eta} ++TN\beta ++\max_{1\leq i\leq N}G_{i,T} ++(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,t} \end{equation} % On souhaite maintenant relier les gains estimés aux gains @@ -154,41 +276,103 @@ D'où on déduit de \eqref{base} : % ,\] % est une suite d'accroissements de martingale. -\paragraph{Étape 3}On souhaite maintenant relier les gains estimés aux gains +On souhaite maintenant relier les gains estimés aux gains réels. On choisit $\beta=\sqrt{\ln(N/\delta)/TN}$, alors avec probabilité supérieure à $1-\delta$ : \[ \max_{1\leq i\leq N} G_{i,T}-\max_{1\leq i\leq N}\widetilde{G}_{i,T} \leq TN\beta = \sqrt{TN\ln\left(\frac{N}{\delta}\right)} \] +d'où en remarquant que $0\leq 1-C\leq 1$ : +\[ +(1-C)\max_{1\leq i\leq N} G_{i,T} ++(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,T} +\leq TN\beta +\] +puis, vu que $\max_{1\leq i\leq N} G_{i,T}\leq T$ : +\[ +\max_{1\leq i\leq N} G_{i,T} ++(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,T} +\leq TN\beta+CT +\] +en injectant cette dernière majoration dans \eqref{etape2}, on obtient +finalement : +\[ +R_T(\mathbf{p},\mathbf{g}) +\leq \frac{\ln N}{\eta} ++2TN\beta+\big(\gamma+\eta(1+\beta)\big)T +\] + +\section{Prédiction dans un univers convexe} +Soit $F$ un convexe compact de $\set{R}^n$. À chaque tour on choisit un +élément $x_t$ dans $F$ tandis que l'adversaire choisit une fonction de perte +convexe $l_t : F\longrightarrow \set{R}^+$. -\paragraph{Étape 4}On repart de \eqref{etape2} : +On définit le regret par rapport à une stratégie fixe : \[ -\left[1-\gamma-\eta(1+\beta)N\right]\max_{1\leq i\leq N}\widetilde{G}_{i,T} -\leq G_T+TN\beta+\frac{1-\gamma}{\eta}\ln N +R_T(\mathbf{x},\mathbf{l})=\sum_{t=1}^T l_t(x_t) - \min_{x\in F}\sum_{t=1}^T +l_t(x) \] -puis en utilisant l'étape 3, en remarquant que $0\leq -1-\gamma-\eta(1+\beta)N\leq 1$ : + +On veut obtenir des bornes sur le regret valables pour toute stratégie de +l'adversaire. + +\subsection{Réduction au cas des pertes linéaires} + +\begin{prop} +Pour toute stratégie convexe $\mathbf{l}$ de l'adversaire, il existe une +stratégie linéaire $\mathbf{l'}$ de l'adversaire telle que : \[ -\left[1-\gamma-\eta(1+\beta)N\right]\left(\max_{1\leq i\leq N}G_{i,T}-TN\beta -\right) -\leq G_T+TN\beta+\frac{1-\gamma}{\eta}\ln N +R_T(\mathbf{x},\mathbf{l})\leq R_T(\mathbf{x},\mathbf{l'}) \] +\end{prop} + +\begin{proof} (A PRECISER) +Il suffit de considérer une suite de sous-gradients des fonctions $l_t$. +\end{proof} + +On peut donc se restreindre à l'étude du regret pour des fonctions de perte +linéaire. Dans ce cas on identifie la fonction de perte est représentée par un +vecteur que l'on nomme également $l_t$. On a donc $l_t(x_t)=l_t\cdot x_t$. + +\subsection{Cas de l'information totale} + +On considère ici qu'à chaque tour on observe le vecteur $l_t$ (et pas seulement +$l_t\cdot x_t$). +On fixe une suite $(\eta_t)_{t\in\set{N}^*}$. On utilise alors la stratégie +suivante : \[ -\left[1-\gamma-\eta(1+\beta)N\right]\max_{1\leq i\leq N}G_{i,T} -\leq G_T+2TN\beta+\frac{1-\gamma}{\eta}\ln N +x_{t+1}=p_F(x_t-\eta_t l_t) \] -On exprime maintenant cette inégalité en termes de pertes : +où $p_F$ est la projection sur le convexe fermé $F$ comme rappelée en +appendice. + +Dans le cas d'une fonction de perte linéaire, le vecteur $l_t$ s'identifie au +gradient de la fonction de perte. La stratégie ci-dessus s'apparente donc à une +descente de gradient gloutonne. + +\begin{thm} +Si toutes les fonctions de pertes sont bornées par la même constante $K$ et que +l'on note $D$ le diamètre du compact $F$, alors on a : \[ -\left[1-\gamma-\eta(1+\beta)N\right]\left(T-\min_{1\leq i\leq N}L_{i,T}\right) -\leq T-L_T+2TN\beta+\frac{1-\gamma}{\eta}\ln N +R_T(\mathbf{x},\mathbf{l}) +\leq\frac{D^2}{2\eta_T} ++\frac{K^2}{2}\sum_{t=1}^T \eta_t \] -d'où : + +En particulier, en prenant $\eta_t=\frac{1}{\sqrt{t}}$, on obtient : \[ -L_T - \min_{1\leq i\leq N}L_{i,T} -\leq\left(\gamma+\eta(1+\beta)N\right)T +2TN\beta+\frac{1-\gamma}{\eta}\ln N +R_T(\mathbf{x},\mathbf{l}) +\leq\frac{D^2}{2}\sqrt{T} ++K^2\left(\sqrt{T}-\frac{1}{2}\right) \] +\end{thm} +\begin{proof} (A PRECISER) majoration du corollaire \ref{projection} + +transformation d'Abel. +\end{proof} + + \section{Appendice} \subsection{Quelques résultats d'analyse réelle} @@ -451,4 +635,53 @@ N\leq\frac{\ln T}{\ln C}+1=\ln T\frac{(1+\ln C/\ln T)}{\ln C} \] \end{proof} +\subsection{Projection sur un convexe fermé} + +On se place dans un espace euclidien $E$. Si $x$ et $y$ sont dans $E$, on note +$x\cdot y$ le produit scalaire entre $x$ et $y$ et $\|x\|$ la norme euclidienne +associée. + +\begin{prop} +Soient $F$ une partie convexe fermée non vide de $E$ et $y\in E$. Alors, il +existe un unique $x\in F$ tel que : +\[ +\|y-x\|=d(y,F)=\inf_{z\in F}\|y-z\| +.\] + +De plus $x$ vérifie la propriété de l'angle obtus : +\[ +\forall z\in F,\quad +(y-x)\cdot(z-x)\leq 0 +\] + +On dit que $x$ est la projection de $y$ sur le convexe $F$, et on note +$x=p_F(y)$. +\end{prop} + +On en déduit notamment que pour tout $z\in F$, $\|y-p_F(y)\|\leq\|y-z\|$. +L'inégalité de l'angle obtus permet d'obtenir une autre inégalité. + +\begin{cor}\label{projection} +Soient $F$ une partie convexe fermée non vide de $E$ et $y\in E$. Alors : +\[ +\forall z\in F,\quad +\|z-p_F(y)\|\leq\|z-y\| +\] +\end{cor} + +\begin{proof} +Soit $z\in F$, on part de l'inégalité de l'angle obtus : +\[ +(y-p_F(y))\cdot(z-p_F(y))\leq 0 +\] +d'où : +\[ +(y-z+z-p_F(y))\cdot(z-p_F(y)) +=\|z-p_F(y)\|^2-(z-y)\cdot(z-p_F(y))\leq 0 +\] +puis en appliquant l'inégalité de Cauchy-Schwarz : +\[ +\|z-p_F(y)\|^2\leq\|z-y\|\|z-p_F(y)\|\qedhere +\] +\end{proof} \end{document} -- cgit v1.2.3-70-g09d2