Keywords: Asymptotically Optimal Scheduling Schemes for Large Networks resources allocation, queuing delay, Age of information, Whittle's indices, Lagrangian Relaxation, Asymptotic optimality Q m . . . . . . . .

W ) in function of W for different values of n (L = 5

Résumé: Au courant de la dernière décennie, le nombre de machines connectées aux réseaux sans fils, a connu une croissance exponentielle à cause de l'apparition de l'Internet des Objets. Ainsi, le réseau sans fils 5G, est apparu pour accompagner cette grande évolution technologique. Parmi les exigences de la 5G est d'optimiser certaines métriques qui permettent une communication fiable et fluide, à savoir la latence des paquets et l'âge de l'information. Dans ce cadre, un problème majeur consiste à savoir comment partager les ressources disponibles entre le nombre massif des utilisateurs dans le réseau de telle façon à optimiser ces métriques en question. Pour répondre à cette problématique, nous étudions dans cette thèse le problème d'allocation des canaux où le nombre d'utilisateurs dans le système est supérieur à celui des canaux. Notre but est de trouver une solution qui permet d'allouer les canaux disponibles à un sousensemble d'utilisateurs à chaque instant, de manière à minimiser l'espérance de la moyenne à long terme du temps d'attente des paquets avant la transmission ou bien l'espérance de la moyenne à long terme de l'âge de l'information. Puisque le problème étudié entre dans le cadre des problèmes de Restless bandits, la solution optimale est hors de portée. Néanmoins, pour contourner cette difficulté, nous adoptons une approche basée sur les indices de Whittle pour obtenir une méthode d'allocation appelée "Whittle Index Policy" (WIP) qui qui est très performante avec une complexité faible, surtout lorsque le nombre d'utilisateurs et des canaux est suffisamment grand. Dans cette mesure, nous expliquons en détail, au chapitre 2, l'approche pour obtenir les indices de Whittle. Ensuite, nous étudions au chapitre 3 le problème d'allocation des canaux dans un système de files d'attente avec pour objectif de minimiser le temps d'attente des paquets dans les files. Nous adoptons une méthode basée sur la Relaxation Lagrangienne et nous démontrons que la solution optimale de l'équation de Bellman du problème dual est de type solution à seuils (threshold-based solution). Ensuite, nous prouvons que ce problème est indexable trouvons par la suite l'expression des indices de Whittle, en distinguant si la taille maximale des files est finie ou infinie. Puis, nous prouvons par une démonstration mathématique rigoureuse que notre solution est effectivement optimale dans le cas où le nombre d'utilisateurs est infiniment grand. Enfin, nous donnons des résultats numériques qui mettent en évidence la bonne performance de notre solution proposée et qui confirment nos résultats théoriques. Dans le chapitre 4, nous examinons le problème d'allocation des canaux dans un réseau sans fil avec pour objectif de minimiser l'âge de l'information moyen. Comme le problème étudié dans le chapitre 3 et de façon similaire, trouver une solution optimale n'est pas évident. De ce fait, nous adoptons également l'approche basée sur les indices de Whittle pour développer une politique d'allocation simple et performante. Notre principale contribution dans ce chapitre consiste d'une part à donner des résultats rigoureux sur l'optimalité asymptotique de la politique de Whittle (WIP) dans un régime où le nombre d'utilisateurs et des canaux tend vers l'infini. En effet, nous présentons une nouvelle approche mathématique pour établir l'optimalité lorsque l'âge de l'information n'est pas borné par une certaine valeur. Cette nouvelle approche est basée sur des techniques complexes (critères de Cauchy, etc.), et contrairement aux travaux précédents, la démonstration n'exige aucune hypothèse simplificatrice sur le système considéré. Finalement, nous présentons des résultats numériques qui montrent l'optimalité de la politique de Whittle et qui confirment nos résultats théoriques.

eral channel allocation problem where the number of channels is less than that of users. The aim is to find a policy that schedules the channels to a given subset of users at each time slot in such a way to minimize two different objectives functions namely, the long-run expected average queuing delay (chapter 3) and the long-run expected average age of information (Chapter 4). We show that our problems fall in the framework of Restless Bandit Problems (RBP), for which obtaining the optimal solution is known to be out of reach. To circumvent this difficulty, we tackle the problem by adopting a Whittle index approach. In Chapter 2, we explain the Lagrangian relaxation, the steady-state and discounted cost approaches used to obtain the expressions of Whittle indices. The structure of each subproblem's optimal solution is provided in chapter 3 and 4 depending on the system models and the considered metrics (queue length or Age of Information).

In Chapter 3, the objective of the scheduling problem is to minimize the total average backlog queues of the network in question. We apply the Lagrangian relaxation approach detailed in Chapter 2 for the present model, and we prove that the optimal solution of the one-dimensional problem is of type threshold policy. After that, we establish that the aforementioned problem is indexable. Armed with that, we apply the discounted cost approach when the queue size is infinite and the steady-state approach when the queue size is tight to obtain the Whittle indices expressions. We then provide rigorous mathematical proof that our policy is optimal in the infinitely many users regime. Finally, we provide numerical results that showcase the remarkable good performance of our proposed policy and that corroborate the theoretical findings.

In Chapter 4, we examine the average age minimization problem where users transmit over unreliable channels. Similarly to the problem studied in Chapter 3, finding the optimal scheduling scheme is known to be challenging. Accordingly, we adopt the Whittle index approach to derive the Whittle indices. Our main contribution is to provide rigorous results on the asymptotic optimality of Whittle Index Policy (WIP) in the many-users regime when the state space of the age of information is finite. However, when the state space of the Age of Information is infinite, we provide a new mathematical approach to establish the optimality of WIP for specific network settings. This novel approach is based on intricate techniques, and unlike previous works in the literature, it is free of any mathematical assumptions. Finally, we lay out numerical results that corroborate our theoretical findings and demonstrate the policy's notable performance in the many-users regime.

First and foremost, I would like to thank God for all his blessings and for providing me the opportunity to work in a research field that I appreciate. I would like to express my sincere gratitude to my advisor Prof. Mohamad Assaad for the continuous support of my Ph.D. study and research, for his motivation, for his encouragement during my thesis. He offered me generously his time and gave me relevant advice about technical and non-technical issues regarding my thesis and its development. He always had faith in me and encouraged me to move forward with my research and my studies. His guidance helped me in all the time of research and writing of this thesis. I also express my deepest thanks to Doctor Larranaga Maialen for giving me the necessary advice and guidance, which were extremely valuable for my progress concerning my work during my internship, which is an initiation of my thesis. I would also like to express my appreciation to the jury committee members: Nikkos Pappas, Rachid El Azouzi, Inbar Fijalkow, Omur Ozel, and Samson Lasaulce for the time spent reading this work and for all their valuable feedback on it. Thanks also go out to my office colleague Ali Maatouk with whom I try to solve some issues confronted in our collaborative works. I thank him also for his valuable assistance in writing articles. I would also like to thanks the professors who helped me through skills training to improve my professional attitude. I thank all my friends who support me during my time in French. I would also like to express my gratitude to my brother Yassine for his constant support during my thesis, and all my brothers and sisters who always encouraged me. I am extremely grateful to my beloved parents in Morocco for their unlimited support during my years in France and all my life. Thank you for your sacrifices, your love, your encouragement, and your trust. Special thanks to my mother for her crucial role and invaluable assistance. I am forever indebted to her.

Chapter 1 Introduction en français 1.1 Motivation

Au cours du siècle dernier, le monde a assisté à un changement radical dans la communication grâce à l'apparition de technologies électriques et électromagnétiques telles que les téléphones, les télévisions et les ordinateurs. Cette transformation stupéfiante trouve son origine dans les développements pionniers des communications sans fil de Nikola Tesla, connu pour être l'inventeur de la radio. Les technologies de télécommunication ont dès lors connu une progression exponentielle en termes de performance, d'accessibilité et de quantité, au point qu'aujourd'hui, nous vivons dans un monde entièrement connecté où chaque être humain peut communiquer avec un autre être humain, quel que soit son endroit. Par ailleurs, selon les données d'intelligence en temps réel de GSMA, le nombre d'utilisateurs d'appareils mobiles dans le monde dépasse aujourd'hui les 5 milliards. Cela représente 66.5% de la population mondiale. D'autre part, grâce à l'émergence de l'IA (intelligence artificielle), les appareils sont devenus plus autonomes et conscients d'eux-mêmes. Cela conduit à l'apparition d'un grand nombre de machines dotées d'identifiants uniques et capables de transférer des données sur un réseau sans nécessiter d'interaction entre humains ou entre ordinateurs. Ce phénomène est mieux connu sous le nom d'IdO (Internet des Objets). En fait, d'ici la fin de l'année 2030, environ 50 milliards de ces dispositifs IdO seront utilisés dans le monde [1], créant ainsi un réseau massif de dispositifs interconnectés couvrant plusieurs domaines tels que les réseaux de véhicules, les maisons intelligentes, la surveillance de l'environnement, les soins médicaux et de santé, la sécurité et les transports. D'autre part, pour assurer une communication fiable entre deux hôtes finaux distants, nous devons disposer de ressources telles que la bande de fréquences. Cependant, ces ressources radio sont limitées par rapport au nombre massif de dispositifs dans le système de réseau actuel. Dans cette mesure, il faut partager efficacement ces ressources disponibles entre les appareils des utilisateurs et les objets connectés pour répondre aux exigences de service de chaque appareil connecté. Les exigences de chaque dispositif peuvent se manifester différemment : Par exemple, certains appareils implémentent des logiciels qui nécessitent un débit de données élevé (le nombre de paquets transmis par unité de temps). D'autres applications sont plus sensibles aux temps d'attente, comme les jeux vidéo et les vidéoconférences, et exigent alors une faible latence, c'est-à-dire que Chapter 1. Introduction en français le temps entre l'envoi de données par un hôte final et la réception de données par l'autre hôte final doit être aussi faible que possible. Par ailleurs, d'autres applications de surveillance deviennent populaires et attirent l'attention des chercheurs de nos jours. Dans ces applications, certaines entités centrales ont besoin de recevoir des mises à jour fréquentes d'une information d'intérêt telle que la température, la vitesse et ou la position dans les réseaux de véhicules, pour exécuter une tâche donnée. Néanmoins, pour effectuer l'action appropriée, elle doit acquérir l'information la plus récente et la plus fraîche transmise par les capteurs. Cette notion de fraîcheur peut être quantifiée par l'âge de l'information (AdI). Afin d'offrir les services susmentionnés dans les systèmes sans fil, une branche bien connue des problèmes d'optimisation, à savoir les problèmes d'ordonnancement et d'allocation de ressources, a été développée permettant ainsi de répondre aux exigences de tels services. Le problème de l'ordonnancement a été largement étudié dans le passé, et plusieurs politiques d'allocation ont été développées pour différents contextes dans différents domaines. Plus précisément, dans le domaine des Télécommunications et en particulier dans le domaine des réseaux sans fil, plusieurs politiques d'ordonnancement sont proposées pour obtenir une bonne performance des réseaux et répondre aux exigences de service. En outre, comme il a été mentionné précédemment, l'émergence de l'IdO et la croissance considérable des appareils des utilisateurs dans les réseaux 5G nécessitent le développement des politiques d'allocation des ressources pour optimiser certaines métriques pertinentes telles que le débit, la latence, le temps d'attente et l'âge de l'information lorsqu'il y a un nombre massif de machines. Dans ce contexte, nous abordons dans notre thèse les problèmes d'ordonnancement des utilisateurs et des canaux et nous nous focalisons sur la minimisation du temps d'attente moyen dans les files d'attente et de l'âge moyen de l'information. Plus précisément, nous étudions le problème suivant : Comment allouer K ressources à N utilisateurs de manière à minimiser une certaine métrique, en particulier Age de l'information et Temps d'attente.

Ordonnancement basé sur le temps d'attente

Aujourd'hui, surtout après les perturbations sociales et économiques généralisées causées par la pandémie mondiale COVID-19, une solution alternative a été mise en place pour éviter l'interruption de la communication entre les personnes, notamment dans les entreprises et les institutions publiques. En effet, des technologies telles que la VoIP, la téléconférence et la télé-présence robotique ont été adoptées pour assurer une communication en temps réel entre les collaborateurs et les membres de la famille. Ces technologies permettent un échange quasi simultané d'informations entre l'émetteur et le récepteur. Dans cette mesure, comme nous vivons dans un monde où un nombre massif de machines sont connectées, il s'avère pertinent de partager la bande passante du canal entre les utilisateurs de manière optimale afin de réduire la latence. Cette métrique peut être décomposée en deux variables : le temps d'attente dans la file d'attente et le délai de propagation. La première concerne la couche logique, elle correspond au temps entre l'arrivée du paquet dans la file d'attente de l'utilisateur et sa sortie de celle-ci. Quant au délai de propagation, il correspond au temps que met le signal pour arriver au récepteur. Dans cette thèse, nous nous concentrons davantage sur le contexte d'ordonnancement qui minimisent la longueur moyenne de la file d'attente (et donc le temps d'attente moyen de la file) dans un modèle de réseau en temps discret. Ceci dit, le délai de propagation sera normalisé à l'unité de temps. Plus précisément, notre objectif est de trouver une politique d'ordonnancement qui alloue les canaux disponibles à un sous-ensemble donné d'utilisateurs de manière à minimiser la longueur moyenne des files d'attente des utilisateurs, ce qui résulte, selon la loi de Little [2] en la minimisation du temps d'attente moyen. Par conséquent, pour traiter ce problème, nous devons d'abord étudier l'évolution de la file d'attente pour chaque utilisateur. Pour cela, nous donnons dans ce qui suit un bref aperçu du modèle de file d'attente discrète considéré dans notre thèse en relation avec le problème qui nous intéresse : Notre système de files d'attente est composé de N files d'attente et de K canaux. Le nombre de canaux est inférieur au nombre de files d'attente. De plus, chaque file d'attente a un processus d'entrée et de sortie. Le processus d'entrée indique l'arrivée des paquets dans la file, tandis que le processus de sortie désigne le départ des paquets de la file. Dans le cas discret, le processus d'arrivée suit un processus discret iid (indépendant et identiquement distribué). Plus précisément, le nombre de paquets arrivés à l'instant actuel ne dépend pas de celui de l'instant précédent. De même, le processus de départ est un processus iid discret dans le temps. Dans cette mesure, en désignant par Q(t), A(t), D(t), la longueur de la file d'attente, le processus d'arrivée, et le processus de départ respectivement au temps t, la longueur de la file d'attente évolue de façon stochastique comme suit :

Q(t + 1) = max{Q(t) -D(t), 0} + A(t)
En se basant sur l'équation ci-dessus, le processus Q(t) peut être modélisé comme une chaîne de Markov puisque la valeur de Q(.) à l'instant suivant ne dépend que de l'état actuel. Cette propriété est mieux connue comme loi sans mémoire. Dans cette mesure, notre objectif est de sélectionner à chaque instant, K parmi N utilisateurs auxquels les K canaux sont alloués de manière à minimiser l'expectation de la moyenne totale des files d'attente de tous les utilisateurs (Figure 1.2). L'expression explicite du problème susmentionné est fournie dans le chapitre 4.

Ordonnancement basé sur l'âge

Il est largement reconnu que l'IdO apportera une amélioration impressionnante dans divers domaines et secteurs de nos activités quotidiennes. Dans cette mesure, il est en- visagé qu'un monde numérique futur soit composé de nombreux capteurs et dispositifs connectés sans fil et à faible coût. Cela permettra aux moniteurs d'exécuter certaines opérations en exploitant les informations acquises par des capteurs distants. Cependant, l'information du côté des moniteurs doit être aussi fraîche que possible pour effectuer les opérations appropriées. Cette notion de fraîcheur peut être capturée, comme il a été mentionné précédemment, par la notion d'âge de l'information. En effet, le concept d'âge de l'information (AdI) a été introduit pour la première fois en 2011 dans le but de quantifier la fraîcheur des informations dont nous disposons sur l'état d'une donnée d'intérêt. Plus précisément, l'AdI peut être considérée comme la durée qui sépare l'instant de génération du dernier paquet reçu avec succès et l'heure actuelle. L'AdI a attiré de nombreux chercheurs (par exemple, [3][4][5][6]) avec plus de 50 publications à ce jour en raison de sa bonne adéquation avec le concept de fraîcheur de l'information. En effet, on peut remarquer que les métriques de débit, temps d'attente et la latence ne capturent pas la notion d'intemporalité ou de fraîcheur de l'information comme le fait l'AdI. Pour souligner ce fait, nous expliquons les deux approches suivantes où la source transmet des paquets sous forme des mises à jour d'une certaine information.

• Maximisation du débit:

Pour maximiser le débit d'un hôte final donné, ou explicitement pour maximiser la quantité de données envoyées par la source dans une unité de temps, nous devons augmenter autant que possible le taux de génération de paquets pour tirer le meilleur parti de la capacité du canal. L'inconvénient de cette méthode est qu'un délai de retard sera encouru dans la file du canal. Par conséquent, le moniteur recevra des paquets pour lesquels le temps de livraison est considérablement plus grand que leur temps de génération. Donc, cette approche ne permet pas de satisfaire la propriété de ponctualité du système de mise à jour C'est pour cette raison que la métrique de l'âge de l'information a été créée pour optimiser le système de mise à jour des statuts. Mathématiquement, l'AdI est formulé comme suit:

δ(t) = t -max i {s i : d i ≤ t} où s i et d i désignent
d i = s i + 1
Si le paquet est perdu pendant la transmission, la mise à jour correspondante est rejetée. Par conséquent, il faut donner une nouvelle formulation mathématique qui correspond au problème d'ordonnancement étudié dans notre thèse au chapitre 5. qui sera décrit en détail dans le chapitre 5.1.2. L'évolution de l'AdI est :

δ(t) = t -max i {s i : s i ≤ t -1} (1.1)
À la lumière de ce fait, on peut observer sur la figure 1.4 que lorsque une nouvelle mises à jour de l'information en question est générée, ou de manière équivalente, lorsque le canal est alloué au capteur concerné, la valeur de l'âge passe à 1 à l'instant suivant en supposant que la transmission est réussie. 1.4 Etat de l'Art Dans [START_REF] Wang | Delay-aware two-hop cooperative relay communications via approximate mdp and stochastic learning[END_REF][START_REF] Bettesh | Optimal power and rate control for minimal average delay: The single-user case[END_REF], les auteurs tentent de minimiser le temps d'attente moyen dans les files des utilisateurs en utilisant le processus de décision de Markov (PDM) et des outils d'apprentissage stochastique. Cette méthode a également été adopté dans [START_REF] Cui | Distributive stochastic learning for delay-optimal ofdma power and subband allocation[END_REF] pour traiter le problème de l'allocation de puissance dans un système OFDM (Orthogonal Frequency Division Multiplexing) avec pour objectif de minimiser le temps d'attente moyen des paquets des utilisateurs dans les files d'attente. Cependant, la solution développée nécessite une mémoire et une complexité de calcul élevées.

Politique de Whittle index pour minimiser le temps d'attente

Les politiques basées sur l'indice de Whittle ont été utilisées/développées dans les réseaux sans fil dans le cadre de problèmes d'ordonnancement en raison de leur faible complexité et de leurs bonnes performances dans la plupart des cas : [START_REF] Liu | Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access[END_REF][START_REF] Ansell | Whittle index policy for a multi-class queueing system with convex holding costs[END_REF][START_REF] Aalto | Whittle index approach to size-aware scheduling with time-varying channels[END_REF][START_REF] Akbarzadeh | Restless bandits with controlled restarts: Indexability and computation of whittle index[END_REF][START_REF] Avrachenkov | Whittle index policy for crawling ephemeral content[END_REF][START_REF] Borkar | Whittle index for partially observed binary markov decision processes[END_REF][START_REF] Iannello | Optimality of myopic scheduling and whittle indexability for energy harvesting sensors[END_REF][START_REF] Larrañaga | Asymptotically optimal pilot allocation over markovian fading channels[END_REF][START_REF] Meshram | On the whittle index for restless multiarmed hidden markov bandits[END_REF][START_REF] Ouyang | Downlink scheduling over markovian fading channels[END_REF][START_REF] Sombabu | Whittle index for aoi-aware scheduling[END_REF][START_REF] Tripathi | A whittle index approach to minimizing functions of age of information[END_REF][START_REF] Wang | Whittle index policy for dynamic multichannel allocation in remote state estimation[END_REF][START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF]. Dans [START_REF] Ansell | Whittle index policy for a multi-class queueing system with convex holding costs[END_REF], une dérivation des valeurs de l'indice de Whittle pour un modèle M/M/1 multi-classe simple a été considérée (où un seul utilisateur peut être servi). Cependant, l'optimalité de la politique d'indice de Whittle obtenue n'a pas été prouvée. Les auteurs dans [START_REF] Weber | On an index policy for restless bandits[END_REF] ont considéré le problème de l'ordonnancement des projets/travaux dans lequel un effort est alloué à un nombre fixe de projets. La performance d'une politique basée sur l'indice de Whittle a été analysée dans un modèle à temps continu. Dans [START_REF] Larrañaga | Dynamic control of birth-and-death restless bandits: Application to resource-allocation problems[END_REF], une politique basée sur l'indice de Whittle a été dérivée pour un système de file d'attente composé de plusieurs classes et serveurs où l'arrivé et le départ des paquets évoluent selon un processus de naissance et de mort. Dans [START_REF] Van Mieghem | Dynamic scheduling with convex delay costs: The generalized c| mu rule[END_REF], une politique d'indexation optimale appelée loi cµ généralisée (Gcµ) est développée dans le contexte d'un régime de trafic intense avec un coût de temps d'attente convexe. En outre, contrairement à la politique de la règle cµ, [START_REF] Mandelbaum | Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cµ-rule[END_REF] établit l'optimalité de la règle cµ-généralisée (Gcµ) même avec plusieurs serveurs. Dans [START_REF] Ansell | Whittle index policy for a multi-class queueing system with convex holding costs[END_REF], les auteurs calculent la politique d'indexation de Whittle pour un système de file d'attente comportant plusieurs classes avec des fonctions de coût générales. Nous notons que pour ces travaux cités, contrairement à notre modèle, le temps a été considéré comme étant continu.

Problème d'ordonnancement: Minimisation de l'Age

Parmi les premiers travaux qui étudient le problème de minimisation de l'AdI, on trouve celui de Kaul, Gruteser et Yates [4]. Ils considèrent un modèle de système où une source transmet des paquets contenant des mises à jour d'une information particulière à une destination. Le canal est représenté par une simple file d'attente. Dans ce travail, les auteurs montrent que ni l'envoi de mises à jour à une forte cadence ni l'envoi de mises à jour à une faible cadence ne permettent d'avoir une livraison opportune des paquets transmis. En effet, la solution optimale n'est pas triviale, comme on peut le prévoir. Dans [START_REF] Kaul | Age of information: Updates with priority[END_REF], les auteurs étudient l'impact de la salle d'attente sur l'AdI dans un système de file d'attente où plusieurs flux d'information partagent un service commun avec une seule salle d'attente qui peut accueillir au plus un paquet. Ces flux ont des priorités différentes. Les auteurs ont trouvé le taux d'arrivée optimal des mises à jour qui minimise l'âge moyen de chaque flux.

Dans le cadre des problèmes d'ordonnancement, de nombreux travaux (par exemple, [START_REF] Bedewy | The age of information in multihop networks[END_REF][START_REF] Kadota | Scheduling policies for minimizing age of information in broadcast wireless networks[END_REF][START_REF] Hsu | Age of information: Design and analysis of optimal scheduling algorithms[END_REF][START_REF]Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals[END_REF][START_REF] Sun | Age-optimal updates of multiple information flows[END_REF][START_REF] Bacinoglu | Scheduling status updates to minimize age of information with an energy harvesting sensor[END_REF][START_REF] Ceran | Average age of information with hybrid arq under a resource constraint[END_REF]) ont étudié ce type de problèmes afin de minimiser l'âge de l'information dans des contextes variés. Dans cette optique, nous citons dans ce qui suit quelques travaux intéressants liés à notre domaine d'études.

Ordonnancement tenant compte de l'énergie [START_REF] Bacinoglu | Scheduling status updates to minimize age of information with an energy harvesting sensor[END_REF] étudie un scénario de détection en temps réel sous contraintes d'énergie et de batterie.

Les auteurs trouvent une politique de seuil optimale en terme d'AdI en fonction de l'énergie et des états d'âge actuels estimés. Un autre travail intéressant dans ce domaine est [START_REF] Ceran | Average age of information with hybrid arq under a resource constraint[END_REF], où les auteurs étudient un problème d'ordonnancement pour minimiser l'AdI en considérant que le taux de mise à jour de la source ne peut pas dépasser une certaine limite prédéfinie en raison de limitations énergétiques. Ils fournissent une dérivation analytique de la solution optimale lorsque les statistiques du canal sont connues.

Algorithmes d'apprentissage stochastiques

De nombreux algorithmes ont été développés pour trouver l'ordonnancement optimal par rapport à l'AdI en se basant sur des outils d'apprentissage stochastiques. Par exemple, [START_REF]Reinforcement learning to minimize age of information with an energy harvesting sensor with harq and sensing cost[END_REF] propose un algorithme d'apprentissage par renforcement à coût moyen qui apprend les paramètres du système, à savoir les statistiques de canal et de récolte d'énergie, afin d'obtenir la politique optimale. Dans [START_REF] Beytur | Age minimization of multiple flows using reinforcement learning[END_REF], les auteurs considèrent le problème de l'ordonnancement de plusieurs flux desservis par un seul serveur.

Contributions et Aperçu de la thèse

Cette thèse est structurée en trois chapitres. Plus précisément :

• Chapitre 3: Dans ce chapitre, nous expliquons en détail la méthodologie appliquée pour obtenir la politique de l'indice de Whittle (WIP). Plus précisément, nous expliquons en détail les étapes pour obtenir les indices de Whittle et nous exposons la méthode utilisée pour montrer l'optimalité de WIP dans le régime multi-utilisateurs.

Motivation

In the last century, the world has witnessed a radical change in communication thanks to the apparition of electrical and electromagnetic technologies such as phones, televisions, and computers. This astounding transformation has its origin in the pioneering developments in wireless communications by Nikola Tesla, who is known to be the inventor of the radio. The telecommunication technologies have thenceforth known an exponential advancement in terms of performance, reachability, and quantity to the extent that today, we live in a fully connected world where each human-being can communicate with the other human being regardless of their locations. Besides, according to GSMA real-time intelligence data, the number of mobile device users worldwide today surpasses 5 billion. That is 66.5% of the world's population. On the other side, due to the emergence of AI (Artificial Intelligence), the devices became more autonomous and self-aware. That leads to the apparition of a huge number of machines provided with unique identifiers and can transfer data over a network without requiring human-to-human or human-to-computer interaction. This is better known by IoT (Internet of Things). In fact, by the end of 2030, around 50 billion of these IoT devices will be in use around the world [1], creating a massive web of interconnected devices covering several domains such as vehicular network, smart homes, environmental Monitoring, Medical and health-care, security, transportation.

On the other hand, to ensure reliable communication between two distant end-hosts, we need to afford resources such as frequency band. However, these radio resources are limited compared to the massive number of devices in the network system nowadays. To that extent, one should effectively share these available resources between users' devices and connected objects to meet the service requirement for each connected device. Each device's requirements can be manifested differently: For instance, some devices implement software that needs a high data rate (the number of transmitted packets per time unit). Other applications are more delay sensitives, such as video games and video conferencing, and then require low latency, i.e., the time between sending data by one end-host and receiving data by the other end-host should be as low as possible. Besides, other monitoring applications are becoming popular and attract the attention of researchers nowadays. In such applications, some central entities need to receive frequent updates about an information of interest such as temperature, velocity and position in vehicular networks, to execute a given task. Nevertheless, to perform the appropriate action, it needs to acquire the up-to-date and the freshest information from the sensors. This notion of freshness can be captured by Age of Information (AoI).

In order to offer the aforementioned services in wireless systems, a well known branch of optimization problems, namely scheduling and resource allocation problems, has been developed allowing thus to meet the requirements of such services.

The scheduling problem has been widely studied in the past, and several allocation policies have been developed for various contexts in different fields. Specifically, in the field of Telecommunication and precisely in wireless network domain, several scheduling policies are proposed to achieve a good performance of networks and meet the service requirements. Moreover, as it was mentioned before, the emergence of IoT and the considerable growth of users' handsets in 5G networks requires the development of resource allocation frameworks to optimize some relevant metrics such as throughput, latency, queuing delay, and age of information when there are a massive number of machines. In this context, we tackle in our thesis users and channels scheduling problems and we focus on minimizing the average delay and the average age of informaion. More precisely, we study the following problem: How to allocate K resources to N users in such a way to minimize a certain metrics, in particular Age Of Information and Queuing Delay.

Delay-based Scheduling

Today, especially after the widespread social and economic disruption caused by the global pandemic COVID-19, an alternative solution has taken place to avoid interruption of communication between people, particularly in companies and state institutions. Indeed, technologies such as VoIP, teleconferencing, and robotic telepresence have been adopted to ensure real-time communication between the collaborators and family members. These technologies allow a near simultaneous exchange of information from the sender to the receiver in a connection with negligible latency. To that extent, as we live in a world where a massive number of machines are connected, it turns out to be relevant to share the channel bandwidth between users in an optimal way in order to reduce the latency. This metric can be decomposed into two variables: queuing delay and propagation delay. The first one concerns the logical layer, it refers to the time between the packet arrival in user's queue and its departure from it. As for the propagation delay, it refers to the amount of time it takes for the signal to travel from the sender to the receiver. In this thesis, we focus more on scheduling frameworks that minimize the average queuing length (and hence the average queuing delay) in a discrete time network model. Having said that, the propagation delay will be normalized to the time unit. Specifically, our objective is to find a scheduling policy that allocates the available channels to a given subset of users in such a way to minimize the average queue length of the users which results, according to Little's Law [2] in the minimization of the average delay. Therefore, to deal with this problem, we need first to investigate the evolution of the queue for each user. To proceed so, we give in the following a brief insight about the discrete queuing model considered in our thesis related to our problem of interest: Our queueing system is composed by N queues and K channels. The number of channels is less than the number of queues. Furthermore, each queue has an input and output process. The input process indicates the packets' arrival to the queue, while the output process designates the packets' departure from the queue. In the discrete case, the arrival process follows a discrete iid (independent and identically distributed) process. Specifically, the number of arrived packets at the current time doesn't depend on that at the previous time slot. Likewise, the departure process is a discrete iid process over time. To that extent, denoting by Q(t), A(t), D(t), the queue length, the arrival process, and the departure process respectively at time t, the queue or the buffer length evolves stochastically as follows: Based on the above equation, the process Q(t) can be modeled as a Markov chain since the value of Q(.) at the next time slot depends only on the current state. This property is better known as memoryless. To that extent, our goal is to select per each time slot K among N users to which the K channels are allocated in such a way to minimize the Chapter 2. Introduction total expected average queues of all users. The explicit expression of the aforementioned problem is provided in Chapter 4.

Q(t + 1) = max{Q(t) -D(t), 0} + A(t)

Age-based Scheduling

It is widely recognized that IoT will bring an impressive enhancement in various areas and domains of our daily activities. To that extent, it is envisioned that a future digital world will be composed of numerous wireless low-cost connected sensors and devices. This will allow to the monitors to execute some operations exploiting the information acquired remotely from the sensors. Meanwhile, the information at the monitors side should be as fresh as possible to perform the appropriate and convenient operations. Accordingly, as it was mentioned previously, the notion of freshness can be captured by the notion of AoI. Indeed, the concept of Age of Information (AoI) was introduced the first time in 2011 in [START_REF] Kaul | Minimizing age of information in vehicular networks[END_REF] to quantify the freshness of the information that we have about the status of a given data of interest. More specifically, AoI can be viewed as the duration which separates the generation of the last successfully received packet's time-stamp and the current time. AoI has attracted many researchers (for instance, [3][4][5][6]) due to its well-fitting with the concept of freshness of information. Indeed, one can remark that the metrics of throughput, delay, and latency don't capture the notion of timeless or freshness of the information as AoI does. To highlight this fact, we explain the two following approaches where the source transmits packets as status updates.

• Throughput maximization: To maximize the throughput of a given end-host, or explicitly to maximize the amount of data sent by the source within a unit of time, we need to increase as much as possible the generation rate of packets to make the most of the canal capacity. The shortcomings of this is high delays will be incurred in channel buffer. Therefore, the monitor will receive packets for which the delivery time is considerably larger than their generation time. As a consequence, this approach falls short in satisfying the timeliness property of the status updates system.

• Delay minimization:

We now explain why the delay minimization cannot capture the notion of freshness of information. In fact, minimizing the packets' delay can be achieved by decreasing the generation rate of packets to alleviate the burden on the system. By doing so, the time between the generation of the status update and its reception by the monitor will be reduced. However, the monitor will receive outdated status information about the system since the updates generation rate is low.

For this reason, the Age of Information metric was arisen to optimize the status updates system. Mathematically, AoI is formulated as follows:

δ(t) = t -max i {s i : d i ≤ t}
where s i and d i refer to the generation time of the i-th status update packet and the delivery time to the monitor respectively. From this definition, one can notice that effectively δ(t) captures well the notion of the freshness since a small value of δ(t) implies that the monitor possess a fresh status update, and if δ(t) is large, the monitor possess an outdated status update.

Figure 2.3 -Illustration of the AoI evolution

These status updates can be either generated at the will of the source-sensor or spontaneously depending on external factors such as climate change or velocity variation.

To that extent, considering the scheduling problem's framework, in the scenario where the remote source can generate status updates at any desired time instance, it sounds that to avoid a useless waste of energy, the source or the sensor should not generate a status update if it is not allowed to transmit. Subsequently, the pertinent and the optimum way to minimize as possible the energy consumed by sensors is to produce packets only at the request of the monitor, i.e., when this later allocates the channel to the sensor in question. This leads also to reduce the average AoI, since the delay between the generation and the reception of the packet carrying the information about the process of interest is restricted only to the delay incurred in the channel buffer. Moreover, assuming that there is no additional delay caused by the channel except that of signal's propagation which is normalized to one, then s i and d i that refer to the generation time slot and delivery time slot of the i-th status update packet successfully received by the monitor respectively, verify:

d i = s i + 1
If the packet is lost during the transmission, then the corresponding status update is discarded. Therefore, one should give a new mathematical formulation that fits with the scheduling problem studied in our thesis in Chapter 5. Accordingly, the evolution of AoI is:

δ(t) = t -max i {s i : s i ≤ t -1} (2.1) Chapter 2. Introduction
In light of that fact, one can observe in figure 2.4 that when the new status updates is generated, or equivalently, when the channel is allocated to the concerned sensor, the value of the age goes to 1 at the next time slot assuming that the transmission is successful. As the number of connected end-hosts in the networks has significantly increased while the available resources such as transmission channels are still limited, it is worthwhile to study the resource allocation problems to minimize AoI metric in a large network system.

To that extent, we study in our thesis the following problem: how to allocate the K channels to the N users in such a way to minimize the total average age of information of all users of the system. The mathematical derivation of the aforementioned problem is given in Chapter 5. Several works have studied the scheduling problems for minimizing the delay metric (for instance [START_REF] Wu | End-to-end delay minimization for scientific workflows in clouds under budget constraint[END_REF][START_REF] Liu | Delay minimization and priority scheduling in wireless mesh networks[END_REF][START_REF] Liu | Delay-optimal computation task scheduling for mobile-edge computing systems[END_REF][START_REF] He | Delay minimization for data dissemination in large-scale vanets with buses and taxis[END_REF][START_REF] Nazir | Dynamic sleep scheduling for minimizing delay in wireless sensor network[END_REF][START_REF] Zhang | Resource scheduling for delay minimization in multi-server cellular edge computing systems[END_REF]). In the sequel, we cite some relevant works in this particular area.

Energy-aware scheduling

Energy conservation is getting great attention in 5G networks; however, as we know that there is a trade-off between saving energy and provisioning performance guarantees, especially end-to-end delays.

To that extent, [START_REF] Rajan | Delay-bounded packet scheduling of bursty traffic over wireless channels[END_REF] studies minimal power transmission of bursty sources over wireless channels with constraints on mean queuing delay. They propose a low-complexity scheduler that has a near-optimal performance. Regarding the energy that allows a machine to stay active whether it is in a transmit mode or idle mode, on can consider that the best way to save this power consumed is to turn off the machines. However, transitioning between the active and sleeping modes consumes considerable power and increases the delay. [START_REF] Andrews | Routing and scheduling for energy and delay minimization in the powerdown model[END_REF] investigates this problem in a multi-hop network and proposes for a line topology as well as for an arbitrary topology, a scheduling policy that is near-optimal with regards to delay metric for a minimum active period per element of the network.

Stochastic learning algorithms

Significant number of works in the literature use Markov Decision Process (MDP) frameworks and develop allocation strategies using stochastic learning algorithms [START_REF] Cui | Distributive stochastic learning for delay-optimal ofdma power and subband allocation[END_REF][START_REF] Cui | A survey on delay-aware resource control for wireless systems-large deviation theory, stochastic lyapunov drift, and distributed stochastic learning[END_REF][START_REF] Zheng | Delay-optimal virtualized radio resource scheduling in software-defined vehicular networks via stochastic learning[END_REF][START_REF] Wang | Delay-aware two-hop cooperative relay communications via approximate mdp and stochastic learning[END_REF][START_REF] Ruan | Delay-aware massive random access for machine-type communications via hierarchical stochastic learning[END_REF][START_REF] Li | Resource allocation optimization for delay-sensitive traffic in fronthaul constrained cloud radio access networks[END_REF][START_REF] Lei | Delay-optimal dynamic mode selection and resource allocation in device-to-device communications-part ii: Practical algorithm[END_REF], (e.g., by using value iteration, policy iteration, etc.) in order to optimize the delay in users' queues in scheduling problem backgrounds. However, MDP frameworks suffer from the curse of dimensionality, which leads to complex resource allocation strategies. For instance, [START_REF] Zhang | Resource scheduling for delay minimization in multi-server cellular edge computing systems[END_REF] studies resource scheduling for delay minimization in multi-server cellular edge computing systems. The authors propose a solution based on a new Lyapunov function called the delay-based Lyapunov function. Specifically, they design a scheduling algorithm based on this new function to derive an approximate solution that minimizes both queuing and propagation delay. They further establish that the proposed algorithm gives good performance compared to the traditional Lyapunov method based scheduling algorithm. However, the algorithm derived still sup-optimal and its computational complexity is considerably high. In [START_REF] Wang | Delay-aware two-hop cooperative relay communications via approximate mdp and stochastic learning[END_REF][START_REF] Bettesh | Optimal power and rate control for minimal average delay: The single-user case[END_REF], the authors try to minimize the average delay in users' queues using Markov Decision Process (MDP) and stochastic learning tools. It has been also adopted in [START_REF] Cui | Distributive stochastic learning for delay-optimal ofdma power and subband allocation[END_REF] to deal with the problem of power allocation in an OFDM (Orthogonal Frequency Division Multiplexing) system with the goal being to minimize the average delay of the users' packets in the queues. However, the developed solution requires high memory and computational complexity.

Whittle index for minimizing delay

Whittle index-based policies have been used/developed in wireless networks in the framework of scheduling problems due to its low complexity and its good performance in most cases [START_REF] Liu | Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access[END_REF][START_REF] Ansell | Whittle index policy for a multi-class queueing system with convex holding costs[END_REF][START_REF] Aalto | Whittle index approach to size-aware scheduling with time-varying channels[END_REF][START_REF] Akbarzadeh | Restless bandits with controlled restarts: Indexability and computation of whittle index[END_REF][START_REF] Avrachenkov | Whittle index policy for crawling ephemeral content[END_REF][START_REF] Borkar | Whittle index for partially observed binary markov decision processes[END_REF][START_REF] Iannello | Optimality of myopic scheduling and whittle indexability for energy harvesting sensors[END_REF][START_REF] Larrañaga | Asymptotically optimal pilot allocation over markovian fading channels[END_REF][START_REF] Meshram | On the whittle index for restless multiarmed hidden markov bandits[END_REF][START_REF] Ouyang | Downlink scheduling over markovian fading channels[END_REF][START_REF] Sombabu | Whittle index for aoi-aware scheduling[END_REF][START_REF] Tripathi | A whittle index approach to minimizing functions of age of information[END_REF][START_REF] Wang | Whittle index policy for dynamic multichannel allocation in remote state estimation[END_REF][START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF]. In [START_REF] Ansell | Whittle index policy for a multi-class queueing system with convex holding costs[END_REF], a derivation of the Whittle index values for a simple multiclass M/M/1 model has been considered (where only one user can be served). However, the optimality of the obtained Whittle index policy has not been proved. The authors in [START_REF] Weber | On an index policy for restless bandits[END_REF] have considered the problem of project/job scheduling in which an effort is allocated to a fixed number of projects. The performance of a Whittle index-based policy was analyzed under a continuous time model. Whittle index policy has been derived for a birth-and-death multi-class multi servers queue in [START_REF] Larrañaga | Dynamic control of birth-and-death restless bandits: Application to resource-allocation problems[END_REF]. In [START_REF] Van Mieghem | Dynamic scheduling with convex delay costs: The generalized c| mu rule[END_REF], an optimal index policy called Generalizedcµ-rule (Gcµ) is developed in the context of heavy-traffic regime with convex delay cost. Furthermore, in contrast to cµ rule policy, [START_REF] Mandelbaum | Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cµ-rule[END_REF] establishes the optimality of Generalizedcµ-rule (Gcµ) even with multiple servers.

Scheduling Problem: Age Minimization

Among the earliest works that study the AoI minimization problem is that of Kaul, Gruteser, and Yates [4]. They consider a system model where a source is transmitting packets containing status updates to a destination. The channel is represented by a simple queue. In that work, the authors show that neither sending updates as fast as possible nor as low as possible can achieve timeliness goal. Indeed, the optimal solution is not trivial, as one can predict.

In [START_REF] Kaul | Age of information: Updates with priority[END_REF], the authors investigate the impact of the waiting room on AoI in a priority-based queuing system where multiple information streams share a common service facility with null or one waiting room. These streams have different priorities. The authors found the optimal arrival rate of status updates that minimizes the average age of each stream.

In scheduling problems, a wide range of works (for instance, [START_REF] Bedewy | The age of information in multihop networks[END_REF][START_REF] Kadota | Scheduling policies for minimizing age of information in broadcast wireless networks[END_REF][START_REF] Hsu | Age of information: Design and analysis of optimal scheduling algorithms[END_REF][START_REF]Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals[END_REF][START_REF] Sun | Age-optimal updates of multiple information flows[END_REF][START_REF] Bacinoglu | Scheduling status updates to minimize age of information with an energy harvesting sensor[END_REF][START_REF] Ceran | Average age of information with hybrid arq under a resource constraint[END_REF]) have studied these types of problems in order to minimize the age of information in various contexts. To that extent, we cite in the following some interesting works related to our field of studies.

Energy-aware scheduling [START_REF] Bacinoglu | Scheduling status updates to minimize age of information with an energy harvesting sensor[END_REF] studies a real-time sensing scenario under energy constraints and battery limitations.

The authors find an age-optimal threshold policy in function of the energy and the estimated current age states. Another interesting work in this field is [START_REF] Ceran | Average age of information with hybrid arq under a resource constraint[END_REF], where the authors study a scheduling problem for minimizing AoI considering that the source's update rate cannot exceed a certain predefined limit due to energy limitations. They provide the analytical derivation for the optimal solution when the channel statistics are known.

Stochastic learning algorithm

Many algorithms have been developed to find the optimal scheduling with respect to AoI based on stochastic learning tools. For instance, [START_REF]Reinforcement learning to minimize age of information with an energy harvesting sensor with harq and sensing cost[END_REF] proposes an average-cost reinforcement learning algorithm that learns the system parameters, namely channel and energy harvesting statistics, in order to get the optimal policy. In [START_REF] Beytur | Age minimization of multiple flows using reinforcement learning[END_REF], the authors consider the problem of AoI-optimal scheduling of multiple flows served by a single server. They employ Policy Gradients and Deep Q-Learning methods to achieve scheduling decisions that are resilient to network conditions and packet arrival processes.

On the other hands, a Markov Decision Process (MDP) approximation approach was adopted to propose both off-line and on-line scheduling algorithms in the asymmetric case in [START_REF] Hsu | Age of information: Design and analysis of optimal scheduling algorithms[END_REF], which turns out to be asymptotically optimal.

Whittle index policy for minimizing AoI

As it was indicated in 2.4.1, Whittle index policy has been widely applied when dealing with scheduling problem due to its advantages comparing with other scheduling policies, namely its low complexity and its well performance. Precisely, Whittle index policy is used in Restless Bandit Problem framework which will be detailed in Chapter 3. One of the most known instance of this problem is: How to allocate M resources to N users (M less than N ) in a such a way to minimize a given metric that evolves stochastically. [START_REF] Kadota | Scheduling policies for minimizing age of information in broadcast wireless networks[END_REF] tackles this aforementioned problem. Given that RBP is a special case of MDP (Markov decision problem) whose solution is known to be unreachable for many cases, [START_REF] Kadota | Scheduling policies for minimizing age of information in broadcast wireless networks[END_REF] have proved that a greedy algorithm is optimal when the users have identical channel statistics, while for the asymmetric case, they propose as solution Whittle's index policy which remains sub-optimal. In [START_REF]Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals[END_REF], the authors aim to minimize the total average AoI, under random arrivals by adopting a Whittle's index-based policy. Accordingly, they derive a simple closed form of the Whittle index policy. They give in addition some numerical results to showcase the performance of the proposed policy. Meanwhile, they don't prove its optimality. To that extent, we adopt in our work, this well-performing policy, and we further establish its otpimality in the asymptotic regime when the number of users scales.

Chapter 2. Introduction

Contributions and overview of the thesis

The remainder of this thesis is structured in tree chapters. Specifically:

• Chapter 3: In this chapter, we explain in depth the methodology applied to get the Whittle index policy (WIP). Specifically, we explain in details the steps to get the Whittle indices and we lay out the method used to show the optimality of WIP in the the many-users regime.

• Chapter 4: Unlike [START_REF] Ansell | Whittle index policy for a multi-class queueing system with convex holding costs[END_REF][START_REF] Weber | On an index policy for restless bandits[END_REF][START_REF] Larrañaga | Dynamic control of birth-and-death restless bandits: Application to resource-allocation problems[END_REF][START_REF] Van Mieghem | Dynamic scheduling with convex delay costs: The generalized c| mu rule[END_REF][START_REF] Mandelbaum | Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cµ-rule[END_REF], we tackle in this Chapter a scheduling problem considering a discrete time model. Specifically, we study the delay minimization problem in discrete time queuing system model. To that extent, we investigate a resource allocation problem in which a base station allocates M channels to N users' queues at each time slot depending on the scheduling policy considered. The queues evolves according to a Markov process. Furthermore, the users or queues1 are divided into classes depending on the system parameters namely, packet's arrival rate and packet's transmission rate which differ from one class to another one. Our goal is to find the adequate policy that minimize the long-run total expected average queue length of all users. This aforementioned problem can be cast as Restless Bandit Problem whose solution is known to be unreachable. For that purpose, we apply the low-complex and the well-performing policy, Whittle index policy (WIP) to our specific system model. In a nutshell, we can summarize our contributions into two following points:

-We derive the Whittle index policy for two scenarios: large buffer size (infinite size), and tight buffer size (less than the transmission rate).

-We establish the local and the global optimality of WIP in the asymptotic regime when the number of users is very large.

• Chapter 5: In this chapter, we apply Whittle index policy in the context of the age of information (AoI). We consider a scheduling problem with unreliable channels. We consider several classes of users such that each class is characterized by its own channel statistics. Accordingly, our aim is to minimize the long-run total expected average age of all users. Our main contribution in this work, is the proof of asymptotic optimality for both scenarios which are:

-AoI evolves in finite state's space.

-AoI evolves in infinite state's space

For the first scenario, we provide the rigorous analysis in order to establish the asymptotic local optimality based on some mathematical techniques. Whilst for the second scenario, we adopt an innovative and original approach to make out the asymptotic global optimality of Whittle index policy. This approach relies essentially on Cauchy criterion: instead of proving that a given function f (•) converges to a fixed point, we show that the terms of f (•) are getting closer when t grows. This method will be detailed in Chapter 5. Finally, we provide some numerical results that bear out our technical analysis.

Chapter 3. Methodology Chapter 3

Methodology

In this thesis, we tackle users and channels scheduling problems related to wireless communication, and we aim to develop a policy called Whittle Index Policy (WIP) that turns out to be optimal under some conditions regarding our metrics of interest, which are Queuing Delay and AoI. Our problem consists of how to allocate channels to a given subset of users in such a way to optimize the considered metric. Specifically, from a mathematical point of view, we consider a discrete-time model and an MDP (Markov decision problem) since the system evolves stochastically depending on the system parameters and the policy implemented. Therefore, our purpose will be to minimize the metric of interest that can be viewed as a stochastic objective function, precisely, penalty or cost function that takes discrete values, by adopting the suitable allocation policy. We develop a low complex heuristic policy called Whittle Index Policy, which is optimal when the number of users is large. To that extent, in this chapter, we introduce first the Restless Bandit Problem, then we show that our problem in question is a Restless Bandit Problem (RPB). After that, we give in details the steps to get Whittle's index policy for this kind of problems. Finally, we explain the procedure used to establish the optimality of Whittle's index policy.

Restless Bandit Problem

The Multi-armed problem (MAP) models an agent that attempts to acquire knowledge and share or allocates the available resources among the competing bandits in way to optimize certain value function. The mathematical model can be described as follows: There are N bandits and only one bandit can be activated at each time slot. A bandit k is characterized by: the state space S k , an action a k that equals to 0 or 1; 0 and 1 refer to the passive and the active action respectively, the transition probability p k (s, s ) where (s, s ) belongs to S k × S k , and the cost function C k (s, a) that depends on the state of bandit k which is s as well as the action taken a. Therefore, the role of a given policy φ is to prescribe the active action to one of the bandits while prescribing the passive action to others. We denote by Φ, the broad class of scheduling policies that make a scheduling decision based on the history of observed bandit states and scheduling actions. We let s φ k (t) be the state of bandit k under policy φ at time slot t. We denote further by a φ k (t) the action taken with respect to bandit k under policy φ. Given an initial state s(0) = (s 1 (0), . . . , s K (0)), the optimal policy φ aims to minimize the long-run expected average cost incurred by the system:

min φ∈Φ lim sup T →∞ 1 T E T -1 t=0 N k=1 C k (s φ k (t), a φ k (t)) | s(0) (3.1)
Under the following constraint that must be satisfied per each time slot:

N k=1 a φ k (t) ≤ 1, for all t (3.2)
MAP has been originally considered by scientists in the second world war, and it has getting more attention after the breakthrough result of Gittin. This later found an optimal policy called Gittin index policy for the MAP problem [START_REF] Gittins | Multi-armed bandit allocation indices[END_REF]. However, the shortcoming of the MAP is that M=1 and the bandits for which the action prescribed is the passive action, stay idle, which is not often the case in practice. Thus, Whittle introduces RBP where M can be higher than one, and all bandits evolve whether the action taken is active or not. That is, the constraint on the available resources per each time slot has a more general expression:

N k=1 a φ k (t) ≤ M, for all t (3.3)

System model of interest

In this thesis, as we have already explained in the Introduction, we are interested in minimizing the average delay and the average age. For both cases, we consider M channels that must be allocated to N users in such a way to minimize the long-run expected average cost. The action of assigning channel to a given user is the active action. Regarding the first metric, the cost function will be the queue state that evolves stochastically depending on the system's parameters and the action taken. For the second metric AoI, the cost function will be the age of information that also evolves stochastically depending on the system's parameters and the chosen action. After all, we end up with RBP for both metrics.

Lagrangian approach and Whittle index policy

RBPs are PSPACE-Hard (see Papadimitriou et al. [START_REF] Papadimitriou | The complexity of optimal queuing network control[END_REF]), and hence their optimal solution is out of reach. One should, therefore, proposes sub-optimal policies when dealing with such problems. In this thesis, we approach the considered RBP problem using the Lagrangian relaxation technique, which consists of relaxing the constraint on the available resources. Instead of having the constraint on the number of available channels satisfied in every time slot, we consider that it has to be met on average. This relaxation allows us to decompose the large relaxed optimization problem into much simpler one-dimensional problems. Based on the optimal solution of the one-dimensional relaxed problems, we develop a heuristic for the original (i.e., non-relaxed) optimization problem. This heuristic is known as the Whittle's index policy (WIP). In this section, we will explain the Lagrangian relaxation method. Then we expose some techniques used to solve RBP based Chapter 3. Methodology on the Lagrangian relaxation approach, and we see why these techniques are not feasible in practice. After that, we lay out the steps that allow us to get the Whittle's index Policy.

Relaxed Problem and Dual Problem

The Lagrangian relaxation consists of relaxing the constraint of the available resources. Namely, we consider that the constraint in Equation (3.3), has to be satisfied on average and not in every decision epoch, that is,

lim sup T →∞ 1 T E N k=1 a φ k (t) ≤ αN. (3.4)
where α is the proportion of users that are scheduled (αN = M ). Note that, contrary to the strict constraint in Equation (3.3), the relaxed constraint allows the activation of more than α fraction of users in each time slot. If we note W the Lagrangian multiplier for the constrained problem, then the Lagrange function equals to:

f (W, φ) = lim sup T →∞ 1 T E T -1 t=0 N k=1 (C k (s φ k (t), a φ k (t)) + W a φ k (t)) | s(0) -W αN,
where W can be seen as a subsidy for not transmitting. Therefore, the dual problem for a given W is min φ∈Φ f (W, φ).

(3.5)

Problem Decomposition

In this section, we show that the relaxed problem can be decomposed into N onedimensional subproblems. To do that, we first get rid of the constants that do not depend on φ and reformulate the problem as follows, min φ∈Φ lim sup

T →∞ 1 T E T -1 t=0 N k=1 (C k (s φ k (t), a φ k (t)) + W a φ k (t)) | s(0) . (3.6)
One can see that the solution of this problem is the solution of the well known Bellman equation, see Ross [START_REF] Ross | Introduction to stochastic dynamic programming[END_REF], namely,

V (s) + θ = min a { N k=1 C k (s k , a k ) + s P r(s |s, a) V (s )}, (3.7)
for all s = (s 1 , . . . , s N ), and a = (a 1 , . . . , a N ), with a k ∈ {0, 1} the action taken with respect to bandit k. In Equation (3.7), V (•) represents the Value Function, θ is the optimal average cost and

C k (s k , a k ) = C k (s k , a k ) + W a k is the holding cost.
The optimal decision for each state s can be obtained by minimizing the right hand side of Equation (3.7).

We now show that the problem can be decomposed into N independent subproblems by decomposing V (•) into Value Functions for bandit k, i.e., V k (•). In other words, the Chapter 3. Methodology optimal decision a to Problem (3.7) is a vector composed of elements a k , where each a k is nothing but the optimal decision that solves the one-dimensional Bellman equation:

V k (s k ) + θ k = min a k {C k (s k , a k ) + s k P r(s k |s k , a k )V k (s k )}. (3.8)
This is proven in the next proposition.

Proposition 3.1. Let V k (•) be the optimal value function that solves Equation (3.8), and let V (•) be the optimal value function that solves Equation (3.7), then:

V (•) = N k=1 V k (•) Proof. See appendix A.1
In that sense, resolving (3.8) is equivalent to find an optimal solution of the following problem:

min φ∈Φ lim sup T →∞ 1 T E T -1 t=0 (C k (s φ k (t), a φ k (t)) + W a φ k (t)) | s k (0) . (3.9)
Since we deal with the one-dimensional problem, we drop the bandit's index for ease of notation until section 3.4. The solution of Bellman equation (3.8) V (•), can be obtained by the well known Value iteration algorithm, which consists in updating V t (•) using the following equation:

V t+1 (s) = min a {C (s, a) + s P r(s |s, a)V t (s )} -θ (3.10)
We consider that the initial value function V 0 equals to 0 for any s, (i.e. for all s V 0 (s) = 0).

In fact, after many iteration V t (•) will converge to the unique fixed point of the equation (3.8) called V (•) under some conditions (see Puterman [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF]). To that extent, the Value iteration algorithm stops when the number of iteration is large enough (when V t (•) is nearly constant). We consider that t inf is the stopping time. As a result, the optimal solution φ * using Value iteration algorithm, verifies for all state s:

φ * (s) = arg min a {C (s, a) + s P r(s |s, a)V t inf (s )} (3.11)
Dynamic programming solutions and particularly, Value iteration algorithm described above, have been adopted by many existing works that deal with Markov Decision Problem. However these techniques suffer from the curse of dimensionality, which leads to complex resource allocation strategies. In most cases, the developed solutions based on Dynamic Programming require high memory and computational complexity which make them unfeasible. For this reason, we will be limited to give some structural properties of the value function V t (•) for any t to conclude for V (•). Based on this, we then establish the structure of the optimal policy of (3.9). Indeed, in our case, after studying the structure of V (•), we end up with an optimal solution of type threshold-based policy in function of the state s: Definition 3.1. An increasing threshold policy is a policy φ ∈ Φ for which there exists n ∈ S k such that when the bandit k is in state s ≤ n, the prescribed action is a = 0, and when the bandit is in state s > n, the prescribed action is a = 1.

In light of that, we derive the indices of Whittle for each state s, then we express our heuristic policy Whittle Index Policy (WIP). To that end, we provide and explain the steps followed to get the Whittle indices in the next section under the assumption that the optimal solution of Problem (3.8) is threshold-based increasing policy.

Whittle's Index

In this section, we provide the derivation of the Whittle indices, which are values that depend on the state n and system parameters. Although this derivation is made using the relaxed problem, it allows us to develop a heuristic for the original problem. It is worth mentioning that the Whittle's index at a given state, say n, represents the Lagrange multiplier for which the optimal decision of the one-dimensional dual relaxed problem at this state is indifferent (passive and active decision are both optimal). However, the Whittle index is well defined only if the property of indexability is satisfied. This property requires establishing that as the Lagrange multiplier (or equivalently the subsidy for passivity W ) increases, the collection of states in which the optimal action is passive increases. In this section, we consider a given bandit k, and we present two approaches that can be applied to get the Whittle indices. Now, we formalize the indexability and the Whittle's index in the following definitions.

Definition 3.2. Considering problem (3.9) for a given W , we define D(W ) as the set of states in which the optimal action (with respect to the optimal solution of Problem (3.9)) is the passive one. In other words, n ∈ D(W ) if and only if the optimal action at state n is the passive one.

D(W

) is well defined as the optimal solution of Problem (3.9) is a stationary policy, more precisely, a threshold-based policy by assumption.

Definition 3.3. A class is indexable if the set of states in which the passive action is the optimal action increases in

W , that is, W < W ⇒ D(W ) ⊆ D(W ).
When the class is indexable, the Whittle's index in state n is defined as:

W (n) = min{W |n ∈ D(W )} (3.12)
In the following, we provide two approaches that can be used to compute the Whittle index values.

Discounted Cost Approach

This approach consists in introducing a new expected discounted cost function and deriving the Whittle's index values with respect to the discount parameter β < 1. We then deduce the Whittle's indices for the original problem (i.e., with the total average cost Chapter 3. Methodology minimization) by taking the limit β → 1. We start by formulating the original problem with the expected discounted cost:

min φ∈Φ E +∞ t=0 N k=1 β t C k (s k (t), a k (t)) | s(0), φ , s.t. N k=1 a k (t) ≤ αN, ∀t. (3.13)
Following the same steps as in 3.3.1, we relax the problem and give the dual relaxed problem for a given W :

min φ∈Φ +∞ t=0 E[ N k=1 β t (C k (s k (t), a k (t)) + W a k (t)) | φ, s(0)]. (3.14)
Then, we decompose it into N one-dimensional problems since the Bellman equation that resolves the dual problem is decomposable. The Bellman equation for an one-dimensional problem is [START_REF] Ross | Introduction to stochastic dynamic programming[END_REF].

V β (s) = min a {C (s, a) + β s P r(s |s, a)V β (s )}. (3.15)
In fact, V β (s) is no more than the discounted cost when the initial state is s,

V β (s) = +∞ t=0 E[β t (C (s(t), a(t))) | φ, s(0) = s].
Unlike the steady-state approach, we can only work with the Bellman equation to derive the Whittle index thanks to the parameter β. In fact, for most cases, especially for our models, the optimal solution of the Bellman equation (3.15), is of type threshold based policy. On the other hand, under a given threshold policy n, we are able to give the explicit expression of V β (s) in function of the system parameters as well as the lagrangian parameter W for all states s. According to the definition of Whittle index, we need to check first that the bandit is indexable. This can be verified by showing that the optimal threshold of the problem (3.8) is increasing with subsidy W . Given that, the Whittle index of state s denoted by W β (s) is the langrangian parameter W that satisfies

V 0 β (s) = V 1 β (s), where V 0 β (s) = C (s, 0)+β s P r(s |s, 0)V β (s ) and V 1 β (s) = C (s, 1) + β s P r(s |s, 1)V β (s ).
Hence, resolving this later equation allows us to find W β (s) in function of s, β and the system parameters. Then under certain conditions on V β (•) (see [START_REF] Dutta | What do discounted optima converge to?: A theory of discount rate asymptotics in economic models[END_REF] and [START_REF] Ross | Introduction to stochastic dynamic programming[END_REF]), the Whittle index of state s under average cost criterion is

W (s) = lim β→1 W β (s).

Steady State Approach

Let us define n as the threshold of the bandit k, i.e., if s ≤ n, then the bandit will not be scheduled, and else, the bandit will be selected. To that extent, the Steady-State Approach consists in the first place of deriving the stationary distribution of the Markov process s(t) that refers to the state of the bandit k at time slot t under the threshold increasing policy n. Then, we provide a closed-form expression of the Whittle index values based on the steady-state form of the Problem (3.9). Denoting by p n (i, j) the transition probability from state i to j, by u n the stationary distribution under the threshold policy n, and by S the state space of bandit k, then finding u n requires to resolve the full balance equation, i.e.:

u

n (i) = j∈S p n (j, i)u n (j) (3.16)
With that in mind, we reformulate the dual of the relaxed problem using the stationary distribution. Since the solution of the one-dimensional dual of the relaxed problem (3.9) (given a constant W ) is a threshold-based policy, we can reformulate the problem as follows:

min n∈S E[C n (s, a) + W a n ] = min n∈S {C n (s, a) -W n s=0 u n (s) + W } (3.17)
with n and u n being the threshold and the stationary distribution under the threshold policy n respectively, C n (s, a) being the mean cost under threshold policy n

The new formulation of the problem turns out to be useful to derive the Whittle indices since, for any W , we can find the minimizer of the expression in equation (3.17).

In the literature, several works have been conducted to find Whittle index values. For example, an interesting iterative algorithm has been provided in [START_REF] Larrañaga | Dynamic control of stochastic and fluid resource-sharing systems[END_REF]. In the following, we provide a more general algorithm that can be applied in both cases that we have studied in this thesis (AoI and Queuing Delay) up to some modifications. In the next chapters, further analysis will be provided to derive a closed-form expression of the Whittle index values based on this algorithm. To that extent, we will first present this algorithm and then prove that it allows the Whittle's index values' computation.

Algorithm 1 Whittle Index Computation

1: Init. Let j be initialized to 0 2: Find W 0 = inf n∈N C n (s,a)-C -1 (s,a) n s=0 u n (s)
3: Define n 0 as the largest minimizer of the above expression 4: Let W (k) = W 0 for all k ≤ n 0 5: while n j = max{S} do 6:

j = j + 1 7: Define M j the set {n : n s=0 u n (s) = n j-1 s=0 u n j-1 (s)} ∪ {0, • • • , n j-1 } 8: Find W j = inf n∈N\M j C n (s,a)-C n j-1 (s,a) n s=0 u n (s)- n j-1 s=0 u n j-1 (s) 9:
Define n j as the largest minimizer of the above expression 10:

Let W (k) = W j for all n j-1 < k ≤ n j 11:
Output The Whittle index of state k which is given by W (k) Proposition 3.2. Assuming that the optimal solution is a threshold policy, and that b n = n s=0 u n (s) is increasing, then the class is indexable. Moreover, if a n = C n (s, a) is increasing with n and for all i and j such that i < j i s=0 u i (s) = j s=0 u j (s) =⇒ C i (s, a) < C j (s, a), then the Whittle's index values are computed by applying Algorithm 1.

Proof. For the proof, see appendix A.2.

Chapter 3. Methodology

In chapters 4 and 5, we prove that in our context, the two conditions of Proposition 3.2 are satisfied. Thereby, the algorithm is applicable.

Whittle's Index Policy

Considering the original Problem (3.8), Whittle's Index Policy, denoted by WIP, will consist simply of allocating the channels to the M bandits that have the highest Whittle indices at time t computed using the algorithm 1. As one can remark, Whittle index policy is less complex than the Value iteration algorithm.

Asymptotic Optimality of Whittle Index Policy

The Whittle index policy's performance has been investigated by many works in literature ( [START_REF] Larrañaga | Asymptotically optimal pilot allocation over markovian fading channels[END_REF], [START_REF] Ouyang | Downlink scheduling over markovian fading channels[END_REF], [START_REF] Liu | Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access[END_REF], [START_REF] Liu | Indexability and whittle index for restless bandit problems involving reset processes[END_REF], [START_REF] Tripathi | A whittle index approach to minimizing functions of age of information[END_REF], [START_REF] Wang | Whittle index policy for dynamic multichannel allocation in remote state estimation[END_REF], [START_REF] Iannello | Optimality of myopic scheduling and whittle indexability for energy harvesting sensors[END_REF]). This policy turns out to be effectively asymptotically optimal, i.e., it is optimal when the number of bandits and the number of available resources (the number of scheduled bandits per time slot t, M ) scale. In this thesis, we discuss two types of optimality: local and global asymptotic optimality. The Whittle index policy's local optimality means that WIP is asymptotically optimal if the initial state s(0) belongs to a fixed and restricted set of states. It is often feasible to establish it when the number of bandits is finite. While the global optimality doesn't require any condition of the initial state, it is often hard to be established and needs to take into account some assumptions. In both cases, we show that the long-run average cost under Whittle index policy converges to the optimal cost of the Relaxed problem (the problem (3.1) under the constraint (3.4)) denoted by C RP,N . The reason behind that is that C RP,N is a lower bound of all expected average cost obtained by any policy that resolves the original Problem (the problem (3.1) under the constraint (3.3)). Hence, it is sufficient to show that 1

T E T -1 t=0 N k=1 C k (s φ k (t), a φ k (t))
| s(0) converges to C RP,N under Whittle Index policy when the number of bandits N and T grows. In asymmetric cases (the bandits have not the same characteristics), we put together the bandits with the same characteristics in one class. As a consequence, we end up with many classes such that each class contains identical bandits. To that extent, we define Z k,N i the proportion of bandits at state i in class k over all the system's bandits. In other words, it denotes the number of bandits at state i in class k over the number of all bandits, which is N . If the number of states is finite, then we define the vector

Z N = (Z 1,N 1 , • • • , Z K,N max S ).
In this section, we present briefly the steps followed to prove the asymptotic local and global optimality of Whittle Index Policy when the number of bandit's states is finite.

Local Optimality

The local optimality is mainly based on the fluid approximation technique that consists of analyzing the evolution of the expectation of Z N (t) under Whittle's Index policy. For that, we define the vector z(t) as follows:

z(t + 1) -z(t)| z(t)=z = E Z N (t + 1) -Z N (t)|Z N (t) = z (3.18)
In the followings we give the proof outline:

• Showing that z(t) converges to the optimal proportion vector of the Relaxed Problem z * , when z(0) is within a neighborhood of z * .

• We then connect the fluid approximation model z(t) to the discrete-time stochastic system state Z N (t) by using a discrete-time extension of Kurtz's Theorem. Essentially, it states that, over any finite time duration [0, T ], the actual system evolution Z N (t) can be made arbitrarily close to the above fluid approximation z(t) by increasing the number of bandits N

• Provided that the initial state is within a neighborhood of z * , we conclude for the convergence of the long-run expected average cost under Whittle index policy to C RP,N when N is very large.

Global Optimality

We give the proof outline:

• Establishing the existence of a steady-state distribution associated with Z N (t) by demonstrating that Z N (t) under Whittle's index policy evolves in one recurrent class in finite state space.

• Under the assumption that the expected time of reaching a neighborhood of z * doesn't scale with N , we establish the asymptotic global optimality by adopting the steady-state expression of the long-run expected average cost under Whittle's index policy.

When the number of bandits is infinite, as we have mentioned in Section 2.5, we adopt a new method to prove the global optimality. This method is well explained in Chapter 5. In this chapter, we apply the Whittle index policy in a discrete queuing system model. Precisely, we adopt the WIP as solution to the scheduling problem that consists of selecting M queues among N queues such that the average queue length of all users is minimized.

In the first section, we present our system model. As for the next section, we analyze two scenarios in parallel: The first one is about the case where the buffer size is very small. That is, for each user, the departure rate is greater than the buffer size. While in the second one, the queue length is considered infinite. After that, we express the scheduling problem of interest, then we give the steps of the Lagrangian Relaxation method for our particular problem. Then, we prove that the optimal solution of the Bellman equation that corresponds to the one-dimensional dual relaxed problem, is effectively a threshold policy. Armed with that, and adopting the Steady State approach when the buffer size is finite, we derive Whittle's index policy in closed-form expression in function of the system parameters namely the Buffer length and the departure rate. Whereas, for the infinite buffer size's case, the approach used for the first case when the buffer size is tight fails to give us the expression of Whittle index for all states. To circumvent this difficulty, we handle the problem by applying a new approach named Discounted Cost approach in order to get an approximated Whittle index policy for the original problem. Similarly to the first case, we use the Lagrangian Relaxation technique and show that the optimal solution of the one-dimensional discounted Bellman equation is a threshold-based policy. Then, we obtain the Whittle index expressions by manipulating the Value function V β under the discounted parameter β. We conclude for the original problem by tending β to one. Next, we show that Whittle index policy is asymptotically locally optimal using the fluid approximation technique, and globally optimal under a recurrence assumption that is verified numerically for our problem. Finally, we give some numerical results that showcase the remarkable good performance of our proposed policy and that corroborate our theoretical findings.

System Model

We consider a time-slotted system with one central scheduler, N users/queues and M uncorrelated channels (or servers) with (N > M ). The terms "server" and "channel" will be used interchangeably throughout this chapter, as well as the terms "user" and "queue".

A channel can be allocated to at most one user, hence only M users will be able to transmit (i.e. send packets) at time slot t. We consider K different classes of users and we assume that each user in class-k, if scheduled, transmits at most R k packets per time slot. We will refer to R k as the maximum transmission rate for every user in class k and we assume that min k {R k } ≥ 2. We denote by γ k the proportion of class-k users in the system. We further denote by A k i (t) ∈ {0, . . . , R k -1} the number of packets that arrive to queue i in class k at time slot t which is independent and identically distributed (i.i.d.) over time. We also let q k,φ i (t) denote the number of packets in queue i in class k. Furthermore, s k,φ i (q φ (t)) will denote the transmission action under a decision policy φ for user i in class k and q φ (t) the vector of all queue lengths (q 1,φ 1 (t), . . . , q 1,φ N γ 1 (t), . . . , q K,φ 1 (t), . . . , q K,φ N γ K (t)). For the sake of clarity, we define s k,φ i (t) := s k,φ i (q φ (t)). If policy φ prescribes to schedule user i in class k at time t, then s k,φ i (t) = 1, and s k,φ i (t) = 0 otherwise. We denote by L the buffer capacity, which is considered to be the same for all queues and can be infinite. The general system model is presented in Figure 4.1. Based on our system model, the number of packets in queue i of class k evolves as follows:

q k,φ i (t + 1) = min{(q k,φ i (t) -R k s k,φ i (t)) + + A k i (t), L}, (4.1)
where (x) + = max{x, 0}.

The objective of the present work is to find a scheduling policy φ that minimizes the average queue length of the users which results, according to Little's Law [2] in the minimization of the average delay.

Problem formulation

The cost incurred by user i in class k, at time t is equal to a k q k,φ i (t) for all i ∈ {1, . . . , γ k N } where a k is a predefined weight. One can see that the model described in Section 4.1 belongs to the family of Restless Bandit Problems (RBP). We consider the broad class Φ of scheduling policies in which a scheduling decision depends on the history of observed queue states and scheduling actions. Our user and channel allocation problem therefore consists of identifying the policy φ ∈ Φ that minimizes the infinite horizon expected average queues, subject to the constraint on the number of users selected at each time slot. Given the initial state q(0) = (q 1 1 (0), . . . , q 1 N γ 1 (0), ..., q K 1 (0), . . . , q K N γ K (0)), the problem can be formulated as follows:

min φ∈Φ lim sup T →∞ 1 T E T -1 t=0 K k=1 γ k N i=1 a k q k,φ i (t) | q(0) , s.t. K k=1 γ k N i=1 s k,φ i (t) ≤ αN, for all t, (4.2)
where α = M/N is the fraction of users that can be scheduled.

Relaxed Problem and Threshold-based Policy

As it has been discussed in Section 3.3, RBPs are PSPACE-Hard and therefore one should develop well performing sub-optimal policies to solve these problems. Accordingly, we have proposed as solution Whittle's index policy for this type of problem. Hence, to derive a closed-form expression of Whittle's index for each state, we apply the methodology explained in Chapter 3. To that extent, in the following, we give briefly the main results for this particular system model.

Relaxed Problem and Dual Problem

The Lagrangian relaxation consists of relaxing the constraint on the available resources. Namely, we consider that the constraint in Equation (4.2), has to be satisfied on average and not in every decision epoch, that is,

lim sup T →∞ 1 T E K k=1 γ k N i=1 s k,φ i (t) ≤ αN. (4.3)
If we note W the Lagrangian multiplier for the constrained problem, then the Lagrange function equals to:

f (W, φ) = lim sup T →∞ 1 T E T -1 t=0 K k=1 γ k N i=1 (a k q k,φ i (t) + W s k,φ i (t)) | q(0) -W αN, (4.4)
where W can be seen as a subsidy for not transmitting. Therefore, the dual problem for a given W is min φ∈Φ f (W, φ). (4.5)

Problem Decomposition and Threshold-based Policy

After getting rid of the constants that do not depend on φ, the problem (4.5) can be reformulated as follows:

min φ∈Φ lim sup T →∞ 1 T E T -1 t=0 K k=1 γ k N i=1 (a k q k,φ i (t) + W s k,φ i (t)) | q(0) . (4.6)
Chapter 4. Whittle's index policy for minimizing the Delay in Queuing systems

The Bellman equation that corresponds to this problem:

V (q) + θ = min s { K k=1 γ k N i=1 C k (q k i , s k i ) + q P r(q |q, s)V (q )}, (4.7)
for all q = (q 1 1 , . . . , q 1 γ 1 N , . . . , q K 1 , . . . , q K γ k N ), with q k i ∈ {1, . . . , L} being the queue length of class-k user i, and s = (s 1 1 , . . . , s 1 γ 1 N , . . . , s K 1 , . . . , s K γ k N ), with s k i ∈ {0, 1} being the action taken with respect to user i in class k. In equation (4.7), V (•) represents the Value Function, θ is the optimal average cost and

C k (q k i , s k i ) is the holding cost a k q k i + W s k i .
According to the Chapter 3, section 3.3.2, the problem can be decomposed into N independent sub-problems, one for each user i in class k. Accordingly, resolving the Bellman equation (4.7) is equivalent to resolve the following Bellman equation for each user i in class k.

V k i (q k i ) + θ k i = min s k i {C k (q k i , s k i ) + q k i P r(q k i |q k i , s k i )V k i (q k i )}. (4.8)
In the following, for both cases of buffer size L (L < R k for all k, or L is infinite), we show that the solution to each one-dimensional problem (for each user i) follows the structure of a threshold policy. For ease of notation, we drop the indices k and i and consider that V (•) is the value function for a given user. From this perspective, we let A be the random variable that indicates the number of arrival packets at each time slot.

As it has been indicated in Chapter 3 Section 3.3.2, the solution of the Bellman equation (4.8), V (•) can be obtained by the well known Value iteration algorithm:

V t+1 (q) = min s {C(q, s) + q P r(q |q, s)V t (q )} -θ (4.9)

Providing that lim

t→+∞ V t (•) = V (•)
, we give some structural properties of the value function V t (•) for any t and conclude for V (•). Then we give the structure of the optimal solution.

To that end, we distinguish between two cases of L:

Remark 4.1. It is worth to emphasize that when L is less than R, if the arrival packets plus the current queue length overflow on the buffer capacity, the user retain only the L packets and get rid of the surplus of the packets. Subsequently, from the state q, we can reach the state L when the number of arrival packets A can be either L-q or plus. Having said that, nor P r(L|q, 1) = P r(A = L -(q -R) + ) = P r(A = L) neither P r(L|q, 0) = P r(A = L -q), rather P r(L|q, 1) = R-1 A=L P r(A = L) and P r(L|q, 0) = R-1 A=L-q P r(A = L -q). While if L is infinite, since there is no overflow on the buffer capacity, for all queue sates q and q , we have that P r(q |q, 1) = P r(A = q -(q -R) + ) and P r(q |q, 0) = P r(A = q -q).

L < R

To tackle this case, we proceed with these following steps:

• We prove that V (•) is increasing with q • We establish that V 1 (q) -V 0 (q) is decreasing with q where V 0 (q) and V 1 (q) are the value functions when the action prescribed at state q is s = 0 and s = 1 respectively

• Finally, we show that the optimal solution is an increasing threshold policy

Regarding the first point, we show that V t (•) is increasing with q for all t by induction. Precisely, we establish that:

• V 0 (•) increases with q.

• If V t (•) is increasing with q, V t+1 (•) is also increasing with q.

Given that V 0 (•) = 0, then V 0 (•) is increasing with q. Considering V t (•) is increasing with q, then q P r(q |•, s)V t (q ) grows with q (see Puterman [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF]). We have by construction, C(•, s) increases with q. Since θ is just a constant, V t+1 (•) will be as well an increasing function with q.

As consequence, we show that V t (•) is increasing with q for all t. Leveraging the fact that V (•) is the limit of V t (•) when t grows, then V (•) is also increasing with q.

As for the second point, one can see that for any q, we have that q ≤ L < R. Then the next state before the arrival of the packets will be q = 0 if the action prescribed is the active action since all packet in the buffer will be transmitted. Consequently, the probability to transit to the state q from a given state q under the active action is the probability to have A = q if q < L, or L ≤ A ≤ R -1 if q = L (according to the remark 4.1). Hence P r(q |q, 1) doesn't depend on q. Likewise for L q =0 P r(q |q, 1)V (q ). We have that:

V 1 (q) -V 0 (q) = W + q P r(q |q, 1)V (q )q P r(q |q, 0)V (q )

Bearing in mind that V (•) is increasing with q, then again according to Puterman [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF],

q P r(q |q, 0)V (q ) is increasing with q. Leveraging the above result, L q =0 P r(q |q, 1)V (q ) is constant with respect to q. Consequently, V 1 (q) -V 0 (q) decreases with q. To prove the last point, we recall that the optimal action s(q) at state q according to Equation (4.7), is the one that minimizes V s (q). Explicitly, s(q) = argmin{V 0 (q), V 1 (q)}. Moreover, exploiting the fact that V 1 (q) -V 0 (q) is decreasing with q, then there exists q 0 (can be infinite) such that for all q ≤ q 0 , V 1 (q) ≥ V 0 (q) and for all q > q 0 , V 1 (q) ≤ V 0 (q). Consequently, we deduce that for all q ≤ q 0 , the optimal decision is to stay idle, and for all q > q 0 , the optimal decision is to transmit. Thereby, we prove that the optimal solution of Problem (4.5) is of type threshold increasing policy.

L = +∞

We consider the operator T O such that for each (q, s)

∈ N × {0, 1} (T O(V ))(q, s) = C(q, s) + q P r(q |q, s)V (q ) -θ (4.10)
We first provide some useful definitions and preliminary results before proving the desired results.

Chapter 4. Whittle's index policy for minimizing the Delay in Queuing systems Definition 4.1. We say that a function f is R-convex in X = N, if for any x and y in X such that x < y, we have:

f (y + R) -f (x + R) ≥ f (y) -f (x) (4.11) Lemma 4.1.
If for a given function f , there exists R such that for any integer x, f

(x + 1 + R) -f (x + R) ≥ f (x + 1) -f (x), then f is R-convex
Proof. Considering y and x in N, with y > x, we have:

f (y + R) -f (x + R) = y-1 k=x [f (k + 1 + R) -f (k + R)] (4.12) ≥ y-1 k=x [f (k + 1) -f (k)] (4.13) = f (y) -f (x) (4.14)
which concludes the proof.

Definition 4.2. Let g(q, s) be a real valued function defined on X × S, with S = {0, 1}, and X = N. We say that g is submodular if g(q + 1, 1) -g(q + 1, 0) ≤ g(q, 1) -g(q, 0) for all q on X. Proof. Let us consider that the input of T O(V )(•, s), i.e. a given V (•), is R-convex and increasing function with q. For the increase property of min s T O(V )(•, s), we have by definition that C(•, s) is increasing with q. We also have that V (•) is increasing with q, then q P r(q |•, s)V (q ) grows with q (see Puterman [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF]). Since θ is a constant, T O(V )(•, s) increases with q and therefore min s T O(V )(•, s) is increasing with q. For R-convexity, we should first prove the following lemma. Lemma 4.2. If V (•) is R-convex and increasing with q, C(q, s) and q P r(q |q, s)V (q ) are submodular functions.

Proof. The proof is given in appendix B. 1. This demonstrates that the function T O(V )(•, •) is submodular since it is the sum of two submodular functions. Let us now show that min

s T O(V )(•, s) is R-convex.
For that, we consider the function ∆T O(V )(q) = T O(V )(q, 1) -T O(V )(q, 0) which is decreasing with q since T O(V )(•, •) is submodular. Therefore, there exists r ∈ R ∪ {+∞} such that for q ≤ r, ∆T O(V )(q) ≥ 0 and for q ≥ r, ∆T O(V )(q) ≤ 0. In the remainder of the proof, we consider all possible cases of q and r.

If q + R + 1, q + R, q, q + 1 ≥ r:

min s T O(V )(q + 1 + R, s) -min s T O(V )(q + R, s) =T O(V )(q + 1 + R, 1) -T O(V )(q + R, 1) (4.15) =T O(V )(q + 1, 0) -T O(V )(q, 0) (4.16) ≥T O(V )(q + 1, 1) -T O(V )(q, 1) (4.17) =min s T O(V )(q + 1, s) -min s T O(V )(q, s) (4.18)
where the inequality is due to the sub-modularity of

T O(V )(•, •). If q ≤ r ≤ q + 1, q + R, q + 1 + R: min s T O(V )(q + 1 + R, s) -min s T O(V )(q + R, s) =T O(V )(q + 1 + R, 1) -T O(V )(q + R, 1) (4.19)
=T O(V )(q + 1, 0) -T O(V )(q, 0) (4.20)

≥T O(V )(q + 1, 1) -T O(V )(q, 0) (4.21)

=min s T O(V )(q + 1, s) -min s T O(V )(q, s) (4.22)
if q, q + 1 ≤ r ≤ q + R, q + R + 1:

min s T O(V )(q + 1 + R, s) -min s T O(V )(q + R, s) =T O(V )(q + 1 + R, 1) -T O(V )(q + R, 1) (4.23) =T O(V )(q + 1, 0) -T O(V )(q, 0) (4.24) =min s T O(V )(q + 1, s) -min s T O(V )(q, s) (4.25)
if q, q + 1, q + R ≤ r ≤ q + R + 1:

Chapter 4. Whittle's index policy for minimizing the Delay in Queuing systems

min s T O(V )(q + 1 + R, s) -min s T O(V )(q + R, s) =T O(V )(q + 1 + R, 1) -T O(V )(q + R, 0) (4.26) ≥T O(V )(q + 1 + R, 1) -T O(V )(q + R, 1) (4.27) =T O(V )(q + 1, 0) -T O(V )(q, 0) (4.28) =min s T O(V )(q + 1, s) -min s T O(V )(q, s) (4.29)
If q, q + 1, q + R; q + R + 1 ≤ r:

min s T O(V )(q + 1 + R, s) -min s T O(V )(q + R, s) =T O(V )(q + 1 + R, 0) -T O(V )(q + R, 0) (4.30) ≥T O(V )(q + 1 + R, 1) -T O(V )(q + R, 1) (4.31)
=T O(V

)(q + 1, 0) -T O(V )(q, 0) (4.32) =min s T O(V )(q + 1, s) -min s T O(V )(q, s) (4.33)
Using Lemma 4.1, min s T O(V )(•, s) is R-convex with q, i.e., we can conclude the Rconvexity conservation.

Remark 4.2. Theorem 1 means that if the value function V t is increasing and R-convex, then the value function V t+1 in equation (4.9), which is computed with the operator T O, is increasing and R-convex. Thus, as V 0 is increasing and R-convex, all V t are increasing and R-convex and therefore we can conclude that the value function V will be also R-convex and increasing with q.

Corollary 4.1. The optimal policy φ * of each one-dimensional relaxed subproblem is a threshold-based policy.

Proof. Since we have only two possible actions, a policy is of the form threshold policy if and only if it is monotone with q. Therefore, it is sufficient to prove that the optimal policy φ * is monotone with q. For that, we consider q 1 ≤ q 2 . According to Remark 4.2, V (.) is increasing and R-convex, then using Lemma 4.2, T O(V ) is submodular. Therefore, we have:

(T O(V ))(q 1 , 1) -(T O(V ))(q 1 , 0) ≥ (T O(V ))(q 2 , 1) -(T O(V ))(q 2 , 0) (4.34)
Chapter 4. Whittle's index policy for minimizing the Delay in Queuing systems

If φ * (q 2 ) = argmin s (T O(V ))(q 2 , s) = 0
Hence, (T O(V ))(q 2 , 1) -(T O(V ))(q 2 , 0) ≥ 0. Consequently, we get:

(T O(V ))(q 1 , 1) -(T O(V ))(q 1 , 0) ≥ 0 (4.35)
Which leads to: argmin

s (T O(V ))(q 1 , s) = 0 (4.36)
i.e. φ * (q 1 ) ≤ φ * (q 2 ) (4.37)

If φ * (q 2 ) = argmin s (T O(V ))(q 2 , s) = 1
, obviously we have that:

φ * (q 1 ) ≤ φ * (q 2 ) (4.38)
Therefore, we can conclude that the optimal solution is monotone and increasing with q, then it is a threshold-based policy.

Whittle's Index

For L < R, we apply the Steady State approach described in Chapter 3, Section 3.3.3 to find the Whittle's indices.

Steady State approach (L < R)

Let us define n as the threshold for users in a given class, i.e. if the queue state is q such that q ≤ n, then the user will not be scheduled, and else, the user will be selected for transmission. The objective of this section is to derive the stationary distribution of the users' states. We assume here that the packets arrive according to a discrete uniform distribution, that is, P(A(t) = x) = ρ for all 0 ≤ x ≤ R -1 and 0 otherwise, where ρ = 1/R. We denote by p n (i, j) the transition probability from state i to j, by u the stationary distribution under the threshold policy n, and by R the maximum rate (ρ = 1/R). One can notice that u verifies the full balance equation, i.e.:

u(i) = L j=0 p n (j, i)u(j) = n j=0 p n (j, i)u(j) + L j=n+1 p n (j, i)u(j) (4.39)
Definition 4.3. We define π i as:

π i = ρ if 0 ≤ i ≤ R -1 0 else (4.40)
Proposition 4.1. The expressions of p n (j, i) are given by: If 0 ≤ i < L and j ≤ n

p n (j, i) = π i-j = ρ if 0 ≤ i -j ≤ R -1 0 else (4.41)
Chapter 4. Whittle's index policy for minimizing the Delay in Queuing systems

if 0 ≤ i < L and n < j ≤ L p n (j, i) = π i = ρ if 0 ≤ i ≤ R -1 0 else (4.42) if i = L and j ≤ n p n (j, L) = (R -L + j)π L-j = (R -L + j)ρ (4.43) if i = L and n < j ≤ L p n (j, L) = (R -L)π L = (R -L)ρ (4.44)
Proof. See appendix B.2.

Proposition 4.2. The expressions of the stationary distribution is:

u(i) =    ρ(1 -ρ) n-i if 0 ≤ i ≤ n ρ if n + 1 ≤ i ≤ L -1 (1 -ρ) n+1 -(L -n -1)ρ if i = L (4.45) 2) n = L: u(i) = 0 if 0 ≤ i ≤ L -1 1 if i = L (4.46)
Proof. See appendix B.3.

We reformulate the dual of the relaxed problem using the stationary distribution derived above, i.e., min

n∈[-1,L] E[aq n + W s n ] = min n∈[-1,L] { L q=0 au n (q)q -W n q=0 u n (q) + W } (4.47)
with n and u n being the threshold and the stationary distribution under the threshold policy n.

We first give the expression of the mean cost in equation (4.47) given threshold n when

L < R. If -1 ≤ n ≤ L -1: L q=0 au n (q)q = a[(L + R)(1 -ρ) n+1 + n -R + 1 + (L -1 -n)(n -L) 2R ] (4.48) If n = L: L q=0
au n (q)q = aL (4.49)

Secondly, we provide the expression of the passive decision's average time in equation (4.47) given a threshold n.

If -1 ≤ n ≤ L -1: n q=0 u n (q) = 1 -(1 -ρ) n+1 (4.50) If n = L: n q=0 u n (q) = 1 (4.51)
According to Chapter 3 Section 3.3.3, to get the values of Whittle's indices, we apply the algorithm 1. Nevertheless, we need to adapt it to this case before using it. To that extent, the adapted algorithm will be:

Algorithm 2 Whittle Index Computation

1:
Init. Let j be initialized to 0

2: Find W 0 = inf n∈N L q=0 au n (q)q-L q=0 au -1 (q)q n q=0 u n (q)
3: Define n 0 as the largest minimizer of the above expression 4: Let W (k) = W 0 for all k ≤ n 0 5: while n j = L do 6:

j = j + 1 7: Define M j the set {0, • • • , n j-1 } 8: Find W j = inf n∈N\M j L q=0 au n (q)q-L q=0 au n j-1 (q) n q=0 u n (q)- n j-1 q=0 u n j-1 (q)
9:

Define n j as the largest minimizer of the above expression 10:

Let W (k) = W j for all n j-1 < k ≤ n j 11: Output The Whittle index of state k which is given by W (k)

Remark 4.3. In order to simplify the notation in the sequel, we denote L q=0 au n (q)q by a n and n q=0 u n (q) by b n . However, in order to apply Algorithm 2 that allows to obtain the Whittle's index for each state, we need to check that the conditions given in Proposition 3.2 are satisfied. We start first by establishing the indexability. Theorem 4.2. For each k, the class-k is indexable.

Proof. According to Proposition 3.2, we just need to prove that n q=0 u n (q) is increasing with n. It is clear that from (4.50), n q=0 u n (q) is increasing with n. Hence, the class is indexable.

We prove the two others conditions of Proposition 3.2 which are the increase property of L q=0 au n (q)q with n, and that for all i and j such that i < j, i q=0 u i (q) = j q=0 u j (q) =⇒ L q=0 au i (q)q < L q=0 au j (q)q. The second property for this case is meaningless since i q=0 u i (q) is strictly increasing with i. While for the first one, one should demonstrate that a n is increasing with n. Proposition 4.3. a n = L q=0 au n (q)q is increasing with n.

Proof. See appendix B.4.

As the indexability is satisfied and the two conditions of Proposition 3.2 are verified, then we can apply Algorithm 2 to get the Whittle's index for each state. However, the complexity of this algorithm is L 2 . In order to overcome this complexity issue, we will provide further analysis and derive simple expressions of the Whittle indices. We first proceed by laying out the following definitions and lemmas.

Definition 4.4. For any given increasing threshold policy n, we define y n as a function of the subsidy W , such that y n (W ) = L q=0 au n (q)q -W n q=0 u n (q) = a n -W b n .

Lemma 4.3. The intersection point W = x i,j between y i (W ) and y j (W ) is equal to:

x i,j = L q=0 au i (q)q -L q=0 au j (q) i q=0 u i (q) -j q=0 u j (q) (4.52) Theorem 4.3. The Whittle index of state n ∈ [0, L]: W (n) = x n,n-1 = a[ρ[(L -n) -(L + R)(1 -ρ) n ] + 1] ρ(1 -ρ) n
Proof. See appendix B.5

Whittle's Index policy for the original problem

We now consider the original optimization problem (4.2) and propose a simple Whittle's Index policy. This policy consists of simply allocating the channels to the M users that have the highest Whittle indices at time t, denoted by W IP , and computed using the simple expressions in Theorem 4.3. Now, we tackle the second case: when L is infinite. For that, we use the Discounted Cost approach detailed in Chapter 3 Section 3.3.3.

Discounted Cost approach (L = +∞)

In this section, we will adopt the Discounted Cost approach to get the Whittle indices.

We will also explain the limitation of the steady state approach, and why it cannot be used to find the Whittle index values if the queues have an unlimited capacity.

Applying the steady state approach in the unlimited capacity framework, we get the following results:

• Computing the stationary distribution under a given threshold policy n, we end up with an increasing average passive time with n, i.e., n i=0 u n (i) grows with n. Therefore, according to Proposition 3.2, the problem is indexable.

• The Whittle's indices expressions are defined only for states in [0, R k -1] and are given by: For

0 ≤ n ≤ R k -1: W k (n) = a k R k n R k -n
As one can see, the above result is limited to the case where the states are in [0, R k -1].

For this reason, we rely on another method which allows us to find the Whittle index values for all possible states. To do so, we formulate a discounted cost problem in which β is a discount factor. We analyze this discounted problem and find the Whittle index expressions (that depends on β). Then by taking β → 1, we obtain the Whittle index for our original problem. Similarly, since the Discounted Cost approach is already explained in Chapter 3 Section 3.3.3, we give briefly the main theoretical findings.

The original problem with the expected discounted cost is:

min φ∈Φ E +∞ t=0 K k=1 γ k N i=1 β t a k q k i (t) | q(0), φ , s.t. K k=1 γ k N i=1 s k i (t) ≤ αN, ∀t. (4.53)
The dual of the relaxed problem for a given W is:

min φ∈Φ +∞ t=0 E[ K k=1 γ k N i=1 β t (a k q k i (t) + W s k i (t)) | φ, q(0)]. (4.54)
The Bellman equation for an one-dimensional problem is:

V (q k i ) = min s k i {C(q k i , s k i ) + β q k i P r(q k i |q k i , s k i )V (q k i )}. (4.55)
Following the same method in 4.3.2 but with a parameter β instead of θ, we can prove that the optimal solution that satisfies this Bellman equation is a threshold policy, by proving that the function T O(V ) is submodular. We can also conclude that the value function has the same structural property as in Section 4.3.2, especially, the submodularity and R kconvexity. However, contrary to the method applying when L is finite, finding the steadystate distribution will not give an explicit expression of Problem (4.54). Nevertheless, we can work only with the Bellman equation to derive the Whittle index thanks to the parameter β which helps us to find the Whittle index for all states.

From now on, we detail the procedure followed to obtain the Whittle index policy for the discounted Cost problem (4.54).

To prove that the Whittle index for a given state n in class k is a given W k (n), according to the definition of the Whittle's index, we have to demonstrate that for all W ≤ W k (n), at state n the optimal decision of the Bellman equation (4.55) must be the active action.

And for all W > W k (n), at state n the optimal decision of (4.55) must be the passive action. In other terms, since the optimal solution of (4.55) is a threshold-based policy, it is sufficient to show that for all W ≤ W k (n), the optimal threshold policy must be strictly less than n, and for all W > W k (n), the optimal threshold policy must be greater than n. Accordingly, if we can find a function that links a given state n to the corresponding lagrangian parameter W for which n is the optimal threshold policy with respect to the problem (4.55), then we will be able to characterize the Whittle's index of state n by investigating the variation of this function with respect to n. To that end, we proceed in two steps: finding this aforementioned function, and studying its evolution. Regarding the first step, we start by giving these two following definitions.

Definition 4.5. We define C n 0 (q k i , W ) and C n 1 (q k i , W ) in class k as the discounted costs starting at the initial queue state q k i at which the decision taken is to not be scheduled (s k i = 0) or to be scheduled (s k i = 1) respectively and when the policy considered is threshold n, explicitly:

C n 0 (q k i , W ) a k q k i + β q k i P r(q k i |q k i , 0)V n (q k i , W ), C n 1 (q k i , W ) a k q k i + W + β q k i P r(q k i |q k i , 1)V n (q k i , W ),
where V n (•, W ) is the value function under threshold policy n and lagrangian parameter W .

Definition 4.6. We define g k (n, W ) as a function defined in [0, +∞[×R, such that for all

(n, W ) ∈ [0, +∞[×R, g k (n, W ) = C n 1 (n, W ) -C n 0 (n, W ) Proposition 4.4. For 0 ≤ n ≤ R k -1: g k (n, W ) = W (1 -nβρ k ) -a k nβ For n ≥ R k : g k (n, W ) = W (1 -β) -a k R k β 1 -ρ k β Proof. See Appendix B.6.
We emphasize that to prove that for a fixed W , in class k, a given state n is indeed an optimal threshold (i.e. if q k i ≤ n the queue is not scheduled and otherwise it is scheduled), we just need to prove that it satisfies for all states q k i ≤ n, C n 0 (q k i , W ) ≤ C n 1 (q k i , W ) and for q k i > n, C n 0 (q k i , W ) ≥ C n 1 (q k i , W ) (according to Bellman equation). In other words, we suppose that n is a threshold (i.e. if q k i ≤ n the queue is not scheduled and otherwise it is scheduled), and we show that for all states q k i ≤ n, C n 0 (q k i , W ) ≤ C n 1 (q k i , W ) and for q k i > n, C n 0 (q k i , W ) ≥ C n 1 (q k i , W ). We note that for a given value of W , the optimal threshold might not be unique. Proposition 4.5. For a given lagrangian parameter W and class k, if there exists n such that C n 0 (n, W ) = C n 1 (n, W ), then n is an optimal threshold. Proof. See Appendix B.7.

According to the proposition above, the lagrangian parameter W for which n is the optimal threshold is the one that verifies, g k (n, W ) = 0. Subsequently, as we have already derived the explicit expression of g k (•, •), we can find the expression of the parameter W in question in function of n. For that purpose, we provide this following proposition.

Proposition 4.6. If n ≤ R k -1, then for W = βa k R k n R k -βn , n is an optimal threshold. If n ≥ R k , then for W = a k R k β 1-β , n is an optimal threshold. Proof. See Appendix B.8.
As for the second step, we study the function g k defined in Definition 4.6.

Lemma 4.4. g k is strictly increasing with W , and decreasing with n.

Proof. g k is clearly strictly increasing with W and decreasing with n from its expression.

Leveraging the above result, we lay out our desired result in this following Theorem. Theorem 4.4. For each queue state n in class k, the Whittle index expression is given by: For

0 ≤ n ≤ R k -1, W k (n) = βa k R k n R k -βn . For n ≥ R k , W k (n) = a k R k β 1-β . Proof. See Appendix B.9.
We know that for β → 1, the solution for Problem (4.54) is the same as Problem (4.6), see [START_REF] Ross | Introduction to stochastic dynamic programming[END_REF]. Hence, to derive the Whittle index for the expected average cost's case, we must compute the limit as β tends to 1. However, for states greater or equal than R k , the Whittle indices tend to +∞. On the other hand, by looking at our policy which consists on selecting the users at states with the M highest Whittle's index values, we can notice that this policy is the same if the order of the Whittle indices from the biggest to the smallest one is not affected even if the Whittle index values are modified. Theorem 4.5. For any β > 1 -min{a j R j } max{a j R 2 j } , the Whittle index policy where the Whittle indices in each class k are given by: For

0 ≤ n < R k : W k (n) = βa k R k n R k -βn For R k ≤ n: W k (n) = a k R k max{a j R 2
j } is exactly the Whittle index policy when the Whittle indices are given by Theorem 4.4.

Proof. See Appendix B.10.

Whittle's Index policy for the original problem

When β → 1, the condition given in Theorem 4.5 still true. Hence, we get the Whittle index policy for our original problem with the expected average cost given by Theorem 4.5. We can notice that the Whittle index of states greater than the maximum transmission rate are different only by

a k and R k (W k (n) = a k R k max{a j R 2 j }).
Thereby, it is worth mentioning that the obtained policy can be seen as cµ rule when all states are greater than R k , since we choose M users with the highest a k R k .

Further analysis of the optimal solution of the relaxed problem

As it has been mentioned in 3 Section 3.4, to establish the asymptotic optimality, we compare the average cost under Whittle's index policy with the optimal cost of the relaxed problem denoted C RP,N . For this reason, we should provide further analysis and give the structure of the optimal solution for the relaxed problem. From now on, we focus only on the case where L is finite. As we have seen in Section 4.3, for any given W , the optimal solution for the dual relaxed problem (4.6) is a threshold-based policy for each user. By using the Whittle index expressions derived in Theorem 4.3, we provide a derivation of the optimal threshold for each class as a function of the Lagrange parameter W . In this section, we denote by W k i the Whittle index at state i in class k. We denote by l = (l 1 , l 2 , • • • , l K ) the vector which represents the set of thresholds for each class k. We denote by u n k , the stationary distribution for class k under threshold policy n.

Proposition 4.7. For a given W , the optimal threshold vector l = (l 1 (W ), l 2 (W ),

• • • , l K (W ))
for the dual problem satisfies: For each k:

l k (W ) = arg max i {W k i |W k i ≤ W } (4.56) or l k (W ) = arg max i {W k i |W k i < W } (4.57)
We note that the solution can also be a linear combination between the threshold policies

arg max i {W k i |W k i ≤ W } and arg max i {W k i |W k i < W }.
Proof. See appendix B.11. Now, we give the structure of the optimal solution of the constrained relaxed problem.

Proposition 4.8. The solution of the constrained relaxed problem is of type threshold policy l(W * ), with l being the function vector defined in Proposition 4.7 and

W * satisfies α = K k=1 γ k L i=l k (W * )+1 u l k (W * ) k (i).
Proof. See appendix B.12.

However, W * that satisfies the above constraint may not exist since α is a real number that can take any value in [0, 1], and

K k=1 γ k L i=l k+1 (W ) u l k (W ) k
(i) is discrete, since the vector l(W ) can only take discrete values in [-1, L] K . To deal with this issue, we use the fact that for some values of W , the optimal solution of the dual problem can be a linear combination or more precisely a randomized policy between two threshold policies for a given class as it has been mentioned in Proposition 4.7. To that extent, our task is to find among these values of W , the one for which there exists a randomized parameter θ such that the constraint is satisfied with equality. To that end, we introduce this following proposition. Proposition 4.9. There exists a class m, state p, and a randomization parameter θ * such that the optimal solution of the dual problem when the langrangian parameter W = W m p = W * is characterized by:

• For k = m, the optimal threshold is l k (W m p ) = arg max i {W k i |W k i ≤ W m p }
• For k = m, the optimal solution is randomized policy between two threshold policies

l m (W m p ) = arg max i {W m i |W m i ≤ W m p } and l m (W m p )-1 = arg max i {W m i |W m i < W m p }
, where the factor of randomization θ * is the probability of adopting the policy l m (W m p ) and 1 -θ * , the probability of adopting the policy l m (W m p ) -1. • The constraint (4.3) is satisfied with equality, i.e.

α = k =m L i=l k (W m p )+1 γ k u l k (W m p ) k (i) + L i=lm(W m p )+1 γ m u * m (i) + (1 -θ * )γ m u lm(W m p )-1 m (l m (W m p ))
Where

u * m = θ * u lm(W m p ) + (1 -θ * )u lm(W m p )-1 .

Proof. See appendix B.13

The solution of the dual problem described in Proposition 4.9 satisfies the constraint (4.3) with equality, then according to Proposition 4.8, this solution is indeed the optimal solution of the constrained problem. In that regard, the optimal cost of the relaxed problem C RP,N , is expressed as following:

C RP,N = k =m L i=0 N γ k a k u l k (W m p ) k (i)i + L i=0 N γ m a m u * m (i)i (4.58)

Local asymptotic optimality (L < R)

In this section, we will show that the performance of the Whittle's Index policy is asymptotically locally optimal when L is finite. As we have clarified in Chapter 3 Section 3.4, we will compare the average cost obtained by the Whittle's Index policy; WIP; with the one obtained for the relaxed problem RP to establish the optimality of WIP. Explicitly, denoting by C N T (x) the average cost obtained over the time duration 0 ≤ t ≤ T under Whittle's Index policy conditioned on the initial state x ,we show that C N T (x) tends to C RP,N when N and T scale. For that, we will be in need of the relaxed problem's optimal cost's expression, C RP,N derived in Section 4.5. We reconsider the notion of the proportion defined in Chapter 3 Section 3.4 that represents the number of queues at state i in class k over the number of all users which is N . We have that

Z N = (Z 1,N , ....., Z K,N ) with Z k,N = (Z k,N 1 , ......, Z k,N L ) and L i=0 Z k,N i = γ k for each class k. The expression of C N T (x) in function of Z N is 1 T E T -1 t=0 K k=1 L i=1 a k Z k,N i (t)iN | Z N (0) = x ,
where Z N (t) evolves under Whittle's Index policy. Denoting by z * the optimal proportion of the relaxed problem, we say that the Whittle's Index policy is asymptotically locally optimal if there exists δ > 0 such that the initial proportion vector Z N (0) is within Ω δ (z * ) (i.e. ||Z N (0) -z * || < δ), then C N T (x) converges to C RP,N when T and N scale. In order to prove that, we use the fluid limit technique introduced in Chapter 3, i.e., we investigate the evolution of the expectation of Z N (t) under the Whittle's Index policy. The expectation of Z N (t) denoted by z(t), verifies:

z(t + 1) -z(t)| z(t)=z = E Z N (t + 1) -Z N (t)|Z N (t) = z (4.59)
If we denote by w h j the Whittle index for class h at state j and by p k i (z) the probability that a user is selected randomly among z k i to transmit, one can easily show that [START_REF] Weber | On an index policy for restless bandits[END_REF]:

p k i (z) = min{z k i , max(0, α - w h j >w k i z h j )}/z k i (4.60)
We denote by q k,0 i,j and q k,1 i,j the probabilities of transition from state i to state j in a class-k if the queue is not scheduled and if the queue is scheduled for transmission respectively. Then, the probability of transition from state i to state j in class k is:

q k i,j (z) = p k i (z)q k,1 i,j + (1 -p k i (z))q k,0 i,j (4.61)
Accordingly, we have that for each i and k:

z k i (t + 1) -z k i (t) = j =i q k j,i (z(t))z k j (t) - i =j q k i,j (z(t))z k i (t) (4.62)
Let w * be the Lagrangian parameter that gives the optimal solution of the relaxed problem. Then, according to Proposition 4.9, there exists a given class m such that w m lm = w * for which the corresponding optimal solution of the relaxed problem is of type threshold policy for class k = m denoted l k , and a randomized policy between two threshold policies l m and l m -1 for class m. We define  w * as the set of states such that at any system state z ∈  w * , if we use the Whittle's Index policy, all users with the Whittle index value higher than w * are scheduled, while the users with Whittle index value smaller than w * stay idle and the users with Whittle index value w * are scheduled with a certain randomization. Specifically,  w * = {z :

w k i >w * z k i < α, w k i ≥w * z k i ≥ α}.
Providing that for all k and t:

L j=0 z k j (t) = γ k (4.63)
Therefore, the following equation always holds for z(t) ∈  w * : 1) k = m:

z k i (t + 1) = l k -1 j=0 (q k,0 j,i -q k,0 l k ,i )z k j (t) + L j=l k +1 (q k,1 j,i -q k,0 l k ,i )z k j (t) + γ k q k,0 l k ,i (4.64)
Chapter 4. Whittle's index policy for minimizing the Delay in Queuing systems

2) k = m z m i (t + 1) = lm-1 j=0 (q m,0 j,i -q m,0 lm,i )z m j (t) + L j=lm+1 (q m,1 j,i -q m,1 lm,i )z m j (t) + (1 -α)q m,0 lm,i + αq m,1 lm,i - w h j >w m lm h =m,j =l h z h j (t) q m,1 lm,i - w h j ≤w m lm h =m,j =l h z h j (t) q m,0 lm,i + K h=1 h =m L j=0 j =l h 1 {w h l h >w m lm } z h j (t) q m,1 lm,i + K h=1 h =m L j=0 j =l h 1 {w h l h ≤w m lm } z h j (t) q m,0 lm,i - K h=1 h =m γ h (1 {w h l h >w m lm } q m,1 lm,i + 1 {w h l h ≤w m lm } q m,0 lm,i ) (4.65) Let g m i = K h=1 h =m γ h (1 {w h l h >w m lm } q m,1 lm,i + 1 {w h l h ≤w m lm } q m,0 lm,i ) ∀ i ∈ [0, L], and C = (c 1 , • • • , c K ) such that c k = (γ k q k,0 l k ,0 , • • • , γ k q k,0 l k ,L ) and c m = ((1-α)q m,0 lm,0 +αq m,1 lm,0 -g m 0 , • • • , (1-α)q m,0 lm,L + αq m,1 lm,L -g m L ) for each k = m.
Then, 1) k = m:

z k i (t + 1) = l k -1 j=0 (q k,0 j,i -q k,0 l k ,i )z k j (t) + L j=l k +1 (q k,1 j,i -q k,0 l k ,i )z k j (t) + c k i (4.66) 2) k = m: z m i (t + 1) = lm-1 j=0 (q m,0 j,i -q m,0 lm,i )z m j (t) + L j=lm+1 (q m,1 j,i -q m,1 lm,i )z m j (t) + c m i - w h j >w m lm h =m,j =l h z h j (t) q m,1 lm,i - w h j ≤w m lm h =m,j =l h z h j (t) q m,0 lm,i + K h=1 h =m L j=0 j =l h 1 {w h l h >w m lm } z h j (t) q m,1 lm,i + K h=1 h =m L j=0 j =l h 1 {w h l h ≤w m lm } z h j (t) q m,0 lm,i (4.67)
Then, by replacing in the equation above for all k z k l k (t) with γ k -L j=0,j =l k z k j (t), we obtain the following linear relation in  w * between z(t + 1) and z(t) where z is the proportion vector in which the elements z k l k for different k are eliminated.

