Multi-Armed Bandit Learning in IoT Networks: Learning helps even in non-stationary settings

1Introduction

Unlicensed bands are more and more used and considered for mobile and LAN communication standards (WiFi, LTE-U), and for Internet of Things (IoT) standards for short-range (ZigBee, Z-Wave, Bluetooth) and long-range (LoRaWAN, SIGFOX, Ingenu, Weightless) communications [?]. This heavy use of unlicensed bands will cause performance drop, and could even compromise IoT promises.

Efficient Medium Access (MAC) policies allow devices to avoid interfering traffic and can significantly reduce the spectrum contention problem in unlicensed bands. As end-devices battery life is a key constraint of IoT networks, this leads to IoT protocols using as low signaling overhead as possible and simple ALOHA-based mechanisms. In this article, we analyze the performance of Multi-Armed Bandits (MAB) algorithms [?], used in combination with a time-frequency slotted ALOHA-based protocol. We consider the Upper-Confidence Bound (${UCB}_1$) [?], and the Thompson-Sampling (TS) algorithms [?].

MAB learning has already been proposed in Cognitive Radio (CR) [?], and in particular, for sensing-based Dynamic Spectrum Access (DSA) in licensed bands [?]. Recently, TS and ${UCB}_1$ algorithms have been used for improving the spectrum access in (unlicensed) WiFi networks [?], and the ${UCB}_1$ algorithm was used in a unlicensed and frequency- and time-slotted IoT network [?]. Many recent works show that MAB algorithms work well for real-world radio signal. However, even with only one dynamic user using the learning algorithm, the background traffic or the traffic of the other devices is never really stationary or i.i.d (independent and identically distributed). In recent works like [?], several devices are using bandit algorithms, and the assumptions made by the stochastic bandit algorithms are not satisfied: as several agents learn simultaneously, their behavior is neither stationary nor i.i.d. As far as we know, we provide the first study to confirm robustness of the use of stochastic bandit algorithms for decision making in IoT networks with a large number of intelligent devices in the network, which makes the environment not stationary at all, violating the hypothesis required for mathematical proofs of bandit algorithms convergence and efficiency.

The aim of this article is to assess the potential gain of learning algorithms in IoT scenarios, even when the number of intelligent devices in the network increases, and the stochastic hypothesis is more and more questionable. To do that, we suppose an IoT network made of two types of devices: static devices that use only one channel (fixed in time), and dynamic devices that can choose the channel for each of their transmissions. Static devices form an interfering traffic, which could have been generated by devices using other standards as well. We first evaluate the probability of collision if dynamic devices randomly select channels (naive approach), and if a centralized controller optimally distribute them in channels (ideal approach). Then, these reference scenarios allow to evaluate the performance of ${UCB}_1$ and TS algorithms in a decentralized network, in terms of successful communication rate, as it reflects the network efficiency.

The rest of this article is organized as follows. The system model is introduced in Section 2. Reference policies are described in Section 3, and MAB algorithms are introduced in Section 4. Numerical results are presented in Section 5.

2System model and notations

As illustrated in Figure 1, we suppose a slotted protocol. All devices share a synchronized time, and know in advance the finite number of available RF channels. In each time slot, devices try to send packets to the unique Base Station, which listens continuously to all channels, following an ALOHA-based communication (no sensing). Each time slot is divided in two parts: first for uplink communications in which data packets are sent by end-devices to the base station. If only one packet is sent in this part of the slot, the base station can decode it and sends an acknowledgement to the device in the second part. If two or more devices send an uplink packet in the same slot, the uplink packets collide (i.e., there is a collision), and the acknowledgement Ack is not transmitted. This way, no collision can occur on the downlink messages, easing the analysis of collisions.

There are two types of end-devices in the network:

• Static end-devices have poor RF abilities, and each of them uses only one channel to communicate with the base station. Their choice is assumed to be fixed in time (stationary) and independent (i.i.d.). The traffic generated by these devices is considered as an interfering traffic for other devices.

