Decomposition Methods for Solving Finite-Horizon Large MDPs
Conventional algorithms for solving Markov decision processes (MDPs) become intractable for a large finite state and action spaces. Several studies have been devoted to this issue, but most of them only treat infinite-horizon MDPs. This paper is one of the first works to deal with non-stationary fin...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2022/8404716 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832551109020876800 |
|---|---|
| author | Bouchra el Akraoui Cherki Daoui Abdelhadi Larach khalid Rahhali |
| author_facet | Bouchra el Akraoui Cherki Daoui Abdelhadi Larach khalid Rahhali |
| author_sort | Bouchra el Akraoui |
| collection | DOAJ |
| description | Conventional algorithms for solving Markov decision processes (MDPs) become intractable for a large finite state and action spaces. Several studies have been devoted to this issue, but most of them only treat infinite-horizon MDPs. This paper is one of the first works to deal with non-stationary finite-horizon MDPs by proposing a new decomposition approach, which consists in partitioning the problem into smaller restricted finite-horizon MDPs, each restricted MDP is solved independently, in a specific order, using the proposed hierarchical backward induction (HBI) algorithm based on the backward induction (BI) algorithm. Next, the sub-local solutions are combined to obtain a global solution. An example of racetrack problems shows the performance of the proposal decomposition technique. |
| format | Article |
| id | doaj-art-5092dd93d61d40f0888530495d994132 |
| institution | Kabale University |
| issn | 2314-4785 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-5092dd93d61d40f0888530495d9941322025-02-03T06:04:53ZengWileyJournal of Mathematics2314-47852022-01-01202210.1155/2022/8404716Decomposition Methods for Solving Finite-Horizon Large MDPsBouchra el Akraoui0Cherki Daoui1Abdelhadi Larach2khalid Rahhali3Laboratory of Information Processing and Decision SupportLaboratory of Information Processing and Decision SupportLaboratory of Information Processing and Decision SupportLoboratory of MathematicsConventional algorithms for solving Markov decision processes (MDPs) become intractable for a large finite state and action spaces. Several studies have been devoted to this issue, but most of them only treat infinite-horizon MDPs. This paper is one of the first works to deal with non-stationary finite-horizon MDPs by proposing a new decomposition approach, which consists in partitioning the problem into smaller restricted finite-horizon MDPs, each restricted MDP is solved independently, in a specific order, using the proposed hierarchical backward induction (HBI) algorithm based on the backward induction (BI) algorithm. Next, the sub-local solutions are combined to obtain a global solution. An example of racetrack problems shows the performance of the proposal decomposition technique.http://dx.doi.org/10.1155/2022/8404716 |
| spellingShingle | Bouchra el Akraoui Cherki Daoui Abdelhadi Larach khalid Rahhali Decomposition Methods for Solving Finite-Horizon Large MDPs Journal of Mathematics |
| title | Decomposition Methods for Solving Finite-Horizon Large MDPs |
| title_full | Decomposition Methods for Solving Finite-Horizon Large MDPs |
| title_fullStr | Decomposition Methods for Solving Finite-Horizon Large MDPs |
| title_full_unstemmed | Decomposition Methods for Solving Finite-Horizon Large MDPs |
| title_short | Decomposition Methods for Solving Finite-Horizon Large MDPs |
| title_sort | decomposition methods for solving finite horizon large mdps |
| url | http://dx.doi.org/10.1155/2022/8404716 |
| work_keys_str_mv | AT bouchraelakraoui decompositionmethodsforsolvingfinitehorizonlargemdps AT cherkidaoui decompositionmethodsforsolvingfinitehorizonlargemdps AT abdelhadilarach decompositionmethodsforsolvingfinitehorizonlargemdps AT khalidrahhali decompositionmethodsforsolvingfinitehorizonlargemdps |