\begin{frameO}[We want]

    We control a \emph{lot} of IoT devices \includegraphics[height=0.37cm]{dynamic-devices.png}
    % want to access to \emph{one} gateway
    % (base station).

    \begin{itemize}
        % \tightlist
        \item
            We want to insert them in an already \textbf{crowded wireless network}
        \item
            Within a protocol \textbf{slotted in time and frequency}
        \item
            Each device \includegraphics[height=0.37cm]{dynamic-devices.png} / \includegraphics[height=0.37cm]{static-devices.png} has a \textbf{low duty cycle} \hfill{}
            \textcolor{gray}{ex: few messages per day}
    \end{itemize}

    \pause

    \only<1-2>{
        % \begin{figure}[!h]
        \centering
        \includegraphics[width=0.70\linewidth]{system_model1.eps}
        % \caption{In our system model, some dynamic devices (in the \textcolor{blue}{IoT network in blue}) transmit packets to a gateway and suffer from the interference generated by neighboring networks (in \textcolor{orange}{orange left/right}).}
        % \label{fig:41:system_model1}
        % \end{figure}
    }

    % \only<3>{
    %     % \pause

    %     \begin{colorblock}{Goal}
    %         \begin{itemize}
    %             % \tightlist
    %             \item Maintain a \textbf{good Quality of Service}.
    %             \item \textbf{Without} centralized supervision!
    %         \end{itemize}
    %     \end{colorblock}

    %     % \pause

    %     \begin{alertblock}{How?}
    %         \begin{itemize}
    %             % \tightlist
    %             \item Use \textbf{learning algorithms}\newline
    %             $\implies$ can devices learn on which frequency they should talk ?
    %         \end{itemize}
    %     \end{alertblock}
    % }

\end{frameO}



\subsection{Model and hypotheses}

\subsubsection{A new model for IoT networks}

\begin{frameO}[A new model for IoT networks]

    \begin{itemize}
        % \tightlist
        \item
              Discrete time \(t\in\mathbb{N}^*\) and \(K\) radio channels (\emph{e.g.}, 10)
              \hfill{} (\emph{known})
    \end{itemize}

    \begin{figure}[h!]
        \centering
        \includegraphics[height=0.35\textheight]{protocol.eps}\\
        
        {\small Chosen protocol: \textcolor{blue}{uplink messages {\large $\nearrow$}} followed by \textcolor{darkgreen}{\emph{acknowledgements} {\large $\searrow$}}}\\
        \hfill{} {\tiny \textcolor{gray}{[Bonnefoi, Besson et al, 17], Sec.5.2}}
    \end{figure}

    \begin{itemize}
        % \tightlist
        \item
              \(D\) \textbf{dynamic} devices \includegraphics[height=0.37cm]{dynamic-devices.png} trying to access the network \emph{independently}
        \item
              \(S=S_1+\dots+S_{K}\) \textbf{static} devices \includegraphics[height=0.37cm]{static-devices.png} occupying the network:
              \newline
              \(S_1,\dots,S_{K}\) in each channel \(\{1,\dots,K\}\) \hfill{} (\emph{unknown})
    \end{itemize}

\end{frameO}


\begin{frameO}[Protocol: decentralized access with Ack. mode]

    \begin{center}
        \only<1>{
            \includegraphics[width=0.98\textwidth]{Protocol_successful_transmission.png}
            \vfill{}
            \underline{$1^\text{st}$ case}: Successful transmission if no collision on \textcolor{blue}{uplink messages {\large $\nearrow$}} !
        }
        \only<2>{
            \includegraphics[width=0.97\textwidth]{Protocol_failed_transmission.png}
            \vfill{}
            \underline{$2^\text{nd}$ case}: Failed transmission if collision on \textcolor{blue}{uplink messages {\large $\nearrow$}}\dots
        }
    \end{center}

\end{frameO}


\subsubsection{Hypotheses}

