\documentclass[titlepage,11pt,twoside]{article}
\usepackage[french]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{calc,amsmath,amssymb,amsthm}
\usepackage{mathrsfs}
\usepackage[hmargin=3.45cm,vmargin=3cm]{geometry}
\setlength{\headheight}{13.6pt}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}
\fancyhead[LE,RO]{\thepage}
\fancyhead[RE]{Prédiction de suites individuelles}
\fancyhead[LO]{\leftmark}
\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\sectionmark}[1]{\markboth{#1}{}}

\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}
\newcommand{\bs}{\boldsymbol}
\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

\tableofcontents
\newpage

\section{Introduction}
On s'intéresse ici à la prédiction séquentielle. Dans ce problème, une suite $(y_t)_{t\in\set{N}^*}$ est dévoilée progressivement. À chaque instant discret $t\in\set{N}^*$, on fait une prévision $x_t$, puis celle-ci est confrontée à la valeur réelle $y_t$ qui nous est révélée. 

La qualité de notre prévision est pénalisée par une fonction de perte $\ell$,
c'est à dire que l'on reçoit à chaque tour la perte\footnote{On peut aussi
adopter un point de vue plus optimiste
et considérer que l'on reçoit à chaque tour le gain $g(x_t,y_t)$ pour une
certaine fonction de gain $g$. Mais quitte à considérer des fonctions de perte
pouvant prendre des valeurs positives ou négatives, le problème reste le
même.} $\ell(x_t,y_t)$. 

On ne fait aucune hypothèse sur l'origine de la suite $(y_t)$ : elle peut être générée suivant un processus aléatoire indépendant, tout comme elle peut être choisie par un adversaire qui cherche à nous nuire. Il est donc intéressant d'adopter le modèle d'un jeu entre deux entités : la personne qui fait les prévisions, que l'on appellera simplement \emph{le joueur} ; et l'origine de la suite $(y_t)$, \emph{l'environnement}.

Une fois la valeur de $y_t$ fixée par l'environnement, la seule donnée qui nous intéresse est la fonction partielle $\ell(\cdot,y_t)$. On peut donc considérer indifféremment que l'environnement choisit à chaque tour une valeur $y_t$ ou une fonction de perte $\ell_t$. Le jeu prend donc la forme suivante :

\begin{encadre}{\textwidth}
À chaque tour $t$ : 
\begin{enumerate}
\item Le joueur choisit un élément $x_t$ d'un ensemble $\mathcal{A}$.
\item Indépendamment l'environnement choisit une fonction de perte $\ell_t$ définie sur $\mathcal{A}$.
\item Le joueur observe l'information $I_t$.
\end{enumerate}
\end{encadre}

On distingue principalement deux problèmes suivant la nature de l'information
$I_t$ révélée : 
\begin{itemize}
\item Si on observe la fonction de perte $\ell_t$, on parlera de problème à information parfaite : on connaît notre perte, mais aussi la perte que l'on aurait eue en faisant un autre choix.
\item Si on observe seulement notre perte $\ell_t(x_t)$, on parlera de problème de type \emph{bandit}. Quand le cardinal de $\mathcal{A}$ est fini et égal à $N$, on parle du problème de \emph{bandits à N bras}. 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 à sous, en choisissant à chaque tour une machine à sous à actionner. Dans ce cas, on observe uniquement la perte de la machine choisie.
\end{itemize}

L'ensemble $\mathcal{A}$ est appelé l'ensemble de décision. Quand celui-ci est
de cardinal fini, choisir un élément de $\mathcal{A}$ revient à choisir une
action parmi une nombre fini de possibilités. La fonction de perte $\ell_t$
définie sur $\mathcal{A}$ devient alors un \emph{vecteur de perte} que l'on note
$\bs{\ell}_t$ : on ordonne arbitrairement $\mathcal{A}$ de cardinal $K$, et
l'environnement choisi pour chaque action la perte correspondante, on a alors
$\bs{\ell}_t= (\ell_ {1,t},\ldots,\ell_{K,t})$.

Par la suite, toutes les fonctions de perte seront bornées par une constante
$B$ et le but du joueur est de minimiser sa perte. Cependant, si l'environnement
choisit à chaque tour la fonction de perte constante égale à $B$, le joueur n'a
plus aucun choix stratégique à faire. Il apparaît alors que la quantité
significative est le \emph{regret cumulé}. Celui-ci mesure l'écart entre
deux quantités
\begin{enumerate}
\item la perte accumulée par le joueur jusqu'à l'instant $T$ : c'est
tout simplement la somme des pertes obtenues à chaque tour pour l'action
choisie
\item la perte accumulée d'une stratégie considérée comme « optimale ». Pour un
ensemble de décision fini ou infini, cette stratégie optimale est simplement le
choix constant de l'action de plus faible perte cumulée jusqu'à l'instant $T$.
Dans le cas de la prévision avec experts (section \ref{sec:banditsexp}), on
étend la notion de perte pour les experts, et la stratégie optimale est l'expert
de plus faible perte.
\end{enumerate}

Comme on le voit, la notion de regret varie un peu suivant le problème et
suivant ce que l'on souhaite mesurer. Elle sera précisée à chaque fois dans les
différents cadres étudiés, on peut toutefois retenir la forme générale suivante
pour le regret jusqu'à l'instant $T$, que l'on note $R_T$ :
\[
\begin{split}
R_T &= \text{Perte accumulée par le joueur jusqu'à l'instant T}\\
&\qquad- \text{Perte accumulée d'une stratégie considérée comme optimale}
\end{split}
\]


La borne sur les fonctions de perte nous assure que $R_T=O(T)$. On cherche des bornes qui assurent que le regret rapporté au nombre de tour tend vers 0, c'est à dire $R_T=o(T)$. Pour cela, on utilise une stratégie qui dépend de l'ensemble $\mathcal{A}$, de l'information révélée, et du comportement de l'environnement. Ces stratégies seront définies et étudiées dans les sections suivantes.

\newpage

\section{Prévision dans un univers fini}

Dans cette partie l'ensemble de décision $\mathcal{A}$ est de cardinal fini égal
à $K$. Ceci permet de modéliser les jeux où le joueur doit choisir à chaque
tour parmi un nombre fini d'actions. On étudie tout d'abord le problème des
\emph{bandits stochastiques} pour lequel les gains de chaque action sont choisis
suivant une loi de probabilité fixée à l'avance et inconnue du joueur. Le
regret est alors défini par rapport à l'action de plus grande espérance
de gain, et on cherche à obtenir une borne sur l'espérance du regret.

On étudie ensuite le problème des \emph{bandits déterministes}, pour lequel on
ne fait pas d'hypothèses sur l'origine de la fonction de perte. On introduit
alors la notion de \emph{prédiction randomisée} : on choisit à chaque tour
une loi de probabilité sur l'ensemble des actions et l'action à jouer est tirée
aléatoirement suivant cette loi. Suivant que l'on est aidé ou non par des
\emph{experts} (sections \ref{sec:bandits} et \ref{sec:banditsexp}), le regret
est défini ou bien par rapport à l'action la plus performante ou l'expert le
plus performant. On obtient dans les deux cas une borne sur le regret
valable en grande probabilité. L'étude du problème des \emph{bandits
déterministes} est précédée par l'étude du cas de l'information parfaite. 

\subsection{Bandits stochastiques}

La référence principale pour ce problème est \cite{bandsto} qui contient la stratégie $\textsc{ucb}$ étudiée ci-dessous. Celle-ci assure un regret en $O(\ln T)$.

Considérons pour fixer les idées que l'on joue sur $K$ machines à sous,
numérotées $\mathbf\{1,\ldots,K\}$. Conformément au monde des casinos, on
raisonnera en terme de gains. Ceux-ci sont régis par une famille de lois de
probabilité $(P_1,\ldots,P_K)$, qui nous est bien sûr inconnue.  La fonction de
gain $G_t$ est donc une variable aléatoire à valeur dans $[0,1]^K$, que l'on
représente par une famille de variable aléatoire $(G_{1,t},\ldots,G_{K,t})$ :
$G_{i,t}$, la i-ème composante de $G_t$ est le gain de la machine $i$ au tour
$t$. C'est une variable aléatoire de loi $P_i$. On suppose que les machines sont
indépendantes, c'est à dire que $G_t$ suit la loi $P_1\otimes\ldots\otimes P_K$.

On résume ci-dessous le déroulement du jeu.

\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_{K,t})$ sont tirées suivant la loi
$P_1\otimes\ldots\otimes P_K$.
\item Le joueur reçoit (et observe) le gain $G_{I_t,t}$. 
\end{enumerate}
\end{encadre}

La stratégie du joueur est donc la donnée d'un bras initial est d'une 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 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 montre par récurrence que $I_t$ est mesurable par rapport à la tribu
$\trib{F}_{t-1}$.

