Concentration of Contractive Stochastic Approximation and Reinforcement Learning

2021/06/27 by Chandak, Siddharth, Borkar, Vivek S., Dodhia, Parth · 4 citations
#FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.2106.14308

Abstract

Using a martingale concentration inequality, concentration bounds `from time n₀ on' are derived for stochastic approximation algorithms with contractive maps and both martingale difference and Markov noises. These are applied to reinforcement learning algorithms, in particular to asynchronous Q-learning and TD(0).

Cited by

• A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies
• On the Optimality of Tracking Fisher Information in Adaptive Testing with Stochastic Binary Responses
• Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
• Revisit Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds

Related

• Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise
• Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach
• Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise
• Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning
• A Concentration Bound for TD(0) with Function Approximation