\documentclass[11pt,french,ignorenonframetext,aspectratio=169,]{beamer}
% \documentclass[11pt,french,ignorenonframetext,]{beamer}

%%%%%%%%%%%%%%%
%% Beamer theme
% choose one from http://deic.uab.es/~iblanes/beamer_gallery/
% or http://www.hartwork.org/beamer-theme-matrix/
% \usetheme{Warsaw}
\usetheme{CambridgeUS}

%%%%%%%%%%%%%%%%%%%%%%
%% Beamer color theme
%% default albatross beaver beetle crane dolphin dove fly lily
%% orchid rose seagull seahorse whale wolverine

%\usecolortheme{seahorse}  %% very lighty
\usecolortheme{dolphin}    %% nice blue
\usecolortheme{orchid}     %% dark red ?
\usecolortheme{whale}      %% black et séquences bnaires Warsaw

%%%%%%%%%%%%%%%%%%%%%%%%%
%% Change the theme
%\setbeamercolor{alerted text}{fg=orange}
%\setbeamercolor{background canvas}{bg=white}
%\setbeamercolor{block body alerted}{bg=normal text.bg!90!black}
%\setbeamercolor{block body}{bg=normal text.bg!90!black}
%\setbeamercolor{block body example}{bg=normal text.bg!90!black}
%\setbeamercolor{block title alerted}{use={normal text,alerted text},fg=alerted text.fg!75!normal text.fg,bg=normal text.bg!75!black}
%\setbeamercolor{block title}{bg=blue}
%\setbeamercolor{block title example}{use={normal text,example text},fg=example text.fg!75!normal text.fg,bg=normal text.bg!75!black}
%\setbeamercolor{fine separation line}{}
\setbeamercolor{frametitle}{fg=black}
%\setbeamercolor{item projected}{fg=black}
%\setbeamercolor{normal text}{bg=black,fg=yellow}
%\setbeamercolor{palette sidebar primary}{use=normal text,fg=normal text.fg}
%\setbeamercolor{palette sidebar quaternary}{use=structure,fg=structure.fg}
%\setbeamercolor{palette sidebar secondary}{use=structure,fg=structure.fg}
%\setbeamercolor{palette sidebar tertiary}{use=normal text,fg=normal text.fg}
%\setbeamercolor{section in sidebar}{fg=brown}
%\setbeamercolor{section in sidebar shaded}{fg= grey}
\setbeamercolor{separation line}{}
%\setbeamercolor{sidebar}{bg=red}
%\setbeamercolor{sidebar}{parent=palette primary}
%\setbeamercolor{structure}{bg=black, fg=green}
%\setbeamercolor{subsection in sidebar}{fg=brown}
%\setbeamercolor{subsection in sidebar shaded}{fg= grey}
%\setbeamercolor{title}{fg=blackblue}
%\setbeamercolor{titlelike}{fg=blackblue}


%%%%%%%%%%%%%%%%%%%%%%%
%% Other beamer options
% \setbeamercovered{transparent}
\setbeamercovered{invisible}
% Permet de laisser en gris le texte qui n'est pas encore apparu (lorsqu'on utilise les commandes avec des <1,2> ou <4-9>.

%\setbeamercolor{normal text}{fg=black,bg=white}

%%%%%%%%%%%%%%%%%%%%%%%
%% Change Beamer fonts
% \usefonttheme{default}
% \usefonttheme[onlymath]{serif}
\usefonttheme{serif}