On note $\mu_i$ l'espérance de $P_i$. On choisit $j^*$ l'indice d'un bras
d'espérance maximale, et on note $\mu^*=\mu_{j^*}$, on a donc :
\[\mu^*=\mu_{j^*}=\max_{1\leq i\leq K} \mu_i\]
Plus généralement on notera avec un exposant étoile toute grandeur rattachée au
bras $j^*$ d'espérance maximale. Enfin on note :
\[
\Delta_i = \mu^*-\mu_i
\]

On défini le regret par rapport à la machine la plus performante :
\[
R_T=\sum_{t=1}^T G_{j^*,t}-\sum_{t=1}^T G_{I_t,t}
\]
et on souhaite obtenir une borne sur l'espérance du regret :
\[
\esp{R_T}=\sum_{t=1}^T \esp{G_{j^*,t}}-\sum_{t=1}^T
\esp{G_{I_t,t}}=T\mu^*-\sum_{t=1}^T \esp{G_{I_t,t}}
\]
on peut réordonner la dernière somme en fonction des valeurs prises par $I_t$ :
si $I_t=i$, alors $\esp{G_{I_t,t}}=\mu_i$. Notons alors $N_i(T)$ 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\}}
,\]
l'espérance du regret devient alors :
\[
\esp{R_T}=T\mu^*-\sum_{i=1}^K \mu_i \esp{N_i(T)}
\]
puis en utilisant que $\sum_{i=1}^T\esp{N_i(T)}=T$ et on obtient finalement
l'expression suivante pour l'espérance du regret :
\begin{equation}\label{eq:regretsto}
 \esp{R_T}=\sum_{i=1}^K \Delta_i \esp{N_i(T)}
\end{equation}

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 $K$
premiers tours.

À chaque tour $t> K$ :
\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\in \argmax_{1\leq i\leq K}
\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_K)$ des machines sont à support dans $[0,1]$, alors
pour la stratégie UCB, on a :
\[
\esp{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}^K \Delta_i\right)
\]
\end{thm}

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

Vu la forme du regret obtenu en \eqref{eq:regretsto}, on va majorer
$\esp{N_i(T)}$. Dans cette preuve, on
notera $\{A\}$ au lieu de $\mathbf{1}_A$. Soit $\ell$ un entier avec
$\ell\geq 1$. Notons $T_0$ l'instant tel que $N_i(T_0)=\ell$, puisqu'on
commence par jouer chaque bras une fois, on a $T_0\geq K$. En découpant le
temps par rapport à $T_0$, on obtient :

\[
\begin{split}
N_i(T)&\leq N_i(T_0)
+\sum_{t=T_0+1}^T\left\{I_t=i,\ N_i(t-1)\geq\ell\right\}\\
&\leq \ell
+\sum_{t=K+1}^T \left\{I_t=i,\ N_i(t-1)\geq \ell\right\}\\
&\leq\ell
+\sum_{t=K+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 \ell\right\}\\
\end{split}
\]
Puis en découpant suivant les valeurs possibles de $N_i(t-1)$ et $N^*(t-1)$, on
obtient:
\[N_i(T)\leq\ell
+\sum_{t=K+1}^{T}\sum_{s=1}^{t-1}\sum_{s'=\ell}^{t-1}
\left\{\bar{X}^*_{s}+c_{t-1,s}
\leq\bar{X}_{i,s'}+c_{t-1,s'}\right\}
\]
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\big(-4\ln(t-1)\big)=(t-1)^{-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
\]

En utilisant les différentes majoration précédentes et en utilisant la valeur
de $\ell$ ci-dessus :
\[
\begin{split}
\esp{N_i(T)}
&\leq \left\lceil \frac{8\ln T}{\Delta_i^2}\right\rceil
+\sum_{t=2}^{\infty}\sum_{s=1}^{t-1}\sum_{s'=1}^{t-1}\frac{2}{(t-1)^4}\\
&\leq \left\lceil \frac{8\ln T}{\Delta_i^2}\right\rceil
+\sum_{t=2}^{\infty}\frac{2}{(t-1)^2}
=\leq \left\lceil \frac{8\ln T}{\Delta_i^2}\right\rceil+\frac{\pi^2}{3}
\end{split}
\]

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

\begin{rem}
L'inégalité de Bernstein peut sembler plus adaptée pour majorer des
probabilités d'événements du type $\left\{\widehat{\mu}_{i,t-1}\geq\mu_i
+c_{t-1,N_i(t-1)}\right\}$ et ainsi éviter le découpage suivant les valeurs de
$N_i(t-1)$ effectué dans la preuve précédente. Par exemple réécrivons :
\[
\widehat{\mu}_{i,t-1} -\mu_i
=\frac{1}{N_i(t-1)}\sum_{k=1}^{t-1}\big(G_{i,k}-\mu_i\big)\mathbf{1}_{I_k=i}
\]
d'où :
\[
\prob{\widehat{\mu}_{i,t-1} -\mu_i\geq c_{t-1,N_i(t-1)}}
=\prob{\sum_{k=1}^{t-1}\big(G_{i,k}-\mu_i\big)\mathbf{1}_{I_k=i}
\geq\sqrt{2\ln(t-1)N_i(t-1)}}
\]

Si on note $X_k=\big(G_{i,k}-\mu_i\big)\mathbf{1}_{I_k=i}$, $X_k$ est une suite
d'accroissement de martingale pour la filtration $\trib{F}_t$ et on a avec les
notations de la section \ref{inegmart} : $V_{t-1}=\sigma_i^2N_i(t-1)$ où
$\sigma_i^2$ représente la variance du $i$-ième bras. La probabilité à majorer
s'écrit donc :
\[
\prob{\sum_{k=1}^{t-1}X_k\geq\sqrt{2\frac{\ln(t-1)}{\sigma_i^2}V_{t-1}}}
\]
On sait que $\ell\sigma_i^2\leq V_{t-1}\leq \sigma_i^2 (t-1)$, donc on peut
appliquer le lemme \ref{megabernstein} :
\[
\prob{\frac{S_{t-1}}{\sqrt{V_{t-1}}}
\geq \sqrt{3\ln\left(\frac{\ln \big((t-1)/\ell\big)}{\delta/4}\right)}
+\frac{2}{3\sqrt{V_{t-1}}}\ln\left(\frac{\ln
\big((t-1)/\ell\big)}{\delta/4}\right)}
\leq \delta
\]
d'où :
\[
\prob{\frac{S_{t-1}}{\sqrt{V_{t-1}}}
\geq \sqrt{3\ln\left(\frac{\ln \big((t-1)/\ell\big)}{\delta/4}\right)}
+\frac{2}{3\sqrt{\sigma_i^2 \ell}}\ln\left(\frac{\ln
\big((t-1)/\ell\big)}{\delta/4}\right)}
\leq \delta
\]
Vu l'ordre de grandeur de $\ell$, le premier terme de la borne ci-dessus est le
plus grand, d'où :
\[
\prob{\frac{S_{t-1}}{\sqrt{V_{t-1}}}
\geq 3\sqrt{\ln\left(\frac{\ln \big((t-1)/\ell\big)}{\delta/4}\right)}}
\leq \delta
\]
On voit qu'il faut alors prendre $\delta$ de l'ordre de :
\[
\frac{\ln \big((t-1)/l\big)}{t-1}=\frac{\ln \big((t-1)/\ln T\big)}{t-1}
\]
Cependant en sommant de $1$ à $T$, on obtient une borne supérieure à $\ln T$.
Il semble que ce qui empêche ici d'appliquer l'inégalité de Bernstein est que
le contrôle que nous avons sur la variance $V_T$ c'est à dire sur $N_i(T)$
n'est pas assez précis pour autoriser un traitement général
\end{rem}

\subsection{Adversaire déterministe et information parfaite}\label{fullinfo}

On ne fait plus maintenant d'hypothèse sur l'origine des pertes. Elles peuvent
par exemple être choisies de façon déterministe par l'environnement de façon à
maximiser notre regret. Il peut par exemple, en observant les tours passés,
deviner et s'adapter à notre stratégie. Face à un tel adversaire, on s'autorise
à faire appel à une randomisation externe pour choisir l'action à jouer : au
lieu de choisir directement l'action à jouer, celle-ci est tirée aléatoirement
suivant une loi que l'on choisit au début du tour. Même en observant la loi
choisie, le simple fait pour l'adversaire de n'avoir aucun contrôle sur l'issu
du tirage aléatoire, rétablit une certaine forme d'équilibre et permet
d'obtenir avec une bonne stratégie une borne satisfaisante sur le regret.

On résume ci-dessus le déroulement du jeu :

\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 choisit un loi de probabilité sur $\mathcal{A}$,
$\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$
\item Simultanément, l'adversaire choisit un vecteur de perte,
$\bs{\ell}_t=(\ell_{1,t},\ldots,\ell_{K,t})$
\item Le joueur tire $I_t$ suivant la loi $\bs{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 $\bs{\ell}_t$ et
l'action $I_t$.
\end{enumerate}
\end{encadre}

Le joueur choisit une loi de probabilité sur $\mathcal{A}$, mais observe une réalisation de cette loi, ceci oblige à étendre la notion de stratégie introduite dans la section précédente. On note $\Delta(\mathcal{A})$ l'ensemble des lois de probabilités sur $\mathcal{A}$ (qui s'injecte canoniquement dans $\mathcal{A}^K$).

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}^K\right)^{t}
\longrightarrow\Delta(\mathcal{A})
\]
qui donne la loi $\bs{p}_t$ en fonction des actions et des pertes passées.

