text:
Navikkumar Modi
email: navikkumar.modi@centralesupelec.fr

Member, IEEE Philippe Mary

Member, IEEE Christophe Moy

QoS driven Channel Selection Algorithm for Cognitive Radio Network: Multi-User Multi-armed Bandit Approach

Keywords: User Multi-armed Bandit Approach Cognitive Radio, Upper Confidence Bound, Opportunistic Spectrum Access, Machine Learning

QoS driven Channel Selection Algorithm for Cognitive

Radio Network: Multi-

I. INTRODUCTION

A. Bandit Theory and Opportunistic Spectrum Access

Opportunistic spectrum access (OSA) has emerged as an effective alternative to alleviate the spectrum scarcity issue and to improve the spectrum efficiency. In OSA, secondary users (SUs) also referred as unlicensed users identifies vacant spectrum through sensing and transmit opportunistically into the selected band without interfering with primary users (PUs). One of the main challenges of the cognitive networks is to achieve coexistence of heterogeneous SUs trying to access the same part of the spectrum. Due to resource and hardware constraints, SUs may sense only a part of the spectrum at any given time and hence they need to learn about statistics of the PUs' channels without having any a priori informations or very few. OSA scenario is hence generally tackled with reinforcement learning (RL) approaches whose the principle is to reward good trials and penalize bad ones.

It has been shown in several works that multi-armed bandit (MAB) approach is particularly well adapted to tackle the OSA problem. Indeed, each SU senses, at each time step, one of the K frequency bands available in the PUs spectrum, according to a given policy, and searches for learning the best channel given a certain criterium, e.g. availability. The performance is analyzed using two criteria: convergence and regret [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF]. The former is the guarantee that the policy, at the end, finishes to play almost always the best channel, and the latter measures the speed at which the convergence is achieved and is defined as the difference between the expected reward obtained using an infeasible ideal policy and the selected policy.

Additionally in this paper, we consider a distributed framework where there is no information exchange or prior agreement among the different SUs, thus it introduces additional challenges such as: loss in the collected reward due to collisions among the different SUs trying to access same channel, and also competition among different SUs since they all sense and access a channel with higher reward in the long run. It is necessary for the channel access policies to overcome the above challenges.

B. Related Work

Detailed discussions on MAB problems can be found in [START_REF] Jouini | Upper confidence bound based decision making strategies and dynamic spectrum access[END_REF], [START_REF] Jouini | Decision making for cognitive radio equipment: analysis of the first 10 years of exploration[END_REF], [START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF], [START_REF] Oksanen | A sensing policy based on confidence bounds and a restless multi-armed bandit model[END_REF]. In [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF], [START_REF]Sample mean based index policies with O(log n) regret for the multi-armed bandit problem[END_REF], the authors have provided a lower bound on the regret of single user MAB policies and developed simple mean based index policies for independent and identical distributed (iid) rewards to achieve this bound. In [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], the authors have proposed a simple mean based index policy for single SU, named upper confidence bound 1 (UCB1) for iid reward which achieves logarithmic order regret uniformly over time and not only asymptotically.

The reward distribution model is fundamental in the machine learning analysis and the iid assumption is not the only one used. For instance, Markovian reward is also particularly well adapted to OSA scenario in which the probability for a channel to be free at the current time is correlated to its state at the previous time instant. Logarithmic lower bound on regret has also been shown for Markov MAB in [START_REF] Anantharam | Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple playspart ii: Markovian rewards[END_REF]. In Markov MAB framework, two use cases can be considered, i.e. rested or restless MAB. In the former case, the state of arms (or bands in OSA scenario) that are not played do not change and only the arm played continues to evolve, while in the later case, the state of non-played arms may change [START_REF] Oksanen | A sensing policy based on confidence bounds and a restless multi-armed bandit model[END_REF], [START_REF] Liu | Learning in a changing world: Restless multiarmed bandit with unknown dynamics[END_REF]. In [START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF], [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], the authors have proved that the single user regenerative cycle algorithm (RCA) are order optimal for rested and restless MAB, respectively. In general, there have been relatively few works on MAB problem with Markovian reward, however, the authors in [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], [START_REF] Liu | Learning in a changing world: Restless multiarmed bandit with unknown dynamics[END_REF], have proposed few policies for restless Markov MAB problem when a single user accesses the spectrum.

The authors in [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF] and [START_REF] Liu | Cooperative game in dynamic spectrum access with unknown model and imperfect sensing[END_REF] have considered centralized spectrum access schemes in contrast to distributed spectrum access here. In a centralized spectrum access, multiple channels are selected by a single centralized user, at each iteration, and receives the reward which is a linear combination of the collected rewards from the selected channels. However, it requires extensive information flow among users, and this type of learning cannot generally be used in cognitive networks where multiple users act selfishly and their collected rewards are affected by the actions of other users operating in a same spectrum.

Moreover, the MAB framework have been also designed to address the distributed channel selection problem, as discussed in [START_REF] Liu | Decentralized multi-armed bandit with imperfect observations[END_REF], [START_REF] Kalathil | Decentralized learning for multiplayer multiarmed bandits[END_REF]. In [START_REF] Kalathil | Decentralized learning for multiplayer multiarmed bandits[END_REF], the authors have proposed a set of policies for multiple-user iid and rested MAB problems, whereas in this paper we propose a policy for restless MAB problems. [START_REF] Kalathil | Decentralized learning for multiplayer multiarmed bandits[END_REF] has assumed that each SU declares its actions to others e.g. the selected channel, which can be a strong constraint. Liu and Zhao, in [START_REF] Liu | Decentralized multi-armed bandit with imperfect observations[END_REF], have proposed a distributed learning and spectrum access policy, time-division fair share (TDFS), for iid rewards and have proved that the policy has a logarithmic order regret. In [START_REF] Liu | Decentralized multi-armed bandit with imperfect observations[END_REF] and [START_REF] Liu | Distributed learning under imperfect sensing in cognitive radio networks[END_REF], the SUs orthogonalize their transmission with different offsets in their time-sharing schedule, while we consider that SUs orthogonalize into different channels. Moreover, the TDFS policies consider that each SU collects almost the same time-average reward while policy proposed in this paper achieves probabilistic fairness.

In [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF], the authors have formulated the OSA problem of decentralized learning and spectrum access for multiple SUs, however they have considered MAB framework with iid reward distribution only. In this paper, we consider a similar probabilistic channel access framework as in [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF], however contrary to the previous works, we consider restless Markov MAB, which has been proven to be an NP-hard problem, and we prove that the presented policy achieves logarithmic order regret for restless Markovian rewards. Moreover in the above presented works, upon availability, each channel provides the same reward which is a restrictive hypothesis since it ignores different channel qualities. Moreover, the authors in [START_REF] Wang | Two-dimensional pomdp-based opportunistic spectrum access in time-varying environment with fading channels[END_REF] have modeled the OSA problem with partially observable Markov decision process (POMDP) framework which considers channel quality along with availability statistics to decide about the channel to sense. However, their solution has comparatively an higher complexity and also there is no theoretical guarantee on the convergence property of the proposed policies. On the contrary, the OSA problem is modeled under the MAB framework which turns to be very easy and less complex to implement.

Most of the previous works, [START_REF] Liu | Learning in a changing world: Restless multiarmed bandit with unknown dynamics[END_REF], [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], [START_REF] Kalathil | Decentralized learning for multiplayer multiarmed bandits[END_REF], on restless Markov MAB models a considered fixed positive reward (i.e. expectation of the reward distribution of each channel). In this paper, we consider not only a reward coming from the availability of the channel, which evolves according to a Markov chain, but also a positive random reward iid that we decide to be related to the quality of a channel when the channel is accessed by the user. It is worth mentioning that the distribution of this reward is unknown from the user. Also, an important difference compared to previous approaches, is that the quality reward changes time to time; it is not fixed. Moreover in wireless communication field, the separation of both functionalities, i.e. availability and quality, is necessary for applications where certain level of QoS is required. Hence, by making the engine able to learn on the availability and on the quality, we can choose to emphasize on one or the other criteria.

C. Contributions

Our contributions are to propose single and multi-player policies able to learn on two different criteria, i.e. availability and quality, and to prove the logarithmic order of the regret for these policies. The contributions of this paper are summarized in the following:

• A new version of the quality of service UCB (QoS-UCB), proposed in [START_REF] Modi | QoS driven channel selection algorithm for opportunistic spectrum access[END_REF], for the restless Markov MAB framework is proposed and named RQoS-UCB that takes into account not only the availability but also the quality for rating a channel. This new metric allows not only to opportunistically use the spectrum holes but also maximizing the data rate achieved by the unlicensed users. • A single-user followed by the multi-user version of the algorithm are proposed. The regret bound analysis is provided for the both cases and is proved to be logarithmic over time. • No information exchange or prior agreement between different users is assumed thereby minimizing the communication overhead. In that context we show that the number of collisions is bounded.

D. Paper Structure

Section II introduces the CR model and hypothesis on the restless Markov MAB problem. In Section III, the new distributed RQoS-UCB algorithm taking into account channel availability and quality is presented for the single-user restless Markov MAB problem and the regret law is derived and Section IV extends to the multi-user case. Numerical results are presented in Section V, which validates the efficiency of the proposed distributed RQoS-UCB policy compared to state-of-the-art algorithms in literature. Finally, Section VI concludes the paper.

II. MODEL AND PROBLEM FORMULATION

A. System Model

Let U ≥ 1 be the number of SUs which opportunistically access the spectrum, and K ≥ U be the number of PUs' channels available 1 . We consider that each SU can sense only one channel in each time slot. Moreover SUs operate in a completely uncorrelated manner w.r.t. primary users, hence the actions of individual SU does not affect the PUs policy. A policy is defined as a one-to-one mapping A such as at each time n, a frequency band i ∈ K, K = {1, • • • , K}, is selected:

A : N -→ K n -→ i
Each band is modeled as an aperiodic, irreducible and discrete time Markov chain with finite state space S i = {q 0 , q 1 }, where q 0 and q 1 are the states occupied and free respectively, and the transition probability matrix of the i-th band is

