Academic literature on the topic 'Bandit à plusieurs bra'

Il était une fois un bandit de grand chemin nommé Ransomware … Voilà qui pourrait débuter la narration qui va suivre concernant ce malandrin, un brigand des Temps modernes. S’il n’est plus question des guerres qui ont opposé si longtemps la France à l’Angleterre, l’analogie avec les cybercriminels n’est pas si éloignée de cela. Sans doute cela est-il dû au fait qu’il s’agisse d’attaques perpétrées par des bandes d’assaillants ayant pour unique objectif la remise de fonds, l’obtention d’un butin, et ce, sur les chemins que sont nos autoroutes de l’information, nos réseaux sociaux, nos routes d’échanges numériques. L’actualité SI & IT, cyber et criminelle fait la part belle depuis plusieurs années à ce phénomène. Le rançongiciel ne distingue pas ses victimes (quelques exceptions dernièrement) mais s’affranchit de toutes frontières, règles, lois, pour n’user que de celles lui permettant d’atteindre son objectif. Car ne perdons pas de vue que les auteurs d’attaques par rançongiciels poursuivent des objectifs liés à la déstabilisation et à la terreur au sein d’une entreprise ou chez un particulier.

Cette thèse présente des avancées dans les algorithmes d'apprentissage par renforcement (RL) pour la gestion des ressources et des politiques dans les problèmes de bandit multiarmé sans repos (RMAB). Nous développons des algorithmes à travers deux approches dans ce domaine. Premièrement, pour les problèmes avec des actions discrètes et binaires, ce qui est le cas original de RMAB, nous avons développé QWI et QWINN. Ces algorithmes calculent les indices de Whittle, une heuristique qui découple les différents processus RMAB, simplifiant ainsi la détermination de la politique. Deuxièmement, pour les problèmes avec des actions continues, qui se généralisent aux processus de décision de Markov faiblement couplés (MDP), nous proposons LPCA. Cet algorithme utilise une relaxation lagrangienne pour découpler les différents PDM.Les algorithmes QWI et QWINN sont présentés comme des méthodes à deux échelles de temps pour le calcul des indices de Whittle pour les problèmes RMAB. Dans nos résultats, nous montrons mathématiquement que les estimations des indices de Whittle de l'algorithme QWI convergent vers les valeurs théoriques. QWINN, une extension de QWI, incorpore des réseaux neuronaux pour calculer les valeurs Q utilisées pour calculer les indices de Whittle. Grâce à nos résultats, nous présentons les propriétés de convergence locale du réseau neuronal utilisé dans QWINN. Nos résultats montrent que QWINN est plus performant que QWI en termes de taux de convergence et d'évolutivité.Dans le cas de l'action continue, l'algorithme LPCA applique une relaxation lagrangienne pour découpler les processus de décision liés, ce qui permet un calcul efficace des politiques optimales sous contrainte de ressources. Nous proposons deux méthodes d'optimisation différentes, l'évolution différentielle et les stratégies d'optimisation gourmande, pour gérer efficacement l'allocation des ressources. Dans nos résultats, LPCA montre des performances supérieures à d'autres approches RL contemporaines.Les résultats empiriques obtenus dans différents environnements simulés valident l'efficacité des algorithmes proposés.Ces algorithmes représentent une contribution significative au domaine de l'allocation des ressources dans le cadre de l'apprentissage par renforcement et ouvrent la voie à de futures recherches sur des cadres d'apprentissage par renforcement plus généralisés et évolutifs
This thesis presents advances in Reinforcement Learning (RL) algorithms for resource and policy management in Restless Multi-Armed Bandit (RMAB) problems. We develop algorithms through two approaches in this area. First, for problems with discrete and binary actions, which is the original case of RMAB, we have developed QWI and QWINN. These algorithms compute Whittle indices, a heuristic that decouples the different RMAB processes, thereby simplifying the policy determination. Second, for problems with continuous actions, which generalize to Weakly Coupled Markov Decision Processes (MDPs), we propose LPCA. This algorithm employs a Lagrangian relaxation to decouple the different MDPs.The QWI and QWINN algorithms are introduced as two-timescale methods for computing Whittle indices for RMAB problems. In our results, we show mathematically that the estimates of Whittle indices of QWI converge to the theoretical values. QWINN, an extension of QWI, incorporates neural networks to compute the Q-values used to compute the Whittle indices. Through our results, we present the local convergence properties of the neural network used in QWINN. Our results show how QWINN outperforms QWI in terms of convergence rates and scalability.In the continuous action case, the LPCA algorithm applies a Lagrangian relaxation to decouple the linked decision processes, allowing for efficient computation of optimal policies under resource constraints. We propose two different optimization methods, differential evolution and greedy optimization strategies, to efficiently handle resource allocation. In our results, LPCA shows superior performance over other contemporary RL approaches.Empirical results from different simulated environments validate the effectiveness of the proposed algorithms.These algorithms represent a significant contribution to the field of resource allocation in RL and pave the way for future research into more generalized and scalable reinforcement learning frameworks