La stratégie de l'adversaire est une fonction $E$ :
\[
E : \bigsqcup_{t\geq 1}\left(\mathcal{A}\times\set{R}^K\right)^{t}
\longrightarrow\mathcal{A}^K
\]
qui donne le vecteur de perte $\bs{\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 $\bs{p}_t$ et $\bs{\ell}_t$ sont
mesurables par rapport à cette tribu.

Le regret jusqu'au temps $T$ de la stratégie $P$ contre la stratégie $E$ est
défini par rapport à la meilleure action, c'est à dire celle de plus faible
perte cumulée.

On note $L_{i,T}$ la perte cumulée de l'action $i$ jusqu'à l'instant T :
\[
L_{i,T}=\sum_{t=1}^T\ell_{i,t}
\]
le regret est donc défini par : 
\[
R_T
=\sum_{t=1}^T \ell_{I_t,t}-\min_{1\leq i\leq K}L_{i,T}
=\sum_{t=1}^T \ell_{I_t,t}-\min_{1\leq i\leq K}\sum_{t=1}^T \ell_{i,t}
\]
le \emph{regret espéré} s'éloigne légèrement de la notion habituelle de regret
car il ne fait pas intervenir directement la perte du joueur, mais l'espérance
de
cette perte : 
\[
\bar{R}_T = 
\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\ell_{i,t}
-\min_{1\leq i\leq K}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, en notant $G_{i,T}$ le gain cumulé jusqu'à
l'instant $T$ :
\[
\bar{R}_T = 
\max_{1\leq i\leq K}\sum_{t=1}^T g_{i,t}
-\sum_{t=1}^T\sum_{i=1}^K 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/K$ pour
$i\in\{1,\ldots,K\}$.

À chaque tour $t\geq 1$ :

\begin{enumerate}
\item On tire $I_t\in\{1,\ldots,K\}$ suivant la loi
$\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$.
\item On observe les gains $\bs{g}_t=(g_{1,t},\ldots,g_{K,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}^{K}w_{i,t}\bigg)
.\]
\end{enumerate}
\end{encadre}

Le théorème suivant donne une borne sur le regret espéré de la
stratégie exponentielle. Ce théorème est important pour l'étude du problèmes
des bandits déterministes (section \ref{sec:bandits}), dans lequel le regret
espéré apparaît naturellement. Au lieu de l'étude habituelle du cas de
l'information parfaite utilisant l'inégalité de Hoeffding, on utilise ici une
majoration de l'exponentielle par un polynôme d'ordre 2 (lemme \ref{espexp}). On
fait ainsi apparaître un terme de type variance qui sera crucial dans la preuve
du théorème \ref{thm:exp3}.

\begin{thm}\label{thm:exp}
On suppose que les gains sont à valeurs dans $]-\infty, B]$, alors, pour
tout $\eta$ tel
que $\eta B\leq 1$ :
\[
\bar{R}_T =\max_{1\leq i\leq K}\sum_{t=1}^T g_{i,t}
-\sum_{t=1}^T\sum_{i=1}^K p_{i,t}g_{i,t}
\leq\frac{\ln K}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^K 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}^K\exp(\eta G_{i,T})\right)-\ln K \\
\geq \eta \max_{1\leq i\leq K}G_{i,T}-\ln K
\]

Pour la majoration, on remarque que :
\[
\ln\left(\frac{W_t}{W_{t-1}}\right)
=\ln\left(\sum_{i=1}^K
\frac{w_{i,t-1}}{W_{t-1}}\exp(g_{i,t})\right)
=\ln\mathbb{E}_t\big[\exp(\eta X)\big]
\]
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}^K p_{i,t}g_{i,t}
+\eta^2\sum_{i=1}^K p_{i,t}g_{i,t}^2
\]

On somme pour $t\in\{1,\ldots,K\}$ et on combine avec la minoration :
\[
\eta \max_{1\leq i\leq K}G_{i,T}-\ln K 
\leq \eta\sum_{t=1}^T\sum_{i=1}^K p_{i,t}g_{i,t}
+\eta^2 \sum_{t=1}^T\sum_{i=1}^K p_{i,t}g_{i,t}^2
.\]

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

\begin{rem}
On peut majorer le terme d'ordre 2 par $\eta B^2 T$. Le choix optimal pour $\eta$, $\eta=\sqrt{\ln K}/B\sqrt{T}$, conduit à la borne suivante pour le regret :
\[
\esp{R_T}\leq 2B\sqrt{T\ln K}
\]

On retrouve donc à un facteur multiplicatif près, la borne optimale dans le cas de l'information parfaite (cf. par exemple \cite{plg}).
\end{rem}

\subsection{Bandits déterministes}\label{sec:bandits}

Contrairement au paragraphe précédent, on observe à la fin de chaque tour
uniquement le gain correspondant à l'action choisie. La stratégie par poids exponentiels
ne s'applique pas directement car les gains cumulés de chaque action ne sont
plus disponibles.

L'idée naturelle pour contourner cette difficulté consiste à estimer à chaque
tour les gains qui nous sont inconnus et d'appliquer la stratégie du problème
à information parfaite en utilisant les gains estimés.

On obtient alors une borne sur le regret en appliquant, pour les gains
estimés, un résultat d'information parfaite, puis en contrôlant l'écart
entre les gains estimés et les gains réels par concentration. Cette méthode est
générale et sera également utilisée dans la section \ref{conv}.

L'estimateur naturel du gain pour l'action $i$ au tour $t$ serait, avec les
mêmes notations que dans la section \ref{fullinfo} :
\[
\widetilde{h}_{i,t}=\frac{g_{i,t}\mathbf{1}_{\{I_t=i\}}}{p_{i,t}}
\]
Cet estimateur est conditionnellement sans biais, c'est à dire
que :
\[
\espc{\widetilde{h}_{i,t}-g_{i,t}}{\trib{F}_{t-1}}=0.
\]
Toutefois, il n'est pas possible pour cet estimateur de contrôler de façon
satisfaisante l'écart entre les gains estimés et les gains réels. On lui
préfère donc l'estimateur biaisé suivant :
\[
\widetilde{g}_{i,t}=\frac{g_{i,t}\mathbf{1}_{\{I_t=i\}}}{p_{i,t}}+\frac{\beta}{
p_{i,t}}
\]
ceci conduit à l'algorithme Exp3.P (pour algorithme par poids Exponentiels pour
l'Exploration et l'Exploitation en grande Probabilité). Cet
algorithme a été présenté pour la première fois dans \cite{bandet} et donne une
borne pour le regret en $O\big(\sqrt{KT\ln(K/\delta)}\big)$.

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Algorithme Exp3.P}
\end{center}

\textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/K$ pour
$i\in\{1,\ldots,K\}$.

À chaque tour $t\geq 1$ :

\begin{enumerate}
\item On tire $I_t\in\{1,\ldots,K\}$ suivant la loi
$\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$.
\item On estime les gains
$\widetilde{\bs{g}}_t=(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{K,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}{K}
\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{K}w_{i,t}\bigg)\]
\end{enumerate}
\end{encadre}

\begin{rem}
On voit apparaître un compromis entre exploitation (utilisation des poids
exponentiels) et exploration (utilisation des poids uniformes en $1/K$). Le
paramètre $\gamma$ que l'on doit régler en fonctions des contraintes de jeu
assure ce compromis.
\end{rem}

\begin{thm}\label{thm:exp3}
Soit $\delta\in]0,1[$. On suppose que les gains sont à valeurs dans $[0,1]$ ($\bs{g}_t\in [0,1]^K$). Si les paramètres de la stratégie Ex3.P vérifient :
\[\beta\leq 1,\quad
\gamma\leq \frac{1}{2},\quad
\eta\leq \frac{\gamma}{2K}
,\]
alors on a avec probabilité supérieure à $1-\delta$ :
\[
R_T=\sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i \leq K}\sum_{t=1}^T\ell_{i,t}
\leq \frac{\ln K}{\eta}
+\frac{1}{\beta}\ln\left(\frac{K}{\delta}\right)
+TK\beta+\big(\gamma+\eta(1+\beta)K\big)T
\]

En particulier, en prenant:
\[
\eta=\frac{1}{2}\sqrt{\frac{\ln K}{KT}},\quad
\gamma=\sqrt{\frac{K\ln K}{T}},\quad
\beta=\sqrt{\frac{\ln K}{KT}},
\]
si $T\geq 4K\ln K$, on obtient avec probabilité supérieure à $1-\delta$ :
\[
R_T=\sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i \leq K}\sum_{t=1}^T\ell_{i,t}
\leq \frac{9}{2}\sqrt{KT\ln K}+\sqrt{\frac{KT}{\ln K}}\ln\left(\frac{K}{\delta}\right)
+\frac{\ln K}{2}
\]
\end{thm}

