path: root/rapport.tex

\documentclass[titlepage,11pt]{article}
\usepackage[french]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{calc,amsmath,amssymb,amsthm}
\usepackage{mathrsfs}
\usepackage[hmargin=3.5cm]{geometry}
\usepackage{}
\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}
\DeclareMathOperator*{\argmax}{arg\,max}
\newsavebox{\fmbox}
\newenvironment{encadre}[1]
{
\begin{lrbox}{\fmbox}
\begin{minipage}{\textwidth-3em}
\vspace{0.3\baselineskip}\setlength{\parskip}{0.5em}
}
{
\vspace{\baselineskip}
\end{minipage}\end{lrbox}
\begin{center}
\fbox{\hspace{1em}\usebox{\fmbox}\hspace{1em}}
\end{center}
\vspace{0.5\baselineskip}
}

\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

\theoremstyle{definition}
\newtheorem{prop}{Proposition}[section]
\newtheorem{thm}[prop]{Théorème}
\newtheorem{cor}[prop]{Corollaire}
\newtheorem{lem}[prop]{Lemme}
\newtheorem*{defi}{Définition}

\theoremstyle{remark}
\newtheorem*{rem}{Remarque}

\begin{document}

\maketitle

\section{Introduction : Jeu répété de prévision et regret}

\section{Prévision dans un univers fini}
Dans cette partie on souhaite choisir un action parmi un ensemble fini
$\mathcal{A}$ d'actions. On distingue plusieurs problèmes suivant l'information
dont on dispose  :
\begin{itemize}
\item On parle de \emph{bandit à N bras} si à la fin de chaque tour
on observe uniquement la perte correspondant à l'action choisie. L'appellation
provient du monde des casinos où le terme \emph{bandit manchot} est synonyme de
machine à sous. Un exemple de problème de \emph{bandit à N bras} consiste donc
à jouer sur $N$ machines en même temps, en choisissant une seule machine à
chaque tour. On ne reçoit donc que la perte de la machine sur laquelle on a
joué.
\item Par opposition, on parle de problème à information parfaite si on a accès
à la perte de toutes les actions (même celles que l'on n'a pas choisies) à la
fin de chaque tour.
\end{itemize}

Le comportement de l'environnement influe également sur la nature du problème :
\begin{itemize}
\item On parle d'\emph{environnement stochastique} si les pertes reçues sont
distribuées suivant une loi fixée à l'avance.
\item Si l'environnement choisit de façon déterministe (et sans faire appel à
une randomisation externe) les pertes en fonction des actions passées et de
notre stratégie, il est dit \emph{adversaire déterministe}.
\end{itemize}

\subsection{Bandits stochastiques}
On joue ici sur $N$ machines à sous régies par une famille de lois de
probabilités $(P_1,\ldots,P_N)$. Au tour $t$, le gain donné par la machine $i$
est donc une variable aléatoire $G_{i,t}$ à valeurs dans $[0,1]$. La famille
$(G_{1,t},\ldots,G_{N,t})$ suit la loi $P_1\otimes\ldots\otimes P_N$. Le jeu a
donc la forme suivante :

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Jeu contre des bandits stochastiques}
\end{center}

À chaque tour $t\geq 1$ :
\begin{enumerate}
\item Le joueur choisit un bras $I_t$.
\item Les gains $(G_{1,t},\ldots,G_{N,t})$ sont tirées suivant la loi
$P_1\otimes\ldots\otimes P_N$.
\item Le joueur reçoit (et observe) le gain $G_{I_t,t}$. 
\end{enumerate}
\end{encadre}

La stratégie du joueur est donc une fonction $S$ :
\[
S : \bigsqcup_{t\geq
1}\big(\mathcal{A}\times[0,1]\big)^t\longrightarrow\mathcal{A}
\]
qui donne le bras à jouer en fonction du passé : $I_{t+1} =
S\big((I_1,G_{I_1,1}),\ldots,(I_t,G_{I_t,t})\big)$.

La stratégie est donc déterministe, c'est à dire que le joueur choisit le bras
à jouer à l'instant $t$ de façon déterministe en fonction du passé, sans faire
appel à une randomisation externe.

