% \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}%[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 T-BGLR + klUCB % \vspace*{15pt} % % \item % % Analyse du regret % % \vspace*{15pt} % \item % Simulations numériques % \end{enumerate} % \end{frame} \section{\hfill{}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 T-BGLR + klUCB % } % \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 vieux nom pour une machine à sous ! \begin{center} % \centering \includegraphics[height=0.55\textheight]{figures/Lucky_Luke__Le_Bandit_Manchot.jpg} \end{center} Collaboration avec mon encadrante de thèse \textbf{Émilie Kaufmann}, cf. sa conférence plénière de mardi 27 août ! \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} \begin{frame}{Bandits multi-bras : stationnaires vs non-stationnaires} \begin{block}{Stationnaires} Ok ! \end{block} \pause \begin{alertblock}{Non stationnaires} Difficile ! \end{alertblock} \pause \begin{block}{Notre direction de résolution} On combine : \begin{itemize} \item un \alert{algorithme classique} (kl-UCB) pour sélectionner les bras, \item et \alert{on détecte les ruptures activement grâce à un test statistique} effectué sur chaque bras. \end{itemize} \end{block} \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 On observe des données $X_1,X_2,\cdots,X_t,\cdots \in[0,1]$\ldots \item On sait que $X_t$ est générée par une distribution \alert{inconnue}\ldots \end{itemize} \only<1>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps1.pdf}} \only<2>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps2.pdf}} \only<3>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps3.pdf}} \only<4>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps4.pdf}} \only<5>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps5.pdf}} \only<6>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps6.pdf}} \only<7>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps7.pdf}} \only<8>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps8.pdf}} \only<9>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps9.pdf}} \only<10>{\includegraphics[width=0.90\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu__temps10.pdf}} \end{frame} \begin{frame}{Le problème de détection de rupture} % Imaginez le jeu suivant\ldots % \begin{itemize} % \item On observe des données $X_1,X_2,\cdots,X_t,\cdots \in[0,1]$\ldots % \item On sait que $X_t$ est générée par une distribution \alert{inconnue}\ldots % \item \alert{Le 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 On s'arrête au temps $\widehat{\tau}$, dès qu'on détecte une rupture % \end{itemize} \vspace*{20pt} \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} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_facile_inconnu.pdf} % \end{center} % \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_facile_connu.pdf} % \end{center} % \end{frame} \begin{frame}[plain]{Exemple facile de détection de rupture} \begin{center} \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_moyen_inconnu.pdf} \end{center} \end{frame} \begin{frame}[plain]{Exemple facile de détection de rupture} \begin{center} \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_moyen_connu.pdf} \end{center} \end{frame} \begin{frame}[plain]{Difficile avec peu d'échantillons ?} \begin{center} \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_inconnu.pdf} \end{center} \end{frame} \begin{frame}[plain]{Difficile avec peu d'échantillons ?} \begin{center} \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_facile__T_difficile_connu.pdf} \end{center} \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_moyen__T_facile_inconnu.pdf} % \end{center} % \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_moyen__T_facile_connu.pdf} % \end{center} % \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_moyen__T_moyen_inconnu.pdf} % \end{center} % \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_moyen__T_moyen_connu.pdf} % \end{center} % \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_moyen__T_difficile_inconnu.pdf} % \end{center} % \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_moyen__T_difficile_connu.pdf} % \end{center} % \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_difficile__T_facile_inconnu.pdf} % \end{center} % \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_difficile__T_facile_connu.pdf} % \end{center} % \end{frame} \begin{frame}[plain]{Difficile avec des moyennes trop proches ?} \begin{center} \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_difficile__T_moyen_inconnu.pdf} \end{center} \end{frame} \begin{frame}[plain]{Difficile avec des moyennes trop proches ?} \begin{center} \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_difficile__T_moyen_connu.pdf} \end{center} \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_difficile__T_difficile_inconnu.pdf} % \end{center} % \end{frame} % \begin{frame}[plain]{Exemples de détection de rupture} % \begin{center} % \includegraphics[width=1.10\textwidth]{figures_exemple_rupture/exemple_rupture__mu_difficile__T_difficile_connu.pdf} % \end{center} % \end{frame} \begin{frame}{Qu'est-ce qu'un bon test de détection de rupture ?} Deux propriétés essentielles : \begin{block}{1. Pas de \textbf{fausse alarme}} 1. Un bon test ne doit rien détecter s'il n'y a pas de rupture à détecter\ldots \visible<2>{ \hfill{} \alert{Premier extrême} : aucune fausse alarme si on détecte \emph{jamais} \dXey{} } \end{block} \begin{block}{2. Un \textbf{délai de détection} court} 2. 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 \visible<2>{ \hfill{} \alert{Autre extrême} : délai nul si on détecte \emph{tout le temps} \dXey{} } \end{block} \visible<2>{ $\implies$ résoudre le compromis entre \alert{les deux extrêmes} ! } \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 avec 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 } s},\underbrace{\widehat{\mu}_{1:n}}_{\text{tout}} ) \\ + & (n-s) \times \mathrm{kl} (\underbrace{\widehat{\mu}_{s+1:n}}_{\text{après } s},\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 T-BGLR\hfill{}} % \begin{frame}{Généralisable à des observations bornées \dCooley{}} % \begin{itemize} % \item % On peut étendre ce test si les observations sont \alert{sous-Bernoulli}. % \item % Toute distribution $\nu$ à 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{small} % \begin{exampleblock}{Distributions sous-Bernoulli} % % If $\nu$ is supported in $[0,1]$, % % $\nu$ is \emph{sub-Bernoulli} if it verifies % $\nu$ sous-Bernoulli \\ % $\Leftrightarrow$ % sa fonction génératrice des moments est bornée par celle d'une Bernoulli $\mathcal{B}$ \\ % $\Leftrightarrow$ % $\phi_{\nu} \leq \phi_{\mathcal{B}}$ % $\Leftrightarrow$ % $\forall \lambda, \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{exampleblock} % \end{small} % \end{frame} \begin{frame}{Le test généralisé de rapport de vraisemblances de Bernoulli (T-BGLR)} % \begin{block}{Le test de détection séquentielle de rupture B-GRLT} Le \alert{T-BGLR} est le temps d'arrêt $\widehat{\tau}_{\delta}$ 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 \in \mathbb{N}^*$ est le nombre d'observations ($X_1,\dots,X_n$), \item $0 < \delta < 1$ est le niveau de confiance. \end{itemize}% % \end{block} \end{frame} \subsection{\hfill{}Fausse alarme\hfill{}} \begin{frame}{Probabilité de fausse alarme} % 1. 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$, Une rupture est détectée si $\widehat{\tau}_\delta < \infty$. \vspace*{10pt} 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$}. \vspace*{10pt} 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 ?} $\hookrightarrow$ 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} % 2. 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$}. \vspace*{10pt} % L'\alert{écart} de cette rupture est $\Delta = |\mu_0 - \mu_1|$. % \vspace*{10pt} Le \alert{délai de détection} est définit par la variable aléatoire $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 \textcolor{gray}{\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 T-BGLR\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 \vspace*{10pt} \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} \vspace*{10pt} \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} % \subsection{\hfill{}Modèle mathématique de bandits\hfill{}} % \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/}}} % \end{tiny} % \end{frame} % \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{}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 T-BGLR + klUCB % % } % % \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$ donne 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$ donne 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$ : % \vspace*{-20pt} % WARNING % \begin{center} % \includegraphics[width=1.10\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{}L'algorithme T-BGLR + klUCB\hfill{}} % % \begin{frame}{4. L'algorithme T-BGLR + 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 T-BGLR + klUCB % % }} % % \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} % 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) % \pause % % $\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 Quelques instants, forcer une exploration de chaque bras % \pause % \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} % $\hookrightarrow$ Algorithme BGRL + kl-UCB détaillé dans l'article % % \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 T-BGLR + 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{}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 T-BGLR + klUCB % } % \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]{Pour les curieux : SMPyBandits est sur GitHub et PyPI} \centering \includegraphics[width=1.20\textwidth]{figures/overview_documentation_1.png} $\hookrightarrow$ \href{https://SMPyBandits.GitHub.io}{\textcolor{blue}{\texttt{SMPyBandits.GitHub.io}}} \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]{Exemple de détections de ruptures pour le problème 1} \centering \includegraphics[width=1.05\textwidth]{figures/Visualizing_locations_of_change_points_for_different_algorithms__4algs_Pb1.pdf} $\implies$ Notre test est efficace ! (sur un exemple) \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 (hors non-oracles) \dCooley{} ! \end{frame} % \begin{frame}[plain]{Problème 2 : seulement des changements globaux} % \centering % \includegraphics[width=1.00\textwidth]{figures/Problem_2.pdf} % \end{frame} % \begin{frame}[plain]{Exemple de détections de ruptures pour le problème 2} % \centering % \includegraphics[width=1.05\textwidth]{figures/Visualizing_locations_of_change_points_for_different_algorithms__4algs_Pb2.pdf} % $\implies$ Notre test est efficace ! % (sur un exemple) % \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.00\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{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 test généralisé de rapport de vraisemblances de Bernoulli (T-BGLR) est très efficace \dCooley{} % (T-BGLR) \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 $\Delta$ \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} \begin{frame}[plain]{Crise climatique ?} \begin{center} \includegraphics[height=0.85\textheight]{../common/TalkAboutGlobalWarmingNow.png} \begin{tiny} \textcopyright{} Jeph Jacques, 2015, \texttt{QuestionableContent.net/view.php?comic=3074} \end{tiny} \end{center} \end{frame} \begin{frame}[plain]{Parlons d'action contre la crise climatique !} \begin{center} \includegraphics[height=0.30\textheight]{../common/TalkAboutGlobalWarmingNow.png} \end{center} \begin{alertblock}{Nous sommes scientifiques\ldots} Buts : \alert{s'informer, réfléchir, résoudre, transmettre} ! \begin{itemize} \item \alert{Informons nous} des \alert{causes} et \alert{conséquences} de la crise climatique, \item \alert{Réfléchissons} aux problèmes, à l'échelle politique, locale et individuelle, \item \alert{Trouvons} des solutions simples !\\ $\implies$ Viser la sobriété : transports, tourisme, vêtements, alimentation, calculs informatique, lutte contre le tabagisme, etc. \item \alert{Transmettons} notre prise de conscience, et nos actions. \end{itemize} \end{alertblock} \end{frame} \end{document}