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

DOI10.1137/20M1367192zbMath1486.90203arXiv2009.10427OpenAlexW3088211401MaRDI QIDQ5862806

Zheng Qu, Marianne Akian, Stéphane Gaubert, Omar Saadi

Publication date: 10 March 2022

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2009.10427

zbMATH Keywords

optimal controldynamic programmingvalue iterationnonexpansive mapsfixed point problemslarge scale optimizationKrasnosel'skiĭ-Mann algorithmNesterov acceleration

Mathematics Subject Classification ID

Dynamic programming (90C39) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Markov and semi-Markov decision processes (90C40)

Uses Software

• Anderson
• SuperMann

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the convergence rate of the Halpern-iteration
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Introductory lectures on convex optimization. A basic course.
• Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators
• Performance of first-order methods for smooth convex minimization: a novel approach
• Circular law theorem for random Markov matrices
• Controlled Markov processes and viscosity solutions
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• Approximate policy iteration: a survey and some new methods
• Two classes of multisecant methods for nonlinear acceleration
• Anderson Acceleration for Fixed-Point Iterations
• A General Inertial Proximal Point Algorithm for Mixed Variational Inequality Problem
• An Analysis of Stochastic Shortest Path Problems
• Monotone Operators and the Proximal Point Algorithm
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• A generic online acceleration scheme for optimization algorithms via relaxation and inertia
• Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
• SuperMann: A Superlinearly Convergent Algorithm for Finding Fixed Points of Nonexpansive Operators
• Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor
• Newton-Type Methods for Optimization and Variational Problems
• Some methods of speeding up the convergence of iteration methods
• Iterative Procedures for Nonlinear Integral Equations
• Mean Value Methods in Iteration

This page was built for publication: Multiply Accelerated Value Iteration for NonSymmetric Affine Fixed Point Problems and Application to Markov Decision Processes