Hoeffding's inequality for uniformly ergodic Markov chains
type: Item
instance of: scholarly article
title: Hoeffding's inequality for uniformly ergodic Markov chains
zbMATH Open document ID: 0999.60019
DOI: 10.1016/S0167-7152(01)00158-4
author: Peter W. Glynn
author: Dirk Ormoneit
published in: Statistics \& Probability Letters
publication date: 2002-09-05T00:00:00Z
review text: 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.
reviewed by: Neculai Curteanu
Mathematics Subject Classification ID: 60E15
zbMATH DE Number: 1796672
zbMATH Keywords: Hoeffding's inequality
zbMATH Keywords: Markov chains
zbMATH Keywords: large deviations
zbMATH Keywords: reinforcement learning algorithm
MaRDI profile type: Publication
cites work: Stationarity detection in the initial transient problem
cites work: Weighted sums of certain dependent random variables
cites work: Multiplicative ergodicity and large deviations for an irreducible Markov chain.
cites work: Q4881152
cites work: Q5822308
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Markov chains and stochastic stability
cites work: Kernel-based reinforcement learning in average-cost problems
cites work: Q4315289
cites work: Q3857500
full work available at URL: s0167-7152(01)00158-4
OpenAlex ID: W2082040833
description: scientific article; zbMATH DE number 1796672