Si on note $\trib{F}_t$ la tribu engendrée par $(G_{I_1,1},\ldots,G_{I_t,t})$,
on voit facilement que $I_t$ est mesurable par rapport à la tribu
$\trib{F}_{t-1}$.

On note $\mu_i$ l'espérance de $P_i$, et $\mu^*=\max_{1\leq i\leq N} \mu_i$
(plus généralement on notera avec un exposant étoile toute grandeur rattachée à
un bras d'espérance maximale). Enfin on note :
\[
\Delta_i = \mu^*-\mu_i
\]


On souhaite avoir une borne sur le regret défini par :
\[
R_T = \esp{T\mu^* - \sum_{t=1}^T G_{I_t,t}}
=T\mu^* - \sum_{i=1}^N \mu_i \esp{N_i(T)}
=\sum_{i=1}^N \esp{N_i(T)}\Delta_i
\]
où $N_i(T)$ désigne le nombre de fois que le bras $i$ a été joué jusqu'à
l'instant $t$ :
\[
N_i(T)=\sum_{t=1}^T \mathbf{1}_{\{I_t=i\}}
\]

On utilise la stratégie de prévision suivante :

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Stratégie \textsc{ucb} pour les bandits stochastiques}
\end{center}

\textbf{Initialisation :} On joue chaque bras une fois au cours des $N$
premiers tours.

À chaque tour $t> N$ :
\begin{enumerate}
\item On estime $\mu_i$ à l'aide des données passées :
\[
\widehat{\mu}_{i,t-1} = \frac{1}{N_i(t-1)}
\sum_{k=1}^{t-1}G_{I_k,k}\mathbf{1}_{\{I_k=i\}}
\]
\item On choisit un bras $I_t$ qui vérifie :
\[
I_t= \argmax_{1\leq i\leq N}
\left(\widehat{\mu}_{i,t-1}+\sqrt{\frac{2\ln (t-1)}{N_i(t-1)}}\;\right)
\]
\item On observe $G_{I_t,t}$. 
\end{enumerate}
\end{encadre}

\begin{thm}
Si les lois $(P_1,\ldots,P_N)$ des machines sont à support dans $[0,1]$, le
regret au temps T vérifie :
\[
R_T\leq
\left(8\sum_{\mu_i<\mu^*}\frac{1}{\Delta_i}\right) \ln T
+\left(1+\frac{\pi^2}{3}\right)\left(\sum_{i=1}^N \Delta_i\right)
\]
\end{thm}

\begin{proof}On note :
\[
c_{t,s}=\sqrt{\frac{2\ln t}{s}}
\]

