% \documentclass[slideopt,A4,11pt,english,aspectratio=169,]{beamer} \documentclass[slideopt,A4,11pt,english,]{beamer} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{environ} \usepackage{multimedia} % videos in beamer \usepackage{lmodern} \usepackage{textcomp} \usepackage{fourier-orns} % danger % \usepackage{fourier} % for € % \usepackage[utopia]{mathdesign} % for € % \usepackage{MnSymbol} % https://www.ctan.org/pkg/mnsymbol \usepackage{amsmath,amsfonts,amssymb} % Maths. \usepackage{array} \usepackage{algorithm} \usepackage{algorithmic} \usepackage{eso-pic} \usepackage[normalem]{ulem} % https://tex.stackexchange.com/a/23712/ % --- Figures Tikz \usepackage{tikz} \usetikzlibrary{positioning} \usetikzlibrary{fit} \usetikzlibrary{arrows} \usetikzlibrary{decorations.pathmorphing} \usetikzlibrary{shapes.geometric} \usetikzlibrary{shapes.symbols} \usetikzlibrary{backgrounds} \usetikzlibrary{chains} \usepackage{tikzsymbols} % http://texdoc.net/texmf-dist/doc/latex/comprehensive/symbols-a4.pdf for the \Coffeecup{} command! \usepackage{layout} \usepackage{xcolor,colortbl} \usepackage{appendixnumberbeamer} \useoutertheme{infolines} % \usefonttheme{serif} % default family is serif % % \usepackage{palatino} % Use the Palatino font % XXX remove if it is ugly ? % \usepackage{mathpazo} % \usepackage{tgpagella} % alternative to MinionPro \usepackage{graphicx} \graphicspath{{figures/}} \usepackage{wasysym} % for \pentagon \usepackage[absolute,showboxes,overlay]{textpos} \TPshowboxesfalse \textblockorigin{0mm}{0mm} %%%%% COLORS \xdefinecolor{myorange}{rgb}{1.,0.15,0.} \newcommand{\blue}{\color{blue}} \newcommand{\red}{\color{red}} \newcommand{\orange}{\color{orange}} \newcommand{\black}{\color{black}} \newcommand{\gray}{\color{gray}} \definecolor{lightgray}{RGB}{200,200,200} % rgb(200,200,200) \definecolor{blackblue}{RGB}{19,19,59} % rgb(19,19,59) \definecolor{bleu}{RGB}{0,0,204} % rgb(0,0,204) \definecolor{lightblue}{RGB}{50,50,204} % rgb(50,50,204) \definecolor{lightlightblue}{RGB}{98,98,255} % rgb(98,98,255) \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{bluegreenrhorand}{RGB}{76,191,129} % rgb(76,191,129) \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{lightred}{RGB}{255,160,160} % rgb(255,160,160) \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) \definecolor{centralesupelec}{RGB}{150,14,59} % rgb(150,14,59) \definecolor{centralesupelecdark}{RGB}{84,8,33} % rgb(84,8,33) \definecolor{centralesupeleclight}{RGB}{204,19,80} % rgb(204,19,80) %%%%% BEAMER CUSTOMIZATION \setbeamercolor{block body}{bg=blue!10!white} \setbeamercolor{block body alerted}{bg=red!10!white} \setbeamercolor{block body example}{bg=green!10!white} \setbeamercolor{block title}{bg=blue!80!black,fg=white} \setbeamercolor{block title alerted}{use={normal text,alerted text},fg=white,bg=red!80!black} \setbeamercolor{block title example}{use={normal text,example text},fg=white,bg=green!50!black} \setbeamercolor{item projected}{bg=blue!70!white,fg=white} \setbeamertemplate{enumerate items}[ball] \setbeamertemplate{enumerate subitem}{\insertenumlabel.\insertsubenumlabel} \setbeamertemplate{enumerate subsubitem}{\insertenumlabel.\insertsubenumlabel.\insertsubsubenumlabel} \setbeamertemplate{enumerate mini template}{\insertenumlabel} \setbeamertemplate{blocks}[rounded][shadow=true] \setbeamertemplate{navigation symbols}{} \setbeamertemplate{headline}{} \setbeamersize{text margin left=1cm,text margin right=1cm} \setbeamersize{text margin left=0.5cm,text margin right=0.3cm} %%%%% customize blocks \newenvironment<>{orangeblock}[1]{% \setbeamercolor{block title}{fg=white,bg=orange}% \setbeamercolor*{block body}{fg=black,bg=orange!5} \begin{block}#2{#1}}{\end{block}} \newenvironment<>{blueblock}[1]{% \setbeamercolor{block title}{fg=white,bg=blue}% \setbeamercolor*{block body}{fg=black,bg=blue!5} \begin{block}#2{#1}}{\end{block}} \newenvironment<>{redblock}[1]{% \setbeamercolor{block title}{fg=white,bg=red}% \setbeamercolor*{block body}{fg=black,bg=orange!5} \begin{block}#2{#1}}{\end{block}} \newenvironment<>{colorblock}[1]{% \setbeamercolor{block title}{fg=white,bg=centralesupelec}% \setbeamercolor*{block body}{fg=black,bg=centralesupelec!5} \begin{block}#2{#1}}{\end{block}} \newenvironment<>{darkblock}[1]{% \setbeamercolor{block title}{fg=white,bg=centralesupelecdark}% \setbeamercolor*{block body}{fg=black,bg=centralesupelecdark!5} \begin{block}#2{#1}}{\end{block}} \newenvironment<>{lightblock}[1]{% \setbeamercolor{block title}{fg=white,bg=centralesupeleclight}% \setbeamercolor*{block body}{fg=black,bg=centralesupeleclight!5} \begin{block}#2{#1}}{\end{block}} \newenvironment<>{whiteblock}[1]{% \setbeamercolor{block title}{fg=white,bg=white}% \setbeamercolor*{block body}{fg=black,bg=white} \begin{block}#2{#1}}{\end{block}} %%%%% customize titles \setbeamertemplate{frametitle}{\centering\vspace{0.2cm}\color{blue}\insertframetitle\par\vspace{.2cm}} \newcommand{\shadedtitle}[3]{ \setlength{\fboxsep}{0pt}% \setlength{\fboxrule}{1pt}% \begin{textblock}{12.6}(0.,0.75) \begin{tikzpicture} \node[top color=black,bottom color=white] { \begin{minipage}[t][0cm][b]{12.6cm} {.} \end{minipage} }; \end{tikzpicture} \end{textblock} \begin{textblock}{12.6}(0,0) \begin{tikzpicture} \node[left color=#2,right color=#3] { \begin{minipage}[t][12pt][t]{12.6cm} {\color{white}#1} \end{minipage} }; \end{tikzpicture} \end{textblock} } % \newcommand{\mytitle}[2]{\shadedtitle{\Large\bf #2}{#1}{#1!10!white}} \newcommand{\mytitle}[3]{\shadedtitle{\Large\bf #3}{#1}{#1!10!#2}} %%%%%%% define new frames % Odalric's style frame \NewEnviron{frameO}[1][]{% \begin{frame}\mytitle{centralesupelecdark}{centralesupelec}{#1} \vspace{0.4cm} \BODY \end{frame} } % frame for (main) titles \NewEnviron{frameT}[1][]{ \setbeamertemplate{background canvas}{\includegraphics[width=\paperwidth,height=\paperheight]{../templateCS/PremierePage_CentraleSupelec}} \setbeamertemplate{footline}{ \hspace{5em} \textcolor{white} {PhD defense -- Lilian Besson -- \emph{``MAB Algorithms for IoT Networks''} \hfill 20 November, 2019}\hspace{2em}\null \vspace*{3pt}} \begin{frame}{#1} \BODY \end{frame} } \NewEnviron{frameTTnobottom}[1][]{ \setbeamertemplate{background canvas}{\includegraphics[width=\paperwidth,height=\paperheight]{../templateCS/PremierePage_CentraleSupelec}} \setbeamertemplate{footline}{ \hspace{5em} \textcolor{white} {}\hspace{2em}\null \vspace*{3pt}} \begin{frame}{#1} \BODY \end{frame} } \NewEnviron{frameTTnobottomNoLogo}[1][]{ \setbeamertemplate{background canvas}{\includegraphics[width=\paperwidth,height=\paperheight]{../templateCS/background}} \setbeamertemplate{footline}{ \hspace{5em} \textcolor{white} {}\hspace{2em}\null \vspace*{3pt}} \begin{frame}{#1} \BODY \end{frame} } \NewEnviron{frameTT}[1][]{ \setbeamertemplate{background canvas}{\includegraphics[width=\paperwidth,height=\paperheight]{../templateCS/PremierePage_CentraleSupelec}} \setbeamertemplate{footline}{ \hspace{5em} \textcolor{white} {PhD defense -- Lilian Besson -- \emph{``MAB Algorithms for IoT Networks''} \hfill 20 November, 2019}\hspace{2em}\null \vspace*{3pt}} \begin{frame}{#1} \BODY \end{frame} } % frame for intermediate titles \NewEnviron{frameTI}[1][]{ \setbeamertemplate{background canvas}{\includegraphics[width=\paperwidth,height=\paperheight]{../templateCS/PageTab_CentraleSupelec}} \setbeamertemplate{footline}{\hspace{2cm} \raisebox{2.5ex} {{PhD defense -- Lilian Besson -- \emph{``MAB Algorithms for IoT Networks''}}}\hfill \raisebox{2.5ex} {{20 November, 2019 -- \insertframenumber / \inserttotalframenumber \hspace{5mm} \null }}} \begin{frame}{#1} \BODY \end{frame} } %%%%% mathematical symbols \input{symbolsdef} %%%%% XXX from my old template \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 \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 \newcommand{\thinkingface}{\includegraphics[height=0.38cm]{thinking-face_1f914.png}} \newcommand{\thinkingfacelarge}{\includegraphics[height=0.44cm]{thinking-face_1f914.png}} \newcommand{\snail}{\includegraphics[height=0.30cm]{snail_1f40c.png}} \newcommand{\tgvsmall}{\includegraphics[height=0.25cm]{high-speed-train_1f684.png}} \newcommand{\tgv}{\includegraphics[height=0.34cm]{high-speed-train_1f684.png}} \newcommand{\slotmachine}{\includegraphics[height=0.38cm]{slot-machine_1f3b0.png}} % \newcommand{\etoile}{\includegraphics[height=0.23cm]{party-popper_1f389.png}} \newcommand{\etoilenorm}{$\star$} \newcommand{\etoile}{\Large{$\star$}} % Prevent slide breaks in the middle of a paragraph: \widowpenalties 1 10000 \raggedbottom %%%%%%%% BEGINS HERE \begin{document} \begin{frameTTnobottomNoLogo} \color{white} \begin{center} \begin{LARGE} \textsc{``Multi-players Bandit Algorithms for Internet of Things Networks''} \end{LARGE} \end{center} \begin{Large} \begin{itemize} \setlength\itemsep{10pt} \color{white} \item By \textbf{Lilian Besson} \item \textbf{PhD defense} at \textbf{CentraleSupélec} (Rennes) \item Wednesday $20$th of November, $2019$ \item \underline{Supervisors}: \begin{itemize} \color{white} \item Prof. Christophe Moy at SCEE team, IETR \& CentraleSupélec % in Rennes (France) \item Dr. Émilie Kaufmann at SequeL team, CNRS \& Inria, in Lille \end{itemize} \end{itemize} \end{Large} \vspace*{5pt} \vfill{} % XXX manual inclusion of logos \begin{whiteblock}{} % \begin{center} \includegraphics[height=0.19\textheight]{../common/LogoIETR.png} \includegraphics[height=0.23\textheight]{../common/LogoCS.png} \includegraphics[height=0.19\textheight]{../common/LogoInria.jpg} % \end{center} \end{whiteblock} \color{black} \end{frameTTnobottomNoLogo} %%% presentation for standard frames \setbeamertemplate{background canvas}{\includegraphics[width=\paperwidth,height=\paperheight]{../templateCS/PageTabInverse_CentraleSupelec}} \setbeamertemplate{footline}{\hspace{2cm} \raisebox{2.5ex} {\textcolor{white}{PhD defense -- Lilian Besson -- \emph{``MAB Algorithms for IoT Networks''}}}\hfill \raisebox{2.5ex} {\textcolor{white}{20 November, 2019 -- \insertframenumber / \inserttotalframenumber \hspace{5mm} \null }}} % \begin{frameO}[Welcome to my PhD defense] % % Hi, I'm Lilian\dots % \begin{itemize} % \item Title: \textsc{Multi-players Bandit Algorithms for Internet of Things Networks} % \item % \textbf{PhD defense}, % at \textbf{CentraleSupélec}, campus de Rennes, % Wednesday $20$th of November, $2019$ % % \item Defense for my PhD in Telecommunications and Machine Learning % \item PhD (2016-19) under supervision of Prof. Christophe Moy\\ % at SCEE team, IETR \& CentraleSupélec in Rennes (France) % \item and Dr. Émilie Kaufmann at SequeL team, in CNRS and Inria in Lille % % \hfill{} \emph{Thanks to her for some of the slides material!} % % \item \textcolor{orange}{and I'm joining the PANAMA team in December!} % \end{itemize} % \vspace*{5pt} % % \begin{small} % % \begin{itemize} % % \item Email: \href{https://perso.crans.org/besson/}{\textcolor{darkgreen}{\texttt{Lilian.Besson @ CentraleSupelec.fr \& Inria.fr}}} % % \item $\hookrightarrow$ \href{https://perso.crans.org/besson/}{{\textcolor{blue}{\texttt{perso.crans.org/besson/}}}} \& \href{https://GitHub.com/Naereen/}{{\textcolor{blue}{\texttt{GitHub.com/Naereen}}}} % % \end{itemize} % % \end{small} % \vfill{} % % XXX manual inclusion of logos % \begin{center} % \includegraphics[height=0.20\textheight]{../common/LogoIETR.png} % \includegraphics[height=0.22\textheight]{../common/LogoCS.png} % \includegraphics[height=0.20\textheight]{../common/LogoInria.jpg} % \end{center} % \end{frameO} % \begin{frameO}[What did I study during my PhD ?] % \begin{darkblock}{Telecommunications technology\dots} % \hspace{5pt} $\hookrightarrow$ \alert{\textbf{wireless}} networks\dots % \vspace*{20pt} % \hspace{10pt} $\hookrightarrow$ networks with \alert{\textbf{decentralized}} access\dots % \vspace*{20pt} % \hspace{15pt} $\hookrightarrow$ \alert{\textbf{some/many}} wireless devices access a wireless network\\ % \hspace{30pt} served from \alert{\textbf{one}} access point, in an unlicensed standard:\\ % \hspace{30pt} the base station is \alert{\textbf{not}} affecting devices to radio resources\dots % \vspace*{20pt} % \hspace{35pt} $\hookrightarrow$ we focus on the case of \alert{\textbf{Internet of Things}} networks % \end{darkblock} % \end{frameO} \section{Spectrum issues in wireless networks} \begin{frameTI} \begin{center} {\textcolor{white} {\Huge \textsc{Introduction:} }} \end{center} \vspace*{10pt} \begin{center} {\textcolor{white} {\Huge \textsc{Spectrum issues} }} \end{center} \begin{center} {\textcolor{white} {\Huge \textsc{in wireless networks} }} \end{center} \vspace*{-4pt} \vfill{} \small{\textcolor{lightgray}{Ref: Chapter 1 of my thesis.}} \end{frameTI} \begin{frameO}[Wireless networks] \begin{itemize} \item All spectrum is allocated to different applications % Wireless networks run on different frequencies \item But all zones are not always used everywhere % most of which are already allocated to a fixed usage \item[\thinkingface] \textbf{What if we could dynamically use the (most) empty channels?} \end{itemize} % $\implies$ Almost all frequencies are registered and their usages are limited! \begin{center} \includegraphics[width=0.65\textwidth]{United_States_Frequency_Allocations_Chart_2016_The_Radio_Spectrum_3} \end{center} \hfill{} {\tiny \textcolor{gray}{United States of North America, Department of Commerce, \textcopyright{} 16}} \end{frameO} % \begin{frameO}[But\dots world-wide non-homogeneous frequency usage] % But\dots almost everywhere and at anytime in the world, some radio channels are not used! (in any standard) % \begin{center} % \includegraphics[width=0.80\textwidth]{scan_WiFi_maison} % \end{center} % \hfill{} % {\tiny \textcolor{gray}{Lilian Besson, screenshot from my FreeBox control interface, \textcopyright{} 2019}} % \vspace*{10pt} % \hfill{} % \thinkingface{} % \textbf{What if we could dynamically use the (most) empty channels?} % \end{frameO} % \begin{frameO}[What did I study during my PhD ? ($1/2$)] \begin{frameO}[Target of this study] % \begin{darkblock}{Telecommunications technology\dots} % \hspace{5pt} $\hookrightarrow$ wireless networks\dots\\ % \hspace{10pt} $\hookrightarrow$ networks with decentralized access\dots\\ % \hspace{15pt} $\hookrightarrow$ SOME/MANY wireless devices access a wireless network\\ % \hspace{30pt} served from ONE access point, in an unlicensed standard:\\ % \hspace{30pt} the base station is NOT affecting devices to radio resources\dots\\ % \hspace{35pt} $\hookrightarrow$ we focus on the case of \emph{Internet of Things} networks % \end{darkblock} \begin{darkblock}{Wireless networks\dots} We focus on \textbf{\alert{Internet of Things}} networks (IoT) in unlicensed bands. % \hspace{5pt} $\hookrightarrow$ \textbf{\alert{wireless} networks}\dots \hspace{10pt} $\hookrightarrow$ networks with \textbf{\alert{decentralized} access}\dots \hspace{15pt} $\hookrightarrow$ \textbf{\alert{many} wireless devices} \includegraphics[height=0.37cm]{dynamic-devices.png} access a wireless network\\ \hspace{30pt} served from \textbf{\alert{one} access point}\\ % in an unlicensed standard:\\ \hspace{30pt} the base station is \textbf{\alert{not}} affecting devices to radio resources\dots \end{darkblock} \pause \begin{center} % \centering \includegraphics[width=0.50\linewidth]{system_model1.eps} % \caption{In our system model, some dynamic devices (in the \textcolor{blue}{IoT network in blue}) transmit packets to a gateway and suffer from the interference generated by neighboring networks (in \textcolor{orange}{orange left/right}).} % \label{fig:41:system_model1} \end{center} % \hfill{} % \vspace*{-30pt} % {\tiny \textcolor{gray}{[Bonnefoi, Besson et al, CROWNCOM 2017], Ch.5}} \end{frameO} \begin{frameO}[The ``Internet of Things''] % Test ! \begin{columns}%[onlytextwidth] \begin{column}{0.59\textwidth} \begin{colorblock}{Main constraints} \small \begin{itemize} \item decentralized: \textcolor{orange}{devices initiate transmission} \item can be in unlicensed radio bands \item \textcolor{orange}{massive number of devices} \item long range \item ultra-low power devices \item \textcolor{orange}{low duty cycle} \item \textcolor{orange}{low data rate} \end{itemize} \end{colorblock} \end{column} % ... \begin{column}{0.40\textwidth} % Test ! \vspace*{10pt} % % \begin{center} \includegraphics[width=1.00\linewidth]{Screenshot_from_what_is_the_Internet_of_Things_video.jpg} \includegraphics[width=1.00\linewidth]{Connected_cows.jpg} % % \end{center} \end{column} \end{columns} \vfill{} % \hfill{} {\tiny \textcolor{gray}{ Images from \texttt{http://IBM.com/blogs/internet-of-things/what-is-the-iot} % \texttt{YouTu.be/QSIPNhOiMoE} and and \texttt{http://www.globalsign.com/en/blog/}\\ \texttt{connected-cows-and-crop-control}\texttt{-to-drones-the-internet-of-things}\texttt{-is-rapidly-improving-agriculture/} }} \end{frameO} \begin{frameO}[Main questions] \begin{darkblock}{} % {Main questions} \begin{itemize} \item Can the IoT devices \includegraphics[height=0.37cm]{dynamic-devices.png} optimize their access to the radio resources\\ in a \textbf{\alert{simple}}, \textbf{\alert{efficient}}, \textbf{\alert{automatic}} and \textbf{\alert{decentralized}} way?\\ \textcolor{gray}{In a given location, and a given time, for a given radio standard\dots} % \item % \alert{Can the devices learn \textbf{on their own} to communicate \textbf{more efficiently}?} \end{itemize} \end{darkblock} % \vspace{5pt} \pause % \begin{colorblock}{Main goals} \begin{itemize} \item Goal: increase the battery life of IoT devices \includegraphics[height=0.37cm]{dynamic-devices.png} \item Fight the spectrum scarcity issue by using the spectrum more efficiently than a static or uniformly random allocation \end{itemize} % \end{colorblock} % \vspace{5pt} \pause \begin{lightblock}{\textbf{Main solutions !}} % \begin{itemize} % \item % Yes we can! By letting the radio devices \includegraphics[height=0.37cm]{dynamic-devices.png} become ``intelligent'' \\ % \includegraphics[height=3cm]{Venn_Diagram_ML_RL_MAB.pdf} % % \hspace{5pt} $\hookrightarrow$ by using \emph{Machine Learning} algorithms\dots\\ % % \hspace{10pt} $\hookrightarrow$ of the \emph{Reinforcement Learning} family\dots\\ % % \hspace{15pt} $\hookrightarrow$ we focus on \textbf{\alert{Multi-Armed Bandit}} algorithms\\ % % % \hspace{30pt} and we showed they are well suited for (some of) these problems! % \end{itemize} \begin{columns}%[onlytextwidth] \begin{column}{0.50\textwidth} \begin{small} \begin{itemize} \item Yes we can! \item By \textcolor{orange}{letting the radio devices \includegraphics[height=0.37cm]{dynamic-devices.png} become ``intelligent''} \item With \textcolor{darkgreen}{\textbf{MAB algorithms}} ! \end{itemize} \end{small} \end{column} % ... \begin{column}{0.49\textwidth} \includegraphics[height=2.75cm]{Venn_Diagram_ML_RL_MAB.png} % \includegraphics[height=2.75cm]{Venn_Diagram_ML_RL_MAB.pdf} \end{column} \end{columns} \end{lightblock} \end{frameO} \section{Outline of this presentation} \begin{frameTI} \color{white} \begin{center} {\textcolor{white} {\Huge \textsc{Outline of this} }} \end{center} % \vspace*{5pt} \begin{center} {\textcolor{white} {\Huge \textsc{presentation} }} \end{center} % \vspace*{-15pt} \end{frameTI} % \begin{frameO}[Main contributions presented today] % \large % \begin{itemize} % \setlength\itemsep{10pt} % \item a simple model of IoT network, with decentralized learning embedded in the autonomous IoT devices, % \item numerical simulations proving the quality of the proposed solution, % \item a realistic implementation on radio hardware, % % \item my Python library SMPyBandits. % \item theoretical results in a simplified model: multi-player bandits, % \item and an extension beyond the stationary hypothesis. % \end{itemize} % \end{frameO} % \begin{frameO}[Chapters of my thesis addressed today] % \large % \begin{enumerate}[leftmargin=50pt] % \setlength\itemsep{10pt} % % \item[Ch.1)] Introduction % \item[Ch.2)] \textcolor{blue}{Stochastic Multi-Armed Bandits} % \item[\textcolor{gray}{Ch.3)}] \textcolor{gray}{SMPyBandits: an exhaustive Python library to simulate MAB problems} % \item[\textcolor{gray}{Ch.4)}] \textcolor{gray}{Expert aggregation for online MAB algorithms selection} % \item[Ch.5)] \textcolor{blue}{Improving Spectrum Usage of IoT Networks with Selfish MAB Learning} % \item[Ch.6)] \textcolor{blue}{Multi-Players Multi-Armed Bandits} % \item[Ch.7)] \textcolor{blue}{Piece-Wise Stationary Bandits} % % \item[Ch.8)] General Conclusion and Perspectives % \end{enumerate} % \end{frameO} % \begin{frameO}[Reading map of my thesis for today] \begin{frameO}[Contributions of my thesis highlighted today] \begin{figure}[h!] \centering \resizebox{0.95\textwidth}{!}{ \begin{tikzpicture}[>=latex',line join=bevel,scale=2.25] % \node[align=center] (introduction) at (0,3.25) [rectangle,draw,fill=blue!15] {\textbf{Chapter~1}\\Introduction}; \node[align=center] (chapter2) at (0,2.25) [rectangle,draw,fill=green!15] {Chapter~2\\The Stochastic\\Multi-Armed Bandit models}; \node[align=center] (chapter3) at (-2.5,2.25) [rectangle,draw,fill=gray!10,text=gray] {Chapter~3\\SMPyBandits: simulation\\library for MAB}; \node[align=center] (chapter25) at (+2.5,2.25) [rectangle,draw,fill=gray!10,text=gray] {Chapter~4\\Online selection\\of the best algorithm}; \node[align=center] (chapter4) at (-2.5,1) [rectangle,draw,fill=green!25] {\textbf{Chapter~5}\\Two MAB models\\for IoT networks}; \node[align=center] (chapter5) at (0,1) [rectangle,draw,fill=green!25] {\textbf{Chapter~6}\\Multi-players\\Multi-Armed Bandits}; \node[align=center] (chapter6) at (2.5,1) [rectangle,draw,fill=green!25] {\textbf{Chapter~7}\\Piece-Wise Stationary\\Multi-Armed Bandits}; \node[align=center] (conclusion) at (0,-0.25) [rectangle,draw,fill=blue!20] {\textbf{Chapter~8}\\General Conclusion}; % \node[align=center] (appendix) at (2.5,-0.25) [rectangle,draw,fill=yellow!10] {Appendix}; % \draw [color=black,thick,->] (introduction) to (chapter2); \draw [color=black,dotted,->] (chapter2) to (chapter3); \draw [color=black,dotted,->] (chapter2) to (chapter25); \draw [color=black,thick,->] (chapter2) to (chapter4); % \draw [color=black,thick,->] (chapter2) to (chapter5); \draw [color=black,thick,->] (chapter4) to (chapter5); % \draw [color=black,densely dotted,->] -| (chapter3) to (chapter25); % \draw [color=black,densely dotted,->] -| (chapter25) to (chapter6); \draw [color=black,thick,->] (chapter5) to (chapter6); % \draw [color=black,thick,->] (chapter2) to (chapter6); % \draw [color=black,thick,->] (chapter4) to (conclusion); % \draw [color=black,thick,->] (chapter5) to (conclusion); \draw [color=black,thick,->] (chapter6) to (conclusion); % \draw [color=black,thick,->] (conclusion) to (appendix); % \end{tikzpicture} } % \caption[Organization of the thesis: a reading map.]{A reading map of the thesis. Any top-down path containing Chapter~\ref{chapter:1}, Chapter~\ref{chapter:2}, at least one of the three Chapters~\ref{chapter:4}, \ref{chapter:5} and \ref{chapter:6}, and the Conclusion is a self contained way to read this thesis.} \label{fig:1:organization} \end{figure} \end{frameO} \begin{frameO}[Outline of this presentation] \begin{large} \begin{itemize} \setlength\itemsep{2em} \item \textcolor{gray}{\textbf{Introduction.} Spectrum issues in wireless networks} % \item \textcolor{gray}{\sout{The Stochastic Multi-Armed Bandit models}} % \begin{itemize} % \item \textcolor{gray}{applying bandit to Opportunistic Spectrum Access (OSA)} % \item \textcolor{gray}{performance measure (regret) and first strategies} % \item \textcolor{gray}{best possible regret? Lower bounds} % \item \textcolor{gray}{upper Confidence Bounds (UCB) Algorithms} % \end{itemize} \item \textbf{Part I.} Selfish MAB learning in a new model of IoT network % \begin{itemize} % % \item \textcolor{gray}{reference strategies} % \item \textcolor{gray}{selfish applications of MAB algorithms} % \item \textcolor{gray}{numerical simulations and illustrations} % \item \textcolor{gray}{realistic implementation on real radio hardware} % \item \textcolor{gray}{\emph{intractable} model in theory\dots} % \end{itemize} \item \textbf{Part II.} \emph{Two tractable problems} extending the classical bandit \begin{itemize} \item \textcolor{gray}{multi-player bandits in stationary settings} \item \textcolor{gray}{single-player bandits in piece-wise stationary settings} \end{itemize} \item \textbf{Conclusion and perspectives} \end{itemize} \end{large} \end{frameO} % \section{Introduction to Multi-Armed Bandits} % \begin{frameTI} % \begin{center} % {\textcolor{white} {\Huge \textsc{Introduction to Multi-Armed Bandits} }} % \end{center} % \vspace*{-4pt} % \end{frameTI} % \begin{frame}[c] % \begin{changemargin}{-0.5cm}{-0.5cm} % \begin{center} % \vspace{-0.3in} % \textbf{\huge Introduction to Multi-Armed Bandits} % \vspace{1.5cm} % \textbf{\Large Why Bandits?}\\[0.5cm] % \textcolor{darkgray}{\textbf{\Large Performance measure}\\[0.5cm] } % \textcolor{darkgray}{\textbf{\Large Best possible regret?}\\[0.5cm] } % \textcolor{darkgray}{\textbf{\Large The optimism principle}\\[0.5cm] } % \end{center} % \end{changemargin} % \end{frame} % \begin{frameO}[Hum, what is a \emph{bandit}?] % \begin{center} % It's an old name for a casino machine! % \end{center} % \begin{center} % \includegraphics[height=7cm]{Lucky_Luke__Le_Bandit_Manchot.jpg} % \begin{tiny} % \textcolor{gray}{ % \textcopyright{} Dargaud, % \href{https://www.dargaud.com/bd/LUCKY-LUKE/Lucky-Luke/Lucky-Luke-tome-18-Bandit-manchot-Le}{\textcolor{blue}{Lucky Luke tome 18}}. % } % \end{tiny} % \end{center} % \end{frameO} % \begin{frameO}[Make money in a casino?] % \begin{center} % \includegraphics[height=3cm]{MABpieuvre} % \end{center} % \begin{center} % A (single) \blue agent \black facing (multiple) \red arms \black in a Multi-Armed Bandit. % \end{center} % \pause % \begin{center} % \Huge NO! % \end{center} % \end{frameO} % \begin{frameO}[Sequential resource allocation] % \textbf{Clinical trials} % \begin{itemize} % \item $K$ treatments for a given symptom (with unknown effect) % \includegraphics[width=0.12\linewidth]{medoc1.jpg} % \hspace{0.05cm} % \includegraphics[width=0.12\linewidth]{medoc4.jpg} % \hspace{0.05cm} % \includegraphics[width=0.12\linewidth]{medoc3.jpg} % \hspace{0.05cm} % \includegraphics[width=0.12\linewidth]{medoc2.jpg} % \hspace{0.05cm} % \includegraphics[width=0.12\linewidth]{medoc5.jpg} % \hspace{0.05cm} % \includegraphics[width=0.12\linewidth]{medoc6.jpg} % \hspace{0.05cm} % \item What treatment should be allocated to the next patient, based on responses observed on previous patients? % \end{itemize} % \vspace{0.2cm} % \pause % \textbf{Online advertisement} % \begin{itemize} % \item $K$ adds that can be displayed % \vspace{0.1cm} % \includegraphics[height=0.15\paperheight]{ad6.jpg} % \hspace{0.1cm} % \includegraphics[height=0.15\paperheight]{ad2.jpg} % \hspace{0.1cm} % \includegraphics[height=0.15\paperheight]{ad4.jpg} % \hspace{0.1cm} % \includegraphics[height=0.15\paperheight]{ad5.jpg} % \hspace{0.05cm} % \item Which add should be displayed for a user, based on the previous clicks of previous (similar) users? % \end{itemize} % \end{frameO} % % \begin{frameO}[Dynamic allocation of computational resources] % % \vspace{0.4cm} % % \textbf{Numerical experiments} (bandits for ``black-box'' optimization) % % \vspace{-0.3cm} % % \begin{center} % % \includegraphics[height=2.5cm]{GP} % % \end{center} % % \vspace{-0.3cm} % % \begin{itemize} % % \item where to evaluate a costly function in order to find its maximum? % % \end{itemize} % % \pause % % \textbf{Artificial intelligence for games} % % \begin{center} % % \includegraphics[height=2.2cm]{MCTSWiki} % % \end{center} % % \vspace{-0.5cm} % % \begin{itemize} % % \item where to choose the next evaluation to perform in order to find the best move to play next? % % \end{itemize} % % \end{frameO} % \begin{frameO}[Dynamic channel selection] % \vspace{0.3cm} % \textbf{Communications in presence of a central controller} % \begin{itemize} % \item $K$ assignments from $n$ users to $m$ antennas ($\rightsquigarrow$ \emph{combinatorial} bandit) % \hspace{2.5cm}\includegraphics[height=0.2\paperheight]{assignements} % \item How to select the next \emph{matching} based on the throughput observed in previous communications? % \end{itemize} % \vspace{0.1cm} % \pause % \textbf{Opportunistic Spectrum Access (OSA)} % \begin{itemize} % \item $K$ radio channels (orthogonal frequency bands) % \hspace{0.4cm}\includegraphics[height=0.17\paperheight]{spectrum} % \item In which channel should a radio device send a packet, based on the quality of its previous communications? % \end{itemize} % \end{frameO} % %%% TITLE SLIDE FOR PART I % % standard slides for Part I % \setbeamertemplate{background canvas}{\includegraphics[width=\paperwidth,height=\paperheight]{../templateCS/PageTabInverse_CentraleSupelec}} % \setbeamertemplate{footline}{\hspace{2cm} \raisebox{2.5ex} % {\textcolor{white}{PhD defense -- Lilian Besson -- \emph{``MAB Algorithms for IoT Networks''}}}\hfill % \raisebox{2.5ex} % {\textcolor{white}{20 November, 2019 -- \insertframenumber / \inserttotalframenumber \hspace{5mm} \null }}} % \subsection{Multi-armed Bandit} % \begin{frameO}[\alt<2>{The \blue Stochastic \color{white} Multi-Armed Bandit Setup}{The Multi-Armed Bandit Setup}] % \alt<2>{\vspace{0.4cm}}{} % \begin{center} % $K$ \textbf{arms} $\Leftrightarrow$ $K$ \alt<2>{\blue probability distributions \black : $\nu_a$ has mean $\blue\mu_a$}{rewards streams $(X_{a,t})_{t\in\N}$} % \end{center} % \begin{center} % \includegraphics[height=0.15\textheight]{slot1.jpg} % \hspace{0.4cm} % \includegraphics[height=0.15\textheight]{slot2.jpg} % \hspace{0.4cm} % \includegraphics[height=0.15\textheight]{slot3.jpg} % \hspace{0.4cm} % \includegraphics[height=0.15\textheight]{slot4.jpg} % \hspace{0.5cm} % \includegraphics[height=0.15\textheight]{slot5.jpg} % \hspace{0.4cm} % \end{center} % \vspace{-0.8cm} % \[ \alt<2>{\blue\nu_1}{} \hspace{1.4cm} \alt<2>{\blue\nu_2}{} \hspace{1.4cm} \alt<2>{\blue\nu_3}{} \hspace{1.4cm} \alt<2>{\blue\nu_4}{} \hspace{1.4cm} \alt<2>{\blue\nu_5}{}\] % \alt<2>{\vspace{-0.4cm}}{} % At round $t$, an agent: % \begin{itemize} % \item chooses an arm $A_t$ % \item receives a reward \alt<2>{$R_t = X_{A_t,t}\blue \overset{\text{iid}}{\sim} \nu_{A_t}$ (i.i.d. from a distribution)}{$R_t = X_{A_t,t}$ (from the environment)} % \end{itemize} % \vspace{0.2cm} % \red Sequential \black sampling strategy (\textbf{bandit algorithm}): % $\red A_{t+1} = F_t (A_1,R_1,\dots,A_{t},R_{t})\black$. % \textbf{Goal:} Maximize sum of rewards \alt<2>{$\blue \bE\black\left[\sum\limits_{t=1}^T R_t\right]$}{$\sum\limits_{t=1}^T R_t$}. % \end{frameO} % \begin{frameO}[Discover bandits by playing this online demo!] % \begin{center} % \includegraphics[width=0.75\textwidth]{example_of_a_5_arm_bandit_problem.png} % \end{center} % % \begin{small} % $\hookrightarrow$ Interactive demo on this web-page % \href{https://perso.crans.org/besson/phd/MAB_interactive_demo/}{\textcolor{blue}{\texttt{perso.crans.org/besson/phd/MAB\_interactive\_demo/}}} % % Ref: [Bandits Algorithms, Lattimore \& Szepesv{\'a}ri, 2019], % % on \href{https://tor-lattimore.com/downloads/book/book.pdf}{\textcolor{blue}{\texttt{tor-lattimore.com/downloads/book/book.pdf}}} % % \end{small} % \end{frameO} % % \begin{frameO}[Clinical trials] % % \textbf{Historical motivation} \color{gray}[Thompson 1933]\color{black} % % \begin{center} % % \includegraphics[width=0.12\linewidth]{medoc1.jpg} % % \hspace{0.3cm} % % \includegraphics[width=0.12\linewidth]{medoc4.jpg} % % \hspace{0.3cm} % % \includegraphics[width=0.12\linewidth]{medoc3.jpg} % % \hspace{0.5cm} % % \includegraphics[width=0.12\linewidth]{medoc2.jpg} % % \hspace{0.5cm} % % \includegraphics[width=0.12\linewidth]{medoc5.jpg} % % \hspace{0.3cm} % % \end{center} % % \vspace{-0.8cm} % % \hspace{-0.3cm}\[ \cB(\mu_1) \hspace{0.9cm} \cB(\mu_2) \hspace{0.9cm} \cB(\mu_3) \hspace{0.8cm} \cB(\mu_4) \hspace{0.9cm} \cB(\mu_5)\] % % For the $t$-th patient in a clinical study, % % \begin{itemize} % % \item chooses a \blue treatment $A_t$\black % % \item observes a (Bernoulli) \blue response $R_t \in \{0,1\} : \bP(R_t = 1 | A_t = a) = \mu_{a}$\black % % \end{itemize} % % \vspace{0.3cm} % % \textbf{Goal:} maximize the expected number of patients healed. % % \end{frameO} % % \begin{frameO}[Online content optimization] % % \textbf{Modern motivation} ($\$\$\$\$$) \gray [Li et al, 2010] \black % % (recommender systems, online advertisement, etc) % % \begin{center} % % \includegraphics[height=0.15\textheight]{film1.jpg} % % \hspace{0.6cm} % % \includegraphics[height=0.15\textheight]{film2.jpg} % % \hspace{0.6cm} % % \includegraphics[height=0.15\textheight]{film3.jpg} % % \hspace{0.6cm} % % \includegraphics[height=0.15\textheight]{film4.jpg} % % \hspace{0.6cm} % % \includegraphics[height=0.15\textheight]{film5.jpg} % % \hspace{0.6cm} % % \end{center} % % \vspace{-0.8cm} % % \hspace{-0.2cm}\[ \nu_1 \hspace{1.4cm} \nu_2 \hspace{1.4cm} \nu_3 \hspace{1.4cm} \nu_4 \hspace{1.4cm} \nu_5\] % % For the $t$-th visitor of a website, % % \begin{itemize} % % \item recommend a \blue movie $A_t$\black % % \item observe a \blue rating $R_t \sim \nu_{A_t}$\black \ (e.g. $R_t \in \{1,\dots,5\}$) % % \end{itemize} % % \vspace{0.3cm} % % \textbf{Goal:} maximize the sum of ratings. % % \end{frameO} % \begin{frameO}[Application to Cognitive Radios: OSA] % \textbf{Opportunistic Spectrum Access} % \textcolor{gray}{ % % [Liu \& Zhao, 2010] % % [Anandkumar et al. 2011] % [Jouini, Moy et al. 2010] % } % \begin{center} % \emph{streams indicating channel quality} % \vspace{0.3cm} % \begin{tabular}{|c||c|c|c|c|c|c|c|} % \hline % Channel $1$ & \cellcolor{blue!25}$X_{1,1}$ & $X_{1,2}$ & \dots & $X_{1,t}$ & \dots & $X_{1,T}$ & $\sim \nu_1$ \\ % \hline % Channel $2$ & $X_{2,1}$ & \cellcolor{blue!25}$X_{2,2}$ & \dots & $X_{2,t}$ & \dots & \cellcolor{blue!25}$X_{2,T}$ & $\sim \nu_2$ \\ % \hline % \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ % \hline % Channel $K$ & $X_{K,1}$ & $X_{K,2}$ & \dots & \cellcolor{blue!25}$X_{K,t}$ & \dots & $X_{K,T}$ & $\sim \nu_K$ \\ % \hline % \end{tabular} % \end{center} % \vspace{0.2cm} % At round $t$, the device: % \begin{itemize} % \item selects \blue{a channel} $A_t \in \{1,\dots,K\}$\black % \item observes the \blue quality of its communication $R_t = X_{A_t,t} \in [0,1]$\black % \begin{itemize} % \item $R_T \in\{0,1\}$ binary reward: success/failure of message transmission % \item $R_T \in[0,1]$ continuous reward: e.g., received power, etc % \end{itemize} % \end{itemize} % \vspace{0.2cm} % \textbf{Goal:} Maximize the overall quality of communications. % \end{frameO} % \subsection{Performance measure and first strategies} % \begin{frame}[c] % \begin{changemargin}{-0.5cm}{-0.5cm} % \begin{center} % \vspace{-0.3in} % \textbf{\huge Introduction to Multi-Armed Bandits} % \vspace{1.5cm} % \textcolor{darkgray}{\textbf{\Large Why Bandits?}\\[0.5cm]} % \textbf{\Large Performance measure and first strategies}\\[0.5cm] % \textcolor{darkgray}{\textbf{\Large Best possible regret?}\\[0.5cm] } % \textcolor{darkgray}{\textbf{\Large The optimism principle}\\[0.5cm] } % \end{center} % \end{changemargin} % \end{frame} % \begin{frameO}[Regret of a bandit algorithm] % \bigskip % \textbf{Bandit instance:} $\bm\nu = (\nu_1,\nu_2, \dots,\nu_K)$, mean of arm $a$: $\mu_a = \bE_{X \sim \nu_a}[X]$. % \[\red\mu_\star = \max_{a \in \{1,\dots,K\}} \mu_a \ \ \text{and} \ \ \ a_\star = \argmax_{a \in \{1,\dots,K\}} \mu_a.\] % \[\begin{array}{ccl}\text{Maximizing rewards} & \Leftrightarrow & \text{selecting } a_\star \text{ as much as possible } \\ % & \Leftrightarrow & \text{minimizing the \blue regret } \gray \text{[Robbins, 52]} % \end{array}\] % \vspace{-0.4cm} % \begin{eqnarray*} % \blue \cR_{\bm\nu}(\cA,T) \eqdef \black\underbrace{\blue T \mu_\star}_{\substack{\text{sum of rewards of}\\ \text{an oracle strategy} \\ \text{always selecting } a_\star}} \blue- \black\underbrace{\blue\bE\left[\sum_{t=1}^{T}R_{t}\right]}_{\substack{\text{sum of rewards of}\\\text{the strategy} \cA}} % \end{eqnarray*} % \vspace{-0.4cm} % \pause % \begin{colorblock}{What regret rate can we achieve?} % \begin{itemize} % \item[$\Longrightarrow$] consistency \black $\cR_{\bm\nu}(\cA,T) / T \Longrightarrow 0$ (when $T\to\infty$) % \item[$\Longrightarrow$] can we be more precise? % \end{itemize} % \end{colorblock} % \end{frameO} % \begin{frameO}[Regret decomposition] % \vspace{0.6cm} % $N_a(t)$ : number of selections of arm $a$ in the first $t$ rounds % $\Delta_a \eqdef \mu_\star -\mu_a$ : sub-optimality gap of arm $a$ % \begin{colorblock}{Regret decomposition} % \[\alert<1>{ \cR_{\bm\nu}(\cA,T) = \sum_{a=1}^K \Delta_a \bE\left[N_a(T)\right] }.\] % \end{colorblock} % \pause % \vspace{0.6cm} % A strategy with small regret should: % \begin{itemize} % \item select not too often arms for which $\Delta_a > 0$ (sub-optimal arms) % \item \dots which requires to try all arms to estimate the values of the $\Delta_a$ % \end{itemize} % \vspace{0.5cm} % \begin{center} % \red $\Longrightarrow$ Exploration / Exploitation trade-off ! % \end{center} % \end{frameO} % \begin{frameO}[Two naive strategies] % \vspace{0.4cm} % \begin{itemize} % \item \textbf{Idea 1 :} % \hfill{} \color{red}$\Longrightarrow$ EXPLORATION \color{black} % \begin{colorblock}{}Draw each arm $T/K$ times\end{colorblock} % \end{itemize} % \vspace{-0.3cm} % \[\hookrightarrow \cR_{\bm\nu}(\cA,T) = \left(\frac{1}{K}\sum_{a : \mu_a > \mu_\star} \Delta_a\right) T = \alert{\Omega(T)} \] % \pause % \begin{itemize} % \item \textbf{Idea 2 :} Always trust the empirical best arm % \hfill{} \color{red}$\Longrightarrow$ EXPLOITATION \color{black} % \end{itemize} % \begin{colorblock}{} % $A_{t+1}=\underset{a \in \{1,\dots,K\}}{\text{argmax}} \ \blue \widehat{\mu}_a(t)$ % using estimates of the unknown means $\mu_a$ % \[\blue \widehat{\mu}_a(t) =\frac{1}{N_a(t)}\sum_{s=1}^t X_{a,s} \ind_{(A_s=a)}\] % \end{colorblock} % \vspace{-0.3cm} % \[\hspace{1.5cm} \hookrightarrow \cR_{\bm\nu}(\cA,T) \geq (1-\mu_1)\times \mu_2 \times (\mu_1 - \mu_2) T = \alert{\Omega(T)} \] % \begin{center}\vspace{-0.2cm} % \hspace{1.5cm}(with $K=2$ Bernoulli arms of means $\mu_1 \neq \mu_2$) % \end{center} % \end{frameO} % \subsection{Best possible regret? Lower bounds} % \begin{frame}[c] % \begin{changemargin}{-0.5cm}{-0.5cm} % \begin{center} % \vspace{-0.3in} % \textbf{\huge Introduction to Multi-Armed Bandits} % \vspace{1.5cm} % \textcolor{darkgray}{\textbf{\Large Why Bandits?}\\[0.5cm]} % \textcolor{darkgray}{\textbf{\Large Performance measure and first strategies}\\[0.5cm]} % \textbf{\Large Best possible regret? Lower bounds}\\[0.5cm] % \textcolor{darkgray}{\textbf{\Large The optimism principle}\\[0.5cm] } % \end{center} % \end{changemargin} % \end{frame} % \begin{frameO}[The Lai and Robbins lower bound] % \vspace{0.3cm} % \textbf{Context:} a \blue parametric bandit model \black where each arm is parameterized by its mean $\bm\nu =(\nu_{\mu_1},\dots,\nu_{\mu_K})$, $\mu_a \in \cI$. % \[ \text{distributions } \bm\nu \ \ \Leftrightarrow \ \ \bm\mu = (\mu_1,\dots,\mu_K) \text{ means} \] % \textbf{Key tool:} \blue Kullback-Leibler divergence\black. % \begin{colorblock}{Kullback-Leibler divergence} % \alt<3>{\vspace{-0.2cm}}{} % \[ % \red \mathrm{kl}(\mu,\mu') \black : = \alt<3>{\mu\log \left(\frac{\mu}{\mu'}\right) + (1-\mu) \log \left(\frac{1-\mu}{1-\mu'}\right) \ \ \ (\text{Bernoulli bandits})}{\alt<2>{\frac{(\mu - \mu')^2}{2\sigma^2} \ \ \ (\text{Gaussian bandits with variance } \sigma^2)}{\text{KL}\left(\nu_\mu,\nu_{\mu'}\right) =\bE_{X \sim \nu_{\mu}}\left[\log \frac{d\nu_{\mu}}{d\nu_{\mu'}}(X)\right]}} % \] % \vspace{-0.3cm} % \end{colorblock} % \begin{colorblock}{Theorem \hfill{} \textcolor{gray}{[Lai and Robbins, 1985]}} % For uniformly efficient algorithms ($\cR_{\bm\mu}(\cA,T)=o(T^\alpha)$ for all $\alpha\in (0,1)$ and $\bm \mu \in \cI^K$), % \vspace{-0.4cm} % \[ % \color{red}\mu_a<\mu_\star \Longrightarrow \liminf_{T\rightarrow\infty}\frac{\bE_{\bm \mu}[N_{a}(T)]}{\log T}\geq \frac{1}{\mathrm{kl}(\mu_a,\mu_\star)}.\color{black} % \] % \vspace{-0.3cm} % \end{colorblock} % \end{frameO} % \begin{frameO}[Other asymptotic lower bounds] % Such asymptotic lower bound can be generalized to extensions of the stationary single-player MAB model % $ \cR(\cA, T) \geq \Omega(C_{\text{problem}} K \log(T)) $. % \vspace*{2pt} % \begin{lightblock}{For \textbf{multi-player bandits} \hfill{} (with $2 \leq M \leq K$ players)} % Same lower-bound, with a problem-dependent constant $C'_{\text{problem}}$ % \[ \cR(\cA, T) \geq \Omega(C'_{\text{problem}} M K \log(T)). \] % \end{lightblock} % \vspace*{2pt} % \begin{lightblock}{For \textbf{piece-wise stationary bandits} \hfill{} (with $\Upsilon_T$ stationary intervals)} % Larger lower-bound, with a problem-dependent constant $C''_{\text{problem}}$ % \[ \cR(\cA, T) \geq \Omega(C''_{\text{problem}} \sqrt{K \Upsilon_T T}). \] % \end{lightblock} % \textcolor{gray}{(our proposed algorithms are asymptotically matching the lower-bounds)} % \end{frameO} % \subsection{The Optimism Principle and Upper Confidence Bounds Algorithms} % \begin{frame}[c] % \begin{changemargin}{-0.5cm}{-0.5cm} % \begin{center} % \vspace{-0.3in} % \textbf{\huge Introduction to Multi-Armed Bandits} % \vspace{1.5cm} % \textcolor{darkgray}{\textbf{\Large Why Bandits?}\\[0.5cm]} % \textcolor{darkgray}{\textbf{\Large Performance measure and first strategies}\\[0.5cm]} % \textcolor{darkgray}{\textbf{\Large Best possible regret? Lower bounds}\\[0.5cm]} % \textbf{\Large The optimism principle:\\ % Upper Confidence Bounds Algorithms}\\[0.5cm] % \end{center} % \end{changemargin} % \end{frame} % \begin{frameO}[A first UCB algorithm] % \vspace{0.3cm} % \begin{itemize} % \item $N_a(t) = \sum_{s=1}^t\ind_{(A_s = a)}$ number of selections of $a$ after $t$ rounds % \item $\hat \mu_{a,s} = \frac{1}{s}\sum_{k=1}^s Y_{a,k}$ average of the first $s$ observations from arm $a$ % \item $\widehat{\mu}_a(t) = \widehat{\mu}_{a,N_a(t)}$ empirical estimate of $\mu_a$ after $t$ rounds % \end{itemize} % \vspace{0.3cm} % UCB($\alpha$) selects $A_{t+1} = \argmax_a \ \mathrm{UCB}_a(t)$ % where % \[\blue \mathrm{UCB}_a(t) =\black \underbrace{\blue \widehat{\mu}_{a}(t)}_{\text{exploitation term}} + \underbrace{\blue\sqrt{\frac{\alpha\log(t)}{N_a(t)}}}_{\text{exploration bonus}}.\] % \vspace{0.3cm} % \begin{colorblock}{Hoeffding inequality + union bound \hfill{} \textcolor{gray}{[Auer et al. 2002]}} % \[ \bP\left(\mu_a \leq \red \widehat{\mu}_a(t) + \sigma\sqrt{\frac{\alpha\log(t)}{N_a(t)}} \black \right) \geq 1 - \frac{1}{t^{\frac{\alpha}{2} -1}} \] % \end{colorblock} % % \pause % % \textbf{Proof.} % % \vspace{-0.5cm} % % \begin{align*} % % & \bP\left(\mu_a > \widehat{\mu}_a(t) + \sigma\sqrt{\frac{\alpha\log(t)}{N_a(t)}} \black \right) \leq \bP\left(\exists s \leq t : \mu_a > \widehat{\mu}_{a,s} + \sigma\sqrt{\frac{\alpha\log(t)}{s}} \black\right) \\ % % & \leq \sum_{s=1}^t \bP\left(\widehat{\mu}_{a,s} < \mu_a - \sigma\sqrt{\frac{\alpha\log(t)}{s}}\right) \leq \sum_{s=1}^t \frac{1}{t^{\alpha/2}} = \frac{1}{t^{\alpha/2 - 1}}. % % \end{align*} % \end{frameO} % % \begin{frameO}[A first UCB algorithm] % % \vspace{0.4cm} % % UCB($\alpha$) selects $A_{t+1} = \argmax_a \ \mathrm{UCB}_a(t)$ % % where % % \[\blue \mathrm{UCB}_a(t) =\black \underbrace{\blue \widehat{\mu}_{a}(t)}_{\text{exploitation term}} + \underbrace{\blue\sqrt{\frac{\alpha\log(t)}{N_a(t)}}}_{\text{exploration bonus}}.\] % % \begin{itemize} % % \item this form of UCB was first proposed for Gaussian rewards % % \gray [Katehakis and Robbins, 95]\black % % \item popularized by \color{gray}[Auer et al. 02] \color{black} for bounded rewards:\\ % % \red UCB1, for $\alpha=2$\black % % \item the analysis was UCB($\alpha$) was further refined to hold for $\alpha > 1/2$ in that case \gray [Bubeck, 11, Cappé et al. 13] \black % % \end{itemize} % % \end{frameO} % \begin{frameO}[A UCB algorithm in action \textcolor{gray}{[Kaufmann, 2014]} \hfill{} (movie)] % \begin{center} % \movie{\includegraphics[width=0.9\textwidth]{KLUCB.pdf}}{KLUCB.avi} % \end{center} % \end{frameO} % % \subsection{Analysis of UCB($\alpha$)} % % \begin{frame}[c] % % \begin{changemargin}{-0.5cm}{-0.5cm} % % \begin{center} % % \vspace{-0.3in} % % \textbf{\huge Optimistic Algorithms} % % \vspace{1.5cm} % % \textcolor{darkgray}{\textbf{\Large Building Confidence Intervals} \\[0.5cm]} % % {\textbf{\Large Analysis of UCB($\alpha$)}\\[0.5cm] } % % % \textcolor{darkgray}{\textbf{\Large Other UCB algorithms}\\[0.5cm]} % % \end{center} % % \end{changemargin} % % \end{frame} % \begin{frameO}[Regret of UCB($\alpha$) for bounded rewards] % \vspace{0.3cm} % \begin{colorblock}{Theorem \hfill{} \gray[Auer et al, 02]\black} % UCB($\alpha$) with parameter $\alpha=2$ satisfies % \vspace{-0.4cm} % \[\cR_{\bm\nu}(\texttt{UCB1},T) \leq 8 \left(\sum_{a : \mu_a < \mu_\star} \frac{1}{\Delta_a}\right)\log(T) + (1+\frac{\pi^2}{3})\left(\sum_{a=1}^K \Delta_a\right).\] % \end{colorblock} % \vspace{1cm} % In some of our works, we use an extension of UCB called kl-UCB. % % FIXME talk about kl-UCB: just one block saying it works similarly but it is smarter? % \begin{colorblock}{Theorem \hfill{} \gray[Garivier et al, 2013]\black} % For bounded rewards, kl-UCB satisfies $\cR_{\bm\nu}(\texttt{kl-UCB},T) = \mathcal{O}(K C \log(T))$: % \vspace{-0.4cm} % \[\cR_{\bm\nu}(\texttt{kl-UCB},T) \leq \left(\sum_{a : \mu_a < \mu_\star} \frac{\Delta_a}{\texttt{kl}(\mu_a, \mu_\star)}\right)\log(T) + os(\log(T)).\] % \end{colorblock} % % \begin{itemize} % % \item[$\Longrightarrow$] what we will prove today % % \end{itemize} % % \begin{colorblock}{Theorem} For every $\alpha>1$ and every sub-optimal arm $a$, there exists a constant $C_\alpha>0$ such that % % \vspace{-0.8cm} % % \[\bE_{\bm \mu}[N_a(T)] \leq \frac{4\alpha}{(\mu_\star - \mu_a)^2}\log(T) + C_\alpha.\] % % \end{colorblock} % % \vspace{0.2cm} % % It follows that % % \vspace{-0.6cm} % % \[\cR_{\bm\nu}(\mathrm{UCB}(\alpha),T) \leq 4\alpha\blue\left(\sum_{a : \mu_a < \mu_\star}\frac{1}{\Delta_a}\right)\black\log(T) + K C_\alpha\black.\] % \end{frameO} \section{Selfish MAB learning in IoT Networks} \begin{frameTI} \begin{center} {\textcolor{white} {\Huge \textsc{Part I.} }} \end{center} \vspace*{10pt} \begin{center} {\textcolor{white} {\Huge \textsc{Selfish MAB Learning} }} \end{center} \begin{center} {\textcolor{white} {\Huge \textsc{in IoT Networks} }} \end{center} % \vspace*{-4pt} \vfill{} \small{\textcolor{lightgray}{Ref: Chapter 5 of my thesis, and [Bonnefoi, Besson et al, 17].}} \end{frameTI} \input{crowncom2017.tex} \begin{frameO}[We implemented this with real hardware \hfill{} ($1/3$)] We developed a realistic demonstration using USRP boards and GNU Radio, as a proof-of-concept in a ``toy'' IoT network. \begin{center} \movie{\includegraphics[width=0.65\textwidth]{screenshotDemoYouTube.png}}{videos/demoICT2018.mkv} \end{center} % \hfill{} \begin{tiny} \textcolor{gray}{[Bonnefoi et al, ICT 18], [Besson et al, WCNC 19], Ch.5.3} % \newline \textcolor{gray}{and video published on} \textcolor{blue}{\texttt{YouTu.be/HospLNQhcMk}} \end{tiny} \end{frameO} \begin{frameO}[Using USRP board to simulate IoT devices \hfill{} ($2/3$)] \begin{center} % \movie{\includegraphics[width=0.90\textwidth]{screenshotDemoYouTube_Partie1.png}}{videos/Partie1.mp4} \movie{\includegraphics[height=0.90\textheight]{our-demo}}{videos/Partie1.mp4} \end{center} \end{frameO} \begin{frameO}[GNU Radio for the UI of the demo \hfill{} ($3/3$)] \begin{center} % \movie{\includegraphics[width=0.90\textwidth]{screenshotDemoYouTube_Partie2.png}}{videos/Partie2.mp4} \movie{\includegraphics[width=1.01\textwidth]{UI}}{videos/Partie2.mp4} \end{center} \end{frameO} \begin{frameO}[From practice to theory] % from part I : Selfish MAB learning for IoT \textcolor{orange}{\textbf{It works very well empirically}!} But \alert{random activation times} and \alert{collisions due to multiple devices} make the model \textbf{hard to analyze}\dots % \begin{itemize} \setlength\itemsep{5pt} % \tightlist \item \textcolor{darkgreen}{\underline{Hyp 1:}} in avg. $p \times D$ dynamic devices \includegraphics[height=0.37cm]{dynamic-devices.png} are using $K$ channels \slotmachine{}\newline \hfill{} $\implies$ so $p \leq \frac{K}{D}$ or $D \leq \frac{K}{p}$ gives best performance \item \textcolor{deeppurple}{\underline{Hyp 2:}} we assumed a stationary background traffic \includegraphics[height=0.37cm]{static-devices.png} \dots \end{itemize} \pause \begin{alertblock}{} \textbf{Goal}: obtain theoretical result for our proposed model of IoT networks, and guarantees about the observed behavior of \emph{Selfish MAB learning}. \end{alertblock} \pause \begin{colorblock}{} \textcolor{orange}{We can study theoretically two more specific models} % , in two directions \begin{itemize} \item \textcolor{darkgreen}{\underline{Model 1:}} \textbf{multi-player bandits}: devices \includegraphics[height=0.37cm]{dynamic-devices.png} are always activated\\ ie. $p=1$ in their random activation process $\implies$ $D = M \leq \frac{K}{p} = K$ \item \textcolor{deeppurple}{\underline{Model 2:}} \textbf{non-stationary bandits} (for one device \includegraphics[height=0.37cm]{dynamic-devices.png}) \end{itemize} % \hfill{} % $\implies$ Both are \textbf{tractable problems} ! \end{colorblock} \end{frameO} \section{Theoretical analysis of two relaxed models} \begin{frameTI} \begin{center} {\textcolor{white} {\Huge \textsc{Part II.} }} \end{center} \vspace*{10pt} \begin{center} % {\textcolor{white} {\Huge \textsc{Theoretical analysis of two relaxed models} }} {\textcolor{white} {\Huge \textsc{Theoretical analysis of} }} \end{center} \begin{center} {\textcolor{white} {\Huge \textsc{two relaxed models} }} \end{center} % \vspace*{-4pt} \vfill{} \small{\textcolor{lightgray}{Ref: Chapters 6 and 7 of my thesis\newline and [Besson \& Kaufmann, 18] and [Besson et al, 19].}} \end{frameTI} % \begin{frame}[c] % \begin{changemargin}{-0.5cm}{-0.5cm} % \begin{center} % \vspace{-0.3in} % \textbf{\huge Theoretical analysis of \\two relaxed models} % \vspace{1.5cm} % \Large \textbf{Many different extensions}\\ % \small{For your curiousity\dots} % \\[0.5cm] % \textcolor{darkgray}{\textbf{\Large Multi-player bandits}\\[0.5cm]} % \textcolor{darkgray}{\textbf{\Large Piece-wise stationary bandits}} % \end{center} % \end{changemargin} % \end{frame} % \begin{frameO}[Many other bandits models and problems (1/2)] % Most famous extensions: % \begin{itemize}%[<+->] % \setlength\itemsep{1em} % \item (centralized) multiple-actions % \begin{itemize} % \item \textcolor{blue}{multiple choice}: choose $m\in\{2,\dots,K-1\}$ arms (fixed size) % \item combinatorial: choose a subset of arms $S \subseteq \{1,\dots,K\}$ (large space) % \end{itemize} % \item non-stationary % \begin{itemize} % \item \textcolor{blue}{piece-wise stationary / abruptly changing} % \item slowly-varying, rotting\dots % \item adversarial\dots % \end{itemize} % \item (decentralized) collaborative/communicating bandits over a graph % \item \textcolor{blue}{(decentralized) non-communicating multi-player bandits} % \end{itemize} % % \hspace*{5cm} % \vfill{} % \hfill{} % \textcolor{blue}{$\hookrightarrow$ Implemented in our library \textbf{SMPyBandits}!} % \end{frameO} % \begin{frameO}[Many other bandits models and problems (2/2)] % % \textcolor{gray}{And many more extensions\dots} % \begin{itemize}%[<+->] % \setlength\itemsep{0.6em} % \item \textcolor{blue}{non-stochastic, Markov models rested/restless} % \item best arm identification (vs reward maximization) % \begin{itemize} % \item \textcolor{gray}{fixed budget setting} % \item \textcolor{gray}{fixed confidence setting} % \item \textcolor{gray}{PAC (probably approximately correct) algorithms} % \end{itemize} % \item for some applications (content recommendation etc) % \begin{itemize} % \item \textcolor{gray}{contextual bandits: observe a reward and a \emph{context} ($C_t \in\mathbb{R}^d$)} % \item \textcolor{gray}{cascading bandits} % \item \textcolor{gray}{delayed feedback bandits} % \item \textcolor{gray}{bandits with (differential) privacy constraints} % \end{itemize} % \item structured bandits (\textcolor{blue}{sparse}, low-rank, many-armed, Lipschitz etc) % \item $\mathcal{X}$-armed, continuous-armed bandits % \item \textcolor{gray}{and many more} % \end{itemize} % % \hspace*{5cm} % \vfill{} % \hfill{} % \textcolor{blue}{$\hookrightarrow$ Implemented in our library \textbf{SMPyBandits}!} % \end{frameO} \begin{frame}[c] \begin{changemargin}{-0.5cm}{-0.5cm} \begin{center} \vspace{-0.3in} \textbf{\huge Theoretical analysis of\\ two relaxed models} \vspace{1.5cm} % \textcolor{darkgray}{\Large \textbf{Many different extensions} \\[0.5cm]} % \textcolor{darkgray}{\Large \textbf{Insights from the Optimal Solution}} \\[0.5cm] \textbf{\Large Multi-player bandits}\\ \small{\textcolor{gray}{Ref: Chapter 6 of my thesis, and [Besson \& Kaufmann, 18].}} \\[0.5cm] \textcolor{darkgray}{\textbf{\Large Piece-wise stationary bandits}} \end{center} \end{changemargin} \end{frame} \subsection{Bandits for multiple devices} \begin{frameO}[Multi-players bandits: setup] \orange $M \geq 2$ players \black \includegraphics[height=0.37cm]{dynamic-devices.png} playing \textit{the same} $K$-armed bandit \hfill{} ($2 \leq M \leq K$) \newline they are all activated at each time step, ie. \textcolor{orange}{$p=1$} % with \textbf{no communication} between them \vspace{0.3cm} \begin{lightblock}{} At round $t \in\{1,\dots, T\}$: \begin{itemize} \item player $m$ selects arm $A^m_{t}$ \slotmachine{} ; then \textit{this arm generates} $s_{A^m_{t},t} \in \{0,1\}$ \item and the reward is computed as \end{itemize} % \vspace{-0.2cm} \[\red r_{m,t} = \left\{ \begin{array}{cl} s_{A^m_{t},t} & \text{if no other player chose the same arm} \\ 0 & \text{else (= COLLISION)} \end{array}\right.\] \end{lightblock} \pause \vspace{-0.3cm} \begin{colorblock}{Goal} % \textbf{Goal:} \begin{itemize} \item maximize centralized (sum) rewards $\sum\limits_{m=1}^M \sum\limits_{t=1}^T r_{m,t}$ \item \dots{} \textcolor{orange}{without (explicit) communication} between players \item trade-off: exploration / exploitation / \alert{and collisions !} \end{itemize} \end{colorblock} % \underline{\orange Cognitive radio}: (OSA) sensing, attempt of transmission if no PU, possible collisions with other SUs \end{frameO} \begin{frameO}[Multi-Players bandits for Cognitive Radios] \textcolor{darkblue}{Different observation models}: players observe $s_{A^m_{t},t}$ and/or $r_{m,t}$ \vspace*{20pt} \begin{darkblock}{\# 1: ``Listen before talk'' \hfill{} {\tiny \textcolor{lightgray}{[Liu \& Zhao, 10], [Jouini et al. 10], [Anandkumar et al. 11]}} } \begin{itemize} \item Good model for \textcolor{orange}{Opportunistic Spectrum Access} (OSA) \item First do sensing, attempt of transmission if no Primary User (PU), possible collisions with other Secondary Users (SU). \item \textcolor{darkblue}{\emph{Feedback model:}} \begin{itemize} \item observe first $s_{A^m_{t},t}$, \item if $s_{A^m_{t},t} = 1$, transmit and then observe the joint $r_{m,t}$, \item else don't transmit and don't observe a reward. \end{itemize} \end{itemize} \end{darkblock} \end{frameO} \begin{frameO}[M-P bandits for Cognitive Radios: proposed models] \begin{colorblock}{\# 2: ``Talk and maybe collide'' \hfill{} \textcolor{lightgray}{[Besson \& Kaufmann, 18]} } \begin{itemize} \item Good model for \textcolor{orange}{Internet of Things} (IoT) \item Do not do any sensing, just transmit, and wait for an acknowledgment before any next message. \item \textcolor{darkblue}{\emph{Feedback model:}} \begin{itemize} \item observe only the joint information $r_{m, t}$, \item no collision if $r_{m, t} \neq 0$, \item but cannot distinguish between collision or zero reward if $r_{m, t} = 0$. \end{itemize} % \item % \textcolor{gray}{We studied an extension with retransmissions in [Bonnefoi et al, WCNC 19], Ch.5.4.} \end{itemize} \end{colorblock} \pause \begin{lightblock}{\# 3: ``Observe collision then talk?'' \hfill{} {\tiny \textcolor{lightgray}{[Besson \& Kaufmann, 18], [Boursier et al, 19]}} } \begin{itemize} \item A third ``hybrid'' model {\small studied by several recent papers, following our work} \item \textcolor{darkblue}{\emph{Feedback model:}} \begin{itemize} \item first check if collision, \item then if not collision, receive joint reward $r_{m, t}$. % \alert{(less realistic for cognitive radio applications)} \end{itemize} \end{itemize} \end{lightblock} \end{frameO} % \begin{frameO}[Multi-players bandits: algorithms] % \only<1-2>{ % \textbf{Idea:} combine a good \textit{bandit algorithm} (usually index policy)\newline % with an \emph{orthogonalization strategy} (collision avoidance protocol) % \vspace{0.2cm} % } % \only<1>{ % \begin{darkblock}{Old idea: UCB1 index + $\rho^{\text{rand}}$ rule} % \begin{itemize} % \item At round $t$, each player $m\in\{1,\dots,M\}$ % \item has a stored rank $R_{m,t} \in \{1,\dots,M\}$ % \item selects the arm that has \red the $R_{m,t}$-largest UCB\black % \item if a collision occurs, draws a new rank $R_{m,t+1} \sim \cU(\{1,\dots,M\})$ % \item (any index policy may be used in place of UCB1) % \item nice $\cR(\cA, T) = \mathcal{O}(M^2 K \log(T))$ regret bound\dots\\ % but \alert{their proof was wrong!} % \item \textbf{Early references}: \color{gray} [Liu \& Zhao, 10] [Anandkumar et al., 11]\black % \end{itemize} % \end{darkblock} % } % \only<2->{ % \begin{colorblock}{\textbf{Our algorithm:} klUCB index + MCTopM rule} % \begin{itemize} % \only<2>{ % \item same idea, but don't use ranks, just fix on one of the $M$ best arms % \item more complicated behavior (musical chair game) % \item we obtain a $\cR(\cA, T) = \mathcal{O}(M^3 \frac{1}{\Delta_M} \log(T))$ regret upper bound % \item lower bound is $\cR(\cA, T) \geq \Omega(M \frac{1}{\Delta_M} \log(T))$\\ % ($\equiv$ as easy as centralized multiple-play bandits) % \item our algorithm is order optimal, not asymptotically optimal % } % \item \textbf{Our paper from ALT 2018}: \color{gray} [Besson \& Kaufmann, 2018] % \end{itemize} % \end{colorblock} % } % % \only<3->{ % % \textbf{Questions?} % % \begin{itemize} % % \item The number of players $M$ has to be known\\ % % $\Longrightarrow$ but it is possible to estimate it quickly, on the run % % \item Our algorithm does not handle an evolving number of devices\\ % % (entering/leaving the network) % % \item Is it a \textit{fair} orthogonalization rule? (yes! in average) % % \vspace*{10pt} % % \item Could players use the collision indicators to communicate? (yes!)\\ % % \end{itemize} % % $\hookrightarrow$ \textbf{\textsc{Sic-MMAB}} strategy matches the centralized multiple-play lower-bound, % % by using collision indicators to build a communication protocol between devices (\emph{in another feedback model}) % % \textcolor{gray}{[Boursier et al, 19]} % % } % \end{frameO} \begin{frameO}[Regret for multi-player bandits ($M$ players on $K$ arms)] % \only<2-2>{\vspace{-0.2cm}} \only<1>{ \underline{Hypothesis:} arms sorted by decreasing mean: $\mu_1 \geq \mu_2 \geq \dots \geq \mu_K$ $$R_{\bm\mu}(\cA,T) := \underbrace{\left(\sum_{k=1}^{M}{\mu_k}\right) T}_{\text{oracle total reward}} - {\bE_{\bm\mu}^{\cA}}\left[\sum_{t=1}^T\sum_{m=1}^M r_{m,t} \right]$$ } \vspace{-0.3cm} \begin{colorblock}{Regret decomposition \hfill{} {\small \textcolor{lightgray}{[Besson \& Kaufmann, 18]}}} \begin{small} % % If all $M$ players follow the decentralized algorithm $\cA$ % \alt<2>{ \[R_{\bm\mu}(\cA,T) \leq \text{cst} \sum_{k=M+1}^K \bE\left[\textcolor{orange}{N_k(T)}\right] + \text{cst'} \sum_{k=1}^M \bE\left[\textcolor{red}{\mathcal{C}_k(T)}\right].\] % \vspace{0.2cm} }{ \vspace*{-10pt} % \vspace{-0.3cm} \begin{align*} & R_{\bm\mu}(\cA,T) = {\sum_{k=M+1}^K (\mu_M - \mu_k) \bE[\textcolor{orange}{N_k(T)}]} \\ &\hspace{1cm}{+ {\sum_{k=1}^M (\mu_k - \mu_M) \left(T - \bE[\textcolor<1>{orange}{N_k(T)}]\right)} + {\sum_{k=1}^{K} \mu_k \bE[\textcolor{red}{\mathcal{C}_k(T)}]}.} \end{align*} } \vspace*{-5pt} \end{small} \end{colorblock} % \only<2-2>{\vspace{0.3cm}} \alt<2>{ \vspace*{15pt} A good algorithm has to control both \begin{itemize} \item the number of \textcolor{orange}{selections of sub-optimal arms}\newline $\hookrightarrow$ with a good classical bandit policy: like kl-UCB \item the number of \textcolor{red}{collisions} on optimal arms\newline $\hookrightarrow$ with a good orthogonalization procedure \end{itemize}}{ \begin{itemize} \item \textcolor{orange}{$N_k(T)$ total number of selections of arm $k$} \item \textcolor{red}{$\cC_k(T)$ total number of collisions experienced on arm $k$} \end{itemize}} \end{frameO} \begin{frameO}[The MC-Top-$M$ algorithm (for the OSA case)] % \begin{colorblock}{Feedback model} % Agent $m$ observes: % \begin{itemize} % \item the \orange sensing information \black of the chosen arm, $s_{A^m(t),t}$ % \item his reward $r_{m,t}$\black % \end{itemize} % \end{colorblock} % \pause % \vspace{0.2cm} \begin{alertblock}{} At round $t$, player $m$ uses his past sensing information to: \begin{itemize} \item compute an Upper Confidence Bound for each mean $\mu_k$, $\UCB^m_k(t)$ \item use the UCBs to \alert{estimate the $M$ best arms} \[\alert{\hat{M}^m(t)} := \left\{ \text{arms with } M \text{ largest } \UCB^m_k(t)\right\}\] \end{itemize} \end{alertblock} \vspace*{10pt} \begin{colorblock}{} Two simple ideas: \hfill{} {\small inspired by Musical Chair \color{gray}[Rosenski et al. 16] \color{black}} \begin{itemize} \item always pick an arm estimated as ``good'' \hfill{} $\color{red} A^m(t) \in \hat{M}^{m}(t-1)$ \item try not to switch arm too often \end{itemize} \[\orange \sigma^m(t) := \left\{ \text{player } m \text{ is ``fixed'' at the end of round } t \right\}\] \vspace*{-5pt} \end{colorblock} % \vspace{-0.3cm} \vfill{} \begin{small} \emph{Other UCB-based algorithms}: TDFS \textcolor{gray}{[Lui and Zhao, 10]},\\ Rho-Rand \textcolor{gray}{[Anandkumar et al., 11]}, Selfish \textcolor{gray}{[Bonnefoi, Besson et al., 17]} \end{small} \end{frameO} \begin{frameO}[The MC-Top-$M$ algorithm (for the OSA case)] \begin{figure}[h!] \scalebox{0.63}{\begin{minipage}{1.65\textwidth} %% https://tex.stackexchange.com/a/366403/ \begin{tikzpicture}[>=latex',line join=bevel,scale=5.5] % \node (start) at (1.5,0.30) {$(0)$ Start $t=0$}; % \pause \node (notfixed) at (1,0) [draw,rectangle,very thick] {Not fixed, $\overline{\sigma^m(t)}$}; % \draw [color=black,very thick,->] (start) -> (notfixed.20); % \pause \path [color=blue,very thick,->] (notfixed) edge[loop right] node[right,text width=4cm,text badly centered,black] {\small \textcolor{blue}{$\bold{(2)}$} $C^m(t), A^m(t) \in \hat{M}^{m}(t)$} (1); % \pause \path [color=red,very thick,->] (notfixed) edge[loop below] node[below,text centered,black] {\small \textcolor{red}{$\bold{(3)}$} $A^m(t) \notin \hat{M}^{m}(t)$} (1); % \pause \node (fixed) at (0,0) [draw,rectangle,very thick] {Fixed, $\sigma^m(t)$}; \draw [color=cyan,very thick,->] (notfixed) to[bend right] node[midway,above,text width=5cm,text centered,black] {\small \textcolor{cyan}{$\bold{(1)}$} $\overline{C^m(t)}, A^m(t) \in \hat{M}^{m}(t)$} (fixed); % \pause \path [color=darkgreen,very thick,->] (fixed) edge[loop left] node[left,text width=2.9cm,text badly centered,black] {\small \textcolor{darkgreen}{$\bold{(4)}$} $A^m(t) \in \hat{M}^{m}(t)$} (fixed); % \pause \draw [color=red,very thick,->] (fixed) to[bend right] node[midway,below,text centered,black] {\small \textcolor{red}{$\bold{(5)}$} $A^m(t) \notin \hat{M}^{m}(t)$} (notfixed); % \end{tikzpicture} \end{minipage}} % \caption{\small Player $j$ using $\mathrm{MCTopM}$, represented as ``state machine'' with $5$ transitions. % Taking one of the five transitions means playing one round of Algorithm \MCTopM, to decide $A^m(t+1)$ using information of previous steps.} \label{fig:StateMachineAlgorithm_MCTopM} \end{figure} \begin{small} \begin{colorblock}{Sketch of the proof to bound number of collisions} \begin{itemize} \item any sequence of transitions \textcolor{blue}{$(2)$} has constant length \item $\mathcal{O}(\log T)$ number of transitions \textcolor{red}{$(3)$} and \textcolor{red}{$(5)$}, by kl-UCB \item[$\implies$] player $m$ is fixed, for almost all rounds ($\mathcal{O}(T - \log T)$ times) \item nb of collisions $\leq$ $M \times$ nb of collisions of non fixed players \item[$\implies$] nb of collisions $= \mathcal{O}(\log T)$ \hfill{} \& $\mathcal{O}(\log(T))$ sub-optimal selections \textcolor{darkgreen}{$(4)$} \end{itemize} \end{colorblock} \end{small} \end{frameO} % \begin{frameO}[The MC-Top-M algorithm] % Two simple ideas: % \hfill{} {\small inspired by Musical Chair \color{gray}[Rosenski et al. 16] \color{black}} % \begin{itemize} % \item always pick an arm estimated as ``good'' \hfill{} $\color{red} A^m(t) \in \hat{M}^{m}(t-1)$ % \item try not to switch arm too often % \end{itemize} % \[\orange \sigma^m(t) := \left\{ \text{player } m \text{ is ``fixed'' at the end of round } t \right\}\] % \vspace{-0.3cm} % \pause % \begin{colorblock}{MC-Top-M} % \begin{itemize} % \item if $A^m(t-1) \notin \hat{M}^{m}(t-1)$, \\ set $\orange \sigma^m(t) = \mathrm{False}$ and \color{orange}carefully select a new arm in $\hat M^m(t-1)$\color{black}. % \item else if $\overline{\sigma^m(t-1)}\cap C^m(t-1)$, pick a new arm at random % \vspace{-0.2cm} % \[A^m(t) \sim \mathcal{U} (\hat{M}^m(t-1)) \ \ \text{and} \ \ \sigma^m(t) = \mathrm{False} \] % \item else, draw the previous arm, and fix on it % \vspace{-0.2cm} % \[A^m(t) =A^m(t-1) \ \ \text{and} \ \ \orange \sigma^m(t) = \mathrm{True}\] % \end{itemize} % \vspace{-0.6cm} % \end{colorblock} % \end{frameO} \begin{frameO}[Theoretical results for MC-Top-$M$] % \only<1>{ \begin{small} \vspace{0.2cm} MC-Top-$M$ with $\kl$-based confidence intervals \hfill{} \textcolor{gray}{[Cappé et al. 13]} \vspace{-0.3cm} \[\UCB^m_k(t) = \max \left\{ q : N^m_k(t) \kl \left(\hat{\mu}_k^m(t),q\right) \leq \ln(t) \right\},\] \textcolor{gray}{\small where $\kl(x,y) = \KL\left(\cB(x),\cB(y)\right) = x \ln\left(\frac{x}{y}\right) + (1-x)\ln\left(\frac{1-x}{1-y}\right)$.} \end{small} % } \begin{colorblock}{Control of the \textcolor{orange}{sub-optimal selections} \hfill{} (state-of-the-art)} % \only<1>{ \begin{small} For all sub-optimal arms $k \in \{M+1,\dots,K\}$, \vspace{-0.3cm} \[ \bE[\textcolor{orange}{N_k^m(T)}] \leq \alt<2>{\frac{\ln(T)}{\kl(\mu_k,\mu_{M})}}{\frac{\ln(T)}{\kl(\mu_k,\mu_{M})}}+ C_{\boldsymbol{\mu}} \sqrt{\ln(T)}. \] \vspace{-0.2cm} % } % \only<2>{ % \begin{center} % $\bE[\textcolor{orange}{N_k^m(T)}] \leq \mathcal{O}(\log T)$ % \end{center} % } \end{small} \end{colorblock} \uncover<2>{ \hfill{} logarithmic regret $\implies$ $R_{\bm\mu}(\cA,T) = \mathcal{O}((\textcolor{red}{M} \textcolor{blue}{\mathbf{C_{M,\mu}}} + \textcolor{red}{M^2 \mathbf{C}_6}) \log(T))$ } \begin{lightblock}{Control of the \textcolor{lightred}{collisions} \hfill{} (new result)} \begin{small} % \only<1>{ \[ \bE\left[\sum_{k=1}^K \textcolor{red}{\cC_k(T)}\right] \leq M^2 \left(\sum_{a,b : \mu_a < \mu_b} \frac{2 M + 1}{\kl(\mu_a,\mu_b)} \right) \ln(T) + \mathcal{O}(\ln T). \] % } % \only<2>{ % \begin{center} % $\bE\left[\textcolor{red}{\cC_k(T)}\right] \leq \mathcal{O}(\log T)$ % \end{center} % } \end{small} \end{lightblock} % \only<2>{ % \begin{lightblock}{$\implies$ \textbf{logarithmic regret!} \hfill{} \textcolor{lightgray}{[Besson \& Kaufmann, 18]}} % \vspace*{-10pt} % \begin{align*} % R_{\bm\mu}(\cA,T) % & \leq \text{cst} \sum_{k=M+1}^K \bE\left[\textcolor{orange}{N_k(T)}\right] + \text{cst'} \sum_{k=1}^M \bE\left[\textcolor{red}{\mathcal{C}_k(T)}\right] \\ % &= \textcolor{red}{M^2} \textcolor{blue}{\mathbf{C_{M,\mu}}} \log(T) + o(\log(T)), % \end{align*} % with $\textcolor{blue}{\mathbf{C_{M,\mu}}} = \sum\limits_{k: \mu_k < \mu_{M}^*} \sum\limits_{j=1}^M \frac{\mu_{M}^*}{\mathrm{kl}(\mu_k,\mu_j^*)}$ % {\small the same constant as in the centralized multiple-play bandit.} % \end{lightblock} % } \end{frameO} % \begin{frameO}[Results on a multi-player MAB problem] \begin{frameO}[Results on a multi-player MAB problem ($1/2$)] \begin{figure} \centering % \includegraphics[height=0.78\textheight]{MP__K9_M9_T10000_N200__4_algos/all_RegretCentralized____env1-1_2306423191427933958.pdf} % file:///home/lilian/publis/slides/2019_11__PhD_Defense__Multi-players_Bandit_Algorithms_for_Internet_of_Things_Networks/figures/ \includegraphics[height=0.75\textheight]{MP__K9_M9_T10000_N200__4_algos/all_CumNbCollisions____env1-1_5888213631268122907.pdf} \footnotesize{For $M=K$, \textcolor{blue}{our strategy MC-Top-$M$ ($\pentagon$)} achieves \textbf{constant} nb of collisions!\newline $\implies$ Our new orthogonalization procedure is very efficient!} \end{figure} \end{frameO} \begin{frameO}[Results on a multi-player MAB problem ($2/2$)] \begin{figure} % \centering % \includegraphics[height=0.75\textheight]{MP__K9_M6_T5000_N500__4_algos/all_RegretCentralized____env1-1_8318947830261751207.pdf} % \includegraphics[height=0.80\textheight]{all_RegretCentralized_loglog____env1-1_8200873569864822246.pdf} \includegraphics[height=0.78\textheight]{MP__K9_M6_T10000_N200__4_algos/all_RegretCentralized____env1-1_3201141303711964673.pdf} \small{For $M=6$ devices, \textcolor{blue}{our strategy MC-Top-$M$ ($\pentagon$)} largely outperforms \textcolor{bluegreenrhorand}{$\rho^{\text{rand}}$} and other previous state-of-the-art policies (not included).} \end{figure} \end{frameO} % \begin{frameO}[Results on a multi-player MAB problem ($3/3$)] % \centering % \includegraphics[height=0.80\textheight]{all_RegretCentralized_loglog____env1-1_6747959631471381163.pdf} % \caption{\footnotesize{For $M=6$ objects, our strategy (MCTopM) largely outperform \textsc{Sic-MMAB} and $\rho^{\text{rand}}$. \textcolor{cyan}{MCTopM + klUCB} achieves the best performance (among decentralized algorithms) !}} % \end{frameO} \begin{frame}[shrink=22] \mytitle{centralesupelecdark}{centralesupelec}{State-of-the-art multi-player algorithms} \vspace*{0.6cm} \begin{center} \begin{tabular}{ m{2.7cm} | c | c | c | c | m{3cm} } \textbf{Algorithm} & \textbf{Ref.} & \textbf{Regret bound} & \parbox[c]{2cm}{\textbf{\small Performance} \newline {\footnotesize \textcolor{orange}{\etoilenorm{}} \textcolor{gray}{is worst}}} & \parbox[c]{1.5cm}{\textbf{\small Speed} \newline {\footnotesize \textcolor{gray}{\tgvsmall{} is worst}}} & \textbf{Parameters} \\ \hline \textcolor{deeppurple}{\small Centralized multi-play kl-UCB} & \textcolor{gray}{[1]} & $\textcolor{blue}{\mathbf{C_{M,\mu}}} \log(T)$ & {\textcolor{orange}{\etoile{}\etoile{}\etoile{}\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}}} & {just $M$ but \newline \textcolor{deeppurple}{in another model!} } \\ % \vspace*{3pt} \hline % \vspace*{3pt} $\rho^{\text{rand}}$ UCB & \textcolor{gray}{[2]} & $\textcolor{red}{M^3 \mathbf{C}_2} \log(T)$ & {\textcolor{orange}{\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}}} & just $M$ \\ \hline \textsc{MEGA} & \textcolor{gray}{[3]} & $\mathbf{C}_3 \textcolor{red}{T^{3/4}}$ & {\textcolor{orange}{\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}}} & {\footnotesize 4 params, \newline \textcolor{red}{\emph{impossible to tune}} } \\ \hline Musical Chair & \textcolor{gray}{[4]} & $\textcolor{red}{{2M \choose M} \mathbf{C}_4} \log(T)$ & {\textcolor{orange}{\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}}} & {\footnotesize 1 parameter $T_0$ \newline \textcolor{red}{\emph{hard to tune}} } \\ \hline \textcolor{orange}{Selfish UCB} & \textcolor{orange}{[5]} & $\textcolor{red}{T}$ in some case & {\textcolor{orange}{\etoile{} $/$ \etoile{}\etoile{}\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}\tgv{}}} & \textbf{none!} \\ % \vspace*{3pt} \hline % \vspace*{3pt} {\small \textcolor{orange}{MCTop$M$ klUCB}} & \textcolor{orange}{[6]} & {\small $(\textcolor{red}{M} \textcolor{blue}{\mathbf{C_{M,\mu}}} + \textcolor{red}{M^2 \mathbf{C}_6}) \log(T)$} & {\textcolor{orange}{\etoile{}\etoile{}\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}}} & just $M$ \\ \hline \textsc{Sic-MMAB} & \textcolor{gray}{[7]} & $(\textcolor{blue}{\mathbf{C_{M,\mu}}} \textcolor{red}{+ MK}) \log(T)$ & {\textcolor{orange}{\etoile{}\etoile{}\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}}} & \textbf{none!} but \newline \textcolor{deeppurple}{in another model!} \\ \textsc{DPE} & \textcolor{gray}{[8]} & $\textcolor{blue}{\mathbf{C_{M,\mu}}} \log(T)$ & {\textcolor{orange}{??}} & {\textcolor{orange}{\tgv{}}} & \textbf{none!} but \newline \textcolor{deeppurple}{in another model!} % \\ % & & & \textcolor{gray}{(\etoile{}\etoile{}\etoile{}\etoile{} is better)} & \textcolor{gray}{(\tgv{}\tgv{}\tgv{}\tgv{}\tgv{} is better)} & \end{tabular} \end{center} \vspace*{5pt} % \vfill{} Optimal \textbf{regret bound} is multiple-play bound $\cR(\cA, T) \leq \textcolor{blue}{\mathbf{C_{M,\mu}}} \log(T) + o(\log(T))$, with $\textcolor{blue}{\mathbf{C_{M,\mu}}} = \sum\limits_{k: \mu_k < \mu_{M}^*} \sum\limits_{j=1}^M \frac{\mu_{M}^*}{\mathrm{kl}(\mu_k,\mu_j^*)}$, % and $\textcolor{red}{\mathbf{C}_i} \gg \textcolor{blue}{\mathbf{C_{M,\mu}}}$ are much larger constants. \vspace*{5pt} \begin{small} \textbf{Papers:} [1] \textcolor{gray}{Anantharam et al, 87} [2] \textcolor{gray}{Anandkumar et al, 11} [3] \textcolor{gray}{Avner et al, 15} [4] \textcolor{gray}{Rosenski et al, 15} \newline\hspace*{10pt} [5] \textcolor{orange}{Bonnefoi et al 17} [6] \textcolor{orange}{Besson \& Kaufmann, 18} [7] \textcolor{gray}{Boursier et al, 19} [8] \textcolor{gray}{Proutière et al, 19} \end{small} \end{frame} \begin{frame}[c] \begin{changemargin}{-0.5cm}{-0.5cm} \begin{center} \vspace{-0.3in} \textbf{\huge Theoretical analysis of\\ two relaxed models} \vspace{1.5cm} % \textcolor{darkgray}{\Large \textbf{Many different extensions}\\[0.5cm]} % \textcolor{darkgray}{\Large \textbf{Insights from the Optimal Solution}} \\[0.5cm] \textcolor{darkgray}{\textbf{\Large Multi-player bandits}\\[0.5cm]} \textbf{\Large Piece-wise stationary bandits}\\ \small{\textcolor{gray}{Ref: Chapter 7 of my thesis, and [Besson et al, 19].}} \end{center} \end{changemargin} \end{frame} \subsection{Piece-wise stationary bandits} \begin{frameO}[Piece-wise stationary bandits] \begin{orangeblock}{Stationary MAB problems} Arm $k$ \slotmachine{} samples rewards from \textcolor{orange}{the same distribution} for any round \[ \forall t, r_k(t) \overset{\text{iid}}{\sim} \textcolor{orange}{\nu_k} = \mathcal{B}(\textcolor{orange}{\mu_k}). \] \end{orangeblock} \pause \begin{alertblock}{Non stationary MAB problems?} \alert{(possibly) different distributions} for any round ! \[ \forall t, r_k(t) \overset{\text{iid}}{\sim} \nu_k\alert{(t)} = \mathcal{B}(\mu_k\alert{(t)}). \] \end{alertblock} $\implies$ \alert{harder problem!} % And very hard if $\mu_k(t)$ can change at any step! And impossible with no extra hypothesis \pause \begin{colorblock}{\textbf{Piece-wise stationary} problems!} % $\hookrightarrow$ The literature usually focuses on the easier case, when there are at most $\Upsilon_T = o(\sqrt{T})$ intervals, on which the means are all stationary. \end{colorblock} \end{frameO} \begin{frameO}[Example of a piece-wise stationary MAB problem] We plots the means \textcolor{red}{$\mu_1(t)$}, \textcolor{green}{$\mu_2(t)$}, \textcolor{blue}{$\mu_3(t)$} of $K=3$ arms \slotmachine{}.\\ There are $\Upsilon_T=4$ break-points and $5$ sequences % between $t=1$ and $t=T=5000$: in $\{1,\dots,T=5000\}$ \vspace*{-25pt} % \begin{center} \includegraphics[width=1.05\textwidth]{Problem_1.pdf} % \end{center} \end{frameO} \begin{frameO}[Regret for piece-wise stationary bandits] The ``oracle'' plays the (\alert{unknown}) best arm $k^*(t) = \argmax \mu_k(t)$\\ (which changes between the $\Upsilon_T \geq 1$ stationary sequences) % \begin{align*} \cR(\cA,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] \\ &= \underbrace{\left(\alert{\sum_{t=1}^T \max_k \mu_k(t)} \right)}_{\text{oracle total reward}} - \sum\limits_{t=1}^T \mathbb{E}\left[ r(t) \right]. \end{align*} \pause \vspace*{5pt} \begin{colorblock}{Typical regimes for piece-wise stationary bandits} \begin{itemize} % \item Naive kl-UCB algorithms can obtain $\cR(\cA,T) \leq \mathcal{O}(T)$ in worst-case % \item ``Oracle restart'' kl-UCB obtains % $\cR(\cA,T) \leq \mathcal{O}((K / \Delta_{\text{opt}}^2) \Upsilon_T \log(T))$\\ % when knowing the locations of $\Upsilon_T$ break-points % \pause % \vspace*{10pt} \item The (minimax) \emph{worst-case lower-bound} is $\cR(\cA,T) \geq \Omega(\sqrt{K T \Upsilon_T})$ % on a ``bad'' problem \vspace*{5pt} \item State-of-the-art algorithms $\mathcal{A}$ obtain $\cR(\cA,T) \leq \mathcal{O}(K \sqrt{T \Upsilon_T \log(T)})$ % \item % Currently, state-of-the-art algorithms $\mathcal{A}$ obtain % \begin{itemize} % % \tightlist % \item % $\cR(\cA,T) \leq \mathcal{O}((K / \Delta_{\text{change}}^2) \sqrt{T \Upsilon_T \log(T)})$ % if $T$ and $\Upsilon_T$ are known % \item % $\cR(\cA,T) \leq \mathcal{O}((K / \Delta_{\text{change}}^2) \textcolor{orange}{\Upsilon_T} \sqrt{T \log(T)})$ % if $T$ and \textcolor{orange}{$\Upsilon_T$ are unknown} % \end{itemize} \end{itemize} \end{colorblock} \end{frameO} \begin{frameO}[Our new algorithm: kl-UCB index + BGLR detector] % \only<1>{ \begin{colorblock}{Three components of our algorithm \hfill{} \textcolor{lightgray}{[Besson et al, 19]}} \begin{quote} \begin{small} Our algorithm is inspired by CUSUM-UCB \textcolor{gray}{[Liu et al, 18]} and M-UCB \textcolor{gray}{[Cao et al, 19]}, and new analysis of the GLR test \textcolor{gray}{[Maillard, 19]} \end{small} \end{quote} \begin{itemize}[<+->] \item A classical bandit index policy: \textbf{kl-UCB}\newline which gets \emph{restarted} after \textcolor{orange}{a change-point is detected} \item A \textcolor{orange}{change-point detection algorithm}: the \textbf{Generalized Likelihood Ratio Test} for sub-Bernoulli observations (BGLR), we can bound \begin{itemize} \item its false alarm probability (if enough samples between two restarts) \item its detection delay (for ``easy enough'' problems) \end{itemize} \item Forced exploration of parameter $\alpha\in(0,1)$ (tuned with $\Upsilon_T$) \end{itemize} \end{colorblock} % } \pause % \only<2>{ \begin{lightblock}{Regret bound (if $T$ and $\Upsilon_T$ are both known)} Our algorithm obtains % \begin{itemize} % \tightlist % \item $\cR(\cA,T) \leq \mathcal{O} \left( \frac{K}{\Delta_{\text{change}}^2} \sqrt{T \Upsilon_T \log(T)} \right)$ % \item % $\cR(\cA,T) \leq \mathcal{O}((K / \Delta_{\text{change}}^2) \textcolor{orange}{\Upsilon_T} \sqrt{T \log(T)})$ % if $T$ and \textcolor{orange}{$\Upsilon_T$ are unknown} % \end{itemize} % {\small with finite time and more precise results in the thesis\dots} \end{lightblock} % } \end{frameO} \begin{frameO}[Results on a piece-wise stationary MAB problem] % \textbf{Idea:} combine a good \textit{bandit algorithm} with a \emph{break-point detector} \begin{center} \includegraphics[width=1.09\textwidth]{regret_problem1.png} \end{center} \vspace*{-15pt} \begin{small} $\hookrightarrow$ \textcolor{deeppurple}{kl-UCB + BGLR ($\star$)} achieves the best performance (among non-oracle)! \end{small} \end{frameO} % \begin{frameO}[More results ($1/3$)] % \begin{center} % \includegraphics[width=0.99\textwidth]{regret_problem2.png} % \end{center} % \textcolor{blue}{klUCB + BGLR} achieves the best performance (among non-oracle)! % \end{frameO} % \begin{frameO}[More results ($2/3$)] % \begin{center} % \includegraphics[width=0.99\textwidth]{regret_problem3.png} % \end{center} % \textcolor{blue}{klUCB + BGLR} achieves the best performance (among non-oracle)! % \end{frameO} % \begin{frameO}[More results ($3/3$)] % \begin{center} % \includegraphics[width=0.99\textwidth]{regret_problem4.png} % \end{center} % \textcolor{blue}{klUCB + BGLR} achieves the best performance (among non-oracle)! % \end{frameO} \begin{frame}[shrink=23] \mytitle{centralesupelecdark}{centralesupelec}{State-of-the-art piece-wise stationary algorithms} \vspace*{1.5cm} \begin{tabular}{ m{3.5cm} | c | c | c | c | m{3cm} } \textbf{Algorithm} & \textbf{Ref.} & \textbf{Regret bound} & \parbox[c]{2cm}{\textbf{Performance} \newline {\footnotesize \textcolor{orange}{\etoilenorm{}} \textcolor{gray}{is worst}}} & \parbox[c]{1.5cm}{\textbf{Speed} \newline {\footnotesize \textcolor{gray}{\tgvsmall{} is worst}}} & \textbf{Parameters} \\ \hline Naive UCB & \textcolor{gray}{[1]} & \textcolor{red}{$T$} \emph{in worst case} & {\textcolor{orange}{\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}\tgv{}\tgv{}\tgv{}}} & \textbf{none!} \\ \hline \textcolor{deeppurple}{Oracle-Restart UCB} & \textcolor{gray}{[1]} & $\textcolor{blue}{\mathbf{C}} \Upsilon_T \log(T)$ & {\textcolor{orange}{\etoile{}\etoile{}\etoile{}\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}\tgv{}\tgv{}\tgv{}}} & {\footnotesize the break-points \newline \textcolor{deeppurple}{(unrealistic oracle!)}} \\ \hline Discounted UCB & \textcolor{gray}{[2]} & $\textcolor{red}{\mathbf{C}_2} \sqrt{T \Upsilon_T} \textcolor{red}{\log(T)}$ & {\textcolor{orange}{\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}\tgv{}\tgv{}}} & $T$ and $\Upsilon_T$ \\ Sliding-Window UCB & \textcolor{gray}{[2]} & $\textcolor{red}{\mathbf{C}_2'} \sqrt{T \Upsilon_T \log(T)}$ & {\textcolor{orange}{\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}\tgv{}\tgv{}}} & $T$ and $\Upsilon_T$ \\ \hline Exp3.S & \textcolor{gray}{[3]} & $\textcolor{blue}{\mathbf{C}} \sqrt{T \Upsilon_T \log(T)}$ & {\textcolor{orange}{\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}\tgv{}\tgv{}\tgv{}}} & $\Upsilon_T$ \\ Discounted TS & \textcolor{gray}{[4]} & \emph{not yet proven} & {\textcolor{orange}{\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}\tgv{}\tgv{}}} & {\footnotesize \textcolor{red}{how to tune $\gamma$ ?}} \\ \hline CUSUM-UCB & \textcolor{gray}{[5]} & $\textcolor{red}{\mathbf{C}_5} \sqrt{T \Upsilon_T \log(\frac{T}{\Upsilon_T})}$ & {\textcolor{orange}{\etoile{}\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}}}& {\footnotesize $T$, $\Upsilon_T$ \textcolor{red}{and $\delta_{\min}$}} \\ % \hline M-UCB & \textcolor{gray}{[6]} & $\textcolor{red}{\mathbf{C}_6} \sqrt{T \Upsilon_T \log(T)}$ & {\textcolor{orange}{\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}\tgv{}}} & {\footnotesize $T$, $\Upsilon_T$ \textcolor{red}{and $\delta_{\min}$}} \\ \hline \textbf{\textcolor{orange}{BGLR + kl-UCB}} & \textcolor{orange}{[7]} & $\textcolor{blue}{\mathbf{C}} \sqrt{T \Upsilon_T \log(T)}$ & {\textcolor{orange}{\etoile{}\etoile{}\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}\tgv{}}} & $T$ and $\Upsilon_T$ \\ \hline AdSwitch & \textcolor{gray}{[8]} & $\textcolor{red}{\mathbf{C}_8} \sqrt{T \Upsilon_T \log(T)}$ & {\textcolor{orange}{\etoile{}\etoile{}}} & {\textcolor{orange}{\tgv{}}} & just $T$ \\ % \hline Ada-ILTCB$^+$ & \textcolor{gray}{[9]} & $\textcolor{red}{\mathbf{C}_9} \sqrt{T \Upsilon_T \log(T)}$ & {\textcolor{orange}{??}} & {\textcolor{orange}{\tgv{}}} & just $T$ \end{tabular} \vspace*{15pt} \vfill{} Optimal minimax \textbf{regret bound} is $\cR(\cA, T) = \mathcal{O}(\sqrt{K T \Upsilon_T})$, and $\textcolor{blue}{\mathbf{C}} = \textcolor{blue}{\mathbf{C}_{\Upsilon_T,\mu}} = \mathcal{O}(\frac{K}{\Delta_{\text{change}}^2})$. % $\textcolor{red}{\mathbf{C}_i} \gg \textcolor{blue}{\mathbf{C}_{\Upsilon_T,\mu}}$ are much larger constants, and $\delta_{\min} < \Delta_{\text{change}}$ lower-bounds the problem difficulty. \vspace*{10pt} \begin{small} \textbf{Papers:} [1] \textcolor{gray}{Auer et al. 02} [2] \textcolor{gray}{Garivier et al. 09} [3] \textcolor{gray}{Auer et al. 02} [5] \textcolor{gray}{Raj et al. 17} \newline \hspace*{10pt} [5] \textcolor{gray}{Liu et al. 18} [6] \textcolor{gray}{Cao et al. 19} [7] \textcolor{orange}{Besson et al. 19} [8] \textcolor{gray}{Auer et al. 19} [9] \textcolor{gray}{Chen et al. 19} \end{small} \end{frame} % \begin{frameO}[More results ($4/4$)] % \begin{center} % \includegraphics[width=0.99\textwidth]{regret_problem5.png} % \end{center} % \textcolor{blue}{klUCB + BGLR} achieves the best performance (among non-oracle)! % \end{frameO} % \begin{frameO}[Other piece-wise stationary bandit models] % Our change-point detection GLR is useful for other bandit models % \only<1>{ % \begin{center} % \includegraphics[width=0.90\textwidth]{GLRTest_for_PieceWise-Stationary_Combinatorial_Bandits.png} % \end{center} % } % \only<2>{ % \begin{center} % \includegraphics[width=0.90\textwidth]{GLRTest_for_PieceWise-Stationary_Cascading_Bandits.png} % \end{center} % } % \end{frameO} % \section{Numerical simulations with SMPyBandits} % \begin{frameTI} % \begin{center} % {\textcolor{white} {\Huge \textsc{Numerical simulations with SMPyBandits} }} % \end{center} % \vspace*{-4pt} % \end{frameTI} % \begin{frameO}[Numerical simulations with SMPyBandits] % FIXME % \end{frameO} \section{Summary} \begin{frameTI} \begin{center} {\textcolor{white} {\Huge \textsc{Summary} }} \end{center} % \vspace*{15pt} % \begin{center} % {\textcolor{white} {\huge \textsc{Thanks for your attention!} }} % \end{center} \end{frameTI} \begin{frameO}[Contributions \hfill{} ($1/3$)] % \pause % \begin{colorblock}{What we showed} \large \textbf{Part I:} \uncover<2->{ \begin{itemize}%[<+->] \setlength\itemsep{6pt} \item A simple model of IoT network, where autonomous IoT devices can embed decentralized learning (``\textcolor{orange}{selfish MAB learning}''), \item numerical simulations proving the quality of our solution, \item a realistic implementation on radio hardware. % \item my Python library SMPyBandits. % \vspace*{10pt} \end{itemize} } \vspace*{10pt} % \pause \textbf{Part II:} \uncover<3>{ \begin{itemize}%[<+->] \setlength\itemsep{6pt} \item New algorithms and regret bounds, in two simplified models: \begin{itemize} \item for \textcolor{orange}{multi-player bandits}, with $M \leq K$ players, \item for \textcolor{orange}{piece-wise stationary bandits}, with $\Upsilon_T = o(T)$ break-points, \end{itemize} % \item and comparisons of both numerical and theoretical results, showing our proposed algorithms achieve state-of-the-art performance. \item our proposed algorithms achieve state-of-the-art performance \begin{itemize} \item on both numerical, \item and theoretical results. \end{itemize} \end{itemize} } % \end{colorblock} \end{frameO} \begin{frameO}[Perspectives \hfill{} ($2/3$)] % \begin{lightblock}{What could be done with another year(s) ?} % \large \begin{itemize}[<+->] \setlength\itemsep{2pt} \item Unify the \emph{multi-player} and \emph{non-stationary} bandit models\\ \textcolor{gray}{\small $\hookrightarrow$ in progress: already one paper from last year (\texttt{arXiv:1812.05165}), we can probably do a better job with our tools!} \item More validation of our contributions in real-world IoT environments\\ \textcolor{gray}{\small $\hookrightarrow$ started in summer $2019$ with an intern working with Christophe Moy} \vspace*{10pt} \item \textcolor{orange}{Study the ``Graal'' goal:} \begin{itemize} \item propose a more realistic model for IoT networks \newline (exogenous activation, non stationary traffic, etc) \item propose an efficient decentralized low-cost algorithm \item that works empirically \emph{and} has strong theoretical guarantees! \end{itemize} % {\small also let the devices learn \emph{when} to transmit (choose time), not only \emph{where/how} to transmit (choose frequency, etc)\dots{} % % \hfill{} % \alert{Much harder!} search space is VERY LARGE!} \vspace*{10pt} % \item % try to study the ``selfish model'' from other perspectives, % % (game theory\dots{}?), % for large $M$ nb of devices and small $p$ activation probabilities\dots? \item Extend my Python library \textcolor{blue}{SMPyBandits} to cover many other bandit models (cascading, delay feedback, combinatorial, contextual etc)\newline \hfill{} \textcolor{gray}{\small $\hookrightarrow$ it is already online, free and open-source on \href{https://GitHub.com/SMPyBandits/}{\textcolor{blue}{\texttt{GitHub.com/SMPyBandits}}}} \end{itemize} % \end{lightblock} \end{frameO} \begin{frame}[shrink=17] \mytitle{centralesupelecdark}{centralesupelec}{List of publications \hfill{} ($3/3$)} \vspace*{1.25cm} \textcolor{orange}{\textbf{8 International conferences with proceedings:}} \begin{itemize} \item ``\emph{MAB Learning in IoT Networks}'', Bonnefoi, \textbf{Besson} et al, \textcolor{orange}{CROWNCOM}, \textcolor{blue}{2017} \item ``\emph{Aggregation of MAB for OSA}'', \textbf{Besson}, Kaufmman, Moy, \textcolor{orange}{IEEE WCNC}, \textcolor{blue}{2018} \item ``\emph{Multi-Player Bandits Revisited}'', \textbf{Besson} \& Kaufmann, \textcolor{orange}{ALT}, \textcolor{blue}{2018} \item ``\emph{MALIN with GRC \dots}'', Bonnefoi, \textbf{Besson}, Moy, \textcolor{orange}{demo at ICT}, \textcolor{blue}{2018} \item ``\emph{GNU Radio Implementation of MALIN \dots}'', \textbf{Besson} et al, \textcolor{orange}{IEEE WCNC}, \textcolor{blue}{2019} \item ``\emph{UCB \dots LPWAN w/ Retransmissions}'', Bonnefoi, \textbf{Besson} et al, \textcolor{orange}{IEEE WCNC}, \textcolor{blue}{2019} \item ``\emph{Decentralized Spectrum Learning \dots}'', Moy \& \textbf{Besson}, \textcolor{orange}{ISIoT}, \textcolor{blue}{2019} \item ``\emph{Analyse non asymptotique \dots}'', \textbf{Besson} \& Kaufmann, \textcolor{orange}{GRETSI}, \textcolor{blue}{2019} \end{itemize} \vspace*{0.50cm} \textcolor{darkgreen}{\textbf{1 Preprints:}} \begin{itemize} \item ``\emph{Doubling-Trick \dots}'', \textbf{Besson} \& Kaufmann, \textcolor{darkgreen}{\texttt{arXiv:1803.06971}}, \textcolor{blue}{2018} % \texttt{hal-01736357} \& % \item ``\emph{GLRT meets klUCB \dots}'', \textbf{Besson} \& Kaufmann, \texttt{hal-0\textcolor{blue}{2006471} }\texttt{arXiv:1902.01575}, \textcolor{blue}{2019} \end{itemize} \vspace*{0.50cm} \textcolor{darkred}{\textbf{3 Submitted works:}} \begin{itemize} \item ``\emph{Decentralized Spectrum Learning \dots}'', Moy, \textbf{Besson} et al, for \textcolor{darkred}{Annals of Telecommunications}, \textcolor{blue}{July 2019} \item ``\emph{GLRT meets klUCB \dots}'', \textbf{Besson} \& Kaufmann \& Maillard, for \textcolor{darkred}{AISTATS}, \textcolor{blue}{Oct.2019} \item ``\emph{SMPyBandits \dots}'', \textbf{Besson}, for \textcolor{darkred}{JMLR MLOSS}, \textcolor{blue}{October 2019} % \texttt{hal-01840022} \& \texttt{arXiv:1902.01575}, \end{itemize} \end{frame} \begin{frameO}[Conclusion] \begin{center} \begin{huge} \textbf{Thanks for your attention!} \end{huge} \end{center} \vspace*{30pt} \begin{center} \begin{huge} \thinkingfacelarge{} \textbf{Questions \& Discussion} \end{huge} \end{center} % \vspace*{10pt} % \pause % % FIXME pour la soutenance % \begin{center} % \begin{huge} % % FIXME pour la fausse soutenance à Lille % \textcolor{darkgreen}{On se retrouve à 14h pour le pot (cafet Inria bât. A) !} % % FIXME pour la vraie soutenance à Rennes % \textcolor{darkgreen}{On se retrouve à 14h pour le pot (cafet 1er étage) !} % \end{huge} % \end{center} \end{frameO} % FIXME? \appendix{} \begin{frameO}[Didn't have time to talk about\dots \hfill{} ($2/4$)] % \begin{darkblock}{Didn't have time to talk about\dots} \large \begin{itemize}[<+->] \setlength\itemsep{10pt} \item an extension of our model of IoT network to account for retransmissions (Section 5.4), \item my Python library \textcolor{blue}{SMPyBandits} (Chapter 3), \item our proposed algorithm for aggregating bandit algorithms (Chapter 4), \item details about our algorithms, their precise theoretical results and proofs (Chapters 6 \& 7), \item our work on the ``doubling trick'' (to make an algorithm $\cA$ anytime and keep its regret bounds). \end{itemize} % \end{darkblock} \end{frameO} \begin{frameTI} \begin{center} \color{white} \Huge \textsc{References and publications} \end{center} \vspace*{-4pt} \end{frameTI} \begin{frameO}[Where to know more: about bandits \hfill{} ($1/3$)] Check out the \vspace{1cm} \Huge \centering \href{https://tor-lattimore.com/downloads/book/book.pdf}{\textcolor{blue}{``The Bandit Book''}} \normalsize by Tor Lattimore and Csaba Szepesvári\\ Cambridge University Press, 2019. \vspace{0.3cm} \normalsize $\hookrightarrow$ \href{https://tor-lattimore.com/downloads/book/book.pdf}{{\textcolor{blue}{\texttt{tor-lattimore.com/downloads/book/book.pdf}}}} \end{frameO} \begin{frameO}[Where to know more: about our work? \hfill{} ($2/3$)] Reach me (or Christophe or Émilie) out by email, if you have questions \vspace{15pt} \large \centering \href{https://perso.crans.org/besson/}{\textcolor{darkgreen}{\texttt{Lilian.Besson @ CentraleSupelec.fr}}} $\hookrightarrow$ \href{https://perso.crans.org/besson/}{{\textcolor{darkgreen}{\texttt{perso.crans.org/besson/}}}} \vspace{15pt} \href{https://moychristophe.wordpress.com/}{\textcolor{centralesupelec}{\texttt{Christophe.Moy @ Univ-Rennes1.fr}}} $\hookrightarrow$ \href{https://moychristophe.wordpress.com/}{{\textcolor{centralesupelec}{\texttt{moychristophe.wordpress.com}}}} \vspace{15pt} \href{http://chercheurs.lille.inria.fr/ekaufman/}{\textcolor{orange}{\texttt{Emilie.Kaufmann @ Univ-Lille.fr}}} $\hookrightarrow$ \href{http://chercheurs.lille.inria.fr/ekaufman/}{{\textcolor{orange}{\texttt{chercheurs.lille.inria.fr/ekaufman}}}} \end{frameO} \begin{frameO}[Where to know more: in practice \hfill{} ($3/3$)] Experiment with bandits by yourself! \vspace{1cm} Interactive demo on this web-page\\ $\hookrightarrow$ \href{https://perso.crans.org/besson/phd/MAB_interactive_demo/}{\textcolor{blue}{\texttt{perso.crans.org/besson/phd/MAB\_interactive\_demo/}}} \vspace{1cm} Use my Python library for simulations of MAB problems \textbf{SMPyBandits} \\ $\hookrightarrow$ \href{https://smpybandits.github.io/}{\textcolor{blue}{\texttt{SMPyBandits.GitHub.io}}} \& \href{https://GitHub.com/SMPyBandits/}{\textcolor{blue}{\texttt{GitHub.com/SMPyBandits}}} \\ \begin{itemize} \item Install with \texttt{$\$$ pip install SMPyBandits} \item Free and open-source (MIT license) \item Easy to set up your own bandit experiments, add new algorithms etc. \end{itemize} \end{frameO} \begin{frameO}[$\hookrightarrow$ \href{https://smpybandits.github.io/}{\textcolor{lightlightblue}{\texttt{SMPyBandits.GitHub.io}}}] \begin{center} \includegraphics[height=0.85\textheight]{overview_documentation_1} \end{center} \end{frameO} \begin{frameO}[Main references] \begin{itemize} \item My PhD thesis (Lilian Besson)\\ \href{https://github.com/Naereen/phd-thesis/}{\textcolor{blue}{``Multi-players Bandit Algorithms for Internet of Things Networks''}}\\ $\hookrightarrow$ Online at \href{https://perso.crans.org/besson/phd/}{\textcolor{blue}{\texttt{perso.crans.org/besson/phd/}}}\\ $\hookrightarrow$ Open-source at \href{https://github.com/Naereen/phd-thesis/}{\textcolor{blue}{\texttt{GitHub.com/Naereen/phd-thesis/}}} \vspace*{10pt} \item My Python library for simulations of MAB problems, \textbf{SMPyBandits}\\ $\hookrightarrow$ \href{https://smpybandits.github.io/}{\textcolor{blue}{\texttt{SMPyBandits.GitHub.io}}} \vspace*{10pt} \item \href{https://tor-lattimore.com/downloads/book/book.pdf}{\textcolor{blue}{``The Bandit Book''}}, by Tor Lattimore and Csaba Szepesvári\\ $\hookrightarrow$ \href{https://tor-lattimore.com/downloads/book/book.pdf}{{\textcolor{blue}{\texttt{tor-lattimore.com/downloads/book/book.pdf}}}} \vspace*{10pt} \item \href{https://arxiv.org/abs/1904.07272}{\textcolor{blue}{``Introduction to Multi-Armed Bandits''}}, by Alex Slivkins\\ $\hookrightarrow$ \href{https://arxiv.org/abs/1904.07272}{{\textcolor{blue}{\texttt{arXiv.org/abs/1904.07272}}}} \end{itemize} \end{frameO} \begin{frame}[c] \begin{changemargin}{-0.5cm}{-0.5cm} \begin{center} \vspace{-0.3in} \textbf{\huge List of publications} \vspace{1.5cm} \vspace*{10pt} \small{Cf.: \textcolor{blue}{\texttt{CV.archives-ouvertes.fr/lilian-besson}}} \end{center} \end{changemargin} \end{frame} \begin{frameO}[International conferences with proceedings ($1/2)$] {\footnotesize \begin{itemize} \item \emph{Decentralized Spectrum Learning for IoT Wireless Networks Collision Mitigation},\\ by Christophe Moy \& \textbf{Lilian Besson}.\\ 1st International ISIoT workshop, % \footnote{~See \href{https://sites.google.com/view/ISIoT2019}{\texttt{sites.google.com/view/ISIoT2019}}}, at \textcolor{orange}{\emph{Conference on Distributed Computing in Sensor Systems}}, % \footnote{~IEEE DCOSS 2019, see \href{http://2019.dcoss.org}{\texttt{2019.dcoss.org}}}, Santorini, Greece, \textcolor{blue}{May $2019$}.\\ % \href{https://HAL.Inria.fr/hal-02144465}{\texttt{HAL.Inria.fr/hal-02144465}}. \emph{See Chapter~5.} % \cite{MoyBesson2019} % \emph{$\hookrightarrow$ Note that we are already working on an extended version that will be submitted to a journal on Machine Learning for Wireless Communications, in \textcolor{blue}{July $2019$}.} \item \emph{Upper-Confidence Bound for Channel Selection in LPWA Networks with Retransmissions},\\ by Rémi Bonnefoi, \textbf{Lilian Besson}, Julio Manco-Vasquez \& Christophe Moy.\\ 1st International MOTIoN workshop, % \footnote{~MOTIoN 2019, see \href{https://sites.google.com/view/wcncworkshop-motion2019}{\texttt{sites.google.com/view/wcncworkshop-motion2019}}}, at \textcolor{orange}{\emph{WCNC}}, Marrakech, Morocco, \textcolor{blue}{April $2019$}.\\ % \href{https://HAL.Inria.fr/hal-02049824}{\texttt{HAL.Inria.fr/hal-02049824}}. \emph{See Section~5.4.} % \cite{Bonnefoi2019WCNC} \item \emph{GNU Radio Implementation of MALIN: ``Multi-Armed bandits Learning for Internet-of-things Networks''},\\ by \textbf{Lilian Besson}, Rémi Bonnefoi \& Christophe Moy.\\ \textcolor{orange}{\emph{Wireless Communication and Networks Conference}}, % \footnote{~IEEE WCNC 2019, see \href{http://wcnc2019.ieee-wcnc.org}{\texttt{wcnc2019.ieee-wcnc.org}}}, Marrakech, \textcolor{blue}{April $2019$}.\\ % \href{https://HAL.Inria.fr/hal-02006825}{\texttt{HAL.Inria.fr/hal-02006825}}. \emph{See Section~5.3.} % \cite{Besson2019WCNC} \end{itemize} \hfill{} For more details, see: \textcolor{blue}{\href{https://cv.archives-ouvertes.fr/lilian-besson/}{\texttt{CV.Archives-Ouvertes.fr/lilian-besson}}}. } \end{frameO} \begin{frameO}[International conferences with proceedings ($2/2)$] {\footnotesize \begin{itemize} \item \emph{Multi-Player Bandits Revisited},\\ by \textbf{Lilian Besson} \& Émilie Kaufmann.\\ \textcolor{orange}{\emph{Algorithmic Learning Theory}}, % \footnote{~ALT 2018, see \href{http://www.cs.cornell.edu/conferences/alt2018}{\texttt{www.cs.cornell.edu/conferences/alt2018}}}, Lanzarote, Spain, \textcolor{blue}{April $2018$}.\\ % \href{https://HAL.Inria.fr/hal-01629733}{\texttt{HAL.Inria.fr/hal-01629733}}. \emph{See Chapter~6.} % \cite{Besson2018ALT} \item \emph{Aggregation of Multi-Armed Bandits learning algorithms for Opportunistic Spectrum Access},\\ by \textbf{Lilian Besson}, Émilie Kaufmann \& Christophe Moy.\\ \textcolor{orange}{\emph{Wireless Communication and Networks Conference}}, % \footnote{~IEEE WCNC 2018, see \href{http://wcnc2018.ieee-wcnc.org}{\texttt{wcnc2018.ieee-wcnc.org}}}, Barcelona, Spain, \textcolor{blue}{April $2018$}.\\ % \href{https://HAL.Inria.fr/hal-01705292}{\texttt{HAL.Inria.fr/hal-01705292}}. \emph{See Chapter~4.} % \cite{Besson2018WCNC} \item \emph{Multi-Armed Bandit Learning in IoT Networks and non-stationary settings},\\ by Rémi Bonnefoi, \textbf{L.Besson}, C.Moy, É.Kaufmann \& Jacques Palicot.\\ \textcolor{orange}{\emph{Conference on Cognitive Radio Oriented Wireless Networks}}, % \footnote{~CROWNCOM 2017, see \href{http://crowncom.org/2017}{\texttt{crowncom.org/2017}}}, Lisboa, Portugal, \textcolor{blue}{September $2017$}. % \href{https://HAL.Inria.fr/hal-01575419}{\texttt{HAL.Inria.fr/hal-01575419}}, \textbf{Best Paper Award}.\\ \emph{See Section~5.2.} % \cite{Bonnefoi17} \end{itemize} } \end{frameO} \begin{frameO}[Demonstrations in international conferences] {\footnotesize \begin{itemize} \item \emph{MALIN: ``Multi-Arm bandit Learning for Iot Networks'' with GRC: A TestBed Implementation and Demonstration that Learning Helps},\\ by \textbf{Lilian Besson}, Rémi Bonnefoi, Christophe Moy.\\ Demonstration presented in \textcolor{orange}{\emph{International Conference on Communication}}, % \footnote{~ICT 2018, see \href{http://ict-2018.org/demos}{\texttt{ict-2018.org/demos}}}, Saint-Malo, France, \textcolor{blue}{June $2018$}.\\ See \href{https://YouTu.be/HospLNQhcMk}{\textcolor{blue}{\texttt{YouTu.be/HospLNQhcMk}}} for a $6$-minutes presentation video.\\ \emph{See Section~5.3.} % \cite{Besson2018ICT} \end{itemize} } \end{frameO} \begin{frameO}[French language conferences with proceedings] {\footnotesize \begin{itemize} \item \emph{Analyse non asymptotique d'un test séquentiel de détection de ruptures et application aux bandits non stationnaires} (in French),\\ by \textbf{Lilian Besson} \& Émilie Kaufmann,\\ \textcolor{orange}{\emph{GRETSI}}, % \footnote{~GRETSI 2019, see \href{http://GRETSI.fr/colloque2019}{\texttt{GRETSI.fr/colloque2019}}}, \textcolor{blue}{August $2019$}.\\ % \href{https://HAL.Inria.fr/hal-02006471}{\texttt{HAL.Inria.fr/hal-02006471}}.\\ \emph{See Chapter~7.} % \cite{Besson2019Gretsi} \end{itemize} } \end{frameO} \begin{frameO}[Submitted works\dots] {\footnotesize \begin{itemize} \item \emph{Decentralized Spectrum Learning for Radio Collision Mitigation in Ultra-Dense IoT Networks: LoRaWAN Case Study and Measurements},\\ by Christophe Moy, \textbf{Lilian Besson}, G. Delbarre \& L. Toutain, \textcolor{blue}{July $2019$}.\\ Submitted for a special volume of \textcolor{darkred}{\href{https://annalsoftelecommunications.wp.imt.fr/}{the Annals of Telecommunications}} journal, on ``Machine Learning for Intelligent Wireless Communications and Networking''.\\ \emph{See Chapter~5.} % Preprint at \href{https://HAL.Inria.fr/hal-XXX}{\texttt{HAL.Inria.fr/hal-XXX}}. % \cite{MoyBesson2019Annales} % \emph{$\hookrightarrow$ Note that we are already working on an extended version that will be submitted to a journal on Machine Learning and Statistical Learning, in autumn $2019$.} \item \emph{The Generalized Likelihood Ratio Test meets klUCB: an Improved Algorithm for Piece-Wise Non-Stationary Bandits},\\ by \textbf{Lilian Besson} \& Émilie Kaufmann \& Odalric-Ambrym Maillard, \textcolor{blue}{October $2019$}.\\ Submitted for \textcolor{darkred}{\href{https://www.aistats.org/}{AISTATS 2020}}. Preprint at \href{https://HAL.Inria.fr/hal-02006471}{\texttt{HAL.Inria.fr/hal-02006471}}.\\ \emph{See Chapter~7.} % \cite{Besson2019GLRT} \item \emph{SMPyBandits: an Open-Source Research Framework for Single and Multi-Players Multi-Arms Bandits (MAB) Algorithms in Python},\\ by \textbf{Lilian Besson}\\ Active development since October $2016$, \href{https://HAL.Inria.fr/hal-01840022}{\texttt{HAL.Inria.fr/hal-01840022}}.\\ It currently consists in about $45000$ lines of code, hosted on \href{https://GitHub.com/SMPyBandits}{\texttt{GitHub.com/SMPyBandits}}, and a complete documentation accessible on \href{https://SMPyBandits.rtfd.io}{\texttt{SMPyBandits.rtfd.io}} or \href{https://SMPyBandits.GitHub.io}{\texttt{SMPyBandits.GitHub.io}}.\\ Submitted for \textcolor{darkred}{\href{https://jmlr.org/mloss/}{JMLR MLOSS}}, in \textcolor{blue}{October $2019$}.\\ \emph{See Chapter~3.} % \cite{SMPyBanditsJMLR,SMPyBandits} \end{itemize} } \end{frameO} \begin{frameO}[In progress works waiting for a new submission\dots] {\footnotesize \begin{itemize} \item \emph{What Doubling-Trick Can and Can't Do for Multi-Armed Bandits},\\ by \textbf{Lilian Besson} \& Émilie Kaufmann, September $2018$.\\ Preprint at \href{https://HAL.Inria.fr/hal-01736357}{\texttt{HAL.Inria.fr/hal-01736357}}. % \cite{Besson2018DoublingTricks} \end{itemize} } \end{frameO} % FIXME terminer ces slides backup \begin{frameO}[Backup slides] \begin{Large} I included here some extra slides\dots \vspace*{15pt} \begin{itemize} \item pseudo code of Rand-Top-$M$ + kl-UCB \item pseudo code of MC-Top-$M$ + kl-UCB \item exact regret bound of MC-Top-$M$ + kl-UCB % \item drawing explaining the proof of regret bound of MCTopM + kl-UCB \end{itemize} \vspace*{15pt} \begin{itemize} \item pseudo code of GLRT + kl-UCB \item exact regret bound of GLRT + kl-UCB \end{itemize} \end{Large} \end{frameO} \begin{frameO}[Our algorithm Rand-Top-$M$] \begin{center} \includegraphics[width=0.99\textwidth]{Backup_Slides__algo_RandTopM.png} \end{center} \end{frameO} \begin{frameO}[Our algorithm MC-Top-$M$] \begin{center} \includegraphics[width=0.99\textwidth]{Backup_Slides__algo_MCTopM.png} \end{center} \end{frameO} \begin{frameO}[Lemma: bad selections for MC-Top-$M$ with kl-UCB] \begin{center} \includegraphics[width=1.04\textwidth]{Backup_Slides__lemma_MCTopM_bad_selections.png} \end{center} \end{frameO} \begin{frameO}[Lemma: collisions for MC-Top-$M$ with kl-UCB] \begin{center} \includegraphics[width=1.04\textwidth]{Backup_Slides__lemma_MCTopM_collisions.png} \end{center} \end{frameO} \begin{frameO}[Theoreom: regret for MC-Top-$M$ with kl-UCB] \begin{center} \includegraphics[width=1.04\textwidth]{Backup_Slides__lemma_MCTopM_regret.png} \end{center} \end{frameO} \begin{frameO}[Our algorigthm GLRT and kl-UCB] \begin{center} \includegraphics[width=0.99\textwidth]{Backup_Slides__algo_GLRT_klUCB.png} \end{center} \end{frameO} \begin{frameO}[Theorem: regret bound for GLRT + kl-UCB (global)] \begin{center} \includegraphics[width=1.04\textwidth]{Backup_Slides__lemma_GLR_regret.png} \end{center} \end{frameO} \begin{frameO}[Corollary: regret bounds for GLRT + kl-UCB (global)] \begin{center} \includegraphics[width=1.04\textwidth]{Backup_Slides__cor_GLR_regret.png} \end{center} \end{frameO} \begin{frameO}[Theorem: regret bound for GLRT + kl-UCB (local)] \begin{center} \includegraphics[width=1.04\textwidth]{Backup_Slides__lemma_GLRlocal_regret.png} \end{center} \end{frameO} \begin{frameO}[Corollary: regret bounds for GLRT + kl-UCB (local)] \begin{center} \includegraphics[width=0.80\textwidth]{Backup_Slides__cor_GLRlocal_regret.png} \end{center} \end{frameO} \begin{frameO}[End of backup slides] \begin{center} \begin{LARGE} End of backup slides \vfill{} Thanks for your attention! \end{LARGE} \end{center} \end{frameO} % % FIXME remettre pour la vraie soutenance ? \begin{frameO}[What about the climatic crisis?] \begin{center} \includegraphics[height=0.75\textheight]{../common/TalkAboutGlobalWarmingNow.png} \begin{tiny} \textcopyright{} Jeph Jacques, 2015, \href{https://QuestionableContent.net/view.php?comic=3074}{\textcolor{blue}{\texttt{QuestionableContent.net/view.php?comic=3074}}} \end{tiny} \end{center} \end{frameO} % \begin{frameO}[Let's talk about actions against the climatic crisis !] % \begin{center} % \includegraphics[height=0.28\textheight]{../common/TalkAboutGlobalWarmingNow.png} % \end{center} % \begin{alertblock}{We are \emph{scientists}\ldots} % Goals: \alert{inform ourselves, think, find, communicate}! % \begin{itemize} % \item \alert{Inform ourselves} of the \alert{causes} and \alert{consequences} of climatic crisis, % \item \alert{Think} of all the problems, at political, local and individual scales, % \item \alert{Find} simple solutions !\\ % $\implies$ Aim at sobriety: transports, tourism, clothing, housing, technologies, food, computations, fighting smoking, etc. % \item \alert{Communicate} our awareness, and our actions ! % \end{itemize} % \end{alertblock} % \end{frameO} % \begin{frameO}[References ($1/6$)] % TODO: update! remove a lot of references on bandits, and add on radio % TODO: add work of Wassim, Navik, Christophe, etc. % TODO: add a slide listing my publications? % {\footnotesize % \begin{itemize} % \item W.R. Thompson (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika. % \item H. Robbins (1952). Some aspects of the sequential design of experiments. \emph{Bulletin of the American Mathematical Society}. % \item Bradt, R., Johnson, S., and Karlin, S. (1956). On sequential designs for maximizing the sum of n observations. \emph{Annals of Mathematical Statistics}. % \item R. Bellman (1956). A problem in the sequential design of experiments. \emph{The indian journal of statistics}. % \item Gittins, J. (1979). Bandit processes and dynamic allocation indices. \emph{Journal of the Royal Statistical Society}. % \item Berry, D. and Fristedt, B. Bandit Problems (1985). Sequential allocation of experiments. \emph{Chapman and Hall}. % \item Lai, T. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. \emph{Advances in Applied Mathematics}. % \item Lai, T. (1987). Adaptive treatment allocation and the multi-armed bandit problem. \emph{Annals of Statistics}. % \end{itemize} % } % \end{frameO} % \begin{frameO}[References ($2/6$)] % {\footnotesize % \begin{itemize} % \item Agrawal, R. (1995). Sample mean based index policies with $\mathcal{O}(\log n)$ regret for the multi-armed bandit problem. \emph{Advances in Applied Probability}. % \item Katehakis, M. and Robbins, H. (1995). Sequential choice from several populations. \emph{Proceedings of the National Academy of Science}. % \item Burnetas, A. and Katehakis, M. (1996). Optimal adaptive policies for sequential allocation problems. \emph{Advances in Applied Mathematics}. % \item Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. \emph{Machine Learning}. % \item Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. (2002). The nonstochastic multiarmed bandit problem. \emph{SIAM Journal of Computing}. % \item Burnetas, A. and Katehakis, M. (2003). Asymptotic Bayes Analysis % for the finite horizon one armed bandit problem. \emph{Probability in the Engineering and Informational Sciences}. % \item Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, Learning and % Games. \emph{Cambridge University Press}. % \item Audibert, J-Y., Munos, R. and Szepesvari, C. (2009). Exploration-exploitation trade-off using varianceestimates in multi-armed bandits. \emph{Theoretical Computer Science}. % \end{itemize} % } % \end{frameO} % \begin{frameO}[References ($3/6$)] % {\footnotesize % \begin{itemize} % \item Audibert, J.-Y. and Bubeck, S. (2010). Regret Bounds and Minimax Policies under Partial Monitoring. \emph{Journal of Machine Learning Research}. % \item Li, L., Chu, W., Langford, J. and Shapire, R. (2010). A Contextual-Bandit Approach to Personalized News Article Recommendation. \emph{WWW}. % \item Honda, J. and Takemura, A. (2010). An Asymptotically Optimal Bandit % Algorithm for Bounded Support Models. \emph{COLT}. % \item Bubeck, S. (2010). Jeux de bandits et fondation du clustering. PhD thesis, Université de Lille 1. % \item A. Anandkumar, N. Michael, A. K. Tang, and S. Agrawal (2011). Distributed algorithms for learning and cognitive medium access with logarithmic regret. \emph{IEEE Journal on Selected Areas in Communications} % \item Garivier, A. and Cappé, O. (2011). The KL-UCB algorithm for bounded stochastic bandits and beyond. \emph{COLT}. % \item Maillard, O.-A., Munos, R., and Stoltz, G. (2011). A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences. \emph{COLT}. % \item Chapelle, O. and Li, L. (2011). An empirical evaluation of Thompson Sampling. \emph{NIPS}. % \end{itemize} % } % \end{frameO} % \begin{frameO}[References ($4/6$)] % { % \footnotesize % \begin{itemize} % \item {E. Kaufmann}, O. Cappé, A. Garivier (2012). On Bayesian Upper Confidence Bounds for Bandits Problems. \emph{AISTATS}. % \item Agrawal, S. and Goyal, N. (2012). Analysis of Thompson Sampling for the multi-armed bandit problem. \emph{COLT}. % \item E. Kaufmann, N. Korda, R. Munos (2012), {Thompson Sampling~: an Asymptotically Optimal Finite-Time Analysis}. \emph{Algorithmic Learning Theory}. % \item Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. \emph{Fondations and Trends in Machine Learning}. % \item Agrawal, S. and Goyal, N. (2013). Further Optimal Regret Bounds for Thompson Sampling. \emph{AISTATS}. % \item O. Cappé, A. Garivier, O-A. Maillard, R. Munos, and G. Stoltz (2013). Kullback-Leibler upper confidence bounds for optimal sequential allocation. \emph{Annals of Statistics}. % \item Korda, N., Kaufmann, E., and Munos, R. (2013). Thompson Sampling for 1-dimensional Exponential family bandits. \emph{NIPS}. % \end{itemize} % } % \end{frameO} % \begin{frameO}[References ($5/6$)] % {\footnotesize % \begin{itemize} % \item Honda, J. and Takemura, A. (2014). Optimality of Thompson Sampling for Gaussian Bandits depends on priors. \emph{AISTATS}. % \item Baransi, Maillard, Mannor (2014). Sub-sampling for multi-armed bandits. \emph{ECML}. % \item Honda, J. and Takemura, A. (2015). Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. \emph{JMLR}. % \item Kaufmann, E., Capp\'e O. and Garivier, A. (2016). On the complexity of best arm identification in multi-armed bandit problems. \emph{JMLR} % \item Lattimore, T. (2016). Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits. \emph{COLT}. % \item Garivier, A., Kaufmann, E. and Lattimore, T. (2016). On Explore-Then-Commit strategies. \emph{NIPS}. % \item E.Kaufmann (2017), On Bayesian index policies for sequential resource allocation. \emph{Annals of Statistics}. % \item Agrawal, S. and Goyal, N. (2017). Near-Optimal Regret Bounds for Thompson Sampling. \emph{Journal of ACM}. % \end{itemize} % } % \end{frameO} % \begin{frameO}[ ($6/6$)] % {\footnotesize % \begin{itemize} % \item Maillard, O-A (2017). Boundary Crossing for General Exponential Families. \emph{Algorithmic Learning Theory}. % \item Besson, L., Kaufmann E. (2018). Multi-Player Bandits Revisited. \emph{Algorithmic Learning Theory}. % \item Cowan, W., Honda, J. and Katehakis, M.N. (2018). Normal Bandits of Unknown Means and Variances. \emph{JMLR}. % \item Garivier,A. and Ménard, P. and Stoltz, G. (2018). Explore first, exploite next: the true shape of regret in bandit problems, \emph{Mathematics of Operations Research} % \item Garivier, A. and Hadiji, H. and Ménard, P. and Stoltz, G. (2018). % KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints. \emph{arXiv: 1805.05071}. % \item Besson, L., Kaufmann E. (2019). The Generalized Likelihood Ratio Test meets klUCB: an Improved Algorithm for Piece-Wise Non-Stationary Bandits. \emph{Algorithmic Learning Theory}. \emph{arXiv: 1902.01575}. % \end{itemize} % } % \end{frameO} \end{document}