IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v47y2022i3p2138-2159.html

Analyzing Approximate Value Iteration Algorithms

Author

Listed:
  • 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)

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.

Suggested Citation

  • Arunselvan Ramaswamy & Shalabh Bhatnagar, 2022. "Analyzing Approximate Value Iteration Algorithms," Mathematics of Operations Research, INFORMS, vol. 47(3), pages 2138-2159, August.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:3:p:2138-2159
    DOI: 10.1287/moor.2021.1202
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.1202
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2021.1202?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Michel Benaim & Josef Hofbauer & Sylvain Sorin, 2005. "Stochastic Approximations and Differential Inclusions II: Applications," Levine's Bibliography 784828000000000098, UCLA Department of Economics.
    2. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2005. "Stochastic Approximations and Differential Inclusions; Part II: Applications," Working Papers hal-00242974, HAL.
    3. D. P. De Farias & B. Van Roy, 2000. "On the Existence of Fixed Points for Approximate Value Iteration and Temporal-Difference Learning," Journal of Optimization Theory and Applications, Springer, vol. 105(3), pages 589-608, June.
    4. David Silver & Julian Schrittwieser & Karen Simonyan & Ioannis Antonoglou & Aja Huang & Arthur Guez & Thomas Hubert & Lucas Baker & Matthew Lai & Adrian Bolton & Yutian Chen & Timothy Lillicrap & Fan , 2017. "Mastering the game of Go without human knowledge," Nature, Nature, vol. 550(7676), pages 354-359, October.
    5. Volodymyr Mnih & Koray Kavukcuoglu & David Silver & Andrei A. Rusu & Joel Veness & Marc G. Bellemare & Alex Graves & Martin Riedmiller & Andreas K. Fidjeland & Georg Ostrovski & Stig Petersen & Charle, 2015. "Human-level control through deep reinforcement learning," Nature, Nature, vol. 518(7540), pages 529-533, February.
    6. Arunselvan Ramaswamy & Shalabh Bhatnagar, 2017. "A Generalization of the Borkar-Meyn Theorem for Stochastic Recursive Inclusions," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 648-661, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mathieu Faure & Gregory Roth, 2010. "Stochastic Approximations of Set-Valued Dynamical Systems: Convergence with Positive Probability to an Attractor," Mathematics of Operations Research, INFORMS, vol. 35(3), pages 624-640, August.
    2. Giacomo Lanzani, 2025. "Dynamic Concern for Misspecification," Econometrica, Econometric Society, vol. 93(4), pages 1333-1370, July.
    3. Jiacheng Zhang & Haolan Zhang, 2025. "Towards Human-like Artificial Intelligence: A Review of Anthropomorphic Computing in AI and Future Trends," Mathematics, MDPI, vol. 13(13), pages 1-49, June.
    4. Wang, Peixiang & Xu, Qihang & Li, Yufei & Chen, Qunlong & Tao, Jinghan & Qin, Wei & Huang, Heng & Zou, Ying, 2025. "Learning-based hybrid algorithms for container relocation problem with storage plan," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 197(C).
    5. Omar Al-Ani & Sanjoy Das, 2022. "Reinforcement Learning: Theory and Applications in HEMS," Energies, MDPI, vol. 15(17), pages 1-37, September.
    6. Boute, Robert N. & Gijsbrechts, Joren & van Jaarsveld, Willem & Vanvuchelen, Nathalie, 2022. "Deep reinforcement learning for inventory control: A roadmap," European Journal of Operational Research, Elsevier, vol. 298(2), pages 401-412.
    7. Cason, Timothy N. & Friedman, Daniel & Hopkins, Ed, 2010. "Testing the TASP: An experimental investigation of learning in games with unstable equilibria," Journal of Economic Theory, Elsevier, vol. 145(6), pages 2309-2331, November.
    8. Akimoto, Youhei & Auger, Anne & Hansen, Nikolaus, 2022. "An ODE method to prove the geometric convergence of adaptive stochastic algorithms," Stochastic Processes and their Applications, Elsevier, vol. 145(C), pages 269-307.
    9. Lan Luo, By & Shi, Chengchun & Wang, Jitao & Wu, Zhenke & Li, Lexin, 2025. "Multivariate dynamic mediation analysis under a reinforcement learning framework," LSE Research Online Documents on Economics 127112, London School of Economics and Political Science, LSE Library.
    10. Eunji Lim, 2011. "On the Convergence Rate for Stochastic Approximation in the Nonsmooth Setting," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 527-537, August.
    11. Zhang, Yihao & Chai, Zhaojie & Lykotrafitis, George, 2021. "Deep reinforcement learning with a particle dynamics environment applied to emergency evacuation of a room with obstacles," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 571(C).
    12. Elvira Hernández & Juan Perán, 2026. "An underlying theory of multifunctions in discrete-time set-valued dynamical systems," Journal of Optimization Theory and Applications, Springer, vol. 208(2), pages 1-18, February.
    13. Borkar, Vivek S., 2025. "Stochastic approximation with two time scales: The general case," Stochastic Processes and their Applications, Elsevier, vol. 190(C).
    14. Bolte, Jérôme & Le, Tam & Pauwels, Edouard & Silveti-Falls, Antonio, 2022. "Nonsmooth Implicit Differentiation for Machine Learning and Optimization," TSE Working Papers 22-1314, Toulouse School of Economics (TSE).
    15. Prasenjit Karmakar & Shalabh Bhatnagar, 2018. "Two Time-Scale Stochastic Approximation with Controlled Markov Noise and Off-Policy Temporal-Difference Learning," Mathematics of Operations Research, INFORMS, vol. 43(1), pages 130-151, February.
    16. Saeed Hadikhanloo & Rida Laraki & Panayotis Mertikopoulos & Sylvain Sorin, 2022. "Learning in nonatomic games, part Ⅰ: Finite action spaces and population games," Post-Print hal-03767995, HAL.
    17. Leslie, David S. & Collins, E.J., 2006. "Generalised weakened fictitious play," Games and Economic Behavior, Elsevier, vol. 56(2), pages 285-298, August.
    18. Yang, Kaiyuan & Huang, Houjing & Vandans, Olafs & Murali, Adithya & Tian, Fujia & Yap, Roland H.C. & Dai, Liang, 2023. "Applying deep reinforcement learning to the HP model for protein structure prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 609(C).
    19. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2006. "Stochastic Approximations and Differential Inclusions, Part II: Applications," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 673-695, November.
    20. Weifan Long & Taixian Hou & Xiaoyi Wei & Shichao Yan & Peng Zhai & Lihua Zhang, 2023. "A Survey on Population-Based Deep Reinforcement Learning," Mathematics, MDPI, vol. 11(10), pages 1-17, May.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:47:y:2022:i:3:p:2138-2159. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.