Aggregation of Multi-Armed Bandits Learning Algorithms for Opportunistic Spectrum Access

1Introduction

Cognitive Radio (CR), introduced in $1999$ [?], states that a radio, by collecting information about its environment, can dynamically reconfigure itself in order to improve its functionality regarding various metrics. One of the main direction of research, called Dynamic Spectrum Access [?], is focused on the spectrum access when devices reconfigure themselves by simply changing the frequency of their wireless communication. The model of Opportunistic Spectrum Access (OSA) for CR considers one Secondary User (SU) trying to use a licensed radio network occupied by Primary Users (PU). The network usage from the PU determines the availability patterns of the radio channels, and the goal of the SU is to communicate as efficiently as possible, without interfering with the PU. Thus at each step, a SU first senses one channel, and only transmits if this channel is unoccupied by a PU.

A common simple model in the literature is to describe the PU impact on the availability of the $K$ channels in the following way: channels are independent and identically distributed (i.i.d.), and their qualities follow parametric distributions, e.g., Bernoulli of means ${\mu }_1,\dots ,{\mu }_K\in [0,1]$ for availabilities when dealing with binary sensing feedback. The SU has to select the best expected channel each time to maximize its throughput: if successful communications are seen as rewards, the SU has to maximize its cumulative rewards, as in the Multi-Armed Bandit (MAB) problem [?].

MAB learning algorithms have been shown to be useful for the OSA setting [?], and $UCB$ algorithms and other variants (e.g., $kl$-$UCB$or Bayes-UCB, [?]) have been successfully applied to both numerical and physically simulated CR problems [?]. The performance of such learning algorithm $A$ can be measured by different criteria. For example, it is common in the bandit literature to study the regret [?] $\widetilde{R_T^A}={\mu }^{\ast }T-{\sum }_{t=1}^{T}r\left(t\right)$ which compares the loss in rewards between the algorithm $A$ and the full-knowledge strategy which always picks the best arm, i.e., the most available of mean ${\mu }^{\ast }$. Good algorithms are expected to have slow-growing expected regret, but other criterion include the best arm pull frequency, or the throughput of the SU.

Many different learning algorithms have been proposed by the machine learning community, and most of them depend on several parameters, for instance $\alpha$ for $UCB$, the prior for Thompson sampling or BayesUCB, the $kl$ function for $kl$-$UCB$ etc. Every time a new MAB algorithm $A$ is introduced, it is compared and benchmarked on some bandit instance, parameterized by $\mu =({\mu }_1,\dots ,{\mu }_K)$, usually by focusing on its expected regret $R_T=E_{\mu }\left[\widetilde{R_T}\right]$. For a known and specific instance, simulations help to select the best algorithm in a pool of algorithms. But when one wants to tackle an unknown real-world problem, one expects to be efficient against any problem, of any kind, size and complexity: ideally one would like to use an algorithm that can be applied identically against any problem. To choose the best algorithm, two approaches can be followed: either extensive benchmarks are done beforehand – if this is possible – to select the algorithm and its optimal parameters, or an adaptive algorithm is used to learn on the fly its parameters. We present a simple adaptive solution, that aggregates several learning algorithms in parallel and adaptively chooses which one to trust the most.

This paper is organized as follows: our OSA model is described in Section 2, and MAB learning algorithms are briefly presented in Section 3. We explain in Section 4 how to combine such algorithms for aggregation. Our proposed algorithm, called Aggregator, is detailed in Section 4.1, with numerical experiments presented in Section 5, comparing the regret of several algorithms against different aggregation algorithms. Theoretical guarantees are shortly discussed in Section 6, and Section 7 concludes.

2OSA Model for Cognitive Radio

We consider $K\ge 1$ radio channels, also called arms, of different characteristics, unknown to the user. The radio protocol is slotted in both time and frequency, meaning that at each time step $t\in N$, the Secondary User (SU) tries to communicate in a channel $A\left(t\right)\in \{1,\dots ,K\}$. In the OSA model, the SU first senses one channel $k$ at a time, and can use it to communicate only if it was sensed free from any PU (they have full priority over the SU).

