Search

National audience; En apprentissage par renforcement, la recherche locale de politique est une approche classique permettant de prendre en compte de grands espaces d'état. Formellement, elle consiste à chercher localement dans un espace de politiques paramétrées la solution qui va maximiser la fonction de valeur associée, moyennée selon une loi prédéfinie sur les états. La première contribution de cet article montre que si l'espace de politiques est convexe, \emph{tout optimum local} (approché) présente une \emph{garantie globale de performance}. Malheureusement, supposer la convexité de l'espace de recherche est une hypothèse forte : elle n'est pas satisfaite par les représentations usuelles des politiques et définir une paramétrisation non triviale qui satisfasse cette propriété est difficile. Une solution naturelle pour palier ce problème est d'optimiser la fonction objectif associée grâce à une montée de gradient fonctionnel, la recherche étant contrainte à l'enveloppe convexe de l'espace de politiques. Il s'avère que l'algorithme résultant est une légère généralisation du schéma d'itération conservative de la politique. Ainsi, notre seconde contribution consiste à souligner cette connexion originale entre recherche locale de politique et programmation dynamique approchée.

National audience; Nous étudions la conception d'un joueur artificiel pour le jeu de Tetris. Après une revue des principaux travaux, nous soulignons le fait que comparer différentes performances doit être fait avec le plus grand soin, car les scores ont une grande variance, et de subtils détails d'implémentation ont un effet significatif sur les résultats. Nous considérons ensuite la méthode d'entropie croisée pour optimiser la fonction d'évaluation d'un joueur artificiel, comme suggéré par Szita et al. (2006). Dans ce contexte, nous discutons de l'influence du paramètre bruit, et nous effectuons des expériences avec plusieurs jeux de fonctions de base, comme celles introduites par Bertsekas et al. (1996), par Dellacherie (Fahey, 2003) et des fonctions originales. Cette approche aboutit à un programme de Tetris dont les performances dépassent celles des autres programmes connus. Sur une version simplifiée de Tetris, considérée par la plupart des travaux de recherche, il réalise 35 000 000 ± 20 % de lignes en moyenne par partie.