Apprentissage par renforcement rapide pour des grands ensembles d'actions en utilisant des codes correcteurs d'erreur

Gabriel Dulac-Arnold 1 Ludovic Denoyer 1 Philippe Preux 2 Patrick Gallinari 1
1 MALIRE - Machine Learning and Information Retrieval
LIP6 - Laboratoire d'Informatique de Paris 6
2 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Résumé : L'utilisation de l'apprentissage par renforcement (AR) pour la résolution de problèmes réalistes se heurte à des questions de passage à l'échelle. La plupart des algorithmes d'AR sont incapables de gérer des problèmes avec des centaines, voire des milliers d'actions, ce qui en limite l'application dans la pratique. Nous considérons le problème d'AR dans le cadre de l'apprentissage supervisé où la politique optimale est obtenue sous la forme d'un classeur multi-classes, l'ensemble des classes correspondant à l'ensemble des actions du problème. Nous introduisons l'utilisation de codes correcteurs d'erreurs (CCE) dans ce contexte et proposons deux nouvelles méthodes pour réduire la complexité de l'apprentissage en utilisant des approches à base de rollouts. La première de ces méthodes consiste à introduire un classeur basé sur des CCE comme classeur multi-classes, ce qui réduit la complexité de l'apprentissage de O(A^2 ) a O(A log(A)). Ensuite, nous proposons une seconde méthode qui met à profit le dictionnaire de codage du CCE pour découper le PDM initial en O(log(A)) PDM à 2 actions. Cette seconde méthode réduit la complexité de l'apprentissage de O(A^2) a O(log(A)) ce qui permet de traiter en des temps très raisonnables des problèmes avec un grand nombre d'actions. Nous terminons avec une démonstration expérimentale de l'intérêt de notre approche.
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-00736322
Contributor : Olivier Buffet <>
Submitted on : Friday, September 28, 2012 - 9:03:13 AM
Last modification on : Thursday, March 21, 2019 - 1:07:50 PM
Long-term archiving on : Friday, December 16, 2016 - 6:07:13 PM

File

2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00736322, version 1

Citation

Gabriel Dulac-Arnold, Ludovic Denoyer, Philippe Preux, Patrick Gallinari. Apprentissage par renforcement rapide pour des grands ensembles d'actions en utilisant des codes correcteurs d'erreur. Journées Francophones sur la planification, la décision et l'apprentissage pour le contrôle des systèmes - JFPDA 2012, May 2012, Villers-lès-Nancy, France. 12 p. ⟨hal-00736322⟩

Share

Metrics

Record views

536

Files downloads

202