\begin{proof}
On a une information parfaite 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{thm:exp} : 
\begin{equation}\label{eq:exp3-fullinfo}
\max_{1\leq i\leq K}\sum_{t=1}^T \widetilde{g}_{i,t}
-\sum_{t=1}^T\sum_{i=1}^K q_{i,t}\widetilde{g}_{i,t}
\leq\frac{\ln K}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^K q_{i,t}\widetilde{g}_{i,t}^2
\end{equation}
on relie $q_{i,t}$ à $p_{i,t}$ en multipliant par $1-\gamma$ et en
remarquant que $p_{i,t}\geq q_{i,t}(1-\gamma)$ :
\begin{equation}\label{eq:exp3-base}
(1-\gamma)\max_{1\leq i\leq K}\sum_{t=1}^T \widetilde{g}_{i,t}
-\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\widetilde{g}_{i,t}
\leq\frac{\ln K}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\widetilde{g}_{i,t}^2
\end{equation}

Vu le choix de l'estimateur de gain, on a :
\begin{equation}\label{eq:exp3-maj1}
\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\widetilde{g}_{i,t}
=\sum_{t=1}^T\sum_{i=1}^K
\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}+\beta\right)=\sum_{t=1}^T g_{I_t,t}
+TK\beta
\end{equation}
et :
\begin{equation}\label{eq:exp3-maj2}
\sum_{t=1}^T\sum_{i=1}^K p_{i,t}\widetilde{g}_{i,t}^2
\leq\sum_{i=1}^K\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}^K\widetilde{G}_{i,t}
\leq(1+\beta)K\max_{1\leq i\leq K}\widetilde{G}_{i,t}
\end{equation}

On injecte \eqref{eq:exp3-maj1} et \eqref{eq:exp3-maj2} dans \eqref{eq:exp3-base} :
\[
(1-\gamma)\max_{1\leq i\leq K}\sum_{t=1}^T \widetilde{g}_{i,t}
-\sum_{t=1}^T g_{I_t,t}
\leq\frac{\ln K}{\eta}+TK\beta
+\eta(1+\beta)K\max_{1\leq i\leq K}\widetilde{G}_{i,t}
\]
\[
\begin{split}
\max_{1\leq i\leq K}G_{i,t}
-\sum_{t=1}^T g_{I_t,t}
&\leq\frac{\ln K}{\eta}+TK\beta
+\max_{1\leq i\leq K}G_{i,t}
-\big(1-\gamma-\eta(1+\beta)K\big)\max_{1\leq i\leq K}\widetilde{G}_{i,t}\\
&\leq \frac{\ln K}{\eta}+TK\beta
+\big(1-\gamma-\eta(1+\beta) K\big)\left(\max_{1\leq i\leq K}G_{i,T}
-\max_{1\leq i\leq K}\widetilde{G}_{i,t}\right)\\
&\qquad+\big(\gamma+\eta(1+\beta) K\big)\max_{1\leq i\leq K}G_{i,T}
\end{split}
\]
puis vu que $1-\gamma-\eta(1+\beta) K\leq 1$, et que $\max_{1\leq i\leq K}  
G_{i,T}\leq T$ :
\begin{equation}\label{eq:exp3-key}
\max_{1\leq i\leq K}G_{i,t}
-\sum_{t=1}^T g_{I_t,t}
\leq \frac{\ln K}{\eta}+TK\beta
+\left(\max_{1\leq i\leq K}G_{i,T}
-\max_{1\leq i\leq K}\widetilde{G}_{i,t}\right)
+\big(\gamma+\eta(1+\beta)K\big)T
\end{equation}

Il nous reste à majorer l'écart entre les gains et les gains estimés. Pour cela, on
souhaite appliquer le corollaire \ref{semibernstein} 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)
\leq \frac{1}{p_{i,t}}
\end{split}
\]
On applique le corollaire \ref{semibernstein}. On a donc avec probabilité supérieure à $1-\delta/K$, pour tout $\theta\leq 1$ :
\[
G_{i,T}-\widetilde{G}_{i,T} + \beta\sum_{t=1}^T\frac{1}{p_{i,t}}
\leq \theta\sum_{t=1}^T\frac{1}{p_{i,t}}
+\frac{1}{\theta}\ln\left(\frac{K}{\delta}\right)
\]
On choisit alors $\theta=\beta$, ce qui permet d'annuler le terme de variance. Puis en majorant l'intersection des évènements précédents, on a avec probabilité supérieure à $1-\delta$ :
\[
\max_{1\leq i\leq K}G_{i,T}-\max_{1\leq i\leq K}\widetilde{G}_{i,t}
\leq\frac{1}{\beta}\ln\left(\frac{K}{\delta}\right)
\]
en injectant cette dernière majoration dans \eqref{eq:exp3-key}, on obtient
finalement :
\[
\max_{1\leq i\leq K}G_{i,t}
-\sum_{t=1}^T g_{I_t,t}
\leq \frac{\ln K}{\eta}+TK\beta
+\frac{1}{\beta}\ln\left(\frac{K}{\delta}\right)
+\big(\gamma+\eta(1+\beta)K\big)T
\]

La deuxième inégalité du théorème s'obtient par simple injection des valeurs précisées pour les différents paramètres.
\end{proof}

\begin{rem}
La preuve diffère de celle donnée dans \cite{plg} :
\begin{itemize}
\item Tout d'abord, l'accent est mis sur le lien avec le cas de l'information
totale, en appliquant directement le théorème \ref{thm:exp}. À ce sujet, on
peut se demander l'intérêt d'utiliser une borne d'ordre 2 pour le regret,
plutôt que la borne habituelle pour l'information parfaite :
\[
R_T\leq \frac{\ln K}{\eta} +\eta\frac{TB^2}{8}
\]
où $B$ est un majorant des gains. La raison en est que pour les gains estimés,
le meilleur majorant dont on dispose est $(1+\beta)K/\gamma$. Cette majoration
est très grossière car, sauf dans le cas où $i=I_t$, $\widetilde{g}_{i,t}$ est
majoré par $\beta K/\gamma$. La borne du théorème \ref{thm:exp} permet un
traitement plus adapté à la nature de l'estimateur choisi.
\item Le contrôle de l'écart entre les gains estimés et les gains réels est
obtenu grâce à l'inégalité de Bernstein (corollaire \ref{semibernstein}), ce
qui permet d'éviter l'emploi d'un lemme ad hoc. Cette étape de la preuve fait
d'ailleurs apparaître le rôle crucial joué par le paramètre $\beta$ de biais :
il permet de compenser le terme de variance introduit par l'inégalité de
Bernstein. Le terme $TK\beta$ qui apparaît dans la borne du théorème montre
toutefois que ce paramètre introduit un compromis supplémentaire et ne doit pas
être choisi trop grand.
\end{itemize}
\end{rem}

\subsection{Bandits déterministes avec experts}\label{sec:banditsexp}

Dans le problème de prédiction avec experts, on joue au même jeu que
précédemment : on doit choisir une action parmi un ensemble fini $\mathcal{A}$
de cardinal $K$. Cependant, au début de chaque tour, un ensemble d'experts nous
conseille sur l'action à prendre : chaque expert $i$ fournit un vecteur de
conseil $\bs{\xi}^i_t\in\Delta(\mathcal{A})$. Après l'observation de ces
vecteurs, on choisit la loi de probabilité de l'action à joueur. Le jeu prend
donc la forme suivante.

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Jeu de prévision avec expert}
\end{center}
À chaque tour $t\geq 1$ :
\begin{enumerate}
\item Le joueur observe les vecteurs des experts : $\bs{\xi}^1_t,\ldots,\bs{\xi}^N_t$
\item Le joueur choisit une loi de probabilité sur $\mathcal{A}$ : $\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$
\item Simultanément, l'adversaire choisit un vecteur de perte,
$\bs{\ell}_t=(\ell_{1,t},\ldots,\ell_{K,t})$
\item Le joueur tire $I_t$ suivant la loi $\bs{p}_t$ et choisit l'action
$I_t$. Il reçoit la perte $\ell_{I_t,t}$.
\item Le joueur et les experts observent la perte $\ell_{I_t,t}$.
\end{enumerate}
\end{encadre}

La prédiction avec experts généralise donc le problème des bandits
déterministes étudié précédemment (on peut considérer chaque action
comme un expert constant) et apparaît comme un problème de « méta-prédiction » :
on dispose d'un certain nombre de stratégies de prédiction dont on ne connaît
pas a priori la qualité. Au bout d'un certain nombre de tours, on souhaiterait
avoir un gain proche de la meilleure stratégie. Le regret n'est donc pas défini
ici par rapport à la meilleure action, mais par rapport au meilleur expert. On
définit la perte cumulée de l'expert $i$ jusqu'à l'instant $T$ par :
\[
L_{i,T}=\sum_{t=1}^T \bs{\xi}^i_t\cdot\bs{\ell}_t
\]