\setbeamerfont{title}{family=\rm}
\setbeamerfont{titlelike}{family=\rm}
\setbeamerfont{frametitle}{family=\rm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% innertheme
%% rectangles circles inmargin rounded
% \useinnertheme{rounded}  % XXX My preference
\useinnertheme{circles}    % XXX

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% outertheme
%% infolines miniframes shadow sidebar smoothbars smoothtree split tree
%\useoutertheme{infolines}

%% No navigation symbol.
\setbeamertemplate{navigation symbols}{}
\beamertemplatenavigationsymbolsempty

% XXX Add a background image to the slides
% \usepackage{tikz}
% \setbeamertemplate{background}{\includegraphics[width=\paperwidth,height=\paperheight,keepaspectratio]{IETR.jpg}}
% \setbeamertemplate{background}{{\centering\begin{tikzpicture}\node[opacity=0.15]{\includegraphics[width=0.98\paperwidth]{IETR_et_partenaires_IETR.png}};\end{tikzpicture}}}

% Other options
%\setbeamertemplate{footline}[page number]

\beamertemplateballitem
\setbeamertemplate{itemize item}[square]


\setbeamertemplate{caption}[numbered]
\setbeamertemplate{caption label separator}{: }
\setbeamercolor{caption name}{fg=normal text.fg}
\beamertemplatenavigationsymbolsempty
\usepackage{lmodern}
\usepackage{color}
  \newcommand{\urlb}[1]{\textcolor{blue}{\url{#1}}}
%% Color definition
\usepackage{xcolor}
%% WARNING attention when changing the colors, change both the {RGB}{r,g,b} ets séquencnaires(r,g,b)
\definecolor{blackblue}{RGB}{19,19,59}     % rgb(48,48,150)
\definecolor{bleu}{RGB}{0,0,204}           % rgb(0,0,204)
\definecolor{deeppurple}{RGB}{102,0,204}   % rgb(102,0,204)
\definecolor{darkgreen}{RGB}{0,100,0}      % rgb(0,100,0)
\definecolor{yellowgreen}{RGB}{200,215,0}  % rgb(200,215,0)
\definecolor{bluegreen}{RGB}{0,185,140}    % rgb(0,185,140)
\definecolor{lightgold}{RGB}{255,180,0}    % rgb(255,180,0)
\definecolor{gold}{RGB}{175,100,0}         % rgb(175,100,0)
\definecolor{strongred}{RGB}{255,0,0}      % rgb(255,0,0)
\definecolor{normalred}{RGB}{204,0,0}      % rgb(204,0,0)
\definecolor{darkred}{RGB}{174,0,0}        % rgb(174,0,0)
\definecolor{darkblue}{RGB}{0,0,174}       % rgb(0,0,174)
\definecolor{darkpurple}{RGB}{114,0,114}   % rgb(114,0,114)

\usepackage{amssymb,amsmath}
\usepackage{bbm,bm}  % bold maths symbols
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript

% % FIXME remove as soon as possible, it slows down compilation to import TikZ
% %% TikZ
% \usepackage{tikz}
% \usetikzlibrary{snakes,arrows,shapes}
% % https://tex.stackexchange.com/a/226974/
% \tikzset{
%   font={\fontsize{10pt}{10}\selectfont}
% }
\usepackage{tikzsymbols}  % https://tex.stackexchange.com/a/227226/97964

\IfFileExists{macrosText.sty}{\usepackage{macrosText}}{}

% For algorithms
\usepackage[linesnumbered,commentsnumbered,inoutnumbered,slide]{algorithm2e}


\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\newif\ifbibliography
\hypersetup{
            pdfborder={0 0 0},
            breaklinks=true}
% \urlstyle{same}  % don't use monospace font for urls
% Code embedding.
\usepackage{palatino}              % Use the Palatino font % XXX remove if it is ugly ?
\usepackage{graphicx,grffile}
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi}
\def\maxheight{\ifdim\Gin@nat@height>\textheight0.8\textheight\else\Gin@nat@height\fi}
\makeatother
% Scale images if necessary, so that they will not overflow the page
% margins by default, and it is still possible to overwrite the defaults
% using explicit options in \includegraphics[width, height, ...]{}
\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio}

\ifxetex
\usepackage{fontspec}
\setmainfont[Ligatures=Historic]{TeX Gyre Pagella}
\newfontfamily\FiraCode{Fira Code}
\setmonofont[Contextuals={Alternate}]{Fira Code}
\newfontfamily\Fontify[Path = ../common/]{Fontify-Regular}
\else
\newcommand{\Fontify}{}
\fi

% Prevent slide breaks in the middle of a paragraph:
\widowpenalties 1 10000
\raggedbottom

% \AtBeginPart{
%   \let\insertpartnumber\relax
%   \let\partname\relax
%   \frame{\partpage}
% }
% \AtBeginSection{
%   \ifbibliography
%   \else
%     \let\insertsectionnumber\relax
%     \let\sectionname\relax
%     \frame{\sectionpage}
%   \fi
% }
% % Si on veut faire apparaître le sommaire courant à chaque nouvelle section.
% \AtBeginSection{
%   \begin{frame}<beamer>%[t]
%   %\frametitle{Local outline}  % Translate the name of the slide
%   \frametitle{\hspace{0pt}}  % Translate the name of the slide
%     \begin{LARGE}  % XXX LARGE font for this slide?
%     \tableofcontents[currentsection, sectionstyle=show/hide, subsectionstyle=hide/hide]
%     \end{LARGE}  % XXX LARGE font for this slide?
%   \end{frame}
% }
% \AtBeginSubsection{
%   \let\insertsubsectionnumber\relax
%   \let\subsectionname\relax
%   \frame{\subsectionpage}
% }

\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{5}

% https://tex.stackexchange.com/a/70495/
\usepackage{appendixnumberbeamer}


% For \justifying command, see https://tex.stackexchange.com/a/148696/
\usepackage{ragged2e}
\addtobeamertemplate{frame begin}{}{\justifying}
\addtobeamertemplate{block begin}{}{\justifying}
\addtobeamertemplate{block alerted begin}{}{\justifying}
\addtobeamertemplate{block example begin}{}{\justifying}
\addtobeamertemplate{itemize body begin}{}{\justifying}
\addtobeamertemplate{itemize item}{}{\justifying}
\addtobeamertemplate{itemize subitem}{}{\justifying}
\addtobeamertemplate{itemize subsubitem}{}{\justifying}
\addtobeamertemplate{enumerate body begin}{}{\justifying}
\addtobeamertemplate{enumerate item}{}{\justifying}
\addtobeamertemplate{enumerate subitem}{}{\justifying}
\addtobeamertemplate{enumerate subsubitem}{}{\justifying}
\addtobeamertemplate{description body begin}{}{\justifying}
\addtobeamertemplate{description item}{}{\justifying}


\title[Test BGLR et bandits non-stationnaires]{Analyse non asymptotique d'un test séquentiel de détection de ruptures et application aux bandits non stationnaires}
\subtitle{Conférence GRETSI @ Lille, Août 2019}

\author[Lilian Besson]{\Large \textbf{Lilian Besson}}

\institute[]{{\large
  Doctorant}{\newline
  % \normalsize
  \newline Équipe SCEE, labo IETR, CentraleSupélec à Rennes
  \newline \& Équipe SequeL, labo CRIStAL, Inria à Lille}}

\date{Jeudi $29$ Août $2019$}

\begin{document}
\justifying

\begin{frame}[plain]
  \titlepage

  % XXX manual inclusion of logos
  \begin{center}
    \includegraphics[height=0.15\textheight]{../common/LogoIETR.png}
    \includegraphics[height=0.17\textheight]{../common/LogoCS.png}
    \includegraphics[height=0.15\textheight]{../common/LogoInria.jpg}
  \end{center}

\end{frame}


% \begin{frame}{Publications associée à cet exposé}

%   Travaux en collaboration avec mon encadrante de thèse Émilie Kaufmann
%   \dInnocey{} :

%   \begin{itemize}
%     \item
%       \href{https://hal.inria.fr/hal-02006471/document}{\emph{``Analyse non asymptotique d'un test séquentiel de détection de ruptures et application aux bandits non stationnaires''}}\\
%       by \textbf{Lilian Besson} \&
%       \href{http://chercheurs.lille.inria.fr/ekaufman/research.html}{Émilie
%       Kaufmann}

%     \vspace*{30pt}

%     \item
%       \href{https://hal.inria.fr/hal-02006471/document}{\emph{``The Generalized Likelihood Ratio Test meets klUCB: an Improved Algorithm for Piece-Wise Non-Stationary Bandits''}}\\
%       by \textbf{Lilian Besson} \&
%       \href{http://chercheurs.lille.inria.fr/ekaufman/research.html}{Émilie
%       Kaufmann}\\
%       % February 2019,
%       Pre-print on
%       \href{https://hal.inria.fr/hal-02006471}{\textcolor{blue}{HAL-02006471}}
%       and
%       \href{https://arxiv.org/abs/1902.01575}{\textcolor{blue}{arXiv:1902.01575}}

%   \end{itemize}

% \end{frame}


% \section{\hfill{}Plan\hfill{}}

% \begin{frame}{Plan}

%   \begin{enumerate}
%     \item
%       Problèmes de bandits multi-bras (stationnaires)
%     \vspace*{15pt}

%     \item
%       Problèmes de bandits multi-bras stationnaires par morceaux
%     \vspace*{15pt}

%     \item
%       Le test BGLR et ses propriétés à horizon fini
%     \vspace*{15pt}

%     \item
%       L'algorithme B-GLRT + klUCB
%     \vspace*{15pt}

%     % \item
%     %   Analyse du regret
%     % \vspace*{15pt}

%     \item
%       Simulations numériques
%   \end{enumerate}

% \end{frame}


\section{\hfill{}1. Problèmes de bandits multi-bras (stationnaires)\hfill{}}

\begin{frame}{1. Problèmes de bandits multi-bras (stationnaires)}

  \begin{enumerate}
    \item
    \alert{\textbf{%
      Problèmes de bandits multi-bras (stationnaires)
    }}
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      Problèmes de bandits multi-bras stationnaires par morceaux
    }
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      Le test BGLR et ses propriétés à horizon fini
    }
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      L'algorithme B-GLRT + klUCB
    }
    \vspace*{15pt}

    % \item
    % \textcolor{gray}{
    %   Analyse du regret
    % }
    % \vspace*{15pt}

    \item
    \textcolor{gray}{
      Simulations numériques
    }
  \end{enumerate}

\end{frame}

\subsection{\hfill{}Qu'est-ce qu'un problème de bandits ?\hfill{}}


\begin{frame}{Bandits manchots ? ($=$ un bras)}

  Un autre nom pour une machine à sous :

  \begin{center}
    % \centering
    \includegraphics[height=0.60\textheight]{figures/Lucky_Luke__Le_Bandit_Manchot.jpg}
  \end{center}

  \begin{tiny}
  $\hookrightarrow$ Source
    \href{https://www.dargaud.com/bd/LUCKY-LUKE/Lucky-Luke/Lucky-Luke-tome-18-Bandit-manchot-Le}{\textcolor{blue}{Lucky Luke tome 18, \textcopyright{} Dargaud.}}
  \end{tiny}

\end{frame}


\begin{frame}{Bandits multi-bras}

  $=$ Prise de décisions séquentielles face à des environnements incertains :

  \begin{center}
    % \centering
    \includegraphics[height=0.65\textheight]{figures/example_of_a_5_arm_bandit_problem.png}
  \end{center}

  \begin{tiny}
  $\hookrightarrow$ Démo interactive
    \href{https://perso.crans.org/besson/phd/MAB_interactive_demo/}{\textcolor{blue}{\texttt{perso.crans.org/besson/phd/MAB\_interactive\_demo/}}}\\
    Réf : [Bandits Algorithms, Lattimore \& Szepesv{\'a}ri, 2019],
    sur \href{https://tor-lattimore.com/downloads/book/book.pdf}{\textcolor{blue}{\texttt{tor-lattimore.com/downloads/book/book.pdf}}}
  \end{tiny}

\end{frame}


\subsection{\hfill{}Modèle mathématique\hfill{}}

\begin{frame}{Modèle mathématique}

\begin{itemize}[<+->]
  \item
  Étapes de temps discret $t = 1, \dots, T$\\
  L'\emph{horizon} $T$ est fixé et généralement inconnu

  \item
  Au temps $t$, une joueuse \emph{choisit le bras} $A(t)\in\{1,\dots,K\}$,\\
  et elle observe \emph{une récompense aléatoire iid} : $r(t) \sim \nu_k$, $r(t)\in\mathbb{R}$

  \item
  On se restreint souvent à des bras de Bernoulli $\nu_k = \mathcal{B}(\mu_k)$, de moyenne $\mu_k\in[0,1]$,
  qui donnent des récompenses binaires $r(t) \in\{0,1\}$.

  \item
  \textbf{But} : maximiser la somme des récompenses $\sum\limits_{t=1}^T r(t)$

  \item
  ou \alert{maximiser la somme des récompenses \emph{moyennes} $\mathbb{E}\left[ \sum\limits_{t=1}^T r(t) \right]$}

  \item
  Une stratégie efficace doit résoudre le \alert{compromis entre exploration et exploitation} :
  explorer tous les bras pour découvrir le meilleur,
  tout en exploitant le meilleur bras courant.
\end{itemize}

\end{frame}


% \subsection{\hfill{}Naive solutions\hfill{}}

% \begin{frame}{Two examples of bad solutions}

%   \begin{exampleblock}{$i)$ Pure exploration \dXey{}}
%     \begin{itemize}
%       \item
%       Play arm $A(t) \sim \mathcal{U}(\{1,\dots,K\})$ uniformly at random
%       \item
%       $\implies$ Mean expected rewards
%       $ \frac{1}{T} \mathbb{E}\left[ \sum\limits_{t=1}^T r(t) \right] = \frac{1}{K} \sum\limits_{k=1}^K \mu_k \ll \max_k \mu_k$
%     \end{itemize}
%   \end{exampleblock}

%   \pause

%   \begin{exampleblock}{$ii)$ Pure exploitation \dXey{}}
%     \begin{itemize}
%       \item
%         Count the number of samples and the sum of rewards of each arm $N_k(t) = \sum\limits_{s < t} \mathbbm{1}(A(s)=k)$ and $X_k(t) = \sum\limits_{s < t} r(s) \mathbbm{1}(A(s)=k)$
%       \item
%         Estimate the \alert{unknown} mean $\mu_k$ with $\widehat{\mu_k}(t) = X_k(t) / N_k(t)$
%       \item
%         Play the arm of maximum empirical mean : $A(t) = \arg\max_k \widehat{\mu_k}(t)$
%       \item
%         Performance depends on the first draws, and can be very poor!
%     \end{itemize}
%   \end{exampleblock}
%   \vspace*{-10pt}
%   \begin{tiny}
%     $\hookrightarrow$
%     Interactive demo
%     \href{https://perso.crans.org/besson/phd/MAB_interactive_demo/}{\textcolor{blue}{\texttt{perso.crans.org/besson/phd/MAB\_interactive\_demo/}}}
%   \end{tiny}

% \end{frame}


% \subsection{\hfill{}The \emph{``Upper Confidence Bound''} algorithm\hfill{}}

% \begin{frame}{A first solution: \emph{``Upper Confidence Bound''} algorithm}

%   \begin{itemize}
%     \item
%       Compute $\mathrm{UCB}_k(t) = X_k(t) / N_k(t) + \sqrt{\alpha \log(t) / N_k(t)}$\\
%       $=$ an \alert{upper confidence bound} on the \alert{unknown} mean $\mu_k$
%     \item
%       Play the arm of maximal UCB : $A(t) = \arg\max_k \mathrm{UCB}_k(t)$
%       \\
%       $\hookrightarrow$ Principle of ``optimism under uncertainty''
%     \item
%       $\alpha$ balances between \emph{exploitation} ($\alpha\to0$) and \emph{exploration}  ($\alpha\to\infty$)

%     \pause

%     \item
%       \alert{UCB is efficient}:
%       the best arm is identified correctly (with high probability)
%       if there are enough samples (for $T$ large enough)
%     \item
%       $\implies$
%       Expected rewards attains the maximum \dLaughey{}
%       \[ \text{For~} T\to\infty, \;\;\; \frac{1}{T} \mathbb{E}\left[ \sum\limits_{t=1}^T r(t) \right] \to \max_k \mu_k \]
%   \end{itemize}
% \end{frame}

% \begin{frame}{UCB algorithm converges to the best arm}

%   We can prove that suboptimal arms $k$ are sampled about $o(T)$ times\\
%   $\implies \mathbb{E}\left[ \sum\limits_{t=1}^T r(t) \right] \underset{T\to\infty}{\to} \textcolor{deeppurple}{\mu^*} \times \mathcal{O}(T) + \sum\limits_{k: \Delta_k>0} \mu_k \times o(T)$
%   \dLaughey{}

%   \alert{But\ldots{} at which speed do we have this convergence?}

%   \begin{block}{Elements of proof of convergence (for $K$ Bernoulli arms)}
%     \begin{small}
%       \begin{itemize}
%         \item
%           Suppose the first arm is the best:
%           $\textcolor{deeppurple}{\mu^*} = \textcolor{deeppurple}{\mu_1} > \mu_2 \geq \ldots \geq \mu_K$
%         \item
%           $\mathrm{UCB}_k(t) = X_k(t) / N_k(t) + \sqrt{\alpha \log(t) / N_k(t)}$
%         \item
%           Hoeffding's inequality gives
%           $\mathbb{P}(\mathrm{UCB}_k(t) < \mu_k(t)) \leq \mathcal{O}(\frac{1}{t^{2 \alpha}})$\\
%           $\implies$ the different $\mathrm{UCB}_k(t)$ are true ``Upper Confidence Bounds'' on the (unknown) $\mu_k$ (most of the times)
%         \item
%           And if a suboptimal arm $k>\textcolor{deeppurple}{1}$ is sampled, it implies
%           $\mathrm{UCB}_k(t) > \mathrm{UCB}_{\textcolor{deeppurple}{1}}(t)$, but $\mu_k < \textcolor{deeppurple}{\mu_1}$:
%           Hoeffding's inequality also proves that any ``wrong ordering'' of the $\mathrm{UCB}_k(t)$ is unlikely
%         \end{itemize}
%       \end{small}
%     \end{block}

% \end{frame}


\subsection{\hfill{}Regret d'un algorithme de bandit\hfill{}}

\begin{frame}{Mesurer la performance d'un algorithme $\mathcal{A}$ par son regret moyen $R_{\mathcal{A}}(T)$}

\begin{itemize}[<+->]
  \item
  Différence entre les récompenses accumulées par un ``oracle'' et $\mathcal{A}$

  \item
  L'algorithme ``oracle'' joue toujours \textcolor{deeppurple}{le meilleur bras (inconnu) $k^* = \arg\max_k \mu_k$} (la meilleure moyenne est notée \textcolor{deeppurple}{$\mu_{k^*} = \mu^*$})

  \item
  But équivalent : maximiser la somme des récompenses moyennes
  $\Longleftrightarrow$ \alert{minimiser le regret moyen}
  %
  \[ \alert{ R_{\mathcal{A}}(T) } = \mathbb{E}\left[ \sum\limits_{t=1}^T \textcolor{deeppurple}{r_{k^*}}(t) \right] - \sum\limits_{t=1}^T \mathbb{E}\left[ r(t) \right] = T \textcolor{deeppurple}{\mu^*} - \sum\limits_{t=1}^T \mathbb{E}\left[ r(t) \right]. \]

\end{itemize}

\pause
\vspace*{10pt}

\begin{exampleblock}{Régime typique pour des bandits stationnaires (bornes inf \& sup)}
  \begin{itemize}
  \item
  Aucun algorithme $\mathcal{A}$ ne peut atteindre un regret meilleur que
  \hfill{}
  $R_{\mathcal{A}}(T) \geq \Omega(\log(T))$

  \item
  Et un algorithme efficace $\mathcal{A}$ obtient
  \hfill{}
  $R_{\mathcal{A}}(T) \leq \mathcal{O}(\log(T))$
  \end{itemize}
\end{exampleblock}

\end{frame}

% \subsection{\hfill{}Regret de deux algorithmes de type UCB\hfill{}}

% \begin{frame}{Regret des algorithmes UCB et kl-UCB}

%   Pour n'importe quel problème avec $K$ bras de Bernoulli, de moyennes $\mu_1,\dots,\mu_K \in[0,1]$, et de \textcolor{deeppurple}{bras optimal $\mu^*$} :

%   \begin{exampleblock}{Pour l'algorithme UCB}
%     \begin{small}
%       \[ R_T^{\mathrm{UCB}} \leq \sum_{\substack{k=1,\dots,K \\ \mu_k < \textcolor{deeppurple}{\mu^*}}} \frac{8}{(\mu_k - \textcolor{deeppurple}{\mu^*})} \log(T) + o(\log(T)). \]
%     \end{small}%
%   \end{exampleblock}

%   \begin{exampleblock}<2->{Pour l'algorithme kl-UCB : une meilleure borne}
%     \begin{small}
%       \[ R_T^{\mathrm{kl}\text{-}\mathrm{UCB}} \leq \sum_{\substack{k=1,\dots,K \\ \mu_k < \textcolor{deeppurple}{\mu^*}}} \frac{(\mu_k - \textcolor{deeppurple}{\mu^*})}{\mathrm{kl}(\textcolor{deeppurple}{\mu^*}, \mu_k)} \log(T) + o(\log(T)) = \mathcal{O}( \alert{\underbrace{C(\mu_1,\dots,\mu_K)}_{\text{Difficulté du problème}}} \log(T) ). \]
%     \end{small}%
%     \begin{footnotesize}
%       Avec $\mathrm{kl}(x, y) = x \log(x/y) + (1-x) \log((1-x)/(1-y))$ l'\emph{entropie binaire relative}\\
%       (\emph{ie}, la divergence de Kullback-Leibler de deux lois de Bernoulli de moyennes $x$ et $y$)
%     \end{footnotesize}%
%   \end{exampleblock}

% \end{frame}


\section{\hfill{}2. Problèmes de bandits multi-bras stationnaires par morceaux\hfill{}}

\begin{frame}{2. Bandits stationnaires par morceaux}

  \begin{enumerate}
    \item
    \textcolor{gray}{
      Problèmes de bandits multi-bras (stationnaires)
    }
    \vspace*{15pt}

    \item
    \alert{\textbf{%
      Problèmes de bandits multi-bras stationnaires par morceaux
    }}
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      Le test BGLR et ses propriétés à horizon fini
    }
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      L'algorithme B-GLRT + klUCB
    }
    \vspace*{15pt}

    % \item
    % \textcolor{gray}{
    %   Analyse du regret
    % }
    % \vspace*{15pt}

    \item
    \textcolor{gray}{
      Simulations numériques
    }
  \end{enumerate}

\end{frame}


\begin{frame}{Problèmes de bandits non stationnaires}

  \begin{block}{Problèmes de bandits stationnaires}
    Le bras $k$ tire une récompense selon \textcolor{blue}{la même distribution} pour chaque instant :\\
    $\forall t, r_k(t) \overset{\text{iid}}{\sim} \nu_k = \mathcal{B}(\mu_k)$.
  \end{block}

  \pause
  \begin{alertblock}{Problèmes de bandits \emph{non} stationnaires}
    Le bras $k$ tire une récompense selon \alert{une distribution différente à chaque instant} :\\
    $\forall t, r_k(t) \overset{\text{iid}}{\sim} \nu_k\alert{(t)} = \mathcal{B}(\mu_k\alert{(t)})$.
  \end{alertblock}

  $\implies$ \dXey{} problème plus difficile !
  Et très difficile si $\mu_k(t)$ peut changer n'importe quand !

  \pause
  \begin{block}{Problèmes de bandits \textbf{stationnaires par morceaux}}
    $\hookrightarrow$ on se concentre sur le cas où il y a au plus $o(\sqrt{T})$ intervalles sur lesquels les moyennes sont toutes stationnaires (= \textbf{séquences})
  \end{block}
\end{frame}

\subsection{\hfill{}Définitions\hfill{}}

\begin{frame}{Ruptures et séquences stationnaires}

  On définit

  \begin{itemize}
    \item
    Le nombre de rupture
    $\Upsilon_T = \sum\limits_{t=1}^{T-1} \mathbbm{1}(\exists k\in \{1,\dots,K\}$ $:$ $\mu_k(t) \neq \mu_k(t+1) )$

    \item
    Le $i$ème point d'arrêt
    $\tau^{i} = \inf\{t > \tau^{i-1} : \exists k : \mu_k(t) \neq \mu_k(t+1)\}$
    \hfill{} (avec $\tau^0=0$)
  \end{itemize}

  \begin{block}<2->{\textbf{Hypothèses} sur les problèmes stationnaires par morceaux (p.m.)}
    \begin{itemize}\tightlist
      \item Les récompenses $r_k(t)$ générées par chaque bras $k$ sont \alert{\emph{iid} sur chaque intervale} $[ \tau^{i} + 1, \tau^{i+1} ]$ (la $i$ème séquence)
      \item Il y a $\Upsilon_T = o(\sqrt{T})$ ruptures
      \item Et \alert{$\Upsilon_T$ peut être connu à l'avance}
      \item Les séquences sont toutes ``assez longues``
  \end{itemize}
\end{block}
\end{frame}


\begin{frame}[plain]{Exemple d'un problème de bandits stationnaire p.m.}
  On affiche les moyennes \textcolor{red}{$\mu_1(t)$}, \textcolor{green}{$\mu_2(t)$}, \textcolor{blue}{$\mu_3(t)$}
  des $K=3$ bras.\\
  Il y a $\Upsilon_T=4$ ruptures, et $5$ séquences entre $t=1$ et $T=5000$ :
  \begin{center}
    \includegraphics[width=1.00\textwidth]{figures/Problem_1.pdf}
  \end{center}
\end{frame}


\subsection{\hfill{}Étendre la définition du regret\hfill{}}

\begin{frame}{Regret pour les bandits stationnaires par morceaux ?}

  L'algorithme ``oracle'' joue le meilleur bras (inconnu) $k^*(t) = \arg\max \mu_k(t)$
  (qui change entre chaque séquence stationnaire)
  %
  \[ \alert{ R_{\mathcal{A}}(T) } = \mathbb{E}\left[ \sum\limits_{t=1}^T r_{\alert{k^*(t)}}(t) \right] - \sum\limits_{t=1}^T \mathbb{E}\left[ r(t) \right] = \left(\alert{\sum_{t=1}^T \max_k \mu_k(t)} \right) - \sum\limits_{t=1}^T \mathbb{E}\left[ r(t) \right]. \]

\pause
\vspace*{10pt}

\begin{exampleblock}{Régimes typiques pour les bandits stationnaires par morceaux}
  \begin{itemize}
  \item
  La borne inférieure est
  $R_{\mathcal{A}}(T) \geq \Omega(\sqrt{K T \Upsilon_T})$

  \item
  Actuellement, les meilleurs algorithmes $\mathcal{A}$  obtiennent
    \begin{itemize}\tightlist
      \item
      $R_{\mathcal{A}}(T) \leq \mathcal{O}(K \sqrt{T \Upsilon_T \log(T)})$
      si $T$ et $\Upsilon_T$ sont connus
      \item
      $R_{\mathcal{A}}(T) = \mathcal{O}(K \alert{\Upsilon_T} \sqrt{T \log(T)})$
      si $T$ et $\Upsilon_T$ sont inconnus
    \end{itemize}
  \end{itemize}
\end{exampleblock}

\end{frame}


\section{\hfill{}3. Le test BGLR et ses propriétés à horizon fini\hfill{}}

\begin{frame}{3. Le test BGLR et ses propriétés à horizon fini}

  \begin{enumerate}
    \item
    \textcolor{gray}{
      Problèmes de bandits multi-bras (stationnaires)
    }
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      Problèmes de bandits multi-bras stationnaires par morceaux
    }
    \vspace*{15pt}

    \item
    \alert{\textbf{%
      Le test BGLR et ses propriétés à horizon fini
    }}
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      L'algorithme B-GLRT + klUCB
    }
    \vspace*{15pt}

    % \item
    % \textcolor{gray}{
    %   Analyse du regret
    % }
    % \vspace*{15pt}

    \item
    \textcolor{gray}{
      Simulations numériques
    }
  \end{enumerate}

\end{frame}


\subsection{\hfill{}Détection de rupture\hfill{}}

\begin{frame}{Le problème de détection de rupture}

  Imaginez le jeu suivant\ldots

  \begin{itemize}
    \item Vous observez des données $X_1,X_2,\cdots,X_t,\cdots \in[0,1]$\ldots
    \item Vous savez que $X_t$ est généré par une certaine distribution \alert{inconnue}\ldots

    \pause
    \item \alert{Votre but} est de distinguer entre deux hypothèses :
    \begin{itemize}
      \item[\textcolor{deeppurple}{$\mathcal{H}_0$}] \textcolor{deeppurple}{Les distributions \textbf{ont toutes la même moyenne} \hfill{} (``pas de rupture'')\\
      $\exists \mu_0, \mathbb{E}[X_1] = \mathbb{E}[X_2] = \cdots = \mathbb{E}[X_t] = \mu_0$}

      \item[\textcolor{gold}{$\mathcal{H}_1$}] \textcolor{gold}{Les distributions ont \textbf{changé de moyennes au temps $\tau$} \\
      $\exists \mu_0, \mu_1, \tau, \mathbb{E}[X_1] = \cdots = \mathbb{E}[X_{\tau}] = \mu_0, \; \mu_0 \neq \mu_1, \; \mathbb{E}[X_{\tau+1}] = \mathbb{E}[X_{\tau+2}] = \cdots = \mu_1$}
      % $\exists \mu_0, \mu_1, \exists \tau, \forall t \leq \tau, \mathbb{E}[X_t] = \mu_0 \text{ and } \forall t \geq \tau + 1, \mathbb{E}[X_t] = \mu_1$
    \end{itemize}
    \item Vous arrêtez au temps $\widehat{\tau}$, dès que vous détectez une rupture
  \end{itemize}

  \pause
  Un \alert{détecteur de rupture séquentiel} est un \alert{\textbf{temps d'arrêt $\widehat{\tau}$}},
  mesurable selon $\mathcal{F}_t = \sigma(X_1,\cdots,X_t)$,
  qui rejette l'hypothèse \textcolor{deeppurple}{$\mathcal{H}_0$}
  lorsque $\widehat{\tau} < \infty$.

\end{frame}


\subsection{\hfill{}Test de rapport de vraisemblances pour des données de Bernoulli\hfill{}}

\begin{frame}{Test de rapport de vraisemblances de Bernoulli}

  \textbf{Hypothèses} : toutes les distributions sont Bernoulli ($\nu_k = \mathcal{B}(\mu_k)$)

  Le problème se résume à distinguer
    \begin{itemize}
      \item[\textcolor{deeppurple}{$\mathcal{H}_0$}:]
      \textcolor{deeppurple}{$(\exists \mu_0 : \forall i\in\mathbb{N}^*, X_i \overset{\text{i.i.d.}}{\sim} \mathcal{B}(\mu_0))$},
      contre l'alternative
      \item[\textcolor{gold}{$\mathcal{H}_1$}:]
      \textcolor{gold}{$(\exists \mu_0 \neq \mu_1, \tau > 1 : X_1, \cdots, X_\tau \overset{\text{i.i.d.}}{\sim} \mathcal{B}(\mu_0) \text{~et~} X_{\tau+1}, \cdots \overset{\text{i.i.d.}}{\sim} \mathcal{B}(\mu_1))$}.
    \end{itemize}

  \pause

  Après avoir observé $X_1,\cdots,X_n$, la statistique du \alert{test de rapport de vraisemblances} pour cette hypothèse est
  \begin{small}
    \[ \mathcal{L}(n) = \frac{\sup\limits_{\textcolor{gold}{\mu_0,\mu_1,\tau < n}}\ell(X_1,\cdots,X_n ; \textcolor{gold}{\mu_0,\mu_1,\tau})}{\sup\limits_{\textcolor{deeppurple}{\mu_0}}\ell(X_1,\cdots,X_n ;\textcolor{deeppurple}{\mu_0})},\]
  \end{small}

  où $\ell(X_1,\cdots,X_n ; \textcolor{deeppurple}{\mu_0})$ et $\ell(X_1,\cdots,X_n ; \textcolor{gold}{\mu_0,\mu_1,\tau})$ sont les vraisemblances des observations selon les modèles \textcolor{deeppurple}{$\mathcal{H}_0$} et \textcolor{gold}{$\mathcal{H}_1$}.

  \pause

  \alert{$\hookrightarrow$ De grandes valeurs de $\mathcal{L}(n)$ tendent à rejeter \textcolor{deeppurple}{$\mathcal{H}_0$} en faveur de \textcolor{gold}{$\mathcal{H}_1$}.}

\end{frame}

\begin{frame}{(log) Rapport de vraisemblances de Bernoulli}

  On peut réécrire cette statistique
  $\mathcal{L}(n) = \frac{\sup\limits_{\textcolor{gold}{\mu_0,\mu_1,\tau < n}}\ell(X_1,\cdots,X_n ; \textcolor{gold}{\mu_0,\mu_1,\tau})}{\sup\limits_{\textcolor{deeppurple}{\mu_0}}\ell(X_1,\cdots,X_n ;\textcolor{deeppurple}{\mu_0})}$,
  en utilisant les vraisemblances de Bernoulli, et les moyennes glissantes $\widehat{\mu}_{k:k'} = \frac{1}{k'-k+1} \sum\limits_{s=k}^{k'} X_s$ :

  \begin{align*}
    \log \mathcal{L}(n) = \alert{\max_{s \in \{1,\cdots,n-1\}}} \bigl[
      & s \times \mathrm{kl} (\underbrace{\widehat{\mu}_{1:s}}_{\text{avant rupture}},\underbrace{\widehat{\mu}_{1:n}}_{\text{tout}} ) \\
      + & (n-s) \times \mathrm{kl} (\underbrace{\widehat{\mu}_{s+1:n}}_{\text{après rupture}},\underbrace{\widehat{\mu}_{1:n}}_{\text{tout}} ) \bigr].
  \end{align*}

  \begin{small}
    \textcolor{gray}{Où $\mathrm{kl}(x,y) =x \ln\bigl(\frac{x}{y}\bigr) + (1-x)\ln\bigl(\frac{1-x}{1-y}\bigr)$ est l'entropie relative binaire}
  \end{small}

\end{frame}


\subsection{\hfill{}Le B-GLRT\hfill{}}

\begin{frame}{Le test généralisé de rapport de vraisemblances de Bernoulli (B-GLRT)}

  \begin{itemize}
    \item
    On peut étendre ce test si les observations sont \alert{sous-Bernoulli}.\\
    (fonction génératrice $\phi$ des moments bornée par celle d'une loi de Bernoulli $\phi_{\mathcal{B}}$)
    \item
    Et toute distribution à support borné dans $[0,1]$ est sous-Bernoulli !
    \item
    $\implies$ le test B-GLR peut être appliqué à n'importe quelles observations bornées \dCooley{}
  \end{itemize}

  % \begin{block}{Sub-Bernoulli distributions}
  %   If $\nu$ is supported in $[0,1]$,
  %   $\nu$ is \emph{sub-Bernoulli} if it verifies
  %   $\mathbb{E}_{X\sim\nu}\left[e^{\lambda X}\right] \leq  1-\mu + \mu e^\lambda = \mathbb{E}_{X\sim \mathcal{B}(\mu)} [e^{\lambda X}]$.
  %   % where $\mathcal{B}(\mu)$ est la loi de Bernoulli de moyenne $\mu$.
  % \end{block}

  \pause

  \begin{block}{Le test de détection séquentielle de rupture B-GRLT}
    Le \alert{B-GLRT} est le temps d'arrêt définit par
    \begin{small}
    \[ \widehat{\tau}_{\delta} = \inf \bigl\{ n \in \mathbb{N}^* : \max_{s \in \{1,\cdots,n-1\}} \bigl[s \, \mathrm{kl}\left(\widehat{\mu}_{1:s},\widehat{\mu}_{1:n}\right) + (n-s) \, \mathrm{kl}\left(\widehat{\mu}_{s+1:n},\widehat{\mu}_{1:n}\right)\bigr] \geq \beta(n,\delta) \bigr\} \]
    \vspace*{-10pt}
    \end{small}%
    \begin{itemize}\tightlist
      \item avec une \alert{function seuil} $\beta(n,\delta)$ spécifiée plus tard,
      \item $n$ est le nombre d'observations ($X_1,\dots,X_n$),
      \item $\delta$ est le niveau de confiance ($\delta\in(0,1)$).
    \end{itemize}%
  \end{block}

\end{frame}


\subsection{\hfill{}Fausse alarme\hfill{}}

\begin{frame}{Probabilité de fausse alarme}

  Un bon test ne doit pas détecter de rupture s'il n'y a pas de rupture à détecter\ldots

  \pause
  \begin{block}{Définition : fausse alarme}
    Le temps d'arrêt est $\widehat{\tau}_\delta$,
    et une rupture est détectée si $\widehat{\tau}_\delta < \infty$.

    Soit $\mathbb{P}_{\textcolor{deeppurple}{\mu_0}}$ un modèle de probabilité selon lequel les observations sont $\forall t, X_t \in[0,1]$
    et \textcolor{deeppurple}{$\forall t, \mathbb{E}[X_t] = \mu_0$}.

    La \alert{probabilité de fausse alarme} est $\mathbb{P}_{\textcolor{deeppurple}{\mu_0}}(\widehat{\tau}_\delta < \infty)$.
  \end{block}

  \alert{$\implies$ But : contrôler l'événement de fausse alarme !} (en forte proba)

\end{frame}

\begin{frame}{Premier résultat pour le test BGLR \dSmiley{}}

  \begin{block}{Contrôler la probabilité de fausse alarme}
    Pour n'importe quel \alert{niveau de confiance} $0<\delta<1$,
    le test BGLR satisfait
    \[ \mathbb{P}_{\textcolor{deeppurple}{\mu_0}}(\widehat{\tau}_\delta < \infty) \leq \delta \]
    avec la fonction seuil
    \begin{small}
      \[ \beta(n,\delta) = \textcolor{gray}{2\,\mathcal{T}\left(\frac{\ln(3n\sqrt{n}/\delta)}{2}\right) + 6\ln(1+\ln(n))} \simeq \ln\left(\frac{3n \sqrt{n}}{\delta}\right) = \mathcal{O}\left(\log\left(\frac{n}{\delta}\right)\right).\]
    \end{small}
    \begin{footnotesize}
      \textcolor{gray}{Où $\mathcal{T}(x)$ vérifie $\mathcal{T}(x)\simeq x + \ln(x)$ pour $x$ assez grand}
    \end{footnotesize}
  \end{block}


  \begin{small}
    \begin{exampleblock}<2>{Preuve ?}
      Voir la version longue de notre article
      \href{https://hal.inria.fr/hal-02006471}{\textcolor{blue}{HAL-02006471}}
      et
      \href{https://arxiv.org/abs/1902.01575}{\textcolor{blue}{arXiv:1902.01575}}
    \end{exampleblock}
  \end{small}

\end{frame}

\subsection{\hfill{}Délai de détection\hfill{}}

\begin{frame}{Délai de détection}

  Un bon test devrait détecter une rupture ``assez vite'' s'il y a une rupture à détecter, avec assez d'échantillons avant la rupture\ldots

  \pause
  \begin{block}{Definition : délai de détection}
    Soit $\mathbb{P}_{\textcolor{gold}{\mu_0,\mu_1,\tau}}$ un modèle de probabilité selon lequel $\forall t, X_t \in[0,1]$ et \textcolor{gold}{$\forall t \leq \tau, \mathbb{E}[X_t] = \mu_0$ et $\forall t \geq \tau + 1, \mathbb{E}[X_t] = \mu_1$,
    avec $\mu_0 \neq \mu_1$}.

    L'\alert{écart} de cette rupture est $\Delta = |\mu_0 - \mu_1|$.

    Le \alert{délai de détection} est définit par $u = \widehat{\tau}_{\delta} - \tau \in\mathbb{N}$.
  \end{block}

  \alert{$\implies$ But : contrôler le délai de détection!} (en forte probabilité)

\end{frame}

\begin{frame}{Second résultat pour le test BGLR \dSmiley{}}

  \begin{block}{Contrôler le délai de détection}
      Pour une rupture d'amplitude $\Delta = |\mu_1 - \mu_0|$,
      le test BGLR satisfait
      \begin{small}
        \begin{align*}
            \mathbb{P}_{\textcolor{gold}{\mu_0,\mu_1,\tau}} (\widehat{\tau}_{\delta} \geq \textcolor{gold}{\tau} + u) &\leq \exp\left( -\frac{2\textcolor{gold}{\tau} u}{\textcolor{gold}{\tau} + u}\left(\max\left[ 0, \Delta - \sqrt{\frac{\textcolor{gold}{\tau} + u}{2\textcolor{gold}{\tau} u} \beta(\textcolor{gold}{\tau} + u,\delta)} \right]\right)^2 \right) \\
            &= \mathcal{O}(\text{décroissance exponentielle en~} u)
            = \mathcal{O}(\exp\searrow(u)).
        \end{align*}
      \end{small}
      avec la même fonction de seuil
      $\beta(n,\delta) \simeq \ln(3n \sqrt{n}/\delta)$.
  \end{block}

  \begin{exampleblock}{Conséquence}
    En forte probabilité, \alert{le délai $\widehat{\tau}_\delta$ du BGLR est borné} par $\mathcal{O}(\Delta^{-2} \ln(1/\delta))$ \alert{si assez d'échantillons sont observés avant la rupture} au temps $\tau$.
    % (at least $\mathcal{O}(\Delta^{-2} \ln(1/\delta))$ samples.
    % the detection delay of BGLR has the same magnitude.
  \end{exampleblock}

\end{frame}


\subsection{\hfill{}Résumé des résultats du B-GLRT\hfill{}}

\begin{frame}{BGLR est un test de détection de rupture efficace \dCooley{} !}

  \begin{itemize}
    \item
    On a vu qu'en choisissant
    \begin{itemize}\tightlist
      \item
      un niveau de confiance $\delta$,
      \item
      et une bonne fonction de seuil $\beta(n,\delta) \simeq \ln(3n \sqrt{n}/\delta) = \mathcal{O}(\log(n/\delta))$,
    \end{itemize}
    \pause
    \item
    on peut contrôler les deux propriétés du test BGLR :
    \begin{itemize}\tightlist
      \item
        sa \alert{probabilité de fausse alarme} :
        $\mathbb{P}_{\textcolor{darkpurple}{\mu_0}}(\widehat{\tau}_\delta < \infty) \leq \delta$,
      \item
        son \alert{délai de détection} :
        $\mathbb{P}_{\textcolor{gold}{\mu_0,\mu_1,\tau}} (\widehat{\tau}_{\delta} \geq \tau + u)$ décroît exponentiellement rapidement en $u$
        (s'il y a assez d'observations avant et après la rupture).
    \end{itemize}

    \item
    $\implies$ Le test BGLR détecte les ruptures efficacement \dCooley{}
  \end{itemize}

  \pause
  \begin{block}{Garanties non asymptotiques \dCooley{} \hfill{} \tiny{\textcolor{gray}{[Maillard, ALT, 2019]} \textcolor{gray}{[Lai \& Xing, Sequential Analysis, 2010]}}}
    De telles garanties \alert{non asymptotiques} sont des résultats assez récents !
  \end{block}

\end{frame}

\section{\hfill{}4. L'algorithme B-GLRT + klUCB\hfill{}}

\begin{frame}{4. L'algorithme B-GLRT + klUCB}

  \begin{enumerate}
    \item
    \textcolor{gray}{
      Problèmes de bandits multi-bras (stationnaires)
    }
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      Problèmes de bandits multi-bras stationnaires par morceaux
    }
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      Le test BGLR et ses propriétés à horizon fini
    }
    \vspace*{15pt}

    \item
    \alert{\textbf{%
      L'algorithme B-GLRT + klUCB
    }}
    \vspace*{15pt}

    % \item
    % \textcolor{gray}{
    %   Analyse du regret
    % }
    % \vspace*{15pt}

    \item
    \textcolor{gray}{
      Simulations numériques
    }
  \end{enumerate}

\end{frame}

\subsection{\hfill{}Le test BGRL + les indices kl-UCB\hfill{}}

\begin{frame}{On combine le test BGRL + les indices kl-UCB}

  \begin{block}{Idées principales}
    \begin{itemize}
      % \item Forced uniform random exploration with probability $\alpha$
      \item Calculer un indice UCB sur chaque bras $k$ (Borne Sup. Confiance)
        % $\mbox{kl-UCB}_k(t)$
      \item Presque tout le temps, jouer le bras $A(t) = \arg\max\limits_{k\in \{1,\dots,K\}} \mbox{kl-UCB}_k(t)$
      \item Utiliser le test BGLR \alert{pour détecter les ruptures sur le bras joué}
      \item Si une rupture est détectée, \alert{effacer la mémoire des observations de \emph{tous les} bras}
    \end{itemize}
  \end{block}

  \pause

  \begin{exampleblock}{Les indices kl-UCB}
    \begin{itemize}
      \item $\tau_k(t)$ est le temps depuis le dernier redémarrage du bras $k$,
      % avant le temps $t$,
      \item $n_k(t)$ compte les sélections et $\widehat{\mu}_k(t)$ est la moyenne empirique des observations du bras $k$ depuis $\tau_k(t)$,
      % = \sum\limits_{s=\tau_k(t)+1}^{t} \mathbbm{1}(A_s=k)$
      % la moyenne empirique des récompenses obtenues entre la dernière réinitialisation et l'instant $t$.
      %= (\sum_{s=\tau_i(t)+1}^{t}X_{i,s} \mathbbm{1}(A_s=i))/n_i(t)$ (si $n_i(t)\neq0$)
      \item Soit {\small $\mbox{kl-UCB}_k(t) = \max \bigl\{ q\in[0,1] : n_k(t) \times \mathrm{kl}\left(\widehat{\mu}_k(t),q\right) \leq f(t - \tau_k(t)) \bigr\}$ }
      \item $f(t) = \ln(t) + 3 \ln(\ln(t))$ contrôle l'amplitude de la Borne Sup. de Confiance (UCB).
    \end{itemize}
  \end{exampleblock}

\end{frame}

\begin{frame}{Deux détails sur notre algorithme}

  % % \GLRklUCB{} repose sur le calcul d'un \emph{indice} (de type \mathrm{kl}UCB{} \cite{KLUCBJournal}) pour chaque bras,  et choisit en général le bras d'indice le plus élevé.
  % Soit $\tau_i(t)$ l'instant de la dernière réinitialisation pour le bras $i$ avant le temps $t$, $n_i(t) = \sum_{s=\tau_i(t)+1}^{t} \mathbbm{1}(A_s=i)$ le nombre de sélections et $\widehat{\mu}_i(t)$
  % %= (\sum_{s=\tau_i(t)+1}^{t}X_{i,s} \mathbbm{1}(A_s=i))/n_i(t)$ (si $n_i(t)\neq0$)
  % la moyenne empirique des récompenses obtenues entre la dernière réinitialisation et l'instant $t$.

  % % L'indice du bras $i$ à l'instant $t$ est défini par
  % % $\UCB_i(t) = \max \bigl\{ q\in[0,1] : n_i(t) \times \mathrm{kl}\left(\widehat{\mu}_i(t),q\right) \leq f(t - \tau_i(t)) \bigr\}$ (l. $6$) avec la fonction d'exploration $f(t) = \ln(t) + 3 \ln(\ln(t))$.
  % % La détection d'une rupture sur le bras qui vient d'être joué
  % % produit une réinitialisation (l. $12$),

  \begin{exampleblock}{$i)$ Comment est utilisé le test BGLR ? \hfill{} (paramètre $\delta$)}
    Avec les observations $Z_1,\cdots,Z_n$
    % $\mbox{BGLRT}_\delta(Z_1,\dots,Z_n) = \mathrm{True}$
    on utilise le test BGLR pour détecter une rupture
    avec un niveau de confiance $\delta$
    quand
    % \begin{footnotesize}
      \[
        \sup_{1 \leq s \leq n-1} \left[s \times \mathrm{kl} \left( \widehat{Z}_{1:s}, \widehat{Z}_{1:n}\right) + (n-s) \times \mathrm{kl} \left( \widehat{Z}_{s+1:n}, \widehat{Z}_{1:n} \right) \right] \geq \beta(n,\delta)
        \]
    % \end{footnotesize}%
    % We use $\beta(n,\delta) \simeq \ln(3n^{3/2}/\delta)$
  \end{exampleblock}

  \pause

  \begin{exampleblock}{$ii)$ Exploration forcée \hfill{} (paramètre $\alpha$)}
    \begin{itemize}
      \item On utilise une exploration forcée sur tous les bras\ldots\\
        \emph{ie}, en moyenne, le bras $k$ est forcé à être joué au moins $T \times \alpha / K$ fois
      \item $\implies$ dans le but de pouvoir détecter les ruptures sur tous les bras
      \item et pas seulement sur le bras joué par les indices kl-UCB
      % (lignes $5$-$6$), qui assure que chaque bras est suffisamment échantillonné, afin que les ruptures puissent aussi être détectées sur les bras actuellement sous-échantillonnés par l'algorithme de bandit.
    \end{itemize}
  \end{exampleblock}

\end{frame}

\begin{frame}{L'algorithme \textcolor{gold}{BGLR} + \textcolor{deeppurple}{kl-UCB}}

\begin{columns}
\begin{column}{0.02\textwidth}
  %
\end{column}
\begin{column}{0.97\textwidth}
\begin{footnotesize}
  % Documentation at http://mirror.ctan.org/tex-archive/macros/latex/contrib/algorithm2e/doc/algorithm2e.pdf if needed
  % Or https://en.wikibooks.org/wiki/LaTeX/Algorithms#Typesetting_using_the_algorithm2e_package
  % \removelatexerror% Nullify \@latex@error % Cf. http://tex.stackexchange.com/a/82272/
  \begin{algorithm}[H]
      % XXX Options
      % \LinesNumbered  % XXX Option to number the line
      % \RestyleAlgo{boxed}
      % XXX Input, data and output
      \KwData{\emph{Paramètre du problème} : $T\in\mathbb{N}^*$, $K\in\mathbb{N}^*$}
      \KwData{\emph{Paramètre} : $\alpha \in (0, 1)$, $\delta>0$ \tcp*[f]{peut utiliser $T$ et $\Upsilon_T$}}
      % \KwData{\emph{Option} : redémarrages \textbf{Locaux} ou \textbf{Globaux}\;}
      % \KwData{Data}
      % \KwResult{Result}
      % XXX Algorithm
      \textbf{Initialisation : } $\forall k \in \{1,\dots,K\}$, $\tau_k = 0$ et $n_k = 0$ \\
      \For{$t=1,2,\ldots, T$}{
          \pause
          \uIf{
              $t \mod \left\lfloor \frac{K}{\alpha}\right\rfloor \in \{1,\dots,K\}$
          }{
              $A(t) = t \mod \left\lfloor \frac{K}{\alpha}\right\rfloor$
              \tcp*[f]{exploration forcée} \\
          }
          \uElse{
            \textcolor{deeppurple}{$A(t) = \arg\max\limits_{k\in \{1,\dots,K\}} \mbox{kl-UCB}_k(t)$}
              \tcp*[f]{\textcolor{deeppurple}{plus grand indice UCB}}
          }
          \pause
          \mbox{Joue le bras} $k=A(t)$, et incrémente le compteur $n_{A(t)} = n_{A(t)} + 1$ \\
          \mbox{Observe la récompense} $X_{A(t),t}$, et la stocker $Z_{A(t), n_{A(t)}} = X_{A(t),t}$ \\
          \pause
          \uIf{
            \textcolor{gold}{$\mathrm{BGLRT}_\delta(Z_{A(t),1}, \cdots, Z_{A(t), n_{A(t)}})$ = Vrai}
          }
          {
              % \uSi{Redémarrages \textbf{globaux}}{
                \textcolor{gold}{$\forall k, \tau_k = t$ et $n_k = 0 $}
                \tcp*[f]{\textcolor{gold}{efface la mémoire de tous les bras}}
                  % \tcp*[f]{redémarrages globaux}
                  % }
              % \Sinon{
                  % $\tau_{A(t)} = t$ and $n_{A(t)} = 0$
                  % \tcp*[f]{redémarrage local}
              % }
          }
      }
  \end{algorithm}
\end{footnotesize}

\end{column}
\end{columns}

\end{frame}


% \section{\hfill{}5. Analyse du regret\hfill{}}

% \begin{frame}{5. Analyse du regret}

%   \begin{enumerate}
%     \item
%     \textcolor{gray}{
%       Problèmes de bandits multi-bras (stationnaires)
%     }
%     \vspace*{15pt}

%     \item
%     \textcolor{gray}{
%       Problèmes de bandits multi-bras stationnaires par morceaux
%     }
%     \vspace*{15pt}

%     \item
%     \textcolor{gray}{
%       Le test BGLR et ses propriétés à horizon fini
%     }
%     \vspace*{15pt}

%     \item
%     \textcolor{gray}{
%       L'algorithme B-GLRT + klUCB
%     }
%     \vspace*{15pt}

%     \item
%     \alert{\textbf{%
%       Analyse du regret
%     }}
%     \vspace*{15pt}

%     \item
%     \textcolor{gray}{
%       Simulations numériques
%     }
%   \end{enumerate}

% \end{frame}

% \subsection{\hfill{}Hypothèses\hfill{}}

% \begin{frame}{Hypothèses de notre analyse théorique}

%   \begin{itemize}
%     \item
%     Denote $\tau^{i}$ the position of break-point $i$ ($\tau^0 = 0$)
%     \item
%     and $\mu_k^{i}$ the mean of arm $k$ on the segment $[\tau^i, \tau^{i+1}]$
%     \item
%     and $b(i) \in \arg\max_k \mu_k^{i}$ (one of) the best arm(s) on the $i$-th segment
%     \item
%     and the largest gap at break-point $i$ is
%     $\Delta^{i} = \max\limits_{k=1,\dots,K} |\mu_k^{i} - \mu_k^{i-1}| >0$
%   \end{itemize}

%   \pause
%   \begin{block}{Assumption}
%     Fix the parameters $\alpha$ and $\delta$,
%     and let $d^{i} = d^{i}(\alpha,\delta) = \lceil \frac{4K}{\alpha(\Delta^{i})^2}\beta(T,\delta) + \frac{K}{\alpha} \rceil$.

%     \alert{\textbf{We assume that all sequences are ``long enough'':}}
%     \vspace*{-5pt}
%     \[ \forall i \in \{1,\dots,\Upsilon_T\}, \;\;\;\; \alert{\tau^{i} - \tau^{i-1}} \geq 2\max( d^{i}, d^{i-1} ). \]
%   \end{block}

%   \pause
%   $\hookrightarrow$
%   The \alert{minimum length of sequence $i$} depends on the amplitude of the changes at \textcolor{darkred}{the beginning} and \textcolor{darkblue}{the end} of the sequence (\textcolor{darkred}{$\Delta^{i-1}$} and \textcolor{darkblue}{$\Delta^{i}$}).

% \end{frame}


% \subsection{\hfill{}Regret upper-bound\hfill{}}

% \begin{frame}{Theoretical result}

%   Under this hypothesis, we obtained a \emph{finite time}
%   upper-bound on the regret $R_T$,
%   with explicit dependency from the problem difficulty.

%   The exact bound uses:
%   \begin{itemize}
%     \item
%     the divergences $\mathrm{kl}(\mu_{k}^{i},\mu_{b(i)}^{i})$
%     account for the difficulty of the stationary problem on sequence $i$,
%     \item
%     the gaps $\Delta^{i}$
%     account for the difficulty of detecting break-point $i$,
%   \end{itemize}
%   as well as the two parameters
%   \begin{itemize}
%     \item
%     $\alpha$ the probability of forced exploration,
%     \item
%     and $\delta$ the confidence level of the break-point detection test.
%   \end{itemize}

% \end{frame}


% \begin{frame}{Simplified form of the result for \textcolor{gold}{BGLR} + \textcolor{deeppurple}{kl-UCB}}

%   \begin{block}{Regret upper bound for BGLR + kl-UCB \dCooley{}}
%     \begin{itemize}
%       \item
%       On a problem satisfying our assumption\ldots
%       \item
%       let $\alpha = \sqrt{\Upsilon_T \ln(T) / T}$ and $\delta = 1 / \sqrt{T \Upsilon_T}$ (if $T$ and $\Upsilon_T$ are known),
%       \pause
%       \item
%       then if BGLR + kl-UCB uses parameters $\alpha$ and $\delta$, its regret satisfies
%       %
%       \[ R_T =\mathcal{O}\left( \frac{K}{\left(\textcolor{gold}{\Delta^{\text{change}}}\right)^2}\sqrt{T \Upsilon_T \ln(T)} + \frac{(K-1)}{\textcolor{deeppurple}{\Delta^{\text{opt}}}} \Upsilon_T\ln(T) \right),\]
%       \begin{itemize}\tightlist
%         \item
%         with $\textcolor{gold}{\Delta^{\text{change}}} =$
%         %  $\min_{i} \Delta^{i} =$
%         \textcolor{gold}{the smallest detection gap between two stationary segments}
%         $=$ \textcolor{gold}{Difficulty of the break-point detection problems!}
%         \item
%         and $\textcolor{deeppurple}{\Delta^{\text{opt}}} =$
%         \textcolor{deeppurple}{the smallest value of sub-optimality gap on a stationary segment}
%         $=$ \textcolor{deeppurple}{Difficulty of the stationary bandit problems!}
%       \end{itemize}
%       % ($\min_{k: \mu_k(t) < \mu_{k^*(t)}(t)} \mu_{k^*(t)}(t) - \mu_k(t)$)
%     \end{itemize}
%   \end{block}

% \pause
% $\implies$ $R_T = \mathcal{O}(K \sqrt{T \Upsilon_T \log(T)})$ if we hide the dependency on the gaps.

% \end{frame}


% \subsection{\hfill{}Comparison with other algorithms\hfill{}}

% \begin{frame}{Comparison with other state-of-the-art approaches}

%   \begin{exampleblock}{Our algorithm (BGLR + kl-UCB)}
%     \begin{itemize}
%       \item Hypotheses: bounded rewards, known $T$, known $\Upsilon_T = o(\sqrt{T})$, and ``long enough'' stationary sequences
%       \item We obtain $R_T = \mathcal{O}(K \sqrt{T \Upsilon_T \log(T)})$
%     \end{itemize}
%   \end{exampleblock}

%   \pause
%   Two recent competitors
%   use a similar assumption
%   \alert{but they both require prior knowledge of a lower-bound on the gaps}

%   % \begin{block}{Exp3.S \hfill{} \textcolor{gray}{[Auer et al, 2002]}}
%   %   \begin{itemize}
%   %     \item Hypotheses: just bounded rewards
%   %     \item $R_T = \mathcal{O}(K \sqrt{T \Upsilon_T})$
%   %     \item But usually poor in practice
%   %   \end{itemize}
%   % \end{block}

%   \begin{block}{CUSUM-UCB \hfill{} \textcolor{gray}{[Liu \& Lee \& Shroff, AAAI 2018]}}
%     \begin{itemize}
%       \item They obtain $R_T = \mathcal{O}(K \sqrt{T \Upsilon_T \log(T / \Upsilon_T)})$
%     \end{itemize}
%   \end{block}

%   \begin{block}{M-UCB \hfill{} \textcolor{gray}{[Cao \& Zhen \& Kveton \& Xie, AISTATS 2019]}}
%     \begin{itemize}
%       \item They obtain $R_T = \mathcal{O}(K \sqrt{T \Upsilon_T \log(T)})$
%     \end{itemize}
%   \end{block}

% \end{frame}


\section{\hfill{}5. Simulations numériques\hfill{}}

\begin{frame}{5. Simulations numériques}

  \begin{enumerate}
    \item
    \textcolor{gray}{
      Problèmes de bandits multi-bras (stationnaires)
    }
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      Problèmes de bandits multi-bras stationnaires par morceaux
    }
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      Le test BGLR et ses propriétés à horizon fini
    }
    \vspace*{15pt}

    \item
    \textcolor{gray}{
      L'algorithme B-GLRT + klUCB
    }
    \vspace*{15pt}

    % \item
    % \textcolor{gray}{
    %   Analyse du regret
    % }
    % \vspace*{15pt}

    \item
    \alert{\textbf{%
      Simulations numériques
    }}
  \end{enumerate}

\end{frame}


\subsection{\hfill{}Détails des expériences\hfill{}}

\begin{frame}{Simulations numériques}

  \begin{block}{On considère trois problèmes avec}
    \begin{itemize}
      \item
      $K=3$ bras de Bernoulli
      \item
      $T=5000$ étapes de temps (horizon fini)
      \item
      $\Upsilon_T=4$ ruptures ($=5$ séquences stationnaires)\\
      Les algorithmes peuvent utiliser cette connaissance de $T$ et $\Upsilon_T$
      \item
      $1000$ simulations indépendantes, on affiche le regret moyen
    \end{itemize}
  \end{block}

  \pause

  \begin{exampleblock}{Référence}
    \begin{itemize}
      \item
      On utilise ma bibliothèque open-source en Python pour la simulation de problèmes de bandits, \textbf{SMPyBandits}
      \\
      $\hookrightarrow$ Publiée en ligne à \href{https://SMPyBandits.GitHub.io}{\textcolor{blue}{\texttt{SMPyBandits.GitHub.io}}}
      \item
      Plus d'expériences dans la version longue de l'article !\\
      $\hookrightarrow$ sur
      \href{https://hal.inria.fr/hal-02006471}{\textcolor{blue}{HAL-02006471}}
      et
      \href{https://arxiv.org/abs/1902.01575}{\textcolor{blue}{arXiv:1902.01575}}
    \end{itemize}
  \end{exampleblock}

\end{frame}


\begin{frame}[plain]{Problème 1 : seulement des changements locaux}
  \centering
  \includegraphics[width=1.00\textwidth]{figures/Problem_1.pdf}

  On affiche les moyennes :
  \textcolor{red}{$\mu_1(t)$},
  \textcolor{green}{$\mu_2(t)$},
  \textcolor{blue}{$\mu_3(t)$}.
\end{frame}

\begin{frame}[plain]{Résultats pour le problème 1}
  \centering
  \includegraphics[width=1.05\textwidth]{figures/regret_problem1.png}

  $\implies$ BGLR atteint les meilleures performances parmi les algorithmes non-oracles \dCooley{} !
\end{frame}


\begin{frame}[plain]{Problème 2 : seulement des changements globaux}
  \centering
  \includegraphics[width=1.10\textwidth]{figures/Problem_2.pdf}
\end{frame}

\begin{frame}[plain]{Résultats pour le problème 2}
  \centering
  \includegraphics[width=1.05\textwidth]{figures/regret_problem2.pdf}

  $\implies$ BGLR atteint encore les meilleures performances \dCooley{} !
\end{frame}


\begin{frame}[plain]{Pb 3 : longueurs non uniformes des séquences}
  \centering
  \includegraphics[width=1.10\textwidth]{figures/Problem_4.pdf}
\end{frame}

\begin{frame}[plain]{Résultats pour le problème 3}
  \centering
  \includegraphics[width=1.05\textwidth]{figures/regret_problem4.pdf}

  $\implies$ BGLR atteint les meilleures performances parmi les algorithmes non-oracles \dCooley{} !
\end{frame}


\subsection{\hfill{}Conclusions des simulations\hfill{}}

% \begin{frame}{Interprétation des simulations (1/2)}
\begin{frame}{Interprétation des simulations}

  \begin{block}{Conclusions pour le regret}
    \begin{itemize}
      \item
      En pratique, on vérifie que le \alert{test BGLR est efficace} \dCooley{} :
      \begin{itemize}\tightlist
        \item
        il a une \alert{faible probabilité de fausse alarme},
        \item
        il a un \alert{faible délai} si les séquences stationnaires sont assez longues.
      \end{itemize}
      Et cela est aussi le cas hors des hypothèses de notre analyse
      \item
      Utiliser les indices kl-UCB donnent une bonne performance \dCooley{}
    \end{itemize}
    $\implies$ Notre algorithme (test BGLR + kl-UCB) est efficace

    $\implies$ On vérifie qu'il obtient des bonnes performances.
    %  similaires à l'état de l'art !
  \end{block}

\end{frame}


% \begin{frame}{Interprétation des simulations (2/2)}

%   Qu'en est-il de son efficacité en \textcolor{blue}{mémoire} et en \alert{temps} ?

%   \begin{block}{Mémoire : efficace \dSmiley}
%     Notre algorithme est aussi efficace que le reste de l'état de l'art !\\
%     \textcolor{gray}{Coût en mémoire $= \mathcal{O}(K d_{\max})$ pour $K$ bras.}
%   \end{block}

%   \begin{alertblock}<2->{Temps : lent \dSadey{} !}
%     Mais il est très lent !
%     Coût en temps $= \mathcal{O}(K d_{\max} \alert{\times t})$
%     à chaque étape $t$,
%     % for $K$ arms.
%     donc $\mathcal{O}(K d_{\max} \alert{T^2})$ en tout.
%     %  and horizon $T$.

%     $\hookrightarrow$ on a proposé deux astuces pour l'accélerer !

%     $\implies$ Notre algorithme (test BGLR + kl-UCB) peut être aussi rapide que M-UCB ou CUSUM-UCB.
%     % , the two algorithms that perform as well in terms of regret

%     % \hfill{} See the long version on \href{https://hal.inria.fr/hal-02006471}{\textcolor{blue}{HAL-02006471}} and \href{https://arxiv.org/abs/1902.01575}{\textcolor{blue}{arXiv:1902.01575}}
%   \end{alertblock}

%   \begin{small}
%     ($d_{\max} = \max\limits_i \tau^i - \tau^{i+1} =$ longueur de la plus longue séquence stationnaire)
%     % , $T \leq (1+\Upsilon_T) d_{\max}$)
%   \end{small}

% \end{frame}



\section{\hfill{}Conclusion\hfill{}}
\subsection{Résumé}

\begin{frame}{Résumé}

  On a présenté\ldots{}
  \begin{itemize}
    \item
    Les problèmes de bandits multi-bras stationnaires ou \alert{stationnaires par morceaux}
    %  (MAB)
    \item
    Le très efficace test généralisé de rapport de vraisemblances de Bernoulli (T-BGLR) \dCooley{}
    % (B-GLRT)
    \begin{itemize}\tightlist
      \item
      pour détecter les ruptures \alert{sans fausse alarme} et \alert{faible délai}
      \item
      pour des données de Bernoulli, et aussi des données sous-Bernoulli (n'importe quelle distribution bornée !),
      \item
      et n'a \emph{pas} besoin de connaître l'amplitude des ruptures
    \end{itemize}
    \item
    On peut le combiner avec une stratégie de bandit efficace :
    \alert{BGLR + kl-UCB}  \dCooley{}
    \item
    Sa borne de regret est $R_T = \mathcal{O}(K \sqrt{T \Upsilon_T \log(T)})$  \dCooley{} (état de l'art)
    \item
    Notre algorithme est compétitif avec le reste de l'état de l'art sur nos simulations numériques\dCooley
    % \\
    % et BGLR + kl-UCB peut être aussi rapide que ses meilleurs compétiteurs.
  \end{itemize}

\end{frame}

\subsection{Merci}
\begin{frame}{Conclusion}

\begin{center}
  \begin{Large}
    {\Fontify Merci de votre attention.}
    \Innocey[1.2]
  \end{Large}
\end{center}

\vspace*{20pt}

\begin{center}
  \begin{Large}
    Questions \& Discussion ?
  \end{Large}
\end{center}

\vspace*{20pt}

\begin{center}
  \begin{Large}
    Si besoin :
    \texttt{Lilian.Besson{@}CentraleSupelec.fr}
  \end{Large}
\end{center}

\end{frame}

\end{document}
