Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
6-2015
Abstract
Partially observable MDPs provide an elegant framework forsequential decision making. Finite-state controllers (FSCs) are often used to represent policies for infinite-horizon problems as they offer a compact representation, simple-to-execute plans, and adjustable tradeoff between computational complexityand policy size. We develop novel connections between optimizing FSCs for POMDPs and the dual linear programfor MDPs. Building on that, we present a dual mixed integer linear program (MIP) for optimizing FSCs. To assign well-defined meaning to FSC nodes as well as aid in policy search, we show how to associate history-based features with each FSC node. Using this representation, we address another challenging problem, that of iteratively deciding which nodes to add to FSC to get a better policy. Using an efficient off-the-shelf MIP solver, we show that this new approach can find compact near-optimal FSCs for severallarge benchmark domains, and is competitive with previous best approaches.
Discipline
Artificial Intelligence and Robotics | Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering
Research Areas
Intelligent Systems and Optimization
Publication
Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling: Jerusalem, Israel, June 7-11, 2015
First Page
156
Last Page
164
Publisher
AAAI Press
City or Country
Menlo Park, CA
Citation
KUMAR, Akshat and ZILBERSTEIN, Shlomo.
History-Based Controller Design and Optimization for Partially Observable MDPs. (2015). Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling: Jerusalem, Israel, June 7-11, 2015. 156-164.
Available at: https://ink.library.smu.edu.sg/sis_research/2915
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://www.aaai.org/ocs/index.php/ICAPS/ICAPS15/paper/view/10622
Included in
Artificial Intelligence and Robotics Commons, Operations Research, Systems Engineering and Industrial Engineering Commons