Concentration of Contractive Stochastic Approximation and Reinforcement Learning
Siddharth Chandak, Vivek S. Borkar, Parth Dodhia
Abstract
Using a martingale concentration inequality, concentration bounds “from time n 0 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). Funding: V. S. Borkar was supported in part by a S. S. Bhatnagar Fellowship from the Council of Scientific and Industrial Research, Government of India.
Topics & Concepts
Martingale (probability theory)Reinforcement learningMarkov chainTemporal difference learningInequalityMathematicsAsynchronous communicationApplied mathematicsReinforcementMathematical economicsMathematical optimizationComputer scienceDiscrete mathematicsArtificial intelligenceStatisticsMathematical analysisEngineeringComputer networkStructural engineeringReinforcement Learning in RoboticsStochastic Gradient Optimization TechniquesNeural Networks and Applications