• Dynamic (or smart) end-devices have richer RF abilities, they can use all the available channels, by quickly reconfiguring their RF transceiver on the fly. They can also store communication successes or failures they experienced in each channel, in order to change channel, possibly at every time slot.

There are $N_c\ge 1$ channels, $D\ge 0$ dynamic end-devices, and $S\ge 0$ static devices. Furthermore, in channel $i\in 1;N_c$ there are $0\le S_i\le S$ static devices (so $S={\sum }_{i=1}^{N_c}{S}_i$). We focus on dense networks, in which the number of devices $S+D$ is very large compared to $N_c$ (about $1000$ to $10000$, while $N_c$ is about $10$ to $50$). As this problem is only interesting if devices are able to communicate reasonably efficiently with the base station, we assume devices only communicate occasionally, i.e., with a low duty cycle, as it is always considered for IoT.

We suppose that all devices follow the same emission pattern, being fixed in time, and we choose to model it as a simple Bernoulli process: all devices have the same probability to send a packet in any (discrete) temporal slot, and we denote $p\in (0,1)$ this probability¹. The parameter $p$ essentially controls the frequency of communication for each device, once the time scale is fixed (i.e., real time during two messages), and $1/p$ is proportional to the duty cycle.

The goal is to design a simple sequential algorithm, to be applied identically by each dynamic device, in a fully distributed setting (each device runs its own algorithm, from its observations), in order to minimize collisions and maximize the fraction of successful transmissions of all the dynamic devices.

Before explaining how this goal presents similarity with a multi-armed bandit problem, we present some natural baseline policies (i.e., algorithms).

3Three reference policies

This section presents three different policies that will be used to assess the efficiency of the learning algorithms presented in the next section. The first one is naive but can be used in practice, while the two others are very efficient but require full knowledge on the system (i.e., an oracle) and are thus unpractical.

3.1Naive policy: Random Channel Selection

We derive here the probability of having a successful transmission, for a dynamic device, in the case where all the dynamic devices make a purely random channel selection (i.e., uniform on $i\in 1;N_c=\{1,\dots ,N_c\}$).

In this case, for one dynamic device, a successful transmission happens if it is the only device to choose channel $i$, at that time slot. The probability of successful transmission is computed as follows, because the $S_i$ static devices in each channel $i$ are assumed to be independent, and static and dynamic devices are assumed to not transmit at each time $t$ with a fixed probability $1-p$ :

All dynamic devices follow the same policy in this case, so the probability of transmitting at that time in channel $i$ for any dynamic device is $p/N_c$, and there are $D-1$ other dynamic devices. As they are independent, the probability that no other dynamic device sent in $i$ is $q=P\left({\bigcap }_{k=1}^{D-1}\text{device}k\text{did not sent in}i\right)={\prod }_{k=1}^{D-1}P\left(\text{device}k\text{did not sent in}i\right)$. And $P\left(\text{device}k\text{sent in}i\right)=p\times 1/N_c$, by uniform choice on channels and the Bernoulli emission hypothesis. So $q={\prod }_{k=1}^{D-1}(1-p/N_c)=(1-p/N_c{)}^{D-1}$. Thus we can conclude,

This expression is constant (in time), and easy to compute numerically, but comparing the successful transmission rate of any policy against this naive policy is important, as any efficient learning algorithm should outperform it.

One point we could justify more is the following. The probability of having no other dynamic devices sending in channel $i$ in the same time is $(1-\frac{p}{N_c}{)}^{D-1}$. We justified this by saying that as all devices chose their channel uniformly, the observed Bernoulli process in channel $i$ has mean $p/N_c$.

3.2(Unachievable) Optimal oracle policy