P i = { p i kl , k, l ∈ S i }
. Markov chains are independent from each other and π i is the stationary distribution of the i-th Markov chain with π i q (n) = π i q ∀n. S i,j (n) denotes the state observed from band i by SU j, ∀j ∈ U at time n. The reward achieved in state q ∈ S i from band i by SU j at time n is r i,j q (n) ∈ R. Without loss of generality, one can consider that r i,j q (n) = S i,j (n). The mean reward µ S i,j associated with state S i,j of the i-th band and j-th user under stationary distribution π i is given by: µ S i,j = ∑ q∈S i,j r i,j q π i q .

Furthermore, the band quality is rated according to the interference temperature recorded on it. We assume that the band quality in a given state is stationary in the wide sense, meaning that its statistical properties, i.e. first and second moment, are not evolving over time, but the instantaneous value R i,j q (n) may vary.

G i,j q (T i,j (n)) = 1 T i,j (n) ∑ T i,j (n) k=1 R i,j
q (k) denotes the empirical mean of quality observations R i,j q collected from band i by SU j in state q and T i,j (n) denotes the total number of times band i has been sensed up to time n by SU j. The global mean reward, i.e. taking into account the quality as well as the state of each band i, is defined as:

µ R i,j = ∑ q∈S i,j
G i,j q r i,j q π i q .

(1)

Without loss of generality, let us consider that

µ R 1 > µ R i > µ R K , ∀ i ∈ {2, • • • , K -1}.
It is important to note that the optimal bands are the ones having the highest global mean reward, i.e. {µ R j } ∀j∈U . The global mean reward can be seen as the expectation of the reward function of the user j in band i, i.e. G i,j q r i,j q . This function can be seen as a weighting of the channel availability reward, i.e. r i,j q , by a random variable reflecting its quality, i.e. G i,j q . Other combinations of quality and availability might be envisaged but fall out of the scope of this paper and are left for further works.

Let ALOHA-like protocol be considered under which if two or more SUs transmit in the same channel then none of the transmissions are successful, and no collision avoidance mechanisms are considered2 . C j o (i, n) is the collision indicator function at the n-th slot at channel i for SU j. At the end of each slot n, each SU j receives the reward r i,j q (n) and R i,j q (n). Under this model, we are interested in designing a policy A, maximizing the expected number of successful transmissions with good quality in the long run. Let Φ A (n) be the regret and defined as the reward loss after n slots for U SUs and policy A. In the ideal scenario, we assume that the channel mean reward statistics µ R i are known a priori by a central agent and it selects U optimal channels for U SUs.

We are interested in minimizing the regret Φ A (n) associated with the learning and access scheme, defined as:

Φ A (n) = U ∑ j=1 nµ R j - U ∑ j=1 E [ n ∑ t=1 G A(t,j) q A(t,j) (t)r A(t,j) q A(t,j) (t) ] (2)
where the expectation E is taken over the states and quality. Let q A(t,j) being the state observed by SU j under the policy A at time t. Frequency bands whose mean reward is strictly less than {µ R j } ∀j∈U are referred as suboptimal frequency bands.

B. Bandit Theoretical Model of Wireless Network

A centralized primary network is considered where a radio access point serves K frequency bands. In the same cell, Tx-Rx SU pairs are considered. The CR system seeks to interweave the SU's signals with the PUs transmissions in the set of frequency bands. Due to the frequency reuse factor and partial utilization of the frequency band i by PUs in the neighboring cells, the interference level is not the same for all bands which leads to a varying quality according to the band considered. This noise process is considered as stationary in wide sense.

A slotted frame structure for CR is considered. During the frame duration, i.e. T total , SUs sense the channel during T sens , learn during T lear , and transmit (or not depending on the result of the channel sensing) during T trans . The aim of the learning policy is to decide which band should be explored in the next time slot and can be implemented in parallel with transmission requiring a very small time compared to the sensing and transmission duration [START_REF] Melián-Gutiérrez | Upper confidence bound learning approach for real HF measurements[END_REF].

At the current time slot, SUs sense the spectrum on the i-th frequency band and utilize it for communication only when there is no PU. The spectrum sensing part is error-prone but the imperfect sensing has no effect on the optimal solution achieved by algorithms [START_REF] Jouini | Upper confidence bound algorithm for opportunistic spectrum access with sensing errors[END_REF]. The discrete received signal at SUs Rx can be written according to both hypothesis: i.e. H 0 band i is used by a PU and H 1 band i is vacant:

H 0 : y i q0 [m] = p i [m] + u i [m], (3)
H 1 : y i q1 [m] = u i [m] (4
i [m]| 2 ] = σ 2
u,i and independent from the primary users' signal p i . We remind that u i [m] counts for other cells interference and background noise. Theoretically in OSA context, SUs should transmit only when no PU occupies band i. However, they may miss the detection of a primary user and transmit anyway.

1) Energy Detector (ED) as state and quality information metric: ED senses band i and measures a power level. If the measured power level is above a certain threshold υ, ED decides the band is occupied and if the power level is below υ the band is decided to be available. Moreover, in our work, the measured spectrum level is recorded and used as a quality information metric for learning policy. Indeed, instead of having only a binary variable at the output of ED, we get a soft-metric representing the measured power level which will be used later to rate the band quality. Let F s being the sampling frequency at the receiver, then N s = T sens F s is the number of samples acquired during the sensing phase. User j measures the power in the i-th band as

P i,j q = 1/N s ∑ Ns m=1 ∥y i,j q [m]∥ 2 .
The false alarm probability P f (υ, N s ) under the threshold υ and number of samples N s is given as

P f (υ, N s ) = Q (( υ/σ 2 u,i -1 ) √ N s ) [21], Q(•) being the Gaussian Q-function.
The band with the highest quality has the lowest interference plus noise power level. Hence, the quality metric should be inversely proportional to the ED output, i.e. R i,j q = 1/ ( P i,j q + c e

)
where c e is a constant added to the received power in order to avoid taking the inverse of very small numbers. The proposed algorithms in this paper is able to take into account quality metric related to soft output of any spectrum sensing detector [START_REF] Yucek | A survey of spectrum sensing algorithms for cognitive radio applications[END_REF]. There have been some attempts in [START_REF] Bkassiny | Wideband spectrum sensing and non-parametric signal classification for autonomous self-learning cognitive radios[END_REF], [START_REF] Wanuga | Online learning for spectrum sensing and reconfigurable antenna control[END_REF], to consider the energy detector soft output as a reward for general reinforcement learning algorithms, but they lack from significant theoretical guarantee and a relation with achievable throughput.

2) Achievable Throughput Analysis: The SU's average achievable throughput Ξ i,j in the i-th frequency band is given by the sum of the achievable throughput under H 0 and the achievable throughput under H 1 , which can be written as:

Ξ i,j (υ, N s ) = Ξ i,j q1 (υ, N s ) + Ξ i,j q0 (υ, N s ), (5)
where Ξ i,j q1 and Ξ i,j q0 are defined as:

Ξ i,j q1 (υ, T sens ) = T total -T sens T total π i q1 C ( Γ i,j 1 ) (1 -P f (υ, N s )) Ξ i,j q0 (υ, T sens ) = T total -T sens T total π i q0 C ( Γ i,j 0 ) (1 -P d (υ, N s ))
where C (Γ) denotes the achievable rate with SINR Γ, i.e.

C (Γ) = log 2 (1 + Γ). Hence, C ( Γ i,j 1 )
is the achievable rate in the i-th band without any PU and C

( Γ i,j 0 )
is the achievable rate in the i-th band when a PU has not been detected. The achievable throughput under hypothesis H 1 is hence C

( Γ i,j 1 )
multiplied by the probability band i is available, i.e. π i q1 , and the probability not to generate a false alarm, i.e. 1 -P f (υ, N s ). On the other hand, the achievable throughput under H 0 is C

( Γ i,j 0 )
weighted by the probability band i is occupied, i.e. π i q0 and the miss detection probability i.e. P md (υ, N s ) = 1 -P d (υ, N s ) where P d (υ, N s ) is the probability of correct detection. Both rates are weighted by the effective transmission time ratio, i.e. Ttotal-Tsens Ttotal .

III. SINGLE USER RESTLESS MARKOVIAN MAB PROBLEM

Let us consider in a first place that our secondary network only contains 1 transceiver pair. We construct an algorithm called RQoS-UCB, as shown in Algorithm 1, and prove that it achieves logarithmic order regret uniformly over time same as original QoS-UCB policy for rested problem [START_REF] Modi | QoS driven channel selection algorithm for opportunistic spectrum access[END_REF]. On a way to solve the restless MAB problem is to apply regenerative cycle algorithm (RCA), [START_REF] Gai | Online learning for combinatorial network optimization with restless markovian rewards[END_REF], [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], or restless UCB (RUCB), [START_REF] Liu | Learning in a changing world: Restless multiarmed bandit with unknown dynamics[END_REF], policies and ignore the separate weight for channel quality and availability criteria. In this paper, we assume that channel set consists in different transmission quality, and also a CR may have certain preferences, i.e., quality or availability or both, for channel selection. Unlike the rested problem dealt with in [START_REF] Modi | QoS driven channel selection algorithm for opportunistic spectrum access[END_REF], the Markov chains of arms evolve even if they are not observed. Table I summarizes the notation we use for RQoS-UCB algorithm, where the dependence on index j vanishes for 1 SU.

RQoS-UCB operates in a block structure as shown in Fig. 1. For each arm, a state ζ i is chosen and defined as a regenerative state. Each block is further divided into three sub-blocks (SBs), i.e. SB1, SB2 and SB3. SB1 consists in all time slots from the start of the block to right before the first visit to ζ i , SB2 contains all time slots from the first visit to ζ i up to but excluding the second visit to ζ i where state and quality of the band are recorded, and finally SB3 consists in a single time slot with the second visit to state ζ i . At the end of SB3, the policy index is computed and is compared with the index of other arms and the highest one gives the next arm to play, e.g. arm K for the second block in Fig. 1. Note that the sub-block division is relevant for regret analysis purpose. Indeed, all SB2 blocks are virtually assembled to construct a regenerative cycle of the Markov chains. The newly constructed sample path has exactly the same statistics as the original transition probability matrix P i which translates restless problem into a tractable problem. However, it is important to emphasize that the CR does not run only during SB2 block but also in SB1 and SB3 blocks in which channels are sensed and transmissions are performed, if bands are found free.

Initially, all the channels are observed at least once and ζ i is fixed as a first state observed for each arm, i.e. steps 1 to 3 in Algorithm 1. After the initialization, at the beginning of a new block b, RQoS-UCB selects the channel which maximizes the policy index B i (n 2 , T i 2 (n 2 )) ∀ i ∈ K, step 5, according to three terms:

B i (n 2 , T i 2 (n 2 )) = Si (T i 2 (n 2 )) -Q i (n 2 , T i 2 (n 2 )) + A i (n 2 , T i 2 (n 2 )), ∀i (6)
where Si (T i 2 (n 2 )) being the empirical mean of the states of the i-th band (occupied or free) at time n 2 , defined as:

Si (T i 2 (n 2 )) = S i (1) + S i (2) + • • • + S i (T i 2 (n 2 )) T i 2 (n 2 )
, ∀i. [START_REF]Sample mean based index policies with O(log n) regret for the multi-armed bandit problem[END_REF] The second term, i.e.

Q i (n 2 , T i 2 (n 2 )
), is computed same as of rested policy:

Q i (n 2 , T i 2 (n 2 )) = βM i (n 2 , T i 2 (n 2 )) log(n 2 ) T i 2 (n 2 ) , ∀i, (8)
where, Algorithm 1 Single SU RQoS-UCB policy

M i (n 2 , T i 2 (n 2 )) = G q1 max (n 2 ) -G i q1 (T i 2 (n 2 )), ∀i,
Input: b = 1, n = 0, n 2 = 0, T i 2 = 0, α, β, A(0), R i q1 (0) ∀ i ∈ K. Output: A(n + 1) 1: for n 2 = b to K do 2:
Initialize policy by sensing each channel for at least one block (i.e. SB1, SB2 and SB3) 3: end for 4: while (1) do 5:

B i (n 2 , T i 2 (n 2 )) = Si (T i 2 (n 2 )) -Q i (n 2 , T i 2 (n 2 )) + A i (n 2 , T i 2 (n 2 )), ∀i 6: A(n) = arg max i B i (n 2 , T i (n 2 )) 7: Sense i = A(n) and Observe S i (n 2 ) 8:
while

S i (n 2 ) ̸ = ζ i do 9: n = n + 1, A(n) = i // Start SB1 sub-block 10:
Sense channel i and Observe S i (n 2 )

11:

end while

12: n = n+1, n 2 = n 2 +1, T i 2 (n 2 ) = T i 2 (n 2 )+1, A(n) = i; // End of SB1, start SB2 13:
Observe current state S i (n 2 ) and update R i q1 (n 2 )

14: Update Si (T i 2 (n 2 )), Q i (n 2 , T i 2 (n 2 )) and A i (n 2 , T i 2 (n 2
)) as of ( 7), ( 8) and ( 9), respectively 15:

while S i (n 2 ) ̸ = ζ i do 16: n = n + 1, n 2 = n 2 + 1, T i 2 (n 2 ) = T i 2 (n 2 ) + 1, A(n) = i; // Start SB2 sub-block 17: Observe current state S i (n 2 ) and update R i q1 (n 2 ) 18: Update Si (T i 2 (n 2 )), Q i (n 2 , T i 2 (n 2 )) and A i (n 2 , T i 2 (n 2
)) as of ( 7), ( 8) and ( 9), respectively 19:

end while

20: b = b + 1, n = n + 1 // Start of SB3 sub-block 21: end while where G i q1 (T i 2 (n 2 )
) and G q1 max (n 2 ) denote the empirical mean of quality observations R i q1 and the maximum expected quality within the set of frequency bands respectively, defined as in Table I. Finally, the bias term A i (n 2 , T i 2 (n 2 )), is defined as

A i (n 2 , T i 2 (n 2 )) = √ α log(n 2 ) T i 2 (n 2 ) , ∀i. (9)
Two coefficients come into play in ( 8) and ( 9), i.e. β and α respectively, and are introduced to balance the tradeoff between exploration and exploitation. Parameter α in [START_REF] Anantharam | Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple playspart ii: Markovian rewards[END_REF] forces the exploration of the other bands to check their availability while the new parameter β forces the algorithm to give some weight to the quality in the index computation.

We first give an upper bound on the total expected number of plays of suboptimal arms in Theorem 1 and then the regret of RQoS-UCB policy in Theorem 2.

Condition 1. All arms are finite-state, irreducible, aperiodic restless Markov chains whose transition probability matrices have irreducible multiplicative symmetrization, and the state of non-played arms evolve. Let, G

i q ≥ 1 πmax+π i q and ∀β ≥ 84S 2 max r 2 max G 2 max π2 max / ( γ min ∆µ R i M min
) .

Theorem 1. Assume all arms follow condition 1. We can upper bound the total expected number of block spent in suboptimal arms as:

E[F i (b(n))|b(n) = b] ≤ 4α log n (∆µ R i ) 2 + |S 1 | + |S i | π min ∞ ∑ t=1 t -2
and the time spent in suboptimal arm:

∑ i∈K (µ R 1 -µ R i )E[T i (n)] ≤ Z 1 log n + Z 2
where,

Z 1 = K ∑ i=2 ( 1 π i min + Ω i max + 1 ) 4α ∆µ R i Z 2 = K ∑ i=2 ( 1 π i min + Ω i max + 1 ) ∆µ R i [ |S 1 | + |S i | π min ∞ ∑ t=1 t -2 ]
Proof: The proof is given in Appendix A.

Theorem 2. Assume all arms follow condition 1, the regret of RQoS-UCB can be bounded by

Φ R (n) ≤ Z 3 log n + Z 4 , ( 10
)
Z 3 = Z 1 + Z 5 and Z 4 = Z 2 + Z 6 + Z 7 Z 5 = K ∑ i=2 4α ( ∆µ R i ) 2 [ µ R i ( 1 + Ω i max ) + µ R 1 Ω 1 max ] Z 6 = K ∑ i=2 [ |S 1 | + |S i | π min ∞ ∑ t=1 t -2 ] [ µ R i ( 1 + Ω i max ) + µ R 1 Ω 1 max ] Z 7 = µ R 1 ( 1 Π min + max i∈{1,...,K} Ω i max + 1
) K and U : Number of arms (channels) and users respectively P i and S i : transition matrix and state space of the Markov chain of channel i {1, • • • , U } and {U + 1, • • • , K}: denotes set of optimal and suboptimal channels S i,j (n): observed state of channel i at time n for SU j r i,j q (n): reward achieved in state q ∈ S i from a band i by SU j at time n R i,j q (n): Instantaneous observed quality of band i by SU j at time n T i (n) = ∑ U j=1 T i,j (n): total number of times band i has been sensed up to time n G i,j q (T i,j (n)): the empirical mean of quality observations R i,j q by SU j G q,j max (n): maximum expected quality within the set by SU j M i,j (n, T i,j (n)):

G q 1 ,j max (n) -G i,j q 1 (T i,j (n)) A(n, j)
channel index which has to be sensed in the next time slot by SU j B i,j (n, T i,j (n)):

policy index for the set of bands K at SU j α and β: exploration coefficients with respect to availability and quality, respectively ζ i,j : state that determines regenerative cycles for band i by SU j n 2 :

total number of time slots spend in SB2 block up to block b. T i,j 2 (n 2 ): total number of time band i is sensed by SU j during SB2 block up to n 2 time. W :

Frame size for multi-user distributed RQoS-UCB policy

C j o (i, n):
indicator of collision at n-th slot at channel i for SU j Rank(j): Rank(j)-th highest entry in B i,j (n, T i (n)), ∀i ∈ K for SU j π i q : stationary distribution for state q of the Markov chain associated with i

µ R i : global mean reward ∆µ R i,j : µ R j -µ R i G j max :
max q∈S i G q,j max π i min and π min : min q∈S i π i q and min i∈K π i min respectively πi q , πmax and rmax: max

{ π i q , 1 -π i q }
, max q∈S i ,i∈K πi q and max q∈S i ,i∈K r i q respectively Smax:

max i∈K |S i |, where S i stands for the cardinality of the state space of arm i M j min and M j max :

min i∈K M i,j ( n, T i,j (n) )
and max i∈K M i,j ( n, T i,j (n) ) respectively γ i , γ min and γmax:

eigenvalue gap of the i-th channel, min i∈K γ i and max i∈K γ i , respectively Ω i k,l : mean hitting time of state l starting from an initial state k for the ith arm.

Ω i max and Ωmax: max k,l∈S i ,k̸ =l Ω i k,l and max i∈{1,••• ,K} Ω i max respectively b(n) and f (n):
total number of completed blocks and frame up to time n n b time at the end of the last completed block b(n) fw(n) and Tw(n):

number of frame and time where any one of the U optimal channel's estimated ranks is wrong

F i,j (b(n)): total number of block in which arm i is played by SU j up to block b(n) E(Co(n)):
expected number of collisions in U optimal channels Υ:

refers to the time required to reach the absorbing state from any initial state S i,j 1 (k): vector of observed states from SB1 of k-th block in which band i is sensed by SU j S i,j 2 (k): vector of observed states from SB2 of k-th block in which band i is sensed by SU j S i,j (k):

vector of observed states from k-th block

S i (j) = [ S i 1 (j), S i 2 (j), ζ i ] X(j):
j-th combined block in which the optimal band is sensed, i.e. X(j) = [ X1 (j), X2 (j), ζ i ] bi,j : total number of joined blocks up to current block b for optimal band i for SU j

TABLE I NOTATION FOR ALGORITHMS 1 AND 2, AND REGRET ANALYSIS

Proof: Proof of Theorem 2 is given in Appendix B.

IV. DISTRIBUTED MULTI-USER LEARNING AND ACCESS POLICY

In this part, we extend the previous approach to the multiusers case and present the multi-user version of RQoS-UCB, sometimes referred as distributed RQoS-UCB policy. If each SU applies naively the single user RQoS-UCB presented in Algorithm 1, then the number of collisions will likely increase since all SUs go for the best channel. Hence, we introduce the so-called channel access rank [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF]. Let assume that each SU j keeps a decreasing ordering set B i,j ∀i ∈ K indexes. For instance, a user having a rank equal to 3, goes to the channel having the third entry in the ordering set of its index. Moreover, suboptimal channels are expected to be played as less as possible, in order not to increase the regret of the system.

