A First-Order Approach to Accelerated Value Iteration
Operations Research · 2023-03 · 71 (2) · 517-535
DOI: 10.1287/opre.2022.2269 ↗Kurz gefasst
Fachartikel in der Zeitschrift Operations Research, 2023-03. Verfasst von Vineet Goyal und 1 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 36 Literaturangaben.
Abstract (Originalsprache)
Markov decision processes (MDPs) are used to model stochastic systems in many applications, but computing good policies becomes hard when the effective horizon become very large. In “A First-Order Approach to Accelerated Value Iteration,” Goyal and Grand-Clément present a connection between value iteration (VI) algorithms and gradient descent methods from convex optimization and use acceleration and momentum to design faster algorithms, with convergence guarantees for the computation of the value function of a fixed policy for reversible MDP instances. The authors provide a lower bound on the convergence properties of any first-order algorithm for solving MDPs, where no algorithm can converge faster than VI. Finally, the authors introduce safe accelerated value iteration (S-AVI), which alternates between accelerated updates and value iteration updates. The algorithm S-AVI is worst-case optimal and retains the theoretical convergence properties of VI while exhibiting strong empirical performances and providing significant speedups when compared with classical approaches for a large test bed of MDP instances.
Zitieren
APA
Goyal, V., & Grand-Clément, J. (2023). A First-Order Approach to Accelerated Value Iteration. Operations Research, 71(2), 517-535. https://doi.org/10.1287/opre.2022.2269
Vancouver
Goyal V, Grand-Clément J. A First-Order Approach to Accelerated Value Iteration. Operations Research. 2023;71(2):517-535. doi:10.1287/opre.2022.2269
BibTeX
@article{Goyal2023,
author = {Goyal, Vineet and Grand-Clément, Julien},
title = {A First-Order Approach to Accelerated Value Iteration},
journal = {Operations Research},
year = {2023},
volume = {71},
number = {2},
pages = {517--535},
doi = {10.1287/opre.2022.2269}
}
EUVIMED