We investigate in this section the optimal policy that can be achieved if the dynamic devices have a perfect knowledge of everything, and a fully centralized decision making² is possible. We want to find the stationary repartition of devices into channels that maximizes the probability of having a successful transmission.

If the oracle draws once uniformly at random a configuration of dynamic devices, with $D_i$ devices affected to channel $i$ is fixed (in time, i.e., stationary), then this probability is computed as before:

Consequently, the optimal allocation vector $(D_1,\dots ,D_{N_c})$ is the solution of the following real-valued constraint optimization problem :

• The objective function $f:(D_1,\dots ,D_{N_c})\mapsto {\sum }_{i=1}^{N_c}{D}_i(1-p{)}^{S_i+D_i-1}$ is quasi-convex [?] in each of its coordinates, on $[0,\infty {)}^{N_c}$.

• The Lagrange multipliers method can be applied to the optimization problem, with a quasi-convex objective function $f$, linear equality constraints and linear inequality constraints . Thanks to Theorem 1 from [?] for quasi-convex functions, the strong duality condition is satisfied in this case, so finding the saddle points will be enough to find the maximizers. $\square$

Where $(a{)}^{†}=max(a,0)$, and $W$ denotes the $W$-Lambert function which is the reciprocal bijection of $x\mapsto x{e}^x$ on $R^{+}=[0,+\infty )$ [?]. Moreover, condition implies that the Lagrange multiplier $\lambda$ is the solution of

Equation can be solved numerically, with simple one-dimensional root finding algorithms. Solving the optimization problem provides the optimal real number value for $D_i^{\ast }$, which has to be rounded to find the optimal number of devices for channel $i$ : $\widehat{D_i}=\lfloor D_i^{\ast }\rfloor$ for $1\le i<N_c$, and $\widehat{D_{N_c}}=D-{\sum }_{i=1}^{N_c-1}\widehat{D_i}$.

3.3A greedy approach of the oracle strategy

We propose a sequential approximation of the optimal policy: the third solution is a sub-optimal naive policy, simple to set up, but also unpractical as it also needs an oracle. End-devices are iteratively inserted in the channels with the lowest load (i.e., the index $i$ minimizing $S_i+D_i\left(\tau \right)$ at global time step $\tau$). Once the number of devices in each channel is computed, the probability of sending successfully a message is also given by equation . This is the policy that would be used by dynamic devices if they were inserted one after the other, and if they had a perfect knowledge of the channel loads.

4Sequential policies based on bandit algorithms

We now present the stochastic Multi-Armed Bandit (MAB) model, and the two stochastic MAB algorithms used in our experiments [?]. While the stochastic MAB model has been used to describe some aspects of Cognitive Radio systems, it is in principle not suitable for our IoT model, due to the non-stationarity of the channels occupancy caused by the learning policy used by dynamic objects.

4.1Stochastic Multi-Armed Bandits

A Multi-Armed Bandit problem is defined as follows [?]. There is a fixed number $N_c\ge 1$ of levers, or “arms”, and a player has to choose one lever at each discrete time $t\ge 1,t\in N$, denoted as $A\left(t\right)=k\in \{1,\dots ,N_c\}$. Selecting arm $k$ at time $t$ yields a (random) reward, $r_k\left(t\right)\in R$, and the goal of the player is to maximize the sum of his rewards, $r_{1\dots T}={\sum }_{t=1}^T{r}_{A\left(t\right)}\left(t\right)$.

A well-studied version of this problem is the so-called “stochastic” MAB, where the sequence of rewards drawn from a given arm $k$ is assumed to be independent and identically distributed (i.i.d) under some distribution ${\nu }_k$, that has a mean ${\mu }_k$. Several types of reward distributions have been considered, for example distributions that belong to a one-dimensional exponential family (e.g., Gaussian, Exponential, Poisson or Bernoulli distributions). We consider Bernoulli bandit models, in which $r_k\left(t\right)\sim Bern\left({\mu }_k\right)$, that is, $r_k\left(t\right)\in \{0,1\}$ and $P\left(r_k\right(t)=1)={\mu }_k$.

