Computing monotone policies for Markov decision processes: a nearly-isotonic penalty approach * *This work was partially supported by the Swedish Research Council under contract 2016-06079 and the Linnaeus Center ACCESS at KTH
| Autor: | Robert Mattila, Bo Wahlberg, Cristian R. Rojas, Vikram Krishnamurthy |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematical optimization
021103 operations research Theoretical computer science Linear programming Computer science Iterative method 0211 other engineering and technologies Partially observable Markov decision process 020206 networking & telecommunications 02 engineering and technology Markov model Regularization (mathematics) Monotone polygon Control and Systems Engineering Convex optimization 0202 electrical engineering electronic engineering information engineering Markov decision process |
| Zdroj: | IFAC-PapersOnLine. 50:8429-8434 |
| ISSN: | 2405-8963 |
| DOI: | 10.1016/j.ifacol.2017.08.1575 |
| Popis: | This paper discusses algorithms for solving Markov decision processes (MDPs) that have monotone optimal policies. We propose a two-stage alternating convex optimization scheme that can accelerate the search for an optimal policy by exploiting the monotone property The first stage is a linear program formulated in terms of the joint state-action probabilities. The second stage is a regularized problem formulated in terms of the conditional probabilities of actions given states. The regularization uses techniques from nearly-isotonic regression. While a variety of iterative method can be used in the first formulation of the problem, we show in numerical simulations that, in particular, the alternating method of multipliers (ADMM) can be significantly accelerated using the regularization step. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|