KAUFMANN Emilie

Dans cet article, nous proposons de nouvelles bornes inférieures indépendantes du problème sur la complexité d'échantillonnage et le regret dans les MDPs épisodiques, avec un accent particulier sur le cas non-stationnaire dans lequel le noyau de transition est autorisé à changer à chaque étape de l'épisode. Notre principale contribution est une borne inférieure de Ω((H 3 SA/ε 2) log(1/δ)) sur la complexité d'échantillonnage d'un algorithme (ε, δ)-PAC pour l'identification de la meilleure politique dans un MDP non-stationnaire, en s'appuyant sur une construction de "MDPs durs" qui est différente de celles utilisées précédemment dans la littérature. En utilisant cette même classe de MDPs, nous fournissons également une preuve rigoureuse de la borne de regret Ω(√ H 3 SAT) pour les MDPs non-stationnaires. Enfin, nous discutons des liens avec les bornes inférieures de PAC-MDP.

Pas de résumé disponible.

Motivés par une application à la réadaptation des médicaments, nous proposons les premiers algorithmes pour traiter l'identification des m ≥ 1 bras avec les plus grandes moyennes dans un modèle de bandit linéaire, dans le cadre de la confiance fixe. Ces algorithmes appartiennent à la famille générique des Gap-Index Focused Algorithms (GIFA) que nous introduisons pour l'identification du Top-m dans les bandits linéaires. Nous proposons une analyse unifiée de ces algorithmes, qui montre comment l'utilisation de caractéristiques peut réduire la complexité de l'échantillon. Nous validons en outre ces algorithmes de manière empirique sur des données simulées et sur une tâche simple de reprogrammation de médicaments.

Les environnements réalistes fournissent souvent aux agents un feedback très limité. Lorsque l'environnement est initialement inconnu, le retour d'information, au début, peut être complètement absent, et les agents peuvent d'abord choisir de consacrer tous leurs efforts à une exploration efficace. L'exploration reste un défi, bien qu'elle ait été abordée d'une part avec de nombreuses heuristiques réglées à la main avec différents niveaux de généralité, et d'autre part avec quelques stratégies d'exploration fondées sur la théorie. Beaucoup d'entre elles sont incarnées par la motivation intrinsèque et en particulier les bonus d'exploration. Une règle empirique commune pour les bonus d'exploration est d'utiliser 1/ √ n bonus qui est ajouté aux estimations empiriques de la récompense, où n est un nombre de fois que cet état particulier (ou une paire état-action) a été visité. Nous montrons que, de manière surprenante, pour un objectif d'exploration pure sans récompense, les bonus qui s'échelonnent avec 1/n apportent des taux d'apprentissage plus rapides, améliorant les limites supérieures connues par rapport à la dépendance de l'horizon H. De plus, nous montrons qu'avec une analyse améliorée du temps d'arrêt, nous pouvons améliorer d'un facteur H la complexité de l'échantillon dans le cadre de l'identification de la meilleure politique, qui est un autre objectif d'exploration pure, où l'environnement fournit des récompenses mais l'agent n'est pas pénalisé pour son comportement pendant la phase d'exploration.

Dans cet article, nous proposons le premier algorithme de bandit à bras multiples basé sur le rééchantillonnage qui atteint un regret asymptotiquement optimal simultanément pour différentes familles de bras (à savoir les distributions de Bernoulli, Gaussienne et Poisson). Contrairement à l'échantillonnage de Thompson qui nécessite de spécifier un antécédent différent pour être optimal dans chaque cas, notre proposition RB-SDA ne nécessite aucun réglage dépendant de la distribution. RB-SDA appartient à la famille des algorithmes de duel par sous-échantillonnage (SDA) qui combine l'idée de sous-échantillonnage utilisée pour la première fois par les algorithmes BESA [1] et SSMC [2] avec différents schémas de sous-échantillonnage. En particulier, RB-SDA utilise l'échantillonnage par blocs aléatoires. Nous réalisons une étude expérimentale pour évaluer la flexibilité et la robustesse de cette nouvelle approche prometteuse pour l'exploration dans les modèles de bandits.

Pas de résumé disponible.

L'exploration sans récompense est un cadre d'apprentissage par renforcement récemment étudié par Jin et al. qui l'abordent en exécutant plusieurs algorithmes avec des garanties de regret en parallèle. Dans notre travail, nous proposons plutôt une approche plus adaptative pour l'exploration sans récompense qui réduit directement les limites supérieures de l'erreur maximale d'estimation du MDP. Nous montrons que, de manière intéressante, notre algorithme UCRL sans récompense peut être considéré comme une variante d'un algorithme de Fiechter de 1994 [11], proposé à l'origine pour un objectif différent que nous appelons identification de la meilleure politique. Nous prouvons que RF-UCRL a besoin de O (SAH 4 /ε 2) log(1/δ) épisodes pour produire, avec une probabilité de 1 - δ, une ε-approximation de la politique optimale pour toute fonction de récompense. Nous la comparons empiriquement à des stratégies oracle utilisant un modèle génératif.

Nous proposons MDP-GapE, un nouvel algorithme de Monte-Carlo Tree Search basé sur la trajectoire pour la planification dans un processus de décision de Markov dans lequel les transitions ont un support fini. Nous prouvons une limite supérieure sur le nombre d'appels aux modèles génératifs nécessaires pour que MDP-GapE identifie une action quasi-optimale avec une probabilité élevée. Ce résultat de complexité d'échantillon dépendant du problème est exprimé en termes d'écarts de sous-optimalité des paires état-action qui sont visitées pendant l'exploration. Nos expériences révèlent que MDP-GapE est également efficace en pratique, contrairement à d'autres algorithmes avec des garanties de complexité d'échantillon dans le cadre de la confiance fixe, qui sont principalement théoriques.

Nous étudions le problème de la recherche du dosage optimal dans les premiers essais cliniques à travers le prisme du bandit à bras multiples. Nous préconisons l'utilisation du principe d'échantillonnage de Thompson, un algorithme flexible qui peut s'adapter à différents types d'hypothèses de monotonicité sur la toxicité et l'efficacité des doses. Pour la version la plus simple de l'échantillonnage de Thompson, basée sur une distribution antérieure uniforme pour chaque dose, nous fournissons des limites supérieures en temps fini sur le nombre de sélections de doses sous-optimales, ce qui est sans précédent pour les algorithmes de recherche de doses. Par le biais d'une vaste étude de simulation, nous montrons ensuite que les variantes de l'échantillonnage de Thompson basées sur des distributions préalables plus sophistiquées surpassent les algorithmes d'identification de dose de pointe dans différents types d'études de détermination de dose qui se produisent dans les essais de phase I ou de phase I/II.

Nous considérons le dilemme exploration-exploitation dans les problèmes d'apprentissage par renforcement à horizon fini dont l'espace état-action est doté d'une métrique. Nous présentons Kernel-UCBVI, un algorithme optimiste basé sur un modèle qui exploite la fluidité du MDP et un estimateur à noyau non paramétrique des récompenses et des transitions pour équilibrer efficacement l'exploration et l'exploitation. Contrairement aux approches existantes avec des garanties de regret, il n'utilise aucun type de partitionnement de l'espace état-action. Pour les problèmes avec K épisodes et un horizon H, nous fournissons une limite de regret de O H 3 K max(1 2 , 2d 2d+1) , où d est la dimension de couverture de l'espace état-action conjoint. Nous validons empiriquement Kernel-UCBVI sur des MDPs discrets et continus.

Nous étudions un problème de bandit stochastique multijoueur à plusieurs bras dans lequel les joueurs ne peuvent pas communiquer, et si deux joueurs ou plus tirent le même bras, une collision se produit et les joueurs impliqués reçoivent une récompense nulle. Nous considérons le cadre hétérogène difficile, dans lequel différents bras peuvent avoir des moyens différents pour différents joueurs, et nous proposons un nouvel algorithme efficace qui combine l'idée de tirer parti des collisions forcées pour une communication implicite et celle d'effectuer des éliminations de correspondance. Nous donnons une analyse en temps fini de notre algorithme, en limitant son regret par O((log T)^{1+\kappa}) pour tout \kappa>0 fixe. Si l'affectation optimale des joueurs aux armes est unique, nous montrons en outre qu'elle atteint le regret optimal O(log(T)), résolvant ainsi une question ouverte soulevée à NeurIPS 2018.

Dans cet article, nous étudions les problèmes de tests séquentiels avec des hypothèses qui se chevauchent. Nous nous concentrons d'abord sur le problème simple consistant à évaluer si la moyenne µ d'une distribution gaussienne est $≥ ε- ou ≤ε. Si µ ∈ (-ε,ε)$, les deux réponses sont considérées comme correctes. Ensuite, nous considérons l'identification du meilleur bras PAC dans un modèle de bandit : étant donné K distributions de probabilité sur R avec des moyennes $µ_1,.... , µ_K$ , nous dérivons la complexité asymptotique de l'identification, avec un risque au plus égal à $δ$, d'un indice $I ∈ {1, . , K}$ tel que $µ_I ≥ max_i µ_i -ε$. Nous fournissons des bornes non asymptotiques sur l'erreur d'un test de rapport de vraisemblance général parallèle, qui peut également être utilisé pour des problèmes de test plus généraux. Nous proposons également des bornes inférieures sur le nombre d'observations nécessaires pour identifier une hypothèse correcte. Ces limites inférieures reposent sur des arguments de la théorie de l'information, et plus particulièrement sur deux versions d'un lemme de changement de mesure (une forme de haut niveau et une forme de bas niveau) dont les mérites relatifs sont discutés.

Nous étudions un test pour la détection séquentielle de rupture, basé sur le rapport de vraisemblance généralisé (GLR) et qui s'exprime en fonction de l'entropie relative binaire. Il s'applique à la détection de rupture sur la moyenne d'une distribution bornée, et nous obtenons un contrôle non-asymptotique de sa probabilité de fausse alarme et de son délai de détection. Nous expliquons son utilisation pour la prise de décision séquentielle en proposant la stratégie de bandit GLR-klUCB, efficace dans des modèles de bandit stationnaires par morceaux.

Nous étudions et fournissons de nouvelles perspectives sur la règle d'échantillonnage appelée Top-Two Thompson Sampling (TTTS). En particulier, nous justifions son utilisation pour l'identification du meilleur bras à confiance fixe. Nous proposons également une variante du TTTS appelée Top-Two Transportation Cost (T3C), qui élimine la charge de calcul du TTTS. Comme contribution principale, nous fournissons la première analyse de complexité d'échantillon de TTTS et T3C lorsqu'ils sont couplés avec une règle d'arrêt bayésienne très naturelle, pour des bandits avec des récompenses gaussiennes, résolvant une des questions ouvertes soulevées par Russo (2016). Nous fournissons également de nouveaux résultats de convergence postérieure pour TTTS sous deux modèles couramment utilisés dans la pratique : bandits avec récompenses gaussiennes et Bernoulli et prieurs conjugués.

