\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}