The problem parameters ${\mu }_1,\dots ,{\mu }_K$ are unknown to the player, so to maximize his cumulated rewards, he must learn the distributions of the channels, to be able to progressively focus on the best arm (i.e., the arm with largest mean). This requires to tackle the so-called exploration-exploitation dilemma: a player has to try all arms a sufficient number of times to get a robust estimate of their qualities, while not selecting the worst arms too many times.

In a Cognitive Radio application, arms model the channels, and players are the dynamic end-devices. For example in the classical OSA setting with sensing [?], a single dynamic device (a player) sequentially tries to access channels (the arms), and collects a reward of 1 if the channel is available and 0 otherwise. So rewards represent the availability of channels, and the parameter ${\mu }_k$ represents the mean availability of channel $k$.

Before discussing the relevance of a multi-armed bandit model for our IoT application, we present two bandit algorithms, UCB1 and Thompson Sampling, which both strongly rely on the assumption that rewards are i.i.d..

4.2The ${UCB}_1$ algorithm

A naive approach could be to use an empirical mean estimator of the rewards for each channel, and select the channel with highest estimated mean at each time. This greedy approach is known to fail dramatically [?]. Indeed, with this policy, the selection of arms is highly dependent on the first draws, if the first transmission in a channel fails, the device will never use it again. Rather than relying on the empirical mean reward, Upper Confidence Bounds algorithms instead use a confidence interval on the unknown mean ${\mu }_k$ of each arm, which can be viewed as adding a “bonus” exploration to the empirical mean. They follow the “optimism-in-face-of-uncertainty” principle : at each step, they play according to the best model, as the statistically best possible arm (i.e., the highest upper confidence bound) is selected.

More formally, for one device, let $N_k\left(t\right)={\sum }_{\tau =1}^{t}1\left(A\right(\tau )=k)$ be the number of times channel $k$ was selected up-to time $t\ge 1$. The empirical mean estimator of channel $k$ is defined as the mean reward obtained by selecting it up to time $t$, $\widehat{{\mu }_k}\left(t\right)=1/N_k\left(t\right){\sum }_{\tau =1}^t{r}_k\left(\tau \right)1\left(A\right(\tau )=k)$. For ${UCB}_1$, the confidence term is $B_k\left(t\right)=\sqrt{\alpha \log \left(t\right)/N_k\left(t\right)}$, giving the upper confidence bound $U_k\left(t\right)=\widehat{{\mu }_k}\left(t\right)+B_k\left(t\right)$, which is used by the device to decide the channel for communicating at time step $t+1$: $A(t+1)=\arg {max}_{1\le k\le N_c}{U}_k\left(t\right)$. ${UCB}_1$ is an index policy.

The ${UCB}_1$ algorithm uses a parameter $\alpha >0$, originally, $\alpha$ set to $2$ [?], but empirically $\alpha =1/2$ is known to work better (uniformly across problems), and $\alpha >1/2$ is advised by the theory [?]. In our model, every dynamic device implements its own ${UCB}_1$ algorithm, independently. For one device, the time $t$ is the number of time it accessed the network (following its Bernoulli transmission process,i.e., its duty cycle), not the total number of time slots from the beginning, as rewards are only obtained after a transmission, and IoT objects only transmit sporadicly, due to low transmission duty cycles.

4.3Thompson Sampling

Thompson Sampling [?] was introduced in 1933 as the very first bandit algorithm, in the context of clinical trials (in which each arm models the efficacy of one treatment across patients). Given a prior distribution on the mean of each arm, the algorithm selects the next arm to draw based on samples from the conjugated posterior distribution, which for Bernoulli rewards is a Beta distribution.

