2020

Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes

Chen, Zaiwei, Maguluri, Siva Theja, Shakkottai, Sanjay et al.

Understand

Stochastic Approximation (SA) is a popular approach for solving fixed-point equations where the information is corrupted by noise.

In this paper, we consider an SA involving a contraction mapping with respect to an arbitrary norm, and show its finite-sample error bounds while using different stepsizes.
The idea is to construct a smooth Lyapunov function using the generalized Moreau envelope, and show that the iterates of SA have negative drift with respect to that Lyapunov function.
Our result is applicable in Reinforcement Learning (RL).

Built on

Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning
Original
Chen, Z., Zhang, S., Doan, T. T., Clarke, J.-P., and Maguluri, S. T. (2019) · 1905
Earlier work this paper cites.
Stochastic approximation with cone-contractive operators: Sharp ℓ ∞ \ell_{\infty} -bounds for Q {Q} -learning
Original
Wainwright, M. J. (2019) · 1905
Earlier work this paper cites.
Torchbeast: a PyTorch platform for distributed RL
Original
Küttler, H., Nardelli, N., Lavril, T., Selvatici, M., Sivakumar, V., Rocktäschel, T., and Grefenstette, E. (2019) · 1910
Earlier work this paper cites.
Improved upper bounds on the expected error in constant step-size Q Q -learning
Beck, C. L. and Srikant, R. (2013) · 1931
Earlier work this paper cites.
A stochastic approximation method
Robbins, H. and Monro, S. (1951) · 1951
Earlier work this paper cites.
On stochastic approximation
Dvoretzky, A. (1956) · 1956
Earlier work this paper cites.
Proximité et dualité dans un espace hilbertien
Moreau, J.-J. (1965) · 1965
Earlier work this paper cites.
Importance sampling for stochastic simulations
Glynn, P. W. and Iglehart, D. L. (1989) · 1989
Earlier work this paper cites.
Q Q -learning
Watkins, C. J. and Dayan, P. (1992) · 1992
Earlier work this paper cites.
Convergence of stochastic iterative dynamic programming algorithms
Jaakkola, T., Jordan, M. I., and Singh, S. P. (1994) · 1994
Earlier work this paper cites.
Asynchronous stochastic approximation and Q Q -learning
Tsitsiklis, J. N. (1994) · 1994
Earlier work this paper cites.
Dynamic programming and optimal control
Bertsekas, D. P., Bertsekas, D. P., Bertsekas, D. P., and Bertsekas, D. P. (1995) · 1995
Earlier work this paper cites.
Neuro-dynamic programming
Bertsekas, D. P. and Tsitsiklis, J. N. (1996) · 1996
Earlier work this paper cites.
Linear Algebra
Lax, P. (1997) · 1997
Earlier work this paper cites.
Analysis of temporal-difference learning with function approximation
Tsitsiklis, J. N. and Van Roy, B. (1997) · 1997
Earlier work this paper cites.
Average cost temporal-difference learning
Tsitsiklis, J. N. and Van Roy, B. (1999) · 1999
Earlier work this paper cites.

Similar

On the number of samples required for Q Q -learning
Borkar, V. (2000) · 2000
Cited alongside, same era.
The ODE method for convergence of stochastic approximation and reinforcement learning
Borkar, V. S. and Meyn, S. P. (2000) · 2000
Cited alongside, same era.
Finite-time analysis of asynchronous stochastic approximation and Q Q -learning
Original
Qu, G. and Wierman, A. (2020) · 2002
Cited alongside, same era.
Learning rates for Q Q -learning
Even-Dar, E. and Mansour, Y. (2003) · 2003
Cited alongside, same era.
Introduction to Hilbert spaces with applications
Debnath, L., Mikusinski, P., et al. (2005) · 2005
Cited alongside, same era.
Boundedness of iterates in Q Q -learning
Gosavi, A. (2006) · 2006
Cited alongside, same era.
Sample complexity of asynchronous Q Q -learning: Sharper analysis and variance reduction
Original
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020) · 2006
Cited alongside, same era.
Stochastic approximation: a dynamical systems viewpoint
Borkar, V. S. (2009) · 2009
Cited alongside, same era.
Robust stochastic approximation approach to stochastic programming
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. (2009) · 2009
Cited alongside, same era.
Convergence results for some temporal difference methods based on least squares
Yu, H. and Bertsekas, D. P. (2009) · 2009
Cited alongside, same era.
Stochastic approximation: a survey
Kushner, H. (2010) · 2010
Cited alongside, same era.
Smoothing and first order methods: A unified framework
Beck, A. and Teboulle, M. (2012) · 2012
Cited alongside, same era.

Then

Safe, multi-agent, reinforcement learning for autonomous driving
Original
Shalev-Shwartz, S., Shammah, S., and Shashua, A. (2016) · 2016
Later among the works it cites.
Mastering the game of go with deep neural networks and tree search
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016) · 2016
Later among the works it cites.
First-order methods in optimization
Beck, A. (2017) · 2017
Later among the works it cites.
Markov chains and mixing times
Levin, D. A. and Peres, Y. (2017) · 2017
Later among the works it cites.
A finite time analysis of temporal difference learning with linear function approximation
Bhandari, J., Russo, D., and Singal, R. (2018) · 2018
Later among the works it cites.
Optimization methods for large-scale machine learning
Bottou, L., Curtis, F. E., and Nocedal, J. (2018) · 2018
Later among the works it cites.
Finite sample analysis for TD(0) with function approximation
Dalal, G., Szörényi, B., Thoppe, G., and Mannor, S. (2018) · 2018
Later among the works it cites.
IMPALA: Scalable distributed deep-rl with importance weighted actor-learner architectures
Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T., Dunning, I., et al. (2018) · 2018
Later among the works it cites.
Learning to navigate in cities without a map
Mirowski, P., Grimes, M., Malinowski, M., Hermann, K. M., Anderson, K., Teplyashin, D., Simonyan, K., Zisserman, A., Hadsell, R., et al. (2018) · 2018
Later among the works it cites.
Reinforcement learning: An introduction
Sutton, R. S. and Barto, A. G. (2018) · 2018
Later among the works it cites.
High-dimensional probability: An introduction with applications in data science
Vershynin, R. (2018) · 2018
Later among the works it cites.
Stochastic model-based minimization of weakly convex functions
Davis, D. and Drusvyatskiy, D. (2019) · 2019
Later among the works it cites.
Finite-time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning
Doan, T., Maguluri, S., and Romberg, J. (2019) · 2019
Later among the works it cites.
Finite-time error bounds for linear stochastic approximation and TD learning
Srikant, R. and Ying, L. (2019) · 2019
Later among the works it cites.
A concentration bound for stochastic approximation via alekseev’s formula
Thoppe, G. and Borkar, V. (2019) · 2019
Later among the works it cites.
First-order and Stochastic Optimization Methods for Machine Learning
Lan, G. (2020) · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…