Memory Bandits for decision making in dynamical environments. Application to network optimization

Dans cette thèse de doctorat, nous étudions le problème du bandit manchot non stationnaire où le comportement de non-stationnarité de l'environnement est caractérisé par plusieurs changements brusques appelés "points de changement". Nous proposons les bandits à mémoire : une combinaison entre un algorithme pour le bandit manchot stochastique et le détecteur Bayésien de point de changement. L'analyse de ce dernier a toujours été un problème ouvert dans la communauté de la théorie statistique et de l'apprentissage séquentiel. Pour cette raison, nous dérivons une variante du détecteur Bayésien de point de changement qui est plus facile à analyser mathématiquement en termes de taux de fausses alarmes et de délai de détection (qui sont les critères les plus courants pour la détection de point de changement). Ensuite, nous introduisons le problème d'exploration décentralisée dans le cadre du bandit manchot où un ensemble de joueurs collaborent pour identifier le meilleur bras en interagissant de manière asynchrone avec le même environnement stochastique. Nous proposons une première solution générique appelée élimination décentralisée qui utilise n'importe quel algorithme d'identification du meilleur bras comme sous-programme avec la garantie que l'algorithme assure la confidentialité, avec un faible coût de communication. Enfin, nous effectuons une évaluation des stratégies de bandit manchot dans deux contextes différents de réseaux de télécommunications. Tout d'abord, dans le contexte LoRaWAN (Long Range Wide Area Network), nous proposons d'utiliser des algorithmes de bandit manchot à la place de l'algorithme par défaut qui porte le nom d’ADR (Adaptive Data Rate) afin de minimiser la consommation d'énergie et les pertes de paquets des terminaux. Ensuite, dans le contexte IEEE 802.15.4-TSCH, nous effectuons une évaluation de 9 algorithmes de bandits manchot afin de sélectionner ceux qui choisissent les canaux les plus performants, en utilisant les données collectées via la plateforme FIT IoT-LAB. L'évaluation des performances suggère que notre proposition peut améliorer considérablement le taux de livraison des paquets par rapport à la procédure TSCH par défaut, augmentant ainsi la fiabilité et l'efficacité énergétique des transmissions.In this PhD thesis, we study the non-stationary multi-armed bandit problem where the non-stationarity behavior of the environment is characterized by several abrupt changes called "change-points". We propose Memory Bandits: a combination between an algorithm for the stochastic multi-armed bandit and the Bayesian Online Change-Point Detector (BOCPD). The analysis of the latter has always been an open problem in the statistical and sequential learning theory community. For this reason, we derive a variant of the Bayesian Online Change-point detector which is easier to mathematically analyze in term of false alarm rateand detection delay (which are the most common criteria for online change-point detection). Then, we introduce the decentralized exploration problem in the multi-armed bandit paradigm where a set of players collaborate to identify the best arm by asynchronously interacting with the same stochastic environment. We propose a first generic solution called decentralized elimination: which uses any best arm identification algorithm as a subroutine with the guar-antee that the algorithm ensures privacy, with a low communication cost. Finally, we perform an evaluation of the multi-armed bandit strategies in two different context of telecommunication networks. First, in LoRaWAN (Long Range Wide Area Network) context, we propose to use multi-armed bandit algorithms instead of the default algorithm ADR (Adaptive Data Rate) in order to minimize the energy consumption and the packet losses of end-devices. Then, in a IEEE 802.15.4-TSCH context, we perform an evaluation of 9 multi-armed bandit algorithms in order to select the ones that choose high-performance channels, using data collected through the FIT IoT-LAB platform. The performance evaluation suggests that our proposal can significantly improve the packet delivery ratio compared to the default TSCH operation, thereby increasing the reliability and the energy efficiency of the transmissions