A Beta prior $Beta\left(a_k\right(0)=1,b_k(0)=1)$ (initially uniform) is assumed on ${\mu }_k\in [0,1]$, and at time $t$ the posterior is $Beta\left(a_k\right(t),b_k(t\left)\right)$. After every channel selection, the posterior is updated to have $a_k\left(t\right)$ and $b_k\left(t\right)$ counting the number of successful and failed transmissions made on channel $k$. So if the Ack message is received, $a_k(t+1)=a_k\left(t\right)+1$, and $b_k(t+1)=b_k\left(t\right)$, otherwise $a_k(t+1)=a_k\left(t\right)$, and $b_k(t+1)=b_k\left(t\right)+1$. Then, the decision is done by sampling an index for each arm, at each time step $t$, from the arm posteriors: $X_k\left(t\right)\sim Beta\left(a_k\right(t),b_k(t\left)\right)$, and the chosen channel is simply the channel $A(t+1)$ with highest index $X_k\left(t\right)$. For this reason, Thompson Sampling is a randomized index policy.

Thompson Sampling, although being very simple, is known to perform well for stochastic problems, for which it was proven to be asymptotically optimal [?]. It is known to be empirically efficient, and for these reasons it has been used successfully in various applications, including on problems from Cognitive Radio [?], and also in previous work on decentralized IoT-like networks [?].

4.4A bandit model for IoT

Our IoT application is challenging in that there are multiple players (the dynamic devices) interacting with the same arms (the channels), without any centralized communication (they do not even know the total number of dynamic devices).

Considered alone, each dynamic device implements a learning algorithm to play a bandit game, the device is consequently a smart device. In each time slot, if it has to communicate (which happens with probability $p$), then it chooses a channel and it receives a reward $1$ if the transmission is successful, $0$ otherwise. Each device aims at maximizing the sum of the rewards collected during its communication instants, which shall indeed maximize the fraction of successful transmissions. Besides the modified time scale (rewards are no longer collected at every time step), this looks like a bandit problem. However, it cannot be modeled as a stochastic MAB, as the rewards are clearly not i.i.d: they not only depend on the (stationary, i.i.d) behavior of the static devices, but also on the behavior of other smart devices, that is not stationary (because of learning).

Despite this, we show in the next section that running a stochastic bandit algorithm for each device based on its own rewards is surprisingly successful.

Multi-Player MAB with collision avoidance?

Another idea could be to try to use a multi-player MAB model, as proposed by [?], to describe our problem.

In that case, the static and dynamic devices effect is decoupled, and arms only model the availability of the channels in the absence of dynamic devices : they are i.i.d. with mean ${\mu }_i=1-p{S}_i$. Moreover, dynamic devices are assumed to be able to sense a channel before sending [?], and so communicate only if no static device is detected on the channel. The smart devices try to learn the arms with highest means, while coordinating to choose different arms, i.e., avoid collisions in their choice, in a decentralized manner. However, in this model it is assumed that the multiple agents can know that they experienced a collision with another agent, which is non-realistic for our problem at stake, as our model of smart device cannot do sensing nor differentiate collisions between smart and non-smart devices.

Adversarial bandit algorithms?

Instead of using MAB algorithms assuming a stochastic hypothesis on the system, we could try to use MAB algorithms designed to tackle a more general problem, that makes no hypothesis on the interfering traffic. The adversarial MAB algorithms is a broader family, and a well-known and efficient example is the $Exp3$ algorithm [?]. Empirically, the $Exp3$ algorithm turned out to perform worse than both ${UCB}_1$ and TS in the same experiments. Contrarily to the two stochastic algorithms, the use of $Exp3$ is correctly justified, even in the non-stationary and non-i.i.d, as its performance guarantee are true in any setting. But it is not so surprising that it performs worse, as the theoretical performance guarantees of adversarial MAB algorithms are an order of magnitude worse than the one for stochastic ones. More is left on this aspect for our future work.