Vu la forme du regret, on va majorer $\esp{N_i(T)}$. Dans cette preuve, on
notera $\{A\}$ au lieu de $\mathbf{1}_A$. Pour tout entier $\ell\geq 1$, on a :
\[
\begin{split}
N_i(T)&\leq \ell + \sum_{t=N+1}^T \left\{I_t=i,\ N_i(t-1)\geq l\right\}\\
&\leq\ell + \sum_{t=N+1}^T\left\{\widehat{\mu}^*_{t-1}+c_{t-1,N^*(t-1)}
\leq \widehat{\mu}_{i,t-1}+c_{t-1,N_i(t-1)},\ N_i(t-1)\geq l\right\}\\
&\leq\ell + \sum_{t=N+1}^{T}\sum_{s=1}^{t-1}\sum_{s'=l}^{t-1}
\left\{\bar{X}^*_{s}+c_{t-1,s}
\leq\bar{X}_{i,s'}+c_{t-1,s'}\right\}
\end{split}
\]
où on a noté :
\[
\bar{X}_{i,s}=\frac{1}{s}\sum_{k=1}^s X_{i,k}
\quad\mathrm{et}\quad
\bar{X}^*_{s}=\frac{1}{s}\sum_{k=1}^s X^*_{k}
\]
avec $(X_{i,k})_{k\geq 1}$ une suite iid de variables aléatoires de loi $P_i$
et $(X^*_{k})_{k\geq 1}$ une suite iid de variables aléatoires de loi $P^*$.
Le dernier évènement qui apparaît dans la somme est inclus dans l'union des
trois événements suivants :
\begin{equation}\label{ev1}
\bar{X}^*_{s}\leq\mu^*-c_{t-1,s}
\end{equation}
\begin{equation}\label{ev2}
\bar{X}_{i,s}\geq\mu_i+c_{t-1,s'}
\end{equation}
\begin{equation}\label{ev3}
\mu^*<\mu_i + 2 c_{t-1,s'}
\end{equation}

L'inégalité de Hoeffding permet de majorer les probabilités des événements
\eqref{ev1} et \eqref{ev2} par $\exp(-4\ln t)=t^{-4}$. Enfin, si
$\ell=\lceil (8\ln T)/\Delta_i^2\rceil$, l'événement \eqref{ev3} est de
probabilité nulle. En effet, on a alors :
\[
2c_{t-1,s'}\leq 2\sqrt{\frac{2\Delta_i^2\ln (t-1)}{8\ln T}}\leq\Delta_i =
\mu^*-\mu_i
\]

On a donc :
\[
\esp{N_i(T)}\leq \left\lceil \frac{8\ln T}{\Delta_i^2}\right\rceil
+\sum_{t=1}^{\infty}t^2\frac{2}{t^4}
\]

On multiplie alors par $\Delta_i$ et on somme sur $1\leq i \leq N$ pour avoir
le résultat.
\end{proof}

\subsection{Adversaire déterministe et information totale}
Maintenant, l'environnement se comporte comme un adversaire : il connaît notre
stratégie, observe nos actions passées, et peut donc choisir les pertes de façon
à maximiser notre regret. Face à un tel adversaire, on s'autorise à faire
appel à une randomisation externe dans notre stratégie. Ceci rétablit une
certaine forme d'équilibre car l'adversaire n'a pas de contrôle sur l'aléa. La
prévision prend alors la forme du jeu répété suivant :

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Jeu de prévision contre un adversaire déterministe}
\end{center}
À chaque tour $t\geq 1$ :
\begin{enumerate}
\item Le joueur choisi un loi de probabilité sur $\mathcal{A}$,
$P_t=(p_{1,t},\ldots,p_{N,t})$
\item Simultanément, l'adversaire choisi un vecteur de perte,
$\ell_t=(\ell_{1,t},\ldots,\ell_{N,t})$
\item Le joueur tire $I_t$ suivant la loi $P_t$ et choisit l'action
$I_t$. Il reçoit la perte $\ell_{I_t,t}$.
\item Le joueur et l'adversaire observent le vecteur de perte $\ell_t$ et
l'action $I_t$.
\end{enumerate}
\end{encadre}

On note $\Delta(\mathcal{A})$ l'ensemble des lois de probabilités sur
$\mathcal{A}$ (qui s'injecte canoniquement dans $\mathcal{A}^N$).

La stratégie de prévision du joueur est donc la donnée d'une loi initiale
$P_1$, et d'une fonction $P$ :
\[
P : \bigsqcup_{t\geq 1}\left(\mathcal{A}\times\set{R}^N\right)^{t}
\longrightarrow\Delta(\mathcal{A})
\]
qui donne la loi $P_t$ en fonction des actions et des pertes passées.

La stratégie de l'adversaire est une fonction $E$ :
\[
\ell : \bigsqcup_{t\geq 1}\left(\mathcal{A}\times\set{R}^N\right)^{t}
\longrightarrow\mathcal{A}^N
\]
qui donne le vecteur de perte $\ell_t$ en fonction du passé.

Si on note $\trib{F}_t$ la tribu engendrée par $(I_1,\ldots,I_t)$,
l'information disponible au début du tour $t$ est donc la tribu
$\trib{F}_{t-1}$ et les variables $P_t$ et $\ell_t$ sont
mesurables par rapport à cette tribu.

Le regret jusqu'au temps $T$ de la stratégie $P$ contre la stratégie $\ell$ est
défini par :
\[
R_T(P,\ell)
=\sum_{t=1}^T \ell_{I_t,t}-\min_{1\leq i\leq N}L_{i,T}
=\sum_{t=1}^T \ell_{I_t,t}-\min_{1\leq i\leq N}\sum_{t=1}^T \ell_{i,t}
\]
et le regret espéré :
\[
\bar{R}_T(P,\ell) = \esp{R_T} =
\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\ell_{i,t}
-\min_{1\leq i\leq N}L_{i,T}
\]

Par la suite, on raisonnera plutôt en termes de gains : on pose
$g_{i,t}=1-\ell_{i,t}$, on a donc :
\[
\bar{R}_T(P,\ell) = 
\max_{1\leq i\leq N}\sum_{t=1}^T g_{i,t}
-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}
\]

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Stratégie par poids exponentiels}
\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_t=(p_{1,t},\ldots,p_{N,t})$.
\item On observe les gains $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 g_{i,t})$.
\item On calcule la distribution pour le tour suivant :
\[
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}\label{infototale}
On suppose que les gains sont à valeurs dans $]-\infty, K]$, alors, pour
tout $\eta$ tel
que $\eta K\leq 1$ :
\[
\bar{R}_T \leq\frac{\ln N}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2
\]
\end{thm}

