\documentclass[12pt,english,ignorenonframetext,aspectratio=169,]{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} \definecolor{bleu}{RGB}{0,0,204} % rgb(0,0,204) \definecolor{violet}{RGB}{102,0,204} % rgb(102,0,204) \definecolor{darkgreen}{RGB}{0,100,0} % rgb(0,100,0) \definecolor{gold}{RGB}{255,184,0} % rgb(255,184,0) \definecolor{rouge}{RGB}{204,0,0} % rgb(204,0,0) \usepackage{amssymb,amsmath} \usepackage{bbm,bm} % bold maths symbols \usepackage{ifxetex,ifluatex} \usepackage{fixltx2e} % provides \textsubscript \usepackage{macrosText} % FIXME remove \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={MAB Learning in IoT Networks}, pdfauthor={ Christophe Moy Émilie Kaufmann}, 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 ? % 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/2559/ \newcommand{\backupbegin}{ \newcounter{framenumberappendix} \setcounter{framenumberappendix}{\value{framenumber}} } \newcommand{\backupend}{ \addtocounter{framenumberappendix}{-\value{framenumber}} \addtocounter{framenumber}{\value{framenumberappendix}} } \title{MAB Learning in IoT Networks} \subtitle{Decentralized Multi-Player Multi-Arm Bandits} \author[Lilian Besson]{\textbf{Lilian Besson} \newline \emph{Advised by} \and Christophe Moy \and Émilie Kaufmann} \institute[CentraleSupélec \& Inria]{PhD Student \newline Team SCEE, IETR, CentraleSupélec, Rennes \newline \& Team SequeL, CRIStAL, Inria, Lille} \date[SCEE Seminar - 23/11/17]{SCEE Seminar - 23 November 2017} % 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.13\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{}} \end{frame} \begin{frame}{Motivation: \emph{Internet of Things} problem} A \emph{lot} of IoT devices want to access to a single base station. \begin{itemize} \tightlist \item Insert them in a possibly \textbf{crowded wireless network}. \item With a protocol \textbf{slotted in both time and frequency}. \item Each device has a \textbf{low duty cycle} (a few messages per day). \end{itemize} \pause \begin{block}{Goal} \begin{itemize} \tightlist \item Maintain a \textbf{good Quality of Service}. \item \textbf{Without} centralized supervision! \end{itemize} \pause \end{block} \begin{block}{How?} \begin{itemize} \tightlist \item Use \textbf{learning algorithms}: devices will learn frequencies they should talk on! \end{itemize} \end{block} \end{frame} \subsection{\hfill{}1.b. Outline and references\hfill{}} \end{frame} \begin{frame}{Outline and references} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item Introduction and motivation \item Model and hypotheses \item Baseline algorithms : to compare against naive and efficient centralized approaches \item Two Multi-Armed Bandit algorithms : UCB, TS \item Experimental results \item An easier model with theoretical results \item Perspectives and future works \end{enumerate} \vfill{} \begin{footnotesize} Main references are my recent articles (on HAL): \begin{itemize} \item \emph{Multi-Armed Bandit Learning in IoT Networks and non-stationary settings}, Bonnefoi, Besson, Moy, Kaufmann, Palicot. CrownCom 2017, \item \emph{Multi-Player Bandits Models Revisited}, Besson, Kaufmann. arXiv:1711.02317, \end{itemize} \end{footnotesize} \end{frame} \section{\hfill{}2. Model and hypotheses\hfill{}} \subsection{\hfill{}2.a. First model\hfill{}} \end{frame} \begin{frame}{First model} \begin{itemize} \tightlist \item Discrete time \(t\geq1\) and \(K\) radio channels (\emph{e.g.}, 10) \hfill{} (\emph{known}) \end{itemize} \begin{figure}[h!] \centering \includegraphics[height=0.35\textheight]{crowncom/protocol.eps} \caption{\small{Protocol in time and frequency, with an \textcolor{darkgreen}{\emph{Acknowledgement}}.}} \end{figure} \begin{itemize} \tightlist \item \(D\) \textbf{dynamic} devices try to access the network \emph{independently} \item \(S=S_1+\dots+S_{K}\) \textbf{static} devices occupy the network : \newline \(S_1,\dots,S_{K}\) in each channel \hfill{} (\emph{unknown}) \end{itemize} \end{frame} \subsection{\hfill{}2.b. Hypotheses\hfill{}} \end{frame} \begin{frame}[fragile,allowframebreaks]{Hypotheses} \begin{block}{Emission model} \begin{itemize} \tightlist \item Each device has the same \emph{low} emission probability: \newline each step, each device sends a packet with probability \(p\). \newline \hfill{}\small{(this gives a duty cycle proportional to $1/p$)} \end{itemize} \end{block} \begin{block}{Background traffic} \begin{itemize} \tightlist \item Each static device uses only one channel. \item Their repartition is fixed in time. \end{itemize} \begin{quote} \(\implies\) Background traffic, bothering the dynamic devices! \end{quote} \end{block} \begin{block}{Dynamic radio reconfiguration} \begin{itemize} \tightlist \item Each \textbf{dynamic device decides the channel it uses to send every packet}. \item It has memory and computational capacity to implement simple \textbf{decision algorithm}. \end{itemize} \end{block} \begin{block}{Problem} \begin{itemize} \tightlist \item \emph{Goal} : \emph{minimize packet loss ratio} (\(=\) maximize number of received \texttt{Ack}) in a \emph{finite-space discrete-time Decision Making Problem}. \item \emph{Solution ?} \textbf{Multi-Armed Bandit algorithms}, \textbf{decentralized} and used \textbf{independently} by each device. \end{itemize} \end{block} \end{frame} \section{\hfill{}3. Baseline algorithms\hfill{}} \subsection{\hfill{}3.a. A naive strategy : uniformly random access\hfill{}} \end{frame} \begin{frame}{A naive strategy : uniformly random access} \begin{itemize} \item \textbf{Uniformly random access}: dynamic devices choose uniformly their channel in the pull of \(K\) channels. \item Natural strategy, dead simple to implement. \item Simple analysis, in term of \textbf{successful transmission probability} (for every message from dynamic devices) : \end{itemize} \vspace*{-10pt} \begin{small} \begin{align*} \mathbb{P}(\text{success}|\text{sent}) = \sum_{i=1}^{K} \underbrace{(1 - p / K)^{D-1}}_{\text{No other dynamic device}} \times \underbrace{(1-p)^{S_i}}_{\text{No static device}} \times\; \frac{1}{K}. \end{align*} \end{small} \pause \begin{block}{No learning} \begin{itemize} \tightlist \item Works fine only if all channels are similarly occupied,\newline but \textbf{it cannot learn} to exploit the best (more free) channels. \end{itemize} \end{block} \end{frame} \subsection{\hfill{}3.b. Optimal centralized strategy\hfill{}} \end{frame} \begin{frame}[allowframebreaks]{Optimal centralized strategy} \begin{itemize} \tightlist \item If an oracle can decide to affect \(D_i\) dynamic devices to channel \(i\), the \textbf{successful transmission probability} is: \vspace*{-10pt} \begin{small} \begin{align*} \mathbb{P}(\text{success}|\text{sent}) = \sum_{i=1}^{K} \underbrace{(1 - p)^{D_i - 1}}_{\;\;D_i - 1 \;\text{others}\;\;} \times \underbrace{(1 - p)^{S_i}}_{\;\;\text{No static device}\;\;} \times \underbrace{ D_i / D }_{\;\;\text{Sent in channel}\; i}. \end{align*} \end{small} \item The oracle has to solve this \textbf{optimization problem}: \vspace*{-5pt} \begin{small} \begin{equation*} \begin{cases} \underset{D_1,\dots,D_{K}}{\arg\max}\;\;\; & \sum_{i=1}^{K} D_i (1 - p)^{S_i + D_i -1}\\ \text{such that}\;\;\; & \sum_{i=1}^{K} D_i = D \; \text{and} \; D_i \geq 0, \; \; \forall 1 \leq i \leq K . \end{cases} \end{equation*} \end{small} \item We solved this quasi-convex optimization problem with \emph{Lagrange multipliers}, only numerically. \item \(\implies\) Very good performance, maximizing the transmission rate of all the \(D\) dynamic devices \end{itemize} \begin{block}{But unrealistic} But \textbf{not achievable in practice}: no centralized control and no oracle! \end{block} \begin{block}{Now let see \emph{realistic decentralized approaches}} \(\hookrightarrow\) Machine Learning ? \newline \hspace*{30pt}\(\hookrightarrow\) Reinforcement Learning ? \newline \hspace*{60pt} \(\hookrightarrow\) \emph{Multi-Armed Bandit} ! \end{block} \end{frame} \section{\hfill{}4. Two Multi-Armed Bandit algorithms : UCB, TS\hfill{}} \subsection{\hfill{}4.1. Multi-Armed Bandit formulation\hfill{}} \end{frame} \begin{frame}[fragile]{Multi-Armed Bandit formulation} A dynamic device tries to collect \emph{rewards} when transmitting : \begin{itemize} \tightlist \item it transmits following a Bernoulli process \newline (probability \(p\) of transmitting at each time step \(t\)), \item chooses a channel \(A(\tau) \in \{1,\dots,K\}\), \begin{itemize} \tightlist \item if \texttt{Ack} (no collision) \hspace*{10pt} \(\implies\) reward \(r_{A(\tau)} = 1\), \item if collision (no \texttt{Ack}) \hspace*{10pt} \(\implies\) reward \(r_{A(\tau)} = 0\). \end{itemize} \end{itemize} \begin{block}{Reinforcement Learning interpretation} Maximize transmission rate \(\equiv\) \textbf{maximize cumulated rewards} \[\max_{\text{algorithm}\;A} \;\; \sum_{\tau=1}^{\text{horizon}} r_{A(\tau)}.\] \end{block} \end{frame} \subsection{\hfill{}4.2. Upper Confidence Bound algorithm : UCB\hfill{}} \end{frame} \begin{frame}{Upper Confidence Bound algorithm (\(\mathrm{UCB}_1\))} Dynamic device keep \(\tau\) number of sent packets, \(T_k(\tau)\) selections of channel \(k\), \(X_k(\tau)\) successful transmission in channel \(k\). \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item For the first \(K\) steps (\(\tau=1,\dots,K\)), try each channel \emph{once}. \item Then for the next steps \(t > K\) : \begin{itemize} \tightlist \item Compute the index \(g_k(\tau) := \underbrace{\frac{X_k(\tau)}{T_k(\tau)}}_{\text{Mean}\; \widehat{\mu_k}(\tau)} + \underbrace{\sqrt{\frac{\log(\tau)}{2 T_k(\tau)}},}_{\text{Upper Confidence Bound}}\) \item Choose channel \(A(\tau) = \mathop{\arg\max}\limits_{k} \; g_k(\tau)\), \item Update \(T_k(\tau+1)\) and \(X_k(\tau+1)\). \end{itemize} \end{enumerate} \vfill{}\hfill{}\tiny{\textcolor{gray}{References: [Lai \& Robbins, 1985], [Auer et al, 2002], [Bubeck \& Cesa-Bianchi, 2012]}} \end{frame} \subsection{\hfill{}4.3. Thompson Sampling : Bayesian index policy\hfill{}} \end{frame} \begin{frame}[fragile]{Thompson Sampling : Bayesian approach} A dynamic device assumes a stochastic hypothesis on the background traffic, modeled as Bernoulli distributions. \begin{itemize} \item Rewards \(r_k(\tau)\) are assumed to be \emph{i.i.d.} samples from a Bernoulli distribution \(\mathrm{Bern}(\mu_k)\). \item A \textbf{binomial Bayesian posterior} is kept on the mean availability \(\mu_k\) : \(\mathrm{Bin}(1 + X_k(\tau), 1 + T_k(\tau) - X_k(\tau))\). \item Starts with a \emph{uniform prior} : \(\mathrm{Bin}(1, 1) \sim \mathcal{U}([0,1])\). \end{itemize} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item Each step \(\tau \geq 1\), draw a sample from each posterior \(i_k(\tau) \sim \mathrm{Bin}(a_k(\tau), b_k(\tau))\), \item Choose channel \(A(\tau) = \mathop{\arg\max}\limits_k \; i_k(\tau)\), \item Update the posterior after receiving \texttt{Ack} or if collision. \end{enumerate} \vfill{}\hfill{}\tiny{\textcolor{gray}{References: [Thompson, 1933], [Kaufmann et al, 2012]}} \end{frame} \section{\hfill{}5. Experimental results\hfill{}} \subsection{\hfill{}5.1. Experiment setting\hfill{}} \end{frame} \begin{frame}{Experimental setting} \begin{block}{Simulation parameters} \begin{itemize} \tightlist \item \(K = 10\) channels, \item \(S + D = 10000\) devices \textbf{in total}. Change proportion of dynamic \(D/(S+D)\), \item \(p = 10^{-3}\) probability of emission, for all devices, \item Horizon \(= 10^6\) time slots, \hfill{} (\(\simeq 1000\) messages \(/\) device) \item Various settings for \((S_1,\dots,S_{K})\) static devices repartition. \end{itemize} \end{block} \begin{block}{What do we show \hfill{} (for static \(S_i\))} \begin{itemize} \tightlist \item After a short learning time, MAB algorithms are almost as efficient as the oracle solution ! \item Never worse than the naive solution. \item Thompson sampling is more efficient than UCB. \item Stationary alg. outperform adversarial ones (UCB \(\gg\) Exp3). \end{itemize} \end{block} \end{frame} \subsection{\hfill{}5.2. First result: $10\%$\hfill{}} \end{frame} \begin{frame}{\(10\%\) of dynamic devices} \begin{figure}[h!] \centering \includegraphics[height=0.74\textheight]{crowncom/10intelligent.eps} \caption{\small{$10\%$ of dynamic devices. $7\%$ of gain.}} \end{figure} \end{frame} \subsection{\hfill{}5.2. First result: $20\%$\hfill{}} \end{frame} \begin{frame}{\(30\%\) of dynamic devices} \begin{figure}[h!] \centering \includegraphics[height=0.74\textheight]{crowncom/30intelligent.eps} \caption{\small{$30\%$ of dynamic devices. $3\%$ of gain but not much is possible.}} \end{figure} \end{frame} \subsection{\hfill{}5.3. Growing proportion of devices dynamic devices\hfill{}} \end{frame} \begin{frame}{Dependence on \(D/(S+D)\)} \begin{figure}[h!] \centering \includegraphics[height=0.65\textheight]{crowncom/perf_learning.eps} \caption{\small{\emph{Almost optimal}, for any proportion of dynamic devices, \emph{after a short learning time}. Up-to $16\%$ gain over the naive approach!}} \end{figure} \end{frame} \section{\hfill{}6. An easier model\hfill{}} \end{frame} \begin{frame}{Section 6} \begin{center} A brief presentation of a different approach... Theoretical results for an easier model \end{center} \end{frame} \subsection{\hfill{}6.1. Presentation of the model\hfill{}} \end{frame} \begin{frame}[fragile]{An easier model} \begin{block}{Easy case} \begin{itemize} \tightlist \item \(M \leq K\) dynamic devices \textbf{always communicating} (\(p=1\)). \item Still interesting: many mathematical and experimental results! \end{itemize} \pause \end{block} \begin{block}{Two variants} \begin{itemize} \item \emph{With sensing}: Device first senses for presence of Primary Users (background traffic), then use \texttt{Ack} to detect collisions. \small{Model the "classical" Opportunistic Spectrum Access problem. Not exactly suited for IoT networks like LoRa or SigFox, can model ZigBee, and can be analyzed mathematically...} \hfill{}{\small{\textcolor{gray}{(\emph{cf} Wassim's and Navik's theses, 2012, 2017)}}} \item \emph{Without sensing}: like our IoT model but smaller scale. Still very hard to analyze mathematically. \end{itemize} \end{block} \end{frame} \subsection{\hfill{}6.2. Notations\hfill{}} \end{frame} \begin{frame}[fragile]{Notations for this second model} \begin{block}{Notations} \begin{itemize} \tightlist \item \(K\) channels, modeled as Bernoulli (\(0/1\)) distributions of mean \(\mu_k\) \(=\) background traffic from \emph{Primary Users}, \item \(M\) devices use channel \(A^j(t) \in \{1,\dots,K\}\) at each time step, \item Reward: \(r^j(t) := Y_{A^j(t),t} \times \mathbbm{1}(\overline{C^j(t)}) = \mathbbm{1}(\)uplink \& \texttt{Ack}\()\) \begin{itemize} \tightlist \item with sensing information \(Y_{k,t} \sim \mathrm{Bern}(\mu_k)\), \item collision for device \(j\) \(C^j(t) = \mathbbm{1}(\)\emph{alone on arm $A^j(t)$}\()\). \end{itemize} \end{itemize} \pause \end{block} \begin{block}{Goal : \emph{decentralized} reinforcement learning optimization!} \begin{itemize} \tightlist \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{}6.2. Centralized regret\hfill{}} \end{frame} \begin{frame}{Centralized regret} \begin{block}{New measure of success} \begin{itemize} \tightlist \item Not the network throughput or collision probability, \item Now we study the \textbf{centralized regret} \vspace*{-5pt} \[ R_T(\boldsymbol{\mu}, M, \rho) := \left(\sum_{k=1}^{M}\mu_k^*\right) T - \E_{\mu}\left[\sum_{t=1}^T\sum_{j=1}^M r^j(t)\right]. \] \end{itemize} \pause \end{block} \begin{block}{Two directions of analysis} \begin{itemize} \tightlist \item Clearly \(R_T = \mathcal{O}(T)\), but we want a sub-linear regret \item \emph{What is the best possible performance of a decentralized algorithm in this setting?} \newline \hfill{} \(\hookrightarrow\) \textbf{Lower Bound} on regret for \textbf{any} algorithm ! \item \emph{Is this algorithm efficient in this setting?} \newline \hfill{} \(\hookrightarrow\) \textbf{Upper Bound} on regret for \textbf{one} algorithm ! \end{itemize} \end{block} \end{frame} \subsection{\hfill{}6.3. Lower Bound on regret\hfill{}} \end{frame} \begin{frame}[allowframebreaks]{Asymptotic Lower Bound on regret} \vspace*{-3pt} For any algorithm, decentralized or not, we have \vspace*{-5pt} \begin{small}\begin{align*} R_T(\boldsymbol{\mu}, M, \rho) &= \sum_{k \in \Mworst} (\mu_M^* - \mu_k) \E_{\mu}[T_k(T)] \\ &+ \sum_{k \in \Mbest} (\mu_k - \mu_M^*) (T - \E_{\mu}[T_k(T)]) + \sum_{k=1}^{K} \mu_k \E_{\mu}[\mathcal{C}_k(T)]. \end{align*}\end{small} \vspace*{-5pt} \begin{block}{Small regret can be attained if\ldots{}} \begin{enumerate} \def\labelenumi{\arabic{enumi}.} \tightlist \item Devices can quickly identify the bad arms \(\Mworst\), and not play them too much (\emph{number of sub-optimal selections}), \item Devices can quickly identify the best arms, and most surely play them (\emph{number of optimal non-selections}), \item Devices can use orthogonal channels (\emph{number of collisions}). \end{enumerate} \end{block} \vspace*{-5pt} \begin{block}{Lower-bounds} \begin{itemize} \tightlist \item The first term \(\E_{\mu}[T_k(T)]\), for sub-optimal arms, is lower-bounded, using technical information theory tools (Kullback-Leibler divergence, entropy), \item And we lower-bound collisions by\ldots{} \(0\) : hard to do better! \end{itemize} \end{block} \begin{block}{Theorem 1 \hfill{}\textcolor{gray}{[Besson \& Kaufmann, 2017]}} \begin{itemize} \tightlist \item 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 M \times \left( \sum_{k \in \Mworst} \frac{(\mu_M^* - \mu_k)}{\kl(\mu_k, \mu_M^*)} \right) . \] \footnotetext{\tiny Where $\kl(x,y) := x \log(\frac{x}{y}) + (1 - x) \log(\frac{1-x}{1-y})$ is the binary Kullback-Leibler divergence.} \end{itemize} \end{block} \end{frame} \begin{frame}[plain]{Illustration of the Lower Bound on regret} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{alt/figures/main_RegretCentralized____env3-4_2092905764868974160.pdf} \caption{\footnotesize{Any such lower-bound is very asymptotic, usually not satisfied for small horizons. We can see the importance of the collisions!}} \end{figure} \end{frame} \subsection{\hfill{}6.4. Algorithms\hfill{}} \end{frame} \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 \(C^j(t)\)). \end{enumerate} \pause \end{block} \begin{block}{Many different proposals for \emph{decentralized} learning policies} \begin{itemize} \tightlist \item Recent: \MEGA{} and \MusicalChair{}, \hfill{}{\tiny \textcolor{gray}{[Avner \& Mannor, 2015], [Shamir et al, 2016]}} \item State-of-the-art: \textbf{RhoRand policy} and variants, \hfill{}{\tiny \textcolor{gray}{[Anandkumar et al, 2011]}} \item \textbf{Our proposals}: \hfill{}{\tiny \textcolor{gray}{[Besson \& Kaufmann, 2017]}} \begin{itemize} \tightlist \item With sensing: \RandTopM{} and \MCTopM{} are sort of mixes between RhoRand and \MusicalChair{}, using UCB indexes or more efficient index policy (\klUCB), \item Without sensing: \Selfish{} use a UCB index directly on the reward \(r^j(t)\) : like the first IoT model ! \end{itemize} \end{itemize} \end{block} \end{frame} \begin{frame}[plain]{Illustration of different algorithms} \begin{figure}[h!] \centering \includegraphics[height=0.75\textheight]{alt/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$. \textcolor{blue}{\rhoRand{}} < \textcolor{red}{\RandTopM{}} < \textcolor{darkgreen}{\Selfish{}} < \textcolor{gold}{\MCTopM{}} in most cases.}} \end{figure} \end{frame} \subsection{\hfill{}6.5. Regret upper-bound\hfill{}} \end{frame} \begin{frame}{Regret upper-bound for \MCTopM-\klUCB} \begin{block}{Theorem 2 \hfill{}\textcolor{gray}{[Besson \& Kaufmann, 2017]}} \begin{itemize} \tightlist \item If all \(M\) players use \MCTopM-\klUCB, for any non-degenerated problem \(\boldsymbol{\mu}\), \[ R_T(\boldsymbol{\mu}, M, \rho) \leq G_{M,\boldsymbol{\mu}} \log(T) + \smallO{\log T}. \] \end{itemize} \end{block} \begin{block}{Remarks} \begin{itemize} \tightlist \item Hard to prove, we had to carefully design the \MCTopM{} algorithm to conclude, \item For the suboptimal selections, we \emph{match our lower-bound} ! \item We also \emph{minimize the number of channel switching}: interesting as it costs energy, \item Not yet possible to know what is the best possible control of collisions\ldots{} \end{itemize} \end{block} \end{frame} \subsection{\hfill{}6.6. Problems with \Selfish\hfill{}} \end{frame} \begin{frame}{In this model} The \Selfish{} decentralized approach = device don't use sensing, just learn on the receive acknowledgement, \begin{itemize} \tightlist \item Like our first IoT model, \item It works fine in practice! \item Except\ldots{} when it fails drastically! \item In small problems with \(M\) and \(K = 2\) or \(3\), we found small probability of failures (\emph{i.e.}, linear regret), and this prevents from having a generic upper-bound on regret for \Selfish. Sadly\ldots{} \end{itemize} \end{frame} \begin{frame}[plain]{Illustration of failing cases for \(\mathrm{Selfish}\)} \begin{figure}[h!] \centering \includegraphics[height=0.70\textheight]{alt/figures/MP__K3_M2_T5000_N1000__4_algos/all_HistogramsRegret____env1-1_5016720151160452442.pdf} \caption{\footnotesize{Histograms of regret for $M=2$ players, $K=3$ arms, horizon $T=5000$, $1000$ repetitions and $\boldsymbol{\mu} = [0.1, 0.5, 0.9]$ (different scales). \textcolor{darkgreen}{\Selfish{}} have a small probability of failure ($17$ cases of $R_T \geq T$, out of $1000$). The regret for the other algorithms is very small for such ``easy'' problem.}} \end{figure} \end{frame} \section{\hfill{}7. Perspectives and future work\hfill{}} \subsection{\hfill{}7.1. Perspectives\hfill{}} \end{frame} \begin{frame}{Perspectives} \begin{block}{Theoretical results} \begin{itemize} \tightlist \item MAB algorithms have guarantees for \emph{i.i.d. settings}, \item But here the collisions cancel the \emph{i.i.d.} hypothesis, \item Not easy to obtain guarantees in this mixed setting \newline (\emph{i.i.d.} emissions process, ``game theoretic'' collisions). \item For OSA devices (always emitting), we obtained strong theoretical results, \item But harder for IoT devices with low duty-cycle\ldots{} \end{itemize} \end{block} \begin{block}{Real-world experimental validation ?} \begin{itemize} \tightlist \item Radio experiments will help to validate this. \hspace*{40pt}\hfill{}\textcolor{red}{Hard !} \end{itemize} \end{block} \end{frame} \subsection{\hfill{}7.2. Future work\hfill{}} \end{frame} \begin{frame}{Other directions of future work} \begin{itemize} \item \emph{More realistic emission model}: maybe driven by number of packets in a whole day, instead of emission probability. \item Validate this on a \emph{larger experimental scale}. \item Extend the theoretical analysis to the large-scale IoT model, first with sensing (\emph{e.g.}, models ZigBee networks), then without sensing (\emph{e.g.}, LoRaWAN networks). \item And also conclude the Multi-Player OSA analysis (remove hypothesis that objects know \(M\), allow arrival/departure of objects, non-stationarity of background traffic etc) \end{itemize} \end{frame} \section{\hfill{}7. Conclusion\hfill{}}\subsection{\hfill{}7.3 Thanks!\hfill{}} \end{frame} \begin{frame}[allowframebreaks]{Conclusion} \begin{block}{We showed} \begin{itemize} \tightlist \item Simple Multi-Armed Bandit algorithms, used in a Selfish approach by IoT devices in a crowded network, help to quickly learn the best possible repartition of dynamic devices in a fully decentralized and automatic way, \item For devices with sensing, smarter algorithms can be designed, and analyze carefully. \item Empirically, even if the collisions break the \emph{i.i.d} hypothesis, stationary MAB algorithms (UCB, TS, \klUCB) outperform more generic algorithms (adversarial, like Exp3). \end{itemize} \end{block} \begin{block}{But more work is still needed\ldots{}} \begin{itemize} \tightlist \item \textbf{Theoretical guarantees} are still missing for the IoT model, and can be improved (slightly) for the OSA model. \item Maybe study \textbf{other emission models}. \item Implement this on \textbf{real-world radio devices} (\textcolor{rouge}{\emph{TestBed}}). \end{itemize} \end{block} \begin{block}{\textbf{Thanks!}} \begin{center}\begin{Large} \emph{Any question?} \end{Large}\end{center} \end{block} \end{frame} \end{document}