Stochastic Approximation with Markov Noise: Analysis and applications in
  reinforcement learning
  We present for the first time an asymptotic convergence analysis of two
time-scale stochastic approximation driven by "controlled" Markov noise. In
particular, the faster and slower recursions have non-additive controlled
Markov noise components in addition to martingale difference noise. We analyze
the asymptotic behavior of our framework by relating it to limiting
differential inclusions in both time scales that are defined in terms of the
ergodic occupation measures associated with the controlled Markov processes.
Using a special case of our results, we present a solution to the off-policy
convergence problem for temporal-difference learning with linear function
approximation. We compile several aspects of the dynamics of stochastic
approximation algorithms with Markov iterate-dependent noise when the iterates
are not known to be stable beforehand. We achieve the same by extending the
lock-in probability (i.e. the probability of convergence to a specific
attractor of the limiting o.d.e. given that the iterates are in its domain of
attraction after a sufficiently large number of iterations (say) n_0) framework
to such recursions. We use these results to prove almost sure convergence of
the iterates to the specified attractor when the iterates satisfy an
"asymptotic tightness" condition. This, in turn, is shown to be useful in
analyzing the tracking ability of general "adaptive" algorithms. Finally, we
obtain the first informative error bounds on function approximation for the
policy evaluation algorithm proposed by Basu et al. when the aim is to find the
risk-sensitive cost represented using exponential utility. We show that this
happens due to the absence of difference term in the earlier bound which is
always present in all our bounds when the state space is large.
