Note ABES Privacy-Utility Trade-offs in Sequential Decision-Making under Uncertainty Compromis entre confidentialité et utilité dans la prise de décision séquentielle dans l’incertain Apprentissage automatique Confidentialité différentielle Apprentissage par Renforcement Bandit à plusieurs bra Inférence d'appartenance Machine Learning Differential Privacy Reinforcement Learning Multi Armed Bandits Membership Inference Prise de décision (statistique) Apprentissage par renforcement (intelligence artificielle) Protection de l'information (informatique) Problème du bandit manchot 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. Electronic Thesis or Dissertation Text en PDF 2608209 https://pepite-depot.univ-lille.fr/LIBRE/EDMADIS/2024/2024ULILB029.pdf https://theses.hal.science/tel-04928349 https://theses.fr/2024ULILB029/abes https://theses.hal.science/tel-04928349 https://theses.hal.science/tel-04928349 https://theses.hal.science/tel-04928349 Azize Achraf Azize 1998-01-01 MA 282998144 https://theses.fr/2024ULILB029 2024ULILB029 https://doi.org/10.70675/b27f565bz0d3cz47b1za7eez4d5c783c33d6 2024-11-26 Informatique et applications Université de Lille (2022-....) 259265152 Doctorat Docteur es non oui Preux Philippe MADS_DIRECTEUR_DE_THESE_1 059896353 Basu Debabrota MADS_DIRECTEUR_DE_THESE_2 269428674 Dimitrakakis Christos MADS_PRESIDENT_DU_JURY 250404117 Palamidessi Catuscia MADS_MEMBRE_DU_JURY_1 076309495 Smith Adam MADS_RAPPORTEUR_1 282986332 Garivier Aurélien MADS_RAPPORTEUR_2 111902495 École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) MADS_ECOLE_DOCTORALE_1 258621362 Centre Inria de l'Université de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 104752 185432247 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_2 410272 18388695X ddc:004 Preux Philippe Basu Debabrota Dimitrakakis Christos Palamidessi Catuscia Smith Adam Garivier Aurélien École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) Centre Inria de l'Université de Lille Centre de Recherche en Informatique, Signal et Automatique de Lille PDF 2608209