# Geometric States
In memory of Steve Zelditch

Benoit Dherin  Google, Mountain View, CA 94043, USA<EMAIL_ADDRESS>and
Alan Weinstein  Department of Mathematics, University of California, Berkeley,
CA 94720, USA, and Department of Mathematics, Stanford University, Stanford,
CA 94305, USA<EMAIL_ADDRESS>
###### Abstract.

We introduce a special family of distributional $\alpha$-densities and give a
transversality criterion stating when their product is defined, closely
related to Hörmander’s criterion for general distributions. Moreover, we show
that for the subspace of distributional half-densities in this family the
distribution product naturally yields a pairing that extends the usual one on
smooth half-densities.

###### 2020 Mathematics Subject Classification:

46C50, 46F10, 53C99, 81S10

###### Contents

  1. 1 Introduction
  2. 2 Geometric States
  3. 3 Geometric states as distributions
  4. 4 Product of geometric distributions
  5. 5 Pairing of geometric distributions

January 2024

##  1\. Introduction

The notion of state in quantum mechanics is generally defined as a unit
vector, or ray, in a Hilbert space [9], and the probability of transition from
one state $\psi_{1}$ to another state $\psi_{2}$ is given using the Hilbert
space inner product as $|\langle\psi_{1},\,\psi_{2}\rangle|^{2}$. When these
states are realized as the solutions of the Schrödinger equation a number of
technical problems arise with the Hilbert space formulation of the states. In
particular, since its solutions (or initial conditions) can have
singularities, they are distributions rather than honest functions in a
$L^{2}$ Hilbert space [9]. The necessity to include certain distributions as
states makes the axiomatic requirement of the state space to be a Hilbert
space difficult to fulfill in practice. This has led to considering weaker
definitions than that of a Hilbert space as natural state spaces for quantum
mechanics. For example, partial inner product spaces [1, 2] are vector spaces
where the inner product (and hence the transition probability) is only
partially defined. This issue is closely related to the product of
distributions, which is well-known not to be possible in general [4, 8].
Hörmander gave a criterion involving properties of the distributions’ wave-
front sets governing when their product is possible [8]. Extending the product
from functions to distributions has also important implications in quantum
field theory and renormalization theory; see [5, 6] for example.

In this note, we take a geometric approach to the notion of state rather than
an analytic one, based on the concept of $\alpha$-densities as described in
[3, 7]. For instance, the space of half densities on a manifold $X$ is a
natural candidate for a quantum state space as it comes equipped with an
intrinsic Hilbert space product (upon taking suitable completions) and locally
it can be modeled as the space of square-integrable functions. To include
singular states, we still need to consider the dual space of distributional
half densities though on which the natural intrinsic inner product is
unfortunately not always defined.

The main contribution of this work is to give an explicit geometric
description of a special family of distributional $\alpha$-densities, which we
call geometric states, for which the product is well-defined provided that
their spatial components (which we call cores) intersect transversally (which
is a special case of Hörmander’s criterion [8]). When specialized to
$\alpha=1/2$, this product allows us to extend the intrinsic inner-product of
half densities to the whole space of geometric states, assuming transversal
intersection of their cores.

##  2\. Geometric States

Before giving a definition of a geometric state, let us start by recalling the
notion of $\alpha$ -densities; see [3, 7] for more details. Consider a
$n$-dimensional vector space $V$ over $\mathbb{C}$. We denote by $V^{*}$ its
dual, that is, the vector space of linear maps $V\rightarrow\mathbb{C}$, and
by $F(V)$ its set of frames, that is, the set of ordered bases ${\bf
e}=(e_{1},\dots,e_{n})$. For each $\alpha\in\mathbb{C}$, the space of
$\alpha$-densities on $V$ is the space of mappings
$\eta:F(V)\rightarrow\mathbb{C}$ such that $\eta(A{\bf e})=|\det
A|^{\alpha}\eta({\bf e})$, where $A$ is a non-singular linear map and $|\det
A|$ is the absolute value of its determinant. We denote by $|V|^{\alpha}$ the
space of $\alpha$-densities on $V$, which is a complex vector space of
dimension 1.

Now consider a smooth manifold $X$. The space of $\alpha$-densities on $X$,
which we denote by $|\Omega|^{\alpha}(X)$, is the space of sections of the
line-bundle $|TX|^{\alpha}\rightarrow X$ whose fiber at $x$ is
$|T_{x}X|^{\alpha}$. More generally, given a vector bundle $E\rightarrow X$,
we can form the line bundle $|E|^{\alpha}\rightarrow X$ whose fiber at $x$ is
the 1-dimensional vector space over $\mathbb{C}$ of $\alpha$-densities
$|E_{x}|^{\alpha}$. We consider the space of smooth sections
$\Gamma(X,|E|^{\alpha})$ as a $C^{\infty}(X)$-module. We will consider the
tensor product of such modules over $C^{\infty}(X)$. There are a few canonical
isomorphisms of importance to us that we now enumerate for convenience. First
of all $|E^{*}|^{\alpha}\rightarrow X$ naturally identifies with
$|E|^{-\alpha}\rightarrow X$. Second, given an exact sequence $0\rightarrow
A\rightarrow B\rightarrow C\rightarrow 0$ of vector bundles over $X$, we have
the canonical isomorphism $|B|^{\alpha}\simeq|A|^{\alpha}\otimes|C|^{\alpha}$,
where we use the shorthand notation $|E|^{\alpha}$ to denote the vector bundle
$|E|^{\alpha}\rightarrow X$. At last, we have that
$|E|^{\alpha}\otimes|E|^{\beta}\simeq|E|^{\alpha+\beta}$ which specializes to
$|\Omega|^{\alpha}(X)\otimes|\Omega|^{\beta}(X)\simeq|\Omega|^{\alpha+\beta}(X)$
when $E$ is the tangent bundle to $X$.

We can now define our space of geometric states:

######  Definition 1.

We define the space $\mathcal{H}_{X,\,C}^{\alpha}$, where $C$ is a smooth
submanifold of a smooth manifold $X$ and $\alpha\in\mathbb{C}$, as the
subspace of the following density bundle sections

$|\Omega|^{\alpha}(C)\otimes\Gamma(|N^{*}C|^{1-\alpha}).$

The first factor of the tensor product above is the space of smooth
$\alpha$-densities on $C$, while the second factor is the space of the smooth
sections of the $(1-\alpha)$-density bundle associated to the conormal bundle
$N^{*}C\rightarrow C$ to $C$. We call an element in either of this spaces
interchangeably a geometric state or a geometric distributional
$\alpha$-density.

This family of spaces above has interesting well-known extreme cases:

######  Example 2.

When $C=X,$ the spaces $\mathcal{H}_{X,\,C}^{\alpha}$ coincide with the usual
smooth $\alpha$-densities on the full space $X$. In particular, when
$\alpha=0$, this space identifies with the space $\mathcal{E}_{X}$ of the
smooth functions on $X$, which, in turn, can be regarded as a subspace of the
distributions on $X$ (with test “functions” taken in the smooth compactly
supported 1-densities on $X$).

######  Example 3.

When $\alpha=1,$ we have the identification of $\mathcal{H}_{X,\,C}^{\alpha}$
with the space of smooth $1$-densities (or measures) supported on the
submanifold $C$. This space can also be regarded as a subspace of the
distributions on $X$ supported on $C$ (now with test functions the compactly
supported smooth functions on $X$).

######  Example 4.

When $C$ is reduced to a single point $x\in X$, then
$\mathcal{H}_{X,\,C}^{\alpha}$ identifies with the $(\alpha-1)$-densities
$|T_{x}X|^{\alpha-1}$ at that point, which further identifies with
$\mathbb{R}$ when $\alpha=1$, the inverse volume elements $1/|T_{x}X|$ when
$\alpha=0$ (which will see are related with the delta distributions), and the
volume elements $|T_{x}X|$ when $\alpha=2$.

A last example comes from the following Proposition

######  Proposition 5.

Let $C$ be a smooth submanifold of $X$. Consider the conormal bundle $N^{*}C$
to $C$ in $X$. Then the restriction of a half-density in
$|\Omega|^{\frac{1}{2}}(N^{*}C)$ to the zero section of $N^{*}C\rightarrow C$
can be identified with an element of
$|\Omega|^{\frac{1}{2}}(C)\otimes\Gamma(|N^{*}C|^{\frac{1}{2}})$, that is,
with an element of $\mathcal{H}_{X,\,C}^{\frac{1}{2}}$.

###### Proof.

This comes directly from the fact that the tangent space to $N^{*}C$
restricted to the zero section can be identified with the bundle $TC\oplus
N^{*}C$ and the usual canonical isomorphism for $\alpha$-density bundles. ∎

The proposition above motivates the following example:

######  Example 6.

Half-densities on lagrangian submanifolds, such as the conormal bundle
$N^{*}C$ to a submanifold $C$, are typically related to some form of
“geometric quantum states” (see [3] for example). As shown in Proposition 5, a
half-density on $N^{*}C$ induces a element of
$\mathcal{H}_{X,\,C}^{\frac{1}{2}}$. This space can be regarded as a subspace
of the distributional half-densities on $X$ thanks to Proposition 8, which
makes it clear that the pairing of an element of
$\mathcal{H}_{X,C}^{\frac{1}{2}}$ with a compactly supported half density in
$|\Omega_{0}|^{\frac{1}{2}}(X)$ yields a compactly supported $1$-density on
$C$ that can be integrated over $C$ into a complex number. This yields the
natural pairing:

$\langle\cdot\,,\cdot\rangle\>:\;\mathcal{H}_{X,\,C}^{\frac{1}{2}}\times|\Omega_{0}|^{\frac{1}{2}}(X)\longrightarrow\mathbb{C}.$

The examples above suggest the name of “geometric states” for the spaces
$\mathcal{H}_{X,C}^{\alpha}$, since the $1$-density example is related to
classical state spaces, while the half-density example is related to the
quantum state spaces, both of which are given here in term of geometrical
data.

##  3\. Geometric states as distributions

In this section, we show that elements in the geometric state space
$\mathcal{H}_{X,\,C}^{1-\alpha}$ naturally identify with distributional
$(1-\alpha)$-densities, that is, elements in the dual to the space of the
compactly supported smooth $\alpha$-densities on $X$. In the following, we
will denote the spaces of compactly supported smooth $\alpha$-densities on $X$
by

$\mathcal{D}_{X}^{\alpha}:=|\Omega_{0}|^{\alpha}(X).$

Note that $\mathcal{D}_{X}^{0}$ identifies with the space $\mathcal{D}_{X}$ of
compactly supported functions (test functions) on $X$.

######  Lemma 7.

Let $C$ be a smooth submanifold of a smooth manifold $X$. The restriction to
$C$ of the $\alpha$-densities on $X$ yields the following canonical map

(3.1)
$|\Omega|^{\alpha}(X)\longrightarrow|\Omega|^{\alpha}(C)\otimes\Gamma(|NC|^{\alpha})$

###### Proof.

The proof follows immediately from the exact sequence $0\rightarrow
TC\rightarrow TX\rightarrow NC\rightarrow 0$ and the canonical isomorphism
$|A\oplus B|^{\alpha}\simeq|A|^{\alpha}\otimes|B|^{\alpha}$.∎

######  Proposition 8.

There is a natural bilinear pairing

$\langle\cdot,\cdot\rangle:\;\mathcal{H}_{X,C}^{1-\alpha}\times\mathcal{D}_{X}^{\alpha}\longrightarrow\mathbb{C},$

turning $\mathcal{H}_{X,C}^{1-\alpha}$ into a subset of the distributional
$(1-\alpha)$-densities $(\mathcal{D}_{X}^{\alpha})^{{}^{\prime}}$ on $X$.

###### Proof.

Thanks to Lemma 7, the restriction of an element
$\phi\in\mathcal{D}_{X}^{\alpha}$ to the submanifold $C$ can be identified
with a compactly supported section

$\phi_{|C}\in|\Omega_{0}|^{\alpha}(C)\otimes\Gamma_{0}(|NC|^{\alpha}).$

Now taking the tensor product of this restriction with a section

$\theta\in|\Omega|^{1-\alpha}(C)\otimes\Gamma(|N^{*}C|^{\alpha})$

(i.e. with an element $\theta\in\mathcal{H}_{X,C}^{1-\alpha}$), we obtain a
compactly supported $1$-density

$\theta\otimes\phi_{|C}\in|\Omega_{0}|^{1}(C)$

Hence, we can integrate this tensor product, yielding the following natural
pairing:

$\langle\theta,\,\phi\rangle:=\int_{C}\theta\otimes\phi_{|C}.$

∎

##  4\. Product of geometric distributions

On the $\alpha$-density test spaces $\mathcal{D}_{X}^{\alpha}$, that is, the
spaces of compactly supported smooth $\alpha$-densities on $X$, we have the
natural product of $\alpha$-densities

$\mathcal{D}_{X}^{\alpha}\times\mathcal{D}_{X}^{\beta}\longrightarrow\mathcal{D}_{X}^{\alpha+\beta}$

given by the tensor product of the density bundle sections. (When
$\alpha=\beta=0$, it degenerates to the product of smooth compactly supported
functions.) The question of whether and when this product can be extended to
the distributional spaces $(\mathcal{D}_{X})^{{}^{\prime}}$ has wide-reaching
implications for both partial differential equations and quantum-field theory.
In general, it is not possible, and Hörmander [8] has given a criterion on
pairs of distributions which is sufficient to multiply them together in a
meaningful way. Roughly, the Hörmander criterion states that the product of
distributions makes sense when their wave front sets do not interact.

Here we are considering the spaces of distributional $\alpha$-densities (not
only the case $\alpha=0$), and we specialize to the case of the distributional
$\alpha$-density spaces introduced in the previous sections. The main result
is that the product of two geometric states in $\mathcal{H}_{X,C}^{\alpha}$
and in $\mathcal{H}_{X,D}^{\beta}$ is defined when $C$ and $D$ intersect
transversally along a smooth submanifold. Let’s start to see that it is true
on a particular sub-family of the geometric states

Consider the degenerate case when $C=D=X$. Here, we obviously have a
transverse intersection. Now, we have that $\mathcal{H}_{X,X}^{\alpha}$
coincides with the smooth $\alpha$-densities on $X$ and
$\mathcal{H}_{X,D}^{\beta}$ coincides with the smooth $\beta$-densities on
$X$. In this case, we already know that the tensor product gives a well
defined product

$\mathcal{H}_{X,X}^{\alpha}\times\mathcal{H}_{X,X}^{\beta}\rightarrow\mathcal{H}_{X,X}^{\alpha+\beta}$

thanks to the canonical isomorphism
$|\Omega|^{\alpha}(X)\otimes|\Omega|^{\beta}(X)\simeq|\Omega|^{\alpha+\beta}(X).$
The following theorem states that this product can be also extended to
geometric states, provided that their supports intersect transversally.
Moreover, in the particular case when $\alpha=\beta=1/2$, this product can be
used to define a pairing, since the product between two geometric
distributional half-densities specializes to a $1$-density on the
intersection, which can then be integrated, resulting into a pairing between
geometric half-densities with transverse intersection.

######  Theorem 9.

Let $C$ and $D$ be two smooth submanifolds of a manifold $X$ with smooth
transverse intersection $C\cap D$. Then, we have the canonical mapping

$\mathcal{H}_{X,\,C}^{\alpha}\otimes\mathcal{H}_{X,\,D}^{\beta}\,\rightarrow\,\mathcal{H}_{X,\,C\cap
D}^{\alpha+\beta}$

defining a product on the space of geometric distributional densities.

###### Proof.

The proof rests on two simple properties. The first one is always valid, and
it was already implicitly used in the proof of Lemma 7. We state it explicitly
now at the level of the density bundles:

(4.1) $|TX_{|U}|^{\delta}\simeq|TU|^{\delta}\otimes|NU|^{\delta},$

for any smooth submanifold $U$ of smooth manifold $X$. The second property is
valid only when the intersection $C\cap D$ of the two smooth submanifolds $C$
and $D$ of $X$ is smooth and transverse; in this case, we have that

(4.2) $|N(C\cap D)|^{\delta}\simeq|NC|^{\delta}\otimes|NC|^{\delta}.$

Now consider $\theta_{1}\in\mathcal{H}_{X,C}^{\alpha}$ and
$\theta_{2}\in\mathcal{H}_{X,D}^{\beta}$. The tensor product
$\theta_{1}\otimes\theta_{2}$ of the restriction to the intersection $C\cap D$
is a section of the following tensor products of density bundles

(4.3)
$|TC|^{\alpha}\otimes|TD|^{\beta}\otimes|N^{*}C|^{1-\alpha}\otimes|N^{*}D|^{1-\beta}.$

Using (4.1), we can decompose the first two factors as

$|TC|^{\alpha}\simeq|TX|^{\alpha}\otimes|N^{*}C|^{\alpha}\quad\textrm{and}\quad|TD|^{\beta}\simeq|TX|^{\beta}\otimes|N^{*}D|^{\beta}.$

Now substituting the new expression of these factors into (4.3), grouping the
terms together, and using the usual canonical isomorphisms of density bundles,
we obtain that the product space (4.3) identifies with

$|TX|^{\alpha+\beta}\otimes|N^{*}C|^{1}\otimes|N^{*}D|^{1}.$

Since we are assuming that $C$ and $D$ are transverse, we can then use the
identification (4.2) for the two last factors above yielding

$|TX|^{\alpha+\beta}\otimes|N^{*}(C\cap D)|^{1}.$

Now, using again the decomposition (4.1), we obtain that (4.3) can further be
identified with

$|T(C\cap D)|^{\alpha+\beta}\otimes|N^{*}(C\cap D)|^{1-(\alpha+\beta)}.$

Thus, the tensor product $\theta_{1}\otimes\theta_{2}$ of the restrictions
coincide with a section of this last bundle, that is, with an element of
$\mathcal{H}_{X,C\cap D}^{\alpha+\beta}$. ∎

##  5\. Pairing of geometric distributions

The space of all compactly supported smooth $\alpha$-densities does not form
an inner-product space (unless $\alpha=\frac{1}{2}$) but there is always a
pairing

$\langle\cdot\,,\cdot\rangle\,:\mathcal{D}_{X}^{\alpha}\,\times\,\mathcal{D}_{X}^{1-\alpha}\longrightarrow\mathbb{C},$

where the pairing between a (compactly supported) $\alpha$-density and a
(compactly supported) $(1-\alpha)$-density comes from integrating the
1-density obtained by taking their product. The global structure on
$D_{X}=\oplus_{\alpha}D_{X}^{\alpha}$, on which the inner product is only
partially defined, is reminiscent of that of a Partial Inner-Product Space
introduced in [1] (see also [2]).

The main theorem in the previous section tells us that this structure can be
extended to the space of geometric distributions. Namely, if we restrict the
geometric state product to pairs of geometric subspaces with density degree in
the same relation as above and with cores intersecting transversally, we
obtain the following specialization:

$\mathcal{H}_{X,\,C}^{\alpha}\,\otimes\,\mathcal{H}_{X,\,D}^{1-\alpha}\,\rightarrow\,\mathcal{H}_{X,\,C\cap
D}^{1}\,\simeq\,|\Omega|^{1}(C\cap D).$

Now, integrating this last $1$-density, we obtain a pairing that generalizes
the Partial Inner-Product space structure to the space of geometric
distributional $\alpha$-densities. Let us summarize this in a proposition:

######  Proposition 10.

Consider the geometric distribution spaces $\mathcal{H}^{\alpha}_{X,\,C}$ and
$\mathcal{H}^{\beta}_{X,\,D}$. If we have further that $\alpha+\beta=1$ and
that $C$ and $D$ intersect transversally along a compact submanifold, there is
a natural bilinear pairing between these spaces:

$\langle\cdot\,,\cdot\rangle\,:\mathcal{H}_{X,\,C}^{\alpha}\,\times\,\mathcal{H}_{X,\,D}^{1-\alpha}\longrightarrow\mathbb{C}.$

In particular, these pairings endow the geometric distributional half-
densities ($\alpha=1/2$) with a partially defined inner-product, extending the
natural inner-product on the space of smooth compactly supported half-
densities.

If we regard the smooth half-density space $\mathcal{D}_{X}^{1/2}$ on $X$ as
modeling the states of a quantum system, then the collection of geometric
distribution spaces

$\mathcal{H}_{X}^{1/2}:=\oplus_{C}\mathcal{H}_{X,C}^{\frac{1}{2}}$

extends this model. The partially-defined inner product should be then thought
as giving the probability transition from one geometric state to another,
under the compatibility condition that the cores of these states are
intersecting transversally. This implies that a geometric state spatially
supported on $C$ can transition to a geometric state spatially supported on
$D$ only when these states have some amount of spatial overlap.

## References

  * [1] Antoine, J.-P., and Grossmann, A., Partial Inner Product Spaces. I General Properties, Journal of Functional Analysis, Vol. 23, (4), pp. 369-389, 1976.
  * [2] Antoine, J.-P., and Trapani, C., Partial Inner Product Spaces: Theory and Applications. Lecture Notes in Mathematics 1986, Springer-Verlag, 2009.
  * [3] Bates, S., and Weinstein, A., Lectures on the Geometry of Quantization. Berkeley Mathematics Lecture Notes 8, American Mathematical Society,1997.
  * [4] Brouder, C., Dang V. N., and Hélein F., Continuity of the fundamental operations on distributions having a specified wave front set (with a counter example by Semyon Alesker). Studia Mathematica, Vol. 232, pp. 201-226, (3) 2016.
  * [5] Dang, N. V., Renormalization of quantum field theory on curved space- times, a causal approach. Ph.D. thesis, Paris Diderot University, 2013.
  * [6] Dang, N. V., The extension of distributions on manifolds, a microlocal approach. Annales de l’institut Henri Poincaré, Vol. 17, pp. 819-859, (4) 2016.
  * [7] Guillemin, V., and Sternberg, S., Geometric Asymptotics. Mathematical Surveys and Monographs 14, American Mathematical Society, 1977.
  * [8] Hörmander, L., The Analysis of Linear Partial Differential Operators IV. Springer-Verlag, 2009.
  * [9] Isham, C. J., Lectures On Quantum Theory: Mathematical And Structural Foundations. Allied Publishers, 2001.


# Q-Learning for Stochastic Control under General Information Structures and
Non-Markovian Environments

Ali D. Kara and Serdar Yüksel Ali D. Kara is with the Department of
Mathematics, University of Michigan, Ann Arbor, USA, Email<EMAIL_ADDRESS>S. Yüksel is with the Department of Mathematics and Statistics, Queen’s
University, Kingston, Ontario, Canada, K7L 3N6. Email<EMAIL_ADDRESS>This
research was partially supported by the Natural Sciences and Engineering
Research Council of Canada (NSERC).

###### Abstract

As a primary contribution, we present a convergence theorem for stochastic
iterations, and in particular, Q-learning iterates, under a general, possibly
non-Markovian, stochastic environment. Our conditions for convergence involve
an ergodicity and a positivity criterion. We provide a precise
characterization on the limit of the iterates and conditions on the
environment and initializations for convergence. As our second contribution,
we discuss the implications and applications of this theorem to a variety of
stochastic control problems with non-Markovian environments involving (i)
quantized approximations of fully observed Markov Decision Processes (MDPs)
with continuous spaces (where quantization break down the Markovian
structure), (ii) quantized approximations of belief-MDP reduced partially
observable MDPS (POMDPs) with weak Feller continuity and a mild version of
filter stability (which requires the knowledge of the model by the
controller), (iii) finite window approximations of POMDPs under a uniform
controlled filter stability (which does not require the knowledge of the
model), and (iv) for multi-agent models where convergence of learning dynamics
to a new class of equilibria, subjective Q-learning equilibria, will be
studied. In addition to the convergence theorem, some implications of the
theorem above are new to the literature and others are interpreted as
applications of the convergence theorem. Some open problems are noted.

##  1 Introduction

In some stochastic control problems, one does not know the true transition
kernel or the cost function, and may wish to use past data to obtain an
asymptotically optimal solution (that is, via learning from past data). In
some problems, this may be used as a numerical method to obtain approximately
optimal solutions.

Yet, in many problems including most of those in health, applied and social
sciences and financial mathematics, one may not even know whether the problem
studied is a fully observed Markov Decision Process (MDP), or a partially
observable Markov Decision Process (POMDP) or a multi-agent system where other
agents are present or not. There are many practical settings where one indeed
works with data and does not know the possibly very complex structure under
which the data is generated and tries to respond to the environment.

A common practical and reasonable response is to view the system as an MDP,
with a perceived state and action (which may or may not define a genuine
controlled Markov chain and therefore, the MDP assumption may not hold in
actuality), and arrive at corresponding solutions via some learning algorithm.

The question then becomes two-fold: (i) Does such an algorithm converge? (ii)
If it does, what does the limit mean for each of the following models: MDPs,
POMDPs, and multi-agent models?

