Sequential Learning in a strategical environment

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.