Efficient Incremental Planning and Learning with Multi-Valued Decision Diagrams - Sorbonne Université Accéder directement au contenu
Article Dans Une Revue Journal of Applied Logic Année : 2017

Efficient Incremental Planning and Learning with Multi-Valued Decision Diagrams

Jean-Christophe Magnan
  • Fonction : Auteur
  • PersonId : 971578

Résumé

In the domain of decision theoretic planning, the factored framework (Factored Markov Decision Process, fmdp) has produced optimized algorithms using structured representations such as Decision Trees (Structured Value Iteration (svi), Structured Policy Iteration (spi)) or Algebraic Decision Diagrams (Stochastic Planning Using Decision Diagrams (spudd)). Since it may be difficult to elaborate the factored models used by these algorithms, the architecture sdyna, which combines learning and planning algorithms using structured representations, was introduced. However, the state-of-the-art algorithms for incremental learning, for structured decision theoretic planning or for reinforcement learning require the problem to be specified only with binary variables and/or use data structures that can be improved in term of compactness. In this paper, we propose to use Multi-Valued Decision Diagrams (mdds) as a more efficient data structure for the sdyna architecture and describe a planning algorithm and an incremental learning algorithm dedicated to this new structured representation. For both planning and learning algorithms, we experimentally show that they allow significant improvements in time, in compactness of the computed policy and of the learned model. We then analyzed the combination of these two algorithms in an efficient sdynainstance for simultaneous learning and planning using mdds.
Fichier principal
Vignette du fichier
Magnan_Efficient.pdf (1.2 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01399290 , version 1 (23-11-2016)

Identifiants

Citer

Jean-Christophe Magnan, Pierre-Henri Wuillemin. Efficient Incremental Planning and Learning with Multi-Valued Decision Diagrams. Journal of Applied Logic, 2017, 22, pp.63-90. ⟨10.1016/j.jal.2016.11.032⟩. ⟨hal-01399290⟩
321 Consultations
201 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More