Skip to main content

On the Convergence of Techniques that Improve Value Iteration

Grzes, Marek, Hoey, Jesse (2013) On the Convergence of Techniques that Improve Value Iteration. In: Neural Networks (IJCNN), The 2013 International Joint Conference. Proceedings of International Joint Conference on Neural Networks (IJCNN). . pp. 1-8. ISBN 978-1-4673-6128-6. (doi:10.1109/IJCNN.2013.6706982)

Abstract

Prioritisation of Bellman backups or updating only a small subset of actions represent important techniques for speeding up planning in MDPs. The recent literature showed new efficient approaches which exploit these directions. Backward value iteration and backing up only the best actions were shown to lead to a significant reduction of the planning time. This paper conducts a theoretical and empirical analysis of these techniques and shows new important proofs. In particular, (1) it identifies weaker requirements for the convergence of backups based on best actions only, (2) a new method for evaluation of the Bellman error is shown for the update that updates one best action once, (3) it presents the theoretical proof of backward value iteration and establishes required initialisation, (4) and shows that the default state ordering of backups in standard value iteration can significantly influence its performance. Additionally, (5) the existing literature did not compare these methods, either empirically or analytically, against policy iteration. The rigorous empirical and novel theoretical parts of the paper reveal important associations and allow drawing guidelines on which type of value or policy iteration is suitable for a given domain. Finally, our chief message is that standard value iteration can be made far more efficient by simple modifications shown in the paper.

Item Type: Conference or workshop item (Paper)
DOI/Identification number: 10.1109/IJCNN.2013.6706982
Subjects: Q Science > Q Science (General)
Q Science > Q Science (General) > Q335 Artificial intelligence
Divisions: Faculties > Sciences > School of Computing
Faculties > Sciences > School of Computing > Computational Intelligence Group
Depositing User: Marek Grzes
Date Deposited: 26 May 2015 20:54 UTC
Last Modified: 29 May 2019 14:36 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/48658 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year