We should instead write $r_k\left(t\right)\sim Bern\left({\mu }_k\right(t\left)\right)$, if ${\mu }_k\left(t\right)$ represents the probability that no static and no other dynamic device chose to send a packet on channel $k$, at that time $t$.

5Experiments and numerical results

We suppose a network with $S+D=2000$ end-devices, and one IoT base station. Each device sends packets following a Bernoulli process, of probability $p={10}^{-3}$ (e.g., this is realistic: one packet sent about every $20$ minutes, for time slots of $1s$). The RF band is divided in $N_c=10$ channels. Each static device only uses one channel, and their uneven repartitionin the $10$ channels is: $(S_1,\cdots ,S_{N_c})=S\times (0.3,0.2,0.1,0.1,0.05,0.05,0.02,0.08,0.01,$ $0.09)$, to keep the same proportions when $S$ decreases. The dynamic devices have access to all the channels, and use learning algorithms. We simulate the network during ${10}^6$ discrete time slots, during which each device transmits on average $1000$ packets (i.e., the learning time is about $1000$ steps, for each algorithm).

Figure 3 presents the evolution of the successful transmission rate, as a function of time. The two MAB algorithms, ${UCB}_1$ and Thompson Sampling (TS), are compared against the naive random policy from below, and the two oracle policies (optimal and greedy) from above. The results are displayed when $10$, $30$, $50$ and $100\%$ of the traffic is generated by dynamic devices.

We can see in Figure 3 that the TS algorithm (in red) outperforms the ${UCB}_1$ algorithm (in blue), when the number of end-devices is below 50%. When the number of end-devices is higher, both algorithms have almost the same performance, and perform well after very few transmissions (quick convergence). Moreover, we can see in Figures ?, ?, and ? that both have better success rate than the random policy and the probability of successful transmission is between the oracle optimal and oracle suboptimal policies. For instance, for $10\%$ of dynamic devices, after about $1000$ transmissions, using ${UCB}_1$ over the naive uniform policy improved the successful transmission rate from $83\%$ to $88\%$, and using Thompson Sampling improved it to $89\%$. Increasing the number of end-devices decreases the gap between the optimal and random policies: the more dynamic devices, the less useful are learning algorithms, and basically for networks with only dynamic devices, the random policy is as efficient as the optimal one, as seen in Figures ? and Figure 4.

To better assess the evolution of the optimal policy compared to the random one, we have displayed on Figure 4 the evolution of the gain, in term of successful transmissions rate, provided by the optimal oracle and the two learning policies, after ${10}^6$ time slots, i.e., about $1000$ transmissions for each object. We can see that when the proportion of end-devices is low (e.g., $1\%$ of devices are dynamic), the optimal policy provides an improvement of $16\%$ compared to random channel selection. The TS algorithm always provides near-optimal performance, but the ${UCB}_1$ algorithm has a lowest rate of convergence and performs consequently worse after $1000$ transmissions, for instance it only provides a gain of $12\%$ for the same proportion of dynamic devices ($1\%$).

Figure 4 also shows that learning keeps near-optimal performance even when the proportion of devices becomes large. Note that when this proportion increases, the assumptions of a stochastic MAB model are clearly violated, and there is no justification for the efficiency of TS and ${UCB}_1$ algorithms. Hence, it is surprising to have near optimal performance with stochastic MAB algorithms applied to partly dynamic and fully dynamic scenarios.

6Conclusion

In this article, we proposed an evaluation of the performance of MAB learning algorithms in IoT networks, with a focus on the convergence of algorithms, in terms of successful transmission rates, when the proportion of intelligent dynamic devices changes. Concretely, increasing this probability allows to insert more objects in the same network, while maintaining a good Quality of Service. We show that ${UCB}_1$ and TS have near-optimal performance, even when their underlying i.i.d. assumption is violated by the many “intelligent” end-devices.

