Keywords: Opportunistic Spectrum Access, Multi-Armed Bandit, Priority Dynamic Access xix Acronyms ADC Analog to Digital Converter AMPS Analog Mobile Phone Service

Since 1990's, the demand on wireless devices, mobile and wireless networks, has experienced unprecedented growth which makes the frequency bands more and more crowded. Several studies, initiated by the Federal Communications Commission (FCC) in the United States (US), have shown that the frequency bands are not well used: Some frequency bands are overlapped while others underutilized. The Opportunistic Spectrum Access (OSA) in Cognitive Radio (CR) represents one of several proposed solutions to tackle the scarcity and enhance the efficiency use of the spectrum. In OSA, two categories of users are considered: Primary Users (PUs), also known as licensed users, have the right to fully access their dedicated bandwidths; and Secondary Users (SUs), i.e. opportunistic users, would like to exploit vacant frequency bands unused by the PUs. Due to hardware limitation, a SU can access one channel at each time slot trying to reach the best channel with the highest vacancy probability. To identify the best channel, we formulate OSA as a Multi-Armed Bandit (MAB) problem, in which an agent plays one arm at each time trying to reach the optimal arm with the highest expected reward. Several MAB algorithms have been suggested to solve the MAB problem in the context of OSA, such as: Thompson Sampling (TS), Upper Confidence Bound (UCB), e-greedy, etc.

By focusing first on a single SU, we analyze the performance of the well-known MAB algorithms (i.e. TS, UCB, e-greedy) that deal with OSA. Thus, we propose our MAB algorithms based on UCB, called: e-UCB and AUCB. Both of them achieve good results compared to well-known variants of MAB algorithms, i.e. UCB and e-greedy, in which the SU can quickly learn the vacancy probability of channels without any information or prior knowledge about the available channels. Our analytical proof, as well as the simulation results, of e-UCB and AUCB show that the SU can efficiently distinguish and converge to the best channel after a finite number of time slots.

For multiple users, the big challenge of SUs remains to learn collectively (Cooperative learning) or separately (Competitive learning) the vacancy probabilities of the channels. As a matter of fact, a cooperative or competitive learning policy is required in order to manage the secondary network and decrease the number of collisions among users. Generally, the policies to manage a secondary network can be classified into two main categories: Random access or priority access. Most recent works in OSA focus on the random access while the priority access is not enough considered in the literature. In fact, the priority access can have an important role in tactical networks in which several SUs exist with some hierarchy levels.

In our work, we propose a cooperative and competitive policies for the priority access respectively called Side Channel and All-Powerful Learning (APL). In our policies, each SU has an assigned priority rank, and his target remains to access the channels according to his rank. Moreover, Side Channel and APL deal with the priority dynamic access where the users can enter into or leave the network. While, to the best of our knowledge, only the priority or dynamic access are considered in several recent works. Finally, a proof is developed to verify the performance of proposed learning policies on a real radio environment. Simulation results show that Side channel and APL can achieve better results than several recent works: the users can quickly reach their dedicated channels while decreasing the number of collisions among them.

Titre: Thèse de doctorat, Théorie des jeux pour les communications militaires tactiques Mots-clés: Accès Opportuniste au Spectre, Multi-arm bandit , Accès prioritaire dynamique Durant le siècle passé, les ressources spectrales ont été allouées exclusivement aux services qui sont apparus au fur et à mesure des années. Avec une augmentation soutenue, des besoins en bandes fréquentielles à allouer aux applications de communication sans fil émergentes, les opérateurs de radiocommunication se sont trouvés, face à une pénurie de ressources spectrales. Néanmoins, plusieurs études initiées par la Commission fédérale des communications (FCC : Federal Communications Commission qui est une agence indépendante du gouvernement des États-Unis) ont montré que les bandes de fréquences sont mal exploitées: certaines bandes sont peu chargées, or d'autres sont surchargées. L'Accès Opportuniste au Spectre (AOS) dans une radio cognitive (RC) représente une potentielle solution proposée pour lutter contre un manque accru du spectre et améliorer le rendement de l'utilisation. Dans un AOS, deux catégories d'utilisateurs sont définis: les utilisateurs primaires (PU), possédant les licences, ont un droit exclusif d'accéder à leurs bandes fréquentielles en permanence; et les utilisateurs secondaires (SU) ou opportunistes qui cherchent à exploiter les bandes de fréquences libérer par un PU. Dans beaucoup de situations et dû généralement à limitation matérielle ou à un coût, un SU ne peut explorer et y accéder qu'un seul canal à un instant donné. Ce SU cherche donc à trouver le meilleur canal, i.e. le canal possédant les meilleures conditions de transmission qui sera le plus disponible. Pour identifier le meilleur canal, nous avons proposé un modèle d' AOS en se basant sur un problème de multi-arm bandit (MAB), dans lequel un joueur joue une seule machine à sous à chaque tournée en espérant de découvrir la meilleure machine qui augmentera son gain. Dans la littérature, plusieurs algorithmes ont été développés pour mieux aborder le problème du MAB, notamment: Thompson Sampling (TS), Upper Confidence Bound (UCB), e-greedy, etc.. En considérant uniquement le cas d'un seul SU, nous avons analysé et comparé les performances des algorithmes bien cités du MAB (TS, UCB, e-greedy). Nous avons par ailleurs proposé deux nouveaux variétés de l'algorithme UCB: e-UCB et AUCB. Les deux derniers algorithmes ont donné une grande satisfaction en montrant des meilleures performances que les autres variantes bien connues des algorithmes UCB ou egreedy, dans lesquelles le SU peut rapidement estimer la probabilité de disponibilité des canaux sans préalable information.

Dans un deuxième temps, nous avons penché sur un cas plus général où plusieurs utilisateurs secondaires coexistent, leur principal goal de ces SU reste à trouver la meilleur stratégie (apprentissage coopératif) ou les stratégies individuelles (apprentissage compétitif) pour mieux estimer les probabilités de disponibilité des canaux. Généralement, un réseau secondaire peut être générer selon deux types d'accès : aléatoire ou prioritaire. Plusieurs travaux récents sur l'AOS ont exclusivement considéré l'accès aléatoire. Par contre, l'accès prioritaire a été relativement négligé, alors qu'un accès prioritaire devient crucial dans des réseaux tactiques pour lesquels plusieurs SU coexistent avec un certain niveau de hiérarchie. Pour plusieurs utilisateurs, le grand défi des SU reste d'apprendre collectivement (apprentissage coopératif) ou séparément (apprentissage compétitif) les probabilités de disponibilité des canaux. En effet, une stratégie d'apprentissage coopératif ou compétitif est nécessaire pour gérer le réseau secondaire et diminuer le nombre de collisions entre les utilisateurs. Généralement, les stratégies de gestion d'un réseau secondaire peuvent être classées en deux catégories principales: accès aléatoire ou accès priorité. Les travaux les plus récents en OSA se concentrent sur l'accès aléatoire alors que l'accès priorité n'est pas suffisamment pris en compte dans la littérature. En fait, l'accès priorité peut avoir un rôle important dans les réseaux tactiques dans lesquels plusieurs SU existent avec certains niveaux de hiérarchie.

Dans nos études et pour un réseau tactique avec une certaine hiérarchie, nous avons proposé deux stratégies, l'une coopérative et l'autre compétitive Side Channel et All-Powerful Learning (APL) respectivement. Selon ces deux stratégies, chaque SU a un rang fixe, et son objectif est d'accéder aux canaux disponibles en respectant son rang. En plus, Side Channel et APL prennent en compte un accès prioritaire et dynamique, où les utilisateurs peuvent entrer ou sortir du réseau à tout moment. Dans la littérature, un accès prioritaire ou un accès dynamique ont été séparément évoqués. Finalement une étude de performance théorique a été développée pour les stratégies d'apprentissage proposées. Les simulations ont montré que Side Channel et APL ont donné les meilleurs résultats par rapport à la littérature. En appliquant l'une de ces deux stratégies, les utilisateurs secondaires peuvent rapidement identifier les canaux correspondants à leurs rangs tout en réduisant le nombre de collisions parmi eux. SOUR for his continuous support, motivation and untiring guidance have made this dream come true. His vast knowledge, calm nature and positive criticism motivated me to starve for nice results. I would also express my sincere thanks to his wife "Houwaida", his son "Taha" and his daughter "Mariam" for the warm and gracious hospitality during different vacations spent in the villages, beaches and mountains. They are my second family members in France. I would like to express my thanks to Prof. Karim ABED MERAIM and Prof. Nadège Thirion for reviewing my thesis and for all their valuable comments that helped me to improve it. Also, thank you to Prof. Emanuel Radoi and Prof. Christian Jutten as examiners. I would like to acknowledge Dr. Christophe Osswald, Prof. Christophe Moy, Dr. Denis Lejeune for their support throughout the Ph.D. years. I have improved immeasurably as a scientist and as a communicator, and the opportunity to work with them over the last three years was an honor. Thanks go out to Prof. Ammar Assoum for his guidance (academic, scientific, and otherwise) through the course of this research, and to Dr. Vincent Choqueuse for his useful comments in the CSI and for attending my defense as an invited member. My eternal cheerleader: I miss our interesting and long-lasting chats. My forever interested, encouraging and always enthusiastic my mother: Ghazwa Almasri, she was always keen to know what I was doing and how I was proceeding, although it is likely that she has never grasped what it was all about! I will miss your screams of joy whenever a significant momentous was reached. This moment also reminds me of the influence of my father and my siblings, who have provided me through moral and emotional support in my life. I am also grateful to my other family members and friends who have supported me along the way Jean Marrie, Houssam Barbara, Kahina Bensafia. I wished if they share with me this moment that they and I dreamt of. Thanks for all your encouragement! 1. 1 Efficiency of each cellular wireless generation, 1G allowed making a call, 2G allowed to send text messages and MMS, 3G added video calls and access to the internet, 4G guarantees a worthy quality of a Wi-Fi connection. The high speed of the 5G will allow to develop many communication systems in the urban landscape, such as transport, traffic, radar imagery, security control it will also ensure faster data rates, higher connection density, improved overall wireless coverage, etc. . . . 6

2.1 Comparison between the well-known MAB algorithms. '|' indicates a high performance, '|||' indicates that the performance is weak and 'N/A' indicates that the information is not available. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.2 Compares the performance of the well-known MAB algorithms for multiple agents. '|' indicates a high performance, '|||' indicates that the performance is weak and 'N/A' indicates that the information is not available or no value available. . . . . . [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF] 5.1 Two SUs access three available channels. In this case, the total number of collisions for the two users is

D(n) = ∑ U k=1 D k (n) = D SU1 (n) + D SU2 (n).
The number of collisions in all channels produced by the users is

O C (n) = ∑ C i=1 O i (n) = O C1 (n) + O C2 (n) + O C3 (n)
, while the number of collisions in the best channels, i.e. C1 and C2, is Nowadays, it is very easy to establish in a few minutes a wireless network allowing computers or mobile devices to communicate with each other. The difficulty of implementation is the reception area, related to the power of the transmitter, the detection of the receiver and the security of the transmitted data. The primary and essential advantage of wireless communication systems is mobility. Finally, we can say that, due to their advantages, flexibility and mobility, wireless communication networks such as WLAN or telephony networks represent the best technologies to the industrial automation. Moreover, it has been shown that the frequency bands of wireless communication are not uniformly used (some frequency bands are not well used while others are very crowded), hence the necessity to introduce novel technologies in order to achieve an efficient use of the spectrum. The Cognitive Radio represents one of the proposed technologies, widely suggested in the literature, to enhance the efficiency use of the spectrum.

O U (n) = ∑ U k=1 O k (n) = O C1 (n) + O C2 (n).

WLAN and unlicensed standards

Nowadays, WLAN represents one of the most popular technologies used by the industry in order to provide machine-to-machine connections, help mobile devices to connect to a given network, as well as to extend the internet networks (e.g. the connection between mobile devices and routers can reach up to 150 meters indoors and 300 meters outdoors).

WLAN IEEE 802.11 (WiFi) family represents the famous standards firstly commercialized by Apple for their iBook series in 1999. Several new applications that provide new technical challenges, based on WiFi technology, have been proposed such as Voice over IP (VoIP), Video streaming, etc. Recently, these applications, becoming mature with low cost compared to cellular communication, use a broadband Internet connection in order to make unlimited phone calls and to unload overcrowded cellular networks. Even though their benefits, the arrival of new wireless applications and services makes the unlicensed frequency bands more and more crowded.

For its simplicity and efficiency, all cellphones, laptops, tablet computers and printers nowadays, having 802.11 wireless modems, use the 2.4 GHz or 5 GHz ISM (Industrial, Scientific and Medical) bands. Based on [1,2], we make a comparison between the most commonly used ISM bands in the industrial wireless networks. Despite the intent of the original allocation, the fastest-growing uses of the ISM bands recently return to the low-power and short-range communication systems: Wireless computer networks, wireless keyboards and mice, baby monitors, cordless phones, garage door openers. The ISM bands, specifically the 2.4 GHz, have been originally designed for several applications, such as: medical equipment, microwave, types of electrodeless lamps, and process heating [3]. ISM generally represents unlicensed frequency bands that are overloaded, Chapter 1. Advanced Technologies in Wireless Internet and Communications Networks noisy, and need powerful Radio Frequency (RF) system to manage the interference problems. Moreover, many technologies that use ISM bands (e.g. WiFi) do not provide any protection or warranty that may lead to unsecure communication among the devices. Over the past few years, there have been many applications and communication techniques that have adopted ISM bands. The Internet of Things (IoT) represents one of these applications and this is mainly due to the low power and cost of spectrum of ISM bands without users being directly involved. Furthermore, the future technologies that use ISM frequency bands may incorporate satellite communications, such as smallSATs (small-satellites), cubeSATs (cube-satellites), nanoSATs (nanosatellites) [4,5].

To solve the overlap of the unlicensed bands, in which all the mentioned technologies make the frequency bands more and more crowded, the US Federal Communications Commission (FCC) has recommended several ways to manage and solve the limitation of the frequency resources. The well-known adopted solution by FCC is to open the licensed frequencies for the opportunistic use, provided that the interference with the license users are under certain limits.

Evolution of the mobile generations

Since a few decades, mobile wireless communications have experienced four generations of revolution and evolution as shown in Table 1.1. Each of them has a higher capacity and new features compared to the previous one. The 5G implies the whole wireless world interconnection together with very high data rates Quality of Service (QoS). From second to fifth generation, each generation has a significant improvement to the previous one (e.g. enhancement the quality of services with more satisfaction in customer experience). The Cognitive Radio (CR) represents one of the new technologies that use the benefit of the Software-Defined Radio (SDR), based on its flexibility, in order to greatly increase the spectrum efficiency. As we will see in section 1.2, the Opportunistic Spectrum Access (OSA) in CR allows a cognitive user to access the unused licensed spectrum in opportunistic manner. As mentioned in [START_REF] Hong | Cognitive radio in 5g: a perspective on energyspectral efficiency trade-off[END_REF][START_REF] Liang | Cognitive radio networking and communications: An overview[END_REF][START_REF] Hossain | Evolution and future trends of research in cognitive radio: a contemporary survey[END_REF], CR is a future technology that is considered as an enabling technology for future cellular mobile generations. allowed making a call, 2G allowed to send text messages and MMS, 3G added video calls and access to the internet, 4G guarantees a worthy quality of a Wi-Fi connection. The high speed of the 5G will allow to develop many communication systems in the urban landscape, such as transport, traffic, radar imagery, security control it will also ensure faster data rates, higher connection density, improved overall wireless coverage, etc.

The explosive growth of wireless communications: Towards Cognitive Radio

The past decade has witnessed an explosive demand of wireless spectrum and that led to the major stress and the scarcity in the frequency bands. Moreover, the radio landscape has become progressively heterogeneous and very complex (e.g. several radio standards, diversity of services offered). Nowadays, the rise of the new applications and technologies accelerates the spectrum scarcity problem and encouraged wireless applications. The new wireless technologies (e.g. 5G) will support high speed data transfer rates including voice, video, and multimedia. In order to combine, at a very low cost, these future technologies with the existing one, the future network infrastructure should have a sufficient flexibility. The software-defined radio (SDR), a programmable and multi-functional radio that can adapt to a wide variety of services and standards, will facilitate the dynamic air interface reconfiguration of the network nodes by software modifications. Moreover, SDR represents a low-cost power-efficient solution that is becoming more and more apparent in the commercial world and can easily switch from one standard to another (e.g. GSM, EDGE, Wi-Fi, Bluetooth, and LTE) to provide a continuous and high-speed connection.

Software Defined Radio: The core of Cognitive Radio

The Software-Defined Radio (SDR) is a radio communication system that can adapt to any frequency band and receive any modulation using the same hardware. SDR is a wireless technology in which hardware platform like modulators/demodulators, amplifiers, mixers, filters are replaced by a software or firmware operating on programmable processing devices [START_REF] Volkwin | Suitability of a commercial software defined radio system for passive coherent location[END_REF]. Besides providing a very cheap radio receiver, SDR devices can easily examine the spectrum, assign of frequency distributions in an efficient manner, detect interferences, analyze the characterization of noise by bands and identify spectrum intruders.

SDR may be used for cellular networks where standards upgrade regularly. Indeed, when using a generic hardware, the upgrade of standards can be easily performed, for instance the shift from the third generation to the fourth one could be successfully achieved by updating the software of SDR and reconfiguring it without changing the hardware. Several definitions of SDR can be found in the literature [START_REF] Palicot | Radio engineering: From software radio to cognitive radio[END_REF][START_REF]SDRF cognitive radio definitions[END_REF], in which the common definition ground is that: SDR is a radio communication system in which some parameters, such as transmit power, frequency carrier and bandwidth, can be adjusted in software without changing the hardware itself. One of the important benefits of SDR, for the further technology, is its ability to offer the flexibility, reconfigurability and portability features for the Cognitive Radio (CR).

1.2. The explosive growth of wireless communications: Towards Cognitive Radio 9

In [START_REF] Marcus | Federal Communications Commission: Spectrum policy task force[END_REF], some frequency bands are saturated while others are not used depending on time and place. The cognitive radio, therefore, seems to be more and more necessary to homogenize the use of the spectrum and to allow the coexistence of different wireless communication technologies and multitude of communicating objects (e.g. M2M). More generic and powerful reasoning mechanisms are needed to enable radio:

• Adapt to the wide variety of wireless networking technologies (e.g. GSM, UMTS, WiFi, Bluetooth, etc.),

• Consider multiple conflicting goals (e.g. several competitive accesses in the network),

• Select the most relevant opportunity among a multitude of available choices (e.g. the most vacant one or tend to selecting high-quality channels),

The rise of Cognitive radio

The Cognitive Radio (CR) is a new paradigm firstly proposed by Mitola in 1999. One of the main features of CR is the flexibility in which the parameters of the radio (e.g. carrier frequency, power, modulation, and bandwidth) can be modified depending on: the radio environment, the situation, the state of the network and geolocation. The CR can be seen as an extension paradigm of the SDR that helps the decision-making engine to enhance its future decision where the functionality of the SDR is to help the CR to dynamically and autonomously modify its parameters and protocols accordingly [START_REF] Garg | Wireless communications & networking[END_REF][START_REF] Benedetto | The Newcom++ Vision Book[END_REF][START_REF] Benmammar | Radio resource allocation and dynamic spectrum access[END_REF][START_REF] Harada | Software defined radio prototype toward cognitive radio communication systems[END_REF]. The CR represents one of the important solutions to solve the explosive growth of wireless communications and the spectrum scarcity. Since the last decade, the CR has more and more attracted the attention as a new future technology. J. Mitola introduced in his Ph.D. the definition of the CR as follows: "The cognitive radio identifies the point at which wireless personal digital assistants (PDAs) and the related networks are sufficiently computationally intelligent about radio resources and related computer-tocomputer communications to:

• Detect user communication needs,

• Provide radio resources and wireless services most appropriate to those needs."

Chapter 1. Advanced Technologies in Wireless Internet and Communications Networks

Generally, there are two types of users in a CR system: Licensed (Primary Users: PU) and unlicensed (Secondary Users: SU) users. The spectrum sharing among licensed and unlicensed users can be classified into three main models:

• Underlay Access • Overlay Access

• Interweave Access

Underlay Access

In the underlay access, rather than detecting holes in the frequency band, the SU can access and transmit his data simultaneously with the PU. In other words, PU and SU are authorized to coexist in the same frequency band only if the interference is controlled and managed properly. Indeed, the SU, on the one hand, should use his cognitive ability by controlling his transmission power in order to keep the interference with the PU under a certain limit. On the other hand, primary transmission may be able to withstand some degrees of harmful interference. The average of the harmful interference at the primary receiver, also known as interference threshold, must not exceed the interference level defined by the FCC as interference temperature [START_REF]Establishment of interference temperature metric to quantify and manage interference and to expand available unlicensed operation in certain fixed mobile and satellite frequency bands[END_REF]. In order to keep the interference with PU under a certain threshold, underlay systems use ultra-wideband (UWB) transmission where the SU can spread his transmission signal on a very large bandwidth bands. In this case, the transmission power is below the power of the PU, and this fact limits the interference with the latter [START_REF] Wang | Advances in cognitive radio networks: A survey[END_REF]. Underlay access suffers from various drawbacks such as: it can be used only for a short transmission range (i.e. limited transmission power can be reached), and requires high level of cognition in order to measure the interference power with the PU.

Overlay Access

Unlike Underlay, the Overlay access authorizes SUs and PUs to transmit simultaneously at a maximum power transmission without interference. Indeed, in Overlay access, the SU should not cause any harm to the PU's QoS because there is a high cooperation level between them. Many works focus on the overlay access in which the SU plays the role of a relay to ensure the transmission of the PU's data and to enhance the transmission rate of the latter [START_REF] López-Martínez | A superprocess with upper confidence bounds for cooperative spectrum sharing[END_REF][START_REF] Feng | Cooperative spectrum sharing in cognitive radio networks: A distributed matching approach[END_REF].

Interweave access

In this method, there is no constraint on the transmission power of a SU except that he should limit his transmission to available spectral holes. Indeed, the SU should accurately notice the unused frequency band and survey the activity of the PU in order to prevent any interference with the licensed users.

In other words, a SU can exploit the spectrum holes in an opportunistic manner. Upon the localization of a spectrum hole, he can transmit his data with the maximum authorized power level.

In our work, we focus on the Interweave Access where the SU can access, in an opportunistic manner, the unused frequency band without any cooperation with the PU. This technique refers to the Opportunistic Spectrum Access (OSA) in the context of CR which is the most attractive way to access the spectrum [START_REF] Akyildiz | Next generation/dynamic spectrum access/cognitive radio wireless networks: A survey[END_REF][START_REF] Goldsmith | Capacity of cognitive radio networks[END_REF][START_REF] Yucek | A survey of spectrum sensing algorithms for cognitive radio applications[END_REF][START_REF] Akyildiz | Cooperative spectrum sensing in cognitive radio networks: A survey[END_REF].

The Cognitive Cycle

A cognitive radio, based on intelligent observation of its environment, should make the best decision. However, it is impractical for a cognitive radio (also called Secondary User: SU) to observe wide frequency bands to access the best one (e.g. the band with the highest availability, quality, etc.). Subsequently, under a partial observation (e.g. one band at each time slot), SU should make the best decision in order to improve his communication performance in the most prevailing conditions. According to Mitola [START_REF] Mitola | An integrated agent architecture for software defined radio[END_REF], in a cognitive cycle, the user has the capacity to collect some information from his environment (observation), and then analyze them in order to make the best action. As shown in Fig. 1.4 proposed by Mitola, at each time slot, the cognitive radio executes six steps: Observe, Orient, Plan, Decide, Act and Learn. In the observation phase, the cognitive radio discovers its environment using different sensors (e.g. the state or the quality of the selected channel, the interference level). In the orientation phase, the cognitive radio determines its priorities, makes plans according to the characteristics of the environment found in the observation phase. In the decision phase, the cognitive radio chooses and selects the best candidate plans, and finally makes actions during the act phase (e.g. transmits the data, reconfigures its parameters, etc).

