  In this work, we investigate stochastic approximation (SA) with Markovian
data and nonlinear updates under constant stepsize $\alpha>0$. Existing work
has primarily focused on either i.i.d. data or linear update rules. We take a
new perspective and carefully examine the simultaneous presence of Markovian
dependency of data and nonlinear update rules, delineating how the interplay
between these two structures leads to complications that are not captured by
prior techniques. By leveraging the smoothness and recurrence properties of the
SA updates, we develop a fine-grained analysis of the correlation between the
SA iterates $\theta_k$ and Markovian data $x_k$. This enables us to overcome
the obstacles in existing analysis and establish for the first time the weak
convergence of the joint process $(x_k, \theta_k)_{k\geq0}$. Furthermore, we
present a precise characterization of the asymptotic bias of the SA iterates,
given by
$\mathbb{E}[\theta_\infty]-\theta^\ast=\alpha(b_\text{m}+b_\text{n}+b_\text{c})+O(\alpha^{3/2})$.
Here, $b_\text{m}$ is associated with the Markovian noise, $b_\text{n}$ is tied
to the nonlinearity, and notably, $b_\text{c}$ represents a multiplicative
interaction between the Markovian noise and nonlinearity, which is absent in
previous works. As a by-product of our analysis, we derive finite-time bounds
on higher moment $\mathbb{E}[\|\theta_k-\theta^\ast\|^{2p}]$ and present
non-asymptotic geometric convergence rates for the iterates, along with a
Central Limit Theorem.