z(t + 1) = Qz(t) + C (4.68)
where C is a constant matrix and the expression of matrix Q is given in Appendix B. The analysis of the above linear system is therefore important to prove the local optimality. We first provide the following lemma.

Lemma 4.5. If for all eigenvalues λ of Q, |λ| < 1, then there exists a neighborhood Ω σ (z * ) ⊆  w * such that if z(0) ∈ Ω σ (z * ), we have the following: 1) For all t ≥ 0, ||z(t) -z * || < σ (z(t) ∈  w * ).

2) z(t) converges to z * .

Proof. The proof follows from the convergence of the linear system.

Proposition 4.10. For all eigenvalue λ of Q, |λ| < 1

Proof. See the proof in appendix B.14.

The aforementioned result, combined with Lemma 4.5, proves the convergence of the fluid limit system. Consequently, z(t) converges to the fixed point of Equation (4.59), z * . However, the above result is not enough to prove the local optimality, as we have to show that the stochastic vector Z N (t) converges to z * in probability. For that, we introduce the discrete-time version of Kurtz Theorem applied to our problem (see [START_REF] Kurtz | Strong approximation theorems for density dependent markov chains[END_REF]):

Proposition 4.11. There exists a neighborhood

Ω δ (z * ) of z * such that if Z N (0) = z(0) = x ∈ Ω δ (z *
), then for any µ > 0 and finite time horizon T , there exist positive constants C 1 and C 2 such that