\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 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(g_{i,t})\right)
=\ln\esp{\exp(\eta X)}
\]
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 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}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
.\]

Enfin on réordonne et on divise par $\eta$.
\end{proof}

\subsection{Bandits à $N$ bras}

Contrairement au paragraphe précédent, on observe à la fin de chaque tour
uniquement le gain correspondant à l'action choisie. On ne peut donc pas
utiliser directement la stratégie par poids exponentiels, car on ne peut plus
évaluer la perte cumulée de chaque action. L'idée est donc d'estimer les pertes
qui ne nous sont pas révélées. On utilise pour cela un estimateur biaisé (grâce
au paramètre $\beta$) : 

\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_t=(p_{1,t},\ldots,p_{N,t})$.
\item On estime les gains
$\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-1}/W_{t-1}$ et en appliquant le résultat du théorème
\ref{infototale} : 
\[
\bar{R}_T(Q,\widetilde{g})
=\max_{1\leq i\leq N}\sum_{t=1}^T \widetilde{g}_{i,t}
-\sum_{t=1}^T\sum_{i=1}^N q_{i,t}g_{i,t}
\leq\frac{\ln N}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}^2
\]

puis en multipliant par $1-\gamma$ et en remarquant que 
$p_{i,t}\geq q_{i,t}(1-\gamma)$ :
\[
(1-\gamma)\max_{1\leq i\leq N}\sum_{t=1}^T \widetilde{g}_{i,t}
-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
\leq\frac{\ln N}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
\]
d'où en réordonnant et en utilisant la définition du regret :
\begin{equation}\label{base}
\bar{R}_T(P,\widetilde{g})
=\max_{1\leq i\leq N}\sum_{t=1}^T \widetilde{g}_{i,t}
-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
\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 :
\begin{equation}\label{estimation}
\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
\end{equation}
et :
\begin{equation}\label{estimation2}
\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
\leq\sum_{i=1}^N\sum_{t=1}^T\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}
\leq(1+\beta)N\max_{1\leq i\leq N}\widetilde{G}_{i,t}
\end{equation}

En utilisant \eqref{estimation}, on a :
\[
\bar{R}_T(P,\widetilde{g})
=\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-\sum_{t=1}^T g_{I_t,t} - TN\beta
=R_T(P,g)
+\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-\max_{1\leq i\leq N}G_{i,T}
-TN\beta
\]
On injecte dans\eqref{base} et on utilise la majoration \eqref{estimation2} :
\[
R_T(P,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}
+\big(\gamma+\eta(1+\beta) N\big)\max_{1\leq i\leq N}\widetilde{G}_{i,t}
+TN\beta
\]
\[
\begin{split}
R_T(P,g)
&\leq \frac{\ln N}{\eta}
+\big(1-\gamma-\eta(1+\beta) N\big)\left(\max_{1\leq i\leq N}G_{i,T}
-\max_{1\leq i\leq N}\widetilde{G}_{i,t}\right)\\
&\qquad+\big(\gamma+\eta(1+\beta) N\big)\max_{1\leq i\leq N}G_{i,T}+TN\beta
\end{split}
\]

