# Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 23 references that are in the map.
- First posted on arXiv 24 Sep 2026.

## Builds on (most cited first, 2 of 2)

- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024)
- [Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise](https://mlsanity.com/paper/2605.20999/) (2026)

## Abstract (arXiv)

Adaptive algorithms increasingly make decisions while reshaping the dynamics that generate their future data. We establish a shrinking-tube concentration bound for projected stochastic approximation driven by an adaptive Markov chain. The bound guarantees, with high probability, that every iterate after a chosen time remains within a tolerance around the target that tightens over time. The probability of any exit after the chosen time admits a polynomially decaying upper bound, and a matching lower bound shows that its polynomial exponent cannot be improved in general under finite second moments. The result therefore identifies a sharp tradeoff between how quickly the tolerance shrinks and how rapidly the probability of any future exit decreases. We also extend the analysis to recursions with additional martingale-difference noise and predictable bias, showing how growth in the martingale-difference noise scale slows the decay of the exit-probability bound while predictable bias restricts the admissible tube shrinkage. The proof combines backward kernel replacement, a finite-time mean-squared-error bound, and a blockwise maximal first-exit argument. We apply the theory to inventory learning with stockout-dependent demand and fixed stockout costs, and quantify how numerical gradient accuracy affects the all-future reliability of the resulting policies.