La quantité que l'on souhaite majorer est donc le regret :
\[
R_T = \sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i\leq N}\sum_{t=1}^T \bs{\xi}^i_t\cdot\bs{\ell}_t
\]

Comme précédemment, on suppose que les pertes appartiennent à l'intervalle $[0,1]$, on pose $g_{i,t}=1-\ell_{i,t}$. Le regret s'écrit également :
\[
R_T = \max_{1\leq i\leq N}\sum_{t=1}^T\bs{\xi}^i_t\cdot\bs{g}_t - \sum_{t=1}^T g_{I_t,t}
\]

On pourrait appliquer directement l'algorithme Exp3.P en considérant chaque
expert $i$ comme une action de gain associé $\bs{\xi}^i_t\cdot\bs{g}_t$. On
obtient alors avec le théorème \ref{thm:exp3} une borne pour le regret en
$O(\sqrt{NT\ln N})$. Dans certains cas les experts sont très nombreux par
rapport au nombre d'actions ($N$ peut devenir exponentiel en $K$), on
souhaiterait donc avoir une borne dont la dépendance en $N$ est au plus en
$O(\ln N)$.

L'algorithme présenté ici est l'algorithme Exp4.P (algorithme par poids
Exponentiels pour l'Exploitation et l'Exploration avec Experts en grande
Probabilité). Il s'agit d'un mélange entre les algorithmes Ex3.P et Exp4 comme
présenté dans \cite{exp4}, et permet d'obtenir une borne en $O(\sqrt{KT\ln N})$.

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Algorithme Exp4.P}
\end{center}

\textbf{Paramètres :} $\beta,\eta,\gamma>0$

\textbf{Initialisation :} On pose $w_{j,0}=1$ et $p_{j,1}=1/K$ pour
$j\in\{1,\ldots,K\}$.

À chaque tour $t\geq 1$ :

\begin{enumerate}
\item On tire $I_t\in\{1,\ldots,K\}$ suivant la loi
$\bs{p}_t=(p_{1,t},\ldots,p_{K,t})$ et on observe le gain $g_{I_t,t}$.
\item On estime les gains
$\widetilde{\bs{g}}=(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{K,t})$ à
partir du gain observé :
\[
\forall j\in\{1,\ldots,K\},\quad
\widetilde{g}_{j,t}=\frac{1}{p_{j,t}}\left(g_{I_t,t}\mathbf{1}_{\{I_t=j\}}
+\beta\right)
\]
\item On calcule les gains estimés de chaque expert :
\[
\forall i\in\{1,\ldots,N\},\quad
\widetilde{y}_{i,t} = \bs{\xi}^i_t\cdot\widetilde{\bs{g}}_t
\]

\item On met à jour les poids exponentiels :
\[
\forall i\in\{1,\ldots,N\},\quad
w_{i,t}=w_{i,t-1}\exp(\eta\widetilde{y}_{i,t})
\]
\item On calcule la distribution pour le tour suivant :
\[
\forall j\in\{1,\ldots,K\},\quad
p_{j,t+1}=(1-\gamma)\sum_{i=1}^N\frac{w_{i,t}\xi^i_{j,t}}{W_t}+\frac{\gamma}{K}
\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{N}w_{i,t}\bigg)\]
\end{enumerate}
\end{encadre}

\begin{thm}\label{thm:exp4}
Soit $\delta\in]0,1[$. On suppose que l'ensemble des experts contient l'expert « uniforme », pour lequel $\bs{\xi}_t=(1/K,\ldots,1/K)$. Si les paramètres de la stratégie Ex4.P vérifient :
\[\beta\leq 1,\quad
\gamma\leq \frac{1}{2},\quad
\eta\leq \frac{\gamma}{2K}
,\]
alors on a avec probabilité supérieure à $1-\delta$ :
\[
\sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i\leq N}\sum_{t=1}^T \bs{\xi}^i_t\cdot\bs{\ell}_t
\leq \frac{\ln N}{\eta} + \beta KT
+\frac{1}{\beta}\ln\left(\frac{N}{\delta}\right)
+\big(\gamma+\eta(1+\beta)K\big)T
\]

En particulier, en prenant:
\[
\eta=\frac{1}{2}\sqrt{\frac{\ln N}{KT}},\quad
\gamma=\sqrt{\frac{K\ln N}{T}},\quad
\beta=\sqrt{\frac{\ln N}{KT}},
\]
si $T\geq 4K\ln N$, on obtient avec probabilité supérieure à $1-\delta$ :
\[
\sum_{t=1}^T \ell_{I_t,t} - \min_{1\leq i\leq N}\sum_{t=1}^T \bs{\xi}^i_t\cdot\bs{\ell}_t
\leq \frac{9}{2}\sqrt{KT\ln N}+\sqrt{\frac{KT}{\ln
N}}\ln\left(\frac{N}{\delta}\right)
+\frac{\ln N}{2}
\]
\end{thm}

\begin{proof}
On suit pas à pas la preuve du théorème \ref{thm:exp3} en faisant correspondre
à chaque étape les équations obtenues. On pose $q_{i,t}=w_{i,t-1}/W_{t-1}$. On a
une information parfaite sur les gains estimés des experts, donc en appliquant
le théorème~\ref{thm:exp}, on obtient comme en \eqref{eq:exp3-fullinfo} :
\begin{equation}\label{eq:exp4-fullinfo}
\max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}
-\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{y}_{i,t}
\leq\frac{\ln N}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{y}_{i,t}^2
\end{equation}

On relie les $q_{i,t}$ aux $p_{j,t}$ en remarquant que
$(1-\gamma)\sum_{i=1}^Nq_{i,t}\xi^i_{j,t}\leq p_{j,t}$.

On a :
\[
\sum_{i=1}^N q_{i,t}\widetilde{y}_{i,t}
=\sum_{i=1}^Nq_{i,t}\sum_{j=1}^K \xi^i_{j,t}\widetilde{g}_{j,t}
=\sum_{j=1}^K\widetilde{g}_{j,t}\sum_{i=1}^N q_{i,t}\xi^i_{j,t}
\leq\frac{1}{1-\gamma}\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}
\]
et, en appliquant l'inégalité de Jensen à la fonction $x\mapsto x^2$ :
\[
\begin{split}
\sum_{i=1}^N q_{i,t}(\widetilde{y}_{i,t})^2
=\sum_{i=1}^Nq_{i,t}\left(\sum_{j=1}^K \xi^i_{j,t}\widetilde{g}_{j,t}\right)^2
&\leq\sum_{i=1}^Nq_{i,t}\sum_{j=1}^K\xi^i_{j,t}\widetilde{g}_{j,t}^2\\
&=\sum_{j=1}^K\widetilde{g}_{j,t}^2\sum_{i=1}^Nq_{i,t}\xi^i_{j,t}
\leq\frac{1}{1-\gamma}\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}^2
\end{split}
\]
on injecte les deux inégalités précédentes dans \eqref{eq:exp4-fullinfo}, et
après multiplication par $1-\gamma$, on obtient comme en \eqref{eq:exp3-base}
: 
\begin{equation}\label{eq:exp4-base}
(1-\gamma)\max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}
-\sum_{t=1}^T\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}
\leq\frac{\ln N}{\eta}
+\eta\sum_{t=1}^T\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}^2
\end{equation}

On a de même qu'en \eqref{eq:exp3-maj1} :
\begin{equation}\label{eq:exp4-maj1}
\sum_{t=1}^T\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}=
\sum_{t=1}^T g_{I_t,t}+TK\beta
\end{equation}
et on montre l'analogue de \eqref{eq:exp3-maj2} :
\begin{equation}\label{eq:exp4-maj2}
\sum_{t=1}^T\sum_{j=1}^K p_{j,t}\widetilde{g}_{j,t}^2
\leq(1+\beta)\sum_{t=1}^T \sum_{j=1}^{K}\widetilde{g}_{j,t}
=(1+\beta) K \sum_{t=1}^T \sum_{j=1}^{K}\frac{\widetilde{g}_{j,t}}{K}
\leq (1+\beta)K \max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}
\end{equation}
En effet, on voit apparaître le gain estimé de l'expert « uniforme », que l'on
sait appartenir à l'ensemble des experts.

On injecte \eqref{eq:exp4-maj1} et \eqref{eq:exp4-maj2} dans
\eqref{eq:exp4-base}, et en réordonnant de la même manière que dans la preuve
du théorème \ref{thm:exp3}, il vient comme en \eqref{eq:exp3-key} :
\[
\max_{1\leq i\leq N}\sum_{t=1}^T y_{i,t}
-\sum_{t=1}^Tg_{I_t,t}
\leq \frac{\ln N}{\eta} + \beta KT
+\left(\max_{1\leq i\leq N}\sum_{t=1}^T y_{i,t}
-\max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}\right)
+\big(\gamma+\eta(1+\beta)K\big)T
\]