Fig. 2 illustrates the functioning of the distributed RQoS-UCB policy for 2 SUs. Let us consider a slotted system with a frame size W , where each SU can be synchronized for their index calculation. Each SU computes its own B i,j index at the end of W if possible, i.e. the sub block SB3 has been encountered for user j in channel i when the frame ends. If not, the computation is delayed to the next frame and user j continues to play the same channel. If two or more users go to the same channel, they collide and then they draw a random number from the channels' set K as their new rank. Letting a player randomizes among its U optimal ranked arms can help alleviate this problem, and focuses to eventually orthogonalize the U players in their choice of arms. This random rank is the same idea that has been used in Anandkumar et al. [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF]. The difference in this paper is that, in Anandkumar et al. [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF] the randomization is performed at each time step a collision occurs under an iid reward model, whereas in our case the randomization is performed at the end of a completed frame of length W and is therefore less frequent as block lengths are random. The reason for this is because with the Markovian reward model, index updates can Fig. 2. Running cycle for 2 different SUs using the distributed RQoS-UCB policy. Actions of user 1 and 2 are listed on top and bottom, respectively only be performed after finishing a regenerative cycle, and switching a channel before a completion of regenerative block will waste the state observations made within that incomplete block. Algorithm 2 summarizes the steps followed by each user. Note that policy operation in each block (containing SB1, SB2 and SB3) follows the same steps as the single user policy detailed in Algorithm 1, but not reported here for the sake of simplicity.

Algorithm 2 Multi-User Distributed RQoS-UCB policy Input: U : Number of users, K: Number of channels, B i,j (n, T i (n)): single-user policy index for each SU j ∈ U and channel i ∈ K, C j o (i, n): collision indicator in channel i for SU j, Rank(j): the Rank(j)-th highest entry in B i,j (n, T i (n)), ∀i ∈ K for SU j Output: A(n, j)

1: if SB3 sub-block observed by SU j in last frame then 2:

Calculate RQoS-UCB policy index B i,j (n, T i (n)) as in Algorithm 1

3:

if C j o (A(n -1, j), n -1) = 1 then 4:
Draw a new Rank(j) randomly from the set

{1, • • • , U } for SU j 5: else 6:
Maintain the same Rank(j) for SU j 7:

end if

8:

A(n, j): channel having Rank(j)-th highest entry in

B i,j (n, T i (n)) 9:
Sense A(n, j) channel 10:

if collision then 11:

C j o (A(n, j), n) ← 1, 12:
E[T i,j (n)] ≤ U ∑ j=1 ( 1 π i min + Ω i max + W ) E [ F i,j (f (n)) ] ≤ U ∑ j=1 ( 1 π i min + Ω i max + W ) [ 4α log n (∆µ R i,j ) 2 + [ |S j | + |S i | π min ∞ ∑ t=1 t -2 ] ] (11)
Proof: Proof of Theorem 3 is given in Appendix C. Let now focus on the analysis of the number of collisions C o (n) in the U optimal channels up to time n. First, we state a bound on the expected number of collisions in the ideal scenario where each SU has perfect knowledge of the mean reward µ R i . In this case, SUs try to reach an orthogonal configuration by uniformly randomizing over the U optimal channels. We use the following Lemma from [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF] and [START_REF] Bóna | A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory[END_REF] to bound the number of collisions arising due to the distributed scenario:

Lemma 1 (Number of collisions under perfect knowledge of µ R i , [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF], [START_REF] Bóna | A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory[END_REF]). The expected number of collisions under the random allocation access scheme in Algorithm 2, assuming that each SU has perfect knowledge of the mean reward µ R i , is given by

E[C o (n)|µ R i ] ≤ U E[Υ] ≤ U [( 2U -1 U ) -1
] .

The above Lemma 1 states that there is a finite number of collisions, bounded by U E[Υ] under the perfect knowledge of µ R i . However as stated before, there are no collisions in a case where all SUs have the perfect knowledge of µ R i in the presence of pre-allocated ranks. Thus, U E[Υ] gives a bound on the additional number of collisions due to absence of preallocated ranks or the lack of direct communication among the SUs to negotiate their rank. To analyze the number of collisions under multi-user distributed RQoS-UCB learning of the unknown µ R i , we show that all are able to learn the correct order of the different with only logarithmic regret, and then we show that only an additional finite number of collisions occurs before reaching collisionfree configuration.

Let define T w (n) and f w (n) as the number of time and frames where any one of the U optimal channel's estimated ranks is wrong under the distributed RQoS-UCB policy.

Lemma 2 (Wrong order of distributed RQoS-UCB index statistics without perfect knowledge of µ R i ). Under the distributed RQoS-UCB scheme in Algorithm 2, the total expected number of frames and time slots for which the estimated B i,j (n, T i,j (n)) indices of distributed RQoS-UCB policy is not in a same order as the mean reward µ R i , is:

E[T w (n)] ≤ U U ∑ a=1 K ∑ b=1 ( 1 π b min + Ω b max + W ) [ 4α log n (∆µ R a,b ) 2 + |S a | + |S b | π min ∞ ∑ t=1 t -2 ] (12)
Proof: Proof of Lemma 2 is achieved by following same argument and steps as of [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF].

With the help of Theorem 3 and Theorem 3 from [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF], the number of time slots spent in the suboptimal channels is also logarithmic, we proceed to prove one of the main results of this paper that the sum regret under multi-user distributed RQoS-UCB policy is logarithmic for restless Markovian reward.

Theorem 4 (Regret analysis of multi-user distributed RQoS-UCB policy). Assume all arms follow condition 1. Then, the regret of distributed RQoS-UCB policy can be bounded by O(log n)

Φ M (n) ≤ X 3 log n + X 4 ( 13
)
where X 3 and X 4 are as stated in Appendix D.

Proof: Proof of Theorem 4 is given in Appendix D. We can note that the presented upper bound does not depend on the regenerative state ζ. Thus, with minimal information about the bands, an SU can still have a logarithmic regret by selecting appropriate exploration coefficients.

V. NUMERICAL ANALYSIS

The performance of distributed RQoS-UCB policy is investigated on a set of 10 bands, and with different number of SUs U ∈ {1, • • • , 10}. Simulation is performed over 10 3 runs, each with a duration about 1000 seconds. QPSK signaling are assumed to be used for PU signals same as [START_REF] Liang | Sensing-throughput tradeoff for cognitive radio networks[END_REF]. The threshold υ is set to have a high detection probability, i.e. P d (υ, T s ) = 0.95 for each channel i. Note that the learning phase represents a very low computational complexity and it may be neglected compared to sensing [START_REF] Melián-Gutiérrez | Upper confidence bound learning approach for real HF measurements[END_REF]. Learning can be done in parallel with the transmission, and so uses no time that could prevent from transmitting frames, and thus be considered as having no impact on bandwidth usage. The exploration coefficients of RQoS-UCB policy are α = 0.25, β = 0.32, like in [START_REF] Modi | QoS driven channel selection algorithm for opportunistic spectrum access[END_REF], and will be used throughout the numerical analysis unless otherwise mentioned.

Table II summarizes the Markov chain parameters modeling the primary network, such as the transition probabilities P i , selected arbitrarily, for each channel on the first and second rows, the vacancy probability π i q1 calculated from P i , the empirical average of the band quality G i q1 calculated as explained in Section II and estimated at Rx and feedback to Tx, on the fourth row and the global mean reward, µ R i calculated with (1) taking into account availability and quality on the fifth row.

A. Single user case

In this Section, only one cognitive transceiver pair is considered trying to exploit the frequency bands of a primary network. Theorems 1 and 2 state that the new metric introduced to rate the quality in the learning phase does not prevent from achieving a logarithmic order regret in the restless case, as it has been also observed but not proved in the rested case [START_REF] Modi | QoS driven channel selection algorithm for opportunistic spectrum access[END_REF]. Due to the application to OSA context, regret analysis is not sufficient to characterize the performance of a learning policy and its ability to provide high reliable data rate is of great interest for telecommunication purposes. Hence, RQoS-UCB policy is compared to several other learning policies found in literature, such as RCA [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], RUCB [START_REF] Liu | Learning in a changing world: Restless multiarmed bandit with unknown dynamics[END_REF] and Q-learning [START_REF] Chen | Stochastic power adaptation with multiagent reinforcement learning for cognitive wireless mesh networks[END_REF] with the optimal exploration parameters suggested by the authors. The classical RCA and RUCB policies are modified such as the unique reward takes into account the combination of availability and quality, i.e. s i,j q = R i,j q r i,j q . Here, r i,j q is the fixed reward selected for channel i and user j in state q, whereas R i,j q is the sample drawn from the fixed iid reward distribution modeling the quality of channel i in state q for user j which is not considered in previous works. The algorithms are also compared with two other policies used as baseline for comparison, i.e. best channel selection and best opportunistic selection policies. The best channel selection policy always selects the optimal channel, i.e. channel with the highest mean reward, and if it is occupied does not transmit, whereas the best opportunistic selection policy is a "god driven" policy which knows a priori all holes in the spectrum as well as the quality associated to. Then at a given time, it exploits the best available channel among all channels to transmit.

Fig. 3(a) presents the percentage of transmission opportunities defined as the ratio between the number of times a policy selects an available channel and the total number of trials. Best opportunistic transmission policy is an upper bound since it possesses a prior information about the spectrum occupancy. The proposed RQoS-UCB but also RCA [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], RUCB [START_REF] Liu | Learning in a changing world: Restless multiarmed bandit with unknown dynamics[END_REF] and Q-learning policies are able to find an optimal channel in the long run, and match the performance of best channel selection policy which always selects a channel having the highest mean reward µ R i . However, the proposed RQoS-UCB policy greatly outperforms other approaches in term of convergence and achieves the higher number of opportunities. This result highlights the benefits of using separate optimization of both availability and quality as we propose with QoS-UCB compared to use a single reward in the UCB policy.