Le réglage des hyperparamètres est une partie importante des systèmes modernes d'apprentissage automatique. Le réglage lui-même peut être considéré comme un problème d'allocation séquentielle des ressources. À ce titre, des méthodes de bandits à bras multiples ont déjà été appliquées. Dans cet article, nous considérons l'optimisation des hyperparamètres comme une instance de l'identification du meilleur bras dans des bandits à nombre infini de bras. Nous proposons D-TTTS, un nouvel algorithme adaptatif inspiré de l'échantillonnage de Thompson, qui équilibre dynamiquement entre le raffinement de l'estimation de la qualité des configurations d'hyper-paramètres précédemment explorées et l'ajout de nouvelles configurations d'hyper-paramètres au pool de candidats. L'algorithme est facile à mettre en œuvre et présente des performances compétitives par rapport aux algorithmes de pointe pour le réglage des hyperparamètres.

Nous étudions une généralisation du problème du bandit à plusieurs bras avec des jeux multiples où il y a un coût associé à la traction de chaque bras et l'agent a un budget à chaque moment qui dicte combien il peut s'attendre à dépenser. Nous dérivons une borne inférieure de regret asymptotique pour tout algorithme uniformément efficace dans notre cadre. Nous étudions ensuite une variante de l'échantillonnage de Thompson pour les récompenses de Bernoulli et une variante de KL-UCB pour les familles exponentielles à un paramètre et les récompenses bornées à support fini. Nous montrons que ces algorithmes sont asymptotiquement optimaux, à la fois en termes de taux et de constantes dépendantes du problème, y compris dans le cadre de la marge épaisse où plusieurs bras tombent sur la limite de décision.

Les bandits stochastiques de rang un (Katarya et al, (2017a,b)) sont un cadre simple pour les problèmes de minimisation du regret sur les matrices de rang un d'armes. Les algorithmes initialement proposés sont prouvés avoir un regret logarithmique, mais ne correspondent pas à la borne inférieure existante pour ce problème. Nous comblons cette lacune en prouvant d'abord que les bandits rank-one sont une instance particulière des bandits unimodaux, puis en fournissant une nouvelle analyse de l'échantillonnage Thompson unimodal (UTS), initialement proposé par Paladino et al (2017). Nous prouvons une limite de regret asymptotiquement optimale sur le regret fréquentiste de l'UTS et nous soutenons nos affirmations avec des simulations montrant l'amélioration significative de notre méthode par rapport à l'état de l'art.

Les bandits hiérarchiques sont une approche pour l'optimisation globale de fonctions extrêmement irrégulières. Cet article fournit de nouveaux éléments concernant POO, un méta-algorithme adaptatif qui ne nécessite pas la connaissance de la régularité locale de la fonction cible. Nous mettons d'abord en évidence le fait que l'algorithme de sous-routine utilisé dans POO doit avoir un petit regret sous l'hypothèse de lissage local par rapport au partitionnement choisi, qui est inconnu s'il est satisfait par le sous-routine standard HOO. Dans ce travail, nous établissons une telle garantie de regret pour HCT, qui est un autre algorithme d'optimisation optimiste hiérarchique qui a besoin de connaître la régularité. Cela confirme la validité de POO. Nous montrons que POO peut être utilisé avec HCT comme sous-programme avec une borne supérieure de regret qui correspond à celle des algorithmes les plus connus utilisant la connaissance de la régularité jusqu'à un facteur √ log n. En plus de cela, nous proposons une enveloppe générale, appelée GPO, qui peut faire face aux algorithmes qui n'ont que des garanties de regret simples. Enfin, nous complétons nos résultats par des expériences sur des fonctions difficiles.

Nous proposons un nouvel algorithme pour le problème de bandit non stationnaire i.i.d. par morceaux avec récompenses bornées. Notre proposition, GLR-klUCB, combine un algorithme de bandit efficace, klUCB, avec un détecteur de points de changement efficace et sans paramètres, le test du rapport de vraisemblance généralisé de Bernoulli, pour lequel nous fournissons de nouvelles garanties théoriques d'intérêt indépendant. Nous analysons deux variantes de notre stratégie, basées sur des redémarrages locaux et des redémarrages globaux, et montrons que leur regret est limité par $O(\Upsilon_T \sqrt{T \log(T)})$ si le nombre de points de changement $Υ_T$ est inconnu, et par $O(\sqrt{\Upsilon_T T \log(T)})$ si $\Upsilon_T$ est connu. Ceci améliore les limites actuelles de l'état de l'art, car notre algorithme ne nécessite aucun réglage basé sur la connaissance de la complexité du problème autre que $Υ_T$. Nous présentons des expériences numériques montrant que GLR-klUCB surpasse les algorithmes passifs et activement adaptatifs de la littérature, et nous soulignons l'avantage d'utiliser des redémarrages locaux.

Nous étudions une généralisation du problème du bandit à plusieurs bras avec des jeux multiples où il y a un coût associé à la traction de chaque bras et l'agent a un budget à chaque moment qui dicte combien il peut s'attendre à dépenser. Nous dérivons une borne inférieure de regret asymptotique pour tout algorithme uniformément efficace dans notre cadre. Nous étudions ensuite une variante de l'échantillonnage de Thompson pour les récompenses de Bernoulli et une variante de KL-UCB pour les familles exponentielles à un paramètre et les récompenses bornées à support fini. Nous montrons que ces algorithmes sont asymptotiquement optimaux, à la fois en termes de taux et de constantes dépendantes du problème, y compris dans le cadre de la marge épaisse où plusieurs bras tombent sur la limite de décision.

