2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | L.12.1 | ||
| Paper Title | A Hoeffding Inequality For Finite State Markov Chains and its Applications to Markovian Bandits | ||
| Authors | Vrettos Moulos, University of California Berkeley, United States | ||
| Session | L.12: Multi-Arm Bandits | ||
| Presentation | Lecture | ||
| Track | Statistics and Learning Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | 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. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
