A Sparse Linear Program for Global Planning in Large MDPs

We study a linear programming (LP) approach to planning in large Markov Decision Processes (MDPs), addressing some well-known tractability issues of traditional LP-based approaches. Starting from an LP formulation involving state-action value functions originally due to Mehta and Meyn (2009), we propose a method for reducing both the number of constraints and the number of variables, and study the conditions under which a near-optimal action-value function can be extracted from the solution of the LP. Precisely, we show that whenever the optimal Q-function is nearly realizable by a set of known features, and the feature space is covered by a small number of core state-action pairs, the solution of our reduced LP will be a close approximation of the optimal Q-function. This result significantly extends previous work that only considered state-value functions, and gives hope that LP-based methods can be effective for finding globally optimal policies.

Authors

• Gergely Neu
• Nneka M Okolo

Keywords

No keywords are indexed for this paper.