P x ( sup 0≤t<T ||Z N (t) -z(t)|| ≥ µ) ≤ C 1 exp(-N C 2 ) (4.70)
where δ < σ, and P x denotes the probability conditioned on the initial state Z N (0) = z(0) = x. Furthermore, C 1 and C 2 are independent of x and N .

According to the above proposition, the system state Z N (t) behaves very closely to the fluid approximation model z(t) when the number of users N is large. Since we have shown the convergence of z(t) to within Ω σ (z * ), we are ready to establish the local convergence of the system state Z N (t) to z * . Lemma 4.6. If Z N (0) = x ∈ Ω δ (z * ), then for any µ > 0, there exists a time T 0 such that for any T > T 0 , there exists positive constants s 1 and s 2 with,

P x ( sup T 0 ≤t<T ||Z N (t) -z * || ≥ µ) ≤ s 1 exp(-N s 2 ) (4.

Global asymptotic optimality (L < R)

In this section, we prove that from any initial state x, the long-run expected average cost obtained with the Whittle's Index policy is optimal when N is very large. In contrast to the method used to prove the local optimality, we work here with the steady state distribution of the stochastic process Z N (t). To ensure that such a stationary distribution exists, we need to show that there is at least one recurrent state. Since the states evolve according to a finite state Markov chain, we just need to prove that there exists a state reachable from any other states.

Lemma 4.7. The state defined as for each class k, z k = (1, 0, • • • , 0) and denoted by z 01 , is reachable from any initial state using the Whittle's Index policy.

Proof. See appendix B.17

This lemma is stronger than proving the existence of a recurrent state. Indeed, this allows us to deduce that Z N (t) evolves in one recurrent aperiodic class, and that there exists a stationary distribution for Z N (t) denoted by Z N (∞). We still need to check if for a fixed N , there exists at least one recurrent state within Ω (z * ), as otherwise Ω (z * ) will be a transient class. If such a state exists, surely Z N (t) will evolve in one recurrent class that contains this recurrent state. To that end, we demonstrate here that z * is reachable from any state for a fixed N . Since z 0 is reachable from any state, we just need to find a path from z 0 to z * . Lemma 4.8. By applying the Whittle's Index policy, the steady state z * is reachable from the state z 0 .

Proof. Since L < R, the probability of transitioning from queue state 0 to any other state whether the action is active or passive is strictly positive. Thereby, there exists a trajectory from z 0 to z * which lasts only one time slot. Consequently, z * is reachable from z 0 . From this lemma above, the state z * is reachable from any state, which means that z * is a recurrent state. However, the considered actions schedule a proportion of users (i.e. not an integer value). This is not feasible and unrealistic for some (small) values of N since the queues are not splittable. In fact, for some values of N , the state z * may not exist. On the other hand, we can say that for enough large N , and for any > 0, there exists at least one recurrent state within the neighborhood Ω (z * ). This will ensure that there is a path to enter a neighborhood Ω (z * ) from any initial state. However, it is important to ensure that the time to enter Ω (z * ) should not scale up with N . For that, we give the following assumption which will be later justified via numerical studies in Section 4.8. Assumption 4.1. We assume that the expected time to enter a neighborhood of z * from any initial state x does not depend on the number of queues N . In other words, for all N the time to enter a neighborhood Ω (z * ) denoted by Γ N

x ( ) is bounded by a constant T b .

Now we provide a useful lemma that allows us to demonstrate the global asymptotic optimality.

Chapter 4. Whittle's index policy for minimizing the Delay in Queuing systems Lemma 4.9. Under assumption 4.1, and for any , we have that:

lim

N →+∞ P (Z N (∞) ∈ Ω (z * )) = 1 (4.73)
Proof. See Lemma 6 in [START_REF] Ouyang | Downlink scheduling over markovian fading channels[END_REF].

Since we have found a stationary distribution of Z N (t) under Whittle's Index policy, the expected average cost under Whittle's Index policy for a fixed N can be written as follows:

lim T →∞ C N T (x) N = K k=1 L i=0 a k E Z k,N i (∞) iN (4.74)
Theorem 4.6. Under assumption 4.1, and for any initial state, we have that:

lim N →+∞ lim T →∞ C N T (x) N = C RP,N N (4.75)
Proof. See appendix B.18

Numerical Results

In this section, we provide numerical results that confirms the asymptotic optimality of the developed Whittle index policy. To that extent, we study two scenarios depending on the buffer size L:

• L = +∞ • L = +∞

Numerical Results for finite buffer size

We consider 2 classes having a respective rate of R 1 = 15 and R 2 = 20. Moreover, we suppose that α = 1/2, L = 10, γ 1 = γ 2 = 1/2, and a 1 = a 2 = a = 1. We also consider two initial states x and y such that all the queues are equal to 0 and L respectively.

Verification of Assumption 4.1

We plot in Figure 4.3, the evolution of the time needed to enter a neighborhood Ω (z * ) (i.e. hitting time of Ω (z * )) with respect to N , given that is small enough. One can see that for large values of N , the hitting time can be considered as a constant and does not diverge for both initial states x and y. This implies that the hitting time is bounded for large values of N which consolidates Assumption 4.1. In this section, we compare the long-run expected average cost per user under the Whittle's Index policy, i.e. lim T →∞ C N T (x)/N = C W IP,N /N , with the one obtained by applying the Max-Weight policy M W P , C M W P,N /N . The policy M W P schedules, at each time t, the M weighted longest queues (equivalently the M highest a k q k i (t)). We also compare the performance of these two policies with the optimal cost per user obtained by using the optimal solution of the relaxed problem, i.e. C RP,N /N . The results are plotted in Figures (4. One can see that for large N , regardless of the initial state, the cost incurred by adopting the Whittle's Index policy tends to the optimal cost of the relaxed problem, which proves that it asymptotically converges to the optimal solution of the original problem. One can also remark that the optimal cost of the relaxed problem per user is constant and does not depend on N (see section 4.5). Lastly, we remark that the solution given by M W P is suboptimal and lacks behind our proposed scheduling scheme.

Fairness among users

In order to improve the fairness among the users in the network, one can use the developed Whittle index policy up to some modifications. To that extent, we introduce in this section a new policy Θ which works as follows: at each time slot t, we schedule the users with the highest W k (q k i (t))D k (q k i (t)), where q k i (t) is the queue state of user i in class k, W k is the Whittle index of state q k i (t) when the transmission rate is R k and D k (q k i (t)) = t u=1 a k q k i (u) t . To evaluate numerically the performance of this policy, we consider the following two costs C π,N

= lim T →∞ 1 T E T -1 t=0 γ 1 N i=1 a 1 q 1 i (t) | x, π and C π,N 2 = lim T →∞ 1 T E T -1 t=0 γ 2 N i=1 a 2 q 2 i (t) | x, π .
We plot these quantities over N when π = W IP and when π = Θ with respect to N in figure 4.5. We conclude that the new policy gives a better performance in terms of fairness, since it reduces the gap between the costs of the two classes of users.

Numerical Results for infinite buffer size

For this scenario, we compare the average cost given by our policy W IP with the one given by the myopic policy or the Max-Weight policy. We plot the results on Figures where we consider two classes of users with their respective transmission rate R 1 and R 2 , and the number of servers is equal to N/2 where N is the number of users. In Figure According to these figures, one can show that our policy WIP is asymptotically optimal even with L = +∞, and performs much better than the myopic policy. This confirms our main motivation behind developing the Whittle index policy when L is infinite.

Conclusion

In this chapter, we have studied the problem of users and channels scheduling under bursty traffic arrivals. At each time slot, only M channels can be allocated to the users knowing that a user can be allocated one channel at most. For both scenarios (L < +∞ and L = +∞), we have formulated a Lagrangian relaxation of the optimization problem and have provided a characterization of the optimal solution of this relaxed problem. We have then developed a simple Whittle's Index policy to allocate the channels to the users and have proved its asymptotic local and global optimality when the numbers of users and channels are large enough and when the buffer size L is finite. This result is of interest as the developed Whittle's Index policy has a low complexity and is near optimal for large number of users. We have then provided numerical results that corroborate our claims.

Chapter 5 Whittle's index policy for minimizing the Age of Information

In this chapter, we apply Whittle index policy (WIP) for minimizing the age of information (AoI) in the framework of scheduling problems. For that purpose, we start by showcasing our system model in the context of AoI minimization problem and in RBP framework. Then, following the same methodology detailed in Chapter 3, we derive the corresponding Whittle's index policy. Afterwards, we provide the rigorous analytical proof of the local and the global optimality of WIP. Lastly, we give some numerical results that put into perspective the exactitude of our theoretical findings. We emphasize that in this chapter, we show the local optimality of Whittle's index policy for a system containing several classes. Whereas, we prove the global optimality for a system containing two different classes. We note that to establish the last result, we proceed with a novel and original approach completely different from that used in the previous chapter and in the literature. Essentially, this new method doesn't require that assumption 4.1 be taken into account.

System Model

Network description

We consider N users that send status updates to a monitor. Due to the limited amount of channels, only M < N users can transmit simultaneously. Let α = M N ∈]0, 1[ be the portion of the N users that can tansmit. Time is considered to be discrete. We recall that in our system model, neither the users nor the channels are equipped with buffers, but instead, the channel is considered to be unreliable, which means that: at time slot t, if user i is scheduled, then the channel is good, i.e., the transmitted packet is successfully received by the monitor at time t + 1 with a probability p i . Otherwise, the packet fails to reach the destination. Moreover, we suppose that users are divided into K classes such that the probability of successful transmission for users in class k is p k . Each class k has γ k N users and, consequently, the following holds:

K k=1 γ k = 1.
Our goal is to let the monitor to have the freshest information carried by the users. To that end, we need first to introduce the AoI metric adapted to our system model.

Adopted age metric

At each time instant t ≥ 0, we let g k i (t) be the time-stamp of the freshest packet by user i of class k that has been delivered to the monitor. Subsequently, the age of information of this user is defined as:

S k i (t) = min(t -g k i (t), L) (5.1)
where L is in N * ∪ {+∞}. To that extent, we study in the sequel the problem of channels allocation with two different metrics depending on L:

1. L is finite 2. L is infinite
To do so, we adapt the methodology given in Chapter 3 for this particular model and similarly to the chapter 4, we derive the theoretical results for both metrics in parallel.

Problem formulation

We let the age vector at time t be S(t) = (S 1 1 (t), . . . , S K γ K N (t)) where S k i (t) is the age at the monitor of user i of class k at time slot t. A scheduling policy π is defined as a sequence of actions π = (a π (0), a π (1), . . .) where a π (t) = (a 1,π 1 (t), a 1,π 2 (t), . . . , a K,π γ K N (t)) is a binary vector such that a k,π i (t) = 1 if user i of class k is scheduled at time t. We let c k,π i (t) ∈ {0, 1} be an i.i.d. Bernoulli random variable that indicates if the transmitted packet by the scheduled user is successfully received (value c k,π i (t) = 1) or not (value c k,π i (t) = 0). Hence, by definition of c k,π i (t), we have that Pr(c k,π i (t) = 1) = p k and Pr(c k,π i (t) = 0) = 1 -p k . Therefore, the evolution of the age of user i of class k under policy π can be summarized in the following:

S k i (t + 1) = 1 if a k,π i (t) = 1, c k,π i (t) = 1 min(S k i (t) + 1, L) otherwise (5.2)
Denoting by Π, the set of all causal scheduling policies, our scheduling problem can formulated as follows:

minimize π∈Π lim T →+∞ sup 1 T E π T -1 t=0 K k=1 γ k N i=1 S k,π i (t)|S(0) subject to K k=1 γ k N i=1 a k,π i (t) ≤ αN t = 1, 2, . . . (5.3)
According to Chapter 3, the problem in (5.3) belongs to the family of RMAB problems, then, the optimal solution is out of reach. For this reason, we derive the Whittle's index policy due to its low complexity and good performance. To that end, we follow the same steps explained in Chapter 3. However, in order to avoid redundancy, we skip the part about the Lagrangian Relaxation approach, and we will be limited to give only the important results in the form of Propositions and Theorems.

1. The Bellman equation that corresponds to the dual relaxed problem for a given user after decomposition is:

θ + V (S) = min a∈{0,1} S + W a + S ∈{1,...,L} Pr(S → S |a)V (S ) (5.4)
where Pr(S → S ) is the transition probability from the age state S to S , θ is the optimal value of the problem and V (S) is the differential cost-to-go function.

2. Since we are not able to find the explicit solution of the Bellman equation for a given W , we focus only on studying the structure of the optimal scheduling policy. By doing so, the following results can be obtained. First of all, we recall the definition of an increasing threshold policy.

Definition 5.1. An increasing threshold policy is a policy π n ∈ Π such that when the age of information is larger or equal1 to n, the user is scheduled. Otherwise, it is not scheduled.

Theorem 5.1. The optimal solution of the problem in (5.4) is an increasing threshold policy.

Proof. The proof can be found in Appendix C.1.

3.

In order to establish the indexability of the problem and find the Whittle's index expressions, we tackle in more depth the behavior of the MDP that characterize the evolution of the age when a threshold policy is adopted. In fact, under a threshold policy n, the MDP can be modeled through a Discrete Time Markov Chain (DTMC) as seen in Fig. 5.1 and in Fig. 5.2. To that extent, we derive in the next proposition, the stationary distribution of the DTMC in question for both cases of L.

Proposition 5.1. For any given threshold n ∈ {1, . . . , L}, the DTMC is irreducible and admits u n (i) for i = 1, . . . , L as its stationary distribution:

• Finite L:

(a) n ≤ L u n (i) =      p np+1-p if 1 ≤ i ≤ n (1 -p) i-n p np+1-p if i ≥ n (1-p) L-n np+1-p if i = L (5.5) (b) n ≥ L + 1 u n (i) = 0 if 1 ≤ i ≤ L -1 1 if n = L (5.6)
• Infinite L:

u n (i) = p np+1-p if 1 ≤ i ≤ n (1 -p) i-n p np+1-p if i ≥ n (5.7)
Proof. The expressions results from solving the full balance equation satisfied by

u n (•) while bearing mind that L i=1 u n (i) = 1.
Based on the stationary distribution under a threshold policy n, we can give the steady-state form of the one-dimensional dual relaxed problem that corresponds to the Bellman equation (5.4) as follows:

min n∈[1,L] L i=1 iu n (i) + W L i=n u n (i) (5.8)
where W is the Lagrangian parameter, L i=1 iu n (i) = lim sup

T →∞ 1 T E πn T -1
t=0 s πn (t) refers to the long run expected average age under threshold policy π n , and L i=n u n (i) = lim sup

T →∞ 1 T E πn T -1
t=0 a πn (t) indicates the long run expected average time when the active action is prescribed to the user of interest under threshold policy π n . As it was mentioned in Chapter 3, this closed form of the one-dimensional dual relaxed problem turns out to be crucial to derive the Whittle index values as we will see in the sequel. By leveraging the above results, we can now proceed with finding a closed-form of the average age as well as the average active time under a given threshold policy π n for both cases of L. Theorem 5.2. For any given threshold n, the explicit expressions of L i=1 iu n (i) and L i=n u n (i) are: • Finite L:

L i=1 iu n (i) = [(n -1) 2 + (n -1)]p 2 + 2p(n -1) 2p((n -1)p + 1) + 2[1 -(1 -p) L-n+1 ] 2p((n -1)p + 1) (5.9) L i=n u n (i) = 1 np + 1 -p (5.10) (b) n ≥ L + 1: L i=1 iu n (i) =L (5.11) L i=n u n (i) =1
(5.12)

• Infinite L:

L i=1 iu n (i) = [(n -1) 2 + (n -1)]p 2 + 2p(n -1) 2p((n -1)p + 1) + 2 2p((n -1)p + 1) (5.13) L i=n u n (i) = 1 np + 1 -p (5.14)
4. Based on the above results, we establish the indexability property of the problem for all users, which ensures the existence of the Whittle's indices and allows us to establish our index policy as it was explained in Chapter 3.

Proposition 5.2. For both cases of L, and for each user belonging to any class k = 1, . . . , K, the one-dimensional problem is indexable.

Proof. The proof can be found in Appendix C.2.

As the indexability property has been established in the above proposition, we can now affirm the existence of the Whittle's index. To that extent, we provide the expressions of Whittle's indices in the following theorem.

Theorem 5.3. The Whittle's index of state i ∈ [1, L] in class k is defined as:

• Finite L:

W k i = i(i -1)p k 2 + i -i(1 -p k ) L-i (5.15)
• Infinite L:

W k i = i(i -1)p k 2 + i (5.16)
Proof. The proof can be found in Appendix C.3.

5.

In light of the last result, we summarize in the following the Whittle's index scheduling policy for the original problem (5.3).

Algorithm 3 Whittle's index scheduling policy 1: At each time slot t, calculate the Whittle's index of all users using Theorem 5.3.

2: Schedule the M users having the highest Whittle's index values at time t.

Although the above scheduling policy is easy to implement, it remains sub-optimal. Subsequently, characterizing its performance compared to the optimal policy is important.

Local optimality: Finite L

In this section, we study the local optimality properties of the Whittle's index policy when L is finite. To that end, we reintroduce the state space {Z k,N i (t), 1 ≤ i ≤ γ k N, 1 ≤ k ≤ K} defined in Chapter 3, Section 3.4 over which the local optimality will be established. Analogously to the method used in the previous chapter with regard to the optimality of WIP, we proceed with the fluid approximation technique to establish the desired result. Accordingly, the deterministic vector z(t) evolves as:

z(t + 1) -z(t)| z(t)=z = E[Z N (t + 1) -Z N (t)|Z N (t) = z]
(5.17)

In order to obtain the linear relation between z(t + 1) and z(t) when the Whittle's index policy is implemented, we should first determine the transition probability from a given state of age to another state for a given z(t) = z. To that end, we reintroduce the probability that a user of class k in state i is selected among the proportion z k i for transmission:

p k i (z) = min{z k i , max(0, α - W h j >W k i z h j )}/z k i , (5.18)
Next, as it was done in Chapter 4, Section 4.6, we denote by q k,0 i,j and q k,1 i,j the probability of transition from state i to state j in a class k if the user is left to idle or is scheduled for transmission respectively. The expressions of q k,0 i,j and q k,1 i,j can be easily derived from the age dynamics detailed in (5.2). Specifically:

q k,0 i,j = 1 if j = min(i + 1, L) 0 otherwise q k,1 i,j =      p k if j = 1 1 -p k if j = min(i + 1, L) 0 otherwise (5.19)
Therefore, given z, the probability of transition between state i and j in class k, q k i,j (z) which can be also seen as the output stream from the state i to the state j given z for a user at state i, is as follows:

q k i,j (z) = p k i (z)q k,1 i,j + (1 -p k i (z))q k,0 i,j .
(5.20)

Given that, we can summarize the evolution of z(t) as follows:

z k i (t + 1) -z k i (t) = j =i q k j,i (z(t))z k j (t) - i =j q k i,j (z(t))z k i (t) (5.21)
This can be rewritten in the following manner:

z(t + 1) = Q(z(t))z(t) + z(t) (5.22)
We recall that to establish the asymptotic optimality of Whittle's index policy, according to 3.4, we compare its performance to the average age of the relaxed problem. Precisely, we show that C N T (x) converges to C RP,N when N and T grows where C RP,N and C N T (x) are the optimal total average age of the relaxed problem and the total expected average age over time duration 0 ≤ t ≤ T starting from the initial proportion vector z(0) = x when the Whittle's index policy is adopted respectively. For that, we need to have the expression of C RP,N . To proceed in that direction, we rewrite the Proposition 4.9 adapted for our specific case. Proposition 5.3. There exists a class m, state p, and a randomization parameter θ * such that the optimal solution of the dual problem when the langrangian parameter W = W m p = W * is characterized by:

• For k = m, the optimal threshold is l k (W * ) = arg max i {W k i |W k i ≤ W m p } + 1
• For k = m, the optimal solution is randomized policy between two threshold policies

l m (W * ) = arg max i {W m i |W m i ≤ W m p } + 1 and l m (W * ) -1 = arg max i {W m i |W m i ≤ W m p }
, where the factor of randomization θ * is the probability of adopting the policy l m (W * ) and 1 -θ * , the probability of adopting the policy l m (W * ) -1.

• The relaxed constraint is satisfied with equality, i.e.

α = k =m L i=l k (W * ) γ k u l k (W * ) k (i) + L i=lm(W * ) γ m u * m (i) + (1 -θ * )γ m u lm(W * )-1 m (l m (W * ) -1)
Where u * m = θ * u lm(W * ) + (1 -θ * )u lm(W * )-1 . Remark 5.1. In the above proposition, one can notice that the thresholds are differed by one compared with that of Proposition 4.9. This comes from the fact that the definition of a threshold policy is not the same for both chapters 4 and 5.

According to Proposition 5.3, the optimal solution of the relaxed problem is a threshold policy characterized by W * and θ * defined in the above proposition, Accordingly,

C RP,N = K k=1 k =m γ k N L i=1 u l k (W * ) k (i)i + γ m N θ * L i=1 u lm(W * ) m (i)i + γ m N (1 -θ * ) L i=1 u lm(W * )-1 m (i)i (5.23)
For ease of notations we denote l k (W * ) by l * k . For the local optimality, we restrict our analysis to a specific set in Z which is a subset of  W * defined in Section 4.6, Chapter 4. In fact, in this aforementioned set, Q(z(t)) doesn't depend on z(t). This will be confirmed in the sequel by establishing the link between z(t + 1) and z(t) within this set. 1) k = m: In this case, we can replace

z k l * k -1 (t) by γ k -L j=1,j =l * k -1 z k j (t).
Therefore, there is no need to track the evolution of z k l * k -1 (t) with time as it can be deduced from the evolution of z k j (t) for j = l * k -1. Accordingly, we let

z k (t) = [z k 1 (t), . . . , z k l * k -2 (t), z k l * k (t), . . . , z k L (t)].
Next, by replacing q k j,i (z(t)) with its value in (5.21), we can obtain the following expression of z k i (t + 1) in function of z k (t):

L j=l * k p k z k j (t) if i = 1 z k i-1 (t) if 1 < i < l * k -1 - l * k -2 j=1 z k j (t) -L j=l * k z k j (t) + γ k if i = l * k (1 -p k )z k i-1 (t) if l * k < i < L (1 -p k )z k L-1 (t) + (1 -p k )z k L (t) if i = L (5.24)
2) k = m: To tackle this case, we first replace

