Soutenance mémoire
Les travaux présentés dans ce manuscrit concerne la théorie des jeux et l’apprentissage automatique dans un contexte de télécommunications. Dans cette thèse, nous étudions les enjeux de la coopération d’agents apprenants (notamment des politiques d’apprentissage par renforcement) au sein de situations appelées dilemmes sociaux. Nous chercherons à appliquer ce type de modèle et d’agents intelligents dans un contexte de collaborations entre opérateurs de télécommunications.
Les enjeux de l’intelligence artificielle coopérative
Dans l’industrie ou dans notre quotidien, l’implémentation et le déploiement d’agents intelligents sont de plus en plus présents. Dès lors que ces agents sont indépendants et a priori intéressés uniquement par leurs intérêts personnels, il peut survenir des situations où l’intérêt collectif peut être plus profitable. Dans la suite, nous proposons quelques exemples pour illustrer les enjeux de la coopération entre agents artificiels.
• Internet des objets
L’explosion de l’utilisation d’objets connectés indépendants peut naturellement impliquer des situations de coopération. On peut en particulier envisager que des appareils puissent coopérer pour s’échanger des données de capteurs sans fil [YKAD12] ou collaborer pour mieux effectuer une tâche. Ceci peut être réalisé notamment grâce à un partage d’informations, comme cela a été proposé avec des appareils du domaine de la santé [RPP11]. Enfin, on peut imaginer les situations où les objets connectés ont à leur disposition de l’énergie pour leur batterie ou de la connectivité à partager, et qu’ils doivent coopérer pour ne pas aboutir à des situations non optimales [BEBS+19].
• Véhicules autonomes
Dans le cadre des véhicules autonomes qui se développent sur les routes [HCS+16], dans les entrepôts [WDM08] ou bien dans les airs [WYZL20], il devient nécessaire de s’intéresser aux enjeux des comportements ego-centrés. En effet, parfois, des conflits dûs à des choix égoïstes sans vision collective peuvent s’avérer contre-productifs voire très pénalisants, comme des collisions ou des impasses.
• Apprentissage fédéré
L’apprentissage fédéré (federated learning) consiste à entraîner des modèles de Machine Learning (ML) de manière décentralisée sur des machines différentes [SS15, MMR+17]. L’objectif des machines est d’entraîner localement ces modèles sur des données locales (souvent privées, ce qui fait l’intérêt du federated learning) puis de partager les mises à jour de modèle aux partenaires. Les agents décentralisés peuvent être considérés comme indépendants. Dans ce cas, ils peuvent faire preuve d’égoïsme comme par exemple, continuer de recevoir les mises à jour des paramètres des modèles sans consommer personnellement de l’énergie pour l’entraînement local, ou bien volontairement de ne pas partager les mises à jour issues d’entraînement sur des données précieuses. Dans ce contexte, il est alors intéressant d’introduire des mécanismes pour inciter la coopération et se prémunir des agents égoïstes [KXN+19, ZLQ+20].
• Partage et gestion des ressources
La rareté des ressources naturelles et les besoins croissants en énergie doivent faire prendre conscience qu’il serait idéal que des agents intelligents coopérent ensemble pour mieux gérer collectivement les ressources. Ils peuvent alors apprendre à exploiter de manière collective et altruiste les ressources naturelles [OGW+94, PLZ+17] ou bien homogénéiser leurs ressources de manière optimale afin d’éviter le gaspillage ou les sur-coûts de stockage [SF89, LH19].
L’intérêt de la collaboration dans l’univers des Télécom
Le trafic des données mobiles est en constante augmentation. Ceci est dû en particulier à l’explosion des usages d’internet, comme la vidéo en streaming, en 4K ou bien la multiplication des objets connectés et le développement de nouvelles technologies comme les véhicules autonomes ou la télémedecine. Par conséquent, la gestion de ce trafic devient un enjeu fondamental pour les prochaines générations de téléphonie mobile (telles que la 5G). Pour adresser cette augmentation de demande, il est nécessaire de déployer de nouvelles infrastructures. Cependant dans un soucis environnemental et financier, il pourrait être intéressant de considérer des approches consistant à mutualiser certaines infrastructures entre opérateurs de télécommunications par le biais de transactions de ressources radio.
Le partage de ressources peut être envisagé dans deux principaux cas de figure. Dans un premier temps, ces échanges peuvent contribuer à augmenter les capacités de réseau (amélioration de la qualité de service par l’augmentation du débit). Cette situation illustrée par la Figure 4a implique des clients que l’on suppose en bordure de réseau de leur antenne de rattachement. Ils pourraient être idéalement pris en charge par l’antenne d’un opérateur concurrent plus proche afin d’offrir une meilleure connectivité. Si le service est rendu de manière réciproque, alors la coopération entre opérateurs aura été gagnante pour les deux acteurs. Le deuxième cas de figure concerne l’augmentation de couverture réseau . L’idée est ici d’adresser les zones à faible couverture voire les zones sans couverture (zones blanches). Un opérateur rendrait alors service à un autre en lui allouant de la ressource dans une cellule où il en manquerait.
Jeux non-coopératifs et dilemmes sociaux
La théorie des jeux est un domaine à l’intersection des mathématiques, de l’économie et de l’intelligence artificielle. Elle est souvent désignée comme la science de la décision, elle a pour objectif d’étudier les situations impliquant des choix de plusieurs acteurs rationnels. Les situations étudiées dans cette thèse sont celles de la catégorie des jeux non-coopératifs, i.e. où les acteurs agissent dans leur seul intérêt personnel et de manière indépendante.
La théorie des jeux est une branche scientifique relativement récente dont les fondations ne remontent qu’au siècle dernier. Pourtant, ses concepts nous touchent quotidiennement. Avant d’aborder des concepts de manière plus formelle dans les prochaines sections, nous présentons dans cette introduction quelques aspects historiques et proposons d’illustrer ce domaine à travers quelques exemples simples du quotidien.
De l’économie aux mathématiques
Les tous premiers concepts de la théorie des jeux tirent leurs origines au lendemain de la seconde guerre mondiale. Le mathématicien John von Neumann et l’économiste Oskar Morgenstern partagent alors la volonté de refonder l’économie sur des bases mathématiques. Ils proposent alors dans l’ouvrage fondateur Theory of Games and Economic Behavior [MVN53], une formalisation mathématique pour modéliser les comportements stratégiques d’acteurs économiques. Depuis ces fondations, de nombreux scientifiques ont contribué aux concepts liés à la théorie des jeux et pas moins de onze économistes se sont vus décerner depuis 1944, le prix Nobel d’économie pour leurs recherches sur la théorie des jeux. On peut citer John Forbes Nash, connu notamment pour la formalisation des équilibres du même nom [Nas51], et Roger Myerson pour ses contributions sur la théorie des mécanismes d’incitation [Mye79].
L’économie est donc la discipline reine où l’on retrouve par essence les concepts de la théorie des jeux. Le gain que les acteurs ou les agents rationnels cherchent à maximiser est naturellement l’argent. Par exemple, le commerçant cherche à vendre ses articles le plus cher possible tandis que le client souhaite l’inverse. La présence de concurrents et le principe de l’offre et la demande permettent alors de régir les prix de manière rationnelle [Cou38].
Des applications omniprésentes
Bien que la théorie des jeux soit originellement dédiée à l’économie, on peut l’appliquer dans de nombreux autres domaines. Pour commencer, on retrouve ces concepts bien entendu dans les jeux au sens plus commun, telles que les échecs, le poker, le morpion ou tout autre jeu de plateau. Chaque joueur souhaite maximiser un gain représentant le but recherché. Par exemple, un gain positif en cas de victoire, négatif pour une défaite et éventuellement nul en cas d’égalité.
Certains jeux sont dits compétitifs et à somme nulle. Les joueurs agissent alors de manière antagoniste avec intérêts personnels et la somme des gains des joueurs à l’issue du jeu est nulle : ce que l’un gagne, l’autre le perd ; il y a un gagnant et un perdant, éventuellement une égalité (gains nuls). D’autres jeux peuvent être à somme non-nulle ce qui peut prêter à des stratégies gagnant-gagnant. Enfin certains jeux de plateau sont dits collaboratifs auquel cas les joueurs partagent le même gain qu’ils cherchent à maximiser collectivement. Dans le jeu du morpion , deux joueurs s’affrontent, en choisissant des stratégies (placer une croix ou un cercle) et obtiennent à l’issue du jeu, un gain selon les objectifs visés (par exemple, +10 en cas de victoire , −10 en cas de défaite). Il s’agit donc d’un jeu à somme nulle. Cette catégorie de jeu peut être résolue en suivant notamment le principe du minimax [Fan53] : on déroule des simulations de jeu et on choisit à chaque tour les stratégies qui minimisent les pertes en supposant que l’adversaire cherche lui, à les maximiser pour son propre adversaire.
Dans le monde du sport, on peut imaginer également de nombreuses problématiques liées à la théorie des jeux. Hormis les aspects directement liés à la pratique (par exemple de quel côté plonger pour le gardien de but lors d’un penalty), on peut penser aux choix stratégiques tels que la simulation d’une faute ou la tentation du dopage. Ces deux derniers cas s’apparentent d’ailleurs à la catégorie des dilemmes sociaux. En effet, il peut être risqué d’être seul à jouer honnêtement (risque de carton rouge à la place ou à cause d’un joueur qui simule ou un déclassement dans le cas du dopage car entourés de sportifs meilleurs). Il est aussi tentant d’être malhonnête (obtention d’un penalty ou gain de performance grâce au dopage). Cela peut facilement conduire à un comportement collectif malhonnête, qui est évidement regrettable (beauté du jeu, risques pour la santé, etc).
|
Table des matières
Introduction
Contexte et motivations de la thèse
L’intelligence artificielle coopérative
L’intérêt de la collaboration dans l’univers des Télécom
Contributions
Contributions algorithmiques
Contributions logicielles
Publications et brevets
Organisation du manuscrit
I Des dilemmes sociaux à l’apprentissage multi-agents
1 Jeux non-coopératifs et dilemmes sociaux
1.1 Introduction
1.1.1 De l’économie aux mathématiques
1.1.2 Des applications omniprésentes
1.1.3 Notions abordées dans ce chapitre
1.2 Notions générales de la théorie des jeux
1.2.1 Définition d’un jeu sous forme normale
1.2.2 Stratégies dominantes et dominées
1.2.3 Equilibre de Nash
1.2.4 Extension mixte d’un jeu sous forme normale
1.2.5 Optimum de Pareto
1.2.6 Jeux à information incomplète
1.2.7 Jeux répétés
1.3 Les dilemmes sociaux
1.3.1 Définition de base
1.3.2 Les trois catégories de dilemme social
1.3.3 Dilemme du prisonnier itéré
1.3.4 Dilemme du prisonnier continu
1.3.5 Le dilemme du prisonnier à N joueurs
1.4 Stratégies gagnantes pour le dilemme du prisonnier itéré
1.4.1 Les « bonnes » stratégies
1.4.2 Exemples de stratégies
1.4.3 Simulations de tournois
1.4.4 Tit-for-Tat continu
1.5 Synthèse
2 Apprentissage par renforcement et dilemmes sociaux complexes
2.1 Le Machine Learning : une brève topologie
2.1.1 Les catégories d’apprentissage
2.1.2 Les réseaux de neurones
2.2 Apprentissage par renforcement
2.2.1 Processus de décision markovien
2.2.2 Principe général et dilemme « exploitation/exploration »
2.2.3 Catégories d’algorithmes
2.2.4 Des méthodes tabulaires au Deep Reinforcement Learning (DRL)
2.2.5 Bandits manchots : du Reinforcement Learning (RL) sans observation
2.2.6 Apprentissage par Renforcement Multi-Agents (MARL)
2.3 Dilemmes sociaux séquentiels
2.3.1 Exemples de jeux
2.3.2 Dilemme social séquentiel
2.3.3 Approches proposées pour jouer dans les Sequential Social Dilemma (SSD)
2.4 Conclusion et perspectives
II Vers l’apprentissage de la coopération
3 Apprentissage de stratégies dans un dilemme du prisonnier itéré simple
3.1 Introduction
3.2 Aspects méthodologiques
3.2.1 Tournoi de dilemme du prisonnier itéré à deux joueurs
3.2.2 Métriques sociales
3.3 Apprentissage par renforcement et dilemmes du prisonnier itérés
3.3.1 Modèle
3.3.2 Scénarios étudiés
3.3.3 Étude de l’algorithme Q-learning
3.3.4 Impact des valeurs des gains (S, P, R, T) sur la coopération
3.4 Propositions d’une stratégie de Tit-for-Tat continu à deux joueurs
3.4.1 Contexte
3.4.2 Proposition d’un Tit-for-Tat (TFT) continu
3.4.3 Bilan
3.4.4 Simulations empiriques
3.4.5 Évaluation des paramètres
3.4.6 Quelques aspects théoriques
3.5 Conclusions et perspectives
4 Proposition d’un dilemme du prisonnier à N joueurs continu et non-réciproque
4.1 Introduction et motivations
4.1.1 Les coopérations réciproques non systématiques
4.1.2 Un Tit-for-Tat classique inadapté
4.2 Formalisme du dilemme du prisonnier basé sur des graphes
4.2.1 Comparaison des modèles et algorithmes existant
4.2.2 Dilemme du prisonnier à N joueurs
4.2.3 Dilemme du prisonnier multi-joueurs basé sur des graphes
4.2.4 Exemples de Graph-based Iterated Prisoner’s Dilemma (GIPD)
4.3 Une extension de la politique de Tit-for-Tat classique
4.3.1 Rappels sur le Tit-for-Tat et notions de réseaux de flots
4.3.2 Principe et architecture de notre extension (GTFT)
4.4 Méthode comparative des algorithmes de Tit-for-Tat
4.4.1 Métriques utilisées
4.4.2 Agents étudiés et leurs caractéristiques
4.4.3 Tournois de simulation
4.5 Résultats et discussion
4.5.1 Impact du choix d’algorithme pour le traitement de graphe
4.5.2 Impact du choix de la fonction de Tit-for-Tat
4.5.3 Synthèse des observations
4.6 Limitations
4.6.1 Observation partielle
4.6.2 Ambiguïté du choix commun du cycle
4.7 Conclusion et perspectives
Conclusion