This is both a surprising and a very encouraging result, showing that application of bandit algorithms tailored for a stochastic model is still useful in broader settings. The fully decentralized application of classic stochastic MAB algorithms are almost as efficient as the best possible centralized policy in this setting, after a short learning period, even though the dynamic devices can not communicate with each others, and do not know the system parameters. We will investigate this behavior in order to understand it better theoretically. We will also experiment more with adversarial algorithms, to confirm that they work less efficiently than stochastic bandit algorithms in our non-stochastic setting.

Moreover, for sake of simplicity we supposed that all devices use the same standard. Our future work will consider more realistic interference scenarios and IoT networks, with, e.g., non-slotted time, more than one base station etc.

We presented a simple model for IoT networks, slotted in frequency and in (discrete) time, where some of the end-devices are assumed to be fixed in one channel and some can reconfigure themselves dynamically, and can possibly access a different channel for every message they want to send. In a LoRaWan-like communication protocol with acknowledgments (Ack), dynamic end-devices can use the fact that they received an Ack to know if there choice of channel was smart, and so we presented the use of Reinforcement Learning algorithm to help dynamic devices improve their performance in this setting, like for Opportunistic Spectrum Access in Cognitive Radio.

If there is not a lot dynamic devices, the stationary hypothesis of the other devices allow to model the problem as a Multi-Armed Bandit (MAB) problem, but this stochastic model is less and less accurate as the number of dynamic devices grows. We focused on decentralized learning, where each dynamic device makes its own decision based only on its previous observation, with no central control; and we applied two classical bandit algorithms, ${UCB}_1$ and Thompson Sampling, for the decision making for dynamic devices. Their performance in term of improvement of the probability of successful transmission, and they were compared against the best possible allocation (if a central control with full knowledge of the system was possible, computed theoretically and approximated numerically), and a naive fully uniform random spectrum access.

We proved that both learning algorithms always perform better than the naive allocation policy, and after a short learning period (at least $1000$ messages for each devices), they are almost as efficient as the best allocation scheme, even when the proportion of dynamic devices is high, and even in the limit scenario when there is no static device. This is both a surprising and a very encouraging result, showing that application of bandit algorithms tailored for stochastic problem is still useful when the problem become less stochastic.

Acknowledgements

This work is supported by the French National Research Agency (ANR), under the projects SOGREEN (grant coded: N ANR-14-CE28-0025-02) and BADASS (N ANR-16-CE40-0002), by Région Bretagne, France, by the French Ministry of Higher Education and Research (MENESR) and ENS Paris-Saclay.

The simulation code used for the experiments in Section 5 is for MATLAB or GNU Octave, and is open-sourced under the MIT License, at: https://Bitbucket.org/SCEE_IETR/MAB_for_Non-stochastic_IoT_networks.

AAdditional details

a.1Possible extensions of this model

This work could easily be generalized with two probabilities $p_S$ and $p_D$, if static and dynamic devices had different transmission pattern, and less easily with one probability per device. Also, other emission pattern could be considered, instead of a Bernoulli process for each user. We prefer to consider that all devices have the same probability to transmit to keep the notation as simple as possible.

Another extension could be to not have a Bernoulli process (or any random process), but a fixed rate of transmission, e.g., one transmission a day. So additionally to deciding the channel for communication, each device has to also decide when to communicate. This is another direction of research, that we will investigate in the future.

a.2Proof of Proposition

This short subsection contains the missing details of the proof of Proposition ?.

1. First, we need to justify that the objective function is quasi-convex, in each of its coordinates.

2. Then, we develop the computation of $D_i^{\ast }\left(\lambda \right)$, as a closed form expression of the system parameters ($N_c,p$), the repartition of static devices ($S_1,\dots ,S_{N_c}$) and the Lagrange multiplier $\lambda$.

Quasi-convexity