In the stochastic model considered in this paper, after choosing the arm $k$, it is assumed that the sensing provides a reward $r_k\left(t\right)$, randomly drawn from a certain distribution depending on the arm index. Rewards are assumed to be bounded in $[0,1]$, and generally they follow one-parameter exponential families. We present our algorithm by restricting to Bernoulli distributions¹, for sake of simplicity, meaning that arm $k$ has a parameter ${\mu }_k\in [0,1]$ and rewards are drawn from $B\left({\mu }_k\right)$, $r_k\left(t\right)\sim B\left({\mu }_k\right)$, which can be simply interpreted by the SU: it is $1$ if the channel $k$ is not used by any PU during the time slot $t$, and is $0$ otherwise. Aggregation algorithms usually deal with losses rather rewards [?], so we also introduce the quantity ${\ell }_k\left(t\right):=1-r_k\left(t\right)\in [0,1]$.

3Classical MAB Algorithms : $UCB$, $kl$-$UCB$, Ts

An algorithm $A$ has to maximize its cumulative rewards, by choosing the arm $A\left(t\right)\in \{1,\dots ,K\}$ at time $t$, or, equivalently, to minimize its pseudo-regret $\widetilde{R_T^A}$ is defined as

where ${\mu }^{\ast }$ is the mean of the best arm: ${\mu }^{\ast }={max}_{k=1}^k{\mu }_k={max}_{k=1}^k{E}_{\mu }\left[r_k\right(t\left)\right]$, for an expectation taken on the arm distributions. This pseudo-regret is random so we prefer to focus on the expected regret, $R_T^A:=E_{\mu }\left[\widetilde{R_T^A}\right]$.

The $UCB$ algorithm [?] selects the arm with highest index, where each index is an Upper Confidence Bound on the unknown mean, computed as the sum of the empirical mean of each arm $\widehat{{\mu }_k}\left(t\right)=X_k\left(t\right)/N_k\left(t\right)$ (if $X_k\left(t\right):={\sum }_{t=1}^T{r}_{A\left(t\right)}\left(t\right)1\left(A\right(t)=k)$ and $N_k\left(t\right):={\sum }_{t=1}^{T}1\left(A\right(t)=k)$), and an exploration term defined by $\sqrt{\alpha \log \left(t\right)/N_k\left(t\right)}$. $\alpha =1/2$ is known to yield logarithmic regret on all problems, but on some specific instance $\mu$ a better value of $\alpha$ may be found empirically [?].

The $kl$-$UCB$ algorithm is similar, but instead it uses a Kullback-Leibler divergence function to compute a statistically better UCB [?]. As a different KL function exists for each different exponential family, this algorithm also requires a prior knowledge of the problem to be efficient.

The Thompson sampling (TS) [?] algorithm is Bayesian: it maintains a posterior distribution on each means (e.g., Beta posteriors for Bernoulli arms), updated after each observation, and chooses an arm by sampling a random mean from each posterior and playing the arm with highest mean. The posterior distribution has to be chosen according to the exponential family as the conjugated posterior.

Both $UCB$, $kl$-$UCB$ and TS have been proved to have logarithmic regrets [?], meaning that $R_T^A=O\left(\log T\right)$, in Bernoulli bandit problems and also under more general assumptions. The constant in the big-$O$ is important, and [?] showed that in this setting, the regret of any (uniformly efficient) algorithm is at least $C\left(\mu \right)\log T$ when $T$ is large, for a constant $C\left(\mu \right)$ depending only on the problem instance $\mu$ : $C\left(\mu \right)={\sum }_{{\mu }_k\ne {\mu }^{\ast }}({\mu }^{\ast }-{\mu }_k)/kl({\mu }_k,{\mu }^{\ast })$ (with a unique best arm), where $kl(x,b)$ is the binary KL divergence between two Bernoulli distributions of parameters $x$ and $y$.

4Aggregating Bandit Algorithms

