# A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jan 2020.

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

- [Hoeffding's Inequality for Markov Chains under Generalized Concentrability Condition](https://mlsanity.com/paper/2310.02941/) (2023)
- [Online Regenerative Learning](https://mlsanity.com/paper/2209.08657/) (2022)
- [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)

This paper develops a Hoeffding inequality for the partial sums sumk=1n f (Xk), where Xk_k ∈ mathbbZ> 0 is an irreducible Markov chain on a finite state space S, and f : S → [a, b] is a real-valued function. Our bound is simple, general, since it only assumes irreducibility and finiteness of the state space, and powerful. In order to demonstrate its usefulness we provide two applications in multi-armed bandit problems. The first is about identifying an approximately best Markovian arm, while the second is concerned with regret minimization in the context of Markovian bandits.