s'authentifier
version française rss feed

hal-00747729, version 1

Fast Reinforcement Learning with Large Action Sets Using Error-Correcting Output Codes for MDP Factorization

Gabriel Dulac-Arnold () a1, Ludovic Denoyer 1, Philippe Preux () b2, Patrick Gallinari c1

European Conference on Machine Learning 2 (2012) 180-194

Résumé : The use of Reinforcement Learning in real-world scenarios is strongly limited by issues of scale. Most RL learning algorithms are unable to deal with problems composed of hundreds or sometimes even dozens of possible actions, and therefore cannot be applied to many real-world problems. We consider the RL problem in the supervised classification framework where the optimal policy is obtained through a multiclass classifier, the set of classes being the set of actions of the problem. We introduce error-correcting output codes (ECOCs) in this setting and propose two new methods for reducing complexity when using rollouts-based approaches. The first method consists in using an ECOC-based classifier as the multiclass classifier, reducing the learning complexity from O(A2) to O(Alog(A)) . We then propose a novel method that profits from the ECOC's coding dictionary to split the initial MDP into O(log(A)) separate two-action MDPs. This second method reduces learning complexity even further, from O(A2) to O(log(A)) , thus rendering problems with large action sets tractable. We finish by experimentally demonstrating the advantages of our approach on a set of benchmark problems, both in speed and performance.

  • a –  Université Pierre et Marie Curie - Paris 6
  • b –  Université Charles de Gaulle - Lille III
  • c –  Université Pierre et Marie Curie - Paris VI
  • 1 :  Laboratoire d'Informatique de Paris 6 (LIP6)
  • CNRS : UMR7606 – Université Pierre et Marie Curie (UPMC) - Paris VI
  • 2 :  SEQUEL (INRIA Lille - Nord Europe)
  • INRIA – CNRS : UMR8146 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – Ecole Centrale de Lille
  • Domaine : Informatique/Apprentissage
  • Mots-clés : reinforcement learning
 
  • hal-00747729, version 1
  • oai:hal.inria.fr:hal-00747729
  • Contributeur : 
  • Soumis le : Jeudi 8 Novembre 2012, 15:21:30
  • Dernière modification le : Jeudi 8 Novembre 2012, 15:39:43
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...