To finish the cognitive cycle, the cognitive radio should execute a last step that represents the learning phase in order to enhance the decision issues. This step can improve the future action of cognitive radio based on its past perceptions, observations, decisions and actions.

A decision-making process should consider certain parameters such as: spectrum, modulation scheme, power specification, data rate, etc. Consequently, the decision about the availability or the quality of a spectrum should be made to access a particular spectrum bandwidth. Finally, the best decisionmaking of cognitive radio should depend on its environment parameters, and on the nature of interaction between users (i.e. cooperative or competitive behavior).

Our Motivations

Our Research Objectives

This research focuses on the decision-making in the context of cognitive radio. We mainly focus on the learning and decision-making in the cognitive cycle. The main goal of the thesis is to develop algorithms to help the cognitive radio to make an efficient decision in order to maximize a utility function (e.g. data rate, throughput capacity, etc.). Our work also considers both cooperative and competitive network trying to increase the transmission time and decrease the number of collisions among users. Moreover, we focus on some features of networks with the priority access.

Our major contributions can be summarized as follows:

• Focus on learning algorithms capable to evaluate the vacancy probabilities of channels.

• Consider multi-cognitive users.

• Determine the quality of service.

• Investigate the convergence.

• Investigate competitive or cooperative learning policies.

• Consider networks with priority access.

Outlines

Chapter 2 introduces the Multi-Armed Bandit game and presents its major areas of applications. It also presents briefly the Dynamic Spectrum Access (DSA) and the Opportunistic Spectrum Access (OSA), a subset of DSA. OSA allows a cognitive user to exploit opportunities in the frequency bands and enables the coexistence of both cognitive and licensed users. In addition, it focuses on the self-adaptation and learning in wireless networks and discusses the design space and networking algorithms.

Chapter 1. Advanced Technologies in Wireless Internet and Communications Networks

In chapter 3, we evaluate the performance of the existing MAB learning algorithms suggested for a single user. We also study the performance of MAB algorithms in the multi-user case. The main contributions introduced in chapter 3 are:

• The mathematical MAB model.

• The performance of existing MAB.

• Extension of MAB algorithms to consider multi cognitive users.

• A novel cooperative policy to manage a secondary network.

In chapter 4, we propose two MAB algorithms called AUCB and e-UCB that can achieve better results compared to the well-known MAB algorithms, such as: Thompson Sampling, UCB and e-greedy. These two algorithms can help the cognitive user to increase his throughput capacity. Thus, the main contributions in chapter 4 are briefly summarized as follows:

• AUCB and e-UCB to enhance the spectrum learning of the cognitive user.

• Extend AUCB and e-UCB to consider multiple priority users.

• Investigate the performance of AUCB and e-UCB

• Investigate the analytical convergence of the proposed algorithms.

In chapter 5, we analyze the sequential decision-making applied in OSA. We introduce the system model for multiple users. We also study the quality and the availability of channels in order to optimize the performance of communication and enhance the quality of service. Hereinafter, we investigate the competitive cognitive users' behavior in the priority cognitive networks for which two competitive policies, All-Powerful Learning (APL) and Priority Fairness Access (PFA), have been proposed. Those latter help the cognitive users to learn separately the vacant probabilities of channels and decrease the number of collisions among them. Our policies provide a steady state where each user has no interest to change its action since shifting to another action may affect his award. The main contributions in chapter 5 are briefly summarized as follows:

• Propose APL for the priority access.

• Investigate the convergence proof of APL.

Our Motivations

15

• Evaluate the performance of AUCB and e-UCB with APL and compare to several recent works.

• Study the Quality of Service where the user should estimate the availability and quality of channels.

• Propose PFA to tackle two or more priority levels.

Finally, chapter 6 concludes the thesis by summarizing our contributions, providing some discussions of the main results, and suggesting future research tracks based on this thesis.

Introduction

In this chapter, we introduce the state of the art of the decision-making and learning mechanisms for the Opportunistic Spectrum Access (OSA). OSA, a particular case of Dynamic Spectrum Access (DSA), represents one of the proposed solutions to better use the frequency bands.

The main idea of OSA is to share the spectrum between Primary Users (PUs) with a privilege access to their bands and Secondary or opportunistic Users (SUs), who can access these bands when PUs are not active. The outline for this chapter is as follows: In section 2.2, we discuss the concept of DSA in CR and the main challenge of the SU in OSA. In section 2.3, we investigate the spectrum decision and the machine learning classification. In this section, we also introduce the reinforcement learning and how it can help the SU make an optimal decision. In section 2.4, we introduce the Multi-armed bandit problem and we formulate the OSA as MAB in order to enhance the spectrum learning. In section 2.5, we introduce the different existing models in MAB that are used to formulate the obtained reward such as Independent Identical Distributed (IID) or Markovian Models. In section 2.6, we present the state of the art of MAB algorithms for single or multiple agents. Finally, section 2.7 summarizes this chapter.

Dynamic Spectrum Access and Opportunistic

Spectrum Access

The radio spectrum can be classified into two different categories:

• Static spectrum used in various standards on the wireless spectrum where licensed users have a full and privilege access to a specific band.

• Dynamic access in which the spectrum can be wisely shared between users to reduce the time where any band is free.

However, Dynamic Spectrum Access can be seen as a new concept to maximize the spectral efficiency. Several studies in the United States (US) have shown that some frequency bands have become more and more crowded while others are almost not used [START_REF] Kolodzy | Spectrum policy task force report[END_REF]. As shown in Fig. 2.1, DSA can be categorized into three main models: Exclusive Use, Open Sharing and Hierarchical Access [START_REF] Zaho | A survey of dynamic spectrum access: Signal processing, networking and regulatory policy[END_REF] In practice, Interweave is the widely used model that allows SU to access the unused frequency bands, in opportunistic manner, without any cooperation with the PU. Due to the detection cost, the SU is not able to sense simultaneously all the available frequencies. Subsequently, under a constraint detection (e.g. one channel at each time slot), the SU should make a decision and find an opportunity to send his data. In our work, we are interested to apply the MAB algorithm in OSA for which several algorithms are suggested in the literature to help SU make a decision. SU in OSA faces many challenges in order to reduce the interference with PU [START_REF] Haykin | Brain-empowered wireless communications[END_REF]:

• Searching for unused bands using Spectrum Sensing techniques.

• Spectrum Decision: Selecting the band with the highest vacancy probability.

• Spectrum Mobility: Evacuating a previously selected channel when PU reappears.

• Spectrum Sharing: Sharing available frequency bands with other SUs.

In our study, we choose to focus on two challenges: Spectrum Decision and Spectrum Sharing. To help the SU make a good decision, the game theory is recently applied in CR and represents a suitable solution for: adjusting the transmission power, management spectrum, allocating resources, etc. The most used games in the CR are prisoner's Dilemma, Stackelberg and Multi-armed Bandit (MAB).

In our work, we mainly focus on the Multi-armed Bandit problem in which we formulate the OSA as a MAB problem which is widely used in the literature. For multiple SUs, the extended MAB should reach an equilibrium among users, use optimally the frequency bands and decrease the number of collisions among users.

Decision-Making Process and Machine Learning

Spectrum Decision is the ability to find and access the most suitable frequency band with the highest availability probability. However, in the context of CR, the main target of a SU is to increase his transmission time and rate by finding the most vacant band. At each time slot, the SU can observe the state of the frequency bands, decide which band to access, and make an action in order to be adapted to his environment (e.g. transmitting power, frequency band). To evaluate the taken action, good or bad, a SU receives a reward, the goal being to enhance its behavior at the next stage. Thereby, a SU should be a cognitive device in order to learn its environment from Chapter 2. Learning and Decision-Making for Opportunistic Spectrum Access past decisions and make the best action. Recently, there is a growing interest in applying machine learning in the context of cognitive radio in order to achieve an efficient resource allocation [START_REF] Clancy | Applications of machine learning to cognitive radio networks[END_REF][START_REF] Mody | Machine learning based cognitive communications in white as well as the gray space[END_REF]. However, in the cognitive cycle, the learning and the comprehensive situation represent the more important functions in order to help the SU adapt to his environment. Generally, the machine learning problem can be defined as in [START_REF] Russell | Artificial intelligence: a modern approach[END_REF]: "An agent learns about his environment with respect to a task A (e.g. his action to the environment at instant t) and measures the performance obtained from this task r (e.g. reward at instant t) if his performance at task A, measured by r, is improved over time". The machine learning algorithms, as shown in Fig. 2.3, are classified into three main categories [START_REF] Russell | Artificial intelligence: a modern approach[END_REF][START_REF] Alpaydin | Introduction to machine learning[END_REF]:

• Supervised learning: The agent can create a function model based on the input data where the desired output is known. Then, for new data input, and based on the generated function, the agent is able to predict the future output. The supervised learning algorithm can be classified into two main categories: Classification or Regression problems. In the classification problem, the data variable is considered as discrete, and the objective is to identify the classes of the data. The regression algorithm is very useful to predict a real value quantity for an input data, such as: Linear regression, logistical regression, perception.

• Unsupervised learning: Unsupervised model is widely used to draw inferences or extract features and patterns from the dataset, without any feedback. The most important unsupervised learning methods are clustering, k-Means, Self-organizing maps, etc.

• Reinforcement learning (RL): It represents another part of machine leaning and has an important role in the multi-agent system, since it allows an agent to learn from his environment by interacting with it. The agent should enhance his behavior from the feedback (e.g. reward). Indeed, RL may allow an agent to adapt to his environment by finding a suitable action to reach the best reward. Several variants of RL can be found in the literature such as Q-learning, Upper Confidence Bound (UCB), egreedy, etc.

Machine Learning

Reinforcement Learning

In the Reinforcement Learning (RL), the agent can maximize his reward without any prior information about his environment. However, by memorizing the states of an environment or the actions he took, the agent can make a better decision in the future. The reward feedback, also called reinforcement signal, has an important role to help an agent to learn from its environment. As shown in Fig. 2.4, at each time slot, the agent observes the state of his environment S(t), selects an action A(t) and receives a reward r(t). Based on the expected reward obtained up to time slot t and the state of the environment, the agent tries to enhance his action at the next slot.

RL is widely used in several domains: Robotics, Aircraft control, selfdriving cars, Business strategy planning, etc. It was first developed for a single agent who should find an optimal policy that maximizes his expected reward knowing that the optimal policy depends on the environment. Unlike the case of a single agent, for multiple agents, the optimal policy depends not only on the environment but also on the policies selected by other agents. Moreover, when multiple agents apply the same policy their approaches in such systems often fail because each agent tries individually to reach a desired result. In other words, it is impossible for all agents in a certain system to maximize simultaneously their personal reward, although find an equilibrium for the system representing a point of interest. Subsequently, it is important to find a policy for each agent in order to guarantee the convergence to an equilibrium state in which no agent can gain more when modifying its own action. Recently, the multi-agent in the reinforcement learning attracts more and more the attention in several fields where multiple agents may exist in the system, such as: robotics, distributed control, telecommunications, economics, etc. For a given system, the agent may independently find his own good policy, without coordinating with other agents neither their reward nor their actions. Fig. 2.5 shows all the possible reinforcement learning frameworks for a single or multiple agents. In a centralized algorithm, the decision is made at the network level, while in a distributed algorithm, each agent makes his own decision independently without any cooperation with others. A semidistributed algorithm is based on the combination between centralized and distributed techniques. In RL, Exploitation-Exploration dilemma represents an attractive problem. In order to maximize his performance (exploitation), the agent should gather some information about his environment (exploration). This is known as the Exploration-Exploitation dilemma in the reinforcement learning. If the agent spends a lot of time on the exploration phase, then he cannot maximize his reward. Similarly, when the agent focuses on the exploitation phase by exploiting his current information, then he may miss the best action that leads to the highest reward. Thus, the agent needs to balance the tradeoff between Exploration and Exploitation in order to obtain an appropriate result.

Multi-Armed Bandit problem

Due to its generic nature, Multi-armed bandit game attracts more and more attention and is widely used to solve the decision-making problem in several fields such as: Jamming communication, Clinical trials, object tracking, ads selection on web pages. The Multi Armed-Bandit problem represents a subset of RL in which an agent is in front of several slot machines (or arms), and at each time slot he pulls an arm and receives a fixed reward. Like most RL frameworks, the agent starts the game without any priori knowledge about the expected reward of the arms. The main goal of the agent is to find the arm with the highest expected reward. Here, we should define two classes of arms:

Optimal arm: This arm has the highest expected reward and is represented by the arm 2 in Fig. 2.6. The agent tries to reach this arm in order to maximize his expected reward.

Suboptimal arms: Include all other arms considered as non-optimal. Efficient MAB algorithms should be able to limit playing with suboptimal arms. Chapter 2. Learning and Decision-Making for Opportunistic Spectrum Access

Model of MAB reward

In order to formulate the obtained reward from the slot machines, different models exist in the literature such as: Markovian or IID. In this section, we focus on these two models, being the most widespread, in order to address the MAB problem.

IID Bandit Problem Formulation

Due to its simplicity, this model has received much attention to formulate the reward obtained from different arms [START_REF]Sample mean based index policies with o(log n) regret for the multiarmed bandit problem[END_REF][START_REF] Jouini | Upper confidence bound based decision making strategies and dynamic spectrum access[END_REF][START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF][START_REF] Liu | Distributed learning in multi-armed bandit with multiple players[END_REF][START_REF] Gai | Learning multiuser channel allocations in cognitive radio networks: a combinatorial multi-armed bandit formulation[END_REF]. The paper of Lai and Robbins in [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF] presents one of the earliest studies to solve the MAB problem based on the Independent Identical Distributed (IID) model. In their study, the authors considered C arms and showed that the expected regret, i.e. the loss of reward by selecting non-optimal arms, achieves a logarithmic asymptotic behavior with respect to the number of plays. In [START_REF] Anantharam | Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-part i: Iid rewards[END_REF], Anantharam et al. extended the work of Lai and Robbins while considering that the agent can play simultaneously N arms (C > N) and they also proved a logarithmic regret. Using IID model, the authors of [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] proposed a simple algorithm called UCB1 (Upper Confidence Bound) for a single agent inspired from the work presented in [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF].

At each time slot t, the agent selects an arm i ∈ {1, . . . , C} based on the past observations and obtains an IID reward r i (t). The i-th arm can be observed in one of the two binary states S i (t): S i (t) = 1 if the i-th channel is free and 0 otherwise. Without any loss of generality, we can consider that: r i (t) = S i (t). The main target of the agent is to maximize his long-term reward. Subsequently, the optimization problem consists in maximizing the following quantity:

max n ∑ t=1 r i (t) (2.1)
where n stands for the total number of slots. The mean reward of the i-th arm up to slot n can be defined as follows:

µ i = 1 n n ∑ t=1 r i (t) (2.2)
Based on the IID model, several works recently consider the case of multiple agents [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF][START_REF] Liu | Distributed learning in multi-armed bandit with multiple players[END_REF][START_REF] Gai | Learning multiuser channel allocations in cognitive radio networks: a combinatorial multi-armed bandit formulation[END_REF] which represents a more realistic case in OSA. However, 2.6. Model of MAB reward 29 in OSA, several SUs may exist in the network and their main objective is to learn collectively the availability of channels in order to decrease the number of collisions among them.

Markov Bandit Problem Formulation

In MAB problem, the received arms reward can be formulated as a Markov model where each arm has finite states space and each state provides a stationary and positive reward. Moreover, the state of the arms changes according to a stochastic process that is referred to as a Markov process. In other words, in a Markov process, the future state of the arm is related to its current as well as its previous state and to the transition probability P. In a Markov model, two modes of arms can be considered: active and passive. However, when an arm is selected by the agent during the current time step, it is considered in active mode, otherwise it is referred as passive. In Markov MAB, two sub-models can be considered (as shown in Fig. 2.7):

• Rested MAB model: In this model, only the state of the selected arm evolves, while the state of other arms stays frozen, i.e. does not evolve.

• Restless MAB model: In such model, the states of all arms continue to evolve at each time step. This model was first proposed by Whittle in 1988, in which the passive arms evolve regardless of whether there are played or not. The restless model is also sufficiently suggested in the literature and several works such as [START_REF] Anantharam | Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays, part ii: Markovian rewards[END_REF][START_REF] Modi | Qos driven channel selection algorithm for cognitive radio network: Multi-user multi-armed bandit approach[END_REF] considered this model under the multi-user case.

Under Markovian model, each arm is modeled as aperiodic, irreducible and discrete time with finite state S i (t). In Fig. 2.8, we consider two binary states (e.g. free or busy) for each arm with a Markov chain characterized by:

• Transition matrix of probability (P i ).

• Transition diagram (Fig. 2.8).

• Stationary vector of the states (π i ).

Let P kl i be the transition probability for the i-th arm from state k to state l, then the transition matrix, P i , of Markov model for two states becomes: = φ i , knowing that P 00 i + P 01 i = P 10 i + P 11 i = 1, then the matrix P i can be simplified as follows:

P i = P 00 i P 01 i P
P i = 1 -φ i φ i 1 -φ i φ i
The stationary vector defines the mean rewards for a transition matrix:

π i = [π 0 i , π 1 i ],
where Consequently, the mean reward for each arm i is given below:

π 0 i = P 10 i P
µ i = 1 n n ∑ t=1 ∑ b∈S i π b i r b i (t) (2.3)
The main goal of the agent is to estimate µ i in order to access the best channel with the highest vacancy probability. Based on [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], recent works in [START_REF] Modi | Qos driven channel selection algorithm for opportunistic spectrum access[END_REF][START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF][START_REF] Liu | Logarithmic weak regret of non-bayesian restless multiarmed bandit[END_REF] tackle the Markov MAB for multiple agents, that achieves a logarithmic regret with respect to time slot. In our work, we focus on the IID model in which the well-known MAB algorithms proposed to address the MAB problem are based on the IID model.

In the following section, we present the MAB algorithms for a single user to tackle the MAB problem; and latter, we focus on MAB with multiple agents in order to apply it in OSA.

MAB algorithms

In this section, we discuss the state of the art of the proposed algorithms to tackle the IID MAB problem for a single or multiple agents cases. In MAB problem, an agent faces the exploration vs the exploitation dilemma. As a matter of fact, the agent may fail to pull the optimal arm, and thus should gather more information about the expected reward of arms to select the optimal one (exploration). On the other hand, the agent tries to select the current optimal arm in order to maximize his gain (exploitation).

MAB algorithms for a single agent

In the literature, a variety of MAB algorithms have been proposed to tackle the exploration-exploitation dilemma for a single agent. e-greedy represents the simplest MAB algorithm and was initially proposed in [START_REF] Cornish | Learning from delayed rewards[END_REF]. In e-greedy, the agent pulls a random arm with a constant probability e (exploration), and then pulls the arm that has the highest expected reward with a probability of 1e (exploitation). As a result, we conclude from e-greedy that a higher value of e may increase the exploration epoch and thus the total regret. Moreover, e-greedy does not achieve an asymptotic convergence to the optimal arm since e is considered as a constant. To solve the asymptotic convergence, the authors of [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] proposed the decreasing e-greedy in which e is not considered as a constant but a parameter decreasing with time. However, when e tends towards 0, the agent may have a good estimation about the expected reward of each arm and regularly accesses the optimal one. The authors also found the analytical convergence of the decreasing e-greedy that achieves a logarithmic asymptotic behavior. The main drawback of the decreasing egreedy is that the exploration and exploitation epochs are independent, since the agent should stop the exploration after a finite period. Subsequently, the agent cannot follow a dynamic environment in which the mean reward of arms changes over time. Unlike e-greedy, Upper Confidence Bound (UCB) makes a tradeoff between exploration and exploitation at each time slot [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]. UCB has strong performance guarantees and represents the widely used algorithm to address the IID MAB problem. Lai and Robbins in their paper [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF] have shown that the regret of UCB achieves a logarithmic convergence with respect to time. Subsequently, after a finite number of time slots, and based on UCB, the agent may find the best arm by maximizing his reward. Several versions of UCB have been proposed to achieve a better performance compared to the classical one [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF][START_REF] Giuseppe | A survey of online experiment design with the stochastic multi-armed bandit[END_REF][START_REF] Kaufmann | On bayesian upper confidence bounds for bandit problems[END_REF][START_REF] Maillard | A finite-time analysis of multi-armed bandits problems with kullback-leibler divergences[END_REF]. In [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], the authors proposed UCB1

Chapter 2. Learning and Decision-Making for Opportunistic Spectrum Access in order to achieve a balance between exploration and exploitation epochs. In UCB1, each arm assigned an index B i (T i (t)) where T i (t) is the number of times to play with the i-th arm. The index B i (T i (t)) of the i-th arm up to slot t can be defined as follows:

B i (T i (t)) = X i (T i (t)) + A i (t, T i (t))
where X i (T i (t)) and A i (T i (t)) represent the exploitation and exploration epochs respectively. At each time step, the agent makes an action a t and pulls the arm with the highest index B i (t, T i (t)) as follows:

a t = argmax(B i (t, T i (t)))
After a finite time step, the agent may have a good estimation about the expected regret of each arm, and then he regularly pulls the optimal one. In the same study, the authors also proposed two other versions of UCB, called UCB2 and UCB-tuned, achieving both better results than UCB. These two versions have also the exploration-exploitation factors X i (T i (t)) and A i (t, T i (t)). In UCB2, the agent selects at each time step the arm that has the highest index B i (t, T i (t)) and then pulls this arm [(1 + α)

r i + 1(1 + α) r i ]
times where α is a constant (0 < α < 1) and r i denotes the number of epochs the arm i is selected. Moreover, the effect of the exploration factor, A i (t, T i (t)), is reduced compared to UCB1 in order to minimize the exploration epoch and converge towards the optimal arm. Unlike UCB1 and UCB2, in UCB-tuned, the exploration factor depends on the variance of the reward obtained from the i-th arm while achieving better results. Similarly to UCB-tuned, and based on the variance and the expected mean of arms reward, the authors of [START_REF] Audibert | Tuning bandit algorithms in stochastic environments[END_REF] proposed a novel version of UCB called UCB-Variance (UCB-V) that achieves a better regret compared to UCB1, UCB2 and UCB-tuned.

Recent versions of UCB, such as Kullback-Leibler-UCB (KL-UCB) [START_REF] Cappé | Kullback-leibler upper confidence bounds for optimal sequential allocation[END_REF] and Bayes-UCB [START_REF] Kaufmann | On bayesian upper confidence bounds for bandit problems[END_REF], have been proposed in order to reduce the total regret compared to classical versions of UCB. KL-UCB considers the distance between the estimated expected rewards of the arms as a factor in order to discriminate the optimal arm. Unlike KL-UCB, Bayes-UCB is a Bayesian model in which each arm is characterized as an estimate of a distribution O = {O 1 , . . . , O C } that is drawn from a priori distribution. Another important Bayesian algorithm is referred to Thompson Sampling (TS). Because of its optimal regret and excellent performance that can exceed the state of the Chapter 2. Learning and Decision-Making for Opportunistic Spectrum Access art MAB algorithms, TS attracts more and more the attention of the machine learning community [START_REF] Giuseppe | A survey of online experiment design with the stochastic multi-armed bandit[END_REF][START_REF] Scott | A modern bayesian look at the multi-armed bandit[END_REF][START_REF] Chapelle | An empirical evaluation of thompson sampling[END_REF]. Recently, several studies have found a concrete bound of its optimal regret [START_REF] Agrawal | Analysis of thompson sampling for the multi-armed bandit problem[END_REF][START_REF] Kaufmann | Thompson sampling: An asymptotically optimal finite-time analysis[END_REF][START_REF] Agrawal | Further optimal regret bounds for thompson sampling[END_REF]. More details and discussion about TS and its performance are introduced in the next chapter. Moreover, we adopt TS in chapter 4 as a reference in order to evaluate the performance of our proposed AUCB and e-UCB. Table 2.1 compares the performance of the three general families of the MAB algorithms: Thompson Sampling, UCB and e-greedy.