z m l * m (t) by γ m -L j=1,j =l * m z m j (t)
. Similarly to the first case, there is no need to track the evolution of z m l * m (t) with time. Accordingly, we let

z m = [z m 1 , . . . , z m l * m -1 (t), z m l * m +1 (t), . . . , z m L (t)].
The difference between this case and the above one is that there exists a given set of users in class m whose Whittle's index equals to W * . That implies that, as z(t) ∈  W * , there is a group of users among this aforementioned set which will be scheduled, while the remaining group will be in the idle mode. Thus, unlike the previous case, the relation between z m 1 (t + 1) and z m (t + 1) will not be easy to express. Nevertheless, we recall that the portion of scheduled users is always equal to α. Hence, the portion of scheduled users of class m can be always written as the difference αk =m

L j=l * k z k j (t).
With that in mind, we can write the evolution of z m i (t + 1) for any i = l * m in function of z(t) as follows:

(α -k =m L j=l * k z k j (t))p m if i = 1 z m i-1 (t) if 1 < i < l * m -l * m -1 j=1 z m j (t) -L j=l * m +1 (1 -p m )z k j (t) + γ m -p m (α -k =m L j=l * k z k j (t)) if i = l * m + 1 (1 -p m )z m i-1 (t) if l * m + 1 < i < L (1 -p m )z m L-1 (t) + (1 -p m )z m L (t) if i = L (5.25)
Based on this, we can conclude that when z(t) ∈  W * , z(t+1) and z(t) are related through the simpler linear equation:

z(t + 1) = Q z(t) + c, (5.26)
Where the expression of Q has the following form:

Q =            Q 1 0 • • • • • • • • • • • • 0 0 Q 2 • • • • • • • • • • • • 0 . . . . . . A 1 A 2 • • • Q m • • • A K-1 A K . . . . . . . . . 0 0 • • • • • • • • • Q K-1 0 0 0 • • • • • • • • • 0 Q K            . ( 5.27)
Let us define z * ∈ Z as the system state vector that results from adopting the optimal policy of the relaxed problem. By exploiting the results of Propositions 5.1 and 5.3, and using the definition of z * , one can find the exact expression of z * . Specifically:

z * ,k i = γ k u l * k k (i) z * ,m i = γ m [θu l * m m (i) + (1 -θ)u l * m -1 m (i)]
(5.28)

To prove that C N T (x) converges to C RP,N when T and N scale, we should first demonstrate that z(t), when the Whittle's index policy is adopted, converges to z * within a given subset of  W * . In fact, z * is not simply a system state that belongs to the set  W * , but beyond that, it is the fixed point of the fluid approximation equation (5.17). Bearing that in mind, we have this following always holds when z(t) ∈  W * :

z(t) -z * = Qe (5.29)
where e = z(0) -z * . As consequence, as it was depicted in Section 4.6 Chapter 4, we must set out that all eigenvalues of Q are strictly less than one to establish our desired result. The proof of this statement is elaborated in C.4.

Proposition 5.4. For all eigenvalue λ of Q, |λ| < 1 Proof. See appendix C.4.
Accordingly, there exists σ > 0 such that, if z(0) ∈ Ω σ (z * ) ⊆  W * , we have z(t) ∈  W * and z(t) converges to z * . Leveraging these above results, we prove that Z N (t) evolves closely to z * when N is large.

Proposition 5.5. There exists a neighborhood Ω δ (z * ) such that, for any T, µ > 0, if Z N (0) = x ∈ Ω δ (z * ), there exists a constant C 1 independent of N and x such that:

Pr x ( sup 0≤t<T ||Z N (t) -z(t)|| ≥ µ) ≤ C 1 N (5.30)
where Pr x denotes the probability conditioned on the initial state Z N (0) = x.

Providing that z(t) converges to z * within a neighborhood Ω δ (z * ), we get the following corollary based on the previous proposition.

Corollary 5.1. There exists a neighborhood Ω δ (z * ) such that, for any µ > 0, if Z N (0) = x ∈ Ω δ (z * ), then there exists a time T 0 such that for any time instant T > T 0 , there exists a constant C f independent of N and x such that:

Pr x ( sup T 0 ≤t<T ||Z N (t) -z * || ≥ µ) ≤ C f N (5.31)
Proof. The proof is identical to that of Lemma 4.6.

Based on this corollary, we are ready now to establish the local optimality of the Whittle's index policy.

Proposition 5.6. If the initial state x is in the set Ω δ (z * ), then lim

T →∞ lim N →∞ C N T (x) N = C RP,N N (5.32)
Proof. The proof is identical to that of Proposition 4.12. Accordingly, it will be skipped for sake of shortness.

Global Optimality: Infinite L

In this section, we will show that the Whittle Index Policy is asymptotically globally optimal when L is infinite. Specifically, we show that the Whittle index Policy is optimal for a large number of users N and a large number of channels M , the ratio α = M N being constant and starting from any initial state. For that, we will compare the average cost obtained by the Whittle Index Policy with the optimal cost of the original problem. Providing that the number of states of the age is infinite, we denote by m k (t), the highest state at time t in class k. Without loss of generality, we have that