Les thèmes abordés dans cette thèse visent à caractériser les compromis à réaliser entre confidentialité et utilité dans la prise de décision séquentielle dans l'incertain. Le principal cadre adopté pour définir la confidentialité est la protection différentielle, et le principal cadre d'utilité est le problème de bandit stochastique à plusieurs bras. Tout d'abord, nous proposons différentes définitions qui étendent la définition de confidentialité à l'environnement des bandits à plusieurs bras.Ensuite, nous quantifions la difficulté des bandits avec protection différentielle en prouvant des bornes inférieures sur la performance des algorithmes de bandits confidentielles. Ces bornes suggèrent l'existence de deux régimes de difficulté en fonction du budget de confidentialité et des distributions de récompenses.Nous proposons également un plan générique pour concevoir des versions confidentielles quasi-optimales des algorithmes de bandits.Nous instancions ce schéma directeur pour concevoir des versions confidentielles de différents algorithmes de bandits dans différents contextes: bandits à bras finis, linéaires et contextuels avec le regret comme mesure d'utilité, et bandits à bras finis avec la complexité d'échantillonnage comme mesure d'utilité.L'analyse théorique et expérimentale des algorithmes proposés valide aussi l'existence de deux régimes de difficulté en fonction du budget de confidentialité.Dans la deuxième partie de cette thèse, nous passons des défenses de la confidentialité aux attaques. Plus précisément, nous étudions les attaques par inférence d'appartenance où un adversaire cherche à savoir si un point cible a été inclus ou pas dans l'ensemble de données d'entrée d'un algorithme. Nous définissons la fuite d'information sur un point comme l'avantage de l'adversaire optimal essayant de déduire l'appartenance de ce point.Nous quantifions ensuite cette fuite d'information pour la moyenne empirique et d'autres variantes en termes de la distance de Mahalanobis entre le point cible et la distribution génératrice des données.Notre analyse asymptotique repose sur une nouvelle technique de preuve qui combine une expansion de Edgeworth du test de vraisemblance et un théorème central limite de Lindeberg-Feller.Notre analyse montre que le test de vraisemblance pour la moyenne empirique est une attaque par produit scalaire mais corrigé pour la géométrie des données en utilisant l'inverse de la matrice de covariance.Enfin, comme conséquences de notre analyse, nous proposons un nouveau score de covariance et une nouvelle stratégie de sélection des points cible pour l'audit des algorithmes de descente de gradient dans le cadre de l'apprentissage fédéré en white-box
The topics addressed in this thesis aim to characterise the privacy-utility trade-offs in sequential decision-making under uncertainty. The main privacy framework adopted is Differential Privacy (DP), and the main setting for studying utility is the stochastic Multi-Armed Bandit (MAB) problem. First, we propose different definitions that extend DP to the setting of multi-armed bandits. Then, we quantify the hardness of private bandits by proving lower bounds on the performance of bandit algorithms verifying the DP constraint. These bounds suggest the existence of two hardness regimes depending on the privacy budget and the reward distributions. We further propose a generic blueprint to design near-optimal DP extensions of bandit algorithms. We instantiate the blueprint to design DP versions of different bandit algorithms under different settings: finite-armed, linear and contextual bandits under regret as a utility measure, and finite-armed bandits under sample complexity of identifying the optimal arm as a utility measure. The theoretical and experimental analysis of the proposed algorithms furthermore validates the existence of two hardness regimes depending on the privacy budget.In the second part of this thesis, we shift the view from privacy defences to attacks. Specifically, we study fixed-target Membership Inference (MI) attacks, where an adversary aims to infer whether a fixed target point was included or not in the input dataset of an algorithm. We define the target-dependent leakage of a datapoint as the advantage of the optimal adversary trying to infer the membership of that datapoint. Then, we quantify both the target-dependent leakage and the trade-off functions for the empirical mean and variants of interest in terms of the Mahalanobis distance between the target point and the data-generating distribution. Our asymptotic analysis builds on a novel proof technique that combines an Edgeworth expansion of the Likelihood Ratio (LR) test and a Lindeberg-Feller central limit theorem. Our analysis shows that the LR test for the empirical mean is a scalar product attack but corrected for the geometry of the data using the inverse of the covariance matrix. Finally, as by-products of our analysis, we propose a new covariance score and a new canary selection strategy for auditing gradient descent algorithms in the white-box federated learning setting

Cette thèse s'inscrit dans le domaine des statistiques séquentielles. Le cadre principal étudié est celui des bandits stochastiques à plusieurs bras, cadre idéal qui modélise le dilemme exploration-exploitation face à des choix répétés. La thèse est composée de quatre chapitres, précédés d'une introduction. Dans la première partie du corps de la thèse, on présente un nouvel algorithme capable d'atteindre des garanties optimales à la fois d'un point de vue distribution-dépendent et distribution-free. Les deux chapitres suivants sont consacrés à des questions dites d'adaptation. D'abord, on propose un algorithme capable de s'adapter à la régularité inconnue dans des problèmes de bandits continus, mettant en évidence le coût polynomial de l'adaptation en bandits continus. Ensuite, on considère un problème d'adaptation au supports pour des problèmes de bandits à K bras, à distributions de paiements bornés dans des intervalles inconnus. Enfin, dans un dernier chapitre un peu à part, on étudie un cadre légèrement différent de bandits préservant la diversité. On montre que le regret optimal dans ce cadre croît à des vitesses différentes des vitesses classiques, avec notamment la possibilité d'atteindre un regret constant sous certaines hypothèses
The main topics adressed in this thesis lie in the general domain of sequential learning, and in particular stochastic multi-armed bandits. The thesis is divided into four chapters and an introduction. In the first part of the main body of the thesis, we design a new algorithm achieving, simultaneously, distribution-dependent and distribution-free optimal guarantees. The next two chapters are devoted to adaptivity questions. First, in the context of continuum-armed bandits, we present a new algorithm which, for the first time, does not require the knowledge of the regularity of the bandit problem it is facing. Then, we study the issue of adapting to the unknown support of the payoffs in bounded K-armed bandits. We provide a procedure that (almost) obtains the same guarantees as if it was given the support in advance. In the final chapter, we study a slightly different bandit setting, designed to enforce diversity-preserving conditions on the strategies. We show that the optimal regert in this setting at a speed that is quite different from the traditional bandit setting. In particular, we observe that bounded regret is possible under some specific hypotheses