The achievable throughput is investigated in Fig. 3(b) and is computed with [START_REF] Oksanen | A sensing policy based on confidence bounds and a restless multi-armed bandit model[END_REF]. The best opportunistic selection policy logically upper bounds the performance due to the higher number of transmission opportunities it exploits as it can be seen in Fig. 3(a). RQoS-UCB, RCA and Q-learning converge toward the best channel selection because of their ability to learn the band with the best weighted combination of quality and availability but with different convergence speed. RQoS-UCB achieves 87% of the best channel selection policy rate in 1000 frames while more than 4000 frames is needed to achieve less than 87% of this value for RCA and Q-learning policies. Moreover, Fig. 3(b) also depicts that RQoS-UCB outperforms RUCB, in [START_REF] Liu | Learning in a changing world: Restless multiarmed bandit with unknown dynamics[END_REF], in convergence speed which is relatively far from the best channel and the best opportunistic transmission policies. This behavior is probably due to the exploitation-exploration epoch structure which has an exponentially growing length. Hence, if the channel selected is not the optimal one, the policy in [START_REF] Liu | Learning in a changing world: Restless multiarmed bandit with unknown dynamics[END_REF] has difficulties to change in a real communication scenario. On the other hand, the exploration and exploitation are done in the regenerative cycle of a near constant length in our policy, which makes it more suitable to try other channels and hence converge faster to the optimal one. These results also demonstrate the efficiency of controlling the learning phase with two rewards instead of one when channels are characterized by not only their availability but also by their quality. As expected, a simple round-robin technique cannot compete in this scenario.

In Fig. 3(c), the average symbol error rate (SER) is investigated. The SER of RQoS-UCB, RCA and Q-learning converge toward the SER obtained with the best channel selection policy, i.e. 5 • 10 -3 which is the SER of QPSK signaling under 9 dB of SNR, i.e. SNR of band 3. Again, the slower convergence characteristic of Q-learning and RCA, w.r.t. RQoS-UCB, can be emphasized in this figure. This figure also reveals the limitation of the RUCB policy, which likely does not select the band with the best SNR as often as the competing policies, i.e. RQoS-UCB, RCA and Q-learning. We can even notice that the SER of the best opportunistic transmission policy is higher than the RQoS-UCB policy, because it selects a sub-optimal bands to continue transmission when optimal band is occupied. Indeed, the best opportunistic policy is an ideal scheme which exploits at each time the best (in term of quality) available channel, but not necessarily the best one globally. Hence, rather than stopping transmission because the best channel in term of quality is occupied, it goes to a suboptimal (in quality) channel but available. Hence, during the transmission the secondary link experiences a degraded SINR which increases the SER compared to the case where it would have used the optimal channel, however it allows to transmit anyway. In [START_REF] Oksanen | A sensing policy based on confidence bounds and a restless multi-armed bandit model[END_REF], the achievable throughput depends not only on SINR but also on the transmission opportunities exploited. In other words, transmitting on a link with a better SINR leads to an increase of throughput but attenuated by the log function. On the other hand, if the link is of bad quality, this results in a decrease of throughput but marginally due to the log function which can be compensated by using more often this link (if it is more available than another one with a better SINR). This what explains that the best opportunistic policy may have a larger SER than the best channel selection policy but a larger throughput than the latter, Fig. 3(b).

Complexity Analysis

To conclude this first part, a comparative study, in terms of complexity, optimality and convergence speed, between the three learning algorithms, i.e. RQoS-UCB, Q-learning and RCA, has been summarized in Table III. The running time complexity is the number of operation performed and space complexity is related to the storage space (memory) needed to run [START_REF] Koenig | Complexity analysis of real-time reinforcement learning[END_REF]. For the running time complexity, RCA, RQoS-UCB and Q-learning policies behave in O(N K) for large N and K, where N and K are the number of time slots and channels. Time complexity of these algorithms are comparable however, RQoS-UCB performs better than the others as seen in numerical analysis. Time complexity of reinforcement learning is negligible and it is approximately 1% of the sensing time complexity of energy detector that is also required for OSA as stated in [START_REF] Melián-Gutiérrez | Upper confidence bound learning approach for real HF measurements[END_REF]. On the other hand, it is clear that space complexity (expected memory requirement) is the drawback of Q-learning that needs to store all past observations contrary to RCA and RQoS-UCB policies whose complexity is about O(K).

B. Multiple users case

In this part, RQoS-UCB is implemented as presented in Algorithm 2 and compared to distributed RCA, distributed RUCB, and round robin-perfect order (R2PO) policy. Only the single user version of RCA can be found in literature, however multi-user version can be implemented easily following the same structure as distributed RQoS-UCB leading to the distributed RCA in the following. Moreover, the round robinperfect order policy plays each channel consecutively without suffering from collisions, and best channel selection and best opportunistic selection are defined in a same manner as for the single-user policy.

Fig. 4 presents the average percentage of transmission opportunities exploited by the RQoS-UCB, RCA, RUCB, R2PO and the best channel selection policies w.r.t. the number of frames for 2 SUs, Fig. 4(a), and w.r.t. the number of users in Fig. 4(b). The best opportunistic selection policy logically upper bounds the performance. From Fig. 4(a), one can remark that distributed RQoS-UCB policy achieves better performance compared to RCA converging towards the best channel selection policy due to separation of two optimization criteria, i.e. availability and quality, and both significantly outperform R2PO which finds less transmission opportunities even if all SUs have a perfect knowledge about each others' actions. This is also confirmed by Fig. 4(b) where the percentage of transmission opportunities is investigated w.r.t. the number of SUs. The distributed RQoS-UCB outperforms RCA in general, and also percentage of opportunities decreases for both when the number of SUs in the network increases and achieves similar performance than R2PO when 9 secondary transceivers are considered. Note that R2PO is not an interesting solution for CR systems, because requiring a predefined agreement or information exchange among SUs. Hence, the distributed implementation of RQoS-UCB is able to find sufficiently high number of transmission opportunities without additional signaling overhead.

The average achievable throughput is investigated in Fig. 5 w.r.t. the number of frames for 2 users in the network, in Fig. 5(a), and w.r.t. the number of SUs in Fig. 5(b). Distributed RQoS-UCB converges rapidly towards the best channel selection policy while distributed RCA achieves similar performance after a larger learning time. Our policy, RQoS-UCB, outperforms RUCB for all values of the number of users and converges to the same performance than RCA when the number of users is larger than or equal to 6, Fig. 5(b). Note that these particular values are not absolute but depend on the scenario considered and the total number of primary users' channels. Hence, our proposal is not only beneficial for up to 6 SUs but can be greater if the number of channels is higher.

Average SER obtained with several policies is investigated in Fig. 6, w.r.t. the number of frames and 2 SUs in Fig. 6(a), and w.r.t. the number of SUs in 6(b). The SER of distributed RQoS-UCB converges towards the SER obtained with the best channel selection policy. Like in Figs. 3, 4 and5, the distributed RUCB [START_REF] Liu | Learning in a changing world: Restless multiarmed bandit with unknown dynamics[END_REF] and RCA [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF] converge to an optimal band but with a slower convergence speed due to the single reward mixing the availability and quality, and hence the average SER achieved with RUCB and RCA is poorer than the one with RQoS-UCB. We remark in Fig. 6

Transmission opportunities exploited (U =2 users)