m k (t) i=0 Z k,N i (t) = γ k for each class k.
We establish the global optimality for two different classes of users where p 1 and p 2 are the successful transmission probabilities of the class 1 and 2 respectively (p 1 > p 2 ). As it has been proven in 5.2, we prove likewise that Z N (t), evolving under the Whittle index policy, converges in probability to z * when N and t are very large. To that extent, we start by showing that the fluid approximation of Z N (t) denoted by z(t) converges to z * . To that end, for a sake of clarity, we give in the sequel an insight into the theoretical analysis developed to demonstrate this desired result: Recalling that the relation that links z(t + 1) to z(t) is not linear in general as it was reported in Section 5.2, then establishing the convergence of z(t) requires a new method involving terms of α 1 (t) and α 2 (t) where these two users' proportions refer to the scheduled users' proportion at time t of the class 1 and 2 respectively (α 1 (t) + α 2 (t) = α). To that extent, we give in the following the outlines of the proof:

1. For a large enough time t, based on Lemma 5.1, we show that there exists T t such that we can find a partial relation between each element of the vector z(t + T t ) and terms of the sequence {α k (t )} k=1,2 t ≤t+Tt

. More precisely, we prove that for T t , we can express each proportion of users that are not scheduled at time t + T t in function of one term of {α k (t )} k=1,2 t ≤t+Tt

. This allows us to obtain 1 -α as a linear combination between the terms of {α k (t )} k=1,2 t ≤t+Tt at time t + T t .

2. We define in Definition 5.3, T max that satisfies these two following properties proven in Propositions 5.8 and 5.9 using Lemma 5.2:

• The Whittle index alternates between the two classes from state 1 to T max + 1 under a given assumption on α.

• The instantaneous thresholds l 1 (.) and l 2 (.) are bounded by T max at time t + T t .

Chapter 5. Whittle's index policy for minimizing the Age of Information 3. Based on the above result, we derive the relation between the instantaneous thresholds at time t + T t in Proposition 5.10.

4.

Taking as an initial time t + T t = T 0 , we show by induction in Proposition 5.11, that for all T ≥ T 0 , the instantaneous thresholds are less than T max and that all proportions containing the non scheduled users can be expressed in function of terms of the sequence {α k (t )} k=1,2 t ≤T .

5. We define for each class k a vector A k (T ) composed by α k (T ) (the scheduled users' proportion at time T ) plus the finite subset of the sequence {α k (t )} t ≤T such that for all proportion of users in class k at a given state at time T that is not scheduled can be expressed by one element belonging to this subset. Then, we provide the relation between the elements of the vectors A k (T ) and A k (T + 1) in Propositions 5.12 and 5.13

6. We conclude the convergence of the highest and the smallest element of A k (T ) when T grows in Theorem 5.4.

7.

We demonstrate by contradiction that the highest and the smallest element of A k (T ) must converge to the same limit in Proposition 5.14. This last result implies that α k (t) converges when t scales.

8. In light of that fact, we prove that z(t) converges to z * in Proposition 5.15.

9. Using Kurth theorem, we show in Proposition 4.11 that Z N (t) converges to z * in probability.

10. Finally we establish in Proposition 5.17, the convergence of C N T (x) to C RP,N as N and T grow starting from any initial point x.

Remark 5.2. We highly emphasize that the proportion α k (t) and 1 -α refer to the scheduled users' proportion at time t in class k and the non scheduled users' proportion either for class 1 or 2 respectively. Meanwhile, for any other proportion A, it refers only to the number of users in this proportion over the total users' number of the system whatever the different states of users that contains. Having said that, A = B means that they are equal in terms of proportion, while they can contain users in different states.

We remind that the fluid limit technique consists of analyzing the evolution of the expectation of Z N (t) under the Whittle Index Policy. For ease of reading, we rewrite the equation (5.17):

z(t + 1) -z(t)| z(t)=z = E Z N (t + 1) -Z N (t)|Z N (t) = z (5.33)
This above equation reveals to us that we have a sequence z(t) defined by recurrence for a fixed initial state z(0) that we should study its behavior when t is very large. Hence, we end up with a function z(t) that depends on two variables, t and the initial value z(0). To that extent, our aim is to prove that z(t) converges to z * regardless of the initial state z(0) where z * denotes the users' proportion corresponding to the optimal policy of the relaxed problem when L is infinite. We let z(t) = (z 1 (t), ....., z K (t)) with

Chapter 5. Whittle's index policy for minimizing the Age of Information

z k (t) = (z k 1 (t), ......, z k m k (t) (t)) where z k i (t)
is the expected proportion of users at state i in class k at time t with respect to the equation (5.33). Accordingly we have that

m k (t) i=0 z k i (t) = γ k for each class k.
One can notice that z * is a particular vector with respect to the equation (5.33).

Proposition 5.7. z * is the unique fixed point of the fluid approximation equation. In other words, z(t) = z(t + 1), if and only if z(t) = z * .

Proof. The proof follows the same methodology of the paper [32, Lemma 9] According to this proposition, it is sufficient to show that z(t) converges starting from any initial state z(0), as the only eventual finite limit of z(t) when t tends to +∞ is the fixed point of the equation (5.33), z * .

In the following, we prove that the fluid approximation vector of Z N (t), z(t) under the Whittle Index Policy converges starting from any initial state. We prove this result for 2 different classes of users where p 1 and p 2 are the successful transmission probabilities of the class 1 and 2 respectively (p 1 > p 2 ), given a sufficient condition on α. Throughout this section, we denote by w 1 (n) and w 2 (n), the Whittle's index, whose expression is given in Proposition 5.3, of state n in class 1 and class 2 respectively. We need to prove that z k i (t) converges for each state i in class k. Now, focusing on the Whittle index policy, we can see it as an instantaneous threshold policy for each class, where the thresholds vary over time t. Moreover, under the Whittle index policy, the proportion of users that are scheduled at each time slot t is fixed and equals to α since the number of scheduled users at each time slot t is αN . This proportion α contains the users with the highest Whittle index values. In that respect, we define α 1 (t) and α 2 (t) the proportion of users in class 1 and class 2 respectively at time t with the highest Whittle index values such that α 1 (t) + α 2 (t) = α. The remaining proportion of users which are not scheduled at each time slot t, which is equal to 1 -α, contains the users with the smallest Whittle index values. Now, regarding this proportion, we give its decomposition into proportions of users at different states in different classes. Denoting by l 1 (t) and l 2 (t) at time t the instantaneous threshold integers under Whittle index policy, then there exists two real values between 0 and 1, β(t) and γ(t), with γ(t) = 1 and 0 < β(t) ≤ 1, or 0 < γ(t) ≤ 1 and β(t) = 1, such that:

l 1 (t)-1 i=1 z 1 i (t) + l 2 (t)-1 i=1 z 2 i (t) + β(t)z 1 l 1 (t) (t) + γ(t)z 2 l 2 (t) (t) = 1 -α (5.34)
and

{z 1 i (t)} 1≤i≤l 1 (t) ∪{z 2 i (t)} 1≤i≤l 2 (t) is exactly the set {z k i : w k (i) ≤ max(w 1 (l 1 (t), w 2 (l 2 (t))}.
For the case where L is finite, we have assumed that z(0) is within a neighborhood of z * . This assumption has allowed us to find an easy linear relation between z(t) and z(t + 1) (z(t + 1) = Qz(t) + c), and then deduce the convergence of z(•) by establishing that the spectral value of Q is strictly less than one as it was depicted in Proposition 5.4. Whereas for this case, when L is infinite, since we aim to prove the convergence of z(•) from any initial state, the general relation between z(t + 1) and z(t) is as follows:

z(t + 1) = Q(z(t))z(t) + c(t) (5.35)
This equation is not linear which makes studying the evolution of z(•) a hard task. Moreover, as the number of state is infinite, then the dimensions of z(t) varies per time. Therefore, the matrix Q(z(t)) is not square. Hence we can not apply the same method as in Section 5.2 since the spectral values are not defined for a non square matrix. For these reasons, we proceed differently than 5.2. Our method consists in fact on expressing each proportion z k i (t) that belongs to a non scheduled users' proportion at time t in function of a term of α k (•) at a given time less than t. By this way, we will obtain a part of the vector z(t) in function of {α k (t )} t ≤t, k∈{0,1}

, and the sum of the other part equal to α. Then, we show that α k (•) converges for k = 1, 2. We will see later that it is sufficient to show that α k (•) converges in order to conclude for the convergence of z(•). To find the partial relation between z(t) and {α k (t )} t ≤t k∈{0,1}

, we prove the following lemma.

Lemma 5.1. Knowing z k (t), α k (t) and l k (t), we have that:

For i = 1: z k 1 (t + 1) = p k α k (t). For 1 ≤ i < l k (t): z k i+1 (t + 1) = z k i (t). Proof. See appendix C.5.
According to Lemma 5.1, after scheduling under the Whittle's Index Policy, we get at time t + 1, a proportion of p 1 α 1 (t) of users at state 1 in class 1 and p 2 α 2 (t) of users at state 1 in class 2 respectively (i.e. z 1 1 (t + 1) = p 1 α 1 (t) and z 2 1 (t + 1) = p 2 α 2 (t)). According to the same lemma, at time t + 2, a proportion of p 1 α 1 (t) and p 2 α 2 (t) of users will go to state 2 in class 1 and class 2 respectively and p 1 α 1 (t + 1), p 2 α 2 (t + 1) of users will move to state 1 in class 1 and class 2 respectively (i.e. z 1 1 (t + 2) = p 1 α 1 (t + 1), z 2 1 (t + 2) = p 2 α 2 (t + 1), z 1 2 (t + 2) = p 1 α 1 (t) and z 2 2 (t + 2) = p 2 α 2 (t)). At time t + 3, a proportion of p 1 α 1 (t) and p 2 α 2 (t) of users will go to state 3 in class 1 and class 2 respectively, p 1 α 1 (t+1), p 2 α 2 (t+1) of users will move to state 2 in class 1 and class 2 respectively, p 1 α 1 (t + 2) and p 2 α 2 (t + 2) of users will move to state 1 in class 1 and class 2 respectively, (i.e. z 1 1 (t + 3) = p 1 α 1 (t + 2), z 2 1 (t + 3) = p 2 α 2 (t + 2), z 1 2 (t + 3) = p 1 α 1 (t + 1) and z 2 2 (t + 3) = p 2 α 2 (t + 1), z 1 3 (t + 3) = p 1 α 1 (t), z 2 3 (t + 3) = p 2 α 2 (t)) Thereby, at time t + t 0 where the instantaneous threshold l k (t + t 0 ) ≥ t 0 , we get a set of proportions {p 1 α 1 (t), p 2 α 2 (t), • • • , p 1 α 1 (t + t 0 -1), p 2 α 2 (t + t 0 -1)} that belong to the proportion 1 -α of users with the lowest Whittle index values, such that z

1 1 (t + t 0 ) = p 1 α 1 (t + t 0 -1), z 2 1 (t + t 0 ) = p 2 α 2 (t + t 0 -1), • • • , z 1 t 0 (t + t 0 ) = p 1 α 1 (t) and z 2 t 0 (t + t 0 ) = p 2 α 2 (t). Hence, we obtain a z k i (t + 1) which is well expressed in function of terms of α k (•) (k = 1, 2) for i ∈ [1, t 0 ], k = 1, 2.
Remark 5.3. Considering Whittle index policy framework, the order of the different users' proportions with respect to their Whittle index values must be taking into account throughout this analysis. In fact, as we have already mentioned, we need to give the expression of the non scheduled users' proportions in function of the terms of α k (•) for k = 1, 2, which can not be done only if we consider the order of the Whittle index values. To that extent, since the set of the non scheduled users' proportions, according to the Whittle's index policy, is exactly the set of users' proportions with the lowest Whittle index values among all the different users' proportions of the system, then the form at time t of this specific set will be {z k i (t) : w k (i) ≤ w m (n)} for a given m and n that vary with t.

Based on this remark above, we need to find at time t + t 0 , a set of the form {z k i (t + t 0 ) : w k (i) ≤ w m (n)} for a given class m and state n, such all the elements of this set are well expressed in function of α k (•). We show in the sequel that the highest Whittle index of this set could be w 2 (t 0 ). Indeed, given that the Whittle index function is increasing with n where n refers to a given age of information state, then for any state in class 2 with Whittle index less than w 2 (t 0 ), belongs to [1, t 0 ]. Moreover, considering the state q in class 1 such that w 1 (q) ≤ w 2 (t 0 ) ≤ w 1 (t 0 ) (p 1 > p 2 ), then w 1 (q) ≤ w 1 (t 0 ), which means that q ∈ [1, t 0 ]. Hence, for any element in {z k i (t + t 0 ) : w k (i) ≤ w 2 (t 0 )}, can be expressed in function of terms of α k (•) (k = 1, 2). Accordingly, {z k i (t + t 0 ) : w k (i) ≤ w 2 (t 0 )} equals to the set {p 2 α 2 (t), • • • , p 2 α 2 (t + t 0 -1), p 1 α 1 (t + t 0 -l(t + t 0 )), • • • , p 1 α 1 (t + t 0 -1)}, where l(t + t 0 ) is the greatest state q in class 1 such that w 1 (q) ≤ w 2 (t 0 ). We note that l(t + t 0 ) ≤ t 0 because w 2 (l(t + t 0 )) ≤ w 1 (l(t + t 0 )) ≤ w 2 (t 0 ). Therefore, in that regards, for a fixed t, we associate for each t 0 the corresponding sum

l(t+t 0 ) j=1 z 1 j (t + t 0 ) + t 0 j=1 z 2 j (t + t 0 ) = l(t+t 0 ) j=1 p 1 α 1 (t + t 0 -j) + t 0 j=1 p 2 α 2 (t + t 0 -j).
To that extent, we define in the following the time t 0 when this aforementioned sum exceeds 1 -α. Definition 5.2. Starting at time t, we define T t such that t + T t is the first time that verifies:

l(t+Tt) j=1 p 1 α 1 (t + T t -j) + Tt i=1 p 2 α 2 (t + T t -j) ≥ 1 -α (5.36)
In other words, the first time when l(t+t 0 )

j=1 p 1 α 1 (t + t 0 -j) + t 0 i=1 p 2 α 2 (t + t 0 -j) exceeds 1 -α is t + t 0 = t + T t .
Then, at time t + T t , there exists l 1 (t + T t ) ≤ l(t + T t ), l 2 (t + T t ) ≤ T t , such that the set {z 1 i (t + T t )} 1≤i≤l 1 (t+Tt) ∪ {z2 i (t + T t )} 1≤i≤l 2 (t+Tt) is exactly the set {z k i (t + T t ) : w k (i) ≤ max(w 1 (l 1 (t + T t ), w 2 (l 2 (t + T t ))} 2 , and γ(t + T t ) = 1 and 0 < β(t + T t ) ≤ 1, or 0 < γ(t + T t ) ≤ 1 and β(t + T t ) = 1 such that:

l 1 (t+Tt)-1 j=1 p 1 α 1 (t + T t -j) + l 2 (t+Tt)-1 j=1 p 2 α 2 (t + T t -j) + β(t + T t )p 1 α 1 (t + T t -l 1 (t + T t )) + γ(t + T t )p 2 α 2 (t + T t -l 2 (t + T t )) = 1 -α, ( 5
(t + T t ) = p 1 α 1 (t + T t -1), z 2 1 (t + T t ) = p 2 α 2 (t + T t -1), • • • , z 1 l 1 (t+Tt) (t + T t ) = p 1 α 1 (t + T t -l 1 (t + T t )) and z 2 l 2 (t+Tt) (t + T t ) = p 2 α 2 (t + T t -l 2 (t + T t ))
, and the rest of the proportions belongs to α 1 (t + T t ) for class 1 and α 2 (t + T t ) for class 2. For this reason, we work only with α 1 (•) and α 2 (•) in order to prove the convergence. As we have mentioned earlier, the proof of the optimality is valid under an assumption on α. This later relies on the maximum value that can take the instantaneous thresholds l k (t + T t ) at time t + T t for k = 1, 2. To that extent, we start by defining and bounding a certain constant T max . Then under an assumption on α, we show that the order of Whittle index alternates between the two classes in the set [1, T max + 1] (this will be detailed later). Based on this, we establish that T max is an upper bound of l k (t + T t ). First of all, we give a lemma which will be useful to prove the propositions 5.9, 5.10 and 5.11. Lemma 5.2. There exists a time t f such that for all t ≥ t f , α 1 (t) > 0.

Proof. See appendix C.6.

In this following definition, we define T max , and we check later that it coincides with the upper bound of l k (t + T t ) for k = 1, 2. Definition 5.3. Starting at time t, we define T max as T t defined in Definition 5.2, that verifies the following:

• l(t+Tt) j=1 p 1 α 1 (t + T t -j) + Tt j=1 p 2 α 2 (t + T t -j) ≥ 1 -α • α 1 (t + i) = 0 for all i ∈ [0, T max -1]
In the next lemma, we determine the upper and the lower bound of T max . Lemma 5.3. T max doesn't depend on t and satisfies: Proposition 5.10. At any time t > t f , if max(l 1 (t), l 2 (t)) ≤ T max = l max , then there exists l(t) ≤ l max and, β(t) = 0 and 0 < γ(t) ≤ 1, or 0 < β(t) ≤ 1 and γ(t) = 1 such that:

l(t)-1 i=1 z 1 i (t) + l(t)-1 i=1 z 2 i (t) + β(t)z 1 l(t) (t) + γ(t)z 2 l(t) (t) = 1 -α (5.40)
Proof. See appendix C.11.

Starting at time t ≥ t f , we have that at time t + T t , the thresholds l 1 (t + T t ) and l 2 (t + T t ) are less than l max . Hence, according to Proposition (5.10), there exists l(t + T t ) such that:

l(t+Tt)-1 j=1 p 1 α 1 (t + T t -j) + l(t+Tt)-1 j=1 p 2 α 2 (t + T t -j) + β(t + T t )p 1 α 1 (t + T t -l(t + T t )) + γ(t + T t )p 2 α 2 (t + T t -l(t + T t )) = 1 -α (5.41)
where β(t + T t ) = 0 and 0 ≤ γ(t + T t ) < 1, or 0 ≤ β(t + T t ) < 1 and γ(t

+ T t ) = 1.
Denoting t + T t by T 0 , we obtain:

l(T 0 )-1 j=1 p 1 α 1 (T 0 -j)+ l(T 0 )-1 j=1
p 2 α 2 (T 0 -j)+β(T 0 )p 1 α 1 (T 0 -l(T 0 ))+γ(T 0 )p 2 α 2 (T 0 -l(T 0 )) = 1-α

(5.42) where β(T 0 ) = 0 and 0 < γ(T 0 ) ≤ 1, or 0 < β(T 0 ) ≤ 1 and γ(T 0 ) = 1. Now, we prove by induction that this latter expression is valid for all T ≥ T 0 , and that l(T ), the instantaneous threshold at time T , is less than l max . Proposition 5.11. For all T ≥ T 0 , there exists l(T ) ≤ l max , β(T ) and γ(T ), such that:

l(T )-1 j=1 p 1 α 1 (T -j) + l(T )-1 j=1 p 2 α 2 (T -j) + β(T )p 1 α 1 (T -l(T )) + γ(T )p 2 α 2 (T -l(T )) = 1 -α (5.43)
where β(T ) = 0 and 0 < γ(T ) ≤ 1, or 0 < β(T ) ≤ 1 and γ(T ) = 1.

Proof. See appendix C.12.

According to the latter proposition, we can now define at each time T ≥ T 0 , for each class k, the vector

A k (T ) = (α k (T ), α k (T -1), • • • , α k (T -l(T )
)), such that, there exists β(T ) Chapter 5. Whittle's index policy for minimizing the Age of Information and γ(T ): [START_REF] Hsu | Age of information: Design and analysis of optimal scheduling algorithms[END_REF] where β(T ) = 0 and 0 < γ(T ) ≤ 1, or 0 < β(T ) ≤ 1 and γ(T ) = 1. We note that as we have explained previously, the relation between A k (T ) and z k (T ) is:

l(T )-1 j=1 p 1 α 1 (T -j) + l(T )-1 j=1 p 2 α 2 (T -j) + β(T )p 1 α 1 (T -l(T )) + γ(T )p 2 α 2 (T -l(T )) = 1 -α (5.
p k α k (T -1) = z k 1 (T ), p k α k (T -2) = z k 2 (T ), • • • , p k α k (T -l(T )) = z k l(T ) (T ).
Remark 5.5. We emphasize that in the following analysis, T is always considered greater than T 0 .

We prove in the sequel that max A k (T ) is decreasing and min A k (T ) is increasing (with the max and min referring to the element of the vector with the greatest value, and the smallest value respectively). After that, we conclude the convergence of max A k (T ) and min A k (T ) when T tends to +∞. Then, we prove that they must converge to the same real number. In order to prove that max A k (T ) is decreasing and min A k (T ) is increasing, we first demonstrate this following proposition.

Proposition 5.12. All the elements of the vector A k (T + 1) belong to the elements of the vector A k (T ) except α k (T + 1).

Proof. See appendix C.13

With the intention of proving the monotony of max A 1 (T ) and min A 1 (T ), we still need to prove that the value of α 1 (T + 1) must be less than max A 1 (T ) and greater than min A k (T ). For that, we introduce the following proposition. Before doing that, we note that, as α 1 (t) + α 2 (t) = α at each time slot t, then it is sufficient for us to prove that α 1 (•) is converging. To that extent, we study only the vector function A 1 (T ) in order to prove the convergence.

Proposition 5.13. Under assumption 5.1, for a given vector

A 1 (T ) = (α 1 (T ), α 1 (T - 1), • • • , α 1 (T -l(T )
))(T ≥ T 0 ), we have four possible cases of inequalities:

α 1 (T ) ≤ α 1 (T + 1) ≤ α 1 (T -l(T )) α 1 (T -l(T )) ≤ α 1 (T + 1) ≤ α 1 (T ) α 1 (T -l(T ) + 1) ≤ α 1 (T + 1) ≤ α 1 (T ) α 1 (T ) ≤ α 1 (T + 1) ≤ α 1 (T -l(T ) + 1)
Moreover: If α 1 (T ) ≤ α 1 (T + 1) ≤ α 1 (T -l(T )), then:

α 1 (T + 1) -α 1 (T ) ≤ p 1 (α 1 (T -l(T )) -α 1 (T ))
If α 1 (T -l(T )) ≤ α 1 (T + 1) ≤ α 1 (T ), then:

α 1 (T ) -α 1 (T + 1) ≤ p 1 (α 1 (T ) -α 1 (T -l(T )))
If α 1 (T -l(T ) + 1) ≤ α 1 (T + 1) ≤ α 1 (T ), then:

α 1 (T ) -α 1 (T + 1) ≤ p 1 (α 1 (T ) -α 1 (T -l(T ) + 1))
If α 1 (T ) ≤ α 1 (T + 1) ≤ α 1 (T -l(T ) + 1), then:

α 1 (T + 1) -α 1 (T ) ≤ p 1 (α 1 (T -l(T ) + 1) -α 1 (T ))
Proof. See appendix C.14.

Theorem 5.4. min A 1 (T ) and max A 1 (T ) converge and we denote their limits respectively by l 1 and l 2 .

Proof. According to Proposition 5.12, the elements of the vector A 1 (T +1) except the first element which is α 1 (T +1) belong to the elements of the vector A 1 (T ). Hence, the values of these elements (except the first element of A 1 (T + 1)) is less than max A 1 (T ) and greater than min A 1 (T ). According to the first result of Proposition 5.13, we deduce that α 1 (T +1) is between two values of two elements of the vector A 1 (T ). Hence, combining the results of Proposition 5.12 and 5.13, max A 1 (T + 1) ≤ max A 1 (T ) and min A 1 (T + 1) ≥ min A 1 (T ).

Then max A 1 (T ) is decreasing with T and min A 1 (T ) is increasing with T . Given that for all T , 0 ≤ α 1 (T ) ≤ α, then max A 1 (T ) and min A 1 (T ) are bounded by 0 and α. Therefore, we can conclude that min A 1 (T ) and max A 1 (T ) converge and we denote their limits by l 1 and l 2 respectively. Moreover max A 1 (T ) is lower bounded by l 2 and min A 1 (T ) is upper bounded by l 1 .

However, in order to have α 1 (T ) converges to a unique point, we need to establish that max A 1 (T ) and min A 1 (T ) converge to the same limit. In other words, we need to prove that l 1 = l 2 . For that, we will use the second result of Proposition 5.13. To that extent, we proceed by contradiction, i.e. we suppose that l 1 = l 2 . More specifically, given that l 1 ≤ l 2 by definition, the two possible cases satisfied by l 1 and l 2 are: l 1 < l 2 or l 1 = l 2 , then to show that l 1 = l 2 , it is sufficient to find a contradiction considering l 1 < l 2 .

In fact, we prove that if l 1 < l 2 , there exists T d such that all the elements of A 1 (T d ) are strictly less than l 2 , that contradicts with the fact that max A 1 (T ) is lower bounded by l 2 .

As max A 1 (T ) converges to l 2 , then for a given > 0, there exists a given time slot that we denote by T ≥ T 0 such that for all T ≥ T , max A 1 (T ) < l 2 + . Our proof consists of showing that for a small enough , there exists T ≥ T , max A 1 (T ) is strictly less than l 2 . We need first to determine an upper bound of the number of the elements of the vector A 1 (T ) whatever T . In fact, as we have demonstrated that at each time T , the instantaneous threshold l(T ) is less than l max . Then the number of the elements of A 1 (T ) will not exceed l max + 1. In the following proof, we denote l max by L.

Proposition 5.14. If l 1 < l 2 , for ≤ (l 2 -l 1 ) (1-p 1 ) L 1-(1-p 1 ) L , there exist T d ≥ T such that all the elements of A 1 (T d ) are strictly less than l 2 .

Proof. See appendix C.15.

Providing that l 2 is a lower bound of max A 1 (T ) which contradicts with the result of the above proposition. Hence, the supposition of l 1 = l 2 is not valid. Therefore, l 1 = l 2 . Consequently, max A 1 (T ) and min A 1 (T ) converge to the same limit denoted α * 1 . Given that min A 1 (T ) ≤ α 1 (T ) ≤ max A 1 (T ) for all T , then α 1 (T ) also converges to α * 1 . Similarly, α 2 (T ) converges to α -α * 1 = α * 2 . In the following proposition, we prove that z(t) converges.

Proposition 5.15. If α k (t) converges to α * k , then for each state i and class k, z k i (t) converges to z k, * i .

Proof. See appendix C.16.

However, we still have to establish that the stochastic vector Z N (t) converges to z * in probability when N scales. For that, we introduce the following proposition inspired from the discrete-time version of Kurtz Theorem in [START_REF] Kurtz | Strong approximation theorems for density dependent markov chains[END_REF]. Before that, knowing that the norms on the infinite dimension vector space are not equivalents, we work only with a specific norm which will be useful to show the optimality of the Whittle index's policy. Accordingly, we define || • || as follows:

||v|| = +∞ i=1 |v 1 i |i + +∞ i=1 |v 2 i |i (5.45)
where v k i is the i-th component in the class k of the vector v. The reason behind chosen a such norm will be revealed in the proof of Proposition 5.17. Proposition 5.16. For any µ > 0 and finite time horizon T , there exists positive constant C such that

P x ( sup 0≤t<T ||Z N (t) -z(t)|| ≥ µ) ≤ C N
where P x denotes the probability conditioned on the initial state Z N (0) = z(0) = x. Furthermore, C is independent of N .

Proof. See appendix C.17.

According to the Proposition above, the system state Z N (t) behaves very close to the fluid approximation model z(t) when the number of users N is large and starting from any initial state. To that extent, in order to establish the optimality of Whittle's index policy, we give first this following lemma which is a consequence of the Proposition 5.16.

Lemma 5.4. For any µ > 0, there exists a time T 0 such that for each T > T 0 , there exists a positive constant s with,

P x ( sup T 0 ≤t<T ||Z N (t) -z * || ≥ µ) ≤ s N Proof. See appendix C.18
We remind that starting from an initial state x, our objective is to compare the total expected average age per user under Whittle index policy which can be expressed as

1 T E wi T -1 t=0 K k=1 +∞ i=1 Z k,N i (t)i | Z N (0) =
x where Z N (t) evolves under Whittle index policy, with the optimal age of the relaxed problem per user whose expression in function of z * is,

C RP = C RP,N N = K 1 +∞ i=1 z k, *
i i, when the number of users N as well as the time duration T grow. According to Lemma 5.4, we are ready now to establish the asymptotic optimality of the Whittle index policy.

Proposition 5.17. Starting from a given initial state Z N (0) = z(0) = x, then: lim

T →+∞ lim N →∞ 1 T E wi T -1 t=0 K k=1 +∞ i=1 Z k,N i (t)i | Z N (0) = x = K k=1 +∞ i=1 z k, * i i (5.46)
Proof. See appendix C.19.

Numerical Results

Verification of Assumption 5.1

In this section, we compute the value of the lower bound on α given in Assumption 5.

Implementation of the Whittle's index policy

In this section, we evaluate the performance of the Whittle's index policy by comparing the per user average age of the Whittle's index policy to the optimal per user average age of the relaxed problem C RP,N /N . For that purpose, we consider two scenarios, when L is finite, and precisely equal to 100 and when L is infinite3 . We further consider for both scenarios that N 2 is the number of users of the class 1 and class 2 where N is the total number of users. Accordingly, γ 1 = γ 2 = 1 2 . The probability of a successful transmission of class 1 and class 2 are respectively p 1 = 0.8 and p 2 = 0.5. At each time slot t, at most, M = N 2 of users can be scheduled per each time slot, therefore α = M N = 1 2 . . These results showcase that, besides its optimality in the symmetric case as shown in [START_REF] Kadota | Scheduling policies for minimizing age of information in broadcast wireless networks[END_REF] (i.e., when p k = p for k = 1, . . . , K), the Whittle's index policy is also optimal for the general asymmetric case in the many-users regime.

Conclusion

In this paper, we have examined the average age minimization problem where only a fraction of the network users can transmit simultaneously over unreliable channels. We have provided analytical results on the local optimality of the Whittle's index policy in the many-users regime for finite L. While for infinite L, we presented and derived a novel method based on Cauchy criterion to prove the Whittle's index policy's global optimality. Numerical results were then presented that corroborate our theoretical findings and showcase the optimal performance of the policy when N grows.

Chapter 6

Conclusions and Outlook

Conclusion

In this thesis, we have focused on user scheduling frameworks that minimize the average age of information and average delay. Specifically, we have studied in Chapter 4, a scheduling problem in which one base station allocates the available channels to a subset of users in such a way to minimize the expected total average delay metric incurred in the users' queues. Based on Lagrangian relaxation approach, we derive the Whittle indices for the case where the queue size is finite and the case where the queue size is infinite. We also provide rigorous analysis to establish the asymptotic optimality of Whittle's index policy when the queue size is finite. To that extent, we prove the local asymptotic optimality using fluid approximation techniques, and the global asymptotic optimality under a recurrence assumption. To highlight the performance of Whittle's index policy, we give some numerical results that effectively affirm our theoretical findings, i.e., WIP is asymptotically optimal and in addition, it performs much better that the myopic policy.

In Chapter 5, we have examined a resource allocation problem in the context of AoI where one base station allocates the unreliable channels to a subset of users or sensors in such a way to minimize the expected total average age incurred in the sensors. Similarly to the chapter 4, we follows the Lagrangian relaxation approach to derive the Whittle's index policy for two different cases: the first one is when the age value can not exceed a certain upper bound, while the second one is when the age value can take any integer value. Our main contributions reside in showing the optimality of Whittle index policy. Indeed, we prove that WIP is asymptotically locally optimal for a system model composed of several classes when the age is bounded. Whereas, when the age is unbounded, we prove that WIP is asymptotically globally optimal for a system model composed of two classes using an original and novel method. As for numerical results, we have evaluated the performance of WIP by comparing it with the optimal solution of the relaxed problem. Our obtained simulations show that WIP is definitively optimal for a network system with high density, i.e., when the number of users and channels grows.

Future Works

For future works, there exists several scheduling problems with various system settings that can be examined for which we can derive the low-complex and the asymptotically optimal policy: WIP. In Chapter 4, we have investigated a multi-class system where the packets arrival follows an uniform distribution and the departure rate is constant over time. The model and analysis of this chapter can be extended by considering:

• General packets arrival distribution.

• Unreliable channels: the transmission rate process is a sequence of an i.i.d (independent and identically distributed) Bernoulli random variables.

Another interesting case to be examined is the Poissonian packet arrival distribution when the buffer size is infinite. The ultimate question arises when dealing with these type of scenarios is whether a closed-form expressions of Whittle indices can be obtained or not. Indeed, deriving WIP is not always feasible for any system model and requires considering assumptions on the parameters of the system. Meanwhile, for a general system model, one can at least look for an algorithm with low complexity that allows to obtain a general expressions of Whittle indices.

Regarding the method applied to prove the global asymptotic optimality of WIP in the chapter 5, one can apply it for different contexts and system models, namely the one studied in the chapter 4. Furthermore, one can extend the proof for several classes instead of two classes and where the assumption 5.

j-1 , b j , b j+1 , such that b j-1 < b j < b j+1 . 1. If a j -a j-1 b j -b j-1 ≤ a j+1 -a j b j+1 -b j Then: a j -a j-1 b j -b j-1 ≤ a j+1 -a j-1 b j+1 -b j-1 ≤ a j+1 -a j b j+1 -b j (A.8) 2. If a j -a j-1 b j -b j-1 ≥ a j+1 -a j b j+1 -b j Then: a j -a j-1 b j -b j-1 ≥ a j+1 -a j-1 b j+1 -b j-1 ≥ a j+1 -a j b j+1 -b j (A.9) 3. If a j -a j-1 b j -b j-1 ≤ a j+1 -a j-1 b j+1 -b j-1
Then:

a j -a j-1 b j -b j-1 ≤ a j+1 -a j-1 b j+1 -b j-1 ≤ a j+1 -a j b j+1 -b j (A.10) 4. If a j -a j-1 b j -b j-1 ≥ a j+1 -a j-1 b j+1 -b j-1 Then: a j -a j-1 b j -b j-1 ≥ a j+1 -a j-1 b j+1 -b j-1 ≥ a j+1 -a j b j+1 -b j (A.11) 5. If a j+1 -a j-1 b j+1 -b j-1 ≤ a j+1 -a j b j+1 -b j Then: a j -a j-1 b j -b j-1 ≤ a j+1 -a j-1 b j+1 -b j-1 ≤ a j+1 -a j b j+1 -b j (A.12) 6. If a j+1 -a j-1 b j+1 -b j-1 ≥ a j+1 -a j b j+1 -b j Then: a j -a j-1 b j -b j-1 ≥ a j+1 -a j-1 b j+1 -b j-1 ≥ a j+1 -a j b j+1 -b j (A .13)
• P (i) ⇒ P (i -1):

We have that min(i -1, n) = i -1, then:

u(i -1) = i-1 0 ρu(j) + L n+1 ρu(j) u(i -1) = i 0 ρu(j) + L n+1 ρu(j) -ρu(i) u(i -1) = u(i) -ρu(i) (B.9)
By induction assumption, we have that u(i) = ρ(1 -ρ) n-i . To that extent, replacing the expression of u(i) in (B.9), we obtain:

u(i -1) = (1 -ρ)u(i) = ρ(1 -ρ) n-(i-1)
That concludes the proof.

As for i = L, u(L) is nothing but the subtraction of the L-1 j=0 u(j) from 1. By doing so, we get:

u(L) = (1 -ρ) n+1 -(L -n -1)ρ 2. n = L: u(i) = L j=0 p L (j, i)u(j) (B. 10
)
For i ≤ L -1:

According to Proposition 4.1, we have:

u(i) = L j=0 π i-j u(j) (B.11)
By definition of π, we get:

u(i) = i 0 ρu(j) (B.12)
We prove by induction that for 0 ≤ i < L, u(i) = 0

We have u(0) = ρu(0) = 0. We suppose that u(j) = 0 for all 0 ≤ j ≤ i, then:

u(i + 1) = i+1 0 ρu(j) (B.13) = i 0 ρu(j) + ρu(i + 1) (B.14) = 0 + ρu(i + 1) (B.15) u(i + 1) = 0 (B.16)
Then, for all i ∈ [0, L -1], u(i) = 0. Since L j=0 u(j) = 1, we have u(L) = 1 -L-1 j=0 u(j) = 1 -0 = 1. This ends the proof.

Proof. We have for all n ∈ [0, L -1]:

x n+1,n -x n,n-1 = W (n + 1) -W (n) = aρ 2 (L -n) ρ(1 -ρ) n+1 > 0 That concludes the proof. Lemma B.2. If for any k ∈ [0, L -1], we have that: b k-1 < b k < b k+1 and a k -a k-1 b k -b k-1 < a k+1 -a k b k+1 -b k . Then for any k ∈ [0, L -1], we have for each k < s ≤ L: a s -a k-1 b s -b k-1 > a k -a k-1 b k -b k-1 (B.23)
Proof. We fix certain k ∈ [0, L -1], we prove the result by induction:

for s = k + 1 a k+1 -a k-1 b k+1 -b k-1 = a k+1 -a k-1 -a k + a k b k+1 -b k-1 (B.24) = a k+1 -a k b k+1 -b k-1 + a k -a k-1 b k+1 -b k-1 (B.25) > (a k -a k-1 )(b k+1 -b k ) (b k -b k-1 )(b k+1 -b k-1 ) + (a k -a k-1 )(b k -b k-1 ) (b k -b k-1 )(b k+1 -b k-1 ) (B.26)
where the strict inequality comes from the lemma's assumptions. Therefore, we have that:

a k+1 -a k-1 b k+1 -b k-1 > a k -a k-1 b k -b k-1 [ b k+1 -b k b k+1 -b k-1 + b k -b k-1 b k+1 -b k-1 ] (B.27) = a k -a k-1 b k -b k-1 (B.28)
By induction, we consider that the inequality (B.23) is true for certain s strictly higher than k. The inequality below is then verified for s + 1:

a s+1 -a k-1 b s+1 -b k-1 = a s+1 -a k-1 -a s + a s b s+1 -b k-1 (B.29) = a s+1 -a s b s+1 -b k-1 + a s -a k-1 b s+1 -b k-1 (B.30) > (a k -a k-1 )(b s+1 -b s ) (b k -b k-1 )(b s+1 -b k-1 ) + (a k -a k-1 )(b s -b k-1 ) (b k -b k-1 )(b s+1 -b k-1 ) (B.31) = a k -a k-1 b k -b k-1 [ b s+1 -b s b s+1 -b k-1 + b s -b k-1 b s+1 -b k-1 ] (B.32) = a k -a k-1 b k -b k-1 . (B.33)
So the inequality is also true for s + 1. This concludes the proof of the lemma.

Referring to Algorithm 1 that allows us to obtain the Whittle indices, we denote by j the step j described in the algorithm.

According to the same algorithm, to establish that x j,j-1 is the Whittle's index at the First of all, we give the order of the Whittle indices given by Theorem 4.4, when β > 1 -min{a j R j } max{a j R 2 j } . Due to the indexability of all classes, it's obvious that the Whittle index is increasing with n for a given class k. Moreover, considering any two classes k and m, then, the Whittle index of any state n k in class k and greater than R k is larger than the Whittle index of any state n m in class m less than R m . In fact we have β > 1 -

min{a j R j } max{a j R 2 j } , that means 1 -β < min{a j R j } max{a j R 2 j } . Hence, 1 1-β > max{a j R 2 j } min{a j R j } . Then, W k (n k ) = a k R k 1-β > a k R k max{a j R 2 j } min{a j R j } ≥ max{a j R 2 j } ≥ a m R 2 m ≥ a m R m (R m -1) ≥ βa m R m (R m -1) ≥ βamRm(Rm-1) Rm-β(Rm-1) (because R m -β(R m -1) ≥ 1) = W m (R m -1) ≥ W m (n m ).
For the new form of Whittle index where we get rid of β for states greater than maximum transmission rate, the order is not affected for the states less than R k -1, since the Whittle indices are the same. For the states greater than R k , the Whittle index

a k R k max{a j R 2 j } is higher than a k R k a m R m (R m -1) ≥ a m R m (R m -1) ≥ βamRm(Rm-1)
Rm-β(Rm-1) = W m (R m -1). Furthermore, the order between the Whittle indices greater than the transmission rate doesn't change since we just multiply by a constant which is

1-β max{a j R 2 j } to go from a k R k 1-β to a k R k max{a j R 2 j }.
Hence, the order of these new expressions of Whittle indices is not affected. That means, by adopting this policy, we end up with the same Whittle index policy in Theorem 4.4.

B.11 Proof of Proposition 4.7

In order to prove this proposition, we distinguish between two types of classes: 1) Class k in which W is different from all W k i . 2) Class k such that there exists a given state j that satisfies W k j = W . First type of classes: For the class k in which W is different from all W k i , we prove that the optimal threshold verifies l k

(W ) = l k = arg max i {W k i |W k i ≤ W } = arg max i {W k i )|W k i < W }. First we have arg max i {W k i |W k i ≤ W } = arg max i {W k i )|W k i < W } since W k i is dif- ferent from W for all state i. For state i less than l k , given that W k i is increasing with i, then W k i ≤ W k l k < W .
Hence, due to the indexability of the class, D(W k i ) ⊆ D(W ), which implies that the optimal decision at state i is the passive action. For the state i strictly greater than l k , by definition of l k , W k i must be strictly greater than W since l k is the integer that gives the highest Whittle index less than W . Then, according to the definition of Whittle index, W < min{W, i ∈ D(W )}, that means W ∈ {W, i ∈ D(W )}. Therefore i ∈ D(W ). Thus, the optimal decision at state i > l k is the active decision. Hence

l k = arg max i {W k i |W k i ≤ W } = arg max i {W k i )|W k i < W } is effectively the optimal threshold l k (W ).
Now, we tackle the case when there exists j, W k j = W : We know that according to Theorem 4.3, W k j = x k j,j-1 which is the point for which if W = x k j,j-1 , we have L q=0 a k u j k (q)q -W j q=0 u j k (q) = L q=0 a k u j-1 k (q)q -W j-1 q=0 u j-1 k (q). That means, according to Equation (4.47), for W = x k j,j-1 , if j is a minimizer of this equation (j is the optimal threshold), then j -1 is also a minimizer of this equation. Due to the indexability of the class k, for all states less or equal than j, the optimal decision is to stay passive. Besides, according to the definition of Whittle index, for all states strictly higher than j, the optimal decision is to be active. Then, j is indeed an optimal threshold, so as for j -1. Hence, the optimal threshold can be either j or j -1. In fact, since

W k 0 < • • • < W k j-1 < W k j = W , then j = arg max i {W k i |W k i ≤ W }, and j -1 = arg max i {W k i |W k i < W }.
This proves the proposition.

B.12 Proof of Proposition 4.8

From optimization theory, it is known that the optimal solution of the dual problem is less or equal than the primal problem's solution when the constraint is satisfied, i.e:

max W min φ∈Φ f (W, φ) ≤ min φ∈Φ lim sup T →∞ 1 T E T -1 t=0 K k=1 γ k N i=1 a k q k i (t) | q(0), φ (B.60)
As the optimal solution for a fixed W is a threshold-based policy, we use the steady state form and the expression of the LHS of the above inequality becomes:

max W min φ f (W, φ) = max W { K k=1 γ k N i=1 [ min l k ∈[-1,L] { L q=0 a k u l k k (q)q -W l k q=0 u l k k (q)}] + W (1 -α)N } (B.
61) with φ being the threshold policy that corresponds to l(W ) computed using Proposition 4.7 for a fixed W . For W * that satisfies the constraint with equality (i.e. αN =

K k=1 γ k N L i=l k+1 (W * ) u l k (W * ) k (i),
which is in fact true for all N , and then we can get rid of N ), we have:

K k=1 γ k N i=1 [-W l k (W * ) q=0 u l k (W * ) k (q)] + W (1 -α)N = K k=1 γ k N [-W (1 - L i=l k+1 (W * ) u l k (W * ) k (i))] + W (1 -α)N = -N W + K k=1 γ k N W L i=l k+1 (W * ) u l k (W * ) k (i) + W (1 -α)N = -N W + αN + W N -αN = 0. Hence, we get: min φ f (W * , φ) = f (W * , l(W * )) = K k=1 γ k N i=1 [ L q=0 a k u l k (W * ) k (q)q] = lim sup T →∞ 1 T E T -1 t=0 K k=1 γ k N i=1 a k q k i (t) | q(0), l(W * ) (B.62)
Therefore, we obtain a threshold vector l(W * ) that gives us a solution for the constrained relaxed problem (primal problem) that satisfies the constraint (4.3). Moreover, according to the inequality (B.60), we have that for all policy φ that satisfies the constraint and belong to Φ:

f (W * , l(W * )) = K k=1 γ k N i=1 [ L q=0 a k u l k (W * ) k (q)q] = lim sup T →∞ 1 T E T -1 t=0 K k=1 γ k N i=1 a k q k i (t) | q(0), l(W * ) =min φ f (W * , φ) ≤max W min φ f (W, φ) ≤min φ lim sup T →∞ 1 T E T -1 t=0 K k=1 γ k N i=1 a k q k i (t) | q(0), φ . (B.63)
We deduce that the solution of the relaxed problem is of type threshold-based policy l(W * ) with

W * satisfies α = K k=1 γ k L i=l k+1 (W * ) u l k (W * ) k (i).
B.13 Proof of Proposition 4.9

We define the following order relation in R K such that for any two vectors l 1 and l 2 , l 1 ≤ l 2 ⇐⇒ for each element of vector of index k, we have l 1 k ≤ l 2 k . Recall that according to Proposition 4.7, we can directly deduce that for W 1 ≤ W 2 l(W 1 ) ≤ l(W 2 ). Without loss of generality, when W ∈ R + , the corresponding set of threshold vectors l(W ) is perfectly ordered. Then, K k=1 γ k L i=l k (W )+1 u l k (W ) k (i) is strictly decreasing in l(W ), and take discrete values from 1 to 0. According to Proposition 4.7, we have for each class k and state i, if W = W k i then there is two possible optimal thresholds vectors l 1 (W ) and l 2 (W ) with l 1 (W ) < l 2 (W ). Hence we can deduce that there exists a class m and state p such that

K k=1 γ k L i=l 1 k (W m p )+1 u l 1 k (W m p ) k (i) ≥ α and K k=1 γ k L i=l 2 k (W m p )+1 u l 2 k (W m p ) k (i) ≤ α. According to Proposition 4.7, when W = W m p , l m (W m p ) = l 2 m (W m p ) and l 1 m (W m p ) = l 2 m (W m p ) -1 = l m (W m p ) - 1
can be both the optimal thresholds for class m. As for the other classes,

l 1 k (W m p ) = l 2 k (W m p ) = l k (W m p
). If we force W * to be equal to W m p , the optimal threshold vector can be either l 1 (W m p ) or l 2 (W m p ), then we can introduce some randomization between the two policies. In other words, we use the threshold policy l 1 (W m p ) with probability θ and l 2 (W m p ) with probability 1 -θ. The new stationary distribution for the class m is then a linear combination of these two threshold policies l m (W m p ) and l m (W m p ) -1:

u * m = θu lm(W m p ) m + (1 -θ)u lm(W m p )-1 m .
Hence, in the class m, at state strictly less than l m (W m p ), the queues will not transmit, whereas in a state strictly greater than l m (W m p ), they will transmit with probability one. If the queues are in state l m (W m p ), they will transmit with probability . Since the probability to be in this state l m (W m p ) is u * m (l m (W m p )), the proportion of time that the queues will be in active mode is: When θ = 0, the threshold policy is l m (W m p )-1 and the total average time in active mode is higher than α. When θ = 1, the threshold policy is l m (W m p ) and the total average time in active mode is less than α. Given that k =m (l m (W m p )) is continuous with θ, then there exists θ * which verifies the equality. Hence, for W * = W m p , we get a threshold policy for all classes except for class m where the optimal solution is a linear combination of two threshold policies. Moreover for a given randomized parameter θ * , the constraint (4.3) is satisfied with equality:

k =m L i=l k (W m p )+1
α = k =m L i=l k (W m p )+1 γ k u l k (W m p ) k (i) + L i=lm(W m p )+1 γ m u * m (i) + (1 -θ * )γ m u lm(W m p )-1 m (l m (W m p ))
B.14 Proof of Proposition 4.10

We derive the eigenvalues of Q.

The matrix Q is of the form:

           Q 1 0 • • • • • • • • • • • • 0 0 Q 2 • • • • • • • • • • • • 0 . . . . . . A 1 A 2 • • • Q m • • • A K-1 A K . . . . . . . . . 0 0 • • • • • • • • • Q K-1 0 0 0 • • • • • • • • • 0 Q K            (B.64)
The characteristic polynomial of Q is the product of the characteristic polynomial of each matrix Q k :

χ Q (λ) = K k=1 χ Q k (λ) (B.65)
Therefore, the set of Q's eigenvalues denoted by Sp(Q) is composed by the eigenvalues of the matrices Q k . Specifically:

Sp(Q) = ∪ k Sp(Q) .
1)The case k = m:

Q k = 0 1 • • • l k -2 l k -1 l k + 1 l k + 2 • • • L -1 L                                 0 ρ k 0 • • • 0 0 ρ k • • • • • • ρ k ρ k 1 ρ k ρ k . . . 0 0 ρ k • • • • • • ρ k ρ k . .
l k -1 ρ k • • • • • • ρ k ρ k ρ k • • • • • • ρ k ρ k l k + 1 0 • • • • • • 0 0 0 • • • • • • 0 0 . . . . . . 0
L -1 0 • • • • • • 0 0 0 • • • • • • 0 0 L -l k ρ k (1 -l k )ρ k • • • -2ρ k -ρ k -l k ρ k • • • • • • -l k ρ k -l k ρ k
After computations and some algebraic manipulations, we get, χ Q k (λ) = (-λ) L

2)The case k = m:

Q m = 0 1 • • • l m -2 l m -1 l m + 1 l m + 2 • • • L -1 L                                 0 ρ m 0 • • • 0 0 0 • • • • • • 0 0 1 ρ m ρ m . . . 0 0 0 • • • • • • 0 0 . .
l m -1 ρ m • • • • • • ρ m ρ m 0 • • • • • • 0 0 l m + 1 0 • • • • • • 0 0 0 • • • • • • 0 0 . . . . . . 0 0 . . . . . . . . . 0 0 . . . . . . L -1 0 • • • • • • 0 0 0 • • • • • • 0 0 L -l m ρ m (1 -l m )ρ m • • • -2ρ m -ρ m 0 • • • • • • 0 0
After computations and some algebraic manipulations, we get: χ Qm (λ) = (-λ) L-lm (ρ m -λ) lm For k = m, Q k has only 0 as eigenvalue.

For k = m, χ Qm (λ) = 0 ⇔ λ = 0 or λ = ρ m . Hence, Q m has two eigenvalues: 0 and ρ m which are strictly less than 1.

Consequently, in both cases, the norms of all eigenvalues of Q k are strictly less than 1.

Hence, for λ ∈ Sp(Q) ⇒ |λ| < 1.

B.15 Proof of Lemma 4.6

We take 0 < < µ, z(t) converges to z * , i.e. there exists T 0 such that for all t ≥ T 0 , ||z(t) -z * || ≤ . Hence: We recall that Z N (t) represents the proportion vector at time t under Whittle's Index policy.

P x (
Replacing C RP,N by its expression given in Section 4. B.17 Proof of Lemma 4.7

We consider any initial state (z 1 , z 2 , • • • , z K ), and we consider only the following possible event (that arises with strictly positive probability): whatever the transmission decision taken, there is no arrivals for all classes up to time T = 1 α (A k (t) = 0 from t = 0 up till T = 1 α for all 1 ≤ k ≤ K). To that extent, we show that at time T , we reach the state z 0 . For that purpose, we divide the queues into 1 α groups denoted by G 1 , • • • , G α such that G k contains a proportion α of queues with the highest Whittle indices among all queues of the system excluding those of the groups G 1 , G 2 , • • • , G k-1 at time t = 0. Based on this, at time slot t = 0, the queues in G 1 will be scheduled and will transit to state 0 as the number of arrival packets is equal to 0. According to the expressions given in Proposition 4.3, the Whittle index of state 0 is equal to 0 whatever the value of the class. While according to the same Proposition, the Whittle index of state n strictly higher than 0 is strictly greater than 0 for any class k. Therefore, regardless of the class, The Whittle index of state n strictly higher than 0 is greater than that of 0. Bearing that in mind, at time slot t = 1, the queues in G 2 at state different than 0 have the highest Whittle's indices among all system's queues. Therefore, these aforementioned queues will be scheduled, and subsequently, all queues in G 2 will be at state 0. In this way, at time slot 1 α , we get all the queues of the system in state 0. Consequently, at time T = 1 α , we attain the desired state which is z 0 . That concludes the proof. We have the function f : z → K k=1 L i=0 a k z k i i is lipchitz and continuous, then for an arbitrary small , there exists µ such that if ||z -z * || < µ, then |f (z) -f (z * )| < . We denote U N the event sup||Z N (∞) -z * || ≥ µ, then : i and column j of the matrix Q k . For i = 2 till l * k -2, we add to each row the previous row multiplied by 1 λ . In other words:

K k=1 L i=0 a k E Z k,N i (∞) i - K k=1 L i=0 a k z k, * i i ≤P (U N )E K k=1 L i=0 (a k Z k,N i (∞)i) -a k z k, * i i U N + (1 -P (U N ))E K k=1 L i=0 (a k Z k,N i (∞)i) -a k z k, * i i U N ≤L(L + 1)
l m -1 0 • • • 0 1 0 0 0 • • • • • • 0 l m + 1 -1 • • • • • • • • • -1 p m -1 • • • • • • • • • p m -1 l m + 2 0 0 • • • • • • 0
r i = r i-1 λ + r i i = 2, . . . , l * k -2 (C.16)
Note that these operations are not done simultaneously but rather successively. In other words, in the increasing order of the rows, and at each iteration i, we add to r i the updated row r i-1 at iteration i -1 multiplied by 1 λ . After doing so, we execute the following operation in order to have zeros for the elements a l * k ,1 to a l * k ,l * k -2 :

r l * k = - l * k -2 i=1 r i λ + r l * k (C.17)
As a result, χ Q k (λ) will be the determinant of the matrix G reported in the same table. Since G is an upper triangular block matrix, we will not be interested in the expression By employing standard real functions analysis, it can be shown that the polynomial:

1 2 • • • l * k -3 l * k -2 l * k l * k + 1 • • • L -1 L 1 -λ 0 • • • 0 0 p k p k • • • • • • p k 2
l * k -2 0 • • • 0 1 -λ 0 0 • • • • • • 0 l * k -1 • • • • • • • • • -1 -1 -λ • • • • • • • • • -1 l * k + 1 0 0 • • • • • • 0 1 -p k -λ 0
L 0 • • • • • • • • • 0 0 0 0 1 -p k 1 -p k -λ G =                        -λ 0 • • • 0 0 0 -λ . . .
0 • • • 0 0 -λ B 0 -λ -1 -1 λ l * k -2 i=0 p k λ i -1 -1 λ l * k -2 i=0 p k λ i • • • • • • • • • -1 -1 λ l * k -2 i=0 p k λ i 1 -p k -λ 0 • • • • • • 0
x 2 -(1 -p k )x -p k (C.25)
is negative if and only if x ∈ [-p k , 1]. However, |λ| ≥ 1 by assumption. Accordingly, |λ| can only be equal to 1. Next, we prove that, in this case, the imaginary part of λ is equal to zero. To that end, let us consider λ = x + iy. Therefore, we have:

p k = |λ| l * k -1 |p k -1 + x + iy| = |p k -1 + x + iy| (C.26)
By using the definition of the modulus, and by squaring both sides, we get:

p 2 k = (1 -x -p k ) 2 + y 2 (C.27)
Knowing that x 2 + y 2 = 1, we can deduce:

2 -2p k 2(1 -p k ) = x (C.28)
Hence, x = 1, i.e. y = 0, and we can deduce that λ = 1. However, 1 is not eigenvalue of matrix Q k . This can be seen by replacing λ with 1 in the characteristic polynomial of Q k . Accordingly, the hypothesis that |λ| ≥ 1 fails and all the eigenvalues of Q k for any k = m have a modulus strictly less than 1.

k = m

The characteristic polynomial of the matrix Q m is reported in Table C.3. We follow the same steps of the previous case. For i = 2 till l * m -1, we sequentially add to each row, the previous row multiplied by 1 λ . In other words: (C.30)

r i = r i-1 λ + r i i =
1 2 • • • l * m -2 l * m -1 l * m + 1 l * m + 2 • • • L -1 L 1 -λ 0 • • • 0 0 0 0 • • • • • • 0 2 1 -λ . . . 0
l * m -1 0 • • • 0 1 -λ 0 0 • • • • • • 0 l * m + 1 -1 • • • • • • • • • -1 p m -1 -λ • • • • • • • • • p m -1 l * m + 2 0 0 • • • • • • 0 1 -p m -λ 0
L 0 • • • • • • • • • 0 0 0 0 1 -p m 1 -p m -λ H =                       -λ 0 • • • 0 0 0 -λ . . .
0 • • • • • • • • • 1 -p m 1 -p m -λ                      
Table C.3 -The expressions of the characteristic polynomials of Q m

As a result, χ Qm (λ) will be the determinant of the matrix H reported in the same table.

By replacing 1 -p m with A, the determinant of H will be equal to (-λ) l * m -1 multiplied by the following determinant:

-λ -A -A • • • • • • • • • -A 1 -p m -λ 0 • • • • • • 0

Titre:

  Les schémas d'ordonnancement asymptotiquement optimaux pour les grands réseaux Mots clés: allocation des resources, Temps d'attente, Age de l'information, indice de Whittle, Relaxation Lagrangian, optimalité asymptotique

Figure 1 . 1 -

 11 Figure 1.1 -Illustration du temps d'attente et du délai de propagation

Figure 1 . 2 -

 12 Figure 1.2 -Modèle de files d'attente

Figure 1 . 3 -

 13 Figure 1.3 -Illustration de l'évolution de l'AdI

Figure 1 . 4 -Figure 1 . 5 -

 1415 Figure 1.4 -Illustration de l'évolution de l'AdI adaptée au problème d'ordonnancement étudié

Figure 2 . 1 -

 21 Figure 2.1 -Illustration of Queuing and Propagation Delay

Figure 2 . 2 -

 22 Figure 2.2 -Queuing System Model

Figure 2 . 4 -

 24 Figure 2.4 -Illustration of the AoI evolution adapted to the scheduling problem of interest

Figure 2 . 5 -

 25 Figure 2.5 -Age system model

Chapter 4 .

 4 Whittle's index policy for minimizing the Delay in Queuing systems Chapter 4 Whittle's index policy for minimizing the Delay in Queuing systems

Figure 4 .

 4 Figure 4.1 -System Model

Theorem 4 . 1 .

 41 min s T O(•)(•, s) conserves the R-convexity and the increase properties. In other words, if the input of the operator TO, i.e. a given V (•), is R-convex and increasing function with q then min s T O(V )(•, s) is R-convex and increasing function with q.

Figure 4 . 2 -

 42 Figure 4.2y n (W ) in function of W for different values of n (L = 5 and R = 10): W (i) indicates the Whittle index at state i

Chapter 4 .

 4 Whittle's index policy for minimizing the Delay in Queuing systems

Figure 4 . 3 -

 43 Figure 4.3 -Hitting Time of Ω (z * ) in function of N : (a) Z N (0) = x, (b) Z N (0) = y

Figure 4 . 4 -

 44 Figure 4.4 -Performance evaluation of Whittle's Index policy

  4.a) and (4.4.b) respectively for the initial states x and y (defined above).

1 and C π,N 2 incurred

 12 respectively by users of class 1 and users of class 2 under policy π, specifically C π,N 1

  (4.6.a), we take R 1 = 5 and R 2 = 20, while in Figure (4.6.b), the values of R 1 and R 2 are respectively 10 and 45.

Figure 4 . 5 -

 45 Figure 4.5 -Evaluation of C π,N 1

Figure 4 . 6 -

 46 Figure 4.6 -Performance evaluation of Whittle's Index policy

Figure 5 . 1 -Figure 5 . 2 -

 5152 Figure 5.1 -The states transitions under a threshold policy n when L < +∞

Chapter 5 .

 5 Whittle's index policy for minimizing the Age of Information (a) n ∈ [0, L]:

Figure 5 . 3 -

 53 Figure 5.3 -Evolution of z k i (•) for different states i in function of α 1 (t) and α 2 (t) under the Whittle Index Policy (the green and the yellow colors refer to class 1 and 2 respectively)

Figure 5 . 8 -

 58 Figure 5.8 -Average age per user under Whittle Index Policy

N

  k=1 V k (s k ) and θ = N k=1 θ k . This is equivalent to find for each user the decision that minimizes the right hand side of each individual Bellman equation. This concludes the proof.A.2 Proof of Proposition 3.2Before proving the proposition, we give two useful lemmas.Lemma A.1. Considering a j-1 , a j , a j+1 and b

  γ k u l k (W m p ) k (i) + L i=lm(W m p )+1 γ m u * m (i) + (1 -θ)γ m u lm(W m p )-1 m (l m (W m p ))

L

  i=l k (W m p )+1 γ k u l k (W m p ) k (i)+ L i=lm(W m p )+1 γ m u * m (i)+(1-θ)γ m u lm(W m p )-1 m

  5 and knowing that z k, * i = γ k u l k k (i) for k = m and z m, * i = γ m u * m (i) = θ * γ m u lm m (i) + (1 -θ * )γ m u lm-1 m(i) (by definition of z * ), then the difference between C N T (x) and C RP,N can be expressed as:C N T (x) -C RP,N i) -a k z k, * i i (B.72)We have that the function f : z → K k=1 L i=0 a k z k i i is lipchitz and continuous, then for an arbitrary small , there existsµ such that if |z -z * || < µ, then |f (z) -f (z * )| < . Queuing systemWe denote Y N the event supT 0 ≤t<T ||Z N (t) -z * || ≥ µ, we proceed to bound the second term: k Z k,N i (t)i) -a k z k, * i i ≤P x (Y N ) i) -a k z k, * i i Y N + (1 -P x (Y N )i) -a k z k, * i i Y N ≤ (T -T 0 )L(L + 1) T K k=1 a k γ k P x (Y N ) + (1 -P x (Y N )) . (B.73)where the above inequality comes from the fact that |a k Z k,N i (t)i -a k z k, * i i| ≤ 2γ k a k i. According to Lemma 5.4, we have lim N →∞ P x (Y N ) = 0, then:

a

  k γ k P (U N ) + (1 -P (U N )) (B.78)According to Lemma 4.9, we have lim N →∞ P (U N ) = 0, then: This is true for any . Finally we have:

1 -

 1 p m 1 -p m Table C.1 -The expressions of the matrices Q k for k = m and Q m

  k = |λ| l * k -1 |p k -1 + λ| ≥ (a) |λ| l * k -1 (|λ| -|1 -p k |) ≥ (b) |λ|(|λ| -|1 -p k |) = |λ| 2 -|λ|(1 -p k )where (a) and (b) originate from the reverse triangular inequality and the fact that |λ| ≥ 1 respectively. Hence:|λ| 2 -|λ|(1 -p k ) -p k ≤ 0 (C.24)

2 , 1 (C. 29 )

 2129 . . . , l * m -Then, we execute the following operation in order to have zeros for the elements a l * m +1,1 to a l * m +1,l * m -1 :r l * m +1 = -l * m -1 i=1 r i λ + r l * m +1

1 +

 1 p m -1 + p m • • • • •

