From bcf4f0c11291b6bbe898ca61e3bbdecfe3a8770f Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 30 May 2010 15:12:01 +0200
Subject: Ajout de la fin de la preuve des bandits : reste à prouver l'étape 3
 et à améliorer l'étape 4. Reprise du corollaire de l'inégalité de Bernstein
 (avec un découpage multiplicatif).
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 rapport.tex | 109 ++++++++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 80 insertions(+), 29 deletions(-)

(limited to 'rapport.tex')

diff --git a/rapport.tex b/rapport.tex
index b53b365..8716905 100644
--- a/rapport.tex
+++ b/rapport.tex
@@ -135,21 +135,59 @@ et :
 \]
 
 D'où on déduit de \eqref{base} :
-\[
+\begin{equation}\label{etape2}
+\begin{split}
 (1-\gamma)\max_{1\leq i\leq N}\widetilde{G}_{i,T} -\frac{1-\gamma}{\eta}\ln N
-\leq G_T + TN\beta +\eta(1+\beta)\sum_{i=1}^N\widetilde{G}_{i,T}
-\]
+&\leq G_T + TN\beta +\eta(1+\beta)\sum_{i=1}^N\widetilde{G}_{i,T}\\
+&\leq G_T + TN\beta +\eta(1+\beta)N\max_{1\leq i\leq N}\widetilde{G}_{i,T}
+\end{split}
+\end{equation}
+
+% On souhaite maintenant relier les gains estimés aux gains
+% réels. On remarque que :
+% \[
+% \espc{g_{i,t}-\widetilde{g}_{i,t}}{\trib{F}_{t-1}}=-\frac{\beta}{p_{i,t}}
+% .\]
+% Donc le processus $(X_t)$ défini par
+% \[
+% X_t=g_{i,t}-\widetilde{g}_{i,t}+\frac{\beta}{p_{i,t}}
+% ,\]
+% est une suite d'accroissements de martingale.
 
 \paragraph{Étape 3}On souhaite maintenant relier les gains estimés aux gains
-réels. On remarque que :
+réels. On choisit $\beta=\sqrt{\ln(N/\delta)/TN}$, alors avec probabilité
+supérieure à $1-\delta$ :
 \[
-\espc{g_{i,t}-\widetilde{g}_{i,t}}{\trib{F}_{t-1}}=-\frac{\beta}{p_{i,t}}
-.\]
-Donc le processus $(X_t)$ défini par
+\max_{1\leq i\leq N} G_{i,T}-\max_{1\leq i\leq N}\widetilde{G}_{i,T}
+\leq TN\beta = \sqrt{TN\ln\left(\frac{N}{\delta}\right)}
+\]
+
+\paragraph{Étape 4}On repart de \eqref{etape2} :
 \[
-X_t=g_{i,t}-\widetilde{g}_{i,t}+\frac{\beta}{p_{i,t}}
-,\]
-est une suite d'accroissements de martingale.
+\left[1-\gamma-\eta(1+\beta)N\right]\max_{1\leq i\leq N}\widetilde{G}_{i,T}
+\leq G_T+TN\beta+\frac{1-\gamma}{\eta}\ln N 
+\]
+puis en utilisant l'étape 3, en remarquant que $0\leq
+1-\gamma-\eta(1+\beta)N\leq 1$ :
+\[
+\left[1-\gamma-\eta(1+\beta)N\right]\left(\max_{1\leq i\leq N}G_{i,T}-TN\beta
+\right)
+\leq G_T+TN\beta+\frac{1-\gamma}{\eta}\ln N 
+\]
+\[
+\left[1-\gamma-\eta(1+\beta)N\right]\max_{1\leq i\leq N}G_{i,T}
+\leq G_T+2TN\beta+\frac{1-\gamma}{\eta}\ln N 
+\]
+On exprime maintenant cette inégalité en termes de pertes :
+\[
+\left[1-\gamma-\eta(1+\beta)N\right]\left(T-\min_{1\leq i\leq N}L_{i,T}\right)
+\leq T-L_T+2TN\beta+\frac{1-\gamma}{\eta}\ln N 
+\]
+d'où :
+\[
+L_T - \min_{1\leq i\leq N}L_{i,T}
+\leq\left(\gamma+\eta(1+\beta)N\right)T +2TN\beta+\frac{1-\gamma}{\eta}\ln N 
+\]
 
 \section{Appendice}
 
