Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments
Authors: Ali Devran Kara
Serdar Yuksel
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (05/2024)
Q- Q-Learning for Stochastic Control under General Informa- tion Structures and Non-Markovian Environments
Ali Devran Kara
alikar.@umich.comm edu
Deportment of Mathematics
University of Michigan, Ann Arbor, MI, USA
Serdar Yüksel
yukscl(@quuenssn.ca
Deportment of Mathematics and Statistics
Queen's University, Kingston, ON, Canada
Reviewed on OpenReview: openreveee. net/ pet//formm id= 11p6pp TV55
Abstract
As our primary contribution, we present a convergence thcorem for stochastic iterations, and in particular, Q-learning iterales, under a general, possibly non-Markovian, slochastic environment. Our conditions for convergence involve an ergodicity and positivity crite- rion. We provide a procise characterization the environment and initializations for convergence. As our second contribution, dis- cuss 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 contimuous spaces (where quantization breaks down the Markovian structure), (ii) quantized approximations 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 win- dow approximations of POMDPs under 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 stud- ied. 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.
the limit of the iterates and conditions
1 Introduction
In some stochastic control problems one does not know the true dynamics or the cost structure, and may wish to use past data to obtain an asymptotically optimal solution (that is, via learning from past data). some problems, this may be used as numerical method to obtain approximately optimal solutions.
Yet, in many problems including most of those in health, applied and social sciences, and financial mathe- matics, may not know whether the problem studied can be formulated a fully observed Markov Decision Process (MDP), 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.
partially observable Markov Decision Process (POMDP) or multi-agent
A common practical and reasonable response is view the system as an MDP, with a perceived state and action (which may or may not define genuine controlled Markov chain and therefore, the MDP assumption may not hold in actuality), and arrive at corresponding solutions via some learning algorithm.
*This research was partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC)

---