Distributed RCA [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF] Round robin -perfect order Distributed RUCB [ RQoS-UCB matches the best channel selection policy which lower bounds the SER of all other strategies when the number of users is varying. The SER of RQoS-UCB increases as the number of users increases, since the number of channels with worse quality increases but is still lower than the SER of RCA and RUCB. At a point, i.e. more than 7 SUs in network, the difference between all learning approaches and round robinperfect order becomes negligible as they finish to select an important proportion of the same channels. Furthermore, if K would be much larger, the number of users at which our policy would offer better performance than round-robin would also be larger.

Fairness in Channel Access

One of the important features of the proposed restless RQoS-UCB policy is that it does not favor one specific user over another in order to access optimal arms. In the proposed distributed RQoS-UCB approach, each user has an equal chance to sense and transmit in any one of the U -optimal channels. Fig. 7(a) illustrates the percentage of opportunities exploited and Fig. 7(b) the optimal arm selection percentage for 4 SUs when K = 10 channels w.r.t. the number of frames. As it can be observed, each user exploits approximately the same amount of transmission opportunities and select the optimal arm more or less the same proportion of time. This demonstrate that the proposed distributed RQoS-UCB scheme is indeed fair in user allocation.

VI. CONCLUSION

This paper has dealt with OSA problem in multi-user infrastructure-less cognitive wireless network. A new machine learning algorithm, called distributed RQoS-UCB, has been proposed to address the multi-user OSA problem modeled as a restless Markov MAB formulation. The proposed policy takes into account a quality information metric instead of only availability for most of algorithms in literature. Moreover, we have proved that our proposed policies achieve a logarithmic order regret uniformly over time for the restless Markov MAB. In cognitive radio applications, the ability to learn on a different criteria than the traditional free or occupied status of a channel is of particular interest in order to improve the QoS of SUs transmissions. Using the soft-output of ED as a quality metric for the sensed band, we have shown that the proposed policies are able to achieve a larger throughput than the stateof-the-art algorithms which suffer from a larger convergence time compared to the proposed policies. The idea proposed in this paper can be used to learn on many other criteria such as energy efficiency or actual SINR on the secondary link and will be investigated in further works. Moreover, our model ignores dynamic traffic at the secondary nodes and extension to a queueing-theoretic formulation is left for future work.

APPENDIX A PROOF OF THEOREM 1

In order to bound the regret, we need to bound the expected number of blocks, E[F i (b)], for any suboptimal band i > 1.

Let l being a positive integer and A(b) the action performed by policy A in block b. n 2 (b) represents total time spent in SB2 block up to block b. Following the steps as in [START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF], the number of blocks a band has been visited up to block b can be expressed as

F i (b) = 1 + b ∑ m=K+1 1 ((A(m) = i)) ( 14
)
F i (b) = l + b ∑ m=K+1 1 (( A(m) = i, F i (m -1) ≥ l )) (15)
= l + b ∑ m=K+1 1 ( B 1 ( T 1 2 (n 2 (m)), n 2 (m)
)

≤ B i ( T 1 2 (n 2 (m)), n 2 (m) ) , F i (m) ≥ l ) (16)
≤ l + b ∑ m=K+1 1 ( ∃ω i : l ≤ ω i ≤ n 2 (m), B i (ω i , n 2 (m)) > µ R 1 ) + 1 (( ∃ω 1 : 1 ≤ ω 1 ≤ n 2 (m), B 1 (ω 1 , n 2 (m)) ≤ µ R 1 )) (17)
where ( 15) comes from the fact that each band has been sensed at least l blocks up to block b. [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF] comes from the reason why suboptimal band i is chosen up to n 2 (m-1) time at the end of block m -1, i.e. the index of an optimal band at block m -1, i.e. B 1 (

T 1 2 (n 2 (m -1)), n 2 (m -1)
)

, is below the index of the suboptimal band i. Moreover ( 16) is upper bounded by [START_REF] Wang | Two-dimensional pomdp-based opportunistic spectrum access in time-varying environment with fading channels[END_REF] because these two conditions are not exclusive. Taking the expectation on both sides and using union bound we get:

E[F i (b)] ≤ l + b ∑ m=K+1 n2(m-1) ∑ ω i =n2(l) P(B i (ω i , n 2 (m)) > µ R 1 ) + b ∑ m=K+1 n2(m-1)
∑

ω 1 =1 P(B 1 (ω 1 , n 2 (m)) ≤ µ R 1 ) ≤ l + n2(b) ∑ t=1 t-1 ∑ ω i =l P(B i (ω i , t) > µ R 1 ) + n2(b) ∑ t=1 t-1 ∑ ω 1 =1 P(B 1 (ω 1 , t) ≤ µ R 1 ) (18)
The summation over t starts from 1 instead of K + 1 because it does not change the validity of the upper bound. Note that channel 1 is optimal in terms of mean reward, µ R 1 , i.e. both in vacancy and quality. G 1 is hence the empirical mean of the quality reward of this channel, it does not mean necessarily that G 1 = G q1 max . Moreover, let's remind that ∆µ

R i = µ R 1 -µ R i . let's choose l = ⌈ 4α ln n (∆µ R i ) 2
⌉ , take expectation on both sides and relaxing the outer sum in [START_REF] Modi | QoS driven channel selection algorithm for opportunistic spectrum access[END_REF] from n 2 (b) to ∞, and proceed from [START_REF] Modi | QoS driven channel selection algorithm for opportunistic spectrum access[END_REF]:

E[F i (b)] ≤ l + ∞ ∑ t=1 t-1 ∑ ω i =l P(B i (ω i , t) > µ R 1 ) + ∞ ∑ t=1 t-1 ∑ ω 1 =1 P(B 1 (ω 1 , t) ≤ µ R 1 ) (19)
Let's start with the first part of ( 19), i.e. P(B i (ω i , t) > µ R 1 ). By writing µ R 1 = µ R i + ∆µ R i and replacing the B i (ω i , t) by its expression, we get

P(B i (ω i , t) > µ R 1 ) = P ( Si (ω i ) - βM i (ω i ) ln(t) ω i + √ α ln(t) ω i > µ R i + ∆µ R i ) (20)
For sake of notational simplicity, let's note

D i (ω i , t) = βM i (ω i ) ln(t) ω i . Moreover, using l = ⌈ 4α ln n (∆µ R i ) 2
⌉ and ω i ≥ l, the third term in [START_REF] Jouini | Upper confidence bound algorithm for opportunistic spectrum access with sensing errors[END_REF] can be upper-bounded by:

√ α ln t ω i ≤ √ α ln t l ≤ √ α ln t(∆µ R i ) 2 4α ln t = ∆µ R i 2
Substituting this last bound into [START_REF] Jouini | Upper confidence bound algorithm for opportunistic spectrum access with sensing errors[END_REF] and because all terms are positive we get

P(B i (ω i , t) > µ R 1 ) ≤ P ( Si (ω i ) -µ R i > ∆µ R i 2 + D i (ω i , t) ) (21)
Let, O i q (t) being the number of times reward r i q associated with state q of arm i has been observed up to time t, hence Si (ω i ) = 1 ω i ∑ q∈S i r i q O i q (ω i ). Following from [START_REF] Liang | Sensing-throughput tradeoff for cognitive radio networks[END_REF]:

P ( Si (ω i ) -µ R i ≥ ∆µ R i 2 + D i (ω i , t) ) = P ( ∑ q∈S i ( -r i q O i q (ω i ) + ω i G i q r i q π i q ) ≤ -ω i ( ∆µ R i 2 + D i (ω i , t) ) ) (22)
Following same steps as of [START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF], [START_REF] Yucek | A survey of spectrum sensing algorithms for cognitive radio applications[END_REF] is upper bounded as:

≤ ∑ q∈S i N h i exp      - ω i ( ∆µ R i 2 +D i (ω i ,t) r i q |S i |G i q πi q ) 2 γ i 28      ( 23
)
where S i is the arm i state space cardinality, πi q = max { π i q , 1 -π i q } and πmax = max i∈K πi q . Moreover, (23) follows from Theorem 3.3 from [START_REF] Lezaud | Chernoff-type bound for finite markov chains[END_REF]

by considering n = ω i , f (X i t ) = 1(S i t =q)-G i q π i q G i q πi q
. The Theorem 3.3 from [START_REF] Lezaud | Chernoff-type bound for finite markov chains[END_REF] conditions are fulfilled if G i q ≥ 1 πmax+π i q . Consider an initial distribution h i as defined in [START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF] and eigenvalue gap γ i for the ith arm, then

N h i = ( h i q π i q , q ∈ S i ) 2 ≤ ∑ q∈S i h i q π i q 2 ≤ 1 π min , ( 24
)
In order to lighten the notation, let us redefine the following variables. G max ≡ G q1 max but the superscript is dropped and r max = max q∈S i ,i∈K r i q . Moreover, let's define M min = min i∈K M i ( ω i ) , ω max = max i∈K ω i and ω min = 1. From [START_REF] Bkassiny | Wideband spectrum sensing and non-parametric signal classification for autonomous self-learning cognitive radios[END_REF],

≤ |S i | π min exp      - ω i ( ∆µ R i 2 +D i (ω i ,t) |S i |r i q G i q πi q ) 2 γ i 28      ≤ S i π min t - ∆µ R i βM min γ min 28S max r 2 max G 2 max π2 max (25)
∑ ω i =l P(B i (ω i , t) ≥ µ R 1 ) ≤ |S i | π min ∞ ∑ t=1 t -2 (26)
where,

β ≥ 84S 2 max r 2 max G 2 max π2 max / ( γ min ∆µ R i M min
) is considered to obtain [START_REF] Bóna | A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory[END_REF].

Similarly, we prove the second part of [START_REF] Melián-Gutiérrez | Upper confidence bound learning approach for real HF measurements[END_REF]:

P(B 1 (ω 1 , t) ≤ µ R 1 ) = P ( S1 (ω 1 ) - βM 1 (ω 1 ) ln t ω 1 + √ α ln t ω 1 ≤ µ R 1 ) (27)
Let, C(ω 1 , t) = √ α ln t ω 1 and D 1 (ω 1 , t) = βM 1 (ω 1 ) ln(t)

ω 1
for notation simplification.

P(B 1 (ω 1 , t) ≤ µ R 1 ) = P ( S1 (ω 1 ) -µ R 1 ≤ -(C(ω 1 , t) -D 1 (ω 1 , t)) ) (28)
Similarly as shown in [START_REF] Bkassiny | Wideband spectrum sensing and non-parametric signal classification for autonomous self-learning cognitive radios[END_REF], we obtain

P ( S1 (ω 1 ) -µ R 1 ≤ -(C(ω 1 , t) -D 1 (ω 1 , t)) ) = P ( ∑ q∈S 1 (r 1 q O 1 q (ω 1 ) -ω 1 G 1 q r 1 q π 1 q ) ≤ -ω 1 (C(ω 1 , t) -D 1 (ω 1 , t)) ) ( 29
) ≤ ∑ q1∈S 1 N h 1 exp ( -w 1 ( C(ω 1 , t) -D 1 (ω 1 , t) ) 2 γ 1 28 ( |S 1 |G 1 q r 1 q π1 q ) 2 ) (30)
where, [START_REF] Bremaud | Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues[END_REF] follows from Theorem 3.3 from [START_REF] Lezaud | Chernoff-type bound for finite markov chains[END_REF] with C(ω 1 , t) -D 1 (ω 1 , t) can be proved to be positive from a certain time. Indeed, C(ω

1 , t) -D 1 (ω 1 , t) = √ ln t w 1 ( √ α -βM 1 ( w 1 ) √ ln t w 1
) and ∃A ∈ N, ∃ϵ > 0 such that ∀t > A, √ ln t w 1 < ϵ. This can be justified by the fact that ln t grows always slower than t and so w 1 which can be viewed as a fraction of t. Using inequalities in [START_REF] Wanuga | Online learning for spectrum sensing and reconfigurable antenna control[END_REF]

P(B 1 (ω 1 , t) ≤ µ R 1 ) ≤ S 1 π min t - γ min ( α-2 √ αβM 1 (ω 1 ) ) 28(Smax Gmaxrmax πmax) 2 ≤ S 1 π min t - γ min (α-2 √ αβMmax ) 28(Smax Gmaxrmax πmax) 2 (32)
where

M max = max i∈K M i ( ω i )
and where from (31) to (32) the second term in t is upper bounded by 1. By choosing α such that

γmin(α-2 √ αβMmax) 28(SmaxGmaxrmax πmax) 2 ≥ 3 we obtain P(B 1 (ω 1 , t) ≤ µ R 1 ) ≤ S 1 π min t -3 (33)
Replacing (33) into second part of ( 19), we get

∞ ∑ t=1 t-1 ∑ ω 1 =1 P(B 1 ( ω 1 , t ) ≤ µ R 1 ) ≤ |S 1 | π min ∞ ∑ t=1 t ∑ ω 1 =1 t -3 = |S 1 | π min ∞ ∑ t=1 t -2 (34)
Then the bound follows from combining [START_REF] Bóna | A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory[END_REF] and (34):

E[F i (b(n))|b(n) = b] ≤ 4α ln n (∆µ R i ) 2 + |S 1 | + |S i | π min ∞ ∑ t=1 t -2 (35)
The SB2 block begins with the state ζ i and ends with a return to the same state. The total number of plays of sub-optimal arm i at the end of block b(n) is estimated by considering the observations acquired in: i) the total number of plays of sub-optimal arm i during SB2 sub-block (upper bounded by 1 π i min ), ii) the total number of plays in SB1 before entering in SB2 (upper bounded by Ω i max ), and iii) one more play during SB3. Thus, we have