Il reste à majorer l'écart entre les gains estimés et les gains réels. On définit la suite d'accroissements de martingale : 
\[
X_{i,t}=y_{i,t}-\widetilde{y}_{i,t}+\sum_{j=1}^K\frac{\xi^i_{j,t}\beta}{p_{j,t}}
= \sum_{j=1}^K \xi^i_{j,t} g_{j,t}\left(1-\frac{\bs{1}_{\{I_t=j\}}}{p_{j,t}}\right)
\]

On a :
\[
\begin{split}
\mathbb{E}_t[X_{i,t}^2]
&=\mathbb{E}_t\left[\left(\sum_{j=1}^K \xi^i_{j,t} g_{j,t}\frac{\bs{1}_{\{I_t=j\}}}{p_{j,t}}\right)^2\right]
-\left(\sum_{j=1}^K \xi^i_{j,t} g_{j,t}\right)^2\\
&=\mathbb{E}_t\left[\sum_{j=1}^K \left(\xi^i_{j,t} g_{j,t}\right)^2\frac{\bs{1}_{\{I_t=j\}}}{p_{j,t}^2}
\right]-\left(\sum_{j=1}^K \xi^i_{j,t} g_{j,t}\right)^2
\leq \sum_{j=1}^K\frac{\xi^i_{j,t}}{p_{j,t}}
\end{split}
\]

On applique le corollaire \ref{semibernstein} de la même façon que dans la preuve du théorème \ref{thm:exp3}, on obtient avec probabilité supérieure à $1-\delta$ :
\[
\max_{1\leq i\leq N}\sum_{t=1}^T y_{i,t}-\max_{1\leq i\leq N}\sum_{t=1}^T\widetilde{y}_{i,t}
\leq \frac{1}{\beta}\ln\left(\frac{N}{\delta}\right)
\]

On conclut alors de la même manière que, avec probabilité supérieure à $1-\delta$ :
\[
\max_{1\leq i\leq N}\sum_{t=1}^T y_{i,t}
-\sum_{t=1}^Tg_{I_t,t}
\leq \frac{\ln N}{\eta} + \beta KT
+\frac{1}{\beta}\ln\left(\frac{N}{\delta}\right)
+\big(\gamma+\eta(1+\beta)K\big)T
\]

Il reste à injecter les valeurs des différents paramètres pour obtenir la deuxième inégalité du théorème.
\end{proof}

\section{Prévision dans un univers convexe}\label{conv}

Dans les cas où l'ensemble de décision est infini, les algorithmes précédents
tombent en défaut. Le cadre naturel pour étendre le problème précédent est de
prendre pour ensemble de décision un convexe compact de $\mathbf{R}^d$.

Dans l'étude des algorithmes qui suivent, on fera fréquemment des
considérations de distance. On munit donc $\mathbf{R}^d$ de la métrique usuelle
induite par la norme euclidienne. On note $\|x\|$ la norme euclidienne d'un
vecteur $x$ et $x\cdot y$ le produit scalaire canonique entre
deux vecteurs. Enfin, on choisit $C$ un convexe compact de
$\mathbf{R^d}$, et on note $\Pi_C$ la projection sur le convexe $C$ définie
comme au paragraphe \ref{projection}.

Le jeu consiste donc à choisir à chaque tour un élément de $C$, l'adversaire
choisit non pas un vecteur de perte mais une fonction de perte définie sur le
convexe tout entier. On impose que les fonctions de perte soient convexes. 

Le plan de cette partie est le même que celui de la partie précédente : on
commence par étudier le cas de l'information parfaite. L'étude du cas de
l'information partielle consiste à estimer l'information que l'on ne connaît
pas et à se ramener au cas précédent.

\subsection{Cas de l'information parfaite}

Ici, le joueur et l'environnement choisissent leurs actions de façon
déterministe en fonction du passé. On étudie un algorithme de descente de
gradient tiré de \cite{zink}.

\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 le
joueur 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)$.

Le regret pour la stratégie $S$ contre la stratégie $E$ est
défini par rapport au meilleur choix constant d'un élément de $C$ :
\[
R_T=\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)
\]

Dans le cas où la fonction de perte $\ell_t$ ne varie pas dans le temps, on
voit que minimiser le regret revient à trouver le minimum d'une fonction
convexe. Dans ce cas, on sait que les algorithmes de descente de gradient
fournissent une méthode efficace pour converger vers le minimum.

On cherche une borne sur le regret valable pour tous choix de suite $(\ell_t)$,
et donc notamment lorsque l'adversaire choisit une suite constante de fonctions
de perte. Ceci motive l'emploi d'un algorithme de descente de gradient pour
étudier le problème de prévision dans un ensemble convexe. Auparavant on montre
que dans le cas de l'information totale, on peut réduire le problème aux
fonctions de perte linéraires.

\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 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 les assimiler au produit scalaire par un vecteur de $\set{R}^d$, que
l'on notera également $\ell_t$ par abus. Le gradient de la fonction $x\mapsto
\ell_t\cdot x$ est $\ell_t$, donc l'algorithme ci-dessous est effectivement un
algorithme de descente de gradient.

\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}\label{thm:simplezink}
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=\eta=\frac{D}{K\sqrt{T}}$, on obtient :
\[
R_T\leq DK\sqrt{T}
\]
\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é, le choix de $\eta_t$ constant indiqué donne immédiatement la borne voulue.
\end{proof}

Le choix optimal pour la suite $(\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 choix adaptatif des
paramètres $\eta_t$, on peut toutefois avoir une borne satisfaisante pour le
regret :

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

\begin{proof}En reprenant le début de la preuve précédente, on obtient :
\[
\sum_{t=1}^T \ell_t\cdot(x_t-x)
\leq \frac{D^2}{2\eta_T}+\frac{1}{2}\sum_{t=1}^T \eta_t\|\ell_t\|^2
\]

Notons $T_0$ le premier instant où $V_{t-1}\geq K^2$. Le choix de $\eta_t$ conduit à :
\begin{equation}\label{zinkadap}
\sum_{t=1}^T \ell_t\cdot(x_t-x)
\leq \frac{D^2}{2\eta_T}
+\frac{1}{2}\sum_{t=1}^{T_0-1} \eta_t\|\ell_t\|^2
+\frac{1}{2}\sum_{t=T_0}^T \frac{D}{\sqrt{V_{t-1}}}\|\ell_t\|^2
\end{equation}

En écrivant $\|\ell_t\|^2=V_t-V_{t-1}$, on voit qu'on doit majorer la quantité :
\[
\sum_{t=T_0}^T\frac{V_t-V_{t-1}}{\sqrt{V_{t-1}}}
=\sum_{t=T_0}^T\frac{\sqrt{V_t}+\sqrt{V_{t-1}}}{\sqrt{V_{t-1}}}\big(\sqrt{V_t}-\sqrt{V_{t-1}}\big)
\]
Or, en majorant $\sqrt{V_t}$ par $\sqrt{V_{t-1}}+\|\ell_t\|$ :
\[
\frac{\sqrt{V_t}+\sqrt{V_{t-1}}}{\sqrt{V_{t-1}}}
\leq 2+ \frac{\|\ell_t\|}{\sqrt{V_{t-1}}}
\leq 3
\]
On a donc :
\[
\sum_{t=T_0}^T\frac{V_t-V_{t-1}}{\sqrt{V_{t-1}}}
\leq 3\sqrt{V_T}\leq 3K\sqrt{T}
\]

En injectant dans \eqref{zinkadap} on obtient :
\[
\sum_{t=1}^T \ell_t\cdot(x_t-x)
\leq \frac{D^2}{2\eta_T}
+\frac{3}{2}DK\sqrt{T}
+\frac{1}{2}\sum_{t=1}^{T_0-1} \eta_t\|\ell_t\|^2
\leq\frac{1}{2}DK\sqrt{T}
+\frac{3}{2}DK\sqrt{T}
+\frac{1}{2}\sum_{t=1}^{T_0-1} \eta_t\|\ell_t\|^2
\]

En prenant le maximum pour $x\in C$ on obtient finalement :
\[
R_T\leq 2 DK\sqrt{T}+\frac{1}{2}\sum_{t=1}^{T_0-1} \eta_t\|\ell_t\|^2
\leq 2 DK\sqrt{T} + \frac{D}{2}V_{T_0-1}
\leq 2 DK\sqrt{T} + \frac{DK^2}{2}
\]

\end{proof}

\subsection{Information partielle}

On s'intéresse au même problème que précédemment, mais au lieu d'observer la fonction de perte $\ell_t$ à la fin du tour $t$, seule sa valeur en quelques points nous est révélée. On ne peut donc pas directement appliquer l'algorithme de descente de gradient vu précédemment, car on ne plus calculer le gradient de la fonction de perte. L'idée naturelle est donc d'estimer le gradient à partir des observations dont on dispose. 

Dans \cite{conv}, un seul point est observé à chaque tour, et l'estimateur
proposé conduit à une borne en $O(T^{3/4})$ pour le regret. Pour des fonctions
de pertes linéaires, Abernethy, Hazan et Rakhlin (\cite{linband}) ont montré une
borne en $O(\sqrt{T})$. Pour le cas
général des fonctions convexes, on ne connaît pas encore d'algorithme en
$O(\sqrt{T})$, \cite{multi} suggère que celui-ci sera sans doute assez différent
des algorithmes de descente de gradient étudiés jusqu'ici.

Ici, on étudie l'adaptation de l'estimateur de \cite{conv} dans le cas d'une
observation de deux points comme développée dans \cite{multi}. On obtient alors
une borne en $O(\sqrt{T})$, borne que l'on sait optimale. 

On choisit comme précédemment pour ensemble de décision un convexe $C$ compact
de $\mathbf{R^d}$ et on note $D$ son diamètre pour la norme euclidienne.

On observe donc à chaque tour $t$ deux éléments de $C$ que l'on note $y_{1,t}$
et $y_{2,t}$. On paye ce que l'on observe, c'est à dire que notre perte au tour
$t$ est mesurée par :
\[
\frac{1}{2}\big(\ell_t(y_{1,t})+\ell_t(y_{2,t})\big)
\]

Comme dans la section précédente, le regret est défini par rapport au meilleur
choix constant dans $C$ :
\[
R_T = \sum_{t=1}^T\frac{1}{2}\big(\ell_t(y_{1,t})+\ell_t(y_{2,t})\big)
-\min_{x\in C}\sum_{t=1}^T \ell_t(x)
\]

Précisons maintenant les hypothèses faites sur le convexe $C$ et les fonctions
de perte $\ell_t$.

On suppose que le convexe contient $0$, et que $0$ est
dans l'intérieur du convexe, c'est à dire qu'il existe $r$ tel que la boule de
centre $0$ et de rayon $r$ soit contenue dans le convexe.

Cette hypothèse peut sembler restrictive. En effet, si l'on considère
l'exemple du simplexe standard de $\mathbf{R^d}$, qui est un cas fréquent en
prédiction convexe, il est d'intérieure vide dans $\mathbf{R^d}$. En fait le
problème n'est qu'une apparence :

Tout d'abord, sauf quand le convexe est réduit à un point\footnote{auquel cas
toute stratégie assure un regret nul}, on peut toujours supposer que le convexe
est d'intérieur non vide quitte à réduire la dimension de l'espace ambiant
$\mathbf{R^d}$. En effet, si on prend l'exemple du simplexe standard de
$\mathbf{R^2}$, il s'agit d'un segment de droite, donc d'intérieur vide dans
$\mathbf{R^2}$, mais si on le considère plongé dans $\mathbf{R}$, il est
d'intérieur non vide. Inversement un triangle dans le plan est d'intérieur non
vide, mais si on le plonge dans l'espace, il devient d'intérieur vide. Il faut
donc sous-entendre que le convexe $C$ est plongé dans $\mathbf{R^d}$, avec
\emph{$d$ la dimension minimale pour contenir $C$}. La proposition
\ref{prop:inclusion}, précise que l'on peut toujours considérer $C$ comme
plongé dans un espace dans lequel il est d'intérieur non vide.

