Stochastic approximation for nonexpansive maps: Application to Q-learning algorithms

Jinane Abounadi, Dimitri P. Bertsekas, Vivek Borkar

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


We discuss synchronous and asynchronous iterations of the form xk+1 = xk + γ(k)(h(xk) + wk), where h is a suitable map and {wk} is a deterministic or stochastic sequence satisfying suitable conditions. In particular, in the stochastic case, these are stochastic approximation iterations that can be analyzed using the ODE approach based either on Kushner and Clark's lemma for the synchronous case or on Borkar's theorem for the asynchronous case. However, the analysis requires that the iterates {xk} be bounded, a fact which is usually hard to prove. We develop a novel framework for proving boundedness in the deterministic framework, which is also applicable to the stochastic case when the deterministic hypotheses can be verified in the almost sure sense. This is based on scaling ideas and on the properties of Lyapunov functions. We then combine the boundedness property with Borkar's stability analysis of ODEs involving nonexpansive mappings to prove convergence (with probability 1 in the stochastic case). We also apply our convergence analysis to Q-learning algorithms for stochastic shortest path problems and are able to relax some of the assumptions of the currently available results.

Original languageEnglish (US)
Pages (from-to)1-22
Number of pages22
JournalSIAM Journal on Control and Optimization
Issue number1
StatePublished - 2003
Externally publishedYes


  • Neuro-dynamic programming
  • Q-learning
  • Stochastic approximation

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Stochastic approximation for nonexpansive maps: Application to Q-learning algorithms'. Together they form a unique fingerprint.

Cite this