Sequential Learning in a strategical environment
Apprentissage séquentiel dans un environnement stratégique
Résumé
In sequential learning (or repeated games), data is acquired and treated on the fly and an algorithm (or strategy) learns to behave as well as if it got in hindsight the state of nature, e.g., distributions of rewards. In many real life scenarios, learning agents are not alone and interact, or interfere, with many others. As a consequence, their decisions have an impact on the other and, by extension, on the generating process of rewards. We aim at studying how sequential learning algorithms behave in strategic environments, when facing and interfering with each others. This thesis thus considers different problems, where some interactions between learning agents arise and provides computationally efficient algorithms with good performance (small regret) guarantees.When agents are cooperative, the difficulty of the problem comes from its decentralized aspect, as the different agents take decisions solely based on their observations. In this case, we propose algorithms that not only coordinate the agents to avoid negative interference with each other, but also leverage the interferences to transfer information between the agents, thus reaching performances similar to centralized algorithms. With competing agents, we propose algorithms with both satisfying performance and strategic (e.g., epsilon-Nash equilibria) guarantees.This thesis mainly focuses on the problem of multiplayer bandits, which combines different interactions between learning agents in a formalized online learning framework. Both for the cooperative and competing case, algorithms with performances comparable to the centralized case are proposed.Other sequential learning instances are also considered in this thesis. We also propose a strategy reaching centralized performances for decentralized queuing systems. For online auctions, we suggest to balance short and long term rewards with a utility/privacy trade-off. It is formalized as an optimization problem, that is equivalent to Sinkhorn divergence and benefits from the recent advances on Optimal Transport. We also study social learning with reviews, when the quality of the product varies over time.
En apprentissage séquentiel (ou jeux répétés), les données sont acquises et traitées à la volée et un algorithme (ou stratégie) apprend à se comporter aussi bien que s'il avait pu observer l'état de nature, par exemple les distributions des gains. Dans de nombreuses situations réelles, de tels agents intelligents ne sont pas seuls et interagissent ou interfèrent avec d'autres. Ainsi, leurs décisions ont un impact direct sur les autres agents et indirectement sur leurs propres gains à venir. Nous étudions de quelle manière les algorithmes d'apprentissage séquentiel peuvent se comporter dans des environnements stratégiques quand ils sont confrontés à d'autres agents. Cette thèse considère différents problèmes où certaines interactions entre des agents intelligents apparaissent, pour lesquels nous proposes des algorithmes efficaces en termes de calcul avec de bonnes garanties de performance (faible regret).Lorsque les agents sont coopératifs, la difficulté du problème vient de son aspect décentralisé, étant donné que les agents prennent leurs décisions en se basant seulement sur leurs propres observations. Dans ce cas, les algorithmes proposés non seulement coordonnent les agents afin d'éviter des interférences entre eux, mais ils utilisent également ces interférences pour transférer de l'information entre les agents. Cela permet d'obtenir des performances comparables aux meilleurs algorithmes centralisés. Avec des agents en concurrence, nous proposons des algorithmes avec des garanties satisfaisantes, à la fois en terme de performance et de stratégie (epsilon-équilibre de Nash par exemple).Cette thèse s'intéresse principalement au problème de bandits à plusieurs joueurs, combinant différentes interactions entre agents intelligents dans le cadre de l'apprentissage séquentiel. Des algorithmes comparables au cas centralisés sont proposés, lorsque les agents sont coopératifs, mais aussi lorsqu'ils sont compétitifs.D'autres exemples d'apprentissage séquentiel sont considérés dans cette thèse. Une stratégie comparable au cas centralisé est également proposé pour les systèmes de file d'attente. Pour les enchères en ligne, nous proposons de balancer les gains court et long terme à travers un dilemne utilité/confidentialité. Ce dilemne est formalisé par un problème d'optimisation, equivalent à la minimisation de la divergence Sinkhorn et qui bénéficie des récents progrès en transport optimal.Nous étudions aussi l'apprentissage social avec revues, lorsque la qualité du produit est variable dans le temps.
Origine : Version validée par le jury (STAR)