puis vu que $1-\gamma-\eta(1+\beta) N\leq 1$ et $\max_{1\leq i\leq N}
G_{i,T}\leq T$

\begin{equation}\label{etape2}
R_T(P,g)
\leq \frac{\ln N}{\eta}
+\left(\max_{1\leq i\leq N}G_{i,T}
-\max_{1\leq i\leq N}\widetilde{G}_{i,t}\right)
+\big(\gamma+\eta(1+\beta)N\big)T+TN\beta
\end{equation}

Il nous reste à majorer l'écart entre les gains et les gains estimés. On
souhaite appliquer le corollaire \ref{megabernstein} pour la suite
d'accroissement de martingale $(X_{i,t})_{1\leq t\leq T}$ définie par :
\[
X_{i,t}=g_{i,t}-\widetilde{g}_{i,t}+\frac{\beta}{p_{i,t}}
= g_{i,t}\left(1-\frac{\mathbf{1}_{\{I_t=i\}}}{p_{i,t}}\right)
\]
Cette suite est clairement une suite d'accroissements de martingale car on a
retranché le terme de biais. La variance conditionnelle vaut :
\[
\begin{split}
\mathbb{E}_t[X_{i,t}^2]=\espc{X_{i,t}^2}{\trib{F}_{t-1}}
&=g_{i,t}^2\,\mathbb{E}_t\Bigg[\bigg(1-\frac{\mathbf{1}_{\{I_t=i\}}}{p_{i,t}}
\bigg)^2\Bigg]\\
&=g_{i,t}^2\left(\frac{1}{p_{i,t}}-1\right)
\end{split}
\]
On applique le corollaire \ref{megabernstein} avec $K=1$ et
$\sigma_T^2=NT/\gamma$. On a donc avec probabilité supérieure à $1-\delta/N$ :
\[
G_{i,T}-\widetilde{G}_{i,T} + \beta\sum_{t=1}^T\frac{1}{p_{i,t}}
\leq \sqrt{3\sum_{t=1}^T\frac{1}{p_{i,t}}\ln\left(\frac{N\ln
(NT/\gamma)}{\delta/4}\right)}
+\frac{2}{3}\ln\left(\frac{N\ln(NT/\gamma)}{\delta/4}\right)
\]
puis en majorant l'intersection des évènements précédents, on a avec
probabilité supérieure à $1-\delta/N$ :
\[
a
\]

en injectant cette dernière majoration dans \eqref{etape2}, on obtient
finalement :
\[
R_T(P,g)
\leq \frac{\ln N}{\eta}
+\beta T(N-1)+\big(\gamma+\eta(1+\beta)\big)T
+\sqrt{2\frac{NT}{\gamma}\ln\left(\frac{1}{\delta}\right)}
+\frac{2}{3}\ln\left(\frac{1}{\delta}\right)
\]

\section{Prévision dans un univers convexe}

Soit $C$ un convexe compact de $\set{R}^n$. On joue au même jeu que
précédemment, mais au lieu de choisir une action parmi un ensemble fini, on
choisit un élément de $C$. L'environnement ne choisit donc pas un vecteur de
perte, mais une fonction de perte définie sur $C$ tout entier.

On note $\Pi_C$ la projection sur le convexe $C$ définie comme au paragraphe
\ref{projection}.


\subsection{Cas de l'information parfaite}

Ici, le joueur et l'environnement choisissent leurs actions de façon
déterministe
en fonction du passé :

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Jeu à information parfaite dans un univers convexe}
\end{center}
À chaque tour $t\geq 1$ :
\begin{itemize}
\item Le joueur choisit un vecteur $x_t\in C$.
\item Simultanément, l'adversaire choisit une fonction de perte convexe $\ell_t
: C\to\set{R}^+$.
\item Le joueur et l'environnement observent la fonction $\ell_t$ et reçoit la
perte
$\ell_t(x_t)$.
\end{itemize}
\end{encadre}

Plus précisément, notons $\mathscr{C}$ l'ensemble des fonctions de $C$ dans
$\set{R}^+$. Le passé avant $t$, noté $H_t$, est une partie de $(C\times
\mathscr{C})^{t-1}$ :
\[
H_t = \big((x_1,\ell_1),\ldots,(x_{t-1},\ell_{t-1})\big)
\]

