Abstract

We consider the problem of producing lower bounds on the optimal cost-to-go function of a Markov decision problem. We present two approaches to this problem: one based on the methodology of approximate linear programming (ALP) and another based on the so-called martingale duality approach. We show that these two approaches are intimately connected. Exploring this connection leads us to the problem of finding "optimal" martingale penalties within the martingale duality approach which we dub the pathwise optimization (PO) problem. We show interesting cases where the PO problem admits a tractable solution and establish that these solutions produce tighter approximations than the ALP approach.

Authors
Vijay Desai, Vivek Farias, and Ciamac Moallemi
Format
Chapter
Publication Date
Book
Reinforcement Learning and Approximate Dynamic Programming for Feedback Control

Full Citation

Desai, Vijay, Vivek Farias, and Ciamac Moallemi
. “Bounds for Markov decision processes.” In
Reinforcement Learning and Approximate Dynamic Programming for Feedback Control
, edited by
F.L. Lewis and D. Liu
,
452
-
473
.
New York
:
Wiley-IEEE Press
, 2012.