Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a minimax-optimal estimator for the pseudo-spectral gap of continuous-state Markov chains from a single trajectory, extending prior work to continuous state spaces. The proposed estimator, when combined with Bernstein-type inequalities, yields novel empirical concentration bounds applicable to various machine learning tasks. Specifically, it enables UCB algorithms for Markovian rested bandits with regret bounds matching the i.i.d. case without prior knowledge of the spectral gap.
Continuous Markov chains can now have their pseudo-spectral gap estimated with minimax optimality, unlocking tighter concentration bounds and improved regret guarantees in bandit settings.
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.