Hoeffding's inequality for uniformly ergodic Markov chains

162 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Zap Q-Learning (2017, background): “Extensions to Markovian models either offer very crude bounds [17], or restrictive assumptions [14, 11]; this remains an active area of research [20].”
A tail inequality for suprema of unbounded empirical processes with applications to Markov chains (2007, unknown): “+ f(Xn) where Xi’s form a uniformly ergodic Markov chain were also obtained by Glyn and Ormoneit [6].”
Control Techniques for Complex Networks: Workload (2007, background): “Value functions & CV Kontoyiannis & M. 1999 - Large deviations M. 2006, KLM 2006 Exact bounds & CV Pandit & M. 2005 Control variates: Henderson 1997 Nelson, Glynn Large deviations: Donsker & Varadhan Nummelin & Ney Glynn & Ormoneit 2002 Background: Simulation”
Robustness and generalization (2010, methodology): “Furthermore, we have the following lemma adapted from Theorem 2 of Glynn and Ormoneit (2002).”
Bernstein's inequalities for general Markov chains (2018, unknown): “A few other concentration inequalities for Markov chains are developed upon the mi-norization and drift conditions (Glynn and Ormoneit, 2002; Douc et al., 2011; Adamczak and Bednorz, 2015), or information-theoretical ideas (Kontoyiannis et al., 2005, 2006) rather than the spectral analysis.”