Published in Transactions on Machine Learning Research (05/2024)
The question then becomes two-fold: (i) Does such algorithm converge? (ii) If it does, what does the limit mean for each of the following models: MDPs, POMDPs, and multi-agent models?
We answer the two questions noted above in the paper:
The answer the first question will follow from a general convergence result, stated in Theorem 2.1 below. The result will require an ergodicity condition and 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 approach builds on Kara & Yüksel 2023a), the generality considered in this paper requires 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 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.
We first show that under weak contimuity conditions and a technical ergodicity condition, Q-learming can be applied to fully observable MDPs for near optimal performance under discounted cost criteria.
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 arrive near optimality, under 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 ap- proximations, for both MDPs and belicf-MDPs, raise mathematical questions on unique ergodicity and the initialization, which are also addressed in the paper.
For decentralized stochastic control problems and multi-agent systems, under a variety information struc- tures with strictly local information or partial global information, we show that Q-learning can be used arrive equilibria, even though this may be subjective one (i.e., one which may depend on subjective modcling or probabilistic assumptions of each agent).
We thus study reinforcement learning in stochastic control under variety of models and information struc- tures. The general theme is that reinforcement learning can be applied to large class of models under a varicty of performance criteria, provided that certain regularity conditions apply for the associated kernels.
We note that these questions and related ones have been studied the literature starting with [Singh et al. (994h, and Szepesvåri & Smart (2004); MMlo et al. (2008), and including the recent studies Chandak et al. 2024 and Dong et al. (2022), to be discussed further below.
Contributions.
The main contribution of the paper is Theorem 2.1 where we prove general convergence result for class of, possibly non-Markovian, stochastic iterations applicable to large class of sccnarios.
In Section 3 we provide several applications and implications of Theorem 2.1 In particular, we show that Theorem 2.1 can be used explain the convergence behavior observed in Q learning of several non-Markovian environments.
(1) We note that the proof of Theorem 2.1 when applied to the standard finite model MDP setup, also offors an alternative to the standard martingale approach used to prove the convergence of Q learning (Jaakkola et al. (1994); Tsitsikii (1994); see also Szepesvári (2010): Berlsekas & Tsitsiklis (1996a)) ; Meyn (2022) for general review). In particular, we do not require separate proof for the boundedness of the iterates to establish the convergence result.
(ii) Different versions Q learning under space discretization, and Q learning for POMDPs with finite memory information variables, as well as for multi agent systems have been shown to converge under various ergodicity assumptions. We show that Theorem 2.1 collectively explains these convergence results and also allows for further generalizations and relaxations: For example,
2

---

Published in Transactions on Machine Learning Research (05/2024)
in the context of Theorem 3.2 and Corollary Harris recurrence assumption in (Kara & Yükkel 2023a Assumption 3) to only unique ergodicity which is much more general condition especially for applications where the state process is uncountable.
3.3 Theorem 2.1 allows to relax the positive
(iii) In Section 3.4 we show that the application of Q learning for POMDPs with quantized (prob- ability measure valued) belief states will converge under suitable assumptions. Note that this result is different from the use of finite memory history variables (utilized in Theorem 3.2 and Corollary 3.3) and new result.. The complementary convergence conditions, building on the verification of Theorem 2.1 are stated in the paper with a detailed comparison noted in Remark
(iv) The convergence result and its broad applicability raises an open question on the existence of equilibria where multiple agents learn their best response policies through subjectively updating their local approximate Q functions (i.e., responding via reinforcement. learning under their subjective MDP models).
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 mcasures are weak convergence, and convergence under lotal variation. For some N E N, a sequence {Mo, n E N} in P(X) is said to converge to μ E P(X) weakly if fx c(z))n((z) + fx ((x))(dx) for every continuous and bounded c X + R. One important property weak convergence that the space of probability measures on a complete, separable, and metric (Polish) space endowed with the topology of weak convergence itself complete, separable, and metric (Parthasarathy 1967). One such metric is the bounded Lipschitz metric (Villani 2008 p.109), which is defined for μ, V E P(X) as
I [dd - f fdvl
PBL(U,V) = sup
(1)
where
[s(x) [wwl and ||/||> d(x,v)
1l == |1 + sup
sup =EX
xzy
We next introduce the first order Wasserstein metric. The Wosserstein metric of order 1 for two distributions n1, P E P(X) is defined as
inf / n(dx, dy)læ y/.
nEH()u)) Xxxx W, (1,
where H(,, v) denotes the set of probability measures on X x X with the first marginal μ and the second marginal v. Furthermore, using the dual representation of the first order Wasserstein metric, we equivalently have
/ f(z)u(d>)= -
- / f(z)v(dz))
Wi(,v))= sup Lip(f)11
where Lip(f) the minimal Lipschitz constant of f.
A sequence {ur} is said to converge in W1 to E P(X) if Wi - 0. For compact X, the Wasscrstein distance of order metrizes the weak topology on the set of probability measures on X (see (Villani 2008 Theorem 6.9)). For non-compact X convergence in the W, metric implies weak convergence (in particular this metric bounds from above the bounded- bounded-Lipschitzz metric (Villani 2008 p.109), which metrizes the weak convergence).
For probability measures μ, E P(X), the total variation metric is given by
If [())u(d))) - / s(o)u(de))
|| - -0l/ = sup [n(B) - v(B)|= sup f
BEB(X)
3

---

Published in Transactions on Machine Learning Research (05/2024)
where the supremum is taken over all measurable real f such that II suppex If(x) I 1. A sequence Mn is said to converge in total variation to P(X) if Il 1l|TV 0. We refer the reader to (aadi et al. 2020, Sections 3 and 5) for further discussions on spaces of probability measures.
2 A Q-Learning Convergence Theorem under Non-Markovian Environments
Q-learning under non-Markovin scttings have been studied recently in a few publications, c.g. Dong et al. (2 | Chandak et al. (2024); Kara & Yüksel (2023a). Prior lo such recent studies, we note that Singh et al.
[194]) 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 limit means for the original POMDP was not studied.
Recently, Kara & Yüksel (023a]] showed the convergence of Q-eaarning 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 Kara & Yüksel (2023a) 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: Dong et al. (0022) and Chandak et al. (2024), but with both different contexts and interpretations well mathematical analysis.
Dong et al. (022)) presents a general paradigm of reinforcement learning under complex envirouments 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. uniform convergence result for the convergence of time averages is implicitly imposed in the paper. Chandak et al. (2024) considers the convergence of Q-lcarning under non-Markovian environments where the cost function structure is aligned with the paradigm in Dong el al. (2022). The setup in Chandak et al. (2024) assumes that the realized cost is 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. the theory of non-linear filtering processes Chigansky & Handel (2010). Chandak al. (2024) pursues an ODE method for the convergence analysis (which was pioneered in Borkar & Meyn (2000)).
Regarding the comment on the infinite past dependence, the approximations in both Dong et al. 2022 and Chandak et al. (2024) require worst case error in sample-path sense, which, for example, is too restrictive for POMDPs, as it has been udied in Kara & Yüksel (2023a) and Kara. & Yüksel (2022). Notably the term L, defined below in (10) is more natural and relaxed under filter stability conditions.
In our setup, there is an underlying model, the true incurred costs admit exogenous uncertainty which impacts the realized costs, and the considered hidden observable random variables may be uncountable space valued. We adopt the general and concise proof method presented in Kara & Yüksel (2023a) (and
Kara et al. (2023)) ) tailored to ergodic non-Markovian dynamics, to allow for convergence to limit. The generality of our setup requires us to precisely present conditions for convergence.
Let {C be R-valued, {Si}e be s-valued and (Uch be U-valued three stochastic processes. Consider the following iteration defined for each (s, u) ES x U pair
Qc+1 u) = (1 101-ay as(s8 Qr(s, u) + an(s, (C, + (V+(
(2)
where Vs()) = min Qr(s, u), and or (s, u) is a sequence of constants also called the learning rates. We assume that the process U, is selected so that the following conditions hold. An umbrella sufficient condition is the following:
Assumption 2.1. S. U are finite sets, and the joint process (St+1, Sr, Uc, Ci)12o asymptotically ergodic in the sense that for the given initialization random variable So, for any measurable bounded function f, we
4

---

Published in Transactions on Machine Learning Research (05/2024)
have that with probability one,
N-1 N Σ S,, / [(81, ())((s))) ds, du, de)
for some measure such that I(S XiSxxxxxxx > for any (s,u) ES
Remark 2.1. Although we assume that U are finite, we will sometimes use the integral sign instead of the summation sign for nolational convenience and consistency, where we simply use the counling measure for finite spaces.
Remark 2.2. The assumption that x (s XXXXXRR for any (8. E E x U is in the same spirit as the standard condition for reinforcement algorithms that every state-action pair is visited infinitely often during braining. We nole that is possible to relox this condition as we will see Assumplion 3-4 if one is only interested in the convergence of the algorithm. In particular, we might consider a measure т such that called
(S X R) 0 for all (s, u) B S U, for some subset B, where the set B represents Irained slale-action pairs. For the learned policies to be oplimal, however, needs to make sure that the controlled process stays within the trained part of the system during the execution of an optimal policy.
The above implics Assumption 2.2 Rii)-(iii below: Assumption 2.2.
i. (s, O unless (S,, Uz) = (s, u). Parthermore,
ae(s,u)
1+ Ei (s==aUl=ut
and with probability 1, Ee (s) 000 i.. For Co, we have, as - 00,
Elwo C (*,
Elzo 1(8i=aUl==))
almost surely for some function C
M.. For the St process, we have, for any function J, as + oo,
Et Ekzo ((8,=,
/ (dssss))
almost surely for some pa
Note that stationarity assumption is required.
Under Assumption 2.1 we have that with
1( C.) = C,1(s, m,))m,) N + 0o,
N-1 N
Cdl + / CT(S= = = u, d.).).
JCER
We also have that with 1(S Sr. U., C.) = [(S,=,,U==u); as N + xi,
N-1
[(S=s, + T(S = s, U = u)
N
almost surely. Hence, we can write
Eizo CRd(s,=ativvu),
CT(dCIS- s. U u) (s,
Ete k= [(8,=s,ii=m)
5

---

Published in Transactions on Machine Learning Research (05/2024)
which implies Assumption 2.2 (it). Similarly, also establish Assumption 2.2 (ii) under Assumption
2.
As before, let S,U U be finite sets. Consider the following equation
3 Σ (((ss)))((s)sss
(3)
for some functions Q" C", to be defined explicitly, and for some regular conditional probability distribution PM (-18, u), where (u) == min, Q* (s, u).
Theorem 2.1. Under Assumption 2. Qr(s, + Q* u) almost surely for each (s, u) E ESA x TJ pair where Q" satisfies S for any initialization of Qu-
Proof. We adapt the proof method presented in (Kara & Yüksel
2023a Theorem 4.1), where instead of
positive Harris recurrence, we build on ergodicity, We first prove that the process Qe, determined by the algorithm in (2), converges almost surely to Q" We define
As(s, u) Qi(s, u) (s)
Fr(s, u) C. + (VV((())) -((
Ass, u) = (s,,,u) 3 Σ
Ve(ss) - Qs,
$1
where vs()) = min, Qe(s,
Then, we can write the following iteration
(s, u) = ((((((()))) ((s,))
Now, we write = wa such that
(8 w) = (1 - ()) we+1 (8, v) = (1 us) an(s ((( (s)
where re == Fi - F. =V+1()++1) E.,, (((ss) C*
Next, define
rs) = (S - V C CC
(s,
We further separate w, u, + 1/2 such that
1 (8, u) = (1 ar, u)), ar (()
1 u) (1 - (olss ()
this term reduces to where Fi rē. We now show that uz(s, u) + 0 almost surely for all (s, u). We have
1 u) = (1 - (s, (s) u) + ar(s, (s)
When the learning rates are chosen such that as u) unless (S,,U) (s, u), and,
a3(s, u) 1 Et_ 1 ((5.=,
(44 Et rz u) =s, u)(s,
1+ Ei 1(8,=,,Ui=u)

---

Published in Transactions on Machine Learning Research (05/2024)
Recall that
- 3 Σ V (s + Cx C*
$1
Hence, it is direct implication of Assumption
2.2 that ve(s, u) 0 almost surely for all (s, u).
Now, we go back to the iterations:
6.+ (8, u) (1 az (s,, u()
Ne+1 (3, u) = (I_=a(s.))uu(ss.) (((s)))
Ut+ (s, u) = =(1- a1,
(r)
Note that, we want to show A, 6, U2 + U; almost surely and we have that us) almost surely for all (s, u). The following analysis holds for any path that belongs to the probability one event in which (s(8, u) - 0. For any such path and for any given 0, we can find an N < co such that || < e for all t> >> N as (s,u) takes values from a finite set.
We now consider the term &c + us for t N:
(de+1 + (s, = (1 (s) u) + u((ss us)
(4)
Observe that for N,
(fi+)))(s,))) = (Fi - us, = 3V((S++1) 3V* S 3 max [Qr(s, u) Q2 u)) = A
S,
S 311 uello + Be
where the last step follows from the fact that + 0 almost surcly. 3 = BC + 1)/C < 1, for |6 + uxlloe > Ce, we can write that
By choosing C < oc such that
B11e + at + clooo S B118, + ur uelloe.
Now we rewrite
(ōe41 u441) (1 u)) + us)(s,) ta((s (s)
S (1 (, 4)) + (s, + tulss, u) + ulloc
(5)
| + ur|
Hence max,,,((00-1 + ws41)(s, u)) monotonically decreases for [|o + uello > Ce and hence there are two possibilitics: it cither gets below Cc or never gets below Ce in which case by the monotone non-decrcasing property it will converge to some number, say Mj with Mi 2 Ce.
First, we show that once the process hits below Cee, always stays there. Suppose ||, + uelloc Ce,
(5e+1 + 1r+1) u) s (1 ax(8, u)) us) u) + ar(s, (116, + uelloo +
S (1 az(s, ((,
(1 (4 (() 1)c
(1 an(s, a Ce, (3(C + SC)
C'e.
To show that M1 2 Ce is not possible, we start by (5). we have that for all (s, u)
16x+1 + (s+1) u)l (1 au w)) 16xx + uw)(s, w) + au 3 + uxloo

---

Published in Transactions on Machine Learning Research (05/2024)
Assume ||6x ux lolloo is bounded by some Ky for all k, which we can always do since it is decreasing sequence. One can then iteratively show that these iterations are bounded from above by the sequence solving the following dynamics
(s+1(s, = (1- u)) (s, u)] - og u)8Kk.
Thus, (s u) will converge to the value 3Kg for any initial point and starting from any time instance This follows since under the assumed learning rates, the iterates will converge to the averages of the constant Ko Hence, the sequence ||ōx + us lol will eventually become smaller than 3Kg + Ko for any arbilrarily small Ko > 0. Similarly, once the sequence bounded by some K1 = 3o + Ki (where 81 > arbitrarily small), they will eventually get smaller than 3K1 + R for any K > O. Repeating the same argument, follows that | + uolloo will hit below Ce eventually, finite time.
This shows that the condition | loc > Ce cannot be sustained indefinitely for some fixed C' (independent of e). Hence, (6, + u,) process converges to some value below Ce for any path that belongs to the probability one set. Then, can write ||o, uz lo < Ce for large enough t. Since >> 0 is arbitrary, taking e - 0, we can conclude that A, = 6, + ue + + 0 almost surcly.
Therefore, the process Qt determined by the algorithm
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 X, U, W- {0, 1} with
81 [1 machine is working at time machine is not working at time t.
{ machine being repaired at time
U4 =
machine is not being repaired at time t
We assume that the noise variable w, is not iid. but is Markov process with transition kernel
Pr(we+ 0/w, 0) 0.9, Pr(w++ Olw, 1) 0.4
Give the noise, we have the dynamics Fk+1 f [ uk, me) for the controlled state process
3 0 if 0, u 0,w 0,
31 0 if 0, w, =1
21 1 if 0, u 1, O,
ø1 0 if 0, 1, =
21 = 1 if x = 1,u = 0, w = O,
21 = 0 if 1, 0,
3 = 1 if x = 1, = 1, w O, Φ1 = 0 if x = 1, 1, 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 not present, ie. w = 0 then the machine fixed 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
R E
x 0,
E
0,
O(1, u)
0
x 1,
x 1,
where is the cost repair and E is the cost incurred by a broken machine.
We study the example with discount factor 3 0.7, and R E 1.5. For the exploration policy, we use random policy such that Pr(u, 0) 1 and Pr(u+- 1) 1/2 for all t.
8

---

Published in Transactions on Machine Learning Research (05/2024)
Note that the state process 24 is no longer controlled Markov chain. However, 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 (Iz, wx) forms a Markov chain under the exploration policy, and admits a stationary distribution, say æ such that
(æ 0, w = 0) = 0.145, <(x 0, w 0.127, (( = 1, w 0) 0.654, 7( = 1, 1) = 0.0728.
Hence, the Q learning algorithm constructed using the following transition probabilities:
2t will converge to the Q values of an MDP with
(= En 1 (al f( ((mM))) w)
(6)
Ew
2, us,
where T(s, u, w) = [s, w) for the exploration policy we use.
In Figure D on the left we plot the learned value functions for the non-Markov state process when we take
5t Zt. The plot on the right represents the learned value function when we simulate the environment
MDP with the transition kernel pa given in (6 One can that they converge to the same values
expected from the theoretical arguments.
Value at 5=0 for Markov state
Value at 5=0 for Markov state
4.0
4.0
3.5
35
3.0
25
2.0
20
15
15
10
10
0.5
0.5
0.0
0.0
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Number of iterations
Number iterations
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 8 = xa learns the policy
(1) = 0, n (0) 1.
Via simulation, the value of this policy can be found to be around 2.41 when the initial state, and the initial noise are uniformly distributed.
However, one can also construct the Q learning with (ae, 12-) (which is still not a Markovian state, however). The learned policy in this case is
(x()) = {1 s (0,0)
0 otherwisc
The value of this policy can be simulated to be around 2.35, again when the initial state, and the initial noise are uniformly distributed. Thus, it performs better than the policy for the state variable s; = Zz.
In the following, will discuss a number of applications, together with conditions under which the limit of the iterates near-optimal.

---

Published in Transactions on Machine Learning Research (05/2024)
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 T++1 f(z, ue, we), where ze an X-valued state variable, 44 a U-valued control action variable, wi a W-valued i.dd noise process, and f function, where X, U, W are appropriate spaces, defined on some probability space F,,,, P). By, e-g. (Gihman & Skorohod
2012 Lemma 1.2), the model above contains processes satisfying
the following for all Borel B and 2 0
P(Z+41 E B| = d)0,)), M[o.]] b(o.)) = P(z++1 E B|2 = 0t, = b.) =: T(Bla, bt)
(7)
where T-| u) is a stochastic kernel from X x U to X. Here, T[u.[] == f 21. ... x.) A stochastic process which satisfies 77 is called a controlled Markov choin. Let the control actions un be generated via a control policy 7 = {7, t 2 0} with ut = ve(4)), where 4 is the information available to the Decision Maker (DM) or controller time If = {ro.... Fz: "o....... .u.hh we have a fully observed system and an optimization problem is referred to as a. Markov Decision Process (MDP). As an optimization criterion, given cost function : X - IR,, may consider ()( E7 E Btc(zz, We)], for some (0, and zo This is called discounted infinite-horizon optimal control problem Bertsckas (1776).
If the DM has only access to noisy measurements = g(x,, with et being another i.i.d. noise, and 4 = tyo..... Mei up. 1-1h we then have a Portially Observable Markov Decision Process (POMDP). We let O(y, E 122 = 2) denote the transition kernel for the measurement variables. We will assume that is continuous and bounded, though the boundedness can be relaxed.
We assume in the following that X is a compact subset of Polish space and that Y is finite. We assume that U is compact set. However, without any loss, but building on (Saldi et al. 2018 Chapter 3), under weak Feller contimuity conditions (i.e., E[f(x1) = bounded continuous f), we can approximate T with a finite set with an arbitrarily small performance loss. Accordingly, we will assume that this set finite.
u) is continuous in (z, u) E X x U for every
The same applies when a POMDP is reduced belief-MDP and the belief- weak Feller: POMDPs can be reduced to completely observable Markov process Yushkevich (1976): Rhenius 1974). whose states are the posterior state distributions beliefs:
== = P(X. E IV....., Yo, ... U-11 E P(X),
where P(X) is the set of probability measures on X. We call n, the filter process, whose transition probability can be constructed via a Bayesian update. With
F(T, = P(X++1 E - = J, = u, Vt+1 = y),
and the stochastic kernel
K(- |,, u) Pf1 E = u u).
can write transition kernel, n, for the belief process:
u) / 1 (LF(r.m)E))KK(d
(8)
The equivalent cost function is
a( ud) = / c(x, (ddr)
Thus, the filter process defines a beLicf-MDP with kernel n. The kernel r7 is a weak Feller kernel if (a) If is weakly continuous and the mcasurement kernel Oly E la,, = x) total variation continuous Feinberg ct al. (2016) (see also Crisan & Doucet (2002)), or (b) if the kernel T is total variation continuous (with no assumptions on O) Kara et al. (2019).
10

---

Published in Transactions on Machine Learning Research (05/2024)
Wasserstein regularity of 77 is studied in Demirci et al. 2023 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:
C* (s) + 3
Σ (M(ss)) #1
We note that these Q values correspond to an MDP model with state space S, the action space U, the stage-wise cost function is (s, u) and the transition model is (s)sss,, 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 are.
3.1 Finite MDPs
Consider a finite MDP where the state process zt takes values in some finite set X, the control action process "r takes values in some finite set U. The dynamics for the state process is governed by the following
+++1 P (+12,, uz)
and at each time t, the controller receives a stage- wise cost
c(It; ue).
Corollary 3.1 (Corollary to Theorem 2.1 The iterations in converges a.s. with S. and C. t). Porthermore, the limil Q" is the optimal Q volues
cla,, ut), if the learning rales og salisfy Assumplion of the system.
Remark 3.1. This, of course, standard result Watkins & Dayan (992) Tsitsiklis 1994 Baker 1997)
Szepesvári & Littman [1999); Szepesvári (2010); Bertsekas & Tsitsiklis 19966). However, we emphasize that different from the standard martingale proof (c.g. Joakkola et al. (1994); Tsitsiklis (992)), we do not need to separalely eslablish the boundedness of the ilerales due to the converyence properly- Accordingly, the above can also be seen as an alternative proof of the standard Q-learning algorithm, though we restrict the exploration policy (umlike the standard proof where such a restriction is not needed as long as each stote action pair is visited infinitely often with no ergodicity condition, together with standard sunmability conditions). We also note that avoiding the boundedness of the iterates is essential extend the result non-Markovian environments.
3.2 Quantized Q-Learning for Weakly Continuous MDPs with General Spaces
In this section, we assume that X a compact subset of a Polish space and that Y and are finite sets. We use d(z, x²) to metrize the space X for any x, x X.
Consider a controlled Markov chain X, whose dynamics are determined by
Xx+1 T(122,,))) u)).
Furthermore, let C. C= c(Xr, U.) take values from bounded set.. The controller observes the cost realizations and some noisy version of the hidden state variable. In particular, assume that the controller observes the measurement process Y;
Y Y= -X,, V.)
for some mcasurable function g and for some i.idd. noise process V..
In the following, we let the measurement structure be that corresponds to quantization of the state variable X6: We discretize continuous MDPs, where the state space X is quantized such that for disjoint { [B, M with UM, B, X, we define finite set $ = fyi....,.. .mm. and write
= g(x), if B..
11

---

Published in Transactions on Machine Learning Research (05/2024)
We take S ((x)) = y.. Therefore, the problem can be 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.
POMDP and thus an adaptation of
Assumption 3.1. Under the exploration policy and initialization, the controlled state and control action joint process {X,, Ut} is asymptotically ergodic the sense that for any measurable bounded function f we have lhal
N-1
lim N
Σ t=0
f() - f(x, 2)x7 du)
N
for some n² E P(X x U) such that (B, x u) > 0 for any guantization bin B, and for any u E U.
We note that sufficient condition for the ergodicity assumption, for every initialization of Xo, would be positive Harris recurrence under the exploration policy.
Corollary 3.2 (Corollary to Theorem 2.1 The iterations given in converges almost surely under ii) with S = g(x)) = Y2 and C₁ = c(X,, Uk).
Assumption 3.1 and Under Assumption
The limit Q values correspond an approximate control model (scc Kara et al. (2023) For near optimality of the learned polices (Kara al. 2023 Corollary 12) notes the following:
A Assumption 3.2. (a) X is compact.
(b) There crists constant 0t 0 such that le(z, u) c(x', s a.d(x, x') for all o. e X and for all u E U.
for all x, x' E X and (c) There ezists constant or > 0 such that W1 (T u), T(12', u)) S ard(æ, for all u E U. Thcorem 3.1. KKraa al. 2023 Corollary 12)
(a) Let Assumplion
3.2 hold
Then, for the policy constructed from the limil Q values, say 9, we have
20ce L.
sup [Ja( 4) Jz(2o)) (1 -1-10 -) -Bar))
zo
where
L:= max
sup d(r e.
i=I....M M
(b) Saldi et al. 2017) For asymptotic convergence (without rate of convergence) to optimality as the quantization rule goes to 0o, only weak Feller properly T is sufficient for the the algorithe to be near optimal.
Remark 3.2. Further error bounds under different set of assumptions, such as for systems with non-compact state space X and non-uniform quantization and models with total variation continuous transition kernels can be found in Kara el. al. 2023). Q-learning for average cost problems inwolving continnous space models
has recently been studied in Kara & Yüksel 2023b
3.3 Finite Window Memory POMDP with Uniform Geometric Controlled Filter Stability
We now assume that X is compact subset of a Polish space and that Y and U are finite sets.
Suppose that the controller keeps a finite window the most recent N observation and control action variables, and perceives this as the state variable, which in general non-Markovian. That we take
S. = (Yp-N. Up- Up-Ne-11h
and C, = c({,
In this case, the pair X,, U.) forms controlled Markov chain, even (St, U.) does not. We state the ergodicity assumption formally next.
12

---

Published in Transactions on Machine Learning Research (05/2024)
Assumption 3.3.
(i) Under the exploration policy Y and initialization, and the controlled state and control action joint process (Xt, Uz} is asgmptotically ergodic in the sense that for any measurable bounded function f we have that
Σ (,), / ((x, (dx,
lim N
(
for some x7 PXX U). Purthermore, we have that P(Y: = y/x) for every x E
ii) Assumption 2.1 8) holds with St = MYI-NN,,U-aN U--N.-1)-
We note that a sufficient condition for the ergodicity assumption, for every initialization of Xo, would positive Harris recurrence under the exploration policy.
Corollary 3.3. [Corollary Theorem 2.14 Under Assumption 3.3 and Assumption 2.2(1,, the iterations in converges a.s. with St N.), N and C2 == U1)
The question then is whether the limit Q values correspond to a meaningful control problem, and how "close' this control problem is to the original POMDP. We denote by N. T, the value of the partially observed control problem when the initial prior mcasure of the hidden state XN at time N is given by aN and when we use finite window control policy. In particular, the costs are incurred after the N-measurements are collected. (Kara& & Yüksel 2023a 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. (Kara & Yüksel, 2023d, Theorem 4-1) If we denote the policies constructed using the limit Q values by , and apply 7 in the original problem, we obtoin the following error bound:
2||c||
E BJ - J, T1 S (1 3) 1=
B
where IN is the first N observation and control variables, that is
IN = (Yo...,, YN, UN.Uo....UNN UN
and the expectation laken with respect to different realizations of To" under the initial distribution of the hidden state To and the initialization policy used in the first N time steps. Furthermore,
T = P(XN -1
and
L, = sup Set "
E
[|p-5 (X++N E MMMHANNNUUULsS p=' (X++N E +lu,,+)),, -uHNN--iin
(10)
and πt is the invariant measure on It under the exploration policy 7
Remark 3.3. Theorem 2.1 allows us to relaz the positive Harris recurrence assumption in [Kara & Yüksel 2023d Assumption 9) only unique ergodicity which significantly more relaxed condition for applications where the slale process is uncountable.
Remark 3.4. The term L, is related to the filter stability problem, and caplicit bounds for this can be found in Kara 8 Vūksell 2023d Section 5), notably building on McDonald & Yükssel 2020): Recall the following Definition 3.1. (Dbrushin 1956, Equation 1.16) For a kernel operator K : S + P(S2) (that is regular conditional probability from S to S2) for standard Borel spaces SI, S2, we define the Dobrushin coefficient as:
8(K) = inf
K (v,
(11)
1=1
where the infimuum is over all x. y S and all partitions {A of S2.
13

---

Published in Transactions on Machine Learning Research (05/2024)
This definition holds for both continuous or finite/countable spaces S1 and S2 and 0 S 8(K) I for ony
kernel operator. Let
(T) = inf (-)(-),))
wet
We then have that (Kara & Yüksel 2023a.
Section 5)
L S ((1 -2
3.4 Quantized Approximations for Weak Feller POMDPs with only Asymptotic Filter Stability
We again assume that X compact subset of Polish space and that Y and U are finite sets.
As noted earlier, any POMDP can be reduced to completely observable Markov process Yushkevich (1976) whose states are the posterior state distributions or beliefs of the observer; that is, the state at time is
Rhenius (1744) (see
Ty (-): E ly......, Ut, 20, 2-11 E P(X).
We call this conditional probability measure process the filter process.
Recall the kernel (8) for the filter process. Now, by combining the quantized Q-lcarning above in Section 3.2 and the weak Feller continuity results for the non-linear filter kernel (Feinberg et al. (2016) Kara et al. (2019)), we can conclude that the setup in Section 3.2 is applicable though with significantly more tedious analysis involving ergodicity requirements. Additionally, one needs to quantize probability measures (that is, beliefs or filter realizations). Accordingly, we take S = ((T)) for some quantizer
g P(X) + P(x) (BI. Ba. Bipox)ari
with |P(X) < oo, and C. = c(X,, Ut).
We state the ergodicity condition formally:
Assumption 3.4. Under the exploration policy y and inétialization, the controlled belief state and control action joint process { U.} is asymplolically uniquely ergodic in the sense that for any measurable bounded function have that
N-1 Σ f(T)) f(Ti)=/ / f(x))((d)) t=
lim N
N
for some 77" E P(P(X) U).
We refer to the set
P, : :-:=(m: (M: CP()) (B,) 0}.
the trained set of states; since these sets will be visited infinitely often under the exploration policy.
Unique ergodicity of the dynamics follows from results in the literature, such as, (Masi & Stettner 2005 Theorem 2) and (van Handel 2009 Prop 2.1), which hold when the randomized control is memoryless under mild conditions on the process notably that the hidden variable is a uniquely ergodic Markov chain and the measurement structure satisfies filter stability in total variation expectation (one can show that weak merging expectation also suffices); we refer the reader (McDonald & Yüksel 2024, Figure 1) for mild conditions leading to filter stability in this sense, which is related to stochastic observability (McDonald & Yüksel 2024. Definition 11.1). Notably, 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-lincar filters, we can apply the Q-learning algorithu to also belief-based models to arrive at near optimal control policies. Nonetheless, since positive Harris recurrence cannot be assumed for the filter process, the initial state of the filter process may not be arbitrary: If the invariant mcasure under the exploration policy the initial state (of the filter process), (van Handel 2009. Prop 2.1) implics that the time averages will converge imposed in Assumption 2.2 A sufficient. condition for unique ergodicity then is the following.
14

---

Published in Transactions on Machine Learning Research (05/2024)
Assumption 3.5. Under the exploration policy y the hidden process {Xi} is uniquely ergodic (with measure () and the mensurement dynamics are so that the filler is slable in expectation under weak convergen.ce.
The initialization during the implementation of the algorithm affects both the trained sets, which are those visited infinitely often, and the computation of policies for the set of states reachable from the initialization: The condition that sy2 (B:) > 0 requires an analysis tailored for each problem. For example, the quantization is performed as in Kara Yüikel (2022) by clustering bins based on a finite past window, then the condition is satisfied by requiring that P(Y, y|r) > for every x X. If the clustering is done, e.g. by quantization of the probability measures via first quantizing X and then quantizing the probability measures on the finite set (see (Saldi et al., 2020 Section 5)), then the initialization could be done according to the invariant probability measure corresponding to the hidden Markov source.
For some applications, the quantization does not have to be uniform as the entire probability space P(X) may not be visited; this case suffices have the conditions be restricted to the subset reachable from the initial probability mcasure under any policy (or least set of policies which contains an optimal policy). Accordingly, if during the implementation for given initialization one can ensure that all the visited states while applying optimal policy remain inside Pn. near optimality follows. A sufficient condition is that < 77 or that To is in the topological support of v7;; see (Cregg et al. 2023 Corollary 2).
Assumption 3.6. The controlled transition kernel for the belief process (/1 u) is Lipschitz continuous under the metric W, such that
W1 (nr(l2,, u), n(- u)) S (2(,2'))
for all u, and 2, E P(X) for some or 00.
The following result from (Deiirci et al. observed model to guarantee Assumption
2023
Theorem 2.3) provides set of assumptions on the partially
3.6 when P(X) is equipped with the W1 metric.
Proposition 3.1. Demirci et al. 2023 Theorem 2.3)
(X, d) is a compact metric space with diameter D (where D supx,yex d(x, 9)
2. There exists E Rt such that
IT x, T-( 22, u)ll S ad(
for every x, x' E X, U.
Under the conditions above we have
/aD(3 (aD(3-26(O)) -6(01)) Wi (zo, =
W1 (rl- so, u) =6. u)) <
2
for all 20, 2/ E u.
Thus, Assumption 3.6 holds with or = aD(3-28(00)
Theorem 3.3.
(a) Suppose that under the exploration policy and initialization the controlled filter pro-
cess satisfies Assumption 3-4 and converge almost surely.
2. 2.1(i) with S. = g(m,), and C, = c(Xi, Ut). Then, the Q iterates
(b) Let Assumption 3.6 hold such that arB < 1 and assume that the cost function c(x, u) is Lipschitz continuous in such that
le(z, u) c(2', u)l S acd(x,xx) x').
For the policy constructed using the limit Q values, say fi we have the following bound:
20r L.
Ji 4) - (T(()) (1-5)2(1 BBrr)
15

---

Published in Transactions on Machine Learning Research (05/2024)
where
::= sup Wi Wi(F,
(12)
(c) The bound in (b) above also holds if relaxed to
sup L "aeupp(n"),BeeBn
W1 g()))
provided that my is in the support of if? (such as mo being the invoriiant mensure of X, under the exploration policy).
(d) Por asymptolic converyence (wilhout a rale of converyence) to oplimalily as the quanlization rule goes to xo (i.e., - 0), only weak Feller property of is sufficient for the the algorithm be near optimal.
Notably, suppose that for exploration To K < ø or = S where Ç is the invariant mcasure for the hidden state process under exploration. Then, the Q₁ iterates converge almost surely.
The above approximation result, given the general convergence theorem, Theorem 2.1 follows from Kara ct al. (203)) TTeorem 6,7] under the provided assumptions.
Remark 3.5. We now present comparison between the two approaches given in Sections 3.3 and 3.4 above: filter quantization finite window based learning:
(a) (1) For the filter quantization, we only need unique ergodicity of the filter process under the ex- ploration policy for which asymptotic filter stability in expectation in weak or total variation is sufficient.
(i) The runming cost can start immediately without waiting for window of measurements. (68) 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.
(iv) A Additionally, the inatialization canmot be arbilrary (e.g. the initialization for the filter may be the invariant measure of the state under the exploration policy so that the iterations for the fonite approzimation given the inétialization always remain in the absorbing set compotible with the insariant measure under exploration policy; this ensures that the infinile occupalion conditions hold for the reachable quantized belief state and action pairs from the initialization).
(b) (i) For the finile window approach, uniform convergence of filter slabilily, via Tt, is needed and it does not appear that only asymptotic filter stability can suffice.
(i) On the other hand, this is universal algorithm in that the controller does not need to know the model.
(iii) 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 selup, however, we have explicil and testable conditions. We note that it is possible to construct various discretization and approzimation methods for POMDPs, and their corresponding belief counterparts. Each such approzimation requires a different analysis to quantify the error of the approzimation. See e.g. in Kara & Yüksel (2022) where nearest neighbor approrimation scheme is considered for finâte memory information structures and the resulting loss function is in terms of more relaved distance notions. Another alternative general direction is via called 'approrimate information states' (see Subramanian et al. [2022] Seyedsalehi el al. (2023)), where a uwiiform approsimation error under various dislance notions for the approzimate information states for near optimality is considered.
Remark 3.6 (Further Models: Continuous- Time and Applications). We note that the richness of the con- vergence theorem manifests itself also in the applications involving contimuous-time models Bayraktar & Kara (2033) where quantized Q-learning finds a natural opplication area, and applications to optimal zero-delay coding Cregg el al. 2023) which also studies several subtleties with regard to ergodicity of belief dynamics.
16

---

Published in Transactions on Machine Learning Research (05/2024)
3.5 Multi-Agent Models and Joint Learning Dynamics: Subjective Q-Learning and an Open Question
As our final application, we consider multi-ageni models. Multi-agent reinforcement learning (often referred to as MARL) is the study of emergent behavior in reinforcement learning under multi-agent and complex environments, and is one of the important fronticrs in artificial intelligence research. Consider an environment with N-agents, each of which generate actions, and whose rewards impact one another. Notably, for = 1, ,,,,,, N,
1/41 f(a ub, ui: 2 we)
with cost criteria
Σ 3 uf. un uF 27
or mean-field models with
2/4 [att u/s u4 we)
and sample path costs
Σ 8 cla Wh 1e)
where
14
(2
k=1
We assume several information structures, for each m 1, N: (i) [Global state with local action] With {xt,... ,xx,, J, we have 1Tth (x "0.44] ), (ii) [Local state with local action and mean-field state] N I. = (1 (oa) p ) (iii) [Local state and local action] I = {-.t " Accordingly, for each agent ut" 71" (I(") for all / E Z+.
Given these policies, one would like to minimize the expected values of the cost functions defined above, and given the policies of other agents. Study of such docentralized systems is known to be challenging both for stochastic leams 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 docentralization of information: relevant information will be unvaiiaale to some of the players. 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 RI. algorithms which typically rely on statc-action value estimates or gradient estimates that are made using historical data-in multi- agent setlings. A number of studies have reported non-convergent play when single-agent algorithms using local information employed, without modification, in multi-agent settings. Thus, for such models the main obstacle to convergence of Q-lcarning is due to the presence of multiple active learners lcading to a non-stationary environment for all learners.
3.5.1 Two-time scales and a Markov chain over play path graphs
To overcome this obstacle, also building inspiration from prior work Foster & Young (0066 Germano & Lugosi 2007); ; Arslan & Yüksel (2117) modifies the Q-lcarning for stochastic games as follows: In the varia- tion of Qllearning, DMs are allowed to use constant policies for extended periods of time called exploration phases. This also referred to as two-time scoles approaci
As illustrated in Figure the k-th exploration phase runs through times t t....., txt1 1, where
tx+1 = tu + +T
(with to 0)
We note that an alternative twu-time scales approach via different learning rates applied by agents by taking advantage of slow learning (typically of policies) and fast learning (typically of values); soe Borkar 19977 2002 2003 [Saynn al. (2021). This approach couples the stochastic learning dynamics with system of ODEs which characterizes rest-response dynamics, whose stability can be used establish convergence in a variety of setups.
Lostic Collins 2003
17

---

Published in Transactions on Machine Learning Research (05/2024)
for some integer Tę [1, oo) denoting the length of the k-th exploration phase. During the k-th exploration phase, DMs use some constant policies "....., 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 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 acyelic games Arslan & Yüksel (2017) 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 salisficing paths dynamics Yongacoglu et. al. 2022 2023) 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 perceived state updates for cach agent, ensures convergence for each explo- ralion phase, under the required conditions (see Yongacoglu el. al. (2022
(or UX, for the mean-field [Global State] ST X. U. U., C. c( U2 U (XO) setup),
ii [Local State] Stn = XI", U, U. C. c(x;, Ug U X (or c(Xi, Uf, Uf, for the mean-field setup),
iii [Local and Mean-Field State or Compressed Global State] S = {X?". F(X.)),, UT C. c(X,, U,",,', ","), for some function F (which may include μu = F(X,) as a special case).
Subjective Satisficing Paths and Subjective Q-Learning Equilibrium
Consider the following subjective win-st vin-stay/Mnn swwsssttylssssse llofe-hhit algorithm: At the end of each exploration phase, if agents are e-satisfied, then they do not alter their policies. However, if they are not in an e-equilibrium, they randomly select 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).
(2022 2023) Let é 2 O and let π E Ts. A policy o E e's is called a Definition 3.2. Yongacoglu et al. (V", (r,,W")-ubbppe -subjecttve e-best-response to π if
V*i m (v) S
min W -- (v.d')+e, +e, VyeY. e'EU
Yongacoglu et al. subjective c-equilibrium if, for every i E N, we have
Definition 3.3.
(2022 2023)
Let 2 0. A joint policy nt E Is is called "*)-
Vei. m. (v) S min W e'EU
- (U,
Vyev.
introduced such a paradigm and presented conditions under which equilibrium or subjective equilibrium is arrived at. The limit in which each agent is e-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.
Yongacoglu et al. 2023
Accordingly, each agent then applies
22 during exploration phases. This is stated explicitly in the following
Yongacoglu et al. (2022)
k- Uh exploration phase
T
Figure 2: An illustration of the k-th exploration phase.
18

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 1: Independent Learning via e-Subjective Satisficing: Subjective Q-Learning Yongacoglu
ct al. 2022)
Set Parameters
IT' C s's a fine quantization of stationary policies : S + P(U), where sf ES, u² E {Ti]k20: a sequence in of learning phase lengths
4
set lo 0 and 4++1 = 4 + Ta for all 2 0.
1): random policy updating probability
d' (0, oo): tolerance level for sub-optimality
Initialize z II (arbitrary), Ø6 = 0 E RSXU To 0 e R
for k 2 0 (1th exploration phase)
for 1- 1= 4 + +1....,,4+ -1
10
Observe st
Seloct un ~ (-ss))
11
Observe ct = c(r/ u1, Ft ; ur) and 8:41
12
Set ni Σt 4 [(( u²) = (6%. u/}}
13
Set m Σ 1= 1(s b/
14
2i+1 (s), u/) (1 (1- (i( u.) + 1 [c + minn ((())1))))
15
nt
Ti = (1- (1- J(())) + [ (+(+))))
16
if Jr (v) S mina Dians (v. + d Vy E S, then
17
18 k++l Th
19
else
Tht1 (1 - -6) + Unif((IT')
20
Reset Ji.. E R and Qi, SxU
Theorem 2.1 shows that the exploration phase in Algorithm is such that the two-time scale and satisficing- paths paradigm is applicable to a much broader class of set
Building on the general approach presented in Yongacoglu et al. 2022 it follows that under mild numerical parameter selection conditions, if (i) a subjective Q-learning c-equilibrium exists (with sufficiently fine quan- tization of the randomized stationary policy space) and (ii) if there finite e-subjective satisficing path from any initial policy profile to subjective Q-learning c-equilibrium equilibrium, Algorithm T will converge to subjective equilibrium with arbitrarily high probability by adjusting the Ti terms accordingly.
Beyond the setups in which the limit may be close enough to each agent's 's objective equilibrium (case with global state, or mcan-field state information) Yongacoglu et al. (2022), and symmetric games Yongacoglu et al. (2023) conditions for the existence of subjective Q-learning equilibria is an open problem and requires further research. In particular, an application of Kakutani- Caaaani-------e Fan--aa----aaaaa fan-Gliiksbeer theorem (Aliprantis & Border 2006 Corollary 17.55) would entail 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 ilerates, under a general, possibly non-Markovian, stochastic environment. Our conditions for convergence were an ergodicity and a positivity condition. We furthermore provided a precise charactorization of 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 weak Feller continuity together
19

---

Published in Transactions on Machine Learning Research (05/2024)
with mild version of filter stability and quantization of filter realizations (which requires the knowledge of the model but more restrictive conditions on the initialization), (iti) POMDPs and the convergence to near-optimality under 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-lcarning equilibria; where open questions on existence are noted. We highlighted that the satisfaction of ergodicity conditions required an analysis tailored to applications.
References
C.D. Aliprantis and K.C. Border. Infinite Dimensional Analysis. Berlin, Springer, 3rd cd., 2006.
G. Arslan and S. Yüksel. Decentralized Q-learning for stochastic teams and games. IEEE Transactions on Aulomalic Control, 62:1545 1558, 2017.
W. L. Baker. Learning via Stochastic Approzimalion in Punction Space. PhD Dissertation, Harvard Univer- sity, Cambridge, MA, 1997.
E. Bayraklar and A. D. Kara. Approximate q learning for controlled diffusion processes and its near opti- mality. SIAM Journal on Mathematics of Data Science, 5(3))615-63) 2023.
D. P. Bertsekas. Dynamic Programming and Stochastic Optimal Control. Academic Press, New York, New York, 1976.
D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, Belmont, MA, 1996a.
D.P. Bertsekas and J.N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996b.
V. S. Borkar. Stochastic approximation with two time scales. Systems & Control Letters, 29(5):29112 -944, 1997.
V. Borkar. Reinforcement learning in markovian evolutionary games. Advances in Compler Systems, 5 (01):55 72, 2002.
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-48) 2000.
S. Chandak, V.S. Borkar, and P. Dodhia. Reinforcement learning in non-markovian environments. Systems & Control Lellers, 185:105751, 2024.
P. Chigansky and R. Van Handel. A complete solution to Blackwell's unique orgodicity problem for hidden Markov chains. The Annals of Applied Probability, 20(6):2318 2345, 2010.
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 (xXiu:231000644: 2023.
D. Crisan and A. Doucet. A survey of convergence results on particle filtering methods for practitioners. IEEE Transactions on Signal Processing, 50(3):736-746, 2002.
Y.E. Demirci, A.D. Kara, and S. Yüksel. Average cost optimality of partially observed mdps: Contraction of non-linear filters and existence of optimal solutions. arXiv preprint ar arXiv:2312144111, 2023.
R.L. Dobrushin. Central limit theorem for nonstationary Markov chains. i. Theory of Probability E Its Applications, 1(1):65 80, 1956.
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-11690, 2022.
E.A. Feinberg, P.O. Kasyanov, and M.Z. Zgurovsky. Partially observable total-cost Markov decision process with weakly continuous transition probabilities. Mathemalics of Operations Research, 41 41(2):656 681, 2016.
20

---

Published in Transactions on Machine Learning Research (05/2024)
D.P. Foster and H.P. Young. Regret testing: learning to play Nash equilibrium without knowing you have opponent. pp. 1411-67, 2006.
F. Germano and G. Lugosi. Global nash convergence of foster and young's regret testing. Games and Economic Behavior, 60(1):135-14) 154, 2007.
I. Gihman and V. Skorohod. Coutrolled Stochastic Processes. Springer Science & Business Media, 2012.
T. Jaakkola, M.I. Jordan, and S.P. Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neurol computation, 6(6):1185-122) -1001, 1994.
A.D Kara and S. Yüksel. Near optimality of finile memory leedback policies in partially observed markov decision processes. Journal of Machine Learning Research, 23(11):1-44, 2022.
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, 48 48(4):2066-2)) 2093, 2023a.
A.D. Kara and S. Yüksel. Q-learning for continuous state and action mdps under average cost criteria. arXiv preprint or Xiv:2300 07501, 2023b.
A.D Kara, N. Saldi, and S. Yüksel. Weak Feller property of non-linear filters. Systems Control Letters, 134:104 512, 2019.
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, pp. 34, 2023.
D.S. Leslie and E.J. Collins. Convergent multsple-timeesales reinforcement learning algorithms in normal form games. The Annols of Applied Probability, 13(4):123111251, 2003.
D.S. Leslic and E.J. Collins. Individual q-lcarning in normal form games. SIAM Journal on Control and Oplimizalion, 44(2):495-33 514, 2005.
G. Di Masi and L. Stettner. Ergodicity of hidden markov models. Mathematics of Control, Signals and Systems, (7(4):269-290) 2005.
C. McDonald and S. Yüksel. Exponential filter stability via Dobrushin's coefficient. Electronic Communicaa- tions in Probubility, 25, 2020.
C. McDonald and S. Yükksel. Stochastic observability and filter stability under several criteria. Transactions on Automatic Control, 69(5):2931 2946, 2024.
JEEE
F. C. Melo, P. Meyn, and I. M. Ribeiro. An analysis reinforcement learning with function approximation. Proceedings of the 25th international conference on Machine learning, pp. 664 671, 2008
S. Meyn. Control systems and reinforcement learning. Cambridge University Press, 2022.
K.R. Parthasarathy. Probability Measures Metric Spaces. AMS Bookstore, 1967.
Rhenius. Incomplete information in Markovian decision models. Ann. Statist., 2:1327 1334, 1974.
N. Saldi, S. Yüksel, and T. Linder. On the asymptotic optimality of finite approximations to Markov decision processes with Borel spaces. Mathematics of Operations Research, 42(4): 978, 2017.
N. Saldi, T. Linder, and S. Yüksel. Finite Approzimations in Discrete- Time Stochastic Control: Quantized Models and Asymptotic Optimality, Springer, Cham, 2018.
N. Saldi, S. Yüksel, and T. Linder. Finite model approximations for partially observed Markov decision processes with discounted cost. IEEE Transactions on Aulomatic Control, 65, 2020.
M. Sayin, K. Zhang, D. Leslie, T. Başar, and A. Ozdaglar. Decentralized qlcarning in zero-sum markov games. Advances in Neural Information Processing Systems, 11888320-13334 2021.
21

---

Published in Transactions on Machine Learning Research (05/2024)
E. Seyedsalehi, N. Akbarzadeh, A. Sinha, and A. Mahajan. Approximate information state based convergence analysis of recurrent q-learning. arXiv preprint ar arXim:2306.0550 05991, 2023.
S.P. Singh, T. Jaakkola, and M.I. Jordan. Learning without state-cstimation in partially observable marko- vian decision processes. In Machine Learning Proceedings 1994, pp- 284-292. Flsevier, 1994.
J. Subramanian, A. Sinha, R. Seraj, and A. Mahajan. Approximate information state for approximate planning and reinforcement learning in partially observed systems. The Journal of Machine Learning Research, 23(1):483-5633 2022.
C. Szepesvári. Algorithms for Reinforcement Learning. Morgan and Claypool 2010.
C. Szepesvári and W.D. Smart. Interpolation-based q-learning. 2004.
C. Szepesvári and M.L. Littman. A unified analysis value-function-based reinforcement-leariing algo- rithms. Neural computation, 11(8):2017 2060, 1999.
J. N. Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine Learning, 16:185 202, 1994.
R. van Handel. Uniform time average consistency of Monte Carlo particle filters. Stochastic Processes and their Applications, 119(11):3835-388) 3861, 2009.
C. Villani. Optimal Transport: Old and New. Springer, 2008.
C. J. C. H. Watkins and P. Dayan. Q-learning. Machine Learning, 8:279 292, 1992.
Yongacoglu, G. Arslan, and Yüksel. Independent learning in mean-field games: Satisficing paths and convergence subjective equilibria. arXiv preprint Sttk::2209.05000) 2022.
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.046333 2023.
A.A. Yushkevich. Reduction of controlled Markov model with incomplete data to problem with complete information in the case of Borel state and control spaces. Theory Prob. Appl., 21:153 158, 1976.
22


Reviews:
[{"review_id": "ay72xpD7AE", "reviewer": "Reviewer_46oT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S1) The technical contributions of the paper seem very solid and novel: presenting a unified analysis tool (Thm 2.1) for characterizing convergence criterion for Q-learning in the non-standard settings such as multi-agent models and quantized MDPs is very nice.\n(S2) Theorem 2.1  strikes me as quite general and elegant, especially given the (relative) simplicity of its proof.\n(S3) I appreciate the instantiation of Thm 2.1 on a simple example in section 2.1, as it helped understand its implications a bit better.\n(S4) The analysis under non-traditional information structures in Section 3 is very interesting.  Providing convergence guarantees for POMDPs and multi-agent scenarios using a unified approach is very elegant.  However, the section would be made stronger if a clear delineation between what is novel and what is a recovery of existing results in the literature is made.  Indeed much of this section seems to be restating existing results from the literature.\n\n(W1, minor) the writing style throughout is a bit odd, with very short paragraphs of just a single sentence or two.\n(W2) I think the authors can do a better job of highlighting what is a truly novel result, and what is a novel derivation of existing results.\n(W3) The notion of subjective equilibria is used prior to its definition (even informal) in the introduction.\n(W4) While I appreciate the discussion at the start of Section 2 is meant to highlight the difference between the submitted paper and existing work, the discussion is very technical, and for a non-expert, it was difficult for me to extract what the significant differences were.  Would it be possible to have a table or something that summarizes which assumptions are made (or not made) in each of the respective papers (including the submitted one) so that the reader can identify at a glance where the proposed work fits in the existing work landscape?\n(W5) The text is very dense, and there is very little prose to help the reader interpret the consequences of, e.g., Assumptions 2.1 and 2.2.\n(W6) Controlled Markov chains are only defined in equation (8), at the start of section 3, and yet are mentioned in section 2.1.  I would suggest a reorganization of preliminary material so that concepts are introduced/defined before they are referred to in the text.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a convergence theorem for Q-learning under general non-Markovian stochastic environments based on ergodicity and a positivity criterion.  Then the implications of this theorem are explored in the context of stochastic control problems in non-Markovian environments: specific examples studied include quantized approximations of fully observed MDPs, belief-space MDPs (arising from POMDPs), and multi-agent models.  For multi-agent models in particular, convergence to subjective Q-learning equilibria is shown.  Furthermore, for POMDPs, under suitable technical assumptions, it is shown that finite memory policies can be used to arrive to near optimality.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(1) Please make more explicit what is a novel result and what is an existing result that is derived in a new way;\n(2) The paper is extremely dense, and at times, impenetrably terse.  Please consider adopting a less is more approach, and perhaps relegating some of the \"existing results derived in a new way\" to supplementary material, such that the novel results can be clearly explained and appreciated.\n(3) Please consider running more experiments to empirically validate the theoretical results in the different environmental settings, or explicitly comment as to why this would not be useful or informative.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cCFnUqWzbT", "reviewer": "Reviewer_YkT4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- The general theoretical result is a strong one, and compelling applications to interesting theoretical problems are given. \n\n- The proof of the main result is clear, with some minor issues discussed below.\n\n- The writing is well-organized, and the contributions are articulated well. \n\n# Weaknesses\n\n- Some of the formal statements are a bit awkward or sloppy:\n    * In assumption 2.1, it is assumed that the ergodic average converges to the average with respect to some measure $\\pi$, such that $\\pi(B)>0$ for all measurable $B$. This does not make sense as the cost space is all of the real numbers, and so under any reasonable measure, there will be sets of measure zero. (More generally, the empty set should always have measure zero.). This assumption about $\\pi(B)>0$ does not appear to actually be used, and as a result, it could likely be omitted or modified as needed. \n    * A similar problem arises in Assumption 3.1\n    * The limiting argument starting around equation (6) is a bit sloppily written. In particular, the iterates do not satisfy (6), and so it would be more precise to define a separate sequence with an equality, analogous to (6), and then show that the under the hypothesis that the iterates of interest converge to $M_1\\ge C\\epsilon$, then they must converge to the iterates of the separate sequence. Then show that the separate sequence must drop below $C\\epsilon$. \n- The contributions could be articulated more clearly in the main text. \n    * All of the applications of Theorem 2.1 are stated as parts of paragraphs of text. This makes it a bit hard to see what the actual results are without careful reading. It would be better to formulate explicitly as theorems or corollaries, with clearly defined hypotheses.\n    * Sometimes, it is difficult to disentangle the contributions of this particular work from prior work. This is particularly problematic in Section 3.3, in which all of the stated results are attributed to prior papers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper gives sufficient condition for Q learning to converge to a function satisfying a Bellman-type equation under a general set of ergodicity conditions that do not require the system to be Markovian. Then it is shown how these general conditions apply to a variety of non-Markovian settings, such as quantized MDPs, a few different approaches to POMDPs, and multi-agent problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Clean up the basic math issues described above.\n* Articulate the contributions more explicitly and formally. (I.e. write theorems or corollaries for the applications of Theorem 2.1)\n* Articulate more clearly what is gained from the current results beyond prior results, where appropriate.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DDbVFCKwA7", "reviewer": "Reviewer_gfQB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe paper is clearly written and the message is clear as well.\nAlso, the unified view the work presents seems valuable.\n\nWeakness:\n\nIt is not the weakness, but there seems a phrase that is revealing the author identity (it says “as we have studied in …” )\n\nShould put some texts describing how strong the ergodicity assumption is and show what kind of examples it does not apply.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a convergence theorem for stochastic iterations under a possibly non Markovian environment under ergodicity and positivity assumptions.\nThe work presents examples of applications.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested Change:\n\n1. Perhaps the introduction can be clarified more; some tables or figures showing the position of this work would help read the second question part in particular.  Also the author(s) mention Kara & Yuksel twice in the introduction, and it makes me feel the introduction flows less naturally; could be better to reorganize the paragraphs a bit (not necessarily a large edit though)\n\n2. In the proof of Theorem 2.1. what is I_1?  Also in the theorem, how is the Q_0 assumed to be distributed?\n\n3. Minor point; in page 7, with which is the learning rate linear?  In page 8 have you defined gamma?  3.5 and 3.6 subsections are related; should be within the same subsection?\n\n4. Should put some texts describing how strong the ergodicity assumption is and show what kind of examples it does not apply.\n\n(5. Can you elaborate more on the convergence rate in the future?)", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a very strong theory paper, and it deserves recognition on that basis.
Decision: Accept (poster)