Hoeffding's inequality for uniformly ergodic Markov chains (Q1612983)

The aim of the present mathematical note is to provide a generalization of Hoeffding's inequality which, in its classical form, gives an exponential bound on partial sums of independent and bounded random variables. The authors propose and prove an extension of the Hoeffding's inequality to the setting of (uniformly ergodic) Markov chains. The deviation of the partial sums (derived from a Markov chain) from their expectation is particularly useful in situations where the uniform control on the constants involved in the exponential bound is required; in particular, within the analysis of reinforcement learning algorithms.