Convex and Lipschitz function approximations for Markov decision processes

Jeremy Yee

Published 2017-12-04Version 1

This paper studies the use of convex Lipschitz continuous functions to approximate the value functions in Markov decision processes. Compact convergence is proved under various sampling schemes for the driving state disturbance. Under some assumptions, these approximations give a non-decreasing sequence of lower bounding or a non-increasing sequence of upper bounding functions. Numerical experiments involving piecewise linear approximations for a Bermudan put option demonstrate that tight bounds for its fair price can be obtained within fractions of a cpu second.