# Revisiting the Constant Stepsize Stochastic Approximation with Decision-Dependent Markovian Noise

arXiv: https://arxiv.org/abs/2604.13378 · HTML: https://mlsanity.com/paper/2604.13378/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2026.

## Built on by (most cited first, 2 of 2)

- [Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling](https://mlsanity.com/paper/2608.10896/) (2026)
- [Scaling Limits of Constant-Stepsize SGD at Flat Minima](https://mlsanity.com/paper/2607.16384/) (2026)

## Abstract (arXiv)

We revisit the convergence analysis of constant stepsize stochastic approximation (SA) with decision-dependent Markovian noise, with a focus on characterizing the stationary bias against the root of the mean-field equation. We first establish the finite-time p-th moment bounds for the SA iterates in a general decision-dependent setting, which serve as a stability foundation for the subsequent analysis. Building on this foundation, and leveraging a local regularity condition termed Poisson--Gateaux differentiability (WD^ast) for the solution to Poisson equation induced by the decision-dependent Markov kernel, we show that the stationary bias is of the order O(α) for a broad class of decision-dependent settings. Additionally, we establish geometric weak convergence of the joint SA process towards a unique stationary distribution, and a functional central limit theorem. Our relaxed regularity condition enables us to cover cases of non-smooth kernels such as acceptance--rejection mechanisms, projected Langevin dynamics, and clipped state dynamics.