@@ -362,42 +400,55 @@ directement la variance conditionnelle du processus :
 
 \begin{cor}
 Soit $(X_1,\ldots,X_T)$ une suite d'accroissements de
-martingale par rapport à la filtration $(\trib{F}_t)$. Supposons
-qu'il existe $K>0$ tel que :
+martingale par rapport à la filtration $(\trib{F}_t)$. Supposons que $V_T\geq
+1$ et qu'il existe $K>0$ tel que :
 \[
 \forall t \in \{1,\ldots,T\},\quad \left|X_t\right|\leq K,
 \]
-alors, avec probabilité supérieure à $1-\delta$ :
+alors, avec probabilité supérieure à $1-\delta$ et pour $T\geq 3$ :
+\[
+\forall C\in\left]1 ;+\infty\right[,\quad
+S_T\leq\frac{2K}{3}\ln\left(\frac{\ln T}{\delta}\frac{(1+\ln C)}{\ln C}\right)+
+\sqrt{2CV_T\ln\left(\frac{\ln T}{\delta}\frac{(1+\ln C)}{\ln C}\right)}
+.\]
+
+En particulier, en choisissant $C=3/2$, on obtient :
 \[
-S_T\leq\frac{2K}{3}\ln\left(\frac{T}{\delta}\right)+
-\sqrt{2(V_T+K^2)\ln\left(\frac{T}{\delta}\right)}
+S_T\leq\frac{2K}{3}\ln\left(\frac{\ln T}{\delta/4}\right)+
+\sqrt{3V_T\ln\left(\frac{\ln T}{\delta/4}\right)}
 .\]
 \end{cor}
 
 \begin{proof}
-D'après le corollaire précédent, pour tout $t\in\{1,\ldots,T\}$ :
+Posons $N=\lceil\ln T/\ln C\rceil$
+D'après le corollaire précédent, pour tout $r\in\{1,\ldots,N\}$ :
 \[
-\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{T}{\delta}\right)+
-\sqrt{2K^2t\ln\left(\frac{T}{\delta}\right)}
-\ \mathrm{et}\ V_T\leq K^2t}\leq\frac{\delta}{T}
+\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{N}{\delta}\right)+
+\sqrt{2K^2C^r\ln\left(\frac{N}{\delta}\right)}
+\ \mathrm{et}\ V_T\leq K^2C^r}\leq\frac{\delta}{N}
 \]
 
 D'où :
 \[
-\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{T}{\delta}\right)+
-\sqrt{2(V_T+K^2)\ln\left(\frac{T}{\delta}\right)}
-\ \mathrm{et}\ K^2(t-1)\leq V_T\leq K^2t}\leq\frac{\delta}{T}
+\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{N}{\delta}\right)+
+\sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}
+\ \mathrm{et}\ K^2C^{r-1}\leq V_T\leq K^2C^r}\leq\frac{\delta}{N}
 \]
 
-Or, vu que $0\leq V_T\leq K^2T$, en sommant l'inégalité précédente pour
-$t\in\{1,\ldots,T\}$, on obtient :
+Or, vu que $1\leq V_T\leq K^2T\leq K^2C^N$, en sommant l'inégalité précédente
+pour
+$r\in\{1,\ldots,N\}$, on obtient :
 \[
-\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{T}{\delta}\right)+
-\sqrt{2(V_T+K^2)\ln\left(\frac{T}{\delta}\right)}}\leq\delta
-.\qedhere
+\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{N}{\delta}\right)+
+\sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}}\leq\delta
+.
 \]
-\end{proof}
-
 
+On conclut en remarquant que, si $T\geq 3$ :
+\[
+N\leq\frac{\ln T}{\ln C}+1=\ln T\frac{(1+\ln C/\ln T)}{\ln C}
+\leq \ln T\frac{(1+\ln C)}{\ln C}\qedhere
+\]
+\end{proof}
 
 \end{document}
-- 
cgit v1.2.3-70-g09d2

