Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds
Abstract
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.
Related
- Concentration of empirical entropy and transfer entropy for non-regular chains with unbounded memory
- Empirical concentration for chains with infinite memory
- The Spectral Concentration Problem: Interdisciplinary Aspects and Insights
- Robust Estimation of Prior Parameters in Normal-Normal Empirical Bayes
- A Flexible Heavy-Tailed Probability Model for Skewed Positive Data: Theory, Estimation, and Empirical Assessment
BibTeX
@misc{karagulyan2026minimax,
title = {{Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds}},
author = {Vahe Karagulyan and Mikołaj Kasprzak and Pierre Alquier},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20007},
eprint = {2610.20007},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20007},
}
RIS
TY - UNPB
TI - Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds
AU - Vahe Karagulyan
AU - Mikołaj Kasprzak
AU - Pierre Alquier
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20007
UR - https://arxiv.org/abs/2610.20007
AB - 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.
ER -