La stratégie du joueur est donc une fonction $S$ : 
\[
S : \bigsqcup_{t\geq 1}(C\times\mathscr{C})^t 
\longrightarrow C
\]
et on a $x_t = S(H_t)$.

De même, la stratégie de l'environnement est une fonction $E$ :
\[
E : \bigsqcup_{t\geq 1}(C\times\mathscr{C})^t 
\longrightarrow \mathscr{C}
\]
avec $\ell_t = E(H_t)$.

On définit alors le regret pour la stratégie $S$ contre la stratégie $E$ par :
\[
R_T(S,E)=\sum_{t=1}^T \ell_t(x_t)-\min_{x\in C}\sum_{t=1}^T\ell_t(x)
=\max_{x\in C}\left(\sum_{t=1}^T \ell_t(x_t)-\ell_t(x)\right)
\]

\begin{prop}
Soit $(\ell_1,\ldots,\ell_T)$ une famille de fonctions de pertes convexes et
différentiables, alors on a :
\[
R_T\leq
\sum_{t=1}^T \nabla \ell_t(x_t)\cdot x_t-\min_{x\in C}\sum_{t=1}^T
\nabla \ell_t(x_t)\cdot x
\]
\end{prop}

\begin{proof}
Soit $t\in\{1,\ldots,T\}$, $\ell_t$ est au-dessus de ses tangentes, d'où :
\[
\forall x\in C,\quad
\ell_t(x_t)-\ell_t(x)
\leq \nabla \ell_t(x_t)\cdot(x_t-x)
\]

En sommant sur $t$, on obtient :
\[
\forall x\in C,\quad
\sum_{t=1}^T \ell_t(x_t)-\ell_t(x)
\leq \sum_{t=1}^T \ell'_t\cdot(x_t- x)
\]

On prend alors le maximum sur $x\in C$ pour obtenir le résultat.
\end{proof}

Le terme de droite de l'inégalité de la proposition précédente est un terme de
regret pour la suite de fonctions de perte $(\nabla \ell_t(x_t)$. À partir
d'une borne sur le regret valable pour toutes fonctions de perte linéaires, on
peut donc obtenir une borne valable pour des fonctions de perte convexes.

On supposera donc par la suite que les fonctions de pertes sont linéaires, on
peut donc les assimiler au produit scalaire par un vecteur de $\set{R}^N$, que
l'on notera également $\ell_t$ par abus.

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Descente de gradient}
\end{center}

\textbf{Donnée :} une suite décroissante $(\eta_t)_{t\in\set{N}^*}$ de réels
strictement positifs.

\textbf{Initialisation :} On joue $x_1$ n'importe où dans $C$.

À chaque tour $t\geq 2$ :
\begin{itemize}
\item On calcule $y_t = x_{t-1}-\eta_{t-1} \ell_{t-1}$
\item On joue $x_t = \Pi_C(y_t)$
\end{itemize}
\end{encadre}

\begin{thm}
On note $D$ le diamètre de $C$ pour la norme euclidienne. On suppose que les
vecteurs de perte $\ell_t$ sont bornés par une constante $K$ pour cette même
norme. Alors, pour la stratégie de descente de gradient :
\[
R_T=\sum_{t=1}^T\ell_t\cdot x_t - \min_{x\in C}\sum_{t=1}^T\ell_t\cdot x
\leq\frac{D^2}{2\eta_T}
+\frac{K^2}{2}\sum_{t=1}^T \eta_t
\]

En particulier, en prenant $\eta_t=\frac{1}{\sqrt{t}}$, on obtient :
\[
R_T
\leq\frac{D^2}{2}\sqrt{T}
+K^2\left(\sqrt{T}-\frac{1}{2}\right)
\]
\end{thm}