\begin{frameO}[Our model of IoT devices \hfill{} {\small \textcolor{lightgray}{[Bonnefoi, Besson et al, 17]}}]

    \begin{darkblock}{Emission model for IoT devices with \emph{low duty cycle}}

        \begin{itemize}
            % \tightlist
            \item
                Each device \includegraphics[height=0.37cm]{dynamic-devices.png} / \includegraphics[height=0.37cm]{static-devices.png}  has the same \emph{low} emission probability: \\
                each step, each device sends a packet with probability \(p\)
                %   \\
                %   \hfill{}\small{(this gives a duty cycle proportional to $1/p$)}
        \end{itemize}

    \end{darkblock}

    \vspace*{5pt}
    \pause
    \begin{colorblock}{Background \textbf{stationary} ambiant traffic}

        \begin{itemize}
            % \tightlist
            \item
                  Each static device \includegraphics[height=0.37cm]{static-devices.png} uses only one channel
                  \hfill{} {\small ($S_k$ devices in channel $k$)}
            \item
                  Their repartition is fixed in time
                  % \hfill{} $\implies$ \alert{stationary} hypothesis!
        \end{itemize}

        \(\implies\) This surrounding traffic \emph{is disturbing} the dynamic devices \includegraphics[height=0.37cm]{dynamic-devices.png}
    \end{colorblock}

    \vspace*{5pt}
    \pause
    \begin{lightblock}{Dynamic radio reconfiguration}

        \begin{itemize}
            % \tightlist
            \item
                \textbf{Dynamic device} \includegraphics[height=0.37cm]{dynamic-devices.png}  \textbf{decide} the channel to use to send their packets
            \item
                They all have memory and computational capacity to implement small decision algorithms
                % on a small CPU embedded on the devices.
        \end{itemize}

    \end{lightblock}

\end{frameO}


\begin{frameO}[Problem]

    \begin{darkblock}{Goal}
        \begin{itemize}
            \item
            \emph{minimize packet loss ratio} (max \(=\) number of received \texttt{Ack})\\
            \item
            in a \emph{finite-space discrete-time Decision Making Problem}
        \end{itemize}
    \end{darkblock}

    \vspace*{20pt}

    \begin{colorblock}{Baseline (naive solution)}
        Purely random (uniform) spectrum access for the $D$ dynamic devices \includegraphics[height=0.37cm]{dynamic-devices.png} .
    \end{colorblock}

    \begin{lightblock}{A possible solution}
        Embed a \textbf{decentralized Multi-Armed Bandit} algorithm, running \textbf{independently on each dynamic device} \includegraphics[height=0.37cm]{dynamic-devices.png}.
    \end{lightblock}

\end{frameO}



\subsection{Baseline algorithms}

% \subsubsection{$1)$ A naive strategy: uniformly random access}

% \begin{frameO}[$1)$ A naive strategy: uniformly random access]

%     \begin{itemize}
%         % \tightlist
%         \item
%               \textbf{Uniformly random access}: dynamic devices choose uniformly
%               their channel in the pull of \(K\) channels.
%         \item
%               Natural strategy, dead simple to implement.
%     \end{itemize}

%     \pause

%     \begin{itemize}
%         % \tightlist
%         \item
%             Simple analysis, in term of \textbf{successful transmission
%             probability}\newline
%             (for every message from dynamic devices):
%     \end{itemize}

%     \begin{small} \begin{align*}
%             \mathbb{P}(\text{success}|\text{sent}) = \sum_{k=1}^{K} \underbrace{(1 - p / K)^{D-1}}_{\text{No other dynamic device}} \times \underbrace{(1-p)^{S_k}}_{\text{No static device}} \times\; \frac{1}{K}.
%         \end{align*} \end{small}

%     \pause

%     \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{frameO}



\subsubsection{$1)$ \emph{Oracle} centralized strategy}

