Horizon-based Value Iteration

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/19893

Title: Horizon-based Value Iteration
Author: Zang, Peng ; Irani, Arya ; Isbell, Charles Lee, Jr.
Abstract: We present a horizon-based value iteration algorithm called Reverse Value Iteration (RVI). Empirical results on a variety of domains, both synthetic and real, show RVI often yields speedups of several orders of magnitude. RVI does this by ordering backups by horizons, with preference given to closer horizons, thereby avoiding many unnecessary and incorrect backups. We also compare to related work, including prioritized and partitioned value iteration approaches, and show that our technique performs favorably. The techniques presented in RVI are complementary and can be used in conjunction with previous techniques. We prove that RVI converges and often has better (but never worse) complexity than standard value iteration. To the authors’ knowledge, this is the first comprehensive theoretical and empirical treatment of such an approach to value iteration.
Type: Technical Report
URI: http://hdl.handle.net/1853/19893
Date: 2007
Contributor: Georgia Institute of Technology. College of Computing
Georgia Institute of Technology. School of Interactive Computing
Relation: SIC Technical Reports ; GIT-IC-07-07
Publisher: Georgia Institute of Technology
Subject: Convergence
Reinforcement learning
Reverse value iteration (RVI)
Value iteration

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
GIT-IC-07-07.pdf 166.8Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record