We assume to have $N\ge 2$ MAB algorithms, $A_1,\dots ,A_N$, and let $A_{aggr}$ be an aggregation algorithm, which runs the $N$ algorithms in parallel (with the same slotted time), and use them to choose its channels based on a voting from their $N$ decisions. $A_{aggr}$ depends on a pool of algorithms and a set of parameters. We would like that $A_{aggr}$ performs almost as well as the best of the $A_a$, with a good choice of its parameters, independently of the MAB problem. Ideally $A_{aggr}$ should perform similarly to the best of the $A_a$. To simplify the presentation, we only aggregate bandit algorithms that give deterministic recommendations: one arm is chosen with probability $1$ and the others with probability $0$. However, both Exp4 and Aggregator can be adapted to aggregate randomized bandit algorithms, i.e., algorithms that output a probability distribution ${\xi }_t$ over the arms $\{1,\dots ,K\}$ at each time step, and draw the next selected arm according to this distribution.

The aggregation algorithm maintains a probability distribution ${\pi }^t$ on the $N$ algorithms $A_a$, starting from a uniform distribution: ${\pi }_a^t$ is the probability of trusting the decision made by algorithm $A_a$ at time $t$. $A_{aggr}$ then simply performs a weighted vote on its algorithms: it decides whom to trust by sampling $a\in \{1,\dots ,N\}$ from ${\pi }^t$, then follows $A_a$’s decision. The main questions are then to know what observations (i.e., arms and rewards) should be given as feedback to which algorithms, and how to update the trusts at each step, and our proposal Aggregator differs from Exp4 on these very points.

4.1The Aggregator algorithm

Our proposed Aggregator is detailed in Algorithm 1 below.

At every time step, after having observed a loss ${\ell }_{A^{t+1}}(t+1)$ for its chosen action $A^{t+1}$, the algorithm updates the trust probabilities from ${\pi }^t$ to ${\pi }^{t+1}$ by a multiplicative exponential factor (using the learning rate and the unbiased loss). Only the algorithms $A_a$ who advised the last decision get their trust updated, in order to trust more the “reliable” algorithms. The loss estimate is unbiased in the following sense. If one had access to the rewards $r_k(t+1)$ (or the losses ${\ell }_k(t+1)$) for all arms $k$, the loss incurred by algorithm $a$ at time $t+1$ would be ${\tilde{\ell }}_{a,t+1}={\ell }_{A_a^{t+1}}(t+1)$. This quantity can only be observed for those algorithms for which $A_a^{t+1}=A^{t+1}$. However, by dividing by the probability of observing this recommendation, one obtains an unbiased estimate of ${\tilde{\ell }}_{a,t}$. More precisely,

satisfies $E\left[{\hat{\ell }}_{a,t+1}|H_t\right]={\tilde{\ell }}_{a,t+1}$, for all $a$, where the expectation is taken conditionally to the history of observations up to round $t$, $H_t$. Observe that ${\tilde{\ell }}_{a,t+1}={\ell }^{t+1}$ for all algorithms $a$ such that $A_a^{t+1}=A^{t+1}$, and ${\tilde{\ell }}_{a,t+1}=0$ otherwise.

An important feature of Aggregator is the feedback provided to each underlying bandit algorithm, upon the observation of arm $A^{t+1}$. Rather than updating only the trusted algorithms (that is the algorithms which would have drawn arm $A^{t+1}$) with the observed reward $r_{A^{t+1}}(t+1)=1-{\ell }_{A^{t+1}}(t+1)$, we found that updating each algorithm with the (original) loss observed for arm $A^{t+1}$ improves the performance drastically. As expected, the more feedback they get, the faster the underlying algorithms learn, and the better the aggregation algorithm will be [?].

Regarding the update of ${\pi }^t$, one can note that the trust probabilities are not all updated before the normalization step, and an alternative would be to increase ${\pi }_a$ if $A_a^{t+1}=A^{t+1}$ and to decrease it otherwise. It would not be so different, as there is a final renormalization step, and empirically this variation has little impact on the performance of Aggregator.

4.2 Aggregator versus Exp4

The Exp4 algorithm (see, e.g. [?]) is similar to Aggregator, presented in Algorithm ?, but differs in the two following points. First, $a\sim {\pi }^t$ is sampled first and the arm chosen by $A_a$ is trusted, whereas Aggregator needs to listen to the $N$ decisions to perform the updates on ${\pi }^{t+1}$, and Exp4 gives back an observation (arm, reward) only to the last trusted algorithm whereas Aggregator gives it to all algorithms. Second, after having computed the loss estimate $\ell$, Exp4 updates the estimated cumulative loss for each algorithm, ${\tilde{L}}_a\left(t\right)={\sum }_{s=1}^t{\ell }_{A_a^s}\left(s\right)\times 1(A_a^s=A_{aggr}^s)$. Instead of updating ${\pi }^t$ multiplicatively as we do for our proposal, Exp4 recomputes it, proportionally to $\exp (-{\eta }_t{\tilde{L}}_a(t\left)\right)$.