\begin{frameO}[$1)$ \emph{Oracle} centralized strategy \hfill{} {\small \textcolor{lightgray}{[Bonnefoi, Besson et al, 17]}}]

    \begin{itemize}
        % \tightlist
        \item
              If an oracle can affect \(D_k\) dynamic devices \includegraphics[height=0.37cm]{dynamic-devices.png}  to channel
              \(k\) \slotmachine{}, the \textbf{successful transmission probability} of the entire network is
              \vspace*{-5pt}
              \begin{small} \begin{align*}
                      \mathbb{P}(\text{success}|\text{sent}) = \sum_{k=1}^{K} \underbrace{(1 - p)^{D_k - 1}}_{\;\;D_k - 1 \;\text{others}\;\;} \times \underbrace{(1 - p)^{S_k}}_{\;\;\text{No static device}\;\;} \times \underbrace{ D_k / D }_{\;\;\text{Sent in channel}\; k}
                  \end{align*} \end{small}
            %   \vspace*{-10pt}
              \pause
        \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\limits_{k=1}^{K} D_k (1 - p)^{S_k + D_k -1}                                           \\
                          \text{such that}\;\;\;                     & \sum\limits_{k=1}^{K} D_k = D \; \text{and} \; D_k \geq 0, \; \; \forall 1 \leq k \leq K .
                      \end{cases} \end{equation*} \end{small}
        % \item
    \end{itemize}
    \vspace*{5pt}
    \begin{colorblock}{}
        \textcolor{orange}{Contribution}:
        a (numerical) solver for this quasi-convex optimization problem, with \emph{Lagrange
        multipliers}.
    \end{colorblock}

\end{frameO}

\begin{frameO}[$1)$ \emph{Oracle} centralized strategy]

    \begin{colorblock}{}
        \(\implies\) This \emph{oracle} strategy has very good performance, as it maximizes the transmission rate of all the \(D\) dynamic devices
        \includegraphics[height=0.37cm]{dynamic-devices.png}
    \end{colorblock}

    \vspace*{10pt}

    \begin{colorblock}{But unrealistic}
        But \textbf{not achievable in practice}!
        \begin{itemize}
            % \item
            % there is no oracle
            \item \alert{because there is no centralized supervision!}
            \item and $(S_1,\dots,S_K)$ are unknown!
        \end{itemize}
    \end{colorblock}

    \vspace*{10pt}

    % \begin{lightblock}{
        \textcolor{orange}{We propose a \emph{realistic decentralized} approach, with bandits!}
    % }
        \begin{center}
            \includegraphics[height=2.25cm]{Venn_Diagram_ML_RL_MAB.pdf}
        \end{center}

        % \(\hookrightarrow\) Machine Learning \newline
        % \hspace*{15pt}\(\hookrightarrow\) Reinforcement Learning \newline
        % \hspace*{30pt} \(\hookrightarrow\) \emph{Multi-Armed Bandit}

    % \end{lightblock}

\end{frameO}