Soit alors $x_0$ un point dans l'intérieur de $C$, on voit que le problème de
minimisation de contrôle du regret est invariant par isométrie du convexe, on
peut donc effectuer une translation de vecteur $-x_0$ et ainsi obtenir que $0$
est dans le convexe et contenu dans une boule inclue dans le convexe.

Les fonctions de pertes $\ell_t$ sont convexes et vérifient la
propriété de Lipschitz suivante :
\[
\exists G,\;\forall t\geq 1,\;\forall (x,y)\in C^2,\;
\left|\ell_t(x)-\ell_t(y)\right|\leq G\|x-y\|
\]
Enfin on note $\mathcal{B}$ la boule unité. Si $\xi$ est un réel, on note $(1-\xi)C=\{(1-\xi)x,\; x\in C\}$. L'algorithme utilisé est le suivant :

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

\textbf{Données :} une suite $(\eta_t)$ décroissante de réels positifs, $\xi\in]0,1[$, $\delta\in[0,\xi r]$.

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

À chaque tour $t\geq 2$ :
\begin{enumerate}
\item On choisit un vecteur $U_t$ uniformément dans $\mathcal{B}$
\item On note $y_{t,1}=x_t+\delta U_t$ et $y_{t,2}=x_t-\delta
U_t$, et on observe $\ell_t(y_{t,1})$ et $\ell_t(y_{t,2})$.
\item On estime le gradient de la fonction en $x_t$ :
\[
\widetilde{g}_t = \frac{d}{2\delta}\big(\ell_t(y_{t,1})-\ell_t(y_{t,2})\big)U_t
\]
\item On calcule $x_{t+1}$ pour le tour suivant :
\[
x_{t+1}=\Pi_{(1-\xi)C}(x_t-\eta_t\widetilde{g}_t)
\]
\end{enumerate}
\end{encadre}

\begin{rem}
On projette dans $(1-\xi)C$ au lieu de $C$, pour assurer que les points d'exploration $y_{t,1}$ et $y_{t,2}$ appartiennent à $C$. Un argument de convexité montre que pour que tel soit le cas, on doit avoir $\delta\in[0,\xi r]$.
\end{rem}


\paragraph{Notations et premiers résultats}
On note $\trib{F}_t$ la tribu de l'information dont on dispose au début du tour
$t$. Il s'agit de la tribu engendrée par les variables $(U_1,\ldots,U_{t-1})$.
On notera $\mathbb{E}_t$ l'espérance conditionnellement à cette tribu.

On définit une approximation régulière de $\ell_t$ définie sur $(1-\xi)C$. Si
$V$ est une variable aléatoire uniforme à valeur dans $\mathcal{B}$ :
\[
\widehat{\ell}_t(x)=\mathbb{E}_V[\ell_t(x+\delta V)|\trib{F}_t]
\]
$\widehat{\ell}_t$ est convexe car $\ell_t$ l'est. De plus en appliquant la
propriété du Lipschitz à $\ell_t$ sous l'intégrale, on voit que
$\widehat{\ell}_t$ vérifie également cette propriété pour la même constante
$G$.

De plus par une application astucieuse du théorème de Stokes, \cite{multi}
montre que $\widehat{\ell}_t$ est différentiable  en $x_t$ même quand $\ell_t$
ne l'est pas. Plus précisément, on a :
\begin{lem}\label{stokes}
$\widehat{\ell}_t$ est différentiable en $x_t$ et on a :
\[
\nabla \widehat{\ell}_t(x_t) = \mathbb{E}_t[\widetilde{g}_t]
\]
\end{lem}

\begin{proof}
La preuve est dans \cite{multi} et n'est pas reproduite ici.
\end{proof}

En appliquant la propriété de Lipschitz de $\ell_t$ entre les points $y_{1,t}$
et $y_{2,t}$ et en utilisant que $U_t$ est de norme plus petite que 1, on
montre que :
\[
\widetilde{g}_t\leq Gd
\]

Enfin, définissons la fonction $h_t$ sur $(1-\xi)C$ par :
\[
h_t(x)=\widehat{\ell}_t(x)+\big(\widetilde{g}_t-\nabla \widehat{\ell}_t(x_t)\big)\cdot x
\]
$h_t$ est convexe car $\widehat{\ell}_t$ l'est. En utilisant le lemme
\ref{stokes}, on montre que $\nabla h_t(x_t)=\widetilde{g}_t$. De
plus, pour tous $x$ et $y$ dans $(1-\xi)C$ :
\[
\begin{split}
|h_t(x)-h_t(y)|&\leq|\widehat{\ell}_t(x)-\widehat{\ell}_t(y)|
+\big(\|\widetilde{g}_t\|+\|\nabla \widehat{\ell}_t(x_t)\|\big)\|x-y\|\\
&\leq(G+2Gd)\|x-y\|\leq 3Gd\|x-y\|
\end{split}
\]

On est en mesure d'énoncer le théorème :

\begin{thm}
Notons : 
\[
V_t = \sum_{k=1}^t \|\widetilde{g}_t\|^2
\]
pour les choix des paramètres :
\[
\eta_t=\frac{D}{\sqrt{V_{t-1}}},\quad\delta=\frac{r}{T},\quad\xi=\frac{1}{T},
\]
alors, pour tout $x\in C$, pour tout $\varepsilon\in ]0,1[$ on a avec
probabilité supérieure à $1-\varepsilon$ :
\[
\sum_{t=1}^T\frac{1}{2}\big(\ell_t(y_{t,1})+\ell_t(y_{t,2})\big)
-\sum_{t=1}^T\ell_t(x)
\leq 2 DGd\sqrt{T} + \frac{DG^2 d^2}{2}
+ 4GD
+4GDd\sqrt{2T\ln\left(\frac{1}{\varepsilon}\right)}
\]
\end{thm}

\begin{proof}
On remarque que $\nabla h_t(x_t)=\widetilde{g}_t$, donc l'algorithme présenté s'identifie à une descente de gradient avec information complète pour la fonction $h_t$ dans l'ensemble convexe $(1-\xi)C$. Soit $x\in C$, vu que $\|\nabla h_t(x_t)\|\leq Gd$ et que $(1-\xi)x\in(1-\xi)C$, on peut appliquer le théorème \ref{superzink} :
\begin{equation}\label{eq:multi-1}
\sum_{t=1}^T h_t(x_t)
-\sum_{t=1}^T h_t\big((1-\xi)x\big)
\leq 2 DGd\sqrt{T} + \frac{DG^2 d^2}{2}
\end{equation}

Ensuite, on relie d'une part $\ell_t$ à $\widehat{\ell}_t$, puis $\widehat{\ell}_t$ à $h_t$. En utilisant la propriété de Lipschitz de $\ell_t$ on montre que :
\[
\frac{1}{2}\big(\ell_t(y_{t,1})+\ell_t(y_{t,2})\big)\leq\ell_t(x_t)+G\delta
\quad\text{et}\quad
\ell_t\big((1-\xi)x\big)\leq\ell_t(x)+GD\xi
\]

Soit $y\in(1-\xi)C$, en utilisant successivement la définition de
$\widehat{\ell}_t$, l'inégalité de Jensen et la propriété de Lipschitz de
$\ell_t$, on obtient :
\[
|\ell_t(y)-\widehat{\ell}_t(y)|
\leq\mathbb{E}_V|\ell_t(y)-\ell_t(y+\delta V)|
\leq G\delta
\]
Notamment : 
\[
\ell_t(x_t)\leq\widehat{\ell}_t(x_t)+G\delta
\quad\text{et}\quad
\widehat{\ell}_t\big((1-\xi)x\big)\leq\ell_t\big((1-\xi)x\big)+G\delta
\]
En combinant les inégalités précédentes, on obtient :
\begin{equation}\label{eq:multi-2}
\sum_{t=1}^T\frac{1}{2}\big(\ell_t(y_{t,1})+\ell_t(y_{t,2})\big)
-\sum_{t=1}^T\ell_t(x)
\leq \sum_{t=1}^T\widehat{\ell}_t(x_t)
-\sum_{t=1}^T\widehat{\ell}_t\big((1-\xi)x\big)+(3G\delta+GD\xi)T
\end{equation}

Enfin, pour relier $\widehat{\ell}_t$ à $h_t$, on remarque que $\mathbb{E}_t[h_t]=\widehat{\ell}_t$, donc en posant :
\[
X_t=\widehat{\ell}_t(x_t)-\widehat{\ell}_t\big((1-\xi)x\big)-h_t(x_t)+h_t\big((1-\xi)x\big)
,\]
$X_t$ est une suite d'accroissement de martingale. De plus, en utilisant les
remarques préliminaires :
\[
|X_t|\leq\big|\widehat{\ell}_t(x_t)-\widehat{\ell}_t\big((1-\xi)x\big)\big|
+\big|h_t(x_t)-h_t\big((1-\xi)x\big)\big|\leq GD+3GdD\leq 4GDd
\]
En appliquant l'inégalité de Hoeffding-Azuma, on obtient qu'avec probabilité
supérieure à $1-\varepsilon$ :
\begin{equation}\label{eq:multi-3}
\sum_{t=1}^T X_t \leq 4GDd\sqrt{2T\ln\left(\frac{1}{\varepsilon}\right)}
\end{equation}

En combinant \eqref{eq:multi-1}, \eqref{eq:multi-2} et \eqref{eq:multi-3}, on
obtient avec probabilité supérieure à $1-\varepsilon$ :
\[
\begin{split}
 \sum_{t=1}^T\frac{1}{2}\big(\ell_t(y_{t,1})+\ell_t(y_{t,2})\big)
-\sum_{t=1}^T\ell_t(x)
&\leq 2 DGd\sqrt{T} + \frac{DG^2 d^2}{2}
+ (3G\delta+GD\xi)T\\
&\qquad+4GDd\sqrt{2T\ln\left(\frac{1}{\varepsilon}\right)}
\end{split}
\]

On obtient alors le résultat annoncé en remplaçant les paramètres par les valeurs indiquées dans l'énoncé.
\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}\label{inegmart}

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. Le résultat principal de cette partie est la proposition \ref{bernstein} tirée de \cite{massart}. Il s'agit d'une extension de l'inégalité de Bernstein pour les suites d'accroissements de martingale. On dérive ensuite plusieurs variantes de cette inégalité. L'idée de découpage utilisée dans le corollaire \ref{megabernstein} provient de \cite{label}.

