Conference item
On the complexity of value iteration
- Abstract:
-
Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal n-step payoff by iterating n times a recurrence equation which is naturally associated to the MDP. At the same time, value iteration provides a policy for the MDP that is optimal on a given finite horizon n. In this paper, we settle the computational complexity of value iteration. We show that, given a horizon n in binary and an MDP, computing an optim...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Version of record, pdf, 537.5KB)
-
- Publisher copy:
- 10.4230/LIPIcs.ICALP.2019.102
Authors
Funding
Bibliographic Details
- Publisher:
- Schloss Dagstuhl Publisher's website
- Host title:
- 46th International Colloquium on Automata, Languages and Programming (ICALP 2019)
- Series:
- Leibniz International Proceedings in Informatics
- Journal:
- 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) Journal website
- Volume:
- 132
- Article number:
- 102
- Publication date:
- 2019-07-08
- Acceptance date:
- 2019-04-19
- DOI:
- ISSN:
-
1868-8969
Item Description
- Keywords:
- Pubs id:
-
pubs:994754
- UUID:
-
uuid:686c3244-5566-4400-851b-93b6c179760b
- Local pid:
- pubs:994754
- Source identifiers:
-
994754
- Deposit date:
- 2019-04-29
Terms of use
- Copyright holder:
- Balaji et al
- Copyright date:
- 2019
- Notes:
- © Nikhil Balaji, Stefan Kiefer, Petr Novotný, Guillermo A. Pérez, and Mahsa Shirmohammadi; licensed under Creative Commons License CC-BY
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record