\begin{frameO}[Hum, what is a (one-armed) \emph{bandit}?]
    \begin{center}
        It's an old name for a casino machine \slotmachine{} !
    \end{center}

    \begin{center}
        \includegraphics[height=6.5cm]{Lucky_Luke__Le_Bandit_Manchot.jpg}

        \begin{tiny}
            \textcolor{gray}{
                \textcopyright{} Dargaud $1981$,
                \href{https://www.dargaud.com/bd/LUCKY-LUKE/Lucky-Luke/Lucky-Luke-tome-18-Bandit-manchot-Le}{\textcolor{blue}{Lucky Luke tome 18}},.
            }
        \end{tiny}
    \end{center}
\end{frameO}



\subsection{Multi-Armed Bandit algorithm: UCB}

\subsubsection{Multi-Armed Bandit formulation}

\begin{frameO}[Stochastic \emph{Multi-Armed Bandit} formulation]

    A player tries to collect \alert{rewards} when playing a $K$-armed \slotmachine{} bandit game.

    \begin{lightblock}{}
        At each round $t\in\{1,\dots,T\}$
        \begin{itemize}
            % \tightlist
            \item
                player chooses an \emph{arm} \slotmachine{} \(A(t) \in \{1,\dots,K\}\)
            \item
                the arm generates an i.i.d. \alert{reward} $r_{A(t)}(t) \sim \nu_{A(t)}$\\
                \textcolor{gray}{Ex: from a Bernoulli distribution $\nu_{k} = \mathcal{B}(\mu_k)$}
            \item
                player observes the reward $r_{A(t)}(t)$
        \end{itemize}
    \end{lightblock}

    \pause

    \begin{colorblock}{Goal (Reinforcement Learning)}
        Maximize the \alert{sum reward} or \textcolor{orange}{its expectation}
        \[\max_{A} \;\; \sum\limits_{t=1}^{T} \alert{r_{A(t)}} \,\,\,\,\,\, \text{or} \,\,\,\,\,\, max_{A} \;\; \textcolor{orange}{ \mathbb{E}\left[\sum\limits_{t=1}^{T} r_{A(t)}\right] }.\]
    \end{colorblock}

    \vfill{}
    \hfill{} {\small \textcolor{gray}{[Bubeck, 12], [Lattimore \& Szepesvári, 19], [Slivkins, 19]}}

\end{frameO}

\begin{frameO}[$2)$ Pseudo \emph{MAB} formulation of our IoT problem]

    A dynamic device \includegraphics[height=0.37cm]{dynamic-devices.png}  tries to collect \alert{rewards} when transmitting:

    \begin{itemize}
        % \tightlist
        \item
            it transmits following a random Bernoulli process \newline
            \textcolor{gray}{(ie. probability \(p\) of transmitting at each round \(t\))}
        \item
            it chooses a channel \(A(\tau) \in \{1,\dots,K\}\)
            \hfill{} ($=$ arm \slotmachine)
        \begin{itemize}
        \item
            if \texttt{Ack} (no collision) \hspace*{2pt} \(\implies\) \alert{reward
            \(r_{A(\tau)} = 1\)} \hfill{} (successful transm.!)
        \item
            if collision (no \texttt{Ack}) \hspace*{2pt} \(\implies\) \alert{reward
            \(r_{A(\tau)} = 0\)} \hfill{} (failed transmission!)
        \end{itemize}

    \end{itemize}

    \pause

    \vspace*{15pt}

    \begin{colorblock}{}
        \vspace*{4pt}
        \textbf{Goal:}
        Maximize transmission rate \(\equiv\) \textbf{maximize \alert{cumulated rewards}}
        \vspace*{4pt}
        % \(\equiv \max_{A} \;\; \sum\limits_{\tau=1}^{\text{nb of transm.}} r_{A(\tau)}\).
    \end{colorblock}

    \vspace*{5pt}

    \begin{lightblock}{It is not a \emph{stochastic} Multi-Armed Bandit problem}
        \textcolor{orange}{It looks like a MAB}
        but the \textbf{environment is not stochastic or stationary}
        % \newline
        % {\small (if only one device is activated at a time: average reward \(\mathbb{E}[r_k(\tau)] = p S_k\))}
    \end{lightblock}

\end{frameO}

\subsubsection{Upper Confidence Bound algorithm: UCB}

% \begin{frameO}[$2)$ Upper Confidence Bound algorithm (\(\mathrm{UCB}_1\))]
\begin{frameO}[$2)$ Upper Confidence Bound algorithm \hfill{} {\small \textcolor{lightgray}{[Auer et al, 02]}}]

    \only<1-2>{
        A dynamic device keeps \(\tau\) number of sent packets
    }

    \begin{enumerate}
        \def\labelenumi{\arabic{enumi}.}

        % \tightlist
        \only<1-2>{
            \item
              For the first \(K\) activations (\(\tau=1,\dots,K\)), try each channel
              \emph{once}.
        }
        \pause
        \item
              \only<1-2>{
                  Then for the next steps \(t\):
              }
              \only<3>{
                  For any dynamic device \includegraphics[height=0.37cm]{dynamic-devices.png},
                  for any round $t$:
              }

              \begin{itemize}
                  % \tightlist
                  \item
                        \textcolor{orange}{With probability $p$, the device is active ($\tau := \tau + 1$)}
                \only<1-2>{
                  \item
                        Compute the index
                        \(\mathrm{UCB}_k(\tau) := \overbrace{\frac{X_k(\tau)}{N_k(\tau)}}^{\text{Mean}\; \widehat{\mu_k}(\tau)} + \overbrace{\sqrt{\frac{\log(\tau)}{2 N_k(\tau)}},}^{\text{Confidence Bonus}}\)
                    % \only<1-2>{
                    %     \newline
                    %     \hfill{}
                    %     {\small \textcolor{gray}{[Auer et al, 02]}}
                    % }
                  \item
                        Choose channel
                        \(A(\tau) = \mathop{\arg\max}\limits_{k} \; \mathrm{UCB}_k(\tau)\),
                  \item  Observe reward $r_{A(\tau)}(\tau)$ from arm $A(\tau)$
                  \begin{itemize}
                  \item
                        Update \(N_k(\tau+1)\) nb selections of channel \(k\)
                        % \newline
                        % \(N_{A(\tau)}(\tau+1) = N_{A(\tau)}(\tau) + 1\) else
                        % \(N_k(\tau+1) = N_k(\tau)\)
                    \item
                        Update \(X_k(\tau)\) nb of successful transmissions
                        % \newline
                        % \(X_{A(\tau)}(\tau+1) = X_{A(\tau)}(\tau) + r_{A(\tau)}(\tau)\) else
                        % \(X_k(\tau+1) = X_k(\tau)\)
                  \end{itemize}
                }
                \only<3>{
                    \item Play UCB algorithm\dots{}
                    \hfill{}
                    {\small \textcolor{gray}{[Auer et al, 02]}}
                }
                  \item
                        \textcolor{orange}{Wait for next message\dots \hfill{} (mean waiting time $\simeq 1/p$)}
              \end{itemize}
    \end{enumerate}

    \only<3>{
    \begin{alertblock}{Problem 1: multiple dynamic devices}
        \begin{itemize}
            \item The collisions between dynamic devices \includegraphics[height=0.37cm]{dynamic-devices.png} are \textbf{not stochastic}!
        \end{itemize}
    \end{alertblock}
    \begin{alertblock}{Problem 2: random activation times $\tau$?}
        \begin{itemize}
            \item
                Devices transmits only with probability $p$ at each time $t$\newline
                \textcolor{gray}{(following its Bernoulli activation pattern)}
            \item
                The times $\tau$ are \textbf{not} the global time indexes $t$ (synchronized clock) !
        \end{itemize}
    \end{alertblock}
    \vspace*{10pt}
        {\large
            \alert{$\implies$ These two problems make the model \textbf{hard to analyze} !}
        }
    }

    % \vfill{}\hfill{}\tiny{\textcolor{gray}{References: [Lai \& Robbins, 85], [Auer et al, 02], [Bubeck \& Cesa-Bianchi, 12]}}

\end{frameO}



\subsection{Experimental results}

\subsubsection{Experiment setting}

\begin{frameO}[Experimental setting: simulation parameters]

    \vspace*{5pt}
    % \begin{colorblock}{}

        \begin{itemize}
            % \setlength\itemsep{10pt}
            % 
            % \tightlist
            \item
                \(K = 10\) channels \slotmachine,
            \item
                \(S\) \includegraphics[height=0.37cm]{static-devices.png}
                \(+\)
                \(D\) \includegraphics[height=0.37cm]{dynamic-devices.png}
                \(= 10000\) devices
                in total,
            \pause
            \item
                \(p = 10^{-3}\) probability of emission,
            \item
                Horizon \(T = 10^5\) total time slots
                (\textcolor{orange}{avg. \(\simeq 100\) messages \(/\) device}),
            \pause
            \item
                We change the proportion of dynamic devices
                \(D\)
                \includegraphics[height=0.37cm]{dynamic-devices.png}
                \(/\)
                \((S\)
                \includegraphics[height=0.37cm]{static-devices.png}
                \(+\)
                \(D\)
                \includegraphics[height=0.37cm]{dynamic-devices.png}
                \()\),
            \item
                For one example of \textcolor{darkgreen}{repartition of \((S_1,\dots,S_{K})\) static devices} \includegraphics[height=0.37cm]{static-devices.png}.
        \end{itemize}
        \vspace*{-10pt}
        \begin{center}
            \includegraphics[height=4.3cm]{Repartition_of_static_devices.png}
        \end{center}

    % \end{colorblock}

