La carotte et le bâton... et Tetris  

Tetris est un célèbre jeu vidéo créé en 1985 par Alexey Pajitnov. Dans ce jeu de réflexion, le joueur doit empiler des pièces de différentes formes de manière à créer un mur formé de lignes horizontales superposées. Un ordinateur est-il capable d'apprendre tout seul à jouer à ce jeu ? L'apprentissage par renforcement, un domaine de l'intelligence artificielle, propose des solutions à ce genre de problèmes.

1. Apprendre à jouer à Tetris... en théorie

Les êtres vivants ont naturellement la capacité d'améliorer, au fil de leurs expériences, leurs réactions à l'environnement : ainsi, face à une situation donnée, une action entraînant une sensation agréable à plus ou moins long terme sera davantage choisie dans des circonstances analogues qu'une action suivie d'une réponse moins favorable.

L'apprentissage par renforcement a pour objectifs la compréhension et la conception de systèmes informatiques possédant cette aptitude : comment, par exemple, concevoir un programme informatique qui serait capable d'apprendre de façon autonome à jouer à Tetris ? La sensation, agréable ou non, est remplacée par une récompense numérique, positive (une carotte) ou négative (un coup de bâton). Le programme va alors expérimenter les différentes actions qui s'ouvrent à lui au cours du jeu. Petit à petit, pour chaque situation, le programme devra apprendre à choisir les « bonnes » actions. Toute la difficulté réside dans la nécessité de trouver de bons compromis :

• Faut-il explorer l'environnement, au risque d'effectuer de mauvaises actions, ou faut-il exploiter en priorité les actions déjà connues comme étant bonnes, au risque de ne jamais découvrir de meilleures actions ?
• Est-il important d'obtenir immédiatement une récompense élevée, au risque d'avoir de nombreuses récompenses négatives plus tard ?

Modéliser Tetris comme un Processus de Décision Markovien

Initialement inspiré par des travaux en psychologie et développé par la communauté de l'intelligence artificielle, l'apprentissage par renforcement est aujourd'hui reconnu comme un problème entrant dans le cadre mathématique du contrôle optimal, et peut s'appuyer sur un modèle formel qui porte le nom de « Processus de Décision Markovien » (PDM). Un PDM permet de décrire d'une façon générale un agent informatique qui prend des décisions de sorte à bien contrôler un système. À chaque instant, l'agent observe l'état du système. À partir de cet état, l'agent choisit une action. Cette action a deux effets immédiats : le système évolue vers un nouvel état et l'agent reçoit une récompense (ou subit un coût). À l'instant suivant, l'agent se trouve dans une situation analogue, à ceci près que l'état du système peut être différent et que l'agent devra de nouveau faire le choix d'une action, qui ne sera pas forcément la même.

Principe d'un Processus de Décision Markovien.

Le terme « Markovien » désigne un système qui vérifie une propriété fondamentale : la propriété de Markov. Celle-ci signifie que lorsque le système est dans un état, et que l'agent effectue une certaine action, l'état suivant et la récompense obtenue ne dépendent que de l'état actuel, et pas des états précédents. En d'autres termes, le passé (la manière d'être arrivé jusqu'à l'état actuel) n'a plus d'importance, seul le présent (l'état actuel) a une influence sur le futur.

Modéliser un problème sous la forme d'un PDM revient à définir l'ensemble des états du système, l'ensemble des actions de l'agent, la dynamique du système (comment on passe d'un état à un autre), ainsi que les récompenses et les coûts. Pour nous familiariser avec les PDM, voici comment nous pourrions modéliser le jeu de Tetris. Après une courte réflexion, les choix suivants s'imposent :

• L'état contient deux informations : la configuration actuelle du mur et la pièce courante.
• Une action est également composée de deux informations : la colonne et l'orientation dans lesquelles on va lâcher la pièce courante.
• La dynamique, rappelons-le, décrit comment on passe d'un état à un autre quand on choisit une action ; elle découle donc de la définition des états et des actions. Étant donné un état et une action, c'est-à-dire un mur et une pièce qu'on vient de lâcher, on obtient un nouveau mur (sans oublier l'éventuelle suppression des lignes qui pourraient se trouver complétées)... et pour avoir un nouvel état (un état contient un mur et une pièce !), il faut encore préciser comment sera choisie la prochaine pièce : on en sélectionne une aléatoirement avec une probabilité uniforme.
• Finalement, la récompense est d'évidence le nombre de lignes qui sont complétées au moment où on pose la pièce courante.

Application au jeu de Tetris d'un Processus de Décision Markovien.

Valeur et décisions optimales

Pour l'instant, nous avons simplement décrit un modèle... Comment faire maintenant pour que notre programme de Tetris prenne de bonnes décisions ? Que doit-on mettre dans notre programme pour qu'il reçoive le plus de récompenses lors de ses parties ? L'apprentissage par renforcement, qui a pour but de trouver la séquence d'actions qui maximise les récompenses, est la solution que nous allons envisager ici.

Les mathématiciens du contrôle optimal, dont notamment Richard Bellman, ont eu l'idée remarquable d'introduire le concept de valeur optimale. La valeur optimale d'un état est la somme maximale des récompenses qu'il est possible de recevoir en moyenne à partir de cet état. Les algorithmes d'apprentissage par renforcement cherchent à calculer la valeur optimale de chaque état. Si on connaît cette valeur pour chaque état, il est alors facile de choisir la meilleure action à faire dans un état donné : c'est tout simplement celle qui mène à des états dont la valeur optimale est la plus grande. On montre que lorsque la propriété de Markov est vérifiée, la valeur optimale est la solution d'une équation particulière, dite équation de Bellman. Cette équation établit une relation entre la valeur optimale d'un état et la valeur optimale des états auxquels il peut mener. Ainsi, on a une équation pour chaque état, et trouver la valeur optimale de toutes les états revient à résoudre le système composé de l'ensemble de ces équations. On peut par exemple résoudre ce système par un algorithme de « programmation dynamique ». Pour en savoir plus sur l'équation de Bellman et sa résolution, le tout illustré sur un exemple, voir ici .

Revenons à présent à Tetris. Dans ce cadre, comme la récompense est le nombre de lignes que l'on vient de compléter, optimiser la somme des récompenses revient à maximiser le nombre de lignes effectuées durant une partie, c'est-à-dire le score ! Et la valeur optimale introduite par les mathématiciens est tout simplement le meilleur score moyen à venir si dans une configuration du mur on lâche la pièce courante de telle ou telle manière. Comme précédemment, le mieux est évidemment de choisir l'endroit qui nous prédit le meilleur score ou encore la plus grande valeur optimale. On mesure ici la beauté de la théorie du contrôle optimal : si on est capable de calculer cette valeur optimale, c'est-à-dire simplement de résoudre une équation, on peut immédiatement en déduire comment jouer à Tetris de façon optimale.

Mais qu'en est-il en pratique ?