  Stochastic approximation (SA) is a key method used in statistical learning.
Recently, its non-asymptotic convergence analysis has been considered in many
papers. However, most of the prior analyses are made under restrictive
assumptions such as unbiased gradient estimates and convex objective function,
which significantly limit their applications to sophisticated tasks such as
online and reinforcement learning. These restrictions are all essentially
relaxed in this work. In particular, we analyze a general SA scheme to minimize
a non-convex, smooth objective function. We consider update procedure whose
drift term depends on a state-dependent Markov chain and the mean field is not
necessarily of gradient type, covering approximate second-order method and
allowing asymptotic bias for the one-step updates. We illustrate these settings
with the online EM algorithm and the policy-gradient method for average reward
maximization in reinforcement learning.
