Artikel
Accelerated decomposition techniques for large discounted Markov decision processes
Many hierarchical techniques to solve large Markov decision processes (MDPs) are based on the partition of the state space into strongly connected components (SCCs) that can be classified into some levels. In each level, smaller problems named restricted MDPs are solved, and then these partial solutions are combined to obtain the global solution. In this paper, we first propose a novel algorithm, which is a variant of Tarjan's algorithm that simultaneously finds the SCCs and their belonging levels. Second, a new definition of the restricted MDPs is presented to ameliorate some hierarchical solutions in discounted MDPs using value iteration (VI) algorithm based on a list of state-action successors. Finally, a robotic motion-planning example and the experiment results are presented to illustrate the benefit of the proposed decomposition algorithms.
- Language
-
Englisch
- Bibliographic citation
-
Journal: Journal of Industrial Engineering International ; ISSN: 2251-712X ; Volume: 13 ; Year: 2017 ; Issue: 4 ; Pages: 417-426 ; Heidelberg: Springer
- Classification
-
Management
- Subject
-
Markov decision process
Graph theory
Tarjan's algorithm
Strongly connected components
Decomposition
- Event
-
Geistige Schöpfung
- (who)
-
Larach, Abdelhadi
Chafik, S.
Daoui, C.
- Event
-
Veröffentlichung
- (who)
-
Springer
- (where)
-
Heidelberg
- (when)
-
2017
- DOI
-
doi:10.1007/s40092-017-0197-7
- Handle
- Last update
-
10.03.2025, 11:43 AM CET
Data provider
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. If you have any questions about the object, please contact the data provider.
Object type
- Artikel
Associated
- Larach, Abdelhadi
- Chafik, S.
- Daoui, C.
- Springer
Time of origin
- 2017
Other Objects (12)
Local evaluation of policies for discounted Markov decision problems
Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods
An Iterative Procedure for Non-Discounted Discrete-Time Markov Decisions
Competitive Markov decision processes
Risk-sensitive Markov decision processes
Market versus Political Decision Making: Implications from Discounted Utility Maximization
A Markov decision model for a surveillance application and risk-sensitive Markov decision processes
Equilibrium in misspecified Markov decision processes
Markov decision processes with uncertain parameters
Entropic Regularization of Markov Decision Processes
Target Value Criterion in Markov Decision Processes
A limit theorem for Markov decision processes
Local evaluation of policies for discounted Markov decision problems
Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods
An Iterative Procedure for Non-Discounted Discrete-Time Markov Decisions
Competitive Markov decision processes
Risk-sensitive Markov decision processes
Market versus Political Decision Making: Implications from Discounted Utility Maximization
A Markov decision model for a surveillance application and risk-sensitive Markov decision processes
Equilibrium in misspecified Markov decision processes
Markov decision processes with uncertain parameters
Entropic Regularization of Markov Decision Processes
Target Value Criterion in Markov Decision Processes
A limit theorem for Markov decision processes
Local evaluation of policies for discounted Markov decision problems
Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods
An Iterative Procedure for Non-Discounted Discrete-Time Markov Decisions
Competitive Markov decision processes
Risk-sensitive Markov decision processes
Market versus Political Decision Making: Implications from Discounted Utility Maximization
A Markov decision model for a surveillance application and risk-sensitive Markov decision processes
Equilibrium in misspecified Markov decision processes
Markov decision processes with uncertain parameters
Entropic Regularization of Markov Decision Processes
Target Value Criterion in Markov Decision Processes