L’apprentissage par renforcement appliqué au routage

L’apprentissage par renforcement appliqué au routage

 Introduction

Les problèmes des réseaux informatiques sont complexes, que ce soit le routage, la classifica‐ tion du trafic ou la prédiction de pannes. L’apprentissage automatique peut permettre de résoudre ces problèmes. L’apprentissage automatique est composé de plusieurs catégories. Les trois caté‐ gories principales sont l’apprentissage supervisé, non supervisé et par renforcement. Dans le cas de l’apprentissage supervisé, l’objectif est de créer un modèle à partir de données labellisées. L’ap‐ prentissage supervisé peut être utilisé pour effectuer de la classification de trafic [Pac+19]. Dans le cas de l’apprentissage non supervisé, l’objectif est de créer un modèle à partir de données non labellisées. Il peut être utilisé par exemple pour la détection d’anomalies [Fal+19]. Contrairement aux deux autres approches, le modèle est créé par essais et erreurs (try and error) pour l’apprentis‐ sage par renforcement. Il ne nécessite donc pas de jeu de données initial d’entraînement, ce qui est un atout. Les problèmes de routage peuvent être résolus grâce à l’apprentissage par renforcement comme nous allons le voir par la suite. Nous allons commencer par présenter plus en détail l’appren‐ tissage par renforcement (Section 4.2). Nous verrons ensuite des travaux utilisant l’apprentissage par renforcement pour résoudre des problèmes des réseaux informatiques. Enfin, nous termine‐ rons par Q‐routing [BL94], un algorithme de routage inspiré de l’algorithme d’apprentissage par renforcement Q‐learning [WD92] (Section 4.4).

Apprentissage par renforcement

Nous allons commencer par définir un peu plus en détails l’apprentissage par renforcement. L’apprentissage par renforcement est le troisième paradigme d’apprentissage automatique. Contrai‐ rement à l’apprentissage supervisé et non supervisé, il ne nécessite pas nécessairement de jeu de données initial. L’apprentissage s’effectue à partir de ses expériences (try‐and‐error). 53 L’apprentissage par renforcement appliqué au routage Agent Environnement action At récompense Rt état St Rt+1 St+1 FIG. 4.1 : Interaction entre l’agent et l’environnement dans un processus de décision Markovien, extrait de [SB18]. L’apprentissage par renforcement définit quatre notions fondamentales : l’agent, l’environne‐ ment, l’action et la récompense. Les interactions entre ces quatre notions sont illustrées par la Figure 4.1 qui résume le cadre d’un processus de décision Markovien (MDP). De manière pédago‐ gique, nous allons utiliser une analogie d’un joueur dans une salle remplie de machines à sous [SB18]. Ce problème est aussi connu sous le nom de bandit manchot. Le joueur est notre agent. La salle remplie de machines à sous est notre environnement. Les machines à sous composent l’ensemble des états de l’environnement. Une action consiste à jouer sur une des machines à sous. La récom‐ pense est le gain obtenu. Chaque machine a une espérance de gain qui lui est propre. L’objectif dans ce cas consiste à maximiser les gains cumulés soit à long terme, soit sur une période (en nombre d’essais). L’apprentissage par renforcement définit quatre notions supplémentaires : la fonction de va‐ leur, la stratégie, le signal de récompense et le modèle. Nous reprenons notre analogie précédente. Comme l’espérance de chaque machine n’est pas connue, elle peut être au mieux estimée. La fonc‐ tion de valeur est le nom de la fonction associant une machine à sous et l’estimation de son espé‐ rance. Le processus de choix de la machine à sous compose la stratégie de l’agent. Par exemple, la stratégie gloutonne (greedy) consisterait à toujours choisir la machine à sous dont l’espérance esti‐ mée est la plus élevée. Le signal de récompense est l’objectif de gain à réaliser. Le modèle permet d’effectuer des prédictions sur le comportement de l’environnement, notamment ses réactions par rapport à une action et l’état suivant. Certains algorithmes comme Q‐learning ne nécessitent pas de modèle de l’environnement. Dans une stratégie, il y a deux phases possibles : la phase d’exploration et la phase d’exploita‐ tion. Ces deux phases ont une finalité différente. La phase d’exploration sert à améliorer l’estimation des récompenses des différentes actions. L’objectif de la phase d’exploitation est uniquement d’at‐ teindre l’objectif. Nous reprenons notre exemple de bandit manchot. Durant la phase d’exploration, le joueur va essayer une ou plusieurs machines à sous afin d’améliorer l’estimation de l’espérance des gains de celles‐ci. Durant la phase d’exploitation, le joueur va utiliser la machine à sous permet‐ tant de maximiser les gains. Le passage d’une phase à l’autre est dépendant de la stratégie. Une stratégie gloutonne n’est composée que d’une phase d’exploitation. 

Quelques exemples d’algorithmes d’apprentissage par renforcement

Nous allons nous intéresser à quelques algorithmes d’apprentissage par renforcement dont Q‐ learning et ses dérivés. La modélisation d’un réseau informatique est très compliqué, nous avons choisi Q‐learning car il ne nécessite pas de modèle, ni de jeu de données initial. La Figure 4.2 illustre le développement de l’apprentissage automatique ci‐dessus. Tous les algorithmes présentés ou cités sont encadrés en vert. Ils appartiennent à la catégorie des processus de décision Markovien. Q‐learning Q‐learning est un algorithme d’apprentissage par renforcement créé pendant la thèse de doc‐ torat de Watkins en 1989 et présenté en 1992 [WD92]. Q‐learning définit A l’ensemble des ac‐ tions a, S l’ensemble des états s de l’environnement et R l’ensemble des récompenses r. Afin de contrôler l’apprentissage, Q‐learning utilise deux paramètres : le taux d’apprentissageα et le facteur dégressif γ. Le taux d’apprentissage α permet de pondérer la récompense actuelle. Plus la valeur du taux d’apprentissage α est grande, plus Q‐learning va donner de l’importance aux dernières ré‐ compenses obtenues. Le facteur dégressif γ pondère l’influence de l’état suivant dans le calcul de la récompense de l’état actuel. Plus le facteur dégressif est proche de 1, plus le choix de Q‐learning se‐ ra influencé par le prochain état. En pratique, le prochain état n’est pas toujours connu. Dans ce cas, le facteur dégressif est nul.