ring abxring

# Hoeffding’s Inequality for Markov Chains under Generalized Concentrability
Condition

Hao Chen<EMAIL_ADDRESS>
Abhishek Gupta<EMAIL_ADDRESS>
Department of ECE
The Ohio State University
Columbus, OH 43210, USA Yin Sun<EMAIL_ADDRESS>
Department of ECE
Auburn University
Auburn, AL 36849, USA Ness Shroff<EMAIL_ADDRESS>
Department of ECE and CSE
The Ohio State University
Columbus, OH 43210, USA

###### Abstract

This paper studies Hoeffding’s inequality for Markov chains under the
generalized concentrability condition defined via integral probability metric
(IPM). The generalized concentrability condition establishes a framework that
interpolates and extends the existing hypotheses of Markov chain Hoeffding-
type inequalities. The flexibility of our framework allows Hoeffding’s
inequality to be applied beyond the ergodic Markov chains in the traditional
sense. We demonstrate the utility by applying our framework to several non-
asymptotic analyses arising from the field of machine learning, including (i)
a generalization bound for empirical risk minimization with Markovian samples,
(ii) a finite sample guarantee for Ployak-Ruppert averaging of SGD, and (iii)
a new regret bound for rested Markovian bandits with general state space.

Keywords: Hoeffding’s inequality, Markov chains, Dobrushin coefficient,
integral probability metric, concentration of measures, ergodicity, empirical
risk minimization, stochastic gradient descent, rested bandit

##  1 Introduction

In this paper, we revisit Hoeffding’s inequality for general state space
Markov Chains through the lens of integral probability metric (IPM). The
general state space considered here is Polish space, i.e., a separable
completely metrizable space. Concentration inequalities provide upper bounds
on the tail probability of large deviation, that is, the deviation of the sum
of random variables from its mean. One of the most important and celebrated
concentration inequalities was first proposed by Hoeffding (1994). Hoeffding’s
inequality states that for $n$ independent bounded random variables
$Y_{i}\in[a_{i},b_{i}]$, $i=1,\cdots,n$ and some $\epsilon>0$, the following
holds

