Lagrange Dual Decomposition for Finite Horizon Markov Decision Processes

Thomas Furmston, David BarberECML/PKDD 2011 · OpenReview

Abstract

Solving finite-horizon Markov Decision Processes with stationary policies is a computationally difficult problem. Our dynamic dual decomposition approach uses Lagrange duality to decouple this hard problem into a sequence of tractable sub-problems. The resulting procedure is a straightforward modification of standard non-stationary Markov Decision Process solvers and gives an upper-bound on the total expected reward. The empirical performance of the method suggests that not only is it a rapidly convergent algorithm, but that it also performs favourably compared to standard planning algorithms such as policy gradients and lower-bound procedures such as Expectation Maximisation.
BibTeX
@inproceedings{furmston2011lagrange,
  author = {Thomas Furmston and David Barber},
  title = {{Lagrange Dual Decomposition for Finite Horizon Markov Decision Processes}},
  booktitle = {ECML/PKDD},
  year = {2011},
  url = {https://openreview.net/forum?id=Vczcz9inEU},
}

Loading related content...

Figure