# Offline Estimation of Controlled Markov Chains: Minimaxity and Sample
Complexity

Imon Banerjee  Department of Statistics, Purdue University Harsha Honnappa
School of Industrial Engineering, Purdue University  Vinayak Rao  Department
of Statistics, Purdue University

###### Abstract

In this work, we study a natural nonparametric estimator of the transition
probability matrices of a finite controlled Markov chain. We consider an
offline setting with a fixed dataset, collected using a so-called logging
policy. We develop sample complexity bounds for the estimator and establish
conditions for minimaxity. Our statistical bounds depend on the logging policy
through its mixing properties. We show that achieving a particular statistical
risk bound involves a subtle and interesting trade-off between the strength of
the mixing properties and the number of samples. We demonstrate the validity
of our results under various examples, such as ergodic Markov chains, weakly
ergodic inhomogeneous Markov chains, and controlled Markov chains with non-
stationary Markov, episodic, and greedy controls. Lastly, we use these sample
complexity bounds to establish concomitant ones for offline evaluation of
stationary Markov control policies.

##  1 Introduction

This paper presents probably approximately correct (PAC)-style minimax sample
complexity results for statistical estimation of transition matrices of
discrete-time, finite-state controlled Markov chains (CMCs) [7]. CMCs
represent a natural model setting for stochastic optimal control problems, as
well as reinforcement learning (RL) problems. Our work is motivated by the
need for rigorous statistical inference in offline settings, using a dataset
pre-collected under some fixed but unknown logging policy. Besides being
important in its own right, this is also a key consideration of offline
reinforcement learning.

The offline RL setting is fundamentally different from the now standard online
setting, and is significantly harder to solve, owing to the fact that the
agent cannot interact with the environment (so that globally suboptimal
decisions cannot be corrected), and owing to the fact that the logging policy
is typically unknown. However, the offline RL framework is quite natural in
the setting of learning to manage operations and service systems, and
decision-making in mission-critical settings, where it is either too risky
and/or uneconomical to use online RL. To fix these ideas, consider the
following two vignettes from clinical and operational decision-making.

  * A

Data sets on prognosis, diagnosis, and treatment decisions made by physicians
have been proposed to be used to train RL agents to potentially identify new
(superior) paths to achieving the same (better) outcomes for patients [50, 32,
66, 11]. A crucial fact, as noted in [32], is that “Unlike other domains, such
as game playing…the RL agent has to learn from a limited set of data and
intervention[s]…collected offline.”

  * B

Analogous learning problems also arise in a variety of manufacturing and
service operations management settings. Recent literature has considered the
problem of learning to route jobs in a multi-class stochastic processing
network, using online RL [13]. However, in many application settings, such as
patient flow modelling in a hospital network, as observed in [2], data
collected using pre-existing flow control and routing policies can be mined to
discover new/better protocols and policies. Offline RL is a natural learning
framework to achieve this.

Solving such problems through a model-based approach involves two steps –
system identification to estimate a CMC model of the system dynamics, followed
by value function estimation and policy evaluation using the estimated system
dynamics model. Our work addresses both these issues through the lens of
sample complexity,

the importance of which arises from the fact that many applications involve
datasets limited in size, with the collection of new data prohibitively
expensive, as observed in [32, 2] above. Inferential questions are further
complicated by the fact that the logging policy used to collect data is
unknown or structurally complex; again, see the setting of medical decision-
making [32] above. Of course, assuming that the policy is stationary Markovian
(i.e., for instance, solely dependent on the current state of a patient)
simplifies the inference problems, often reducing it to the setting of an
ergodic Markov chain (and opening the door to a plethora of results, including
frequentist PAC bounds [59], Bayesian PAC bounds [4], asymptotic convergence
[62] etc.). On the other hand, if the logging policy is non-Markovian, the
corresponding stochastic dynamics are not Markovian, and statistical inference
results are quite sparse for this setting. Highlighting the importance of non-
Markovian policies, a recent paper by Mutti et al. [40] argues that
Markovianity is actually insufficient for finite sample exploration of the
state-control space and one must consider non-Markovian policies for optimal
reward-free exploration in online RL settings. Given these requirements, an
understanding of the sample complexity of system identification and offline
policy evaluation is an important open problem. This paper precisely addresses
this question in the context of finite-state CMCs. We adopt a broader view of
CMCs following [7] and model the sequence of controls generated by the logging
policy as an adapted and ‘mixing’ (in a sense defined in Assumptions 3 and 4)
stochastic sequence. We focus specifically on the robustness of a simple non-
parametric estimator of CMC transition matrices. Although non-parametric
estimators of transition matrices have been used in various model-based RL
studies [30, 36], there are no extant statistical guarantees on the specific
estimator we study. This paper fills this obvious gap in the literature. The
main contributions of this paper can be summarised as follows.

  1. 1.

We show that the non-parametric estimator is minimax optimal in Theorem 2 if
the number of samples is large enough and identify an explicit lower bound on
the sample size to achieve a high probability estimate. Informally, we prove
that the sample complexity of estimating the transition matrices in a CMC with
$d$ states and $k$ controls is $\Theta(d^{2}\,k)$ if the CMC is geometrically
fast mixing. As we argue in section 4, a geometrically ergodic Markov chain
with $d\,k$ states can be thought of as a special case of a $d$-state,
$k$-control CMC where the controls are so-called “stationary”. Therefore, our
result (Theorem 2) recovers the optimal sample complexity of estimating Markov
chains from [59] as a special case.

  2. 2.

We tease out a subtle trade-off between assuming stronger mixing conditions
and obtaining tighter sample complexity. In particular, we prove in Theorem 1
that the transition probabilities can be estimated even under a weaker mixing
assumption than is required for minimaxity (Theorem 2). However, there is a
trade-off in requiring more samples (roughly $\Omega(d^{2}k^{2})$ in place of
$\Omega(d^{2}k)$) to achieve the same level of estimation error and, thus,
losing guarantees of minimax optimality.

  3. 3.

Our sample complexity results on the estimator of transition matrices
immediately yield error bounds on the offline policy evaluation (OPE). OPE in
offline model-based RL involves estimating the average reward obtained from a
given policy (different from the logging policy) using the estimated
transition matrix as a plug-in. In particular, Theorem 4 focuses on evaluating
stationary Markov policies on a system model estimated using data logged under
a mixing logging control sequence that may not be Markovian. The sample
complexity results recover minimax optimal rates obtained in the literature
where the logging policy is universally assumed to be Markovian.

From a methodological perspective, our analysis reveals two principles that
are broadly useful in establishing sample efficiency results for learning CMCs
and other controlled stochastic models. First, a crucial fact underlying the
results in this paper is a ‘Goldilocks principle’ that no state-control pair
must be visited too many or too few times in a single observed sample path.
This can be achieved by ensuring that the control sequence is such that the
time-to-return to a particular pair is uniformly bounded over the state-
control space (see Assumptions 1 and 2).

Second, the effect of history on the probability of under- or over-visiting
any part of the state-control space is controlled by the mixing properties of
the control sequence, as defined in Assumption 5 and Assumption 7. Broadly
speaking, weaker mixing properties imply looser bounds on these probabilities,
in turn implying that estimators are possibly sample inefficient. The bulk of
the existing literature on offline estimation of CMCs focuses on the setting
where the control sequence forms a stationary ergodic Markov sequence and,
under this condition, the nonparametric estimator is minimax optimal, as
implied by Theorem 2 and Proposition 13. However, if the control sequence
mixes comparatively slowly (say, polynomially), then Theorem 1 yields a loose
sample complexity bound. This point is of particular interest in the presence
of model misspecification. As we prove in Sections 4.2 and 4.4, it is
relatively straightforward to verify the geometric mixing properties of the
control sequences when the controls are Markovian. However, when the controls
are non-Markovian, there is no general result to demonstrate geometric mixing.
Thus, a practitioner must be cautious of erroneously assuming the logging
policy to be Markovian when it is not. If the controls are not Markovian, then
$\Omega(d^{2}k)$ samples are not necessarily sufficient to control the
probability of large estimation errors on the transition probabilities.
Instead, one might need $\Omega(d^{2}k^{2})$ samples to guarantee a low
probability of large estimation errors.

As a final note on the methodological implications, while we focus on finite
state-control spaces, we believe that these principles, and our analysis,
yield a broad framework for proving sample efficiency results for offline
estimation of CMCs, and potentially other controlled stochastic models, under
much broader modeling conditions. For instance, if one uses a histogram or a
density estimator of a transition kernel on continuous state spaces and
compact control spaces, then our results are directly applicable, although the
optimal sample complexity would depend upon the smoothness properties of the
transition function.

From an operational and applications perspective, we observe that offline RL,
although not as popular, is a natural learning framework for solving many
data-driven operations management and decision-making problems, wherein a
fixed dataset of system performance and inputs has been pre-collected. As
noted before, this is a fundamentally different setting from online RL, and
yet a very natural one for the broad audience of this journal. The sharp
sample complexity results in this paper provide confidence in the conditions
under which a natural non-parametric estimator of the system dynamics (and
hence, value function estimators) is sample efficient. The principles outlined
above should provide guidelines for statistical inference in specific
operational modeling problems.

###  1.1 Related Literature

We divide the review of the literature into three parts. In the first part, we
place our results in the context of the existing literature and on non-
parametric estimation for stochastic processes. In the second and third parts,
we relate our sample complexity results to existing relevant ones in the
literature on offline RL, and system identification, respectively.

##### Non-parametric estimation:

The foundations of non-parametric estimation [54] of finite ergodic Markov
chains were laid by [6]. Subsequently, [63] presented an important extension
to infinite state spaces, with follow-up work on applications to regression
[62]. There is also extensive literature establishing laws of large numbers
(LLNs) [18] and central limit theorems (CLTs) [23] for a range of time-
homogeneous Markov chains. However, somewhat surprisingly, minimax sample
complexity bounds for finite ergodic Markov chains were only established
recently in [59]. However, barring some results on Laws of Large Numbers, and
CLTs [45, 46, 14, 15], results on statistical inference for time-inhomogenous
Markov chains remain sparse. Furthermore, such properties when the controls
are stochastic in nature are even less understood. A crucial complication in
our setting is that the state-control pair process need not be Markovian,
complicating the application of existing results. Nonetheless, we recover
rates similar to those of [59] as a special case in section 4.2, demonstrating
the generality of our results.

##### Offline Reinforcement Learning:

Model-based offline reinforcement learning methods [25, 69, 49] have recently
received significant attention in the literature. Controlled Markov chains are
most relevant in offline reinforcement learning as a tool towards maximising a
value function. It involves constructing a model for the transition
probability matrix and then using it to solve the expected Bellman equation (a
detailed discussion of the problem can be found in [29, Section 2.1 ]).

Although there is a plethora of articles based on model-free learning the
value or $Q$ functions [65, 42, 49], few articles discuss the optimality of
their results. Notable works in this regard are the trio of papers [30, 31,
64], which prove the optimality of their results by proving minimaxity of
their recovered sample complexities. Crucially, their work involved the more
limited scope of discounted or finite-horizon problems under Markovian
policies.

Of particular interest is the fact that the empirical estimator is optimal for
model-based RL problems under these settings [30, 31, 64]. Furthermore, our
results show that it continues to be an optimal estimator in the non-Markovian
regime under suitable mixing conditions.

##### System Identification:

The problem setting in our paper is analogous to system identification in
optimal control, [57, 34, 53] where the parameters to be estimated are the
transition matrices. There is a growing body of work that revolves around so-
called “active learning” for system identification [35, 12, 43]. However, in
our work, the logging policy does not necessarily aid active learning.
Furthermore, the former settings are online in nature, and system
identification in the offline setting traditionally does not involve a
controlling policy [ljung1987theory]. Our work recognises the obvious utility
of being able to use offline data, and our results apply in considerable
generality.

##### Outline:

The rough outline of the paper is as follows. In Section 2, we introduce some
notation and the concepts from uniform mixing and weak mixing. In Section 3,
we construct the empirical estimator $\hat{M}^{(l)}$ for the transition matrix
$M^{(l)}$ for any control $l$ and formally introduce our assumptions. We then
illustrate the trade-off discussed previously by producing weaker PAC bounds
for the estimation error $\sup_{l}\|\hat{M}^{(l)}-M^{(l)}\|_{\infty}$ under
weaker mixing assumptions, and a stronger minimax PAC bound under stronger
mixing assumptions. In Section 4, we apply our main result to derive
statistical guarantees for various reward-free offline RL tasks under a range
of settings, such as stationary controls, Markov controls, and episodic
controls. Finally, in Section 5, we use our estimator to obtain estimation
guarantees for learning the value function. We end with a summary and
discussion of the open questions in Section 6. This paper presents probably
approximately correct (PAC)-style minimax sample complexity results for
statistical estimation of transition matrices of discrete-time, finite
controlled Markov chains (CMC) [7], motivated by the need for rigorous
statistical inference in offline reinforcement learning (RL) and system
identification problems. CMCs represent a natural model setting for stochastic
optimal control problems, but also reinforcement learning problems, including
pure or reward-free exploration and/or learning a value function or optimal
policy when endowed with a reward structure. In fact, a wide range of now
standard RL methods have been developed to manage the exploration-exploitation
tradeoff (see [52]) inherent in RL, assuming that a reward signal is available
in real time that simultaneously allows for estimating the optimal value
function while exploring the policy space.

##  2 Preliminaries

##### Notations.

Let $\mathbb{N}$ and $\mathbb{R}$, respectively, denote the set of natural and
real numbers. The symbol $\lfloor\cdot\rfloor$ represents the floor function.
All random variables in this paper will be defined with respect to a filtered
probability sample space $(\Omega,\mathcal{F},\mathbb{F},\mathbb{P})$, where
$\mathcal{F}$ is a $\sigma$-algebra and $\mathbb{F}:=\\{\mathcal{F}_{i}\\}$,
with $\mathcal{F}_{i}\subset\mathcal{F}$, is a given filtration. Let
$\\{X_{i}\\}$ represent a discrete-time stochastic process adapted to
filtration $\mathbb{F}$, with finite state space $\chi$. $\mathcal{L}(X)$
denotes the law associated with the random variable $X$, $\mathbb{E}[X]$ the
expectation and $\sigma(X)$ the $\sigma$-algebra induced by $X$. A $d\times d$
matrix $Q$ is a _stochastic matrix_ if the rows of $Q$ add up to 1 and
$Q_{s,t}$ denotes the $(s,t)$’th entry of $Q$. Let $\mathbb{I}$ be a finite
set representing the control space, and $\\{a_{i}\\}$ represent the sequence
of controls where $a_{i}\in\mathbb{I}\enspace\forall\enspace i$.

##### Definitions.

Following [7], we define a controlled Markov chain (CMC) as an
$\mathbb{F}$-adapted pair process $\\{(X_{i},a_{i})\\}$, where the process
$\\{X_{i}\\}$ satisfies ‘controlled’ Markovian dynamics,

$\mathbb{P}\left(X_{i+1}=s_{i+1}|\mathcal{F}_{i}\right)=\mathbb{P}(X_{i+1}=s_{i+1}|X_{i}=s_{i},a_{i}=l)=:M_{s_{i},s_{i+1}}^{(l)}.$

Let $\mathbb{M}:=\\{M^{(1)},\dots,M^{(k)}\\}$ represent the set of transition
probability matrices where $M^{(l)}=\left[M^{(l)}_{s,s^{\prime}}\right]$ for
all $s,s^{\prime}\in\chi$ and $l\in\mathbb{I}$. The control sequence
$\\{a_{i}\\}$ is assumed to satisfy $a_{i}\in\mathcal{F}_{i}$ for each $i\geq
0$ (i.e., $\\{a_{i}\\}$ is an adapted sequence of controls). In the case,
$\\{a_{i}\\}$ is deterministic, $\\{X_{i}\\}$ forms a time inhomogeneous
Markov chain, where the transition matrix changes at time step $i$ according
to the control $a_{i}$. Note that there are a finite number of possible
transition matrices (since $\mathbb{I}$ is assumed to be finite). Observe, in
particular, that if $a_{i}=f(X_{i})$, for some given function
$f:\mathcal{S}\to\mathbb{I}$, then $\\{a_{i}\\}$ is a Markov control sequence.

For two time points $i<j$, we define the _history_ $\mathcal{H}_{i}^{j}$ to be
$\mathcal{H}_{i}^{j}:=\sigma(X_{j},a_{j},\dots,X_{i},a_{i})\subset\mathcal{F}_{j}$
and _sample history_
$\hbar_{i}^{j}\in\left(\chi\times\mathbb{I}\right)^{(j-i)}$ to be a fixed
sequence of states and controls
$\hbar_{i}^{j}:=\left(s_{j},l_{j},\dots,s_{i},a_{i}\right)$.

Unless stated otherwise, the initial states are assumed to be sampled from
some distribution $D_{0}$ over $\chi\times\mathbb{I}$.

Next, we define the ‘time to return’ for every pair of states and controls
$(X_{i},a_{i})$.

######  Definition 1.

When $i=1$ the first _hitting time_ $(s,l)$ is defined as

$\tau_{s,l}^{(1)}:=\min\left\\{n:(X_{n}=s,a_{n}=l),(X_{j}\neq s,a_{n}\neq l)\
\forall\ 0<j<n\right\\}.$

When $i\geq 2$ the $i$-th _time to return_ of the state-control pair $(s,l)$
is recursively defined as

$\tau^{(i)}_{s,l}:=\min\\{n:(X_{\sum_{k=1}^{i-1}\tau^{(k)}_{s,l}+n}=s,a_{\sum_{k=1}^{i-1}\tau^{(k)}_{s,l}+n}=l),(X_{j}\neq
s\cup a_{j}\neq
l)\enspace\forall\enspace\sum_{k=1}^{i-1}\tau^{(k)}_{s,l}<j<\sum_{k=1}^{i-1}\tau^{(k)}_{s,l}+n\\}.$

######  Remark.

In the ensuing sections, we will use the phrases _time to return_ and _return
time_ interchangeably.

###  2.1 Mixing Coefficients

In this subsection, we define the weak and uniform mixing coefficients, and
some fundamental lemmas concerning them. Let $\left\\{X_{i},a_{i}\right\\}$ be
an CMC.

For any $j\leq m\in\mathbb{N}$, let
$\mathbb{T}\in(\chi\times\mathbb{I})^{m-j}$, $s_{1},s_{2}\in\chi$, and
$l_{1},l_{2}\in\mathbb{I}$. Finally, let $\hbar_{0}^{i-1}$ be an element of
$(\chi\times\mathbb{I})^{i}$. Define the map
$(\mathbb{T},s_{1},s_{2},l_{1},l_{2},\hbar_{0}^{i-1})\mapsto\eta_{i,j}(\mathbb{T},s_{1},s_{2},l_{1},l_{2},\hbar_{0}^{i-1})$
as

$\displaystyle\eta_{i,j}(\mathbb{T},s_{1},s_{2},l_{1},l_{2},\hbar_{0}^{i-1})$
$\displaystyle:=\left|\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|X_{i}=s_{1},a_{i}=l_{1},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)\right.$
$\displaystyle\left.\qquad-\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|X_{i}=s_{2},a_{i}=l_{2},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)\right|.$

Then the weak-mixing coefficient $\bar{\eta}_{i,j}$ is

$\displaystyle\leavevmode\nobreak\
\bar{\eta}_{i,j}:=\underset{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\begin{subarray}{c}\mathbb{T},s_{1},s_{2},l_{1},l_{2},\hbar_{0}^{i-1},\\\
\mathbb{P}\left(X_{i}=s_{1},a_{i}=l_{1},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)>0,\\\
\mathbb{P}\left(X_{i}=s_{2},a_{i}=l_{2},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)>0\end{subarray}}{\sup}\eta_{i,j}(\mathbb{T},s_{1},s_{2},l_{1},l_{2},\hbar_{0}^{i-1}).$
(2.1)

Next, we define the _uniform mixing_ coefficient. As before, let
$\mathbb{T}\in(\chi\times\mathbb{I})^{m-j}$, and $\hbar_{0}^{i}$ be an element
of $(\chi\times\mathbb{I})^{i+1}$. Then, the uniform-mixing coefficient is
defined as

$\displaystyle\leavevmode\nobreak\
\sup_{\mathbb{T},\hbar_{0}^{i}}\phi_{i,j}:=\sup_{\begin{subarray}{c}\mathbb{T},\hbar_{0}^{i},\\\
\mathbb{P}\left(\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)>0\end{subarray}}\left|\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathbb{P}((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}\right|.$
(2.2)

######  Lemma 1.

The uniform and the weak mixing coefficients defined in equations 2.1 and 2.2
(respectively) are satisfy

$\displaystyle\phi_{i,j}\leq\bar{\eta}_{i,j}\leq 2\phi_{i,j}.$

Next, consider the following version of Hölder’s inequality for uniformly
mixing sequences from [22, Theorem A.6 ], by setting $p=1$ and $q=\infty$ in
that result.

######  Lemma 2.

For any two real functions $f$, and $g$,

$\displaystyle|\mathrm{Cov}(f(X_{j},a_{j}),g(X_{i},a_{i}))|\leq\phi_{i,j}\mathbb{E}\left|f(X_{j},a_{j})-\mathbb{E}[f(X_{j},a_{j})]\right|\
\mathrm{ess}\sup_{X_{i},a_{i}}\left|g(X_{i},a_{i})\right|.$

It follows from Lemma 1 that,

$\displaystyle|\mathrm{Cov}(f(X_{j},a_{j}),g(X_{i},a_{i}))|\leq\bar{\eta}_{i,j}\mathbb{E}\left|f(X_{j},a_{j})-\mathbb{E}[f(X_{j},a_{j})]\right|\
\mathrm{ess}\sup_{X_{i},a_{i}}\left|g(X_{i},a_{i})\right|.$

##  3 Empirical Estimation of Transition Probability Matrices

As stated before, our objective is to estimate the transition matrices of the
Markov chain from a single, large but finite sample path of length $m\gg 1$.
Consequently, in this section, we formally describe the estimation problem and
our proposed empirical estimator $\mathbb{M}$ of the CMC. Recall that the
sequence of controls $\\{a_{0},a_{1},\dots\\}$ is an adapted stochastic
sequence of controls taking values $\mathbb{I}$. It can be readily seen that
$\left\\{X_{i},a_{i}\right\\}$ need not be Markovian or ergodic. In
particular, we focus on the ‘natural’ empirical estimator of the transition
matrices for any given state-control-state (SCS) tuple, $(s,l,t)$. Define the
number of visits to a state control pair $(s,l)$, $N_{s}^{(l)}$, and the
number of transitions from state $s$ to state $t$ under $l$: $N_{s,t}^{(l)}$
as

$\displaystyle N_{s}^{(l)}$
$\displaystyle:=\sum_{i=1}^{m}\mathbbm{1}[X_{i}=s,a_{i}=l],\quad
N_{s,t}^{(l)}:=\sum_{i=1}^{m}\mathbbm{1}[X_{i}=s,X_{i+1}=t,a_{i}=l].$ (3.1)

Correspondingly, define the empirical estimator of $M_{s,t}^{(l)}$ as

$\displaystyle\hat{M}_{s,t}^{(l)}:=\frac{N_{s,t}^{(l)}}{N_{s}^{(l)}}\leavevmode\nobreak\
,$ (3.2)

and construct the estimated matrix $\hat{M}^{(l)}$ as
$\left[\hat{M}_{s,t}^{(l)}\right]$. The following proposition are obtained as
a consequence of the previous definitions.

######  Proposition 3.

Consider a sample $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ from a
controlled Markov chain.

Define

$\hat{M}^{(l)}(s,\cdot):=\left(\hat{M}_{s,1}^{(l)},\hat{M}_{s,2}^{(l)},\dots,\hat{M}_{s,d}^{(l)}\right),\text{
and
}{M}^{(l)}(s,\cdot):=\left({M}_{s,1}^{(l)},{M}_{s,2}^{(l)},\dots,{M}_{s,d}^{(l)}\right),$

and let $0<n_{low,s}<n_{high,s}<m$ be any two integers. Then we have

$\displaystyle\mathbb{P}\Bigg{(}\bigg{\|}\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\bigg{\|}_{1}$
$\displaystyle>\varepsilon,\ n_{low,s}\leq N_{s}^{(l)}\leq n_{high,s}\Bigg{)}$
$\displaystyle\leq
m\exp\left({-\frac{n_{low,s}}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n_{high,s}}}\right\\}^{2}}\right)\leavevmode\nobreak\
.$ (3.4)

It is apparent from Proposition 3 that one needs to control the number of
visits to a state-control pair $N_{s}^{(l)}$ to find theoretical guarantees
for $\hat{M}_{s,t}^{(l)}$. Here, we return to the 3 challenges of
transitioning from a Markov chain to a controlled Markov chain.

  1. 1.

Question of “Aperiodicity”. As mentioned previously, the notion of
aperiodicity is fundamental to a Markov chain but ill-defined for a controlled
Markov chain. As an example, consider the following three transition
probability matrices

$\displaystyle M^{(1)}=\begin{bmatrix}0&1&0\\\ 1/3&1/3&1/3\\\
1/3&1/3&1/3\end{bmatrix}\ M^{(2)}=\begin{bmatrix}1/3&1/3&1/3\\\ 0&0&1\\\
1/3&1/3&1/3\end{bmatrix}\ M^{(3)}=\begin{bmatrix}1/3&1/3&1/3\\\ 1/3&1/3&1/3\\\
1&0&0\end{bmatrix}.$

It can be verified easily that each of the transition probability matrices are
aperiodic (and, in fact, ergodic). However, consider a time-inhomogenous
Markov chain on state-space $\\{1,2,3\\}$ where the transition matrices arrive
in a sequence $``M^{(1)},M^{(2)},M^{(3)},M^{(1)},M^{(2)},M^{(3)},\dots"$. Not
only is it periodic if the initial state is $1$, it is guaranteed to
eventually become periodic!

  2. 2.

Question of “Irreducibility”. As mentioned previously, irreducibility [38,
page 85] is a fundamental concept to any Markov chain. Furthermore, observe
from [38, Theorem 13.0.1] that an aperiodic and irreducible Markov chain
admits a stationary distribution (defined as in [38, Chapter 13]), a key
consequence of which is KAC’s theorem [38, Theorem 10.2.2] establishing the
finiteness of the return times of every state in a Markov chain. However, such
notions do not translate to a controlled Markov chain.

  3. 3.

Question of “Mixing”. We already mentioned that an ergodic Markov chain on a
finite state space is uniformly mixing geometrically fast. However, there
exist no such equivalent result for controlled Markov chain. Furthermore, a
glaring question remains about the speed of mixing of controlled Markov
chains. Although geometrically fast mixing might be sufficient, it might not
be necessary for the estimation of transition probability Matrices. Finally,
one may wonder how the overall mixing of the controlled Markov chain affect
the mixing of the states and the controls.

Consequently, we make simplifying assumptions that allow us to mitigate the
challenges. Our first two assumptions address the notions of aperiodicity and
irreducibility. Informally, we need to ensure that no part of the chain is
deterministic in nature, and every state-control pair $(s,l)$ is visited
sufficiently often. Our first assumption follows.

######  Assumption 1.

For all time steps $i$, there exists two constants $\zeta_{1}$ and $\zeta_{2}$
and a set $\mathcal{S}_{i}\subset\\{1,\dots,d\\}\times\mathbb{I}$ such that

$\displaystyle
0<\zeta_{2}\leq\mathbb{P}[(X_{i},a_{i})\in\mathcal{S}_{i}]\leq\zeta_{1}<1.$

######  Remark.

Since we can always discard finitely many samples, our results continue to
hold even when the controlled Markov chain satisfies the previous assumptions
on all but a finite number of time points. However, it would lead to more
cumbersome (but very similar) calculations.

######  Assumption 2 (Return Time).

There exists an integer $T>0$ such that,

$\displaystyle\sup_{s,l,i}\mathrm{E}[\tau^{(i)}_{s,l}|{\mathcal{F}_{\sum_{p=0}^{i-1}\tau_{s,l}^{(p)}}}]<T\textit{
almost everywhere.}$

The following is an immediate consequence of the previous assumptions.

######  Lemma 4.

For any controlled Markov chain that satisfies Assumptions 1 and 2,

$\displaystyle\frac{m}{T}-1<\mathrm{E}\left[N_{s}^{(l)}\right]\leq
m\max\\{\zeta_{1},1-\zeta_{2}\\},$ (3.5)

where $\zeta_{1},\zeta_{2}\in(0,1)$ are defined in Assumption 1. In
particular, if $m\geq 2T$, then

$\displaystyle\frac{m}{2T}<\mathrm{E}\left[N_{s}^{(l)}\right]\leq
m\max\\{\zeta_{1},1-\zeta_{2}\\}.$ (3.6)

######  Remark.

Observe a parallel between this lemma and the minorization property described
in various texts related to Markov chains such as [38, Chapter 5.1.1 ], [47],
etc. In particular, when $m=1$ and $k=1$, and $D_{0}$ is uniform over $\chi$,
we notice that this lemma recovers the minorization condition described in
[38, Equation 5.3 ] for a uniform measure. Furthermore, taking summation over
all $l$ and $s$ in the lower bound. Consequently,

$\displaystyle\sum_{s,l}\frac{m}{2T}<\sum_{s,l}\mathrm{E}\left[N_{s}^{(l)}\right].$

Obviously,
$\sum_{s,l}\mathrm{E}\left[N_{s}^{(l)}\right]=\mathrm{E}\left[\sum_{s,l}N_{s}^{(l)}\right]=m$.
Therefore,

$\displaystyle dk\frac{m}{2T}<m,$

which in turn implies that,

$T>\frac{dk}{2}.$

Next, we make the following two assumptions on the $\bar{\eta}$-mixing
coefficients of the stochastic process $\\{X_{i},a_{i}\\}$:

######  Assumption 3 ($\eta$-mixing).

There exists a constant $\mathbb{C}_{\Delta}>1$ independent of $m$ such that,

$\displaystyle\|\Delta_{m}\|:=\underset{1\leq i\leq
m}{\max}(1+\bar{\eta}_{i,i+1}+\bar{\eta}_{i,i+2}+\dots\bar{\eta}_{i,m})\leq\mathbb{C}_{\Delta}.$

######  Assumption 4 (Exponential $\eta$-mixing).

There exists an constant $\mathbb{C}_{\Delta}>1$ independent of $m$ such that,

$\displaystyle\bar{\eta}_{i,j}\leq\exp\left(-(j-i)\log\left(\frac{\mathbb{C}_{\Delta}}{\mathbb{C}_{\Delta}-1}\right)\right).$

######  Remark.

It is obvious that if Assumption 4 is satisfied, so is Assumption 3 with the
same constant. It also follows from Lemma 1 that if the $\bar{\eta}$-mixing
coefficients satisfy the previous assumptions, so does the $\phi$-mixing
coefficients with appropriately adjusted constants.

We have the following concentration inequalities as an immediate consequence
of the previous assumptions.

######  Proposition 5.

Consider a sample $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ from a
controlled Markov chain that satisfies Assumptions 1, 2, and 3. Let
$N_{s}^{(l)}$ be the number of visits to state-control pair $(s,l)$ as defined
in eq. 3.1. Then for all integers
$n_{high,s}>\mathbb{E}[N_{s}^{(l)}]>n_{low,s}$, we have

$\displaystyle\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}])\leq$
$\displaystyle\
2\exp\left({-{\frac{\left(n_{low,s}-\frac{m}{2T}\right)^{2}}{2m\left(\mathbb{C}_{\Delta}\right)^{2}}}}\right)$
$\displaystyle+2\exp\left({-{\frac{\left(n_{high,s}-m\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{2m\left(\mathbb{C}_{\Delta}\right)^{2}}}}\right).$

###### Proof.

We observe that,

$\displaystyle\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}])$
$\displaystyle=\mathbb{P}(N_{s}^{(l)}-\mathbb{E}[N_{s}^{(l)}]<n_{low,s}-\mathbb{E}[N_{s}^{(l)}])$
$\displaystyle\quad+\mathbb{P}(N_{s}^{(l)}-\mathbb{E}[N_{s}^{(l)}]>n_{high,s}-\mathbb{E}[N_{s}^{(l)}]).$

The rest of the proof follows readily by an application of Lemmas 16 and 7. ∎

Next, define $\rho_{s}^{(l)}:=\sup_{1\leq i\leq
m}\mathbb{P}\left(X_{i}=s,a_{i}=l\right)$. Then, we get the following version
of Chernoff/Bernstein inequality for tail probability of $N_{s}^{(l)}$.

######  Proposition 6.

Consider a sample $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ from a
controlled Markov chain that satisfies Assumptions 1, 2, and 4. Let
$N_{s}^{(l)}$ be the number of visits to state-control pair $(s,l)$ as defined
in eq. 3.1. Then there exists a positive constant $\mathbb{C}_{pel}$ depending
only upon $\mathbb{C}_{\Delta}$ such that for all integers
$n_{low,s}<\mathbb{E}[N_{s}^{(l)}]<n_{high,s}$, we have

$\displaystyle\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s}$
$\displaystyle,n_{high,s}])\leq 2\exp\left(-\;\
\frac{\mathbb{C}_{pel}\left(n_{low,s}-\frac{m}{2T}\right)^{2}}{4m\left(\mathbb{C}_{\Delta}\right)\rho_{s}^{(l)}+1+\left(\frac{m}{2T}-n_{low,s}\right)\left(\log
m\right)^{2}}\right)$ $\displaystyle+2\exp\left(-\;\
\frac{\mathbb{C}_{pel}\left(n_{high,s}-m\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{4m\left(\mathbb{C}_{\Delta}\right)\rho_{s}^{(l)}+1+\left(n_{high,s}-m\max\\{\zeta_{1},1-\zeta_{2}\\}\right)\left(\log
m\right)^{2}}\right).$

Proposition 6 is obtained as a consequence of [37, Theorem 2 ] adapted in this
current work as Lemma 18. In many practical examples, $\mathbb{C}_{pel}$ is a
universal constant. We discuss this in greater detail in the remark ensuing
Lemma 21 and produce one particular example in Section B. We can now state our
first theorem regarding the sample complexity of estimating the transition
probability matrices of controlled Markov chain.

######  Theorem 1.

Consider a sample $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ from a
controlled Markov chain that satisfies Assumptions 1, 2, and 3. Let,
$\\{\hat{M}_{s,t}^{(l)}:l\in\mathbb{I}\\}$ be the empirical estimators as
defined in eq. 3.2 with $\hat{M}^{(l)}$ being the corresponding estimated
transition matrix. There exists a universal constant $c>1$, such that for any
$\varepsilon>0$, and $\delta\in(0,1)$, if

$\displaystyle
m>c\;\max\left\\{\frac{T}{\varepsilon^{2}}\log\left(\frac{dkT}{\varepsilon^{2}\delta}\right),\left(\mathbb{C}_{\Delta}\right)^{2}\max\left\\{{T}^{2},\frac{1}{\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}\right\\}\log\left(\frac{dk}{\delta}\right)\right\\},$

then the empirical estimator satisfies,

$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\left\|\hat{M}^{(l)}-M^{(l)}\right\|_{\infty}>\varepsilon\right)<\delta,$
(3.8)

where $d=|\chi|$ and $k=|\mathbb{I}|$.

As we see in Theorem 1, assuming that the mixing coefficients are summable
(Assumption 3) allows us to find the sample complexity. However, in Theorem 2
we will see that if we further assume the mixing coefficients to be
geometrically decaying (Assumption 4), then we will have a reduced sample
complexity, and it would also be minimax. So a tradeoff exists in the form of
a requiring a stronger assumption versus requiring more samples. The tradeoff
appears in terms of having a Hoeffding’s inequality (Proposition 5) versus
having a more powerful Chernoff’s inequality (Proposition 6) for the tail
probabilities. It is widely known that Chernoff/Bernstein type inequalities
are tighter than Azuma/Hoeffding type inequalities when the variances are
small. One instance of such a discussion might be found in the introduction of
Section 2.3 in [56].

###  3.1 Sketch of Proof of Theorem 1

STEP 1. As in proposition 3 let,

$\hat{M}^{(l)}(s,\cdot)=\left(\hat{M}_{s,1}^{(l)},\hat{M}_{s,2}^{(l)},\dots,\hat{M}_{s,d}^{(l)}\right),\text{
and
}{M}^{(l)}(s,\cdot)=\left({M}_{s,1}^{(l)},{M}_{s,2}^{(l)},\dots,{M}_{s,d}^{(l)}\right).$

By an application of the union bound, we get

$\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\left\|\hat{M}^{(l)}-M^{(l)}\right\|_{\infty}>\varepsilon\right)\leq\sum_{l\in\mathbb{I}}\sum_{s\in\chi}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right)$

STEP 2. For each $s\in\chi$ and $l\in\mathbb{I}$, we use the law of total
probability [20, Proposition 4.1] to decompose
$\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right)$
into a high probability region and a low probability region. To be precise,
for two integers $n_{high,s}$ and $n_{low,s}$ chosen appropriately by Lemma 4,
we write

$\displaystyle\sum_{s,l}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right)$
$\displaystyle\
\leq\sum_{s,l}\sum_{n=n_{low,s}}^{n_{high,s}}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)$
$\displaystyle\qquad+\sum_{s,l}\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}]).$

STEP 3. In this step we observe that if
$m>\max\left\\{\frac{d}{\varepsilon^{2}\left({1+\max\\{\zeta_{1},1-\zeta_{2}\\}}\right)},\frac{64T}{\varepsilon^{2}}\log\left(\frac{6dk}{\delta}\right)\right\\},$
Proposition 3 gives us the following upper bound, for an appropriate choice of
$m$:

$\sum_{s,l}\sum_{n=n_{low,s}}^{n_{high,s}}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)\leq\delta/3.$

STEP 4. In this step, we use Proposition 5 to upper bound
$\sum_{s,l}\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}])$. Using
Proposition 5 we get,

$\displaystyle\sum_{s,l}\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}])\leq$
$\displaystyle
dk\Bigg{(}2\exp\left({-{\frac{\left(n_{low,s}-\frac{m}{2T}\right)^{2}}{2m\left(\mathbb{C}_{\Delta}\right)^{2}}}}\right)$
$\displaystyle+2\exp\left({-{\frac{\left(n_{high,s}-m\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{2m\left(\mathbb{C}_{\Delta}\right)^{2}}}}\right)).$

Hence, as long as,

$m>c\max\left\\{\mathbb{C}_{\Delta}^{2}\log\left(\frac{dk}{\delta}\right)\max\left\\{{T}^{2},\frac{1}{\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}\right\\}\right\\},$
$\sum_{s,l}\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}])\leq 2\delta/3.$

This completes the sketch.

Before proceeding to the next theorem, we introduce some notation. Consider a
sample $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ from a controlled
Markov chain that satisfies Assumptions 1, 2, and 4. Let
$\rho_{\star}:=\sup_{s,l}\rho_{s}^{(l)}$ where $\rho_{s}^{(l)}$ is defined in
Proposition 6 and define,

$\displaystyle\mathbb{C}_{\zeta}:=\frac{8\left(2\mathbb{C}_{\Delta}\rho_{\star}\left(1-\max{\zeta_{1},1-\zeta_{2}}\right)^{-2}+\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{-1}\right)}{\mathbb{C}_{pel}}$
(3.10)
$\displaystyle\mathbb{C}_{T}:=\frac{64\left(\mathbb{C}_{\Delta}\rho_{\star}T^{2}+2T\right)}{\mathbb{C}_{pel}}\quad\mathbb{C}_{T,\delta}:=\mathbb{C}_{T}\log\left(\frac{6dk}{\delta}\right)\quad\mathbb{C}_{\zeta,\delta}:=\mathbb{C}_{\zeta}\log\left(\frac{6dk}{\delta}\right),$
(3.11)

where $\mathbb{C}_{pel}$ is as in Proposition 6.

######  Theorem 2.

Consider the setting of Theorem 1 and suppose that Assumptions 1, 2, and 4 are
satisfied, and let $\rho_{\star}=\max_{s,l}\rho_{s}^{(l)}$. Then, there exists
a universal constant $c>1$ such that if

$\displaystyle m>c\
\max\left\\{\frac{8d}{\varepsilon^{2}\left(1+\max\\{\zeta_{1},1-\zeta_{2}\\}\right)},2\
\mathbb{C}_{T,\delta}\left(\log\mathbb{C}_{T,\delta}\right)^{2},2\
\mathbb{C}_{\zeta,\delta}\left(\log\mathbb{C}_{\zeta,\delta}\right)^{2}\right\\},$

then the empirical estimator satisfies

$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\left\|\hat{M}^{(l)}-M^{(l)}\right\|_{\infty}>\varepsilon\right)<\delta,$
(3.12)

for all $\varepsilon,\delta>0$ and is minimax upto $\log$ and $\log\log$ terms
whenever $0<\varepsilon<1/32$.

######  Remark.

It is straightforward to see that
$\rho_{s}^{(l)}\leq\max\left\\{\zeta_{1},1-\zeta_{2}\right\\}$. However, this
upper bound is loose to the degree that the resulting sample complexity is no
longer provably Minimax.

We want to point out that this result is tighter than the previous one by a
factor of $\mathbb{C}_{\Delta}\rho_{\star}/\mathbb{C}_{pel}$. $\rho_{\star}$
can be $O(1/T)$ with $\mathbb{C}_{pel}$ being independent of model parameters,
and we present such an example in Section B. Therefore, this result is
significantly tighter than the previous one. The presence of this difference
is significant in the context of model misspecification. If a model is
erroneously assumed to be exponentially mixing when it is not, $O(T)$ samples
are no longer sufficient to guarantee precision while estimating the
transition matrices.

In Sections 4.2, and 4.4 we prove that if the controls are Markovian, then the
process is exponentially mixing under mild conditions. This provides yet
another justification of why it is tempting to assume Markovianity. However,
if the assumption is erroneous, then there is no guarantee that the estimated
probabilities would be accurate. As such, our prescription is to follow
pessimism in the face of uncertainty and collect $O(T^{2})$ samples whenever
there is uncertainty about the logging policy.

###  3.2 Sketch of Proof of Theorem 2

The proof of sample complexity proceeds similarly to the proof of Theorem 1.
The key difference is in STEP 4, where instead of using Proposition 5, we use
Proposition 6 instead. The details can be found in Section D.3. For this
sketch, we focus on the minimaxity. Let $\mathcal{M}_{\chi,\mathbb{I}}$ be the
class of all Markov decision processes on state space $\chi$ with control
space $\mathbb{I}$. Observe that the minimax risk,

$\displaystyle\mathcal{R}_{m}$
$\displaystyle=\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}_{\chi,\mathbb{I}}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\right)$
$\displaystyle\geq\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\right),$

for any subclass of controlled Markov chains
$\mathcal{M}^{\prime}\subset\mathcal{M}_{\chi,\mathbb{I}}$ and any estimation
procedure, $\hat{\mathbb{M}}$ dependent on the data (informally). The rest of
the proof proceeds through 2 cases by constructing appropriate subclasses
$\mathcal{M}^{\prime}$.

##### CASE I:

$\left(m<\frac{8d}{\varepsilon^{2}\left(1+\max\\{\zeta_{1},1-\zeta_{2}\\}\right)}\right)$

For this case, we choose a class of controlled Markov chains with controls
distributed uniformly over $\mathbb{I}$ and transition matrices

$\displaystyle M_{\sigma}$
$\displaystyle=\begin{pmatrix}\frac{1-p_{\star}}{d}&\ldots&\frac{1-p_{\star}}{d}&p_{\star}\\\
\vdots&\vdots&\vdots&\vdots\\\
\frac{1-p_{\star}}{d}&\ldots&\frac{1-p_{\star}}{d}&p_{\star}\\\
\frac{1-p_{\star}+16\sigma_{1}\varepsilon}{d}&\ldots&\frac{1-p_{\star}-16\sigma_{\frac{d}{2}}\varepsilon}{d}&p_{\star}\end{pmatrix}.$

for vectors
$\sigma=\left(\sigma_{1},\dots,\sigma_{\frac{d}{2}}\right)\in\left\\{-1,1\right\\}^{\frac{d}{2}}$.
We then use Tasbykov’s reduction method to lower bound
$\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\right)$
for our chosen subclass of controlled Markov chains.

##### CASE II:

$m<\left(2\ \mathbb{C}_{T,\delta}\left(\log\mathbb{C}_{T,\delta}\right)^{2},2\
\mathbb{C}_{\zeta,\delta}\left(\log\mathbb{C}_{\zeta,\delta}\right)^{2}\right)$

STEP 1. For this case, we set $\mathcal{M}^{\prime}$ to be a class of
controlled Markov chains with controls and transition probability matrices
described in Section B.

STEP 2. We then use Tsybakov’s reduction method [54, Chapter 2.2] to observe
that for any random variable $\mathbb{T}$,

$\mathcal{R}_{m}\geq\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\,|\,\mathbb{T}>m\right)\mathbb{P}\left({\mathbb{T}>m}\right).$

$\mathbb{T}$ is chosen to be an appropriate “touring time” (the time to visit
sufficiently many state-control pairs).

STEP 3. We then prove that as long as

$m<2\ \mathbb{C}_{T,\delta}\left(\log\mathbb{C}_{T,\delta}\right),$

$\mathbb{P}\left({\mathbb{T}>m}\right)$ is bounded away from zero.

STEP 4. We then argue that whenever $\mathbb{T}>m$, there exists a state-
control pair $s_{0},l_{0}$ such that $N_{s_{0}}^{(l_{0})}=0$.

STEP 5. If $N_{s_{0}}^{(l_{0})}=0$, so is $N_{s_{0},t}^{(l_{0})}=0$ for all
$t\in\chi$. This proves that there is an uniform error to estimate
$M_{s_{0},t}^{(l_{0})}$, which proves our claim.

##  4 Applications

Before we move on to the main content of the applications section, we make a
brief discussion about how Assumptions 2, 3, 4, and can be reduced to simpler
assumptions for the purpose of analysis.

###  4.1 Reduction of Assumptions

##### Reduction of Return Times.

First consider the assumption on return times introduced in Assumption 2.
Observe that if $a_{i}$ is $k$-connected Markovian, then

$\displaystyle\sup_{s,l,i}\mathrm{E}[\tau^{(i)}_{s,l}|{\mathcal{F}_{\tau^{\dagger}}}]=\sup_{s,l,i}\mathrm{E}[\tau^{(i)}_{s,l}|\mathcal{H}_{\tau^{\dagger}-k}^{\tau^{\dagger}}]\text{
almost everywhere,}$

where we have defined $\tau^{\dagger}:=\sum_{p=0}^{i-1}\tau_{s,l}^{(p)}$ for
notational convenience. Moreover, if $a_{i}$ is independent of time point $i$
(also called “stationary”), then we further have

$\displaystyle\leavevmode\nobreak\
\sup_{s,l,i}\mathrm{E}[\tau^{(i)}_{s,l}|\mathcal{H}_{\tau^{\dagger}-k}^{\tau^{\dagger}}]=\sup_{s,l}\mathrm{E}[\tau^{(1)}_{s,l}|X_{0},a_{0}]\text{
almost everywhere.}$ (4.1)

##### Reduction of Mixing Coefficients.

Next, we decompose the $\bar{\eta}$-mixing coefficients of the paired process
$\\{X_{i},a_{i}\\}$ into mixing coefficients over states and controls. We
motivate this decomposition using two facts:

  * •

The controls of a controlled Markov chain are often chosen with well-behaved
properties by the user.

  * •

In practice, it is easier to analyse the mixing coefficients of the individual
processes than the paired processes.

We begin by defining the $\gamma$-mixing coefficients $\gamma_{p,j,i}$ for
controls as the following total variation distance

$\displaystyle\gamma_{p,j,i}:=\sup_{s_{p},\hbar_{i+j}^{p-1},\hbar_{0}^{i}}\left\|\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1}\right)\right\|_{TV},$
(4.2)

where
$\mathbb{P}\left(X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)>0$.

######  Assumption 5 (Mixing of controls).

There exists a constant $\mathbb{C}\geq 0$,

$\displaystyle\sup_{1\leq
i\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\infty}}\sum_{j=1}^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\infty}}\sum_{p=i+j+1}^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\infty}}\gamma_{p,j,i}\leq\frac{\mathbb{C}}{2}.$

######  Remark.

In the Markovian settings, when the sequence of controls $a_{i}$ depend only
upon $X_{i}$, it readily follows that

$\gamma_{p,j,i}=0$

for all $p,j,i$. In such case, Assumption 5 is satisfied with $\mathbb{C}=0$.
This phenomenon extends to the case where $a_{i}$ depends upon $j$ many past
time points. If $a_{i}$ depend only upon $X_{i},a_{i-1},X_{i-1},\dots,$
$a_{i-1},X_{i-1}$, then Assumption 5 is satisfied with $\mathbb{C}=k-1$.

We can now make the final technical assumption on the mixing of the underlying
Markov chain. Let $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ be a
collected sample. To be specific, for all integers $j\geq i$ define the mixing
coefficient $\bar{\theta}_{i,j}$

$\displaystyle\bar{\theta}_{i,j}:=\underset{\begin{subarray}{c}s_{1},s_{2}\in\chi,l_{1},l_{2}\in\mathbb{I},\\\
\mathbb{P}(X_{i}=s_{1},a_{i}=l_{1})>0,\\\
\mathbb{P}(X_{i}=s_{2},a_{i}=l_{2})>0\end{subarray}}{\sup}\|\mathcal{L}\left(X_{j}|X_{i}=s_{1},a_{i}=l_{1}\right)-\mathcal{L}\left(X_{j}|X_{i}=s_{2},a_{i}=l_{2}\right)\|_{TV},$
(4.3)

such that $(s_{1},l_{1})\neq(s_{2},l_{2})$. Our final technical assumption is
following.

######  Assumption 6 (Mixing of States).

There exists a constant $\mathbb{C}_{\theta}\geq 0$,

$\sup_{1\leq
i\leq{\infty}}\sum_{j=i+1}^{{\infty}}\bar{\theta}_{i,j}\leq\mathbb{C}_{\theta}.$

We make note that neither of Assumptions 5 and 6 imply the other. The
following counter-examples illustrate this point.

  1. 1.

Let $(X_{i},a_{i})$ be an inhomogenous Markov chain for which

$\sup_{1\leq i\leq\infty}\sum_{j=i+1}^{\infty}\bar{\theta}_{i,j}=\infty.$

One example of such an inhomogenous Markov chain can be found in Lemma 23.
However, since the controls are deterministic, every inhomogenous Markov chain
satisfies Assumption 5. We prove this fact formally in Proposition 11.
Therefore, this chain satisfies Assumptions 5 but not Assumption 6.

  2. 2.

For the second counter-example consider a controlled Markov chain
$(X_{i},a_{i})$ where the $a_{i}$’s do not satisfy Assumption 5. Let $X_{i}$
be independent draws from a uniform distribution over $\chi$. It is easily
seen that $\bar{\theta}_{i,j}=0$ for this example. Therefore, this chain
satisfies Assumptions 6 but not 5.

Observe that the previous assumptions on the states and controls imply the
summability of the weak mixing coefficients. We formalise it in the following
Lemma.

######  Lemma 7.

For any controlled Markov chain that satisfies Assumptions 5 and 6,

$\displaystyle\lVert\Delta_{m}\rVert\leq\mathbb{C}+\mathbb{C}_{\theta}+1,$

where $\|\Delta_{m}\|=\underset{1\leq i\leq
m}{\max}(1+\bar{\eta}_{i,i+1}+\bar{\eta}_{i,i+2}+\dots\bar{\eta}_{i,m})$, and
$\bar{\eta}_{i,j}$ is as defined in eq. 2.1

######  Remark.

As before, observe that Assumptions 5 and 6 provide a sufficient condition for
$\|\Delta_{m}\|$ to be bounded uniformly over $m$. We remark that Theorem 1
continues to hold under this weaker condition. However, in practice, it will
often be easier to prove Assumptions 5 and 6.

Next, we make the following two assumptions as stronger versions of
Assumptions 5 and 6.

######  Assumption 7 (Geometric mixing of controls).

There exists a constant $\mathbb{C}_{\star}>0$ independent of $m$ such that
$\forall$ integers $j\geq i$,

$\displaystyle\sum_{p=i+j+1}^{\infty}\gamma_{p,j,i}\leq
e^{-\mathbb{C}_{\star}\left(j-i\right)}.$

######  Assumption 8 (Geometric mixing of States).

There exists a constant $\mathbb{C}_{\theta,\star}>0$ independent of $m$ such
that $\forall$ integers $j\geq i$,

$\bar{\theta}_{i,j}\leq e^{-\mathbb{C}_{\theta,\star}\left(j-i\right)}.$

We then get the following lemma as a counterpart to Lemma 7.

######  Lemma 8.

For any controlled Markov chain that satisfies Assumptions 7 and 8, there
exists a positive constant $c_{cof}$ independent of $m$ such that $\forall$
integers $j\geq i$,

$\displaystyle\bar{\eta}_{i,j}\leq e^{-c_{cof}(j-i)}.$

######  Remark.

It is easy to observe that if Assumptions 7 and 8 are satisfied, then so are
Assumptions 5 and 6 with constants $1/(1-e^{-\mathbb{C}_{\star}})$ and
$1/(1-e^{-\mathbb{C}_{\theta,\star}})$ respectively. To simplify notations, we
will not use these explicit forms and will denote
$1/(1-e^{-\mathbb{C}_{\star}})$ by $\mathbb{C}$ and
$1/(1-e^{-\mathbb{C}_{\theta,\star}})$ by $\mathbb{C}_{\theta}$ respectively.
Finally, observe that Assumptions 7 and 8 provide a sufficient condition for
$\bar{\eta}_{i,j}$ to be geometrically decaying uniformly over $m$.

###  4.2 Controlled Markov chains with stationary randomised controls and time
homogenous ergodic Markov chains

A Markov decision process is said to have stationary randomised controls if
for any time period $i$, state $s_{i}$, and sample history $\hbar_{0}^{i-1}$,

$\mathcal{L}\left(a_{i}|X_{i}=s_{i},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)=\mathcal{L}\left(a_{i}|X_{i}=s_{i}\right)=\mathcal{L}\left(a_{1}|X_{1}=s_{i}\right).$

In this section we show that assumptions 1,2, 5, and 6 hold for a Markov
decision process with stationary controls.

We observe that the transition probability of the joint state control pair is

$\displaystyle\mathbb{P}\left(X_{i}=t,a_{i}=l|X_{i-1}=s,a_{i-1}=l^{\prime}\right)$
$\displaystyle=\mathbb{P}\left(X_{i}=t|X_{i-1}=s,a_{i-1}=l\right)\mathbb{P}(a_{i}=l|X_{i}=t)$
$\displaystyle=M_{s,t}^{(l)}\times P_{t}^{(l)},$

where $P_{s}^{(l)}$, denotes $\mathbb{P}\left(a_{1}=l|X_{1}=s\right)$. It is
straightforward to see that the state-control pair is a time homogeneous
Markov chain with transition probabilities given by $M_{s,t}^{(l)}\times
P_{t}^{(l)}$. We have the following consequences of the previous definition.

Our goal is to estimate the transition probabilities
$\mathbb{P}(X_{1}=t|X_{0}=s,a_{0}=l)$. Observe that this estimation problem
only makes sense in the case when $\mathbb{P}(X_{0}=s,a_{0}=l)>0$ for any $s$
and $l$. This follows from the fact
$\mathbb{P}(X_{0}=s,a_{0}=l)=P_{s}^{(l)}\times\mathbb{P}(X_{0}=s)$ and,
$P_{s}^{(l)}>0$ for all $s\in\chi$ and $l\in\mathbb{I}$. By $P_{min}$, denote
$\inf_{s,l}P_{s}^{(l)}$. Assume that $M^{(l)}$ is an aperiodic and irreducible
(ergodic) transition probability matrix for all $l\in\mathbb{I}$. Then, we
have the following proposition.

######  Proposition 9.

The paired process $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ is an
uniformly ergodic Markov chain.

By verifying the aperiodicity and irreducibility of the paired process, the
proof of Proposition 9 follows readily from [38, Theorem 16.0.2 ] and is
therefore omitted.

Let $\pi$ be the invariant distribution of this Markov chain with
$\pi_{(s,l)}$ being invariant probability corresponding to $(s,l)$. For
simplicity, assume that $D_{0}=\pi$.

######  Proposition 10.

Let $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ be a sample from a
controlled Markov chain with $d=|\chi|$, $k=|\mathbb{I}|$, and stationary
randomised controls. Fix $\varepsilon>0$, and $\delta\in(0,1)$. Then there
exists a universal constant $c>0$ and a constant $\mathbb{C}_{\theta}>0$ such
Theorem 1 is satisfied with $T=\sup_{s,l}{1}/{\pi_{s,l}}$, $\zeta_{2}=P_{min}$
$\zeta_{1}=1-(k-1)P_{min}$ and $\mathbb{C}_{\theta}$. Moreover, if
$D_{0}=\pi$, then $\zeta_{1}=\zeta_{2}=1/T$ satisfied Assumption 1.

###### Proof.

The proof of this result can be found in Section E.1. ∎

###  4.3 Inhomogenous Markov chains

a controlled Markov chain is said to be an inhomogenous Markov chain if there
exists a sequence of constants $l_{0},l_{1},\dots$ such that for any non-
negative integer $i$, history $\hbar_{0}^{i-1}\in(\chi\times\mathbb{I})^{i}$,
and state $s\in\chi$

$\mathbb{P}(a_{i}=l_{i}|\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1},X_{i}=s)=1,$

$\square$

We make the following assumptions on the controls and the transition
probabilities

Let $\mathbb{T}\in\mathbb{N}$ be a known integer. Then, we assume that

$\sum_{i=j}^{\mathbb{T}+j}\mathbbm{1}[a_{i}=l]>1,$

for all $1\leq j\leq m-\mathbb{T}$ and $l\in\mathbb{I}$. Moreover, we assume
that the transition matrices $M^{(l)}$ are positive stochastic matrices where
every entry in the matrix is strictly positive. It follows from the fact that

$\displaystyle\mathbb{P}\left(X_{i+1}=t|X_{i}=s,a_{i}=l\right)>M_{min}:=\min_{s,t,l}M_{s,t}^{(l)},$
$\displaystyle(I1)$

it further follows that

$\displaystyle\mathbb{P}\left(X_{i+1}\neq t|X_{i}=s,a_{i}=l\right)<1-M_{min}.$
$\displaystyle(I2)$

######  Proposition 11.

Let $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ be a sample from an
inhomogenous Markov chain satisfying $M_{min}>0$ and section 4.3. Fix
$\varepsilon>0$, and $\delta\in(0,1)$. Then Theorem 1 holds with

$T=\left(1-M_{min}\right)^{1-1/\mathbb{T}}/\left({1-\left(1-M_{min}\right)^{\frac{1}{\mathbb{T}}}}\right),\zeta_{2}=M_{min},\zeta_{1}=M_{max}:=\max_{s,t,l}M_{s,t}^{(l)},\textit{
and }\mathbb{C}_{\theta}=e/(e-1).$

###### Proof.

The proof of this result can be found in Section E.2. ∎

######  Remark.

If $\\{X_{n}\\}$ is Markov, then it is well known that
$Y_{n}=(X_{n},\dots,X_{n-j+1})$ is a Markov process on state space $\chi^{j}$.
Marginalising on the first component, conclusions can then be obtained about
the distribution of $X_{n}$ given $X_{n-1},\dots,X_{n-j+1}$. It follows that
our conclusions also hold for $j$-connected inhomogenous Markov chains.

###  4.4 Controlled Markov chains with non-stationary Markov controls

An controlled Markov chain is said to have non-stationary Markov controls if
for any time period $i$, state $s_{i}$, and sample history $\hbar_{0}^{i-1}$,

$\mathcal{L}\left(a_{i}|X_{i}=s_{i},\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)=\mathcal{L}\left(a_{i}|X_{i}=s_{i}\right).$

For convenience, we refer to it as simply Markov controls. Observe that we
allow the law of the control sequence to depend upon the time step $i$.
Observe that we can write the transition probability of the joint state
control pair as

$\displaystyle\mathbb{P}\left(X_{i}=t,a_{i}=l^{\prime}|X_{i-1}=s,a_{i-1}=l\right)$
$\displaystyle=\mathbb{P}\left(X_{i}=t|X_{i-1}=s,a_{i-1}=l\right)\mathbb{P}(a_{i}=l^{\prime}|X_{i}=t)$
$\displaystyle=M_{s,t}^{(l)}\times P_{t,l^{\prime}}^{(i)},$

It is straightforward to see that the state-control pair is a time
inhomogeneous Markov chain with transition probabilities given by
$M_{s,t}^{(l)}\times P_{s,l^{\prime}}^{(i)}$. Our goal is to estimate the
transition probabilities $\mathbb{P}(X_{i}=t|X_{i-1}=s,a_{i-1}=l^{\prime})$.
We proceed by making assumptions on the return times of the controls.

######  Definition 2.

Define $\tau_{s,l}^{(i,\star,j)}$ to be the time between the $j-1$-th and
$j$-th visit to control $l$ after visiting state-control pair $s,l$ for the
$i$-th time. For ease of notation, denote
$\sum_{k=1}^{i}\tau_{s,l}^{(k)}+\sum_{k=1}^{j-1}\tau^{(i,\star,k)}_{s,l}=\tau_{\star}$,
Then $\tau_{s,l}^{(i,\star,j)}$ is recursively defined as

$\tau_{s,l}^{(i,\star,j)}:=\min\\{n:(a_{\tau_{\star}+n}=l),a_{j}\neq
l\enspace\forall\enspace\tau_{\star}<j<\tau_{\star}+n\\}.$

Next we make some simplifying assumptions on $\tau_{s,l}^{(i,\star,j)}$ and
$M^{(l)}$

######  Assumption 9.

  1. 1.

For some constant $T_{\star}>0$,

$\sup_{i\geq
0}\mathbb{E}[\tau_{s,l}^{(i,\star,j)}|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}+\sum_{p=1}^{j-1}\tau_{s,l}^{(i,\star,p)}}]<T_{\star}\textit{
almost everywhere.}$

  2. 2.

For all $i\in\mathbb{I}$ the stochastic matrix $M^{(l)}$ is positive. To be
precise,

$0<M_{min}\leq M_{max}<1,$

where $M_{min}$ and $M_{max}$ are defined as,

$M_{max}:=\max_{s,t}M_{s,t}^{(l)},\text{ and
}M_{min}:=\min_{s,t}M_{s,t}^{(l)}.$

Then, we have the following lemma on the return times.

######  Lemma 12.

Under the conditions of Assumption 9,

$\mathbb{E}[\tau_{s,l}^{(i)}|\mathcal{F}_{\sum_{p=1}^{i-1}\tau_{s,l}^{(p)}}]<\frac{T_{\star}M_{max}}{\max\\{M_{max},1-M_{min}\\}(1-\max\\{M_{max},1-M_{min}\\})}$

almost everywhere for all $(i,s,l)\in\mathbb{N}\times\chi\times\mathbb{I}$.

We can now state our main result about the sample complexity of a controlled
Markov chain with a non-stationary Markov controls.

######  Proposition 13.

Let $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ be a sample from a
controlled Markov chain with non-stationary Markovian controls satisfying
Assumption 9. Fix $\varepsilon>0$, and $\delta\in(0,1)$. Then Assumption 1
holds with $\zeta_{1}=M_{max}$, $\zeta_{2}=M_{min}$,
$T=\frac{T_{\star}M_{max}}{\max\\{M_{max},1-M_{min}\\}(1-\max\\{M_{max},1-M_{min}\\})}\
\text{ and }\ \mathbb{C}_{\theta}:=\frac{1}{1-dM_{min}}.$

###### Proof.

The proof of this result can be found in Section E.3. ∎

######  Remark.

Observe that

$\frac{1}{1-(1-M_{min})^{\frac{1}{\mathbb{T}}}}\leq\frac{\mathbb{T}}{M_{min}}\leq\frac{\mathbb{T}M_{max}}{\max\\{M_{max},1-M_{min}\\}(1-\max\\{M_{max},1-M_{min}\\})}$

where the first inequality follows from Bernoulli’s inequality [10]. Comparing
this to lemma 12 consequently implies that tighter upper bounds to expected
return times can be derived when the controls corresponding to a controlled
Markov chain are deterministic. In other words, a CMC with Markov non-
deterministic controls require more samples to guarantee PAC-bounds than an
inhomogenous Markov chain.

###  4.5 Controlled Markov chains with episodic controls

Controlled Markov chains with episodic controls appear frequently in offline
reinforcement learning [42, 30, 31, 65, 49] and constitute a fixed horizon $H$
after which the algorithm restarts. To formalise, let $H$ be a fixed positive
integer. For any positive integer $i>H$, let $H^{(i)}$ denote the greatest
multiple of $H$ less than or equal to $i$. To be precise

$H^{(i)}:=H\lfloor\frac{i}{H}\rfloor.$

A sample $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ is said to be
from a controlled Markov chain with episodic controls and horizon length $H$
if for any $s\in\chi$ and $\hbar_{0}^{i-1}\in(\chi\times\mathbb{I})^{i}$,

$\mathcal{L}\left(a_{i}|X_{i}=s,\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right)=\mathcal{L}\left(a_{i}|X_{i}=s,\mathcal{H}_{H^{(i)}}^{i-1}=\hbar_{H^{(i)}}^{i-1}\right),$

We assume that for all state-control pair $(t,l^{\prime})$, there exists a
time step $i^{(t,l^{\prime})}<H$ such that

$\min_{t,l^{\prime}\in\chi\times\mathbb{I}}\mathbb{P}\left(X_{i^{(t,l^{\prime})}}=t,a_{i^{(t,l^{\prime})}}=l^{\prime}|X_{0}=s,a_{0}=l\right)>0.$

for some state control pair $(s,a)$. Since this infimum is taken over finitely
many objects there exists a probability $M_{min}$ such that

$\mathbb{P}\left(X_{i^{(s,l)}}=s,a_{i^{(s,l)}}=l|X_{0}=s^{\prime},a_{0}=l^{\prime}\right)>M_{min}.$

We observe that this assumption is similar to the so called persistence of
excitation (Assumption 1 in [5]) and is close to the infinite updates
assumption in [67] and [68].

Our second technical assumption is that .

$(X_{i},a_{i})\overset{i.i.d.}{\sim}Uniform{\left\\{(1,1),\dots,(d,k)\right\\}}.$

whenever $i$ is a multiple of $H$. In other words, multiples of $H$ denote the
start of a new episode.

######  Remark.

We would like to point out that assuming section 4.5 simplifies our
calculations. However, our results also hold when the distribution is not
uniform. The corresponding calculations are very similar (yet more tedious and
notationally challenging).

$\square$

Let $\zeta_{1}=M_{max},\ \zeta_{2}=M_{min},T=dkH-1,\ \mathbb{C}=H^{2},\ \text{
and }\ \mathbb{C}_{\theta}=H$. We can now state our main result about the
sample complexity of a controlled Markov chain with episodic controls.

######  Proposition 14.

Let $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ be a sample from a
controlled Markov chain with episodic controls. Fix $\varepsilon>0$, and
$\delta\in(0,1)$. Then Theorem 1 holds with $\zeta_{1}=M_{max},\
\zeta_{2}=M_{min},T=dkH-1,\ \mathbb{C}=H^{2},\ \text{ and }\
\mathbb{C}_{\theta}=H$.

###### Proof.

The proof of this result can be found in Section E.4. ∎

###  4.6 Controlled Markov chains with greedy controls

Greedy algorithms are an important facet of reinforcement learning appearing
in numerous exploration-exploitation like multi-armed bandit [27],
$Q$-learning [61], Levy-flights [33] among others. In the current context, we
define a controlled Markov chain with greedy controls as follows.

######  Definition 3.

Let $\\{\omega_{i}\\}_{i\geq 0}$ be a sequence of i.i.d. Bernoulli variables
with $\mathbb{P}(\omega_{i}=1)=\upsilon$ for some fixed $\upsilon\in(0,1)$. A
controlled Markov chain with greedy controls is defined to be a triplet
$(X_{i},\omega_{i},a_{i})$ taking values in
$\chi\times\\{0,1\\}\times\mathbb{I}$, where $X_{i}$ represents the state and
$a_{i}$ represents the control at time point $i$ such that

$a_{i}=(1-\omega_{i})\alpha_{i}+\omega_{i}D_{i}^{(1)}$

where $\alpha_{i}$ are random variables on $\mathbb{I}$ adapted to the history
and $D_{i}^{(1)}$ are i.i.d. uniform random variables supported on
$\mathbb{I}$.

Moreover for some probability $M_{s,t}^{(l)}$ depending only upon $s,t$, and
$l$, the transition probabilities satisfy,

$\mathbb{P}\left(X_{i}=t|X_{i-1}=s,a_{i-1}=l,\omega_{i}=\xi\right)=M_{s,t}^{(l)}$

for any $\xi\in\\{0,1\\}$.

This completes our formalisation of a controlled Markov chains with greedy
controls. Intuitively, the definition suggests that greedy controls keep
exploring the control space irrespective of the history. We make the mild
assumption that $M^{(l)}$ is an aperiodic and irreducible (ergodic) transition
probability matrix for all $l\in\mathbb{I}$ and observe that the $l$-th
transition matrix of $(X_{i},\omega_{i})$ is a block matrix
$\mathfrak{M}^{(l)}$ where

$\mathfrak{M}^{(l)}=\begin{bmatrix}(1-\upsilon)M^{(l)}&\upsilon M^{(l)}\\\
(1-\upsilon)M^{(l)}&\upsilon M^{(l)}\end{bmatrix}.$

$\upsilon$ is fixed, so we only need to accurately estimate $M^{(l)}$. The
proof proceeds by making a suitable transformation on data.

##### Transformation.

Our objective in this transformation is to carefully isolate all those time
points $i$ where $\omega_{i}=\omega_{i-1}=1$ and use it to create our
empirical estimator. Let $D_{i}^{(2)}$ be a sequence of i.i.d. uniform random
variables distributed on $\chi$ and $D_{i}^{(3)}$ be the same on $\mathbb{I}$.
We construct a sequence of random variables $\tilde{X}_{i},\tilde{a}_{i}$ as
follows,

$\displaystyle\tilde{X}_{i}$
$\displaystyle=(1-\omega_{i})D_{i}^{(2)}+\omega_{i}X_{i}$ $\displaystyle(G1)$
$\displaystyle\tilde{a}_{i}$
$\displaystyle=(1-\omega_{i})D_{i}^{(3)}+\omega_{i}a_{i}.$ $\displaystyle(G2)$

From $(G1)$ and $(G2)$ we get,

$\displaystyle\mathbb{P}\left(\tilde{X}_{i}=t|\tilde{a}_{i-1}=l,\omega_{i}=\omega_{i-1}=1,\tilde{X}_{i-1}=s\right)$
$\displaystyle=\frac{\mathbb{P}\left(\tilde{X}_{i}=t,\tilde{X}_{i-1}=s,\tilde{a}_{i-1}=l|\omega_{i}=\omega_{i-1}=1\right)}{\mathbb{P}\left(\
\tilde{X}_{i-1}=s,\tilde{a}_{i-1}=l|\omega_{i}=\omega_{i-1}=1\right)}$
$\displaystyle=\frac{\mathbb{P}\left(X_{i}=t,X_{i-1}=s,a_{i-1}=l|\omega_{i}=\omega_{i-1}=1\right)}{\mathbb{P}\left(\
X_{i-1}=s,a_{i-1}=l|\omega_{i}=\omega_{i-1}=1\right)}$
$\displaystyle=\mathbb{P}\left(X_{i}=t|a_{i-1}=l,\omega_{i}=\omega_{i-1}=1,X_{i-1}=s\right)$
$\displaystyle=M_{s,t}^{(l)}.$ (4.11)

Therefore, the $l$-th transition probability matrix associated with
$(\tilde{X}_{i+1},\omega_{i+1})$ is

$\displaystyle\tilde{\mathfrak{M}}^{(l)}=\begin{bmatrix}(1-\upsilon)J&\upsilon
M^{(l)}\\\ (1-\upsilon)J&\upsilon M^{(l)}\end{bmatrix}$ (4.12)

where $J$ is a $d\times d$ matrix with each element $1/d$. The following lemma
holds

######  Lemma 15.

The controlled Markov chain $(Y_{i},\tilde{a}_{i})$, where
$Y_{i}:=(\tilde{X}_{i},\omega_{i})$ denotes the state at time point $i$, and
$\tilde{a}_{i}$ denotes the control, is a CMC over
$\chi\times\\{0,1\\}\times\mathbb{I}$ with ergodic transition probability
matrix $\tilde{\mathfrak{M}}^{(l)}$ for all $l\in\mathbb{I}$ and stationary
controls $\tilde{a}_{i}$.

As an immediate consequence, we apply Proposition 9 to obtain that the
$(\tilde{X}_{i},\omega_{i},\tilde{a}_{i})$ is a uniformly ergodic Markov
chain. Let $\pi$ be its stationary distribution on
$\chi\times\\{0,1\\}\times\mathbb{I}$ and for
$(s,\xi,l)\in\chi\times\\{0,1\\}\times\mathbb{I}$, let
$\pi_{\star}:=\inf_{s,\xi,l}\pi_{s,\xi,l}$. Furthermore, without losing
generality let $\upsilon<(1-\upsilon)$. Next, let $\mathbb{C}=0$,
$\mathbb{C}_{\theta}=1/\upsilon$, $T=1/\pi_{\star}$, $\zeta_{2}=1/k$,
$\zeta_{1}=1/k$, and by $\hat{\mathfrak{M}}^{(l)}$ denote the empirical
estimator for $\tilde{\mathfrak{M}}^{(l)}$. Then we have the following
theorem,

######  Theorem 3.

There exists a universal constant $c>1$, such that for any $\varepsilon>0$,
and $\delta\in(0,1)$, if

$\displaystyle
m>c\max\left\\{\frac{T}{\varepsilon^{2}}\log\left(\frac{dkT}{\varepsilon^{2}\delta}\right),\left(1+\mathbb{C}_{\theta}\right)^{2}\log\left(\frac{dk}{\delta}\right)\max\left\\{{T}^{2},\frac{1}{\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}\right\\}\right\\},$

then the empirical estimator of $\tilde{M}^{(l)}$ satisfies,

$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\left\|\hat{\mathfrak{M}}^{(l)}-\tilde{\mathfrak{M}}^{(l)}\right\|_{\infty}>\varepsilon\right)<\delta.$
(4.13)

Applying Proposition 10, the proof is straightforward. The immediate corollary
follows.

######  Corollary 1.

Let $\hat{M}^{(l)}$ be the $d\times d$ block given by rows and columns
$\\{d+1\dots,2d\\}$ of $\tilde{\mathfrak{M}}^{(l)}$. Then,

$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\left\|\frac{1}{\upsilon}\hat{M}^{(l)}-M^{(l)}\right\|_{\infty}>\varepsilon\right)<\delta,$
(4.14)

whenever

$\displaystyle
m>c\max\left\\{\frac{\upsilon^{2}T}{\varepsilon^{2}}\log\left(\frac{\upsilon^{2}dkT}{\varepsilon^{2}\delta}\right),\left(1+\mathbb{C}_{\theta}\right)^{2}\log\left(\frac{dk}{\delta}\right)\max\left\\{{T}^{2},\frac{1}{\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}\right\\}\right\\}.$

###### Proof.

The proof of this follows readily from the fact that

$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\left\|\hat{M}^{(l)}-\upsilon
M^{(l)}\right\|_{\infty}>\frac{\varepsilon}{\upsilon}\right)>\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\left\|\hat{\mathfrak{M}}^{(l)}-\tilde{\mathfrak{M}}^{(l)}\right\|_{\infty}>\frac{\varepsilon}{\upsilon}\right).$

∎

##  5 Sample Complexity of Offline Policy Evaluation

Offline policy evaluation (OPE) is a significant issue in offline RL settings,
wherein candidate policies are comparatively ‘evaluated’ by computing their
value functions (note that the policies need not be optimal). The sample
complexity results in Theorem 1 and Theorem 2 immediately yield bounds for
OPE. To be precise, we use the estimated transition probability matrices
$\hat{M}^{(l)}$ as a plugin to evaluate the value of a given stationary Markov
policy $\pi$. As observed in Section 4.2, a controlled Markov chain with
stationary controls is equivalent to a geometrically ergodic Markov chain.
Therefore, we assume without losing generality that $k=1$, and drop the
superscript from $M^{(1)}$. As in Section 4.2, we assume the Markov chain
satisfies Assumption 2 and Assumption 6, with constants $T$ and
$\mathbb{C}_{\theta}$ respectively.

We start in an abstract setting. Let
$V:=(V(x):x\in\mathcal{X})\in\mathbb{R}^{d}$ be a value function to be
computed, $0<\alpha_{dis}<1$ a known discount factor, and
$g:=(g(x):x\in\mathcal{X})\in\mathbb{R}^{d}$ is a known ‘per-stage’ cost
function. Recall that the value function $V$ is the solution of the value
function or Bellman equation [24, eq. 10],
$V=g+\alpha_{dis}MV,\leavevmode\nobreak\ $ implying that

$\displaystyle V=\left(I-\alpha_{dis}M\right)^{-1}g.$ (5.1)

Now, since $M$ is unknown, one can instead solve the Bellman equation using
$\hat{M}$ as a plug-in estimator, yielding

$\displaystyle\hat{V}=\left(I-\alpha_{dis}\hat{M}\right)^{-1}g.$ (5.2)

Observe that, for a finite state space, the cost function should satisfy
$\|g\|_{1}<\infty$, and define

$T_{\alpha}:=\frac{\left\|g\right\|_{1}^{2}d\alpha_{dis}^{2}T}{(1-\alpha_{dis})^{4}}$

The next theorem provides a sample complexity bound on estimating the value
function $V$.

######  Theorem 4.

Let $X_{0},\dots,X_{m}$ be a sample from a controlled Markov chain with
stationary controls and $V$ and $\hat{V}$ be as defined in equations 5.1 and
5.2 respectively. Then, there exists a universal constant $c>1$ such that if,

$m>c\;\max\left\\{\frac{T_{\alpha}}{\varepsilon^{2}}\log\left(\frac{dkT_{\alpha}}{\varepsilon^{2}\delta}\right),\mathbb{C}_{\theta}^{2}\max\left\\{{T_{\alpha}}^{2},\frac{1}{\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}\right\\}\log\left(\frac{dk}{\delta}\right)\right\\},$

then

$\mathbb{P}\left(\left\|\hat{V}-V\right\|>\varepsilon\right)<\delta.$

###### Proof.

The proof of this theorem can be found in Section D.4 ∎

Now, suppose $\pi:\mathcal{X}\to\Delta(\mathbb{I})$, where $\Delta$ represents
the probability simplex on the control space, is a given stochastic policy;
similar comments hold when $\pi$ is a deterministic policy. Let
$\Pi=[\pi(x,a)]$ represent the $d\times k$ ‘policy’ matrix. Let
$\tilde{g}:=(\tilde{g}(x,a):(x,a)\in\mathcal{X}\times\mathbb{I})$ be a given
cost function on the state-control space $\mathcal{X}\times\mathbb{I}$. Then,
$g$ is the per-stage expected cost function defined as
$g(x):=\sum_{a\in\mathbb{I}}\pi(x,a)\tilde{g}(x,a)$, and the value function is
given by

$\displaystyle V_{\pi}$
$\displaystyle:=\Pi\left(\tilde{g}+\alpha_{dis}MV_{\pi}\right)$
$\displaystyle=g+\alpha_{dis}\Pi MV_{\pi}.$

Similarly, define $\hat{V}_{\pi}:=g+\alpha_{dis}+\Pi\hat{M}V_{\pi}$. Then,
since $\Pi M$ is a stochastic matrix, Theorem 4 can be straightforwardly
applied yielding a sample complexity result for policy evaluation.

##  6 Conclusions

In this paper, we derive exact rates of convergence for the empirical
estimator of the transition probability matrices of a controlled Markov chain,
and used these to derive the sample complexity of achieving a desired
estimation risk. We tease out the exact effect of the mixing coefficients of
the states and controls on the sample complexity, and provide conditions under
which the empirical estimator is minimax optimal. Finally, we use our sample
complexity results on the transition matrices to derive estimation error
bounds for the value function, providing sample complexity results for policy
evaluation. There remain a plethora of unanswered questions that are possible
topics for future research. We highlight three of these below.

##### Countable state spaces.

As an obvious extension, consider the interesting problem of countably
infinite state and control spaces. Some work in this regard can be found in
[59] where state spaces are countably infinite, but there are no reasonable
extensions to the setting with countably infinite control space.

##### Uncountably infinite state space and finite controls/continuous time.

We have also found no result which derives the minimax sample complexity of
estimating the transition probability distribution of a Markov chain on an
uncountably infinite state space. The histogram estimator is the obvious
counterpart to the proportion based estimator discussed in this work. Indeed,
recent studies [48, loffler2021spectral] demonstrates promising properties of
the former. But to the best of our knowledge, the techniques do not translate
to uncountable control spaces, and optimally estimating the transition
probability distribution remains an open question. In the same note, the
extensions to a continuous time finite state controlled Markov chain is
unclear as well.

##### Learning in presence of weaker mixing or adversarial controls.

Although strong mixing properties of the controls is a sufficient condition
for the ‘estimability’ of the transition matrices, it may not be a realistic
assumption when the system dynamics are weakly mixing or adversarial [41].
Indeed, system identification under the presence of an adversary remains an
interesting question, which was addressed in a recent paper [51] using strong
linearization assumptions and exponential computation times. However, this is
well beyond the scope of the current work and is a direction for future study.

##  7 Acknowledgements

Imon Banerjee was supported in part by the Ross-Lynn fellowship at Purdue
University. Harsha Honnappa was partly supported by the National Science
Foundation through grants CAREER/2143752 and DMS/2153915. Vinayak Rao was
supported by the National Science Foundation grants RI/1816499 and
DMS/1812197. Imon Banerjee thanks Anamitra Chaudhuri for numerous insightful
discussions and comments throughout the duration of this project.

## References

  * [1] Tom M Apostol “An elementary view of Euler’s summation formula” In _The American Mathematical Monthly_ 106.5 Taylor & Francis, 1999, pp. 409–418
  * [2] Mor Armony et al. “On patient flow in hospitals: A data-based queueing-science perspective” In _Stochastic systems_ 5.1 INFORMS, 2015, pp. 146–194
  * [3] Kazuoki Azuma “Weighted sums of certain dependent random variables” In _Tohoku Mathematical Journal_ 19.3 Mathematical Institute, Tohoku University, 1967, pp. 357–367
  * [4] Imon Banerjee, Vinayak A Rao and Harsha Honnappa “PAC-Bayes Bounds on Variational Tempered Posteriors for Markov Models” In _Entropy_ 23.3 MDPI, 2021, pp. 313
  * [5] Carolyn L Beck and Rayadurgam Srikant “Error bounds for constant step-size Q-learning” In _Systems & control letters_ 61.12 Elsevier, 2012, pp. 1203–1208
  * [6] Patrick Billingsley “Statistical methods in Markov chains” In _The Annals of Mathematical Statistics_ JSTOR, 1961, pp. 12–40
  * [7] Vivek S Borkar “Topics in controlled Markov chains” Longman Scientific & Technical Harlow, 1991
  * [8] Richard C Bradley “Basic Properties of Strong Mixing Conditions. A Survey and Some Open Questions” In _Probab. Surveys_ 2 ”The Institute of Mathematical Statisticsthe Bernoulli Society”, 2005, pp. 107–144 DOI: 10.1214/154957805100000104
  * [9] Ann Cohen Brandwein and William E Strawderman “Minimax estimation of location parameters for spherically symmetric distributions with concave loss” In _The Annals of Statistics_ 8.2 Institute of Mathematical Statistics, 1980, pp. 279–284
  * [10] David Alexander Brannan “A first course in mathematical analysis” Cambridge University Press, 2006
  * [11] Irene Y Chen, Shalmali Joshi, Marzyeh Ghassemi and Rajesh Ranganath “Probabilistic machine learning for healthcare” In _Annual Review of Biomedical Data Science_ 4 Annual Reviews, 2021, pp. 393–415
  * [12] Robert Chin et al. “Active learning for linear parameter-varying system identification” In _IFAC-PapersOnLine_ 53.2 Elsevier, 2020, pp. 989–994
  * [13] Jim G Dai and Mark Gluzman “Queueing network controls via deep reinforcement learning” In _Stochastic Systems_ 12.1 INFORMS, 2022, pp. 30–67
  * [14] Roland L Dobrushin “Central limit theorem for nonstationary Markov chains. I” In _Theory of Probability & Its Applications_ 1.1 SIAM, 1956, pp. 65–80
  * [15] Roland L’vovich Dobrushin “Central limit theorem for nonstationary Markov chains. II” In _Theory of Probability & Its Applications_ 1.4 SIAM, 1956, pp. 329–383
  * [16] Constance Eeden “Minimax estimators and their admissibility” In _Restricted Parameter Space Estimation Problems: Admissibility and Minimaxity Properties_ Springer, 2006, pp. 33–67
  * [17] Dominique Fourdrinier, Fatiha Mezoued and William E Strawderman “Bayes minimax estimation under power priors of location parameters for a wide class of spherically symmetric distributions” In _Electronic Journal of Statistics_ 7 Institute of Mathematical StatisticsBernoulli Society, 2013, pp. 717–741
  * [18] Charles J Geyer “Markov chain Monte Carlo lecture notes” In _Course notes, Spring Quarter_ 80, 1998
  * [19] BK Ghosh “Probability inequalities related to Markov’s theorem” In _The American Statistician_ 56.3 Taylor & Francis, 2002, pp. 186–190
  * [20] Allan Gut and Allan Gut “Probability: a graduate course” Springer, 2005
  * [21] John Hajnal and Maurice S Bartlett “Weak ergodicity in non-homogeneous Markov chains” In _Mathematical Proceedings of the Cambridge Philosophical Society_ 54, 1958, pp. 233–246 Cambridge University Press
  * [22] Peter Hall and Christopher C Heyde “Martingale limit theory and its application” Academic press, 2014
  * [23] Galin L Jones “On the Markov chain central limit theorem” In _Probability surveys_ 1 Institute of Mathematical StatisticsBernoulli Society, 2004, pp. 299–320
  * [24] Sanyam Kapoor “Multi-agent reinforcement learning: A report on challenges and approaches” In _arXiv preprint arXiv:1807.09427_ , 2018
  * [25] Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli and Thorsten Joachims “Morel: Model-based offline reinforcement learning” In _Advances in neural information processing systems_ 33, 2020, pp. 21810–21823
  * [26] Leonid Aryeh Kontorovich and Kavita Ramanan “Concentration inequalities for dependent random variables via the martingale method” In _Annals of Probability_ 36.6 Institute of Mathematical Statistics, 2008, pp. 2126–2158
  * [27] Volodymyr Kuleshov and Doina Precup “Algorithms for multi-armed bandit problems” In _arXiv preprint arXiv:1402.6028_ , 2014
  * [28] Erich L Lehmann and George Casella “Theory of point estimation” Springer Science & Business Media, 2006
  * [29] Sergey Levine, Aviral Kumar, George Tucker and Justin Fu “Offline reinforcement learning: Tutorial, review, and perspectives on open problems” In _arXiv preprint arXiv:2005.01643_ , 2020
  * [30] Gen Li et al. “Settling the sample complexity of model-based offline reinforcement learning” In _arXiv preprint arXiv:2204.05275_ , 2022
  * [31] Yuanzhi Li, Ruosong Wang and Lin F Yang “Settling the horizon-dependence of sample complexity in reinforcement learning” In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 965–976 IEEE
  * [32] Siqi Liu et al. “Reinforcement learning for clinical decision support in critical care: comprehensive review” In _Journal of medical Internet research_ 22.7 JMIR Publications Inc., Toronto, Canada, 2020, pp. e18477
  * [33] Yahui Liu, Buyang Cao and Hehua Li “Improving ant colony optimization algorithm with epsilon greedy and Levy flight” In _Complex & Intelligent Systems_ 7.4 Springer, 2021, pp. 1711–1722
  * [34] Lennart Ljung “Perspectives on system identification” In _Annual Reviews in Control_ 34.1 Elsevier, 2010, pp. 1–12
  * [35] Horia Mania, Michael I Jordan and Benjamin Recht “Active learning for nonlinear system identification with guarantees” In _arXiv preprint arXiv:2006.10277_ , 2020
  * [36] Shie Mannor and John N Tsitsiklis “On the empirical state-action frequencies in Markov decision processes under general policies” In _Mathematics of Operations Research_ 30.3 INFORMS, 2005, pp. 545–561
  * [37] Florence Merlevède, Magda Peligrad and Emmanuel Rio “Bernstein inequality and moderate deviations under strong mixing conditions” In _High dimensional probability V: the Luminy volume_ 5, 2009, pp. 273–292
  * [38] Sean P Meyn and Richard L Tweedie “Markov chains and stochastic stability” Springer Science & Business Media, 2012
  * [39] Farrukh Mukhamedov “The Dobrushin ergodicity coefficient and the ergodicity of noncommutative Markov chains” In _Journal of Mathematical Analysis and Applications_ 408.1 Elsevier, 2013, pp. 364–373
  * [40] Mirco Mutti, Riccardo De Santi and Marcello Restelli “The Importance of Non-Markovianity in Maximum State Entropy Exploration” In _arXiv preprint arXiv:2202.03060_ , 2022
  * [41] Lerrel Pinto, James Davidson, Rahul Sukthankar and Abhinav Gupta “Robust adversarial reinforcement learning” In _International Conference on Machine Learning_ , 2017, pp. 2817–2826 PMLR
  * [42] Paria Rashidinejad et al. “Bridging offline reinforcement learning and imitation learning: A tale of pessimism” In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 11702–11716
  * [43] Tirthankar RayChaudhuri and Leonard GC Hamey “Active learning for nonlinear system identification and control” In _IFAC Proceedings Volumes_ 29.1 Elsevier, 1996, pp. 2592–2596
  * [44] Emmanuel Rio “On McDiarmid’s concentration inequality” In _Electronic Communications in Probability_ 18 Institute of Mathematical StatisticsBernoulli Society, 2013, pp. 1–11
  * [45] M Rosenblatt-Roth “Some theorems concerning the law of large numbers for non-homogeneous Markoff chains” In _Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete_ 1.5 Springer, 1963, pp. 433–445
  * [46] M Rosenblatt-Roth “Some theorems concerning the strong law of large numbers for non-homogeneous Markov chains” In _The Annals of Mathematical Statistics_ 35.2 JSTOR, 1964, pp. 566–576
  * [47] Jeffrey S Rosenthal “Minorization conditions and convergence rates for Markov chain Monte Carlo” In _Journal of the American Statistical Association_ 90.430 Taylor & Francis, 1995, pp. 558–566
  * [48] Mathieu Sart “Estimation of the transition density of a Markov chain” In _Annales de l’IHP Probabilités et statistiques_ 50.3, 2014, pp. 1028–1068
  * [49] Laixi Shi et al. “Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity” In _arXiv preprint arXiv:2202.13890_ , 2022
  * [50] Susan M Shortreed et al. “Informing sequential clinical decision-making through reinforcement learning: an empirical study” In _Machine learning_ 84.1 Springer, 2011, pp. 109–136
  * [51] Mehrdad Showkatbakhsh, Paulo Tabuada and Suhas Diggavi “System identification in the presence of adversarial outputs” In _2016 IEEE 55th Conference on Decision and Control (CDC)_ , 2016, pp. 7177–7182 IEEE
  * [52] Richard S Sutton and Andrew G Barto “Reinforcement learning: An introduction” MIT press, 2018
  * [53] Arun K Tangirala “Principles of system identification: theory and practice” Crc Press, 2018
  * [54] Alexandre B Tsybakov “Introduction to Nonparametric Estimation.” In _Springer series in statistics_ Springer, 2009, pp. I–XII
  * [55] Jacobus Hendricus Van Lint “Introduction to coding theory” Springer Science & Business Media, 2012
  * [56] Roman Vershynin “High-dimensional probability: An introduction with applications in data science” Cambridge university press, 2018
  * [57] Mathukumalli Vidyasagar and Rajeeva L Karandikar “A learning theory approach to system identification and stochastic adaptive control” In _Probabilistic and randomized methods for design under uncertainty_ Springer, 2006, pp. 265–302
  * [58] Yimin Wei, Yanhua Cao and Hua Xiang “A note on the componentwise perturbation bounds of matrix inverse and linear systems” In _Applied mathematics and computation_ 169.2 Elsevier, 2005, pp. 1221–1236
  * [59] Geoffrey Wolfer and Aryeh Kontorovich “Statistical estimation of ergodic Markov chain kernel over discrete state space” In _Bernoulli_ 27.1 Bernoulli Society for Mathematical StatisticsProbability, 2021, pp. 532–553
  * [60] Jacob Wolfowitz “Products of indecomposable, aperiodic, stochastic matrices” In _Proceedings of the American Mathematical Society_ 14.5 JSTOR, 1963, pp. 733–737
  * [61] Michael Wunder, Michael L Littman and Monica Babes “Classes of multiagent q-learning dynamics with epsilon-greedy exploration” In _ICML_ , 2010
  * [62] Sidney Yakowitz “Nonparametric density and regression estimation for Markov sequences without mixing assumptions” In _Journal of Multivariate Analysis_ 30.1 Elsevier, 1989, pp. 124–136
  * [63] Sidney Yakowitz “Nonparametric estimation of Markov transition functions” In _The Annals of Statistics_ JSTOR, 1979, pp. 671–679
  * [64] Yuling Yan, Gen Li, Yuxin Chen and Jianqing Fan “Model-Based Reinforcement Learning Is Minimax-Optimal for Offline Zero-Sum Markov Games” In _arXiv preprint arXiv:2206.04044_ , 2022
  * [65] Ming Yin and Yu-Xiang Wang “Towards instance-optimal offline reinforcement learning with pessimism” In _Advances in neural information processing systems_ 34, 2021, pp. 4065–4078
  * [66] Chao Yu, Jiming Liu, Shamim Nemati and Guosheng Yin “Reinforcement learning in healthcare: A survey” In _ACM Computing Surveys (CSUR)_ 55.1 ACM New York, NY, 2021, pp. 1–36
  * [67] Huizhen Yu and Dimitri P Bertsekas “On boundedness of Q-learning iterates for stochastic shortest path problems” In _Mathematics of Operations Research_ 38.2 INFORMS, 2013, pp. 209–227
  * [68] Huizhen Yu and Dimitri P Bertsekas “Q-learning and policy iteration algorithms for stochastic shortest path problems” In _Annals of Operations Research_ 208.1 Springer, 2013, pp. 95–132
  * [69] Tianhe Yu et al. “Mopo: Model-based offline policy optimization” In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 14129–14142
  * [70] Fuzhen Zhang “Matrix theory: basic results and techniques” Springer, 2011

ljung1987theory loffler2021spectral

##  Appendix A Technical Desiderata

###  A.1 Concentration Inequalities

##### Hoeffding’s concentration inequality for mixing sequences.

For two sequences of real numbers $\tilde{x}=\\{x_{0},\dots,x_{m}\\}$ and
$\tilde{y}=\\{y_{0},\dots,y_{m}\\}$, define the Hamming metric $d$ between
them as $d(\tilde{x},\tilde{y}):=\sum_{i}\mathbbm{1}[x_{i}\neq y_{i}]$.
Observe that for any two sequences $\tilde{x}$ and $\tilde{y}$ we have,

$\displaystyle|N_{s}(\tilde{x})-N_{s}(\tilde{y})|$
$\displaystyle=\left|\sum_{i=1}^{m}\mathbbm{1}[x_{i}=s]-\sum_{i=1}^{m}\mathbbm{1}[y_{i}=s]\right|$
$\displaystyle\leq\sum_{i=1}^{m}\left|\mathbbm{1}[x_{i}=s]-\mathbbm{1}[y_{i}=s]\right|$
$\displaystyle\leq\sum_{i=1}^{m}\mathbbm{1}[x_{i}\neq
y_{i}]=d(\tilde{x},\tilde{y}).$

Therefore, the function $N_{s}(\tilde{x}):=\sum_{i=1}^{m}\mathbbm{1}[x_{i}=s]$
is $1$-Lipschitz in Hamming metric. This allows us to specialise Theorem 1.1
from [26] to our current setting.

######  Lemma 16.

Let $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ be a sequence of
stochastic random variables on a finite state space $\chi\times\mathbb{I}$.
Then, for any $t>0$ we have,

$\displaystyle\mathbb{P}(|N_{s}^{(l)}-\mathbb{E}[N_{s}^{(l)}]|>t)\leq
2\exp\left(-\frac{t^{2}}{2m\|\Delta_{m}\|^{2}}\right),$ (A.1)

where $\|\Delta_{m}\|=\underset{1\leq i\leq
m}{\max}(1+\bar{\eta}_{i,i+1}+\bar{\eta}_{i,i+2}+\dots\bar{\eta}_{i,m})$, and
$\bar{\eta}_{i,j}$ is as defined in eq. 2.1.

######  Remark.

It is clear that analysing the tail properties of $N_{s}^{(l)}$ requires an
appropriate concentration inequality. The result from [26], as recalled in
Lemma 16 is a refinement of the celebrated Azuma-Hoeffding’s inequality [3]
where the martingale differences are linked to the underlying mixing
coefficients of the stochastic process. Observe that the inequality is
guaranteed to be as tight as Azuma-Hoeffding’s inequality [26, Theorem 7.5].
However, as we discuss is Remark Remark, it is not tight enough to achieve
minimaxity.

##### Chernoff’s concentration inequality for geometrically mixing sequences.

We begin this subsection with the following lemma.

######  Lemma 17.

For some $i,j$, let $T_{\star}\in\left\\{0,1\right\\}^{m-j}$ and
$\hbar_{\star}\in\left\\{0,1\right\\}^{i+1}$. For the convenience of notation,
denote $\left(\mathbbm{1}[X_{i},a_{i}],\dots\mathbbm{1}[X_{0},a_{0}]\right)$
by $\mathbbm{1}(\mathcal{H}_{0}^{i})$. Observe that

$\displaystyle\phi_{i,j}$
$\displaystyle=\sup_{\begin{subarray}{c}\mathbb{T},\hbar_{0}^{i-1}\end{subarray}}\left|\mathbb{P}\left((X_{m},a_{m},\dots,X_{j},a_{j})\in\mathbb{T}|\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathbb{P}\left(X_{m},a_{m},\dots,X_{j},a_{j}\in\mathbb{T}\right)\right|$
$\displaystyle\geq\sup_{\begin{subarray}{c}\mathbb{T}_{\star},\hbar_{\star}\end{subarray}}\left|\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\mathbb{T}_{\star}|\mathbbm{1}\left(\mathcal{H}_{0}^{i}\right)=\hbar_{\star}\right)\right.$
$\displaystyle\quad\left.-\mathbb{P}\left(\mathbbm{1}[X_{m}=s,a_{m}=l],\dots,\mathbbm{1}[X_{j}=s,a_{j}=l])\in\mathbb{T}_{\star}\right)\right|.$

######  Remark.

The uniform mixing coefficients of random variables form an upper bound to the
uniform mixing sequences of the indicator functions of the same random
variables.

Using the aforementioned fact, we specialise Theorem 2 from [37]. As in the
proof of Proposition 6, we drop s and l, and denote
$\mathbbm{1}[X_{i}=s,a_{i}=l]$ by $I_{i}$. Then we have the following lemma.

######  Lemma 18.

Let $(X_{m},a_{m},\dots,X_{0},a_{0})$ be a sequence of stochastic random
variables on a finite state space $\chi\times\mathbb{I}$. Assume that there
exists a positive constant $c_{cof}>0$ such that the uniform mixing
coefficient $\phi_{i,j}$ satisfies

$\sup_{j-i}\phi_{i,j}\leq e^{-c_{cof}(j-1)}.$

Then, there exists a constant $\mathbb{C}_{pel}$ which depends only upon
$c_{cof}$ such that for all $m\geq 2$

$\mathbb{P}\left(\left|N_{s}^{(l)}-\mathbb{E}[N_{s}^{(l)}]\right|\geq
t\right)\leq\exp\left(-\frac{\mathbb{C}_{pel}t^{2}}{m\sup_{i\geq
0}\left(\mathrm{Var}(I_{i})+2\sum_{j\geq
i}|\mathrm{Cov}(I_{i},I_{j})|\right)+1+t(\log m)^{2}}\right)$ (A.2)

###### Proof.

The proof follows from [37, eqn. 2.1] by observing from [8, eqn. 1.12 ] that
uniform mixing coefficients form a natural upper bound to strong mixing
coefficients (defined as in [8, eqn. 1.1 ]), and then observing that for
indicator variables $M=1$. ∎

######  Remark.

This gives us a cleaner version of the original inequality appropriated to our
current setup.

######  Lemma 19.

Let $X,Y,$ and $Z$ be 3 discrete random variables in the sample space
$\Omega$. Then

$\displaystyle\lVert\mathcal{L}(X,Y|Z=z_{1})$
$\displaystyle-\mathcal{L}(X,Y|Z=z_{2})\rVert_{TV}\leq\lVert\mathcal{L}(Y|z=z_{1})-\mathcal{L}(Y|Z=z_{2})\rVert_{TV}$
$\displaystyle\qquad+\sup_{y}\lVert\mathcal{L}(X|Y=y,Z=z_{1})-\mathcal{L}(X|Y=y,Z=z_{2})\rVert_{TV}.$

Two finite-state Markov chains are of the same _type_ if their transition
matrices have zeros in the same entries. The following lemma is found in [60,
Theorem 1 ].

######  Lemma 20.

Suppose that $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ is a sample
from a time-inhomogeneous Markov chain. Then $\bar{\theta}_{i,j}\leq
e^{-\upsilon|j-i|}$, where $\upsilon$ is a constant depending only on the
number of types of matrices in the set $\mathbb{M}$.

As a follow-up remark, we note from [60] that whether a transition matrix
belongs to an ergodic and irreducible Markov chain depends solely on the type.
The following lemma extends the previous one to the case of controlled Markov
chains with non-stationary Markov controls.

######  Lemma 21.

Let $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ be a sample from a
controlled Markov chain with transition matrices $M^{(l)}$ and Markov controls
such that for any $s\in\chi$,$l\in\mathbb{I}$,
$\hbar_{0}^{i-1}\in(\chi\times\mathbb{I})^{i-1}$ and
$i\in\mathbb{N}\cup\\{0\\}$,

$P_{s,l}^{(i)}:=\mathbb{P}\left[a_{i}=l\,|\,X_{i}=s,\mathcal{H}_{0}^{i-1}=\hbar_{0}^{i-1}\right]=\mathbb{P}\left[a_{i}=l\,|\,X_{i}=s\right].$

If there exists a $\chi_{0}\subseteq\chi$ and $M_{min>0}$ such that,

$\min_{s\in\chi,l\in\mathbb{I}}M_{s,t}^{(l)}\geq M_{min},\quad\forall\
t\in\chi_{0},$

then, for this controlled Markov chain,

$\bar{\theta}_{i,j}\leq\left(1-|\chi_{0}|M_{min}\right)^{j-i-1}.$

As a consequence, this CMC satisfies 6 with
$\mathbb{C}_{\theta}=1/(1-|\chi_{0}|M_{min})$.

######  Remark.

If the number of types of matrices is independent of $k$, observe it follows
from Lemma 20 that there exists a class of Inhomogenous Markov chains for
which $c_{cof}$ is independent of the parameters of the Markov chain, where
the definition of $c_{cof}$ is as in Lemma 18. This naturally implies that
$\mathbb{C}_{pel}$ is a universal constant for that class.

Furthermore, it can be derived from Lemma 21 that whenever
$\|\chi_{0}\|M_{min}$ is independent of $d,k$ there exists a CMC with non-
stationary Markov controls, which satisfy a similar property.

######  Lemma 22.

Let $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ be a sample from a
controlled Markov chain belonging to the class of CMC’s as defined in section
D.3. Then, $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ satisfies
Assumptions 1,2,5, and 6.

###### Proof.

This controlled Markov chain has only $1$ control with the corresponding
transition matrix positive. Therefore, it is irreducible and aperiodic [38,
Proposition 8.1.1] and therefore, corresponds to a geometrically ergodic
Markov chain [38, Theorem 15.0.1]. The rest of the proof follows similarly to
the proof of Proposition 10. ∎

######  Lemma 23.

Let $(X_{i},a_{i})$ be an inhomogenous Markov chain with
$\chi=\left\\{1,2,4,5\right\\}$ and $\mathbb{I}=\left\\{1,2\right\\}$ such
that $\mathbb{P}(a_{0}=1)=1$, $\mathbb{P}(a_{1}=2)=1$, $\mathbb{P}(a_{2}=1)=1$
and so on. Moreover, $a_{i}$ depends only upon time point $i$ and is
independent of $(X_{i},\mathcal{H}_{0}^{i-1})$. The transition matrices are
given by

$\displaystyle M^{(1)}=\begin{bmatrix}1/2&1/2&0&0\\\ 1/2&1/2&0&0\\\
0&0&1/2&1/2\\\ 0&0&1/2&1/2\\\ \end{bmatrix}$ $\displaystyle\textit{ and
}M^{(2)}=\begin{bmatrix}0&0&1/2&1/2\\\ 0&0&1/2&1/2\\\ 1/2&1/2&0&0\\\
1/2&1/2&0&0\\\ \end{bmatrix}.$

$X_{0}$ is drawn uniformly from $\\{1,2,3,4\\}$. Then, for this inhomogenous
Markov chain $\bar{\theta}_{i,j}=1$ for any time points $j>i$.

###### Proof.

We observe that

$\bar{\theta}_{i,i+1}=\underset{\begin{subarray}{c}s_{1},s_{2}\in\chi,l_{1},l_{2}\in\mathbb{I},\\\
\mathbb{P}(X_{i}=s_{1},a_{i}=l_{1})>0,\\\
\mathbb{P}(X_{i}=s_{2},a_{i}=l_{2})>0\end{subarray}}{\sup}\|\mathcal{L}\left(X_{j}|X_{i}=s_{1},a_{i}=l_{1}\right)-\mathcal{L}\left(X_{j}|X_{i}=s_{2},a_{i}=l_{2}\right)\|_{TV}$

is only well-defined if $l_{1}=l_{2}$. Let $s_{1}=1$, and $s_{2}=3$. Then,

$\displaystyle\bar{\theta}_{i,i+1}\geq|\mathbb{P}\left(X_{j}\in\\{1,2\\}|X_{i}=1,a_{i}=l_{1}\right)-\mathbb{P}\left(X_{j}\in\\{1,2\\}|X_{i}=3,a_{i}=l_{1}\right)|=1.$

Thus, $\bar{\theta}_{i,i+1}=1$. Similarly, $\bar{\theta}_{i,i+1}=1$ for any
$j>i$ and

$\sup_{1\leq i\leq\infty}\sum_{j=i+1}^{\infty}\bar{\theta}_{i,j}=\infty.$

∎

##  Appendix B Minimaxity Example

That uniform distribution is the least favourable choice for estimation
purposes are well studies both in frequentist and in Bayesian statistics, and
can be found in [9, Section 3.2 ], [16], [28, page 340-342, example 3.4 ], and
[17]. Consequently, the controlled Markov chain which we use to prove
minimaxity of the empirical estimator closely mirrors an uniform distribution.

Let $\iota$ be a fixed real number between $0$ and $31/64$ and furthermore,
let $d$ be an integer divisible by 3. Consider a class of Markov decision
processes with $\chi=\\{1,\dots,d\\}$ and
$\mathbb{I}=\left\\{1,\dots,k+1\right\\}$ such that the sequence of controls
$a_{i}$ satisfies,

$\displaystyle a_{i}=l\text{ with probability }\frac{1}{k}\ \forall\
l\in\mathbb{I}$ (B.1)

Our next step is to construct the transition probability matrices. $\square$

Transition Matrices . Let $\iota$ be a fixed real number between $0$ and $1$
and for each $l\in\\{1,\dots,k\\}$, let
$\xi^{(l)}=(\xi_{1}^{(l)},\dots,\xi_{d/3}^{(l)})$ be some vector in
$\left\\{0,1\right\\}^{d/3}$. For convenience, assume that
$\xi^{(l)}\neq(0,\dots,0)$ for at least some $l\in\mathbb{I}$. Then the $l$-th
transition probability matrix $M_{\iota,\xi^{(l)}}^{(l)}$ is a block matrix
such that

$M_{\iota,\xi^{(l)}}^{(l)}=\begin{bmatrix}\boldsymbol{C}_{\iota}&\boldsymbol{R}_{\xi^{(l)}}\\\
\boldsymbol{J}_{\iota}&\boldsymbol{L}_{\iota}\end{bmatrix},$ (B.2)

where the blocks $\boldsymbol{C}_{\iota}\in\mathbb{R}^{d/3\times d/3}$,
$\boldsymbol{L}_{\iota}\in\mathbb{R}^{2d/3\times 2d/3}$,
$\boldsymbol{J}_{\iota}\in\mathbb{R}^{2d/3\times d/3}$, and
$\boldsymbol{R}_{\xi^{(l)}}\in\mathbb{R}^{d/3\times 2d/3}$ are given by

$\displaystyle\boldsymbol{L}_{\iota}=\operatorname{diag}\left(1-\iota,1-\iota,\dots,1-\iota\right),$
$\displaystyle\boldsymbol{R}_{\xi^{(l)}}=\frac{1}{2}\begin{bmatrix}1+\xi^{(l)}_{1}\varepsilon-2\iota&1-\xi^{(l)}_{1}\varepsilon-2\iota&\frac{3\iota}{d-3}&\frac{3\iota}{d-3}&\ldots&\frac{3\iota}{d-3}\\\
\frac{3\iota}{d-3}&\frac{3\iota}{d-3}&1+\xi^{(l)}_{2}\varepsilon-2\iota&1-\xi^{(l)}_{2}\varepsilon-2\iota&\ldots&\frac{3\iota}{d-3}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
\frac{3\iota}{d-3}&\ldots&\ldots&\ldots&1+\xi^{(l)}_{d/3}\varepsilon-2\iota&1-\xi^{(l)}_{d/3}\varepsilon-2\iota\\\
\end{bmatrix},$

and, $\boldsymbol{C}_{\iota}$ and $\boldsymbol{J}_{\iota}$ are matrices with
every element equal to $3\iota/d$. It can be verified by summing over the rows
that for each $l$, $M_{\iota,\xi^{(l)}}^{(l)}$ is a valid transition
probability matrix. We get the following lemma:

######  Lemma 24.

The stationary distribution of a Markov chain with transition probability
matrix $M_{\iota,\xi^{(l)}}^{(l)}$ is a block vector
$\Pi^{(l,\iota,\xi^{(l)})}:=\left[\Pi^{(\iota)}_{1},\Pi_{2}^{(l,\iota,\xi^{(l)})}\right]$
where $\Pi_{1}^{(\iota)}$ is a row vector of length $d/3$ and every element
$3\iota/d$. Furthermore,

$\displaystyle\Pi_{2}^{(l,\iota,\xi^{(l)})}=\left(\frac{3(1+\xi_{1}^{(l)}\varepsilon-\iota)}{2d},\frac{3(1-\xi_{1}^{(l)}\varepsilon-\iota)}{2d},\dots,\frac{3(1-\xi_{d/3}^{(l)}\varepsilon-\iota)}{2d}\right).$

The proof follows by verifying
$\Pi^{(l,\iota,\xi^{(l)})}M_{\iota,\xi^{(l)}}^{(l)}=\Pi^{(l,\iota,\xi^{(l)})}$
and is straightforward. Therefore, we omit it.

######  Proposition 25.

Let $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$ be a sample from a
controlled Markov chain with controls given by eq. B.1, transition probability
matrices given by eq. B.2, and initial distribution
$\Pi=\frac{1}{k}\left(\Pi^{(1,\iota,\xi^{(1)})},\dots,\Pi^{(k,\iota,\xi^{(k)})}\right)$.
Then, it satisfies Assumptions 1 with $\zeta_{1}=\zeta_{2}=\iota$, 2 with
$T=2dk/3\iota$, and 7-8 with $\mathbb{C}_{\star}$ and
$\mathbb{C}_{\theta,\star}$ independent of $d,k$ or $\xi^{(l)}$ for any
$l\in\mathbb{I}$. Furthermore, for this controlled Markov chain,
$\rho_{\star}=3(1-\iota)/2dk$ where $\rho_{\star}$ is defined as in Theorem 2.

###### Proof.

It is obvious that the state-control pair $(X_{i},a_{i})$ is a Markov chain
with transition probability matrix given by the block matrix

$\displaystyle\frac{1}{k}\begin{bmatrix}M_{\iota,\xi^{(1)}}^{(1)}&\dots&M_{\iota,\xi^{(k)}}^{(k)}\\\
\vdots&\vdots&\vdots\\\
M_{\iota,\xi^{(1)}}^{(1)}&\dots&M_{\iota,\xi^{(k)}}^{(k)}\end{bmatrix}.$

Taking
$\mathcal{S}_{i}=\left\\{(1,1),\dots,(d/3,1),(2,1),\dots,(d/3,k)\right\\}$, we
can immediately see that 1 is satisfied with $\zeta_{1}=\zeta_{2}=\iota$.
Next, let $\Pi$ be the stationary distribution of this Markov chain. Recall
from the proof of Proposition 10 that any controlled Markov chain with
stationary Markov controls satisfies 2 with $T$ to be the supremum of the
inverse of its stationary probabilities. In other words,

$T=\sup_{s,l}\frac{1}{\Pi_{s,l}}.$

We simply verify that $\Pi_{s,l}>3\iota/2dk$ for any
$(s,l)\in\chi\times\mathbb{I}$. It is known from Lemma 24 that
$\Pi^{(l,\iota,\xi^{(l)})}$ is the stationary distribution of
$M_{\iota,\xi^{(l)}}^{(l)}$. Using this fact, it can be easily verified that
the stationary distribution of the paired process $(X_{i},a_{i})$ is given by

$\Pi=\frac{1}{k}\left(\Pi^{(1,\iota,\xi^{(1)})},\dots,\Pi^{(k,\iota,\xi^{(k)})}\right).$

Recall from hypothesis that $\varepsilon<1/32$. This implies that, for any
$\xi\in\left\\{0,1\right\\}$

$1-\xi\varepsilon-\iota>31/32-\iota>\iota$

whenever $\iota<31/64$. Thus,

$\frac{3(1-\xi\varepsilon-\iota)}{2dk}>\frac{3\iota}{2dk}$

Obviously, $3\iota/dk>3\iota/2dk$. Thus, $\Pi_{s,l}>3\iota/2dk$ for any pair
$(s,l)\in\chi\times\mathbb{I}$. As a consequence, since $\\{X_{i},a_{i}\\}$ is
a stationary Markov chain, it follows that the marginal probabilities

$\mathbb{P}(X_{i}=s,a_{i}=l)={\Pi_{s,l}}<\frac{3(1-\xi\varepsilon-\iota)}{2dk}<\frac{3(1-\iota)}{2dk}.$

This establishes that $\rho_{\star}=3(1-\iota)/2dk$. Next, because $a_{i}$’s
are distributed uniformly over $\mathbb{I}$, it is obvious that

$\displaystyle\gamma_{p,j,i}$
$\displaystyle=\sup_{s_{p},\hbar_{i+j}^{p-1},\hbar_{0}^{i}}\left\|\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1},\mathcal{H}_{0}^{i}=\hbar_{0}^{i}\right)-\mathcal{L}\left(a_{p}|X_{p}=s_{p},\mathcal{H}_{i+j}^{p-1}=\hbar_{i+j}^{p-1}\right)\right\|_{TV}$
$\displaystyle=0.$

Consequently, we get that $\mathbb{C}_{\star}$ is independent of
$d,k,\xi^{(l)}$ and $\mathbb{C}=0$, where $l\in\mathbb{I}$. Finally, observe
that every controlled Markov chain with stationary controls is also trivially
a CMC with non-stationary Markov controls. Therefore, we can use Lemma 21 with
$\chi_{0}=(1,\dots,d/3)$, and $M_{min}=3\iota/d$ to see that

$\bar{\theta}_{i,j}\leq\left(1-\frac{d}{3}\frac{3\iota}{d}\right)^{j-i-1}=(1-\iota)^{j-i-1},$

Consequently, we get that $\mathbb{C}_{\star}$ is independent of
$d,k,\xi^{(l)}$ and $\mathbb{C}_{\theta}=1-\iota$, where $l\in\mathbb{I}$.
This proves our claims. ∎

##  Appendix C The controlled Markov chain Sampling Scheme

For each $l\in\mathbb{I}$ and $M^{(l)}\in\mathbb{M}$, create the following
infinite array of i.i.d random variables which are also _independent_ of the
data $\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}$.

$\displaystyle\mathbb{X}^{(l)}:\begin{array}[]{ccccc}X_{1,1}^{(l)}&X_{1,2}^{(l)}&\dots&X_{1,\tau}^{(l)}&\dots\\\
X_{2,1}^{(l)}&X_{2,2}^{(l)}&\dots&X_{2,\tau}^{(l)}&\dots\\\
\dots&\dots&\dots&\dots&\dots\\\
X_{d,1}^{(l)}&X_{d,2}^{(l)}&\dots&X_{d,\tau}^{(l)}&\dots\end{array}$ (C.5)

where,
$\forall\enspace(s,t,\tau)\in\\{1,\dots,d\\}\times\\{1,\dots,d\\}\times\mathbb{N}$,
the random variables $X_{s,\tau}^{(l)}$ follow the mass function given by
$\mathbb{P}(X_{s,\tau}^{(l)}=t)=M_{s,t}^{(l)}$. Moreover, for every time point
$i\geq 1$, and
$(s_{0},l_{0},\dots,s_{i-1},l_{i-1},s_{i})\in(\chi\times\mathbb{I})^{i-1}\times\chi$,
let, $\alpha_{i}^{(s_{0},l_{0},\dots,s_{i-1},l_{i-1},s_{i})}$ be independent
random variables with support $\mathbb{I}$ and mass function given by,

$\displaystyle\mathbb{P}(\alpha_{i}^{(s_{0},l_{0},\dots,s_{i-1},l_{i-1},s_{i})}=l)$
$\displaystyle=\mathbb{P}(a_{i}=l|X_{i}=s_{i},\mathcal{H}_{0}^{i-1}=s_{0},l_{0},\dots,s_{i-1},l_{i-1})$
$\displaystyle=:P_{l}^{(s_{0},l_{0},\dots,s_{i-1},l_{i-1},s_{i})}.$

The sampling scheme runs as follows: sample $\tilde{X_{0}}\sim D_{0}$ and set
$\tilde{a}_{0}\overset{d}{=}a_{0}$. Recursively sample
$\tilde{X}_{i+1}=X_{\tilde{X_{i}},\tilde{N}_{\tilde{X_{i}}}^{(i,\tilde{a}_{i})}+1}^{(\tilde{a}_{i})}$
from the array $\mathbb{X}^{(\tilde{a}_{i})}$ and
$\tilde{a}_{i+1}{=}\alpha_{i+1}^{(\tilde{X}_{0},\tilde{a_{0}},\dots,\tilde{X}_{i+1})}$,
where each $i\geq 0$, define $\tilde{N}_{s}^{(i,l)}:=\underset{j\leq
i}{\sum}\mathbbm{1}[\tilde{X}_{j}=s,\tilde{a}_{j}=l]$ and
$\tilde{N}_{s}^{(m,l_{m})}=\tilde{N}_{s}^{(l_{m})}$. This completes the
sampling scheme.

######  Proposition 26.

$\left(X_{0},a_{0},\dots,X_{m},a_{m}\right)$ is identically distributed to
$\left(\tilde{X}_{0},\tilde{a}_{0},\dots,\tilde{X}_{m},\tilde{a}_{m}\right)$.

###### Proof.

Using induction, the proof is straightforward and can be found in Section
F.12. ∎

##  Appendix D Proofs of Theorems

###  D.1 Proof of Theorem 1 (Sample Complexity)

###### Proof.

We start by analysing the event
$\left\\{\underset{l\in\mathbb{I}}{\sup}\|\hat{M}^{(l)}-M^{(l)}\|_{\infty}>\varepsilon\right\\}$.
We note that if
$\underset{l\in\mathbb{I}}{\sup}\|\hat{M}^{(l)}-M^{(l)}\|_{\infty}>\varepsilon$,
then it must be that for at least some $l_{0}\in\mathbb{I}$,
$\|\hat{M}^{(l_{0})}-M^{(l_{0})}\|_{\infty}>\varepsilon$ and vice versa.
Therefore, it follows that

$\displaystyle\left\\{\underset{l\in\mathbb{I}}{\sup}\|\hat{M}^{(l)}-M^{(l)}\|_{\infty}>\varepsilon\right\\}$
$\displaystyle=\bigcup_{l=1}^{k}\left\\{\|\hat{M}^{(l)}-M^{(l)}\|_{\infty}>\varepsilon\right\\}.$

Hence, applying the union bound,

$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\left\|\hat{M}^{(l)}-M^{(l)}\right\|_{\infty}>\varepsilon\right)$
$\displaystyle=\mathbb{P}\left(\bigcup_{l\in\mathbb{I}}\left\\{\|\hat{M}^{(l)}-M^{(l)}\|_{\infty}>\varepsilon\right\\}\right)$
(D.1)
$\displaystyle\leq\sum_{l\in\mathbb{I}}\mathbb{P}\left(\left\|\hat{M}^{(l)}-M^{(l)}\right\|_{\infty}>\varepsilon\right).$
(D.2)

Fix $l\in\mathbb{I}$. Recall the definition of $\hat{M}^{(l)}(s,\cdot)$ and
${M}^{(l)}(s,\cdot)$ from section 3.1.

Using the fact that $\|\cdot\|_{\infty}<\|\cdot\|_{1}$, we get the following.

$\left\\{\left\|\hat{M}^{(l)}-M^{(l)}\right\|_{\infty}>\varepsilon\right\\}\subseteq\bigcup_{s\in\chi}\left\\{\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right\\}.$

It follows from the union bound that

$\displaystyle\mathbb{P}\left(\left\|\hat{M}^{(l)}-M^{(l)}\right\|_{\infty}>\varepsilon\right)$
$\displaystyle\leq\sum_{s\in\chi}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right).$

Our next objective is to find an upper bound for the probability
$\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right)$
that is independent of $s$. Fix an $s\in\chi$ and recall the definition of
$N_{s}^{(l)}$ from Section 3. Using the law of total probability [20,
Proposition 4.1], it follows that

$\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right)=\sum_{n=1}^{m}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right).$

For any two integers $0\leq n_{low,s}<n_{high,s}\leq m$, we can decompose the
right hand side of section D.1 into two parts,

$\displaystyle\sum_{n=1}^{m}$
$\displaystyle\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)$
$\displaystyle=\sum_{n=n_{low,s}}^{n_{high,s}}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)$
$\displaystyle\qquad+\sum_{n\notin[n_{low,s},n_{high,s}]}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right).$
(D.4)

We can further decompose the second summation by noting that for each $n$,
every summand,

$\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)\leq\mathbb{P}\left(N_{s}^{(l)}=n\right).$

Therefore, it follows that

$\sum_{n\notin[n_{low,s},n_{high,s}]}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)\leq\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}]).$

Hence, the right hand side of Equation D.4 is upper bounded by

$\displaystyle\sum_{n=n_{low,s}}^{n_{high,s}}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)+\mathbb{P}(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}])$
(D.5) $\displaystyle\quad=\text{Term 1 + Term 2},$

We deal with the two terms on the right hand side (RHS) separately.

#### Term 1.

The analysis of the first term follows directly via Proposition 3. We get

$\displaystyle\sum_{n=n_{low,s}}^{n_{high,s}}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)$
$\displaystyle\leq
m\exp\left({-\frac{n_{low,s}}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n_{high,s}}}\right\\}^{2}}\right).$

#### Term 2.

We begin the analysis of the second term by observing that

$\displaystyle\leavevmode\nobreak\
\mathbb{P}\left(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}]\right)$
$\displaystyle=\mathbb{P}\left[N_{s}^{(l)}-\mathrm{E}[N_{s}^{(l)}]<n_{low,s}-\mathrm{E}[N_{s}^{(l)}]\right]$
$\displaystyle\qquad+\mathbb{P}\left[N_{s}^{(l)}-\mathrm{E}[N_{s}^{(l)}]>n_{high,s}-\mathrm{E}[N_{s}^{(l)}]\right].$
(D.6)

As long as $n_{high,s}-\mathrm{E}[N_{s}^{(l)}]>0$, directly applying the upper
bound in Lemma 16 gives us,

$\displaystyle\mathbb{P}\left(N_{s}^{(l)}-\mathrm{E}[N_{s}^{(l)}]>n_{high,s}-\mathrm{E}[N_{s}^{(l)}]\right)$
$\displaystyle\leq
2\exp\left(-{\frac{\left(n_{high,s}-\mathrm{E}\left[N_{s}^{(l)}\right]\right)^{2}}{2m\|\Delta_{m}\|^{2}}}\right).$
(D.7)

Our next step is to select an $n_{high,s}$ such that

$\left(n_{high,s}-\mathrm{E}[N_{s}^{(l)}]\right)>0.$

Recall from Lemma 4 that under our hypothesis,

$\mathrm{E}\left[N_{s}^{(l)}\right]\leq m\max\\{\zeta_{1},1-\zeta_{2}\\}.$

Therefore, by setting
$n_{high,s}=m\left(\frac{1+\max\\{\zeta_{1},1-\zeta_{2}\\}}{2}\right)$, we can
ensure that

$\displaystyle\left(n_{high,s}-\mathrm{E}[N_{s}^{(l)}]\right)=m\left(\frac{1+\max\\{\zeta_{1},1-\zeta_{2}\\}}{2}\right)-\mathrm{E}\left[N_{s}^{(l)}\right]>m\left(\frac{1-\max\\{\zeta_{1},1-\zeta_{2}\\}}{2}\right)>0.$

Similarly, by choosing $n_{low,s}=\frac{m}{2T}$ we ensure
$n_{low,s}-E\left[N_{s}^{(l)}\right]<-\frac{m}{2T}$. Using Lemma 16 again we
obtain,

$\displaystyle\mathbb{P}\left(N_{s}^{(l)}-\mathrm{E}[N_{s}^{(l)}]<n_{low,s}-\mathrm{E}[N_{s}^{(l)}]\right)$
$\displaystyle\leq
2\exp\left(-{\frac{\left(n_{low,s}-\mathrm{E}\left[N_{s}^{(l)}\right]\right)^{2}}{2m\|\Delta_{m}\|^{2}}}\right).$
(D.9)

This completes the analysis of term 2. Combining the results from equations
F.5, D.7 and D.9, we arrive at the following upper bound.

$\displaystyle\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right)$
$\displaystyle\leq
m\exp\left({-\frac{n_{low,s}}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n_{high,s}}}\right\\}^{2}}\right)+2\exp\left({-{\frac{(n_{high,s}-\mathrm{E}[N_{s}^{(l)}])^{2}}{2m\|\Delta_{m}\|^{2}}}}\right)$
$\displaystyle\qquad\qquad+2\exp\left({-{\frac{(n_{low,s}-\mathrm{E}[N_{s}^{(l)}])^{2}}{2m\|\Delta_{m}\|^{2}}}}\right)$
$\displaystyle=\text{A+B+C}.$ (D.10)

Substituting the values of $n_{high,s}$ and $n_{low,s}$ in A we get,

$\displaystyle
m\exp\left({-\frac{n_{low,s}}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n_{high,s}}}\right\\}^{2}}\right)$
$\displaystyle\quad=m\exp\left({-\frac{m}{16T}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{m\left(\frac{1+\max\\{\zeta_{1},1-\zeta_{2}\\}}{2}\right)}}\right\\}^{2}}\right).$

Recall that by hypothesis,

$m>\frac{8d}{\varepsilon^{2}\left(1+\max\\{\zeta_{1},1-\zeta_{2}\\}\right)}.$

This implies that,

$\left(\varepsilon-\sqrt{\frac{d}{m\left(\frac{1+\max\\{\zeta_{1},1-\zeta_{2}\\}}{2}\right)}}\right)^{2}>\varepsilon^{2}\left(1-\frac{1}{2}\right)^{2}=\frac{\varepsilon^{2}}{4}.$

Thus,

$\displaystyle\exp\left({-\frac{n_{low,s}}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n_{high,s}}}\right\\}^{2}}\right)$
$\displaystyle\leq\exp\left({-\frac{m\varepsilon^{2}}{64T}}\right).$

This gives us an upper bound for $A$.

Recall that, we have chosen $n_{high,s}$ such that
$n_{high,s}-\mathbb{E}[N_{s}^{(l)}]>m\left(\frac{1-\max\\{\zeta_{1},1-\zeta_{2}\\}}{2}\right)$.
Consequently,
$\left(n_{high,s}-\mathbb{E}[N_{s}^{(l)}]\right)^{2}>m^{2}\left(\frac{1-\max\\{\zeta_{1},1-\zeta_{2}\\}}{2}\right)^{2}$,
and

$\displaystyle
2\exp\left({-{\frac{(n_{high,s}-\mathrm{E}[N_{s}^{(l)}])^{2}}{2m\|\Delta_{m}\|^{2}}}}\right)\leq
2\exp\left({-{\frac{m\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{8\|\Delta_{m}\|^{2}}}}\right),$

which provides us an upper bound for B. Recall that
$n_{low,s}-\mathbb{E}[N_{s}^{(l)}]<-\frac{m}{8T}$. Therefore,
$(n_{low,s}-\mathbb{E}[N_{s}^{(l)}])^{2}>\left(\frac{m}{8T}\right)^{2}$, and

$\displaystyle
2\exp\left({-{\frac{(n_{low,s}-\mathrm{E}[N_{s}^{(l)}])^{2}}{2m\|\Delta_{m}\|^{2}}}}\right)\leq
2\exp\left({-{\frac{m}{128T^{2}\|\Delta_{m}\|^{2}}}}\right).$

This gives us an upper bound for C.

Returning to eq. D.10, we substitute in the upper bounds for A,B, and C.
Consequently,

$\displaystyle\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right)$
$\displaystyle\leq m\exp\left({-\frac{m\varepsilon^{2}}{64T}}\right)$
$\displaystyle\qquad+2\exp\left({-{\frac{m}{128T^{2}\|\Delta_{m}\|^{2}}}}\right)$
$\displaystyle\qquad+2\exp\left({-{\frac{m\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{8\|\Delta_{m}\|^{2}}}}\right)$
$\displaystyle\leq\frac{64T}{\varepsilon^{2}}\exp\left({-\frac{m\varepsilon^{2}}{128T}}\right)$
$\displaystyle\qquad+2\exp\left({-{\frac{m}{128T^{2}\|\Delta_{m}\|^{2}}}}\right)$
$\displaystyle\qquad+2\exp\left({-{\frac{m\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{8\|\Delta_{m}\|^{2}}}}\right),$

where the inequality follows from the fact that $xe^{-x}\leq e^{-x/2}$. Recall
that the control/control space satisfies $|\mathbb{I}|=k$ and the state space
satisfies $|\chi|=d$. Using a union bound on $l$, we see,

$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\left\|\hat{M}^{(l)}-M^{(l)}\right\|_{\infty}>\varepsilon\right)$
$\displaystyle\leq\sum_{l\in\mathbb{I}}\sum_{s\in\chi}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon\right)$
$\displaystyle\leq\sum_{l\in\mathbb{I}}\sum_{s\in\chi}\Bigg{(}\frac{64T}{\varepsilon^{2}}\exp\left({-\frac{m\varepsilon^{2}}{128T}}\right)$
$\displaystyle\qquad+2\exp\left({-{\frac{m}{128T^{2}\|\Delta_{m}\|^{2}}}}\right)$
$\displaystyle\qquad+2\exp\left({-{\frac{m\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{8\|\Delta_{m}\|^{2}}}}\right)\Bigg{)}$
$\displaystyle=dk\Bigg{(}\frac{64T}{\varepsilon^{2}}\exp\left({-\frac{m\varepsilon^{2}}{128T}}\right)$
$\displaystyle\qquad+2\exp\left({-{\frac{m}{128T^{2}\|\Delta_{m}\|^{2}}}}\right)$
$\displaystyle\qquad+2\exp\left({-{\frac{m\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{8\|\Delta_{m}\|^{2}}}}\right)\Bigg{)}.$
(D.11)

By Assumption 3, $\|\Delta_{m}\|\leq\mathbb{C}_{\Delta}$. Let
$\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}$ be four constants such that,

$\displaystyle\gamma_{1}$
$\displaystyle=\mathbb{C}_{\Delta}^{2}T^{2}\log\left(\frac{6dk}{\delta}\right)$
$\displaystyle\gamma_{2}$
$\displaystyle=\mathbb{C}_{\Delta}^{2}\frac{1}{\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}\log\left(\frac{6dk}{\delta}\right)$
$\displaystyle\gamma_{3}$
$\displaystyle=\frac{128T}{\varepsilon^{2}}\log\left(\frac{192dkT}{\varepsilon^{2}\delta}\right)$
$\displaystyle\gamma_{4}$
$\displaystyle=\frac{d}{\varepsilon^{2}\left({1+\max\\{\zeta_{1},1-\zeta_{2}\\}}\right)}.$

Hence, there exists a universal constant $c$ large enough such that if,

$\displaystyle
m>c\left\\{\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}\right\\},$

then

$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\|\hat{M}^{(l)}-M^{(l)}\|_{\infty}>\varepsilon\right)<\delta.$
(D.12)

However, recall from remark Remark that $T>\frac{dk}{2}$. Therefore, it
follows that $\gamma_{3}>\gamma_{4}$. Hence, there exists an universal
constant $c$ such that as long as

$\displaystyle
m>c\max\left\\{\mathbb{C}_{\Delta}^{2}\log\left(\frac{dk}{\delta}\right)\max\left\\{{T}^{2},\frac{1}{\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}\right\\},\frac{T}{\varepsilon^{2}}\log\left(\frac{dkT}{\varepsilon^{2}\delta}\right)\right\\},$
$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\|\hat{M}^{(l)}-M^{(l)}\|_{\infty}>\varepsilon\right)<\delta.$
(D.13)

∎

###  D.2 Proof of Sample Complexity in Theorem 2

###### Proof.

The first part of this proof follows similarly to that of Theorem 1. We
proceed until eq. D.5, and analyse Term 1 similarly as before to get

$\sum_{n=n_{low,s}}^{n_{high,s}}\mathbb{P}\left(\left\|\hat{M}^{(l)}(s,\cdot)-{M}^{(l)}(s,\cdot)\right\|_{1}>\varepsilon,N_{s}^{(l)}=n\right)\leq
m\exp\left({-\frac{n_{low,s}}{2}\max\left\\{0,\varepsilon-\sqrt{\frac{d}{n_{high,s}}}\right\\}^{2}}\right).$
(D.14)

The difference arises in the analysis of Term 2, where, instead of using
Proposition 5, we use Proposition 6 to obtain

Term 2
$\displaystyle=\mathbb{P}\left(N_{s}^{(l)}\notin[n_{low,s},n_{high,s}]\right)\leq
2\exp\left(-\;\
\frac{\mathbb{C}_{pel}\left(n_{low,s}-\frac{m}{2T}\right)^{2}}{4m\mathbb{C}_{\Delta}\rho_{s}^{(l)}+1+\left(\frac{m}{2T}-n_{low,s}\right)\left(\log
m\right)^{2}}\right)$ $\displaystyle+2\exp\left(-\;\
\frac{\mathbb{C}_{pel}\left(n_{high,s}-m\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{4m\mathbb{C}_{\Delta}\rho_{s}^{(l)}+1+\left(n_{high,s}-m\max\\{\zeta_{1},1-\zeta_{2}\\}\right)\left(\log
m\right)^{2}}\right).$

Observe that the right-hand side of the previous equation is increasing in
$\rho_{s}^{(l)}$. Furthermore, we also have $\rho_{s}^{(l)}\leq\rho_{\star}$.
Thus, we can replace $\rho_{s}^{(l)}$ by $\rho_{\star}$ in the upper bound to
get

Term 2 $\displaystyle\leq 2\exp\left(-\;\
\frac{\mathbb{C}_{pel}\left(n_{low,s}-\frac{m}{2T}\right)^{2}}{4m\mathbb{C}_{\Delta}\rho_{\star}+1+\left(\frac{m}{2T}-n_{low,s}\right)\left(\log
m\right)^{2}}\right)$ $\displaystyle\quad+2\exp\left(-\;\
\frac{\mathbb{C}_{pel}\left(n_{high,s}-m\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{4m\mathbb{C}_{\Delta}\rho_{\star}+1+\left(n_{high,s}-m\max\\{\zeta_{1},1-\zeta_{2}\\}\right)\left(\log
m\right)^{2}}\right).$

Next, we substitute the values
$n_{high,s}=m(1+\max\\{\zeta_{1},1-\zeta_{2}\\})/2$ and $n_{low,s}=m/4T$ into
the previous term to get

Term 2 $\displaystyle\leq
2\exp\left(-\;\frac{1}{16T^{2}}\frac{\mathbb{C}_{pel}m^{2}}{4m\mathbb{C}_{\Delta}\rho_{\star}+1+\frac{m}{4T}\left(\log
m\right)^{2}}\right)$ $\displaystyle\quad+2\exp\left(-\;\
\frac{1}{4}\frac{\mathbb{C}_{pel}m^{2}\left(1-\max\\{\zeta_{1},1-\zeta_{2}\\}\right)^{2}}{4m\mathbb{C}_{\Delta}\rho_{\star}+1+m\left(\frac{1-\max\\{\zeta_{1},1-\zeta_{2}\\}}{2}\right)\left(\log
m\right)^{2}}\right).$ (D.15)

We only analyse the first term. The calculations for the second term follow in
a similar way. Recall from hypothesis that $m>\mathbb{C}_{T}$. Obviously,
$m>4T$. In other words, $1<m/T$. Substituting $1$ for $m/T$ into the
denominator, we get

$\displaystyle 2\exp\left(-\;\frac{1}{16T^{2}}\
\frac{\mathbb{C}_{pel}m^{2}}{4m\mathbb{C}_{\Delta}\rho_{\star}+1+\frac{m}{4T}\left(\log
m\right)^{2}}\right)$ $\displaystyle\quad\leq 2\exp\left(-\;\frac{1}{16T^{2}}\
\frac{\mathbb{C}_{pel}m^{2}}{4m\mathbb{C}_{\Delta}\rho_{\star}+\frac{m}{4T}+\frac{m}{4T}\left(\log
m\right)^{2}}\right)$ $\displaystyle\quad=2\exp\left(-\;\frac{1}{4}\
\frac{\mathbb{C}_{pel}m}{16\mathbb{C}_{\Delta}\rho_{\star}T^{2}+T+T\left(\log
m\right)^{2}}\right)$ $\displaystyle\quad\leq 2\exp\left(-\;\frac{1}{64}\
\frac{\mathbb{C}_{pel}\frac{m}{\left(\log
m\right)^{2}}}{\mathbb{C}_{\Delta}\rho_{\star}T^{2}+2T}\right).$

The last inequality follows by taking $16(\log m)^{2}$ common from the
denominator and trivially upper bounding $(\log m)^{-2}$ by $1$. Observe that
$\mathbb{C}_{pel}/64\left(\mathbb{C}_{\Delta}\rho_{\star}T^{2}+2T\right)$ is
less than $1$ and constant in $m$. Recall from eq. 3.11 that the _inverse of_
this term was defined to be $\mathbb{C}_{T}$. It is clear that
$2dk\exp\left(-\;\frac{m}{\mathbb{C}_{T}(\log m)^{2}}\right)$ is decreasing in
$m$. Our objective is to find an $m$ such that

$\displaystyle 2dk\exp\left(-\;\frac{m}{\mathbb{C}_{T}(\log m)^{2}}\right)$
$\displaystyle\leq\frac{\delta}{3},$ which is equivalent to finding an $m$
such that $\displaystyle\frac{m}{(\log m)^{2}}$
$\displaystyle>\mathbb{C}_{T}\log\left(\frac{6dk}{\delta}\right)=\mathbb{C}_{T,\delta}.$
(D.16)

Let $m=2\mathbb{C}_{T,\delta}\left(\log\mathbb{C}_{T,\delta}\right)^{2}$. The
denominator of the term on the left-hand side of the previous equation
decomposes into

$\displaystyle(\log m)^{2}$
$\displaystyle=\left(\log\left(2\mathbb{C}_{T,\delta}\left(\log\mathbb{C}_{T,\delta}\right)^{2}\right)\right)^{2}$
$\displaystyle=\left(\log
2+\log\mathbb{C}_{T,\delta}+2\log\log\mathbb{C}_{T,\delta}\right)^{2}$
$\displaystyle=\left(\log\mathbb{C}_{T,\delta}\right)^{2}\left(1+\frac{\log
2}{\log\mathbb{C}_{T,\delta}}+2\frac{\log\log\mathbb{C}_{T,\delta}}{\log\mathbb{C}_{T,\delta}}\right)^{2}.$

Consider the function,

$\displaystyle f(x)=\left(1+\frac{\log 2}{\log x}+2\frac{\log\log x}{\log
x}\right)^{2}.$

This is obviously decreasing in $x$. It can be easily verified that there
exists a universal constant ‘$c$’ such that $f(x)<2$ if $x>c$. Using this fact
and substituting $m$ in eq. D.16, we get

$\displaystyle\frac{m}{(\log m)^{2}}$
$\displaystyle=2\mathbb{C}_{T,\delta}\frac{\left(\log\mathbb{C}_{T,\delta}\right)^{2}}{\left(\log\mathbb{C}_{T,\delta}\right)^{2}f(\mathbb{C}_{T,\delta})}$
$\displaystyle\geq\mathbb{C}_{T,\delta}.$

Therefore, the first term on the left-hand side of eq. D.15 is upper bounded
by $\delta/3$. We can similarly show that, whenever
$m>2\mathbb{C}_{\zeta,\delta}\left(\log\mathbb{C}_{\zeta,\delta}\right)^{2}$
the second term on the right-hand side of eq. D.15 can be upper bounded by
$\delta/3$. We now proceed similarly to eq. D.11. This gives us that, under
our current hypothesis,

$\displaystyle\mathbb{P}\left(\underset{l\in\mathbb{I}}{\sup}\|\hat{M}^{(l)}-M^{(l)}\|_{\infty}>\varepsilon\right)<\delta.$

This completes the proof of the sample complexity. We can now proceed to the
proof of Minimaxity. ∎

###  D.3 Proof of Minimaxity in Theorem 2

###### Proof.

As before, let $\mathcal{M}_{\chi,\mathbb{I}}$ be the class of all Markov
decision processes on state space $\chi$ with control space $\mathbb{I}$. We
will view an element of $\mathcal{M}_{\chi,\mathbb{I}}$ as doublet
$(\mathbb{M},P)$, where $\mathbb{M}:=(M^{(1)},\dots,M^{(k)})$ is a collection
of distinct $d$-state Markov transition matrix, and
$P:=\left(P_{1},P_{2},\dots,\right)$ is the distribution of control sequences,
with each $P_{i}$ being a probability measure on $\mathbb{I}$ that depends on
the history until time point $i$. Let $\mathcal{M}_{\chi}$ and
$\mathcal{M}_{\mathbb{I}}$ be the set of all $\mathbb{M}$ and $P$,
respectively. For $\mathbb{M}_{1},\mathbb{M}_{2}\in\mathcal{M}_{\chi}$, define

$\left\|\mathbb{M}_{1}-\mathbb{M}_{2}\right\|_{\infty}^{*}:=\sup_{l\in\mathbb{I}}\left\|M_{1}^{(l)}-M_{2}^{(l)}\right\|_{\infty}.$

For
$\left\\{(X_{0},a_{0}),\dots,(X_{m},a_{m})\right\\}\in(\chi\times\mathbb{I})^{m}$,
a sample of length $m$ from some MDP belonging to
$\mathcal{M}_{\chi,\mathbb{I}}$, define an estimation procedure
$\hat{\mathbb{M}}$ as the mapping
$\hat{\mathbb{M}}:(\chi\times\mathbb{I})^{m}\mapsto\mathcal{M}_{\chi}$. We
seek to provide a lower bound for the minimax risk over all estimation
procedures:

$\begin{split}\mathcal{R}_{m}&=\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}_{\chi,\mathbb{I}}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\right).\end{split}$
(D.17)

We note that if $\mathcal{M}^{\prime}\subset\mathcal{M}_{\chi,\mathbb{I}}$ is
a subclass of MDP’s, then

$\displaystyle\mathcal{R}_{m}$
$\displaystyle\geq\inf_{\hat{\mathbb{M}}}\sup_{(\mathbb{M},P)\in\mathcal{M}^{\prime}}\mathbb{P}\left({\left\|\hat{\mathbb{M}}-\mathbb{M}\right\|_{\infty}^{*}>\varepsilon}\right).$
(D.18)

The rest of the proof proceeds by constructing an appropriate subclass
$\mathcal{M}^{\prime}$.

#### Part 1 ($m<cT/\varepsilon^{2}$):

Our example below considers an MDP with stationary Markovian controls. Any
such MDP with $k$ transition matrices and $d^{\prime}$ states can be viewed as
a single Markov chain with $d=d^{\prime}k$ states. For convenience, we use the
latter representation. By ${M}$ denote its transition matrix, and by $\hat{M}$
denote the estimate. Without losing generality, let there be $d+1$ states
where $d$ is even; the odd case is handled similarly. Let
$0<p_{\star}<\frac{1}{d+1}$ and for a vector
$\sigma=\left(\sigma_{1},\dots,\sigma_{\frac{d}{2}}\right)\in\left\\{-1,1\right\\}^{\frac{d}{2}}$,
define $\boldsymbol{\eta}(\sigma)$ as the following perturbation of
$\left(\frac{1-p_{\star}}{d},\frac{1-p_{\star}}{d},\dots,p_{\star}\right)$:

$\boldsymbol{\eta}(\sigma)=\left(\frac{1-p_{\star}+16\sigma_{1}\varepsilon}{d},\frac{1-p_{\star}-16\sigma_{1}\varepsilon}{d},\dots,\frac{1-p_{\star}+16\sigma_{\frac{d}{2}}\varepsilon}{d},\frac{1-p_{\star}-16\sigma_{\frac{d}{2}}\varepsilon}{d},p_{\star}\right).$

Since $\varepsilon<\frac{1}{32}$ and $d>2$ by hypothesis, it follows that
$\boldsymbol{\eta}(\sigma)$ is a valid probability mass function on
$\\{1,\dots,d+1\\}$. Let $\mathcal{M}_{\sigma}$ be a class of transition
matrices indexed by $\sigma$, taking the form

$\displaystyle M_{\sigma}$
$\displaystyle=\begin{pmatrix}\frac{1-p_{\star}}{d}&\ldots&\frac{1-p_{\star}}{d}&p_{\star}\\\
\vdots&\vdots&\vdots&\vdots\\\
\frac{1-p_{\star}}{d}&\ldots&\frac{1-p_{\star}}{d}&p_{\star}\\\
\frac{1-p_{\star}+16\sigma_{1}\varepsilon}{d}&\ldots&\frac{1-p_{\star}-16\sigma_{\frac{d}{2}}\varepsilon}{d}&p_{\star}\end{pmatrix}.$
(D.19)

From the Varshamov-Gilbert lemma [55, Theorem 5.1.7], there exists
$\Sigma\subset\left\\{-1,1\right\\}^{d/2}$, $\left|\Sigma\right|=2^{d/16}$,
such that for $(\boldsymbol{\sigma},\boldsymbol{\sigma}^{\prime})\in\Sigma$
with $\boldsymbol{\sigma}\neq\boldsymbol{\sigma}^{\prime}$, we have

$\sum_{i=1}^{d/2}\mathbbm{1}[\boldsymbol{\sigma_{i}}\neq\boldsymbol{\sigma_{i}^{\prime}}]\geq\frac{d}{16},$

Define the subclass $\mathcal{M}^{\prime}$ as