\end{frameO}



\subsubsection{First result: $10\%$}

\begin{frameO}[One result for \(10\%\) of dynamic devices]

    \begin{figure}[h!]
        \centering
        \includegraphics[height=0.74\textheight]{10intelligent.eps}

        % \caption{
            $10\%$ of dynamic devices \includegraphics[height=0.37cm]{dynamic-devices.png}. Gives $7\%$ of gain.\\
            {\small \textcolor{gray}{[Bonnefoi, Besson et al, 17], Sec.5.2}}
        % }
    \end{figure}

\end{frameO}



% \subsubsection{Second result: $30\%$}

% \begin{frameO}[\(30\%\) of dynamic devices]

%     \begin{figure}[h!]
%         \centering
%         \includegraphics[height=0.74\textheight]{30intelligent.eps}

%         % \caption{
%             \begin{small}
%                 $30\%$ of dynamic devices \includegraphics[height=0.33cm]{dynamic-devices.png}. Gives $3\%$ of gain but not much is possible here.
%             \end{small}
%         % }
%     \end{figure}

% \end{frameO}


\subsubsection{Growing proportion of dynamic devices}

\begin{frameO}[Growing proportion of dynamic devices \(D/(S+D)\)]

    \begin{figure}[h!]
        \centering
        \includegraphics[height=0.70\textheight]{perf_learning.eps}

        % \caption{
            \begin{itemize}
                \item
                The MAB selfish learning is \emph{almost optimal}, for any proportion of dynamic devices \includegraphics[height=0.37cm]{dynamic-devices.png}, \emph{after a short learning time}.

                \item
                In this example, it gives up-to $16\%$ gain over the naive approach!
            \end{itemize}
        % }
    \end{figure}

\end{frameO}


% \begin{frameO}[\emph{Positive} conclusion from experiments ($1/2$)]

%     \begin{colorblock}{What do we show}

%         \begin{itemize}
%             \setlength\itemsep{10pt}
%                   % \tightlist
%             \item
%                   After a short learning time, MAB algorithms are almost as efficient as
%                   the oracle solution,
%             \item
%                   Never worse than the naive solution, even at first iterations,
%             \item
%                   Thompson sampling is more efficient than UCB
%                   (as always),
%             \item
%                   The dynamic devices \includegraphics[height=0.37cm]{dynamic-devices.png} can learn to communicate more efficiently,\\
%                   in any network configuration (we tried a lot more!).
%         \end{itemize}

%     \end{colorblock}

% \end{frameO}


% \begin{frameO}[\emph{Negative} conclusion from experiments ($2/2$)]

%     \begin{lightblock}{But what are the limitations?}

%         \begin{itemize}
%             \setlength\itemsep{5pt}
%                   % \tightlist
%             \item
%                 \textcolor{orange}{\textbf{Only works empirically}!}
%                 \\
%                 Theoretically, we showed counter examples where the \textbf{Selfish} approach can fail, for the smallest case $D = 2$ devices, $p=1$ in $K=3$ channels
%             \item
%                 $p \times (D + S)$ devices in $K$ channels in average\\
%                 $\implies$ $p \ll \frac{K}{(D + S)}$ gives best performance
%             \item
%                 Only works empirically with a stationary hypothesis on the background traffic\dots
%             \item
%                 \textbf{Intractable model} in theory, mainly due to too much randomness (activations, collisions, selections\dots)
%         \end{itemize}

%     \end{lightblock}

% \end{frameO}