MAB algorithms to manage multiple agents

To formulate the OSA as a MAB problem, recent works extend the simple case of MAB (i.e. the case of a single agent) to consider several agents [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF][START_REF] Liu | Decentralized multi-armed bandit with imperfect observations[END_REF][START_REF] Rosenski | Multi-player bandits-a musical chairs approach[END_REF][START_REF] Gai | Decentralized online learning algorithms for opportunistic spectrum access[END_REF][START_REF] Torabi | Rank-optimal channel selection strategy in cognitive networks[END_REF]. In our work, we are interested in the OSA for multiple priority access in which SUs should access the spectrum according to their ranks. Moreover, decreasing the number of collisions among SUs represents a point of interest to enhance the global performance of the secondary network. In general, when two SUs access the same channel to transmit, their data cannot be correctly received because of the interference between them. When a collision occurs among users, several proposals can be found in the literature in order to enhance their behavior in the next slots. We present below two well-known collision models in the literature that are widely used in OSA:

• ALOHA-like model: If a collision occurs between two or more users, then none of them receives a reward, despite the selected channels is free. This model may ensure the fairness among users, and no collision avoidance mechanism is used.

• Reward sharing model: If two or more users select the same channel at the same time, the colliding users share the obtained reward from the selected channel (each of them receives the same reward).

The above models can affect the methodologies used to collect the reward from the target channel while the learning phase is not affected. In our work, we consider the most widely used, ALOHA-like. Based on the ALOHA-like, the works of [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF][START_REF] Liu | Decentralized multi-armed bandit with imperfect observations[END_REF][START_REF] Rosenski | Multi-player bandits-a musical chairs approach[END_REF][START_REF] Torabi | Rank-optimal channel selection strategy in cognitive networks[END_REF][START_REF] Avner | Concurrent bandit and cognitive radio networks[END_REF][START_REF] Almasri | Allpowerful learning algorithm for the priority access in cognitive network[END_REF][START_REF] Almasri | Distributed algorithm under cooperative or competitive users with priority access in cognitive networks[END_REF][START_REF] Almasri | Distributed algorithm to learn osa channels availability and enhance the transmission rate of secondary users[END_REF] proposed semi-distributed and distributed algorithms in which users cannot exchange information with each other. Liu and Zhao in [START_REF] Liu | Decentralized multi-armed bandit with imperfect observations[END_REF] may achieve an asymptotic logarithmic behavior. In such algorithm, the users access the channels with different offsets. TDFS also ensures the fairness among users; while in our work we are interested in the priority access where users access the channels based on their prior rank. In [START_REF] Liu | Decentralized multi-armed bandit with imperfect observations[END_REF], TDFS policy was been used to extend UCB1 algorithm to consider multiple users.

Beside TDFS, the authors of [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF] proposed Random Rank policy, based on UCB1, to manage the secondary network. Random Rank represents a distributed policy (i.e. no-information exchange among users) in which the user achieves a different throughput.

Musical Chair in [START_REF] Rosenski | Multi-player bandits-a musical chairs approach[END_REF] represents another important policy for the random access to manage a secondary network. During time T0, the user selects a random channel to have an information about the channels availability (exploration), after that, the user accesses the channels according to his priori rank (exploitation). Similarly, the authors of [START_REF] Avner | Concurrent bandit and cognitive radio networks[END_REF] proposed Multi-user e-greedy collision Avoiding (MEGA) algorithm for the random access. The importance of MEGA algorithm is that it can handle the random dynamic access in which the users can enter or leave the network.

Generally, the random access is widely suggested in the literature while in our work, we focus on the priority access in which there are few studies. The k-th largest expected rewards (SLK) in [START_REF] Gai | Decentralized online learning algorithms for opportunistic spectrum access[END_REF] is one of rare algorithms Chapter 2. Learning and Decision-Making for Opportunistic Spectrum Access proposed for the priority access based on UCB1. Table 2.2 compares the performance of the most popular MAB policies for the random access or priority access, that can be generally classified into three categories: Centralized, Semi-distributed and Distributed.

Conclusion

Opportunistic Spectrum Access (OSA) in Cognitive Radio (CR) represents a reliable solution to achieve an efficient use of the frequency bands. OSA in CR allows unlicensed users (or Secondary Users: SUs) to access a portion of the licensed frequency bands without causing any harmful interference to the licensed users (also called Primary Users: PUs). First, we investigated the decision-making that represents one of the main challenges faced by SUs in OSA. Then, we presented the machine learning taxonomy and more precisely the Reinforcement learning to address the decision-making problem. Next, we focused on the MAB problem, as a part of reinforcement learning, that is widely suggested in OSA in order to help the SU make a good decision. We continued to present the state of the art of MAB algorithms applied in OSA for a single user. We compared the performance of existing algorithms by comparing some features: Computation complexity, experimental performance, asymptotic convergence. Multiple users case represents a more realistic model in a real radio environment in which a policy is required to learn collectively or separately the vacancy probabilities of channels. Thus, we first introduced the recent works of MAB policies to manage a secondary network, and then we summarized their performance.

In the next chapter, we will investigate the performance of the well-known MAB algorithms in OSA for a single user. Then, we propose a novel policy to extend the MAB algorithms to consider multiple priority users.

Introduction

Opportunistic Spectrum Access (OSA) represents one of the proposed solutions to enhance the spectrum efficiency by sharing the spectrum between two types of users: Primary and Secondary. A Secondary User (SU) should make the best decision in order to maximize his throughput, without any prior information about the vacancy probabilities of channels. Moreover, any interference with the Primary User (PU) should be under a certain limit. Thus, Multi-Armed Bandit (MAB) has been chosen as a suitable solution to help a SU make a decision. In MAB problem, an agent tries to find the optimal arm without any prior knowledge about the arm's reward.

To the best of our knowledge, OSA is not being used in a real radio environment but has recently received more and more attention in order to increase the spectrum efficiency. In this chapter, we investigate the performance of the well-known MAB algorithms in OSA such as: Thompson Sampling (TS), Upper Confidence Bound (UCB) and e-greedy. The performance of MAB algorithms applied in OSA depends on several criteria: The convergence speed towards the optimal channel (i.e the channel with the highest availability probability) and the number of times to access the worst channels. Thus, we evaluate the performance of MAB algorithms using: the percentage to access the best channel (P best ) and the loss of rewards by selecting the worse channels (Regret). We should mention that the well-known MAB algorithms are first suggested for a single user, and to use it in the OSA for multiple users, a policy is required to manage the secondary network. In this chapter, we propose a cooperative learning policy, called Side Channel, that may be used with any learning MAB algorithm. The proposed policy can help SUs to learn collectively the vacancy probabilities of channels and decrease the number of collisions among users. Moreover, this policy takes into account the priority access. It can be shown that the regret of the proposed policy, under MAB algorithms, has a logarithmic asymptotic behavior for any number of users. Subsequently, after a finite number of time slots the users are able to learn the vacancy of channels and each of them accesses his dedicated channel.

In section 3.2, we introduce and discuss in details the well-known MAB algorithms. In section 3.3, we present the major challenges faced by the SU in the licensed bands. The problem formulation in OSA, for a single or multiple users, is introduced in section 3.4. In section 3.5, we propose our first contribution in which a novel cooperative policy is proposed to consider multiple priority users. Section 3.6 provides the simulation results of the MAB algorithms for a single or multiple users. Finally, section 3.7 concludes this chapter.

Single Agent MAB Algorithms

MAB problem is a simple case of Reinforcement Learning (RL) where an agent tries to learn the expected reward of arms. The main target of the agent is to find the best action that maximizes his long-time reward. MAB problem was firstly suggested for a single agent and several algorithms have been proposed on the matter, such as: Thompson Sampling (TS), Upper Confidence Bound (UCB), e-greedy. In such algorithms, the reward obtained from each arm is formulated by an IID model. According to these MAB algorithms, if the mean reward of the worst arms is very close to the optimal one (i.e. arm with the highest payoff), then the agent spends a lot of time to converge towords the optimal arm, otherwise he reaches the optimal behavior faster. MAB algorithms have recently become widely suggested in the literature in several fields such as a website optimization (e.g. maximizing conversions on landing pages, the composition of a landing page may involve deciding which image to show or color background to display) [START_REF] Hill | An efficient bandit algorithm for realtime multivariate optimization[END_REF], internet advertising [START_REF] Graepel | Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's bing search engine[END_REF][START_REF]Computational advertising: the linkedin way[END_REF][START_REF] Agarwal | Laser: A scalable response prediction platform for online advertising[END_REF]. MAB has also been adopted by several companies, including Adobe, Amazon [START_REF] Hill | An efficient bandit algorithm for realtime multivariate optimization[END_REF], Facebook, Google [START_REF] Scott | A modern bayesian look at the multi-armed bandit[END_REF][START_REF] Scott | Multi-armed bandit experiments in the online service economy[END_REF], LinkedIn [START_REF]Computational advertising: the linkedin way[END_REF][START_REF] Agarwal | Laser: A scalable response prediction platform for online advertising[END_REF], Microsoft [START_REF] Graepel | Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's bing search engine[END_REF], Netflix.

Thompson Sampling

Thompson Sampling (TS), a Bayesian algorithm, represents the earliest learning algorithm proposed to tackle the MAB problem [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF]. Despite its better performance compared to several other MAB algorithms, TS is largely ignored in the literature. Recently, TS attracts more and more attention and several works investigated the proof of its strong performance [START_REF] Agrawal | Analysis of thompson sampling for the multi-armed bandit problem[END_REF][START_REF] Kaufmann | Thompson sampling: An asymptotically optimal finite-time analysis[END_REF][START_REF] Agrawal | Further optimal regret bounds for thompson sampling[END_REF]. In TS, each arm (or channel in the context of cognitive radio) has assigned an index B i (t, T i (t)) where T i (t) stands for the number of slot times to access the i-th channel by the agent. The index of each arm follows a Beta distribution:

B i (t, T i (t)) = β(W i (t, T i (t)) + 1, Z i (t, T i (t)) +
Z i (t, T i (t)) = T i (t) -W i (t, T i (t)), B i (t, T i (t)) = β(W i (t, T i (t)) + 1, Z i (t, T i (t)) + 1),
where W i (t, T i (t)) and Z i (t, T i (t)) represent respectively the numbers of success and failure accesses. The expected value of a Beta distribution for a random variable X for a > 1 and b > 1 is given by:

E[X] = a a + b
At the initialization t = 0, the user begins to access the channels without any prior information about their availability probability µ i . When t = 0, W i (t, T i (t))= Z i (t, T i (t)) = 0, and for all channels, the assigned index B i (0, T i (0)) is set to β(1, 1). At each slot t, the user makes an action a t and selects the channel with the highest index:

a t = arg max i B i (t, T i (t))
After a finite number of time slots, the vacancy probability of the i-th channel µ i will be very closed to B i (t, T i (t)). By choosing the channel with the highest index, the user usually selects the optimal one.

Upper Confidence Bound

Upper Confidence Bound (UCB) represents the most famous MAB algorithm that is widely suggested in the literature. The idea of UCB was initially introduced by Lai and Robbins in [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]. Several versions of this algorithm have been also proposed, such as: UCB1, UCB2, UCB-tuned, UCB-Normal, UCB-Bayes, KL-UCB, etc. Unlike TS, UCB is proposed with a solid mathematical background.

Algorithm 2: Upper Confidence Bound Algorithm

Input: α, C, n, α: the exploration-exploitation factor, C: the number of channels, n: the total number of slots, Parameters:

T i (t), X i (T i (t)), A i (t
T i (t) + +, X i (T i (t)) = 1 T i (t) ∑ t τ=1 S i (τ), % S i (τ)
is the observed state from channel i at τ, % S i (τ) = 1 if the channel i is vacant and 0 otherwise,

A i (t, T i (t)) = α ln(t) T i (t) , B i (t, T i (t)) = X i (T i (t)) + A i (t, T i (t)),
To help the SU make a good decision, UCB1 [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] represents the most used version in the literature. The importance of UCB1 is probably due to the fact that it balances between the optimality and the simplicity. Several recent works proposed various policies to manage a secondary network with multiple users based on UCB1. Similar to TS, in UCB1, each channel has assigned an index B i (t, T i (t)), where T( i (t)) has the same definition as in TS. Based on the previous states of the channels, the user should learn the vacancy probabilities of channels. As shown in algorithm 2, B i (t, T i (t)) contains two factors: X i (t, T i (t)) and A i (t, T i (t)) that represent respectively the exploitation Chapter 3. MAB algorithms in OSA for Multiple Users (also known as the expected reward) and the exploration. The role of the exploration factor A i (t, T i (t)) remains to reinforce the algorithm to examine the state of the available channels in order to gather information about their vacancy probabilities. Therefore, the exploitation factor, X i (t, T i (t)), will be very close to the vacancy of channels, µ i . The assigned index of each channel can be defined as follows:

B i (t, T i (t)) = X i (T i (t)) + A i (t, T i (t)) (3.1)
At the initialization period (i.e. t = 1 to the number of channels C), the user selects each channel once to have some knowledge about the vacant probabilities of channels. After that, the user selects the channel that has the highest index B i (t, T i (t)):

a t = arg max i B i (t, T i (t))
In [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], the authors also suggest the upper bound of the sum of regret (i.e. the loss of reward by selecting the worst channels) and show that the regret achieves a logarithmic asymptotic behavior with respect to time. Subsequently, after a finite number of time slots the user recognizes the optimal channel and always selects it.

e-greedy

e-greedy represents one of the simplest algorithms that was first introduced in [START_REF] Cornish | Learning from delayed rewards[END_REF] to tackle the MAB problem. A recent version of this algorithm called decreasing e-greedy is proposed in [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] to achieve a better performance with respect to the classical version (see algorithm 3). In order to have information about the availability of channels (exploration), the user selects a random channel if χ (i.e. a uniform random variable ∈ [0,1]) < t where t = min {1, H t } and H is a constant number. Otherwise, the user selects the channel wih the highest expected reward X i (T i (t)) (exploitation). The authors have also proved that the upper bound of the regret grows linearly due to the selection of a random channel during the exploration period. Later on, the regret achieves a logarithmic asymptotic behavior (exploitation).

Algorithm 3: e-greedy Algorithm

Input: C, n, C: number of channels, n: total number of slots, Parameters: T i (t), T i (t): number of time slots the channel is sensed up to time t, Output: X i (t, T i (t)), X i (T i (t)): the expected reward that depends on T i (t),

foreach t = 1 to n do if χ < t then
The user makes a random action a t , else a t = max i X i (T i (t)),

T i (t) + +, X i (T i (t)) = 1 T i (t) ∑ t τ=1 S i (τ), % S i (τ)
is the observed state from channel i at τ, % S i (τ) = 1 if the channel i is vacant and 0 otherwise,

The Challenges of the Secondary User in the

Licensed Bands

For strategic and logistic reasons as well as to simplify the complexity of SU receivers in our working context, we assume that the SU is able to sense and explore one channel at each time slot to find transmission opportunities. OSA in cognitive radio networks (CRNs) presents new challenges compared to current wireless networks:

• Spectrum sensing,

• Learning and extracting information,

• Decision-making.

Spectrum Sensing

Through its sensors, a cognitive radio is able to gather some information from its environment. So, a SU can find and access frequency bands unused by the licensed users. Subsequently, it is possible for a SU to send his data over these empty bands. In this context, several spectrum-sensing techniques have been proposed in the literature. Matched filter detection (MFD) represents one of these techniques in which the transmission signal of the

Learning and Extracting Information

The cognitive radio system would also benefit from introducing learning capabilities into equipments in order to increase their decision-making autonomy for unexpected situations. The learning abilities would allow to ensure a further optimization and an efficient resource allocation. However, after the collection of some information (e.g. the availability of channels), the SU constructs a database of the environment in order to adapt his transmission parameters then optimize the performance of the communication. Recent studies show that the cognitive user, based on machine learning and spectrum prediction, can increase his throughput compared to the randomly spectrum sensing [START_REF] Qi | Spectrum environment machine learning in cognitive radio[END_REF]. Modern machine learning techniques [START_REF] Alsheikh | Machine learning in wireless sensor networks: Algorithms, strategies, and applications[END_REF][START_REF] Jiang | Machine learning paradigms for next-generation wireless networks[END_REF][START_REF] Sun | Estimating probabilities in recommendation systems[END_REF]] may guide the system reconfiguration in order to maximize the opportunities of the cognitive users and decrease the interference with the licensed users as much as possible. However, when the SU interacts with his environment, it gathers a sequence of information about the history state of channels as shown in Fig. 3.2. The extracting information can be treated by the SU to find the best actions with respect to his environment. Indeed, in the literature, several Multi-Arm Bandit (MAB) learning algorithms have been suggested in order to exploit the available spectrum in the best manner. The well-known MAB learning algorithms are TS [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF], UCB, and e-greedy [START_REF] Cornish | Learning from delayed rewards[END_REF]. Consequently, learning and extracted information can be considered as an important step in order to improve the cognitive user's decision and minimize the time spent trying to find the best action.

Decision-Making

A SU should select the best decision and decide which channel to access among the available spectrum bands. The decision-making of a SU should depend on his past successes and failures decision. When a SU appears in the network, his best decision becomes to increase his transmission time without causing any harm to the licensed user. The decision-making of a SU should consider the following conditions:

• A SU can only access unused licensed spectrum bands.

• When a SU accesses a bad channel (e.g. with respect to the vacancy probability of that channel), he should modify his future decision and switch to the best band in order to improve the throughput, the quality of service and the energy consumption. Consequently, the optimal decision depends on the activities of licensed users, as well as on the competitive or cooperative behavior of the cognitive users.

In competitive access, the cognitive user acts individually, without the need for any interaction with other users, in order to maximize his personal benefits (e.g. throughput, transmission time). Although the competitive access may increase the number of collisions among users, it reduces the complexity of the system. On the other hand, in a cooperative access, the cognitive users should collaborate and exchange some information about their environment in order to make a collective decision to increase the performance of their cognitive network. The collaborative access may decrease the number of collisions among users and avoid conflicts with each other.

Problem Formulation

Single User

In OSA, there are several existing problems not yet considered, to the best of our knowledge, in the context of a MAB approach, such as: multiple users, collisions among users, power transmission levels, sensing techniques, etc. Let us start to formulate the classical OSA as a MAB problem in which we consider a Secondary User (SU) that needs to access opportunistically the frequency band. Later on, we will consider multiple users with more realistic scenarios. Suppose that, the licensed band, reserved to licensed users, contains C Independent Identical Distributed (IID) channels. We denote i ∈ {1, ..., C} the i-th best channel. Each channel, when observed by the SU, appears in two possible states {free, occupied}. In the remainder of this work, we consider the numerical values {1, 0} that denote the states of the channels: 1 if the observed channel is free and 0 otherwise. Thus, we consider that the occupancy of all channels Θ = {θ 1 , ..., θ C } follows a Bernoulli distribution. Moreover, we assume that the vector Θ is supposed stationary.

In our work , we tackle the case in which the activity of the PUs is supposed to be synchronized and the time is slotted (t = 1, 2, ...n). Let S i (t) be the state of the i-th channel at slot t, considered as a random variable drawn from a given distribution θ i . At each time slot, the user chooses a channel to observe its state S i (t), and receives a reward r i (t). Without any loss of generality, in our work we consider that the obtained reward from the i-th channel equals to its binary state, i.e. S i (t) = r i (t). If the channel selected by the SU is free, then he may transmit his own data, otherwise he should wait for the next slot to sense another channel. Let µ i be the expected availability of the i-th channel defined as follows:

µ i = E[θ i ] = Probability(channel i is free) = P(S i (t) = 1) (3.2)
We consider that the channels are ordered by their vacancy probabilities

µ 1 > µ 2 > ... > µ C .
As the vacancy probabilities of channels represented by the vector Γ = {µ 1 , µ 2 , ..., µ C } are unknown, the user has to learn Γ based on the information obtained over time. After evaluating the vector Γ, the target of the user remains to access the best available channel, i.e. µ 1 , in order to increase his transmission time and rate. As µ i is unknown to the user, let us define the regret as the loss of reward between an ideal scenario where the user has a prior knowledge about the vacancy probability of channels and he can always accesses the best one, and the reward obtained from using a particular MAB algorithm. The regret factor is widely used in the literature in order to evaluate the performance of a given algorithm. A MAB algorithm is said to be optimal if the obtained regret is minimal. For a single user, the regret R(n, β) using a given algorithm β up to the total number of slots n can be defined as follows:

R(n, β) = nµ 1 - n ∑ t=1 µ β i (t) (3.3)
where µ β(t) i (t) represents the vacancy probability of the selected channel at slot t using the algorithm β. The regrets of most suggested MAB algorithm, such as Thompson Sampling, UCB and e-greedy achieve a logarithmic asymptotic behavior. Consequently, after a finite number of time slots, the user may have a good estimation of the channels' vacancy probabilities and always selects the optimal one.

Multi-Users

Let us consider U SUs trying to learn the vacant probabilities of channels in order to access only the U best channels. At each time slot t, each user can sense and access a channel when available to transmit. Multiple SUs can work in cooperative or uncooperative modes. The regret for the multi-user Chapter 3. MAB algorithms in OSA for Multiple Users case, no matter if it is under cooperative or competitive modes, can be written as follows:

R(n, U, β) = n U ∑ k=1 µ k - n ∑ t=1 E S β(t) (t) (3.4)
where µ k is the mean availability of the k th best channel; S β(t) (t) stands for the global reward obtained by all users at the time slot t; E(.) represents the mathematical expectation, and β(t) represents all the selected channels1 by users at t. We can define S β(t) (t) by:

S β(t) (t) = U ∑ j=1 C ∑ i=1 S i (t)I i,j (t) (3.5)
where the state variable2 S i (t) = 0 indicates that the channel i is occupied by the PU at slot t, otherwise S i (t) = 1; I i,j (t) = 1 if the j th user is the sole occupant of channel i at the slot t and 0 otherwise. In the multi-user case, the regret may be affected by the collision among the SUs and the vacancy of channels which allows us to define the regret for the U SUs as follows:

R(n, U, β) = n U ∑ k=1 µ k - U ∑ j=1 C ∑ i=1 P i,j (n)µ i (3.6)
where P i,j (n) = ∑ n t=1 E I i,j (t) stands for the expectation of times when the user j is the sole occupant in the channel i up to time n. In the following section, we propose a novel cooperative policy for the priority access to manage a secondary network.

Cooperative learning with a Side Channel policy

The coordination among the SUs can enhance the efficiency of their network, instead of dealing with their partial information about the environment. To manage a cooperative network, we propose a policy based on the use of a Side Channel in order to exchange simple information among SUs with a very low information rate. The Side Channels are widely used in wireless telecommunication networks to share data among the base-stations [START_REF] Van Bosse | Signaling in telecommunication networks[END_REF],

and specifically in the context of cognitive network. However, in [START_REF] López-Martínez | A superprocess with upper confidence bounds for cooperative spectrum sharing[END_REF] and [START_REF] Feng | Cooperative spectrum sharing in cognitive radio networks: A distributed matching approach[END_REF], the authors considered the cooperative spectrum sharing among PUs and SUs to enhance the transmission rate of the PUs using a side channel. The signaling channel in our policy is not wide enough to allow high data rate transmission unlike the ones proposed in [START_REF] López-Martínez | A superprocess with upper confidence bounds for cooperative spectrum sharing[END_REF] and [START_REF] Feng | Cooperative spectrum sharing in cognitive radio networks: A distributed matching approach[END_REF] which should have a high rate to ensure the data transmission among PUs and SUs. In our policy, the transmission is done over periods. During the first period, i.e. Sub-Slot1, SU 1 (the highest priority user) searches the best channel by maximizing his index. At the same time, and via the secure channel, SU 1 must inform the other users to evacuate his selected channel in order to avoid any collision with him (see algorithm 4). While avoiding the first selected channel, the second user SU 2 should repeat the same procedure and so on. If SU 2 does not receive the choice of SU 1 in the first Sub-Slot1 (suppose that SU 1 does not need to transmit during this Sub-Slot), it can choose directly the first suggested channel by maximizing his index B i,2 (t, T i,2 (t)). To the best of our knowledge, all proposed policies, such as SLK, k th MAB consider a fixed priority, i.e. the k th best channel is reserved for the k th user all the time. Then, if SU 1 does not transmit for a certain time, the other users cannot select better channels. Subsequently, the main advantages of the cooperation in this policy are:

• An efficient use of the spectrum where best channels are constantly accessed by users.

• An increase in the users' transmission time by avoiding the collision among them.

• Reaching a lower regret compared to several existing policies.

for a single user. Later on, we evaluate the performance of the proposed learning policy to help users to learn collectively the vacancy probability of channels.

In OSA, the user is supposed to select one channel at each time slot and transmits his data if the targeted channel is free. Otherwise, he should wait the next slot to select another channel. We evaluate the performance of the MAB algorithms in OSA using three important criteria: Regret, P best and the throughput. The Regret measures the speed of the convergence and represents the difference between the reward obtained from the ideal scenario and that obtained from a given policy. P best represents the percentage of times to access the best channel; this is the guarantee that the learning MAB algorithm converges and always selects the best channel. Finally, the throughput represents the percentage of successful transmission by the SU. Without a prior knowledge about the vacancy of the channels, the best successful transmission achieved by the SU may not exceed the availability probability of the best channel. Indeed, a given policy is considered as optimal whereas the best channel is distinguished and always been selected by the user. Moreover, in the ideal scenario where the vacancy probabilities of channels are considered as known, the best strategy for users is to regularly select the best channel with the highest vacancy probability. Subsequently, the best throughput achieved by user is related to the vacancy probability of the best channel.

In our simulations, we consider 9 IID channels ordered by their availability as follows Γ = [0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1] and we suppose that only one SU is trying to learn the availabilities of channels in order to access the most vacant one, i.e. µ 1 = 0.9. For UCB, the exploration-exploitation factor α is set to 1.5. According to several studies [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF][START_REF] Jouini | Multi-armed bandit based policies for cognitive radio's decision making issues[END_REF][START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF][START_REF] Giuseppe | A survey of online experiment design with the stochastic multi-armed bandit[END_REF], α should be higher than 1 in order to ensure the convergence of the UCB. When α increases, UCB gives more weight to the exploration factor A(t, T i (t)) in order to gather more information about the vacancy probability of channels while the exploitation factor X i (t, T i (t)) becomes less important. Unlike UCB, in e-greedy the exploration-exploitation phases are separated and the period of each of them depends on the exploration factor H. According to [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], the value of H should be higher than 90 in order to have a good estimation about the vacancy probability of channels and then access the optimal one. After the initialization part, P best approximately increases in a similar way for the three algorithms. After hundreds of slots, Thompson Sampling outperforms UCB and e-greedy. Up to 1000 slots, Thompson Sampling achieves 85 % of the best channel, while e-greedy achieves around 70 % and finally UCB produce the worst result with only 55 %. Another important metric, widely used in the literature in order to evaluate the performance of the MAB algorithms in OSA, is the throughput capacity (also known as successful transmission). According to Fig. 3.5, we can conclude that the user can find more opportunities using Thompson Sampling with a successful transmission that can reach around 90 %. While under UCB or e-greedy around 85 % of the transmission is achieved.

In the following simulations, we consider 3 SUs with 10 channels and their vacancy probabilities are given by: Γ = [0.9 0.8 0.7 0.6 0.5 0.45 0.4 0.3 0.2 0.1] The percentage of times where each SU k selects his optimal channel using a given approach can be defined as follows: Fig. 3.6 presents P k best (t) of our policy under the three learning algorithms. It shows, as obtained for the single user case, that the P k best (t) is divided into three parts: Initialization, adaptation and convergence. Subfigures (a), (b) and (c) show P k best (t) for our policy under Thompson Sampling, UCB and e-greedy respectively. In each case, three users with different priority levels are considered. Subfigure (d) compares P k best (t) of the first priority user under each algorithm. From our simulations, and based on our policy, one can conclude that users can reach their dedicated channels according to their prior rank. As we can observe, in subfigures (a), (b) and (c), the first priority user SU 1 converges towards the best channel µ 1 , followed by SU 2 and SU 3 towards the second and third best channels µ 2 and µ 3 respectively. In addition, we notice in subfigure (d) a high convergence speed of our policy with TS compared to UCB and e-greedy. Fig. 3.7 depicts the regret defined in equation (3.6), where the proposed approach achieves a logarithmic regret for the three learning algorithms (i.e. Thompson Sampling, UCB and e-greedy). Under our policy, the same figure shows that Thompson Sampling achieves a lower regret compared to UCB or e-greedy. This is due to the fact that Thompson Sampling can learn the vacancy probabilities of channels in a more efficient way and then achieves better results.

P k best (t) = n ∑ t=1 1 (i f a(t)=k)
Random Rank [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF] and Selective Learning of the k-th largest expected rewards (SLK) [START_REF] Gai | Decentralized online learning algorithms for opportunistic spectrum access[END_REF] are two policies proposed in the literature to manage a secondary network in which several users share the frequency band. These policies have been suggested based on UCB algorithm. Our proposed policy and SLK take into account the priority access in which each user has a prior rank. However, in Random Rank, no fixed or prior rank is considered, and after each collision, the users regenerate uniformly their ranks from {1, ..., U}. As we can see in Fig. 3.8, our policy outperforms Random Rank and SLK policies by achieving the lowest regret.

Conclusion

In this chapter, we introduced the well-known algorithms: Thompson Sampling (TS), Upper Confidence Bound (UCB) and e-greedy in order to tackle the MAB problem. Then, we investigated the performance of the mentioned algorithms in the context of OSA. We started by modeling the basic OSA as a MAB problem in which one SU is considered to learn the vacancy probability of channels and then access the best one. Then, we proposed a cooperative learning policy called Side Channel in order to consider the multi-access case in OSA. Indeed, in OSA several SUs may exist in the network and the main issue is to learn collectively the vacancy probability of channels while decreasing the collision among users. In our policy, the users can exchange their choices using a Side Channel in order to avoid any collision among them. Moreover, in our work we are interested in the priority access in which, and based on our proposed policy, the users have different priority levels.

In order to evaluate the performance of MAB algorithms applied in OSA, for a single or multiple users, we used two main factors: the regret (i.e. loss of reward) and the P best . The former represents the widely used parameter in the literature to study the convergence speed towards the optimal choice while the latter confirms that a given MAB algorithm is converged to the optimal channel. In our simulation, we investigated the performance of our proposed policy under TS, UCB and e-greedy. The obtained results showed that a better performance can be reached using TS. Based on our policy for the priority access, the first priority user converges towards the first optimal channel followed by the second and third users to their dedicated channels. Finally, we compared the regret of our policy with those of Random Rank and SLK that have a logarithmic asymptotic behavior and proved that Side Channel achieved the optimal regret.

Introduction

In order to enhance the spectrum learning and obtain better results compared to several well-known Multi-Armed Bandit (MAB) algorithms, we propose two novel algorithms based on Upper Confidence Bound (UCB): e-UCB and AUCB. Well-known MAB algorithms, as well as e-UCB and AUCB, contain two phases: exploration and exploitation. These algorithms generally try to decrease the total regret defined as the gap between the reward obtained in the ideal scenario and that obtained using a given MAB algorithm. Based on e-UCB and AUCB, the Secondary User (SU) can quickly reach the optimal channel (the most vacant one). Subsequently, the SU is not only able to find an opportunity in the licensed band but he will also increase his transmission time and rate in the long-term. Analytical convergences of e-UCB and AUCB are investigated and we will show that the regret can achieve a logarithmic asymptotic behavior with respect to time. That means, after a finite time slots the user is able to learn the vacancy probabilities of channels and will always select the optimal one. Later on, we extend the proposed algorithms to consider multiple users by considering two possible models: Cooperative or competitive. The cooperative access enables users to exchange information with each other in order to maximize a common function (e.g. the throughput of the network). While, the competitive access is more challenging: The collision among users can cause a loss of reward and all users need to learn separately the vacancy probabilities of channels.

The organization of this chapter is as follows: Section 4.2 introduces the proposed MAB algorithm e-UCB and investigates the upper bound of its regret. In section 4.3, we present AUCB and the upper bound of its regret. In section 4.4, the proposed MAB algorithms are extended to consider multiple users under two models: Cooperative and competitive. In section 4.5, we evaluate the performance of our algorithm for a single or multiple users. Finally, section 4.6 concludes this chapter.

Distributed Learning and Access Algorithms

In this section, we propose a novel learning algorithm called e-UCB, to tackle the OSA problem and help a SU to make a decision. In the literature, several algorithms have been proposed to solve the MAB problem: Thompson Sampling (TS), UCB, e-greedy, EXP3, etc. TS represents a simple but effective algorithm that can exceed the state of the art of other MAB algorithms. However, TS is almost neglected in the literature because it was first proposed without any analytical proof. Recently, TS attracts more and more attention and is being successfully applied in a wide variety of domains. Nevertheless, we have the formal proof of its upper bound and optimal regret. In this section, we propose e-UCB that can achieve better results compared to UCB or e-greedy. We also show the analytical proof of e-UCB for a single user.

e-UCB for Opportunistic Access

UCB represents a popular MAB algorithm that is proposed with a solid mathematical background. Several versions of UCB have been proposed to tackle the MAB problem and improve the performance compared to the classical UCB: UCB1, UCB2, UCB-tuned, UCB-Bayes. UCB1, proposed in [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], is widely used in Opportunistic Spectrum Access (OSA) to manage a secondary network for a single or multiple users. The importance of UCB1 is due to the fact that this algorithm achieves a trade-off between the optimality and the complexity. Like all MAB algorithms, UCB1 provides two phases in order to learn the vacancy probabilities of channels: exploration and exploitation. In UCB1, each channel has assigned an index, B i (t, T i (t)), where T i (t) denotes the number of times that the i-th channel was selected by the user up to the slot t. B i (t, T i (t)) is mainly based on the exploitation, X i (T i (t)) 1 , and the exploration, A i (t, T i (t)):

B i (t, T i (t)) = X i (T i (t)) + A i (t, T i (t)) (4.1)
The two factors X i (T i (t)) and A i (t, T i (t)) can be defined as follows:

X i (T i (t)) = 1 T i (t) t ∑ j=1 r i (j) (4.2) A i (t, T i (t)) = α ln(t) T i (t) (4.3)
where r i (j) stands for the reward obtained from the i-th channel at the instant j, 1 ≤ j ≤ t; r i (j) = 1 if the channel i is free, and 0 otherwise; α represents the exploration-exploitation factor.

62

Chapter 4. Distributed Learning for the Priority Cognitive Access Besides UCB1, e-greedy represents another important algorithm first proposed in [START_REF] Cornish | Learning from delayed rewards[END_REF]. According to a recent version of e-greedy proposed in [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], the user selects a random channel if χ (a random variable ∈ [0,1]) < t = min {1, H t } and H is a constant number, else SU selects the most vacant channel.

During the learning epoch, the exploration phase represents a fundamental step to gather information about the vacancy probabilities of channels but it should loss its importance over time 2 . Indeed, the exploration factor A i (t, T i (t)) in UCB1 plays an important role in order to explore the vacancy of channels. Moreover, this factor has the same weight at any given time up to the total number of slots. On the other hand, in the case of e-greedy, the exploitation and exploration are separated. Indeed, the user explores the vacancy of channels if a uniform random variable χ < t , where t = min {1, H t } otherwise, the user exploits the gathered information by selecting the channel with the highest expected reward X i (T i (t)). Subsequently, the user may select many bad channels in the learning phase, i.e. χ < t . Moreover, due to the random selection process during the exploration phase, a large number of collisions may occur and many transmissions can be lost. To solve the mentioned limitations of UCB1 and e-greedy, we propose e-UCB that may learn the vacancy of channels faster than UCB1 and e-greedy. Similarly to UCB1 and e-greedy, in e-UCB, each channel has assigned an index B i (t, T i (t)) and at each time slot, the user tries to select the channel with the highest index B i (t, T i (t)) if χ < t , otherwise the user selects the channel with the highest expected reward X i (T i (t)), see algorithm 5.

Regret Analysis For e-UCB

In this section, we investigate the upper bound of regret for e-UCB for a single user. Let C be the number of independent identically distributed (I.I.D.) channels and Γ = {µ i } stands for the availability vector. For a single user, the regret R(n, β) (i.e. the loss of reward by selecting a non-optimal channel) up to the total number of slots n under a given policy, β, can be expressed as follows:

R(n, β) = nµ 1 - n ∑ t=1 µ β i (t) (4.4)
where nµ 1 means that the channel µ 1 has always been selected up to time n in an ideal scenario; to vacancy probability) obtained from the i th channel selected at time slot t using a given MAB algorithm β. Let T i (n) denote the total number of times that the i-th channel was selected by the user up to the total time of slots n. Due to hardware constraints, we suppose that the user can only sense one channel at each time slot, then:

