Hoeffding's inequality for uniformly ergodic Markov chains (Q1612983)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hoeffding's inequality for uniformly ergodic Markov chains |
scientific article |
Statements
Hoeffding's inequality for uniformly ergodic Markov chains (English)
0 references
5 September 2002
0 references
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.
0 references
Hoeffding's inequality
0 references
Markov chains
0 references
large deviations
0 references
reinforcement learning algorithm
0 references