# Empirical PAC-Bayes Bounds for Markov Chains

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 60 references that are in the map.
- First posted on arXiv 25 Sep 2025.

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

- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [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)
- [Simpler PAC-Bayesian Bounds for Hostile Data](https://mlsanity.com/paper/1610.07193/) (2016)
- [PAC-Bayes Un-Expected Bernstein Inequality](https://mlsanity.com/paper/1905.13367/) (2019)
- [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)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Learning Partially Known Stochastic Dynamics with Empirical PAC Bayes](https://mlsanity.com/paper/2006.09914/) (2020)
- [Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote](https://mlsanity.com/paper/2106.13624/) (2021)
- [Tighter PAC-Bayes Bounds Through Coin-Betting](https://mlsanity.com/paper/2302.05829/) (2023)
- [Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables](https://mlsanity.com/paper/2206.00706/) (2022)
- [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)
- [Better-than-KL PAC-Bayes Bounds](https://mlsanity.com/paper/2402.09201/) (2024)
- [Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds](https://mlsanity.com/paper/2410.21702/) (2024)
- [Estimating the Mixing Coefficients of Geometrically Ergodic Markov Processes](https://mlsanity.com/paper/2402.07296/) (2024)

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

- [PAC-Bayesian Reinforcement Learning Trains Generalizable Policies](https://mlsanity.com/paper/2510.10544/) (2025)
- [PAC-Bayesian Reconstruction Guarantees for Time Series Variational Autoencoders](https://mlsanity.com/paper/2609.05212/) (2026)
- [Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds](https://mlsanity.com/paper/2610.20007/) (2026)

## Abstract (arXiv)

The core of generalization theory was developed for independent observations. Some PAC and PAC-Bayes bounds are available for data that exhibit a temporal dependence. However, there are constants in these bounds that depend on properties of the data-generating process: mixing coefficients, mixing time, spectral gap... Such constants are unknown in practice. In this paper, we prove a new PAC-Bayes bound for Markov chains. This bound depends on a quantity called the pseudo-spectral gap. The main novelty is that we can provide an empirical bound on the pseudo-spectral gap when the state space is finite. Thus, we obtain the first fully empirical PAC-Bayes bound for Markov chains. This extends beyond the finite case, although this requires additional assumptions. On simulated experiments, the empirical version of the bound is essentially as tight as the non-empirical one.