µ β i (t
C ∑ i=1 T i (n) = n
Hereinafter, we show that the upper bound of regret for e-UCB achieves a logarithmic asymptotic behavior. So, after a finite number of time slots, the user can identify the best channel, µ 1 . The regret in eq. ( 4.4) can be expressed

R(n, β) = nµ 1 - C ∑ i=1 T i [n]µ i = C ∑ i=1 E T i (n) µ 1 - C ∑ i=1 E T i (n) µ i = C ∑ i=1 E T i (n) ∆ i (4.5)
where E[.] is the expectation and

∆ i = µ 1 -µ i .
According to e-UCB, the user selects each channel once during the initialization phase and every time a t = i; then, T i (n) can be written as follows:

T i (n) = 1 + n ∑ t=C+1 1 {a t =i} (4.6)
where 1 {a t =i} equals 1 if a t = i and 0 otherwise. Up to time n, the user may select each channel at least l times; then, according to (4.6), T i (n) can be bounded as follows:

T i (n) ≤ l + n ∑ t=C+1 1 {a t =i;T i (t-1)≥l} (4.7)
In e-UCB, the user may select the i th non-optimal channel either in the exploration or exploitation phases. Let M i and N i be the events that the user selects the i th channel during exploration and exploitation respectively, and let D be the event that T i (t -1) ≥ l. Then, T i (n) can be expressed as follows:

T i (n) ≤ l + n ∑ t=K+1 1 {M i (t);D} + n ∑ t=K+1 1 {N i (t);D} (4.8)
In the above equation, the second and third terms follow the Bernoulli distribution i.e. E{X} = p{X = 1} where X is a random variable in {0, 1} . In this case, the expectation of T i (n) can be written as:

E[T i (n)] ≤ l + n ∑ t=K+1 p{M i (t); D} A + n ∑ t=K+1 p{N i (t); D} B (4.9)
According to e-greedy, the user selects the i th channel during the exploration phase if at (t -1), B i (t -1, T i (t -1)) > B 1 (t -1, T 1 (t -1)). Subsequently, A can be expressed as follows:

A = p χ < t ; B i (t -1, T i (t -1)) ≥ B 1 (t -1, T 1 (t -1)); D
The event χ < t in the above equation is independent of the selection procedure. Then, we obtain:

A = t × p B i (t -1, T i (t -1)) ≥ B 1 (t -1, T 1 (t -1)); D So, we get: A ≤ 2H × t -2α+1
Proof. appendix A According to Cauchy theorem [START_REF] Al Cauchy | [END_REF], a series of the form ∑ n t=1 t -2α+1 can converge if α > 1. Let α = 2 (in order to achieve a balance between the explorationexploitation phases), then we obtain:

n ∑ t=C+1 A ≤ 2H × n ∑ t=1 t -3 ≤ π 2 H 3
Let us find an upper bound of B in eq. ( 4.9) that referred to the the probability to access the i-th channel in the exploitation phase. Indeed, during the exploitation phase, the user may select the i-th channel at time slot t whereas X i (T i (t -1)) > X 1 (T 1 (t -1)) at t -1. Then, we get the following inequality:

B = p χ ≥ t ; X i (T i (t -1)) ≥ X 1 (T 1 (t -1)); D (4.10)
Since the two events χ ≥ t and X i (T i (t -1)) ≥ X 1 (T 1 (t -1)) are completely independent, we obtain:

B = 1 -t × p X i (T i (t -1)) ≥ X 1 (T 1 (t -1)); D (4.11)
The probability p in the above equation can be bounded as follows:

p X i (T i (t -1)) ≥ X 1 (T 1 (t -1)); D ≤ Y + Z (4.12)
where Y = p X i (T i (t -1)) ≥ a; D , Z = p X 1 (T 1 (t -1)) ≤ a; D , and a is a constant number that can be chosen as:

a = µ 1 +µ i 2 = µ 1 -∆ i 2 = µ i + ∆ i 2 .
Let us first consider, the first term of eq. (4.12): Chapter 4. Distributed Learning for the Priority Cognitive Access

Y = n ∑ y=l p X i (T i (t -1)) ≥ µ i + ∆ i 2 ; T i (t -1) = y = n ∑ y=l p X i (y) ≥ µ i + ∆ i 2 ; T i (t -1) = y ≤ n ∑ y=l p X i (y) ≥ µ i + ∆ i 2 (4.13)
Using the Chernoff-Hoeffding theorem in [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] 3 , we can upper bound the above equation as follows:

Y ≤ n ∑ y=l exp - 2∆ 2 i y 2 4y ≤ n exp -l∆ 2 i 2
According to the proof provided in appendix A, we consider l = 8 ln(n)

∆ 2 i
. So, we get:

Y ≤ n exp -4 ln n = 1 n 3 (4.14)
The upper bound of Z can be expressed as: Z ≤ 1

n 3
Proof. appendix B Finally, E[T i (n)] can be upper bounded by:

E[T i (n)] ≤ 8 ln n ∆ 2 i + π 2 H 3 + 2 n 3 (4.15)
From the above inequation, we conclude that the user plays each arm no more than 8 ln n ∆ 2 i plus a constant number. Finally, based on eq (4.5) and (4.15), the regret of e-UCB, R(n, e-UCB), can be upper bounded by the following equation:

R(n, e-UCB) = 8 ln n C ∑ i=2 1 ∆ i + π 2 H 3 + 2 n 2 C ∑ i=1 ∆ i (4.16)
3 According to [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF], Chernoff-Hoeffding theorem is stated as follows: Let X 1 , ..., X n be random variables in {0, 1}, and E[X t ] = µ, and let S n = ∑ n i=1 X i . Then ∀ a ≥ 0, we have

P{S n ≥ nµ + a} ≤ exp -2a 2 n and P{S n ≤ nµ -a} ≤ exp -2a 2 n .
4.3. Exploration-Exploitation Dilemma of UCB 67

Exploration-Exploitation Dilemma of UCB

Lower Exploration Impact with AUCB

In this section, we propose an improved version of UCB called Arctan-UCB (AUCB). AUCB achieves better performance with respect to previous versions of UCB. In the previous section, the exploration factor of e-UCB becomes approximately equal to zero after the learning period in which the user gets sufficient information about the vacancy probabilities of channels. While in AUCB, and after the learning period, the impact of the exploration factor decreases without reaching zero as in e-UCB. Indeed, in a dynamic environment in which the availabilities of channels change over time, the exploration factor should keep some importance in order to follow dynamic channels, and thus be adapted to this environment. Hereinafter, we prove analytically that the regret for a single user (the analytically proof for multiple users is included in the next chapter) can achieve a logarithmic asymptotic behavior with respect to time. Subsequently, a SU may quickly find and access the optimal channel (the most vacant one), and then maximizes its transmission time and rate. In the exploration factor of UCB1, A i (t, T i (t)), a non-linear function is used in order to ensure the convergence towards the best channel:

A i (t, T i (t)) = α ln(t) T i (t) (4.17)
where α denotes to the exploration-exploitation factor. This latter has large impact on the behavior of many versions of UCB (e.g. UCB1, UCB2, etc.). For instance, decreasing the factor α may reduce the effect of the exploration factor A i (t, T i (t)) of UCB1. Moreover, by selecting the channel with the highest index B i (t, T i (t)), an additional weight can be added to the exploitation X i (T i (t)). On the other hand, by increasing the value of α, the algorithm spends more time to gather information about the vacancy probabilities of channels. For a large value of α, the expected reward X i (T i (t)) becomes more and more close to the vacancy probabilities of channels. According to several studies [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF][START_REF] Jouini | Multi-armed bandit based policies for cognitive radio's decision making issues[END_REF][START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF][START_REF] Giuseppe | A survey of online experiment design with the stochastic multi-armed bandit[END_REF], the value of α should be in the range ]1, 2] in order to get a balance between exploration-exploitation phases. The impact of α on UCB1 is widely studied in the literature [START_REF] Jouini | Multi-armed bandit based policies for cognitive radio's decision making issues[END_REF][START_REF] Melian-Gutierrez | Hybrid ucb-hmm: A machine learning strategy for cognitive radio in hf band[END_REF][START_REF] Melián-Gutiérrez | Upper confidence bound learning approach for real hf measurements[END_REF]. In this section, we focus on another way to influence the exploration factor by using another nonlinear function. Indeed, the square-root function introduced in eq. (4.17) is Chapter 4. Distributed Learning for the Priority Cognitive Access widely considered [START_REF]Sample mean based index policies with o(log n) regret for the multiarmed bandit problem[END_REF][START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF][START_REF] Tekin | Online algorithms for the multi-armed bandit problem with markovian rewards[END_REF][START_REF] Giuseppe | A survey of online experiment design with the stochastic multi-armed bandit[END_REF] for the following reasons:

• Being a positive function with respect to time t.

• It increases non-linearity which allows to restrict the effect of the exploration after the learning period.

In the case of UCB1, the exploration factor has the same weight at any given time. Thus, the big challenge remains to reduce the effect of the exploration factor after the learning period using another increasing non-linear function with the following features:

• It should have a high derivative with respect to time at the beginning to boost the exploration factor during the learning phase in order to accelerate the estimation of channels availability.

• It should also have a strong asymptotic behavior in order to restrict the exploration factor A i (t, T i (t)) under a certain limit, after the user has collected some information about the vacancy probabilities of channels.

Our study proved that the exploration factor can be adjusted by using the arctan function which is endowed with the above features. Indeed, an improved convergence rate to the best choice can be reached with the arctan compared to the one obtained with the square-root. On the one hand, the effect of the exploration factor A i (t, T i (t)) can be reduced after the learning phase. In the same way, maximizing the index B i (t, T i (t)) can produce some additional weight to the exploitation factor X i (T i (t)). Like the case of e-UCB, we also proved that the regret of AUCB achieves a logarithmic asymptotic behavior.

Regret Analysis

In this section, we prove that the upper bound of regret of AUCB can achieve a logarithmic asymptotic behavior while providing better results compared to e-UCB. According to eq. (4.5) the regret for a single user can be expressed as follows:

R(n, β) = C ∑ i=1 E T i (n) ∆ i (4.18)
As the vacancy probabilities of channels are supposed to be constant, then the upper bound of E T i (n) can imply the upper bound of the regret. T i (n) can be upper bounded by the following expression (also shown is eq (4.7)):

T i (n) ≤ l + n ∑ t=C+1 1 {a t =i;T i (t-1)≥l} (4.19)
As AUCB selects at each time slot the channel with the highest index obtained in the previous slot, the user may access, at the slot t, a non-optimal channel if the index of this channel at (t -1), B i (t -1, T i (t -1)), is higher than the index of the best channel B 1 (t -1, T 1 (t -1)). In this case, we can develop further eq (4.19) as follows:

T i (n) ≤ l + n ∑ t=C+1 1 {B 1 (t-1,T 1 (t-1))<B i (t-1,T i (t-1)) and T i (t-1)≥l} (4.20)
The index of channels

B i (t, T i (t)) = X i (T i (t)) + A i (t, T i (t)
) is based on:

• The exploitation factor X i (T i (t)).

• The exploration factor A i (t, T i (t)). This factor under AUCB is defined as follows: A a t, T i (t) = arctan α ln(t) T i (t) , Using eq (4.20), we can prove that:

T i (n) ≤ l + n ∑ t=C+1 1 {X 1 (T 1 (t-1))+A a (t-1,T 1 (t-1))< X i (T i (t-1)
)+A a (t-1,T i (t-1)) and T i (t-1)≥l} (4.21)

The summation argument in the above equation follows Bernoulli's distribution. In this case, the expectation of T i (n) should satisfy the following constraint:

E[T i (n)] ≤ l + n ∑ t=C+1 P X 1 (T 1 (t -1))+ A a (t -1, T 1 (t -1)) < X i (T i (t -1))+ A a (t -1, T i (t -1)) and T i (t -1) ≥ l (4.22)
The probability in eq (4.22) becomes:

Prob = P X 1 (T 1 (t -1)) -X i (T i (t -1)) ≤ arctan α ln(t) T i (t -1) -arctan α ln(t) T 1 (t -1)
and T i (t -1) ≥ l (4.23)

Chapter 4. Distributed Learning for the Priority Cognitive Access

After the learning period where T i (t -1) ≥ l, the user will have a good estimation of channels availability and thus may access regularly the best channel. Therefore, T i (t -1)

T 1 (t -1); and arctan α ln(t) T i (t-1) ≥ arctan α ln(t) T 1 (t-1) . Using the asymptotic behaviors of the non-linear functions sqrt and arctan, the probability in eq (4.23) becomes bounded by:

Prob ≤ P X i (T 1 (t -1)) -X i (T i (t -1)) ≤ α ln(t) T i (t -1) - α ln(t) T 1 (t -1)
and

T i (t -1) ≥ l (4.24)
By taking the minimum value of X i (T 1 (t -1)) + α ln(t)

T 1 (t-1) and the maximum value of X i (T i (t -1)) + α ln(t)

T i (t-1) at each time slot, we can upper bound eq (4.22) by the following equation:

E[T i (n)] ≤ l + n ∑ t=C+1 P min 0<S 1 <t X 1 (S 1 ) + α ln(t) S 1 ≤ max l≤S i <t X i (S i ) + α ln(t) S i (4.25)
where S i ≥ l to fulfill the condition T i (t -1) ≥ l. Then we obtain:

E[T i (n)] ≤ l + n ∑ t=1 t-1 ∑ S 1 =1 t-1 ∑ S i =l P X 1 (S 1 ) + A 1 (t, S 1 ) < X i (S i ) + A i (t, S i ) (4.26)
The above probability can be upper bounded by:

P X 1 (S 1 ) + A 1 (t, S 1 ) < X i (S i ) + A i (t, S i ) ≤ P X 1 (S 1 ) + A 1 (t, S 1 ) ≤ µ 1 + P µ 1 < µ i + 2A i (t, S i ) + P X i (S i ) + A i (t, S i ) ≥ µ i + 2A i (t, S i ) (4.27)
Using the ceiling operator , let l = 4α ln(n)

∆ 2 i
, where ∆ i = µ 1µ i and S i ≥ l, then the event µ 1 < µ i + 2A i (t, S i ) in eq (4.27) becomes false, in fact:

µ 1 -µ i -2A i (t, S i ) = µ 1 -µ i -2 α ln(t) S i ≥ µ 1 -µ i -2 α ln(n) l ≥ µ 1 -µ i -∆ i = 0
Based on eq (4.26) and (4.27), we obtain:

E[T i (n)] ≤ 4α ln(n) ∆ 2 i + n ∑ t=1 t-1 ∑ S 1 =1 t-1 ∑ S i =l P X 1 (S 1 ) ≤ µ 1 -A 1 (t, S 1 ) + P X i (S i ) ≥ µ i + A i (t, S i ) (4.28)
Using Chernoff-Hoeffding bound [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF], we can prove that:

P X 1 (S 1 ) ≤ µ 1 -A 1 (t, S 1 ) ≤ exp -2 S 1 S 1 α ln(t) S 1 2 = t -2α (4.29) P X i (S) ≥ µ i + A i (t, S i ) ≤ exp -2 S i S i α ln(t) S i 2 = t -2α (4.30)
The two equations above and eq (4.28) lead us to:

E[T i (n)] ≤ 4α ln(n) ∆ 2 i + n ∑ t=1 t-1 ∑ S 1 =1 t-1 ∑ S i =l 2t -2α ≤ 4α ln(n) ∆ 2 i + 1 + 2 n ∑ t=1 t -2α+2 (4.31)
According to the Cauchy theorem [START_REF] Al Cauchy | [END_REF], a series of the form ∑ n t=1 t -2α+2 converges if α > 3 2 . Let α = 2 (in order to achieve a balance between exploration and exploitation phases), then we obtain:

E[T i (n)] ≤ 8 ln(n) ∆ 2 i + 1 + 2 n ∑ t=1 t -2 ≤ 8 ln(n) ∆ 2 i + 1 + π 2 3 (4.
∆ i + 1 + π 2 3 C ∑ i=1 ∆ i (4.33)
According to the above equation, AUCB can yield better results compared to e-UCB in which the upper bound of regret of e-UCB is higher than the one of AUCB (see eq (4.16) and (4.33) for the upper bound of e-UCB and AUCB respectively).

MAB Algorithms with Multiple Users

In this section, we extend the proposed MAB algorithms (AUCB and e-UCB) to consider the case of multiple users trying to learn collectively the channels availability. We consider two possible operation modes: Cooperative and competitive access.

Cooperative Side Channel Policy

We extend our proposed AUCB using the cooperative side channel policy presented in Chapter 3 (Section 3.5) in which users can exchange simple information with a very low information rate. Moreover, the side channel policy takes into consideration the priority access in which, after a finite number of time slots, the k-th user usually accesses the k-th highest entry in the index B i (t, T i (t)) (i.e. the k-th best channel). Based on the side channel policy, the priority user should broadcast the choice of his channel to other users in order to avoid any collision. It should be noticed that the broadcast packet of the priority user has the risk to be lost, then a collision may occur among users and the amount of regret increases. In order to simplify finding an upper bound of AUCB under side channel policy, we consider an error-free channel in which broadcast packet losses do not occur. However, considering no error-free can produce collisions among users and results in adding some constant values to the regret. Hereinafter, we show that the upper bound of the regret has a logarithmic asymptotic behavior. In the case of multiple users, the regret for U users under a policy β, without considering the collision among users can be expressed as follows 4 :

R(n, U, β) = n U ∑ k=1 µ k - C ∑ i=1 U ∑ j=1 µ i E T i,j (n) (4.34)
where µ k represents the k-th best channel; n is the total number of slots and T i,j (n) stands for the number of times that the user j accesses the channel i up to time n.

Let E[T i (n)] = ∑ U j=1 E[T i,j (n)
] be the number of times that the i-th channel is sensed by all users up to time n. By considering that each user can sense one channel at each time slot, we obtain:

C ∑ i=1 E[T i (n)] = nU ⇒ n = 1 U C ∑ i=1 E[T i (n)]
In this case, the regret can be expressed as follows:

R(n, U) = 1 U C ∑ i=1 E[T i (n)] U ∑ k=1 µ k -µ i = 1 U C ∑ i=1 E[T i (n)] U ∑ k=1 ∆ (k,i) (4.35)
where ∆ (k,i) = µ kµ i . To simplify the above equation, we consider the summation over worst and best channels as follows:

R(n, U) = 1 U U ∑ i=1 E[T i (n)] U ∑ k=1 ∆ (k,i) + 1 U C ∑ i=U+1 E[T i (n)] U ∑ k=1 ∆ (k,i) (4.36)
The first term of the regret in eq (4.36) equals 0 whenever i ∈ best channels, then we obtain:

R(n, U) = 1 U C ∑ i=U+1 E[T i (n)] U ∑ k=1 ∆ (k,i) (4.
E[T i (n)] = U ∑ j=1 E[T i,j ] ≤ U ∑ j=1 8 ln(n) ∆ 2 (j,i) + 1 + π 2 3 (4.38)
and the regret of our AUCB under the Side Channel policy can be written as:

R(n, U, AUCB) ≤ C ∑ i=U+1 U ∑ k=1 8 ln(n) ∆ (k,i) + ∆ (k,i) (1 + π 2 3 ) (4.39)
According to the above equation, the global regret of AUCB under the Side Channel policy has a logarithmic upper bound, which means that after a period of time, each user will have a good estimation of the channels availability and each one accesses a channel based on his rank.

Similarly to e-UCB, the upper bound of regret for multiple users can be expressed as follows:

R(n, U, e-UCB) ≤ C ∑ i=U+1 U ∑ k=1 8 ln n ∆ (k,i) + π 2 H 3 + 2 n 2 ∆ (k,i) (4.40)
According to the above upper bound expression of AUCB or e-UCB, we conclude that AUCB can achieve a better result while the users quickly reach their dedicated channels.

Competitive Random Rank Policy

The random access in OSA, cooperative or competitive, is widely suggested in the literature and several policies have been proposed to manage a secondary network. As a matter of fact, if each user tries to reach selfishly the best channel using one of the mentioned MAB algorithms (e-UCB or AUCB), then, a large number of collisions may occur and many transmission data will be lost. Hence, we introduce a simple (but optimal) policy from the literature for the competitive random access. This policy, called Random Rank, was initially proposed under UCB1 (see algorithm 7). During the initialization, and based on the Random Rank policy, each user draws a rank from the set {1, ..., U} where U is the number of users in the network. All users have the same chance to sense and access the i-th channel. As in UCB1, each channel has an assigned index B i (t, T i (t)), and the user should make a decision based on his generated rank. For instance, a user, with a rank equals to 4, should access the fourth highest entry in the index B i (t, T i (t)).

B i (t, T i (t)), X i (T i (t)): B i (t, T i (t))
: the index assigned for channels, X i (T i (t)): the exploitation contribution of channels that depends on T i (t),

Initialization: k = 0, for t = 1 to C do SU k senses each channel once, SU k updates B i (t, T i (t)), X i (T i (t)), A i (t, T i (t)), for t = C + 1 to n do
SU k senses the k-th highest entry in the index B i (t, T i (t)), if ξ k (t) = 1 then SU k generates randomly a new rank from the set {1, ..., U}, else SU k keeps his rank.

SU k updates B i (t, T i (t)), X i (T i (t)), A i (t, T i (t))

Simulation and results

In this section, we evaluate the performance of e-UCB and A-UCB for single and multiple users over 9 channels with the following availability probabilities:

Γ = [0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1] Under the two scenarios, single and multiple users, we evaluate the performance of e-UCB or AUCB using two main parameters: the regret and the percentage of access to the best channel.

Test for a Single User

Let us consider a SU in the secondary network trying to estimate the vacancy probabilities of channels in order to access the best one. In Fig. 4.1, we compare the regret that achieves a logarithmic asymptotic behavior for the 4 MAB algorithms: TS, AUCB, e-UCB, UCB. This result deals with our analytical proof which showed that the upper bound of regret has a logarithmic asymptotic behavior for e-UCB and AUCB. The same figure shows that TS achieves the lower regret. In fact, the good performance of TS is widely suggested for a single user and several studies found an upper bound for its optimal regret that also achieves a logarithmic asymptotic behavior. Despite its high performance for a single user, TS may not achieve a good result for multiple users as shown in the next section. .2 compares the percentage to access the best channel using the 4 MAB algorithms. As mentioned before, TS seems to be a good algorithm that can largely exceed the performance of the state of the art MAB algorithms. For this reason, we adopt TS as a reference in order to evaluate the performance of the two proposed MAB algorithms AUCB and e-UCB. As it can be seen in Fig. 4.2, the 4 MAB algorithms can reach the best channel after a finite number of time slots, while TS represents the best one.

Test for Multiple Users

In this section, we consider the case of multiple users trying to learn the vacancy probabilities of channels. To fix our idea, let us consider 3 SUs that want to learn and access the 3 best channels (i.e. µ 1 = 0.9, µ 2 = 0.8, µ 3 = 0.7) under two possible scenarios: cooperative and competitive access. The cooperation among users has an important role to enhance the spectrum efficiency and to guarantee an optimal sharing of available spectrum. Indeed, the collaboration among users, on the one hand, may lead to a full and quick estimation of the vacancy probabilities of channels. On the other hand, it is necessary to mitigate the harmful interference with PUs. While in the competitive access, each user selfishly makes its own action without any cooperation with others. Despite the increasing number of collisions compared to the cooperative access, the competitive access may decrease the complexity of the network and can be useful in several scenarios. Let us first consider the cooperative priority access based on the Side Channel policy. Fig. 4.3 represents the regret of the 4 MAB algorithms AUCB, TS, e-UCB and UCB1. As it can be seen, the regrets for all algorithms have logarithmic asymptotic behaviors in which the users are able to estimate the vector Γ and often access their dedicated channels. Moreover, based on the Side Channel policy in which no-collision can occur among users, the TS achieves best results followed by AUCB, e-UCB and UCB1 respectively. Fig. 4.4 represents the percentage of times to access the best channels by each user. As we can see, using our Side Policy policy, the users are able to converge towards their dedicated channels: SU 1 converges to the best channel "µ 1 " followed by SU 2 and SU 3 to the second "µ 2 " and third "µ 3 " best channels respectively. Moreover, the users converge quickly to their dedicated channels under TS followed by AUCB, e-UCB and UCB1.

It remains to compare the performance of the 4 MAB algorithms under competitive access. The regrets of the mentioned algorithms are depicted in Fig. 4.5 with the Random Rank policy for multiple users. In the latter policy, the target of the k-th user is to access one of the U best channels and not a specific one as is the case of the Side Channel policy. Despite its optimal convergence for a single user or multiple cooperative users, TS may not achieve the best result for multiple competitive users as shown in Fig. 4.5. In fact, for competitive multiple users, the performance for a given MAB algorithm depends on the access of bad channels and also on the number of collisions among users. Those two factors are related to the exploration impact of MAB algorithms.

Indeed, the impact of the exploration factor should decrease after the learning period, as in AUCB, after the user has got sufficient information about the vacancy probabilities of channels. While in the case of TS, the exploration factor is still having the same weight at any given time, which basically produces a large number of collisions compared to AUCB. This explains why, for multiple users using Random Rank policy, AUCB attains a lower regret and reaches better performance compared to TS. Fig. 4.5 also shows that TS gives better results than e-UCB. Indeed, due to the high exploration impact during the learning period, users access many bad channels which increases the regret. Moreover, a high exploration level may significantly increase the number of collisions among users and by the same way the global regret. According to our simulations, TS represents an optimal solution for a single user but not necessary for multiple users. More precisely, TS is very sensitive to the number of collisions. Indeed, a high level of collisions number among users, under a given policy, can decrease rapidly the convergence speed towards the optimal channels.

Conclusion

In this chapter, we proposed two Multi-Armed Bandit (MAB) algorithms, called Arctan-Upper Confidence Bound (AUCB) and e-UCB, in order to apply them in the Opportunistic Spectrum Access (OSA). In OSA, a SU tries to estimate the vacant probabilities of channels in order to reach the optimal one with the highest vacancy probability. It has been shown that the proposed MAB algorithms achieves a good result in OSA compared to several wellknown MAB algorithms such as UCB1 or e-greedy. However, AUCB and e-UCB cannot exceed the performance of the Thompson Sampling (TS) that seems to exceed the state of the art of MAB algorithms. We also investigate the upper bound of regret (i.e. the loss of reward due to the selection of worse channels) that achieves a logarithmic asymptotic behavior for AUCB and e-UCB. According to the obtained upper bound, AUCB achieves a lower regret compared to e-UCB and thus, can reach the best channel faster than this latter. We also studied the performance of the proposed MAB algorithms for multiple users under two operation modes: Cooperative or competitive access. For the cooperative access, we use our proposed Side Channel policy that takes into account the priority access. We also proved the analytical upper bound of the two proposed MAB algorithms under our policy. For the competitive access, we used Random Rank, an existing policy in the literature to manage a secondary network for the random access. Through our simulations, we can say that TS represents a suitable solution for single or multiple cooperative users compared to AUCB, e-UCB, UCB1 and e-greedy. While, for the competitive access, TS may not achieve the best performance, as a result of the collisions among users, and thus our proposed AUCB achieves better results.

Introduction

As mentioned in previous chapters, Multi-Armed Bandit (MAB) algorithms in Opportunistic Spectrum Access (OSA) can represent a suitable solution to enhance the spectrum usage. The well-known MAB algorithms, such as: Thompson Sampling (TS), Upper Confidence Bound (UCB) and e-greedy have been firstly suggested for a single user case. Recently, several policies have been proposed to extend the MAB algorithms to consider multiple users under cooperative or Competitive accesses. Moreover, these different existing policies can be classified into two main categories: Random access or priority access. In our work, we are interested in the priority access with cooperative or competitive users access that may represent a suitable solution in a tactical network. In the previous chapters, we proposed a novel policy for the cooperative priority access; while in this chapter, we focus on the Competitive priority access. The kind of priority access was not well studied in the literature since the most recent works focus on the random access. Moreover, we particularly focus on the priority dynamic access in which the priority users can leave and enter to the network at any time, while, to the best of our knowledge, only the priority or the dynamic access are considered in several existing works. Later on, we consider the quality of service (QoS) in the secondary network. In this new model, a SU should be able to estimate the availability of channels and consider as well as their qualities. After gathering sufficient information about available channels, the users should only access optimal ones characterized by their highest availability and quality. The organization of this chapter is as follows. Section 5.2 introduces a novel competitive priority policy, called All-Powerful Learning (APL). In section 5.3, we prove that the upper bound of the regret of APL achieves a logarithmic asymptotic behavior. In section 5.4, we study the QoS of AUCB. In section 5.5, we suggest a novel policy to consider different priority levels. Numerical results are presented in section 5.6 in which the performance of APL compared to several existing policies is shown. Finally, section 5.7 concludes the chapter.

Multiple Users for Competitive Access

In the literature, few studies have considered the cooperative access in OSA while the Competitive access is widely treated and many competitive policies have been proposed. The main advantage of the competitive access is the reduction of the network complexity compared to a cooperative access. Indeed, in the latter case, the users should collaborate and exchange some information about their environment in order to make a collective decision which can increase the performance of the cognitive network.

The main challenge in the competitive access remains to learn collectively the vacant probabilities of channels while decreasing the number of collisions among users. In this section, we focus on the competitive access and more precisely on the priority competitive access. First, we discuss the existing policies to manage a secondary network and their drawbacks; then, we propose a novel policy for the priority dynamic access.

Random Access

In a random access, the main target of users is to access one of the optimal channels and not necessarily the most vacant one. Indeed, if all users try to reach the same highly vacant channel, this would cause a large number of collisions among them. A Random Rank policy represents one of the important policies for the random access [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF]. Based on the Random Rank policy, each user should make an action depending on a rank generated randomly from a set {1, ..., U} after each collision. Only collided users should seek a novel rank, while the others keep their current ranks. Musical Chair represents another important policy for the random access [START_REF] Rosenski | Multi-player bandits-a musical chairs approach[END_REF]. In this policy, the users select the channels randomly during the learning period in order to gather information about the vacant probabilities of channels (Exploration phase). Moreover, during the learning period and based on the collision number, users should estimate their number U in the network using the following equation [START_REF] Rosenski | Multi-player bandits-a musical chairs approach[END_REF]:

U ≈ min round log T 0 -C T 0 T 0 log 1 -1 C + 1 , C (5.1)
where C is the number of channels; T 0 represents the duration of the learning period; C T0 is the number of collisions during T 0 . After the learning period, the user accesses a random channel from the U best channels. When a collision occurs, the user chooses randomly another best channel; otherwise, he keeps selecting the same channel. Besides Musical Chair, the Multi-user e-greedy collision Avoiding (MEGA) policy proposed in [START_REF] Avner | Concurrent bandit and cognitive radio networks[END_REF] can achieve a random access. MEGA policy is an extension of the e-greedy firstly proposed in [START_REF] Cornish | Learning from delayed rewards[END_REF] for a single user. According to [START_REF] Rosenski | Multi-player bandits-a musical chairs approach[END_REF], Musical Chair achieves better results compared to MEGA. For this reason, we will compare the performance of our proposed policy to Musical Chair.

Priority Access

The priority access in OSA is not well considered in the literature. Moreover, and to the best of our knowledge, existing MAB algorithms cannot be used for the priority dynamic access in which other users can't enjoy a dedicated channel of a leaving user, as shown in Fig. 5.1. k-th MAB [START_REF] Torabi | Rank-optimal channel selection strategy in cognitive networks[END_REF] and SLK (Selective learning of the K-th largest expected rewards) [START_REF] Gai | Decentralized online learning algorithms for opportunistic spectrum access[END_REF] represent two MAB policies proposed in the literature to address the priority access in the secondary network. Based on the k-th MAB, each user has a known rank and he should access the channels respecting his rank.

The main idea consists on slotting in the time and each slot is divided into multi sub-slots depending on the user priority ranks. Therefore, the transmission time under a large number of users tends towards zero. For the higher ranking users, this fact becomes the major limitation of this policy. In addition, this policy does not consider the dynamic access and the number of users should be fixed and known in advance. Based on UCB1, the authors of [START_REF] Gai | Decentralized online learning algorithms for opportunistic spectrum access[END_REF] proposed the SLK algorithm, an efficient algorithm for the priority access, that does not have the limitation of the k-th MAB. However, as in the latter policy the number of users must be fixed and previously known by each user.

All-Powerful Learning for the Priority Access

In this section, we propose a new policy for the priority access. This policy enables a secondary user to learn the vacant probabilities of channels and ensures the convergence to his dedicated channel. Moreover, it can be used with all learning MAB algorithms such as: Thompson Sampling (TS), Upper Confidence Bound (UCB), AUCB, e-UCB, e-greedy, etc. We should highlight that our proposed policy does not require prior knowledge about the channels as in the case for other policies, such as: Musical Chair [START_REF] Rosenski | Multi-player bandits-a musical chairs approach[END_REF], SLK [START_REF] Gai | Decentralized online learning algorithms for opportunistic spectrum access[END_REF], k-th MAB [START_REF] Torabi | Rank-optimal channel selection strategy in cognitive networks[END_REF], MEGA [START_REF] Avner | Concurrent bandit and cognitive radio networks[END_REF], Side Channel [START_REF] Almasri | Opportunistic spectrum access in cognitive radio for tactical network[END_REF], etc. Indeed, existing policies to manage a secondary network suffer from one or more of the following disadvantages:

1. The number of users should be fixed and known to all users.

2. SUs should have a prior information about the number of channels.

3. Expected transmission time should be known.

4. The dynamic access is not suggested. To recall, in a dynamic access, the users can at any given time enter or leave the network.

5. Some algorithms consider a restricted dynamic access, where a SU can't leave the network during the learning or the exploration phases.

6. The vacant probabilities of channels should be static; otherwise, users cannot adapt to their environment.

7. The priority access is seldomly suggested in the literature, while the random access represents the most used model.

Unlike SLK and k-th MAB, our proposed policy for the priority access, called All-Powerful Learning algorithm (APL), doesn't suffer from the above mentioned drawbacks. As a matter of fact, SLK and k-th MAB policies suffer from the 1 st , 2 nd and 4 th mentioned drawbacks. In a classical priority access, each channel has assigned an index B i (t) and the highest priority user SU 1 should sense and access the channel with the highest index B i (t) at each time slot. Indeed, the best channel, after a finite number of time slots, will have the highest index B i (t).

As the second priority user SU 2 should avoid the first best channel and try to access the second best one. To reach his goal, SU 2 should sense the first and second best channels at each time slot in order to estimate their vacant probabilities and then access the second best channel if available. In this case, the complexity of the hardware is increased, and we conclude that a classical priority access represents a costly and impractical method to settle down each user to his dedicated channel. In the case of APL, at each time slot, the user senses a channel and transmits his data if the channel is available (see algorithm 1). In our policy, each SU k has a prior rank, k ∈ {1, ..., U}, and his target is to access the k-th best channel. The major problem of the competitive priority access is that each user should selfishly estimate the vacant probabilities of the available channels. Our policy can intelligently solve this issue by making each user generate a rank around his prior rank to get information about the channels availability. For instance, if the rank generated by the k-th user equals 3 (considering that k > 3), then he should access the channel that has the third index, i.e. B 3 (t). In this case, SU k can examinate the states of the k best channels and his target is the k-th best one.

However, if the rank created by SU k is different than k, then he selects a channel with one the following probabilities: {µ 1 , µ 2 , ..., µ k-1 } and he may collide with a priority user, i.e. SU 1 , SU 2 , ..., SU k-1 . Therefore, SU k should avoid regenerating his rank at each time slot; otherwise, a large number of collisions may occur among users and transmitted data can be lost. So, after each collision, SU k should regenerate his rank from the set {1, ..., k}. Thus, after a finite number of slots, each user settles down to his dedicated channel. It remains to investigate the analytical convergence of APL to verify its performance in a real radio environment. As a second-major contribution of this chapter, we propose and develop MAUCB which is an extension of our previous algorithm AUCB presented in chapter 4. To present MAUCB, we first need to define the regret. Let us introduce the definition of the regret for multiple users that takes into consideration not only the access to the bad channels but also the collision among users. Under a policy β, the regret represents the difference between the obtained reward in the ideal scenario, S * (n, U), in which best channels are known and accessed by the SUs, and the reward obtained using a given policy, S(n, U, β):

R(n, U, β) = S * (n, U) -S(n, U, β) (5.2)
S * (n, U) and S(n, U, β) are defined as follows:

S * (n, U) = n U ∑ k=1 µ k (5.3) S(n, U, β) = C ∑ i=1 U ∑ j=1 µ i E[P i,j (n)] (5.4)
where n stands for the total number of slots; µ k represents the vacant probability of the k th best channel; E[.] is the expectation and P i,j (n) represents the number of times where user j is the only occupant of the channel i up to n. Let T i,j (n) be the total number of times where the j th user senses the i th channel up to n. For the sake of notational simplicity, we consider T i (n) = ∑ U j=1 T i,j (n) and P i (n) = ∑ U j=1 P i,j (n) as the total number of times where the i-th channel is sensed by all users, and the total number of times where the users access the i-th channel without producing any collision up to n. Let O k (n) be the number of collisions in the k-th best channel as well T k (n) and P k (n) being respectively the total number of times where the k-th best channel is sensed by all users and the total number of times where the users access the k-th best channel without making any collision up to n. O k (n) can be expressed as follows:

O k (n) = T k (n) -P k (n) (5.5)

Chapter 5. Competitive Priority Cognitive Access

It is worth mentioning that the number of channels C should be higher than the number of active users U, otherwise:

• Using a learning algorithm to find the best chan-nels does not make any sense, since all channels need to be accessed.

• Considering that the user should sense one channel at each time slot, at least one collision may occur among users, and users cannot converge to free-collision state under any learning policy.

Subsequently, by considering that C ≥ U and µ 1 ≥ µ i , ∀ i, we can upper bound the regret in eq (5.

2) of MAUCB using APL as follows:

R APL (n, U, MAUCB) ≤ n U ∑ k=1 µ k - U ∑ k=1 µ k E P k (n) ≤ µ 1 Un - U ∑ k=1 E P k (n) (5.6)
Based on the assumption that the user selects only one channel at each time slot, we obtain the following equality:

C ∑ i=1 U ∑ j=1 T i,j (n) = C ∑ i=1 T i (n) = Un (5.7)
From eq (5.6) and (5.7), the regret can be bounded as follows:

R APL (n, U, MAUCB) ≤ µ 1 C ∑ i=1 E T i (n) - U ∑ k=1 E P k (n) (5.8) We can break ∑ C i=1 E[T i (n)] into two terms: C ∑ i=1 E[T i (n)] = U ∑ k=1 E[T k (n)] + C ∑ i=U+1 E[T i (n)] (5.9)
Based on eq (5.8) and (5.9), we obtain the following equation:

R APL (n, U, MAUCB) ≤ µ 1 C ∑ i=U+1 E[T i (n)] + U ∑ k=1 E[O k (n)] (5.10)
As mentioned before, the regret in the multi-user case mainly depends on the access to bad channels and the collisions produced among users. Similarly, the upper bound of R APL (n, U, MAUCB) in eq (5.10) deals with the global definition of the regret in which T i (n) represents the access of bad channels, and O k (n) stands for the number of collisions in the k-th best channel. In order to bound the regret, we need to bound the two terms E[T i (n)] and

E[O k (n)].
In eq (4.32) in the previous chapter, we proved that the upper bound of E[T i (n)] in AUCB for a single user is expressed as follows:

E[T i (n)] ≤ 8 ln(n) ∆ 2 i + 1 + π 2 3 (5.11)
Then, for each user in the multi-user case, we obtain:

E[T i,1 (n)] ≤ 8 ln(n) ∆ 2
(1,i)

+ 1 + π 2 3 . . . E[T i,U (n)] ≤ 8 ln(n) ∆ 2 (U,i) + 1 + π 2 3
Therefore, the upper bound of E[T i (n)] for all users becomes:

E[T i (n)] = U ∑ j=1 E[T i,j ] ≤ U ∑ k=1 8 ln(n) ∆ 2 (k,i) + 1 + π 2 3
(5.12)

In order to obtain an upper bound of the total regret, it remains to find an upper bound of

E[O U (n)] = ∑ U k=1 E[O k (n)]
which stands for the expectation of the total number of collisions that may occur in the U best channels. Let

E[O C (n)] = ∑ C
i=1 O i (n) be the expectation of the total number of collisions that may occur in all channels, and E[D k (n)] be the expectation of the total number of collisions encountered by the k th priority user in all channels. To explain our idea and to identify the difference between these latter parameters, Table (5.1) presents a case study with corresponding D k (n) and O k (n). E[O U (n)] can be defined as follows:

E[O U (n)] = U ∑ k=1 E[O k (n)] ≤ C ∑ i=1 E[O i (n)] = U ∑ k=1 E[D k (n)] (5.13)
We should mention that, when the users get a good estimation about the vacant probabilities of channels and each of them accesses his dedicated channel, then non-collision state can occur. On the other hand, the k th user may collide with other users in two cases:

Āk (t) : B i (t) > B k (t) or B k (t) > B m (t)
Then, the total number of times of a bad estimation where the k th priority user does not access his channel up to n, E[T k (n)], can be upper bounded as follows:

E[T k (n)] ≤ E[T B i >B k (n)] + E[T B m <B k (n)]
(5.16)

where T B i >B k (n) stands for the total number of times in which the index of the i th channel exceeds that of the k th best one for all i ∈ {k + 1, ..., C} up to n; T B m <B k (n) stands for the total number of times in which the index of the k th best channel exceeds the m th best one for all m ∈ {1, ..., k -1}. We should mention that, for the first priority user, E[T B m <B k (n)] should equal 0, since his dedicated channel has the highest vacant probability. Based on eq (4.32) in chapter 4, T B i >B k (n) for the k th user can be upper bound by:

E[T B i >B k (n)] ≤ 8 ln(n) ∆ 2 (k,i) + 1 + π 2 3 (5.17)
where ∆ (k,i) = µ kµ i . Since µ i ≤ µ k+1 for all i ∈ {k + 1, ..., C} and µ k ≥

µ k+1 ≥ ... ≥ µ C , then ∆ (k,i) ≥ ∆ (k,k+1
) . Subsequently, the upper bound of E[T B i >B k (n)] can be expressed by:

E[T B i >B k (n)] ≤ 8 ln(n) ∆ 2 (k,k+1) + 1 + π 2 3 (5.18)
Similarly, the second term E[T B m <B k (n)] in eq (5.16) should satisfy:

E[T B m <B k (n)] ≤ 8 ln(n) ∆ 2 (m,k) + 1 + π 2 3 (5.19)
where ∆ (m,k) ≥ ∆ (k-1,k) for all m ∈ {1, ..., k -1}. Then, we obtain:

E[T B m <B k (n)] ≤ 8 ln(n) ∆ 2 (k-1,k) + 1 + π 2 3 (5.20)
Based on eq (5.16), (5.18) and (5.20), E[T (n)] can be expressed as follows:

E[T (n)] ≤ U ∑ k=1 8 ln(n) ∆ 2 (k,k+1) + 1 + π 2 3 + U ∑ k=2 8 ln(n) ∆ 2 (k-1,k) + 1 + π 2 3 (5.21)
The expectation of time S s for U SUs can be upper bounded by:

E[S s ] ≤ U 2U -1 -1 (5.22)
Proof. appendix D Based on eq (5.13), (5.15), (5.21) and (5.22), the total number of collisions in the best channels for U SUs can be upper bounded by:

E[O U (n)] ≤ U 2U -1 -1 . U ∑ k=1 8 ln(n) ∆ 2 (k,k+1) + 1 + π 2 3 + U ∑ k=2 8 ln(n) ∆ 2 (k-1,k) + 1 + π 2 3 (5.23)
Finally, the global regret of U users for MAUCB using APL can be expressed as follows:

R APL (n, U, MAUCB) ≤ µ 1 U ∑ k=1 C ∑ i=U+1 8 ln(n) ∆ 2 (k,i) + 1 + π 2 3 + 1 -p p U ∑ k=2 8 ln(n) ∆ 2 (k-1,k) + 1 + π 2 3 + U ∑ k=1 8 ln(n) ∆ 2 (k,k+1) + 1 + π 2 3 (5.24)
The above upper bound of regret contains three main components: The first one depends on the loss of reward due to the selection of bad channels. The second and third components stand for the loss of reward resulting from collisions among users in the U best channel. Moreover, the three components have a logarithmic asymptotic behavior, which means that, after a finite number of slots each user can converge to his dedicated channel.

Study the Quality of Service Using AUCB

In wireless communication field and more precisely in the context of OSA, taking into consideration two criteria, i.e. vacancy and quality of channels, is necessary when a certain level of QoS is required. Recent works, such as the one proposed in [START_REF] Modi | Qos driven channel selection algorithm for cognitive radio network: Multi-user multi-armed bandit approach[END_REF], have studied the QoS for multiple users using the Random Rank policy [START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF]. Based on the QoS-UCB, the user can learn the vacancy probabilities of channels and recognize their qualities. For its optimality with respect to other existing works, we adopt AUCB to study the QoS of secondary network. Moreover, we use in our simulations APL policy for the priority access in order to help the users to share the available spectrum under a competitive access. Let each channel have the instantaneous quality q i (t) at the slot t, then the expectation of the quality collected from the channel i up to n is given as follows:

G i (T i (n)) = 1 T i (n) T i (n) ∑ τ=1 q i (τ) (5.25)
The global mean reward, that takes into account the quality as well as the availability of all channels, can be defined as follows [START_REF] Modi | Qos driven channel selection algorithm for cognitive radio network: Multi-user multi-armed bandit approach[END_REF]:

µ Q i = G i (T i (n)).µ i (5.26)
The index assigned to the i th channel, B Q i (t, T i (t)), that takes into account the availability, X i (T i (t)), and quality, Q i (t, T i (t)) of the i th channel can be defined by:

B Q i (t, T i (t)) = X i (T i (t)) + A i (t, T i (t)) -Q i (t, T i (t)) (5.27)
where X i (T i (t)), Q i (t, T i (t)) and A i (t, T i (t))) are given by:

X i (T i (t)) = 1 T i (t) t ∑ τ=1 S i (τ)
(5.28)

A i (t, T i (t))) = arctan α ln(t) T i (t) (5.29) Q i (t, T i (t)) = γM i (t, T i (t)) ln(t) T i (t) (5.30)
where S i is the state of the i-th channel; α being the exploration-exploitation factor; γ represents the impact of the quality factor; M i (t, T i (t)) = G max (t) -G i (T i (t)) is the difference between the maximum expected quality over channels at time t, i.e. G max (t), and the quality collected from channel i up to time slot t, i.e. G i (T i (t)). However, when the i th channel has a good quality G i (T i (t)) as well as a good availability X i (T i (t)) at a time t then the quality factor Q i (t, T i (t)) decreases while X i (T i (t)) increases. Subsequently, by selecting the maximum of his index B Q i (t, T i (t)), the user has a large choice to access the i th channel with a high quality and availability.

Priority and Fairness Access

Existing works, as well as our proposed policy APL for the dynamic access consider the case of U users with U priority level. In this section, we propose another policy called Priority and Fairness Access (PFA) to tackle different priority levels (not necessarily U levels) for U users, and each level may contain at least one user as shown in Fig. 5.2. Users in the same level should have the same chance to access similar channels related to their level.

High Priority level

Low Priority Level authorized to accept only one request based on various parameters 3 , such as: the transmission power, the signal to noise ratio (SNR), the distance to primary BS, etc. The role of the priority user is to maximize the transmission rate of the network while the aim of the ordinary users is to selfishly maximize their transmission rate. SU o with a refused request selects a channel based on his observation and transmits directly his own data to the primary BS. If the request of an ordinary user is accepted by his corresponding SU p , this latter selects the best available channel based on his observation to send the ordinary user's data with his own data. SU o should also make a direct transmission to BS to have an information about his SNR (Signal-to-Noise Ratio) in order to make a decision in the next slot 4 . Indeed, if his direct transmission is accomplished successfully at previous slot, then he continues transmitting to BS in the next slot; Otherwise, he sends a request to the priority users. Therefore, the achievable data rate at time t can be expressed as follows:

R o (t) = W 2 log 2 1 + ρ SU p ,BS (t) + W 2 log 2 1 + ρ SU o ,BS (t) (5.31) = W 2 log 2 1 + ρ SU p ,BS (t) 1 + ρ SU o ,BS (t)
(5.32) 3 In our case, we consider the approval of a request is based on the SNR value, then the priority user can accept the request of an ordinary user who has the lowest SNR because it is more difficult for this user to make a direct transmission to the primary BS in the next slot. 4 Assuming that each user can have a notification on his SNR after each transmission time.

where W is the bandwidth of the selected channel at time t. ρ SU p ,BS (t) and ρ SU o ,BS (t) stand for the SNR of the link between SU p -BS and SU o -BS respectively. If ρ SU p ,BS (t) is much higher than ρ SU o ,BS (t), the achievable rates can be simplified as follows:

R o (t) ≈ W 2 log 2 (1 + ρ SU p ,BS (t)) (5.33)
The transmission time of SU p will be divided into several segments: T p 1 , T p 2 , T p 3 and T p 4 ; where, during T p 1 , the user senses a channel and exchanges information with the ordinary users; T p 2 is the time during which data is received from the ordinary user; T p 3 stands for the time spent to relay the data received by SU p to the PU's channels and depends on hardware constraints; finally, T p 4 is the time required to send the data of the ordinary user to the primary BS.

Simulation Results

In this section, we evaluate separately the performance of the two proposed policies APL and PFA. As mentioned before, the existing policies, as well as APL, tackle U priority levels for U users where each level contains only one user while the case of two or more priority levels in which each level contains at least one user, to the best of our knowledge, is not yet considered. One of the benefits of PFA is that it can enhance the transmission rate of users and extend the transmission range of the network as discussed in the previous section.

In our simulations, we evaluate separately the performance of APL and PFA since it is clear that APL achieves better results compared to PFA. Indeed, in the case of APL, when the k-th user regenerates his rank in the set {1, ..., k}, he may collide with all the top priority users, i.e. SU 1 , SU 2 , ..., SU k-1 , before settling down to his dedicated channel, i.e. the k-th best channel. However, in the case of PFA, when the k-th user in the i-th set regenerates his rank, he may collide with all users in the different sets before settling down to his specific set. First, we compare the performance of APL to the recent works such as SLK and Musical Chair. Hereinafter, we introduce PFA and we evaluate its performance that depends on its ability to make the priority users uniformly access the best channels and to enable the ordinary users to access uniformly the almost best channels.

Evaluating the Performance of APL

In this section, we evaluate the performance of the APL and its ability to make each user selects his dedicated channel after a finite number of time slots. We evaluate the performance of APL compared to the existing learning policies such as Musical Chair and SLK. To make this comparison, we use two main performance indexes: the regret related to the access of worst channels and the percentage of times to access best channels by each user. A collision may occur when two or more users try to access the same channel. We adopt in our simulations the ALOHA model, widely used one in OSA, in which none of the collided users receives a reward. After each collision, and based on our policy APL, the collided users should regenerate their rank. First, we consider a static setting of users, then we investigate the dynamic access in which the priority users can enter or leave the network. Let us consider 4 priority users trying to access 9 communication channels with the following vacant probabilities: Γ = [ 0.9 0.8 0.7 0.6 0.5 0.45 0.3 0.25 0.1] Each user can access one of the available channels according to his prior rank. For instance, the first priority user, SU 1 , should regularly access the best channel, µ 1 = 0.9, while the targets of the users SU 2 , SU 3 and SU 4 are to access respectively the channels 0.8, 0.7, 0.6. Fig. 5.5 shows the regret of our proposed APL with the well-known MAB algorithms: AUCB, TS, UCB1 and e-greedy. As we can see, the regrets of the four MAB algorithms with APL have a logarithmic asymptotic behavior that means the 4 users are able to estimate the vector Γ, and then access their dedicated channels. According to several recent works, TS seems to outperform the current state-of-the-art MAB algorithms by achieving a lower regret for a single user but not necessarily for multiple users. Indeed, despite its good performance compared to UCB1 and e-greedy shown in Fig. 5.5, TS cannot give better results compared to AUCB. Similarly, in the previous chapter, AUCB achieved better results under Random Rank compared to TS. The same figure shows that the regret under e-greedy, varies as an increasing function over time at the beginning with a high derivative, provides worst results. Indeed, the random access by each user, based on e-greedy, during the learning period may lead to a large number of collisions among users. Then, the regret that depends on the access of worse channels and the number of collisions among users may increase significantly. In Fig. 5.6, we compare the regret of APL to SLK and Musical Chair. APL and SLK take into consideration the priority access while Musical Chair is proposed for the random access. Despite the regret of APL and SLK has a logarithmic asymptotic behavior, the regret of Musical Chair has two parts:

• A linear part at the beginning, during the learning period, due to the large number of collisions resulting from the random selection.

• A constant part in which the users exploit the U best channels .

As we can see from Fig. 5.6, APL using AUCB and TS outperforms Musical Chair and SLK by achieving the lower regret. Fig. 5.7 shows the percentage of times that the k-th user accesses his dedicated channel based on our policy APL up to n, P k (n). This latter is given by:

P k (n) = 100 × n ∑ t=1 1 (a t,k =µ k ) t
where a t,k represents the channel selected by the k-th user at instant t; and 1 (a=b) = 1 if a =b 0 otherwise In Fig. 5 • The first part from 1 to the number of channels C represents the initialization phase, where each user selects each channel once in order to collect some information about the vacancy of channels.

• The second part from slot C+1 to 2000 represents the adaptation phase.

• In the last part, the users converge asymptotically to their dedicated channels.

As we can see, based on our policy APL, the users are able to converge to their targeted channels: The first priority user SU 1 converges to the best channel µ 1 , followed by SU 2 , SU 3 and SU 4 to the channels µ 2 , µ 3 and µ 4 respectively. In addition, we can observe a fast converges of APL using AUCB compared to TS.

In [START_REF] Modi | Qos driven channel selection algorithm for cognitive radio network: Multi-user multi-armed bandit approach[END_REF], the authors proposed a novel version UCB1 that considers not only the availability but also the quality of channels. Based on QoS-UCB1, the user is able to estimate the vacant probability as well as the quality of channels. In this section, we study the QoS-AUCB that gives better results In [START_REF] Modi | Qos driven channel selection algorithm for cognitive radio network: Multi-user multi-armed bandit approach[END_REF], the authors show that QoS-UCB achieves good results compared to several existing algorithms, such as Regenerative Cycle Algorithm (RCA) [START_REF] Tekin | Online learning in opportunistic spectrum access: A restless bandit approach[END_REF], restless UCB (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]. From Fig. 5.9, one can observe that QoS-AUCB achieves better results compared to QoS-UCB.

Evaluate the Performance of PFA

According to PFA, two or more sets of users can be considered such that users from the same set have the same choice to select and access the channels. Assuming that two sets (or levels) of users are considered: Priority and ordinary, where the priority set contains one user (P = 1), while the ordinary contains two users (O = 2). The three users try to learn selfishly the vacant probabilities of 9 channels: Γ = [0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1]

If the users have a prior knowledge about the vacant probabilities of channels Γ, then the target of the priority user SU p remains to access the most vacant channel, i.e. µ 1 = 0.9, while the two ordinary users SU o1 and SU o2 access uniformly the two almost-best channels, i.e. µ 2 = 0.8 and µ 3 = 0.7. The performance of PFA depends on its ability to ensure the priority and the fairness: Could PFA provide the priority between two different sets? Or could PFA ensure the fairness among users in the same set? In Fig. 5.10, we display T k (n) that represents the accessing of all channels by each user up to the total number of slots n. We can clearly notice that the priority user often accesses the best channel while the ordinary users uniformly access the two almost-best channels. Fig. 5.11 compares the regret of PFA using TS, UCB1 and e-greedy and SLK for the three users. SLK considers U priority levels for U users where the k-th user tries to select and access the k-th best channel. Although the two policies (i.e. SLK and PFA) have a logarithmic asymptotic behavior, PFA achieves a lower regret. Moreover, obtaining a lower regret can provide more opportunity for users in the licensed network which increases the transmission rate.

As mentioned before, PFA can be used to extend the transmission range of the network, more precisely for the ordinary users, based on the transmission technique proposed in Section (5.5.2). Let us define the throughput of the o-th ordinary users H o (t) that also represents the percentage of successful transmission. Generally, the throughput depends on several factors: the

H o (n) = n ∑ t=1 1 t H L o (t) (5.35)
In Fig. 5.12, the throughput capacity of the priority users SU p exceeds that of the two ordinary users SU o1 and SU o2 . After a finite number of time slots, and based on our policy PFA, the priority user converges towards the most vacant channel, i.e. µ 1 = 0.9. and his percentage of successful transmission will be around 90%. Although the throughput achievable by the priority user should be around 90%, SU p achieves only %80 as shown in Fig. 5.12. This throughput decrease is referred to the collisions produced among users. Fig. 5.12 also shows the throughput capacity of the ordinary users with and without the proposed transmission technique. Beside the two ordinary achieve the same throughput, there is an enhancement of 30% when the proposed transmission technique is considered. Indeed, when the ordinary users transmit directly to the primary Base Station, their reached throughput is around 40% of the throughput while 70% of the throughput can be achieved by the ordinary users using the proposed transmission technique. Finally, the improvement of the SNR using the proposed transmission technique can enhance the throughput capacity of the ordinary users.

Conclusion

This chapter focuses on the multiple Secondary Users (SUs) scenario in the Opportunistic Spectrum Access (OSA). In order to help the SUs make a decision, Multi-Armed Bandit (MAB) has recently attracted the attention and seems to be a suitable solution to solve the OSA problem. The well-known MAB algorithms such Thompson Sampling (TS), Upper Confidence Bound (UCB) or e-greedy applied in OSA, tackle the case of a single user, while several SUs may exist in the network trying to learn separately the vacant probabilities of channels. For multiple users, accessing the spectrum can be cooperative or competitive. In this chapter, we focused on the competitive access in which a novel learning policy, called All-Powerful Learning (APL), for the priority access is proposed. Our proposed APL does not require any cooperation or prior knowledge about the existing channels as do several existing policies, such as: Selective learning of the K-th largest expected rewards (SLK), Musical Chair, Multi-user e-greedy collision Avoiding (MEGA) and k-th MAB. It should be noticed that, the priority access has not been studied sufficiently in the literature although SLK and k-th MAB are two of the rare algorithms for the priority access based on UCB1 and e-greedy. While APL is not based on any specific MAB algorithm and can be used with any MAB algorithm, such as: AUCB, TS, UCB1, e-greedy. APL also considers the priority dynamic access while, to the best of our knowledge, only the priority or the dynamic access are considered in several recent works. It has been shown that when a priority user leaves the network, a little increase of regret can be observed.

Unlike APL that takes into consideration U priority levels for U users, we proposed a novel policy, called Priority Fairness Access (PFA), to consider two or more hierarchical levels for U users. PFA represents a novel issue, not yet considered in the literature, to tackle the priority and the fairness access. In our simulations, we considered two sets of secondary users: Priority users set with one member and ordinary users set with two members. It has been shown that the priority user often accesses the most vacant channel while the ordinary users access uniformly the almost-best channels. 114 Chapter 6. Overview, General Conclusions and Future Work

Conclusion

Cognitive Radio (CR) can reduce the impending spectrum scarcity problem and increase its efficiency by allowing Opportunistic Spectrum Access (OSA) to the licensed spectrum bands. Indeed, in OSA, Secondary users (SUs) search for holes (white space) by sensing the spectrum. The presence of such holes in the primary users licensed channels are exploited by the SUs in order to transmit their data. In this thesis, we investigate several fundamental decision-making techniques used in CR, and more precisely in the Opportunistic Spectrum Access in order to help the SUs make good decisions. In Chapter 1, we discussed, on the one hand, the technological advancement in wireless networks and mobile telephony that makes the frequency bands more and more crowded. On the other hand, the recent studies about the usage of the spectrum showed that up to 60% of the frequency bands is not used in several regions in the United States (US). We also investigate the rise of CR, the Cognitive Cycle (CC) and the Software-Defined Radio (SDR) that represents the core of CR. In Chapter 2, we formulate the access to channels as Multi-Armed Bandit problem in order to help a SU make a good decision. This chapter also investigates the state-of-the-art of MAB algorithms that are widely used in OSA namely: Thompson Sampling (TS), Upper confidence Bound (UCB), egreedy, etc. Our contributions detailed in Chapters 2, 3, 4 and 5 are summarized as follows:

• New MAB algorithm, called e-UCB, based on the classical UCB in order to learn the vacant probabilities of the available communication channels. e-UCB can achieve better results compared to several MAB algorithms by quickly finding the best channel with the highest vacant probability. In e-UCB, the exploration-exploitation phases are separated. Indeed, during the learning period, e-UCB gives a particular importance to the exploration in order to gather enough information about the vacant probabilities of channels. Then, e-UCB focuses on the exploitation by regularly accessing the best channel. We have also proven that the upper bound of the sum regret achieves a logarithmic asymptotic behavior. It has shown that e-UCB represents a suitable solution for a static environment where the vacant probabilities of the channels do not evolve over time while for dynamic environment, the performance of e-UCB decreases significantly as most of MAB algorithms.

• To solve the main drawback of e-UCB in a dynamic environment, we propose AUCB that can achieve better results compared to e-UCB as well to several existing versions of UCB. Unlike e-UCB, the main advantage of AUCB that balances between exploration and exploitation during the learning period. After this period, the user gives the most important effect to the exploitation with a little impact on the exploration. Thanks to this latter property, AUCB can detect the dynamism of the vacant probabilities of the channels and thus easily adapt to a given environment.

• A novel cooperative policy, called Side Channel policy, is proposed in order to help users to learn collectively the vacant probabilities of the available channels. This policy requires some cooperation level among users to learn in an unknown environment. It has been shown that, after a finite number of slots, each user converges towards his dedicated channel that corresponds to his prior rank. Moreover, a significant improvement is achieved with Side Channel policy compared to several existing policies. Indeed, based on our policy, the users can reach their targeted channels faster than other policies that manage a secondary network such as Random Rank and SLK. Our proposed policy can also be used for dynamic priority access where the priority users can enter or leave the network.

• For the competitive access, we proposed a novel policy called All-Powerful Learning (APL) for the priority access. This former does not require any cooperation or prior knowledge about the vacant probabilities of channels. APL can achieve better results compared to several existing policies for the competitive access such as Musical Chair and SLK. We also investigated the upper bound of regret for APL and showed that it achieves a logarithmic asymptotic behavior. That means that, after a finite number of time slots the users are able to learn the vacant probabilities of channels and often access their targeted channels. Finally, it has been shown that APL represents a good solution for competitive priority dynamic access.

• We proposed another competitive policy, called Priority Fairness Access (PFA), that considers different priority levels where each level contains one or more users. PFA achieves the fairness for the users who have the same priority level by letting them uniformly access the available channels. The main advantage of the PFA is that it can be used to extend their transmission range as well to enhance the users' transmission rate.

• We investigated the quality of service in the secondary network where the users are able to learn not only the vacant probabilities of channels but also their quality. Thereby, the main target of a user is to find the best channel with the best quality and highest availability.

• Finally, a proof of concept has been developed for e-UCB, AUCB, Side Channel and APL in order to ensure the convergence of our proposed methods in a real radio environment. Via the analytical convergence analysis as well as the experimental results, it has been shown that the regret achieves a logarithmic asymptotic behavior.

Perspective and Future Work

Opportunistic Spectrum Access in Cognitive Radio is still an attractive research to reach a high efficiency in the current networks. Our proposed MAB, for a single user or multiple-user cases, can be considered to be an effective solution for enhance system reliability. These methods that we developed in this thesis have the ability to be improved further:

• Generally, like most important works based on the Multi-Armed Bandit technique, this work focused on the Independent Identical Distributed (IID) model in which the state of each channel is supposed to be drawn from IID process. While Markov process represents another important technique that may represent a more realistic model to describe the state of the available channels, although it is a complex process compared to IID.

• In the Side Channel policy, each user broadcasts his choice of channels to other users in order to avoid any collision in the next slot. However, the broadcast packet of the user risks to be lost, then a collision may occur among users. Therefore, for a more realistic model, considering By focusing first on a single SU, we analyze the performance of the well-known MAB algorithms (i.e. TS, UCB, e-greedy) that deal with OSA. Thus, we propose our MAB algorithms based on UCB, called: e-UCB and AUCB. Both of them achieve good results compared to well-known variants of MAB algorithms, i.e. UCB and e-greedy, in which the SU can quickly learn the vacancy probability of channels without any information or prior knowledge about the available channels. Our analytical proof, as well as the simulation results, of e-UCB and AUCB show that the SU can efficiently distinguish and converge to the best channel after a finite number of time slots.

For multiple users, the big challenge of SUs remains to learn collectively (Cooperative learning) or separately (Competitive learning) the vacancy probabilities of the channels. As a matter of fact, a cooperative or competitive learning policy is required in order to manage the secondary network and decrease the number of collisions among users. Generally, the policies to manage a secondary network can be classified into two main categories: Random access or priority access. Most recent works in OSA focus on the random access while the priority access is not enough considered in the literature. In fact, the priority access can have an important role in tactical networks in which several SUs exist with some hierarchy levels.

In our work, we propose a cooperative and competitive policies for the priority access respectively called Side Channel and All-Powerful Learning (APL). In our policies, each SU has an assigned priority rank, and his target remains to access the channels according to his rank. Moreover, Side Channel and APL deal with the priority dynamic access where the users can enter into or leave the network. While, to the best of our knowledge, only the priority or dynamic access are considered in several recent works. Finally, a proof is developed to verify the performance of proposed learning policies on a real radio environment. Simulation results show that Side channel and APL can achieve better results than several recent works: the users can quickly reach their dedicated channels while decreasing the number of collisions among them.

xiA

  Upper Bound of A in e-UCB B Upper Bound of Z in e-UCB C Upper Bound of T i (n) in AUCB D Upper Bound of S s in MAUCB xv List of Tables

xviiof Figures 1 . 1 3 . 8 1 2 1. 1 . 1 2 1. 1 . 2 4 1. 2 7 1. 2 . 1 7 1. 2 . 2 9 1. 2 . 3 11 1. 3

 1138121121242721722923113 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 D.1 Three SUs trying to converge toward a steady state where each one finds its prior rank. The roman number indicates the number of users selecting the same rank . . . . . . . . . . . . . . . 128 List Use of ISM band frequencies in industrial wireless networks. . 1.2 Software Defined Radio concept that contains: Analogue to digital converter (ADC or A/D), Digital to analogue converter (DAC or D/A) and Hardware system (i.e. Intermediate Frequency/Radio Frequency: IF/RF) [9]. . . . . . . . . . . . . . . 1.3 Spectrum access according to the three possible models: Interweave, Underlay or Overlay. . . . . . . . . . . . . . . . . . . . 1.4 Cognitive cycle decision-making as introduced by Mitola [25] 2.1 Classification of the DSA where three models are suggested: Exclusive Use Model, Open Sharing Model, and Hierarchical Access Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Cognitive radio decision making as introduced in [28]. . . . . 2.3 Machine learning algorithms. . . . . . . . . . . . . . . . . . . . 2.4 Reinforcement Learning Framework . . . . . . . . . . . . . . . 2.5 Taxonomy of Reinforcement Learning . . . . . . . . . . . . . . 2.6 Several Arms with different expected reward. After a finite period of time the agent has a perception about the reward obtained from each arm. . . . . . . . . . . . . . . . . . . . . . . 2.7 Classification of MAB problem. . . . . . . . . . . . . . . . . . . 2.8 Channel occupancy model . . . . . . . . . . . . . . . . . . . . . 3.1 Spectrum Sensing Techniques . . . . . . . . . . . . . . . . . . . 3.2 Vacancy of licensed channels . . . . . . . . . . . . . . . . . . . 3.3 Regret comparison of Thompson Sampling, UCB1 and e-greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Pbest comparaison of Thompson Sampling, UCB and e-greedy3.5 Throughput capacity of Thompson Sampling, UCB and e-greedy 3.6 P best of the proposed policy under TS, UCB and e-greedy for three priority users. . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Logarithmic Regret of our policy under the three learning algorithms, for three secondary users. . . . . . . . . . . . . . . . xviii Global regret for the three plocies (Our proposed one, Random Rank, SLK) applied on UCB with 3 SUs. . . . . . . . . . . . . . 4.1 The regret of the 4 MAB algorithms . . . . . . . . . . . . . . . . 4.2 The selection percentage of the best channel using the 4 MAB algorithms TS, AUCB, e-UCB and UCB . . . . . . . . . . . . . . 4.3 The regret of the 4 MAB algorithms TS, AUCB, e-UCB and UCB 4.4 Access the best channels by 3 SUs using the 4 MAB algorithms AUCB, TS, e-UCB and UCB . . . . . . . . . . . . . . . . . . . . 4.5 The regret of the 4 MAB algorithms TS, AUCB, e-UCB and UCB 5.1 Priority access after a user left his dedicated channel . . . . . . 5.2 Different priority levels in the secondary network . . . . . . . 5.3 Novel transmission technique to enhance the transmission rate of the secondary network . . . . . . . . . . . . . . . . . . . . . 5.4 Cooperative transmission with one priority user . . . . . . . . 5.5 Regret of APL compared to SLK and Musical Chair policies . 5.6 Regret of APL compared to SLK and Musical Chair policies . 5.7 Pbest of APL using TS and AUCB . . . . . . . . . . . . . . . . . 5.8 Access channels by the priority users using QoS-AUCB and QoS-UCB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.9 Regret of QoS-AUCB and QoS-UCB . . . . . . . . . . . . . . . 5.10 Number of times that the users access the channels . . . . . . 5.11 The regret of our policy PFA under TS, UCB1 and e-greedy compared to SLK . . . . . . . . . . . . . . . . . . . . . . . . . . 5.12 Throughput capacity of the primary and ordinary users . . . . Thirty years of wireless communications technology . . . . WLAN and unlicensed standards . . . . . . . . . . . Evolution of the mobile generations . . . . . . . . . . The explosive growth of wireless communications: Towards Cognitive Radio . . . . . . . . . . . . . . . . . . . . . Software Defined Radio: The core of Cognitive Radio The rise of Cognitive radio . . . . . . . . . . . . . . . The Cognitive Cycle . . . . . . . . . . . . . . . . . . . Our Motivations . . . . . . . . . . . . . . . . . . . . . . . . . 13

FIGURE 1 . 2 :

 12 FIGURE 1.2: Software Defined Radio concept that contains: Analogue to digital converter (ADC or A/D), Digital to analogue converter (DAC or D/A) and Hardware system (i.e. Intermediate Frequency/Radio Frequency: IF/RF) [9].

1. 2 .

 2 The explosive growth of wireless communications: Towards Cognitive Radio 11

FIGURE 1 . 3 :

 13 FIGURE 1.3: Spectrum access according to the three possible models: Interweave, Underlay or Overlay.

Chapter 1 .FIGURE 1 . 4 :

 114 FIGURE 1.4: Cognitive cycle decision-making as introduced by Mitola [25]

Chapter 2 .FIGURE 2 . 4 :

 224 FIGURE 2.4: Reinforcement Learning Framework

4 FIGURE 2 . 6 :

 426 FIGURE 2.6: Several Arms with different expected reward. After a finite period of time the agent has a perception about the reward obtained from each arm.

Fig. 2 .FIGURE 2 . 7 :

 227 Fig.2.7 presents all MAB variants in which several assumptions can be considered: Single or multiple agents, model of rewards, number of arms, with or without prior knowledge, etc.

FIGURE 3 . 1 :

 31 FIGURE 3.1: Spectrum Sensing Techniques

FIGURE 3 . 2 :

 32 FIGURE 3.2: Vacancy of licensed channels

FIGURE 3 . 4 :

 34 FIGURE 3.4: Pbest comparaison of Thompson Sampling, UCB and e-greedy

FIGURE 3 . 5 :

 35 FIGURE 3.5: Throughput capacity of Thompson Sampling, UCB and e-greedy

FIGURE 3 . 6 :

 36 FIGURE 3.6: P best of the proposed policy under TS, UCB and e-greedy for three priority users.

FIGURE 3 . 7 :

 37 FIGURE 3.7: Logarithmic Regret of our policy under the three learning algorithms, for three secondary users.

FIGURE 3 . 8 :

 38 FIGURE 3.8: Global regret for the three plocies (Our proposed one, Random Rank, SLK) applied on UCB with 3 SUs.

Chapter 4 .

 4 Distributed Learning for the Priority Cognitive Access as follows:

32 )

 32 Proof. appendix C Chapter 4. Distributed Learning for the Priority Cognitive Access Finally, we obtain an upper bound of the regret of AUCB, R(n, AUCB): R(n, AUCB) ≤ 8

