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

Abounadi, Jinane ; Bertsekas, Dimitri P. ; Borkar, Vivek (2002) Stochastic approximation for nonexpansive maps: application to Q-learning algorithms SIAM Journal on Control and Optimization, 41 (1). pp. 1-22. ISSN 0363-0129

Full text not available from this repository.

Official URL:


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 factwhic h 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.

Item Type:Article
Source:Copyright of this article belongs to Society for Industrial and Applied Mathematics.
Keywords:Stochastic Approximation; Q-Learning; Neuro-dynamic Programmin
ID Code:81450
Deposited On:06 Feb 2012 05:04
Last Modified:06 Feb 2012 05:04

Repository Staff Only: item control page