The sequence of non-negative learning rates $({\eta }_t{)}_{t\ge 1}$ used by Exp4 can be arbitrary, it can be constant but should be non-increasing [?]. If the horizon $T$ is known (and fixed), the best choice is given by ${\eta }_t=\eta :=2\log \left(N\right)/\left(TK\right)$. However, for real-world communication problems, it is unrealistic to assume a fixed and known time horizon, so we prefer the alternative horizon-free choice of learning rates, ${\eta }_t:=\log \left(N\right)/\left(tK\right)$ suggested by [?]. We compare both approaches empirically, and the second one usually performs better. We also stick to this choice of $({\eta }_t{)}_{t\ge 1}$ for Aggregator.

5Experiments on Simulated MAB Problems

We focus on i.i.d. MAB problems, with $K=9$ channels². For Bernoulli problem, the first one uses $\mu =[0.1,\dots ,0.9]$, and the second one is divided in three groups: 2 very bad arms ($\mu =0.01,0.02$), 5 average arms ($\mu =0.3$ to $0.6$) and 3 very good arms ($\mu =0.78,0.8,0.82$). The horizon is set to $T=20000$ (but its value is unknown to all algorithms), and simulations are repeated $1000$ times, to estimate the expected regret. This empirical estimation of the expected regret $R_T$ is plotted below, as a function of $T$, comparing some algorithms $A_1,\dots ,A_N$ (for $N=6$), and their aggregation with Aggregator (displayed in orange bold). The Lai & Robbins’ logarithmic lower-bound [?] is also plotted, and it is crucial to note that it is only asymptotic and to not be surprised by having regret curves smaller than the lower-bound (e.g., for the easier Bernoulli problem). Note that for each of the $1000$ simulations, we choose to generate all the rewards beforehand, i.e., one full matrix $\left(r_k\right(t){)}_{1\le k\le K,1\le t\le T}$ for every repetition, in order to compare the algorithms on the same realizations of the MAB problem.

We compare our Aggregator algorithm, as well as other aggregation algorithms, Exp4, CORRAL and LearnExp (both with default parameters) [?]. The aggregated algorithms consist in a naive uniform exploration (to have at least one algorithm with bad performances, i.e. linear regret, but it is not included in the plots), $UCB$ with $\alpha =1/2$, three $kl$-$UCB$ with Bernoulli, Gaussian and exponential $kl$ functions, and BayesUCB and Thompson sampling with uniform prior.

Figures Figure 1 and Figure 4 are in semi$\log$-$y$ scale, this helps to see that the best algorithms can be an order of magnitude more efficient than the worst, and the Aggregator performs similarly to the best ones, when the other aggregation algorithms are usually amongst the worst. Figure 5 is in semi$\log$-$x$ scale to show that the regret of efficient algorithms are indeed logarithmic.

For Bernoulli problems (Figures Figure 1 and Figure 2), UCB with $\alpha =1/2$, Thompson sampling, BayesUCB and $kl$-$UCB$${}^{+}$ (with the binary $kl$ function) all perform similarly, and Aggregator is found to be as efficient as all of them. For Gaussian and exponential arms, rewards are truncated into $[0,1]$, and the variance of Gaussian distributions is fixed to ${\sigma }^2=0.05$ for all arms, and can be known to the algorithms (the $kl$ function is adapted to this one-dimensional exponential family). Figure 3 uses only Gaussian arms, with a large gap between their means and a relatively small variance, giving an “easy” problem. And Figure 4 shows a considerably harder “mixed” problem, when the distributions are no longer in the same one-dimensional exponential family and so the Lai & Robbins’ lower-bound no longer holds (even if there still exists a lower-bound).

For each of the 4 problems considered, the Aggregator algorithm with default option (broadcast loss to all players) is the best of all the aggregation algorithms, and its regret is very close to the best of the aggregated algorithms. Especially in difficult problems with mixed or unknown distributions, Aggregator showed to be more efficient that Exp4 and orders of magnitude better than the other reference aggregation algorithms LearnExp and CORRAL (see Figures Figure 4 and Figure 5).

6Theoretical Guarantees

The Aggregator does not have satisfying theoretical guarantees in terms of regret $R_T$ yet, unlike many bandit algorithms. Another notion, the adversarial regret, denoted by $\overline{R_T}$, measures the difference in terms of rewards, between the aggregation algorithm $A_{aggr}$ and the best aggregated algorithm $A_a$. This is in contrast with the (classical) regret, which measure the difference with the best fixed-arm strategy (Eq. ). Thus, even if the aggregated algorithms have logarithmic (classical) regret, having an adversarial regret scaling as $\sqrt{T}$ does not permit to exhibit a logarithmic (classical) regret for the aggregation algorithm. Under some additional hypotheses, [?] proves that Exp4 satisfies a bound on adversarial regret, $\overline{R_T}\le 2\sqrt{TN\log k}$, with the good choice of the learning rate sequence $({\eta }_t{)}_{t\ge 1}$. Our proposed algorithm follows quite closely the architecture of Exp4, and a similar bound for Aggregator is expected to hold.

This would be a first theoretical guarantee, but not satisfactory as simple algorithms like UCB have regrets scaling as $\log T$ [?], not $\sqrt{T}$. Regret bounds in several different settings are proved for the CORRAL algorithm [?], but no logarithmic upper-bound can be obtained from their technique, even in the simplest setting of stochastic bandits. However, Aggregator always seems to have a (finite-horizon) logarithmic regret in all the experiments we performed, for both Bernoulli and non-Bernoulli problems (e.g., Gaussian, exponential and Poisson distributions). Further theoretical developments are left as future work.

7Conclusion

We presented the use of aggregation algorithms in the context of Opportunistic Spectrum Access for Cognitive Radio, especially for the real-world setting of unknown problem instances, when tuning parameters before-hand is no longer possible and an adaptive algorithm is preferable. Our proposed Aggregator was presented in details, and we also highlighted its differences with Exp4.

We realized experiments on simple MAB problems already used in the community of bandit algorithms for OSA [?], and the simulations results showed that Aggregator works as expected, being able to identify on the fly the best algorithm to trust for a specific problem. Experiments on problems mixing different families of distributions were also presented, with similar conclusions in favor of Aggregator. It is not presented in this article, but our proposed algorithm also works well in dynamic scenarios, in which the distribution of the arms can change abruptly at some time, and appears to be more robust than simple non-aggregated algorithms. Exp4 has theoretical guarantees in terms of adversarial regret, and even if the same result could hold for Aggregator, results in terms of classical regret are yet to be proved. Empirically, Aggregator showed to always have a logarithmic regret $R_T$ if it aggregates algorithms with logarithmic regrets (like UCB, $kl$-$UCB$, Thompson sampling, BayesUCB etc). It usually succeeds to be close to the best of the aggregated algorithms, both in term of regret and best arm pull frequency. As expected, the Aggregator is never able to outperform any of the aggregated algorithms, but this was an over-optimistic goal. What matters the most is that, empirically, Aggregator is able to quickly discover on the fly the best algorithms to trust, and then performs almost as well as if it was following it from the beginning.

Our Aggregator algorithm can probably be rewritten as an Online Mirror Descent, as Exp4 and CORRAL, but this does not appear useful as in the case of CORRAL the analysis cannot bring a logarithmic bound on the regret even by aggregating asymptotically optimal algorithms. We will continue investigating regret bounds for Aggregator, and other directions include possible applications to the non-stochastic case (e.g., rested or restless Markovian problems, like it was very recently studied in [?]).

8Acknowledgements

The authors would like to thank Odalric-Ambrym Maillard at Inria Lille, Rémi Bonnefoi and Quentin Bodinier at CentraleSupélec Rennes, for fruitful discussions.

Note: the source code (Python $2$ or $3$) used for the simulations and the figures is open-sourced, at https://GitHub.com/SMPyBandits/SMPyBandits, and a full documentation is available at https://smpybandits.github.io/.