Variable resolution discretization for high-accuracy solutions of optimal control problems

Remi Munos and Andrew Moore
International Joint Conference on Artificial Intelligence, August, 1999.


Download
  • Adobe portable document format (pdf) (431KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
State abstraction is of central importance in reinforcement learning and Markov Decision Processes. This paper studies the case of variable resolution state abstraction for continuous-state, deterministic dynamic control problems in which near-optimal policies are required. We describe variable resolution policy and value function representations based on Kuhn triangulations embedded in a kd-tree. We then consider top-down approaches to choosing which cells to split in order to generate improved policies. We begin with local approaches based on value function properties and policy properties that use only features of individual cells in making splitting choices. Later, by introducing two new non-local measures, influence and variance, we derive a splitting criterion that allows one cell to efficiently take into account its impact on other cells when deciding whether to split. We evaluate the performance of a variety of splitting criteria on many benchmark problems (published on the web), paying careful attention to their number-of-cells versus closeness-to-optimality tradeoff curves.

Keywords
Optimal control, reinforcement learning, adaptive methods

Notes
Associated Lab(s) / Group(s): Auton Lab
Associated Project(s): Auton Project
Number of pages: 8

Text Reference
Remi Munos and Andrew Moore, "Variable resolution discretization for high-accuracy solutions of optimal control problems," International Joint Conference on Artificial Intelligence, August, 1999.

BibTeX Reference
@inproceedings{Munos_1999_2093,
   author = "Remi Munos and Andrew Moore",
   title = "Variable resolution discretization for high-accuracy solutions of optimal control problems",
   booktitle = "International Joint Conference on Artificial Intelligence",
   month = "August",
   year = "1999",
}