$\displaystyle\mathbb{P}\bigg{(}\bigg{|}\sum_{i=1}^{n}Y_{i}-\sum_{i=1}^{n}\mathbb{E}(Y_{i})\bigg{|}\geq
n\epsilon\bigg{)}\leq
2\exp\bigg{(}\frac{-2(n\epsilon)^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\bigg{)}.$
(1)

Inequalities of this type are also called concentration of measure.
Hoeffding’s inequality gives a sub-Gaussian bound on the tail probability,
i.e., the right-hand side of Equation 1 decays as
$\exp[-\Theta(n\epsilon^{2})]$. There are numerous other concentration
inequalities for independent random variables that provide tail bounds with
varying decay rates depending on the probability distributions of the random
variables. Some related results are Bernstein’s inequality and Bennett’s
inequality with decay rates $\exp[-\Theta(n\epsilon)]$ and
$\exp[-\Theta(n\epsilon\log\epsilon+n\epsilon)]$, respectively. Interested
readers can refer to Boucheron et al. (2013, Section 2) for a complete
overview of this topic. These results are widely used in statistics,
econometrics, causal inference, machine learning, reinforcement learning,
empirical process theory, and other fields as a tool for non-asymptotic
analysis.

The independence assumption in the original Hoeffding’s inequality limits its
usage to applications where dependence among random variables naturally
arises. Many research efforts have been dedicated to the extension of this
result to random variables with various dependence structures, such as
martingales (Azuma, 1967, see Azuma-Hoeffding inequality). In particular,
Hoeffding-type inequalities for Markov chains have attracted much attention
during the past few decades, due to their prevalence in statistics, machine
learning, and stochastic dynamic systems. For example, Markovian dependence
occurs broadly in Markov chain Monte Carlo (MCMC), time series prediction, and
reinforcement learning.

Hoeffding-type inequalities for finite state space Markov chains are well-
studied in the past (Davisson et al., 1981; Watanabe and Hayashi, 2017). See
Moulos and Anantharam (2019); Moulos (2020) for a recent survey on this topic.
For general state space Markov chains, Hoeffding’s inequality was originally
studied (Glynn and Ormoneit, 2002) under Doeblin’s condition (Douc et al.,
2018) which implies uniform ergodicity of Markov chains. More relaxed
conditions were not considered until very recently.

Unlike finite or countably infinite state space Markov chains, uniform
ergodicity for general state space Markov chains is not met easily. As implied
by Doeblin’s condition, the Markov chain is required to jump, within a few
steps, to anywhere in the state space with nontrivial probability given an
arbitrary initial condition. Physical processes, such as the motion of
vehicles and the articulation of robotic arms, often naturally follow
continuity, which means the system state is not likely to evolve far from its
starting point within a short period of time. Therefore, uniform ergodicity
assumption can lead to two major inefficiencies in the analysis: (i) excluding
many “well-behaving” systems, such as a stable linear time-invariant system;
and (ii) yielding loose bounds for the tail probability, which are made
precise in Section 4.

For example, a common assumption in reinforcement learning is that the system
is uniformly ergodic under any control policy. However, many reinforcement
learning algorithms are tested in OpenAI Gym (Brockman et al., 2016)
environments that are deterministic robotic systems. They do not satisfy the
uniform ergodicity under a deterministic control policy, as the singular
nature of Dirac measures violates the minorization condition. However, under a
stabilizing control policy, these systems satisfy weaker versions of
ergodicity, such as ergodicity in the sense of the Wasserstein metric.
Similarly, in multi-armed bandit algorithms, the usual assumption is that the
reward distributions are i.i.d. However, bandits that are driven by physical
systems feature reward samples that are Markovian in nature (Tekin and Liu,
2012; Anantharam et al., 1987) with hard-to-determine convergence properties.
The existing results on this topic assume finite state space and Markov chains
are uniformly ergodic, which is a strong assumption to impose on physical
systems and leads to limited utility in practice. Online risk minimization
with temporally correlated samples is another example. A generalization error
bound was proposed for $\beta$-mixing processes (Agarwal and Duchi, 2012). In
the context of Markovian processes, this corresponds to uniform ergodicity
which, again, is very rigid to use in practice.

The aforementioned bottlenecks prohibit the application of Hoeffding-type
inequality in the analysis of learning algorithms in dynamic systems which are
commonly found in reinforcement learning. Various research efforts have been
dedicated to the relaxation of uniform ergodicity used in Glynn and Ormoneit
(2002). In Miasojedow (2014) and Fan et al. (2021), the Markov transition
kernel is viewed as a linear operator on $L^{2}(\pi)$ where $\pi$ is the
invariant distribution. By assuming a positive spectral gap of the transition
kernel, the authors are able to show Hoeffding’s inequalities for
geometrically ergodic Markov chains. A recent study (Sandrić and Šebek, 2023)
shows a version of Hoeffding’s inequality for Markov chains by using the
Wasserstein metric in place of the total variation (TV) distance. By
considering a weaker metric for the Markov chain convergence condition,
Hoeffding’s inequality now can be extended to non-irreducible Markov chains
which are not covered by the classical ergodicity conditions (Example 1).

Despite the various research efforts made to relax the uniform ergodicity,
they still leave something to be desired—does there exist a flexible notion of
ergodicity that generalizes the existing ones and adapts to different use
cases in practice? We answer this question positively by proposing a novel
notion of Markov chains convergence via integral probability metric (IPM)
(Müller, 1997) and studying Hoeffding’s inequality for Markov chains
converging in general integral probability metric. IPM is a statistical
distance function that has been successfully applied to generative adversarial
networks (GAN), distributionally robust optimization (DRO), and other machine
learning problems (see Section 2.3). It can be intuitively thought of as the
maximal discrepancy between to probability distribution seen by a class of
functions $\mathbf{F}$, or generators:

$\displaystyle\textnormal{{IPM}}_{\mathbf{F}}(\mu,\nu)=\sup_{f\in\mathbf{F}}|\mathbb{E}_{\mu}f-\mathbb{E}_{\nu}f|,$

where $f$ is referred to as the witness function. IPM provides a framework
that recovers many probability metrics by choosing the appropriate function
class (or generator) $\mathbf{F}$ (Table 3). The strength of the probability
metric can be easily controlled by the size of $\mathbf{F}$. This allows us to
extend the convergence of Markov chains in terms of total variation metric to
a wide array of distance functions. Our main results, formally stated in
Theorem 9 and 13 show that, depending on the function applied to the Markov
chain, Hoeffding-type inequality holds when the Markov chain converges in a
weaker sense (than TV metric). In most cases, it is unnecessary to enforce the
ergodicity on the Markov chain if the functions of interest lie in a smaller
set than bounded measurable functions. Thus, our results consider richer
classes of Markov chains and the corresponding function classes for computing
the concentration of measure results, which have not been considered before.
Additionally, we refine the existing results by providing a sharper tail bound
than those assuming the ergodicity. Our assumption on the Markov is adaptive
to the functions applied to the Markov chain, which makes our theory a
flexible framework that generalizes many existing studies.

The remainder of the paper is organized as follows. The rest of Section 1
contains the summary of the main contributions of this paper and an
introduction to the notations. Section 2 is dedicated to the review of the
integral probability metric and its application. Section 3 presents the main
results of this paper and the proofs are deferred to the Appendix. Section 4
reviews the existing Hoeffding-type inequalities in the literature and
establishes their connections with our framework. Applications of Hoeffding’s
inequality to machine learning are presented in Section 5.

Assumptions on Markov Chains | Reference
---|---
Doeblin’s condition/Uniformly ergodic | Glynn and Ormoneit (2002)
V-Uniformly ergodic | Douc et al. (2011)
Geometric ergodic | Miasojedow (2014)
Non-irreducible converging in Wasserstein metric | Sandrić and Šebek (2023)
Periodic | Liu and Liu (2021)
Table 1: Existing Hoeffding’s inequalities for Markov chains

###  1.1 Contributions

The contributions of this paper are summarized as follows.

  1. 1.

Extending the Notion for Markov Chain Convergence. We propose, via IPM, the
generalized concentrability condition and IPM Dobrushin coefficient for
general state space Markov chain. We argue that these two new concepts along
with IPM itself should be treated as a framework to study the convergence of
Markov chains. We demonstrate their unifying power by recovering and extending
the traditional conditions on Markov chains assumed for concentration
inequalities, such as the uniform ergodicity (Douc et al., 2018; Meyn and
Tweedie, 2012), V-uniformly ergodicity (Douc et al., 2011), Wasserstein
ergodicity (Sandrić and Šebek, 2023; Rudolf and Schweizer, 2018), and weak
convergence (Diaconis and Freedman, 1999; Breiman, 1960).

The weak convergence of Markov chains to an invariant distribution is studied
in Diaconis and Freedman (1999) and Breiman (1960) under the iterated random
operator theory. The convergence of Markov chains in the Wasserstein metric is
studied in Hairer et al. (2011) and Butkovsky (2014). Our motivation for
further expanding the notion of Markov chain convergence is to increase the
flexibility of the theory to accommodate the ever-changing real-world
challenges. Characterizing the Markov chain convergence with IPM is suitable
for this task as the strength of the distance function can be controlled via
the choice of generators.

  2. 2.

Hoeffding’s Inequality under Weaker Assumptions on the Markov Chain. We relax
the assumptions on the Markov chains required by Hoeffding-type inequalities.
In the main results, we emphasize the link between the functions applied on
the Markov chains and the generator of the IPM. Armed with this insight, one
can identify the unnecessarily strong conditions used in some existing works.
For example, the empirical mean of a bounded Lipschitz function concentrates
around its mean (under invariant distribution) with Hoeffding-type tail bound
as soon as the Markov chain converges in the bounded Lipschitz metric under a
certain speed. However, according to the existing state-of-the-art result (see
Sandrić and Šebek, 2023, Theorem 1), the convergence needs to happen under the
Wasserstein-1 metric which is known to be slightly stronger.

  3. 3.

Unifying and Strengthening Different Versions of Concentration Inequalities.
Our work unifies, and in some cases strengthens, multiple previous results on
Hoeffding’s inequality for general state space Markov chains. Many existing
results on Hoeffding-type inequalities for Markov chains emerge as special
cases under our framework, including Glynn and Ormoneit (2002); Douc et al.
(2011); Fan et al. (2021); Sandrić and Šebek (2023) to name a few. For
example, we strengthen the Hoeffding inequality for uniformly ergodic Markov
chain derived in Glynn and Ormoneit (2002) by a tighter upper bound on the
martingale difference term and exploit the Hoeffding lemma for martingales
with bounded martingale differences. This also allowed us to derive the
constants in the tail bound. In Section 4, we establish the link with various
Hoeffding-type inequalities in the literature.

Our tail bounds also feature explicit constants, whereas some results in the
literature only provide the existence of constants (see Douc et al., 2018,
Chapter 23) rendering them less convenient to use in practice.

  4. 4.

Applications to Learning Problems. We provide three examples of machine
learning and reinforcement learning in Section 5, where our concentration
result is used to weaken the hypotheses under which the results have been
proved previously. The first example covers the well-studied generalization
error bound for empirical risk minimization with non-i.i.d. samples (Agarwal
and Duchi, 2012). We derive the generalization bound of empirical risk
minimization with Markovian samples, where the sample-generating Markov chain
converges in IPM. This result extends the result in Agarwal and Duchi (2012).
The second example tackles the finite sample analysis of averaging of iterates
of the stochastic gradient descent (SGD), extending the results in Gupta et
al. (2020). The last example establishes the logarithmic regret bound for
general state space Markovian bandit under a UCB-type algorithm, which extends
the existing finite state results reported in Anantharam et al. (1987) and
Tekin and Liu (2012).

###  1.2 Notations

Consider a measure space $(\mathbb{X},\mathcal{X},\zeta)$ equipped with Borel
$\sigma$-algebra $\mathcal{X}$ and a non-negative $\sigma$-finite measure
$\zeta$. Assume $\mathbb{X}$ is a Polish space, that is, a separable
completely metrizable topological space with metric $\mathsf{d}$. Consider a
measurable weight function $V:\mathbb{X}\to[1,\infty)$ and define the $V$-norm
for measurable functions $f:\mathbb{X}\to\mathbb{R}$ as

$\displaystyle\|f\|_{V}=\sup_{x\in\mathbb{X}}\frac{|f(x)|}{V(x)}.$ (2)

The integral of a function is written as $\mu(f)=\int_{\mathbb{X}}fd\mu$. Let
$\mathbb{M}(\mathbb{X})$ denote the set of measurable real-valued function on
$\mathbb{X}$ and
$\mathbb{M}_{V}(\mathbb{X})=\\{f\in\mathbb{M}(\mathbb{X}):\|f\|_{V}<\infty\\}$.
Let $\mathcal{P}(\mathcal{X})$ denote the set of probability measures on
$\mathcal{X}$ and
$\mathcal{P}_{V}(\mathcal{X})=\\{\mu\in\mathcal{P}(\mathcal{X}):\mu(V)<\infty\\}$.
When $V\equiv 1$ for $\forall x\in\mathbb{X}$, $\mathbb{M}_{1}(\mathbb{X})$ is
denoted as $L^{\infty}(\mathbb{X},\zeta)$ or $L^{\infty}(\zeta)$ when there is
not ambiguity, and $V$-norm on $\mathbb{M}_{1}(\mathbb{X})$ is denoted as
$\|\cdot\|_{\infty}$, i.e. the uniform norm. Note that
$\mathcal{P}_{1}(\mathcal{X})$ is the set of probability measures on
$\mathcal{X}$ with finite first moment. Let $\mathbb{L}(\mathbb{X})$ denote
the set of real-valued Lipschitz continuous functions on $\mathbb{X}$ and
$\textnormal{{Lip}}(f)$ denote the Lipschitz constant of
$f\in\mathbb{L}(\mathbb{X})$. Let $\mathbb{C}_{b}(\mathbb{X})$ denote the set
of real-valued continuous bounded functions on $\mathbb{X}$. Let $E$ be a set
and scaling of $E$ by $a\in[0,\infty)$ is written as $a\cdot E=\\{ax:x\in
E\\}$.

Let $\\{X_{n}\\}_{n\geq 0}$ be a Markov chain on $\mathbb{X}$ with Markov
transition kernel $P:\mathbb{X}\times\mathcal{X}\to[0,1]$. We assume the
Markov chain to be time-homogeneous throughout the paper. Denote the $n$ step
transition probability as $P^{n}(x,dy)=\mathbb{P}(X_{n}\in dy|X_{0}=x)$ for
$n\geq 1$. We write $\mathbb{P}_{\mu}(X_{n})$ as the probability distribution
of $X_{n}$ given initial state distribution $\mu$. If $\mu=\delta_{x}$ for
some $x\in\mathbb{X}$, where $\delta_{x}$ is the Dirac measure at $x$, we also
write it as $\mathbb{P}_{x}(X_{n})$. For a $f\in\mathbb{M}(\mathbb{X})$, we
denote $P^{n}f(x)=\int_{\mathbb{X}}f(x^{\prime})P^{n}(x,dx^{\prime})$ for
$n\geq 1$.

Let $a\vee b\coloneqq\max\\{a,b\\}$ and $a\wedge b\coloneqq\min\\{a,b\\}$. Let
$\mathbb{R}_{+}=\\{x\in\mathbb{R}:x\geq 0\\}$ be the set of non-negative real
numbers. Let $\mathbb{Z}_{+}=\\{x\in\mathbb{Z}:x>0\\}$ be the set of positive
integers. Let $\mathbb{N}$ denote the set of natural numbers and we follow the
convention that $0\in\mathbb{N}$.

We summarize the notations for various distance functions used throughout the
paper in Table 2.

Notation | Description
---|---
$\mathsf{d}$ | metric for a Polish space
TV | Total variation (TV) metric
$\textnormal{{W}}_{p,\mathsf{d}}$ | Wasserstein-($p$, $\mathsf{d}$) metric
$\|\cdot\|_{\textnormal{{BL}}}$ | Bounded Lipschitz norm of real-valued functions
BL | Bounded Lipschitz metric between probability measures
$\|\cdot\|_{L^{2}(\pi)}$ |  ${L^{2}(\pi)}$-norm for functions and probability measures
Table 2: List of notation for distance functions

##  2 Overview of IPM

To facilitate our discussion on IPM, we briefly recall its fundamental
properties from Müller (1997) where the term integral probability metric was
first coined. Before that, it was known as the probability metric with a
$\zeta$-structure (Zolotarev, 1984).

###  2.1 Definition and Properties

An IPM is characterized by its generating function class (or generator) as
shown in Definition 1. For general choice of $\mathbf{F}$,
$\textnormal{{IPM}}_{\mathbf{F}}$ is a pseudometric with the following
properties:

  1. 1.

$\textnormal{{IPM}}_{\mathbf{F}}(\mu_{1},\mu_{1})=0$,

  2. 2.

$\textnormal{{IPM}}_{\mathbf{F}}(\mu_{1},\mu_{2})=\textnormal{{IPM}}_{\mathbf{F}}(\mu_{2},\mu_{1})$,

  3. 3.

$\textnormal{{IPM}}_{\mathbf{F}}(\mu_{1},\mu_{3})\leq\textnormal{{IPM}}_{\mathbf{F}}(\mu_{1},\mu_{2})+\textnormal{{IPM}}_{\mathbf{F}}(\mu_{2},\mu_{3})$,

for all $\mu_{1},\mu_{2},\mu_{3}\in\mathcal{P}_{V}(\mathcal{X})$.
$\textnormal{{IPM}}_{\mathbf{F}}$ becomes a metric when
$\textnormal{{IPM}}_{\mathbf{F}}(\mu_{1},\mu_{2})=0\Leftrightarrow\mu_{1}=\mu_{2}$.
Examples of $\mathbf{F}$ such that $\textnormal{{IPM}}_{\mathbf{F}}$ is a
metric are provided in Table 3. For instance, when $\mathbf{F}$ is a
reproducing kernel Hilbert space (RKHS) Aronszajn (1950),
$\textnormal{{IPM}}_{\mathbf{F}}$ is a metric if and only if the kernel
function associated with the RKHS is characteristic (Sriperumbudur et al.,
2010b). To the best of our knowledge, a general sufficient condition on
$\mathbf{F}$ for $\textnormal{{IPM}}_{\mathbf{F}}$ to be a metric is still an
open problem in the literature.

######  Definition 1.

An integral probability (pseudo)metric $\textnormal{{IPM}}_{\mathbf{F}}$ on
$\mathcal{P}_{V}(\mathcal{X})$ generated by a function class
$\mathbf{F}\subseteq\mathbb{M}_{V}(\mathbb{X})$ is defined as

$\displaystyle\textnormal{{IPM}}_{\mathbf{F}}(\mu,\nu)\coloneqq\sup_{h\in\mathbf{F}}|\mu(f)-\nu(f)|,\quad\text{for
}\mu,\ \nu\in\mathcal{P}_{V}(\mathcal{X}),$ (3)

where $f$ is referred to as the witness function, and $\mathbf{F}$ is called
the generator.

######  Definition 2.

Let $\mathbf{F}\subseteq\mathbb{M}_{V}(\mathbb{X})$. We define the maximal
generator of $\mathbf{F}$ as

$\displaystyle\mathbf{G}_{\mathbf{F}}=\\{f\in\mathbb{M}_{V}(\mathbb{X}):|\mu(f)-\nu(f)|\leq\textnormal{{IPM}}_{\mathbf{F}}(\mu,\nu),\
\text{for all }\mu,\nu\in\mathcal{P}_{V}(\mathcal{X})\\}.$ (4)

Given generator $\mathbf{F}$, one can define a unique maximal generator as in
Definition 2. The definition of the maximal generator allows the comparison
between IPMs with different generators, which a formally stated in the
following propositions.

######  Proposition 3.

Let $\mathbf{F}\subseteq\mathbf{D}\subseteq\mathbb{M}_{V}(\mathbb{X})$, and
$\mu,\ \nu\in\mathcal{P}_{V}(\mathcal{X})$. The following statements hold

  1. 1.

$\textnormal{{IPM}}_{\mathbf{F}}(\mu,\nu)\leq\textnormal{{IPM}}_{\mathbf{D}}(\mu,\nu)$.

  2. 2.

$\mathbf{G}_{\mathbf{F}}\subseteq\mathbf{G}_{\mathbf{D}}$.

  3. 3.

If $\mathbf{D}\subseteq\mathbf{G}_{\mathbf{F}}$, then
$\textnormal{{IPM}}_{\mathbf{F}}$ and $\textnormal{{IPM}}_{\mathbf{D}}$ are
identical.

######  Proposition 4.

Let $\mathbf{F}\subseteq\mathbb{M}_{V}(\mathbb{X})$. Then:

  1. 1.

$\mathbf{G}_{\mathbf{F}}$ contains the convex hull of $\mathbf{F}$;

  2. 2.

If $f\in\mathbf{G}_{\mathbf{F}}$, then $\alpha
f+\beta\in\mathbf{G}_{\mathbf{F}}$, for all $\alpha\in[-1,1]$ and
$\beta\in\mathbb{R}$;

  3. 3.

$\mathbf{G}_{\mathbf{F}}$ is closed under the uniform norm.

When $\mathbf{F}=\\{\mathbbm{1}_{B}:B\in\mathcal{X}\\}$ and
$\mathbf{D}=\\{\|f\|_{\infty}\leq 1:f\in\mathbb{M}_{V}(\mathbb{X})\\}$, we can
see that $\mathbf{D}\subseteq\mathbf{G}_{\mathbf{F}}$ as
$\mathbf{G}_{\mathbf{F}}$ contains all absolute convex combination of
$\mathbf{F}$ and is closed under the uniform norm by Proposition 4. Using
Proposition 3 (3), we can conclude that
$\textnormal{{IPM}}_{\mathbf{F}}=\textnormal{{IPM}}_{\mathbf{D}}$. In fact,
they are equivalent representations of the TV metric (differ by a factor of
2).

######  Proposition 5.

If $\mathbf{F}\subseteq\mathbf{D}\subseteq\mathbb{M}_{V}(\mathbb{X})$, and
$\mathbf{D}$ is absolutely convex, contains the constant functions, and is
closed with respect to pointwise convergence, then
$\mathbf{D}=\mathbf{G}_{\mathbf{F}}$.

Function class $\mathbf{F}$ |  Description of $\textnormal{{IPM}}_{\mathbf{F}}$ |  Notation
---|---|---
$\\{f\in\mathbb{C}_{b}(\mathbb{X}):\|f\|_{\infty}\leq 1\\}$ |  Continuous and bounded function on $\mathbb{X}$. Convergence in this IPM implies weak convergence (Shorack and Shorack, 2000). |
$\\{\mathbbm{1}_{B}:B\in\mathcal{X}\\}$ or $\\{f:\|f\|_{\infty}\leq 1\\}$ |  It is 2 times the total variation distance. |  TV
$\\{f\in\mathbb{M}(\mathbb{X}):\|f\|_{\infty}+\textnormal{{Lip}}(f)\leq 1\\}$ |  It is the Dudley metric (Dudley, 2018) which metrizes the weak topology on Polish spaces. |
$\\{f\in\mathbb{M}(\mathbb{X}):\max\\{\|f\|_{\infty},\textnormal{{Lip}}(f)\\}\leq 1\\}$ |  It is the bounded Lipschitz metric (Hille and Theewis, 2022; Czapla et al., 2024) which is equivalent to Dudley metric. |  BL
$\\{f\in\mathbb{M}(\mathbb{X}):\textnormal{{Lip}}(f)\leq 1\\}$ |  It is the Kantorovich–Rubinstein dual representation of the Wasserstein-1 metric on a Polish space (Edwards, 2011). |  $\textnormal{{W}}_{1}$
$\\{f\in\mathbb{M}(\mathbb{X}):\|f\|_{\mathbb{H}_{k}}\leq 1\\}$ |  Closed unit ball in a RKHS $\mathbb{H}_{k}$ with kernel $k$. It is the maximum mean discrepancy. |  $\textnormal{{MMD}}_{k}$.
$\\{f\in\mathbb{M}(\mathbb{X}):\|f\|_{\mathbb{W}}\leq 1\\}$ |  Closed unit ball in a Sobolev space $\mathbb{W}$. This is the Sobolev IPM used in the Sobolev GAN (Mroueh et al., 2018). |
Table 3: Probability metrics in the form of IPM

###  2.2 Connections with Classical Probability Metrics and Weak Convergence

As a general form of probability distance function, IPM recovers many
classical probability metrics with different choices of generators. We collect
some of the most well-known probability metrics and their generators in Table
3.

One of the most important properties of probability metrics is the metrization
of weak topology on the space of probability measures. A sequence of
probability measure $\mu_{n}$ converge weakly to $\mu$ if
$\mu_{n}(f)\to\mu(f)$ for all $f\in\mathbb{C}_{b}(\mathbb{X})$ (Billingsley,
2013), i.e., the continuous and bounded functions on $\mathbb{X}$. A
probability metric is said to metrize the weak topology if convergence in this
probability metric is equivalent to weak convergence.

######  Definition 6.

Let $\mathbb{X}$ be a Polish space and let $V:\mathbb{X}\to[1,\infty)$ be any
weight function. $\textnormal{{IPM}}_{\mathbf{F}}$ is said to have:

  1. 1.

Property ($W_{1}$): if
$\lim_{n\to\infty}\textnormal{{IPM}}_{\mathbf{F}}(\mu_{n},\mu)=0$
$\Leftrightarrow$ $\mu_{n}$ converges to $\mu$ weakly;

  2. 2.

Property ($W_{2}$): if
$\lim_{n\to\infty}\textnormal{{IPM}}_{\mathbf{F}}(\mu_{n},\mu)=0$ for all
$\\{\mu_{n}\\}_{n\in\mathbb{N}}\subset\mathcal{P}_{V}(\mathcal{X})$ such that
$\mu_{n}\to\mu\in\mathcal{P}_{V}(\mathcal{X})$ weakly as $n\to\infty$;

  3. 3.

Property ($W_{3}$): if
$\lim\inf_{n\to\infty}\textnormal{{IPM}}_{\mathbf{F}}(\mu_{n},\nu_{n})\geq\textnormal{{IPM}}_{\mathbf{F}}(\mu,\nu)$,
for all $(\mu_{n}),\ (\nu_{n})\subset\mathcal{P}_{V}(\mathcal{X})$ such that
$\mu_{n}\to\mu$ and $\nu_{n}\to\nu$ weakly as $n\to\infty$ with limits
$\mu,\nu\in\mathcal{P}_{V}(\mathcal{X})$.

Property ($W_{1}$) means $\textnormal{{IPM}}_{\mathbb{F}}$ is equivalent to
weak convergence or induces a weak topology on $\mathcal{P}_{V}(\mathcal{X})$.
Property ($W_{2}$)

######  Proposition 7.

Let $W_{1}$, $W_{2}$, and $W_{3}$ be defined above. The following holds:

  1. 1.

If $\mathbf{F}$ has a uniformly bounded span, is equicontinuous, and contains
the function

$\displaystyle x\mapsto f_{n,A}(x)\coloneqq\max\\{0,1/n-d(x,A)\\},$

for every closed set $A\subset\mathbb{X}$ and all $n\in\mathbb{N}$, then
$\textnormal{{IPM}}_{\mathbf{F}}$ has property $(W_{1})$.

  2. 2.

An $\textnormal{{IPM}}_{\mathbf{F}}$ has property $(W_{2})$ if and only if
$\mathbf{F}$ is equicontinuous and has uniformly bounded span.

  3. 3.

If $\mathbf{F}\subset\mathbb{C}_{b}(\mathbb{X})$, then $(W_{3})$ holds.

######  Remark 8.

With $\mathbf{F}=\\{f\in\mathbb{C}_{b}(\mathbb{X}):\|f\|_{\infty}\leq 1\\}$,
$\textnormal{{IPM}}_{\mathbf{F}}$ implies weak convergence. However, the
converse ($W_{2}$ in Definition 6) fails to hold due to Proposition 7, as
$\mathbf{F}$ is uniformly bounded but not equicontinuous. However, one can
verify that the generator of the Dudley metric has these two properties due to
the additional constraint on the Lipschitz constant. Thus, the Dudley metric
is known to induce weak topology on the space of probability measures (Dudley,
2018).

###  2.3 Applications of IPM in Learning and Optimization

IPM has received much attention from the statistics and machine learning
communities in recent years. Three of the most notable use cases are the
formulation of critics in generative adversarial networks (GAN), the
formulation of the ambiguity set in distributionally robust optimization, and
hypothesis testing.

The first GAN (Goodfellow et al., 2020) uses a binary classifier trained with
cross-entropy loss (KL divergence) as its critic. Since then, numerous critic
designs have been proposed based on different probability distance functions
other than KL divergence. Some belong to the family of $f$-divergence111Also
known as $\phi$-divergence in some papers., such as the $f$-GAN (Nowozin et
al., 2016) which includes the original GAN as a special case. Others fall into
the family of IPM, including MMD-GAN (e.g., Dziugaite et al., 2015; Li et al.,
2017; Arbel et al., 2018; Bińkowski et al., 2018), Wasserstein-GAN (e.g.,
Arjovsky et al., 2017; Gulrajani et al., 2017; Adler and Lunz, 2018; Xu,
2021), and Sobolev GAN (Mroueh et al., 2018). These successful developments
exploit the flexible framework by carefully picking the IPM generators such
that the resulting training objectives have desirable computational properties
and regularization effects. Sobolev-GAN (Mroueh et al., 2018) is one such
example. Based on a novel Sobolev IPM proposed in the same paper, Sobolev-GAN
is empirically shown to be better suited for sequence generation compared to
Wasserstein-GAN due to its conditional CDF matching structure (Mroueh et al.,
2018). Additionally, Sobolev IPM enforces an intrinsic smoothness constraint
(Mroueh et al., 2018) which corresponds to the gradient penalty used in
Wasserstein-GAN (Gulrajani et al., 2017). Unlike Wasserstein distance, Sobolev
IPM enjoys a closed form that allows easy estimation from data. Other IPMs
with novel generators used in GAN training include Cramér distance in Cramér-
GAN (Bellemare et al., 2017) and the Fisher IPM in Fisher-GAN (Mroueh and
Sercu, 2017).

Distributionally robust optimization (DRO) is another topic that popularizes
the use of IPM. For a comprehensive review of DRO, we refer readers to the
recent survey papers Rahimian and Mehrotra (2019) and Lin et al. (2022). The
connection between DRO and IPM lies in the construction of the ambiguity
set222Also know as the uncertainty set. which is a set of probability measures
within a certain distance from a predefined nominal probability measure.
Traditionally, the distance function used for the ambiguity set is the KL-
divergence which yields a dual problem that is finite-dimensional and convex
(Hu and Hong, 2013). More recent studies have considered distance functions
from the IPM family, such as the MMD-DRO (e.g., Zhu et al., 2021; Staib and
Jegelka, 2019) and Wasserstein-DRO (e.g., Mohajerin Esfahani and Kuhn, 2018;
Blanchet and Murthy, 2019; Gao and Kleywegt, 2023; Gao et al., 2022). DRO
under general IPM is studied in Husain (2020) where the authors unify the
previous studies and reveal an interesting link between IPM-DRO and the
previously mentioned GANs with different IPMs.

The use of MMD is well-celebrated in statistical hypothesis testing, such as
two-sample tests (e.g., Gretton et al., 2006, 2012) and online change
detection (e.g., Li et al., 2015; Flynn and Yoo, 2019; Arlot et al., 2019),
due to its superior performance. Other applications of IPM include AI fairness
(Kim et al., 2022) with a novel generator optimized for computational
performance, quantum machine learning using MMD as the loss function (Liu and
Wang, 2018), etc.

The computation property is one of the main reasons IPM is well-received
across many communities in machine learning. For empirical estimation of
different instances of IPM, please refer to Sriperumbudur et al. (2012) and
Sriperumbudur et al. (2010a). For the dimension-free approximation of IPM, see
Han et al. (2023).

##  3 Main Results

In this section, we present the main result of this paper: Hoeffding’s
inequality for Markov chains converging in $\textnormal{{IPM}}_{\mathbf{F}}$
for a nonempty generator $\mathbf{F}\subseteq\mathbb{M}(\mathbb{X})$. To avoid
unnecessary notation clutter, the generator $\mathbf{F}$ of an IPM is always
treated as its maximal generator $\mathbf{G}_{\mathbf{F}}$ in the sequel
unless stated otherwise. Thus, we use $\textnormal{{IPM}}_{\mathbf{F}}$ in
place of $\textnormal{{IPM}}_{\mathbf{G}_{\mathbf{F}}}$ whenever possible.

In section 3.1, we state the Hoeffding-type inequality under the generalized
concentrability condition. In section 3.2, we establish the connection between
the concentrability constant and Dobrushin coefficient.

###  3.1 Hoeffding’s Inequality under the Generalized Concentrability

Consider a Markov transition kernel $P:\mathbb{X}\times\mathcal{X}\to[0,1]$
with invariant probability measure $\mu\in\mathcal{P}(\mathcal{X})$. The
kernel $P$ is said to satisfy the generalized concentrability condition under
$\textnormal{{IPM}}_{\mathbf{F}}$ if

$\displaystyle\Gamma_{\mathbf{F}}\coloneqq\sup_{x\in\mathbb{X}}\sum_{i=1}^{\infty}\textnormal{{IPM}}_{\mathbf{F}}(P^{i}(x,\cdot),\pi)<\infty,$
(5)

and $\Gamma_{\mathbf{F}}$ is called the concentrability constant of $P$.

In Theorem 9, we state Hoeffding’s inequality with time-dependent functions of
the Markov chain under the generalized concentrability condition. The proof is
deferred until Appendix A.1. The functions applied to the Markov chain are
assumed to have bounded spans. Particularly, at time $i\in\mathbb{N}$, let
$f_{i}:\mathbb{X}\to[a_{i},b_{i}]$ be the function applied the Markov chain,
where $a_{i}\leq b_{i}$ and $a_{i},b_{i}\in\mathbb{R}$. Let
$\texttt{span}(f_{i})=b_{i}-a_{i}<\infty$ denote the span of $f_{i}$. We
define $M_{i}=\inf\\{m>0:f_{i}\in m\cdot\mathbf{F}\\}$ as the minimal stretch
of $\mathbf{F}$ to include $f_{i}$. A similar definition is also used in
Husain (2020, Definition 2). We subscript the probability and expectation
notation $\mathbb{P}_{\mu},\mathbb{E}_{\mu}$ with a probability measure $\mu$
to indicate the initial distribution of the Markov chain.

######  Theorem 9 (Time-dependent case).

Let $\\{X_{n}\\}_{n\in\mathbb{N}}\subset\mathbb{X}$ be a Markov chain with
transition kernel $P$. Assume that the Markov kernel $P$ admits a unique
invariant probability measure $\pi$ such that Equation 5 is satisfied. For
$i\in\\{0,\cdots,n-1\\}$ and $n\in\mathbb{Z}_{+}$, suppose $f_{i}$ has bounded
span with minimal stretch $M_{i}\in(0,\infty)$ such that $f_{i}\in
M_{i}\cdot\mathbf{F}$. Let
$\tilde{S}_{n}\coloneqq\sum_{i=0}^{n-1}f_{i}(X_{i})$.

Then, $\epsilon>n^{-1}[M_{1}^{\max}\Gamma_{\mathbf{F}}+\texttt{span}(f_{0})]$
and any initial distribution $\mu\in\mathcal{P}(\mathcal{X})$, we have

$\displaystyle\mathbb{P}_{\mu}\bigg{[}\bigg{|}\tilde{S}_{n}-\sum_{i=0}^{n-1}\pi(f_{i})\bigg{|}>n\epsilon\bigg{]}\leq
2\exp\bigg{(}-\frac{2\\{n\epsilon-[M_{1}^{\max}\Gamma_{\mathbf{F}}+\texttt{span}(f_{0})]\\}^{2}}{\sum_{i=0}^{n-1}[M_{i+1}^{\max}\Gamma_{\mathbf{F}}+\texttt{span}(f_{i})]^{2}}\bigg{)},$
(6)

where $M_{i}^{\max}=\max\\{M_{i},\cdots,M_{n-1}\\}$ for
$i\in\\{0,\cdots,n-1\\}$ and $M_{i}^{\max}=0$ for $i\geq n$.

Proof:  See Appendix A.1.

Markov chains satisfying Equation 5 are called Markov chains converging in
$\textnormal{{IPM}}_{\mathbf{F}}$ with constant $\Gamma_{\mathbf{F}}$.
$\Gamma_{\mathbf{F}}$ defined here is similar to the hypothesis in Sandrić and
Šebek (2023) (also see $\Gamma_{\textnormal{{W}}}$ in Equation 34). In fact,
one can recover their result by picking
$\mathbf{F}=\\{f\in\mathbb{M}(\mathbb{X}):\textnormal{{Lip}}(f)\leq 1\\}$. We
will demonstrate how our framework recovers several existing Hoeffding-type
inequalities in the literature in Section 4. Before that, some remarks are in
order.

######  Remark 10.

The functions $f_{i}$ applied to the Markov chain are linked to the generator
$\mathbf{F}$ of the IPM by a multiplicative factor $M_{i}$. This allows the
users to adaptively choose the strength of the IPM according to the functions
used on the Markov chain.

######  Remark 11.

The numerator of the exponent in Equation 6 is different from the i.i.d. case
in Equation 1. This is due to $\tilde{S}_{n}$ is centered at
$\sum_{i=0}^{n-1}\pi(f_{i})$ instead of
$\mathbb{E}_{\mu}\sum_{i=0}^{n-1}f_{i}(X_{i})$ in the tail probability.

######  Remark 12.

The supremum in Equation 5 may be considered restrictive by some. However, our
proof technique requires that in the most general case of $\mathbf{F}$. We
discuss an alternative condition in Section 3.2 with additional constraints of
$\mathbf{F}$.

Our tail bound in Equation 6 does not have obscure constants. Some results
such as Theorem 27 and the ones presented in Douc et al. (2018, Chapter 23.3)
contains some constants without explicit forms, which are less convenient for
computation purposes. The proof technique we employed combined with the use of
function span makes our tail bound tighter than certain existing results as
explained in Remark 23.

As a byproduct of the time-dependent case, we recover the time-independent
case in Theorem 13. The proof of Theorem 9 can be reused with $f_{i}=f$ for
$i\in\\{0,\cdots,n-1\\}$.

######  Theorem 13 (Time-independent case).

Let $\\{X_{n}\\}_{n\in\mathbb{N}}\subset\mathbb{X}$ be a Markov chain with
transition kernel $P$. Assume that the Markov kernel $P$ admits a unique
invariant probability measure $\pi$ and satisfies Equation 5. Suppose $f$ has
bounded span with minimal stretch $M\in(0,\infty)$ such that $f\in
M\cdot\mathbf{F}$. For $n\in\mathbb{Z}_{+}$, let
$S_{n}\coloneqq\sum_{i=1}^{n}f(X_{i})$.

Then, for $\epsilon>n^{-1}[M\Gamma_{\mathbf{F}}+\texttt{span}(f)]$ and any
initial distribution $\mu\in\mathcal{P}(\mathcal{X})$, we have,

$\displaystyle\mathbb{P}_{\mu}[|S_{n}-n\pi(f)|>n\epsilon]\leq
2\exp\bigg{\\{}-\frac{2\\{n\epsilon-[M\Gamma_{\mathbf{F}}+\texttt{span}(f)]\\}^{2}}{n[M\Gamma_{\mathbf{F}}+\texttt{span}(f)]^{2}}\bigg{\\}}.$
(7)

###  3.2 Relation to Dobrushin Coefficient

Dobrushin contraction coefficient was first proposed by R. Dobrushin
(Dobrushin, 1956) for discrete state space Markov chains. Later studies by Del
Moral et al. (2003) extended the contraction coefficient to general state
space Markov chains. The traditional Dobrushin coefficient describes the
contraction rate of the Markov kernel on the space of probability measures
with respect to the TV metric. The formal definition can be found in Chapter
18 of Douc et al. (2018). Rudolf and Schweizer (2018) studied the properties
of the coefficient where $\textnormal{{IPM}}_{\mathbf{F}}$ is the Wasserstein
metric and called it the generalized Dobrushin coefficient of the Markov
kernel.

In this section, we establish the connection between the Dobrushin coefficient
and the concentrability constant. It is beneficial to the understanding of the
generalized concentrability condition as it provides a way to estimate the
concentrability constant under scenarios. As demonstrated later in section
5.2, the concentrability constant of a Markov chain generated by a random
operator can be estimated from the contraction coefficient of the operator.

We start by defining the IPM Dobrushin coefficient as the analog of the usual
Dobrushin coefficient.

######  Definition 14 (IPM Dobrushin Coefficient).

The IPM Dobrushin contraction coefficient of $P$ with generator $\mathbf{F}$
is defined as

$\displaystyle\Delta_{\mathbf{F}}(P)=\sup\\{\textnormal{{IPM}}_{\mathbf{F}}(\xi
P,\xi^{\prime}P):\xi,\xi^{\prime}\in\mathcal{P}(\mathcal{X}),0<\textnormal{{IPM}}_{\mathbf{F}}(\xi,\xi^{\prime})\leq
1\\}.$ (8)

######  Remark 15.

One can recover the usual definition by simply setting
$\mathbf{F}=\mathbf{F}_{\textnormal{{TV}}}\coloneqq\\{f\in\mathbb{M}(\mathbb{X}):\|f\|_{\infty}\leq
1\\}$.

The following two definitions are crucial to the connection between the IPM
Dobrushin coefficient and the concentrability constant.

######  Definition 16 (Stability of generator).

For $f\in\mathbf{F}$, suppose there exists $\rho=\inf\\{m>0:Pf\in
m\cdot\mathbf{F}\\}$333 It suffices to consider the positive stretch of
$\mathbf{F}$, since $\mathbf{F}$ is assumed to the maximal generator which
implies it is a balanced convex hull.. $\mathbf{F}$ is said to be sable by $P$
if $\rho\leq 1$.

######  Definition 17 (Nonexpansiveness in IPM).

$P$ is said to be nonexpansive in $\textnormal{{IPM}}_{\mathbf{F}}$ if for any
$\xi,\xi^{\prime}\in\mathcal{P}(\mathcal{X})$

$\displaystyle\textnormal{{IPM}}_{\mathbf{F}}(\xi
P,\xi^{\prime}P)\leq\textnormal{{IPM}}_{\mathbf{F}}(\xi,\xi^{\prime})$

For some choices of $\mathbf{F}$, Definition 16 can be satisfied without
additional conditions.

######  Proposition 18.

Suppose $P$ admits invariant distribution $\pi$. The following choices of
$\mathbf{F}$ are stable by $P$,

  1. 1.

$\mathbb{B}_{\|\cdot\|_{\infty}}\coloneqq\\{f\in\mathbb{M}(\mathbb{X}):\|f\|_{\infty}\leq
1\\}$444$\mathbb{B}_{\|\cdot\|_{\infty}}$ and $\mathbb{B}_{L^{\infty}(\pi)}$
are different, especially when $\pi$ is not supported on the whole space.;

  2. 2.

$\mathbb{B}_{L^{p}(\pi)}\coloneqq\\{f\in\mathbb{M}(\mathbb{X}):\|f\|_{L^{p}(\pi)}\leq
1\\}$ for $p\in[1,\infty]$.

Proof:  1) It is obvious that
$Pf=\int_{\mathbb{X}}f(y)P(x,dy)\leq\|f\|_{\infty}$. Thus,
$f\in\mathbb{B}_{\|\cdot\|_{\infty}}\Rightarrow Pf\in B_{\|\cdot\|_{\infty}}$.
2) By Douc et al. (2018, Proposition 1.6.3), the operator norm of $P$ on
${L^{p}(\pi)}$ is 1, and the proof is completed.

It is easy to determine that $P$ is nonexpansive when $\mathbf{F}$ is stable
by $P$ which is formally stated as follows.

######  Proposition 19.

If $\mathbf{F}$ is stable by $P$, then $P$ is nonexpansive in
$\textnormal{{IPM}}_{\mathbf{F}}$.

Proof:  From the definition of $\textnormal{{IPM}}_{\mathbf{F}}$ and
nonexpansiveness, we have

$\displaystyle\textnormal{{IPM}}_{\mathbf{F}}(\xi P,\xi^{\prime}P)$
$\displaystyle=\sup_{f\in\mathbf{F}}\bigg{|}\int_{\mathbb{X}}fd(\xi
P)-\int_{\mathbb{X}}fd(\xi^{\prime}P)\bigg{|}=\sup_{f\in\mathbf{F}}\bigg{|}\int_{\mathbb{X}}Pfd\xi-\int_{\mathbb{X}}Pfd\xi^{\prime}\bigg{|}$
$\displaystyle\leq\sup_{f\in\mathbf{F}}\bigg{|}\int_{\mathbb{X}}fd\xi-\int_{\mathbb{X}}fd\xi^{\prime}\bigg{|}=\textnormal{{IPM}}_{\mathbf{F}}(\xi,\xi^{\prime}),$

where the last inequality follows from the fact that $\mathbf{F}$ is stable by
$P$.

The above development allows us to upper-bound the concentrability constant
with IPM Dobrushin coefficient. As we will see in Lemma 46 in the example of
SGD (Section 5.2), the Markov chain generated by SGD is contractive in
Wasserstein-1 metric and the concentrability constant can be easily bounded by
the corresponding IPM Dobrushin coefficient.

######  Proposition 20.

Suppose $P$ is nonexpansive in $\textnormal{{IPM}}_{\mathbf{F}}$, we have for
$\mu\in\mathcal{P}(\mathcal{X})$,

$\displaystyle\sum_{i=0}^{\infty}\textnormal{{IPM}}_{\mathbf{F}}(\mu
P^{i},\pi)\leq\textnormal{{IPM}}_{\mathbf{F}}(\mu,\pi)\sum_{i=0}^{\infty}\Delta_{\mathbf{F}}(P^{i}).$

Proof:  Repeated application of the nonexpansiveness of $P$ yields the desired
result.

As mentioned in the previous section, it is tempting to remove the supremum in
Equation 5. However, we cannot accomplish that in Theorem 9 for two reasons:
(i) it is at the expanse of restricting the initial condition; (ii) our proof
in Lemma 58 require the supremum to be bounded. Nevertheless, with the
nonexpansiveness of $P$, we can at least circumvent (ii) in the following
theorem.

######  Theorem 21.

Let $\\{X_{n}\\}_{n\in\mathbb{N}}$ be a Markov chain with transition kernel
$P$. Assume that the Markov kernel $P$ admits a unique invariant probability
measure $\pi$ such that

$\displaystyle\tilde{\Gamma}_{\mathbf{F}}\coloneqq\sum_{i=0}^{\infty}\Delta_{\mathbf{F}}(P^{i})<\infty,$
(9)

where $\mathbf{F}$ is one of the choices in Proposition 18. For
$i\in\\{0,\cdots,n-1\\}$ and $n\in\mathbb{Z}_{+}$, suppose $f_{i}$ has bounded
span with minimal stretch $M_{i}\in(0,\infty)$ such that $f_{i}\in
M_{i}\cdot\mathbf{F}$. For $n\in\mathbb{Z}_{+}$, let
$\tilde{S}_{n}\coloneqq\sum_{i=0}^{n-1}f_{i}(X_{i})$.

Then, for
$\epsilon>(2n)^{-1}\textnormal{{IPM}}_{\mathbf{F}}(\mu,\pi)\tilde{A}_{0}$ and
any initial distribution $\mu\in\mathcal{P}(\mathcal{X})$ such that
$\textnormal{{IPM}}_{\mathbf{F}}(\mu,\pi)<\infty$, we have

$\displaystyle\mathbb{P}_{\mu}\bigg{[}\bigg{|}\tilde{S}_{n}-\sum_{i=0}^{n-1}\pi(f_{i})\bigg{|}>n\epsilon\bigg{]}\leq
2\exp\bigg{(}-\frac{2[n\epsilon-\textnormal{{IPM}}_{\mathbf{F}}(\mu,\pi)\tilde{A}_{0}/2]^{2}}{\sum_{i=0}^{n-1}\tilde{A}_{i}^{2}}\bigg{)},$
(10)

where

$\displaystyle\tilde{A}_{i}=2\sum_{l=i}^{n-1}M_{l}\Delta_{\mathbf{F}}(P^{l-i})+\texttt{span}(f_{i}),\quad
i\in\\{0,\cdots,n-1\\}.$ (11)

Proof:  See Appendix A.2.

##  4 Comparison to Existing Results

In this section, we demonstrate the generalization power of our result by
recovering some notable Hoeffding’s inequality for Markov chains in the recent
literature. We focus our attention on the general state space setting, thus
excluding results obtained under finite state space settings. According to the
assumption on the Markov chains, we separate the existing Hoeffding-type
inequalities into three categories: (i) uniformly ergodic chains, (ii)
geometric ergodic chains, and (iii) non-irreducible chains. We start from the
strongest assumption (uniform ergodicity) and move toward more relaxed
assumptions. We demonstrate that our theory is a natural extension and
generalizes the previous results.

###  4.1 Ergodic Chains

Traditionally, the ergodicity of the Markov chain is defined with respect to
the total variation metric (TV). The TV metric can be written as IPM with
$\mathbb{M}_{1}(\mathbb{X})$ as its generator. For
$\mu,\nu\in\mathcal{P}(\mathcal{X})$,

$\displaystyle\textnormal{{TV}}(\mu,\nu)\coloneqq\sup_{E\in\mathcal{X}}|\mu(E)-\nu(E)|=\frac{1}{2}\sup_{f\in\mathbb{M}_{1}(\mathbb{X})}|\mu(f)-\nu(f)|.$
(12)

The definition of the TV metric indicates that it ranges between 0 and 1,
whereas IPM is between 0 and 2 by Definition 1. We say an irreducible,
aperiodic, and positive Markov kernel $P:\mathbb{X}\to\mathcal{X}$ is said to
be geometrically ergodic if it converges to its invariant distribution $\pi$
in the following sense. For $n\in\mathbb{N}$ and $x\in\mathbb{X}$, there exist
$\beta\in[0,1)$ and measurable function $\alpha:\mathbb{X}\to[0,\infty)$ with
$\pi(\alpha)<\infty$ such that

$\displaystyle\|P^{n}(x,\cdot)-\pi\|_{\textnormal{{TV}}}\leq\alpha(x)\beta^{n}.$
(13)

The Markov kernel $P$ is uniformly geometrically ergodic if
$\sup_{x\in\mathbb{X}}\alpha(x)$ is finite. Since uniform ergodicity implies
geometric ergodicity (Douc et al., 2018, Proposition 15.2.3), we refer to
uniform geometric ergodicity as uniform ergodicity in the sequel.

We start our discussion with uniformly ergodic Markov chains. We provide two
versions of Hoeffding inequality with this type of Markov chains in
Proposition 22 and 24. Proposition 22 assumes Doeblin’s condition (Assumption
1), and Proposition 24 poses requirements on the TV Dobrushin coefficient. For
aperiodic Markov chains, Doeblin’s condition (Assumption 1) is equivalent to
the uniform ergodicity of the Markov kernel $P$ (Meyn and Tweedie, 2012,
Theorem 16.0.2). Thus, the latter is more general as it allows
subgeometrically ergodic Markov chains. As an extension to the usual ergodic
condition, Hoeffding’s inequality under $V$-uniformly ergodicity (Definition
26) is studied in Douc et al. (2011) which we present in Proposition 27.
Instead of the TV metric, the $V$-total variation metric (Definition 25) is
used to measure the convergence. Additionally, Miasojedow (2014) and Fan et
al. (2021) view a Markov kernel as a bounded linear operator on $L^{2}(\pi)$
and study the Hoeffding-type inequalities under the $L^{2}(\pi)$-geometric
ergodicity. We summarize the result from Fan et al. (2021) in Proposition 30.
Additionally, certain periodic Markov chains can also satisfy Doeblin’s
condition. In fact, the extension of Hoeffding’s inequality to periodic Markov
chains was recently studied in Liu and Liu (2021) which we omit here as it is
similar in form to Glynn and Ormoneit (2002).

We demonstrate in this section that the aforementioned results fit into our
framework which allows easy interpolation and extension.

####  4.1.1 MC converging in TV Metric

In this section, we review the main result of Glynn and Ormoneit (2002) which
states a Hoeffding-type inequality for uniformly ergodic Markov chains. We
start by introducing Doeblin’s condition in Assumption 1 which is the main
assumption on Markov chains used by Glynn and Ormoneit (2002).

######  Assumption 1 (Doeblin’s Condition).

A Markov kernel $P$ is said to satisfy Doeblin’s condition if there exists a
probability measure $\phi$ on $\mathbb{X}$, $\lambda>0$, and a positive
integer $m\in\mathbb{Z}_{+}$ such that $P^{m}(x,\cdot)\geq\lambda\phi(\cdot)$
for all $x\in\mathbb{X}$.

Assumption 1 is also known as the minorization condition and $\phi$ is called
the minorization measure. It is closely related to the definition of a small
set (see Douc et al., 2018, Definition 9.1.1). If $P$ satisfies Assumption 1,
then the state space $\mathbb{X}$ is a ($m$, $\lambda\phi$)-small set and $P$
is $\phi$-irreducible. Theorem 16.2.4 in Meyn and Tweedie (2012) indicates
that Assumption 1 directly implies the geometric convergence of $P$ in TV
metric:

$\displaystyle\textnormal{{TV}}(P^{n}(x,\cdot)-\pi)\leq
2(1-\lambda\phi(E))^{\lfloor n/m\rfloor},$ (14)

for all $x\in E\subset\mathbb{X}$. Thus, under Assumption 1 the Markov chain
is uniformly ergodic, and the following proposition shows a Hoeffding-type
inequality for Markov chains as such.

######  Proposition 22 (Glynn and Ormoneit, 2002).

Suppose that the Markov chain $\\{X_{n}\\}_{n\in\mathbb{N}}$ with transition
kernel $P$ and invariant probability measure $\pi$ satisfies Assumption 1 and
let function $f:\mathbb{X}\to\mathbb{R}$, $f\in L^{\infty}(\mathbb{X})$. Let
$S_{n}=\sum_{i=0}^{n-1}f(X_{i})$, $u=(m+1)\|f\|_{\infty}/\lambda$, where $m$
and $\lambda$ are described in Assumption 1. Then, for any $\epsilon>0$ and
$\epsilon>u/n$, we have

$\mathbb{P}_{x}(|S_{n}-n\pi(f)|\geq n\epsilon)\leq
2\exp\left\\{-\frac{(n\epsilon-2u)^{2}}{2nu^{2}}\right\\}.$ (15)

######  Remark 23.

Suppose Assumption 1 is satisfied with $m=1$ and Equation 14 holds. If we take
$E=\mathbb{X}$ and denote $\Gamma_{\textnormal{{TV}}}$ as the convergence
constant under the TV metric, then we have, for all $x\in\mathbb{X}$,

$\displaystyle\Gamma_{\textnormal{{TV}}}$
$\displaystyle=\sum_{n=0}^{\infty}\textnormal{{TV}}(P^{n}(x,\cdot)-\pi)\leq\sum_{n=0}^{\infty}2(1-\lambda)^{n}=\frac{2}{\lambda}.$

We can see that $\Gamma_{\textnormal{{TV}}}<\infty$ as soon as $0<\lambda\leq
1$. Therefore, Theorem 13 holds with $\mathbf{F}=\mathbb{M}_{1}(\mathbb{X})$
and the resulting tail bound reads:

$\displaystyle\mathbb{P}_{\mu}[|S_{n}-n\pi(f)|>n\epsilon]\leq
2\exp\bigg{\\{}-\frac{2\\{n\epsilon-[2\|f\|_{\infty}/\lambda+\texttt{span}(f)]\\}^{2}}{n[2\|f\|_{\infty}/\lambda+\texttt{span}(f)]^{2}}\bigg{\\}},$
(16)

where $M$ and $\Gamma_{\mathbf{F}}$ in Equation 7 are replaced with
$\|f\|_{\infty}$ and $\Gamma_{\textnormal{{TV}}}=2/\lambda$, respectively.
Comparing Equation 15 to Equation 16, we can observe that

$\displaystyle\texttt{span}(f)\leq 2\|f\|_{\infty}/\lambda,$

due to $\lambda\leq 1$. Consequently, for
$\epsilon>n^{-1}(4\|f\|_{\infty}/\lambda)$, we have

$\displaystyle\exp\bigg{\\{}-\frac{2\\{n\epsilon-[2\|f\|_{\infty}/\lambda+\texttt{span}(f)]\\}^{2}}{n[2\|f\|_{\infty}/\lambda+\texttt{span}(f)]^{2}}\bigg{\\}}\leq\exp\bigg{\\{}-\frac{\\{n\epsilon-4\|f\|_{\infty}/\lambda\\}^{2}}{2n[2\|f\|_{\infty}/\lambda]^{2}}\bigg{\\}},$
(17)

and the right-hand side readily recovers the tail bound in Equation 15.
Equation 17 also shows our tail bound is tighter than Glynn and Ormoneit
(2002), especially when $\lambda$ is close to 0, i.e., when the convergence
rate is slow. This discrepancy is a result of different proof techniques used
to obtain the tail bounds. We refer readers to Appendix A.1 for details.

The following result found in Douc et al. (2018, Corollary 23.2.4) has an
alternative hypothesis that resembles ours in Theorem 21. Indeed, it can be
readily recovered by setting $\mathbf{F}=\mathbb{M}_{1}(\mathbb{X})$ in
Theorem 21.

######  Proposition 24 (Douc et al., 2018).

Suppose the Markov chain $\\{X_{n}\\}_{n\in\mathbb{N}}$ with transition kernel
$P$ admits an invariant probability measure $\pi$ is uniformly ergodic. Set

$\displaystyle\tilde{\Gamma}_{\textnormal{{TV}}}=\sum_{n=0}^{\infty}\Delta(P^{n})<\infty.$
(18)

Given $f\in\mathbb{M}_{1}(\mathbb{X})$ and $\texttt{span}(f)<\infty$. Let
$S_{n}=\sum_{i=0}^{n-1}f(X_{i})$. Then, for all
$\mu\in\mathcal{P}(\mathcal{X})$ and $\epsilon\geq
n^{-1}\textnormal{{TV}}(\mu,\pi)(1+\Gamma_{\textnormal{{TV}}})\texttt{span}(f)$,

$\displaystyle\mathbb{P}_{\mu}(|S_{n}-n\pi(f)|>n\epsilon)\leq
2\exp\bigg{\\{}-\frac{2n[\epsilon-n^{-1}\textnormal{{TV}}(\mu,\pi)(1+\Gamma_{\textnormal{{TV}}})\texttt{span}(f)]^{2}}{\texttt{span}(f)^{2}(1+\Gamma_{\textnormal{{TV}}})^{2}}\bigg{\\}}$
(19)

Our proof is largely inspired by the proof of Douc et al. (2018, Theorem
23.2.2), thus the constants in the exponent of our tail bound are identical to
theirs after setting $\mathbf{F}=\mathbb{M}_{1}(\mathbb{X})$. By Remark 23,
the tail bound in Equation 19 is tighter than that in Equation 15.

To conclude this section, we note that uniform ergodicity is known to be
rather strict for dynamic systems. We give two simple cases where Doeblin’s
condition (Assumption 1) can easily fail. Consider a deterministic stable
linear system (or an AR(1) process) on $\mathbb{X}$, $P^{m}(x,\cdot)$ and
$P^{m}(x^{\prime},\cdot)$ are Dirac measures with disjoint supports for any
$x\neq x^{\prime}\in\mathbb{X}$ and $m\in\mathbb{Z}_{+}$, thus the
minorization measure $\phi$ does not exist in this case. Suppose $\mathbb{X}$
is unbounded and the linear system is now perturbed by an additive noise
supported on the entire $\mathbb{X}$ (such as a Gaussian random variable). One
can readily verify that for any $x\neq x^{\prime}\in\mathbb{X}$ and
$m\in\mathbb{Z}_{+}$ the minorization measure for $P^{m}(x,\cdot)$ and
$P^{m}(x^{\prime},\cdot)$ converges to the trivial measure as
$\mathsf{d}(x,x^{\prime})\to\infty$. The exclusion of simple systems as such
leaves more to be desired, which motivates us to search for a more flexible
notion of convergence.

In fact, it is rather tedious to verify the uniform ergodicity for general
linear and nonlinear systems. See Meyn and Tweedie (2012, Chapter 7) for a
complete overview of the characterization of uniformly ergodic state-space
models. It is also available as a summary in Section III-C in Chen et al.
(2022).

####  4.1.2 MC converging in $V$-Norm

Hoeffding’s inequality for $V$-uniform ergodic Markov chains is presented in
Douc et al. (2011) and Douc et al. (2018, Chapter 23.3). It generalizes the TV
metric to $V$-total variation metric (Definition 25), which is an IPM with
$\mathbb{M}_{V}(\mathbb{X})$ as its generator. The resulting Hoeffding-type
inequality can be applied to $V$-geometrically ergodic Markov chains.

######  Definition 25 ($V$-TV Metric).

For probability measures $\mu,\nu\in\mathcal{P}_{V}(\mathcal{X})$ and function
$V:\mathbb{X}\to[1,+\infty)$, $V$-total variation metric is defined as

$\displaystyle\textnormal{{IPM}}_{V}(\mu,\nu)=\sup_{f\in\mathbb{M}_{V}}\bigg{|}\int
fd\mu-\int fd\nu\bigg{|},$

where $|\cdot|$ denotes the absolute value.

From the definition of the V-TV metric, we can see that for
$\mu,\nu\in\mathcal{P}_{V}(\mathcal{X})$,
$\textnormal{{TV}}(\mu,\nu)\leq\textnormal{{IPM}}_{V}(\mu,\nu)$. Thus,
convergence in $\textnormal{{IPM}}_{V}$ constitutes a stronger assumption of
the Markov chain than the TV metric.

######  Definition 26 ($V$-uniform ergodicity).

A Markov kernel $P$ is $V$-uniform ergodic if it possesses an invariant
distribution $\pi$ and there exists constant $R<\infty$ and $\beta\in[0,1)$
such that

$\displaystyle\textnormal{{IPM}}_{V}(P^{n}(x,\cdot),\pi)\leq RV(x)\beta^{n},$
(20)

for $\forall x\in\mathbb{X},\ \forall n\in\mathbb{N}$.

######  Proposition 27 (Douc et al., 2011).

Suppose the Markov chain $\\{X_{n}\\}_{n\geq 0}$ is $V$-uniform ergodic with
unique invariant probability distribution $\pi$ and initial distribution
$\eta$. Let $f:\mathbb{X}\to\mathbb{R}$ be a measurable function with
$\|f\|_{\infty}<\infty$ and $S_{n}=\sum_{i=0}^{n-1}f(X_{i})$. Then, for any
$\epsilon>0$ and initial distribution $\eta$, there exists a constant $K>0$
such that

$\displaystyle\mathbb{P}_{\eta}(|S_{n}-n\pi(f)|>n\epsilon)\leq
K\mathbb{E}_{\eta}[V]\exp\left[-\frac{1}{K}\left(\frac{n\epsilon^{2}}{\|f\|^{2}_{\infty}}\right)\wedge\frac{n\epsilon}{\|f\|_{\infty}}\right],$
(21)

where $V$ is defined in Definition 25.

######  Remark 28.

This tail bound is a hybrid between a Bernstein-type inequality and a
Hoeffding-type inequality. In the regime where $n\to\infty$, the exponential
term would be
$\exp\left[-\frac{1}{K}\left(\frac{n\epsilon^{2}}{\|f\|^{2}_{\infty}}\right)\right]$
which behaves more like a Hoeffding-type inequality. Although in this case,
the generator of $\textnormal{{IPM}}_{V}$ is $\mathbb{M}_{V}(\mathbb{X})$, the
functions applied to the Markov chain still belong to
$\mathbb{M}_{1}(\mathbb{X})$ which is a subset of $\mathbb{M}_{V}(\mathbb{X})$
for general choices of $V$ other than $V\equiv 1$. $\textnormal{{IPM}}_{V}$
chosen here is unnecessarily strong for the task. In fact, if one only
considers the bounded functions of Markov chains, it suffices to use an IPM as
strong as the TV metric.

####  4.1.3 MC converging in $L^{2}(\pi)$

In this section, we review a Hoeffding-type inequality obtained with spectral
methods for Markov chains. Markov transition kernels can be thought of as a
bounded linear operator on a functional space, such as
$L^{2}(\pi)=\\{f\in\mathbb{M}(\mathbb{X}):\|f\|_{L^{2}(\pi)}<\infty\\}$. One
can study the convergence behavior of Markov chains by looking at the spectrum
of the corresponding operator. For a comprehensive overview of spectral
methods for Markov chains, we advise interested readers to look at Douc et al.
(2018, Chapter 22). We only introduce the necessary facts to facilitate our
discussion in the sequel.

We start by introducing the definition of $L^{2}(\pi)$-absolute spectral gap.
Denote $\\{f\in L^{2}(\pi):\pi(f)=0\\}$ as $L^{2}_{0}(\pi)$.

######  Definition 29 (Douc et al., 2018).

Let $P$ be a Markov transition kernel with invariant probability $\pi$. The
transition kernel $P$ has an $L^{2}(\pi)$-absolute spectral gap if

$\displaystyle\textnormal{{Abs.Gap}}_{L^{2}(\pi)}(P)\coloneqq
1-\sup\\{|\lambda|:\lambda\in\textnormal{{Spec}}(P|L^{2}_{0}(\pi))\\}>0,$ (22)

where
$\sup\\{|\lambda|:\lambda\in\textnormal{{Spec}}(P|L^{2}_{0}(\pi))\\}=\lim_{m\to\infty}\sup\\{\|P^{m}g\|_{L^{2}(\pi)}:g\in
L^{2}_{0}(\pi),\|g\|_{L^{2}(\pi)}\leq 1\\}^{1/m}$.

Under the assumption that $P$ has a positive absolute spectral gap, Fan et al.
(2021) obtains a Hoeffding-type for bounded functions. We repeat their main
result in Proposition 30 for completeness.

######  Proposition 30 (Fan et al., 2021).

Let $\\{X_{n}\\}_{n\geq 0}$ be a Markov chain with invariant measure $\pi$ and
absolute spectral gap $1-\lambda>0$. For any $r\in\mathbb{R}$, uniformly for
all bounded functions $f_{i}:\mathbb{X}\to[a_{i},b_{i}]$, we have

$\displaystyle\mathbb{E}_{\pi}\bigg{[}e^{r[\sum_{i=1}^{n}f_{i}(X_{i})-\sum_{i=1}^{n}\pi(f_{i})]}\bigg{]}\leq\exp\bigg{(}\frac{1+\lambda}{1-\lambda}\sum_{i=1}^{n}\frac{(b_{i}-a_{i})^{2}r^{2}}{8}\bigg{)}.$
(23)

It follows that for any $\epsilon>0$,

$\displaystyle\mathbb{P}_{\pi}\bigg{(}\sum_{i=1}^{n}f_{i}(X_{i})-\sum_{i=1}^{n}\pi(f_{i})>n\epsilon\bigg{)}\leq\exp\bigg{(}-\frac{1-\lambda}{1+\lambda}\cdot\frac{2(n\epsilon)^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\bigg{)}$
(24)

######  Remark 31.

Notice that the initial distribution is required to be $\pi$. The authors
discussed it could be extended to all probability measures with ${L^{2}(\pi)}$
Radon-Nikodym derivative against $\pi$. In contrast, our framework and results
mentioned earlier do not have this restriction on the initial distribution.

To draw the connection with our framework, we need to further understand the
implications of the absolute spectral gap. By Proposition 22.2.4 in Douc et
al. (2018), having an $L^{2}(\pi)$-absolute spectral gap implies being
$L^{2}(\pi)$ geometrically ergodic which is defined formally as follows.
Denote the stationary transition kernel as
$\Lambda_{\pi}(x,\cdot)\coloneqq\pi(\cdot)$ and the unit ball in $L^{2}(\pi)$
as $\mathbf{F}_{L^{2}}\coloneqq\\{f\in L^{2}(\pi):\|f\|_{L^{2}(\pi)}\leq
1\\}$. With an abuse of notation, we write the $L^{2}(\pi)$-norm for a
probability measure as
$\|\mu\|_{L^{2}(\pi)}\coloneqq\|d\mu/d\pi\|_{L^{2}(\pi)}$ whenever $\mu$ in
dominated by $\pi$ and $\|\mu\|_{L^{2}(\pi)}=\infty$ otherwise. Denote the
space of probability measures with finite ${L^{2}(\pi)}$-norm as
$\mathcal{P}_{L^{2}(\pi)}(\mathcal{X})\coloneqq\\{\nu\in\mathcal{P}(\mathcal{X}):\|\nu\|_{L^{2}(\pi)}<\infty\\}$.

######  Definition 32 (Douc et al., 2018).

$P$ is said to be $L^{2}(\pi)$-geometrically ergodic if there exist
$\beta\in[0,1)$, a constant $\tilde{\alpha}(\mu)<\infty$, and for all
$\mu\in\mathcal{P}_{L^{2}(\pi)}(\mathcal{X})$ satisfying

$\displaystyle\|\mu P^{n}-\pi\|_{L^{2}(\pi)}\leq\tilde{\alpha}(\mu)\beta^{n},$
(25)

for $n\in\mathbb{N}$.

Let us consider the $L^{2}(\pi)$-IPM denoted as
$\textnormal{{IPM}}_{L^{2}(\pi)}$ with generator $\mathbf{F}_{L^{2}}$. A
geometric convergence in $\textnormal{{IPM}}_{L^{2}(\pi)}$ can be analogously
defined as follows.

######  Definition 33.

$P$ is said to be geometrically convergent in
$\textnormal{{IPM}}_{L^{2}(\pi)}$ if there exist $\beta\in[0,1)$, a constant
$\alpha(\mu)<\infty$, and for all
$\mu\in\mathcal{P}_{L^{2}(\pi)}(\mathcal{X})$ satisfying

$\displaystyle\textnormal{{IPM}}_{L^{2}(\pi)}(\mu
P^{n},\pi)=\sup_{f\in\mathbf{F}_{L^{2}(\pi)}}|\mu
P^{n}f-\pi(f)|\leq\alpha(\mu)\beta^{n},$ (26)

for $n\in\mathbb{N}$.

The following lemma establishes the equivalence between a geometric
convergence in $\textnormal{{IPM}}_{L^{2}(\pi)}$ and $L^{2}(\pi)$-geometric
ergodicity.

######  Lemma 34.

Suppose $P$ has invariant probability $\pi$. The following statements are
equivalent:

  1. 1.

$P$ is $L^{2}(\pi)$-geometrically ergodic;

  2. 2.

$P$ is geometrically convergent in $\textnormal{{IPM}}_{L^{2}(\pi)}$.

Proof:  Let $\mu\in\mathcal{P}_{L^{2}(\pi)}(\mathcal{X})$ be the initial
distribution. Let $g_{\mu}=d\mu/d\pi$ be the Radon–Nikodym derivative and
$g_{\mu}\in L^{2}(\pi)$. We write the inner product between $\mu$ and a real-
valued function $f$ in $L^{2}(\pi)$ as $\langle\mu,f\rangle=\int fd\mu=\int
fg_{\mu}d\pi=\langle g_{\mu},f\rangle_{{L^{2}(\pi)}}$.

It is easy to show that $\|\mu P\|_{L^{2}(\pi)}\leq\|\mu\|_{L^{2}(\pi)}$ (Douc
et al., 2018, Lemma 22.1.3). Thus, it follows $\mu P^{n}$ is dominated by
$\pi$ and $\|\mu P^{n}\|_{L^{2}(\pi)}\leq\|\mu\|_{L^{2}(\pi)}$ for
$n\in\mathbb{N}$. We can write $\textnormal{{IPM}}_{L^{2}(\pi)}$ using the
inner product form,

$\displaystyle\textnormal{{IPM}}_{L^{2}(\pi)}(\mu P^{n},\pi)$
$\displaystyle=\sup_{f\in\mathbf{F}_{L^{2}(\pi)}}|\langle\mu
P^{n},f\rangle-\langle\pi,f\rangle|=\sup_{f\in\mathbf{F}_{L^{2}(\pi)}}|\langle\mu
P^{n}-\pi,f\rangle|$ $\displaystyle=\|\mu P^{n}-\pi\|_{L^{2}(\pi)},$ (27)

where the last equality is due to Cauchy–Schwarz inequality and the equality
can be obtained with an appropriate choice of $f$ in
$\mathbf{F}_{L^{2}(\pi)}$.

It is obvious that the geometric convergence in
$\textnormal{{IPM}}_{L^{2}(\pi)}$ implies the following

$\displaystyle\Gamma_{L^{2}(\pi)}(\mu)\coloneqq\sum_{i=1}^{\infty}\textnormal{{IPM}}_{L^{2}(\pi)}(\mu
P^{i},\pi)<\infty,$ (28)

for $\mu\in\mathcal{P}_{L^{2}(\pi)}(\mathcal{X})$. Equation 28 depends on the
initial distribution $\mu$, thus being less demanding than Equation 5 used in
Theorem 9 which requires a uniform property across the state space
$\mathbb{X}$. Naturally, one would be skeptical if geometric convergence in
$\textnormal{{IPM}}_{L^{2}(\pi)}$ leads to the same conclusion as in Theorem 9
where the initial distribution is arbitrary. In the rest of this section,
however, we demonstrate a similar consequence (with restricted initial
distribution) to that of Proposition 30 using Equation 28. From previous
discussions, we can deduce $\Gamma_{L^{2}(\pi)}(\mu)<\infty$ is not stronger
than $\textnormal{{Abs.Gap}}_{L^{2}(\pi)}(P)>0$, which implies our framework
generalizes that of Fan et al. (2021).

$\textnormal{{Abs.Gap}}_{L^{2}(\pi)}(P)>0$$L^{2}(\pi)$-geometric ergodicity
${\exists m>1,\Delta_{L^{2}(\pi)}(P^{m})<1}$$\textnormal{{IPM}}_{L^{2}(\pi)}$
geometric convergence$\Gamma_{L^{2}(\pi)}(\mu)<\infty$ Figure 1: Relation
between the convergence concepts in Section 4.1.3.

It is also possible to define the IPM Dobrushin coefficient with
$\textnormal{{IPM}}_{L^{2}(\pi)}$ which we call the ${L^{2}(\pi)}$-Dobrushin
coefficient and is denoted as

$\displaystyle\Delta_{L^{2}(\pi)}(P)\coloneqq\sup\bigg{\\{}\textnormal{{IPM}}_{L^{2}(\pi)}(\xi
P,\xi^{\prime}P):\xi\neq\xi^{\prime}\in\mathcal{P}_{L^{2}(\pi)}(\mathcal{X}),\textnormal{{IPM}}_{L^{2}(\pi)}(\xi,\xi^{\prime})\leq
1\bigg{\\}}.$ (29)

We draw the connection between $\Delta_{L^{2}(\pi)}(P)$ and the operator norm
of $P$ on $L^{2}_{0}(\pi)$ in the following lemma. From there, one can readily
establish the connection with other convergence-related concepts introduced in
this section. To provide a holistic view, we summarize their relations in
Figure 1.

######  Lemma 35.

Let $\vvvert P\vvvert_{L^{2}_{0}(\pi)}\coloneqq\sup_{f\in
L^{2}_{0}(\pi)}\frac{\|Pf\|_{L^{2}(\pi)}}{\|f\|_{L^{2}(\pi)}}$ denote the
operator norm on $L^{2}_{0}(\pi)$. It holds that
$\Delta_{L^{2}(\pi)}(P)=\vvvert P\vvvert_{L^{2}_{0}(\pi)}$.

Proof:  Using Equation 4.1.3, we can deduce that

$\displaystyle\Delta_{L^{2}(\pi)}(P)=\sup\bigg{\\{}\|(\xi-\xi^{\prime})P\|_{L^{2}(\pi)}:\xi\neq\xi^{\prime}\in\mathcal{P}_{L^{2}(\pi)}(\mathcal{X}),\|\xi-\xi^{\prime}\|_{L^{2}(\pi)}\leq
1\bigg{\\}}.$

Since $\xi$ and $\xi^{\prime}$ are arbitrary positive measures in
$\mathcal{P}_{L^{2}(\pi)}(\mathcal{X})$, $\xi-\xi^{\prime}$ can be any signed
measure in $\mathcal{P}_{L^{2}(\pi)}(\mathcal{X})$ and
$\int\frac{d(\xi-\xi^{\prime})}{d\pi}d\pi=0$. Let $P^{*}$ be the adjoint
operator of $P$, i.e., $\langle Pf,g\rangle_{L^{2}(\pi)}=\langle
f,P^{*}g\rangle_{L^{2}(\pi)}$ for $f,g\in{L^{2}(\pi)}$. By Proposition 22.1.5
from Douc et al. (2018), we have the $\xi P=P^{*}(d\xi/d\pi)$. Thus, we can
deduce that

$\displaystyle\sup\bigg{\\{}\|(\xi-\xi^{\prime})P\|_{L^{2}(\pi)}:\xi\neq\xi^{\prime}\in\mathcal{P}_{L^{2}(\pi)}(\mathcal{X}),\|\xi-\xi^{\prime}\|_{L^{2}(\pi)}\leq
1\bigg{\\}}$ $\displaystyle=$
$\displaystyle\sup\bigg{\\{}\bigg{\|}P^{*}\frac{d\xi-d\xi^{\prime}}{d\pi}\bigg{\|}_{L^{2}(\pi)}:\xi\neq\xi^{\prime}\in\mathcal{P}_{L^{2}(\pi)}(\mathcal{X}),\bigg{\|}\frac{d(\xi-\xi^{\prime})}{d\pi}\bigg{\|}_{L^{2}(\pi)}\leq
1\bigg{\\}}$ $\displaystyle=$ $\displaystyle\vvvert
P^{*}\vvvert_{L^{2}_{0}(\pi)}=\vvvert P\vvvert_{L^{2}_{0}(\pi)},$

where the last equality is a result of combining Theorem 22.1.8 and Lemma
22.2.1 from Douc et al. (2018).

######  Remark 36.

Combining Douc et al. (2018, Proposition 22.2.4) and the above lemma, it
follows that $\textnormal{{Abs.Gap}}_{L^{2}(\pi)}(P)>0$ implies there exists
$m>1$ such that $\Delta_{L^{2}(\pi)}^{2}(P^{m})<1$ which further implies
${L^{2}(\pi)}$-geometric ergodicity.

Similar to Equation 9, we can write
$\tilde{\Gamma}_{L^{2}(\pi)}\coloneqq\sum_{i=0}^{\infty}\Delta_{L^{2}(\pi)}(P^{i})$.
It is worth noticing that $\textnormal{{Abs.Gap}}_{L^{2}(\pi)}(P)>0$ also
leads to $\tilde{\Gamma}_{L^{2}(\pi)}<\infty$ after realizing $\vvvert
P^{n}\vvvert_{L^{2}_{0}(\pi)}\leq\|P^{m}\|_{L^{2}_{0}(\pi)}^{\lfloor
n/m\rfloor}$, for $n\geq m$. By conditioning on
$\tilde{\Gamma}_{L^{2}(\pi)}<\infty$, it is possible to obtain a Hoeffding-
type inequality following the steps in the proof of Theorem 21. However, to
avoid repetitiveness, we conclude this section with the variant that uses
Equation 28 in the following corollary. The proof is omitted as it is a
special case of Theorem 21.

######  Corollary 37.

Let $\\{X_{n}\\}_{n\in\mathbb{N}}\subset\mathbb{X}$ be a Markov chain with
transition kernel $P:\mathbb{X}\times\mathcal{X}\to[0,1]$. For initial
distribution $\mu\in\mathcal{P}_{L^{2}(\pi)}(\mathcal{X})$, assume that the
Markov kernel $P$ admits a unique invariant probability measure $\pi$ such
that Equation 28 holds. For $i\in\\{0,\cdots,n-1\\}$ and $n\in\mathbb{Z}_{+}$,
given $f_{i}$ with bounded span and $f_{i}\in M_{i}\cdot\mathbf{F}$ with
minimal stretch $M_{i}=\|f_{i}\|_{L^{2}(\pi)}$. Let
$\tilde{S}_{n}\coloneqq\sum_{i=0}^{n-1}f_{i}(X_{i})$. Then, for
$\epsilon>n^{-1}[M_{1}^{\max}\Gamma_{L^{2}(\pi)}(\mu)+\texttt{span}(f_{0})]$,
we have

$\displaystyle\mathbb{P}_{\mu}\bigg{[}\bigg{|}\tilde{S}_{n}-\sum_{i=0}^{n-1}\pi(f_{i})\bigg{|}>n\epsilon\bigg{]}\leq
2\exp\bigg{(}-\frac{2\\{n\epsilon-[M_{1}^{\max}\Gamma_{L^{2}(\pi)}(\mu)+\texttt{span}(f_{0})]\\}^{2}}{\sum_{i=0}^{n-1}[M_{i+1}^{\max}\Gamma_{L^{2}(\pi)}(\mu)+\texttt{span}(f_{i})]^{2}}\bigg{)},$
(30)

where $M_{i}^{\max}=\max\\{M_{i},\cdots,M_{n-1}\\}$ for
$i\in\\{0,\cdots,n-1\\}$ and $M_{i}^{\max}=0$ for $i\geq n$.

###  4.2 Non-Ergodic MC

In this section, we discuss the Markov chains that are not covered by the
aforementioned ergodicity conditions, namely, non-irreducible chains and
periodic chains.

####  4.2.1 MC converging in Wasserstein metric

Hoeffding’s inequality for Markov chains converging in the Wasserstein metric
is studied in Sandrić and Šebek (2023) which we review in this section. Their
hypothesis includes certain non-irreducible chains. From the definition of the
small set and Doeblin’s condition, we can see that they enforce the
probability measure $P(x,\cdot)$ to be non-singular for $x$ in at least some
subset of the state space $\mathbb{X}$. Since small sets and Doeblin’s
condition play a central role in the ergodicity of Markov chains, one can make
the educated guess that the ergodicity may fail when $P(x,\cdot)$ is singular.
In fact, the real problem here is caused by the TV metric. For example, if we
consider two Dirac measures $\delta_{0}$ and $\delta_{1/n}$ for
$n\in\mathbb{Z}_{+}$, it is easy to see that $\delta_{1/n}$ does not converge
to $\delta_{0}$ in TV metric as $\textnormal{{TV}}(\delta_{1/n},\delta_{0})=1$
for all $n\in\mathbb{Z}_{+}$. Nevertheless, $\delta_{1/n}\to\delta_{0}$ in
some weaker sense which is to be specified later. This “incompatibility" with
singular measures raises problems when one tries to apply Markov chain theory
to deterministic systems or systems with discrete noise. The solution to the
issue is to consider weaker metrics that induce coarser topologies in the
space of probability measures. One of the notable alternatives researchers
have considered is the Wasserstein metric. For Polish space
$(\mathbb{X},\mathcal{X},\mathsf{d})$, define the Wasserstein-($p,\mathsf{d}$)
metric on $\mathcal{P}(\mathcal{X})$ as

$\displaystyle\textnormal{{W}}_{p,\mathsf{d}}(\mu,\nu)\coloneqq\bigg{[}\inf_{\Pi\in\mathcal{C}(\mu,\nu)}\int_{\mathbb{X}\times\mathbb{X}}\mathsf{d}(x,y)^{p}\Pi(dx,dy)\bigg{]}^{1/p},$
(31)

where $\mathcal{C}(\mu,\nu)$ denotes the family of couplings of $\mu$ and
$\nu$. For Wasserstein-1 metric in particular ($p=1$), it holds, by
Kantorovich-Rubinstein duality theorem Dudley (2018), that

$\displaystyle\textnormal{{W}}_{1,\mathsf{d}}(\mu,\nu)=\sup_{\\{f:\textnormal{{Lip}}(f)\leq
1\\}}\bigg{|}\int_{\mathbb{X}}fd\mu-\int_{\mathbb{X}}fd\nu\bigg{|},$ (32)

whenever the integrals are well-defined. Note that the presence of metric
$\mathsf{d}$ is contained in the Lipschitz condition of the witness function
$f$, i.e., $|f(x)-f(y)|\leq\textnormal{{Lip}}(f)\mathsf{d}(x,y)$, for
$x,y\in\mathbb{X}$. Sufficient conditions for geometric and subgeometric
convergence for Markov chains in Wasserstein-1 metric have been established in
Hairer et al. (2011) and Butkovsky (2014), respectively. We borrow the
following example from Butkovsky (2014) to illustrate the necessity of using
the Wasserstein metric.

######  Example 1 (Butkovsky, 2014).

Let $\boldsymbol{X}=\\{X_{n}\\}_{n\geq 0}$ be an autoregressive process
satisfying the following equation:

$\displaystyle X_{n+1}=\frac{1}{10}X_{n}+\epsilon_{n+1},$ (33)

where $\epsilon_{1},\epsilon_{2},\cdots$ are i.i.d. random variables uniformly
distributed on the set $\\{0,\frac{1}{10},\frac{2}{10},\cdots,\frac{9}{10}\\}$
and independent of $X_{0}$. $X_{0}$ is uniformly distributed on $[0,1)$. Then,
$\boldsymbol{X}$ is a Markov chain with state space
$(\mathbb{X},\mathcal{X})=([0,1),\mathcal{B}([0,1)))$ with a unique invariant
measure $\pi$ which is the uniform distribution on $[0,1)$. Let $d(x,y)=|x-y|$
be the metric on $\mathbb{X}$. One can show (Butkovsky, 2014) the following
facts:

  1. 1.

$\boldsymbol{X}$ converge to $\pi$ in Wasserstien-(1, $\mathsf{d}$) metric and
$\textnormal{{W}}_{1,\mathsf{d}}(P^{n}(x,\cdot),\pi(\cdot))\leq 10^{-n}$.

  2. 2.

$\textnormal{{TV}}(P^{n}(x,\cdot),\pi(\cdot))=1$ for $\forall n\in\mathbb{N}$.

  3. 3.

$\boldsymbol{X}$ is not $\psi$-irreducible. Consider $\mathbb{Q}\cap[0,1)$ and
$\mathbb{Q}^{c}\cap[0,1)$ which are disjoint and absorbing.

Since $\boldsymbol{X}$ is not ergodic in the usual sense, Proposition 22, 24,
27, and 30 cannot be used.

Along the same line, one can deduce that systems with stable dynamics and
additive discrete noise are excluded by the usual ergodicity condition as
well. To bridge this gap, Sandrić and Šebek (2023) has made a step in this
direction by giving a version of Hoeffding’s inequality for non-irreducible
Markov chains. We copy their theorem below for completeness.

######  Proposition 38 (Sandrić and Šebek, 2023).

Let $f:\mathbb{X}\to\mathbb{R}$ be bounded and Lipschitz continuous, and let
$S_{n}\coloneqq\sum_{i=0}^{n-1}f(X_{i})$ for $n\in\mathbb{Z}_{+}$. Assume that
$\\{X_{n}\\}_{n\geq 0}$ admits an invariant probability measure $\pi(dx)$ such
that

$\displaystyle\Gamma_{\textnormal{{W}}}\coloneqq\sup_{x\in\mathbb{X}}\sum_{n=1}^{\infty}\textnormal{{W}}(P^{n}(x,\cdot),\pi(\cdot))<\infty$
(34)

Then for any $\epsilon>2n^{-1}\textnormal{{Lip}}(f)\Gamma_{\textnormal{{W}}}$,

$\displaystyle\mathbb{P}_{x}[|S_{n}-n\pi(f)|>n\epsilon]\leq
2\exp\bigg{\\{}\frac{-(n\epsilon-2\textnormal{{Lip}}(f)\Gamma_{\textnormal{{W}}})^{2}}{8n(\textnormal{{Lip}}(f)\Gamma_{\textnormal{{W}}}+\|f\|_{\infty})^{2}}\bigg{\\}}$
(35)

######  Remark 39.

The term $\textnormal{{Lip}}(f)\Gamma_{\textnormal{{W}}}+\|f\|_{\infty}$ in
the denominator is not squared in the original statement of Sandrić and Šebek
(2023, Theorem 1). This term should be squared when Devroye et al. (2013,
Lemma 8.1) is applied but it is missing in their original proof.

With our framework, we present the following corollary which achieves the same
concentration result as in Proposition 38 but under a slightly more general
condition. We notice that Proposition 38 considers bounded Lipschitz functions
applied to the Markov chain, which indicates that the convergence in the
Wasserstein-1 metric is stronger than needed. As pointed out in Remark 10 and
28, the generator of the IPM should be large enough to cover the function of
interests and anything more is unnecessary. In this case, the appropriate IPM
generator is bounded Lipschitz functions which is smaller than that of
Wasserstein-1 metric, resulting in a weaker convergence requirement. Let
$\|\cdot\|_{\textnormal{{BL}}}$ denote the bounded Lipschitz norm and is given
by

$\displaystyle\|f\|_{\textnormal{{BL}}}=\max\bigg{\\{}\|f\|_{\infty},\textnormal{{Lip}}(f)\bigg{\\}}.$

Consider the generalized concentrability condition defined with the generator
$\mathbf{F}_{\textnormal{{BL}}}=\\{f\in\mathbb{M}(\mathbb{X}):\|f\|_{\textnormal{{BL}}}\leq
1\\}$. Let the IPM generated by $\mathbf{F}_{\textnormal{{BL}}}$ be denoted as
BL. We define $\Gamma_{\textnormal{{BL}}}$ using BL in a similar fashion as
Equation 5. The following corollary is given under the condition
$\Gamma_{\textnormal{{BL}}}<\infty$.

######  Corollary 40.

Let $\boldsymbol{X}=\\{X_{n}\\}_{n\in\mathbb{N}}\subset\mathbb{X}$ be a Markov
chain with transition kernel $P:\mathbb{X}\times\mathcal{X}$. Assume $P$
admits a unique invariant probability measure $\pi$ such that

$\displaystyle\Gamma_{\textnormal{{BL}}}\coloneqq\sup_{x\in\mathbb{X}}\sum_{i=0}^{\infty}\textnormal{{BL}}(P^{i}(x,\cdot),\pi)<\infty.$
(36)

Suppose $\boldsymbol{X}$ initializes with $\mu\in\mathcal{P}(\mathcal{X})$.
Consider a bounded Lipschitz continuous function $f:\mathbb{X}\to\mathbb{R}$
and $S_{n}=\sum_{i=0}^{n-1}f(X_{i})$ for $n\in\mathbb{Z}_{+}$. Then, for
$\epsilon>(2n)^{-1}\textnormal{{BL}}(\mu,\pi)[2\|f\|_{\textnormal{{BL}}}\Gamma_{\textnormal{{BL}}}+\texttt{span}(f)]$,
we have

$\displaystyle\mathbb{P}_{\mu}\bigg{[}\bigg{|}S_{n}-n\pi(f)\bigg{|}>n\epsilon\bigg{]}\leq
2\exp\bigg{(}-\frac{2[n\epsilon-\textnormal{{BL}}(\mu,\pi)[2\|f\|_{\textnormal{{BL}}}\Gamma_{\textnormal{{BL}}}+\texttt{span}(f)]/2]^{2}}{n[2\|f\|_{\textnormal{{BL}}}\Gamma_{\textnormal{{BL}}}+\texttt{span}(f)]^{2}}\bigg{)}.$
(37)

Proof:  This is a restatement of the main result using
$\mathbf{F}_{\textnormal{{BL}}}$.

######  Remark 41.

For any bounded Lipschitz function $f$, let $M$ be the minimal stretch of
$\mathbf{F}_{\textnormal{{BL}}}$ that includes $f$. Then,
$M=\|f\|_{\textnormal{{BL}}}$ and
$f\in\|f\|_{\textnormal{{BL}}}\cdot\Gamma_{\textnormal{{BL}}}$.

We apply Corollary 40 to obtain the sample complexity of Ployak-Ruppert
averaging of SGD in Section 5.2. The function of interest there is the
identity function on a compact space. Thus, it can be treated as a bounded
Lipschitz function.

####  4.2.2 Periodic Chains

A version of Hoefdding’s inequality for periodic Markov chains is given in Liu
and Liu (2021). The work is motivated by the observation that Markov chains
satisfying Doeblin’s condition in Assumption 1 are not necessarily aperiodic,
which indicates the uniform ergodicity condition used in Glynn and Ormoneit
(2002) can be relaxed. Since the key step in Glynn and Ormoneit (2002) is to
upper-bound the solution of the Poisson equation which is obtained via
Doeblin’s condition. The authors in Liu and Liu (2021) refine this argument by
directly bounding the solution of the Poisson equation in terms of the drift
condition and the ergodicity coefficient. We skip their results as it is
similar in form as Glynn and Ormoneit (2002).

##  5 Applications

In this section, we provide three application examples in machine learning to
demonstrate the utility of our theory.

###  5.1 Generalization Error Bound for Non-IID Samples

The assumption of i.i.d. samples is prevalent in machine learning literature.
In practice, the samples may not be independent. To relax the i.i.d.
assumption, samples drawn from mixing processes have been considered from the
perspective of empirical process theory (Yu, 1994), time series prediction
(Alquier and Wintenberger, 2012), online learning (Agarwal and Duchi, 2012),
empirical risk minimization (ERM) (Zou et al., 2009), etc. Stationary
processes are considered in the aforementioned papers except for Agarwal and
Duchi (2012) which considers asymptotically mixing processes, i.e. converging
to stationary distribution in a suitable sense.

In this section, we study the generalization error for online learning
algorithms with samples drawn from a Markov chain converging in general IPM.
Consider the following stochastic optimization problem

$\displaystyle\operatorname*{minimize}_{\theta\in\Theta}F(\theta)\coloneqq\mathbb{E}[f(u;\theta)],$
(38)

where $f:\mathcal{U}\times\Theta\to\mathbb{R}$ is the loss function depending
on the random sample $u\in\mathcal{U}$ and parameter $\theta\in\Theta$, and
the expectation is taken with respect to the distribution of $u$. Before
moving forward, we state the following assumptions.

######  Assumption 2.

  1. 1.

$f$ is uniformly bounded on $\mathcal{U}\times\Theta$.

  2. 2.

$f$ is strongly convex in $\theta$.

In practice, the objective in Equation 38 is approximated with the empirical
loss estimated from data. Suppose we have $N$ samples
$\\{u_{i}\\}_{i=1}^{N}\subset\mathcal{U}$. The empirical loss in Equation 38
is written as

$\displaystyle\operatorname*{minimize}_{\theta\in\Theta}\hat{F}(\theta)\coloneqq\frac{1}{N}\sum_{i=1}^{N}f(u_{i};\theta).$
(39)

Under appropriate assumption on $f$, both the original problem in Equation 38
and the approximated problem in Equation 39 have unique solutions, which are
denoted as $\theta^{*}$ and $\hat{\theta}$ respectively. In general, the
optimal solution $\theta^{*}$ and approximated solution $\hat{\theta}$ differ,
and one would like to bound the performance degradation caused by the
approximated solution. That is, finding an upper bound for
$|F(\hat{\theta})-F(\theta^{*})|$ which is referred to as the generalization
error bound. When the samples are i.i.d., the problem can be solved readily
using Hoeffding’s inequality for independent random variables (Hoeffding,
1994). Similarly, if we assume the samples $\\{u_{i}\\}_{i=1}^{N}$ follow a
Markov chain converging in some sense to be specified, then the generalization
error bound can be obtained by applying our version of Hoeffding’s inequality
for Markov chains.

######  Theorem 42.

Suppose Assumption 2 holds and $f\in M\cdot\mathbf{F}$ for $M\in(0,\infty)$
and $\mathbf{F}\subset\mathbb{M}_{1}$. Let $\\{u_{i}\\}_{i=1}^{\infty}$ be a
Markov chain converging in $\textnormal{{IPM}}_{\mathbf{F}}$ with constant
$\Gamma_{\mathbf{F}}$. For $\delta\in(0,1)$, the following holds with
probability at least $1-\delta$

$\displaystyle F(\hat{\theta})\leq
F(\theta^{*})+\frac{4M\Gamma_{\mathbf{F}}+2\texttt{span}(f)}{N}\bigg{(}1+\sqrt{\frac{N}{2}\log(\frac{1}{\delta})}\bigg{)}.$
(40)

Proof:  Since $\mathbf{F}\subset\mathbb{M}_{1}$, we can apply Theorem 21 to
$F(\hat{\theta})-\hat{F}(\hat{\theta})$,

$\displaystyle\mathbb{P}\\{F(\hat{\theta})-\hat{F}(\hat{\theta})<\epsilon\\}=$
$\displaystyle\mathbb{P}\bigg{\\{}\mathbb{E}_{\pi}f(u;\hat{\theta})-\frac{1}{N}\sum_{i=1}^{N}f(u_{i};\hat{\theta})<\epsilon\bigg{\\}}$
(41) $\displaystyle\geq$ $\displaystyle
1-\exp\bigg{\\{}-\frac{2\\{N\epsilon-[2M\Gamma_{\mathbf{F}}+\texttt{span}(f)]\\}^{2}}{N[2M\Gamma_{\mathbf{F}}+\texttt{span}(f)]^{2}}\bigg{\\}}.$
(42)

With probability at least $1-\delta$, we have

$\displaystyle F(\hat{\theta})$
$\displaystyle\leq\hat{F}(\hat{\theta})+\frac{2M\Gamma_{\mathbf{F}}+\texttt{span}(f)}{N}\bigg{(}1+\sqrt{\frac{N}{2}\log(\frac{1}{\delta})}\bigg{)}$
$\displaystyle\leq\hat{F}(\theta^{*})+\frac{2M\Gamma_{\mathbf{F}}+\texttt{span}(f)}{N}\bigg{(}1+\sqrt{\frac{N}{2}\log(\frac{1}{\delta})}\bigg{)},$
(43)

where the last inequality is due to $\theta^{*}$ being the minimizer of
$\hat{F}$. Applying Theorem 21 again to $\hat{F}(\theta^{*})-F(\theta^{*})$
yields

$\displaystyle\mathbb{P}\\{\hat{F}(\theta^{*})-F(\theta^{*})<\epsilon\\}=$
$\displaystyle\mathbb{P}\bigg{\\{}\frac{1}{N}\sum_{i=1}^{N}f(u_{i};\theta^{*})-\mathbb{E}_{\pi}f(u;\theta^{*})<\epsilon\bigg{\\}}$
(44) $\displaystyle\geq$ $\displaystyle
1-\exp\bigg{\\{}-\frac{2\\{N\epsilon-[2M\Gamma_{\mathbf{F}}+\texttt{span}(f)]\\}^{2}}{N[2M\Gamma_{\mathbf{F}}+\texttt{span}(f)]^{2}}\bigg{\\}}.$
(45)

With probability at least $1-\delta$, we have

$\displaystyle\hat{F}(\theta^{*})\leq
F(\theta^{*})+\frac{2M\Gamma_{\mathbf{F}}+\texttt{span}(f)}{N}\bigg{(}1+\sqrt{\frac{N}{2}\log(\frac{1}{\delta})}\bigg{)}.$
(46)

Combine Equation 43 and Equation 46, we have, with probability at least
$1-\delta$,

$\displaystyle F(\hat{\theta})\leq
F(\theta^{*})+\frac{4M\Gamma_{\mathbf{F}}+2\texttt{span}(f)}{N}\bigg{(}1+\sqrt{\frac{N}{2}\log(\frac{1}{\delta})}\bigg{)}.$
(47)

###  5.2 Ployak-Ruppert averaging for SGD

Stochastic recursive algorithms (RSA), including SGD, empirical value
iteration (EVI), etc., are widely used in optimization, stochastic
approximation, and machine learning. In Gupta et al. (2020), the authors model
the general form of RSAs with constant step size as a Markov chain and study
its convergence properties. In particular, the time average of the RSA
iterates is shown to have the variance reduction property given the Markov
chain induced by the RSA converges weakly to its invariant distribution (Gupta
et al., 2020). This result aligns well with the common acceleration technique
used in SGD and stochastic approximation (SA), namely Ployak-Ruppert averaging
(see Polyak and Juditsky, 1992; Ruppert, 1988; Nemirovski et al., 2009). In
the following example, we complement the existing study by demonstrating a
finite sample analysis of the Ployak-Ruppert averaging of the SGD algorithm.
For finite time convergence guarantees are derived for SGD-based algorithms
with constant step size, please refer to Dieuleveut et al. (2017); Bach and
Moulines (2013); Bach (2014).

We first introduce the necessary theoretic background on stochastic
contractive operators, then dive into a case study of the empirical risk
minimization (ERM) via SGD. Let us start with the contractive property for
deterministic operators on complete separable metric spaces. Let the Polish
space $\mathbb{X}$ be equipped with metric
$\mathsf{d}:\mathbb{X}\times\mathbb{X}\to[0,\infty)$. Let
$T:\mathbb{X}\to\mathbb{X}$ be a contraction operator with coefficient
$\alpha\in(0,1)$ and the unique fixed point $x^{*}\in\mathbb{X}$, i.e.,

$\displaystyle\mathsf{d}(T(x_{1}),T(x_{2}))\leq\alpha\mathsf{d}(x_{1},x_{2}),$
(48)

for all $x_{1},x_{2}\in\mathbb{X}$, and $T(x^{*})=x^{*}$. Given any starting
point $x_{0}\in\mathbb{X}$, recursively applying the operator $T$ generates a
sequence $(x_{k})_{k\in\mathbb{N}}$ where $x_{k+1}=T(x_{k})$ for
$k\in\mathbb{N}$. By Banach contraction mapping theorem Granas and Dugundji
(2003, Theorem 1.1),
$\mathsf{d}(x_{k},x^{*})\leq\alpha^{k}\mathsf{d}(x_{0},x^{*})$, thus $x_{k}\to
x^{*}$ geometrically fast as $k\to\infty$.

For stochastic operators, we need a few more notations. Let
$(\Omega,\mathcal{F},\mathbb{P})$ be a probability space where $\Omega$ is the
set of uncertainties, $\mathcal{F}$ is the Borel $\sigma$-algebra over
$\Omega$, and $\mathbb{P}$ is the base probability measure. Let
$\hat{T}^{n}_{k}:\mathbb{X}\times\Omega\to\mathbb{X}$ be a random operator
used at $k$-th iteration and indexed by $n\in\mathbb{N}$. This random operator
is used to model the approximation of the true operator $T$ carried out by
RSAs. In the case of SGD, $n$ is the number of samples (batch size) used to
estimate the gradient. In EVI, $n$ is the number of samples used to estimate
the expected cost-to-go. For simplicity of the presentation, we suppress the
dependence of $\hat{T}^{n}_{k}$ on $\omega\in\Omega$ and we write
$\hat{T}^{n}_{k}(x)\coloneqq\hat{T}^{n}_{k}(x,\omega)$. For each
$x\in\mathbb{X}$, $\hat{T}^{n}_{k}(x)$ is a random variable, and we make the
following independence assumption for random operators at a different time
step.

######  Assumption 3 (Gupta et al., 2020).

For each $x\in\mathbb{X}$, $\hat{T}^{n}_{k}(x)$ and
$\hat{T}^{n}_{k^{\prime}}(x)$ are independent and identically distributed
(i.i.d.) for $k\neq k^{\prime}$.

######  Assumption 4 (Diaconis and Freedman, 1999).

The following conditions are satisfied:

  1. 1.

$\mathbb{X}$ is a Polish space.

  2. 2.

There exists $a,b>0$ such that the operator $\hat{T}^{n}_{k}$ satisfy

$\displaystyle\mathbb{P}\bigg{\\{}\mathsf{d}\bigg{(}\hat{T}^{n}_{k}(z^{*}),z^{*}\bigg{)}>\epsilon\bigg{\\}}\leq\frac{a}{\epsilon^{b}},$
(49)

for all $\epsilon>0$ and $k\in\mathbb{N}$.

  3. 3.

Let $\hat{\alpha}^{n}_{k}$ denote the Lipschitz coefficient of
$\hat{T}_{k}^{n}$. Then, for all $k\in\mathbb{N}$,

$\displaystyle\mathbb{E}[\hat{\alpha}^{n}_{k}]<\infty,\quad\mathbb{E}[\log(\hat{\alpha}^{n}_{k})]<0.$
(50)

######  Lemma 43 (Diaconis and Freedman, 1999).

Suppose that Assumption 3 and 4 hold, then there exists a unique invariant
probability measure $\pi_{n}$ such that the distribution of $\hat{z}^{n}_{k}$
converges to $\pi_{n}$ in weak* topology.

Now, we look at a concrete machine learning example. Consider an empirical
risk minimization problem with the loss function
$l:\mathcal{U}\times\Theta\to\mathbb{R}$, where
$\mathcal{U}\subset\mathbb{R}^{d_{s}}$ is the sample space ,
$\Theta\subseteq\mathbb{R}^{d_{p}}$ is the parameter space. Suppose $\Theta$
is convex, equipped with the Euclidean metric $\|\cdot\|_{2}$, and has a
finite diameter. Let $\mathcal{D}=\\{u_{i}\\}_{i=1}^{N}\subset\mathcal{U}$ be
the training data set with i.i.d. samples. Let $l(u_{i},\theta)$ be the loss
associated with sample $u_{i}$ when the parameter is $\theta$. We formulate
the problem as follows:

$\displaystyle\operatorname*{minimize}_{\theta\in\Theta}F_{\mathcal{D}}(\theta)\coloneqq\frac{1}{N}\sum_{i=1}^{N}l(u_{i},\theta).$
(51)

We make the following assumptions before moving forward.

######  Assumption 5.

Suppose the following conditions hold:

  1. 1.

$l(u,\cdot)$ is twice-differentiable almost everywhere, for all
$u\in\mathcal{U}$.

  2. 2.

$\nabla_{\theta}l(u,\cdot)$ is Lipschitz continuous with constant $L>0$ for
all $u\in\mathcal{U}$, i.e.,

$\displaystyle\|\nabla_{\theta}l(u,\theta)-\nabla_{\theta}l(u,\theta^{\prime})\|_{2}\leq
L\|\theta-\theta^{\prime}\|_{2},\quad\text{for
}\forall\theta,\theta^{\prime}\in\Theta.$

  3. 3.

$l(u,\cdot)$ is strongly convex with modulus $\eta\in(0,L)$ for all
$u\in\mathcal{U}$, i.e.,

$\displaystyle\langle\nabla_{\theta}l(u,\theta)-\nabla_{\theta}l(u,\theta^{\prime}),\theta-\theta^{\prime}\rangle\geq\eta\|\theta-\theta^{\prime}\|_{2}^{2},\quad\text{for
}\forall\theta,\theta^{\prime}\in\Theta.$

  4. 4.

$\nabla_{\theta}l(u,\theta)$ is uniformly bounded function of
$u\in\mathcal{U}$ for all $\theta\in\Theta$.

  5. 5.

$\Theta\subset\mathbb{R}^{d_{p}}$ is compact.

As an immediate result, the problem in Equation 51 has a unique minimizer
$\theta^{*}\in\Theta$ and can be readily solved by the projected gradient
descent algorithm. The gradient of $F_{\mathcal{D}}$ is given by

$\displaystyle\nabla_{\theta}F_{\mathcal{D}}(\theta)=\frac{1}{N}\sum_{i=1}^{N}\nabla_{\theta}l(u_{i},\theta).$

The usual projected gradient descent algorithm approximates $\theta^{*}$ by
performing the following iterative operation $T:\Theta\to\Theta$. Given an
initial point $\theta_{0}\in\Theta$,

$\displaystyle\theta_{k+1}=T(\theta_{k})\coloneqq\textnormal{{Proj}}_{\Theta}\\{\theta_{k}-\beta\nabla_{\theta}F_{\mathcal{D}}(\theta_{k})\\}=\textnormal{{Proj}}_{\Theta}\bigg{\\{}\theta_{k}-\frac{\beta}{N}\sum_{i=1}^{N}\nabla_{\theta}l(u_{i},\theta_{k})\bigg{\\}},$
(52)

where $\beta\in(0,1/L]$ is the learning rate and
$\textnormal{{Proj}}_{\Theta}\\{\cdot\\}$ is the projection operator on to
$\Theta$. The following Lemma gives the fact that $T$ is a contraction with a
unique fixed point $\theta^{*}$.

######  Lemma 44.

Suppose Assumption 5 is satisfied. Then, $F_{\mathcal{D}}$ has unique
minimizer $\theta^{*}\in\mathbb{R}^{d_{p}}$. Given $\theta_{0}\in\Theta$ and
$\beta\in(0,2/L)$, $T$ is a contraction with coefficient
$\alpha_{T}=\max\\{|1-\beta\eta|,|1-\beta L|\\}$ and unique fixed point
$\theta^{*}$, and the sequence $(\theta_{k})_{k\in\mathbb{N}}$ generated by
Equation 52 converges geometrically,

$\displaystyle\|\theta_{k}-\theta^{*}\|_{2}\leq\alpha_{T}^{k}\|\theta_{0}-\theta^{*}\|_{2}.$
(53)

Proof:  $F_{\mathcal{D}}$ has a unique minimizer comes from the fact
$F_{\mathcal{D}}$ is continuous and strongly convex. To see $T$ is a
contraction, we first consider
$h(\theta)=F_{\mathcal{D}}(\theta)-\frac{\eta}{2}\|\theta\|_{2}^{2}$ which is
convex and with $(L-\eta)$-Lipschitz gradient. Due to the co-coercivity of
$\nabla_{\theta}h$, we have, for $\theta,\theta^{\prime}\in\Theta$,

$\displaystyle\langle\nabla_{\theta}F_{\mathcal{D}}(\theta)-\nabla_{\theta}F_{\mathcal{D}}(\theta^{\prime}),\theta-\theta^{\prime}\rangle\geq\frac{L\eta}{L+\eta}\|\theta-\theta^{\prime}\|^{2}_{2}+\frac{1}{\eta+L}\|\nabla_{\theta}F_{\mathcal{D}}(\theta)-\nabla_{\theta}F_{\mathcal{D}}(\theta^{\prime})\|_{2}^{2}.$
(54)

Now, we bound the different between $T(\theta)$ and $T(\theta^{\prime})$ using
Equation 54 and the nonexpansiveness of the projection operator,

$\displaystyle\|T(\theta)-T(\theta^{\prime})\|_{2}^{2}\leq\|(\theta-\theta^{\prime})-\beta(\nabla_{\theta}F_{\mathcal{D}}(\theta)-\nabla_{\theta}F_{\mathcal{D}}(\theta))\|^{2}_{2}$
$\displaystyle=$
$\displaystyle\|\theta-\theta^{\prime}\|_{2}^{2}+\beta^{2}\|\nabla_{\theta}F_{\mathcal{D}}(\theta)-\nabla_{\theta}F_{\mathcal{D}}(\theta)\|^{2}_{2}-2\beta\langle\nabla_{\theta}F_{\mathcal{D}}(\theta)-\nabla_{\theta}F_{\mathcal{D}}(\theta^{\prime}),\theta-\theta^{\prime}\rangle$
$\displaystyle\leq$
$\displaystyle\bigg{[}1-2\beta\bigg{(}\frac{L\eta}{L+\eta}\bigg{)}\bigg{]}\|\theta-\theta^{\prime}\|_{2}^{2}+\bigg{(}\beta^{2}-\frac{2\beta}{L+\eta}\bigg{)}\|\nabla_{\theta}F_{\mathcal{D}}(\theta)-\nabla_{\theta}F_{\mathcal{D}}(\theta)\|^{2}_{2}.$

Suppose $\beta\in(0,2/L)$, we consider the following two cases:

Case 1 $\beta\leq\frac{2}{L+\eta}$: in this case,
$\beta^{2}-\frac{2\beta}{L+\eta}\leq 0$, we replace
$\|\nabla_{\theta}F_{\mathcal{D}}(\theta)-\nabla_{\theta}F_{\mathcal{D}}(\theta)\|_{2}$
with its lower bound $\eta\|\theta-\theta^{\prime}\|_{2}$ which is a
consequence of the $\eta$-strong convexity. Then, we arrive at

$\displaystyle\|T(\theta)-T(\theta^{\prime})\|_{2}\leq(1-\beta\eta)\|\theta-\theta^{\prime}\|_{2},$

which indicates the contraction rate of $T$ is $1-\beta\eta$. One can check
$1-\beta\eta\geq|1-\beta L|$ when $\beta\in(0,\frac{2}{L+\eta})$ .

Case 2 $\beta\geq\frac{2}{L+\eta}$: in this case,
$\beta^{2}-\frac{2\beta}{L+\eta}\geq 0$, we replace
$\|\nabla_{\theta}F_{\mathcal{D}}(\theta)-\nabla_{\theta}F_{\mathcal{D}}(\theta)\|_{2}$
with its upper bound $L\|\theta-\theta^{\prime}\|_{2}$ which is a consequence
of having a $L$-Lipschitz gradient. Then, we arrive at

$\displaystyle\|T(\theta)-T(\theta^{\prime})\|_{2}\leq(\beta
L-1)\|\theta-\theta^{\prime}\|_{2},$

which indicates the contraction rate of $T$ is $(\beta L-1)$. One can check
$1-\beta\eta\geq|1-\beta L|$ when $\beta\in(\frac{2}{L+\eta},\frac{2}{L})$.

Combining the above two cases, we have that $T$ is a contraction with rate
$\alpha_{T}=\max\\{|1-\beta\eta|,|1-\beta L|\\}$ and $\beta\in(0,2/L)$ ensures
$\alpha_{T}<1$. By Banach contraction mapping theorem (Granas and Dugundji,
2003, Theorem 1.1), we arrive at the desired result after verifying
$T(\theta^{*})=\theta^{*}$.

In practice, the exact gradient descent in Equation 52 is replaced by the SGD
to reduce the computational complexity, especially when $N$ is large. At the
time $k$, the algorithm chooses a subset of $n$ samples
$\mathcal{N}_{k}\subset\\{1,\cdots,N\\}$ randomly and independently from
previous steps. The gradient at time $k$ is approximated with samples in
$\mathcal{N}_{k}$. Let $\hat{T}_{k}^{n}$ be the SGD operator, and we write the
update equation as

$\displaystyle\hat{\theta}^{n}_{k+1}=\hat{T}_{k}^{n}(\hat{\theta}^{n}_{k})\coloneqq\hat{\theta}_{k}^{n}-\frac{\beta}{n}\sum_{j\in\mathcal{N}_{k}}\nabla_{\theta}l(u_{j},\hat{\theta}^{n}_{k}),$

and
$\boldsymbol{\hat{\theta}}^{n}\coloneqq\\{\hat{\theta}^{n}_{k}\\}_{k\in\mathbb{N}}$
is in fact a Markov chain. Under some mild conditions, we show, in Lemma 46,
that $\boldsymbol{\hat{\theta}}^{n}$ admits a unique invariant distribution
$\pi_{n}$ and converges to $\pi_{n}$ weakly and in Wasserstein metric as
$k\to\infty$. Lemma 43 enables the weak convergence of
$\boldsymbol{\hat{\theta}}$, however, it remains to check that the random
operators $\\{\hat{T}^{n}_{k}\\}_{k\in\mathbb{N}}$ satisfy Assumption 4.

######  Lemma 45.

Under Assumption 5, $\\{\hat{T}^{n}_{k}\\}_{k\in\mathbb{N}}$ satisfies
Assumption 4

Proof:  Assumption 4 (1) is satisfied by Assumption 5 (5). Assumption 4 (2)
can be shown by applying Hoeffding’s inequality for bounded i.i.d. random
variables. Without loss of generality, we can pick the metric $\mathsf{d}$ in
Equation 49 to be $\|\cdot\|_{1}$ as the $\Theta$ has finite dimensions. Given
$\epsilon>0$ and $k\in\mathbb{N}$,

$\displaystyle\mathbb{P}\bigg{\\{}\bigg{\|}\hat{T}^{n}_{k}(\theta^{*})-\theta^{*}\bigg{\|}_{1}>\beta\epsilon\bigg{\\}}$
$\displaystyle=\mathbb{P}\bigg{\\{}\bigg{\|}\frac{1}{n}\sum_{j\in\mathcal{N}_{k}}\nabla_{\theta}l(u_{j},\theta^{*})\bigg{\|}_{1}>\epsilon\bigg{\\}}\stackrel{{\scriptstyle(a)}}{{\leq}}2d_{p}\exp\bigg{\\{}\frac{-n\epsilon^{2}}{\sigma}\bigg{\\}},$

where $(a)$ is due to Hoeffding (1994) and $\sigma\in(0,\infty)$ is a constant
related to the uniform norm of $\nabla_{\theta}l(\cdot,\theta)$.

Assumption 4 (3) can be established by Assumption 5 (1)(2)(3) which, together,
imply the fact that eigenvalues of $\nabla^{2}_{\theta\theta}l(u,\theta)$ fall
in the interval of $[\eta,L]$. By picking the appropriate learning rate
$\beta$, $\hat{T}^{n}_{k}$ is a contraction for every realization with
contraction rate $\hat{a}_{k}^{n}=\max\\{|1-\beta L|,|1-\beta\eta|\\}<1$.

Combining the results in Lemma 45 and 43, we can conclude
$\boldsymbol{\hat{\theta}}^{n}$ converges to $\pi_{n}$ weakly. Conveniently,
for metric spaces with bounded diameter, which is the case for $\Theta$,
Wasserstein-(1, $\|\cdot\|_{2}$) metrizes the weak topology (Gibbs and Su,
2002), i.e. weak convergence is equivalent to convergence in Wasserstein-(1,
$\|\cdot\|_{2}$). Using the fact that
$\tilde{\mathbf{F}}_{\textnormal{{BL}}}\subseteq\tilde{\mathbf{F}}_{\textnormal{{W}}}=\\{f\in\mathbb{M}(\Theta):\textnormal{{Lip}}(f)\leq
1\\}$, we can deduce that the bounded Lipschitz metric BL is bounded by
Wasserstein-(1, $\|\cdot\|_{2}$), and $\boldsymbol{\hat{\theta}}^{n}$ also
converges in BL. Therefore, it suffices to verify that
$\Gamma_{\textnormal{{W}}}$ is finite.

######  Lemma 46.

$\boldsymbol{\hat{\theta}}^{n}$ converges to its unique invariant distribution
$\pi_{n}$ in Wasserstein-(1, $\|\cdot\|_{2}$) with constant
$\Gamma_{\textnormal{{W}}}$ defined in Equation 36,

$\displaystyle\Gamma_{\textnormal{{W}}}=\sup_{\theta\in\Theta}\textnormal{{W}}_{1,\|\cdot\|_{2}}(\delta_{\theta},\pi_{n})\sum_{k=1}^{\infty}\prod_{i=0}^{k}\hat{\alpha}_{i}^{n}<\infty,$

where $\hat{\alpha}_{i}^{n}$ is the contraction coefficient of $T_{i}^{n}$ for
$i=0,1,2,\cdots$.

Proof:  Let $Q_{n}$ denote the transition kernel of
$\boldsymbol{\hat{\theta}}^{n}$. Consider two independent chains starting from
$\mu$ and $\nu$, respectively. The contraction in the Wasserstein metric from
time $k$ to $k+1$ is written as follows,

$\displaystyle\textnormal{{W}}_{1,\|\cdot\|_{2}}(\mu Q_{n}^{k+1},\nu
Q_{n}^{k+1})=$ $\displaystyle\inf_{\Pi\in\Pi(\mu P^{k},\nu
P^{k})}\int_{\Theta\times\Theta}\|\hat{T}^{n}_{k}(\theta)-\hat{T}^{n}_{k}(\theta^{\prime})\|_{2}d\Pi(\mu
Q_{n}^{k},\nu Q_{n}^{k})$ $\displaystyle\leq$
$\displaystyle\hat{\alpha}_{k}^{n}\inf_{\Pi\in\mathcal{C}(\mu Q_{n}^{k},\nu
Q_{n}^{k})}\int_{\Theta\times\Theta}\|\theta-\theta^{\prime}\|_{2}d\Pi(\mu
Q_{n}^{k},\nu Q_{n}^{k})$ $\displaystyle=$
$\displaystyle\hat{\alpha}_{k}^{n}\textnormal{{W}}_{1,\|\cdot\|_{2}}(\mu
Q_{n}^{k},\nu Q_{n}^{k}),$

for $k=0,1,2,\cdots$. Thus, $\\{\alpha_{k}^{n}\\}$ is also the contraction
coefficient of the $\boldsymbol{\hat{\theta}}$ in Wasserstein-(1,
$\|\cdot\|_{2}$). Consequently, we can deduce that

$\displaystyle\Gamma_{\textnormal{{W}}}$
$\displaystyle=\sup_{\theta\in\Theta}\sum_{k=0}^{\infty}\textnormal{{W}}_{1,\|\cdot\|_{2}}(Q_{n}^{k}(\theta,\cdot),\pi_{n})=\sup_{\theta\in\Theta}\sum_{k=0}^{\infty}\textnormal{{W}}_{1,\|\cdot\|_{2}}(\delta_{\theta}Q_{n}^{k},\pi_{n}Q_{n}^{k})$
$\displaystyle\leq\sup_{\theta\in\Theta}\sum_{i=0}^{\infty}\textnormal{{W}}_{1,\|\cdot\|_{2}}(\delta_{\theta},\pi_{n})\prod_{i=0}^{k}\hat{\alpha}_{i}^{n}.$

The proof is complete by noting $\hat{\alpha}_{i}^{n}<1$ for every
realization.

Combining Lemma 46 and the fact that
$\textnormal{{BL}}\leq\textnormal{{W}}_{1,\|\cdot\|_{2}}$ yields the following
corollary which states that $\Gamma_{\textnormal{{BL}}}$ defined in Equation
36 is also bounded. This completes our preparation for the main conclusion in
this example.

######  Corollary 47.

It holds that
$\Gamma_{\textnormal{{BL}}}\leq\Gamma_{\textnormal{{W}}}<\infty$.

With the above development, we are ready to present the main result of this
example. Corollary 47 allows us to apply Hoeffding’s inequality in Corollary
40 to determine the concentration of Ployak-Ruppert averaging. As a result, we
demonstrate the sample complexity bound for the averaged iterates in the
following theorem.

######  Theorem 48.

Let $\bar{\theta}^{n}_{m}=\frac{1}{m}\sum^{m-1}_{k=0}\hat{\theta}^{n}_{k}$ for
$m\geq 1$. Suppose the Markov chain $\boldsymbol{\hat{\theta}}^{n}$ converges
in Wasserstein-(1, $\|\cdot\|_{2}$) metric with constant
$\Gamma_{\textnormal{{BL}}}$. Given $\epsilon>0$ and $\delta\in(0,1)$, the
$\|\bar{\theta}^{n}_{m}-\mathbb{E}_{\pi_{n}}(\theta)\|_{2}<\epsilon$ holds
with probability at least $1-\delta$ whenever

$\displaystyle
m\geq\frac{d_{p}^{2}}{4\epsilon^{2}}\log\frac{2d_{p}}{\delta}\textnormal{{diam}}(\Theta)^{2}(2\Gamma_{\textnormal{{BL}}}+1)^{2},$
(55)

where $\textnormal{{diam}}(\Theta)<\infty$ is the diameter of the parameter
space $\Theta$ in $\|\cdot\|_{2}$.

Proof:  Let $f$ be the identity function on $\Theta$ and $\|\cdot\|_{1}$
denote the 1-norm on $\mathbb{R}^{d_{p}}$. We have
$\|\theta\|_{2}\leq\|\theta\|_{1}$ for all $\theta\in\mathbb{R}^{d_{p}}$,
which implies

$\displaystyle\|\bar{\theta}^{n}_{m}-\pi_{n}(f)\|_{2}=\bigg{\|}\frac{1}{m}\sum^{m-1}_{k=0}\hat{\theta}^{n}_{k}-\pi_{n}(f)\bigg{\|}_{2}$
$\displaystyle\leq$
$\displaystyle\bigg{\|}\frac{1}{m}\sum^{m-1}_{k=0}\hat{\theta}^{n}_{k}-\pi_{n}(f)\bigg{\|}_{1}=\sum_{i=1}^{d_{p}}\bigg{|}\frac{1}{m}\sum_{k=0}^{m-1}f_{i}(\hat{\theta}^{n}_{k})-\pi_{n}(f_{i})\bigg{|},$
(56)

where $f_{i}:\mathbb{R}^{d_{p}}\to\mathbb{R}$ maps a vector in
$\mathbb{R}^{d_{p}}$ to its $i$-th component for $i\in\\{1,\cdots,d_{p}\\}$.
For identity function $f$, it holds
$\|f_{i}\|_{\textnormal{{BL}}}=\max\\{\textnormal{{Lip}}(f_{i}),\|f_{i}\|_{\infty}\\}\leq\max\\{1,\textnormal{{diam}}(\Theta)/2\\}$.
Applying Equation 37 to each summand of the last term in Equation 5.2 yields

$\displaystyle\mathbb{P}_{\theta_{0}}\bigg{[}\bigg{|}\frac{1}{m}\sum_{k=0}^{m-1}f_{i}(\hat{\theta}^{n}_{k})-\pi_{n}(f_{i})\bigg{|}>\epsilon\bigg{]}\leq
2\exp\bigg{\\{}\frac{-2(m\epsilon-2\|f_{i}\|_{\textnormal{{BL}}}\Gamma_{\textnormal{{BL}}}-\texttt{span}(f_{i}))^{2}}{m(2\|f_{i}\|_{\textnormal{{BL}}}\Gamma_{\textnormal{{BL}}}+\texttt{span}(f_{i}))^{2}}\bigg{\\}},$
(57)

for $i\in\\{1,\cdots,d_{p}\\}$. After applying union bound, we have

$\displaystyle\mathbb{P}_{\theta_{0}}$
$\displaystyle\bigg{[}\sum_{i=1}^{d_{p}}\bigg{|}\frac{1}{m}\sum_{k=0}^{m-1}f_{i}(\hat{\theta}^{n}_{k})-\pi_{n}(f_{i})\bigg{|}>\epsilon\bigg{]}\leq\mathbb{P}_{\theta_{0}}\bigg{[}\bigcup_{i=1}^{d_{p}}\bigg{\\{}\bigg{|}\frac{1}{m}\sum_{k=0}^{m-1}f_{i}(\hat{\theta}^{n}_{k})-\pi_{n}(f_{i})\bigg{|}>\frac{\epsilon}{d_{p}}\bigg{\\}}\bigg{]}$
$\displaystyle\leq\sum_{i=1}^{m_{\theta}}\mathbb{P}_{\theta_{0}}\bigg{[}\bigg{|}\frac{1}{m}\sum_{k=0}^{m-1}f_{i}(\hat{\theta}^{n}_{k})-\pi_{n}(f_{i})\bigg{|}>\frac{\epsilon}{d_{p}}\bigg{]}$
$\displaystyle\leq
2d_{p}\exp\bigg{\\{}\frac{-2(m\epsilon/d_{p}-2\textnormal{{diam}}(\Theta)\Gamma_{\textnormal{{BL}}}-\max_{i\in\\{1,\cdots,d_{p}\\}}\|f_{i}\|_{\infty})^{2}}{m(2\textnormal{{diam}}(\Theta)\Gamma_{\textnormal{{BL}}}+\max_{i\in\\{1,\cdots,d_{p}\\}}\|f_{i}\|_{\infty})^{2}}\bigg{\\}}.$
(58)

Note that $f$ is the identity map, thus
$\max_{i\in\\{1,\cdots,d_{p}\\}}\|f_{i}\|_{\infty}=\sup_{\theta\in\Theta}\|\theta\|_{\infty}\leq\textnormal{{diam}}(\Theta)$.
Using the inequality in Equation 5.2, we conclude that

$\displaystyle\mathbb{P}_{\theta_{0}}[\|\bar{\theta}^{n}_{m}-\pi_{n}(f)\|_{2}>\epsilon]$
$\displaystyle\leq\mathbb{P}_{\theta_{0}}\bigg{[}\sum_{i=1}^{d_{p}}\bigg{|}\frac{1}{m}\sum_{k=0}^{m-1}f_{i}(\hat{\theta}^{n}_{k})-\pi_{n}(f_{i})\bigg{|}>\epsilon\bigg{]}$
$\displaystyle\leq
2d_{p}\exp\bigg{\\{}\frac{-2(m\epsilon/d_{p}-2\textnormal{{diam}}(\Theta)\Gamma_{\textnormal{{BL}}}-\textnormal{{diam}}(\Theta))^{2}}{m(2\textnormal{{diam}}(\Theta)\Gamma_{\textnormal{{BL}}}+\textnormal{{diam}}(\Theta))^{2}}\bigg{\\}}.$

By setting $\delta\geq
2d_{p}\exp\bigg{\\{}\frac{-2(m\epsilon/d_{p}-2\textnormal{{diam}}(\Theta)\Gamma_{\textnormal{{BL}}}-\textnormal{{diam}}(\Theta))^{2}}{m(2\textnormal{{diam}}(\Theta)\Gamma_{\textnormal{{BL}}}+\textnormal{{diam}}(\Theta))^{2}}\bigg{\\}}$
and solving for the lower bound of $m$, we have

$\displaystyle m$ $\displaystyle\geq\frac{-b+\sqrt{b^{2}-4ac}}{2a},\text{
where}$ $\displaystyle a=\frac{2\epsilon^{2}}{d_{p}^{2}},\ b$
$\displaystyle=-\log\frac{2d_{p}}{\delta}(2\textnormal{{diam}}(\Theta)\Gamma_{\textnormal{{BL}}}+\textnormal{{diam}}(\Theta))^{2}-4(2\textnormal{{diam}}(\Theta)\Gamma_{\textnormal{{BL}}}+\textnormal{{diam}}(\Theta))\frac{\epsilon}{d_{p}},$
$\displaystyle c$
$\displaystyle=2(2\textnormal{{diam}}(\Theta)\Gamma_{\textnormal{{BL}}}+\textnormal{{diam}}(\Theta)).$

For small $\epsilon$, $\delta$, and large $d_{p}$, $\Gamma_{\mathcal{W}}$,
$\textnormal{{diam}}(\Theta)$, we have

$\displaystyle
m\geq\frac{d_{p}^{2}}{4\epsilon^{2}}\log\frac{2d_{p}}{\delta}\textnormal{{diam}}(\Theta)^{2}(2\Gamma_{\textnormal{{BL}}}+1)^{2},$

which yields the desired result in Equation 55.

######  Remark 49.

So far we have discussed the concentration of averaged iterates around the
mean of $\pi_{n}$, where $n$ is the batch size. It is expected that as
$n\to\infty$ the mean of $\pi_{n}\to\theta^{*}$. Indeed, one can directly
apply Gupta et al. (2018, Theorem 2.2) to the current example to show
$\pi_{n}$ converges weakly to $\mathbbm{1}_{\theta^{*}}$ without additional
assumption other than Assumption 5.

###  5.3 Rested Bandit with UCB

In this section, we consider the finite sample analysis of the UCB-type policy
for the multi-arm bandit (MAB) with Markovian reward. Suppose $\mathbb{X}$ is
a Polish space. We assume the state of the $i$-th arm
$\\{X_{i,n}\\}_{n\in\mathbb{N}}\subset\mathbb{X}$ is an Markov chain with
transition kernel $P_{i}$, for $i\in\\{1,\cdots,K\\}$. The states of arms
evolve independently. The reward of the $i$-th arm is a non-negative function
of the state $r_{i}:\mathbb{X}\to[0,\infty)$. This is known as the rested or
restless bandit problem in the literature. The distinction between rested and
restless bandits is that the Markov chain associated with an arm in the former
evolves only when the arm is pulled, whereas the Markov chains in the latter
evolve regardless of which arm is pulled at each time step. Since the purpose
of this example is to demonstrate the usage of Hoeffding’s inequality in the
analysis of the regret bound, we opt for the classical UCB-type policy for the
sake of simplicity. For finite state space and uniform ergodic Markov chains,
the UCB-type policy for both rested and restless bandits is studied in Tekin
and Liu (2012). We restate their UCB-M algorithm for rested bandit in
Algorithm 1 for completeness.

With our theory, the regret analysis can be readily extended to general state
space Markov chains with weaker convergence requirements. The logarithmic
regret bound is presented in Theorem 54. Before presenting the regret
analysis, we make the following further assumptions for the state process and
reward function of each arm.

######  Assumption 6.

For each arm $i$, suppose there exist a measurable function
$V_{i}:\mathbb{X}\to[1,\infty)$ such that the following condition holds:

  1. 1.

There exists a differentiable concave increasing function
$\phi_{i}:\mathbb{R}_{+}\to\mathbb{R}_{+}$, $\phi_{i}(0)=0$ and a constant
$b_{i}\geq 0$ such that the following drift condition holds with Lyapunov
function $V_{i}$,

$\displaystyle P_{i}V_{i}\leq V_{i}-\phi_{i}\circ V_{i}+b_{i}.$

  2. 2.

The Markov chain $\\{X_{i}(n)\\}_{n\in\mathbb{N}}$ induced by transition
kernel $P_{i}$ converges to its unique stationary distribution $\pi_{i}$ in
IPM with generator $\mathbf{F}_{i}\subset\mathbb{M}_{1}(\mathbb{X})$ and
constant $\Gamma_{\mathbf{F}_{i}}$.

######  Assumption 7.

For $i\in\\{1,\cdots,K\\}$, the reward function $r_{i}\in
R_{i}\cdot\mathbf{F}_{i}$ for $R_{i}<\infty$. Denote
$R_{\max}=\max\\{R_{1},\cdots,R_{K}\\}$ and
$R_{\min}=\min\\{R_{1},\cdots,R_{K}\\}$

######  Remark 50.

Assumption 6 (1) comes from Butkovsky (2014, Theorem 2.1) which shows a set of
sufficient conditions for convergence of Markov chains in Wasserstein-(1,
$\mathsf{d}$) metric with subgeometric rate. Assumption 6 (1) is known as the
drift condition for subgeometric convergence. It becomes the drift condition
for geometric convergence when $\phi_{i}$ is a linear function. Assumption 6
(1) turns out to be a crucial component in the proof of Lemma 51.

For Markov chains converging in TV metric, necessary and sufficient conditions
exist for both geometric and subgeometric rate (Douc et al., 2018). For Markov
chains converging in the Wasserstein metric, sufficient conditions have been
proposed for both geometric rate (Hairer et al., 2011) and subgeometric rate
(Butkovsky, 2014). To the best of our knowledge, sufficient conditions for
Markov chains converging in general IPM is still an open problem. The drift
condition seems to be the common requirement for convergence in TV metric and
Wasserstein metric, and they only differ in the definition of the small set
(or $d$-small set in the case of Wasserstein-(1, $d$) metric). We only
speculate here that the convergence in general IPM requires a new definition
of “small set".

We introduce the following notations which are used in the sequel.

  * •

$X_{i}(n)$ is the state of arm $i$ at time $n$.

  * •

$\mu_{i}$ is the initial distribution of the state process of arm $i$.

  * •

$A(n)$ is the set of selected arms at time $n$.

  * •

$T_{i}(n)$ is the number of time arm $i$ pulled up to time $n$.

  * •

$\bar{r}_{i}(n)=(1/n)\sum_{t=1}^{n}r_{i}(X_{i}(t))$ is the (sample) average
reward for arm $i$ after $n$ pulls.

  * •

$h_{i}(n)$ is the UCB index of arm $i$ at time $n$.

  * •

$\eta_{i}=\pi_{i}(r_{i})$ is the expected reward of arm $i$ under stationary
distribution $\pi_{i}$.

  * •

$L$ is the exploration parameter for the UCB policy.

  * •

$M$ number of arms pulled per time step, $M\in\\{1,\cdots,K-1\\}$.

Suppose the arms are ordered by their expected rewards in decreasing order,
that is,
$\eta_{1}\geq\eta_{2}\geq\cdots\geq\eta_{M}\geq\eta_{M+1}\geq\cdots\geq\eta_{K}$.
The equality between $\eta_{M}$ and $\eta_{M+1}$ is allowed under the rested-
arm assumption, whereas a strict inequality is required for restless bandits
(Tekin and Liu, 2012). The regret $\mathcal{R}(n)$ is defined as the
difference in the expected total reward up to time $n$ between playing the
first $M$ arms only and playing according to some policy that determines the
selected arms $A(n)$. Formally, we have

$\displaystyle\mathcal{R}(n)=n\sum_{j=1}^{M}\eta_{j}-\mathbb{E}\bigg{[}\sum_{t=1}^{n}\sum_{i\in
A(t)}r_{i}(X_{i}(t))\bigg{]}.$

The goal of this application example is to show that regret is order-optimal
under the UCB-M policy. Before presenting the regret bound in Theorem 54, we
introduce the supporting results in Lemma 51, 52, and 53.

input: exploration constant $L$;

1 Play each arm $M$ time in the first $K$ time steps;

2 while  _$n\geq K$_ do

3 foreach  _$i\in\\{1,\cdots,K\\}$_ do

4 Calculate index: $h_{i}(n)=\bar{r}_{i}(T_{i}(n))+\sqrt{\frac{L\log
n}{T_{i}(n)}}$;

5

6 end foreach

7 Play $M$ arms with highest indices;

8 Observe $R_{i,n+1}$ and calculate $T_{i}(n+1)$ for $\forall
i\in\\{1,\cdots,K\\}$;

9 $n\leftarrow n+1$;

10

11 end while

Algorithm 1 UCB-M for rested bandit

Lemma 51 is a modification of Moustakides (1999, Theorem 2.1). The original
assumption is that the Markov chain is geometrically convergent in TV metric
which implies the drift condition is satisfied (Moustakides, 1999, Theorem
1.1). We replace that with Assumption 6 (1) and obtain the following Lemma.
Lemma 52 gives an upper bound on the average of times the optimal arm is
missed by the UCB-M policy. It is an adaption of Tekin and Liu (2012, Lemma 7)
using the Hoeffding-type inequality from Theorem 13. Building on top of Lemma
52, Lemma 53 further upper-bounds the expected number of times each suboptimal
arm is pulled. Combining Lemma 51 and 53, we are able to deduce the
logarithmic regret bound in Theorem 54.

######  Lemma 51.

Suppose Assumption 7 and 6 are satisfied and
$\mathbb{E}V_{i}(X_{i}(0))<\infty$ where the expectation is taken with respect
to initial distribution $\mu_{i}$, then for any stopping time $\tau$ such that
$\mathbb{E}\tau<\infty$, we have

$\displaystyle\sum_{n=1}^{\tau}r_{i}(X_{i}(n))-\eta_{i}\mathbb{E}\tau=\mathbb{E}g_{i}(X_{i}(0))-\mathbb{E}g_{i}(X_{i}(N)),$

where

$\displaystyle
g_{i}(x)=\sum_{n=1}^{\infty}\bigg{[}\mathbb{E}_{x}[r_{i}(X_{n})]-\pi_{i}(r_{i})\bigg{]}$

is the solution to $g_{i}(x)-P_{i}g_{i}(x)=r_{i}(x)-\pi_{i}(f_{i})$ which is
the Poisson’s equation associated with transition kernel $P_{i}$.

Proof:  From Assumption 6 (1), we have

$\displaystyle P_{i}V_{i}\leq V_{i}-\phi_{i}\circ V_{i}+b_{i}.$ (59)

Since $\phi_{i}$ is differentiable and concave on $\mathbb{R}_{+}$, its
derivative $\phi_{i}^{\prime}$ is non-increasing and has no simple
discontinuity in any closed interval in $\mathbb{R}_{+}$. However, monotonic
functions have no discontinuities of the second kind. Thus, it follows that
$\phi_{i}^{\prime}$ is a continuous function on $\mathbb{R}_{+}$. Suppose
$\phi_{i}^{\prime}(x)\neq 0$ for $x\in\mathbb{R}_{+}$, $\phi$ is invertible on
$\mathbb{R}_{+}$ by inverse function theorem, and $\phi_{i}^{-1}$ is a convex
function. Applying $\phi_{i}^{-1}$ to both sides of Equation 59 and Jensen’s
inequality to the right-hand side, we have

$\displaystyle P_{i}(\phi_{i}^{-1}\circ V_{i})\leq\phi_{i}^{-1}\circ
V_{i}-V_{i}+\phi_{i}^{-1}(b_{i}).$ (60)

For any function $f\in\mathbb{M}_{V_{i}}(\mathbb{X})$, i.e.
$\|f\|_{V_{i}}=\sup_{x\in\mathbb{X}}|f(x)/V_{i}(x)|<\infty$, and any stopping
time $\tau$, we can apply Proposition 11.3.2 from Meyn and Tweedie (2012) with
$Z_{k}=\|f\|_{V_{i}}\phi_{i}^{-1}\circ V_{i}(X_{i}(k))$, $f_{k}(x)=|f(x)|$ and
$s_{k}(x)=\|f\|_{V_{i}}\phi_{i}^{-1}(K_{i})$ and get

$\displaystyle\mathbb{E}\bigg{[}\sum_{n=0}^{\tau-1}|f(X_{i}(n))|\bigg{]}\leq\|f\|_{V_{i}}\bigg{(}\mathbb{E}[\phi_{i}^{-1}\circ
V_{i}(X_{i}(0))]+\phi_{i}^{-1}(b_{i})\mathbb{E}\tau\bigg{)}.$ (61)

Since $r_{i}$ is bounded by Assumption 7,
$\|r_{i}\|_{V_{i}}\leq\|r_{i}\|_{\infty}<\infty$ and we replace $f$ with
$r_{i}$ in Equation 61. Then, the desired result follows the proof of Theorem
2.1 from Moustakides (1999) and the fact that we assume $r_{i}$ is bounded and
$\mathbb{E}V_{i}(X_{i}(0))<\infty$.

######  Lemma 52.

Suppose Assumption 6 holds and all arms are rested. Under UCB-M algorithm with
constant
$L\geq(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))^{2}\vee(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{j}))^{2}(1/\sqrt{\log
K}+2\sqrt{2})^{2}$, for any suboptimal arm $i\in\\{M+1,\cdots,K\\}$ and
optimal arm $j\in\\{1,\cdots,M\\}$, we have

$\displaystyle\mathbb{E}\bigg{[}\sum_{t=K+1}^{n}\sum_{s=1}^{t-1}\sum_{s_{i}=l}^{t-1}\mathbbm{1}\\{h_{j}(s)\leq
h_{i}(s_{i})\\}\bigg{]}\leq 2\sum_{t=1}^{n}t^{-2},$ (62)

where $l=\left\lceil\frac{4L\log n}{(\eta_{M}-\eta_{i})^{2}}\right\rceil$.

Proof:  Let $c_{t,s}=\sqrt{(L\log t)/s}$ and observe that the event
$\\{h_{j,s}\leq h_{i,s_{i}}\\}$ implies that at least one of the following
must hold

$\displaystyle\bar{r}_{j}(s)$ $\displaystyle\leq\eta_{j}-c_{t,s}$ (63)
$\displaystyle\bar{r}_{i}(s_{i})$ $\displaystyle\geq\eta_{i}+c_{t,s_{i}}$ (64)
$\displaystyle\eta_{j}$ $\displaystyle<\eta_{i}+2c_{t,s_{i}}.$ (65)

We bound the probability of events Equation 63 and Equation 64 using Theorem
13,

$\displaystyle\mathbb{P}\\{\bar{r}_{j}(s)\leq\eta_{j}-c_{t,s}\\}$
$\displaystyle=\mathbb{P}\bigg{\\{}\frac{1}{s}\sum_{t=1}^{s}r_{j}(t)\leq\mathbb{E}_{\pi}r_{j}-c_{t,s}\bigg{\\}}\leq\exp\bigg{(}\frac{-2(sc_{t,s}-(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{j})))^{2}}{s(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{j}))^{2}}\bigg{)}$
$\displaystyle\leq\exp\bigg{(}\frac{-2[\sqrt{L\log
t}-(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{i}))/\sqrt{s}]^{2}}{(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{j}))^{2}}\bigg{)},$
(66) $\displaystyle\mathbb{P}\\{\bar{r}_{i}(s_{i})\geq\eta_{i}+c_{t,s_{i}}\\}$
$\displaystyle=\mathbb{P}\bigg{\\{}\frac{1}{s_{i}}\sum_{t=1}^{s_{i}}r_{i}(t)\geq\mathbb{E}_{\pi}r_{i}+c_{t,s_{i}}\bigg{\\}}\leq\exp\bigg{(}\frac{-2(s_{i}c_{t,s_{i}}-(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i})))^{2}}{s_{i}(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))^{2}}\bigg{)}$
$\displaystyle\leq\exp\bigg{(}\frac{-2[\sqrt{L\log
t}-(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))/\sqrt{s_{i}}]^{2}}{(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))^{2}}\bigg{)}.$
(67)

If we choose $s_{i}\geq(4L\log n)/(\eta_{M}-\eta_{i})^{2}$, then

$\displaystyle 2c_{t,s_{i}}=2\sqrt{\frac{L\log t}{s_{i}}}\leq
2\sqrt{\frac{L\log t(\eta_{M}-\eta_{i})^{2}}{4L\log
n}}\leq\eta_{j}-\eta_{i}\quad\text{for }t\leq n,$ (68)

which indicates event Equation 65 never occurs. Combining Equation 66 and
Equation 67, we obtain the desired result by choosing an appropriate
$L\geq(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))^{2}\vee(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{j}))^{2}(1/\sqrt{\log
K}+2\sqrt{2})^{2}$,

$\displaystyle\mathbb{E}$
$\displaystyle\bigg{[}\sum_{t=K+1}^{n}\sum_{s=1}^{t-1}\sum_{s_{i}=l}^{t-1}\mathbbm{1}\\{h_{j}(s)\leq
h_{i}(s_{i})\\}\bigg{]}$ (69) $\displaystyle\leq
2\sum_{t=K+1}^{n}t^{2}\exp\bigg{(}\frac{-2[\sqrt{L\log
t}-[(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))/\sqrt{s_{i}}\vee(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{j}))/\sqrt{s}]]^{2}}{(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))^{2}\vee(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{j}))^{2}}\bigg{)}$
$\displaystyle\leq 2\sum_{t=K+1}^{n}t^{2}\exp\bigg{(}\frac{-2\log
t[\sqrt{L}-[(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))/\sqrt{s_{i}\log
t}\vee(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{j}))/\sqrt{s\log
t}]]^{2}}{(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))^{2}\vee(R_{j}\Gamma_{\mathbf{F}_{j}}+\texttt{span}(r_{j}))^{2}}\bigg{)}$
$\displaystyle\leq 2\sum_{t=K+1}^{n}t^{2}\exp(\log t^{-4})\leq
2\sum_{t=K+1}^{n}t^{-2}.$

######  Lemma 53.

Suppose Assumption 6 holds and all arms are rested. Under UCB-M algorithm
(Algorithm 1) with exploration constant
$L\geq\max_{i\in\\{1,\cdots,K\\}}\\{(R_{i}\Gamma_{\mathbf{F}_{i}}+\texttt{span}(r_{i}))^{2}\\}(1/\sqrt{\log
K}+2\sqrt{2})^{2}$, for any suboptimal arm $i$, we have

$\displaystyle\mathbb{E}[T^{i}(n)]\leq(1+2\beta)M+\frac{4L\log
n}{(\eta_{M}-\eta_{i})^{2}},$ (70)

where $\beta=\sum_{t=1}^{\infty}t^{-2}$.

Proof:  For any arm $i$, we upper bound $T_{i}(n)$ on any sequence of plays.
Let $l$ be an arbitrary positive integer.

$\displaystyle T_{i}(n)$ $\displaystyle=M+\sum_{t=K+1}^{n}\mathbbm{1}\\{i\in
A(t)\\}\leq M-1+l+\sum_{t=K+1}^{n}\mathbbm{1}\\{i\in A(t),\ T_{i}(t-1)\geq
l\\}$ (71)

Consider the event

$\displaystyle E_{i}$ $\displaystyle=\bigcup_{j=1}^{M}\bigg{\\{}h_{j}(n)\leq
h_{i}(n)\bigg{\\}},$ $\displaystyle E_{i}^{C}$
$\displaystyle=\bigcap_{j=1}^{M}\bigg{\\{}h_{j}(n)>h_{i}(n)\bigg{\\}}.$

If $E^{C}_{i}$ occurs then $i\notin A(t)$. Thus, $\\{i\in A(t)\\}\subset
E_{i}$ and

$\displaystyle\mathbbm{1}\\{i\in A(t),\ T_{i}(t-1)\geq l\\}$
$\displaystyle\leq\mathbbm{1}\\{E_{i},\ T_{i}(t-1)\geq l\\}$
$\displaystyle\leq\sum_{j=1}^{M}\mathbbm{1}\\{h_{j}(n)\leq h_{i}(n),\
T_{i}(t-1)\geq l\\}$ (72)

Plug Equation 5.3 into Equation 71, we have

$\displaystyle T_{i}(n)$ $\displaystyle\leq
M-1+l+\sum_{j=1}^{M}\sum_{t=K+1}^{n}\mathbbm{1}\\{h_{j}(n)\leq h_{i}(n),\
T_{i}(t-1)\geq l\\}$ $\displaystyle\leq
M-1+l+\sum_{j=1}^{M}\sum_{t=K+1}^{n}\mathbbm{1}\bigg{\\{}\min_{0<s<t}h_{j}(s)\leq\max_{l\leq
s_{i}\leq t}h_{i}(s_{i})\bigg{\\}}$ $\displaystyle\leq
M-1+l+\sum_{j=1}^{M}\sum_{t=K+1}^{n}\sum_{s=1}^{t-1}\sum_{s_{i}=l}^{t-1}\mathbbm{1}\\{h_{j}(s)\leq
h_{j}(s_{i})\\}.$ (73)

Using Lemma 52 with $l=\left\lceil\frac{4L\log
n}{(\eta_{M}-\eta_{i})^{2}}\right\rceil$, we have for any suboptimal arm $i$,

$\displaystyle\mathbb{E}[T_{i}(n)]\leq M+\frac{4L\log
n}{(\eta_{M}-\eta_{i})^{2}}+2M\sum_{t=1}^{\infty}t^{-2}.$ (74)

We conclude this example with the following regret bound for rested Markovian
bandits under the generalized concentrability condition and general state
space.

######  Theorem 54.

Suppose the Markov chain $\\{X_{i}(n)\\}_{n\in\mathbb{N}}$ associated with
each arm $i\in\\{1,\cdots,K\\}$ satisfy Assumption 6, and the reward function
$r_{i}$ satisfies Assumption 7. Then, the regret $\mathcal{R}(n)$ of Algorithm
1 up to time $n$ is upper bounded by

$\displaystyle\mathcal{R}(n)\leq 4L\log
n\sum_{i>M}\frac{(\eta_{1}-\eta_{i})}{(\eta_{M}-\eta_{i})^{2}}+\sum_{i>M}(\eta_{1}-\eta_{i})(1+2\beta)M+2\sum_{i=1}^{K}R_{i}\Gamma_{\mathbf{F}_{i}},$
(75)

where $\beta>0$ is a constant.

Proof:

$\displaystyle
n\sum_{j=1}^{M}\eta_{i}-\sum_{i=1}^{K}\eta_{i}\mathbb{E}[T_{i}(n)]$
$\displaystyle=\sum_{j=1}^{M}\sum_{i=1}^{K}\eta_{j}\mathbb{E}[T_{i,j}(n)]-\sum_{j=1}^{M}\sum_{i=1}^{K}\eta_{i}\mathbb{E}[T_{i,j}(n)]$
$\displaystyle=\sum_{j=1}^{M}\sum_{i>M}(\eta_{j}-\eta_{i})\mathbb{E}[T_{i,j}(n)]\leq\sum_{i>M}(\eta_{1}-\eta_{i})\mathbb{E}[T_{i}(n)]$
(76)

Using Lemma 51, we can get the following equality in $(a)$ and $g_{i}$ is the
solution to Poisson’s equation associated with the transition kernel $P_{i}$
and function $r_{i}$.

$\displaystyle\bigg{|}\mathcal{R}(n)-\bigg{(}n\sum_{j=1}^{M}\eta_{j}-\sum_{i=1}^{K}\eta_{i}\mathbb{E}[T_{i}(n)]\bigg{)}\bigg{|}=\bigg{|}\mathbb{E}\bigg{[}\sum_{i=1}^{K}\sum_{t=1}^{T_{i}(n)}r_{i}(X_{i}(t))\bigg{]}-\sum_{i=1}^{K}\eta_{i}\mathbb{E}[T_{i}(n)]\bigg{|}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\bigg{|}\sum_{i=1}^{K}\mathbb{E}[g_{i}(X_{i}(0))-g_{i}(X_{i}(N))]\bigg{|}\stackrel{{\scriptstyle(b)}}{{\leq}}2\sum_{i=1}^{K}R_{i}\Gamma_{\mathbf{F}_{i}},$
(77)

where $(b)$ comes from Lemma 55. To bound the regret, we combine Equation 5.3
and Equation 5.3 and obtain the inequality $(c)$ and $(d)$

$\displaystyle\mathcal{R}(n)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}n\sum_{j=1}^{M}\eta_{j}-\sum_{i=1}^{K}\eta_{i}\mathbb{E}[T_{i}(n)]+2\sum_{i=1}^{K}R_{i}\Gamma_{\mathbf{F}_{i}}\stackrel{{\scriptstyle(d)}}{{\leq}}\sum_{i>M}(\eta_{1}-\eta_{i})\mathbb{E}[T_{i}(n)]+2\sum_{i=1}^{K}R_{i}\Gamma_{\mathbf{F}_{i}}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\sum_{i>M}(\eta_{1}-\eta_{i})\bigg{[}(1+2\beta)M+\frac{4L\log
n}{(\eta_{M}-\eta_{i})^{2}}\bigg{]}+2\sum_{i=1}^{K}R_{i}\Gamma_{\mathbf{F}_{i}}$
$\displaystyle=4L\log
n\sum_{i>M}\frac{(\eta_{1}-\eta_{i})}{(\eta_{M}-\eta_{i})^{2}}+\sum_{i>M}(\eta_{1}-\eta_{i})(1+2\beta)M+2\sum_{i=1}^{K}R_{i}\Gamma_{\mathbf{F}_{i}},$
(78)

where $(e)$ and $\beta$ are from Lemma 53.

##  6 Conclusion

In this paper, we study the Hoeffding-type inequality for Markov chains under
the generalized concentrability condition and the IPM Dobrushin coefficient.
The generalized concentrability condition provides a flexible notion of
convergence for Markov chains, which allows easy application of the Hoeffding-
type inequality in practice. The IPM Dobrushin coefficient provides an
approach to estimate the concentrability constant whenever the problem
structure allows it. Under our framework, several existing Hoeffding-type
inequalities for Markov chains in the literature emerge as special cases. We
provide three application examples from machine learning and reinforcement
learning to demonstrate the utility of our theory.

We hope our work can shed some light on the concentration of measure and
convergence of Markov chains from the IPM perspective. Nevertheless, there are
many problems left unanswered which we list a few here for future studies:

  * •

What are the necessary and sufficient conditions for the Markov chains to
satisfy the generalized concentrability condition?

  * •

Can we establish the connection between generalized concentrability condition
and usual conditions studied in Markov chain theory, such as the drift
condition, Harris recurrence, and small set?

  * •

How to extend the Hoeffding inequality to the unbounded functions with sub-
Gaussian distribution assumption?

  * •

Are there more ways to estimate the concentrability constant in Equation 5
other than the IPM Dobrushin coefficient?

Acknowledgments and Disclosure of Funding

The authors gratefully acknowledge the insightful discussions with our
collaborators from Cisco Systems on potential applications of this work,
including Ashish Kundu, Jayanth Srinivasa, and Hugo Latapie.

Hao Chen and Abhishek Gupta’s work was supported by Cisco Systems grant
GR127553. Yin Sun’s work was supported in part by the NSF under grant
CNS-2239677, and by the ARO under grant W911NF-21-1-02444. Ness Shroff’s work
has been supported in part by NSF grants NSF AI Institute (AI-EDGE)
CNS-2112471, CNS-2106933, CNS-2312836, CNS-1955535, and CNS-1901057, by Army
Research Office under Grant W911NF-21-1-0244, and Army Research Laboratory
under Cooperative Agreement Number W911NF-23-2-0225.

##  Appendix A Proofs of Section 3

The following two lemmas encapsulate simple inequalities repeatedly used in
the proofs. Let $\mathbf{F}\subseteq\mathbb{M}(\mathbb{X})$ be a set of real-
valued measurable functions on $\mathbb{X}$.

######  Lemma 55.

Consider a bounded real-valued function $f\in M\cdot\mathbf{F}$ which
$M\in(0,\infty)$ is the minimal stretch of $\mathbf{F}$ to include $f$. It
holds

$\displaystyle|\mu(f)-\nu(f)|\leq
M\cdot\textnormal{{IPM}}_{\mathbf{F}}(\mu,\nu)$ (79)

Proof:

$\displaystyle|\mu(f)-\nu(f)|$
$\displaystyle=\bigg{|}\int_{\mathbb{X}}fd\mu-\int_{\mathbb{X}}fd\nu\bigg{|}=M\bigg{|}\int_{\mathbb{X}}\frac{1}{M}fd\mu-\int_{\mathbb{X}}\frac{1}{M}fd\nu\bigg{|}$
$\displaystyle\leq
M\sup_{g\in\mathbf{F}}\bigg{|}\int_{\mathbb{X}}gd\mu-\int_{\mathbb{X}}gd\nu\bigg{|}=M\cdot\textnormal{{IPM}}_{\mathbf{F}}(\mu,\nu)$

######  Lemma 56.

For $i\in\\{0,\cdots,n-1\\}$, consider a bounded real-valued function
$f_{i}\in M_{i}\cdot\mathbf{F}$ with minimal stretch $M_{i}\in(0,\infty)$.
Suppose the transition kernel $P:\mathbb{X}\times\mathcal{X}\to[0,1]$ admits a
unique invariant probability measure $\pi$, then we have

$\displaystyle\bigg{|}\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]-\pi(f_{i})\bigg{|}\leq\sum_{i=0}^{n-1}M_{i}\textnormal{{IPM}}_{\mathbf{F}}(\mu
P^{i},\pi),$

for any initial distribution $\mu\in\mathcal{P}(\mathcal{X})$.

Proof:  This is a direct consequence of Lemma 55 after applying triangular
inequality.

The following lemma demonstrates the martingale decomposition of cumulative
sums of a Markov chain.

######  Lemma 57.

Let $\mathbf{X}=\\{X_{i}\\}_{i\in\mathbb{N}}$ be a Markov chain with
transition kernel $P$ and initial distribution
$\mu\in\mathcal{P}(\mathcal{X})$. Assume that $P$ admits a unique invariant
probability measure $\pi$. For $i\in\\{0,\cdots,n-1\\}$ and
$n\in\mathbb{Z}_{+}$, let $f_{i}:\mathbb{X}\to\mathbb{R}$ be different
functions on the Markov chain. Let
$\tilde{S}_{n}\coloneqq\sum_{i=1}^{n-1}f_{i}(X_{i})$ be cumulative sum. Let
$\\{\mathcal{F}_{i}\\}_{i=0}^{n-1}$ be the filtration generated by
$\mathbf{X}$, i.e., $\mathcal{F}_{i}=\sigma(X_{0},\cdots,X_{i})$. Then, there
exists a Martingale difference sequences $\\{D_{i}\\}_{i=1}^{n-1}$ adapted to
$\\{\mathcal{F}_{i}\\}_{i=0}^{n-1}$ such that

$\displaystyle\tilde{S}_{n}-\mathbb{E}_{\mu}[\tilde{S}_{n}]=\sum_{i=1}^{n-1}D_{i}+f_{0}(X_{0})-\mathbb{E}_{\mu}[f_{0}].$
(80)

Proof:  We employ the martingale decomposition technique introduced in Chapter
23 of Douc et al. (2018). For the following development, we use these short
notations for tuples: $X_{m}^{n}\coloneqq(X_{m},\cdots,X_{n})$ and