A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits
This work addresses theoretical gaps in concentration inequalities for Markov chains, with applications in reinforcement learning and decision-making under uncertainty, though it is incremental in extending classical results to Markovian settings.
The paper develops a Hoeffding inequality for partial sums in finite-state irreducible Markov chains, providing a simple and general bound, and applies it to multi-armed bandit problems for identifying approximately best arms and minimizing regret.
This paper develops a Hoeffding inequality for the partial sums $\sum_{k=1}^n f (X_k)$, where $\{X_k\}_{k \in \mathbb{Z}_{> 0}}$ is an irreducible Markov chain on a finite state space $S$, and $f : S \to [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.