Partitioned linear programming approximations for MDPs

Branislav Kveton, Milos Hauskrecht
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:341-348, 2008.

Abstract

Approximate linear programming (ALP) is an efficient approach to solving large factored Markov decision processes (MDPs). The main idea of the method is to approximate the optimal value function by a set of basis functions and optimize their weights by linear programming (LP). This paper proposes a new ALP approximation. Comparing to the standard ALP formulation, we decompose the constraint space into a set of low-dimensional spaces. This structure allows for solving the new LP efficiently. In particular, the constraints of the LP can be satisfied in a compact form without an exponential dependence on the treewidth of ALP constraints. We study both practical and theoretical aspects of the proposed approach. Moreover, we demonstrate its scale-up potential on an MDP with more than 2100 states.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-kveton08a, title = {Partitioned linear programming approximations for MDPs}, author = {Kveton, Branislav and Hauskrecht, Milos}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {341--348}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/kveton08a/kveton08a.pdf}, url = {https://proceedings.mlr.press/r6/kveton08a.html}, abstract = {Approximate linear programming (ALP) is an efficient approach to solving large factored Markov decision processes (MDPs). The main idea of the method is to approximate the optimal value function by a set of basis functions and optimize their weights by linear programming (LP). This paper proposes a new ALP approximation. Comparing to the standard ALP formulation, we decompose the constraint space into a set of low-dimensional spaces. This structure allows for solving the new LP efficiently. In particular, the constraints of the LP can be satisfied in a compact form without an exponential dependence on the treewidth of ALP constraints. We study both practical and theoretical aspects of the proposed approach. Moreover, we demonstrate its scale-up potential on an MDP with more than 2100 states.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T Partitioned linear programming approximations for MDPs %A Branislav Kveton %A Milos Hauskrecht %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-kveton08a %I PMLR %P 341--348 %U https://proceedings.mlr.press/r6/kveton08a.html %V R6 %X Approximate linear programming (ALP) is an efficient approach to solving large factored Markov decision processes (MDPs). The main idea of the method is to approximate the optimal value function by a set of basis functions and optimize their weights by linear programming (LP). This paper proposes a new ALP approximation. Comparing to the standard ALP formulation, we decompose the constraint space into a set of low-dimensional spaces. This structure allows for solving the new LP efficiently. In particular, the constraints of the LP can be satisfied in a compact form without an exponential dependence on the treewidth of ALP constraints. We study both practical and theoretical aspects of the proposed approach. Moreover, we demonstrate its scale-up potential on an MDP with more than 2100 states. %Z Reissued by PMLR on 09 October 2024.
APA
Kveton, B. & Hauskrecht, M.. (2008). Partitioned linear programming approximations for MDPs. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:341-348 Available from https://proceedings.mlr.press/r6/kveton08a.html. Reissued by PMLR on 09 October 2024.

Related Material