Cet article présente un nouvel algorithme spectral avec regroupement additif, conçu pour identifier les communautés qui se chevauchent dans les réseaux. L'algorithme est basé sur les propriétés géométriques du spectre de la matrice d'adjacence attendue dans un modèle de graphe aléatoire que nous appelons modèle de bloc stochastique avec chevauchement (SBMO). Il est prouvé qu'une version adaptative de l'algorithme, qui ne nécessite pas la connaissance du nombre de communautés cachées, est cohérente sous le SBMO lorsque les degrés du graphe sont (légèrement plus que) logarithmiques. On montre que l'algorithme fonctionne bien sur des données simulées et sur des graphes du monde réel avec des communautés connues qui se chevauchent.

Nous considérons le problème de l'identification quasi-optimale des bras dans le cadre de confiance fixe du problème du bandit infiniment armé lorsque rien n'est connu de la distribution du réservoir des bras. Nous (1) introduisons un cadre de type PAC dans lequel nous pouvons dériver et présenter des résultats. (2) dériver une limite inférieure de complexité d'échantillon pour une identification de bras quasi-optimale. (3) proposer un algorithme qui identifie un bras quasi-optimal avec une probabilité élevée et dériver une limite supérieure sur sa complexité d'échantillon qui est dans un facteur logarithmique de notre limite inférieure. et (4) discuter si notre dépendance log^2(1/delta) est inéluctable pour les algorithmes "à deux phases" (sélectionner les bras d'abord, identifier le meilleur plus tard) dans le cadre infini. Ce travail permet d'appliquer les modèles de bandit à une classe plus large de problèmes pour lesquels moins d'hypothèses s'appliquent.

Cet article présente de nouvelles inégalités de déviation qui sont valables uniformément en temps sous échantillonnage adaptatif dans un modèle de bandit à plusieurs bras. Les déviations sont mesurées en utilisant la divergence de Kullback-Leibler dans une famille exponentielle unidimensionnelle donnée, et peuvent prendre en compte plusieurs bras à la fois. Elles sont obtenues en construisant pour chaque bras une martingale de mélange basée sur une antériorité hiérarchique, et en multipliant ces martingales. Nos inégalités de déviation nous permettent d'analyser des règles d'arrêt basées sur des rapports de vraisemblance généralisés pour une grande classe de problèmes d'identification séquentielle, et de construire des intervalles de confiance serrés pour certaines fonctions des moyennes des bras.

Les bandits hiérarchiques sont une approche pour l'optimisation globale de fonctions extrêmement irrégulières. Cet article fournit de nouveaux éléments concernant POO, un méta-algorithme adaptatif qui ne nécessite pas la connaissance de la régularité locale de la fonction cible. Nous mettons d'abord en évidence le fait que l'algorithme de sous-routine utilisé dans POO doit avoir un petit regret sous l'hypothèse de lissage local par rapport au partitionnement choisi, qui est inconnu s'il est satisfait par le sous-routine standard HOO. Dans ce travail, nous établissons une telle garantie de regret pour HCT, qui est un autre algorithme d'optimisation optimiste hiérarchique qui a besoin de connaître le lissage. Cela confirme la validité de POO. Nous montrons que POO peut être utilisé avec HCT comme une sous-routine avec une borne supérieure de regret qui correspond à celle des algorithmes les plus connus utilisant la connaissance de la régularité jusqu'à un facteur √ log n.

Les Bandits Multi-Armés (MAB) multi-joueurs ont été largement étudiés dans la littérature, motivés par des applications aux systèmes de Radio Cognitive. C'est également en raison de ces applications que nous motivons l'introduction de plusieurs niveaux de rétroaction pour les algorithmes MAB multi-joueurs. La plupart des travaux existants supposent que les informations de détection sont disponibles pour l'algorithme. Sous cette hypothèse, nous améliorons la limite inférieure de l'état de l'art pour le regret de tout algorithme décentralisé et nous introduisons deux algorithmes, RandTopM et MCTopM, dont on montre qu'ils surpassent empiriquement les algorithmes existants. De plus, nous fournissons de solides garanties théoriques pour ces algorithmes, y compris une notion d'optimalité asymptotique en termes de nombre de sélections de mauvais bras. Nous introduisons ensuite une heuristique prometteuse, appelée Selfish, qui peut fonctionner sans information de détection, ce qui est crucial pour les applications émergentes aux réseaux de l'Internet des objets. Nous étudions les performances empiriques de cet algorithme et fournissons quelques premiers éléments théoriques pour la compréhension de son comportement.

La mise en place des futurs réseaux de l'Internet des objets (IoT) nécessitera de supporter de plus en plus de dispositifs communicants. Nous prouvons que les dispositifs intelligents dans les bandes sans licence peuvent utiliser des algorithmes d'apprentissage MAB (Multi-Armed Bandit) pour améliorer l'exploitation des ressources. Nous évaluons la performance de deux algorithmes d'apprentissage MAB classiques, UCB1 et Thompson Sampling, pour gérer la prise de décision décentralisée de l'accès au spectre, appliquée aux réseaux IoT. ainsi que la performance d'apprentissage avec un nombre croissant de dispositifs finaux intelligents. Nous montrons que l'utilisation d'algorithmes d'apprentissage permet d'intégrer davantage de dispositifs dans ces réseaux, même lorsque tous les dispositifs finaux sont intelligents et changent dynamiquement de canal. Dans le scénario étudié, l'apprentissage stochastique MAB fournit un gain allant jusqu'à 16% en termes de probabilités de transmission réussie, et a des performances quasi optimales même dans des configurations non-stationnaires et non-i.i.d. avec une majorité de dispositifs intelligents.

Cet article présente un nouvel algorithme spectral avec regroupement additif conçu pour identifier les communautés qui se chevauchent dans les réseaux. L'algorithme est basé sur les propriétés géométriques du spectre de la matrice d'adjacence attendue dans un modèle de graphe aléatoire que nous appelons modèle de bloc stochastique avec chevauchement (SBMO). Il est prouvé qu'une version adaptative de l'algorithme, qui ne nécessite pas la connaissance du nombre de communautés cachées, est cohérente sous le SBMO lorsque les degrés du graphe sont (légèrement plus que) logarithmiques. On montre que l'algorithme fonctionne bien sur des données simulées et sur des graphes du monde réel avec des communautés connues qui se chevauchent.

Les algorithmes de bandits à bras multiples ont été récemment étudiés et évalués pour la radio cognitive (CR), en particulier dans le contexte de l'accès opportuniste au spectre (OSA). Plusieurs solutions ont été explorées sur la base de divers modèles, mais il est difficile de prédire exactement laquelle pourrait être la meilleure pour les conditions du monde réel à chaque instant. C'est pourquoi les algorithmes d'agrégation d'experts peuvent être utiles pour sélectionner en temps réel le meilleur algorithme pour une situation spécifique. Les algorithmes d'agrégation, tels que Exp4 datant de 2002, n'ont jamais été utilisés pour l'apprentissage de l'OSA, et nous montrons qu'il apparaît empiriquement sous-efficace lorsqu'il est appliqué à des problèmes stochastiques simples. Dans cet article, nous présentons une variante améliorée, appelée Aggregator. Nous présentons des résultats de simulation pour des problèmes OSA synthétiques modélisés comme des problèmes de bandits à plusieurs bras (MAB) afin de démontrer son efficacité empirique. Nous combinons des algorithmes classiques, tels que l'échantillonnage de Thompson, les algorithmes de limites supérieures de confiance (UCB et variantes), et les UCB bayésiennes ou de Kullback-Leibler. Notre algorithme offre de bonnes performances par rapport aux algorithmes de l'état de l'art (Exp4, CORRAL ou LearnExp), et apparaît comme une approche robuste pour sélectionner à la volée le meilleur algorithme pour tout problème MAB stochastique, étant plus réaliste aux paramètres radio du monde réel que toute approche basée sur le tuning.

L'apprentissage de la moyenne minimale/maximale parmi un ensemble fini de distributions est une sous-tâche fondamentale en planification, en recherche d'arbres de jeux et en apprentissage par renforcement. Nous formalisons cette tâche d'apprentissage comme le problème de tester séquentiellement comment la moyenne minimale parmi un ensemble fini de distributions se compare à un seuil donné. Nous développons des limites inférieures non asymptotiques raffinées, qui montrent que l'optimalité exige un comportement d'échantillonnage très différent pour un vrai minimum faible ou élevé. Nous montrons que l'échantillonnage de Thompson et la politique intuitive des limites inférieures de confiance ne règlent chacun qu'un seul de ces cas. Nous développons une nouvelle approche que nous appelons l'échantillonnage de Murphy. Bien qu'elle ne prenne en compte que les vrais minima faibles, nous prouvons qu'elle est optimale pour les deux possibilités. Nous concevons ensuite des inégalités de déviation auto-normalisées avancées, alimentant des règles d'arrêt plus agressives. Nous complétons nos garanties théoriques par des expériences montrant que le MS fonctionne le mieux en pratique.

Fournir les infrastructures de calcul nécessaires à la résolution des problèmescom-plexes de la société moderne constitue un défistratégique. Lesorganisations y répondent classiquement en mettant en place de largesinfrastructures de calcul parallèle et distribué. Les vendeurs de systèmes deCalcul Hautes Performances sont incités par la compétition à produire toujoursplus de puissance de calcul et de stockage, ce qui mène à des plateformes”Petascale“ spécifiques et sophistiquées, et bientôt à des machines”Exascale“. Ces systèmes sont gérés de manière centralisée à l’aide desolutions logicielles de gestion de jobs et de resources dédiées. Un problèmecrucial auquel répondent ces logiciels est le problème d’ordonnancement, pourlequel le gestionnaire de resources doit choisir quand, et sur quellesresources exécuter quelle tache calculatoire. Cette thèse fournit des solutionsà ce problème. Toutes les plateformes sont différentes. En effet, leurinfrastructure, le comportement de leurs utilisateurs et les objectifs del’organisation hôte varient. Nous soutenons donc que les politiquesd’ordonnancement doivent s’adapter au comportement des systèmes. Dans cemanuscrit, nous présentons plusieurs manières d’obtenir cette adaptativité. Atravers une approche expérimentale, nous étudions plusieurs compromis entre lacomplexité de l’approche, le gain potentiel, et les risques pris.

Un algorithme d'apprentissage par renforcement en ligne est dit "anytime" s'il n'a pas besoin de connaître à l'avance l'horizon T de l'expérience. Une technique bien connue pour obtenir un algorithme anytime à partir de n'importe quel algorithme non-anytime est le "Doubling Trick". Dans le contexte des bandits à bras multiples adversaires ou stochastiques, la performance d'un algorithme est mesurée par son regret, et nous étudions deux familles de séquences d'horizons croissants (géométrique et exponentielle) pour généraliser des résultats précédemment connus selon lesquels certaines astuces de doublement peuvent être utilisées pour conserver certaines limites de regret. Dans un cadre général, nous prouvons qu'une astuce de doublement géométrique peut être utilisée pour conserver les limites (minimax) dans $R_T = O(\sqrt{T})$ mais ne peut pas conserver les limites (dépendantes de la distribution) dans $R_T = O(\log T)$. Nous expliquons pourquoi les astuces de doublement exponentiel peuvent être meilleures, car elles conservent les bornes dans $R_T = O(\log T)$, et sont proches de la conservation des bornes dans $R_T = O(\sqrt{T})$.

Nous étudions une variante du problème du bandit multi-bras stochastique (MAB) dans lequel les récompenses sont corrompues. Dans ce cadre, motivé par la préservation de la vie privée dans les systèmes de recommandation en ligne, l'objectif est de maximiser la somme des récompenses (non observées), sur la base de l'observation de la transformation de ces récompenses par un processus de corruption stochastique dont les paramètres sont connus. Nous fournissons une limite inférieure sur le regret attendu de tout algorithme de bandit dans ce cadre corrompu. Nous concevons un algorithme fréquentiste, KLUCB-CF, et un algorithme bayésien, TS-CF, et donnons des limites supérieures à leur regret. Nous fournissons également les paramètres de corruption appropriés pour garantir un niveau souhaité de confidentialité locale et analysons l'impact de ces paramètres sur le regret. Enfin, nous présentons quelques résultats expérimentaux qui confirment notre analyse.

Les progrès récents des outils et des techniques de bandit pour l'apprentissage séquentiel permettent régulièrement de nouvelles applications et promettent la résolution d'une série de problèmes connexes difficiles. Nous étudions le problème de la recherche dans un arbre de jeu, où le but est d'identifier rapidement le coup optimal dans un arbre de jeu donné en échantillonnant séquentiellement ses gains stochastiques. Nous développons de nouveaux algorithmes pour des arbres de profondeur arbitraire, qui fonctionnent en résumant tous les niveaux plus profonds de l'arbre en intervalles de confiance à la profondeur un, et en appliquant une procédure d'identification du meilleur bras à la racine. Nous prouvons de nouvelles garanties de complexité d'échantillon avec une dépendance raffinée sur l'instance du problème. Nous montrons expérimentalement que nos algorithmes sont plus performants que les algorithmes existants basés sur l'élimination et qu'ils égalent les méthodes spéciales précédentes pour les arbres de profondeur deux.

Cet article traite des politiques d'indexation visant à minimiser le regret (fréquentiste) dans un modèle stochastique de bandit à bras multiples, inspiré par une vision bayésienne du problème. Notre principale contribution est de prouver que l'algorithme Bayes-UCB, qui repose sur les quantiles des distributions postérieures, est asymptotiquement optimal lorsque les distributions de récompense appartiennent à une famille exponentielle unidimensionnelle, pour une grande classe de distributions antérieures. Nous montrons également que la littérature bayésienne donne un nouvel aperçu du type de taux d'exploration qui pourrait être utilisé dans les algorithmes fréquentistes de type UCB. En effet, les approximations de la solution optimale bayésienne ou des indices de Gittins à horizon fini fournissent une justification pour les algorithmes kl-UCB+ et kl-UCB-H+, dont l'optimalité asymptotique est également établie.

Cet article présente un nouvel algorithme spectral avec regroupement additif conçu pour identifier les communautés qui se chevauchent dans les réseaux. L'algorithme est basé sur les propriétés géométriques du spectre de la matrice d'adjacence attendue dans un modèle de graphe aléatoire que nous appelons modèle de bloc stochastique avec chevauchement (SBMO). Il est prouvé qu'une version adaptative de l'algorithme, qui ne nécessite pas la connaissance du nombre de communautés cachées, est cohérente sous le SBMO lorsque les degrés du graphe sont (légèrement plus que) logarithmiques. On montre que l'algorithme fonctionne bien sur des données simulées et sur des graphes du monde réel avec des communautés connues qui se chevauchent.

Au cours des dernières années, le modèle de bandit à bras multiples est devenu de plus en plus populaire dans la communauté de l'apprentissage automatique, en partie en raison d'applications telles que l'optimisation du contenu en ligne. Cet article passe en revue deux tâches d'apprentissage séquentiel différentes qui ont été considérées dans la littérature sur le bandit. Elles peuvent être formulées comme l'apprentissage (séquentiel) de la distribution ayant la moyenne la plus élevée parmi un ensemble de distributions, avec certaines contraintes sur le processus d'apprentissage. Pour les deux (minimisation du regret et identification du meilleur bras), nous présentons des algorithmes récents, asymptotiquement optimaux. Nous comparons les comportements de la règle d'échantillonnage de chaque algorithme ainsi que les termes de complexité associés à chaque problème.

Cet article présente un nouvel algorithme spectral avec regroupement additif conçu pour identifier les communautés qui se chevauchent dans les réseaux. L'algorithme est basé sur les propriétés géométriques du spectre de la matrice d'adjacence attendue dans un modèle de graphe aléatoire que nous appelons modèle de bloc stochastique avec chevauchement (SBMO). Il est prouvé qu'une version adaptative de l'algorithme, qui ne nécessite pas la connaissance du nombre de communautés cachées, est cohérente sous le SBMO lorsque les degrés du graphe sont (légèrement plus que) logarithmiques. On montre que l'algorithme fonctionne bien sur des données simulées et sur des graphes du monde réel avec des communautés connues qui se chevauchent.

Le modèle de bandit stochastique à plusieurs bras est une abstraction simple qui s'est avérée utile dans de nombreux contextes différents en statistique et en apprentissage automatique. Alors que la limite réalisable en termes de minimisation du regret est maintenant bien connue, notre objectif est de contribuer à une meilleure compréhension de la performance en termes d'identification des m meilleurs bras. Nous introduisons des notions génériques de complexité pour les deux cadres dominants considérés dans la littérature : les cadres à budget fixe et à confiance fixe. Dans le cadre de la confiance fixe, nous fournissons la première limite inférieure connue de la complexité en fonction de la distribution qui implique des quantités théoriques de l'information et qui tient lorsque m est supérieur à 1 sous des hypothèses générales. Dans le cas spécifique de deux bandits armés, nous dérivons des limites inférieures raffinées à la fois dans le cadre de la confiance fixe et du budget fixe, ainsi que des algorithmes de correspondance pour les modèles de bandits gaussiens et de Bernoulli. Ces résultats montrent en particulier que la complexité du cadre à budget fixe peut être plus petite que la complexité du cadre à confiance fixe, ce qui contredit le comportement familier observé lors du test d'alternatives entièrement spécifiées. En outre, nous fournissons également des règles d'arrêt séquentielles améliorées qui ont des probabilités d'erreur garanties et des temps d'exécution moyens plus courts. Les preuves reposent sur deux résultats techniques qui présentent un intérêt indépendant : un lemme de déviation pour les sommes auto-normalisées (Lemma 19) et une nouvelle inégalité de changement de mesure pour les modèles de bandits (Lemma 1).

Nous étudions un problème original d'exploration pure dans un modèle de bandit stratégique motivé par la recherche d'arbres de Monte Carlo. Il consiste à identifier la meilleure action dans un jeu, lorsque le joueur peut échantillonner les résultats aléatoires de paires d'actions choisies séquentiellement. Nous proposons deux stratégies pour le cadre de confiance fixe : Maximin-LUCB, basée sur des limites de confiance inférieure et supérieure, et Maximin-Racing, qui fonctionne en éliminant successivement les actions sous-optimales. Nous discutons de la complexité d'échantillonnage des deux méthodes et comparons leurs performances de manière empirique. Nous esquissons une analyse des bornes inférieures, et des connexions possibles à un algorithme optimal.

Nous étudions le problème de la minimisation du regret dans des problèmes de bandit à deux bras avec des récompenses gaussiennes. Notre objectif est d'utiliser ce cadre simple pour illustrer que les stratégies basées sur une phase d'exploration (jusqu'à un temps d'arrêt) suivie d'une exploitation sont nécessairement sous-optimales. Les résultats sont valables que l'on connaisse ou non la différence de moyenne entre les deux bras. Outre le message principal, nous raffinons également les inégalités de déviation existantes, ce qui nous permet de concevoir des stratégies entièrement séquentielles avec des garanties de regret en temps fini qui sont (a) asymptotiquement optimales à mesure que l'horizon croît et (b) optimales par ordre dans le sens minimax. En outre, nous fournissons des preuves empiriques que la théorie est également valable en pratique et nous discutons des extensions au cas non gaussien et à celui des armes multiples.

Nous donnons une caractérisation complète de la complexité de l'identification du meilleur bras dans les problèmes de bandits à un paramètre. Nous prouvons une nouvelle limite inférieure serrée sur la complexité de l'échantillon. Nous proposons la stratégie `Track-and-Stop', dont nous prouvons qu'elle est asymptotiquement optimale. Elle consiste en une nouvelle règle d'échantillonnage (qui suit les proportions optimales de tirages de bras mises en évidence par la borne inférieure) et en une règle d'arrêt nommée d'après Chernoff, pour laquelle nous donnons une nouvelle analyse.

Le test A/B consiste à déterminer la meilleure option parmi deux alternatives dont les résultats sont aléatoires. Nous fournissons des limites inférieures dépendantes de la distribution pour la performance du test A/B qui améliorent les résultats actuellement disponibles à la fois dans le cadre de la confiance fixe (ou delta-PAC) et du budget fixe. Lorsque la distribution des résultats est gaussienne, nous prouvons que la complexité des paramètres de confiance fixe et de budget fixe est équivalente, et que l'échantillonnage uniforme des deux alternatives est optimal uniquement dans le cas de variances égales. Dans le cas de variance commune, nous fournissons également une règle d'arrêt qui se termine plus rapidement que les algorithmes de confiance fixe existants. Dans le cas des distributions de Bernoulli, nous montrons que la complexité de l'établissement du budget fixe est plus petite que celle de l'établissement de la confiance fixe et que l'échantillonnage uniforme des deux alternatives - bien que non optimal - est conseillé en pratique lorsqu'il est combiné avec un critère d'arrêt approprié.

Dans cette thèse, nous étudions des stratégies d'allocation séquentielle de ressources, sous le modèle dit du bandit multi-bras stochastique. Dans ce modèle, lorsqu'un agent tire un bras, il reçoit comme récompense une réalisation issue d'une distribution de probabilité associée à ce bras. Dans ce document, nous considérons deux problèmes de bandit différents. Dans l'objectif de maximisation de la récompense, l'agent vise à maximiser la somme des récompenses obtenues lors de son interaction avec le bandit, tandis que dans l'objectif d'identification du meilleur bras, son but est de trouver l'ensemble des m meilleurs bras (i.e. les bras avec la récompense moyenne la plus élevée), sans subir de perte lors du tirage de "mauvais" bras. Pour ces deux objectifs, nous proposons des stratégies, également appelées algorithmes de bandit, qui sont optimales (ou proches de l'optimal), dans un sens précisé ci-dessous. Maximiser la somme des récompenses est équivalent à minimiser une quantité appelée regret. Grâce à une borne inférieure asymptotique sur le regret de tout algorithme uniformément efficace donnée par Lai et Robbins, on peut définir les algorithmes asymptotiquement optimaux comme des algorithmes dont le regret atteint cette borne inférieure. Dans cette thèse, nous proposons, pour deux algorithmes bayésiens, Bayes-UCB et Thompson Sampling, une analyse en temps fini, c'est-à-dire une borne supérieure non-asymptotique sur leur regret, dans le cas particulier de bandits à récompenses binaires. Cette borne supérieure permet d'établir l'optimalité asymptotique des deux algorithmes. Dans le cadre de l'identification des meilleures armes, un objectif possible est de déterminer le nombre d'échantillons d'armes nécessaires pour identifier, avec une forte probabilité, l'ensemble des m meilleures armes. Nous définissons une notion de complexité pour l'identification du meilleur bras dans deux contextes différents considérés dans la littérature : le contexte à budget fixe et le contexte à confiance fixe. Nous fournissons de nouvelles bornes inférieures sur ces termes de complexité et nous analysons de nouveaux algorithmes, dont certains atteignent la borne inférieure dans des cas particuliers de modèles de bandits à deux bras et sont donc optimaux. Dans cette thèse, nous étudions des stratégies d'allocation séquentielle de ressources.

Dans cette thèse, nous étudions des stratégies d’allocation séquentielle de ressources. Le modèle statistique adopté dans ce cadre est celui du bandit stochastique à plusieurs bras. Dans ce modèle, lorsqu’un agent tire un bras du bandit, il reçoit pour récompense une réalisation d’une distribution de probabilité associée au bras. Nous nous intéressons à deux problèmes de bandit différents : la maximisation de la somme des récompenses et l’identification des meilleurs bras (où l’agent cherche à identifier le ou les bras conduisant à la meilleure récompense moyenne, sans subir de perte lorsqu’il tire un «mauvais» bras). Nous nous attachons à proposer pour ces deux objectifs des stratégies de tirage des bras, aussi appelées algorithmes de bandit, que l’on peut qualifier d’optimales. La maximisation des récompenses est équivalente à la minimisation d’une quantité appelée regret. Grâce à une borne inférieure asymptotique sur le regret d’une stratégie uniformément efficace établie par Lai et Robbins, on peut définir la notion d’algorithme asymptotiquement optimal comme un algorithme dont le regret atteint cette borne inférieure. Dans cette thèse, nous proposons pour deux algorithmes d’inspiration bayésienne, Bayes-UCB et Thompson Sampling, une analyse à temps fini dans le cadre des modèles de bandit à récompenses binaires, c’est-à-dire une majoration non asymptotique de leur regret. Cette majoration permetd’établir l’optimalité asymptotique des deux algorithmes. Dans le cadre de l’identification des meilleurs bras, on peut chercher à déterminer le nombre total d’échantillons des bras nécessaires pour identifier, avec forte probabilité, le ou les meilleurs bras, sans la contrainte de maximiser la somme des observations. Nous définissons deux termes de complexité pour l’identification des meilleurs bras dans deux cadres considérés dans la littérature, qui correspondent à un budget fixé ou à un niveau de confiance fixé. Nous proposons de nouvelles bornes inférieures sur ces complexités, et nous analysons de nouveaux algorithmes, dont certains atteignent les bornes inférieures dans des cas particuliers de modèles de bandit à deux bras, et peuvent donc être qualifiés d’optimaux.

Nous considérons le problème de l'exploration efficace des bras d'un bandit stochastique pour identifier le meilleur sous-ensemble d'une taille spécifiée. Sous les formulations PAC et à budget fixe, nous dérivons des bornes améliorées en utilisant des intervalles de confiance basés sur la divergence KL. Alors que l'application d'une idée similaire dans le cadre du regret a donné des limites en termes de divergence KL entre les bras, nos limites dans le cadre de l'exploration pure impliquent l'"information de Chernoff" entre les bras. En plus d'introduire cette nouvelle quantité dans la littérature sur les bandits, nous contribuons à une comparaison entre les stratégies basées sur l'échantillonnage uniforme et adaptatif pour les problèmes d'exploration pure, trouvant des preuves en faveur de la seconde.

.

L'échantillonnage de Thompson a été démontré dans de nombreux modèles de bandits complexes, cependant les garanties théoriques disponibles pour le bandit multi-armé paramétrique sont encore limitées au cas de Bernoulli. Ici, nous les étendons en prouvant l'optimalité asymptotique de l'algorithme en utilisant la priorisation de Jeffreys pour les bandits à famille exponentielle unidimensionnelle. Notre preuve s'appuie sur des travaux antérieurs, mais fait également un usage intensif des formes fermées de la divergence de Kullback-Leibler et de l'information de Fisher (par le biais de la priorité de Jeffreys) disponibles dans une famille exponentielle. Cela nous permet de donner une inégalité de concentration exponentielle en temps fini pour les distributions postérieures sur les familles exponentielles qui peut être intéressante en soi. De plus, notre analyse couvre certaines distributions pour lesquelles aucun algorithme optimiste n'a encore été proposé, notamment les familles exponentielles à queue lourde.

.

L'échantillonnage de Thompson a été démontré dans de nombreux modèles de bandits complexes, cependant les garanties théoriques disponibles pour le bandit paramétrique à bras multiples sont encore limitées au cas de Bernoulli. Nous les étendons ici en prouvant l'optimalité asymptotique de l'algorithme en utilisant la priorité de Jeffreys pour les bandits de la famille exponentielle à une dimension. Notre preuve s'appuie sur des travaux antérieurs, mais fait également un usage intensif des formes fermées pour la divergence de Kullback-Leibler et l'information de Fisher (et donc la priorité de Jeffreys) disponibles dans une famille exponentielle. Cela nous permet de donner une inégalité de concentration exponentielle en temps fini pour les distributions postérieures sur les familles exponentielles qui peut être intéressante en soi. De plus, notre analyse couvre certaines distributions pour lesquelles aucun algorithme optimiste n'a encore été proposé, notamment les familles exponentielles à queue lourde.