\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{T}^*, \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{T}^*,\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}\label{bernstein}
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 : $v\leq V_T\leq V$ avec $V/v\geq e$ 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 (V/v)}{\delta}\frac{(1+\ln C)}{\ln C}\right)}
+\frac{2K}{3}\ln\left(\frac{\ln (V/v)}{\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 (V/v)}{\delta/4}\right)}
+\frac{2K}{3}\ln\left(\frac{\ln (V/v)}{\delta/4}\right)
.\]
\end{cor}

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

Or, vu que $v\leq V_T\leq V\leq vC^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 (V/v)}{\ln C}+1=\ln (V/v)\frac{\big(1+\ln C/\ln
(V/v)\big)}{\ln C}
\leq \ln (V/v)\frac{(1+\ln C)}{\ln C}\qedhere
\]
\end{proof}

Dans les deux corollaires précédents, on applique directement la proposition \ref{bernstein}. Cependant, la preuve de cette proposition fait apparaître une optimisation (celle du paramètre $\eta$ dans la surmartingale $M_t$). Dans certains cas, il est préférable d'optimiser en fonction du contexte d'application. On peut ainsi énoncer une inégalité de Bernstein « non optimisée » :

\begin{cor}\label{semibernstein}
Soit $(X_1,\ldots,X_T)$ une suite d'accroissements de martingale majorée par 1. Soit $\delta\in]0,1[$, alors pour tout $\eta\in\set{R}^+$, avec probabilité supérieure à $1-\delta$ :
\[
S_T\leq\frac{e^{\eta}-\eta-1}{\eta}\,V_T+\frac{1}{\eta}\ln\left(\frac{1}{\delta}\right)
\]

En particulier, si $\eta\leq 1$ :
\[
S_T\leq\eta V_T+\frac{1}{\eta}\ln\left(\frac{1}{\delta}\right)
\]
\end{cor}

\begin{proof}
On repart du lemme \ref{lembernstein}. En appliquant l'inégalité de Doob à la surmartingale $M_t$ du lemme, on a:
\[
\prob{M_t\geq \varepsilon}\leq\frac{\esp{M_1}}{\varepsilon}\leq\frac{1}{\varepsilon}
\]
En posant $\delta=1/\varepsilon$, on a avec probabilité supérieure à $1-\delta$ :
\[
\eta S_T - \big(e^{\eta}-\eta-1\big)V_T\leq\ln\left(\frac{1}{\delta}\right)
\]
Ce qui donne, après réarrangement et division par $\eta$ la première inégalité du corollaire.

La deuxième inégalité est une application directe du lemme \ref{inegexp}.
\end{proof}


\subsection{Ensembles convexes}
\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}

\begin{prop}\label{prop:inclusion}
Soit $C$ un convexe de $\mathbf{R}^d$ non réduit à un point, alors il existe
un sous espace de $\mathbf{R}^d$ contenant $C$ et dans lequel $C$ est
d'intérieur non vide.
\end{prop}

\begin{proof}
Notons $E$ l'espace engendré par le convexe $C$, celui-ci est de dimension
finie inférieure à $d$. Notons $n$ cette dimension. Par définition, on peut
trouver une base de $E$, $(c_1,\ldots,c_n)$ constituée d'éléments de $C$.

Considérons $f$ l'application linéaire de $E$ dans $\mathbf{R}^n$ qui envoie
la base $(c_1,\ldots,c_n)$ sur la base canonique $(e_1,\ldots,e_n)$ de
$\mathbf{R}^n$. Cette application est bijective.

Munissions $E$ de la topologie induite par la restriction de la norme
euclidienne de $\mathbf{R^d}$, et $\mathbf{R}^n$ de la topologie euclidienne
canonique. Puisqu'on est en dimension finie, $f$ est continue, et réalise donc
un \emph{homéomorphisme linéaire} de $E$ dans $\mathbf{R}^n$.

$C$ étant convexe, l'hyperpyramide de sommmets de $(c_1,\ldots,c_n)$ est
contenue dans $C$. Donc l'hyperpyramide de sommets $(e_1,\ldots,e_n)$ est
contenue dans $f(C)$. Il est facile de voir que cet hyperpyramide contient une
boule ouverte de $\mathbf{R}^n$. L'image réciproque de cette boule ouverte par
$f$ est donc un ouvert de $C$ (l'image réciproque d'un ouvert par une
application continue est un ouvert), ce qui prouve que $C$ est d'intérieur non
vide dans~$E$. 
\end{proof}


\newpage
\bibliographystyle{plain-fr}
\bibliography{biblio}

\end{document}