# Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds

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

## Key facts

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

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Generalization Bounds: Perspectives from Information Theory and PAC-Bayes](https://mlsanity.com/paper/2309.04381/) (2023)
- [Variational approach for learning Markov processes from time series data](https://mlsanity.com/paper/1707.04659/) (2017)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [Learning Partially Known Stochastic Dynamics with Empirical PAC Bayes](https://mlsanity.com/paper/2006.09914/) (2020)
- [Predictive PAC Learning and Process Decompositions](https://mlsanity.com/paper/1309.4859/) (2013)
- [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024)
- [PAC-Bayesian theory for stochastic LTI systems](https://mlsanity.com/paper/2103.12866/) (2021)
- [Rosenthal-type inequalities for linear statistics of Markov chains](https://mlsanity.com/paper/2303.05838/) (2023)
- [Approximations of the Restless Bandit Problem](https://mlsanity.com/paper/1702.06972/) (2017)
- [A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits](https://mlsanity.com/paper/2001.01199/) (2020)
- [Hoeffding's Inequality for Markov Chains under Generalized Concentrability Condition](https://mlsanity.com/paper/2310.02941/) (2023)
- [Estimating the Mixing Coefficients of Geometrically Ergodic Markov Processes](https://mlsanity.com/paper/2402.07296/) (2024)
- [Empirical PAC-Bayes Bounds for Markov Chains](https://mlsanity.com/paper/2509.20985/) (2025)
- [Estimating the spectral gap of a trace-class Markov operator](https://mlsanity.com/paper/1704.00850/) (2017)
- [Spectral thresholding for the estimation of Markov chain transition operators](https://mlsanity.com/paper/1808.08153/) (2018)
- [Adaptive KL-UCB based Bandit Algorithms for Markovian and i.i.d. Settings](https://mlsanity.com/paper/2009.06606/) (2020)
- [Deviation inequalities for stochastic approximation by averaging](https://mlsanity.com/paper/2102.08685/) (2021)
- [Restless Linear Bandits](https://mlsanity.com/paper/2405.10817/) (2024)

## Abstract (arXiv)

We study the minimax estimation of the pseudo-spectral gap γps of a Markov chain from the observation of a single trajectory. Extending earlier works on finite-state space chains by Wolfer and Kontorovich (2024), we provide an estimator in the case of a compact, continuous state-space. Our estimator appears to be minimax-optimal on the class of chains with a transition operator with Lipschitz density, up to logarithmic terms. Our estimator, combined with Paulin's version of Bernstein inequality, allows to derive empirical concentration inequalities for Markov chains. This unlocks many applications, from confidence intervals, to active learning and generalization bounds. In particular, for rested bandits with Markov rewards, we provide a version of UCB with a regret bound similar to the one in the iid case, without assuming any knowledge on the pseudo-spectral gap of the chains.