Contributions.  We answer the two questions noted above in the paper:

The answer to the first question will follow from a general convergence
result, stated in Theorem 2.1 below. The result will require an ergodicity
condition and a positivity condition, which will be specified and will need to
be ensured depending on the specifics of the problem in various forms and
initialization conditions. While our approach builds on [19], the generality
considered in this paper requires us to precisely present conditions on
ergodicity and positivity, which will be important in applications.

The second question will entail further regularity and assumptions depending
on the particular (hidden) information structure considered, whose
implications under several practical and common settings will be presented.
Some of these have not been reported elsewhere and some will build on prior
work though with a unified lens: We will first study fully observed MDPs with
continuous spaces, then POMDPs with continuous spaces, and finally
decentralized stochastic (or multi-agent) control problems: (i) We first show
that under weak continuity conditions and a technical ergodicity condition,
Q-learning can be applied to fully observable MDPs for near optimal
performance under discounted cost criteria. (ii) For POMDPs, we show that
under a uniform controlled filter stability, finite memory policies can be
used to arrive at near optimality, and with only asymptotic filter stability
quantization can be used to arrive at near optimality, under a mild unique
ergodicity condition (which entails the mild asymptotic filter stability
condition) and weak Feller continuity of the non-linear filter dynamics. We
note that the quantized approximations, for both MDPs and belief-MDPs, raise
mathematical questions on unique ergodicity and the initialization, which are
also addressed in the paper. (iii) For decentralized stochastic control
problems and multi-agent systems, under a variety of information structures
with strictly local information or partial global information, we show that
Q-learning can be used to arrive at equilibria, even though this may be a
subjective one.

We thus study reinforcement learning in stochastic control under a variety of
models and information structures. The general theme is that reinforcement
learning can be applied to a large class of models under a variety of
performance criteria, provided that certain regularity conditions apply for
the associated kernels.

Our Q-learning convergence theorem under non-Markovian settings builds on
[19], however with generalizations and technical specifications in view of the
generality presented in this paper. We note that similar studies have been
studied in the literature starting with [29], and including the recent studies
[8] and [12], to be discussed further below.

###  1.1 Convergence Notions for Probability Measures

For the analysis of the technical results, we will use different convergence
and distance notions for probability measures.

Two important notions of convergences for sequences of probability measures
are weak convergence, and convergence under total variation. For some
$N\in\mathbb{N}$ a sequence $\\{\mu_{n},n\in\mathbb{N}\\}$ in
$\mathcal{P}(\mathbb{X})$ is said to converge to
$\mu\in\mathcal{P}(\mathbb{X})$ _weakly_ if
$\int_{\mathbb{X}}c(x)\mu_{n}(dx)\to\int_{\mathbb{X}}c(x)\mu(dx)$ for every
continuous and bounded $c:\mathbb{X}\to\mathbb{R}$. One important property of
weak convergence is that the space of probability measures on a complete,
separable, and metric (Polish) space endowed with the topology of weak
convergence is itself complete, separable, and metric [25]. One such metric is
the bounded Lipschitz metric [34, p.109], which is defined for
$\mu,\nu\in\mathcal{P}(\mathbb{X})$ as

$\rho_{BL}(\mu,\nu):=\sup_{\|f\|_{BL}\leq 1}|\int fd\mu-\int fd\nu|$ (1)

where

$\|f\|_{BL}:=\|f\|_{\infty}+\sup_{x\neq y}\frac{|f(x)-f(y)|}{d(x,y)}$

and $\|f\|_{\infty}=\sup_{x\in\mathbb{X}}|f(x)|$.

We next introduce the first order Wasserstein metric. The _Wasserstein metric_
of order 1 for two distributions $\mu,\nu\in\mathcal{P}(\mathbb{X})$ is
defined as

$\displaystyle
W_{1}(\mu,\nu)=\inf_{\eta\in\mathcal{H}(\mu,\nu)}\int_{\mathbb{X}\times\mathbb{X}}\eta(dx,dy)|x-y|,$

where $\mathcal{H}(\mu,\nu)$ denotes the set of probability measures on
$\mathbb{X}\times\mathbb{X}$ with first marginal $\mu$ and second marginal
$\nu$. Furthermore, using the dual representation of the first order
Wasserstein metric, we equivalently have

$\displaystyle W_{1}(\mu,\nu)=\sup_{Lip(f)\leq 1}\left|\int f(x)\mu(dx)-\int
f(x)\nu(dx)\right|$

where $Lip(f)$ is the minimal Lipschitz constant of $f$.

A sequence $\\{\mu_{n}\\}$ is said to converge in $W_{1}$ to
$\mu\in\mathcal{P}(\mathbb{R}^{N})$ if $W_{1}(\mu_{n},\mu)\to 0$. For compact
$\mathbb{X}$, the Wasserstein distance of order $1$ metrizes the weak topology
on the set of probability measures on $\mathbb{X}$ (see [34, Theorem 6.9]).
For non-compact $\mathbb{X}$ convergence in the $W_{1}$ metric implies weak
convergence (in particular this metric bounds from above the Bounded-Lipschitz
metric [34, p.109], which metrizes the weak convergence).

For probability measures $\mu,\nu\in\mathcal{P}(\mathbb{X})$, the _total
variation_ metric is given by

$\displaystyle\|\mu-\nu\|_{TV}$
$\displaystyle=2\sup_{B\in\mathcal{B}(\mathbb{X})}|\mu(B)-\nu(B)|=\sup_{f:\|f\|_{\infty}\leq
1}\left|\int f(x)\mu(dx)-\int f(x)\nu(dx)\right|,$

where the supremum is taken over all measurable real $f$ such that
$\|f\|_{\infty}=\sup_{x\in\mathbb{X}}|f(x)|\leq 1$. A sequence $\mu_{n}$ is
said to converge in total variation to $\mu\in\mathcal{P}(\mathbb{X})$ if
$\|\mu_{n}-\mu\|_{TV}\to 0$.

##  2 A Q-Learning Convergence Theorem under Non-Markovian Environments

Q-learning under non-Markovian settings have been studied recently in a few
publications. Prior to such recent studies, we note that [29] showed the
convergence of Q-learning for POMDPs with measurements viewed as state
variables under certain conditions involving unique ergodicity of the hidden
state process under the exploration. However, what the results mean was not
studied.

Recently, [19] showed the convergence of Q-learning with finite window
measurements and showed near optimality of the resulting limit under filter
stability conditions. In the following, we will adapt the proof method in [19]
to the setup where the environment is an ergodic process but also generalize
the class of problems for which the limit of the iterates can be shown to
imply near optimality (for POMDPS) or near-equilibrium (for stochastic games).

The convergence result will serve complement to two highly related recent
studies: [12] and [8], but with both different contexts and interpretations as
well as mathematical analysis.

[12] presents a general paradigm of reinforcement learning under complex
environments where an agent responds with the environment. A regret framework
is considered, where the regret comparison is with regard to policies from a
possibly suboptimal collection of policies. The variables are assumed to be
finite, even though an infinite past dependence is allowed. The distortion
measure for approximation is a uniform error among all past histories which
are compatible with the presumed state. A uniform convergence result for the
convergence of time averages is implicitly imposed in the paper. [8] considers
the convergence of Q-learning under non-Markovian environments where the cost
function structure is aligned with the paradigm in [12]. The setup in [8]
assumes that the realized cost is a measurable function of the assumed finite
state, a finite-space valued observable realization and the finite action;
furthermore a continuity and measurability condition for the infinite
dimensional observable process history is imposed which may be restrictive
given the infinite dimensional history process and subtleties involved for
such conditioning operations, e.g. in the theory of non-linear filtering
processes [9]. [8] pursues an ODE method for the convergence analysis (which
was pioneered in [7]).

Regarding the comment on the infinite past dependence, the approximations in
both [12] and [8] require a worst case error in a sample-path sense, which,
for example, is too restrictive for POMDPs, as we have studied in [19] and
[20], in view of the term $L_{t}$ defined below in (3.2). Notably, for such
problems, filter stability only provides guarantees in expectation and when
sample path results are presented, these typically only involve asymptotic
merging and not uniform merging.

In our setup, there is an underlying model and the true incurred costs admit
exogenous uncertainty which impacts the incurred costs and the considered
hidden or observable random variables may be uncountable space valued. We
adopt the general and concise stochastic proof method presented in [19] (and
[18]), tailored to ergodic non-Markovian dynamics, to allow for convergence to
a limit. The generality of our setup requires us to precisely present
conditions for convergence.

Let $\\{C_{t}\\}_{t}$ be $\mathbb{R}$-valued, $\\{S_{t}\\}_{t}$ be
$\mathbb{S}$-valued and $\\{U_{t}\\}_{t}$ be $\mathbb{U}$-valued three
stochastic processes. Consider the following iteration defined for each
$(s,u)\in\mathbb{S}\times\mathbb{U}$ pair

$\displaystyle
Q_{t+1}(s,u)=\left(1-\alpha_{t}(s,u)\right)Q_{t}(s,u)+\alpha_{t}(s,u)\left(C_{t}+\beta
V_{t}(S_{t+1})\right)$ (2)

where $V_{t}(s)=\min_{u\in\mathbb{U}}Q_{t}(s,u)$, and $\alpha_{t}(s,u)$ is a
sequence of constants also called the learning rates. We assume that the
process $U_{t}$ is selected so that the following conditions hold. An umbrella
sufficient condition is the following:

######  Assumption 2.1.

$\mathbb{S},\mathbb{U}$ are finite sets, and the joint process
$(S_{t+1},S_{t},U_{t},C_{t})$ is asymptotically ergodic in the sense that for
the given initialization random variable $S_{0}$, for any measurable function
$f$, we have that with probability one,

$\displaystyle\frac{1}{N}\sum_{t=0}^{N-1}f(S_{t+1},S_{t},U_{t},C_{t})\to\int
f(s_{1},s,u,c)\pi(ds_{1},ds,du,dc)$

for some measure $\pi$ such that $\pi(B)>0$ for any measurable
$B\subset\mathbb{S}\times\mathbb{S}\times\mathbb{U}\times\mathbb{R}$.

The above implies Assumption 2.2(ii)-(iii) below:

######  Assumption 2.2.

  * i.

$\alpha_{t}(s,u)=0$ unless $(S_{t},U_{t})=(s,u)$. Furthermore,

$\displaystyle\alpha_{t}(s,u)=\frac{1}{1+\sum_{k=0}^{t}1_{\\{S_{k}=s,U_{k}=u\\}}}$

and with probability $1$, $\sum_{t}\alpha_{t}(s,u)=\infty$

  * ii.

For $C_{t}$, we have

$\displaystyle\frac{\sum_{k=0}^{t}C_{k}1_{\\{S_{k}=s,U_{k}=u\\}}}{\sum_{k=0}^{t}1_{\\{S_{k}=s,U_{k}=u\\}}}\to
C^{*}(s,u),$

almost surely for some $C^{*}$.

  * iii.

For the $S_{t}$ process, we have, for any function $f$,

$\displaystyle\frac{\sum_{k=0}^{t}f(S_{k+1})1_{\\{S_{k}=s,U_{k}=u\\}}}{\sum_{k=0}^{t}1_{\\{S_{k}=s,U_{k}=u\\}}}\to\int
f(s_{1})P^{*}(ds_{1}|s,u)$

almost surely for some $P^{*}$.

Note that a stationary assumption is not required. Under Assumption 2.1, we
have that with $f(S_{t+1},S_{t},U_{t},C_{t})=C_{t}1_{\\{S_{t}=s,U_{t}=u\\}}$

$\displaystyle\frac{1}{N}\sum_{t=0}^{N-1}C_{t}1_{\\{S_{t}=s,U_{t}=u\\}}\to\int_{C\in\mathbb{R}}C\pi(S=s,U=u,dC).$

We also have that with
$f(S_{t+1},S_{1},U_{t},C_{t})=1_{\\{S_{t}=s,U_{t}=u\\}}$

$\displaystyle\frac{1}{N}\sum_{t=0}^{N-1}1_{\\{S_{t}=s,U_{t}=u\\}}\to\pi(S=s,U=u).$

Hence, we can write

$\displaystyle\frac{\frac{1}{t+1}\sum_{k=0}^{t}C_{k}1_{\\{S_{k}=s,U_{k}=u\\}}}{\frac{1}{t+1}\sum_{k=0}^{t}1_{\\{S_{k}=s,U_{k}=u\\}}}\to\int
C\pi(dC|S=s,U=u)=:C^{*}(s,u)$