FIGURE 4 . 1 :Fig. 4

 414 FIGURE 4.1: The regret of the 4 MAB algorithms

FIGURE 4 . 2 :

 42 FIGURE 4.2: The selection percentage of the best channel using the 4 MAB algorithms TS, AUCB, e-UCB and UCB

Chapter 4 .

 4 Distributed Learning for the Priority Cognitive Access

FIGURE 4 . 3 :

 43 FIGURE 4.3: The regret of the 4 MAB algorithms TS, AUCB, e-UCB and UCB

FIGURE 4 . 4 :

 44 FIGURE 4.4: Access the best channels by 3 SUs using the 4 MAB algorithms AUCB, TS, e-UCB and UCB

  -Rank TS with Rand-Rank e-UCB with Rand-Rank UCB with Rand-Rank

FIGURE 4 . 5 :

 45 FIGURE 4.5: The regret of the 4 MAB algorithms TS, AUCB, e-UCB and UCB

FIGURE 5 . 1 :

 51 FIGURE 5.1: Priority access after a user left his dedicated channel

FIGURE 5 . 5 :

 55 FIGURE 5.5: Regret of APL compared to SLK and Musical Chair policies

Fig. 5 .FIGURE 5 . 8 :Chapter 5 FIGURE 5 . 9 :

 558559 Fig. 5.9 depicts the regret of QoS-AUCB and QoS-UCB for the 4 priority