Motivés par les scénarios de diffusion de l'information et de publicité dans le les réseaux sociaux, nous étudions un problème de maximisation de l'influence (MI) dans lequel on suppose que l'on en sait peu sur le réseau de diffusion ou sur le modèle qui détermine comment l'information peut se propager.Dans un tel environnement incertain, on peut se concentrer sur des campagnes de diffusion à plusieurs tours, avec l'objectif de maximiser le nombre d'utilisateurs distincts qui sont influencés ou activés, à partir d'une base de nœuds influents.Au cours d'une campagne, les graines de propagation sont sélectionnées séquentiellement lors de tours consécutifs, et les commentaires sont collectés sous la forme des nœuds activés à chaque tour.L'impact (récompense) d'un tour est alors quantifié par le nombre de nœuds nouvellement activés. En général, il faut maximiser la propagation totale de la campagne, comme la somme des récompenses des tours.Nous considérons deux sous-classes de d'IM, emph{cimp} (CIMP) et emph{ecimp} (ECIMP), où (i) la récompense d'un tour d'une campagne en cours consiste uniquement en de nouvelles activations (non observées lors des tours précédents de cette campagne),(ii) le contexte du tour et les données historiques des tours précédents peuvent être exploités pour apprendre la meilleure politique, et(iii) ECIMP est CIMP répété plusieurs fois, ce qui permet d'apprendre également des campagnes précédentes.Ce problème est directement motivé par les scénarios du monde réel de la diffusion de l'information dans le marketing d'influence, où (i) seule la première / unique activation d'un utilisateur cible présente un intérêt (et cette activation persistera comme une activation acquise, latente, tout au long de la campagne).(ii) de précieuses informations secondaires sont disponibles pour l'agent d'apprentissageDans ce contexte, une approche d'exploration-exploitation pourrait être utilisée pour apprendre les principaux paramètres de diffusion sous-jacents, tout en exécutant les campagnes.Pour CIMP, nous décrivons et comparons deux méthodes de bandits à bras multiples contextuels, avec des limites supérieures de confiance sur le potentiel restant des influenceurs, l'une utilisant un modèle linéaire généralisé et l'estimateur de Good-Turing pour le potentiel restant, et l'autre adaptant directement l'algorithme LinUCB à notre cadre.Pour ECIMP, nous proposons l'algorithmelgtlsvi qui implémente le principe d'optimisme face à l'incertitude pour l'apprentissage par renforcement, avec approximation linéaire.L'agent d'apprentissage estime pour chaque nœud de départ son potentiel restant avec un estimateur de Good-Turing, modifié par une fonction Q estimée. Nous montrons qu'ils surpassent les performances des méthodes de base utilisant les idées les plus récentes, sur des données synthétiques et réelles, tout en présentant un comportement différent et complémentaire, selon les scénarios dans lesquels ils sont déployés
Motivated by scenarios of information diffusion and advertising in social media, we study an emph{influence maximization} (IM) problem in which little is assumed to be known about the diffusion network or about the model that determines how information may propagate. In such a highly uncertain environment, one can focus on emph{multi-round diffusion campaigns}, with the objective to maximize the number of distinct users that are influenced or activated, starting from a known base of few influential nodes.During a campaign, spread seeds are selected sequentially at consecutive rounds, and feedback is collected in the form of the activated nodes at each round.A round's impact (reward) is then quantified as the number of emph{newly activated nodes}.Overall, one must maximize the campaign's total spread, as the sum of rounds' rewards.We consider two sub-classes of IM, emph{cimp} (CIMP) and emph{ecimp} (ECIMP), where (i) the reward of a given round of an ongoing campaign consists of only the extit{new activations} (not observed at previous rounds within that campaign), (ii) the round's context and the historical data from previous rounds can be exploited to learn the best policy, and (iii) ECIMP is CIMP repeated multiple times, offering the possibility of learning from previous campaigns as well.This problem is directly motivated by the real-world scenarios of information diffusion in emph{influencer marketing}, where (i) only a target user's emph{first} / unique activation is of interest (and this activation will emph{persist} as an acquired, latent one throughout the campaign), and (ii) valuable side-information is available to the learning agent.In this setting, an explore-exploit approach could be used to learn the key underlying diffusion parameters, while running the campaigns.For CIMP, we describe and compare two methods of emph{contextual multi-armed bandits}, with emph{upper-confidence bounds} on the remaining potential of influencers, one using a generalized linear model and the Good-Turing estimator for remaining potential (glmucb), and another one that directly adapts the LinUCB algorithm to our setting (linucb).For ECIMP, we propose the algorithmlgtlsvi, which implements the extit{optimism in the face of uncertainty} principle for episodic reinforcement learning with linear approximation. The learning agent estimates for each seed node its remaining potential with a Good-Turing estimator, modified by an estimated Q-function.We show that they outperform baseline methods using state-of-the-art ideas, on synthetic and real-world data, while at the same time exhibiting different and complementary behavior, depending on the scenarios in which they are deployed