• For $0<\gamma <1$, the function: $g:x\mapsto x{\gamma }^x$ is quasi-convex on $[0,\infty )$, i.e., $g(\eta x+(1-\eta \left)y\right)\le max\left(g\right(x),g(y\left)\right)$ for any $x,y\in [0,\infty )$ and $\eta \in [0,1]$ (definition from Indeed, $g(\eta x+(1-\eta \left)y\right)=\eta \left[x({\gamma }^x{)}^{\eta }\right]{\gamma }^{\left(\right(1-\eta \left)y\right)}+(1-\eta )\left[y({\gamma }^y{)}^{1-\eta }\right]{\gamma }^{\eta x}$, and ${\gamma }^{\left(\right(1-\eta \left)y\right)}\le 1$ and ${\gamma }^{\eta x}\le 1$. But also $({\gamma }^x{)}^{\eta }\le {\gamma }^x$ as $\eta \le 1$, and the same holds for $({\gamma }^y{)}^{1-\eta }\le {\gamma }^y$. So $g(\eta x+(1-\eta \left)y\right)\le \eta \left(x{\gamma }^x\right)+(1-\eta )\left(y{\gamma }^y\right)$ which is a convex combination of $x{\gamma }^x$ and $y{\gamma }^y$, so smaller than the larger of the two values, and so $g(\eta x+(1-\eta \left)y\right)\le max(x{\gamma }^x,y{\gamma }^y)$.

• The function $f:(D_1,\dots ,D_{N_c})\mapsto {\sum }_{i=1}^{N_c}{D}_i(1-p{)}^{S_i+D_i-1}$ is quasi-convex in each of its coordinates, on $[0,\infty {)}^{N_c}$, as a sum of component-wise quasi-convex functions (with $\gamma =(1-p)\in (0,1)$, thanks to the first point). $\square$

Derivation of the Lagrange multiplier solution

Let us now prove the expression for $D_i^{\ast }$ given in .

• If $D=(D_1,\dots ,D_{N_c})$, the Lagrangian is denoted $L(D,\lambda )=f\left(D\right)+\lambda (D-{\sum }_{i=1}^{N_c}{D}_i)$, and its derivative w.r.t. $D_i$ is $\frac{\partial }{\partial D_i}L(D,\lambda )=(1-p{)}^{S_i+D_i-1}+\log (1-p\left)D_i\right(1-p{)}^{S_i+D_i-1}-\lambda$.

• So the gradient is canceling $\frac{\partial }{\partial D_i}L(D,\lambda ){|}_{D_i=D_i^{\ast }}=0$ iff $D_i^{\ast }$ satisfies $(1-p{)}^{D_i^{\ast }}(1+\log (1-p)D_i^{\ast })=\lambda /(1-p{)}^{S_i-1}$. Let $x=\log (1-p)D_i^{\ast }$ this is equivalent to $e^x(1+x)=\lambda /(1-p{)}^{S_i-1}$ and with $y=1+x$, we get $e^{y}y=\lambda e/(1-p{)}^{S_i-1}$.

• By using the $W$-Lambert function $W$ [?], reciprocal of $y\mapsto e^{y}y$, we get $x=y-1=W\left(\lambda e/\right(1-p{)}^{S_i-1})-1$. So the gradient of the Lagrangian is canceling iff $D_i^{\ast }=max(0,1/\log (1-p\left)x\right)={\left[\frac{1}{\log (1-p)}W\left(\lambda e/\right(1-p{)}^{S_i-1})-1\right]}^{†}$, because $D_i^{\ast }$ has to be non-negative. This gives the $i$-th coordinate of the unique saddle point of $f\left(D\right)$, and so the unique solution to the maximization problem, thanks to $\square$

a.3Example of another simulation

• We can include one with a uniform repartition of static device, to check that learning does not help in this case, but does not decrease performance either.

• And we should include another example with a different scenarios, maybe $(0.3,0.3,0.3,0.015,0.015,0.014,0.014,0.014,0.014,0.014)$ (Rémi already did the simulations).