Concentration of Contractive Stochastic Approximation and Reinforcement Learning

References

• Abounadi J, Bertsekas DP, Borkar V (2002) Stochastic approximation for nonexpansive maps: Application to Q-learning algorithms. SIAM J. Control Optim. 41(1):1–22.Google Scholar
• Benveniste A, Métivier M, Priouret P (2012) Adaptive Algorithms and Stochastic Approximations (Springer Science & Business Media, New York).Google Scholar
• Bertsekas DP, Tsitsiklis JN (1989) Parallel and Distributed Computation: Numerical Methods (Prentice-Hall, Upper Saddle River, NJ).Google Scholar
• Bhandari J, Russo D, Singal R (2018) A finite time analysis of temporal difference learning with linear function approximation. Proc. 31st Conf. Learn. Theory, vol. 75 (PMLR), 1691–1692.Google Scholar
• Borkar VS (1991) Topics in Controlled Markov Chains (Longman Scientific & Technical, Harlow, Essex, UK).Google Scholar
• Borkar VS (2000) On the number of samples required for Q-learning. Proc. 38th Allerton Conf.Google Scholar
• Borkar VS (2002) On the lock-in probability of stochastic approximation. Combinatorics Probability Comput. 11(1):11–20.Google Scholar
• Borkar VS (2021) A concentration bound for contractive stochastic approximation. Systems & Control Letters 153:104947.Google Scholar
• Chen Z, Maguluri ST, Shakkottai S, Shanmugam K (2020) Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes. Advances in Neural Information Processing Systems (Curran Associates Inc., Red Hook, NY), 8223–8234.Google Scholar
• Chen Z, Maguluri ST, Shakkottai S, Shanmugam K (2021) A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants. Preprint, submitted February 2, https://arxiv.org/abs/2102.01567.Google Scholar
• Cho GE, Meyer CD (2001) Comparison of perturbation bounds for the stationary distribution of a Markov chain. Linear Algebra Its Appl. 335(1):137–150.Google Scholar
• Dalal G, Szörényi B, Thoppe G, Mannor S (2018a) Finite sample analyses for TD(0) with function approximation. Proc. AAAI Conf. Artificial Intelligence 32(1):6144–6160.Google Scholar
• Dalal G, Thoppe G, Szörényi B, Mannor S (2018b) Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning. Proc. 31st Conf. Learn. Theory, vol. 75 (PMLR), 1199–1233.Google Scholar
• Doan TT, Nguyen LM, Pham NH, Romberg J (2020) Finite-time analysis of stochastic gradient descent under Markov randomness. Preprint, submitted March 24, https://arxiv.org/abs/2003.10973.Google Scholar
• Even-Dar E, Mansour Y (2004) Learning rates for Q-learning. J. Machine Learn. Res. 5:1–25.Google Scholar
• Jin C, Allen-Zhu Z, Bubeck S, Jordan MI (2018) Is Q-learning provably efficient? Adv. Neural Inform. Processing Systems, vol. 31 (Curran Associates Inc., Red Hook, NY).Google Scholar
• Kamal S (2010) On the convergence, lock-in probability, and sample complexity of stochastic approximation. SIAM J. Control Optim. 48(8):5178–5192.Google Scholar
• Kushner HJ, Shwartz A (1984) An invariant measure approach to the convergence of stochastic approximations with state dependent noise. SIAM J. Control Optim. 22(1):13–27.Google Scholar
• Lasserre JB (1991) Exact formula for sensitivity analysis of Markov chains. J. Optim. Theory Appl. 71(2):407–413.Google Scholar
• Li G, Wei Y, Chi Y, Gu Y, Chen Y (2020) Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction Adv. Neural Inform. Processing Systems, vol. 31 (Curran Associates Inc., Red Hook, NY). 7031–7043.Google Scholar
• Li G, Cai C, Chen Y, Gu Y, Wei Y, Chi Y (2021) Is Q-learning minimax optimal? A tight sample complexity analysis. Preprint, submitted February 12, https://arxiv.org/abs/2102.06548.Google Scholar
• Liu Q, Watbled F (2009) Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in a random environment. Stochastic Processing Appl. 119(10):3101–3132.Google Scholar
• Marbach P, Tsitsiklis J (2001) Simulation-based optimization of Markov reward processes. IEEE Trans. Automated Control 46(2):191–209.Google Scholar
• Meerkov SM (1972) Simplified description of slow Markov walks. 2. Automated Remote Control 33(5):761.Google Scholar
• Meyn S, Tweedie RL (2009) Markov Chains and Stochastic Stability, 2nd ed. (Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK).Google Scholar
• Powell WB (2007) Approximate Dynamic Programming: Solving the Curses of Dimensionality (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Prashanth L, Korda N, Munos R (2021) Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform sampling. Machine Learn. 110(3):559–618.Google Scholar
• Qu G, Wierman A (2020) Finite-time analysis of asynchronous stochastic approximation and Q-learning. Proc. 33rd Conf. Learn. Theory, vol. 125 (PMLR), 3185–3205.Google Scholar
• Seneta E (2021) Sensitivity analysis, ergodicity coefficients, and rank-one updates for finite Markov chains. Stewart WJ, ed. Numerical Solution of Markov Chains (CRC Press, Boca Raton, FL), 121–129.Google Scholar
• Sidford A, Wang M, Wu X, Yang L, Ye Y (2018) Near-optimal time and sample complexities for solving Markov decision processes with a generative model. Adv. Neural Information Processing Systems, vol. 31 (Curran Associates Inc., Red Hook, NY).Google Scholar
• Singh S, Jaakkola T, Littman ML, Szepesvári C (2000) Convergence results for single-step on-policy reinforcement-learning algorithms. Machine Learn. 38(3):287–308.Google Scholar
• Srikant R, Ying L (2019) Finite-time error bounds for linear stochastic approximation and TD learning. Proc. 32nd Conf. on Learn. Theory, 2803–2830.Google Scholar
• Sun T, Sun Y, Yin W (2018) On Markov chain gradient descent. Adv. Neural Information Processing Systems, vol. 31 (Curran Associates Inc., Red Hook, NY).Google Scholar
• Thoppe G, Borkar V (2019) A concentration bound for stochastic approximation via Alekseev’s formula. Stochastic Systems 9(1):1–26.Link, Google Scholar
• Tsitsiklis J, Van Roy B (1997) An analysis of temporal-difference learning with function approximation. IEEE Trans. Automated Control 42(5):674–690.Google Scholar
• Wainwright MJ (2019a) Stochastic approximation with cone-contractive operators: Sharp ℓ∞-bounds for Q-learning. Preprint, submitted May 15, https://arxiv.org/abs/1905.06265.Google Scholar
• Wainwright MJ (2019b) Variance-reduced Q-learning is minimax optimal. Preprint, submitted June 11, https://arxiv.org/abs/1906.04697.Google Scholar
• Wang G, Li B, Giannakis GB (2020) A multistep Lyapunov approach for finite-time analysis of biased stochastic approximation. Preprint, submitted September 10, https://arxiv.org/abs/1909.04299.Google Scholar
• Wang M, Liu J (2016) A stochastic compositional gradient method using Markov samples. Proc. Winter Simulation Conf., 702–713.Google Scholar
• Watkins CJ (1989) Learning from delayed rewards. PhD thesis, King’s College, Cambridge UK.Google Scholar
• Watkins CJ, Dayan P (1992) Q-learning. Machine Learn. 8(3-4):279–292.Google Scholar
• Yang L, Wang M (2019) Sample-optimal parametric Q-learning using linearly additive features. Proc. 36th Internat. Conf. on Machine Learn., 6995–7004.Google Scholar
• Yang Z, Jin C, Wang Z, Wang M, Jordan M (2020) On function approximation in reinforcement learning: Optimism in the face of large state spaces. Adv. Neural Information Processing Systems, vol. 34 (Curran Associates Inc., Red Hook, NY).Google Scholar