\begin{proof}
Soit $x\in C$, d'après l'inégalité \eqref{inegprojection}, on a :
\[
\forall t\geq 0,\quad \| x_{t+1} -x\|^2= \| \Pi_C(y_{t+1}) -x\|^2
\leq \|y_{t+1} -x\|^2
\]
D'où :
\[
\begin{split}
\| x_{t+1} -x\|^2
&\leq \| x_t-\eta_t\ell_t -x\|^2\\
&=\| x_t -x\|^2-2\eta_t\ell_t\cdot(x_t-x)+\eta_t^2\|\ell_t\|^2
\end{split}
\]
Puis en réordonnant et en majorant $\|\ell_t\|$ par $K$ :
\[
\ell_t\cdot(x_t-x)
\leq \frac{1}{2\eta_t}\big(\| x_t -x\|^2-\| x_{t+1} -x\|^2\big)
+\frac{\eta_t}{2}K^2
\]

On somme pour $t\in\{1,\ldots,T\}$ :
\[
\sum_{t=1}^T \ell_t\cdot(x_t-x)
\leq \frac{1}{2\eta_1}\| x_1 -x\|^2 
+\frac{1}{2}
\sum_{t=2}^T\left(\frac{1}{\eta_t}-\frac{1}{\eta_{t-1}}\right)\| x_t-x\|^2
-\frac{1}{2\eta_T}\| x_{T+1} -x\|^2 
+\frac{K^2}{2}\sum_{t=1}^T \eta_t
\]

En majorant $\| x_t-x\|^2$ par $D^2$, on fait apparaître une somme
télescopique :
\[
 \sum_{t=1}^T \ell_t\cdot(x_t-x)
\leq \frac{D^2}{2\eta_T}+\frac{K^2}{2}\sum_{t=1}^T \eta_t
\]

On obtient la première inégalité du théorème en prenant le maximum sur $x\in
C$. Pour la seconde inégalité, il suffit de majorer $\sum_{t=1}^T 1/\sqrt{t}$ :
\[
\sum_{t=1}^T \frac{1}{\sqrt{t}}
\leq 1+\int_{1}^T \frac{\mathrm{d}t}{\sqrt t}
=2\sqrt T -1
\qedhere\]
\end{proof}

Dans le théorème précédent, le choix du $\eta_t$ est arbitraire. Le choix
optimal pour $\eta_t$ dépend bien sûr des constantes $K$ et $D$. Cependant,
si le diamètre $D$ est généralement connu, ce n'est pas toujours le cas de
$K$, la borne des fonctions de perte. Pour un bon choix des paramètres $\eta_t$,
on peut toutefois avoir une borne satisfaisante pour le regret :

\begin{thm}
Avec les mêmes hypothèses que précédemment, posons :
\[
V_t = \sum_{k=1}^t \|l_t\|^2
\]
alors, pour le choix $\eta_t=D/\sqrt{V_{t-1}}$ on a :
\[
R_T\leq \sqrt{6} DK\sqrt{T} + \ldots
\]
\end{thm}

\begin{proof}
$\ldots$ est une constante dépendant de $K$. FINIR LE CALCUL
\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\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 $(S_T)$ défini par :
\[
\forall T \in \set{N}^*,\quad S_T=\sum_{t=1}^{T}X_t
\]
est une martingale par rapport à la filtration $(\trib{F}_T)$.
\end{defi}

On notera également :
\[
V_T=\sum_{t=1}^T
\espc{X_t^2}{\trib{F}_{t-1}}
\]

\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 conditionnelle :
\[
\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'il existe $K>0$ tel que :
\[
\forall t \in \{1,\ldots,T\},\quad X_t\leq K,
\]
et $\sigma^2_T\geq 0$ tel que $V_T\leq \sigma^2_T$ presque sûrement, 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_T^2+\frac{2}{3}K\varepsilon}\right)
\]
\end{prop}

\begin{proof} Par homogénéité, on se ramène au 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_T^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_T^2(e^\eta-\eta-1)-\eta\varepsilon\big)\esp{M_1}\\
&\leq \exp\big(\sigma_T^2(e^\eta-\eta-1)-\eta\varepsilon\big)
\end{split}
\]

