Analyzing Approximate Value Iteration Algorithms

Arunselvan Ramaswamy () and Shalabh Bhatnagar ()
Additional contact information
Arunselvan Ramaswamy: Department of Computer Science, Paderborn University, 33098 Paderborn, Germany
Shalabh Bhatnagar: Department of Computer Science and Automation and the Robert Bosch Center for Cyber-Physical Systems, Indian Institute of Science, Bengaluru 560012, India

Mathematics of Operations Research, 2022, vol. 47, issue 3, 2138-2159

Abstract: In this paper, we consider the stochastic iterative counterpart of the value iteration scheme wherein only noisy and possibly biased approximations of the Bellman operator are available. We call this counterpart the approximate value iteration (AVI) scheme. Neural networks are often used as function approximators, in order to counter Bellman’s curse of dimensionality. In this paper, they are used to approximate the Bellman operator. Because neural networks are typically trained using sample data, errors and biases may be introduced. The design of AVI accounts for implementations with biased approximations of the Bellman operator and sampling errors. We present verifiable sufficient conditions under which AVI is stable (almost surely bounded) and converges to a fixed point of the approximate Bellman operator. To ensure the stability of AVI, we present three different yet related sets of sufficient conditions that are based on the existence of an appropriate Lyapunov function. These Lyapunov function–based conditions are easily verifiable and new to the literature. The verifiability is enhanced by the fact that a recipe for the construction of the necessary Lyapunov function is also provided. We also show that the stability analysis of AVI can be readily extended to the general case of set-valued stochastic approximations. Finally, we show that AVI can also be used in more general circumstances, that is, for finding fixed points of contractive set-valued maps.

Keywords: Primary: 90C39; 62L20; 90C40; 47H04; approximate value iteration; Lyapunov function–based stability; fixed-point theory for set-valued functions; set-valued stochastic approximation algorithms; dynamical systems viewpoint (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1202 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:3:p:2138-2159

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().