EET 0

 0 • • • • • • 1 -p m 1 -p m -λTherefore, we end up with the same determinant S k defined previously but with A = 1 -p m . Fortunately, we have already computed this determinant for any k and regardlessT wi Z k,N i (t)i -z k, * i i Z N (0) = x (C.228)We start by bounding (C.227). We have that:As m k (.) is increasing with t, then denoting m(t) = max{m 1 (t), m 2 (t)}, we get:T 0 ) + C RP )T 0 T (C.232)We denote Y N the event supT 0 ≤t<T||Z N (t) -z * || ≥ µ, and we proceed to bound the second i -z k, * i i Y N , Z N (0) = x (C.233) + (1 -P x (Y N )i -z k, * i i Y N , Z N (0) = x (C.234) ≤ (a) (T -T 0 )(m(T ) + C RP ) T P x (Y N ) + (1 -P x (Y N ))µ (C.235)where (a) results from:wi Z k,N i (t)i -z k, * i i Y N , Z N (0) = x i -z k, * i i| Y N , Z N (0) = x (C.236) = E wi sup T 0 ≤t<T ||Z N (t) -z * || Y N , Z N (0) = x < µ (C.237) According to Lemma 5.4, we have lim N →∞ P x (Y N ) = 0. Thus, combining the result (C.232) and (C.235), we obtain: (m(T 0 ) + C RP ) T + µ (C.238) This inequality is true for all µ > 0, then: i Z N (0) = x = K k=1 +∞ i=1 z k, * i i (C.241)

  Chapter 1. Introduction en français pertinente et optimale de minimiser autant que possible l'énergie consommée par les capteurs est de produire des paquets uniquement à la demande du moniteur, c'est-à-dire lorsque celui-ci alloue le canal au capteur en question. Cela conduit également à réduire l'AdI moyen, puisque le délai entre la génération et la réception du paquet transportant l'information sur le processus d'intérêt est limité uniquement au délai encouru dans la file du canal. De plus, en supposant qu'il n'y a pas de délai supplémentaire causé par le canal, à l'exception de celui de la propagation du signal qui est normalisé à un, alors s i et d i qui désignent le temps de génération et le temps de livraison du i-ième paquet de mise à jour reçu avec succès par le moniteur respectivement, vérifient :

respectivement le temps de génération du i-ième paquet de mise à jour de l'information en question et son temps de livraison au moniteur. D'après cette définition, on peut remarquer qu'effectivement δ(t) capture bien la notion de fraîcheur puisqu'une petite valeur de δ(t) signifie que le moniteur possède une mise à jour récente, et si δ(t) est grand, le moniteur possède une mise à jour obsolète. Ces mises à jour peuvent être générées soit à la volonté de la source-capteur, soit spontanément en fonction des facteurs externes tels que les changements climatiques ou les variations de vitesse. Dans cette mesure, en considérant le cadre du problème d'ordonnancement, dans le scénario où la source distante peut générer des mises à jour à n'importe quel moment, il semble que pour éviter une perte inutile d'énergie, la source ou le capteur ne devrait pas générer de mise à jour s'il n'est pas autorisé à transmettre. Par conséquent, la manière

  Chapter 1. Introduction en français formance, notamment les délais de bout en bout. Dans cette optique,[START_REF] Rajan | Delay-bounded packet scheduling of bursty traffic over wireless channels[END_REF] étudie la transmission à puissance minimale sur des canaux sans fil avec des contraintes sur le temps d'attente moyen. Ils proposent un ordonnanceur à faible complexité qui a une performance quasi-optimale. Concernant l'énergie qui permet à une machine de rester active, qu'elle soit en mode transmission ou en mode veille, on peut considérer que la meilleure façon d'économiser cette énergie consommée est d'éteindre les machines. Cependant, la transition entre les modes actif et passive consomme une énergie considérable et augmente le délai.[START_REF] Andrews | Routing and scheduling for energy and delay minimization in the powerdown model[END_REF] étudie ce problème dans un réseau multi-sauts et propose pour une topologie de ligne ainsi que pour une topologie arbitraire, une politique d'ordonnancement qui est quasi-optimale en ce qui concerne la métrique du délai pour une période active minimale par élément du réseau.

	Plusieurs travaux ont étudié les problèmes d'ordonnancement pour minimiser la métrique
	de temps d'attente(par exemple : [7-12]). Dans la suite, nous citons quelques travaux
	pertinents dans ce domaine particulier.

1.4.1 Problème d'ordonnancement: Minimisation du temps d'attente

Ordonnancement tenant compte de l'énergie L'économie d'énergie fait l'objet d'une grande attention dans les réseaux 5G. Cependant, nous savons qu'il existe un compromis entre l'économie d'énergie et les garanties de per-

Algorithmes d'apprentissage stochastiques

Un nombre important de travaux dans la littérature développent des stratégies d'allocation à l'aide d'algorithmes d'apprentissage stochastiques

[START_REF] Cui | Distributive stochastic learning for delay-optimal ofdma power and subband allocation[END_REF][START_REF] Cui | A survey on delay-aware resource control for wireless systems-large deviation theory, stochastic lyapunov drift, and distributed stochastic learning[END_REF][START_REF] Zheng | Delay-optimal virtualized radio resource scheduling in software-defined vehicular networks via stochastic learning[END_REF][START_REF] Wang | Delay-aware two-hop cooperative relay communications via approximate mdp and stochastic learning[END_REF][START_REF] Ruan | Delay-aware massive random access for machine-type communications via hierarchical stochastic learning[END_REF][START_REF] Li | Resource allocation optimization for delay-sensitive traffic in fronthaul constrained cloud radio access networks[END_REF][START_REF] Lei | Delay-optimal dynamic mode selection and resource allocation in device-to-device communications-part ii: Practical algorithm[END_REF]

afin d'optimiser le temps d'attente dans les files des utilisateurs dans le contexte de problèmes d'ordonnancement. Cependant, les cadres des processus de décision de Markov (PDM) souffrent du fléau de la dimensionnalité, ce qui conduit à des stratégies d'allocation des ressources complexes. Par exemple,

[START_REF] Zhang | Resource scheduling for delay minimization in multi-server cellular edge computing systems[END_REF]

étudie l'ordonnancement des ressources pour la minimisation du temps d'attente dans les systèmes informatiques cellulaires multi-serveurs en périphérie de réseau. Les auteurs proposent une solution basée sur une nouvelle fonction de Lyapunov appelée fonction de Lyapunov basée sur le temps d'attente. Plus précisément, ils conçoivent un algorithme d'ordonnancement basé sur cette nouvelle fonction afin de dériver une solution approximative qui minimise à la fois la file d'attente et le délai de propagation. Ils établissent ensuite que l'algorithme proposé donne de bonnes performances par rapport à l'algorithme d'ordonnancement traditionnel basé sur la méthode de Lyapunov. Cependant, l'algorithme dérivé reste sous optimal et sa complexité est considérablement élevée.

  Chapter 1. Introduction en français un problème d'allocation de ressources dans lequel une station de base alloue M canaux à N files d'attente d'utilisateurs à chaque instant en fonction de la politique d'ordonnancement considérée. Les files d'attente évoluent selon un processus de Markov. En outre, les utilisateurs ou les files d'attente 1 sont divisés en classes en fonction des paramètres du système, à savoir le taux d'arrivée des paquets et le taux de transmission des paquets, qui diffèrent d'une classe à l'autre. Notre objectif est de trouver la politique adéquate qui minimise la longueur moyenne totale attendue de la file d'attente de tous les utilisateurs sur le long terme. Le problème susmentionné peut être considéré comme un problème de bandit sans repos dont la solution est connue pour être inaccessible. Pour cela, nous appliquons la politique peu complexe et très performante, la politique de l'indice de Whittle (WIP) à notre modèle spécifique. Nous pouvons résumer nos contributions en deux points :

	Chapter 2. Introduction
	Chapter 2
	Introduction

• Chapitre 4: Contrairement à

[START_REF] Ansell | Whittle index policy for a multi-class queueing system with convex holding costs[END_REF][START_REF] Weber | On an index policy for restless bandits[END_REF][START_REF] Larrañaga | Dynamic control of birth-and-death restless bandits: Application to resource-allocation problems[END_REF][START_REF] Van Mieghem | Dynamic scheduling with convex delay costs: The generalized c| mu rule[END_REF][START_REF] Mandelbaum | Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cµ-rule[END_REF]

, nous abordons dans ce chapitre un problème d'ordonnancement en considérant un modèle en temps discret. Plus précisément, nous étudions le problème de minimisation de temps d'attente dans un modèle de système de file d'attente en temps discret. Dans cette mesure, nous étudions -Nous dérivons la politique de l'indice de Whittle pour deux scénarios : files d'attente de taille infinie, et files d'attente de taille restreinte (inférieure au taux de transmission).

-Nous établissons l'optimalité locale et globale du WIP dans le régime asymptotique lorsque le nombre d'utilisateurs est très grand.

• Chapitre 5: Dans ce chapitre, nous appliquons la politique de l'indice de Whittle dans le contexte de l'âge de l'information (AdI). Nous considérons un problème d'ordonnancement avec des canaux non fiables. Nous considérons plusieurs classes d'utilisateurs telles que chaque classe est caractérisée par ses propres statistiques de canal. Par conséquent, notre objectif est de minimiser l'âge moyen total attendu à long terme de tous les utilisateurs. Notre principale contribution dans ce travail est la preuve de l'optimalité asymptotique pour les deux scénarios :

-AdI évolue dans un espace d'état fini.

-AdI évolue dans un espace d'état infini.

Pour le premier scénario, nous fournissons une analyse rigoureuse afin d'établir l'optimalité locale asymptotique basée sur certaines techniques mathématiques. Pour le second scénario, nous adoptons une approche innovante et originale pour établir l'optimalité globale asymptotique de la politique de l'indice de Whittle. Cette approche repose essentiellement sur le critère de Cauchy : au lieu de prouver qu'une fonction donnée f (•) converge vers un point fixe, nous montrons que les termes de f (•) se rapprochent lorsque t croît. Cette méthode sera détaillée dans le chapitre 5. Enfin, nous fournissons quelques résultats numériques qui confirment notre analyse technique.

  .[START_REF] Weber | On an index policy for restless bandits[END_REF] with l 1 (t+T t ) and l 2 (t+T t ) being the instantaneous thresholds in class 1 and 2 respectively at time t + T t . α 1 (t + T t ) and α 2 (t + T t ) are the users' proportions with the highest Whittle index values, and their sum is equal to α. Without loss of generality, we letl k (t + T t ) = l k (t + T t ).As we can see, at time t + T t , all the expressions of the users' proportions that belong to the 1 -α of users with the smallest Whittle index values, are in function of α 1 (t) or α 2 (t) at various time. In fact, at time t + T t , we end up with z 1 1

  1-α p 2 α ≤ T max ≤ 1-α p 2 α + 1.Figure5.5 -The proportions of users at different states at time t + T t when β(t + T t ) = and 0 < γ(t + T t ) ≤ 1Remark 5.4. It is worth mentioning that, as we have defined l max in Proposition 5.9, it refers to the highest value that can be attained by the thresholds of the class 1 or 2 at time t + T t for t > t f where t f is a given in Lemma 5.2. Whereas, at any time t > t f , max(l 1 (t), l 2 (t)) ≤ l max might not be true since we don't have necessary a given t such that t + T t = t for any t > t f .

	Chapter 5. Whittle's index policy for minimizing the Age of Information Chapter 5. Whittle's index policy for minimizing the Age of Information
		𝛼 1 (𝑡 + 𝑇 𝑡 )
		𝛼 1 (𝑡 + 𝑇 𝑡 )
	𝑠𝑡𝑎𝑡𝑒 1 𝑠𝑡𝑎𝑡𝑒 1 1 𝑠𝑡𝑎𝑡𝑒 1 𝑠𝑡𝑎𝑡𝑒 1 2 𝑙 2 𝑡 + 𝑇 𝑡 3 𝑙 1 𝑡 + 𝑇 𝑡 -1 𝑙 2 𝑡 + 𝑇 𝑡 -1 . . . . 𝑙 1 𝑡 + 𝑇 𝑡 . 𝑙 1 𝑡 + 𝑇 𝑡 . 𝑙 2 𝑡 + 𝑇 𝑡 . . 𝑇 𝑚𝑎𝑥	. . 𝑝 1 𝛼 1 (𝑡 + 𝑇 𝑡 -1) 𝑝 2 𝛼 1 (𝑡 + 𝑇 𝑡 -1) 𝑝 2 𝛼 1 (𝑡 + 𝑇 𝑡 -1) 𝑝 1 𝛼 1 (𝑡 + 𝑇 𝑡 -1) . 𝛽(𝑡 + 𝑇 𝑡 )𝑝 1 𝛼 1 (𝑡 + 𝑇 𝑡 -𝑙 1 𝑡 + 𝑇 𝑡 ) 𝑝 2 𝛼 𝑝 2 𝛼 𝑝 2 𝛼 2 (𝑡 + 𝑇 𝑡 -𝑙 2 𝑡 + 𝑇 𝑡 ) 𝑝 1 𝛼 1 (𝑡 + 𝑇 𝑡 -𝑙 1 𝑡 + 𝑇 𝑡 + 1) . . 𝑝 2 𝛼 . 𝑝 1 𝛼 1 (𝑡 + 𝑇 𝑡 -𝑙 1 𝑡 + 𝑇 𝑡 ) 𝑝 2 𝛼 2 (𝑡 + 𝑇 𝑡 -𝑙 2 𝑡 + 𝑇 𝑡 + 1) . 1 -𝛼 . . 𝑝 2 𝛼 γ(𝑡 + 𝑇 𝑡 )𝑝 2 𝛼 2 (𝑡 + 𝑇 𝑡 -𝑙 2 𝑡 + 𝑇 𝑡 ) 𝑝 2 𝛼 𝛼 2 (𝑡 + 𝑇 𝑡 ) 𝛼 2 (𝑡 + 𝑇 𝑡 ) 𝑝 2 𝛼	1 -α -α 𝛼 𝛼
	Figure 5.4 -The proportions of users at different states at time t + T t when γ(t + T t ) = 1
	and 0 < β(t + T t ) ≤ 1 Figure 5.6 -Graphical representation of T max

Table 5 .

 5 1.We denote this lower bound by B α . For a wide range of parameters p 1 and p 2 , we provide an exhaustive table that represents the lower bound on α in function of p 1 and p 2 . As can be seen, the lower bound decreases when p 1 and p 2 are close one to the other. Moreover, it grows even smaller when p 1 and p 2 have relatively high values. According to table 5.1, we can notice that in most cases of (p 1 , p 2 ), the lower bound B α doesn't exceed 0.5. This implies that the interval of α where the assumption 5.1 is satisfied, is enough wide for different values of p 1 and p 2 . 1 -Evaluation of B α under wide range of channel statistics

	p 1	0.1	0.2	0.3	0.4	0.4	0.5	0.5	0.6	0.7	0.8
	p 2	0.2	0.4	0.5	0.6	0.8	0.8	1	0.9	0.9	0.9
	B α 0.7034 0.6250 0.4711 0.3556 0.5328 0.3612 0.5 0.2893 0.1675 0.1351

  1 is violated. Moreover, in our thesis we consider a linear objective function of delay or age. One can derive the Whittle indices for a nonlinear objective function, specially, convex or concave function.According to Theorem 2.1 Chapter 2,[START_REF] Ross | Introduction to stochastic dynamic programming[END_REF], it exists a unique function V and a constant θ that resolves Equation (3.7). Subsequently, since we have found a bounded function

	V (s) =	N k=1 V k (s k ), and a constant	N k=1 θ k that satisfy also Equation (3.7), then

  supT 0 ≤t<T ||Z N (t) -z * || ≥ µ) ≤ P x ( sup T 0 ≤t<T ||Z N (t) -z(t)|| + ||z(t) -z * || ≥ µ) (B.66)Using Proposition 4.11, there exists s 1 and s 2 such that:

	≤ P x ( sup	||Z N (t) -z(t)|| ≥ µ -)	(B.67)
	T 0 ≤t<T
	≤ P x ( sup	||Z N (t) -z(t)|| ≥ µ -)	(B.68)
	0≤t<T
	P x ( sup		(B.69)
	Therefore:
	P x ( sup

0≤t<T ||Z N (t) -z(t)|| ≥ µ -) ≤ s 1 exp(-N s 2 ). T 0 ≤t<T ||Z N (t) -z * || ≥ µ) ≤ s 1 exp(-N s 2 ).

(B.70) B.16 Proof of Proposition 4.12

Maison du doctorat de l'Université Paris-Saclay 2ème étage aile ouest, Ecole normale supérieure Paris-Saclay 4 avenue des Sciences, 91190 Gif sur Yvette, France

avenue des Sciences, 91190 Gif sur Yvette, France

Les termes utilisateurs et files d'attente sont interchangeables dans ce chapitre

The terms users and queues will be used interchangeably in this Chapter

z 0 can be seen as the system's state where all queues are in the queue state 0

Unlike the definition of threshold policy given in Chapter 4, here we suppose that under threshold policy π n , even at state n, the action prescribed is the active action

According to Remark 5.3, the form of this set means that it contains the users' proportions with the lowest Whittle index values among all users' proportions of the system

We adopt the Whittle's index policy derived in Theorem 5.3 for both scenarios.

Acknowledgements

Proof. See appendix C.7.

We say that the order of the Whittle index strictly alternates between the two classes in [1, n] or from state 1 to n, if we have w 2 (1) < w 1 (1) < w 2 (2) < w 1 (2) < w 2 (3) < w 1 (3) < • • • < w 2 (n) < w 1 (n). To that extent, the proof of α k (•) convergence is feasible when the alternation condition is satisfied from 1 to l k (t + T t ) + 1 for all t. We note that this condition will be relevant in the proof of the proposition 5.13. To that end, we start by introducing the assumption on α. Then, we demonstrate effectively that under this assumption the condition of alternation is satisfied from 1 to l k (t + T t ) + 1.

Assumption 5.1.

) by D. Then, the users' proportion scheduled at each time α satisfies:

If T max is the highest value that l k (t + T t ) can take, (this will be shown later in proposition 5.9), then it is sufficient to prove that the hypothesis of the Whittle index alternation is satisfied from 1 to T max + 1. This will be shown in the next proposition.

Proposition 5.8. Under Assumption (5.1), the order of the Whittle index alternates between the two classes from state 1 to state to T max + 1.

Proof. See appendix C.8. Now we prove that the instantaneous thresholds of the two classes can not exceed T max .

Proposition 5.9. Denoting by l max the highest instantaneous threshold in the sense that ∀t ≥ t f , max(l 1 (t + T t ), l 2 (t + T t )) ≤ l max , then T max = l max .

Proof. See appendix C.9

According to the last proposition, T max is truly the upper bound of l k (t + T t ) for all t and k = 1, 2. As consequence, the order of the Whittle index alternates between the two classes in the set [1, l k (t + T t ) + 1]. The next goal is to find a relation between l 1 (t + T t ) and l 1 (t + T t ). To do so, we recall that we have at time t:

with l 1 (t) and l 2 (t) being the thresholds in class 1 and 2 respectively at time t, and β(t) = 1 and 0 < γ(t) ≤ 1, or γ(t) = 1 and 0 < β(t) ≤ 1. Thereby, the first step consists of establishing the relationship between l 1 (t) and l 2 (t) when max(l 1 (t), l 2 (t)) ≤ T max depending on two different cases that we will explain thereafter in order to give a generalized expression of the aforementioned equation (5.39) where the index of the class is not specified in the expressions of the thresholds l 1 (t) and l 2 (t).

Appendix A Appendix: Methodology

A.1 Proof of Proposition 3.1

We consider the Bellman Equation (3.8). By summing the RHS and the LHS of Equation (3.8), for all i we obtain:

where a = (a 1 , . . . , a N ). We also have that: for all s = (s 1 , . . . , s N ) and s = (s 1 , . . . , s N ). Since P r(s k |s, a) only depends on the decision taken with respect to user i, we obtain:

From the previous equations we obtain: Proof. We will just prove the first case. For the other cases, the proof is similar. First case:

a j+1 -a j b j+1 -b j : For the LHS inequality:

The inequality above comes from the fact that b j-1 < b j < b j+1 and

For the RHS inequality:

where the above inequality comes from the fact that b j-1 < b j < b j+1 and

Lemma A.2. The largest minimizer at step j in algorithm 1 satisfies n j = min{k : b k = b n j } Proof. We consider i such that b i = b n j and we prove that n j ≤ i: By construction of n j , b n j-1 = b n j and n j-1 < n j . Hence, by increase of b k , b n j ≥ b n j-1 . Therefore b i = b n j > b n j-1 , and i > n j-1 . Consequently, according to definition of n j :

This implies that a n j ≤ a i . If i < n j , as b i = b n j , then a i < a n j which contradicts with a n j ≤ a i . Therefore n j ≤ i. This concludes the proof.

We start by the indexability then we show that the expressions given by algorithm 1 are effectively the Whittle's indices.

• Indexability:

We consider n 1 and n 2 the optimal thresholds of the problem (3.17) when the lagrangian parameter W is equal to W 1 and W 2 respectively, such that W 1 < W 2 . To that extent, we show that n 1 is less that n 2 . In fact, establishing the aforementioned result is sufficient to show the indexability since by proving it, we can say that the set of states for which the optimal decision is passive action when W = W 1 , is included in the set of states for which the optimal decision is passive action when

In order to prove that, we just need to demonstrate that b n 1 ≤ b n 2 since n 1 ≤ n 2 is equivalent to b n 1 ≤ b n 2 , due to the increase of b n with n.

As n 1 and n 2 are the minimizers of Equation (4.6) when W = W 1 and W = W 2 respectively, then:

This implies:

Thereby, we conclude the indexability.

• Whittle's index expressions:

For the Whittle's index expressions, we should demonstrate that, for k ∈]n j-1 , n j ], W j = min{W, k ∈ D(W )}.

For that, we prove first that for W < W j , k / ∈ D(W ). If k > n j-1 , W < W j , and b k = b n j-1 , then W < W j ≤ a k -an j-1 b k -bn j-1

. Therefore, a k -b k W > a n j-1 -b n j-1 W . If k > n j-1 , W < W j and b k = b n j-1 , given that a k > a n j-1 , then a k -b k W > a n j-1 -b n j-1 W Hence we have proved that, for W < W j and k > n j-1 , a k -b k W > a n j-1 -b n j-1 W . That means for W < W j , the optimal threshold is n j-1 or even less. Therefore, for k ∈]n j-1 , n j ], the optimal action is the active one, i.e. k / ∈ D(W ). We still have to prove that k ∈ D(W j ).

For that, we prove that the optimal threshold is at least n j when W = W j . In other words, for all k < n j , a k -b k W j ≥ a n j -b n j W j . We demonstrate this result by induction in j:

j = 0

By definition, W 0 ≤ a k -a -1 b k ∀k ≥ 0. Furthermore, as b n is increasing with n, then b k ≤ b n 0 for 0 ≤ k < n 0 . However, according to Lemma A.2, b k is necessarily strictly less than b n 0 . Thus, by using Lemma A.1 (fourth case), we can deduce that an 0 -a k bn 0 -b k ≤ W 0 . That means, as b -1 = 0, we have for k ∈ [-1, n 0 [, Appendix A. Appendix: Methodology an 0 -a k bn 0 -b k ≤ W 0 , which implies that a k -b k W 0 ≥ a n 0 -b n 0 W 0 .

-We suppose at step j, a k -b k W j ≥ a n j -b n j W j i.e.

an j -a k bn j -b k ≤ W j for k < n j (this remains true since b k < b n j according to Lemma A.2). We show that a k -b k W j+1 ≥ a n j+1 -b n j+1 W j+1 for k < n j+1 , i.e.: When

. Thus, by using Lemma A.1 (fourth case), we get

When k < n j , we have that

and by using again Lemma A.1 (first case),

As consequence, we have proved by induction that at any step j,

Then when W = W j , the optimal threshold is at least n j . This means that if k ∈]n j-1 , n j ], then k is surely less or equal than the optimal threshold when W = W j , which implies that the optimal decision at state k is passive action, i.e. k ∈ D(W j ). Combining the two results for k ∈]n j-1 , n j ]:

k ∈ D(W j ).

Then W j = min{W, k ∈ D(W )}. This concludes the proof. We first prove that C(•, •) is submodular. That is, (C(q + 1, 1) -C(q + 1, 0)) -(C(q, 1) -C(q, 0)) = a(q + 1) + W -a(q + 1) -(aq + W -aq) = 0 ≤ 0. The latter is obtained by substituting the values of C(q , s) for s ∈ {0, 1} and q ∈ {q, q + 1}. In order to prove that q P r(q |q, s)V (q ) is submodular, we distinguish between two cases: Case 1) q < R, then:

The inequality follows from the fact that V (•) is increasing. This concludes the proof for q < R. Queuing system

Case 2) q ≥ R, then:

Moreover, we have: q P r(q |q, 1)V (q )q P r(q |q, 0)V (q ) = q =q P r(A = q -q)V (q -R) -

3)), we obtain:

which follows from the R-convexity of V (•). Therefore, q P r(q |q, s)V (q ) is submodular.

B.2 Proof of Proposition 4.1

When i < L: 1) j ≤ n: Since j ≤ n, the optimal decision is to stay idle, that means if A denotes the number of arrival packets, in the next time slot the number of packets will be i = j + A with A ≤ R -1, then A = i -j. Therefore, the probability to transit from state j to i is the probability that A = i -j, which is exactly π i-j .

2) j > n:

The optimal decision in this case is to transmit. As j ≤ L < R, then all j packets will be transmitted. Taking into account the A arrival packets, then the new state for the next time slot will be i = A. This explains that the probability to transit from state j to i is the probability that A is equal to i which is equal to π i . When i = L: 1) j ≤ n:

The optimal decision is the passive action. Then, A arriving packets are added to the j packets present in the queue. At the next time slot, the number of packets is j + A.

According to Equation (4.1), since we cannot exceed the buffer length L, we reach the state L if j +A ≥ L. Since A ≤ R-1, then the probability of this event or equivalently the probability to transit from state j to state

The optimal decision is the active action. Subsequently, the next state is 0 as j < R. Thus to reach the state L, the arrival packet number A must be in the set [L, R -1]. Therefore, the probability to transit from

B.3 Proof of Proposition 4.2

We have that:

We distinguish between two cases: n < L and n = L. We analyze each case separately.

n < L:

We first give the expression of u(i) when i < L based on Proposition 4.1:

By definition of π given in Definition 4.3, we have that:

Now, in order to prove Proposition 4.2 for this case, we will distinguish between tree sub-cases:

We have min(i, n) = n, then:

We prove this result by induction, i.e., we start by proving that the statement

We have that:

To that end, we give the second derivative of f (.):

It is clear from the above equation that f (.) is non positive. Hence, f (.) is concave function with n. That is, for all n ∈ [0, L], f (n) ≥ min{f (0), f (L)}. Thereby, our task will be to demonstrate that f (0) and f (L) are both positive. In fact, f (0) = 0 ≥ 0. While for n = L, it requires more technical analysis to establish the desired result. Computing f (L), we get:

Therefore:

From the above inequality, 1 -ρ(L + R)(1 -ρ) L should be positive otherwise, we will have a non positive term higher than a positive term. Consequently,

We still have to show that a L -a L-1 ≥ 0. In fact:

Thus, combining the two results (B.21) and (B.22), we end up with the desired result.

B.5 Proof of Theorem 4.3

In order to prove this theorem, we introduce the following useful lemmas.

Lemma B.1. x n,n-1 is strictly increasing with n Queuing system state j, we need to prove that for all n ∈ [j + 1, L],

an-a j-1

bn-b j-1 > a j -a j-1 b j -b j-1 . Thus, the minimizer of an-a j-1 bn-b j-1 at step j is j. As consequence, the Whittle index of state j according to Algorithm 2 is effectively W

We start first by giving an useful lemma

We decompose the discounted cost V p (i + R k , W ) in the cost incurred at first time slot plus the discounted cost starting at the next time slot. At state i + R k , the decision taken is to transmit since i + R k ≥ R k > p, and at state i, the decision taken is passive action since i ≤ p, hence,

Subtracting the second term from the first term,

We have:

That means,

Applying the Lemma B.3,

We consider a given threshold n ≥ R k , i.e., for states less than n, we don't transmit otherwise we transmit. At state n if we decide to transmit then the next possible states are n -R k + i (i varies from 0 to R k -1) with the probability to reach each state is ρ k , hence, we have,

We know that,

Hence,

That means,

At state n if we decide to not transmit then the next possible states are n + i with the probability to reach each state is ρ k . Thus, we have,

Then,

As the function T O(V n ) is submodular, then for all q k i ≤ n, we have

, and for all q k i > n, we have

That means n is indeed an optimal threshold.

B.8 Proof of Proposition 4.6

Applying Proposition 4.5, the threshold n is indeed an optimal solution when W = a k R k β 1-β . That is true for all n ≥ R k , which concludes the proof.

B.9 Proof of Theorem 4.4

Before proving the Theorem, we give an useful proposition.

1-β , then the optimal threshold is surely finite. Proof. We consider that the infinite threshold policy denoted by ∞ is the optimal solution, and its respective Value function is

Under the infinite threshold, since the decision taken for all states is passive action, then we have for all q k i ≥ 0,

Applying Lemma B.4

According to Proposition's assumption, we have that

Thus, at state q k i , the optimal decision is to transmit which contradict with the fact that the threshold is infinite. That concludes the proof of the present proposition.

) is strictly increasing with W , then g k (n, W ) is strictly less than g k (n, a k R k nβ R k -βn ) = 0. As g k is decreasing with n, then for all q k i ≥ n, g k (q k i , W ) ≤ g k (n, W ) < 0. That implies for all q k i ≥ n, q k i can not be threshold (otherwise there exists q k i ≥ n such that g k (q k i , W ) ≥ 0). Moreover, since W < a k R k nβ R k -βn ≤ aR k β 1-β , then according to Proposition B.1, the optimal threshold must be finite. Thereby, surely the optimal threshold is strictly less than n. That means at state n the optimal decision is the active action. Hence, when

, the threshold n is an optimal solution. Then n ∈ D(W ). Consequently, we conclude the result for the first case. 2) n ≥ R k : For this case, we need to prove that for all

That implies for all n ≥ R k , n can not be the optimal threshold. Moreover according to Proposition B.1, the optimal threshold must be finite. Hence, the optimal threshold is surely strictly less than R k . That means at state n ≥ R k , the optimal decision is the active action, i.e., when

1-β , the threshold n is an optimal solution, then n ∈ D(W ). Hence, we conclude the result.

B.10 Proof of Theorem 4.5

In order to prove this result, we need to show that the order from the biggest Whittle index to the smallest one is the same. Information Proof. The proof is based on the Value iteration algorithm. This algorithm consists of computing by iteration V t+1 (s) for all states s defined by induction as follows:

In fact, regardless of the initial value V 0 (.), V t (.) will converge to the function V (.), the solution of the Bellman equation (5.4). Then, the structural properties of V (.) are the same as V t (.). In this case, it is sufficient for us to show that, for all t, V t (.) is increasing with the age in order to conclude the same for V (.). To that extent, we prove that V t (.) is increasing with s for all t by induction. In other words, we prove the following property:

Without loss of generality, taking V 0 (s) = 0 for all s, then V 0 (.) is clearly increasing with s.

If V t (.) is increasing with s, i.e. (C.2) holds for t, we prove that it holds for t + 1. In this regard, we compare between V t+1 (s + 1) and V t+1 (s). For that purpose, we define V 0 t+1 (s) as the value function at state s when the action prescribed is a passive one (the user stays idle), and V 1 t+1 (s) the value function at state s when the action prescribed is an active one (the user is granted the channel). Therefore:

• If L is infinite, we have for all s:

We have that:

Accordingly, when L is finite, we have for all

Analogously to the case above, when L is infinite, as V t (.) is increasing with s, then V 0 t+1 (.) and V 1 t+1 (.) are increasing with s. Hence, V t+1 (s + 1) ≥ V t+1 (s). Thus, we have shown by induction that V t (.) is increasing with s for both cases. Consequently, we can deduce that V (.) will be also increasing with s. Hence, the proof is complete.

In the sequel, we focus only on the case when L is infinite, since the demonstration for the other case is practically the same. For that, let us define ∆V t+1 (s) as:

Then, by substituting the equations (C.7) and (C.8) in (C.10), we have that:

As it was previously discussed, ∆V t+1 (s) will converge to ∆V (s) that equals to λ+pV (1)-pV (s + 1). According to Lemma C.1, V (.) is increasing with s, then, ∆V (.) is decreasing with s. This means that there exists a certain state s * ∈ [0, +∞] such that for all s < s * , V 1 (s) ≥ V 0 (s) (the optimal action is a passive one) and for all s ≥ s * , V 1 (s) ≤ V 0 (s) (the optimal action is an active one). In other words, there exists a given state s * such that for all s < s * , remaining idle is more beneficial than transmitting, and for all s ≥ s * , transmitting is more gainful than staying idle. Consequently, the optimal solution of the Bellman equation (5.4) is an increasing threshold-based policy. Information

C.2 Proof of Proposition 5.2

According to Proposition 3.2, we just need to prove that n-1 i=1 u n (i) is increasing with n. In fact, one can check easily from equations (5.10), (5.12) and (5.14), that L i=n u n (i) is decreasing with n for both cases of L. Thereby, n-1 i=1 u n (i) = 1 -L i=n u n (i) is increasing with n. That concludes the proof.

C.3 Proof of Theorem 5.3

Given that L i=1 u n (i)i is strictly increasing with n, then the Whittle's index of state s is effectively the one given by the algorithm 1. Moreover W k i in nothing but x k i+1,i defined in Lemma 4.3. Subsequently, according to the proof of Theorem 4.3 in Chapter 4, it is sufficient to show that W k i is increasing with i to establish the desired result.

Lemma C.2. W k i is increasing with i for both cases of L.

Proof. We have these following outcomes:

That concludes the proof.

Leveraging the above result, W k i is genuinely the Whittle's index of state i in the class k.

C.4 Proof of Proposition 5.4

Our proof is based on finding the characteristic polynomial of Q, and investigating the norm of its roots. By examining the expression of Q, we can deduce that the characteristic polynomial of Q is the product of the characteristic polynomial of each matrix Q k :

Therefore, it is sufficient to find the eigenvalues of each matrix Q k to conclude those of Q. To do so, we distinguish between two cases:

The characteristic polynomial of the matrix Q k is defined as follows:

The characteristic polynomial of Q k is reported in Table C.2. In order to get a closed-form of this determinant, we apply elementary row and column operations. More specifically, let us denote by r i the row i of the determinant. We also denote by a i,j the element in row Information

of B as the determinant will be independent of it. By letting

p k λ i , the determinant of G will be equal to (-λ) l * k -2 (the determinant of the upper left block) times the following determinant:

which originates from the lower right block matrix of G, and of dimension

). Now, we need to find an explicit expression of this determinant, which we will denote by S k . To achieve this goal, we first start by developing the determinant through the last column. By doing so, we end up with:

where D n is determinant of the following matrix:

We need to find the expression of D n for any fixed integer value n in order to conclude it for D L-l * k . To do so, we define ∆ n as:

The second step consists of computing ∆ n for all n. To that end, we provide the following lemma.

Lemma C.3. The determinant ∆ n can be expressed for any integer value n as:

where

Proof. The proof follows a mathematical induction. For n = 1, we can easily check that ∆ 1 is indeed -λ -A by replacing n by 1. Next, we suppose that (C.19) holds up till n and we aim to prove that it holds for n + 1. By developing ∆ n+1 through the last column, we get:

By replacing ∆ n with its value, we end up with:

Therefore, (C. [START_REF] Ruan | Delay-aware massive random access for machine-type communications via hierarchical stochastic learning[END_REF]) holds for n + 1 which concludes our proof.

By leveraging the above lemma, we can conclude the expression of D L-l * k :

As a consequence, we are able to find S k in function of λ and p k , as well as the expression of χ Q k (λ). In fact, after computations, we get:

Now, based on the expression of the characteristic polynomial χ Q k , we prove that all the eigenvalues of Q k have a modulus strictly less than one. We prove this result by contradiction. More specifically, we suppose there exists a given eigenvalue of the matrix

Hence, it verifies:

By factorizing the element λ l * k , and by using the modulus on both sides, we get: Information χ Qm (λ) = Information of the value of A. Given that, we can find the expression of S m in function of λ and p m as well as the expression of χ Qm (λ). After extensive computations, we obtain:

Hence, the only eigenvalue of Q m is 0 that has a multiplicity of L -1.

By combining all these results, we can conclude that the eigenvalues of the matrix Q have a modulus strictly less than one, which concludes our proof.

C.5 Proof of Lemma 5.1

We can formulate the fluid limit equation (5.33) as follows:

At time t + 1, applying Whittle index policy, in average exactly a proportion of p k α k (t) of users will be at state one since α k (t) refers to the proportion of users in class k that are scheduled. Accordingly, z k 1 (t + 1) = p k α k (t). While for 1 ≤ i < l k (t), the users' proportion z k i (t) is not scheduled. Therefore at time t + 1, since prescribing idle action to a given user implies that its state will be increased by 1, the proportion z k i (t) at state i in class k will be at state i + 1.

C.6 Proof of Lemma 5.2

First of all, we provide an useful lemma.

Lemma C.4. We have for all integer i and for k = 1, 2:

Proof. The result can be obtained directly by replacing w k (i) by its expression.

In order to prove the present lemma, we proceed in two steps:

• We prove first by contradiction that there exists a given time t f such that α 1 (t f ) > 0.

• We prove that if α 1 (t f ) > 0, then α 1 (t) > 0 for all t ≥ t f .

1. For the first point, we suppose that for all t, we have that α 1 (t) = 0. Consequently, we get that z 1 1 (t + T t ) = 0, • • • , z 1 l 1 (t+Tt) (t + T t ) = 0, and α 1 (t + T t ) = 0. This means that, the proportion of all users in class 1 is equal to 0. However, the users' proportion of class 1 is γ 1 = 0. That is, there exists a given time t f such α 1 (t f ) > 0.

2. Before addressing the second point, we recall that α 1 (t) refers to the scheduled users' proportion in the class 1. Thereby, α 1 (t) contains all users with the highest Whittle index values among all users in class 1. To that extent, at time t f , the Whittle index of α 1 (t f ) is greater than the Whittle index of the users' proportion 1 -α that we Information denote by C. We let S t f (C) be the set of pair (state,class) at time t f in the users' proportion C. Denoting by q the smallest state of α 1 (t f ), n and m a given state and class respectively such that z m n (t) belongs to C at time t f , then w m (n) ≤ w 1 (q). Under the Whittle index policy, at time t f + 1, the states of a users' proportion that equals to (1 -p 1 )α 1 (t f ) among the users' proportion α 1 (t f ), will be increased by one in comparison with the time slot t f , as well as the users' proportion C. Accordingly, the smallest state of the proportion (1-p 1 )α 1 (t f ), is q +1. S t f +1 (C) is shifted of one with respect to S t f (C), i.e., (n, m) ∈ S t f (C) ⇔ (n + 1, m) ∈ S t f +1 (C). We compare w 1 (q + 1) with the Whittle index of n in class m such that (n, m) ∈ S t f +1 (C). In that direction, we let (n, m) ∈ S t f +1 (C), and we distinguish between two cases:

That implies that n -1 ≤ q since w k (.) is increasing. Hence n ≤ q + 1. As consequence, w 1 (n) ≤ w 1 (q + 1) • m = 2: Again we distinguish between two case:

Therefore, we obtain our desired result for the first case.

We have that:

Applying Lemma C.4, we obtain:

Given that w 2 (n -1) ≤ w 1 (q), therefore replacing by their expressions we get:

As n -1 > q, then:

Hence, knowing that w 1 (q) -w 2 (n -1) ≥ 0 we end up with our desired result for this case, i.e. w 1 (q + 1) -w 2 (n) ≥ 0.

Thus, we have proved that at time t f + 1, all the users' proportions in C whose sum is equal to 1 -α have a Whittle index less than that of (1 -p 1 )α 1 (t f ) defined in the beginning of this proof. That means that there exists at least a users' proportion that equals to 1 -α with Whittle index values less than those of the states of the users' proportion (1 -p 1 )α 1 (t f ). Then surely, the users' proportion (1 -p 1 )α 1 (t f ) that is different from 0 belongs to the users' proportion α with the highest Whittle index values. This implies that surely at time t f + 1, there will be at least one queue in class 1 belonging to α with the highest Whittle index values. Therefore, we have that α 1 (t f + 1) > 0. This result can be generalized for all t ≥ t f . In other words, we have for all t ≥ t f , α 1 (t) > 0. Information C.7 Proof of Lemma 5.3

As α 1 (j)+α 2 (j) = α for all integers j, then, if