E [ T i (n) ] ≤ ( 1 π i min + Ω i max + 1 ) E [ F i (b(n)) ] Thus, ∑ i∈K (µ R 1 -µ R i )E[T i (n)] ≤ Z 1 ln n + Z 2 ,
where,

Z 1 = ∑ i:µ R i <µ R 1 ( 1 π i min + Ω i max + 1 ) 4α ∆µ R i Z 2 = ∑ i:µ R i <µ R 1 ( 1 π i min + Ω i max + 1 ) ∆µ R i [ |S 1 | + |S i | π min ∞ ∑ t=1 t -2
Φ R (n) = nµ R 1 -E [ n ∑ t=1 G A(t) q A(t) (t)r A(t) q A(t) (t) ] Φ R (n) = µ R 1 E ζ [n b ] -E ζ   n b ∑ t=1 r A(t) q A(t) G A(t) q A(t)   + µ R 1 E ζ [n -n b ] -E ζ   n ∑ t=n b +1 r A(t) q A(t) G A(t) q A(t)   = { µ R 1 E ζ [n b ] - K ∑ i=1 µ R i E ζ [ T i (n) ] } + K ∑ i=1 µ R i E ζ [ T i (n) ] -E ζ   n b ∑ t=1 r A(t) q A(t) G A(t) q A(t)   + µ R 1 E ζ [ n -n b ] -E ζ   n ∑ t=n b +1 r A(t) q A(t) G A(t) q A(t)   (36)
First difference in (36) is bounded logarithmically with the help of Theorem 1 as:

µ R 1 E ζ [n b ] - K ∑ i=1 µ R i E ζ [ T i (n) ] ≤ K ∑ i=2 ( µ R 1 -µ R i ) E ζ [ T i (n) ] ≤ Z 1 ln n + Z 2 (37)
We have to bound only the two remaining differences in (36). We can bound second difference in (36) by following same steps as of Theorem 2 in [START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF], as:

K ∑ i=1 µ R i E ζ [ T i (n) ] -E ζ   n b ∑ t=1 r A(t) q A(t) G A(t) q A(t)   ≤ K ∑ i=2 µ R i (Ω i max + 1)E ζ [ F i (b(n)) ] + µ R 1 Ω 1 max K ∑ i=2 E ζ [ F i (b(n)) ] (38)
by following same steps as of Theorem 2 in [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF]. Finally, the last part in (36) is bounded as:

µ R 1 E ζ [ n -n b ] -E ζ   n ∑ t=n b +1 r A(t) q A(t) G A(t) q A(t)   ≤ µ R 1 ( 1 π min + max i∈{1,...,K} Ω i max + 1 ) . ( 39
)
From ( 37), ( 38), (39) and Theorem 1, the upper bound on the regret of RQoS-UCB policy is:

Φ R (n) ≤ Z 1 ln n + Z 2 + K ∑ i=2 µ R i (Ω i max + 1)E ζ [ F i (b(n)) ] + µ R 1 Ω 1 max K ∑ i=2 E ζ [F i (b(n))] + µ R 1 ( 1 π min + max i∈{1,...,K} Ω i max + 1 ) ≤ Z 3 ln n + Z 4
where Z 1 , Z 2 , Z 3 , Z 4 , Z 5 , Z 6 and Z 7 are as stated in Theorems 1 and 2 and obtained by identification with previous quantities and the proof is complete.

APPENDIX C PROOF OF THEOREM 3

The total number of frames f (n) up to time n for which the distributed RQoS-UCB policy suggested suboptimal arms i to sense is bounded in the same way as for the RQoS-UCB policy in a single-user restless Markov MAB setting. For convenience, let T i (n) := ∑ U j=1 T i,j (n) and ∑ K i=1 T i (n) = nU , since each SU selects at least one channel to sense in each slot and there are U SUs. Let, ∀j, i : j ∈ {1, • • • , U } and i ∈ {U + 1, • • • , K} denote the set of optimal and suboptimal channel respectively. Following the same steps as in [START_REF] Kalathil | Decentralized learning for multiplayer multiarmed bandits[END_REF], [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF], the total expected number of blocks E

[ F i,j (f (n)) ]
up to frame f (n) for which SU j implementing distributed RQoS-UCB policy selected suboptimal channels i can be bounded as:

E [ F i,j (f (n)) ] = P [ B j ( f j (n), n ) ≤ B i ( f i (n), n )] ≤ U ∑ j=1 P [ B j ( f j (n), n ) ≤ B i ( f i (n), n )]
For one user, Theorem 1 gives the expected number of blocks used to sense a suboptimal band:

E [ F i,1 (b(n)) ] = n ∑ t=1 1 ( B 1 ( f 1 (t), t ) ≤ B i ( f i (t), t )) ≤ 4α ln n (∆µ R i ) 2 + [ |S 1 | + |S i | π min ∞ ∑ t=1 t -2
] Thus, we have for U optimal channels for SU j:

E [ F i,j (f (n)) ] ≤ U ∑ j=1 [ 4α ln n (∆µ R i,j ) 2 + [ |S j | + |S i | π min ∞ ∑ t=1 t -2 ]]
The total number of senses of the suboptimal channel i at the end of the frame f (n) is estimated by considering the observations acquired during i) the entire block duration (i.e. SB1, SB2 and SB3), and ii) after the end of SB3 and before finishing of current frame f (n) within the fixed time slot W . Thus, we have

E [ T i,j (n) ] ≤ U ∑ j=1 ( 1 π i min + Ω i max + W ) [ 4α ln n (∆µ R i,j ) 2 + [ |S j | + |S i | π min ∞ ∑ t=1 t -2 ]] APPENDIX D PROOF OF THEOREM 4 Let {1, • • • , U } and {U + 1, • • • , K}
denote the set of optimal and suboptimal channels, respectively, and n b is the time at the end of the last completed block b(n) as detailed in Fig. 1. Following the same spirit as in the proof of Theorem 2, we have

Φ M (n) = U ∑ j=1 nµ R j - U ∑ j=1 E [ n ∑ t=1 G A(t),j q A(t) (t)r A(t),j q A(t) (t) ] =    E ζ [n b ] U ∑ j=1 µ R j - U ∑ j=1 K ∑ i=1 µ R i E ζ [ V i,j (n) ]    + { U ∑ j=1 K ∑ i=1 µ R i E ζ [ V i,j (n) ] - U ∑ j=1 E ζ   n b ∑ t=1 r A(t),j q A(t) G A(t),j q A(t)   } +    E ζ [n -n b ] U ∑ j=1 µ R j - U ∑ j=1 E ζ   n ∑ t=n b +1 r A(t),j q A(t) G A(t),j q A(t)      (40)
where V i,j (n) is the total number of times where an SU j is the only one to sense and access the channel i up to time n.

Working with the first part of (40) we have:

   E ζ [n b ] U ∑ j=1 µ R j - U ∑ j=1 K ∑ i=1 µ R i E ζ [ V i,j (n) ]    ≤ U ∑ i=1 µ R i ( E ζ [n b ] -E ζ [ V i (n) ]) ≤ µ R 1 ( U E ζ [n b ] - U ∑ i=1 E ζ [ V i (n) ] ) (41) = µ R 1 ( U E ζ [n b ] + E ζ [C o (n)] - U ∑ i=1 E ζ [ T i (n) ] ) ≤ µ R 1 ( E ζ [C o (n)] + K ∑ i=U +1 E ζ [ T i (n b ) ] ) (42) ≤ µ R 1 ( U (E[Υ(U, U )] + 1) E[T w (n)] + K ∑ i=U +1 E ζ [ T i (n) ] ) (43)
where in (41), we use the fact that

E ζ [ V i (n) ] = U ∑ j=1 E ζ [ V i,j (n) ] because of V i (n) < E ζ [n b ],
since the total number of time a unique SU occupies the channel i is at most E ζ [n b ]. In (42), we use the fact that the total number of collisions in U optimal channels is defined as

C o (n) = U ∑ i=1 ( T i (n) -V i (n) )
. Moreover, in (42), we have

U E ζ [n b ] = ( U ∑ i=1 T i (n b ) + K ∑ i=U +1 T i (n b )
)

, and

E ζ [ T i (n) ] ≥ E ζ [ T i (n b ) ]
. Finally (43) is achieved by applying Theorem 3 and Theorem 3 from [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF].

Concerning the second part of (40), we can upper bound as shown in (44) at the top of next page, where the first and the

U ∑ j=1 K ∑ i=1 µ R i E ζ [ V i,j (n) ] - U ∑ j=1 E ζ   n b ∑ t=1
r A(t),j q A(t) G A(t),j q A(t)

  ≤    U ∑ j=1 U ∑ i=1 µ R i E ζ [ V i,j (n) ] - U ∑ j=1 U ∑ i=1 ∑ q∈S i r i q G i q E ζ   F i,j (f (n)) ∑ k=1 ∑ S(t)∈S i,j (k) 1 (S(t)=q)      + { U ∑ j=1 K ∑ i=U +1 µ R i E ζ [ V i,j (n) ] - U ∑ j=1 K ∑ i=U +1 ∑ q∈S i r i q G i q E ζ   F i,j (f (n)) ∑ k=1 ∑ S(t)∈S i,j 2 (k) 1 (S(t)=q)   } +    U ∑ i=1 ∑ q∈S i r i q G i q E ζ [C o (n)] + K ∑ j=1 E ζ [C o (n)] K ∑ i=U +1 ∑ q∈S i r i q G i q    (44)
second part of (44) are the rewards collected in optimal and suboptimal arms separately. The last part is the reward loss due to the collisions in optimal and suboptimal channels, where

E ζ [C o (n)]
is the expected number of collisions in optimal channels. Let us start with the first part of (44) and following the same reasoning than in [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], we have:

E ζ [ bi,j (n)] ≤ K ∑ k=U +1 E ζ [F k,j (f (n))]. (45)
where, { bi,j } is the total number of the joined blocks, and is always less than or equal to the total number of discontinuities. Thus, each successive combined block Xi,j can be separated into two sub-blocks: i) Xi,j 1 consisting in the states observed from the beginning of Xi,j (empty if the first state is ζ i,j ) to the state right before observing ζ i,j , and ii) Xi,j 2 consisting in the rest of Xi,j .