FIGURE 5 . 10 :

 510 FIGURE 5.10: Number of times that the users access the channels

FIGURE 5 . 11 :

 511 FIGURE 5.11: The regret of our policy PFA under TS, UCB1 and e-greedy compared to SLK

FIGURE 5 . 12 :

 512 FIGURE 5.12: Throughput capacity of the primary and ordinary users

  Since 1990's, the demand on wireless devices, mobile and wireless networks, has experienced unprecedented growth which makes the frequency bands more and more crowded. Several studies, initiated by the Federal Communications Commission (FCC) in the United States (US), have shown that the frequency bands are not well used: Some frequency bands are overlapped while others underutilized. The Opportunistic Spectrum Access (OSA) in Cognitive Radio (CR) represents one of several proposed solutions to tackle the scarcity and enhance the efficiency use of the spectrum. In OSA, two categories of users are considered: Primary Users (PUs), also known as licensed users, have the right to fully access their dedicated bandwidths; and Secondary Users (SUs), i.e. opportunistic users, would like to exploit vacant frequency bands unused by the PUs. Due to hardware limitation, a SU can access one channel at each time slot trying to reach the best channel with the highest vacancy probability. To identify the best channel, we formulate OSA as a Multi-Armed Bandit (MAB) problem, in which an agent plays one arm at each time trying to reach the optimal arm with the highest expected reward. Several MAB algorithms have been suggested to solve the MAB problem in the context of OSA, such as: Thompson Sampling (TS), Upper Confidence Bound (UCB), e-greedy, etc.

1 Thirty years of wireless communications tech- nology

	Demand of wireless devices, mobile and wireless networks, has experienced
	unprecedented advancement since 1990's. However, wireless networks started
	with small personal area networks (e.g. WiFi, Bluetooth, etc.) and evolved
	into metropolitan networks (e.g. GSM: Global System for Mobile communi-
	cation). From wireless local area networks (WLANs) to mobile phones, peo-
	ple need to be connected to the network anytime no matter where they are.
	Indeed, WLANs entered in everyday life through standards. Moreover, sev-
	eral generations of wireless networks have been deployed, mainly dedicated

1.3.1 Our Research Objectives . . . . . . . . . . . . . . . . 13 1.3.2 Outlines . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Chapter 1. Advanced Technologies in Wireless Internet and Communications Networks 1.to cellular telephone technology (e.g. GSM) then more oriented towards multimedia (e.g. UMTS: Universal Mobile Telecommunications System).

  Used by SCADA and RFID applications with lower data rate requirements

	900 MHZ
		 Most widely used frequency= can become overcrowded.
	2.4 GHZ	 Used for Wi-Fi, Bluetooth, microwave ovens, baby monitors, pronters, keyboards and gaming controllers.
		 Voice, video and data communications typically use 2.4
		GHZ systems with higher data rates.

1.1. Thirty years of wireless communications technology 3  Very narrow= Limited maximum data rates.  Able to penetrate obstruction in the Line-of-Sight, i.e. trees and leaves.   Shortest range.  Used in commercial Wi-Fi applications.  Supports 802.11n standard and 802.11ac standard, which provides up to 1.3 Gbps of wireless data throughput.

  s and fully implemented throughout the 1980's, purely designed for voice calls without considering data services. AMPS had several problems such as poor voice quality, lack of security, and sometimes suffered from calls dropped. Unlike the first generation, Global System for Mobile Communications (GSM) is a digital standard developed by the CNET (Centre National d'Etudes des Télécommunications) in France, also known as the second generation cellular technology, it is used by mobile phones and tablets for full duplex voice telephony. In order to add a packet transmission capability to GSM, General Packet Radio Service (GPRS) was developed and has been available for users over GSM. GPRS is more suitable method for transmitting data over a cellular network. Indeed, in the case of GPRS, the resources are not contin-

	particu-
	lar, UMTS made it possible to transfer multimedia message such as images,
	sound and videos in real time. In France, SFR Company (a French telecom-
	munication operator) was the first to launch its UMTS commercial offer on
	November 10th 2004, followed by Orange on December 9th 2004. Never-

The first mobile generation (1G) , also known as AMPS (Analog Mobile Phone Service), is an analog technology of cellular network, and was introduced in 1970'uously allocated for transmission but only when data is exchanged, unlike for Circuit Switched Voice Services in GSM where a virtual circuit is established and associated resources are reserved for the duration of the communication. GPRS is a data service that can be used for Multimedia Messaging Service (MMS), short message service (SMS), Wireless Access Point (WAP), Internet browsing, etc. GPRS is often called 2.5G or 2G+ where 2.5 indicates that it is a technology between GSM (second generation) and Universal Mobile Telecommunications System (UMTS: third generation). This latter is a cellular technology based on the Wideband Code Division Multiple Access (WCDMA) technique while the multiple access for GSM is done by a combination between Time Division Multiple Access (TDMA) and Frequency Division Multiple Access (FDMA). A major improvement of UMTS over GSM is, thanks to its new coding technique, the possibility to reuse same frequencies in adjacent radio cells and consequently to assign a larger spectral width for each cell (5 MHz). Whereas in GSM, adjacent radio cells must use different frequency bands (reuse factor varying from 1/3 to 1/7) which implies (in GSM) dividing and distributing the frequencies allocated to the operator between several radio cells. Thanks to the increased speed of data transmission, UMTS opened the door to new applications and services. In theless, Bouygues Telecom has opened its UMTS license commercially at the beginning of 2007. The 4th generation or Long Term Evolution (LTE) mobile network was quickly installed in France to replace previous generations: 3G, Chapter 1. Advanced Technologies in Wireless Internet and Communications Networks

TABLE 1 .

 1

1: Efficiency of each cellular wireless generation, 1G

