\documentclass[12pt,english,ignorenonframetext,]{beamer} %%%%%%%%%%%%%%% %% Beamer theme % choose one from http://deic.uab.es/~iblanes/beamer_gallery/ % or http://www.hartwork.org/beamer-theme-matrix/ % \usetheme{Warsaw} \usetheme{CambridgeUS} %%%%%%%%%%%%%%%%%%%%%% %% Beamer color theme %% default albatross beaver beetle crane dolphin dove fly lily %% orchid rose seagull seahorse whale wolverine %\usecolortheme{seahorse} %% very lighty \usecolortheme{dolphin} %% nice blue \usecolortheme{orchid} %% dark red ? \usecolortheme{whale} %% black and blue as Warsaw %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Define your own colors \definecolor{blackblue}{rgb}{19,19,59} % rgb(48,48,150) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Change the theme %\setbeamercolor{alerted text}{fg=orange} %\setbeamercolor{background canvas}{bg=white} %\setbeamercolor{block body alerted}{bg=normal text.bg!90!black} %\setbeamercolor{block body}{bg=normal text.bg!90!black} %\setbeamercolor{block body example}{bg=normal text.bg!90!black} %\setbeamercolor{block title alerted}{use={normal text,alerted text},fg=alerted text.fg!75!normal text.fg,bg=normal text.bg!75!black} %\setbeamercolor{block title}{bg=blue} %\setbeamercolor{block title example}{use={normal text,example text},fg=example text.fg!75!normal text.fg,bg=normal text.bg!75!black} %\setbeamercolor{fine separation line}{} \setbeamercolor{frametitle}{fg=black} %\setbeamercolor{item projected}{fg=black} %\setbeamercolor{normal text}{bg=black,fg=yellow} %\setbeamercolor{palette sidebar primary}{use=normal text,fg=normal text.fg} %\setbeamercolor{palette sidebar quaternary}{use=structure,fg=structure.fg} %\setbeamercolor{palette sidebar secondary}{use=structure,fg=structure.fg} %\setbeamercolor{palette sidebar tertiary}{use=normal text,fg=normal text.fg} %\setbeamercolor{section in sidebar}{fg=brown} %\setbeamercolor{section in sidebar shaded}{fg= grey} \setbeamercolor{separation line}{} %\setbeamercolor{sidebar}{bg=red} %\setbeamercolor{sidebar}{parent=palette primary} %\setbeamercolor{structure}{bg=black, fg=green} %\setbeamercolor{subsection in sidebar}{fg=brown} %\setbeamercolor{subsection in sidebar shaded}{fg= grey} %\setbeamercolor{title}{fg=blackblue} %\setbeamercolor{titlelike}{fg=blackblue} %%%%%%%%%%%%%%%%%%%%%%% %% Other beamer options %\setbeamercovered{transparent} % Permet de laisser en gris le texte qui n'est pas encore apparu (lorsqu'on utilise les commandes avec des <1,2> ou <4-9>. %\setbeamercolor{normal text}{fg=black,bg=white} %%%%%%%%%%%%%%%%%%%%%%% %% Change Beamer fonts % \usefonttheme{default} % \usefonttheme[onlymath]{serif} \usefonttheme{serif} \setbeamerfont{title}{family=\rm} \setbeamerfont{titlelike}{family=\rm} \setbeamerfont{frametitle}{family=\rm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% innertheme %% rectangles circles inmargin rounded % \useinnertheme{rounded} % XXX My preference \useinnertheme{circles} % XXX %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% outertheme %% infolines miniframes shadow sidebar smoothbars smoothtree split tree %\useoutertheme{infolines} %% No navigation symbol. \setbeamertemplate{navigation symbols}{} \beamertemplatenavigationsymbolsempty % XXX Add a background image to the slides % \usepackage{tikz} % \setbeamertemplate{background}{\includegraphics[width=\paperwidth,height=\paperheight,keepaspectratio]{IETR.jpg}} % \setbeamertemplate{background}{{\centering\begin{tikzpicture}\node[opacity=0.15]{\includegraphics[width=0.98\paperwidth]{IETR_et_partenaires_IETR.png}};\end{tikzpicture}}} % Other options %\setbeamertemplate{footline}[page number] \beamertemplateballitem \setbeamertemplate{itemize item}[square] \setbeamertemplate{caption}[numbered] \setbeamertemplate{caption label separator}{: } \setbeamercolor{caption name}{fg=normal text.fg} \beamertemplatenavigationsymbolsempty \usepackage{lmodern} \usepackage{color} \newcommand{\urlb}[1]{\textcolor{blue}{\url{#1}}} %% Color definition \usepackage{xcolor} %% WARNING attention when changing the colors, change both the {RGB}{r,g,b} and % rgb(r,g,b) \definecolor{bleu}{RGB}{0,0,204} % rgb(0,0,204) \definecolor{deeppurple}{RGB}{102,0,204} % rgb(102,0,204) \definecolor{darkgreen}{RGB}{0,100,0} % rgb(0,100,0) \definecolor{yellowgreen}{RGB}{200,215,0} % rgb(200,215,0) \definecolor{bluegreen}{RGB}{0,185,140} % rgb(0,185,140) \definecolor{gold}{RGB}{255,180,0} % rgb(255,180,0) \definecolor{strongred}{RGB}{255,0,0} % rgb(255,0,0) \definecolor{normalred}{RGB}{204,0,0} % rgb(204,0,0) \definecolor{darkred}{RGB}{174,0,0} % rgb(174,0,0) \usepackage{amssymb,amsmath} \usepackage{bbm,bm} % bold maths symbols \usepackage{ifxetex,ifluatex} \usepackage{fixltx2e} % provides \textsubscript % FIXME remove as soon as possible, it slows down compilation to import TikZ %% TikZ \usepackage{tikz} \usetikzlibrary{snakes,arrows,shapes} % https://tex.stackexchange.com/a/226974/ \tikzset{ font={\fontsize{10pt}{10}\selectfont} } \usepackage{tikzsymbols} % https://tex.stackexchange.com/a/227226/97964 \IfFileExists{macrosText.sty}{\usepackage{macrosText}}{} \usepackage{fourier} \usepackage[linesnumbered,commentsnumbered,inoutnumbered,slide]{algorithm2e} \ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \else % if luatex or xelatex \ifxetex \usepackage{mathspec} \else \usepackage{fontspec} \fi \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase} \fi % use upquote if available, for straight quotes in verbatim environments \IfFileExists{upquote.sty}{\usepackage{upquote}}{} % use microtype if available \IfFileExists{microtype.sty}{% \usepackage{microtype} \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts }{} \ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex \usepackage[shorthands=off,main=english]{babel} \else \usepackage{polyglossia} \setmainlanguage[]{} \fi \newif\ifbibliography \hypersetup{ pdftitle={Multi-Player Bandits Revisited}, pdfauthor={Lilian Besson}, pdfborder={0 0 0}, breaklinks=true} % \urlstyle{same} % don't use monospace font for urls % Code embedding. \usepackage{palatino} % Use the Palatino font % XXX remove if it is ugly ? \ifxetex \usepackage{fontspec} %\setmainfont[Ligatures=Historic]{TeX Gyre Pagella} \setmainfont[Ligatures=Historic]{Palatino-Roman} \newfontfamily\FiraCode{Fira Code} \setmonofont[Contextuals={Alternate}]{Fira Code} \newfontfamily\Fontify[Path = ../common/]{Fontify-Regular} \else \newcommand{\Fontify}{} \fi % Prevent slide breaks in the middle of a paragraph: \widowpenalties 1 10000 \raggedbottom \setlength{\parindent}{0pt} \setlength{\parskip}{6pt plus 2pt minus 1pt} \setlength{\emergencystretch}{3em} % prevent overfull lines \providecommand{\tightlist}{% \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}} \setcounter{secnumdepth}{5} % https://tex.stackexchange.com/a/70495/ \usepackage{appendixnumberbeamer} \title{Multi-Player Bandits Revisited} \subtitle{Decentralized Multi-Player Multi-Arm Bandits} \author[Lilian Besson]{\textbf{Lilian Besson} \newline \emph{Joint work with} \and Émilie Kaufmann} \institute[CentraleSupélec \& Inria]{PhD Student \newline Team SCEE, IETR, CentraleSupélec, Rennes \newline \& Team SequeL, CRIStAL, Inria, Lille} \date[CMAP Seminar -- $31$ Oct $2018$]{CMAP Seminar -- $31^{\text{st}}$ October $2018$} % For \justifying command, see https://tex.stackexchange.com/a/148696/ \usepackage{ragged2e} \addtobeamertemplate{frame begin}{}{\justifying} \addtobeamertemplate{block begin}{}{\justifying} \addtobeamertemplate{block alerted begin}{}{\justifying} \addtobeamertemplate{block example begin}{}{\justifying} \addtobeamertemplate{itemize body begin}{}{\justifying} \addtobeamertemplate{itemize item}{}{\justifying} \addtobeamertemplate{itemize subitem}{}{\justifying} \addtobeamertemplate{itemize subsubitem}{}{\justifying} \addtobeamertemplate{enumerate body begin}{}{\justifying} \addtobeamertemplate{enumerate item}{}{\justifying} \addtobeamertemplate{enumerate subitem}{}{\justifying} \addtobeamertemplate{enumerate subsubitem}{}{\justifying} \addtobeamertemplate{description body begin}{}{\justifying} \addtobeamertemplate{description item}{}{\justifying} \begin{document} \justifying \begin{frame}[plain] \titlepage % XXX manual inclusion of logos \begin{center} \includegraphics[height=0.13\textheight]{../common/LogoIETR.png} \includegraphics[height=0.17\textheight]{../common/LogoCS.png} \includegraphics[height=0.13\textheight]{../common/LogoInria.jpg} \end{center} \end{frame} \section*{\hfill{}CentraleSupélec Rennes \& Inria Lille\hfill{}} \subsection*{\hfill{}Team {:} SCEE @ IETR \& SequeL @ CRIStAL\hfill{}} \section{\hfill{}1. Introduction and motivation\hfill{}} \subsection{\hfill{}1.a. Objective\hfill{}} \begin{frame}{Motivation} We control some communicating devices, they want to use a wireless access point. \pause \begin{itemize}\tightlist \item Insert them in a \textbf{crowded wireless network}. \item With a protocol \textbf{slotted in both time and frequency}. \end{itemize} \pause \begin{block}{Goal} \begin{itemize}\tightlist \item Maintain a \textbf{good Quality of Service}. \item \textbf{With no centralized control} as it costs network overhead. \end{itemize} \end{block} \pause \begin{block}{How?} \begin{itemize}\tightlist \item Devices can choose a different radio channel at each time \hook learn the best one with a \emph{sequential algorithm}! \end{itemize} \end{block} \end{frame} \subsection{\hfill{}1.b. Outline and references\hfill{}} \begin{frame}{Outline \uncover<5->{and reference}} \vspace*{-15pt} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item Introduction \item Our model: \(3\) different feedback levels \item Regret of the system, and our lower bound on regret \vspace*{10pt} \pause \item Quick reminder on single-player MAB algorithms \item New multi-player non-coordinated decentralized algorithms \item Our upper bound on regret for \MCTopM \vspace*{10pt} \pause \item Experimental results \item Review of two more recent articles % \item % An heuristic (\Selfish), and disappointing results \vspace*{10pt} \pause \item Conclusion \end{enumerate} \pause \vfill{} \begin{footnotesize} Based on \emph{``Multi-Player Bandits Revisited''}, by Lilian Besson \& {\'E}milie Kaufmann. \texttt{\textcolor{blue}{\href{https://arXiv.org/abs/1711.02317}{arXiv:1711.02317}}}, presented at \emph{ALT 2018} (Lanzarote, Spain) in April. \end{footnotesize} \end{frame} \section{\hfill{}2. Our model: $3$ different feedback levels\hfill{}} \begin{frame}{Our model} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item Our communication model \item With or without sensing \item Background traffic, and rewards \item Different feedback levels \item Goal \end{enumerate} \end{frame} \subsection{\hfill{}2.a. Our communication model\hfill{}} \begin{frame}{Our communication model} \(K\) radio channels (\eg, 10). Discrete and synchronized time \(t\geq1\). % Every time frame \(t\) is: \begin{figure}[h!] \centering % \includegraphics[height=0.27\textheight]{figures/protocol.eps} % \caption{\small{Protocol in time and frequency, with an \textcolor{darkgreen}{\emph{Acknowledgement}}.}} \includegraphics[height=0.50\textheight]{figures/protocol_v2.png} % \caption{\small{Protocol in time and frequency, with an \textcolor{darkgreen}{\emph{Acknowledgement}}.}} \end{figure} \pause \begin{block}{Dynamic device \(=\) dynamic radio reconfiguration} \begin{itemize}\tightlist \item It decides \textbf{each time} the channel it uses to send \textbf{each packet}. \item It can implement a simple \textbf{decision algorithm}. \end{itemize} \end{block} \end{frame} \subsection{\hfill{}2.b. With or without sensing\hfill{}} \begin{frame}[fragile]{Our model} \begin{block}{``Easy'' case} \begin{itemize}\tightlist \item \(M \leq K\) devices \textbf{always communicate} and try to access the network, \emph{independently} without centralized supervision, \item Background traffic is \iid. \end{itemize} \end{block} \pause \begin{block}{Two variants : with or without \emph{sensing}} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item \emph{With sensing}: Device first senses for presence of Primary Users that have strict priority (background traffic), then use \texttt{Ack} to detect collisions. % \begin{quote} % \small{Model the ``classical'' Opportunistic Spectrum Access problem. % Not exactly suited for \emph{Internet of Things}, but can model ZigBee, and can be analyzed mathematically...} % \end{quote} \item \emph{Without sensing}: same background traffic, but cannot sense, so only \texttt{Ack} is used. % \small{More suited for ``IoT'' networks like LoRa or SigFox} (Harder to % analyze mathematically.) \end{enumerate} \end{block} \end{frame} \subsection{\hfill{}2.c. Background traffic, and rewards\hfill{}} \begin{frame}{Background traffic, and rewards} \begin{block}{\iid{} background traffic} \begin{itemize}\tightlist \item \(K\) channels, modeled as Bernoulli (\(0/1\)) distributions of mean \(\mu_k\) \(=\) background traffic from \emph{Primary Users}, bothering the dynamic devices, \item \(M\) devices, each uses channel \(A^j(t) \in \{1,\dots,K\}\) at time \(t\). \end{itemize} \pause \end{block} \begin{block}{Rewards} \[r^j(t) := Y_{A^j(t),t} \alert{\times} \mathbbm{1}(\overline{C^j(t)}) = \mathbbm{1}(\text{uplink \alert{\&} Ack})\] \begin{itemize}\tightlist \item with sensing information \(\;\;\) \(\forall k, \;\; Y_{k,t} \overset{\text{iid}}{\sim} \mathrm{Bern}(\mu_k) \in \{0, 1\}\), \item collision for device \(j\) : \(\;\;\) \(C^j(t) = \mathbbm{1}(\)\emph{alone on arm $A^j(t)$}\()\). \newline \(\hookrightarrow\) \(r^j(t)\) \alert{combined} binary reward \textbf{but not} from two Bernoulli! \end{itemize} \end{block} \end{frame} \subsection{\hfill{}2.d. Different feedback levels\hfill{}} \begin{frame}{3 feedback levels} \only<1>{$$r^j(t) := \textcolor{red}{Y_{A^j(t),t}} \times \textcolor{blue}{\mathbbm{1}(\overline{C^j(t)})}$$} \only<2>{$$r^j(t) := \textcolor{strongred}{Y_{A^j(t),t}} \times \textcolor{normalred}{\mathbbm{1}(\overline{C^j(t)})}$$} \only<3>{$$r^j(t) := \textcolor{deeppurple}{Y_{A^j(t),t} \times \mathbbm{1}(\overline{C^j(t)})}$$} \only<4>{$$\alert{r^j(t)} := Y_{A^j(t),t} \times \mathbbm{1}(\overline{C^j(t)})$$} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item ``Full \textcolor<1>{red}{feed}\textcolor<1>{blue}{back}'': observe both \textcolor<1>{red}{$Y_{A^j(t),t}$} \emph{and} \textcolor<1>{blue}{$C^j(t)$} separately, \hook Not realistic enough, we don't focus on it. \vspace*{10pt}\pause \item \textcolor<2>{strongred}{``Sensing''}: first observe \(\textcolor<2>{strongred}{Y_{A^j(t),t}}\), \emph{then} \(\textcolor<2>{normalred}{C^j(t)}\) only if \(\textcolor<2>{strongred}{Y_{A^j(t),t}} \neq 0\), \hook Models licensed protocols (ex. ZigBee), our main focus. \vspace*{10pt}\pause \item \textcolor<3>{deeppurple}{``No sensing''}: observe only the combined \(\textcolor<3>{deeppurple}{Y_{A^j(t),t} \times \mathbbm{1}(\overline{C^j(t)})}\), \hook Unlicensed protocols (ex. LoRaWAN), harder to analyze ! \end{enumerate} \uncover<4>{\begin{quote}But all consider the same instantaneous \alert{reward $r^j(t)$}.\end{quote}} \end{frame} \subsection{\hfill{}2.e. Goal\hfill{}} \begin{frame}{Goal} \begin{block}{Goal} \begin{itemize}\tightlist \item \emph{Minimize packet loss ratio} \newline (\(=\) maximize nb of received \texttt{Ack}) \item in a \emph{finite-space discrete-time Decision Making Problem}. \end{itemize} \end{block} \vspace*{20pt} \pause \begin{block}{Solution ?} \textbf{Multi-Armed Bandit algorithms} \begin{itemize}\tightlist \item \textbf{decentralized} and \item used \textbf{independently} by each dynamic device. \end{itemize} \end{block} % \begin{block}{\emph{Decentralized} reinforcement learning optimization!} % \begin{itemize} % \tightlist % \item % Max transmission rate \(\equiv\) \textbf{max cumulated rewards} % \(\max\limits_{\text{algorithm}\;A} \;\; \sum\limits_{t=1}^{T} \sum\limits_{j=1}^M r^j(t)\). % \item % Each player wants to \textbf{maximize its cumulated reward}, % \item % With no central control, and no exchange of information, % \item % Only possible if: each player converges to one of the \(M\) best % arms, orthogonally (without collisions). % \end{itemize} % \end{block} \end{frame} \subsection{\hfill{}2.f. Centralized regret\hfill{}} \begin{frame}{Centralized regret} \begin{block}{A measure of success} \begin{itemize}\tightlist \item \textbf<1>{Not} the network throughput or collision probability, \item We study the \textbf<1>{centralized} (\textcolor<1>{blue}{expected}) \textbf<1>{regret}: \end{itemize} \begin{small}\vspace*{-10pt} $$R_T(\boldsymbol{\mu}, M, \rho) := % \E_{\mu}\left[ \sum_{t=1}^T \sum_{j=1}^M \alert<1>{\mu_j^*} - r^j(t)\right] \pause= \left(\sum_{k=1}^{M}\alert<1>{\mu_k^*}\right) T - \textcolor<1>{blue}{\E_{\mu}}\left[\sum_{t=1}^T\sum_{j=1}^M r^j(t) \right].$$ \end{small} \vspace*{-10pt} \end{block} \only<1>{ Notation: $\alert{\mu_k^*}$ is the mean of the $k$-best arm ($k$-th largest in $\boldsymbol{\mu}$): \begin{itemize} \item $\mu_1^* := \max \boldsymbol{\mu}$, \item $\mu_2^* := \max \boldsymbol{\mu} \setminus \{\mu_1^*\}$, \item etc. \end{itemize} \citationbottomright{Ref: [Lai \& Robbins, 1985], [Liu \& Zhao, 2009], [Anandkumar et al, 2010]} } \begin{block}<2->{Two directions of analysis} \begin{itemize}\tightlist % \item<2-4> % Clearly \(R_T = \mathcal{O}(T)\), but we want a sub-linear regret, as % small as possible! \item<2-> \emph{How good a decentralized algorithm can be in this setting?} \hook{} \alert{Lower Bound} on the regret, for \alert{any} algorithm ! \item<2-> \emph{How good is my decentralized algorithm in this setting?} \hook{} \alert{Upper Bound} on the regret, for \alert{one} algorithm ! \end{itemize} \end{block} \end{frame} \section{\hfill{}3. Lower bound\hfill{}} \begin{frame}{Lower bound} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item Decomposition of the regret in \(3\) terms,\vspace*{15pt} \item Asymptotic lower bound on one term,\vspace*{15pt} \item And for the regret,\vspace*{15pt} \item \alert{Possibly wrong result, not sure yet!} \end{enumerate} \end{frame} \subsection{\hfill{}3.a. Lower bound on the regret\hfill{}} \begin{frame}{\only<1-4>{Decomposition}\only<5>{\alert{Lower bound}} on the regret} \begin{block}{\only<1-4>{Decomposition}\only<5>{Lower bound}} For any algorithm, decentralized or not, we have \vspace*{-10pt} \begin{footnotesize}\begin{align*} R_T(\boldsymbol{\mu}, M, \rho) &\only<1-4>{=}\only<5>{\alert<5>{\boldsymbol{\geq}}} \alert<2>{\sum_{k \in \Mworst} (\mu_M^* - \mu_k) \E_{\mu}[\textcolor<1>{blue}{T_k(T)}]} \\ &\uncover<1-4>{+ \alert<3>{\sum_{k \in \Mbest} (\mu_k - \mu_M^*) \left(T - \E_{\mu}[\textcolor<1>{blue}{T_k(T)}]\right)} + \alert<4>{\sum_{k=1}^{K} \mu_k \E_{\mu}[\textcolor<1>{red}{\mathcal{C}_k(T)}]}.} \end{align*}\end{footnotesize} \vspace*{-10pt} \end{block} \only<1>{\small{ Notations for an arm $k\in\{1,\dots,K\}$: \begin{itemize} \item $T_k^j(T) := \sum_{t=1}^T \mathbbm{1}(A^j(t) = k)$, counts selections by the player $j\in\{1,\dots,M\}$, \item $\textcolor{blue}{T_k(T)} := \sum_{j=1}^M T_k^j(T)$, counts selections by all $M$ players, \item $\textcolor{red}{\mathcal{C}_k(T)} := \sum_{t=1}^T \mathbbm{1}(\exists j_1 \neq j_2, A^{j_1}(t) = k = A^{j_2}(t))$, counts collisions. \end{itemize} }} \begin{block}<2-4>{Small regret can be attained if\ldots{}} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item<2-4> Devices can quickly identify the bad arms \(\Mworst\), and not play them too much (\alert<2>{\emph{number of sub-optimal selections}}), \item<3-4> Devices can quickly identify the best arms, and most surely play them (\alert<3>{\emph{number of optimal non-selections}}), \item<4> Devices can use orthogonal channels (\alert<4>{\emph{number of collisions}}). \end{enumerate} \end{block} \end{frame} \begin{frame}{Asymptotic lower bound on the regret I} \begin{block}{Theorem $1$ \hfill{}\textcolor{gray}{[Besson \& Kaufmann, 2018]}} Sub-optimal arms selections are lower bounded asymptotically, \[\forall\, \text{player}\, j, \text{bad arm}\,k,\;\;\;\; \mathop{\lim\inf}\limits_{T \to +\infty} \frac{\E_{\mu}[T_k^j(T)]}{\log T} \geq \frac{1}{\kl(\mu_k, \mu_M^*)},\] \footnotetext{\tiny Where $\kl(x,y) := \mathcal{KL}(\mathcal{B}(x), \mathcal{B}(y)) = x \log(\frac{x}{y}) + (1 - x) \log(\frac{1-x}{1-y})$ is the \emph{binary} KL divergence.} % Kullback-Leibler \end{block} Proof: using classical information theory tools (Kullback-Leibler divergence, change of distributions)\dots \citationright{Ref: [Garivier et al, 2016]} \end{frame} \begin{frame}{Asymptotic lower bound on the regret II} \begin{block}{Theorem $2$ \hfill{}\textcolor{gray}{[Besson \& Kaufmann, 2018]}} \small{For any uniformly efficient decentralized policy, and any non-degenerated problem \(\boldsymbol{\mu}\),} \vspace*{-10pt} \[ \mathop{\lim\inf}\limits_{T \to +\infty} \frac{R_T(\boldsymbol{\mu}, M, \rho)}{\log(T)} \geq \alert<2>{M \times} \left( \sum_{k \in \Mworst} \frac{(\mu_M^* - \mu_k)}{\kl(\mu_k, \mu_M^*)} \right) . \] \end{block} \pause \begin{block}{Remarks} \begin{itemize}\tightlist \item The centralized \emph{multiple-play} lower bound is the same without the \alert{\(M\) multiplicative factor}\ldots{} \citationright{Ref: [Anantharam et al, 1987]} \hook \alert{``price of non-coordination''} \(= M =\) nb of player? \item Improved state-of-the-art lower bound, but still not perfect: collisions should also be controlled! \end{itemize} \end{block} \end{frame} \subsection{\hfill{}3.b. Possibly wrong result, not sure yet\hfill{}} \begin{frame}{\alert{Possibly wrong result, not sure yet?}} \begin{itemize}\tightlist \item A recent article studied the same problem (\textcolor{blue}{\href{https://arxiv.org/abs/1809.08151}{arXiv:1809.08151}}). \only<1>{ \vspace*{10pt} \begin{figure}[h!] \centering \includegraphics[height=0.65\textheight]{figures/SIC_MMAB_front_page.png} % \caption{\footnotesize{Front page of their article.}} \end{figure} } \pause \item They showed a regret upper bound for their \SICMMAB{} algorithm which disproves our regret lower bound:\\ they do not suffer from any ``price of decentralization'' {\Sadey} ! \only<2>{ \begin{figure}[h!] \centering \includegraphics[height=0.50\textheight]{figures/SIC_MMAB_and_its_regret_bound.png} % \caption{\footnotesize{Theorem 1 from their article, regret bound for the \SICMMAB{} algorithm (same setting as ours: with sensing).}} \end{figure} } \pause \vspace*{15pt} \item Their algorithm works fine in practice, see later, and their proof seems fine, but the point they indicate as wrong in our paper is not clear and we couldn't find an error. \item $\implies$ I will work on this more in the near future! \end{itemize} \vfill{} \begin{footnotesize} ``\emph{SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits}'', by Etienne Boursier \& Vianney Perchet, \textcolor{blue}{\href{https://arxiv.org/abs/1809.08151}{arXiv:1809.08151}} \end{footnotesize} \end{frame} \section{\hfill{}4. Single-player MAB algorithm: \klUCB\hfill{}} \begin{frame}{Single-player MAB algorithms} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist % \item % Index-based MAB deterministic policies,\vspace*{15pt} \item Upper Confidence Bound algorithm : \UCB,\vspace*{15pt} \item Kullback-Leibler UCB algorithm : \klUCB. \end{enumerate} \end{frame} \subsection{\hfill{}4.a. Upper Confidence Bound algorithm : \UCB\hfill{}} \begin{frame}{Upper Confidence Bound algorithm (\(\mathrm{UCB}_1\))} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item For the first \(K\) steps (\(t=1,\dots,K\)), try each channel \emph{once}. \item Then for the next steps \(t > K\) : \begin{itemize} \tightlist \item \(T_k^j(t) := \sum\limits_{s=1}^{t} \mathbbm{1}(A^j(s) = k)\) selections of channel \(k\), \item \(S_k^j(t) := \sum\limits_{s=1}^{t} Y_{k}(s) \mathbbm{1}(A^j(s) = k)\) sum of sensing information. \item Compute the index \(\mathrm{UCB}_k^j(t) := \underbrace{\alert{\frac{S_k^j(t)}{T_k^j(t)}}}_{\text{Empirical Mean}\; \widehat{\mu_k}(t)} + \underbrace{\sqrt{\frac{\log(t)}{2 \; T_k^j(t)}},}_{\text{Confide isnce Bonus}}\) \item Choose channel \(A^j(t) = \mathop{\arg\max}\limits_{k} \; \mathrm{UCB}_k^j(t)\), \item Update \(T_k^j(t+1)\) and \(S_k^j(t+1)\). \end{itemize} \end{enumerate} \citationbottomright{Ref: [Auer et al, 2002], [Bubeck \& Cesa-Bianchi, 2012]} \end{frame} \subsection{\hfill{}Kullback-Leibler UCB algorithm: \klUCB\hfill{}} \begin{frame}{Kullback-Leibler UCB algorithm (\(\mathrm{kl}\)-\(\mathrm{UCB}\))} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item For the first \(K\) steps (\(t=1,\dots,K\)), try each channel \emph{once}. \item Then for the next steps \(t > K\) : \begin{itemize} \tightlist \item \(T_k^j(t) := \sum\limits_{s=1}^{t} \mathbbm{1}(A^j(s) = k)\) selections of channel \(k\), \item \(S_k^j(t) := \sum\limits_{s=1}^{t} Y_{k}(s) \mathbbm{1}(A^j(s) = k)\) sum of sensing information. \item Compute \(\mathrm{UCB}_k^j(t)\), \emph{Upper Confidence Bound} on mean \(\mu_k\) \newline \(\mathrm{UCB}_k^j(t) := \sup\limits_{q \in [a, b]} \left\{ q : \mathrm{kl}\left(\alert{\frac{S_k^j(t)}{T_k^j(t)}}, q\right) \leq \frac{\log(t)}{T_k^j(t)} \right\}\), \item Choose channel \(A^j(t) = \mathop{\arg\max}\limits_{k} \; \mathrm{UCB}_k^j(t)\), \item Update \(T_k^j(t+1)\) and \(S_k^j(t+1)\). \end{itemize} \end{enumerate} \begin{small} Known result: \klUCB{} is asymptotically optimal for $1$-player Bernoulli stochastic bandit. \citationright{Ref: [Garivier \& Cappé, 2011], [Cappé et al, 2013]} \end{small} \end{frame} \section{\hfill{}5. Multi-player decentralized algorithms\hfill{}} \begin{frame}{Multi-player decentralized algorithms} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item Common building blocks of previous algorithms,\vspace*{15pt} % \item % First proposal: \RandTopM,\vspace*{15pt} \item % Second proposal: One of our proposal: the \MCTopM{} algorithm. \end{enumerate} \end{frame} \subsection{\hfill{}5.a. State-of-the-art MP algorithms\hfill{}} \begin{frame}{Algorithms for this easier model} \begin{block}{Building blocks: separate the two aspects} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item \textbf{MAB policy} to learn the best arms (use sensing \(Y_{A^j(t),t}\)), \item \textbf{Orthogonalization scheme} to avoid collisions (use collision indicators \(C^j(t)\)). \end{enumerate} \end{block} \begin{block}{Many different proposals for \emph{decentralized} learning policies} \begin{itemize}\tightlist \item ``State-of-the-art'': \rhoRand{} % policy and variants, \citationright{Ref: [Anandkumar et al, 2011]} \item Recent: \MEGA{} and \MusicalChair{}. \citationright{Ref: [Avner \& Mannor, 2015], [Shamir et al, 2016]} \end{itemize} \end{block} \pause \begin{exampleblock}{Our contributions: \hfill{}\textcolor{gray}{[Besson \& Kaufmann, 2018]}} % \RandTopM{} and \MCTopM{} are sort of mixes % between \rhoRand{} and \MusicalChair, using UCB or more % efficient index policies (\klUCB). Two new orthogonalization scheme inspired by \RhoRand{} and \MusicalChair{}, combined with the use of \klUCB{} indices. \end{exampleblock} \end{frame} % \subsection{\hfill{}5.b. \RandTopM{} algorithm\hfill{}} % \begin{frame}{A first decentralized algorithm (naive)} % \centerline{\scalebox{0.80}{\begin{minipage}{1.25\textwidth} %% https://tex.stackexchange.com/a/366403/ % \begin{figure}[h!] % \centering % % Documentation at http://mirror.ctan.org/tex-archive/macros/latex/contrib/algorithm2e/doc/algorithm2e.pdf if needed % % Or https://en.wikibooks.org/wiki/LaTeX/Algorithms#Typesetting_using_the_algorithm2e_package % % \removelatexerror% Nullify \@latex@error % Cf. http://tex.stackexchange.com/a/82272/ % \begin{algorithm}[H] % % XXX Input, data and output % % \KwIn{$K$ and policy $P^j$ for arms set $\{1,\dots,K\}$\;} % % \KwData{Data} % % \KwResult{Result} % % XXX Algorithm % Let $A^j(1) \sim \mathcal{U}(\{1,\dots,K\})$ and $C^j(1)=\mathrm{False}$ \\ % \For{$t = 1, \dots, T - 1$}{ % % % \pause % \eIf{$A^j(t) \notin \TopM(t)$ or $C^j(t)$}{ % $A^j(t+1) \sim \mathcal{U} \left(\TopM(t)\right)$ % \tcp*[f]{randomly switch} % }{ % $A^j(t+1) = A^j(t)$ % \tcp*[f]{stays on the same arm} % } % \pause % Play arm $A^j(t+1)$, get new observations (sensing and collision), \\ % Compute the indices $\mathrm{UCB}^j_k(t+1)$ and set $\TopM(t+1)$ for next step. % } % \caption{A first decentralized learning policy (for a fixed underlying index policy $\mathrm{UCB}^j$). \newline The set $\TopM(t)$ is the \alert{$M$ best arms according to indexes $\mathrm{UCB}^j(t)$}.} % \label{algo:firstAlgo} % \end{algorithm} % \end{figure} % \end{minipage}}} % \end{frame} % \begin{frame}{\RandTopM{} algorithm \only<3>{\hfill{} (good but not the best!)}} % \centerline{\scalebox{0.80}{\begin{minipage}{1.25\textwidth} %% https://tex.stackexchange.com/a/366403/ % \begin{figure}[h!] % \centering % % Documentation at http://mirror.ctan.org/tex-archive/macros/latex/contrib/algorithm2e/doc/algorithm2e.pdf if needed % % Or https://en.wikibooks.org/wiki/LaTeX/Algorithms#Typesetting_using_the_algorithm2e_package % % \removelatexerror% Nullify \@latex@error % Cf. http://tex.stackexchange.com/a/82272/ % \begin{algorithm}[H] % % XXX Input, data and output % % \KwIn{$K$ and policy $P^j$ for arms set $\{1,\dots,K\}$\;} % % \KwData{Data} % % \KwResult{Result} % % XXX Algorithm % Let $A^j(1) \sim \mathcal{U}(\{1,\dots,K\})$ and $C^j(1)=\mathrm{False}$ \\ % \For{$t = 1, \dots, T - 1$}{ % % % \eIf{$A^j(t) \notin \TopM(t)$}{ % \eIf(\tcp*[f]{collision}){$C^j(t)$}{ % $A^j(t+1) \sim \mathcal{U} \left(\TopM(t)\right)$ % \tcp*[f]{randomly switch} % \pause % }(\tcp*[f]{\alert{arm with smaller index at $t-1$}}){ % $A^j(t+1) \sim \mathcal{U} \left(\TopM(t) \cap \left\{k : \alert{\mathrm{UCB}_k^j(t-1) \leq \mathrm{UCB}^j_{A^j(t)}(t-1)}\right\}\right)$ % } % }{ % \pause % $A^j(t+1) = A^j(t)$ % \tcp*[f]{stays on the same arm} % } % Play arm $A^j(t+1)$, get new observations (sensing and collision), \\ % Compute the indices $\mathrm{UCB}^j_k(t+1)$ and set $\TopM(t+1)$ for next step. % } % \label{algo:RandTopM} % \end{algorithm} % \end{figure} % \end{minipage}}} % \end{frame} \subsection{\hfill{}5.b. \MCTopM{} algorithm\hfill{}} \begin{frame}{Ideas for the \MCTopM{} algorithm} \begin{itemize}\tightlist \item Based on sensing information, each user \(j\) keeps \(\mathrm{UCB}_k^j(t)\) for each arm \(k\), \item Use it to estimate the \(M\) best arms: \[\TopM(t) = \{\text{arms with } M \text{ largest } \mathrm{UCB}_k^j(t)\}.\] \end{itemize} Two ideas: \begin{itemize}\tightlist \item Always pick an arm \(A^j(t) \in \TopM(t)\), \citationright{Ref: [Anandkumar et al, 2011]} \item Try not to switch arm too often. \end{itemize} Introduce a \textbf{fixed state} \(s^j(t)\): \citationright{Ref: [Shamir et al, 2016]} \newline first non fixed, then fix when happy about an arm and no collision. \end{frame} \begin{frame}[plain]{\MCTopM{} algorithm} \centerline{\scalebox{0.78}{\begin{minipage}{1.25\textwidth} %% https://tex.stackexchange.com/a/366403/ \begin{figure}[h!] \centering % Documentation at http://mirror.ctan.org/tex-archive/macros/latex/contrib/algorithm2e/doc/algorithm2e.pdf if needed % Or https://en.wikibooks.org/wiki/LaTeX/Algorithms#Typesetting_using_the_algorithm2e_package % \removelatexerror% Nullify \@latex@error % Cf. http://tex.stackexchange.com/a/82272/ \begin{algorithm}[H] % XXX Input, data and output % \KwIn{$K$ and policy $P^j$ for arms set $\{1,\dots,K\}$\;} % \KwData{Data} % \KwResult{Result} % XXX Algorithm Let $A^j(1) \sim \mathcal{U}(\{1,\dots,K\})$ and $C^j(1)=\mathrm{False}$ and $s^j(1)=\mathrm{Non}\;\mathrm{fixed}$ \\ \For{$t = 1, \dots, T-1$}{ \uIf(\tcp*[f]{\textcolor{red}{transition $\bold{(3)}$ or $\bold{(5)}$}}){ $A^j(t) \notin \TopM(t)$} { $A^j(t+1) \sim \mathcal{U} \left(\TopM(t) \cap \left\{k : \mathrm{UCB}_k^j(t-1) \leq \mathrm{UCB}^j_{A^j(t)}(t-1)\right\}\right)$ \tcp*[f]{not empty} \\ \alert{$s^j(t+1) = \mathrm{Non}\;\mathrm{fixed}$} \tcp*[f]{go for arm with smaller index at $t-1$} \pause } \uElseIf(\tcp*[f]{collision and not fixed}){ $C^j(t)$ \emph{and} $s^j(t) = \mathrm{Non}\;\mathrm{fixed}$ % $\overline{s^j(t)}$ } { $A^j(t+1) \sim \mathcal{U} \left(\TopM(t)\right)$ \tcp*[f]{\textcolor{blue}{transition $\bold{(2)}$}} \\ \alert{$s^j(t+1) = \mathrm{Non}\;\mathrm{fixed}$} \pause } \Else(\tcp*[f]{transition \textcolor{cyan}{$\bold{(1)}$} or \textcolor{darkgreen}{$\bold{(4)}$}}){ $A^j(t+1) = A^j(t)$ \tcp*[f]{stay on the previous arm} \\ \alert{$s^j(t+1) = \mathrm{Fixed}$} \tcp*[f]{become or stay fixed on a ``chair''} } \pause Play arm $A^j(t+1)$, get new observations (sensing and collision), \\ Compute the indices $\mathrm{UCB}^j_k(t+1)$ and set $\TopM(t+1)$ for next step. } \label{algo:MCTopM} \end{algorithm} \end{figure} \end{minipage}}} \end{frame} \begin{frame}{\MCTopM{} algorithm illustrated, step by step} \begin{figure}[h!] \scalebox{0.65}{\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{s^j(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^j(t), A^j(t) \in \TopM(t)$} (1); \pause \path [color=red,very thick,->] (notfixed) edge[loop below] node[below,text centered,black] {\small \textcolor{red}{$\bold{(3)}$} $A^j(t) \notin \TopM(t)$} (1); \pause \node (fixed) at (0,0) [draw,rectangle,very thick] {Fixed, $s^j(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^j(t)}, A^j(t) \in \TopM(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^j(t) \in \TopM(t)$} (fixed); \pause \draw [color=red,very thick,->] (fixed) to[bend right] node[midway,below,text centered,black] {\small \textcolor{red}{$\bold{(5)}$} $A^j(t) \notin \TopM(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^j(t+1)$ using information of previous steps.} \label{fig:StateMachineAlgorithm_MCTopM} \end{figure} \end{frame} \section{\hfill{}6. Regret upper bound\hfill{}} \begin{frame}{Regret upper bound} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item Theorem,\vspace*{15pt} \item Remarks.\vspace*{15pt} % \item % Idea of the proof. \end{enumerate} \end{frame} \subsection{\hfill{}6.a. Theorem for \MCTopM{} with \klUCB\hfill{}} \begin{frame}{Regret upper bound for \MCTopM{}} \begin{block}{Theorem $3$ \hfill{}\textcolor{gray}{[Besson \& Kaufmann, 2018]}} One term is controlled by the two others: \begin{small}\begin{align*} \sum_{k \in \Mbest} & (\mu_k - \mu_M^*) \left(T - \E_{\mu}[T_k(T)]\right) \\ \leq &(\mu_1^* - \mu_M^*) \left( \textcolor<1>{red}{\sum_{k \in \Mworst} \E_{\mu}[T_k(T)]} + \textcolor<1>{blue}{\sum_{k \in \Mbest} \E_{\mu}[C_k(T)]} \right) \end{align*}\end{small} \only<1>{So only need to work on both \textcolor<1>{red}{sub-optimal selections} and \textcolor<1>{blue}{collisions}.} \end{block} \pause \begin{block}{Theorem $4$ (finite time logarithmic regret) \hfill{}\textcolor{gray}{[Besson \& Kaufmann, 2018]}} If all \(M\) players use \MCTopM{} with \klUCB: \[ \forall \boldsymbol{\mu}, \exists G_{M,\boldsymbol{\mu}},\;\;\;\; \alert{R_T(\boldsymbol{\mu}, M, \rho) \leq G_{M,\boldsymbol{\mu}} \times \log(T) + \smallO{\log T}}. \] \end{block} \end{frame} \begin{frame}{Regret upper bound for \MCTopM{}} \begin{block}{How?} Control both terms, both are logarithmic at finite horizon: \begin{itemize}\tightlist \item Suboptimal selections with the ``classical analysis'' on \klUCB{} indexes. \item Collisions are also controlled with inequalities on the \klUCB{} indexes\ldots{} \end{itemize} \end{block} \pause \begin{block}{Remarks} \begin{itemize}\tightlist \item The constant \(G_{M,\boldsymbol{\mu}}\) scales as \(M^3\), way better than \rhoRand's constant scaling as \(M^2 {2M-1 \choose M}\), \item We also \emph{minimize the number of channel switching}: interesting as changing arm costs energy in radio systems, \item For the suboptimal selections, we \emph{match our lower bound} ! \end{itemize} \end{block} \end{frame}\section{\hfill{}A. Regret upper bound (more details)\hfill{}} \subsection{\hfill{}A.b. Sketch of the proof of the upper bound\hfill{}} \begin{frame}{Sketch of the proof} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \item Bound the expected number of collisions by \(M\) times the number of collisions for non-fixed players,\pause \item Bound the expected number of \textcolor<2>{red}{transitions of type $(3)$ and $(5)$}, by \(\bigO{\log T}\) using the \klUCB{} indexes and the forced choice of the algorithm: \(\mathrm{UCB}_k^j(t-1) \leq \mathrm{UCB}^j_{k'}(t-1), \;\;\text{and}\;\; \mathrm{UCB}_k^j(t) > \mathrm{UCB}^j_{k'}(t)\) when switching from \(k'\) to \(k\),\pause \item Bound the expected length of a sequence in the non-fixed state by a constant,\pause \item So most of the times (\(\bigO{T - \log T}\)), players are fixed, and no collision happens when they are all fixed! \end{enumerate} \begin{quote} \strut \hfill\(\hookrightarrow\) See our paper for details! \end{quote} \end{frame} \subsection{\hfill{}A.b. Illustration of the proof of the upper bound\hfill{}} \begin{frame}{Illustration of the proof} \begin{figure}[h!] \scalebox{0.65}{\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$}; \node (notfixed) at (1,0) [draw,rectangle,thick] {Not fixed, $\overline{s^j(t)}$}; \node (fixed) at (0,0) [draw,rectangle,thick] {Fixed, $s^j(t)$}; % \draw [color=black,very thick,->] (start) -> (notfixed.20); \draw [color=cyan,very thick,->] (notfixed) to[bend right] node[midway,above,text width=5cm,text centered,black] {\small $(1)$ $\overline{C^j(t)}, A^j(t) \in \TopM(t)$} (fixed); \path [color=blue,very thick,->] (notfixed) edge[loop right] node[right,text width=4cm,text badly centered,black] {\small $(2)$ $C^j(t), A^j(t) \in \TopM(t)$} (1); \path [color=red,very thick,->] (notfixed) edge[loop below] node[below,text centered,black] {\small $(3)$ $A^j(t) \notin \TopM(t)$} (1); \path [color=darkgreen,very thick,->] (fixed) edge[loop left] node[left,text width=2.9cm,text badly centered,black] {\small $(4)$ $A^j(t) \in \TopM(t)$} (fixed); \draw [color=red,very thick,->] (fixed) to[bend right] node[midway,below,text centered,black] {\small $(5)$ $A^j(t) \notin \TopM(t)$} (notfixed); % \end{tikzpicture} \end{minipage}} \label{fig:StateMachineAlgorithm_MCTopM} \end{figure} \begin{small} -- Time in fixed state is $\bigO{\log T}$, and collisions are $\leq M$ collisions in fixed state $\implies \bigO{\log T}$ collisions.\newline -- Suboptimal selections is $\bigO{\log T}$ also as $A^j(t+1)$ is always selected in $\TopM(t)$ which is $\Mbest$ at least $\bigO{T - \log T}$ (in average). \end{small} \end{frame} \section{\hfill{}7. Experimental results\hfill{}} \begin{frame}{Experimental results} \begin{quote} Experiments on Bernoulli problems \(\boldsymbol{\mu}\in[0,1]^K\). \end{quote} % \begin{enumerate} % \def\labelenumi{\arabic{enumi}.} % \tightlist % \item % Lower bound on the regret,\vspace*{15pt} % \item % Illustration of the regret for a single problem and % \(M = K\),\vspace*{15pt} % \item % Regret for uniformly sampled problems and \(M < K\),\vspace*{15pt} % \item % Logarithmic number of collisions,\vspace*{15pt} % \item % Logarithmic number of arm switches,\vspace*{15pt} % % \item % % Fairness? % \end{enumerate} \end{frame} \subsection{\hfill{}7.a. Illustration of the lower bound\hfill{}} \begin{frame}[plain]{Illustration of the regret lower bound} \begin{figure}[h!] \includegraphics[height=0.78\textheight]{figures/main_RegretCentralized____env3-4_2092905764868974160.pdf} \caption{\footnotesize{Any such lower bound is \alert{very asymptotic}, usually not satisfied for small horizons. We can see the importance of the collisions!}} \end{figure} \end{frame} \subsection{\hfill{}7.b. Illustration of the regret\hfill{}} \begin{frame}[plain]{Constant regret if \(M=K\)} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{figures/MP__K9_M9_T10000_N200__4_algos/all_RegretCentralized____env1-1_2306423191427933958.pdf} \caption{\footnotesize{Regret, $M=9$ players, $K=9$ arms, horizon $T=10000$, $200$ repetitions. Only \textcolor{red}{\RandTopM{}} and \textcolor{yellowgreen}{\MCTopM{}} achieve constant regret in this saturated case (proved).}} \end{figure} \end{frame} \begin{frame}[plain]{Illustration of the regret of different algorithms} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{figures/MP__K9_M6_T5000_N500__4_algos/all_RegretCentralized____env1-1_8318947830261751207.pdf} \caption{\footnotesize{Regret, $M=6$ players, $K=9$ arms, horizon $T=5000$, against $500$ problems $\boldsymbol{\mu}$ uniformly sampled in $[0,1]^K$. Conclusion : \textcolor{blue}{\rhoRand{}} < \textcolor{red}{\RandTopM{}} < \textcolor{bluegreen}{\Selfish{}} < \textcolor{yellowgreen}{\MCTopM{}} in most cases.}} \end{figure} \end{frame} \subsection{\hfill{}7.c. Number of collisions\hfill{}} \begin{frame}[plain]{Logarithmic number of collisions} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{figures/MP__K9_M6_T5000_N500__4_algos/all_CumNbCollisions____env1-1_8318947830261751207.pdf} \caption{\footnotesize{Cumulated number of collisions. Also \textcolor{blue}{\rhoRand{}} < \textcolor{red}{\RandTopM{}} < \textcolor{bluegreen}{\Selfish{}} < \textcolor{yellowgreen}{\MCTopM{}}.}} \end{figure} \end{frame} \subsection{\hfill{}7.d. Number of arm switches\hfill{}} \begin{frame}[plain]{Logarithmic number of arm switches} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{figures/MP__K9_M6_T5000_N500__4_algos/all_CumNbSwitchs____env1-1_8318947830261751207.pdf} \caption{\footnotesize{Cumulated number of arm switches. Again \textcolor{blue}{\rhoRand{}} < \textcolor{red}{\RandTopM{}} < \textcolor{bluegreen}{\Selfish{}} < \textcolor{yellowgreen}{\MCTopM{}}, but no guarantee for \textcolor{blue}{\rhoRand{}}. \emph{Bonus} result: logarithmic arm switches for our algorithms!}} \end{figure} \end{frame} \subsection{\hfill{}7.e. Fairness\hfill{}} \begin{frame}[plain]{Fairness} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{figures/MP__K9_M6_T5000_N500__4_algos/all_FairnessSTD____env1-1_8318947830261751207.pdf} \caption{\footnotesize{Measure of fairness among player. All $4$ algorithms seem fair \textbf{in average}, but none is fair on a single run. \textbf{It's quite hard to achieve both efficiency and single-run fairness!}}} \end{figure} \end{frame} \subsection{\hfill{}7.f. Comparison with \SICMMAB{} and other approaches\hfill{}} \begin{frame}{A larger benchmark} Now I also want to compare more approaches. \begin{itemize}\tightlist \item \rhoRand, with \UCB{} or \klUCB{}, \item \RandTopM, with \UCB{} or \klUCB{}, \item \MCTopM, with \UCB{} or \klUCB{}, \item \Selfish, with \UCB{} or \klUCB{}, \item a centralized agent (\alert{not playing the same game, not fair to compare against it}), with \UCB{} or \klUCB{}, \item three hand-tuned Musical-Chair algorithms, \item three variants of the \SICMMAB{} algorithm (from \textcolor{blue}{\href{https://arxiv.org/abs/1809.08151}{arXiv:1809.08151}}), with \UCB, \klUCB{} and their proposal with \UCBH. \end{itemize} \end{frame} \begin{frame}[plain]{Comparison with other approaches (1/3)} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{figures/MP__K9_M6_T50000_N40__16_algos/all_RegretCentralized_loglog____env1-1_6747959631471381163.pdf} \caption{\footnotesize{For $M=6$ objects, \MCTopM{} and \RandTopM{} largely outperform \SICMMAB{} and \rhoRand.}} \end{figure} \end{frame} \begin{frame}[plain]{Comparison with other approaches (2/3)} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{figures/MP__K9_M8_T50000_N40__16_algos/all_RegretCentralized_loglog____env1-1_2473883029686742467.pdf} \caption{\footnotesize{For $M=8$ objects, \MCTopM{} still outperforms \SICMMAB{} for short term regret, but the constant in front of the $\log(T)$ term seems smaller for \SICMMAB.}} \end{figure} \end{frame} \begin{frame}[plain]{Comparison with other approaches (3/3)} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{figures/MP__K9_M9_T50000_N40__16_algos/all_RegretCentralized_loglog____env1-1_4780366798347909369.pdf} \caption{\footnotesize{For $M=9$ objects, \MCTopM{} and \RandTopM{} largely outperform all approaches, they have finite regret when the other don't. For our algorithm, $M=K$ is the easiest case: just orthogonalize and it's done!}} \end{figure} \end{frame} \begin{frame}{Short summary of these benchmarks} In such experiments, and many more not showed here, I did the following observations: \begin{itemize}\tightlist \item For any algorithm, the \klUCB{} variant is uniformly better than the \UCB{} and \UCBH variant (obviously), \item Any decentralized approach is less efficient than the ``cheating'' centralized multiple-play approach, \item And for a fixed index policy, the following ordering on decentralized approaches can be observed (smaller means smaller regret, so a better algorithm): \begin{center} \MCTopM{} < \RandTopM{} < \SICMMAB{} < \Selfish{} < \rhoRand. \end{center} \end{itemize} \end{frame} \section{\hfill{}8. Conclusion\hfill{}} \subsection{\hfill{}8. Other recent related works\hfill{}} \begin{frame}{Other recent related works (1/2)} \begin{itemize}\tightlist \item Another recent article studied a similar problem. \only<1>{ \vspace*{10pt} \begin{figure}[h!] \centering \includegraphics[height=0.65\textheight]{figures/1808_04875_front_page.png} % \caption{\footnotesize{Front page of their article.}} \end{figure} } \pause \item Implementing their algorithms should be easy, but their model is quite different: \begin{itemize}\tightlist \item Objects can choose to \emph{not} communicate, it is denoted by choosing arm $0$ and not $k$ in $\{1,\dots,K\}$, \item \danger{} But more importantly, objects can send some bits of data directly to each other... \item So it's a little bit more complicated than my (simple) model. \end{itemize} \pause \item $\implies$ I will\footnote{\tiny I will try to code their model in my framework, see \href{https://github.com/SMPyBandits/SMPyBandits/issues/139}{\texttt{GitHub.com/SMPyBandits/SMPyBandits/issues/139}}} work on this more in the near future! \end{itemize} \vfill{} \begin{footnotesize} ``\emph{Multi-user Communication Networks: A Coordinated Multi-armed Bandit Approach}'', by Orly Avner \& Shie Mannor, \textcolor{blue}{\href{https://arxiv.org/abs/1808.04875}{arXiv:1808.04875}} \end{footnotesize} \end{frame} \begin{frame}{Other recent related works (2/2)} \begin{itemize}\tightlist \item And another recent article also studied a similar problem. \only<1>{ \vspace*{10pt} \begin{figure}[h!] \centering \includegraphics[height=0.65\textheight]{figures/1808_08416_front_page.png} % \caption{\footnotesize{Front page of their article.}} \end{figure} } \pause \item A very strong work from a theoretical point of view, but completely impractical even for simulations. \only<2,3>{ \item Their analysis says that their algorithm can be efficient only after at least $T_{1,2}$ \href{https://smpybandits.readthedocs.io/en/latest/docs/Policies.MusicalChairNoSensing.html?highlight=musicalchairnosensing\#Policies.MusicalChairNoSensing.estimate\_length\_phases\_12}{steps of uniform exploration} (\ie, linear regret). \pause \item On very easy problems with minimal gap between arms of $\Delta_{\min} = 0.1$ (rewards in $[0,1]$), and very small horizons, small $M$ and $K$, $T_{1,2}$ is computed as: \begin{itemize} \item For $M = 2$ and $K = 2$, and $T = 100$, $T_{1,2} = 198214307$, % \item For $M = 2$ and $K = 2$, and $T = 100$, and $\Delta_{\min} = 0.01$ $T_{1,2} = 19821430723$, \item For $M = 2$ and $K = 2$, and $T = 1000$, $T_{1,2} = 271897030$, \item For $M = 2$ and $K = 3$, and $T = 100$, $T_{1,2} = 307052623$, \item For $M = 2$ and $K = 5$, and $T = 100$, $T_{1,2} = 532187397$. \end{itemize} \item \danger{} That's just unreasonable! } \pause \item After discussing with the author, I tried using a much smaller value for their constant $g$ ($1$ instead of $128$), and their algorithm is still very much asymptotic in practice, even on very simple problems! \pause \item $\implies$ I will\footnote{\tiny I already added their first algorithm in my framework, see \href{https://github.com/SMPyBandits/SMPyBandits/issues/141}{\texttt{GitHub.com/SMPyBandits/SMPyBandits/issues/141}}} work on this more in the near future! \end{itemize} \vfill{} \begin{footnotesize} ``\emph{Multiplayer Bandits Without Observing Collision Information}'', by Gabor Lugosi \& Abbas Mehrabian, \textcolor{blue}{\href{https://arxiv.org/abs/1808.08416}{arXiv:1808.08416}} \end{footnotesize} \end{frame} \subsection{\hfill{}8.a. Conclusion\hfill{}} \begin{frame}{Sum up} \begin{itemize}\tightlist \item In a wireless network with an \iid{} background traffic in \(K\) channels, \item \(M\) devices can use both sensing and acknowledgement feedback, to learn the most free channels and to find orthogonal configurations. \end{itemize} \pause \begin{block}{We showed} \begin{itemize}\tightlist \item Decentralized bandit algorithms can solve this problem, \item We have a lower bound for any decentralized algorithm, \item And we proposed an order-optimal algorithm, based on \klUCB{} and an improved Musical Chair scheme, \MCTopM. \end{itemize} \end{block} \end{frame} \subsection{\hfill{}8.b. Future works\hfill{}} \begin{frame}{Future works} \begin{itemize}\tightlist \item Implement and test this on \textbf{real-world radio devices}? \hook Yes!\\ Demo presented at the ICT \(2018\) conference! (Saint-Malo, France) \vspace*{15pt} \pause \item Remove hypothesis that objects know \(M\)? (easy) \item Allow arrival/departure of objects? (harder) \item Non-stationarity of background traffic? (much harder) \vspace*{15pt} \pause \item Extend to more objects (\ie, when \(M > K\)) ? ``Large-scale'' IoT model, with (\eg, ZigBee networks), or without sensing (\eg, LoRaWAN networks). \hook objects should no longer communicate at every time step! \vspace*{15pt} \pause \item Maybe study \textbf{other emission models}? \end{itemize} \end{frame} \subsection{\hfill{}8.c. Thanks!\hfill{}} \begin{frame}{Thanks!} \begin{center}\begin{Huge} {\Fontify Thanks !} \Smiley[0.9] \end{Huge}\end{center} \vspace*{20pt} \begin{center}\begin{Huge} {\Fontify Any question ?} \end{Huge}\end{center} \end{frame} % ---------------------------------------------------------------------------- \appendix{} \section{\hfill{}Appendix\hfill{}} \begin{frame}{Appendix} \begin{itemize}\tightlist \item An heuristic for the ``IoT'' case (no sensing): the \Selfish{} algorithm, \item Success and failures case for \Selfish{}. \end{itemize} \end{frame} \section{\hfill{}B. An heuristic, \Selfish\hfill{}} \begin{frame}{An heuristic, \Selfish} For the harder feedback model, without sensing. \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item An heuristic,\vspace*{15pt} \item Problems with \Selfish,\vspace*{15pt} \item Illustration of failure cases. \end{enumerate} \end{frame} \subsection{\hfill{}B.a. Problems with \Selfish\hfill{}} \begin{frame}[allowframebreaks]{\Selfish{} heuristic} \Selfish{} decentralized approach = device don't use sensing: \begin{block}{\Selfish} Use \UCB{} (or \klUCB) indexes on the (non \iid) rewards \(r^j(t)\) and not on the sensing $Y_{A^j(t)}(t)$. \citationright{Ref: [Bonnefoi \& Besson et al, 2017]} \end{block} \begin{block}{Works fine\ldots{}} \begin{itemize}\tightlist \item More suited to model IoT networks, \item Use less information, and don't know the value of \(M\): we expect \Selfish{} to not have stronger guarantees. \item It works fine in practice! \end{itemize} \end{block} \begin{block}{\emph{But why would it work?}} \begin{itemize}\tightlist \item Sensing feedback were \iid, so using \UCB{} to learn the \(\mu_k\) makes sense, \item But collisions make the rewards not \iid{} ! \item Adversarial algorithms should be more appropriate here, \item But empirically, \Selfish{} works much better with \klUCB{} than, \eg, \ExpThree\ldots{} \end{itemize} \end{block} \begin{block}{Works fine\ldots{}} \begin{itemize}\tightlist \item Except\ldots{} when it fails drastically! \Sadey[1.3] \item In small problems with \(M\) and \(K = 2\) or \(3\), we found small probability of failures (\ie, linear regret), and this prevents from having a generic upper bound on the regret for \Selfish. \end{itemize} \end{block} \end{frame} \subsection{\hfill{}B.b. Failing cases for \Selfish\hfill{}} \begin{frame}[plain]{Illustration of failing cases for \(\mathrm{Selfish}\)} \begin{figure}[h!] \includegraphics[height=0.70\textheight]{figures/MP__K3_M2_T5000_N1000__4_algos/all_HistogramsRegret____env1-1_5016720151160452442.pdf} \caption{\footnotesize{Regret for $M=2$, $K=3$, $T=5000$, $1000$ repetitions and $\boldsymbol{\mu} = [0.1, 0.5, 0.9]$. Axis $x$ is for regret (different scale for each), and \textcolor{bluegreen}{\Selfish{}} have a small probability of failure ($17/1000$ cases of $R_T \gg \log T$). The regret for the three other algorithms is very small for this ``easy'' problem.}} \end{figure} \end{frame} \end{document}