La borne de droite est minimale pour
$\eta=\ln\left(1+\frac{\varepsilon}{\sigma_T^2}\right)$ et donne la majoration
: 
\[
\prob{\max_{1\leq t\leq T}S_t>\varepsilon} 
\leq \exp\left(-\sigma_T^2 h\left(\frac{\varepsilon}{\sigma_T^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}\label{corbernstein}
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
\sqrt{2\sigma_T^2\ln\left(\frac{1}{\delta}\right)}
+\frac{2K}{3}\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_T^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}\label{megabernstein}
Soit $(X_1,\ldots,X_T)$ une suite d'accroissements de
martingale par rapport à la filtration $(\trib{F}_t)$. Supposons que
presque sûrement on ait : $1\leq V_T\leq \sigma_T^2$ avec $\sigma_T^2\geq 3$ et
qu'il existe $K>0$
tel que :
\[
\forall t \in \{1,\ldots,T\},\quad X_t\leq K,
\]
alors, avec probabilité supérieure à $1-\delta$ :
\[
\forall C\in\left]1 ;+\infty\right[,\quad
S_T\leq
\sqrt{2CV_T\ln\left(\frac{\ln \sigma_T^2}{\delta}\frac{(1+\ln C)}{\ln C}\right)}
+\frac{2K}{3}\ln\left(\frac{\ln \sigma_T^2}{\delta}\frac{(1+\ln C)}{\ln
C}\right)
.\]

En particulier, en choisissant $C=3/2$, on obtient :
\[
S_T\leq
\sqrt{3V_T\ln\left(\frac{\ln \sigma_T^2}{\delta/4}\right)}
+\frac{2K}{3}\ln\left(\frac{\ln \sigma_T^2}{\delta/4}\right)
.\]
\end{cor}

\begin{proof}
Posons $N=\lceil\ln \sigma_T^2/\ln C\rceil$
D'après le corollaire précédent, pour tout $r\in\{1,\ldots,N\}$ :
\[
\prob{S_T\geq
\sqrt{2C^r\ln\left(\frac{N}{\delta}\right)}
+\frac{2K}{3}\ln\left(\frac{N}{\delta}\right)
\ \mathrm{et}\ V_T\leq C^r}\leq\frac{\delta}{N}
\]

D'où :
\[
\prob{S_T\geq
\sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}
+\frac{2K}{3}\ln\left(\frac{N}{\delta}\right)
\ \mathrm{et}\ C^{r-1}\leq V_T\leq C^r}\leq\frac{\delta}{N}
\]

Or, vu que $1\leq V_T\leq \sigma_T^2\leq C^N$, en sommant l'inégalité
précédente pour
$r\in\{1,\ldots,N\}$, on obtient :
\[
\prob{S_T\geq
\sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}
+\frac{2K}{3}\ln\left(\frac{N}{\delta}\right)
\leq\delta}
.
\]

On conclut en remarquant que :
\[
N\leq\frac{\ln \sigma_T^2}{\ln C}+1=\ln \sigma_T^2\frac{(1+\ln C/\ln
\sigma_T^2)}{\ln C}
\leq \ln \sigma_T^2\frac{(1+\ln C)}{\ln C}\qedhere
\]
\end{proof}

\subsection{Projection sur un convexe fermé}
\label{projection}

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=\Pi_F(y)$.
\end{prop}

On en déduit notamment que pour tout $z\in F$, $\|y-\Pi_F(y)\|\leq\|y-z\|$.
L'inégalité de l'angle obtus permet d'obtenir une autre inégalité.

\begin{cor}\label{inegprojection}
Soient $F$ une partie convexe fermée non vide de $E$ et $y\in E$. Alors :
\[
\forall z\in F,\quad
\|z-\Pi_F(y)\|\leq\|z-y\|
\]
\end{cor}

\begin{proof}
Soit $z\in F$, on part de l'inégalité de l'angle obtus :
\[
\big(y-\Pi_F(y)\big)\cdot\big(z-\Pi_F(y)\big)\leq 0
\]
d'où :
\[
\big(y-z+z-\Pi_F(y)\big)\cdot\big(z-\Pi_F(y)\big)
=\|z-\Pi_F(y)\|^2-(z-y)\cdot\big(z-\Pi_F(y)\big)\leq 0
\]
puis en appliquant l'inégalité de Cauchy-Schwarz :
\[
\|z-\Pi_F(y)\|^2\leq\|z-y\|\|z-\Pi_F(y)\|\qedhere
\]
\end{proof}

\end{document}