Text

Multiply Accelerated Value Iteration for NonSymmetric Affine Fixed Point Problems and Application to Markov Decision Processes

We analyze a modified version of the 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 dth-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 nonlinear fixed point problems arising from Markov decision processes. This is illustrated by numerical experiments.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS; Vol.43 No.1 January-March 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 199-232

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

DYNAMIC PROGRAMMING
OPTIMAL CONTROL
VALUE ITERATION
LARGE SCALE OPTIMIZATION
NONEXPANSIVE MAPS
NESTEROV ACCELERATION
KRASNOSEL'SKIĬ--MANN ALGORITHM
FIXED POINT PROBLEMS

Info Detail Spesifik

https://doi.org/10.1137/20M1367192

Pernyataan Tanggungjawab

Marianne Akian, Stephane Gaubert, Zheng Qu, Omar Saadi

Versi lain/terkait

Lampiran Berkas

Komentar