Voir la notice de l'article provenant de la source Numdam
Markov Decision Processes (MDPs) are a classical framework for stochastic sequential decision problems, based on an enumerated state space representation. More compact and structured representations have been proposed: factorization techniques use state variables representations, while decomposition techniques are based on a partition of the state space into sub-regions and take advantage of the resulting structure of the state transition graph. We use a family of probabilistic exploration-like planning problems in order to study the influence of the modeling structure on the MDP solution. We first discuss the advantages and drawbacks of a graph based representation of the state space, then present our comparisons of two decomposition techniques, and propose to use a global approach combining both state space factorization and decomposition techniques. On the exploration problem instance, it is proposed to take advantage of the natural topological structure of the navigation space, which is partitioned into regions. A number of local policies are optimized within each region, that become the macro-actions of the global abstract MDP resulting from the decomposition. The regions are the corresponding macro-states in the abstract MDP. The global abstract MDP is obtained in a factored form, combining all the initial MDP state variables and one macro-state “region” variable standing for the different possible macro-states corresponding to the regions. Further research is presently conducted on efficient solution algorithms implementing the same hybrid approach for tackling large size MDPs.
@article{RO_2006__40_2_195_0,
author = {Teichteil-K\"onigsbuch, Florent and Fabiani, Patrick},
title = {Influence of modeling structure in probabilistic sequential decision problems},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {195--234},
publisher = {EDP-Sciences},
volume = {40},
number = {2},
year = {2006},
doi = {10.1051/ro:2006019},
zbl = {1112.90092},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2006019/}
}
TY - JOUR AU - Teichteil-Königsbuch, Florent AU - Fabiani, Patrick TI - Influence of modeling structure in probabilistic sequential decision problems JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2006 SP - 195 EP - 234 VL - 40 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2006019/ DO - 10.1051/ro:2006019 LA - en ID - RO_2006__40_2_195_0 ER -
%0 Journal Article %A Teichteil-Königsbuch, Florent %A Fabiani, Patrick %T Influence of modeling structure in probabilistic sequential decision problems %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 195-234 %V 40 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2006019/ %R 10.1051/ro:2006019 %G en %F RO_2006__40_2_195_0
Teichteil-Königsbuch, Florent; Fabiani, Patrick. Influence of modeling structure in probabilistic sequential decision problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 2, pp. 195-234. doi: 10.1051/ro:2006019
Cité par Sources :