Probabilistic Contraction Analysis of Iterated Random Operators
- 6 February 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 69 (9) , 5947-5962
Abstract
In many branches of engineering, Banach contraction mapping theorem is employed to establish the convergence of certain deterministic algorithms. Randomized versions of these algorithms have been developed that have proved useful in data-driven problems. In a class of randomized algorithms, in each iteration, the contraction map is approximated with an operator that uses independent and identically distributed samples of certain random variables. This leads to iterated random operators acting on an initial point in a complete metric space, and it generates a Markov chain. In this article, we develop a new stochastic dominance-based proof technique, called probabilistic contraction analysis, for establishing the convergence in probability of Markov chains generated by such iterated random operators in certain limiting regime. The methods developed in this article provides a general framework for understanding convergence of a wide variety of Monte Carlo methods, in which contractive property is present. We apply the convergence result to conclude the convergence of fitted value iteration and fitted relative value iteration in continuous state and continuous action MDPs as representative applications of the general framework developed here.Keywords
All Related Versions
Funding Information
- NSF (CCF-1817212)
- ONR (N00014-20-1-2258)
This publication has 40 references indexed in Scilit:
- Markov Chains2018
- On the reduction of total‐cost and average‐cost MDPs to discounted MDPsNaval Research Logistics (NRL), 2017
- PAC Bounds for Discounted MDPsLecture Notes in Computer Science, 2012
- The ODE Method and Spectral Theory of Markov Operators2007
- Stochastic Orders2007
- Infinite Dimensional Analysis2006
- Principles of Nonparametric Learning2002
- Weak Convergence and Empirical Processes1996
- Recurrent iterated function systemsConstructive Approximation, 1989
- Convergence of Stochastic Processes1984