Shie Mannor, Yishay Mansour, Aviv Tamar
This chapter presents an alternative optimization-based approach to solving MDPs through linear programming (LP) formulations. The chapter develops LP formulations for both finite-horizon and discounted infinite-horizon MDPs. The key innovation is representing policies through occupancy measures. The primal LP maximizes return subject to flow constraints, while the dual LP has an elegant interpretation in terms of value functions. The LP approach offers theoretical insights through duality.