Therefore, the first part of (44) can be upper bound as shown in (48) at the top of next page, where (46) comes from counting the rewards in two different sub-blocks SB1 and SB2. The inequality in (48) is obtained by observing

that E ζ [ ∑bi,j (n) k=1 | Xi,j 2 (k)| ] ≤ 1 π i ζ E ζ [ bi,j (n) ] in SB2 and E ζ [ ∑bi,j (n) k=1 | Xi,j 1 (k)| ] ≤ Ω i max E ζ [ bi,j (n) ] in SB1
. Since rewards are positive, the last part of (46) is larger than 0, and applying Lemma 2 from [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], [START_REF] Bremaud | Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues[END_REF] to the second part of (46).

The second part of (44) can be upper bound as shown:

≤ U ∑ j=1 K ∑ i=U +1 µ R i E ζ [ T i,j (n) ] - U ∑ j=1 K ∑ i=U +1 µ R i π i ζ E ζ [ F i,j (f (n)) ] = U ∑ j=1 K ∑ i=U +1 µ R i ( Ω i max + W ) E ζ [ F i,j (f (n)) ] (49)
where (49) comes from V i,j (n) ≤ T i,j (n), and applying Lemma 2 from [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], [START_REF] Bremaud | Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues[END_REF]. (49) is obtained with Theorem 3. Now we bound the last part of (44) in (50):

≤ E ζ [C o (n)] [ U ∑ i=1 µ R i π i min + K K ∑ i=U +1 µ R i π i min ] ≤ [ K 2 -KU + U ] µ R 1 π min U (E[Υ(U, U )] + 1) E[T w (n)] (50)
where (50) follows from Theorem 3 and Theorem 3 from [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF]. Combining (50), ( 49) and ( 48) into (44), we immediately upper bound (44) as (51):

U ∑ j=1 K ∑ i=1 µ R i E ζ [ V i,j (n) ] -E ζ [ U ∑ j=1 n b ∑ t=1
r A(t),j q A(t) G A(t),j q A(t) ]

≤ U ∑ j=1 U ∑ i=1 µ R i Ω i max K ∑ K=U +1 E ζ [F k,j (f (n))] + U ∑ j=1 K ∑ i=U +1 µ R i ( Ω i max + W ) E ζ [ F i,j (f (n)) ] + [ K 2 -KU + U ] µ R 1 π min U (E[Υ(U, U )] + 1) E[T w (n)] (51)
The last part of (40) is bounded as:

E ζ [n -n b ] U ∑ j=1 µ R j -E ζ [ U ∑ j=1 n ∑ t=n b +1
r A(t),j q A(t) G A(t),j q A(t) ]

≤ U ∑ j=1 µ R j ( 1 π ζ + Ω max + W ) (52)
Combining (43), (51), (52) and using Lemma 2 and Theorem 3, the upper bound on the regret Φ M (n) of the multi-user distributed RQoS-UCB policy is obtained as:

Φ M (n) ≤ X 3 ln n + X 4 X 3 = X 1 + X 5 and X 4 = X 2 + X 6 + X 8 X 1 = ( [ K 2 -KU + U ] π min + 1 ) µ R 1 U 2 ( E[Υ(U, U )] + 1
) U ∑ a=1 K ∑ b=1 4α ∆µ R a,b X 9 X 2 = ( [ K 2 -KU + U ] π min + 1 ) µ R 1 U 2 ( E[Υ(U, U )] + 1
) U ∑ a=1 K ∑ b=1 [ |S a | + |S b | π min ∞ ∑ t=1 t -2 ] X 9 X 5 = K ∑ i=U +1 U ∑ k=1 4α ( ∆µ R i,k ) 2 X 7 U ∑ j=1 U ∑ i=1 µ R i E ζ [ V i,j (n) ] - U ∑ j=1 U ∑ i=1 ∑ q∈S i r i q G i q E ζ   F i,j (f (n)) ∑ k=1 ∑ S i,j t ∈S i (k) 1 (S i,j t =q)   ≤ U ∑ j=1 U ∑ i=1 ∑ q∈S i r i q G i q π i q E ζ   bi,j (n) ∑ k=1 | Xi,j 2 (k)|   - U ∑ j=1 U ∑ i=1 ∑ q∈S i r i q G i q E ζ   bi,j (n) ∑ k=1 ∑ S(t)∈ Si,j 2 (k) 1 (S(t)=q)   + U ∑ j=1 U ∑ i=1 ∑ q∈S i r i q G i q π i q E ζ   bi,j (n) ∑ k=1 | Xi,j 1 (k)|   - U ∑ j=1 U ∑ i=1 ∑ q∈S i r i q G i q E ζ   bi,j (n)
≤ U ∑ j=1 U ∑ i=1 µ R i π i ζ E ζ [ bi,j (n) ] - U ∑ j=1 U ∑ i=1 µ R i π i ζ E ζ [ bi,j (n) ] + U ∑ j=1 U ∑ i=1 µ R i Ω i max E ζ [ bi,j (n) ] -0 (47) < U ∑ j=1 U ∑ i=1 µ R i Ω i max K ∑ K=U +1 E ζ [F k,j (f (n))] (48)
X 6 = K ∑ i=U +1 U ∑ k=1 [ |S k | + |S i | π min ∞ ∑ t=1 t -2 ] X 7 X 7 =   µ R i ( W + Ω i max ) + U ∑ j=1 µ R j Ω j max + µ R 1 X 9   X 8 = U µ R 1 ( 1 π ζ + Ω max + W ) X 9 = ( 1 π ζ + Ω max + W )

Fig. 1 .

 1 Fig. 1. Example of block (i.e. SB1, SB2 and SB3 sub-block) operation of RQoS-UCB policy. At the end of block 1, RQoS-UCB policy computes index based on the observations collected in SB2 block, finds a channel having highest the index among the set of channels K, and moves to channel (for example K) with the highest index for block 2.

16 :

 16 A(n, j) = A(n -1, j) 17: Follow on SB1 and SB2 block same as Algorithm 1 18: end if We now present a logarithmic upper bound on the number of time one of the suboptimal channel i ∈ {U + 1, • • • , K} is sensed by one of the U SUs employing the same distributed RQoS-UCB policy 3 . Theorem 3 (Time spent in suboptimal channels under multi--user distributed RQoS-UCB policy). Assume all arms follow condition 1. Under the distributed RQoS-UCB scheme, total time spent by any SU j ∈ {1, • • • , U } in any suboptimal channel i ∈ {U + 1, • • • , K} is given by:

Fig. 4 .

 4 Fig. 4. Opportunities transmission percentage for 2 SUs w.r.t. the number of frames a) and w.r.t. the number of SUs operating in the primary network b).

Fig. 5 .

 5 Fig. 5. Average achievable throughput for 2 SUs w.r.t. the number of frames a) and w.r.t. the number of SUs operating in the primary network b).

Fig. 6 .

 6 Fig. 6. Average SER for 2 SUs w.r.t. the number of frames a) and w.r.t. the number of SUs operating in the primary network b).

Fig. 7 .

 7 Fig. 7. Fairness analysis for 4 SUs implementing RQoS-UCB policy w.r.t. the number of frames.

  regenerative states are denoted by ζ = [ζ 1 , • • • , ζ K ]. The expectation w.r.t. the modified sample path is defined as E ζ . Let n b be the time at the end of the last completed block b(n) for all SUs.

TABLE II STATE

 II TRANSITION PROBABILITIES, MEAN AVAILABILITY, EMPIRICAL MEAN QUALITY AND GLOBAL MEAN REWARD.

							channel (i)	1		2	3	4	5	6	7	8	9	10
							p i q 0 q 1 p i q 1 q 0 π i q 1 G i q 1 µ R i	0.3 0.7 0.3 0.67 0.31	0.65 0.75 0.35 0.25 0.65 0.75 0.64 0.79 0.77 0.6 0.4 0.6 0.48 0.60 0.47	0.8 0.2 0.8 0.70 0.80 0.67 0.63 0.4 0.2 0.65 0.6 0.8 0.35 0.4 0.2 0.65 0.58 0.33 0.26 0.46	0.45 0.35 0.55 0.65 0.45 0.35 0.64 0.79 0.39 0.29
			100	Percentage of transmission opportunities exploited
	Percentage of transmission opportunities		20 30 40 50 60 70 80 90 10							RCA [11] Round Robin Q-learning [35] RUCB [10] RQoS-UCB Best channel selection Best oppo. Selection
			0
			0	1000	2000	3000	4000	5000	6000	7000	8000	9000 10000
							Number of Frames
			1.8	Cumulative Achievable Throughput for Single SU Terminal
	Cumulative Achievable Throughput (bit/sec/Hz)	0.4 0.6 0.8 1 1.2 1.4 1.6							RCA [11] Round Robin Q-learning [35] RUCB [10] RQoS-UCB Best channel selection Best oppo. selection
			0.2
			0	1000	2000	3000	4000	5000	6000	7000	8000	9000 10000
							Number of Frames
				(b) Achievable throughput w.r.t. the number of frames
		0.06				Symbol Error Rate
										RCA [11]
										Round Robin
		0.05							Q-learning [35]
										RUCB [10]
	Symbol Error Rate (SER)	0.02 0.03 0.04							RQoS-UCB Best channel selection Best oppo. selection
		0.01
			0
			0	1000	2000	3000	4000	5000	6000	7000	8000	9000 10000
							Number of Frames

(a) Opportunities w.r.t. the number of frames (c) Symbol error rate (SER) w.r.t. the number of frames Fig. 3. Percentage of transmission opportunities exploited, achievable throughput and SER for single SUs w.r.t. the number of frames.

When U ≥ K all channels need to be accessed to avoid collisions and hence learning makes less sense.

The effect of employing CSMA-CA is not taken into an account here although the use of CSMA-CA increases spectrum usage and consecutively decreases the regret, thus, the bound we derive in this paper is applicable.

Note that the upper bound on E[T i,j (n)] is still valid even if other SUs use a different policy than distributed RQoS-UCB. However on the contrary, we need to ensure that every SU must implement the same random access mechanism in order to analyze the expected number of collisions

This work has received a French government support granted to the CominLabs excellence laboratory and managed by the National Research Agency in the "Investing for the Future" program under reference No. ANR-10-LABX-07-01. The authors would also like to thank the Region Bretagne, France, for its support of this work.

N.