  We study stochastic approximation algorithms with Markovian noise and
constant step-size $\alpha$. We develop a method based on infinitesimal
generator comparisons to study the bias of the algorithm, which is the expected
difference between $\theta_n$ -- the value at iteration $n$ -- and $\theta^*$
-- the unique equilibrium of the corresponding ODE. We show that, under some
smoothness conditions, this bias is of order $O(\alpha)$. Furthermore, we show
that the time-averaged bias is equal to $\alpha V + O(\alpha^2)$, where $V$ is
a constant characterized by a Lyapunov equation, showing that
$\esp{\bar{\theta}_n} \approx \theta^*+V\alpha + O(\alpha^2)$, where
$\bar{\theta}_n=(1/n)\sum_{k=1}^n\theta_k$ is the Polyak-Ruppert average. We
also show that $\bar{\theta}_n$ converges with high probability around
$\theta^*+\alpha V$. We illustrate how to combine this with Richardson-Romberg
extrapolation to derive an iterative scheme with a bias of order $O(\alpha^2)$.