we have that T max -j ∈ [0, T max -1]. This means that α 1 (t + T max -j) is equal to 0, which implies that α 2 (t + T max -j) = α. Moreover, knowing that l(t + T max ) ≤ T max , then for all j ∈ [1, l(t

Therefore, according to the definition 5.2, T max satisfies:

Providing that T max by definition is the first time when l(t+Tmax) j=1

This latter sum is equal to (T max -1)p 2 α which is less than 1 -α. Therefore, we have as result that T max < 1-α p 2 α + 1. As there is one integer value between 1-α p 2 α and 1-α p 2 α + 1, then T max doesn't depend on t, and satisfies:

C.8 Proof of Proposition 5.8

We have that w 1 (n) = (n-1)p 1 n

2

+ n, and w 2 (n) = (n-1)p 2 n 2 + n. We start first by finding the set of states for which the Whittle index alternate between the two classes. As we can see from the expression of the Whittle index, for a given state n, w 2 (n) < w 1 (n) as p 2 < p 1 . In order to have the condition of alternation strictly satisfied for any given state n, we must have w 1 (n) < w 2 (n + 1). Hence, denoting by f (n) the difference w 2 (n + 1) -w 1 (n), we study the sign of f (n) to see for which n f is strictly positive.

Proof. We have that:

Hence:

The derivative is equal to zero for n = p 1 +p 2 2(p 1 -p 2 ) , which is strictly greater than 0. This means that f is strictly increasing in [0,

]. This means that, the unique positive solution for f (n) = 0 must be in the interval

Indeed, the unique solution

, +∞[ is the biggest root of the polynomial (C.34) which is exactly the value D introduced in Assumption 5.1. As the function f is decreasing in

According to Lemma C.5, the order of the Whittle index strictly alternates between the two states when n ∈ [1, D[. Therefore, we need to prove that T max + 1 is upper bounded by D in order to prove that the alternation condition is satisfied from state 1 to T max + 1. Indeed, as we have found an upper bound of T max which is equal to 1-α p 2 α + 1 (according to Lemma 5.3), we just need to prove that 1-α p 2 α + 2 is strictly less than D. Under assumption (5.1), we have that:

Hence, from state 1 to T max + 1, the order of the Whittle index strictly alternates between the two classes. Accordingly, the proof is concluded.

C.9 Proof of Proposition 5.9

We present first a lemma which will be helpful in proving this proposition as well as the next ones.

Lemma C.6. For any state q, at any time t, we have that:

Proof. See appendix C.10

We consider t ≥ t f . After time T t , we have that:

Then, as it has been showcased, at time t+T t , there exists l 1 (t+T t ) ≤ l(t+T t ), l 2 (t+T t ) ≤ T t , γ(t + T t ) = 1 and 0 < β(t + T t ) ≤ 1; or 0 < γ(t + T t ) ≤ 1 and β(t + T t ) = 1 such that:

with l 1 (t+T t ) and l 2 (t+T t ) being the instantaneous thresholds in class 1 and 2 respectively at time t + T t . Now, we prove by contradiction that max(l 1 (t + T t ), l 2 (t + T t )) ≤ T max . We prove first that l 2 (t + T t ) is greater than l 1 (t + T t ).

As we have that w 2 (l 1 (t + T t )) < w 1 (l 1 (t + T t )), then according to lemma C.6, w 2 (l 1 (t + T t )) ≤ w 2 (l 2 (t + T t )). This implies that l 2 (t + T t ) is greater than l 1 (t + T t ).

Reasoning by contradiction, we suppose that l 2 (t + T t ) > T max (l 2 (t + T t ) = max(l 1 (t + T t ), l 2 (t + T t )) > T max ). Based on this, we have that w 1 (T max ) < w 2 (l 2 (t + T t )) because w 1 (T max ) < w 2 (T max + 1) ≤ w 2 (l 2 (t + T t )) since the order of the Whittle index alternates between the two classes as it has been proved in Proposition 5.9. To that extent, we distinguish between two cases: 1) First case:

We have that w 1 (T max ) < w 2 (l 2 (t + T t )). Then, according to Lemma C.6, we have that w 1 (T max ) ≤ w 1 (l 1 (t + T t )). Hence, we can conclude that T max ≤ l 1 (t + T t ) as w 1 is an increasing function with the age of information.

Moreover, since we have that p 1 α 1 (t + T t -j) + p 2 α 2 (t + T t -j) > p 2 α (the strict inequality is due to the fact that α 1 (t) > 0 as t ≥ t f according to Lemma 5.2), then according to Lemma 5.3, we obtain:

The last inequality comes from the fact that T max ≥ 1-α p 2 α . This implies that:

This gives us an illogical statement. Consequently, in this case, the assumption l 2 (t+T t ) > T max is not true. As it has been established before tackling the first case, w 1 (T max ) < w 2 (l 2 (t + T t )), then Information w 1 (T max ) < w 1 (l 1 (t + T t )). This means that l 1 (t + T t ) > T max . Therefore, we have that:

This implies that:

Consequently, in this case, the assumption l 2 (t + T t ) > T max is not true. Hence, in both cases, l 2 (t+T t ) must be less than T max , i.e. max(l 1 (t+T t ), l 2 (t+T t )) ≤ T max for all t. Thus, we end up with T max = l max , which concludes our proof.

C.10 Proof of Lemma C.6

We prove only the first statement as the proof steps for both cases are exactly the same. By definition of l 1 (t) and l 2 (t), we have that

Hence, if a given q verifies w 1 (q) ≤ w 2 (l 2 (t)), then w 1 (q) ≤ max(w 1 (l 1 (t), w 2 (l 2 (t)), that implies that z 1 q (t) ∈ {z k i (t) :

. Knowing that the highest users' proportion's state of the aforementioned set in class 1 is l 1 (t), then q ≤ l 1 (t). Therefore as w 1 (.) is increasing, w 1 (q) ≤ w 1 (l 1 (t)).

C.11 Proof of Proposition 5.10

We have that:

with l 1 (t) and l 2 (t) being the thresholds in class 1 and 2 respectively at time t, and

Our aim in this proof is to show that there is a link between l 1 (t) and l 2 (t) when they are less than T max . By doing so, we find a general form of the aforementioned equation. To that end, we prove first that l 1 (t) is less than l 2 (t).

Indeed, as we have w 2 (l 1 (t)) < w 1 (l 1 (t)), then according to lemma C.6, w 2 (l 1 (t)) ≤ w 2 (l 2 (t)). Consequently, we can conclude that l 1 (t) ≤ l 2 (t).

Secondly, we prove that l 2 (t) ≤ l 1 (t) + 1. As the order of the Whittle indices alternates between the two classes from state 1 to state T max + 1, w 1 (l 2 (t) -1) < w 2 (l 2 (t)). Hence, according to lemma C.6, we have that w 1 (l 2 (t) -1) ≤ w 1 (l 1 (t)). Consequently, l 2 (t) -1 ≤ l 1 (t).

Given that l 1 (t) ≤ l 2 (t) ≤ l 1 (t) + 1, then l 1 (t) can be either l 2 (t) or l 2 (t) -1. Information

The second step consists of deriving the value of β(t) or γ(t) depending on the value of l 1 (t) and l 2 (t).

We prove that γ(t) = 1 if z 2 l 2 (t) > 0. Indeed, if γ(t) = 1 and z 2 l 2 (t) > 0, thus there is at least a non empty set of users in class 2 at state l 2 (t) that belongs to the users' proportion α with the highest Whittle index values. However there exists always a non empty set of queues in class 1 at state l 1 (t) that belong to 1 -α users' proportion with the least Whittle index values, since β(t) > 0. Then, we have that w 2 (l 2 (t)) ≥ w 1 (l 1 (t)). However, we know that w 2 (l 2 (t)) = w 2 (l 1 (t)) < w 1 (l 1 (t)). This later inequality contradicts with what precedes. Thus, the statement that γ(t) = 1 is not true, i.e. γ(t) = 1.

In this case we denote l(t) = l 1 (t) = l 2 (t). We end up:

If z 2 l 2 (t) = 0, the last equation still valid since z 2 l 2 (t) = 0 whatever the value of γ(t), namely when γ(t) = 1.

We prove that β(t) = 1 if z 1 l 1 (t) > 0. Indeed, if β(t) = 1 and z 1 l 1 (t) > 0, there is at least a set of users in class 1 in state l 1 (t) that belongs to the users' proportion α with the highest Whittle index values. However there is always a set of queues in class 2 at state l 2 (t) that belong to 1 -α users' proportion with the least Whittle index values, since γ(t) > 0. Then, we have that w 1 (l 1 (t)) ≥ w 2 (l 2 (t)). However, we know that w 2 (l 2 (t)) = w 2 (l 1 (t) + 1) > w 1 (l 1 (t)) since the order of Whittle index alternates between the two classes from state 1 to T max + 1 according to Proposition 5.9. Thus, w 2 (l 1 (t) + 1) > w 1 (l 1 (t)) ≥ w 2 (l 1 (t) + 1), which gives us an obvious contradiction. Therefore, we can assert that β(t) = 1. In this case, we consider that l(t) = l 1 (t) + 1 = l 2 (t) and we get:

Similarly to the first case, if z 1 l 1 (t) = 0, the last equation still valid since z 1 l 1 (t) = 0 whatever the value of β(t), namely when β(t) = 1. Subsequently, combining the two cases, there exists l(t) such that:

where β(t) = 0 and 0 < γ(t) ≤ 1, or 0 < β(t) ≤ 1 and γ(t) = 1 Information C.12 Proof of Proposition 5.11

We prove the Proposition by induction:

• For T = T 0 , we have already proved our claim.

• We suppose that the statement is valid for a given T , i.e. there exists l(T ), β(T ) and γ(T ) such that:

where β(T ) = 0 and 0 < γ(T ) ≤ 1, or 0 < β(T ) ≤ 1 and γ(T ) = 1. Then, at the next time slot, among the users' proportion scheduled, α, exactly p 1 α 1 (T ) and p 2 α 2 (T ) will go to state one for each class, while for the rest, their states will be incremented by one. Likewise, for the other users for which the action taken is passive, their states will be incremented by one. As consequence, the decreasing order according to the Whittle index value for these proportions of users at the next slot is

, p 2 α 2 (T ) (As we have mentioned before, the order of the Whittle indices alternates between the two classes because l(T ) + 1 ≤ l max + 1). Moreover, the states of the users' proportion (1-p 1 )α 1 (t) and (1-p 2 )α 2 (t); which are scheduled but they don't transit to the state 1 with respect to their classes; will be increased by one. Leveraging the above results, we provide the decreasing order of all users' proportions according to the Whittle index value depending on two cases of β(t). If β(T ) = 0, then the smallest state's value among the users' proportions (1-p 1 )α 1 (t) and (1 -p 2 )α 2 (t) at time T + 1 is l(T ) + 1. Hence, their Whittle index values will be higher than w 2 (l(T ) + 1), and consequently, they will be higher than those of users' proportion of γ(T )p 2 α 2 (T -l(T )) at state l(T ) + 1 in class 2. If β(T ) = 1, the smallest state value among the users' proportions (1 -p 1 )α 1 (t) and (1 -p 2 )α 2 (t) at time T + 1 is respectively l(T ) + 1 and l(T ) + 2. Then, their Whittle index values will be higher than w 1 (l(T ) + 1) (w 1 (l(T ) + 1) < w 2 (l(T ) + 2) as the alternation condition is satisfied from 1 until l max + 1). Consequently, their Whittle index values will be higher than the Whittle index of users' proportion β(T )p 1 α 1 (T -l(T )) at state l(T ) + 1 in class 1. Thus, the decreasing order of all users' proportions according to the Whittle index value whatever the value of β(T ) at T +1 is:

As we have that (1 -p 1 )α 1 (t) + (1 -p 2 )α 2 (t) ≤ α, then surely the thresholds at time T + 1 in class 1 and in class 2 are less than the state of the users' proportion β(T )p 1 α 1 (T -l(T )) and γ(T )p 2 α 2 (T -l(T )) respectively. Therefore, there exists l 1 (T + 1), l 2 (T + 1), β(T + 1) and γ(T + 1) such that 0 < β(T + 1) ≤ 1 and Information γ(T + 1) = 1, or β(T + 1) = 1 and 0 < γ(T + 1) ≤ 1:

Now we prove by contradiction that max(l 1 (T + 1), l 2 (T + 1)) ≤ T max . We prove first that l 2 (T + 1) is greater than l 1 (T + 1).

As w 2 (l 1 (T + 1)) < w 1 (l 1 (T + 1)), that means according to lemma C.6, l 2 (T + 1) is greater than l 1 (T + 1) (w 2 (l 1 (T + 1)) < w 2 (l 2 (T + 1))).

Reasoning by contradiction, if l 2 (T + 1) > T max , then we distinguish between two cases:

-First case: If β(T + 1) = 1: we have that w 1 (T max ) < w 2 (l 2 (T + 1)) (w 1 (T max ) < w 2 (T max + 1) as the alternation condition is satisfied in [1, T max + 1]), i.e., according to lemma C.6, we have that l max ≤ l 1 (T + 1). Hence, according to lemmas 5.2 and 5.3, we have that:

Therefore we end up with:

Hence, the assumption that l 2 (T + 1) > T max leads us to an illogical statement. Consequently, the hypothesis of l 2 (T + 1) > l max is not valid for the first case.

-Second case: If β(T + 1) < 1:

Then we have that γ(T + 1) = 1. Therefore, all users at state l 2 (T + 1) in class 2 are in the proportion 1 -α with the smallest Whittle index values. However, there are users in state l 1 (T + 1) in class 1 of the α proportion with the highest Whittle index values. In other words, w 1 (l 1 (T +1)) ≥ w 2 (l 2 (T +1)) > w 1 (T max ). This means that l 1 (T + 1) > T max . Therefore, according to lemmas 5.2 and Information

5.3:

Hence,

Therefore, the hypothesis of l 2 (T + 1) > T max is not valid for the second case.

Consequently, we have that l 2 (T + 1) ≤ T max , i.e. max(l 1 (T + 1), l 2 (T + 1)) ≤ T max . Then, according to Proposition 5.10, there exists l(T +1), and γ(T +1) and β(T +1) such that:

where β(T + 1) = 0 and 0 < γ(T + 1) ≤ 1, or 0 < β(T + 1) ≤ 1 and γ(T + 1) = 1.

To conclude, we have proved by induction, that for all T ≥ T 0 , there exists l(T ), β(T ) and γ(T ), such that:

where β(T ) = 0 and 0 < γ(T ) ≤ 1, or 0 < β(T ) ≤ 1 and γ(T ) = 1, which concludes our proof.

C.13 Proof of Proposition 5.12

We proceed by the same method used to prove the Proposition 5.11. We consider at time T :

where β(T ) = 0 and 0 ≤ γ(T ) < 1, or 0 ≤ β(T ) < 1 and γ(T ) = 1. Among the users' proportion scheduled α, exactly p 1 α 1 (T ) and p 2 α 2 (T ) will go to state one for each classes, and (1 -p 1 )α 1 (T ) and (1 -p 2 )α 2 (T ) will go to the next state. For the other users for which the action taken is passive, their states will be increased by one, then the decreasing order according to the Whittle index value at the next time slot is

T ) (As we said before that the order based on the value of the Whittle indices, alternate between the two classes from state 1 to l(T ) ≤ l max +1). Moreover, the users' proportion scheduled (1-p 1 )α 1 (T ) and (1-p 2 )α 2 (T ) will be at states that have Whittle index values higher than those of β(T )p 1 α 1 (T -l(T )) and γ(T )p 2 α 2 (T -l(T )) (as we have explained in the proof of Proposition 5.11). Hence, the global decreasing order according to the Whittle index value is (1-p 1 )α 1 (T ), (1-

Then, there exists β = 0 and 0 < γ ≤ 1, or 0 < β ≤ 1 and γ = 1, and sub-set

, and the elements of the set {α 1 (T ),

} are exactly the elements of the vectors A 1 (T + 1) and A 2 (T + 1) respectively. Given that {α 1 (T ),

included in the set of elements of the vector A 1 (T ) and A 2 (T ) respectively, then for k = 1, 2, all the elements of the vector A k (T + 1) except α k (T + 1) belong to the elements of vector A k (T ).

C.14 Proof of Proposition 5.13

According to Proposition 5.11, the elements of the vectors A 1 (T ) and A 2 (T ) satisfy:

where 0 < β(T ) ≤ 1 and γ(T ) = 1, or β(T ) = 0 and 0 < γ(T ) ≤ 1. We distinguish between two cases depending on the values of β and γ (we drop the index T on β(T ) and Information γ(T ) to ease the notation):

• First case: 0 < β ≤ 1, and γ = 1:

Hence:

Our aim is to derive the expression of α k (T + 1) for class 1 and class 2. Among the users' proportion scheduled α, exactly p 1 α 1 (T ) and p 2 α 2 (T ) will go to state one for each class, and the rest will go to the next state. Hence:

At time T + 1, the decreasing order according to the Whittle index value is

In order to get B 1 (T ) and B 2 (T ), we sum the users' proportions at different states starting from the users' proportion βp 1 α 1 (T -l(T )) following the decreasing order of the Whittle index until we get the sum that equals to p 1 α 1 (T ) + p 2 α 2 (T ). We distinguish between six sub-cases and for each sub-case, we prove that α k (T + 1) is surely between two elements of the vector A k (T ). In fact, if we prove it just for one class, the result will be true for the other one, since α 1 (T ) + α 2 (T ) = α for all T .

In the following, we derive the expression of α k (T + 1) for k = 1, 2, in function of the elements of the vector A 1 (T ) and A 2 (T ) and we show that α 1 (T + 1) is surely between two elements of the vector A 1 (T ).

. Therefore, we will take a proportion of users from p 1 βα 1 (T -l(T )) that equals to p 1 α 1 (T ) + p 2 α 2 (T ) denoted by C. This users' proportion exactly equals to B 1 (T ) + B 2 (T ) that we add to (1 -p 1 )α 1 (T ) and (1 -p 2 )α 2 (T ). Thus, B 1 (T ) + B 2 (T ) = C. However, since all the users of the proportion C belong to p 1 βα 1 (T -l(T )), then C contains only the users of the class 1. Consequently, B 1 (T ) = C and B 2 (T ) = 0. Hence:

As α 1 (T + 1) + α(T + 1) = α, then:

Now we find the upper bound of α 2 (T ) -α 2 (T + 1):

The first inequality comes from the fact that p 1 α 1 (T ) + p 2 α 2 (T ) ≤ p 1 βα 1 (T -l(T )) and the second one comes from the fact that β ≤ 1. Given that α 2 (i) -α 2 (j) = α 1 (j) -α 1 (i) for all integers i and j, thus:

Moreover, we have that α 1 (T + 1) -α 1 (T ) ≥ 0 because α 2 (T + 1) -α 2 (T ) ≤ 0. Therefore, α 1 (T ) ≤ α 1 (T + 1). On the other hands, as

. Consequently, we end up with:

Hence:

Then:

On the other hand, we have according to the right inequality of sub-case's assumption:

Hence :

Knowing that p 2 < p 1 , the later inequalities imply that α

As a result we have that:

Hence:

86)

And:

This means that if α 1 (T ) ≤ α 1 (T + 1):

Hence:

93)

Therefore:

According to the left inequality of the assumption of this case, we have that:

On the other hand, we have that:

And

If α 1 (T + 1) ≤ α 1 (T ):

And

This means that:

We have that:

On the other hand:

Thus:

And:

Hence:

We have that:

On the other hand:

Thus:

And:

• Second case: β = 0 and 0 < γ ≤ 1: Hence, we have that:

Then, at time T + 1, the decreasing order according to the Whittle index value is

In order to obtain B 1 (T ) and B 2 (T ), we sum the users' proportions at different states starting from the users' proportion γp 2 α 2 (T -l(T )) following the decreasing order of the Whittle Information index until we get the sum that equals to p 1 α 1 (T ) + p 2 α 2 (T ). For this case, we distinguish between five sub-cases, and for each sub-case, we prove that α 1 (T + 1) is surely between two elements of the vector A 1 (T ).

We have that:

And:

Hence:

On the other hand, according to the right inequality of the assumption of this case, we have that:

That means:

And:

And:

Hence:

We have that:

And:

And:

Hence:

On the other hand:

Thus:

And:

That implies that:

On the other hand:

177) Information

Thus:

And:

In conclusion, all these six sub-cases when γ = 1 and 0 < β ≤ 1, plus the five sub-cases when β = 0 and 0 < γ ≤ 1, can be summarized in four cases:

Thus, the proof is concluded.

C.15 Proof of Proposition 5.14

In all the proof, we consider that ≤ (l 2 -l 1 ) (1-p 1 ) L 1-(1-p 1 ) L . Before tackling the proof, we give a brief insight about the procedure adopted to establish the desired result: We start by finding a given time denoted T 2 ≥ T where α 1 (T 2 ) is less than l 1 . Then, we show that α 1 (T 2 ), • • • , α 1 (T 2 + L) are strictly less than l 2 . To that end, we start first by defining a relevant sequence u n in function of , l 1 , l 2 and p 1 when n ∈ [0, L]. After that, we prove that u n is increasing with n and strictly less than l 2 . Next, we establish that u n is an upper bound of α 1 (•) in [T 2 , T 2 + L]. More precisely, we show that α 1 (T 2 +n) ≤ u n for n ∈ [0, L]. For that purpose, we proceed with two following steps: The first one consists of deriving an inequality verified by two consecutive terms of the sequence α 1 (•), namely α 1 (T ) and α 1 (T + 1) using the Proposition 5.13 given that T ≥ T . As for the second step, we use essentially the aforementioned result to demonstrate by induction that u n is indeed an upper bound of α 1 (T 2 + n). Finally, based on these results, we show that there exists T d such that max A 1 (T d ) < l 2 .

To find a time T 2 ≥ T such that α 1 (T 2 ) is less than l 1 , we use the fact that min A 1 (t) ≤ l 1 for all t. At time T + L, we have the vector A 1 (T + L) = (α 1 (T + L), α 1 (T + L -1), • • • , α 1 (T + L -l(T + L))). Providing that min A 1 (T + L) ≤ l 1 , then there exists an element from the vector A 1 (T + L) less than l 1 denoted by α 1 (T 2 ). According to Proposition 5.11, we have for all T ≥ T 0 , l(T ) ≤ l max = L, then l(T + L) ≤ L. That is, T 2 is greater than T since T 2 ≥ T + L -l(T + L) ≥ T . Therefore, we find an element of the Information sequence α 1 (•) at time T 2 ≥ T such that α 1 (T 2 ) ≤ l 1 . To that extent, we are interested in proving that α 1 (T 2 ), • • • , α 1 (T 2 + L) are strictly less than l 2 . To do so, we define a sequence u n which will constitute an upper bound of the function α 1 (T ).

Definition C.1. We define a sequence u n by induction:

Next, we prove that the L first terms of this sequence are strictly less than l 2 . We detail this in the following.

Lemma C.7. For n ∈ [0, L], u n < l 2

Proof. In fact, the sequence u n satisfies for all n:

where λ = -( + l 2 -l 1 ). u n is clearly increasing with n, then for all n ∈ [0, L]:

We have that:

Given that 1 -(1 -p 1 ) L ≥ 0, then:

Based on the lemma above, we prove that for any element of the set {α 1 (T 2 ), • • • , α 1 (T 2 + L)} must be less than u L .

For that, we introduce a useful Lemma:

we have that:

Then, we have that:

Proof. Before starting the proof, we recall that, according to the first result of Proposition 5.13, the four possible inequalities satisfied by α 1 (T ), α 1 (T + 1), α 1 (T -l(T )), α 1 (Tl(T ) + 1) are:

Therefore, the two cases for which α 1 (T ) ≤ α 1 (T + 1) are:

• α 1 (T ) ≤ α 1 (T + 1) ≤ α 1 (T -l(T ) + 1).

Hence, according to the results of Proposition 5.13, the inequalities satisfied by α 1 (T + 1) -α 1 (T ) are: If α 1 (T ) ≤ α 1 (T + 1) ≤ α 1 (T -l(T )), then:

), then:

Since, by assumption of the Lemma, T ≥ T 2 ≥ T , then max A 1 (T ) ≤ l 2 + . As a consequence, α 1 (T -l(T ) + 1) and α 1 (T -l(T )) which are elements of the vector A 1 (T ), are less than l 2 + . Hence, for T ∈ [T 2 , T 2 + L -1]:

Now we should prove that for all possible sequences of α

Lemma C.9. For all sequences of α 1 when

Proof. We prove this result by induction.

For T = T 2 , we have that:

We suppose that at time T , α 1 (T ) ≤ u T -T 2 , then at time T + 1:

Then as u T -T 2 is increasing in T :

Then, according to Lemma C.8:

. Hence, we have proved by induction that for all

then according to Lemma C.9, the elements

Thus, we have found T 2 ≥ T such that α 1 (T 2 ), α 1 (T 2 + 1), • • • , α 1 (T 2 + l max ) are strictly less than l 2 . We denote T 2 + l max by T d and we verify that max A 1 (T d ) < l 2 . Indeed, we know that T d -l(T d ) ≥ T d -l max = T 2 , then the elements of the vector A 1 (T d ) are included in the set of elements {α 1 (T 2 ),

Hence, we have found

C.16 Proof of Proposition 5.15

In this proof, we show that for each state i in class k, z k i (t) converges. To that end, we start first by specifying the eventual limit of z k i (t) for each i. To do so, we decompose 1 -α as follows:

where l is the biggest integer such that: l(p 1 α * 1 + p 2 α * 2 ) < 1 -α, and 0 < γ ≤ 1 and β = 0; or γ = 1 and 0 < β ≤ 1. Then, we proceed with these following steps:

• We prove by induction that for all states 1 ≤ i ≤ l + 1, z k i (t) converges to p k α * k .

• Based on the theoretical findings of the first step, we prove that z 1 l+2 (t) converges to

• Finally, we show that for all states i > l + 2,

We prove this result by induction

• We consider that for a certain j ≤ l, for each 1 ≤ i ≤ j, z k i (t) converges to p k α * k and we show that z k j+1 (t) converges also to p k α * k . Given that j ≤ l: j(p

Providing that z k i (t) converges to p k α * k for all 1 ≤ i ≤ j, that means there exists t j such that for t ≥ t j , for 1 ≤ i ≤ j:

As consequence, for all t ≥ t j , we have that:

Thus, for all t ≥ t j , the action prescribed to the users' proportion z k j (t) is the passive action 1 . Then, for all t ≥ t j :

Consequently, we prove by induction that for all

To avoid redundancy , we will be limited to the first case when 0 < γ ≤ 1 and β = 0, since the proof's steps for both cases are exactly the same. We have that:

which is strictly less than 1 -α, then there exists t l such that for all t ≥ t l , we have that:

which is strictly greater than 1 -α, then there exists t l+1 such that for all t ≥ t l+1 , we have that:

Knowing that the order of the proportions of the users according to the Whittle's index value alternates between the two classes in the set [1, l max + 1] as was established in 5.8, then for all integer b ∈ [1, l max ], the set {z k i : k = 1, 2; 1 ≤ i ≤ b} is the set of users with the lowest Whittle's index value. Therefore, b i=1 z 1 i (t) + b i=1 z 2 i (t) < 1 -α implies that the actions prescribed to the users belonging to the set {z k i : k = 1, 2; 1 ≤ i ≤ b} is the passive action. By definition of l, l < 1-α p2α , then, l ≤ l max (see Lemma 5.3). Hence, the above reasoning can be applied as well when b = l. Information For t ≥ max{t l , t l+1 }, we have that:

Denoting γ(t) and β(t) the users' proportion of z 2 l+1 (t) and z 1 l+1 (t) respectively which are not scheduled, therefore, the relation that links z 1 l+2 (t + 1) and z 2 l+2 (t + 1) to z 1 l+1 (t) and z 1 l+1 (t) when t ≥ max{t l , t l+1 }:

To that extent, we show that β(t) tends to β = 0 and γ(t) tends to γ. For that purpose, we give the following equation which is always satisfied when t ≥ max{t l , t l+1 }:

Tending t to +∞ in the equation C.203, we obtain:

We consider the set {t : β(t) = 0}. If this set is infinite, then there exists a strictly increasing function n(.) from N to {t ∈ Nβ(t) = 0}, such that β(n(t)) is a subsequence of β(t). As β(n(t)) = 0, then γ(n(t)) = 1. Therefore, we get:

is less than 0, and β(n(t))z 1 l+1 (n(t)) is greater than 0 for all t. Thus:

This implies that γ = 1 = γ(n(t)), and

If {t : β(t) = 0} is finite, then there exists t e such that for all t ≥ t e , β(t) = 0. Therefore, for all t ≥ t e , we have that: Consequently, combining the last result with the one derived in the first step, we conclude that z 1 l+2 (t) converges to

Similar analysis can be applied to come with the aforementioned result when γ(t) = 1 and 0 < β(t) ≤ 1. Information

For

2 : For t ≥ max{t l , t l+1 }, we are sure that the action prescribed to z k i (t) for all i ≥ l + 2 is the active action. As consequence, z k i+1 (t + 1) satisfies:

We conclude that for all states i and k = 1, 2, z k i (t) converges. On the other hands, according to Proposition 5.7, the only possible limit of z(t) is z * . As consequence, for each k and i, z k i (t) converges to z k, * i .

C.17 Proof of Proposition 5.16

For a given z, let m 1 (z) and m 2 (z) be the highest states of the class 1 and the class 2 respectively and l 1 (z) and l 2 (z) be the thresholds of class 1 and 2 respectively at time t when Z N (t) = z. Given that, we introduce the following lemma.

Lemma C.10. For any µ, there exists positive constant C(z) such that:

Proof. By definition of m 1 (z) and m 2 (z), we have that z

). On can easily show that m 1 (z ) = m 1 (z) + 1 and m 2 (z ) = m 2 (z) + 1 since the users' proportions at states m 1 (z) and m 2 (z) in class 1 and class 2 will become at states m 1 (z)+1 and m 2 (z) + 1 at the next time slot respectively. To prove this lemma, we use the Chebychev inequality presented as follows:

for any µ > 0 and random variable X.

As z = E(Z N (t + 1)|Z N (t) = z), we can apply the Chebychev inequality. However we need to find the distribution of Z N (t + 1) knowing Z N (t) = z in order to derive the expression of V ar(Z N (t+1)|Z N (t) = z). It is more simple to study the parameters of one dimensional random variable than multi-dimensional random variable. Hence, instead of investigating Z N (t + 1), we look into Z N,k i . In this regard, we have that:

Therefore:

Now, we look for the distribution of Z N,k i (t + 1) knowing Z N (t) = z. For 2 ≤ i ≤ l k (z), as all the users at state i -1 strictly less than l k (z) will transit to the state i at the next time slot, then we have

This implies that:

For i = 1, defining α 1 (z) and α 2 (z) as the proportions of the scheduled users in class 1 an class 2 respectively when Z N (t) = z, then N Z N,k 1 (t + 1)|Z N (t) = z follows a binomial distribution with parameters p k and α k (z)N . Therefore, V ar(N Z N,k

As a results, according to Chebychev inequality, we have that:

N

. Thus:

where X follows a binomial distribution with parameters 1 -p k and (1 -β k (z))z k i-1 N , then:

(C.212) We end up with:

Knowing that α k (z) ≤ 1, i≥l k (z) z k i ≤ 1, 1 -β k (z) ≤ 1, and for all state i in the vector z , i ≤ m 1 (z ) + m 2 (z ) then:

Hence, denoting by C(z), (m 1 (z )+m 2 (z )) 4

µ 2

[2p 1 (1-p 1 )+2p 2 (1-p 2 )] = (m 1 (z)+1+m 2 (z)+1) 4

µ 2

[2p 1 (1p 1 ) + 2p 2 (1 -p 2 )], we obtain as a result:

Now, we give a lemma that bounds the probability knowing the initial state z(0) = x.

One can easily verifies that m 1 (z(t)) = m 1 (x) + t and m 2 (z(t)) = m 2 (x) + t by induction. Without loss of generality, we let m k (z(t)) = m k (t) for k = 1, 2.

Lemma C.11. For any µ, there exists positive constant C(t + 1) such that:

where C(t + 1) is independent of N .

Proof. We recall from Lemma C.10 that for any µ > 0, there exists a constant C(z) independent of N such that:

Before proving the present lemma, we give an important lemma that will helps us in the later analysis.

Lemma C.12. For any proportion vector z, there exists σ > 0 such that if ||Z N (t)-z|| ≤ σ, then Q(Z N (t)) = Q(z).

Proof. One can deduce from the analysis done in Section 5.2, and more precisely the equation (5.26), that there exists σ > 0 such that if Z N (t) ∈ Ω σ (z), Q(Z N (t)) is constant and doesn't depend on Z N (t). Therefore, there exists σ > 0 such that Q(Z N (t)) = Q(z).

That concludes the proof.

Corollary C. [2p 1 (1p 1 ) + 2p 2 (1 -p 2 )]. Let us suppose that the statement holds for any t ≥ 1. We investigate the property for t + 1. To that end, let us consider ν < µ. Therefore, according to Corollary C.1, there exists ρ such that: where C 1 (t) = (m 1 (z(t))+m 2 (z(t))+2) 4

(µ-ν) 2

[2p 1 (1 -p 1 ) + 2p 2 (1 -p 2 )] = (m 1 (t)+m 2 (t)+2) 4

(µ-ν) C.18 Proof of Lemma 5.4

We show first of all that z(t) converges to z * with respect to our considered norm, i.e. lim t→+∞ +∞ i=1 |z k i (t) -z k, * i |i = 0 for k = 1, 2. For that purpose, we use the limit inversion theorem which states that:

• If the series i f i (t) is uniformly convergent on R + • If for each integer i, f i (t) admits a finite limit r i when t tends to +∞. • Uniform convergence: According to Weierstrass criterion, i f i (t) is uniformly convergent if for each i the function f i (t) is bounded by a constant c i such that i c i is convergent. Based on the proof of the Proposition 5.15, one can deduce that for large enough t denoted by t l , the following induction relation always holds for t ≥ t l and i ≥ l max + 1: z k i+1 (t + 1) = p k z k i (t) That is, choosing t 0 greater than t l , and denoting by i 0 = m k (t 0 ) the highest state of the vector z(t 0 ) which is greater than l max + 1, we have that for each i > i 0 :

Based on the above equation, for each i > i 0 , z k i (t) is less than p i-i 0 k for all t ≥ t 0 . To that extent, we investigate the evolution of the series of interest only when t ≥ t 0 (the limit inversion theorem still applicable since +∞ > t 0 ). Moreover, we have that for all t ≥ t 0 :

This last sum is known to be a finite sum since +∞ i=1 z k, * i i is the optimal average age of the relaxed problem for the class k which is finite, and +∞ i=1 p i i is a finite sum for any 0 ≤ p < 1. Hence, the uniform convergence can be accordingly concluded.

• Existence of the limit of f i (t) = |z k i (t)-z k, * i |i: According to the result of Proposition 5.15, we have lim t→+∞ |z k i (t) -z k, * i |i = 0 which is finite. Therefore, the second condition is satisfied.

Leveraging these findings, we can inverse the order between the limit and the sum. Subsequently:

In other words, for k = 1, 2, +∞ i=1 |z k i (t) -z k, * i |i tends to 0 when t grows. Consequently, z(t) converges to z * with respect to our defined norm. Therefore, for 0 < ν < µ, there exists T 0 such that for any t ≥