Chapter 2 Learning and Decision-Making for Opportunistic Spectrum Access Contents 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Dynamic Spectrum Access and Opportunistic Spectrum Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Decision-Making Process and Machine Learning . . . . . . 2.4 Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . 2.5 Multi-Armed Bandit problem . . . . . . . . . . . . . . . . . 2.6 Model of MAB reward . . . . . . . . . . . . . . . . . . . . . .

	2.6.1 IID Bandit Problem Formulation . . . . . . . . . . . .
	2.6.2 Markov Bandit Problem Formulation . . . . . . . . .

2.7 MAB algorithms . . . . . . . . . . . . . . . . . . . . . . . . .

	2.7.1 MAB algorithms for a single agent . . . . . . . . . . .
	2.7.2 MAB algorithms to manage multiple agents . . . . .

2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Chapter 2. Learning and Decision-Making for Opportunistic Spectrum
	Access

  :

	20	Chapter 2. Learning and Decision-Making for Opportunistic Spectrum Access
		• In Exclusive Use Model, the frequency bands are allocated to the exclu-
		sive use where a cognitive user can access them under some constraints.
		Open Sharing Model Hierarchical Access Model Exclusive Use Model Indeed, in the Spectrum Property Rights, the licensed user (i.e. PU) is Dynamic Spectrum Access Spectrum Property Rights Dynamic Spectrum Allocation Overlay Interweave Underlay authorized to sell or trade a part of his frequency bands. This model encourages the opening of a secondary market. The dynamic spectrum allocation, introduced by the European DRiVE project, aims to improve the spectrum efficiency by exploiting the spatial and temporal traffic statistics of different services. • Open Sharing Model is referred to open new portions of the frequency bands for unlicensed users with the same rights to access the spectrum. • In Hierarchical Access Model, a secondary network is introduced in which a SU may access the spectrum as far as he does not cause any harmful interference to the PU. As mentioned before [Chapter 1, section 2], there are three Hierarchical Access Models: Interweave, Underlay FIGURE 2.1: Classification of the DSA where three models are suggested: Exclusive Use Model, Open Sharing Model, and Hierarchical Access Model. and Overlay access.

TABLE 2 .

 2

1: Comparison between the well-known MAB algorithms. '|' indicates a high performance, '|||' indicates that the performance is weak and 'N/A' indicates that the information is not available.

  , proposed Time-Division Fair Share (TDFS) policy and showed that the proposed algorithm

	MAB for	Learning	Experiment	Asymptotic	Upper
	multiple	ALgorithm	Performance Convergence Bound
	agents
	Centralized	Multiple Play [39]	N/A	Yes	N/A
		Auction problem [67]	|	N/A	N/A
	Semi-	Cooperative [68]	||	N/A	N/A
	distributed Bipartie matching [69]	|||	N/A	log 2 (n)
		Leader-follower[70]	|||	Yes	N/A
	Distributed	Random Rank [35]	||	Yes	log(n)
		TDFS [59]	||	Yes	log(n)
		SLK [61]	|||	Yes	log(n)
		Musical Chair [60]	|	Yes	log(n)
		MEGA [63]	|	Yes	log(n)

TABLE 2 .

 2

2: Compares the performance of the well-known MAB algorithms for multiple agents. '|' indicates a high performance, '|||' indicates that the performance is weak and 'N/A' indicates that the information is not available or no value available.

  W i (t, T i (t)), Z i (t, T i (t)), S i (t): the state of the selected channel, equals one if the channel is free and 0 otherwise, T i (t): the number of times the i-th channel is sensed by the user up to time t, W i (t, T i (t)): the success access up to time t depends on T i (t), Z i (t, T i (t)): the failure access up to time t depends on T i (t), Output: B i (t, T i (t)), B i (t, T i (t)): the index assigned for channels, foreach t = 1 to n do a t = arg max i B i (t, T i (t)), The user observes the state S i (t), W i (t, T i (t)) = ∑ n t=0 S i (t)1 a t =i , % 1 a t =i : equals 1 if the user selects the i-th channel and 0 otherwise,

	Algorithm 1: Thompson Sampling Algorithm
	Input: C, n,
	C: number of channels,
	n: total number of slots,
	Parameters: T i (t),
	1)

  , T i (t)), T i (t): the number of time slots the channel is sensed up to time t, X i (T i (t)): the exploitation contribution of channels depends on T i (t), A

i (t, T i (t)): the exploration contribution of channels depends on T i (t) and t, Output:

B i (t, T i (t)), B i (t, T i (t)): the index assigned for channels, foreach t ∈ [1, C] do

The user senses each channel once, The user updates his index B i (t, T i (t)), while t ≤ n do a t = max i B i (t -1, T(t -1)),

  SU updates B i (t, T i (t)), X i (T i (t)), A i (t, T i (t)) according to eq.

	Algorithm 5: e-UCB for a single user
	Input: H, C, n,
	H: the exploration factor,
	C: the number of channels,
	n: the total number of slots,
	Parameters: T i (t), A i (t, T i (t)),
	T i (t): the number of time slots the channel is sensed up to time t,
	A i (t, T i (t)): the exploration contribution of channels that depends on
	T i (t) and t,
	Output: B i (t, T i (t)), X i (T i (t)):
	B i (t, T i (t)): the index assigned for channels,
	X i (T i (t)): the exploitation contribution of channels that depends on
	T i (t),
	Initialization
	for t = 1 to C do
	SU senses each channel once,
	SU updates B

) is the mean of reward (considered as an estimator i (t, T i (t)), X i (T i (t)), A i (t, T i (t)) according to eq. (4.1), (4.2), (4.3), for t = C+1 to n do if χ < t , then a t = arg max i B i t -1, T i (t -1) , else a t = arg max i X i T i (t -1) , T i (t) + +, (4.1), (4.2),

(4.3)

37 )

 37 Chapter 4. Distributed Learning for the Priority Cognitive Access For a single user, using AUCB or e-UCB, we previously found an upper bound of E[T i (n)] in eq (4.15) and (4.33). First, let us find an upper bound of AUCB under Side Channel policy. Based on eq. (4.33), E[T i (n)] for U users becomes:

  (t): indicates a collision for the k th user at time t, Parameters: T i (t), A i (t, T i (t)), T i (t): number of time slots the channel is sensed up to time t, A i (t, T i (t)): the exploration contribution of channels that depends on T i (t) and t, Output:

	Algorithm 6: Random Rank policy
	Input: C, U, n, ξ k (t),
	C: number of channels,
	U: number of users,
	n: total number of slots,
	ξ k

Algorithm 7 :

 7 All-Powerful Learning algorithm Input: k, ξ k (t), r i (t), k: indicates the kth user or kth best channel, ξ k (t): indicates a presence of collision for the kth user at instant t, r i (t): indicates the state of the ith channel at instant t, r i (t) = 1 if the channel is free and 0 otherwise, Initialization k = 1, for t = 1 to C do SU k senses each channel once, SU k updates his index B i (t), SU k generates a rank of the set {1, ..., k}, k + 1, for t = K+1 to n do SU k senses a channel in his index B i (t) according to his rank, if r i (t)=1 then SU k transmits his data, if ξ k (t)=1 then SU k regenerates his rank of the set {1, ..., k}, else SU k keeps his previous rank, else SU k refrains from transmitting at instant t, SU k updates his index B i (t)

1 PFA for Two Sets of Priority Levels To

  simplify our discussion, we consider at first two sets of secondary users: priority (SU p ) and ordinary (SU o ) users. Our policy PFA ensures the fairness among users belonging to the same set. For instance, SU p have an equal right to access the best channels while SU o will try to fairly share the almost best ones. All users try to learn selfishly the vacancy probabilities of channels. Hereinafter, we propose a cooperative transmission technique in order to extend the transmission range of SU o and enhance the throughput by requesting the SU p to act as relays. PFA takes into consideration the competitive learning (to decrease the complexity of the system) with a cooperative transmission, while, our previous policy Side Channel proposed in Chapter 3 is considered as a cooperative learning that requires a certain cooperation level among users with a competitive transmission. Based on PFA, let P and O = (U -P) be respectively the number of priority and ordinary users in the secondary network and suppose that the vacant probabilities of channels are ordered as: µ 1 > µ 2 > ... > µ C where µ 1 represents the channel with the highest vacant probability and Γ = {µ i }. First, the vector Γ is unknown and the users should estimate it after a finite time observation. Let Γ P = {µ 1 , µ 2 , ..., µ P } represents the P best channels reserved for the priority users and Γ O = {µ P+1 , µ P+2 , ..., µ U } depicts the almost best channels for the ordinary users, then the priority users should examinate only the states of the P best channels at each time slot in order to gather some information about their vacant probabilities. Although, for specific constraints related to hardware, a priority user is not able to sense wide frequency band at each time slot. To solve the latter issue and make each priority user scan the P channels, let each user generate a rank in the set {1, ..., P} in order to scan the P best channels and obtain information about their vacancy, while, the rank generated by the ordinary users should be in the set {1, ..., U}. After the learning period, if the rank generated by the priority users belongs to the set {1, ..., P}, then he accesses one of the best channels and may collide with a priority user (see algorithm 8). SU p generates a rank of the set {1, ..., P}, SU o generates a rank of the set {1, ..., U}, for t = C+1 to n do Each SU senses a channel in his index B i (t) according to his rank, if ξ p (t)=1 then SU p regenerates his rank of the set {1, ..., P}, else SU p retains his previous rank, if ξ o (t)=1 then SU o regenerates his rank of the set {1, ..., U}, else SU o retains his previous rank, Each SU updates his index B i (t)

			SU3 𝑆𝑈 𝑜 1
			SU2 𝑆𝑈 𝑜 2
	Primary Base Station
		SU1 𝑆𝑈
	Level 1	Level 2	Level 3	Level U
				at
	time t,
	ξ o (t): indicates a presence of collision under the oth ordinary user at
	time t,
	Initialization
	for t = 1 to C do
	Each user senses each channel once,
	Each SU updates his index B i (t),

FIGURE 5.2: Different priority levels in the secondary network 5.5.Algorithm 8: Priority and Fairness access (PFA) Input: ξ p (t), ξ o (t) ξ p (t): indicates a presence of collision under the pth priority user 𝑝 FIGURE 5.4: Cooperative transmission with one priority user

  .7, P Best shows three main parts:

	5.6. Simulation Results							103
			AUCB with APL
			UCB1 with APL
		7000	Musical Chair
			UCB1 with SLK
		6000	TS with APL
		5000
	Regret	4000
		3000
		2000
		1000
		0
		0	1	2	3	4	5	6	7	8	9
						Number of slots			10 4
			FIGURE 5.6: Regret of APL compared to SLK and Musical Chair
							policies

  Pbest of APL using TS and AUCB compared to QoS -UCB. Beside the vector Γ, let us define a vector G to represent the empirical mean of the quality observed from the channels: G = [ 0.75 0.99 0.2 0.8 0.9 0.7 0.75 0.85 0.8] Using the two vectors Γ and G, we obtain the global mean, Γ Q , that considers the vacancy as well as the quality of the channels:Γ Q = [0.67 0.79 0.14 0.48 0.37 0.28 0.22 0.17 0.08] After estimating Γ Q , and based on our policy APL, the first priority user SU 1 selects the channel with the highest global mean, i.e. the second entry in vector Γ Q , while the target of SU 2 , SU 3 and SU 4 are the channels 1, 4 and 5 respectively. This result can be observed in Fig.5.8, where each user selects his assigned channel based on QoS-UCB or QoS-AUCB. Moreover, QoS-AUCB enables the users to select their dedicated channels more frequently than in the case of QoS-UCB.

			a: The percentage to access the best channels under AUCB
			Pbest of SU1
			Pbest of SU2
			Pbest of SU3
	Pbest		Pbest of SU4
		10 0	10 1	10 2	10 3	10 4	10 5
	100	b: The percentage to access the best channels under TS Pbest of SU1
		80	Pbest of SU2 Pbest of SU3
	Pbest	60	Pbest of SU4
		40
		20
		0
		10 0	10 1	10 2	10 3	10 4	10 5
	100	c: The percentage that SU1 accesses his channel under AUCB and TS Pbest of SU1 under AUCB
		80	Pbest of SU1 under TS
	40 60 Pbest
		20
		0
		0	10 1	10 2	10 3	10 4	10 5
				Number of slots
			FIGURE 5.7:

  Let SNR ζ stand for the SNR threshold and SNR o (t) be the SNR of the o-th ordinary user SU o at time t. If SNR o (t) < SNR ζ , then this user may lose his transmitted data at time t; then, in the next time slot, SU o should send a request to the priority users. A priority user accepts the request of the SU o with the lowest SNR. Let H L o (t) indicate whether the transmission was successful at instant t for the o-th user. H L o (t) can be expressed as follow: H L o (t) = r i,o (t).C i,o (t).1 (SNR o (t)>SNR ζ ) || r i,p (t).C i,p (t).1 (SNR o (t)<SNR o (t) ) (5.34) where r i,o (t) and r i,p (t) stand for the state of the i-th channel selected by ordinary or priority users respectively, and they equal 1 if the channel is free and 0 otherwise. C i,o (t) and C i,p (t) indicate whether a collision occurs in the i-th channel, and they equal 1 if the user is the sole in occupied in the i-th

	5.6. Simulation Results								109
		0.8
		0.7
	Throughput Capacity (H)	0.3 0.4 0.5 0.6 0.2				H of SU2 using the proposed transmission technique H of SU2
		0.1				H of SU3 using the proposed transmission technique H of SU3
		0				H of SU1
		0	1	2	3	4	5	6	7	8	9	10
						Number of slots				10 4

β(t) indicates the channel selected by the user at instant t in the single user case while in the multi-access it indicates the channels selected by all users at slot t.

The variable S i (t) may represent the reward of the i th channel at slot t.

X i (T i (t)) can be also considered as the expected reward

The impact of the exploration phase during and after the learning period has not been considered in the well-known algorithms such as: UCB1 or e-greedy.

Under no-collision assumption, the regret represents the difference between the reward collected in the ideal scenario where each user accesses all-time his dedicated channel and the one obtained using a given policy.

After each collision and according to our policy APL, the user should regenerate a rank.

The nearest users to the primary base station are considered as priority ones, and a given user can change his set by changing the interval of his generated rank

For SU k , it should regenerate a rank in the set {1, ...k}.

Acknowledgements

First and foremost, I would like to thank my thesis director Prof. Ali MAN-

Chapter 3. MAB algorithms in OSA for Multiple Users Algorithm 4: Side Channel policy based on Upper Confidence Bound, Input: α, C, n, Parameters: k, I j , a(t, j), T i,j (t) k: cyclic sub-slot, I j : indicates the activity of the j th secondary user, % I j = 1 means SU active, otherwise I j = 0, a(t, j): indicates the channel selected by user j at time t, T i,j (t): the number of time the j th user senses the i th channel, Output: B i,j (t, T i,j (t)) B i,j (t, T i,j (t)) : the assigned index of the i th channel for the j th user, foreach t ∈ [1, C] do Each SU should visit each channel one time, Each SU should update his B i,j (t, T i,j (t)), while t ≤ n do t = t + 1, k = k mod(j) + 1, if I j = 0 then There is no transmission; And for all j > j, each SU j has the chance to exploit the (j -1)-th channel, else %test 1

Applies a MAB algorithm and searches the channel a(t, 1) that maximizes his index B i,1 (t, T i,1 (t)), Broadcasts a(t, 1) to other users, Transmits his data.

. . .

%test U SU U if k = U then

Eliminates all channels selected by other users, i.e. a(t, 1),..., a(t, U -1) Applies a MAB algorithm and searches the channel a(t, U) that maximizes his index B i,U (t, T i,U (t)), Transmits his data.

Simulation Results

In this section, we focus first on the well-known MAB algorithms, such as: As we can see, the regrets of the three MAB algorithms achieve logarithmic asymptotic behaviors with respect to time. So, after a finite number of time slots the user will be able to learn the vacancy probability of the channels and then access the most vacant one. Fig. 3.3 also shows that Thompson Sampling outperforms UCB and e-greedy may reach the lowest regret.

In Fig. 3.4, we compare the percentage of times to access the best channel, P best , by the SU that is given as follows:

In Fig. 3.4, P best shows three main parts:

• The initialization part from 1 to C, where the user selects each channel once in order to have a prior information about the vacancy probability of channels.

• The adaptation part that goes from C+1 to 2000 slots approximately.

Chapter 4

Distributed Learning for the Priority Cognitive Access

------------------------

Two SUs access three available channels. In this case, the total number of collisions for the two users is

The number of collisions in all channels produced by the users is

• If he does not identify well his dedicated channel.

• If he does not respect his prior rank 1 .

Let T k (n) and S s be respectively the total number of times, where the k th user badly identifies his dedicated channel and the time he needs to return to his prior rank. After each bad estimation, the user will change his dedicated channel. In this case, he may collide with other users until convergence to his prior rank. Subsequently, for all values of n, the total number of collisions for the k th user D k (n) can be upper bounded by:

As T k (n) and S s are independent, we have:

Let us find an upper bound of E[T k (n)], and let A k (t) be the event that the k th user identifies his dedicated channel, the k th best one, at instant t. Then, ∀ k + 1 ≤ i ≤ C and 1 ≤ m ≤ k -1, the event A k (t) takes place when the following condition is satisfied:

For a bad estimation event at instant t, ∃ i ∈ {k + 1, ..., C} and ∃ m ∈ {1, ..., k -1}, Āk (t) is true when we have the following condition:

Transmission Technique Based on PFA

In [START_REF] López-Martínez | A superprocess with upper confidence bounds for cooperative spectrum sharing[END_REF][START_REF] Simeone | Spectrum leasing to cooperating secondary ad hoc networks[END_REF][START_REF] Zhang | Stackelberg game for utility-based cooperative cognitiveradio networks[END_REF], the authors proposed a cooperative spectrum sharing among primary and secondary users in order to enhance the transmission rate of the former, and thus reduce his spectrum usage.

In this section, we propose a novel transmission technique based on our policy PFA in order to enhance the data rate and extend the transmission range of the secondary network.

When a secondary user is located in a fading location and having access only to poor channels, then he is not able to perform a direct transmission to the primary base station. Thus, this user has the ability to communicate with priority users SU p in order to ensure the transmission of his data. For a simplicity sake, let's consider one priority (SU p ) and two ordinary secondary users (SU o1 and SU o2 ) in the secondary network as shown in Fig. 5.4. In that figure, SU o1 and SU o2 might be interested in communicating with SU p to increase their transmission rate and range 2 .

If, SU o1 and SU o2 send a request to SU p at the same time, this latter is the case of non-error free in the Side Channel can be included in the future work.

• Consider a dynamic environment where the vacancy of channels evolves over time. Indeed, unlike e-UCB and several existing MAB algorithms, we believe that AUCB offers an important solution to adapt to a dynamic environment where the exploration is still having some impact after the learning period.

• In PFA, different priority levels may be considered with one or more users for each level. In our study, and for the simplicity sake, we considered a simplistic case of PFA with only two levels and the scenario with more than two levels should be investigated. Moreover, a concept proof of PFA should be done.

• The analytical convergence of APL has been investigated for a fixed number of users, while, for dynamic access, its performance has been tested only via simulation. Then, developing an analytical proof of APL for dynamic access is required in order to show its performance in a real radio environment.

• For a more realistic model, the future work may also investigate the effect of using the state-of-the-art spectrum sensing techniques to detect the activity of the Primary Users on the performance of the learning and decision-making. Moreover, considering the imperfect sensing, i.e. the probability of false alarm and miss detection, represents a new challenge to developing a more realistic network.

Appendix A Upper Bound of A in e-UCB

In this Appendix, we investigate the upper bound of A = t × Prob in e-UCB where Prob can be expressed as follows:

The index of the i-th channel B i (t, T i (t)) is based on the exploration, X i (T i (t)), and the exploitation, A i (t, T i (t)):

Then, we obtain:

By taking the minimum value of X 1 (T 1 (t -1)) + A 1 (t -1, T 1 (t -1)) and the maximum value of X i (T i (t -1)) + A i (t -1, T i (t -1)) at each time slot, we can upper bound Prob by the following equation:

where S i ≥ l to fulfill the condition T i (t -1) ≥ l. Then, we obtain:

The above probability can be upper bounded by:

Using the ceiling operator , let l = 4α ln(n)

, where

) in eq (A.5) becomes false, in fact:

Based on eq (A.5), we obtain:

Using Chernoff-Hoeffding bound 1 [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF], we can prove that:

1 According to [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF], Chernoff-Hoeffding theorem is defined as follows: Let X 1 , ..., X n be random variables in [0,1], and E[X t ] = µ, and let S n = ∑ n i=1 X i . Then ∀ a ≥ 0, we have

121

The two inequations above and inequation (A.6) lead us to:

Finally, we obtain:

This appendix stands for finding an upper bound of Z that contributes to finding an upper bound of e-UCB:

where a is a constant number that can be chosen as follows:

and

After the learning period where T i (t -1) ≥ l, we have: T 1 (t -1) >> T i (t -1). Then Z can be upper bounded by:

Using the Chernoff-Hoeffding in [125] 1 , we can upper bound the above equation as follows:

According to the proof provided in appendix A, we have l = 8 ln(n)

. So, we obtain:

1 According to [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF], Chernoff-Hoeffding theorem is defined as follows: Let X 1 , ..., X n be random variables in [0,1], and E[X t ] = µ, and let S n = ∑ n i=1 X i . Then ∀ a ≥ 0, we have

To resolve ∑ n t=1 t -2 , we consider the Taylor's series expansion of sin(t):

As sin(t) = 0 when t = ±kπ, then we obtain:

where q k is a general coefficient. By comparing the above equation with eq (C.2), we obtain ∑ n i=1 1 i 2 = π 2 3! . Finally, we obtain the upper bound of E[T i (n)] as follows:

Appendix D

Upper Bound of S s in MAUCB

Let us estimate the time S s and let us consider U users with different priority levels based on our policy APL. At a certain moment, supposing that each user has a random rank, then at least two of them may have the same rank, and a collision may occur. In this case, the collide users should regenerate a random rank around their prior rank 1 . After a finite number of collisions, the system will converge to the steady state where each user has a unique rank, i.e. its prior rank. Let S s be a random variable with a countable set of finite outcomes 1, 2, ... occurring with the probability p 1 , p 2 ... respectively, where p t represents a non-collision at instant t. The expectation of S s can be expressed as follows:

where the random variable S s follows the probability p[S s = t]:

and p indicates the probability of non-collision at an instant t, while (1p) t indicates the probability of having collisions from the instant 0 till t -1. Then we obtain:

Let I a (x) be defined as follows: where a is a constant number such that ax < 1. I(x) can converge to:

Based on the previous equation, we have:

Using the previous equation, we obtain:

Considering that a = 1p, we conclude that E[S s ] = 1-p p . To clarify the idea and estimate the probability p, we consider that three SUs are trying to find their prior rank where the Table (D.1) displays all the possible cases. Subsequently, the probability to converge to a steady state, i.e. the case 3, is p = 1 5 , and E[S s ] = 4. To estimate the value of p as well E[S s ], let us introduce the problem suggested in [START_REF] Bóna | A walk through combinatorics: An Introduction to Enumeration and Graph Theory[END_REF]Chapter 5], to count the number of ways of putting U identical balls into U different boxes. According to [START_REF] Bóna | A walk through combinatorics: An Introduction to Enumeration and Graph Theory[END_REF]Chapter 5], the probability p to converge to a steady state where each box has just one ball is p = 1

and E[S s ] = ( U 2U-1 ) -1. However, our problem of convergence to a steady state represents a restricted case of the problem introduced in [START_REF] Bóna | A walk through combinatorics: An Introduction to Enumeration and Graph Theory[END_REF]. Then, the expected time to converge to a steady state of our policy APL for U SUs can be upper bounded by:

List of publications

Journal Papers: