EUVIMEDEUVIMED entdecken
Crossref

A First-Order Approach to Accelerated Value Iteration

Vineet Goyal, Julien Grand-Clément

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →