Skip to Main content Skip to Navigation
Journal articles

Multiply Accelerated Value Iteration for Non-Symmetric Affine Fixed Point Problems and application to Markov Decision Processes

Marianne Akian 1 Stéphane Gaubert 1 Zheng Qu 2 Omar Saadi 1
1 TROPICAL - TROPICAL
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : We analyze a modified version of Nesterov accelerated gradient algorithm, which applies to affine fixed point problems with non self-adjoint matrices, such as the ones appearing in the theory of Markov decision processes with discounted or mean payoff criteria. We characterize the spectra of matrices for which this algorithm does converge with an accelerated asymptotic rate. We also introduce a $d$th-order algorithm, and show that it yields a multiply accelerated rate under more demanding conditions on the spectrum. We subsequently apply these methods to develop accelerated schemes for non-linear fixed point problems arising from Markov decision processes. This is illustrated by numerical experiments.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-03059718
Contributor : Marianne Akian Connect in order to contact the contributor
Submitted on : Sunday, December 13, 2020 - 1:16:30 AM
Last modification on : Friday, January 21, 2022 - 3:12:26 AM

Links full text

Identifiers

  • HAL Id : hal-03059718, version 1
  • ARXIV : 2009.10427

Citation

Marianne Akian, Stéphane Gaubert, Zheng Qu, Omar Saadi. Multiply Accelerated Value Iteration for Non-Symmetric Affine Fixed Point Problems and application to Markov Decision Processes. SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, In press. ⟨hal-03059718⟩

Share

Metrics

Les métriques sont temporairement indisponibles