which implies Assumption 2.2 (ii). Similarly, one can also establish
Assumption 2.2 (iii) under Assumption 2.1.

As before, let $\mathbb{S},\mathbb{U}$ be finite sets. Consider the following
equation

$\displaystyle
Q^{*}(s,u)=C^{*}(s,u)+\beta\sum_{s_{1}\in\mathbb{S}}V^{*}(s_{1})P^{*}(s_{1}|s,u)$
(3)

for some functions $Q^{*}$, $C^{*}$, to be defined explicitly, and for some
regular conditional probability distribution $P^{*}(\cdot|s,u)$, where
$V^{*}(u):=\min_{u}Q^{*}(s,u)$.

######  Theorem 2.1.

Under Assumption 2.2, $Q_{t}(s,u)\to Q^{*}(s,u)$ almost surely for each
$(s,u)\in\mathbb{S}\times\mathbb{U}$ pair where $Q^{*}$ satisfies (3).

###### Proof.

We adapt the proof method presented in [19, Theorem 4.1], where instead of
positive Harris recurrence, we build on ergodicity. We first prove that the
process $Q_{t}$, determined by the algorithm in (2), converges almost surely
to $Q^{*}$. We define

$\displaystyle\Delta_{t}(s,u)$ $\displaystyle:=Q_{t}(s,u)-Q^{*}(s,u)$
$\displaystyle F_{t}(s,u)$ $\displaystyle:=C_{t}+\beta
V_{t}(S_{t+1})-Q^{*}(s,u)$ $\displaystyle\hat{F}_{t}(s,u)$
$\displaystyle:=C^{*}(s,u)+\beta\sum_{I_{1}}V_{t}(s_{1})P^{*}(s_{1}|s,u)-Q^{*}(s,u),$

where $V_{t}(s)=\min_{u}Q_{t}(s,u)$.

Then, we can write the following iteration

$\displaystyle\Delta_{t+1}(s,u)=(1-\alpha_{t}(s,u))\Delta_{t}(s,u)+\alpha_{t}(s,u)F_{t}(s,u).$

Now, we write $\Delta_{t}=\delta_{t}+w_{t}$ such that

$\displaystyle\delta_{t+1}(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))\delta_{t}(s,u)+\alpha_{t}(s,u)\hat{F}_{t}(s,u)$
$\displaystyle w_{t+1}(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))w_{t}(s,u)+\alpha_{t}(s,u)r_{t}(s,u)$

where $r_{t}:=F_{t}-\hat{F}_{t}=\beta
V_{t}(S_{t+1})-\beta\sum_{s_{1}}V_{t}(s_{1})P^{*}(s_{1}|s,u)+C_{t}-C^{*}(s,u)$.
Next, we define

$\displaystyle r_{t}^{*}(s,u)=\beta
V^{*}(S_{t+1})-\beta\sum_{s_{1}}V^{*}(s_{1})P^{*}(s_{1}|s,u)+C_{t}-C^{*}(s,u)$

We further separate $w_{t}=u_{t}+v_{t}$ such that

$\displaystyle u_{t+1}(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))u_{t}(s,u)+\alpha_{t}(s,u)e_{t}(s,u)$
$\displaystyle v_{t+1}(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))v_{t}(s,u)+\alpha_{t}(s,u)r^{*}_{t}(s,u)$

where $e_{t}=r_{t}-r^{*}_{t}$.

We now show that $v_{t}(s,u)\to 0$ almost surely for all $(s,u)$. We have

$\displaystyle v_{t+1}(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))v_{t}(s,u)+\alpha_{t}(s,u)r^{*}_{t}(s,u).$

When the learning rates are chosen such that $\alpha_{t}(s,u)=0$ unless
$(S_{t},U_{t})=(s,u)$, and,

$\alpha_{t}(s,u)={1\over 1+\sum_{k=0}^{t}\mathbbm{1}_{\\{S_{k}=s,U_{k}=u\\}}}$

this term reduces to

$\displaystyle
v_{t+1}(s,u)=\frac{\sum_{k=0}^{t}r^{*}_{k}(s,u)\mathbbm{1}_{\\{S_{k}=s,,U_{k}=u\\}}+v_{0}(s,u)}{1+\sum_{k=0}^{t}\mathbbm{1}_{\\{S_{k}=s,U_{k}=u\\}}}.$

Recall that

$\displaystyle r_{k}^{*}(s,u)=\beta
V^{*}(S_{k+1})-\beta\sum_{s_{1}}V^{*}(s_{1})P^{*}(s_{1}|s,u)+C_{k}-C^{*}(s,u).$

Hence, it is a direct implication of Assumption 2.2 that $v_{t}(s,u)\to 0$
almost surely for all $(s,u)$.

Now, we go back to the iterations:

$\displaystyle\delta_{t+1}(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))\delta_{t}(s,u)+\alpha_{t}(s,u)\hat{F}_{t}(s,u)$
$\displaystyle u_{t+1}(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))u_{t}(s,u)+\alpha_{t}(s,u)e_{t}(s,u)$
$\displaystyle v_{t+1}(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))v_{t}(s,u)+\alpha_{t}(s,u)r^{*}_{t}(s,u).$

Note that, we want to show $\Delta_{t}=\delta_{t}+u_{t}+v_{t}\to 0$ almost
surely and we have that $v_{t}(s,u)\to 0$ almost surely for all $(s,u)$. The
following analysis holds for any path that belongs to the probability one
event in which $v_{t}(s,u)\to 0$. For any such path and for any given
$\epsilon>0$, we can find an $N<\infty$ such that
$\|v_{t}\|_{\infty}<\epsilon$ for all $t>N$ as $(s,u)$ takes values from a
finite set.

We now consider the term $\delta_{t}+u_{t}$ for $t>N$:

$\displaystyle(\delta_{t+1}+u_{t+1})(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))(\delta_{t}+u_{t})(s,u)+\alpha_{t}(s,u)(\hat{F}_{t}+e_{t})(s,u).$
(4)

Observe that for $t>N$,

$\displaystyle(\hat{F}_{t}+e_{t})(s,u)=(F_{t}-r_{t}^{*})(s,u)=\beta
V_{t}(S_{t+1})-\beta V^{*}(S_{t+1})$
$\displaystyle\leq\beta\max_{s,u}|Q_{t}(s,u)-Q^{*}(s,u)|=\beta\|\Delta_{t}\|_{\infty}$
$\displaystyle\leq\beta\|\delta_{t}+u_{t}\|_{\infty}+\beta\epsilon$

where the last step follows from the fact that $v_{t}\to 0$ almost surely. By
choosing $C<\infty$ such that $\hat{\beta}:=\beta(C+1)/C<1$, for
$\|\delta_{t}+u_{t}\|_{\infty}>C\epsilon$, we can write that

$\displaystyle\beta\|\delta_{t}+u_{t}+\epsilon\|_{\infty}\leq\hat{\beta}\|\delta_{t}+u_{t}\|_{\infty}.$

Now we rewrite (4)

$\displaystyle(\delta_{t+1}+u_{t+1})(s,u)$
$\displaystyle=(1-\alpha_{t}(s,u))(\delta_{t}+u_{t})(s,u)+\alpha_{t}(s,u)(\hat{F}_{t}+e_{t})(s,u)$
$\displaystyle\leq(1-\alpha_{t}(s,u))(\delta_{t}+u_{t})(s,u)+\alpha_{t}(s,u)\hat{\beta}\|\delta_{t}+u_{t}\|_{\infty}$
(5) $\displaystyle<\|\delta_{t}+u_{t}\|_{\infty}$

Hence $\max_{s,u}((\delta_{t+1}+u_{t+1})(s,u))$ monotonically decreases for
$\|\delta_{t}+u_{t}\|_{\infty}>C\epsilon$ and hence there are two
possibilities: it either gets below $C\epsilon$ or it never gets below
$C\epsilon$ in which case by the monotone non-decreasing property it will
converge to some number, say $M_{1}$ with $M_{1}\geq C\epsilon$.

First, we show that once the process hits below $C\epsilon$, it always stays
there. Suppose $\|\delta_{t}+u_{t}\|_{\infty}<C\epsilon$,

$\displaystyle(\delta_{t+1}+u_{t+1})(s,u)$
$\displaystyle\leq(1-\alpha_{t}(s,u))(\delta_{t}+u_{t})(s,u)+\alpha_{t}(s,u)\beta\left(\|\delta_{t}+u_{t}\|_{\infty}+\epsilon\right)$
$\displaystyle\leq(1-\alpha_{t}(s,u))C\epsilon+\alpha_{t}(s,u)\beta(C\epsilon+\epsilon)$
$\displaystyle=(1-\alpha_{t}(s,u))C\epsilon+\alpha_{t}(s,u)\beta(C+1)\epsilon$
$\displaystyle\leq(1-\alpha_{t}(s,u))C\epsilon+\alpha_{t}(s,u)C\epsilon,\quad(\beta(C+1)\leq
C)$ $\displaystyle=C\epsilon.$

To show that $M_{1}\geq C\epsilon$, is not possible, we start by (5), we have
that for all $(s,u)$

$\displaystyle\left|(\delta_{k+1}+u_{k+1})(s,u)\right|$
$\displaystyle\leq(1-\alpha_{k}(s,u))\left|(\delta_{k}+u_{k})(s,u)\right|+\alpha_{k}(s,u)\hat{\beta}\|\delta_{k}+u_{k}\|_{\infty}$

One can iteratively show that the limit of these iterations are bounded by the
limit of the following:

$\displaystyle\left|(\delta_{k+1}+u_{k+1})(s,u)\right|$
$\displaystyle=(1-\alpha_{k}(s,u))\left|(\delta_{k}+u_{k})(s,u)\right|+\alpha_{k}(s,u)\hat{\beta}\|\delta_{k}+u_{k}\|_{\infty}$
(6)

Assume that the sequence $\|\delta_{k}+u_{k}\|_{\infty}$ is bounded by some
constant $K_{0}$. The following iterates

$\displaystyle\left|(\delta_{k+1}+u_{k+1})(s,u)\right|$
$\displaystyle=(1-\alpha_{k}(s,u))\left|(\delta_{k}+u_{k})(s,u)\right|+\alpha_{k}(s,u)\hat{\beta}K_{0}$

will converge to the value $\hat{\beta}K_{0}$ for any initial point and
starting from any time instance $t$. This follows since the learning rates are
assumed to be linear, and under the linear rates, the iterates will be the
averages of the constant $\hat{\beta}K_{0}$. Furthermore, average of any
finitely many sample will not change the average of the infinite sequence.
Hence, the sequence $\|\delta_{k}+u_{k}\|_{\infty}$ will eventually become
smaller than $\hat{\beta}K_{0}+\delta$ for any arbitrarily small $\delta$.
Similarly, once the sequence is bounded by some
$K_{1}:=\hat{\beta}K_{0}+\delta$, they will essentially get smaller than
$\hat{\beta}K_{1}+\delta$ for any $\delta>0$. Repeating the same argument, one
can see that the iterates in (6) will essentially hit below $C\epsilon$.

This shows that the condition $\|\delta_{t}+u_{t}\|_{\infty}>C\epsilon$ cannot
be sustained indefinitely for some fixed $C$ (independent of $\epsilon$).
Hence, $(\delta_{t}+u_{t})$ process converges to some value below $C\epsilon$
for any path that belongs to the probability one set. Then, we can write
$\|\delta_{t}+u_{t}\|_{\infty}<C\epsilon$ for large enough $t$. Since
$\epsilon>0$ is arbitrary, taking $\epsilon\to 0$, we can conclude that
$\Delta_{t}=\delta_{t}+u_{t}+v_{t}\to 0$ almost surely.

Therefore, the process $Q_{t}$, determined by the algorithm in (2), converges
almost surely to $Q^{*}$. ∎

###  2.1 An Example: Machine Replacement with non i.i.d. Noise

In this section we study the implications of the previous result on a machine
replacement problem where the state process is not controlled Markov.

In this model, we have $\mathbb{X,U,W}=\\{0,1\\}$ with

$\displaystyle x_{t}=$ $\displaystyle\begin{cases}1\quad\text{ machine is
working at time t }\\\ 0\quad\text{ machine is not working at time t
}.\end{cases}$ $\displaystyle u_{t}=$ $\displaystyle\begin{cases}1\quad\text{
machine is being repaired at time t }\\\ 0\quad\text{ machine is not being
repaired at time t }.\end{cases}$

We assume that the noise variable $w_{t}$ is not i.i.d. but is a Markov
process with transition kernel

$\displaystyle Pr(w_{t+1}=0|w_{t}=0)=0.9,\quad Pr(w_{t+1}=0|w_{t}=1)=0.4$

Give the noise, we have the dynamics $x_{k+1}=f(x_{k},u_{k},w_{k})$ for the
controlled state process

$\displaystyle x_{1}=0\text{ if }x=0,u=0,w=0,\qquad x_{1}=0\text{ if
}x=0,u=0,w=1$ $\displaystyle x_{1}=1\text{ if }x=0,u=1,w=0,\qquad
x_{1}=0\text{ if }x=0,u=1,w=1$ $\displaystyle x_{1}=1\text{ if
}x=1,u=0,w=0,\qquad x_{1}=0\text{ if }x=1,u=0,w=1$ $\displaystyle
x_{1}=1\text{ if }x=1,u=1,w=0,\qquad x_{1}=0\text{ if }x=1,u=1,w=1$

In words, if the noise $w=1$ then the machine breaks down at the next time
step independent of the repair or the state of the machine. If the noise is
not present, i.e. $w=0$ then the machine is fixed if we decide to repair it,
but stays broken if it was broken at the last step and we did not repair it.

The one stage cost function is given by

$\displaystyle c(x,u)=$ $\displaystyle\begin{cases}R+E\quad&x=0,u=1\\\
E\quad&x=0,u=0\\\ 0\quad&x=1,u=0\\\ R\quad&x=1,u=1\end{cases}$

where $R$ is the cost of repair and $E$ is the cost incurred by a broken
machine.

We study the example with discount factor $\beta=0.7$, and $R=1,E=1.5$. For
the exploration policy, we use a random policy such that
$Pr(\gamma(x)=0)=\frac{1}{2}$ and $Pr(\gamma(x)=1)=\frac{1}{2}$ for all $x$.

Note that the state process $x_{t}$ is no longer a controlled Markov chain.
However, we can check that Assumption 2.2 holds and that we can apply Theorem
2.1 to show that Q learning algorithm will converge. In particular, one can
show that the joint process $\left(x_{t},w_{t}\right)$ forms a Markov chain
under the exploration policy, and admits a stationary distribution, say $\pi$
such that

$\displaystyle\pi(x=0,w=0)=0.145,\quad\pi(x=0,w=1)=0.127,$
$\displaystyle\pi(x=1,w=0)=0.654,\quad\pi(x=1,w=1)=0.0728.$

Hence, the Q learning algorithm constructed using $s_{t}=x_{t}$ will converge
to the Q values of an MDP with the following transition probabilities:

$\displaystyle
P^{*}(s_{1}|s,u)=\frac{\sum_{w}\mathbbm{1}_{\\{s_{1}=f(s,u,w)\\}}\pi(s,u,w)}{\sum_{w}\pi(s,u,w)}$
(7)

where $\pi(s,u,w)=\frac{1}{2}\pi(s,w)$ for the exploration policy we use.

In Figure 1, on the left we plot the learned value functions for the non-
Markov state process when we take $s_{t}=x_{t}$. The plot on the right
represents the learned value function when we simulate the environment as an
MDP with the transition kernel $P^{*}$ given in (7). One can see that they
converge to the same values as expected from the theoretical arguments.

Figure 1: Q value convergence for non Markov and Markov state.

A further note is that since the state process is not Markov, the learned
policies are not optimal. In particular, the Q leaning algorithm with
$s_{t}=x_{t}$ learns the policy

$\displaystyle\gamma_{1}(1)=0,\quad\gamma_{1}(0)=1.$

Via simulation, the value of this policy can be found to be around $1.66$.

However, one can also construct the Q learning with $s_{t}=(x_{t},x_{t-1})$
(which is still not a Markovian state, however). The learned policy in this
case is

$\displaystyle\gamma_{2}(s)=\begin{cases}1\text{ if }s=(0,0)\\\ 0\text{ o.w.
}\end{cases}$

The value of this policy can be simulated to be around $1.59$, and thus
performs better than the policy for the state variable $s_{t}=x_{t}$.

In the following, we will discuss a number of applications, together with
conditions under which the limit of the iterates are near-optimal.

##  3 Implications and Applications under Various Information Structures

In this section, we study the implications and applications of the convergence
result in Theorem 2.1; some of the applications and refinements are new and
some are from recent results viewed in a unified lens.

We first start with a brief review involving Markov Decision Processes.
Consider the model $x_{t+1}=f(x_{t},u_{t},w_{t})$, where $x_{t}$ is an
$\mathbb{X}$-valued state variable, $u_{t}$ a $\mathbb{U}$-valued control
action variable, $w_{t}$ a $\mathbb{W}$-valued i.i.d noise process, and $f$ a
function, where $\mathbb{X},\mathbb{U},\mathbb{W}$ are appropriate spaces,
defined on some probability space $(\Omega,{\cal F},P)$. By, e.g. [16, Lemma
1.2], the model above contains processes satisfying the following for all
Borel $B$ and $t\geq 0$

$\displaystyle P(x_{t+1}\in
B|x_{[0,t]}=a_{[0,t]},u_{[0,t]}=b_{[0,t]})=P(x_{t+1}\in
B|x_{t}=a_{t},u_{t}=b_{t})$ $\displaystyle=:{\cal T}(B|a_{t},b_{t})$ (8)

where ${\cal T}(\cdot|x,u)$ is a stochastic kernel from
$\mathbb{X}\times\mathbb{U}$ to $\mathbb{X}$. Here,
$x_{[0,t]}:=\\{x_{0},x_{1},\cdots,x_{t}\\}$. A stochastic process which
satisfies (3) is called a controlled Markov chain. Let the control actions
$u_{t}$ be generated via a control policy $\gamma=\\{\gamma_{t},t\geq 0\\}$
with $u_{t}=\gamma_{t}(I_{t})$, where $I_{t}$ is the information available to
the Decision Maker (DM) or controller at time $t$. If
$I_{t}=\\{x_{0},\cdots,x_{t};u_{0},\cdots,u_{t-1}\\}$, we have a fully
observed system and an optimization problem is referred to as a Markov
Decision Process (MDP). As an optimization criterion, given a cost function
$c:\mathbb{X}\times\mathbb{U}\to\mathbb{R}_{+}$, one may consider
$J_{\beta}(x,\gamma)=E^{\gamma}_{x}[\sum_{t=0}^{\infty}\beta^{t}c(x_{t},u_{t})],$
for some $\beta\in(0,1)$ and $x_{0}=x$. This is called a discounted infinite-
horizon optimal control problem [5].

If the DM has only access to noisy measurements $y_{t}=g(x_{t},v_{t})$, with
$v_{t}$ being another i.i.d. noise, and
$I_{t}=\\{y_{0},\cdots,y_{t};u_{0},\cdots,u_{t-1}\\}$, we then have a
Partially Observable Markov Decision Process (POMDP). We let
$O(y_{t}\in\cdot|x_{t}=x)$ denote the transition kernel for the measurement
variables. We will assume that $c$ is continuous and bounded, though the
boundedness can be relaxed.

We assume in the following that $\mathbb{X}$ is a compact subset of a Polish
space and that $\mathbb{Y}$ is finite. We assume that $\mathbb{U}$ is a
compact set. However, without any loss, but building on [27, Chapter 3], under
weak Feller continuity conditions (i.e., $E[f(x_{1})|x_{0}=x,u_{0}=u]$ is
continuous in $(x,u)\in\mathbb{X}\times\mathbb{U}$ for every bounded
continuous $f$), we can approximate $\mathbb{U}$ with a finite set with an
arbitrarily small performance loss. Accordingly, we will assume that this set
is finite.

The same applies when a POMDP is reduced to a belief-MDP and the belief-MDP is
weak Feller: POMDPs can be reduced to a completely observable Markov process
[38, 26], whose states are the posterior state distributions or beliefs:
$\pi_{t}(\,\cdot\,):=P\\{X_{t}\in\,\cdot\,|Y_{0},\ldots,Y_{t},U_{0},\ldots,U_{t-1}\\}\in{\cal
P}(\mathbb{X})$, where ${\cal P}(\mathbb{X})$ is the set of probability
measures on $\mathbb{X}$. We call $\pi_{t}$ the filter process, whose
transition probability can be constructed via a Bayesian update. With
$F(\pi,u,y):=P\\{X_{t+1}\in\,\cdot\,|\pi_{t}=\pi,u_{t}=u,y_{t+1}=y\\}$, and
the stochastic kernel
$O(\,\cdot\,|\pi,u)=P\\{y_{t+1}\in\,\cdot\,|\pi_{t}=\pi,u_{t}=u\\}$, we can
write a transition kernel, $\eta$, for the belief process [J43]:

$\displaystyle\eta(\,\cdot\,|\pi,u)=\int_{\mathbb{Y}}1_{\\{F(\pi,u,y)\in\,\cdot\,\\}}O(dy|\pi,u).$
(9)

The equivalent cost function is

$\tilde{c}(\pi_{t},u_{t}):=\int_{\mathbb{X}}c(x,u_{t})\pi_{t}(dx).$

Thus, the filter process defines a belief-MDP. $\eta$ is a weak Feller kernel
if (a) If ${\cal T}$ is weakly continuous and the measurement kernel
$O(y_{t}\in\cdot|x_{t}=x)$ is total variation continuous [13], or (b) if the
kernel ${\cal T}$ is total variation continuous (with no assumptions on $O$)
[17].

We will also consider multi-agent models, to be discussed further below.

Recall (3) which is the limit of the Q iterates if they converge:

$\displaystyle
Q^{*}(s,u)=C^{*}(s,u)+\beta\sum_{s_{1}\in\mathbb{S}}V^{*}(s_{1})P^{*}(s_{1}|s,u).$

We note that these Q values correspond to an MDP model with state space
$\mathbb{S}$, the action space $\mathbb{U}$, the stage-wise cost function is
$C^{*}(s,u)$ and the transition function is $P^{*}(s_{1}|s,u)$. Hence, the
policies constructed using these Q values are optimal for the corresponding
MDP. In the following, we will present some bounds in terms of how ‘close’ the
original control model, and the approximate MDP model the limit Q values
correspond to.

###  3.1 Finite MDPs

Consider a finite MDP where the state process $x_{t}$ takes values in some
finite set $\mathbb{X}$, the control action process $u_{t}$ takes values in
some finite set $\mathbb{U}$. The dynamics for the state process is governed
by the following

$\displaystyle x_{t+1}\sim P^{*}(\cdot|x_{t},u_{t})$

and at each time $t$, the controller receives a stage-wise cost

$c(x_{t},u_{t}).$

It is clear that Assumption 2.2 and Theorem 2.1 apply with
$C_{t}:=c(x_{t},u_{t})$, and $S_{t}=x_{t}$. Furthermore, one can show that the
limit $Q^{*}$ is the optimal Q values of the system. This, of course, is a
standard result [35, 32, 3, 31, 30, 6].

###  3.2 Quantized Q-Learning for Weakly Continuous MDPs with General Spaces

In this section, we assume that $\mathbb{X}$ is a compact subset of a Polish
space and that $\mathbb{Y}$ and $\mathbb{U}$ are finite sets.

Consider a controlled Markov chain $X_{t}$ whose dynamics are determined by

$\displaystyle X_{t+1}\sim\mathcal{T}(\cdot|x_{t},u_{t}).$

Furthermore, let $C_{t}:=c(X_{t},U_{t})$ take values from a bounded set. The
controller observes the cost realizations and some noisy version of the hidden
state variable. In particular, we assume that the controller observes the
measurement process $Y_{t}$ as

$\displaystyle Y_{t}=g(X_{t},V_{t})$ (10)

for some measurable function $g$ and for some i.i.d. noise process $V_{t}$.

In the following, we let the measurement structure be so that it corresponds
to a quantization of the state variable $X_{t}$: We discretize continuous
MDPs, where the state space $\mathbb{X}$ is quantized such that for disjoint
$\\{B_{i}\\}_{i=1}^{M}$ with $\cup_{i=1}^{M}B_{i}=\mathbb{X}$, we define a
finite set $\mathbb{S}=\\{y_{1},\dots,y_{m}\\}$ and write

$\displaystyle y_{i}=g(x),\text{ if }x\in B_{i}.$

We take $S_{k}=g(X_{k})=Y_{k}$. Therefore, the problem can be seen as a POMDP
and thus an adaptation of Assumption 2.1 will guarantee the convergence of the
iterations in (2). In particular, we present the following assumption that
implies Assumption 2.1 in the context of quantized MDPs.

######  Assumption 3.1.

Under the exploration policy $\gamma$ and initialization, the controlled state
and control action joint process $\\{X_{t},U_{t}\\}$ is asymptotically ergodic
in the sense that for any measurable function $f$ we have that

$\displaystyle\lim_{N\to\infty}\frac{1}{N}\sum_{t=0}^{N-1}f(X_{t},U_{t})=\int
f(x,u)\pi^{\gamma}(dx,du)$

for some $\pi^{\gamma}\in\mathcal{P}(\mathbb{X}\times\mathbb{U})$ such that
$\pi^{\gamma}(B)>0$ for any $B\subset\mathbb{X}\times\mathbb{U}$.

We note that a sufficient condition for the ergodicity assumption, for every
initialization of $X_{0}$, would be positive Harris recurrence under the
exploration policy.

The limit Q values correspond to an approximate control model (see [18]). For
near optimality of the learned polices [18, Corollary12] notes the following:

######  Assumption 3.2.

  * (a)

$\mathbb{X}$ is compact.

  * (b)

There exists a constant $\alpha_{c}>0$ such that
$|c(x,u)-c(x^{\prime},u)|\leq\alpha_{c}\|x-x^{\prime}\|$ for all
$x,x^{\prime}\in\mathbb{X}$ and for all $u\in\mathbb{U}$.

  * (c)

There exists a constant $\alpha_{T}>0$ such that
$W_{1}(\mathcal{T}(\cdot|x,u),\mathcal{T}(\cdot|x^{\prime},u))\leq\alpha_{T}\|x-x^{\prime}\|$
for all $x,x^{\prime}\in\mathbb{X}$ and for all $u\in\mathbb{U}$.

######  Theorem 3.1.

[18, Corollary 12] Under Assumption 2.2 (i) and Assumption 3.1, with
$S_{k}=g(X_{k})=Y_{k}$, the $Q_{t}$ iterates converges to a limit.
Furthermore:

  * (a)

Let Assumption 3.2 hold . Then, for the policy constructed from the limit Q
values, say $\hat{\gamma}$, we have

$\displaystyle\sup_{x_{0}\in\mathbb{X}}\left|J_{\beta}(x_{0},\hat{\gamma})-J^{*}_{\beta}(x_{0})\right|\leq\frac{2\alpha_{c}}{(1-\beta)^{2}(1-\beta\alpha_{T})}\bar{L}.$

where

$\displaystyle\bar{L}$ $\displaystyle:=\max_{i=1,\dots,M}\sup_{x,x^{\prime}\in
B_{i}}\|x-x^{\prime}\|.$

  * (b)

For asymptotic convergence (without a rate of convergence) to optimality as
the quantization rate goes to $\infty$, only weak Feller property of ${\cal
T}$ is sufficient for the the algorithm to be near optimal.

######  Remark 3.1.

Further error bounds under different set of assumptions, such as for systems
with non-compact state space $\mathbb{X}$ and non-uniform quantization and
models with total variation continuous transition kernels can be found in
[18]. Q-learning for average cost problems involving continuous space models
has recently been studied in [21].

###  3.3 Finite Window Memory POMDP with Uniform Geometric Controlled Filter
Stability

We now assume that $\mathbb{X}$ is a compact subset of a Polish space and that
$\mathbb{Y}$ and $\mathbb{U}$ are finite sets.

Suppose that the controller keeps a finite window of the most recent $N$
observation and control action variables, and perceives this as the state
variable, which is in general non-Markovian. That is we take

$S_{t}=\\{Y_{[t-N,t]},U_{[t-N,t-1]}\\},$

and $C_{t}:=c(X_{t},U_{t})$.

In this case, the pair $(S_{t},X_{t},U_{t})$ forms a controlled Markov chain,
even if $(S_{t},U_{t})$ does not. Under Assumption 2.1, it can be shown that
Assumption 2.2 holds. We state the ergodicity assumption formally next.

######  Assumption 3.3.

  * (i)

Under the exploration policy $\gamma$ and initialization, and the controlled
state and control action joint process $\\{X_{t},U_{t}\\}$ is asymptotically
ergodic in the sense that for any measurable function $f$ we have that

$\displaystyle\lim_{N\to\infty}\frac{1}{N}\sum_{t=0}^{N-1}f(X_{t},U_{t})=\int
f(x,u)\pi^{\gamma}(dx,du)$

for some $\pi^{\gamma}\in\mathcal{P}(\mathbb{X}\times\mathbb{U})$.
Furthermore, we have that $P(Y_{t}=y|x)>0$ for every $x\in\mathbb{X}$.

  * (ii)

Assumption 2.1(i) holds with $S_{t}=\\{Y_{[t-N,t]},U_{[t-N,t-1]}\\}$.

We note that a sufficient condition for the ergodicity assumption, for every
initialization of $X_{0}$, would be positive Harris recurrence under the
exploration policy.

The question then is if the limit Q values correspond to a meaningful control
problem, and how ‘close’ this control problem to the original POMDP. We denote
by $J_{\beta}(\pi_{N}^{-},\mathcal{T},\gamma^{N})$ the value of the partially
observed control problem when the initial prior measure of the hidden state
$X_{N}$ at time $N$ is given by $\pi_{N}^{-}$ and when we use finite window
control policy. In particular, the costs are incurred after the
$N$-measurements are collected. [19, Theorem 4.1] shows that the limit Q
values indeed correspond to an approximate control problem, and notes the
following bound on the optimality gap for the finite window control policies:

######  Theorem 3.2.

[19, Theorem 4.1] Under Assumption 3.3, the iterations in (2) converges with
$S_{t}=\\{Y_{[t-N,t]},U_{[t-N,t-1]}\\}$ and $C_{t}:=c(X_{t},U_{t})$.
Furthermore, if we denote the policies constructed using these Q values by
$\gamma^{N}$, and apply in the original problem, we get the following error
bound:

$\displaystyle
E\left[J_{\beta}(\pi_{N}^{-},\mathcal{T},\gamma^{N})-J_{\beta}^{*}(\pi_{N}^{-},\mathcal{T})|I_{0}^{N}\right]\leq\frac{2\|c\|_{\infty}}{(1-\beta)}\sum_{t=0}^{\infty}\beta^{t}L_{t}$

where $I_{0}^{N}$ is the first $N$ observation and control variables, and the
expectation is taken with respect to different realizations of $I_{0}^{N}$
under the initial distribution of the hidden state $\pi_{0}$ and the
exploration policy $\gamma$. Furthermore,

$\displaystyle\pi_{N}^{-}=P(X_{N}\in\cdot|I_{0}^{N})$

and

$\displaystyle
L_{t}:=\sup_{\hat{\gamma}\in\hat{\Gamma}}E_{\pi_{0}^{-}}^{\hat{\gamma}}\bigg{[}\|P^{\pi_{t}^{-}}(X_{t+N}$
$\displaystyle\in\cdot|Y_{[t,t+N]},U_{[t,t+N-1]})$
$\displaystyle-P^{\pi^{*}}(X_{t+N}\in\cdot|Y_{[t,t+N]},U_{[t,t+N-1]})\|_{TV}\bigg{]}$
(11)

and $\pi^{*}$ is the invariant measure on $x_{t}$ under the exploration policy
$\gamma$.

######  Remark 3.2.

The term $L_{t}$ is related to the filter stability problem, and some bounds
for it can be found in [19, Section 5], notably building on [23].

###  3.4 Quantized Approximations for Weak Feller POMDPs with only Asymptotic
Filter Stability

As noted earlier, any POMDP can be reduced to a completely observable Markov
process ([38], [26]) (see (9)), whose states are the posterior state
distributions or beliefs of the observer; that is, the state at time $t$ is

$\displaystyle\pi_{t}(\,\cdot\,):=P\\{X_{t}\in\,\cdot\,|y_{0},\ldots,y_{t},u_{0},\ldots,u_{t-1}\\}\in{\cal
P}(\mathbb{X}).$

We call this conditional probability measure process the filter process.

Recall the kernel $\eta$ (9) for the filter process. Now, by combining the
quantized Q-learning above and the weak Feller continuity results for the non-
linear filter kernel ([13] [17]), we can conclude that the setup in Section
3.2 is applicable though with a significantly more tedious analysis involving
ergodicity requirements. Additionally, one needs to quantize probability
measures. Accordingly, we take $S_{t}=g(\pi_{t})$ for some quantizer $g:{\cal
P}(\mathbb{X})\to{\cal P}(\mathbb{X})^{M}=:\\{B_{1},B_{2},\cdots,B_{|{\cal
P}(\mathbb{X})^{M}|}\\}$ with $|{\cal P}(\mathbb{X})^{M}|<\infty$, and
$C_{t}:=c(X_{t},U_{t})$.

We state the ergodicity condition formally:

######  Assumption 3.4.

Under the exploration policy $\gamma$ and initialization, the controlled
belief state and control action joint process $\\{\pi_{t},U_{t}\\}$ is
asymptotically uniquely ergodic in the sense that for any measurable function
$f$ we have that

$\displaystyle\lim_{N\to\infty}\frac{1}{N}\sum_{t=0}^{N-1}f(\pi_{t})=\int
f(\pi)\eta^{\gamma}(d\pi)$

for some $\eta^{\gamma}\in\mathcal{P}({\cal P}(\mathbb{X})\times\mathbb{U})$
such that $\eta^{\gamma}(B)>0$ for any quantization bin $B\subset{\cal
P}(\mathbb{X})$.

The condition that $\eta^{\gamma}(B)>0$ requires an analysis tailored for each
problem. For example, if the quantization is performed as in [20] by
clustering bins based on a finite past window, then the condition is satisfied
by requiring that $P(Y_{t}=y|x)>0$ for every $x\in\mathbb{X}$. If the
clustering is done, e.g. by quantization of the probability measures via first
quantizing $\mathbb{X}$ and then quantizing the probability measures on the
finite set (see [28, Section 5]), then the initialization could be done
according to the invariant probability measure corresponding to the hidden
Markov source.

Unique ergodicity of the dynamics follows from results in the literature, such
as, [22, Theorem 2] and [33, Prop 2.1], which holds when the randomized
control is memoryless under mild conditions on the process notably, the hidden
variable is a uniquely ergodic Markov chain and the measurement structure
satisfies filter stability in total variation in expectation (one can show
that weak merging in expectation also suffices); we refer the reader to [24,
Figure 1] for mild conditions leading to filter stability in this sense, which
is related to stochastic observability [24, Definition II.1]. Notably, a
uniform and geometric controlled filter stability is not required even though
this would be sufficient. Therefore, due to the weak Feller property of
controlled non-linear filters, we can apply the Q-learning algorithm to also
belief-based models to arrive at near optimal control policies. Nonetheless,
since positive Harris recurrence cannot typically be assumed for the filter
process, the initial state may not be arbitrary. If the invariant measure
under the exploration policy is the initial state, [33, Prop 2.1] implies that
the time averages will converge as imposed in Assumption 2.2. A sufficient
condition for unique ergodicity then is the following.

######  Assumption 3.5.

Under the exploration policy $\gamma$ the hidden process $\\{X_{t}\\}$ is
uniquely ergodic and the measurements are so that the filter is stable in
expectation under weak convergence.

######  Assumption 3.6.

The controlled transition kernel for the belief process $\eta(\cdot|\pi,u)$ is
Lipschitz continuous under the metric $\rho_{BL}$ such that

$\displaystyle\rho_{BL}\left(\eta(\cdot|z,u),\eta(\cdot|z^{\prime},u)\right)\leq\alpha_{T}\|z-z^{\prime}\|$

for all $u$, and $z,z^{\prime}\in\mathcal{P}(\mathbb{X})$ for some
$\alpha_{T}<\infty$ for a proper norm on $\mathcal{P}(\mathbb{X})$.

The following result from [20, Theorem 7] provides a set of assumptions on the
partially observed model to guarantee Assumption 3.6 when
$\mathcal{P}(\mathbb{X})$ is equipped with the weak convergence metrizing
$\rho_{BL}$ or the total variation metric $\|\cdot\|_{TV}$. We introduce the
following notation before the result:

######  Definition 3.1.

[11, Equation 1.16] For a kernel operator $K:S_{1}\to\mathcal{P}(S_{2})$ (that
is a regular conditional probability from $S_{1}$ to $S_{2}$) for standard
Borel spaces $S_{1},S_{2}$, we define the Dobrushin coefficient as:

$\displaystyle\delta(K)$
$\displaystyle=\inf\sum_{i=1}^{n}\min(K(x,A_{i}),K(y,A_{i}))$ (12)

where the infimum is over all $x,y\in S_{1}$ and all partitions
$\\{A_{i}\\}_{i=1}^{n}$ of $S_{2}$.

We note that this definition holds for continuous or finite/countable spaces
$S_{1}$ and $S_{2}$ and $0\leq\delta(K)\leq 1$ for any kernel operator.

Let

$\tilde{\delta}({\cal
T}):=\inf_{u\in\mathbb{U}}\delta(\mathcal{T}(\cdot|\cdot,u)).$

######  Theorem 3.3.

[20, Theorem 7]

  * i.

Assume that

$\displaystyle\|\mathcal{T}(\cdot|x,u)-\mathcal{T}(\cdot|x^{\prime},u)\|_{TV}\leq\alpha_{\mathbb{X}}|x-x^{\prime}|$

for some $\alpha_{\mathbb{X}}<\infty$ for all $u\in\mathbb{U}$. We have

$\displaystyle\rho_{BL}\left(\eta(\cdot|z,u),\eta(\cdot|z^{\prime},u)\right)\leq
3(1+\alpha_{\mathbb{X}})\rho_{BL}(z,z^{\prime}).$

  * ii.

Assume that

$\displaystyle\|\mathcal{T}(\cdot|x,u)-\mathcal{T}(\cdot|x^{\prime},u)\|_{TV}\leq\alpha_{\mathbb{X}}|x-x^{\prime}|$

for some $\alpha_{\mathbb{X}}<\infty$ for all $u\in\mathbb{U}$. Then we have

$\displaystyle\rho_{BL}\left(\eta(\cdot|z,u),\eta(\cdot|z^{\prime},u)\right)\leq(3-2\delta(Q))(1+\alpha_{\mathbb{X}})\rho_{BL}(z,z^{\prime}).$

  * iii.

Without any assumption

$\displaystyle\rho_{BL}\left(\eta(\cdot|z,u),\eta(\cdot|z^{\prime},u)\right)\leq
3\|z-z^{\prime}\|_{TV}.$

  * iv.

$\displaystyle\rho_{BL}\left(\eta(\cdot|z,u),\eta(\cdot|z^{\prime},u)\right)\leq(3-2\delta(Q))(1-\tilde{\delta}(\mathcal{T}))\|z-z^{\prime}\|_{TV}.$

######  Theorem 3.4.

  * (a)

Suppose that under the exploration policy and initialization the controlled
filter process satisfies Assumption 3.4 and 2.2(i) with $S_{t}=g(\pi_{t})$,
and $C_{t}=c(X_{t},U_{t})$. Then, the Q iterates converge almost surely.

  * (b)

Let Assumption 3.6 hold such that $\alpha_{T}\beta<1$ and assume that the cost
function $c(x,u)$ is Lipschitz continuous in $x$ such that

$\displaystyle\left|c(x,u)-c(x^{\prime},u)\right|\leq\alpha_{c}|x-x^{\prime}|.$

For the policy constructed using the limit Q values, say $\hat{\gamma}$ we
have the following bound:

$\displaystyle
J_{\beta}^{*}(\pi_{0},\hat{\gamma})-J_{\beta}^{*}(\pi_{0})\leq\frac{2\alpha_{c}}{(1-\beta)^{2}(1-\beta\alpha_{T})}\bar{L}.$

for some $K<\infty$ where

$\displaystyle\bar{L}:=\sup_{\pi}\left\|\pi-g(\pi)\right\|$

  * (c)

For asymptotic convergence (without a rate of convergence) to optimality as
the quantization rate goes to $\infty$ (i.e., $\bar{L}\to 0$), only weak
Feller property of $\eta$ is sufficient for the the algorithm to be near
optimal.

######  Remark 3.3.

We now present a comparison between the two approaches above: filter
quantization vs. finite window based learning:

  * (i)

For the filter quantization, we only need unique ergodicity of the filter
process under the exploration policy for which asymptotic filter stability in
expectation in weak or total variation is sufficient. The running cost can
start immediately without waiting for a window of measurements. On the other
hand, the controller must run the filter and quantize it in each iteration
while running the Q-learning algorithm; accordingly the controller must know
the model. Additionally, the initialization cannot be arbitrary (e.g. the
initialization for the filter may be the invariant measure under the
exploration policy).

  * (ii)

For the finite window approach, a uniform convergence of filter stability, via
$L_{t}$, is needed and it does not appear that only asymptotic filter
stability can suffice. On the other hand, this is a universal algorithm in
that the controller does not need to know the model. Furthermore, the
initialization satisfaction holds under explicit conditions; notably if the
hidden process is positive Harris recurrent, the ergodicity condition holds
for every initialization; both the convergence of the algorithm as well as its
implementation will always be well-defined.

For each setup, however, we have explicit and testable conditions.

######  Remark 3.4 (Further Models: Continuous-Time and Applications).

We note that the richness of the convergence theorem manifests itself also in
the applications involving continuous-time models [4] where quantized
Q-learning finds a natural application area, and applications to optimal
quantization [10] which also studies several subtleties with regard to
ergodicity of belief dynamics.

###  3.5 Multi-Agent Models and Joint Learning Dynamics: Subjective Q-Learning
and an Open Question

As our final application, we consider multi-agent models. Multi-agent
reinforcement learning (often referred to as MARL) is the study of emergent
behaviour in complex, and strategic environments, and is one of the important
frontiers in artificial intelligence research. Consider an environment with
$N$-agents, each of which generate actions, and whose rewards impact one
another. Notably,

$x^{i}_{t+1}=f(x^{i}_{t},u^{i}_{t},u^{-i}_{t},x^{-i}_{t},w_{t})$

with cost criteria

$\sum_{t}\beta^{t}c(x^{i}_{t},u^{i}_{t},u^{-i}_{t},x^{-i}_{t})$

or mean-field models with

$x^{i}_{t+1}=f(x^{i}_{t},u^{i}_{t},\mu^{N}_{t},w_{t})$

and sample path costs

$\sum_{t}\beta^{t}c(x^{i}_{t},u^{i}_{t},\mu^{N}_{t}),$

where

$\mu^{N}_{t}=\sum_{k=1}^{N}\delta_{x^{i}_{t}}(\cdot)$

We assume several information structures, for each $m=1,\cdots,N$: (i)
$I^{m}_{t}=\\{{\bf x}_{[0,t]},u^{m}_{[0,t]}\\}$, (ii)
$I^{m}_{t}=\\{x^{m}_{[0,t]},\mu^{N}_{[0,t]}\\}$, (iii)
$I^{m}_{t}=\\{x^{m}_{t},u^{m}_{[0,t]}\\}$. Accordingly, for each agent
$u^{m}_{t}=\gamma^{m}_{t}(I^{m}_{t})$ for all $t\in\mathbb{Z}_{+}$. Given
these policies, one would like to minimize the expected values of the cost
functions defined above.

Study of such decentralized systems is known to be challenging both for
stochastic teams and stochastic games, where the cost functions above may
depend on individual agents. Learning theory for such systems entails two
primary challenges:

The first immediate challenge for learning in such models is due to
decentralization of information: some relevant information will be unavailable
to some of the players. This may occur due to strategic considerations, as
competing agents may wish to hide their actions or knowledge from their
rivals, or it may occur simply because of obstacles in communicating,
observing, or storing large quantities of information in decentralized systems
and agents may be oblivious to their environment or the presence of other
agents.

The second difficulty inherent to MARL comes from the non-stationarity of the
environment from the point of view of any individual agent. As an agent learns
how to improve its performance, it will alter its behaviour, and this can have
a destabilizing effect on the learning processes of the remaining agents, who
may change their policies in response to outdated strategies. Notably, this
issue arises when one tries to apply single-agent RL algorithms—which
typically rely on state-action value estimates or gradient estimates that are
made using historical data—in multi-agent settings. A number of studies have
reported non-convergent play when single-agent algorithms using local
information are employed, without modification, in multi-agent settings. Thus,
for such models the main obstacle to convergence of Q-learning is due to the
presence of multiple active learners leading to a non-stationary environment
for all learners.

###  3.6 Two Time Scales and a Markov Chain over Play Path Graphs

To overcome this obstacle, also building on inspiration from prior work [14,
15, 2] modifies the Q-learning for stochastic games as follows: In the
variation of Q-learning, DMs are allowed to use constant policies for extended
periods of time called exploration phases. This is also referred to as two-
time scales approach.

Figure 2: An illustration of the $k-$th exploration phase.

As illustrated in Figure 2, the $k-$th exploration phase runs through times
$t=t_{k},\dots,t_{k+1}-1$, where

$t_{k+1}=t_{k}+T_{k}\qquad\mbox{(with $t_{0}=0$)}$

for some integer $T_{k}\in[1,\infty)$ denoting the length of the $k-$th
exploration phase. During the $k-$th exploration phase, DMs use some constant
policies $\pi_{k}^{1},\dots,\pi_{k}^{N}$ as their baseline policies with
occasional experimentation.

The essence of the main idea is to create a stationary environment over each
exploration phase so that DMs can almost accurately learn their optimal
Q-factors corresponding to the constant policies (which is also slightly
randomized to make room for exploration) used during each exploration phase
and update their policies.

This machinery has been adopted under two types of policy updates: (i) Best
response dynamics with inertia for weakly acyclic games [2] considered for the
case where each agent has access to the global state but only local state
(requiring typically deterministic policies), and (ii) a variation of it which
is referred to as satisficing paths dynamics [36, 37] which assumes that the
agents have access to a variety of information states and the policies may be
randomized.

Theorem 2.1, with the following memoryless updates for each agent, ensures
convergence under each exploration phase, under the required conditions.

  * i

[Global State] $S^{m}_{t}={\bf
X}_{t},U_{t}=U^{m}_{t},C_{t}=c(X^{i}_{t},U^{i}_{t},U^{-i}_{t},X^{-i}_{t})$ or
$c(X^{i}_{t},U^{i}_{t},\mu^{N}_{t})$ for the mean-field setup

  * ii

[Local State]
$S^{m}_{t}=X^{m}_{t},U_{t}=U^{m}_{t},C_{t}=c(X^{i}_{t},U^{i}_{t},U^{-i}_{t},X^{-i}_{t})$
or $c(X^{i}_{t},U^{i}_{t},\mu^{N}_{t})$

  * iii

[Local and Compressed Global/Mean-Field State] $S^{m}_{t}=\\{X^{m}_{t},F({\bf
X}_{t})\\},U_{t}=U^{m}_{t},C_{t}=c(X^{i}_{t},U^{i}_{t},U^{-i}_{t},X^{-i}_{t})$.

Subjective Satisficing Paths and Subjective Q-Learning Equilibrium

Consider the following subjective win-stay/lose-shift algorithm: At the end of
each exploration phase, if agents are $\epsilon$-satisfied, then they do not
alter their policies. However, if they are not in an $\epsilon$-equilibrium,
they randomly select a policy mapping their local perceived state to their
actions, possibly with some inertia, where the policy space is quantized. In
particular, the selected policies may be randomized (as they are not best
responses or near best responses).

######  Definition 3.2.

[36, 37] Let $\epsilon\geq 0$ and let $\pi^{-i}\in\Gamma_{S}$. A policy
$\pi^{i}\in\Gamma^{i}_{S}$ is called a
$(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-best-response to
$\pi^{-i}$ if

$V^{*i}_{\pi^{i},\pi^{-i}}(y)\leq\min_{a^{i}\in\mathbb{U}}W^{*i}_{\pi^{i},\pi^{-i}}(y,a^{i})+\epsilon,\quad\forall
y\in\mathbb{Y}.$

######  Definition 3.3.

[36, 37] Let $\epsilon\geq 0$. A joint policy $\pi^{*}\in\Gamma_{S}$ is called
a $(\mathcal{V}^{*},\mathcal{W}^{*})$-subjective $\epsilon$-equilibrium if,
for every $i\in\mathbb{N}$, we have

$V^{*i}_{\pi^{*i},\pi^{*-i}}(y)\leq\min_{a^{i}\in\mathbb{U}}W^{*i}_{\pi^{*i},\pi^{*-i}}(y,a^{i})+\epsilon,\quad\forall
y\in\mathbb{Y}.$

[37] introduced such a paradigm and presented conditions under which
equilibrium or subjective equilibrium is arrived at. The limit in which each
agent is $\epsilon$-satisfied with respect to the computed value functions, as
a result of the Q-learning iterations is referred to as a subjective
(Q-learning) equilibrium.

Accordingly, each agent then applies (2) during exploration phases. This is
stated explicitly in the following [36]:

1

2Set Parameters

3 $\Pi^{i}\subset\Gamma^{i}_{S}$ : a fine quantization of stationary policies
$\Gamma^{i}_{S}:\mathbb{S}\to{\cal P}(\mathbb{U})$, where
$s^{i}\in\mathbb{S}$, $u^{i}\in\mathbb{U}$

4

5$\\{T_{k}\\}_{k\geq 0}$: a sequence in $\mathbb{N}$ of learning phase lengths

6 set $t_{0}=0$ and $t_{k+1}=t_{k}+T_{k}$ for all $k\geq 0.$

7 $e^{i}\in(0,1)$: random policy updating probability

8 $d^{i}\in(0,\infty)$: tolerance level for sub-optimality

9

10Initialize $\pi_{0}^{i}\in\Pi^{i}$ (arbitrary),
$\widehat{Q}_{0}^{i}=0\in\mathbb{R}^{\mathbb{S}\times\mathbb{U}}$,
$\widehat{J}^{i}_{0}=0\in\mathbb{R}^{\mathbb{U}}$

11

12for $k\geq 0$ ($k^{th}$ exploration phase)

13 for $t=t_{k},t_{k}+1,\dots,t_{k+1}-1$

14 Observe $s^{i}_{t}$

15 Select $u^{i}_{t}\sim\pi^{i}_{k}(\cdot|s^{i}_{t})$

16

17 Observe $c^{i}_{t}:=c(x^{i}_{t},u^{i}_{t},x^{-i}_{t},u^{-i}_{t})$ and
$s^{i}_{t+1}$

18 Set
$n_{t}^{i}=\sum_{\tau=t_{k}}^{t}\textbf{1}\\{(s^{i}_{\tau},u^{i}_{\tau})=(s^{i}_{t},u^{i}_{t})\\}$

19 Set $m_{t}^{i}=\sum_{\tau=t_{k}}^{t}\textbf{1}\\{s^{i}_{\tau}=s^{i}_{t}\\}$

20
$\widehat{Q}_{t+1}^{i}(s^{i}_{t},u_{t}^{i})=\left(1-\frac{1}{{n_{t}^{i}}}\right)\widehat{Q}_{t}^{i}(s^{i}_{t},u_{t}^{i})+\frac{1}{{n_{t}^{i}}}\big{[}c^{i}_{t}+\beta\min_{a^{i}}\widehat{Q}_{t}^{i}(s^{i}_{t+1},a^{i})\big{]}$

21
$\widehat{J}^{i}_{t+1}(s^{i}_{t})=\left(1-\frac{1}{{m^{i}_{t}}}\right)\widehat{J}^{i}_{t}(s^{i}_{t})+\frac{1}{{m^{i}_{t}}}\left[c^{i}_{t}+\beta\widehat{J}^{i}_{t}(s^{i}_{t+1})\right]$

22

23

24 if  _
$\widehat{J}^{i}_{t_{k+1}}(y)\leq\min_{a^{i}}\widehat{Q}^{i}_{t_{k+1}}(y,a^{i})+\epsilon+d^{i}$
$\forall y\in\mathbb{S}$,_ then

25 $\pi^{i}_{k+1}=\pi^{i}_{k}$

26 else

27 $\pi^{i}_{k+1}\sim(1-e^{i})\delta_{\pi^{i}_{k}}+e^{i}\text{Unif}(\Pi^{i})$

28 Reset $\widehat{J}^{i}_{t_{k+1}}=0\in\mathbb{R}^{\mathbb{S}}$ and
$\widehat{Q}^{i}_{t_{k+1}}=0\in\mathbb{R}^{\mathbb{S}\times\mathbb{U}}$

29

Algorithm 1 Independent Learning via $\epsilon$-Subjective Satisficing:
Subjective Q-Learning [36]

Theorem 2.1 shows that the exploration phase in Algorithm 1 is such that the
two-time scale and satisficing-paths paradigm is applicable to a much broader
class of setups.

Building on the general approach presented in [36], it follows that under mild
numerical parameter selection conditions, if (i) a subjective Q-learning
$\epsilon$-equilibrium exists (with sufficiently fine quantization of the
randomized stationary policy space) and (ii) if there is a finite
$\epsilon$-subjective satisficing path from any initial policy profile to
subjective Q-learning $\epsilon$-equilibrium equilibrium, Algorithm 1 will
converge to a subjective equilibrium with arbitrarily high probability by
adjusting the $T_{k}$ terms accordingly.

Beyond the setups in which the limit may be close enough to each agent’s
objective equilibrium (case with global state, or mean-field state
information) [36], and symmetric games [37] conditions for the existence of
subjective Q-learning equilibria is an open problem and requires further
research. In particular, an application of Kakutani-Fan-Glicksberg theorem [1,
Corollary 17.55] would entail a detailed study on the continuous dependence of
the limit of Q-learning iterates in Theorem 2.1.

We hope that Theorem 2.1 will provide further motivation for research in this
direction.

##  4 Conclusion

In this paper, motivated by reinforcement learning in complex environments, we
presented a convergence theorem for Q-learning iterates, under a general,
possibly non-Markovian, stochastic environment. Our conditions for convergence
were an ergodicity and a positivity condition. We furthermore provided a
precise characterization on the limit of the iterates. We then considered the
implications and applications of this theorem to a variety of non-Markovian
setups (i) fully observed MDPs with continuous spaces and their quantized
approximations (leading to near optimality), (ii) POMDPs with a weak Feller
continuity together with a mild version of filter stability and quantization
of filter realizations (which requires the knowledge of the model but more
restrictive conditions on the initialization), (iii) POMDPs and the
convergence to near-optimality under a uniform controlled filter stability
plus finite window policies (which does not require the knowledge of the model
and with an arbitrary initialization though under a more restrictive filter
stability condition), and (iv) for multi-agent models where convergence of
learning dynamics to a new class of equilibria, subjective Q-learning
equilibria; where open questions on existence are noted. We highlighted that
the satisfaction of ergodicity conditions required an analysis tailored to
applications.

## References

  * [1] C.D. Aliprantis and K.C. Border.  Infinite Dimensional Analysis.  Berlin, Springer, 3rd ed., 2006.
  * [2] G. Arslan and S. Yüksel.  Decentralized Q-learning for stochastic teams and games.  IEEE Transactions on Automatic Control, 62:1545 – 1558, 2017.
  * [3] W. L. Baker.  Learning via Stochastic Approximation in Function Space.  PhD Dissertation, Harvard University, Cambridge, MA, 1997.
  * [4] E. Bayraktar and A. D. Kara.  Approximate q learning for controlled diffusion processes and its near optimality.  SIAM Journal on Mathematics of Data Science, 5(3):615–638, 2023\.
  * [5] D. P. Bertsekas.  Dynamic Programming and Stochastic Optimal Control.  Academic Press, New York, New York, 1976.
  * [6] D.P. Bertsekas and J.N. Tsitsiklis.  Neuro-dynamic programming.  Athena Scientific, 1996.
  * [7] V.S. Borkar and S.P. Meyn.  The ode method for convergence of stochastic approximation and reinforcement learning.  SIAM Journal on Control and Optimization, 38(2):447–469, 2000.
  * [8] S. Chandak, V.S. Borkar, and P. Dodhia.  Reinforcement learning in non-markovian environments.  arXiv preprint arXiv:2211.01595, 2022.
  * [9] P. Chigansky and R. Van Handel.  A complete solution to Blackwell’s unique ergodicity problem for hidden Markov chains.  The Annals of Applied Probability, 20(6):2318–2345, 2010.
  * [10] L. Cregg, F. Alajaji, and S. Yüksel.  Near-optimality of finite-memory codes and reinforcement learning for zero-delay coding of markov sources.  arXiv preprint arXiv:2310.06742, 2023.
  * [11] R.L. Dobrushin.  Central limit theorem for nonstationary Markov chains. i.  Theory of Probability & Its Applications, 1(1):65–80, 1956.
  * [12] S. Dong, B. van Roy, and Z. Zhou.  Simple agent, complex environment: Efficient reinforcement learning with agent states.  The Journal of Machine Learning Research, 23(1):11627–11680, 2022\.
  * [13] E.A. Feinberg, P.O. Kasyanov, and M.Z. Zgurovsky.  Partially observable total-cost Markov decision process with weakly continuous transition probabilities.  Mathematics of Operations Research, 41(2):656–681, 2016.
  * [14] D.P. Foster and H.P. Young.  Regret testing: learning to play Nash equilibrium without knowing you have an opponent.  pages 341–367, 2006.
  * [15] F. Germano and G. Lugosi.  Global nash convergence of foster and young’s regret testing.  Games and Economic Behavior, 60(1):135–154, 2007.
  * [16] I. I. Gihman and A. V. Skorohod.  Controlled Stochastic Processes.  Springer Science & Business Media, 2012.
  * [17] A.D Kara, N. Saldi, and S. Yüksel.  Weak Feller property of non-linear filters.  Systems & Control Letters, 134:104–512, 2019.
  * [18] A.D Kara, N. Saldi, and S. Yüksel.  Q-learning for MDPs with general spaces: Convergence and near optimality via quantization under weak continuity.  Journal of Machine Learning Research, 2023 (arXiv:2111.06781), 2023\.
  * [19] A.D Kara and S. Yüksel.  Convergence of finite memory Q-learning for POMDPs and near optimality of learned policies under filter stability.  Mathematics of Operations Research (also arXiv:2103.12158), 2022\.
  * [20] A.D Kara and S. Yüksel.  Near optimality of finite memory feedback policies in partially observed markov decision processes.  Journal of Machine Learning Research, 23(11):1–46, 2022.
  * [21] A.D. Kara and S. Yüksel.  Q-learning for continuous state and action mdps under average cost criteria.  arXiv preprint arXiv:2308.07591, 2023.
  * [22] G. Di Masi and L. Stettner.  Ergodicity of hidden markov models.  Mathematics of Control, Signals and Systems, 17(4):269–296, 2005\.
  * [23] C. McDonald and S. Yüksel.  Exponential filter stability via Dobrushin’s coefficient.  Electronic Communications in Probability, 25, 2020.
  * [24] C. McDonald and S. Yüksel.  Stochastic observability and filter stability under several criteria.  IEEE Transactions on Automatic Control (to appear), arXiv:1812.01772, 2022.
  * [25] K.R. Parthasarathy.  Probability Measures on Metric Spaces.  AMS Bookstore, 1967.
  * [26] D. Rhenius.  Incomplete information in Markovian decision models.  Ann. Statist., 2:1327–1334, 1974.
  * [27] N. Saldi, T. Linder, and S. Yüksel.  Finite Approximations in Discrete-Time Stochastic Control: Quantized Models and Asymptotic Optimality.  Springer, Cham, 2018.
  * [28] N. Saldi, S. Yüksel, and T. Linder.  Finite model approximations for partially observed Markov decision processes with discounted cost.  IEEE Transactions on Automatic Control, 65, 2020.
  * [29] S.P. Singh, T. Jaakkola, and M.I. Jordan.  Learning without state-estimation in partially observable markovian decision processes.  In Machine Learning Proceedings 1994, pages 284–292. Elsevier, 1994\.
  * [30] C. Szepesvari.  Algorithms for Reinforcement Learning.  Morgan and Claypool, 2010.
  * [31] C. Szepesvári and M.L. Littman.  A unified analysis of value-function-based reinforcement-learning algorithms.  Neural computation, 11(8):2017–2060, 1999.
  * [32] J. N. Tsitsiklis.  Asynchronous stochastic approximation and Q-learning.  Machine Learning, 16:185–202, 1994.
  * [33] R. van Handel.  Uniform time average consistency of Monte Carlo particle filters.  Stochastic Processes and their Applications, 119(11):3835–3861, 2009.
  * [34] C. Villani.  Optimal Transport: Old and New.  Springer, 2008.
  * [35] C. J. C. H. Watkins and P. Dayan.  Q-learning.  Machine Learning, 8:279–292, 1992.
  * [36] B. Yongacoglu, G. Arslan, and S. Yüksel.  Independent learning in mean-field games: Satisficing paths and convergence to subjective equilibria.  arXiv preprint arXiv:2209.05703, 2022.
  * [37] B. Yongacoglu, G. Arslan, and S. Yüksel.  Satisficing paths and independent multi-agent reinforcement learning in stochastic games.  SIAM Journal on Mathematics of Data Science (arXiv:2110.04638), 2023\.
  * [38] A.A. Yushkevich.  Reduction of a controlled Markov model with incomplete data to a problem with complete information in the case of Borel state and control spaces.  Theory Prob. Appl., 21:153–158, 1976.