Paper deep dive
Robust $Q$-learning for mean-field control under Wasserstein uncertainty in common noise
Mathieu Laurière, Ariel Neufeld, Kyunghyun Park
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 99%
Last extracted: 6/21/2026, 5:23:38 AM
Summary
The paper presents a robust Q-learning algorithm designed for discrete-time mean-field control (MFC) problems subject to Wasserstein uncertainty in the common noise law. The authors address the challenges of infinite-dimensional lifted state spaces and unknown common-noise distributions by introducing a quantization-and-projection scheme and a Wasserstein dual reformulation. The research establishes convergence results for both synchronous and asynchronous learning schemes, providing finite-time iteration bounds and non-asymptotic convergence analysis. Numerical experiments on systemic risk and epidemic models demonstrate the algorithm's effectiveness and the robustness-performance tradeoff.
Entities (11)
Relation Signals (6)
Robust Q-learning algorithm → addresses → Mean-field control
confidence 100% · we present a robust Q-learning algorithm for discrete-time mean-field control problems
Robust Q-learning algorithm → handles → Wasserstein uncertainty
confidence 100% · robust Q-learning algorithm for discrete-time mean-field control problems under Wasserstein uncertainty
Robust Q-learning algorithm → testedon → Systemic risk model
confidence 100% · Numerical experiments on systemic risk and epidemic models
Robust Q-learning algorithm → testedon → Epidemic model
confidence 100% · Numerical experiments on systemic risk and epidemic models
Robust Q-learning algorithm → uses → Quantization-and-projection scheme
confidence 100% · The algorithm combines a quantization-and-projection scheme with a Wasserstein dual reformulation
Robust Q-learning algorithm → uses → Wasserstein dual reformulation
confidence 100% · The algorithm combines a quantization-and-projection scheme with a Wasserstein dual reformulation
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In this article, we present a robust $Q$-learning algorithm for discrete-time mean-field control problems under Wasserstein uncertainty in the common noise law. The algorithm combines a quantization-and-projection scheme with a Wasserstein dual reformulation on the common-noise space. We establish its convergence together with finite-time iteration bounds for both synchronous and asynchronous learning schemes. Numerical experiments on systemic risk and epidemic models compare the asynchronous implementation with an idealized Bellman iteration, illustrate the robustness-performance tradeoff under common-noise misspecification, and report the observed convergence behavior of the asynchronous $Q$-learning algorithm.
Tags
Links
- Source: https://arxiv.org/abs/2606.20356v1
- Canonical: https://arxiv.org/abs/2606.20356v1
Trouble viewing inline? Open PDF directly →
Full Text
214,297 characters extracted from source content.
Expand or collapse full text
Robust Q-learning for mean-field control under Wasserstein uncertainty in common noise Mathieu Laurière Shanghai Center for Data Science; NYU-ECNU Institute of Mathematical Sciences, NYU Shanghai mathieu.lauriere@nyu.edu , Ariel Neufeld Division of Mathematical Sciences, Nanyang Technological University ariel.neufeld@ntu.edu.sg and Kyunghyun Park Division of Mathematical Sciences, Nanyang Technological University kyunghyun.park@ntu.edu.sg (Date: .) Abstract. In this article, we present a robust Q-learning algorithm for discrete-time mean-field control problems under Wasserstein uncertainty in the common noise law. The algorithm combines a quantization-and-projection scheme with a Wasserstein dual reformulation on the common-noise space. We establish its convergence together with finite-time iteration bounds for both synchronous and asynchronous learning schemes. Numerical experiments on systemic risk and epidemic models compare the asynchronous implementation with an idealized Bellman iteration, illustrate the robustness–performance tradeoff under common-noise misspecification, and report the observed convergence behavior of the asynchronous Q-learning algorithm. Key words: Q-learning, mean field control, common noise, Wasserstein uncertainty, robust optimization, dynamic programming, stochastic approximation. Funding: M. Laurière acknowledges the support of NYU Shanghai HPC for the numerical experiments. A. Neufeld gratefully acknowledges support by the MOE AcRF Tier 1 Grant RG109/25. K. Park acknowledges the support of the National Research Foundation of Korea (grant DOI: RS-2025-02633175). 1. Introduction Mean-field control (MFC) [10, 14, 69], also referred to as McKean-Vlasov control, has become an exciting source of progress in the study of dynamic stochastic systems with large-population of cooperative agents. These agents take the same reward and transition functions, while being influenced by the states and actions of other agents through their empirical distributions. Under the notion of mean-field interaction [46, 39], MFC problems admit a tractable reformulation: rather than analyzing a high-dimensional system of explicitly coupled agents, one solves a representative agent’s optimization problem in which the coupling is reduced to the evolving population distribution. This paradigm has grown into an active interdisciplinary field attracting theoretically inclined mathematicians as well as engineers and social scientists. Realistic engineering and economic applications often require a source of randomness that is common to all agents. Indeed, demand fluctuations in traffic systems, environmental disturbances in robotics, and liquidity shocks in financial markets provide convincing evidence for the importance of incorporating common randomness on top of the idiosyncratic randomness affecting only individual agents (e.g., [27, 23, 33, 7]). The introduction of common noise substantially increases both the modeling and analytical complexity of MFC problems, since the resulting mean-field interaction itself becomes stochastic, yet its incorporation remains essential for capturing aggregate randomness and systemic effects arising in realistic large-population systems. This has led to a recent surge of works on MFC problems with common noise [17, 64, 19, 20, 69, 65]. Notably, two major challenges arise when implementing MFC problems with common noise in practice. The first is that analytical solutions of MFC problems are rarely available, while the corresponding numerical methods typically suffer from high dimensionality. In particular, MFC problems with common noise can be formulated as stochastic control problems driven by stochastic flows of probability measures representing mean-field interaction dynamics, and the corresponding optimality conditions take the form of Bellman equations or forward-backward equations defined on spaces of probability measures (see, e.g., [64, 17, 20, 21]). Such equations are therefore intrinsically infinite-dimensional, making them analytically intractable and numerically challenging to solve. The second is that the true law of the common noise is unknown. Model misspecification and estimation errors are thus unavoidable, particularly when the common-noise law must be inferred from limited or non-stationary observations of population measure flows. Crucially, such uncertainty is apparent in MFC problems with common noise, since the dynamics of the probability measure flow are themselves adapted to the common noise. Consequently, misspecification of the common-noise law may lead to inaccurate stochastic control formulations and unreliable solutions. This article aims to address the aforementioned challenges by developing a robust Q-learning algorithm for MFC problems under common-noise uncertainty. Q-learning and its variants [86], which apply stochastic approximation [74] based on the Bellman optimality condition, are among the most widely used reinforcement learning paradigms. Robust Q-learning [12, 67, 92, 75, 60, 61, 66, 77], a recent advancement of this paradigm, incorporates distributional robustness into the learning objective to address uncertainty and distributional shifts arising from limited real data. Building on our companion article [48] in which a theoretical framework covering the dynamic programming principle for discrete-time robust MFC problems under common-noise uncertainty is established, we aim to develop in this paper the corresponding robust Q-learning algorithm and its convergence analysis. In order to introduce the learning target for our robust Q-learning algorithm, we begin by briefly describing the robust MFC problem under Wasserstein uncertainty in common noise, considered in this work; see Section 4.1 for the precise formulation. Let QQ denote a set of probability measures over both idiosyncratic and common noise, inducing Wasserstein uncertainty in the common noise. Given an initial state ξi∈Sξ^i∈ S, an action processes (ati)t≥0⊆A(a^i_t)_t≥ 0 A, and a probability measure ℙ∈QP∈Q, the state of agent i∈ℕi evolves according to (1.1) st+1i:=F(sti,ati,Λti,εt+1i,εt+10)for t≥0,with s0i:=ξi, s_t+1^i:=F(s_t^i,a^i_t, _t^i, _t+1^i, _t+1^0) for $t≥ 0$, with $s_0^i:=ξ^i$, where FF denotes the transition function, εt+1i∈E _t+1^i∈ E and εt+10∈E0 _t+1^0∈ E^0 denote the idiosyncratic and common noise, respectively, and Λti ^i_t denotes the conditional law of (sti,ati)(s^i_t,a^i_t) given (ε10,…,εt0)( _1^0,…, _t^0). Here, the idiosyncratic noise process (εti)t≥1( _t^i)_t≥ 1 has the fixed law pε∈P(E)p_ ∈P(E), while the common noise process (εt0)t≥1( ^0_t)_t≥ 1 is uncertain in the following sense: Fix m≥0m≥ 0, q∈ℕq . For any t≥1t≥ 1, the conditional law of εt0 _t^0 given (ε10,…,εt−10)( _1^0,…, _t-1^0) under ℙP belongs to (1.2) Bm,q0(p^ε0):=p∈P(E0):Wq(p,p^ε0)≤m, B^0_m,q( p_ ^0):=\p∈P(E^0):W_q(p, p_ ^0)≤ m\, where p^ε0 p_ ^0 is a fixed reference measure and WqW_q denotes the Wasserstein q-distance (see (2.1)). In this setting, the robust MFC problem is then defined by (1.3) sup(ati)t≥0infℙ∈Qℙ[∑t=0∞βtr(sti,ati,Λti)], _(a^i_t)_t≥ 0 _P∈QE^P [ _t=0^∞β^tr(s^i_t,a^i_t, ^i_t) ], where r denotes the one-step reward function and β∈[0,1)β∈[0,1) is the discount factor. Following MFC terminology, the conditional law of stis_t^i and that of (sti,ati)(s^i_t,a^i_t) given the common noise history are regarded as elements of a lifted space—the space of probability measures of the state space and the state–action space, respectively. The value function of the problem (1.3) thus lives on the lifted state space, and, via the dynamic programming principle established in [48], satisfies a Hamilton–Jacobi–Bellman–Isaacs equation on this lifted space. The learning target of our robust Q-learning algorithm is the optimal Q-function Q∗Q^* defined on P(S)×ΠP(S)× , where P(S)P(S) denotes the lifted state space and Π denotes the set of Markov kernels inducing randomized actions. More precisely, the optimal Q-function Q∗Q^* is the unique fixed point of the following lifted state-action operator, defined by solving for every (μ,π)∈P(S)×Π(μ,π)∈P(S)× (1.4) Q∗(μ,π)=r¯(μ⊗^π)+βinfp∈Bm,q0(p^ε0)∫E0supπ′∈ΠQ∗(F¯(μ⊗^π,e0),π′)p(de0), Q^*(μ,π)= r(μ π)+β _p∈B^0_m,q( p_ ^0) _E^0 _π ∈ Q^* ( F(μ π,e^0),π )p(de^0), where r¯ r and F¯ F denote the lifted reward and lifted transition functions, induced by the one-step reward function r in (1.1) and transition function FF in (1.3), respectively; see Definition 2.1 in Section 2 for the precise definitions of Π , r¯ r and F¯ F. We note that this robust formulation in (1.1) and (1.3) reduces to the non-robust MFC framework with common noise studied in [17, 64] when the radius m in (1.2) is set to be zero. In this non-robust regime, the optimal Q-function is the fixed point of a standard Bellman operator, in which the nonlinear expectation over the set Bm,q0(p^ε0)B^0_m,q( p_ ^0) in (1.4) is replaced by a linear expectation under the reference measure p^ε0 p_ ^0. We remark that dynamic programming principles on spaces of probability measures have already appeared in existing non-robust discrete-time MFC frameworks [34, 33, 51, 69, 68]. Notably, the corresponding reinforcement learning algorithms have been developed in [34, 2, 33, 17]. The present article contributes to this growing literature by establishing, to the best of our knowledge, the first tabular robust Q-learning framework for MFC under Wasserstein uncertainty in common noise. We now turn to the main contributions of this article. First, we develop a tabular robust Q-learning algorithm for learning the optimal Q-function defined in (1.4) (see also (2.3)). Two nontrivial challenges arise in this endeavor. The first is a dimensionality issue: even though the original state and action spaces (S,A)(S,A) are assumed to be finite, the lifted state space P(S)P(S) and the associated kernel sets have infinite cardinality, precluding a direct tabular treatment. The second is a robust-evaluation issue: the law of the common noise is not assumed to be known exactly, whereas the Bellman target requires a worst-case expectation over the Wasserstein ball Bm,q0(p^ε0)B^0_m,q( p_ ^0). Together, these features make the incorporation of robustness into a sample-based learning procedure nontrivial. To address these challenges, we introduce two key ingredients. The first is a quantization-and-projection scheme for the domain (P(S),Π)(P(S), ) of Q∗Q^*, yielding a finite-dimensional representation amenable to tabular learning. This approach is inspired by the non-robust MFC setting of [17]. The second ingredient is a Wasserstein dual reformulation on the common-noise space itself: applying the duality theory of the Wasserstein metric [4, 13, 30, 62] reduces the worst-case expectation over Bm,q0(p^ε0)B^0_m,q( p_ ^0) to a one-dimensional optimization problem involving a single expectation under the reference law p^ε0 p_ ^0. Furthermore, the dual reformulation enables the use of independent common-noise samples within the asynchronous algorithm. Together, these two ingredients give rise to a robust Q-learning algorithm that achieves distributional robustness without requiring direct access to the worst-case common-noise law. We refer the reader to Section 2.2 for the detailed description of our Q-learning algorithm design. Second, we establish a non-asymptotic convergence analysis of our robust Q-learning algorithm. Following the batch/offline Q-learning paradigm of [25], the algorithm admits synchronous and asynchronous variants according to the specification of the learning rate. The proof of the convergence result is composed of two principal layers: the first concerns the discretized optimal Q-function induced by the quantization-and-projection scheme and the resulting discretization error; the second addresses the stochastic approximation error. Theorem 2.15 establishes that both variants converge to within the discretization error accuracy, where the asynchronous case further requires standard conditions on sampled data. While [40, Theorem 1] serves as a backbone, the estimates for the dual optimizer and the iterative Q-function are newly established and, together with a tailored application of the Wasserstein duality theorem, yield the desired result. Next, Theorem 2.17 provides the finite-time iteration bound in terms of the algorithmic parameters. Namely, it establishes the number of iterations sufficient to achieve a target accuracy at a prescribed confidence level. As in the convergence proof for Theorem 2.15, the discretization error analysis is required; crucially, a concentration inequality for martingale sequences [3, Exercise 9.2.4] is employed to obtain the explicit stochastic approximation error bound for the discretized Q-function. The verification of the requisite martingale structure relies on our Wasserstein duality result and the algorithmic design of the robust Q-learning. As a consequence of Theorem 2.17, we further derive the convergence rate with respect to the iteration number in Corollary 2.19. Finally, Section 3 complements the theoretical developments with numerical experiments on systemic risk and epidemic control. These examples compare the asynchronous implementation of Algorithm 1 with an idealized finite-grid Bellman iteration, illustrate how moderate robustness can improve performance under common-noise misspecification, and report the observed convergence of the asynchronous Q-function iterates. 1.1. Related literature Recent works have adapted reinforcement learning methods to discrete-time mean-field frameworks. For discrete-time mean-field control (MFC) and related mean-field Markov decision/control formulations, we refer to [31, 32, 33, 64, 17, 34, 2]. We stress that MFC problems are different from mean-field games (Nash equilibria among infinitely many infinitesimal players) and from mean field type games (Nash equilibria between players solving MFC problems), which have both been the subject of reinforcement learning methods, see, e.g., [79, 35, 24, 18, 49, 1] and [15, 76, 16, 78, 41]. In contrast, MFC do not require computing Nash equilibria. Moreover, in the continuous-time setting, reinforcement learning and deep learning approaches for mean-field control and games have also been investigated e.g. in [26, 88, 28, 87, 72, 73]. The recent works [72, 73] are close in their treatment of common noise, but they study continuous-time non-robust mean-field control; by contrast, the present paper develops a discrete-time tabular algorithm under Wasserstein uncertainty in the common-noise law. We further refer to the survey articles [47, 36, 50] for comprehensive overviews of existing numerical methods and machine learning approaches for mean-field control and game problems. Robustness in mean-field game and control problems has been studied through risk-sensitive and min–max formulations, including [82, 8, 63, 37, 45, 48, 57, 91, 58]. In continuous-time settings, robust mean-field control problems have also been studied, particularly in linear–quadratic frameworks with drift, disturbance, or volatility uncertainty [38, 84, 85]. In parallel, we refer to [5, 89, 90, 56] for robust Markov decision processes (MDPs) and to [12, 67, 92, 75, 60, 61, 66, 77] for robust Q-learning algorithms. These robust MDPs and Q-learning works do not address the lifted state-action structure arising from mean-field interactions, while the robust mean-field works above do not provide the tabular Wasserstein robust Q-learning algorithm and finite-time iteration bound analysis developed here. Consequently, reinforcement-learning-based numerical methods for robust mean-field game and control problems remain comparatively underdeveloped. Moving away from the above robust mean-field framework toward the perspective of offline Q-learning convergence and finite-time analysis, our convergence result in Theorem 2.15 is closely aligned with the classical convergence theory of Q-learning algorithms [40, 86], which originates from stochastic approximation theory [22, 74]. Furthermore, the finite-time iteration bound analysis established in Theorem 2.17 is in the spirit of [25], and is also related to recent non-asymptotic sample-complexity analyses for Q-learning algorithms developed in [70, 55, 53, 42, 54]. Nevertheless, our setting involves several additional layers of difficulty beyond the classical framework. In particular, the lifted mean-field state-action structure requires the construction of suitable finite discretizations together with a corresponding approximation error analysis. Moreover, the incorporation of robustness through Wasserstein uncertainty leads to a significantly more delicate convergence analysis and finite-time error estimate, due to the additional min–max structure and distributional dependence of the problem. 1.2. Outline of the article The paper is organized as follows. Section 2 introduces the optimal Q-function together with its underlying spaces and key components, presents the robust Q-learning algorithm built on the discretization scheme and the common-noise Wasserstein duality theorem, and establishes the convergence and finite-time iteration bound analysis as well as the convergence rate with respect to the iteration number (Theorems 2.15 and 2.17 and Corollary 2.19). Section 3 presents the numerical setup, robustness profiles, and asynchronous Q-function convergence diagnostics for systemic-risk and epidemic-control examples. Section 4 derives the optimal Q-function from the robust MFC problem under common noise uncertainty and introduces the discretized Q-function. Section 5 collects the key technical lemmas and the proofs of Theorems 2.15 and 2.17 and Corollary 2.19. 2. Q-learning algorithm for robust mean-field control 2.1. Optimal Q-function In this section, we introduce the optimal Q-function that serves as the learning target for solving the robust mean-field control problem under Wasserstein uncertainty in the common noise. We start by introducing the underlying spaces and the corresponding probability spaces. Let S and A denote the state and action spaces, and let E and E0E^0 denote the idiosyncratic and common noise spaces, respectively. Throughout this article, we assume that these spaces are nonempty finite subsets of (possibly different) Euclidean spaces, endowed with the Euclidean norm |⋅||·|. For any such space, or any finite product of such spaces X, we write X¯:=P(X) X:=P(X) for the set of all Borel probability measures on X. We endow X¯ X with the topology induced by the 1-Wasserstein distance, which we recall to be the following: For any μ,ν∈X¯μ,ν∈ X, we write Cpl(μ,ν)⊂X×X¯Cpl(μ,ν)⊂ X× X for the subset of probability measures on X×X× X with marginals μ and ν, called couplings. For q∈ℕq , the q-Wasserstein distance between μ and ν is defined by (2.1) Wq(μ,ν):=(infγ∈Cpl(μ,ν)∫X×X|x−y|qγ(dx,dy))1/q. W_q(μ,ν):= ( _γ (μ,ν) _X× X|x-y|^qγ(dx,dy) )^1/q. Since X is finite, for any q∈ℕq the topology induced by WqW_q coincides with that of weak convergence; see, e.g., [83, Chapter 6]. Let us introduce key components used to define the optimal Q-function. To this end, we recall from (1.1) and (1.3) in Section 1 the transition function F:S×A×S×A¯×E×E0→SF:S× A× S× A× E× E^0→ S, the one-step reward function r:S×A×S×A¯→ℝr:S× A× S× A , the discount factor β∈[0,1)β∈[0,1), and the fixed law of the idiosyncratic noise pε∈E¯p_ ∈ E. Definition 2.1. (i) Define F¯:S×A¯×E0∋(Λ,e0)↦F¯(Λ,e0)∈S¯ F: S× A× E^0 ( ,e^0) F( ,e^0)∈ S by F¯(Λ,e0)(ds′):=((Λ⊗pε)∘F(⋅,⋅,Λ,⋅,e0)−1)(ds′), F( ,e^0)(ds ):= (( p_ ) (·,·, ,·,e^0)^-1 )(ds ), i.e., the push-forward of the product measure Λ⊗pε:=Λ(ds,da)pε(de)∈S×A×E¯ p_ := (ds,da)p_ (de)∈ S× A× E by the mapping F(⋅,⋅,Λ,⋅,e0):S×A×E→SF(·,·, ,·,e^0):S× A× E→ S. (i) Define r¯:S×A¯∋Λ↦r¯(Λ)∈ℝ r: S× A r( ) by r¯(Λ):=∫S×Ar(s,a,Λ)Λ(ds,da). r( ):= _S× Ar(s,a, ) (ds,da). (i) Let Π:=π:S∋s↦π(⋅|s)∈A¯ :=\π:S s π(·|s)∈ A\ denote the policy set (i.e., the set of Markov kernels), endowed with the metric dΠ(π,π′):=maxs∈SW1(π(da|s),π′(da|s))for π,π′∈Π.d_ (π,π ):= _s∈ SW_1(π(da|s),π (da|s)) for $π,π ∈ $. In mean-field control frameworks [34, 64, 17, 48], the space S¯ S and S×A¯ S× A are referred to as the lifted state and state-action spaces, respectively. The mappings F¯ F and r¯ r define the corresponding lifted transition and reward functions on the lifted space. Moreover, the set Π denotes the admissible policy class and serves as the domain of maximization in the Bellman–Isaacs operator characterized by F¯ F and r¯ r, which we introduce in (2.2). The optimal Q-function is derived from a fixed-point theorem of the Bellman–Isaacs operator, which is established under the following conditions on the transition function FF, the reward function r, and the discount factor β. Assumption 2.2. There are some constants CF>0C_F>0 and Cr>0C_r>0 such that (i) for every (s,a,Λ,e0)(s,a, ,e^0) and (s~,a~,Λ~,e~0)∈S×A×S×A¯×E0( s, a, , e^0)∈ S× A× S× A× E^0 ∫E|F(s,a,Λ,e,e0)−F(s~,a~,Λ~,e,e~0)|pε(de) _E|F(s,a, ,e,e^0)-F( s, a, ,e, e^0)|p_ (de) ≤CF(|s−s~|+|a−a~|+W1(Λ,Λ~)+|e0−e~0|), ≤ C_F (|s- s|+|a- a|+W_1( , )+|e^0- e^0| ), (i) for every (s,a,Λ)(s,a, ) and (s~,a~,Λ~)∈S×A×S×A¯( s, a, )∈ S× A× S× A |r(s,a,Λ)−r(s~,a~,Λ~)|≤Cr(|s−s~|+|a−a~|+W1(Λ,Λ~)). |r(s,a, )-r( s, a, )|≤ C_r (|s- s|+|a- a|+W_1( , ) ). (i) β is in [0,1∧(2CF)−1)[0,1 (2C_F)^-1). Remark 2.3. Since S and A are finite and S×A¯ S× A is compact, Assumption 2.2 (i) implies that Cr,∞:=sup(s,a,Λ)∈S×A×S×A¯|r(s,a,Λ)|<∞.C_r,∞:= _(s,a, )∈ S× A× S× A|r(s,a, )|<∞. Moreover, we have by [48, Lemma 5.2] that under Assumption 2.2 (i), (i), the following properties on the lifted components F¯ F and r¯ r in Definition 2.1 hold: (i) for every (Λ,e0),(Λ~,e~0)∈S×A¯×E0( ,e^0),( , e^0)∈ S× A× E^0, W1(F¯(Λ,e0),F¯(Λ~,e~0))≤CF(2W1(Λ,Λ~)+|e0−e~0|),W_1( F( ,e^0), F( , e^0))≤ C_F(2W_1( , )+|e^0- e^0|), (i) for every Λ,Λ~∈S×A¯ , ∈ S× A, |r¯(Λ)|≤Cr,∞and|r¯(Λ)−r¯(Λ~)|≤2Cr.| r( )|≤ C_r,∞ and | r( )- r( )|≤ 2C_r. To introduce the Bellman–Isaacs operator TT, let Cb(S¯)C_b( S) denote the set of bounded, continuous functions v:S¯→ℝv: S , endowed with the supremum norm ‖v‖S¯:=supμ∈S¯|v(μ)|.\|v\|_ S:= _μ∈ S|v(μ)|. Moreover, for any L≥0L≥ 0, let Lipb,L(S¯)⊂Cb(S¯)Lip_b,L( S)⊂ C_b( S) denote the set of bounded, L-Lipschitz continuous functions. Using the components introduced in Definition 2.1 together with the uncertainty set Bm,q0(p^ε0)B^0_m,q( p_ ^0) defined in (1.2), we define the Bellman–Isaacs operator TT by setting, for any v∈Cb(S¯)v∈ C_b( S), (2.2) Tv(μ):=supπ∈Πr¯(μ⊗^π)+βinfp∈Bm,q0(p^ε0)∫E0v(F¯(μ⊗^π,e0))p(de0),μ∈S¯,Tv(μ):= _π∈ \ r(μ π)+β _p∈B^0_m,q( p_ ^0) _E^0v( F(μ π,e^0))p(de^0) \, $μ∈ S$, where μ⊗^π(ds,da):=π(da|s)μ(ds)∈S×A¯μ π(ds,da):=π(da|s)μ(ds)∈ S× A. We now state the fixed-point theorem associated with the operator TT in (2.2), which follows from [48, Propositions 2.15, 2.16]. Proposition 2.4. Suppose that Assumption 2.2 is satisfied, and let L∗:=2Cr/(1−2βCF)L^*:=2C_r/(1-2β C_F). Then there exists a unique fixed point v∗∈Lipb,L∗(S¯)v^* _b,L^*( S) of TT such that v∗=Tv∗v^*=Tv^*. Moreover, for any v∈Lipb,L∗(S¯)v _b,L^*( S), limn→∞Tnv=v∗ _n→∞T^nv=v^*. Using v∗v^* from Proposition 2.4, we define the optimal Q-function Q∗:S¯×Π→ℝQ^*: S× by (2.3) Q∗(μ,π):=r¯(μ⊗^π)+βinfp∈Bm,q0(p^ε0)∫E0v∗(F¯(μ⊗^π,e0))p(de0),(μ,π)∈S¯×Π. Q^*(μ,π):= r(μ π)+β _p∈B^0_m,q( p_ ^0) _E^0v^*( F(μ π,e^0))p(de^0), (μ,π)∈ S× . It is optimal in the sense that supπ∈ΠQ∗(μ,π)=v∗(μ) _π∈ Q^*(μ,π)=v^*(μ) for any μ∈S¯μ∈ S. The optimal Q-function in (2.3) can be viewed as the state–action value function of a lifted robust Markov decision process (MDP) under model uncertainty, induced by the robust mean-field control problem under Wasserstein uncertainty in the common noise. This connection will be presented in detail in Section 4. 2.2. Q-learning algorithm Our goal is to design a tabular Q-learning algorithm to learn the optimal Q-function Q∗Q^* defined in (2.3). We emphasize that although the state and action spaces (S,A)(S,A) are finite, the corresponding lifted spaces of measures S¯ S and kernels Π are not. Therefore, from a numerical view point, two key ingredients are required: (i) quantization and projection of the domain (S¯,Π)( S, ) of Q∗Q^* and (i) computation of worst-case expectations over the Wasserstein uncertainty set Bm,q0(p^ε0)B_m,q^0( p_ ^0) in Q∗Q^*. These two enable a finite-dimensional approximation of Q∗Q^*: the discretization of (S¯,Π)( S, ) enables a tractable tabular representation of Q∗Q^*, while the evaluation of worst-case expectations ensures that the robustness with respect to the set Bm,q0(p^ε0)B^0_m,q( p_ ^0) is properly incorporated into the learning procedure. We begin by introducing the quantization and projection for (S¯,Π)( S, ), following the approach in Section 5.3 of [17]. Definition 2.5. Let Sˇ⊂S¯ S⊂ S be a finite subset such that for any μ∈S¯μ∈ S, minμˇ∈SˇW1(μ,μˇ)≤εSˇfor some εSˇ>0, _ μ∈ SW_1(μ, μ)≤ _ S for some $ _ S>0$, representing an εSˇ _ S-net of S¯ S under W1W_1. Analogously, let Aˇ⊂A¯ A⊂ A be a finite subset such that for any ν∈A¯ν∈ A, minνˇ∈AˇW1(ν,νˇ)≤εAˇ _ ν∈ AW_1(ν, ν)≤ _ A for some εAˇ>0 _ A>0. (i) Let pjSˇ:S¯∋μ↦pjSˇ(μ)∈Sˇpj_ S: S μ _ S(μ)∈ S be a mapping satisfying W1(μ,pjSˇ(μ))=minμˇ∈SˇW1(μ,μˇ).W_1(μ,pj_ S(μ))= _ μ∈ SW_1(μ, μ). (i) Define Πˇ:=πˇ:S∋s↦πˇ(da|s)∈Aˇ :=\ π:S s π(da|s)∈ A\ so that it is a finite subset of Π ; see Definition 2.1 (i). Then let pjΠˇ:Π∋π↦pjΠˇ(π)∈Πˇpj_ : π _ (π)∈ be a mapping satisfying dΠ(π,pjΠˇ(π))=minπˇ∈ΠˇdΠ(π,πˇ).d_ (π,pj_ (π))= _ π∈ d_ (π, π). Remark 2.6. (i) We present a construction of Sˇ S below; an analogous construction applies to Aˇ A. Denote S:=s1,…,s|S|S:=\s_1,…,s_|S|\ and let ΔS:=maxs≠s′∈S|s−s′|<∞ _S:= _s≠ s ∈ S|s-s |<∞. For k∈ℕk , define Sˇ:=μ∈S¯:μ(si)=bik,bi∈ℕ∪0∀i=1,…,|S|,∑i=1|S|bi=k, S:= \μ∈ S:μ(\s_i\)= b_ik,\;b_i ∪\0\\; $∀ i=1,…,|S|$,\; _i=1^|S|b_i=k \, which is finite with |Sˇ|=(k+|S|−1|S|−1)| S|= k+|S|-1|S|-1. For any μ∈S¯μ∈ S, set ℓ:=k−∑i=1|S|⌊kμ(si)⌋ :=k- _i=1^|S| kμ(\s_i\) and define μˇ′∈Sˇ μ ∈ S by μˇ′(si):=⌊kμ(si)⌋+1kifi=1,…,ℓ;μˇ′(si):=⌊kμ(si)⌋kelse. μ (\s_i\):= kμ(\s_i\) +1k if\;i=1,…, ; μ (\s_i\):= kμ(\s_i\) k else. Then |μ(si)−μˇ′(si)|≤1k|μ(\s_i\)- μ (\s_i\)|≤ 1k for all i=1,…,|S|i=1,…,|S|. Hence by [83, Theorem 6.15], W1(μ,μˇ′)≤ΔS‖μ−μˇ′‖TV=ΔS2∑i=1|S||μ(si)−μˇ′(si)|≤ΔS|S|2k,W_1(μ, μ )≤ _S\|μ- μ \|_TV= _S2 _i=1^|S||μ(\s_i\)- μ (\s_i\)|≤ _S|S|2k, where ∥⋅∥TV\|·\|_TV denotes the total variation and the equality holds because S is finite. Thus, choosing k≥⌈ΔS|S|2εSˇ⌉k≥ _S|S|2 _ S ensures minμˇ∈SˇW1(μ,μˇ)≤εSˇ _ μ∈ SW_1(μ, μ)≤ _ S. Finally, once the construction of Aˇ A is obtained as above, the set Πˇ is naturally induced as the set of mappings from S to Aˇ A, and hence satisfies |Πˇ|=|Aˇ||S|| |=| A|^|S|. (i) A construction of the measurable mapping pjSˇpj_ S in Definition 2.5 (i) is given as follows. Fix an arbitrary ordering Sˇ=μˇ1,…,μˇN S=\ μ_1,…, μ_N\ for some N∈ℕN . For any μ∈S¯μ∈ S, define pjSˇ(μ):=μˇi∗,μ,where i∗,μ:=mini∈1,…,N:W1(μ,μˇi)=min1≤ℓ≤NW1(μ,μˇℓ), _ S(μ):= μ_i^*,μ, where i^*,μ:= \i∈\1,…,N\:W_1(μ, μ_i)= _1≤ ≤ NW_1(μ, μ_ ) \, i.e., the nearest element of Sˇ S, with tie-breaking according to the fixed ordering. Since Πˇ in Definition 2.5 (i) is finite, we can construct the mapping pjΠˇpj_ analogously by replacing (S¯,Sˇ;W1)( S, S;W_1) with (Π,Πˇ;dΠ)( , ;d_ ). Next, to enable the tractable computation of worst-case expectations over the set Bm,q0(p^ε0)B^0_m,q( p_ ^0), we exploit a convex duality representation that expresses worst-case expectations in terms of linear expectations with respect to the reference measure p^ε0 p_ ^0, as established, e.g., in [4, 13, 30, 62]. To this end, we recall the notion of λcλ c-transform on the common noise space E0E^0; see Section 2 in [4], Section 5 in [83]. Definition 2.7. For f:E0→ℝf:E^0 and λ≥0λ≥ 0, let (f)λ:E0∋e0↦(f)λ(e0)∈ℝ(f)^λ:E^0 e^0 (f)^λ(e^0) denote the λcλ c-transform of f with the cost function c:E0×E0∋(e0,e~0)↦c(e0,e~0):=|e0−e~0|qc:E^0× E^0 (e^0, e^0) c(e^0, e^0):=|e^0- e^0|^q defined by (2.4) (f)λ(e0):=maxe~0∈E0f(e~0)−λ|e0−e~0|q. (f)^λ(e^0):= _ e^0∈ E^0\f( e^0)-λ|e^0- e^0|^q\. We next recall the convex duality result established, e.g., in Theorem 2.4 of [4]. Lemma 2.8. For any mapping f:E0→ℝf:E^0 , the following convex duality holds: infp∈Bm,q0(p^ε0)∫E0f(e0)p(de0)=supλ≥0∫E0(−(−f)λ(e0))p^ε0(de0)−mqλ. _p∈B^0_m,q( p_ ^0) _E^0f(e^0)p(de^0)= _λ≥ 0 \ _E^0 (-(-f)^λ(e^0) ) p_ ^0(de^0)-m^qλ \. Using the quantization and projection in Definition 2.5, together with the convex duality result in Lemma 2.8, we present a tabular Q-learning algorithm under both the synchronous and asynchronous frameworks of [25]. Framework 2.9. Let (Ω0,ℱ0,ℙ^0)( ^0,F^0, P^0) be a probability space supporting a family of independent and identically distributed random variables (εt,(μˇ,πˇ)0)t≥1,(μˇ,πˇ)∈Sˇ×Πˇ⊆E0,( ^0_t,( μ, π))_t≥ 1,( μ, π)∈ S× E^0, with law p^ε0 p_ ^0. Both synchronous and asynchronous frameworks share the Q-learning update rule in (i) and differ only in the choice of learning rates specified in (i) and (i). Fix w∈(12,1)w∈( 12,1). (i) (Synchronous learning rate) Define the synchronous learning rates by αt,(μˇ,πˇ):=(t+1)−w _t,( μ, π):=(t+1)^-w for every t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . (i) (Asynchronous learning rate) Let (μˇt,πˇt)t≥0⊆Sˇ×Πˇ( μ_t, π_t)_t≥ 0 S× be a pre-sampled, projected dataset. Then we define for every (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× (2.5) T(μˇ,πˇ):=t≥0:(μˇ,πˇ)=(μˇt,πˇt), T_( μ, π):=\t≥ 0:( μ, π)=( μ_t, π_t)\, representing the set of times t≥0t≥ 0 at which (μˇ,πˇ)( μ, π) is visited along (μˇt,πˇt)t≥0( μ_t, π_t)_t≥ 0. Finally, we define the asynchronous learning rates as follows: for every t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (2.6) αt,(μˇ,πˇ):=(Nt,(μˇ,πˇ)+1)−wif t∈T(μˇ,πˇ);αt,(μˇ,πˇ)(μˇ,πˇ):=0else, _t,( μ, π):=(N_t,( μ, π)+1)^-w if $t∈ T_( μ, π)$; _t,( μ, π)( μ, π):=0 else, where Nt,(μˇ,πˇ)N_t,( μ, π) denotes the number of times 0≤ℓ<t0≤ <t at which (μˇ,πˇ)=(μˇℓ,πˇℓ)( μ, π)=( μ_ , π_ ), with the convention that N0,(μˇ,πˇ)=0N_0,( μ, π)=0. (i) Under either choice of learning rates in (i) or (i), the Q-learning algorithm is defined by the following stochastic iteration: For every t≥0t≥ 0 and every pair (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (2.7) Qˇ0(μˇ,πˇ):= Q_0( μ, π):= Qˇ0,for some Qˇ0∈ℝ, Q_0, for some $ Q_0 $, (2.8) Qˇt+1(μˇ,πˇ):= Q_t+1( μ, π):= (1−αt,(μˇ,πˇ))Qˇt(μˇ,πˇ) (1- _t,( μ, π)) Q_t( μ, π) +αt,(μˇ,πˇ)(r¯(μˇ⊗^πˇ)+β[−(−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(εt+1,(μˇ,πˇ)0)−mqλt,(μˇ,πˇ)∗]), + _t,( μ, π) ( r( μ π)+β [- (-J_t,( μ, π) ) _t,( μ, π)^*( ^0_t+1,( μ, π))-m^q _t,( μ, π)^* ] ), where Jt,(μˇ,πˇ):E0∋e0↦Jt,(μˇ,πˇ)(e0)∈ℝJ_t,( μ, π):E^0 e^0 J_t,( μ, π)(e^0) is defined by (2.9) Jt,(μˇ,πˇ)(e0):=maxπˇ′∈ΠˇQˇt(pjSˇ(F¯(μˇ⊗^πˇ,e0)),πˇ′), J_t,( μ, π)(e^0):= _ π ∈ Q_t (pj_ S ( F( μ π,e^0) ), π ), where λt,(μˇ,πˇ)∗ _t,( μ, π)^* appearing in (2.8) is an optimizer of the dual problem Φt,(μˇ,πˇ) _t,( μ, π) defined by (2.10) Φt,(μˇ,πˇ):=supλ≥0ϕt,(μˇ,πˇ)(λ),ϕt,(μˇ,πˇ)(λ):=∫E0(−(−Jt,(μˇ,πˇ))λ(e0))p^ε0(de0)−mqλ,λ≥0. aligned & _t,( μ, π):= _λ≥ 0 _t,( μ, π)(λ),\\ & _t,( μ, π)(λ):= _E^0 (-(-J_t,( μ, π))^λ(e^0) ) p_ ^0(de^0)-m^qλ, λ≥ 0. aligned Remark 2.10. For the synchronous Q-learning algorithm under Framework 2.9 (i) and (i), the update Qˇt+1 Q_t+1 in (2.8) occurs at all pairs in Sˇ×Πˇ S× . In contrast, under the asynchronous Q-learning algorithm under Framework 2.9 (i) and (i), Qˇt+1 Q_t+1 is updated only for the visited pair (μˇt,πˇt)( μ_t, π_t) at time t, since αt,(⋅,⋅) _t,(·,·) is nonzero only in this case; see (2.6). These update rules are explicitly illustrated in Algorithm 1, which presents the overall iteration in chronological order. The following statements hold for either choice of learning rates. For t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (i) λt,(μˇ,πˇ)∗ _t,( μ, π)^* in (2.8) is well-defined under certain conditions on β and Qˇ0 Q_0 in (2.7); see Assumption 2.12 and Remark 2.13. (i) We have by Lemma 2.8 that Φt,(μˇ,πˇ) _t,( μ, π) in (2.10) satisfies (2.11) Φt,(μˇ,πˇ)=infp∈Bm,q0(p^ε0)∫E0maxπˇ′∈ΠˇQˇt(pjSˇ(F¯(μ⊗^π,e0)),πˇ′)p(de0). _t,( μ, π)= _p∈B^0_m,q( p_ ^0) _E^0 _ π ∈ Q_t (pj_ S( F(μ π,e^0)), π )p(de^0). Moreover, when m=0m=0 (i.e., the non-robust case), the update rule (2.8) reduces to Qˇt+1(μˇ,πˇ)=(1−αt,(μˇ,πˇ))Qˇt(μˇ,πˇ)+αt,(μˇ,πˇ)[r¯(μˇ⊗^πˇ)+βmaxπˇ′∈ΠˇQˇt(μˇt+1,(μˇ,πˇ)′,πˇ′)], Q_t+1( μ, π)=(1- _t,( μ, π)) Q_t( μ, π)+ _t,( μ, π) [ r( μ π)+β _ π ∈ Q_t( μ_t+1,( μ, π) , π ) ], where μˇt+1,(μˇ,πˇ)′:=pjSˇ(F¯(μˇ⊗^πˇ,εt+1,(μˇ,πˇ)0))∈Sˇ μ_t+1,( μ, π) :=pj_ S( F( μ π, _t+1,( μ, π)^0))∈ S represents the lifted-state transition from the pair (μˇ,πˇ)( μ, π) at time t. Therefore, this case corresponds to the standard tabular Q-learning algorithm on the finite space Sˇ×Πˇ S× (see, e.g., [11, 86, 59, 40]). Remark 2.11. The asynchronous Q-learning algorithm under Framework 2.9 (i) and (i) adopts an offline-learning, independent-sampling setting. The pre-sampled, projected data (μˇt,πˇt)t≥0( μ_t, π_t)_t≥ 0 in Framework 2.9 (i) is obtained by applying the projection mappings pjSˇpj_ S and pjΠˇpj_ given in Definition 2.5 to a historically collected lifted trajectory (μt,πt)t≥0⊆S¯×Π( _t, _t)_t≥ 0 S× , and is therefore regarded as fixed or, more generally, as defined on an auxiliary probability space independent of (Ω0,ℱ0,ℙ^0)( ^0,F^0, P^0). Consequently, the visitation pattern of state and action pairs is prescribed by this projected data. The stochasticity in update (2.8) enters through the random variables (εt,(μˇ,πˇ)0)t≥1,(μˇ,πˇ)∈Sˇ×Πˇ( ^0_t,( μ, π))_t≥ 1,\,( μ, π)∈ S× . These are directly sampled from a simulator with law p^ε0 p_ ^0, constructed from the original (unprojected) historical lifted trajectory (μt,πt)t≥0⊆S¯×Π( _t, _t)_t≥ 0 S× , for instance, via filtering or direct empirical estimation of the common noise processes. The probability space (Ω0,ℱ0,ℙ^0)( ^0,F^0, P^0) is then understood as the canonical space supporting this simulator, with ℙ^0 P^0 the law it induces on Ω0 ^0. This is consistent with the batch/offline Q-learning paradigm, in which learning is carried out from static, previously collected data; see, e.g., [44, 29, 52, 71, 53]. Numerically, one could alternatively generate data along the way using an ϵε-greedy policy. This approach generally leads to better numerical results but it can be difficult to guarantee that the assumptions used in the proof of convergence (in particular Assumption 2.12 (i) related to the covering time) are satisfied. Algorithm 1 Q-learning algorithm for robust MFC problem 0: Number of iteration T∈ℕT . pre-sampled, projected dataset (μˇt,πˇt)t=0T−1⊆Sˇ×Πˇ( μ_t, π_t)_t=0^T-1 S× used in the asynchronous Q-learning algorithm under Framework 2.9 (i),(i). 1: Initialize Qˇ0(μˇ,πˇ):=Qˇ0 Q_0( μ, π):= Q_0 for all (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× for some Qˇ0∈ℝ Q_0 . 2: if Framework 2.9 (i),(i) (i.e., the synchronous Q-learning) then 3: Set αt,(μ,πˇ):=(t+1)−w _t,(μ, π):=(t+1)^-w for all t=0,…,T−1t=0,…,T-1 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . 4: for t=0,…,T−1t=0,…,T-1 do 5: for every (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× do 6: Execute action πˇ π in state μˇ μ, and observe r¯(μˇ⊗^πˇ) r( μ π) and εt+1,(μˇ,πˇ)0 _t+1,( μ, π)^0. 7: Compute the optimizer λt,(μˇ,πˇ)∗λ^*_t,( μ, π) of Φt,(μˇ,πˇ) _t,( μ, π); see (2.10). 8: Compute the λcλ c-transform value (−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(εt+1,(μˇ,πˇ)0)(-J_t,( μ, π)) _t,( μ, π)^*( ^0_t+1,( μ, π)); see (2.4) and (2.9). 9: Update Qˇt+1(μˇ,πˇ) Q_t+1( μ, π) according to (2.8). 10: end for 11: end for 12: else 13: Use (μˇt,πˇt)t=0T−1( μ_t, π_t)_t=0^T-1 to compute (αt,(μˇt,πˇt))t=0T−1( _t,( μ_t, π_t))_t=0^T-1 according to (2.6) (i.e., the asynchronous Q-learning algorithm under Framework 2.9 (i),(i)). 14: for t=0,…,T−1t=0,…,T-1 do 15: Set Qˇt+1(μˇ,πˇ):=Qˇt(μˇ,πˇ) Q_t+1( μ, π):= Q_t( μ, π) for all (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . 16: Apply Steps 6–9 with (μˇt,πˇt)( μ_t, π_t) in place of (μˇ,πˇ)( μ, π) to update only Qˇt+1(μˇt,πˇt) Q_t+1( μ_t, π_t). 17: end for 18: end if 19: return QˇT∗ Q_T^* 2.3. Main theorems We proceed with our main results on the convergence of the Q-learning algorithm prescribed in Framework 2.9, together with its finite-time iteration bound analysis. To this end, we impose the following conditions. Assumption 2.12. Recall the constants CF>0C_F>0 and Cr>0C_r>0 in Assumption 2.2. (i) β is in [0,13∧(2CF)−1)[0, 13 (2C_F)^-1). Moreover, Qˇ0 Q_0 in (2.7) satisfies |Qˇ0|≤Qˇmax:=Cr,∞1−3β| Q_0|≤ Q_max:= C_r,∞1-3β. (i) There exists a finite covering time Tcov>1T_cov>1 such that for every s≥0s≥ 0 Sˇ×Πˇ⊆(μˇt,πˇt)t=s,…,s+Tcov−1, S× ( μ_t, π_t)_t=s,…,s+T_cov-1, where (μˇt,πˇt)t≥0( μ_t, π_t)_t≥ 0 is the pre-sampled, projected dataset used for Framework 2.9 (i). Remark 2.13. The condition on β in Assumption 2.12 (i) is stronger than that in Assumption 2.2 (i). We impose this stronger condition, together with the assumption on Qˇ0 Q_0, in order to establish the existence of λt,(⋅,⋅)∗ _t,(·,·)^* for all t≥0t≥ 0 in (2.10), as well as to obtain uniform-in-time bounds for (λt,(⋅,⋅)∗)t≥0( _t,(·,·)^*)_t≥ 0 and (Qˇt)t≥0( Q_t)_t≥ 0; see Lemma 5.1. We also note that other conditions on the discount factor appear in robust Q-learning frameworks such as [81, 75], where they are primarily used to establish the contraction property and convergence of the Q-learning iteration. Remark 2.14. The covering-time condition in Assumption 2.12 (i) ensures that under the asynchronous learning rates in Framework 2.9 (i), every pair in Sˇ×Πˇ S× is visited at least once within any time window of length greater than the covering time TcovT_cov. Such a condition is standard in the asynchronous Q-learning literature to guarantee sufficient exploration and convergence of the respective Q-learning algorithm; see, e.g., [9, 55, 70, 80]. We now present the convergence result of our Q-learning algorithm. To this end, we define (2.12) Δ¯S:=mins≠s′∈S|s−s′|>0andΔA:=maxa≠a′∈A|a−a′|<∞, _S:= _s≠ s ∈ S|s-s |>0 and _A:= _a≠ a ∈ A|a-a |<∞, which represent the minimal separation distance in S and the diameter of A, respectively. Last, we recall the constant L∗L^* from Proposition 2.4. Theorem 2.15. Under Assumptions 2.2 (i),(i) and 2.12 (i), the following statements hold: (i) the synchronous version of the Q-learning algorithm in Framework 2.9 (i),(i) satisfies, for every (μ,π)∈S¯×Π(μ,π)∈ S× , (2.13) limt→∞|Qˇt(pjSˇ(μ),pjΠˇ(π))−Q∗(μ,π)|≤C1εSˇ+C2εAˇ,ℙ^0-a.s., _t→∞| Q_t(pj_ S(μ),pj_ (π))-Q^*(μ,π)|≤ C_1 _ S+C_2 _ A, $ P^0$-a.s., where C1:=2(1+ΔAΔ¯S−1)(Cr+βL∗CF)+β1−βL∗>0C_1:=2(1+ _A _S^-1)(C_r+β L^*C_F)+ β1-βL^*>0 and C2:=2(Cr+βL∗CF)1−β>0C_2:= 2(C_r+β L^*C_F)1-β>0. (i) Moreover, if Assumption 2.12 (i) also holds, then the asynchronous version of the Q-learning algorithm in Framework 2.9 (i),(i) satisfies (2.13) for every (μ,π)∈S¯×Π(μ,π)∈ S× . Remark 2.16. The error term “C1εSˇ+C2εAˇC_1 _ S+C_2 _ A” appearing in (2.13) does not arise from the stochastic iteration of the Q-learning algorithm itself, but rather from the quantization and projection procedure in Definition 2.5 used to construct the discretized approximation of the optimal Q-function. The corresponding projection and discretization error analysis is provided in Section 4.2, particularly in Lemma 4.10. We next present the finite-time iteration bound analysis for our Q-learning algorithm. Theorem 2.17. Suppose that Assumptions 2.2 (i),(i) and 2.12 (i) are satisfied. Then the following statements hold for any ε^>0 >0 and δ^∈(0,1) δ∈(0,1). (i) There exists an iteration number T∗∈ℕT^* of order111We denote by O(⋅)O(·) the Landau symbol. O([(Qˇmaxε^)2maxlog(Qˇmaxε^),log(|Sˇ||Aˇ||Sˇ|δ^log(Qˇmaxε^))]1w+[log(Qˇmaxε^)]11−w), O ( [ ( Q_max )^2 \ ( Q_max ), ( | S|| A|^| S| δ ( Q_max ) ) \ ] 1w+ [ ( Q_max ) ] 11-w ), such that the synchronous version of the Q-learning algorithm in Framework 2.9 (i),(i) satisfies, for every T≥T∗T≥ T^*, (2.14) ℙ^0(sup(μ,π)∈S¯×Π|QˇT(pjSˇ(μ),pjΠˇ(π))−Q∗(μ,π)|≤C1εSˇ+C2εAˇ+ε^)≥1−δ^, P^0 ( \ _(μ,π)∈ S× | Q_T(pj_ S(μ),pj_ (π))-Q^*(μ,π) |≤ C_1 _ S+C_2 _ A+ \ )≥ 1- δ, with the constants C1C_1 and C2C_2 given in Theorem 2.15. (i) Moreover, if Assumption 2.12 (i) is satisfied and we let (2.15) Nˇ1:=Tcov1+5wQˇmax2,Nˇ2:=TcovQˇmax,Nˇ3:=Tcov|Sˇ||Aˇ||Sˇ|, N_1:=T_cov^1+5w Q_max^2, N_2:=T_cov Q_max, N_3:=T_cov| S|| A|^| S|, then there exists an iteration number T∗∈ℕT^* of order O([Nˇ1ε^2maxlog(Nˇ2ε^),log(Nˇ3δ^log(Qˇmaxε^))]1w+[Tcovlog(Qˇmaxε^)]11−w), O ( [ N_1 ^2 \ ( N_2 ), ( N_3 δ ( Q_max ) ) \ ] 1w+ [T_cov ( Q_max ) ] 11-w ), such that the asynchronous version in Framework 2.9 (i),(i) also satisfies (2.14) for every T≥T∗T≥ T^*. Remark 2.18. Theorem 2.17 presents a finite-time high-probability convergence estimate for the Q-learning algorithm in Framework 2.9. More precisely, for any prescribed error and confidence levels, one can construct an iteration number T∗T^* of the stated order such that, for every T≥T∗T≥ T^*, the corresponding Q-learning iterate QˇT Q_T has error bounded by the prescribed error plus the discretization error C1εSˇ+C2εAˇC_1 _ S+C_2 _ A (see also Remark 2.16) with at least the prescribed confidence level. For the asynchronous Q-learning case, Theorem 2.17 can also be read as a finite-sample complexity bound, since each iteration updates one state and action pair along the pre-sampled, projected trajectory, so that the iteration bound is equivalently a bound on the number of sampled updates needed to reach the stated accuracy. Related non-asymptotic sample-complexity analyses for asynchronous Q-learning algorithms are presented in [70, 55, 53, 42, 54]. The following corollary reformulates Theorem 2.17 in terms of the convergence rate with respect to the iteration number T. Corollary 2.19. Suppose that Assumptions 2.2 (i),(i) and 2.12 (i) are satisfied. Then the synchronous version of the Q-learning algorithm in Framework 2.9 (i),(i) satisfies,222We denote by Oℙ^0(⋅)O_ P^0(·) the Landau symbol in ℙ^0 P^0-probability; that is, for a sequence of random variables (Xn)n≥1(X_n)_n≥ 1 and a deterministic sequence (an)n≥1(a_n)_n≥ 1, we write Xn=Oℙ^0(an)X_n=O_ P^0(a_n) as n→∞n→∞, if for every δ^>0 δ>0, there exists a finite M>0M>0 and N∈ℕN such that ℙ^0(|Xnan|>M)≤δ P^0(| X_na_n|>M)≤ δ for every n≥Nn≥ N. as T→∞T→∞, (2.16) sup(μ,π)∈S¯×Π|QˇT(pjSˇ(μ),pjΠˇ(π))−Q∗(μ,π)|≤C1εSˇ+C2εAˇ+Oℙ^0(logTTw), _(μ,π)∈ S× | Q_T(pj_ S(μ),pj_ (π))-Q^*(μ,π) |≤ C_1 _ S+C_2 _ A+O_ P^0 ( TT^w ), with the constants C1C_1 and C2C_2 given in Theorem 2.15. Moreover, if Assumption 2.12 (i) is satisfied, then the asynchronous version in Framework 2.9 (i),(i) also satisfies (2.16). 3. Numerics In this section we illustrate the robust Q-learning algorithm on three finite-grid mean-field control examples. 333The code is available at https://github.com/mlauriere/RobustMeanFieldControlQLearning. 3.1. Numerical Setup The computations use the projected finite state and policy spaces from Definition 2.5. The runs of Algorithm 1 use the asynchronous branch, namely the else part of the algorithm, corresponding to Framework 2.9 (i),(i), with learning rates as in (2.6). The robust targets are computed using the common-noise dual in Lemma 2.8 and (2.10); in particular the transportation cost is on E0E^0. In all experiments reported below, we set q=1q=1 and |E0|=3|E^0|=3, and the reference common-noise law is p^ε0=(0.1,0.8,0.1). p_ ^0=(0.1,0.8,0.1). The pre-sampled lifted state–policy pairs (μˇt,πˇt)t≥0( μ_t, π_t)_t≥ 0 used by the asynchronous implementation are generated by repeated random permutations of Sˇ×Πˇ S× . Hence the visitation pattern is independent of the current Qˇ Q table, and one independent common-noise realization is drawn at each update. The dashed reference curves in Figures 2 and 3 are not produced by a model-free algorithm. They are obtained by deterministic Bellman iteration for the finite projected mean-field control problem on Sˇ×Πˇ S× . Below, for radius m, the resulting finite-grid fixed point is denoted by Qˇ∗,m Q^*,m, while the iterated Q-function at iteration T is denoted by QˇTm Q_T^m. The Bellman-iteration procedure to obtain Qˇ∗,m Q^*,m requires the knowledge of the transition and reward functions and hence does not form a reinforcement algorithm. However, we use this methodology as benchmark to compare it with the outcome of our robust Q-learning algorithm. In the examples below, SsysS_ sys, SSISS_ SIS, and SSEIRS_ SEIR denote concrete individual state spaces S in the notation of Section 2; these should be distinguished from the finite projected lifted-state grid Sˇ S. Robustness profiles are evaluated under perturbed common-noise laws pevalζ=(1−ζ)p^ε0+ζpadv,ζ∈0,0.125,…,1,p_ eval^ζ=(1-ζ) p_ ^0+ζ\,p_ adv, ζ∈\0,0.125,…,1\, where ζ=0ζ=0 is the reference law and ζ=1ζ=1 is an example-specific adverse endpoint used only for evaluation. The law padvp_ adv is not a new training distribution; it is a plotting device that concentrates mass on an unfavorable common-noise state so that increasing ζ produces a controlled misspecification of the reference law. We interpret pevalζp_ eval^ζ as the true law for the common noise, which is, however, unknown to the agent, forcing him to optimize robustly. If ζ=0ζ=0, then the reference law p^ε0 p_ ^0 coincides with the true law pevalζp_ eval^ζ, whereas if ζ>0ζ>0, then there is some model misspecification. The plotted quantities in Figures 2 and 3 are discounted rewards of the greedy policy induced by the computed Qˇ Q table. For each fixed value of ζ, this is an ordinary evaluation under the fixed common-noise law pevalζp_ eval^ζ, not an additional robust infimum over laws. Since the primitive dynamics are given by the map F¯ F, the law pevalζp_ eval^ζ enters only through the finite average over common-noise values in the display below. For a fixed evaluation law pevalζp_ eval^ζ and greedy finite-grid policy πˇQˇ(μˇ)∈argmaxπˇ∈ΠˇQˇ(μˇ,πˇ) π_ Q( μ)∈ *arg\,max_ π∈ Q( μ, π), this reward is computed by solving the finite linear system VQˇ(μˇ)=r¯(μˇ⊗^πˇQˇ(μˇ))+β∑e0∈E0pevalζ(e0)VQˇ(pjSˇ(F¯(μˇ⊗^πˇQˇ(μˇ),e0))),μˇ∈Sˇ,V_ Q( μ)= r( μ π_ Q( μ))+β _e^0∈ E^0p_ eval^ζ(e^0)V_ Q (pj_ S( F( μ π_ Q( μ),e^0)) ), μ∈ S, and averaging VQˇV_ Q with respect to the uniform measure on the finite projected state grid Sˇ S. Larger plotted values in Figures 2 and 3 therefore correspond to better performance. In Figures 2 and 3, solid curves show means over 2020 independent seeds of the asynchronous implementation of Algorithm 1, and dashed curves show the deterministic finite-grid Bellman references. Table 1 summarizes the finite-grid configurations. We use Rsys R_ sys =0,0.05,0.1,0.2,0.3,0.4,0.5,0.6,0.75,1, =\0,05,1,2,3,4,5,6,75,1\, Repi R_ epi =0,0.005,0.01,0.02,0.03,0.04,0.05,0.06,0.08,0.1,0.15,0.2,0.3,0.5,0.75,1. =\0,005,01,02,03,04,05,06,08,1,15,2,3,5,75,1\. Here RsysR_ sys and RepiR_ epi denote the choices for Wasserstein robustness radii m used in the robustness-profile experiments. The construction of Sˇ S and Πˇ is explained in each example. Example β |Sˇ|| S| |Πˇ|| | Updates per m w Robustness radii m Systemic Risk 0.50.5 2121 216216 5,000,0005,000,000 0.750.75 RsysR_ sys SIS 0.50.5 1313 1111 1,000,0001,000,000 0.70.7 RepiR_ epi SEIR 0.90.9 165165 1111 3,000,0003,000,000 0.70.7 RepiR_ epi Table 1. Finite-grid configurations for the asynchronous robustness profiles. Remark 3.1. The finite examples satisfy the finiteness and boundedness requirements by construction. The lifted rewards and lifted transition maps used below are Lipschitz on the relevant finite-dimensional simplices, with clipping preserving Lipschitz continuity. The asynchronous data schedule is generated by repeated random permutations of Sˇ×Πˇ S× , hence the covering-time condition in Assumption 2.12 (i) holds with Tcov=|Sˇ||Πˇ|T_cov=| S|| |. The discount-factor condition in Assumption 2.12 (i), however, is a sufficient condition for the theorem and is not imposed in all numerical runs, in particular in the main SEIR experiment where β=0.9β=0.9. Thus the main numerical results should be read as empirical finite-grid evidence for Algorithm 1, while Figure 1 illustrates the rate form in Corollary 2.19. Q-function convergence. Figure 1 reports the convergence speed of the asynchronous Qˇ Q iterates on the same finite grids used in the robustness profiles. For each displayed robustness radius m, let Qˇm∗ Q^*_m denote the corresponding idealized finite-grid fixed point. At iteration time T, the plotted error is ET(m)=‖QˇTm−Qˇ∗,m‖Sˇ×Πˇ=max(μˇ,πˇ)∈Sˇ×Πˇ|QˇTm(μˇ,πˇ)−Qˇ∗,m(μˇ,πˇ)|.E_T(m)=\| Q_T^m- Q^*,m\|_ S× = _( μ, π)∈ S× | Q_T^m( μ, π)- Q^*,m( μ, π)|. The line is the median over 1010 seeds and the band is the 1010–9090 percentile range. The black dashed guide is proportional to log(T)/Tw (T)/T^w, with the learning-rate exponent w from Table 1. This matches the rate form in Corollary 2.19 up to constants and discretization error. Figure 1. Asynchronous Q-function convergence. Error ET(m)E_T(m) against the idealized finite-grid fixed point for selected robustness radii. 3.2. Systemic Risk This example is a stylized finite-state model of a population of financial institutions whose capital levels are affected by individual controls and aggregate shocks. The individual state, action, and common-noise spaces are Ssys=0,1,2,A=−1,0,1,E0=−1,0,1.S_ sys=\0,1,2\, A=\-1,0,1\, E^0=\-1,0,1\. The states 0,1,20,1,2 represent distressed, normal, and well-capitalized agents. Given individual state x, action a, and common shock e0e^0, the next state is x′=min2,max0,x+a+e0.x = \2, \0,x+a+e^0\\. There is no idiosyncratic noise in this example. If the current population distribution is μ and the finite-grid population policy is π, the mean-field transition is the law of x′x when x∼μx μ and a∼π(⋅|x)a π(·|x). The lifted one-step reward is r¯(μ⊗^π)=−‖μ−(0,1,0)‖22−2μ0. r(μ π)=-\|μ-(0,1,0)\|_2^2-2 _0. where μ0 _0 is the population mass in the distressed state. Thus the planner is rewarded for avoiding both deviation from the normal population state and mass in the distressed state. The adverse law is padv=(1,0,0)p_ adv=(1,0,0), which puts all mass on the negative common shock. The projected state grid is the uniform probability-simplex grid Sˇsys=(k05,k15,k25):k0,k1,k2∈ℕ∪0,k0+k1+k2=5. S_ sys= \ ( k_05, k_15, k_25 ):k_0,k_1,k_2 ∪\0\,\ k_0+k_1+k_2=5 \. Thus |Sˇsys|=(72)=21| S_ sys|= 72=21. The individual action set has three actions, A=−1,0,1A=\-1,0,1\. We discretize local randomized actions by Aˇsys=(ℓ−12,ℓ02,ℓ12):ℓ−1,ℓ0,ℓ1∈ℕ∪0,ℓ−1+ℓ0+ℓ1=2, A_ sys= \ ( _-12, _02, _12 ): _-1, _0, _1 ∪\0\,\ _-1+ _0+ _1=2 \, so |Aˇsys|=(42)=6| A_ sys|= 42=6. A finite-grid population policy assigns one element of Aˇsys A_ sys to each individual state x∈Ssysx∈ S_ sys, hence Πˇsys=πˇ:Ssys→Aˇsys,|Πˇsys|=63=216. _ sys=\ π:S_ sys→ A_ sys\, | _ sys|=6^3=216. With the configuration in Table 1, Figure 2 shows a clear hedging effect: under the adverse law ζ=1ζ=1, the mean reward from Algorithm 1 increases from −5.119-5.119 at m=0m=0 to −3.230-3.230 at m=0.6m=0.6, while excessive robustness remains slightly below the best moderate radius. Under the reference law, by contrast, robustness is only mildly useful at very small radius and then lowers reward as m increases. The asynchronous and idealized curves are closest for moderate and large robustness radii; the larger non-robust gap visible at m=0m=0 reflects slower finite-time learning in this example. Figure 2. Systemic Risk robustness profile. Solid curves show reward means from the asynchronous implementation of Algorithm 1; dashed curves show same-grid idealized references. Moderate robustness substantially improves performance under adverse common shocks. 3.3. Epidemics The epidemic examples model a planner who uses distancing to reduce disease transmission in a population subject to aggregate transmission-rate shocks. Both use common noise E0=0.5,0.81,1.8,E^0=\0.5,0.81,1.8\, interpreted as the transmission-rate state. The last point, 1.81.8, is the high-transmission state. The adverse law is padv=(0,0,1)p_ adv=(0,0,1), so the interpolation defining pevalζp_ eval^ζ shifts evaluation mass toward this high-transmission state as ζ increases. In both epidemic models we use the reduced two-action set A=U,DA=\U,D\, where U denotes unrestricted behavior and D denotes distancing. Thus π(D|s)π(D|s) denotes the probability that policy π assigns to the distancing action in individual state s∈Ss∈ S. Since distancing non-susceptible agents does not affect the transition in these finite models and only lowers reward, the reduced policy grid sets π(D|s)=0π(D|s)=0 for non-susceptible states and varies π(D|s)π(D|s) only at susceptible states. 3.3.1. SIS The individual state space is SSIS=S,IS_ SIS=\S,I\ corresponding to susceptible and infected states. With μ=(μS,μI)μ=( _S, _I), common noise e0=be^0=b, and u=π(U|S)u=π(U|S), the finite-grid mean-field transition used in the computation is μI′=[0.7μI+bμIμSu]01,μS′=1−μI′, _I = [0.7 _I+b\, _I _Su ]_0^1, _S =1- _I , where [z]01=min1,max0,z[z]_0^1= \1, \0,z\\. This corresponds to recovery probability 0.30.3 for infected agents and infection pressure proportional to the current infected mass, the transmission state b, and the unrestricted susceptible fraction. The lifted one-step reward penalizes the current infected mass and the population-average probability of choosing the distancing action, and is defined as r¯(μ⊗^π)=−μI−0.5∑s∈SSISμsπ(D|s). r(μ π)=- _I-0.5 _s∈ S_ SIS _sπ(D|s). In this example, the projected state grid is SˇSIS=(kS12,kI12):kS,kI∈ℕ0,kS+kI=12, S_ SIS= \ ( k_S12, k_I12 ):k_S,k_I _0,\ k_S+k_I=12 \, so |SˇSIS|=13| S_ SIS|=13. The individual action set is A=U,DA=\U,D\, where U denotes unrestricted behavior and D denotes distancing. The susceptible-state action distribution is discretized as Aˇepi=(ℓU10,ℓD10):ℓU,ℓD∈ℕ0,ℓU+ℓD=10, A_ epi= \ ( _U10, _D10 ): _U, _D _0,\ _U+ _D=10 \, with coordinates corresponding to (U,D)(U,D). Since distancing infected agents does not affect the SIS transition and only lowers reward, the reduced policy class fixes infected agents to choose unrestricted behavior: ΠˇSIS=πˇ:πˇ(⋅|S)∈Aˇepi,πˇ(⋅|I)=δU. _ SIS= \ π: π(·|S)∈ A_ epi, π(·|I)= _U \. Therefore |ΠˇSIS|=|Aˇepi|=11| _ SIS|=| A_ epi|=11. With the configuration in Table 1, Figure 3 shows close agreement between the asynchronous and idealized profiles. The moderate-robustness effect is visible at intermediate drift: at ζ=0.5ζ=0.5, the mean reward from Algorithm 1 increases from −1.089-1.089 at m=0m=0 to −1.080-1.080 at m=0.03m=0.03, then decreases to −1.098-1.098 at m=1m=1. At the severe law ζ=1ζ=1, high robustness remains beneficial, with the mean reward from Algorithm 1 increasing from −1.175-1.175 at m=0m=0 to −1.138-1.138 at m=0.75m=0.75. Figure 3. SIS robustness profile. Solid curves show reward means from the asynchronous implementation of Algorithm 1; dashed curves show idealized references. The algorithm closely tracks the finite-grid idealized benchmark. 3.3.2. SEIR The individual state space is SSEIR=S,E,I,RS_ SEIR=\S,E,I,R\, where the two new states are interpreted as Exposed and Recovered. In the Exposed state, the agent is not yet infectious. The common noise e0=be^0=b is again the transmission rate. Let θS(π)=π(U|S)+(1−η)π(D|S). _S(π)=π(U|S)+(1-η)π(D|S). Here η is the efficacy of distancing for susceptible agents, σ is the incubation probability, and ρrec _ rec is the recovery probability. For μ=(μS,μE,μI,μR)μ=( _S, _E, _I, _R), the lifted transition map is described by the population mass transfers dSE d_SE =minμS,bμIμSθS(π), = \ _S,b _I _S _S(π)\, dEI d_EI =σμE,dIR=ρrecμI. =σ _E, d_IR= _ rec _I. Equivalently, μS′ μ _S =μS−dSE, = _S-d_SE, μE′ μ _E =μE+dSE−dEI, = _E+d_SE-d_EI, μI′ μ _I =μI+dEI−dIR, = _I+d_EI-d_IR, μR′ μ _R =μR+dIR, = _R+d_IR, followed by clipping and renormalization on the finite population grid. The numerical experiments use η=1η=1, σ=0.5σ=0.5, and ρrec=0.2 _ rec=0.2. The one-step reward is r¯(μ⊗^π)=−μI−0.85∑s∈SSEIRμsπ(D|s). r(μ π)=- _I-0.85 _s∈ S_ SEIR _sπ(D|s). Under the reduced policy class, this distancing term is μSπ(D|S) _Sπ(D|S). In this example, the projected state grid is SˇSEIR=(kS8,kE8,kI8,kR8):kS,kE,kI,kR∈ℕ0,kS+kE+kI+kR=8. S_ SEIR= \ ( k_S8, k_E8, k_I8, k_R8 ):k_S,k_E,k_I,k_R _0,\ k_S+k_E+k_I+k_R=8 \. Thus |SˇSEIR|=(113)=165| S_ SEIR|= 113=165. As in the SIS example, A=U,DA=\U,D\ and the susceptible-state action distribution is discretized on Aˇepi=(ℓU10,ℓD10):ℓU,ℓD∈ℕ0,ℓU+ℓD=10. A_ epi= \ ( _U10, _D10 ): _U, _D _0,\ _U+ _D=10 \. Because distancing exposed, infected, or recovered agents does not affect the SEIR transition in this finite model and only lowers reward, the reduced policy class fixes these states to unrestricted behavior: ΠˇSEIR=πˇ:πˇ(⋅|S)∈Aˇepi,πˇ(⋅|s)=δUfor s∈E,I,R. _ SEIR= \ π: π(·|S)∈ A_ epi, π(·|s)= _U\ for s∈\E,I,R\ \. Therefore |ΠˇSEIR|=|Aˇepi|=11| _ SEIR|=| A_ epi|=11. With the configuration in Table 1, SEIR is the most demanding of the three examples because the state space is larger and the discount factor β is higher. Nevertheless, Figure 4 shows that the asynchronous curves remain close to the idealized reference. At ζ=0.5ζ=0.5, the mean reward from Algorithm 1 increases from −2.680-2.680 at m=0m=0 to −2.641-2.641 at m=0.15m=0.15, then decreases slightly to −2.646-2.646 at m=1m=1. At ζ=1ζ=1, robustness increases the mean reward from Algorithm 1 from −2.775-2.775 at m=0m=0 to −2.650-2.650 at m=0.5m=0.5. Figure 4. SEIR robustness profile. Solid curves show reward means from the asynchronous implementation of Algorithm 1; dashed curves show idealized references. Even at the high discount β=0.9β=0.9, the robust Q-learning algorithm matches the finite-grid idealized benchmark. 4. From Mean-field control to Q-learning In this section, we introduce the robust mean-field control (MFC) problem under common noise uncertainty, which serves as the baseline for our Q-learning algorithm developed in Section 2. We first show how this MFC problem is linked to the fixed-point v∗v^* established in Proposition 2.4. In particular, the optimal Q-function Q∗Q^* defined in (2.3), constructed from v∗v^*, serves as the learning target for our Q-learning algorithm. Building on this connection, we then introduce a discretized approximation of Q∗Q^*, which enables the tabular representation of our Q-learning algorithm as in Framework 2.9. In particular, the quantization and projection introduced in Definition 2.5 constitute the key ingredients for constructing the stochastic iterative scheme associated with the discretized Q-function. 4.1. Robust MFC problem under common noise uncertainty We introduce a social planner’s robust MFC problem under common noise uncertainty studied in [48], which serves as the basis for our Q-learning algorithm and its convergence results in Section 2. We begin by constructing a measurable space (Ω,F)( ,F). Recalling from Section 2 the idiosyncratic noise space E and common noise space E0E^0, define G:=[0,1]G:=[0,1] and Θ:=[0,1] :=[0,1], which represent the initial information space and randomization source space, respectively. We let the space Ω be defined by Ω:=ω:=((gi)i∈ℕ,(θti)t≥0,i∈ℕ,(eti)t≥1,i∈ℕ,(et0)t≥1):(gi,θti)∈G×Θ,for t≥0,i∈ℕ;(eti,et0)∈E×E0,fort≥1,i∈ℕ. := \ω:= ((g^i)_i ,( _t^i)_t≥ 0,i ,(e_t^i)_t≥ 1,i ,(e^0_t)_t≥ 1 )\;: aligned &\;(g^i,θ^i_t)∈ G× ,\;\; for $t≥ 0$,\;i ;\\ &\;(e^i_t,e^0_t)∈ E× E^0,\;\; for\;t≥ 1,\;i aligned \. Then define, for every ω∈Ωω∈ , (4.1) (γi(ω),ϑ0i(ω)):=(gi,θ0i)∈G×Θi∈ℕ,(ϑti(ω),εti(ω)):=(θti,eti)∈Θ×Et≥1,i∈ℕ,εt0(ω):=et0∈E0t≥1, aligned (γ^i(ω), _0^i(ω) )&:=(g^i,θ^i_0)∈ G× &&i ,\\ ( _t^i(ω), ^i_t(ω) )&:=(θ^i_t,e_t^i)∈ × E &&t≥ 1,\;\;i ,\\ _t^0(ω)&:=e_t^0∈ E^0 &&t≥ 1, aligned so that γiγ^i and (ϑti)t≥0( _t^i)_t≥ 0 represent the initial state information of agent i and her randomization source process, respectively. Moreover, (εti)t≥1( _t^i)_t≥ 1 represents her idiosyncratic noise process, whereas (εt0)t≥1( _t^0)_t≥ 1 represents the common noise process for all agents. Last, we let the σ-algebra ℱF be defined by F:=σ((γi)i∈ℕ,(ϑti)t≥0,i∈ℕ,(εti)t≥1,i∈ℕ,(εt0)t≥1)F:=σ((γ^i)_i ,( _t^i)_t≥ 0,i ,( _t^i)_t≥ 1,i ,( ^0_t)_t≥ 1). Under this setting, we introduce the following filtrations: for each i∈ℕi ⋅· 0:=(Ft0)t≥0F^0:=(F_t^0)_t≥ 0 is given by F00:=∅,ΩF_0^0:=\ , \ and Ft0:=σ(ε1:t0)F^0_t:=σ( _1:t^0) for any t≥1t≥ 1. ⋅· i:=(Fti)t≥0F^i:=(F^i_t)_t≥ 0 is given by F0i:=σ(γi)F_0^i:=σ(γ^i) and Fti:=σ(γi,ϑ0:t−1i,ε1:ti,ε1:t0)F^i_t:=σ(γ^i, _0:t-1^i, _1:t^i, _1:t^0) for any t≥1t≥ 1. ⋅· i:=(Gti)t≥0G^i:=(G^i_t)_t≥ 0 is given by Gti:=Fti∨σ(ϑti)G_t^i:=F_t^i σ( _t^i) for all t≥0t≥ 0 so that i⊆iF^i ^i. While Ft0F_t^0 represents the common noise information shared by all agents at time t, FtiF_t^i and GtiG_t^i represent the information of agent i at time t for her state and action processes, respectively (see Definition 4.4). In particular, GtiG_t^i contains the current randomization source ϑti _t^i whereas FtiF_t^i does not. Consequently, these filtrations satisfy 0⊂i⊂iF^0 ^i ^i. In what follows, we construct a set of probability measures that support all the random sources defined in (4.1) while inducing common noise uncertainty. To this end, we recall from Section 1 the set Bm,q0(p^ε0)B^0_m,q( p_ ^0) in (1.2), together with the law pε∈E¯p_ ∈ E. Definition 4.1. Let pγ:=pϑ:=L[0,1]p_γ:=p_ :=L_[0,1], where L[0,1]L_[0,1] denotes the Lebesgue measure on [0,1][0,1]. (i) Let 0K^0 be the set of (pt)t≥1(p_t)_t≥ 1 consisting of a measure and sequence of kernels such that p1∈Bm,q0(p^ε0);pt:(E0)t−1∋e1:t−10↦pt(det0|e1:t−10)∈Bm,q0(p^ε0)for all t≥2, 30.00005ptp_1∈B^0_m,q( p_ ^0); p_t:(E^0)^t-1 e_1:t-1^0 p_t(de_t^0|e_1:t-1^0)∈B^0_m,q( p_ ^0) for all $t≥ 2$, inducing distributional uncertainty in the law of the common noise process (εt0)t≥1( _t^0)_t≥ 1. (i) Let QQ be defined as the subset of all Borel probability measures ℙP on Ω induced by some (pt)t≥1∈0(p_t)_t≥ 1 ^0 in the sense that444For any set X and t≥1t≥ 1, we use the notation Xt:=X×⋯×X^t:=X×·s× X for the t-times Cartesian product of X. Moreover, we write XℕX^N for the countably infinite Cartesian product of X. for every B0∈⋁i∈ℕ0iB_0∈ _i G_0^i and B1∈⋁i∈ℕG1iB_1∈ _i G_1^i ℙ(γi,ϑ0i)i∈ℕ∈B0=Q^0(B0),ℙ((γi,ϑ0:1i,ε1i)i∈ℕ,ε10)∈B1=(Q^0⊗Q^p1)(B1), 40.00006pt aligned &P \(γ^i, _0^i)_i ∈ B_0 \= Q_0(B_0), \((γ^i, _0:1^i, _1^i)_i , _1^0)∈ B_1 \=( Q_0 Q^p_1)(B_1), aligned where Q^0((dgi,dθ0i)i∈ℕ):=⊗i∈ℕpγ(dgi)pϑ(dθ0i)∈P((G×Θ)ℕ)Q^p1((dθ1i,de1i)i∈ℕ,de10):=⊗i∈ℕpϑ(dθ1i)pε(de1i)p1(de10)∈P((Θ×E)ℕ×E0), 40.00006pt aligned Q_0 ((dg^i,d _0^i)_i )&:= _i \p_γ(dg^i)p_ (dθ^i_0) \∈P ((G× )^N )\\ Q^p_1 ((dθ^i_1,de^i_1)_i ,de^0_1 )&:= _i \p_ (d _1^i)p_ (de_1^i) \p_1(de^0_1)∈P (( × E)^N× E^0 ), aligned whereas for every t≥2t≥ 2 and Bt∈⋁i∈ℕGtiB_t∈ _i G_t^i ℙ((γi,ϑ0:ti,ε1:ti)i∈ℕ,ε1:t0)∈Bt=(Q^0⊗Q^p1⊗^Q^p2⊗^⋯⊗^Q^pt)(Bt), 30.00005ptP \ ((γ^i, ^i_0:t, _1:t^i)_i , _1:t^0 )∈ B_t \=( Q_0 Q^p_1 Q^p_2 ·s Q^p_t)(B_t), where the kernel Q^pt:(E0)t−1∋e1:t−10↦Q^pt((dθti,deti)i∈ℕ,det0|e1:t−10)∈P((Θ×E)ℕ×E0) Q^p_t:(E^0)^t-1 e_1:t-1^0 Q^p_t((d _t^i,de_t^i)_i ,de_t^0|e_1:t-1^0)∈P(( × E)^N× E^0) is defined by Q^pt((dθti,deti)i∈ℕ,det0|e1:t−10):=⊗i∈ℕpϑ(dθti)pε(deti)pt(det0|e1:t−10). 30.00005pt Q^p_t ((d _t^i,de_t^i)_i ,de_t^0|e_1:t-1^0 ):= _i \p_ (dθ^i_t)p_ (de_t^i) \p_t(de_t^0|e_1:t-1^0). Remark 4.2. The introduction of G and Θ , together with pγp_γ and pϑp_ in Definition 4.1, allows each agent i∈ℕi to randomize the optimal policy determined by the social planner. This aligns with the existing literature on MFC problems with common noise; see, e.g., [17, 48, 64]. Moreover, the following statements hold: For any ℙ∈QP∈Q with corresponding (pt)t≥1∈0(p_t)_t≥ 1 ^0 (i) (γi)i∈ℕ(γ^i)_i is independent and identically distributed (i.i.d.) with law pγp_γ. Moreover, (ϑti)t≥0,i∈ℕ( _t^i)_t≥ 0,i is i.i.d. with law pϑp_ , and (εti)t≥1,i∈ℕ( _t^i)_t≥ 1,i is i.i.d. with law pεp_ . (i) ε10 _1^0 is independent of ⋁i∈ℕG0i _i G_0^i with law p1p_1, whereas for every t≥2t≥ 2 εt0 _t^0 is conditionally independent of ⋁i∈ℕGt−1i _i G_t-1^i given Ft−10F_t-1^0, satisfying ℒℙ(εt0|Ft−10)=pt(⋅|ε1:t−10)ℙ-a.s.. L_P( _t^0|F_t-1^0)=p_t(\,·\,| _1:t-1^0) $P$-a.s.. Therefore, (εt0)t≥1( _t^0)_t≥ 1 is uncertain in the Wasserstein sense specified in (1.2). Remark 4.3. Recall the reference measure pε∈E¯p_ ∈ E. Let (p^t)t≥1∈K0( p_t)_t≥ 1∈K^0 be defined by p^1:=p^ε0,p^t:(E0)t−1∋e1:t−10↦p^t(det0|e1:t−10):=p^ε0(det0)for all t≥2. p_1:= p_ ^0, p_t:(E^0)^t-1 e_1:t-1^0 p_t(de_t^0|e_1:t-1^0):= p_ ^0(de_t^0) for all $t≥ 2$. Then we denote by ℙ^∈Q P∈Q the probability measure induced by (p^t)t≥1( p_t)_t≥ 1, representing the reference probability measure on (Ω,F)( ,F). When m=0m=0 (so that Q=ℙ^Q=\ P\, i.e., in the absence of uncertainty), the probability framework in Definition 4.1 coincides with the setting in [17, Section 2.1.2] and is also similar to the one in [64, Section 2]. We now define the social planner’s robust MFC problem under open-loop controls setting, following [17, Definition 10] and [48, Definition 2.5]. To this end, we recall from Section 1 the state space S and action space A, together with the basic components F,r,βF,r,β in (1.1) and (1.3). Definition 4.4. For each i∈ℕi , let Lℱ0i0(S)L^0_F_0^i(S) denote the set of ℱ0iF_0^i-measurable, S-valued random variables, representing the initial states of agent i. (i) Denote by ΠOL ^OL the set of all open-loop policies π:=(πt)t≥0π:=( _t)_t≥ 0 in the sense that πt:G×Θt+1×Et×(E0)t→A _t:G× ^t+1× E^t×(E^0)^t→ A is a Borel measurable function for all t≥0t≥ 0. For any π:=(πt)t≥0∈ΠOLπ:=( _t)_t≥ 0∈ ^OL, the corresponding action process of agent i is given by the open-loop control ati,π:=πt(γi,ϑ0:ti,ε1:ti,ε1:t0)t≥1,witha0i,π:=π0(γi,ϑ0i). 10.00002pta_t^i,π:= _t(γ^i, _0:t^i, _1:t^i, _1:t^0) t≥ 1, with\;\;a_0^i,π:= _0(γ^i, _0^i). In other words, (ati,π)t≥0(a_t^i,π)_t≥ 0 is a iG^i-adapted process. (i) Let ξi∈Lℱ0i0(S)ξ^i∈ L^0_F_0^i(S) be an initial state of agent i. For any π:=(πt)t≥0∈ΠOLπ:=( _t)_t≥ 0∈ ^OL, the state process of agent i under ℙ∈QP∈Q is governed by the conditional McKean–Vlasov dynamics: (4.2) st+1i,π,ℙ 10.00002pts_t+1^i,π,P :=F(sti,π,ℙ,ati,π,Λti,π,ℙ,εt+1i,εt+10)t≥0,with s0i,π,ℙ:=ξi, :=F(s^i,π,P_t,a^i,π_t, _t^i,π,P, _t+1^i, _t+1^0) t≥ 0, with s_0^i,π,P:=ξ^i, where (ati,π)t≥0(a^i,π_t)_t≥ 0 is the open-loop control of agent i as defined in (i), and Λti,π,ℙ _t^i,π,P is the conditional joint law of (sti,π,ℙ,ati,π)(s^i,π,P_t,a^i,π_t) under ℙP given the common noise trajectory ε1:t0 _1:t^0, i.e., Λti,π,ℙ:=ℒℙ((sti,π,ℙ,ati,π)|ε1:t0)t≥1, 10.00002pt _t^i,π,P:= L_P ((s^i,π,P_t,a^i,π_t)| _1:t^0 ) t≥ 1, with the convention that Λ0i,π,ℙ:=ℒℙ((s0i,π,ℙ,a0i,π)) _0^i,π,P:= L_P((s^i,π,P_0,a^i,π_0)). (i) The contribution of agent i to the social planner’s gain under π:=(πt)t≥0∈ΠOLπ:=( _t)_t≥ 0∈ ^OL and ℙ∈QP∈Q is defined by (4.3) Ri,π,ℙ(ξi):=∑t=0∞βtr(sti,π,ℙ,ati,π,Λti,π,ℙ). R^i,π,P(ξ^i):= _t=0^∞β^tr(s_t^i,π,P,a_t^i,π, _t^i,π,P). Then the social planner’s robust MFC problem is defined by (4.4) Vi(ξi):=supπ∈ΠOLJi,π(ξi),where Ji,π(ξi):=infℙ∈Qℙ[Ri,π,ℙ(ξi)]. V^i(ξ^i):= _π∈ ^OLJ^i,π(ξ^i), where J^i,π(ξ^i):= _P∈QE^P[R^i,π,P(ξ^i)]. Remark 4.5. Recall F¯,r¯ F, r defined in Definition 2.1. The following statements hold for any i∈ℕi . (i) By construction of the set QQ in Definition 4.1, the law of the initial state ξi∈LF0i0(S)ξ^i∈ L_F_0^i^0(S) is invariant w.r.t. the choice of supporting measure ℙ∈QP∈Q (see also [48, Section 2.4, footnote 3]). Therefore, we can and do write ℒ(ξi):=ℒℙ(ξi)∈S¯ L(ξ^i):= L_P(ξ^i)∈ S for any ℙ∈QP∈Q. (i) For t≥1t≥ 1, let μti,π,ℙμ^i,π,P_t be the conditional law of sti,π,ℙs^i,π,P_t under ℙP given ε1:t0 _1:t^0, with μ0i,π,ℙ:=ℒ(ξi)μ^i,π,P_0:= L(ξ^i). Then both (μti,π,ℙ)t≥0(μ^i,π,P_t)_t≥ 0 and (Λti,π,ℙ)t≥0( ^i,π,P_t)_t≥ 0 in (4.2) are 0F^0-adapted, satisfying μt+1i,π,ℙ=F¯(Λti,π,ℙ,εt+10)ℙ-a.s., for all t≥0.μ^i,π,P_t+1= F( _t^i,π,P, _t+1^0) $P$-a.s., for all $t≥ 0$. Moreover, under the boundedness condition on r in Assumption 2.2 (i), for any π:=(πt)t≥0∈ΠOLπ:=( _t)_t≥ 0∈ ^OL and ℙ∈QP∈Q, Ri,π,ℙ(ξi)R^i,π,P(ξ^i) in (4.3) satisfies ℙ[Ri,π,ℙ(ξi)]=ℙ[∑t=0∞βtr¯(Λti,π,ℙ)].E^P[R^i,π,P(ξ^i)]=E^P [ _t=0^∞β^t r( _t^i,π,P) ]. This implies that the robust MFC problem ViV^i in (4.4) can be formulated as a robust Markov decision process (MDP) on the probability space S¯ S, as shown in [48, Proposition 2.12 and Remark 2.13]. The following theorem shows that the robust MFC problem Vi(ξi)V^i(ξ^i) in (4.4) is law invariant in the sense that Vi(ξi)V^i(ξ^i) depends on its initial state ξiξ^i only via its law ℒ(ξi) L(ξ^i); see Remark 4.5 (i). Moreover, it is indistinguishable in the sense that for any i∈ℕi , Vi(ξi)V^i(ξ^i) coincides with the unique fixed point v∗v^* of the Bellman–Isaacs operator TT defined in (2.2) (see Proposition 2.4). This result follows from [48, Theorem 2.21]. Theorem 4.6. Under Assumption 2.2, it holds for any i∈ℕi that v∗(ℒ(ξi))=Vi(ξi)v^*( L(ξ^i))=V^i(ξ^i). This result is the verification theorem for the robust MFC problem in Definition 4.4. In particular, it justifies that the optimal Q-function Q∗Q^* defined in (2.3), constructed from the fixed point v∗v^* in Proposition 2.4, indeed serves as the learning target for the robust MFC problem. 4.2. Discretized Q-function Since the optimal Q-function Q∗Q^* in (2.3) is defined on a infinite dimensional domain, a direct tabular implementation is not feasible. In this section, we will introduce an approximation of Q∗Q^* living only on the finite subset Sˇ×Πˇ⊂S¯×Π S× ⊂ S× , we refer to as the discretized Q-function, based on quantization and projection introduced in Definition 2.5. Then we will establish the corresponding approximation error bounds. To this end, recalling the mapping F¯ F in Definition 2.1 (i) and the projection pjSˇpj_ S in Definition 2.5 (i), we define the projected version of F¯ F by (4.5) Fˇ:Sˇ×Πˇ×E0∋(μˇ,πˇ,e0)↦Fˇ(μˇ,πˇ,e0):=pjSˇ(F¯(μˇ⊗^πˇ,e0))∈Sˇ. F: S× × E^0 ( μ, π,e^0) F( μ, π,e^0):=pj_ S( F( μ π,e^0))∈ S. Then we introduce a discretized version Tˇ T of the Bellman–Isaacs operator TT in (2.2), defined on the set ℓ∞(Sˇ):=vˇ:Sˇ→ℝ ^∞( S):=\ v: S endowed with ‖vˇ‖Sˇ:=maxμˇ∈Sˇ|vˇ(μˇ)|\| v\|_ S:= _ μ∈ S| v( μ)|, by (4.6) Tˇvˇ(μˇ):=maxπˇ∈Πˇr¯(μˇ⊗^πˇ)+βinfp∈Bm,q0(p^ε0)∫E0vˇ(Fˇ(μˇ,πˇ,e0))p(de0),μˇ∈Sˇ. T v( μ):= _ π∈ \ r( μ π)+β _p∈B^0_m,q( p_ ^0) _E^0 v ( F( μ, π,e^0) )p(de^0) \, μ∈ S. The following lemma shows that Tˇ T admits a unique fixed point. Lemma 4.7. Suppose that Assumption 2.2 is satisfied. Then there exists a unique fixed point vˇ∗∈ℓ∞(Sˇ) v^*∈ ^∞( S) of Tˇ T satisfying vˇ∗=Tˇvˇ∗ v^*= T v^*. Moreover, for any vˇ∈ℓ∞(Sˇ) v∈ ^∞( S), limn→∞Tˇnvˇ=vˇ∗ _n→∞ T^n v= v^*. Proof. We show that ˇ T is a contraction on (ℓ∞(Sˇ),∥⋅∥Sˇ×Πˇ)( ^∞( S),\|·\|_ S× ). Since vˇ∈ℓ∞(Sˇ) v∈ ^∞( S) and the reward function r are bounded (see Remark 2.3), we have ‖Tˇvˇ‖Sˇ≤sup(s,a,Λ)∈S×A×S×A¯|r(s,a,Λ)|+β‖vˇ‖Sˇ=Cr,∞+β‖vˇ‖Sˇ<∞,\| T v\|_ S≤ _(s,a, )∈ S× A× S× A|r(s,a, )|+β\| v\|_ S=C_r,∞+β\| v\|_ S<∞, hence, Tˇvˇ∈ℓ∞(Sˇ) T v∈ ^∞( S). Moreover, for any vˇ,wˇ∈ℓ∞(Sˇ) v, w∈ ^∞( S) and any μˇ∈Sˇ μ∈ S |Tˇvˇ(μˇ)−Tˇwˇ(μˇ)| | T v( μ)- T w( μ)| ≤βmaxπˇ∈Πˇ|infp∈Bm,q0(p^ε0)∫E0vˇ(Fˇ(μˇ,πˇ,e0))p(de0)−infp∈Bm,q0(p^ε0)∫E0wˇ(Fˇ(μˇ,πˇ,e0))p(de0)| ≤β _ π∈ \ | _p∈B^0_m,q( p_ ^0) _E^0 v ( F( μ, π,e^0) )p(de^0)- _p∈B^0_m,q( p_ ^0) _E^0 w ( F( μ, π,e^0) )p(de^0) | \ ≤βmaxπˇ∈Πˇsupp∈Bm,q0(p^ε0)∫|vˇ(Fˇ(μˇ,πˇ,e0))−wˇ(Fˇ(μˇ,πˇ,e0))|p(de0) ≤β _ π∈ _p∈B^0_m,q( p_ ^0) | v ( F( μ, π,e^0) )- w ( F( μ, π,e^0) ) |p(de^0) ≤β‖vˇ−wˇ‖Sˇ. ≤β\| v- w\|_ S. Furthermore, since β∈[0,1)β∈[0,1), Tˇ T is a contraction, as claimed. Thus the proof is concluded by an application of Banach’s fixed point theorem (see, e.g., [6, Theorem A 3.5]). ∎ Using the fixed point vˇ∗ v^* from Lemma 4.7, we define the discretized version of the optimal Q-function by setting for every (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× (4.7) Qˇ∗(μˇ,πˇ):=r¯(μˇ⊗^πˇ)+βinfp∈Bm,q0(p^ε0)∫E0vˇ∗(Fˇ(μˇ,πˇ,e0))p(de0). Q^*( μ, π):= r( μ π)+β _p∈B^0_m,q( p_ ^0) _E^0 v^* ( F( μ, π,e^0) )p(de^0). We have by Lemma 4.7 that maxπˇ∈ΠˇQˇ∗(μˇ,πˇ)=vˇ∗(μˇ) _ π∈ Q^*( μ, π)= v^*( μ) for any μˇ∈Sˇ μ∈ S. We will refer to Qˇ∗ Q^* as the discretized Q-function. Next we aim to establish a bound for the discretized Q-function and quantify its deviation from the optimal Q-function in (2.3) on the quantized spaces Sˇ S and Πˇ . To this end, we collect several preliminary results related to Sˇ S and Πˇ . Lemma 4.8. The following hold: (i) supπ∈Πminπˇ∈ΠˇdΠ(π,πˇ)≤εAˇ _π∈ _ π∈ d_ (π, π)≤ _ A, with the constant εAˇ>0 _ A>0 given in Definition 2.5. (i) For any (μ,π)∈S¯×Π(μ,π)∈ S× and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , W1(μˇ⊗^πˇ,μ⊗^π)≤(1+ΔAΔ¯S−1)W1(μˇ,μ)+dΠ(πˇ,π),W_1( μ π,μ π)≤(1+ _A _S^-1)W_1( μ,μ)+d_ ( π,π), with the constants ΔA _A and Δ¯S _S given in (2.12). Proof. We first prove (i). By Definition 2.5, for any π∈Ππ∈ and s∈Ss∈ S, there exists νsπ∈Aˇ _s^π∈ A such that W1(π(⋅|s),νsπ)≤εAˇ.W_1(π(·|s),ν^π_s)≤ _ A. Define πˇ∈Πˇ π∈ by πˇ(⋅|s):=νsπ π(·|s):= _s^π for each s∈Ss∈ S. Since S is finite, we have dΠ(π,πˇ)=maxs∈SW1(π(⋅|s),νsπ)≤εAˇ.d_ (π, π)= _s∈ SW_1(π(·|s), _s^π)≤ _ A. Hence, minπˇ∈ΠˇdΠ(π,πˇ)≤εAˇ _ π∈ d_ (π, π)≤ _ A, which proves (i). We now prove (i). Let (μ,π)∈S¯×Π(μ,π)∈ S× and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . By the triangle inequality, (4.8) W1(μˇ⊗^πˇ,μ⊗^π)≤W1(μˇ⊗^πˇ,μˇ⊗^π)+W1(μˇ⊗^π,μ⊗^π)=:I+I. W_1( μ π,μ π)≤W_1( μ π, μ π)+W_1( μ π,μ π)=:I+I. For each s∈Ss∈ S, let κs∈Cpl(πˇ(⋅|s),π(⋅|s)) _s ( π(·|s),π(·|s)) be an optimal555That is, κs _s is a coupling such that W1(πˇ(⋅|s),π(⋅|s))=∫A×A|a−a′|κs(da,da′);W_1( π(·|s),π(·|s))= _A× A|a-a | _s(da,da ); see [83, Theorem 4.1]. coupling. Define Γ1(ds,da,ds′,da′):=κs(da,da′)δs(ds′)μˇ(ds)∈Cpl(μˇ⊗^πˇ,μˇ⊗^π). ^1(ds,da,ds ,da ):= _s(da,da ) _s(ds ) μ(ds) ( μ π, μ π). Then, by the definition of W1W_1, (4.9) I≤∫SW1(πˇ(⋅|s),π(⋅|s))μˇ(ds)≤dΠ(πˇ,π). ≤ _SW_1( π(·|s),π(·|s)) μ(ds)≤ d_ ( π,π). Next, let γ∈Cpl(μˇ,μ)γ ( μ,μ) be an optimal coupling. For each s,s′∈Ss,s ∈ S, let κs,s′∈Cpl(π(⋅|s),π(⋅|s′)) _s,s (π(·|s),π(·|s )) be an optimal coupling. Define Γ2(ds,da,ds′,da′):=κs,s′(da,da′)γ(ds,ds′)∈Cpl(μˇ⊗^π,μ⊗^π). ^2(ds,da,ds ,da ):= _s,s (da,da )γ(ds,ds ) ( μ π,μ π). Then, (4.10) I≤∫S×S(|s−s′|+W1(π(⋅|s),π(⋅|s′)))γ(ds,ds′)≤∫S×S(|s−s′|+ΔAs≠s′)γ(ds,ds′)≤(1+ΔAΔ¯S−1)∫S×S|s−s′|γ(ds,ds′)=(1+ΔAΔ¯S−1)W1(μˇ,μ). aligned I&≤ _S× S (|s-s |+W_1(π(·|s),π(·|s )) )γ(ds,ds )\\ &≤ _S× S(|s-s |+ _A 1_\s≠ s \)γ(ds,ds )\\ &≤(1+ _A _S^-1) _S× S|s-s |γ(ds,ds )=(1+ _A _S^-1)W_1( μ,μ). aligned Combining (4.8), (4.9), and (4.10) yields (i). ∎ Lemma 4.9. Under Assumption 2.2, we have for every (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× that |Qˇ∗(μˇ,πˇ)| | Q^*( μ, π)| ≤Cr,∞1−β, ≤ C_r,∞1-β, |Qˇ∗(μˇ,πˇ)−Q∗(μˇ,πˇ)| | Q^*( μ, π)-Q^*( μ, π)| ≤β1−β(L∗εSˇ+2(Cr+βL∗CF)εAˇ), ≤ β1-β (L^* _ S+2(C_r+β L^*C_F) _ A ), with the constant L∗>0L^*>0 given in Proposition 2.4. Proof. We first show that the first estimate holds. Indeed, since maxπˇ′∈ΠˇQˇ∗(μˇ′,πˇ′)=vˇ∗(μˇ′) _ π ∈ Q^*( μ , π )= v^*( μ ) for all μˇ′∈Sˇ μ ∈ S (see (4.7)), by the boundedness of r (see Remark 2.3), for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× |Qˇ∗(μˇ,πˇ)| | Q^*( μ, π)| ≤|r¯(μˇ⊗^πˇ)|+βinfp∈Bm,q0(p^ε0)∫E0maxπˇ′∈Πˇ|Qˇ∗(Fˇ(μˇ,πˇ,e0),πˇ′)|p(de0) ≤| r( μ π)|+β _p∈B^0_m,q( p_ ^0) _E^0 _ π ∈ | Q^*( F( μ, π,e^0), π ) |p(de^0) ≤Cr,∞+βmax(μˇ′,πˇ′)∈Sˇ×Πˇ|Qˇ∗(μˇ′,πˇ′)|. ≤C_r,∞+β _( μ , π )∈ S× | Q^*( μ , π )|. This ensures the first estimate to hold. Next we show that the other estimate holds. Let (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× be given. For every e0∈E0e^0∈ E^0, define μˇ′(e0):=Fˇ(μˇ,πˇ,e0)∈Sˇ μ (e^0):= F( μ, π,e^0)∈ S and μ′(e0)=F¯(μˇ⊗^πˇ,e0)∈S¯μ (e^0)= F( μ π,e^0)∈ S. Then, (4.11) |Qˇ∗(μˇ,πˇ)−Q∗(μˇ,πˇ)|≤βsupp∈Bm,q0(p^ε0)∫|vˇ∗(μˇ′(e0))−v∗(μ′(e0))|p(de0)≤βsupp∈Bm,q0(p^ε0)∫E0(|vˇ∗(μˇ′(e0))−v∗(μˇ′(e0))|+|v∗(μˇ′(e0))−v∗(μ′(e0))|)p(de0). aligned &| Q^*( μ, π)-Q^*( μ, π)|\\ & ≤β _p∈B^0_m,q( p_ ^0) | v^*( μ (e^0))-v^*(μ (e^0)) |p(de^0)\\ & ≤β _p∈B^0_m,q( p_ ^0) _E^0 (| v^*( μ (e^0))-v^*( μ (e^0))|+|v^*( μ (e^0))-v^*(μ (e^0))| )p(de^0). aligned By the definitions of pjSˇpj_ S and Fˇ F (see Definition 2.5 and (4.5)) and the L∗L^*-Lipschitz continuity of v∗v^* (see Proposition 2.4), it holds that for every e0∈E0e^0∈ E^0 (4.12) |v∗(μˇ′(e0))−v∗(μ′(e0))|≤L∗W1(μˇ′(e0),μ′(e0))≤L∗εSˇ. |v^*( μ (e^0))-v^*(μ (e^0))|≤ L^*W_1 ( μ (e^0),μ (e^0) )≤ L^* _ S. We now claim that for every e0∈E0e^0∈ E^0 (4.13) |vˇ∗(μˇ′(e0))−v∗(μˇ′(e0))|≤max(μˇ′,πˇ′)∈Sˇ×Πˇ|Qˇ∗(μˇ′,πˇ′)−Q∗(μˇ′,πˇ′)|+2(Cr+βL∗CF)εAˇ. | v^*( μ (e^0))-v^*( μ (e^0))|≤ _( μ , π )∈ S× | Q^*( μ , π )-Q^*( μ , π )|+2(C_r+β L^*C_F) _ A. To see this, note that maxπˇ′∈ΠˇQˇ∗(μˇ′,πˇ′)=vˇ∗(μˇ′) _ π ∈ Q^*( μ , π )= v^*( μ ) for all μˇ′∈Sˇ μ ∈ S and that Πˇ is finite. Thus, for any e0∈E0e^0∈ E^0, there exists an optimizer πˇ∗(e0)∈Πˇ π^*(e^0)∈ such that vˇ∗(μˇ′(e0))=Qˇ∗(μˇ′(e0),πˇ∗(e0)). v^*( μ (e^0))= Q^*( μ (e^0), π^*(e^0)). Then, since v∗(μˇ′(e0))≥Q∗(μˇ′(e0),πˇ∗(e0))v^*( μ (e^0))≥ Q^*( μ (e^0), π^*(e^0)) for every e0∈E0e^0∈ E^0 (see Proposition 2.4 and (2.3)), (4.14) vˇ∗(μˇ′(e0))−v∗(μˇ′(e0))≤Qˇ∗(μˇ′(e0),πˇ∗(e0))−Q∗(μˇ′(e0),πˇ∗(e0))≤max(μˇ′,πˇ′)∈Sˇ×Πˇ|Qˇ∗(μˇ′,πˇ′)−Q∗(μˇ′,πˇ′)|. aligned v^*( μ (e^0))-v^*( μ (e^0))&≤ Q^*( μ (e^0), π^*(e^0))-Q^*( μ (e^0), π^*(e^0))\\ &≤ _( μ , π )∈ S× | Q^*( μ , π )-Q^*( μ , π )|. aligned Moreover, for any δ>0δ>0 and any e0∈E0e^0∈ E^0, there exists a δ-optimizer πδ(e0)∈Ππ^δ(e^0)∈ such that v∗(μˇ′(e0))=supπ∈ΠQ∗(μˇ′(e0),π)≤Q∗(μˇ′(e0),πδ(e0))+δ.v^*( μ (e^0))= _π∈ Q^*( μ (e^0),π)≤ Q^*( μ (e^0),π^δ(e^0))+δ. Using πˇ∗(e0)∈Πˇ π^*(e^0)∈ (which maximizes vˇ∗(μˇ′(e0)) v^*( μ (e^0))), πδ(e0)∈Ππ^δ(e^0)∈ , and the projection pjΠˇpj_ in Definition 2.5 (i), we have vˇ∗(μˇ′(e0))−v∗(μˇ′(e0))+δ v^*( μ (e^0))-v^*( μ (e^0))+δ ≥Qˇ∗(μˇ′(e0),πˇ∗(e0))−Q∗(μˇ′(e0),πδ(e0)) ≥ Q^*( μ (e^0), π^*(e^0))-Q^*( μ (e^0),π^δ(e^0)) =Qˇ∗(μˇ′(e0),πˇ∗(e0))−Qˇ∗(μˇ′(e0),pjΠˇ(πδ(e0))) = Q^*( μ (e^0), π^*(e^0))- Q^*( μ (e^0),pj_ (π^δ(e^0))) (4.15) +Qˇ∗(μˇ′(e0),pjΠˇ(πδ(e0)))−Q∗(μˇ′(e0),pjΠˇ(πδ(e0))) + Q^*( μ (e^0),pj_ (π^δ(e^0)))-Q^*( μ (e^0),pj_ (π^δ(e^0))) +Q∗(μˇ′(e0),pjΠˇ(πδ(e0)))−Q∗(μˇ′(e0),πδ(e0)) +Q^*( μ (e^0),pj_ (π^δ(e^0)))-Q^*( μ (e^0),π^δ(e^0)) =:I(e0)+I(e0)+I(e0). =:I(e^0)+I(e^0)+I(e^0). By the optimality of πˇ∗(e0) π^*(e^0), we have I(e0)≥0.I(e^0)≥ 0. Moreover, I(e0)≥−max(μˇ′,πˇ′)∈Sˇ×Πˇ|Qˇ∗(μˇ′,πˇ′)−Q∗(μˇ′,πˇ′)|.I(e^0)≥- _( μ , π )∈ S× | Q^*( μ , π )-Q^*( μ , π )|. Lastly, I(e0)≥−|r¯(μˇ′(e0)⊗^pjΠˇ(πδ(e0)))−r¯(μˇ′(e0)⊗^πδ(e0))|−βsupp∈Bm,q0(p^ε0)∫E0|v∗(F¯(μˇ′(e0)⊗^pjΠˇ(πδ(e0))),e~0)−v∗(F¯(μˇ′(e0)⊗^πδ(e0)),e~0)|p(de~0)≥−2(Cr+βL∗CF)W1(μˇ′(e0)⊗^pjΠˇ(πδ(e0)),μˇ′(e0)⊗^πδ(e0))≥−2(Cr+βL∗CF)dΠ(pjΠˇ(πδ(e0)),πδ(e0))≥−2(Cr+βL∗CF)εAˇ. aligned I(e^0)&≥- | r ( μ (e^0) pj_ (π^δ(e^0)) )- r ( μ (e^0) π^δ(e^0) ) |\\ & -β _p∈B^0_m,q( p_ ^0) _E^0 |v^* ( F ( μ (e^0) pj_ (π^δ(e^0)) ), e^0 )-v^* ( F ( μ (e^0) π^δ(e^0) ), e^0 ) |p(d e^0)\\ &≥-2(C_r+β L^*C_F)W_1 ( μ (e^0) pj_ (π^δ(e^0)), μ (e^0) π^δ(e^0) )\\ &≥-2(C_r+β L^*C_F)d_ (pj_ (π^δ(e^0)),π^δ(e^0))\\ &≥-2(C_r+β L^*C_F) _ A. aligned The second inequality follows from the apriori estimates for r¯ r and F¯ F given in Remark 2.3, together with the L∗L^*-Lipschitz continuity of v∗v^* in Proposition 2.4. The third inequality follows from Lemma 4.8 (i), and the last inequality follows from Lemma 4.8 (i). Combining the estimates for I(e0),I(e^0), I(e0)I(e^0) and I(e0)I(e^0) with (4.15), we have (4.16) vˇ∗(μˇ′(e0))−v∗(μˇ′(e0))+δ≥−max(μˇ′,πˇ′)∈Sˇ×Πˇ|Qˇ∗(μˇ′,πˇ′)−Q∗(μˇ′,πˇ′)|−2(Cr+βL∗CF)εAˇ. v^*( μ (e^0))-v^*( μ (e^0))+δ≥- _( μ , π )∈ S× | Q^*( μ , π )-Q^*( μ , π )|-2(C_r+β L^*C_F) _ A. By letting δ↓0δ 0 this and then using (4.14), we have indeed (4.13), as claimed. Finally, combining (4.11), (4.12) and (4.13) ensures the second inequality to hold. This completes the proof. ∎ The estimate of |Qˇ−Q∗|| Q-Q^*| established in Lemma 4.9 is measured on the quantized space Sˇ×Πˇ S× , rather than on the original space S¯×Π S× . To obtain the desired discretization error for the optimal Q-function, one must account for both the error induced by the projection (from S¯×Π S× onto Sˇ×Πˇ S× ) and the estimate of |Qˇ−Q∗|| Q-Q^*| on the quantized spaces. The following lemma provides such an estimate, quantifying the gap between the optimal Q-function and the discretized Q-function when evaluated on the original domain via the projection in Definition 2.5. Lemma 4.10. Under Assumption 2.2, we have for every (μ,π)∈S¯×Π(μ,π)∈ S× that |Qˇ∗(pjSˇ(μ),pjΠˇ(π))−Q∗(μ,π)|≤C1εSˇ+C2εAˇ, | Q^*(pj_ S(μ),pj_ (π))-Q^*(μ,π)|≤ C_1 _ S+C_2 _ A, with the constants C1C_1 and C2C_2 given in Theorem 2.15. Proof. We first claim that for any (μ,π)∈S¯×Π(μ,π)∈ S× (4.17) |Q∗(pjSˇ(μ),pjΠˇ(π))−Q∗(μ,π)|≤2(Cr+βL∗CF)((1+ΔAΔ¯S−1)εSˇ+εAˇ). |Q^*(pj_ S(μ),pj_ (π))-Q^*(μ,π)|≤ 2(C_r+β L^*C_F) ((1+ _A _S^-1) _ S+ _ A ). Indeed, let (μ,π)∈S¯×Π(μ,π)∈ S× and set μˇ:=pjSˇ(μ) μ:=pj_ S(μ) and πˇ:=pjΠˇ(π) π:=pj_ (π). Then, |Q∗(μˇ,πˇ)−Q∗(μ,π)|≤|r¯(μˇ⊗^πˇ)−r¯(μ⊗^π)|+βsupp∈Bm,q0(p^ε0)∫E0|v∗(F¯(μˇ⊗^πˇ,e0))−v∗(F¯(μ⊗^π,e0))|p(de0)≤2(Cr+βL∗CF)W1(μˇ⊗^πˇ,μ⊗^π)≤2(Cr+βL∗CF)((1+ΔAΔ¯S−1)W1(μˇ,μ)+dΠ(πˇ,π))≤2(Cr+βL∗CF)((1+ΔAΔ¯S−1)εSˇ+εAˇ). aligned &|Q^*( μ, π)-Q^*(μ,π)|\\ & ≤| r( μ π)- r(μ π)|+β _p∈B^0_m,q( p_ ^0) _E^0 |v^*( F( μ π,e^0))-v^*( F(μ π,e^0)) |p(de^0)\\ & ≤ 2(C_r+β L^*C_F)W_1( μ π,μ π)\\ & ≤ 2(C_r+β L^*C_F) ((1+ _A _S^-1)W_1( μ,μ)+d_ ( π,π) )\\ & ≤ 2(C_r+β L^*C_F) ((1+ _A _S^-1) _ S+ _ A ). aligned The second inequality follows from the apriori estimates for r¯ r and F¯ F given in Remark 2.3 , together with the L∗L^*-Lipschitz continuity of v∗v^* (see Proposition 2.4). The third inequality follows from Lemma 4.8 (i), and the last inequality follows from the definition of (μˇ,πˇ)=(pjSˇ(μ),pjΠˇ(π))( μ, π)=(pj_ S(μ),pj_ (π)) (see Definition 2.5) and Lemma 4.8 (i). Combining (4.17) with the second estimate in Lemma 4.9 ensures that for any (μ,π)∈S¯×Π(μ,π)∈ S× |Qˇ∗(pjSˇ(μ),pjΠˇ(π))−Q∗(μ,π)| | Q^*(pj_ S(μ),pj_ (π))-Q^*(μ,π)| ≤|Q∗(pjSˇ(μ),pjΠˇ(π))−Q∗(μ,π)| ≤|Q^*(pj_ S(μ),pj_ (π))-Q^*(μ,π)| +|Qˇ∗(pjSˇ(μ),pjΠˇ(π))−Q∗(pjSˇ(μ),pjΠˇ(π))| +| Q^*(pj_ S(μ),pj_ (π))-Q^*(pj_ S(μ),pj_ (π))| ≤C1εSˇ+C2εAˇ.∎ ≤ C_1 _ S+C_2 _ A. Lemma 4.9 shows that the discretized Q-function in (4.7) serves as a suitable approximation target for learning the optimal Q-function in (2.3). In particular, the error bound in the lemma coincides with the desired accuracy level in the convergence result of Theorem 2.15. 5. Proofs for Convergence of robust Q-Learning Algorithm The goal of this section is to provide the proofs for our main results in Theorem 2.15, Theorem 2.17, and Corollary 2.19. To that end, we begin by establishing two key lemmas that are used to derive both the asymptotic convergence and finite-time iteration bound analyses in the following theorems. Throughout this section, we denote by ‖fˇ‖Sˇ×Πˇ:=max(μˇ,πˇ)∈Sˇ×Πˇ|fˇ(μˇ,πˇ)|for any mapping fˇ:Sˇ×Πˇ→ℝ.\| f\|_ S× := _( μ, π)∈ S× | f( μ, π)| for any mapping $ f: S× $. The first lemma establishes the existence of the maximizer λt,(μˇ,πˇ)∗ _t,( μ, π)^* in (2.10) for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× and t≥0t≥ 0, and provides uniform-in-time bounds for the maximizers (λt,(⋅,⋅)∗)t≥0( _t,(·,·)^*)_t≥ 0 and the Q-functions (Qˇt)t≥0( Q_t)_t≥ 0 introduced in Framework 2.9 (i). Lemma 5.1. Suppose that Assumptions 2.2 (i),(i) and 2.12 (i) are satisfied. Then, for both the synchronous and asynchronous versions of the Q-learning algorithm in Framework 2.9, the following statements hold: for every t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (i) There exists a maximizer λt,(μˇ,πˇ)∗ _t,( μ, π)^* of Φt,(μˇ,πˇ) _t,( μ, π) in (2.10). (i) All maximizers λt,(μˇ,πˇ)∗ _t,( μ, π)^* of Φt,(μˇ,πˇ) _t,( μ, π) satisfy λt,(μˇ,πˇ)∗≤2Qˇmaxmq _t,( μ, π)^*≤ 2 Q_maxm^q. (i) ‖Qˇt‖Sˇ×Πˇ≤Qˇmax.\| Q_t\|_ S× ≤ Q_max. Proof. We first consider the synchronous case under Framework 2.9 (i),(i). (Step 1) Assume first that ‖Qˇt‖Sˇ×Πˇ≤Qˇmax\| Q_t\|_ S× ≤ Q_max for some t≥0t≥ 0. We first show the existence of the maximizer λt,(μˇ,πˇ)∗ _t,( μ, π)^* in (2.10) for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . To see this, we recall the definition of Jt,(μˇ,πˇ)J_t,( μ, π) in (2.9). For λ≥0λ≥ 0 and e0∈E0e^0∈ E^0, it holds that −(−Jt,(μˇ,πˇ))λ(e0)=mine~0∈E0maxπˇ′∈ΠˇQˇt(Fˇ(μˇ,πˇ,e~0),πˇ′)+λ|e0−e~0|q. -(-J_t,( μ, π))^λ(e^0)= _ e^0∈ E^0 \ _ π ∈ Q_t( F( μ, π, e^0), π )+λ|e^0- e^0|^q \. Since E0E^0 is finite, the map ∋λ↦−(−Jt,(μˇ,πˇ))λ(e0) λ -(-J_t,( μ, π))^λ(e^0) is concave and continuous for any e0∈E0e^0∈ E^0. Moreover, since for every λ≥0λ≥ 0 and e0∈E0e^0∈ E^0 (5.1) |(−Jt,(μˇ,πˇ))λ(e0)|≤‖Qˇt‖Sˇ×Πˇ+λmine~0∈E0|e0−e~0|q≤QˇM, |(-J_t,( μ, π))^λ(e^0) |≤\| Q_t\|_ S× +λ _ e^0∈ E^0|e^0- e^0|^q≤ Q_M, the map ϕt,(μˇ,πˇ)(⋅) _t,( μ, π)(·) in (2.10) is continuous and satisfies (5.2) ϕt,(μˇ,πˇ)(λ)≤Qˇmax−mqλ=:ϕ¯(λ)for all λ≥0. _t,( μ, π)(λ)≤ Q_max-m^qλ=: φ(λ) for all $λ≥ 0$. This implies lim supλ→∞ϕt,(μˇ,πˇ)(λ)=−∞ _λ→∞ _t,( μ, π)(λ)=-∞. Therefore, λt,(μˇ,πˇ)∗ _t,( μ, π)^* exists for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . Then we show the upper bound for λt,(μˇ,πˇ)∗ _t,( μ, π)^*. To see this, we note that for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× (5.3) Φt,(μˇ,πˇ)≥ϕt,(μˇ,πˇ)(0)=mine~0∈E0Jt,(μˇ,πˇ)(e~0)≥−‖Qˇt‖Sˇ×Πˇ≥−Qˇmax. aligned _t,( μ, π)≥ _t,( μ, π)(0)&= _ e^0∈ E^0J_t,( μ, π)( e^0)≥-\| Q_t\|_ S× ≥- Q_max. aligned Since ϕ¯(λ¯)=−Qˇmax<0 φ( λ)=- Q_max<0 with λ¯:=2Qˇmaxmq λ:= 2 Q_maxm^q, we have by (5.2) that for every λ≥λ¯λ≥ λ, ϕt,(μˇ,πˇ)(λ)≤ϕ¯(λ)≤−Qˇmax. _t,( μ, π)(λ)≤ φ(λ)≤- Q_max. Combining this with (5.3) yields that λt,(μˇ,πˇ)∗≤λ¯ _t,( μ, π)^*≤ λ for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . (Step 2) We now establish the bounds for λt,(μˇ,πˇ)∗ _t,( μ, π)^* and Qˇt Q_t inductively over time t≥0t≥ 0: The claim holds at t=0t=0 by assumption, hence we have by Step 1 that for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , λ0,(μˇ,πˇ)∗≤λ¯ _0,( μ, π)^*≤ λ. Fix t≥0t≥ 0 and suppose ‖Qˇt‖Sˇ×Πˇ≤Qˇmax\| Q_t\|_ S× ≤ Q_max. Then for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , we have Qˇt+1(μˇ,πˇ) Q_t+1( μ, π) ≤(1−αt,(μˇ,πˇ))|Qˇt(μˇ,πˇ)|+αt,(μˇ,πˇ)(|r¯(μˇ⊗^πˇ)|−β(−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(εt+1,(μˇ,πˇ)0)) ≤(1- _t,( μ, π))| Q_t( μ, π)|+ _t,( μ, π) (| r( μ π)|-β(-J_t,( μ, π)) _t,( μ, π)^*( _t+1,( μ, π)^0) ) (5.4) ≤(1−αt,(μˇ,πˇ))Qˇmax+αt,(μˇ,πˇ)(Cr,∞+β|(−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(εt+1,(μˇ,πˇ)0)|) ≤(1- _t,( μ, π)) Q_max+ _t,( μ, π) (C_r,∞+β |(-J_t,( μ, π)) _t,( μ, π)^*( _t+1,( μ, π)^0) | ) ≤(1−αt,(μˇ,πˇ))Qˇmax+αt,(μˇ,πˇ)(Cr,∞+βQˇmax)=Qˇmax(1−2αt,(μˇ,πˇ)β)<Qˇmax, ≤(1- _t,( μ, π)) Q_max+ _t,( μ, π)(C_r,∞+β Q_max)= Q_max(1-2 _t,( μ, π)β)< Q_max, where the second inequality follows from the boundedness of r (see Remark 2.3) and the third inequality follows from (5.1). In a similar manner, by using λt,(μˇ,πˇ)∗≤λ¯, _t,( μ, π)^*≤ λ, we have for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , Qˇt+1(μˇ,πˇ)≥ Q_t+1( μ, π)≥ −(1−αt,(μˇ,πˇ))|Qˇt(μˇ,πˇ)| -(1- _t,( μ, π))| Q_t( μ, π)| +αt,(μˇ,πˇ)(−|r¯(μˇ⊗^πˇ)|+β[−(−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(εt+1,(μˇ,πˇ)0)−mqλt,(μˇ,πˇ)∗]) + _t,( μ, π) (-| r( μ π)|+β [-(-J_t,( μ, π)) _t,( μ, π)^*( _t+1,( μ, π)^0)-m^q _t,( μ, π)^* ] ) ≥ ≥ −(1−αt,(μˇ,πˇ))Qˇmax−αt,(μˇ,πˇ)(Cr,∞+β|(−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(εt+1,(μˇ,πˇ)0)|+βmqλt,(μˇ,πˇ)∗) -(1- _t,( μ, π)) Q_max- _t,( μ, π) (C_r,∞+β |(-J_t,( μ, π)) _t,( μ, π)^*( _t+1,( μ, π)^0) |+β m^q _t,( μ, π)^* ) ≥ ≥ −(1−αt,(μˇ,πˇ))Qˇmax−αt,(μˇ,πˇ)(Cr,∞+3βQˇmax)=−Qˇmax, -(1- _t,( μ, π)) Q_max- _t,( μ, π)(C_r,∞+3β Q_max)=- Q_max, where the last equality holds because Qˇmax=Cr,∞1−3β Q_max= C_r,∞1-3β with β<13β< 13 (see Assumption 2.12 (i)). Combining this with (5.4) yields ‖Qˇt+1‖Sˇ×Πˇ≤Qˇmax\| Q_t+1\|_ S× ≤ Q_max. By induction, the estimate in (i) for Qˇt Q_t holds for all t and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . Step 1 then ensures that the other estimate in (i) λt,(μˇ,πˇ)∗λ^*_t,( μ, π) hold for all t and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . For the case of the asynchronous version, the Q-learning update rule in (2.8) occurs only along the pre-sampled, projected dataset (μˇt,πˇt)t≥0⊆Sˇ×Πˇ( μ_t, π_t)_t≥ 0 S× in Framework 2.9 (i). Therefore, the arguments of Steps 1 and 2 can directly be applied also for the asynchronous case, yielding the existence of (λt,(⋅,⋅)∗)t≥0(λ^*_t,(·,·))_t≥ 0 and the bounds for (λt,(⋅,⋅)∗)t≥0(λ^*_t,(·,·))_t≥ 0 and (Qˇt)t≥0( Q_t)_t≥ 0 given in (i) and (i). This completes the proof. ∎ Using Remark 2.10 (i), we can rewrite the update rule (2.8) in the standard form of stochastic iterative algorithms considered in [11]: for every t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (5.5) Qˇt+1(μˇ,πˇ)=(1−αt,(μˇ,πˇ))Qˇt(μˇ,πˇ)+αt,(μˇ,πˇ)(HˇQˇt(μˇ,πˇ)+βZt+1,(μˇ,πˇ)),whereZt+1,(μˇ,πˇ):=[−(−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(εt+1,(μˇ,πˇ)0)−mqλt,(μˇ,πˇ)∗]−Φt,(μˇ,πˇ), aligned & Q_t+1( μ, π)=(1- _t,( μ, π)) Q_t( μ, π)+ _t,( μ, π) ( H Q_t( μ, π)+β Z_t+1,( μ, π) ),\\ & where Z_t+1,( μ, π):= [-(-J_t,( μ, π)) _t,( μ, π)^*( _t+1,( μ, π)^0)-m^q _t,( μ, π)^* ]- _t,( μ, π), aligned where the operator ℋˇ H on the set Qˇ:Sˇ×Πˇ→ℝ\ Q: S× \ is defined by setting for every (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (5.6) HˇQˇ(μˇ,πˇ):=r¯(μˇ⊗^πˇ)+βinfp∈Bm,q0(p^ε0)∫E0maxπˇ′∈ΠˇQˇ(Fˇ(μˇ,πˇ,e0),πˇ′)p(de0). H Q( μ, π):= r( μ π)+β _p∈B^0_m,q( p_ ^0) _E^0 _ π ∈ Q ( F( μ, π,e^0), π )p(de^0). Next we let ˇ0:=(Fˇt0)t≥0 F^0:=( F_t^0)_t≥ 0 be defined by (5.7) Fˇt0:=σ(εs,(μˇ,πˇ)0:(μˇ,πˇ)∈Sˇ×Πˇ,1≤s≤t),t≥1,with Fˇ00:=∅,Ω0. F_t^0:=σ ( ^0_s,( μ, π):( μ, π)∈ S× ,1≤ s≤ t ), t≥ 1, with $ F_0^0:=\ , ^0\.$ Remark 5.2. By definition of Qˇ∗ Q^* in (4.7) and the operator Hˇ H in (5.6), we have Qˇ∗=HˇQˇ∗ Q^*= H Q^*. Remark 5.3. Recall the probability space (Ω0,F0,ℙ^0)( ^0,F^0, P^0) introduced in Framework 2.9 and the filtration ˇ0 F^0 defined in (5.7). The following hold for every t≥0t≥ 0 and every (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . (i) The random variable Zt+1,(μˇ,πˇ)Z_t+1,( μ, π) in (5.5) is Fˇt+10 F_t+1^0-measurable, (i) Φt,(μˇ,πˇ) _t,( μ, π), λt,(μˇ,πˇ)∗ _t,( μ, π)^*, and (−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗:E0→ℝ(-J_t,( μ, π)) _t,( μ, π)^*:E^0 are Fˇt0 F_t^0-measurable. Leveraging the convex duality result in Lemma 2.8, and the uniform-in-time bound result for (Qˇt)t≥0( Q_t)_t≥ 0 in Lemma 5.1, it is possible to show that Zt+1,(⋅,⋅)Z_t+1,(·,·) defined in (5.5) is bounded and has conditional zero mean with respect to Fˇt0 F^0_t in (5.7). Lemma 5.4. Suppose that Assumptions 2.2 (i),(i) and 2.12 (i) are satisfied. Then, for both the synchronous and asynchronous versions of the Q-learning algorithm in Framework 2.9, the following properties hold: for every t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , ℙ^0[Zt+1,(μˇ,πˇ)|Fˇt0]=0ℙ^0-a.s.,and|Zt+1,(μˇ,πˇ)|≤4Qˇmax.E P^0[Z_t+1,( μ, π)| F_t^0]=0 $ P^0$-a.s., and |Z_t+1,( μ, π)|≤ 4 Q_max. As a consequence, we also obtain that arℙ^0[Zt+1,(μˇ,πˇ)|Fˇt0]≤16Qˇmax2 P^0[Z_t+1,( μ, π)| F_t^0]≤ 16 Q_max^2 ℙ^0 P^0-a.s.. Proof. The proof presented below applies to both the synchronous and asynchronous versions. Let t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . By the definition of Zt+1,(μˇ,πˇ)Z_t+1,( μ, π) in (5.5) and the Fˇt0 F_t^0-measurability of Φt,(μˇ,πˇ) _t,( μ, π) and λt,(μˇ,πˇ)∗ _t,( μ, π)^* in (2.10) (see Remark 5.3 (i)), we have that ℙ^0 P^0-a.s., (5.8) ℙ^0[Zt+1,(μˇ,πˇ)|Fˇt0]+Φt,(μˇ,πˇ)=ℙ^0[−(−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(εt+1,(μˇ,πˇ)0)|Fˇt0]−mqλt,(μˇ,πˇ)∗=:I. P^0[Z_t+1,( μ, π)| F_t^0]+ _t,( μ, π)=E P^0 [-(-J_t,( μ, π)) _t,( μ, π)^*( _t+1,( μ, π)^0) | F_t^0 ]-m^q _t,( μ, π)^*=:I. Moreover, since (−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗:E0→ℝ(-J_t,( μ, π)) _t,( μ, π)^*:E^0 is Ft0F_t^0-measurable (see Remark 5.3 (i)) and the family (εt,(μˇ,πˇ)0)t≥1,(μˇ,πˇ)∈Sˇ×Πˇ⊆E0,( ^0_t,( μ, π))_t≥ 1,( μ, π)∈ S× E^0, is independent and identically distributed according to the law p^ε0 p_ ^0 (see Framework 2.9), we have by Remark 2.10 (i) (see also Lemma 2.8) that ℙ^0 P^0-a.s., I =∫E0(−(−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(e0))p^ε0(de0)−mqλt,(μˇ,πˇ)∗=ϕt,(μˇ,πˇ)(λt,(μˇ,πˇ)∗)=Φt,(μˇ,πˇ), = _E^0 (-(-J_t,( μ, π)) _t,( μ, π)^*(e^0) ) p_ ^0(de^0)-m^q _t,( μ, π)^*= _t,( μ, π)( _t,( μ, π)^*)= _t,( μ, π), where the last two equalities follow from definition of λt,(μˇ,πˇ)∗ _t,( μ, π)^* and (2.10). Combining this with (5.8) yields that ℙ^0[Zt+1,(μˇ,πˇ)|Fˇt0]=0E P^0[Z_t+1,( μ, π)| F_t^0]=0 ℙ^0 P^0-a.s.. Next we show that |Zt+1,(μˇ,πˇ)|≤4Qˇmax|Z_t+1,( μ, π)|≤ 4 Q_max. Indeed, it follows from (2.11) in Remark 2.10 and Lemma 5.1 and (5.1) (see the proof of Lemma 5.1) that |Zt+1,(μˇ,πˇ)|≤|(−Jt,(μˇ,πˇ))λt,(μˇ,πˇ)∗(εt+1,(μˇ,πˇ)0)|+mqλt,(μˇ,πˇ)∗+supp∈ℬm,q0(p^0)∫E0maxπˇ′∈Πˇ|Qˇt(Fˇ(μˇ,πˇ,e0),πˇ′)|p(de0)≤3Qˇmax+‖Qˇt‖Sˇ×Πˇ≤4Qˇmax. aligned &|Z_t+1,( μ, π)|\\ & ≤ |(-J_t,( μ, π)) _t,( μ, π)^*( _t+1,( μ, π)^0) |+m^q _t,( μ, π)^*+ _p _m,q^0( p^0) _E^0 _ π ∈ | Q_t( F( μ, π,e^0), π ) |p(de^0)\\ & ≤ 3 Q_max+\| Q_t\|_ S× ≤ 4 Q_max. aligned Last, we have arℙ^0[Zt+1,(μˇ,πˇ)|Fˇt0]=ℙ^0[|Zt+1,(μˇ,πˇ)|2|Fˇt0]≤16Qˇmax2 P^0[Z_t+1,( μ, π)| F_t^0]=E P^0[|Z_t+1,( μ, π)|^2| F_t^0]≤ 16 Q_max^2 ℙ^0 P^0-a.s.. ∎ 5.1. Proof of Theorem 2.15 The proof of Theorem 2.15 is based on the convergence result for stochastic iterative algorithms in [40, Theorem 1], which we introduce in Lemma 5.5. In particular, the uniform-in-time bound for (Qˇt)t≥0( Q_t)_t≥ 0 established in Lemma 5.1 (i), together with the properties of (Zt+1,(⋅,⋅))t≥0(Z_t+1,(·,·))_t≥ 0 established in Lemma 5.4, are crucial for verifying that both the synchronous and asynchronous versions of our Q-learning algorithm in Framework 2.9 satisfy the hypotheses of [40, Theorem 1]. Applying the convergence result, we obtain that for every (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× limt→∞|Qˇt(μˇ,πˇ)−Qˇ∗(μˇ,πˇ)|=0ℙ^0-a.s., _t→∞| Q_t( μ, π)- Q^*( μ, π)|=0 $ P^0$-a.s., where Qˇ∗ Q^* is the discretized Q-function in (4.7). The desired convergence result presented in Theorem 2.15 then follows from the discretization error estimate for the optimal Q-function given in Lemma 4.10. Lemma 5.5 (Theorem 1 in Jaakkola et al. [40]). Let X and Y be some finite spaces. Consider a family of stochastic processes (αt(x,y),Ft(x,y),Δt(x,y))t≥0,(x,y)∈X×Y( _t(x,y),F_t(x,y), _t(x,y))_t≥ 0,(x,y)∈ X× Y on a probability measure space (Ω~,ℱ~,ℙ~)( , F, P), satisfying, for every t≥0t≥ 0 and (x,y)∈X×Y(x,y)∈ X× Y Δt+1(x,y)=(1−αt(x,y))Δt(x,y)+αt(x,y)Ft(x,y)ℙ~-a.s.. _t+1(x,y)= (1- _t(x,y) ) _t(x,y)+ _t(x,y)F_t(x,y) P-a.s.. Let (ℱ~t)t≥0⊆ℱ~( F_t)_t≥ 0 F be a sequence of increasing σ-algebras such that Δ0(x,y) _0(x,y) and α0(x,y) _0(x,y) are ℱ~0 F_0-measurable for all (x,y)∈X×Y(x,y)∈ X× Y, whereas Δt(x,y) _t(x,y), αt(x,y) _t(x,y), and Ft−1(x,y)F_t-1(x,y) are ℱ~t F_t-measurable for all t≥1t≥ 1 and (x,y)∈X×Y(x,y)∈ X× Y. Furthermore, assume that for every t≥0t≥ 0 and (x,y)∈X×Y(x,y)∈ X× Y, ℙ~ P-a.s., (i) 0≤αt(x,y)≤10≤ _t(x,y)≤ 1, ∑t=0∞αt(x,y)=∞ _t=0^∞ _t(x,y)=∞, and ∑t=0∞αt2(x,y)<∞ _t=0^∞ _t^2(x,y)<∞. (i) There exists some constant δ∈(0,1)δ∈(0,1) such that ∥ℙ~[Ft(⋅,⋅)|ℱ~t]∥X×Y≤δ∥Δt∥X×Y\|E P[F_t(·,·)| F_t]\|_X× Y≤δ\,\| _t\|_X× Y, where we denote by ‖f‖X×Y:=max(x,y)∈X×Y|f(x,y)|\|f\|_X× Y:= _(x,y)∈ X× Y|f(x,y)| for any mapping f:X×Y→ℝf:X× Y . (i) There exists some constant C>0C>0 such that ∥arℙ~[Ft(⋅,⋅)|ℱ~t]∥X×Y≤C(1+∥Δt∥X×Y2),\| P[F_t(·,·)| F_t]\|_X× Y≤ C(1+\| _t\|_X× Y^2), Then limt→∞Δt(x,y)=0 _t→∞ _t(x,y)=0 ℙ~ P-a.s. for any (x,y)∈X×Y(x,y)∈ X× Y. Recalling the iterative Q-functions (Qˇt)t≥0( Q_t)_t≥ 0 given in Framework 2.9 (i) and the discretized optimal Q-function Qˇ∗ Q^* given in (4.7), we define, for every t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (5.9) Δˇt(μˇ,πˇ):=Qˇt(μˇ,πˇ)−Qˇ∗(μˇ,πˇ). _t( μ, π):= Q_t( μ, π)- Q^*( μ, π). By Remark 5.2 and (5.5), we can rewrite the update rule (2.8) as follows: for every t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (5.10) Δˇt+1(μˇ,πˇ)=(1−αt,(μˇ,πˇ))Δˇt(μˇ,πˇ)+αt,(μˇ,πˇ)Fˇt(μˇ,πˇ),where Fˇt(μˇ,πˇ):=HˇQˇt(μˇ,πˇ)−HˇQˇ∗(μˇ,πˇ)+βZt+1,(μˇ,πˇ). aligned & _t+1( μ, π)=(1- _t,( μ, π)) _t( μ, π)+ _t,( μ, π) F_t( μ, π),\\ & where $ F_t( μ, π):= H Q_t( μ, π)- H Q^*( μ, π)+β Z_t+1,( μ, π)$. aligned Proof of Theorem 2.15. For both the synchronous and asynchronous versions of the Q-learning algorithm, we have by Lemma 4.10 that for any t≥0t≥ 0 and (μ,π)∈S¯×Π(μ,π)∈ S× , |Qˇt(pjSˇ(μ),pjΠˇ(π))−Q∗(μ,π)| | Q_t(pj_ S(μ),pj_ (π))-Q^*(μ,π)| (5.11) ≤|Qˇt(pjSˇ(μ),pjΠˇ(π))−Qˇ∗(pjSˇ(μ),pjΠˇ(π))|+|Qˇ∗(pjSˇ(μ),pjΠˇ(π))−Q∗(μ,π)| ≤| Q_t(pj_ S(μ),pj_ (π))- Q^*(pj_ S(μ),pj_ (π))|+| Q^*(pj_ S(μ),pj_ (π))-Q^*(μ,π)| ≤‖Δˇt‖Sˇ×Πˇ+C1εSˇ+C2εAˇ. ≤\| _t\|_ S× +C_1 _ S+C_2 _ A. Thus, it suffices to show that (Δˇt(μˇ,πˇ),αt,(μˇ,πˇ),Fˇt(μˇ,πˇ))t≥0,(μˇ,πˇ)∈Sˇ×Πˇ( _t( μ, π), _t,( μ, π), F_t( μ, π))_t≥ 0,( μ, π)∈ S× in (5.9) and (5.10) satisfy all the conditions of Lemma 5.5, so that for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , Δˇt(μˇ,πˇ)→0 _t( μ, π)→ 0 ℙ^0 P^0-a.s. as t→∞t→∞. We first consider the synchronous version of the Q-learning algorithm. (Measurability) The synchronous learning rates (αt,(μˇ,πˇ))t≥0,(μˇ,πˇ)∈Sˇ×Πˇ( _t,( μ, π))_t≥ 0,( μ, π)∈ S× in Framework 2.9 (i) are deterministic. Moreover, from Remark 5.3, we have for every (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× that Δˇt(μˇ,πˇ) _t( μ, π) and Fˇt−1(μˇ,πˇ) F_t-1( μ, π) are Fˇt0 F_t^0-measurable for any t≥1t≥ 1, while Δˇ0(μˇ,πˇ) _0( μ, π) is Fˇ00 F_0^0-measurable. (Learning rates) Since αt,(μˇ,πˇ)=(t+1)−w _t,( μ, π)=(t+1)^-w for t≥0t≥ 0 with w∈(12,1)w∈( 12,1), for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× ∑t=0∞αt,(μˇ,πˇ)=∑t=0∞(t+1)−w=∞and∑t=0∞αt,(μˇ,πˇ)2=∑t=0∞(t+1)−2w<∞. _t=0^∞ _t,( μ, π)= _t=0^∞(t+1)^-w=∞ and _t=0^∞ _t,( μ, π)^2= _t=0^∞(t+1)^-2w<∞. (Mean estimate of Fˇt F_t) We note that for any t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× (5.12) |HˇQˇt(μˇ,πˇ)−HˇQˇ∗(μˇ,πˇ)|≤βsupp∈Bm,q0(p^ε0)∫E0|maxπˇ1∈ΠˇQˇt(Fˇ(μˇ,πˇ,e0),πˇ1)−maxπˇ2∈ΠˇQˇ∗(Fˇ(μˇ,πˇ,e0),πˇ2)|p(de0)≤βsupp∈Bm,q0(p^ε0)∫E0maxπˇ1∈Πˇ|Qˇt(Fˇ(μˇ,πˇ,e0),πˇ1)−Qˇ∗(Fˇ(μˇ,πˇ,e0),πˇ1)|p(de0)≤β‖Δˇt‖Sˇ×Πˇ. aligned &| H Q_t( μ, π)- H Q^*( μ, π)|\\ & ≤β _p∈B^0_m,q( p_ ^0) _E^0 | _ π^1∈ Q_t( F( μ, π,e^0), π^1)- _ π^2∈ Q^*( F( μ, π,e^0), π^2) |p(de^0)\\ & ≤β _p∈B^0_m,q( p_ ^0) _E^0 _ π^1∈ | Q_t( F( μ, π,e^0), π^1)- Q^*( F( μ, π,e^0), π^1) |p(de^0)\\ & ≤β\| _t\|_ S× . aligned Combining this with Lemma 5.4 yields that for any t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , ℙ^0 P^0-a.s., (5.13) |ℙ^0[Fˇt(μˇ,πˇ)|Fˇt0]|=|ℙ^0[HˇQˇt(μˇ,πˇ)−HˇQˇ∗(μˇ,πˇ)|Fˇt0]|≤ℙ^0[|HˇQˇt(μˇ,πˇ)−HˇQˇ∗(μˇ,πˇ)||Fˇt0]≤β‖Δˇt‖Sˇ×Πˇ. aligned |E P^0[ F_t( μ, π)| F_t^0] |&= |E P^0[ H Q_t( μ, π)- H Q^*( μ, π)| F_t^0] |\\ & P^0 [| H Q_t( μ, π)- H Q^*( μ, π)| | F_t^0 ]≤β\| _t\|_ S× . aligned (Variance estimate of Fˇt F_t) Using (5.12) and Lemma 5.4, we have for any t≥0t≥ 0 and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× ℙ^0[|Fˇt(μˇ,πˇ)|2|Fˇt0]≤2(ℙ^0[|HˇQˇt(μˇ,πˇ)−HˇQˇ∗(μˇ,πˇ)|2|Fˇt0]+β2ℙ^0[|Zt+1,(μˇ,πˇ)|2|Fˇt0])≤2β2(‖Δˇt‖Sˇ×Πˇ2+24Qˇmax). aligned E P^0 [| F_t( μ, π)|^2 | F_t^0 ]&≤ 2 (E P^0 [| H Q_t( μ, π)- H Q^*( μ, π)|^2 | F_t^0 ]+β^2E P^0 [|Z_t+1,( μ, π)|^2 | F_t^0 ] )\\ &≤ 2β^2 (\| _t\|_ S× ^2+2^4 Q_max ). aligned Combining this with (5.13) yields that for any t≥0t≥ 0, ℙ^0 P^0-a.s., (5.14) ∥arℙ^0[Fˇt(⋅,⋅)|Fˇt0]∥Sˇ×Πˇ≤∥ℙ^0[Fˇt(⋅,⋅)|Fˇt0]∥Sˇ×Πˇ2+∥ℙ^0[|Fˇt(⋅,⋅)|2|Fˇt0]∥Sˇ×Πˇ≤β2(‖Δˇt‖Sˇ×Πˇ+25Qˇmax2). aligned \| P^0[ F_t(·,·)| F_t^0]\|_ S× &≤\|E P^0[ F_t(·,·)| F_t^0]\|_ S× ^2+\|E P^0[| F_t(·,·)|^2| F_t^0]\|_ S× \\ &≤β^2(\| _t\|_ S× +2^5 Q_max^2). aligned Therefore, all the conditions in Lemma 5.5 are satisfied. For the case of the asynchronous version, the learning rate in (2.6) is also deterministic, since the trajectory (μˇt,πˇt)t≥0⊆Sˇ×Πˇ( μ_t, π_t)_t≥ 0 S× used in its definition is pre-sampled. Moreover, under Assumption 2.12 (i), for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , the set T(μˇ,πˇ)T_( μ, π) in (2.5) satisfies |T(μˇ,πˇ)|=∞|T_( μ, π)|=∞. Thus, we may enumerate the times in T(μˇ,πˇ)T_( μ, π) as a strictly increasing sequence (tk)k≥0(t_k)_k≥ 0 such that ∑t=0∞αt,(μˇ,πˇ)=∑k=0∞αtk,(μˇ,πˇ)=∑k=0∞(k+1)−w=∞ _t=0^∞ _t,( μ, π)= _k=0^∞ _t_k,( μ, π)= _k=0^∞(k+1)^-w=∞ and ∑t=0∞αt,(μˇ,πˇ)2=∑k=0∞(k+1)−2w<∞ _t=0^∞ _t,( μ, π)^2= _k=0^∞(k+1)^-2w<∞. Moreover, the arguments establishing (5.12), (5.13), and (5.14) for the synchronous case apply directly to the asynchronous case. Consequently, all the conditions in Lemma 5.5 are satisfied, and the result now follows directly from applying the convergence result in Lemma 5.5. This completes the proof. ∎ 5.2. Proof of Theorem 2.17 We start by outlining the main ideas of the proof of Theorem 2.17 for the asynchronous version of the Q-learning algorithm in Framework 2.9 (i),(i). Conceptually, the analysis follows the approach in the literature on a finite-time iteration bound analysis for Q-learning (see, e.g., [25]). In context of our Q-learning algorithm, the process (Δˇt)t≥0( _t)_t≥ 0 defined in (5.9) is controlled epoch-wise. Each epoch accounts for the covering time TcovT_cov in Assumption 2.12 (i). The epochs are constructed so that (Δˇt)t≥0( _t)_t≥ 0 decays inductively over epochs in the following way. The process (Δˇt)t≥0( _t)_t≥ 0 is decomposed into deterministic and stochastic components. The deterministic component vanishes inductively across epochs, whereas the stochastic component is represented as a sum of ℙ^0 P^0-martingale difference terms characterized by (Zt+1,(⋅,⋅))t≥0(Z_t+1,(·,·))_t≥ 0 defined in (5.5). Since (Zt+1,(⋅,⋅))t≥0(Z_t+1,(·,·))_t≥ 0 is bounded and has conditional zero mean; see Lemma 5.4, Azuma’s inequality [3] (also introduced in Lemma 5.13) yields concentration bounds for the stochastic term. Consequently, by choosing the number of iterations T∗T^* of the order of a sufficiently large epoch, we obtain that for every T≥T∗T≥ T^*, ℙ^0(‖ΔˇT‖Sˇ×Πˇ=‖QˇT−Qˇ∗‖Sˇ×Πˇ≤ε^)≥1−δ^, P^0 (\| _T\|_ S× =\| Q_T- Q^*\|_ S× ≤ )≥ 1- δ, where ε^>0 >0 and δ^∈(0,1) δ∈(0,1) denotes the prescribed error and confidence levels, respectively. The final ingredient in the proof is the discretization error bound (i.e., C1εSˇ+C2εAˇC_1 _ S+C_2 _ A) for the optimal Q-function established in Lemma 4.10. The notions and lemmas introduced below are tailored to the asynchronous version, but extend to the synchronous version under Framework 2.9(i),(i) with only minor modifications. The synchronous case is briefly elaborated at the end of the proof. Definition 5.6. Let Assumption 2.12 (i) hold. Recall that w∈(12,1)w∈( 12,1) is the exponent of the asynchronous learning rates and (μˇt,πˇt)t≥0⊆Sˇ×Πˇ( μ_t, π_t)_t≥ 0 S× is the sampled trajectory in Framework 2.9 (i). Fix κˇ∈(0,1) κ∈(0,1) and let cˇ≥1 c≥ 1. (i) Set τ0:=0 _0:=0. For any n≥1n≥ 1 and any tˇ≥1 t≥ 1, define τn+1;tˇ:=τn;tˇ+⌈Tcovcˇκˇτn;tˇw⌉,with τ1;tˇ:=tˇ, _n+1; t:= _n; t+ T_cov c κ _n; t^w , with $ _1; t:= t$, where Tcov>1T_cov>1 is the covering time given in Assumption 2.12 (i), and tˇ t represents the initial epoch’s length. (i) For any 0≤t1<t20≤ t_1<t_2 and (μˇ,πˇ)∈Sˇ×Πˇ,( μ, π)∈ S× , define T(μˇ,πˇ)t1,t2:=t∈[t1,t2):(μˇ,πˇ)=(μˇt,πˇt)⊆T(μˇ,πˇ), T^t_1,t_2_( μ, π):=\t∈[t_1,t_2):( μ, π)=( μ_t, π_t)\ T_( μ, π), with the set T(μˇ,πˇ)T_( μ, π) defined in (2.5). (i) For any n≥1n≥ 1, define Dn+1:=(1−βˇ)nD1D_n+1:=(1- β)^nD_1, where D1:=2QˇmaxD_1:=2 Q_max and βˇ:=1−β2 β:= 1-β2. We first collect some elementary properties of the notions introduced in Definition 5.6 (i),(i) and the learning rates in Framework 2.9 (i). Lemma 5.7. Let Assumption 2.12 (i) hold. Then for any tˇ≥1 t≥ 1, the sequence (τn;tˇ)n≥0( _n; t)_n≥ 0 given in Definition 5.6 (i) satisfy, for every n≥0n≥ 0, (i) τn;tˇTcov≤⌈τn;tˇTcov⌉+⌊cˇκˇτn;tˇw⌋≤τn+1;tˇTcov+1. _n; tT_cov≤ _n; tT_cov + c κ _n; t^w ≤ _n+1; tT_cov+1. (i) τn+1;tˇ1−w≤tˇ1−w+n(1−w)(Tcovcˇκˇ+tˇ−w) _n+1; t^1-w≤ t^1-w+n(1-w)(T_cov c κ+ t^-w). Moreover, for every n≥1n≥ 1, t∈[τn+1;tˇ,τn+2;tˇ)t∈[ _n+1; t, _n+2; t), and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (i) |T(μˇ,πˇ)τn;tˇ,t|≥⌊cˇκˇτn;tˇw⌋|T _n; t,t_( μ, π)|≥ c κ _n; t^w . (iv) Let i∈T(μˇ,πˇ)τn;tˇ,ti∈ T _n; t,t_( μ, π) be the smallest element in the set. Then αi,(μˇ,πˇ)≤(⌊τn;tˇTcov⌋+1)−w _i,( μ, π)≤( _n; tT_cov +1)^-w. Proof. For (i), the inequality τn;tˇTcov≤⌈τn;tˇTcov⌉+⌊cˇκˇτn;tˇw⌋ _n; tT_cov≤ _n; tT_cov + c κ _n; t^w is obvious, while the other inequality follows from the definition of τn+1;tˇ _n+1; t in Definition 5.6 (i). Indeed, for any n≥0n≥ 0 ⌈τn;tˇTcov⌉+⌊cˇκˇτn;tˇw⌋≤τn;tˇ+Tcov⌊cˇκˇτn;tˇw⌋Tcov+1≤τn;tˇ+⌈Tcovcˇκˇτn;tˇw⌉Tcov+1=τn+1;tˇTcov+1. _n; tT_cov + c κ _n; t^w ≤ _n; t+T_cov c κ _n; t^w T_cov+1≤ _n; t+ T_cov c κ _n; t^w T_cov+1= _n+1; tT_cov+1. For (i), since by the concavity of the map ℝ+∋x→x1−w∈ℝ+R_+ x→ x^1-w _+, for any n≥0n≥ 0, τn+1;tˇ1−w−τn;tˇ1−w≤(τn;tˇ+Tcovcˇκˇτn;tˇw+1)1−w−τn;tˇ1−w≤(1−w)τn−w(Tcovcˇκˇτnw+1)≤(1−w)(Tcovcˇκˇ+τ1−w). aligned _n+1; t^1-w- _n; t^1-w&≤ ( _n; t+T_cov c κ _n; t^w+1 )^1-w- _n; t^1-w\\ &≤(1-w) _n^-w (T_cov c κ _n^w+1 )≤(1-w) (T_cov c κ+ _1^-w ). aligned Hence, the desired estimate follows by iterating this inequality over n≥0n≥ 0. For (i), by Assumption 2.12 (i), for every n≥1n≥ 1, t∈[τn+1,τn+2)t∈[ _n+1, _n+2), and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , |T(μˇ,πˇ)τn,t|≥|T(μˇ,πˇ)τn,τn+1|≥τn+1−τnTcov≥⌊cˇκˇτnw⌋.|T _n,t_( μ, π)|≥|T _n, _n+1_( μ, π)|≥ _n+1- _nT_cov≥ c κ _n^w . Last, for (iv), let n≥1n≥ 1, t∈[τn+1,τn+2)t∈[ _n+1, _n+2), and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . Since i∈T(μˇ,πˇ)τn,ti∈ T _n,t_( μ, π) satisfies i≥τni≥ _n, by Assumption 2.12 (i), it holds that Ni,(μˇ,πˇ)≥⌊τnTcov⌋N_i,( μ, π)≥ _nT_cov . Hence, by definition of the asynchronous learning rate in (2.6) the desired inequality holds. ∎ The following lemma establishes a relation between the epoch sequences corresponding to the initial epoch length and its increase. Lemma 5.8. Let Assumption 2.12 (i) hold. Let nˇ≥1 n≥ 1 be given. If the initial epoch length tˇ t satisfies tˇ≥max(2Tcovcˇκˇw(nˇ−1)log2)11−w,(2nˇ+12Tcovcˇκˇ)1w,1, t≥ \ ( 2T_ cov c κw( n-1) 2 ) 11-w, ( 2 n+12T_ cov c κ ) 1w,1 \, then it holds that τnˇ+2;tˇ−1≥τnˇ;tˇ+1 _ n+2; t-1≥ _ n; t+1. Proof. For notational simplicity, set Cˇ:=Tcovcˇ/κˇ C:=T_ cov c/ κ, and write, for every n≥1n≥ 1, dn:=τn;tˇ+1−τn;tˇd_n:= _n; t+1- _n; t Then, it holds that for every n≥1n≥ 1 (5.15) dn+1=τn;tˇ+1+⌈Cˇτn;tˇ+1w⌉−(τn;tˇ+⌈Cˇτn;tˇw⌉)≤dn+Cˇ(τn;tˇ+1w−τn;tˇw)+1≤dn(1+Cˇwτn;tˇw−1)+1, aligned d_n+1= _n; t+1+ C _n; t+1^w -( _n; t+ C _n; t^w )&≤ d_n+ C( _n; t+1^w- _n; t^w)+1\\ &≤ d_n(1+ Cw _n; t^w-1)+1, aligned where the last inequality follows from the concavity of the map ℝ+∋x↦xw∈ℝ+R_+ x x^w _+. Since d1=1d_1=1, iterating the estimate in (5.15) gives, for every 1≤n≤nˇ1≤ n≤ n, (5.16) dn≤n(1+Cˇwtˇw−1)n−1≤nexp(Cˇw(n−1)tˇw−1)≤2n, d_n≤ n (1+ Cw t^w-1 )^n-1≤ n ( Cw(n-1) t^w-1 )≤ 2n, where the last inequality follows from the condition on tˇ t, namely, tˇ≥(2Cˇw(nˇ−1)log2)11−w. t≥( 2 Cw( n-1) 2) 11-w. On the other hand, (5.17) τnˇ+2;tˇ−1−τnˇ;tˇ=⌈Cˇτnˇ;tˇw⌉+⌈Cˇτnˇ+1;tˇw⌉−1≥2Cˇtˇw−1≥2nˇ, aligned _ n+2; t-1- _ n; t&= C _ n; t^w + C _ n+1; t^w -1\\ &≥ 2 C t^w-1≥ 2 n, aligned where the last inequality follows from the condition on tˇ t, namely, tˇ≥(2nˇ+12Cˇ)1w t≥( 2 n+12 C) 1w. Combining (5.16) and (5.17) leads to τnˇ+2;tˇ−1≥τnˇ;tˇ+2nˇ≥τnˇ;tˇ+dnˇ=τn~;tˇ+1. _ n+2; t-1≥ _ n; t+2 n≥ _ n; t+d_ n= _ n; t+1. This proves the claim. ∎ In what follows, we often make use of the following elementary inequalities. Lemma 5.9. The following hold: (i) For any w~∈(0,1) w∈(0,1) and t1,t2∈ℕt_1,t_2 with t2>t1t_2>t_1, ∏i=t1t2(1−(i+1)−w~)≤exp(−t2−t1(t2+1)w~). _i=t_1^t_2(1-(i+1)^- w)≤ (- t_2-t_1(t_2+1) w). (i) For any a>0a>0 satisfying 2aloga>12a a>1, and any A>2alogaA>2a a, Aexp(−2Aa)≤exp(−Aa).A (- 2Aa)≤ (- Aa). Proof. Since 1−x≤ex1-x≤ e^x for all x∈[0,1]x∈[0,1], we obtain (i), namely, ∏i=t1t2(1−(i+1)−w~)≤exp(−∑i=t1t2(i+1)−w~)≤exp(−t2−t1(t2+1)w~), _i=t_1^t_2(1-(i+1)^- w)≤ (- _i=t_1^t_2(i+1)^- w )≤ (- t_2-t_1(t_2+1) w ), where the last inequality holds because (i+1)−w~≥(t2+1)w~(i+1)^- w≥(t_2+1) w for all i=t1,…,t2i=t_1,…,t_2. For (i), let a>0a>0 satisfy 2aloga>12a a>1. For each A∈(2aloga,+∞)A∈(2a a,+∞), define ϕ(A):=Aa−logAφ(A):= Aa- A, and show that ϕ≥0φ≥ 0 on the interval. Since ϕ′(A)=1a−1A=A−aA,φ (A)= 1a- 1A= A-aaA, ϕφ attains the minimum at A∗=maxa,2aloga.A^*= \a,2a a\. Thus it suffices to verify that ϕ(A∗)≥0φ(A^*)≥ 0. Suppose that A∗=aA^*=a. Then, since ϕ(a)=1−logaφ(a)=1- a and 2aloga≤a2a a≤ a, we have ϕ(A∗)≥12>0.φ(A^*)≥ 12>0. Otherwise (i.e., A∗=2alogaA^*=2a a), since ϕ(A∗)=log(a2loga),φ(A^*)= ( a2 a), it suffices to show a≥2loga≥ 2 a. Define ψ(x):=x−2logxψ(x):=x-2 x for x>0x>0. Then ψ′(x)=1−2x=x−2x,ψ (x)=1- 2x= x-2x, so ψ attains the minimum at x=2x=2. Since ψ(2)=2−2log2>0,ψ(2)=2-2 2>0, we conclude ψ(x)>0ψ(x)>0 for all x>0x>0, and thus a>2loga>2 a. Therefore ϕ(A)≥0φ(A)≥ 0 for all A>2alogaA>2a a, which implies Aexp(−2Aa)≤exp(−Aa).A (- 2Aa)≤ (- Aa). ∎ Lemma 5.10. Suppose that Assumptions 2.2 (i),(i) and 2.12 (i) are satisfied. Let (Zt+1,(⋅,⋅))t≥0(Z_t+1,(·,·))_t≥ 0 and (Δˇt)t≥0( _t)_t≥ 0 be given in (5.5) and (5.9), respectively. Let tˇ≥1 t≥ 1 be given. Let (τn;tˇ)n≥0( _n; t)_n≥ 0 and (Dn)n≥1(D_n)_n≥ 1 be given in Definition 5.6. Moreover, for any n≥1n≥ 1, let (Wt;n,Yt;n)t≥τn;tˇ(W_t;n,Y_t;n)_t≥ _n; t be sequences of mappings defined for every t≥τn;tˇt≥ _n; t and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× by (5.18) Wt+1;n(μˇ,πˇ):=(1−αt,(μˇ,πˇ))Wt;n(μˇ,πˇ)+αt,(μˇ,πˇ)βZt+1,(μˇ,πˇ),Yt+1;n(μˇ,πˇ):=(1−αt,(μˇ,πˇ))Yt;n(μˇ,πˇ)+αt,(μˇ,πˇ)βDn, aligned &W_t+1;n( μ, π):=(1- _t,( μ, π))W_t;n( μ, π)+ _t,( μ, π)β Z_t+1,( μ, π),\\ &Y_t+1;n( μ, π):=(1- _t,( μ, π))Y_t;n( μ, π)+ _t,( μ, π)β D_n, aligned with Wτn;tˇ;n(μˇ,πˇ):=0W_ _n; t;n( μ, π):=0 and Yτn;tˇ;n(μˇ,πˇ):=DnY_ _n; t;n( μ, π):=D_n. If ‖Δˇt‖Sˇ×Πˇ≤Dn\| _t\|_ S× ≤ D_n holds for all t∈[τn;tˇ,τn+2;tˇ)t∈[ _n; t, _n+2; t), then we have for every t≥τn;tˇt≥ _n; t and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× that (5.19) −Yt;n(μˇ,πˇ)+Wt;n(μˇ,πˇ)≤Δˇt(μˇ,πˇ)≤Yt;n(μˇ,πˇ)+Wt;n(μˇ,πˇ). -Y_t;n( μ, π)+W_t;n( μ, π)≤ _t( μ, π)≤ Y_t;n( μ, π)+W_t;n( μ, π). Proof. The proof uses an induction over t≥τn;tˇt≥ _n; t. The estimate (5.19) holds at t=τn;tˇt= _n; t because Wτn;tˇ;n(μˇ,πˇ)=0W_ _n; t;n( μ, π)=0, Yτn;tˇ;n(μˇ,πˇ)=DnY_ _n; t;n( μ, π)=D_n and ‖Δˇτn;tˇ‖Sˇ×Πˇ≤Dn\| _ _n; t\|_ S× ≤ D_n. Assume that the estimate holds for some t≥τn;tˇt≥ _n; t. Let (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× be given. Since HˇQˇ∗=Qˇ∗ H Q^*= Q^* (see Remark 5.2), by the assumption that ‖Δˇt‖Sˇ×Πˇ≤Dn\| _t\|_ S× ≤ D_n, the upper bound in (5.19), and the estimate in (5.12), we have Δˇt+1(μˇ,πˇ) _t+1( μ, π) =(1−αt,(μˇ,πˇ))Δˇt(μˇ,πˇ)+αt,(μˇ,πˇ)(HˇQˇt(μˇ,πˇ)−HˇQˇ∗(μˇ,πˇ)+βZt+1,(μˇ,πˇ)) =(1- _t,( μ, π)) _t( μ, π)+ _t,( μ, π) ( H Q_t( μ, π)- H Q^*( μ, π)+β Z_t+1,( μ, π) ) ≤(1−αt,(μˇ,πˇ))Yt;n(μˇ,πˇ)+Wt+1;n(μˇ,πˇ)+αt,(μˇ,πˇ)(HˇQˇt(μˇ,πˇ)−HˇQˇ∗(μˇ,πˇ)) ≤(1- _t,( μ, π))Y_t;n( μ, π)+W_t+1;n( μ, π)+ _t,( μ, π)( H Q_t( μ, π)- H Q^*( μ, π)) ≤(1−αt,(μˇ,πˇ))Yt;n(μˇ,πˇ)+Wt+1;n(μˇ,πˇ)+αt,(μˇ,πˇ)β‖Δˇt‖Sˇ×Πˇ ≤(1- _t,( μ, π))Y_t;n( μ, π)+W_t+1;n( μ, π)+ _t,( μ, π)β\| _t\|_ S× ≤Yt+1;n(μˇ,πˇ)+Wt+1;n(μˇ,πˇ). ≤ Y_t+1;n( μ, π)+W_t+1;n( μ, π). Using similar arguments and the lower bound in (5.19), we also have Δˇt+1(μˇ,πˇ)≥Wt+1;n(μˇ,πˇ)−(1−αt,(μˇ,πˇ))Yt;n(μˇ,πˇ)+αt,(μˇ,πˇ)(HˇQˇt(μˇ,πˇ)−HˇQˇ∗(μˇ,πˇ))≥Wt+1;n(μˇ,πˇ)−(1−αt,(μˇ,πˇ))Yt;n(μˇ,πˇ)−αt,(μˇ,πˇ)β‖Δˇt‖Sˇ×Πˇ≥Wt+1;n(μˇ,πˇ)−Yt+1;n(μˇ,πˇ). aligned _t+1( μ, π)&≥ W_t+1;n( μ, π)-(1- _t,( μ, π))Y_t;n( μ, π)+ _t,( μ, π)( H Q_t( μ, π)- H Q^*( μ, π))\\ &≥ W_t+1;n( μ, π)-(1- _t,( μ, π))Y_t;n( μ, π)- _t,( μ, π)β\| _t\|_ S× \\ &≥ W_t+1;n( μ, π)-Y_t+1;n( μ, π). aligned Therefore, by the induction hypothesis, the desired bound holds at time t+1t+1. ∎ Lemma 5.11. Suppose that Assumptions 2.2 (i),(i) and 2.12 are satisfied. Let δˇ∈(0,e−2) δ∈(0,e-2) be given. Moreover, assume that the initial epoch’s length tˇ≥1 t≥ 1 and cˇ≥1 c≥ 1 in Definition 5.6 satisfy tˇ≥maxtˇ1∗,⌈Tcov(Tcov−1)−1⌉andcˇ≥maxcˇ1∗, 1, t≥ \ t_1^*, T_cov(T_cov-1)^-1 \ and c≥ \ c_1^*,\,1\, where (5.20) tˇ1∗:=Tcov⌈21w(1−log(2+δˇ))−1w⌉,cˇ1∗:=log(2+δˇ)+2(Tcov/tˇ1∗)w1−(log(2+δˇ)+2(Tcov/tˇ1∗)w). t_1^*:=T_cov 2 1w(1- (2+ δ))^- 1w , c_1^*:= (2+ δ)+2(T_cov/ t_1^*)^w1-( (2+ δ)+2(T_cov/ t_1^*)^w). Furthermore, for any n≥1n≥ 1, let (Yt,n)t≥τn;tˇ(Y_t,n)_t≥ _n; t be given in (5.18). If ‖Δˇt‖Sˇ×Πˇ≤Dn\| _t\|_ S× ≤ D_n holds for all t∈τn;tˇ,…,τn+2;tˇ−1t∈\ _n; t,…, _n+2; t-1\, then for every t≥τn+1;tˇt≥ _n+1; t (5.21) ‖Yt;n‖Sˇ×Πˇ≤(β+2βˇ(2+δˇ)−1)Dn. \|Y_t;n\|_ S× ≤(β+2 β(2+ δ)^-1)D_n. Proof. Note that (Yt;n)t≥τn;tˇ(Y_t;n)_t≥ _n; t can be rewritten for every t>τn;tˇt> _n; t and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× by (5.22) Yt;n(μˇ,πˇ)=Dn(β+2βˇρt;n(μˇ,πˇ)),where ρt;n(μˇ,πˇ):=∏i∈T(μˇ,πˇ)τn;tˇ,t(1−αi,(μˇ,πˇ)), Y_t;n( μ, π)=D_n(β+2 β _t;n( μ, π)), where _t;n( μ, π):= _i∈ T _n; t,t_( μ, π)(1- _i,( μ, π)), with setting ρτn;tˇ;n(μˇ,πˇ):=(1−β)Dn _ _n; t;n( μ, π):=(1-β)D_n and recalling that Yτn;tˇ;n=DnY_ _n; t;n=D_n. Then it holds for every t≥τn+1;tˇt≥ _n+1; t and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× that (5.23) ρt;n(μˇ,πˇ)≤∏i=⌈τn;tˇTcov⌉⌈τn;tˇTcov⌉+⌊cˇκˇτn;tˇw⌋−1(1−(i+1)−w)≤exp(I),where I:=−(⌊cˇκˇτn;tˇw⌋−1)(⌈τn;tˇTcov⌉+⌊cˇκˇτn;tˇw⌋)−w. aligned & _t;n( μ, π)≤ _i= _n; tT_cov _n; tT_cov + c κ _n; t^w -1(1-(i+1)^-w)≤ (I),\\ & where I:=- ( c κ _n; t^w -1 ) ( _n; tT_cov + c κ _n; t^w )^-w. aligned Here the first inequality follows from Lemma 5.7 (i), (iv) and the fact that t≥τn+1;tˇt≥ _n+1; t, whereas the second inequality follows from Lemma 5.9 (i). Therefore, it suffices to prove that I≤−log(2+δˇ)I≤- (2+ δ). By Lemma 5.7 (i), we have (5.24) I≤−(cˇκˇτn;tˇw−2)(⌈τn;tˇTcov⌉+⌊cˇκˇτn;tˇw⌋)−w≤−cˇκˇ(τn+1;tˇTcovτn;tˇ+1τn;tˇ)−w+2(Tcovτn;tˇ)w:=I. aligned I&≤- ( c κ _n; t^w-2 ) ( _n; tT_cov + c κ _n; t^w )^-w\\ &≤- c κ ( _n+1; tT_cov _n; t+ 1 _n; t )^-w+2 ( T_cov _n; t )^w:=I. aligned Moreover, it holds that τn+1;tˇTcovτn;tˇ+1τn;tˇ≤τn;tˇ+Tcovcˇκˇτn;tˇw+1Tcovτn;tˇ+1τn;tˇ≤1Tcov+cˇκˇ+1tˇ≤cˇκˇ+1, _n+1; tT_cov _n; t+ 1 _n; t≤ _n; t+T_cov c κ _n; t^w+1T_cov _n; t+ 1 _n; t≤ 1T_cov+ c κ+ 1 t≤ c κ+1, where the last inequality follows from the assumption that tˇ≥Tcov(Tcov−1)−1 t≥T_cov(T_cov-1)^-1. From this and the facts that τn;tˇ≥tˇ _n; t≥ t and kˇ,w<1 k,w<1, we have (5.25) I≤−cˇκˇ(cˇκˇ+1)−w+2(Tcovtˇ)w≤−cˇcˇ+1+2(Tcovtˇ)w≤−log(2+δˇ), ≤- c κ ( c κ+1 )^-w+2 ( T_cov t )^w≤ - c c+1+2 ( T_cov t )^w≤- (2+ δ), where the last inequality holds because tˇ≥tˇ1∗ t≥ t_1^* and cˇ≥cˇ1∗ c≥ c_1^* (see (5.20)), together with the fact that log(2+δˇ)<1 (2+ δ)<1 (because of δˇ∈(0,e−2) δ∈(0,e-2)). Combining (5.24) and (5.25) yields that I≤−log(2+δˇ)I≤- (2+ δ), as claimed. ∎ Next, we define, for every tˇ≥1 t≥ 1, n≥1n≥ 1, t∈τn+1;tˇ,…,τn+3;tˇ−1t∈\ _n+1; t,…, _n+3; t-1\, l∈−1,0,⋯,t−1−τn;tˇl∈\-1,0,·s,t-1- _n; t\, and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , (5.26) Xt;nl(μˇ,πˇ):=β∑i=τn;tˇτn;tˇ+lαi,(μˇ,πˇ)(∏j=i+1t−1(1−αj,(μˇ,πˇ)))Zi+1;(μˇ,πˇ),l≥0, X_t;n^l( μ, π):=β _i= _n; t _n; t+l _i,( μ, π) ( _j=i+1^t-1(1- _j,( μ, π)) )Z_i+1;( μ, π), $l≥ 0$, with Xt;n−1(μˇ,πˇ):=0X_t;n^-1( μ, π):=0. Then the sequence (Wt;n)t=τn+1;tˇτn+3;tˇ−1(W_t;n)_t= _n+1; t _n+3; t-1 given in (5.18) can be rewritten for every t∈τn+1;tˇ,…,τn+3;tˇ−1t∈\ _n+1; t,…, _n+3; t-1\ and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× by (5.27) Wt;n(μˇ,πˇ)=Xt;nt−1−τn;tˇ(μˇ,πˇ)=∑l=0t−1−τn;tˇ(Xt;nl(μˇ,πˇ)−Xt;nl−1(μˇ,πˇ)). W_t;n( μ, π)=X_t;n^t-1- _n; t( μ, π)= _l=0^t-1- _n; t (X_t;n^l( μ, π)-X_t;n^l-1( μ, π) ). Lemma 5.12. Suppose that Assumptions 2.2 (i),(i) and 2.12 are satisfied. Recall the probability space (Ω0,F0,ℙ^0)( ^0,F^0, P^0) in Framework 2.9 and the filtration ˇ0 F^0 in (5.7). Then for every tˇ≥1 t≥ 1, n≥1n≥ 1, t∈τn+1;tˇ,…,τn+3;tˇ−1t∈\ _n+1; t,…, _n+3; t-1\, (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , the following hold. (i) For every k∈τn;tˇ,…,tk∈\ _n; t,…,t\, Xt;nk−1−τn;tˇ(μˇ,πˇ)X_t;n^k-1- _n; t( μ, π) in (5.26) is ℱˇk0 F_k^0-measurable. (i) (Xt;nk−1−τn;tˇ(μˇ,πˇ))k=τn;tˇt(X_t;n^k-1- _n; t( μ, π))_k= _n; t^t is a ℙ^0 P^0-martingale w.r.t. (ℱˇk0)k=τn;tˇt( F_k^0)_k= _n; t^t. (i) For every k∈τn;tˇ,…,t−1k∈\ _n; t,…,t-1\, |Xt;nk−τn;tˇ(μˇ,πˇ)−Xt;nk−1−τn;tˇ(μˇ,πˇ)|≤4βQˇmax(Tcovτn;tˇ)w|X_t;n^k- _n; t( μ, π)-X_t;n^k-1- _n; t( μ, π)|≤ 4β Q_max( T_cov _n; t)^w. Proof. Let tˇ≥1 t≥ 1, n≥1n≥ 1, t∈[τn+1;tˇ,τn+3;tˇ)t∈[ _n+1; t, _n+3; t) and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× . Indeed, since (αt,(μˇ,πˇ))t≥0( _t,( μ, π))_t≥ 0 are deterministic for any (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , we have by Remark 5.3 (i) that for any k=τn;tˇ+1,⋯,t,k= _n; t+1,·s,t, Xt;nk−1−τn;tˇ(μˇ,πˇ)=β∑i=τn;tˇk−1αi,(μˇ,πˇ)(∏j=i+1t−1(1−αj,(μˇ,πˇ)))Zi+1;(μˇ,πˇ)X_t;n^k-1- _n; t( μ, π)=β _i= _n; t^k-1 _i,( μ, π) ( _j=i+1^t-1(1- _j,( μ, π)) )Z_i+1;( μ, π) is Fˇk0 F_k^0-measurable, while Xt;n−1(μˇ,πˇ)=0X_t;n^-1( μ, π)=0 is Fˇτn;tˇ0 F_ _n; t^0-measurable. Thus, Part (i) holds. Parts (i) and (i) follow from Lemma 5.4. Indeed, for any k∈τn;tˇ,…,t−1k∈\ _n; t,…,t-1\, ℙ^0 P^0-a.s., ℙ^0[Xt;nk−τn;tˇ(μˇ,πˇ)−Xt;nk−1−τn;tˇ(μˇ,πˇ)|Fˇk0] P^0[X_t;n^k- _n; t( μ, π)-X_t;n^k-1- _n; t( μ, π)| F_k^0] =βαk,(μˇ,πˇ)∏j=k+1t−1(1−αj,(μˇ,πˇ))ℙ^0[Zk+1;(μˇ,πˇ)|Fˇk0]=0. =β _k,( μ, π) _j=k+1^t-1(1- _j,( μ, π))E P^0[Z_k+1;( μ, π)| F^0_k]=0. Moreover, for any k∈τn;tˇ,…,t−1k∈\ _n; t,…,t-1\, |Xt;nk−τn;tˇ(μˇ,πˇ)−Xt;nk−1−τn;tˇ(μˇ,πˇ)|=βαk,(μˇ,πˇ)∏j=k+1t−1(1−αj,(μˇ,πˇ))|Zk+1;(μˇ,πˇ)|≤4βQˇmaxαk,(μˇ,πˇ)≤4βQˇmax(Tcov/τn;tˇ)w, aligned |X_t;n^k- _n; t( μ, π)-X_t;n^k-1- _n; t( μ, π) |&=β _k,( μ, π) _j=k+1^t-1(1- _j,( μ, π)) |Z_k+1;( μ, π) |\\ &≤ 4β Q_max _k,( μ, π)≤ 4β Q_max(T_cov/ _n; t)^w, aligned where the last inequality holds because N(μˇ,πˇ)k≥⌊τn;tˇTcov⌋≥τn;tˇTcov−1N_( μ, π)^k≥ _n; tT_cov ≥ _n; tT_cov-1 (by the covering time condition in Assumption 2.12 (i); see also (2.6) for definition of the asynchronous learning rates). ∎ The following lemma states Azuma’s inequality [3] (see, e.g., Exercise 9.2.4 in [43]), which will be used in the subsequent lemma. Lemma 5.13. If (Mn)n≥0(M_n)_n≥ 0 is a martingale with M0=0M_0=0 on a filtered probability space (Ω~,F~,~,ℙ~)( , F, F, P) and there exists a sequence (cn)n≥1⊆[0,∞)(c_n)_n≥ 1 [0,∞) such that |Mn−Mn−1|≤cn|M_n-M_n-1|≤ c_n ℙ~ P-a.s. for all n≥1n≥ 1, then Azuma’s inequality holds: ℙ~[|Mn|≥λ]≤2exp(−λ22∑k=1nck2)for all λ≥0. P[|M_n|≥λ]≤ 2 (- λ^22 _k=1^nc_k^2 ) for all $λ≥ 0$. Lemma 5.14. Suppose that Assumptions 2.2 (i),(i) and 2.12 are satisfied. Recall the probability space (Ω0,F0,ℙ^0)( ^0,F^0, P^0) in Framework 2.9 and the filtration ˇ0 F^0 in (5.7). Then, for any tˇ≥1 t≥ 1, n≥1n≥ 1, t∈τn+1;tˇ,…,τn+3;tˇ−1t∈\ _n+1; t,…, _n+3; t-1\, and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× , the random variable Wt;n(μˇ,πˇ)W_t;n( μ, π) in (5.18) satisfies ℙ^0(|Wt;n(μˇ,πˇ)|≥λ) P^0(|W_t;n( μ, π)|≥λ) ≤2exp(−λ2τnw25C3(βQˇmaxTcovw)2),for all λ≥0, ≤ 2 (- λ^2 _n^w2^5C_3(β Q_maxT_cov^w)^2 ), for all $λ≥ 0$, where C3:=C(cˇ,κˇ,w,Tcov):=Tcovcˇκˇ(7+5(Tcovcˇκˇ)w+(Tcovcˇκˇ)2w)+3C_3:=C_( c, κ,w,T_cov):=T_cov c κ(7+5(T_cov c κ)^w+(T_cov c κ)^2w)+3. Proof. Let tˇ≥1 t≥ 1, n≥1n≥ 1, t∈τn+1;tˇ,…,τn+3;tˇ−1t∈\ _n+1; t,…, _n+3; t-1\, and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× be given. Note that Wt;n(μˇ,πˇ)=Xt;nt−1−τn;tˇ(μˇ,πˇ)W_t;n( μ, π)=X_t;n^t-1- _n; t( μ, π); see (5.27). From this and Lemma 5.12, we apply Azuma’s inequality (see Lemma 5.13) to (Xt;nk−1−τn;tˇ(μˇ,πˇ))k=τn;tˇt(X_t;n^k-1- _n; t( μ, π))_k= _n; t^t to have for all λ≥0λ≥ 0 ℙ^0(|Wt;n(μˇ,πˇ)|≥λ)≤2exp(−λ22(t−τn;tˇ)(4βQˇmax(Tcovτn;tˇ)w)2)≤2exp(−λ22(τn+3;tˇ−τn;tˇ)(4βQˇmax(Tcovτn;tˇ)w)2). aligned P^0(|W_t;n( μ, π)|≥λ)&≤ 2 (- λ^22(t- _n; t)(4β Q_max( T_cov _n; t)^w)^2 )\\ &≤ 2 (- λ^22( _n+3; t- _n; t)(4β Q_max( T_cov _n; t)^w)^2 ). aligned Therefore, it suffices to show that τn+3;tˇ−τn;tˇ≤C3τn;tˇw. _n+3; t- _n; t≤ C_3 _n; t^w. From the inequality that (a+b+c)w≤aw+bw+cw(a+b+c)^w≤ a^w+b^w+c^w for all a,b,c≥0a,b,c≥ 0 (as w<1w<1), we have (5.28) τn+1;tˇw≤(τn;tˇ+1+Tcovcˇκˇτn;tˇ)w≤τn;tˇw+1+(Tcovcˇκˇτn;tˇ)w≤C^3τn;tˇw, _n+1; t^w≤ ( _n; t+1+T_cov c κ _n; t )^w≤ _n; t^w+1+ (T_cov c κ _n; t )^w≤ C_3 _n; t^w, where C^3:=2+(Tcovcˇκˇ)w>0 C_3:=2+(T_cov c κ)^w>0. Similarly, we have τn+2;tˇw≤C^3τn+1;tˇw≤C^32τn;tˇw _n+2; t^w≤ C_3 _n+1; t^w≤ C_3^2 _n; t^w. Thus, we have τn+3;tˇ−τn;tˇ≤Tcovcˇκˇ(τn+2;tˇw+τn+1;tˇw+τn;tˇw)+3≤Tcovcˇκˇ(C^32+C^3+1)τn;tˇw+3≤C3τn;tˇw, _n+3; t- _n; t≤ T_cov c κ( _n+2; t^w+ _n+1; t^w+ _n; t^w)+3≤ T_cov c κ( C_3^2+ C_3+1) _n; t^w+3≤ C_3 _n; t^w, as claimed. This completes the proof. ∎ Lemma 5.15. Suppose that Assumptions 2.2 (i),(i) and 2.12 are satisfied. Recall D1=2QˇmaxD_1=2 Q_max (see Definition 5.6 (i)) and let D¯∈(0,D1] D∈(0,D_1] be such that (5.29) 2a(D¯)log(a(D¯))>1,where a(D¯):=a(cˇ,κˇ,δˇ,w,Tcov,β)(D¯):=26C3(βQˇmaxTcovw)2(δˇ(2+δˇ)−1βˇD¯)2>0, 2a( D) (a( D))>1, where \;a( D):=a_( c, κ, δ,w,T_cov,β)( D):= 2^6C_3(β Q_maxT_cov^w)^2( δ(2+ δ)^-1 β D)^2>0, with δˇ∈(0,e−2) δ∈(0,e-2) and C3>0C_3>0 given in Lemma 5.11 and Lemma 5.14, respectively. Moreover, assume that the initial epoch’s length tˇ t in Definition 5.6 satisfies tˇ≥⌈(2a(D¯)log(a(D¯)))1w⌉. t≥ (2a( D) (a( D)) ) 1w . Then for any n¯≥1 n≥ 1 such that Dn¯≥D¯D_ n≥ D, the following holds: ℙ^0(⋂n=1n¯⋂t=τn+1;tˇτn+3;tˇ−1⋂(μˇ,πˇ)∈Sˇ×Πˇ|Wt;n(μˇ,πˇ)|<δˇ(2+δˇ)−1βˇDn)≥1−2|Sˇ||Aˇ||Sˇ|C3n¯exp(tˇw/a(D¯)). aligned P^0 ( _n=1 n _t= _n+1; t _n+3; t-1 _( μ, π)∈ S× \|W_t;n( μ, π)|< δ(2+ δ)^-1 βD_n \ )≥ 1- 2| S|| A|^| S|C_3 n ( t^w/a( D)). aligned Proof. Let n¯∈ℕ n be such that Dn¯≥D¯D_ n≥ D. Then we have by Lemma 5.14 that ℙ^0(⋂n=1n¯⋂t=τn+1;tˇτn+3;tˇ−1⋂(μˇ,πˇ)∈Sˇ×Πˇ|Wt;n(μˇ,πˇ)|<δˇ(2+δˇ)−1βˇDn)≥1−∑n=1n¯∑t=τn+1;tˇτn+3;tˇ−1∑(μˇ,πˇ)∈Sˇ×Πˇℙ^0(|Wt;n(μˇ,πˇ)|≥δˇ(2+δˇ)−1βˇDn)≥1−2|Sˇ||Πˇ|∑n=1n¯(Tcovcˇκˇ(τn+2;tˇw+τn+1;tˇw)+2)exp(−2τn;tˇw/a(D¯))=:I, aligned & P^0 ( _n=1 n _t= _n+1; t _n+3; t-1 _( μ, π)∈ S× \|W_t;n( μ, π)|< δ(2+ δ)^-1 βD_n \ )\\ & ≥ 1- _n=1 n _t= _n+1; t _n+3; t-1 _( μ, π)∈ S× P^0(|W_t;n( μ, π)|≥ δ(2+ δ)^-1 βD_n)\\ & ≥ 1-2| S|| | _n=1 n (T_cov c κ( _n+2; t^w+ _n+1; t^w)+2 ) (-2 _n; t^w/a( D))=:I, aligned where the last inequality holds because Dn≥D¯D_n≥ D for all 0≤n≤n¯0≤ n≤ n. Moreover, using the estimate in (5.28) and the constant C3>0C_3>0 in Lemma 5.14, we have I≥1−2|Sˇ||Πˇ|C3∑n=1n¯τn;tˇwexp(−2τn;tˇw/a(D¯))=:I. ≥ 1-2| S|| |C_3 _n=1 n _n; t^w (-2 _n; t^w/a( D))=:I. Moreover, since 2a(D¯)log(a(D¯))>12a( D) (a( D))>1 and tˇ≥⌈(2a(D¯)log(a(D¯)))1w⌉ t≥ (2a( D) (a( D))) 1w by assumption, we apply Lemma 5.9 (i) to have for every n=1,⋯,n¯n=1,·s, n, τn;tˇwexp(−2τn;tˇw/a(D¯))≤exp(−τn;tˇw/a(D¯))≤exp(−tˇw/a(D¯)). _n; t^w (-2 _n; t^w/a( D))≤ (- _n; t^w/a( D))≤ (- t^w/a( D)). Thus, we conclude the proof by noting that |Πˇ|=|Aˇ||Sˇ|| |=| A|^| S|. ∎ Finally, we present the proof of the finite-time iteration bound analysis for Q-learning algorithm. Proof of Theorem 2.17. We first consider the asynchronous version of the Q-learning algorithm in Framework 2.9 (i),(i). The proof consists of four steps, which rely on the following preliminary settings. Let ε^>0 >0 and δ^∈(0,1) δ∈(0,1) be given. We first set (5.30) n∗:=max⌈βˇ−1log(2Qˇmaxε^−1)⌉,1. n^*:= \ β^-1 (2 Q_max ^-1) ,1\. Recalling tˇ1∗≥1 t_1^*≥ 1 and cˇ1∗>0 c_1^*>0 introduced in (5.20), we then define (5.31) cˇ:=maxcˇ1∗,1. c:= \ c_1^*,1\. Moreover, we define (5.32) tˇ2∗:=max⌈(2Tcovcˇκˇw(n∗−1)log2)11−w⌉,⌈(2n∗+12Tcovcˇκˇ)1w⌉,1. t^*_2:= \ ( 2T_ cov c κw(n^*-1) 2 ) 11-w , ( 2n^*+12T_ cov c κ ) 1w ,1 \. Then by Lemma 5.8, we have for any t≥tˇ2∗t≥ t_2^* (5.33) τn∗+2;tˇ−1≥τn∗;tˇ+1. _n^*+2; t-1≥ _n^*; t+1. In what follows, we construct the (least) initial epoch length tˇ∗≥1 t^*≥ 1 such that all conditions imposed in Lemmas 5.10, 5.11, and 5.15 hold, while (5.33) holds for all tˇ≥tˇ∗ t≥ t^*. To this end, we let σ∗∈(0,1)σ^*∈(0,1) be so that (5.34) Dn∗<ε^,Dn∗≥σ∗ε^,and2a(σ∗ε^)log(a(σ∗ε^))>1, D_n^*< , D_n^*≥σ^* , and 2a(σ^* ) (a(σ^* ))>1, where a(σ∗ε^)>0a(σ^* )>0 is defined as in (5.29) (with replacing D¯ D by σ∗ε^σ^* therein), we define tˇ∗≥1 t^*≥ 1 by (5.35) tˇ∗:=maxtˇ1∗,⌈Tcov(Tcov−1)−1⌉,tˇ2∗,tˇ3∗,tˇ4∗, t^*:= \ t_1^*, T_cov(T_cov-1)^-1 , t_2^*, t_3^*, t_4^*\, where tˇ1∗ t_1^* and tˇ2∗ t_2^* are given in (5.20) and (5.32), respectively, tˇ3∗ t_3^* and tˇ4∗ t_4^* are given by (5.36) tˇ3∗:=⌈(2a(σ∗ε^)log(a(σ∗ε^)))1w⌉,tˇ4∗:=⌈(a(σ∗ε^)log(2|Sˇ||Aˇ||Sˇ|C3n∗δ^))1w⌉, aligned & t_3^*:= (2a(σ^* ) (a(σ^* )) ) 1w ,\\ & t_4^*:= (a(σ^* ) ( 2| S|| A|^| S|C_3n^* δ ) ) 1w , aligned with the constant C3>0C_3>0 given in Lemma 5.14, which depends on the constant cˇ≥1 c≥ 1 in (5.31). Last, define, for every tˇ≥tˇ∗ t≥ t^* and k≥1k≥ 1, Ik(tˇ):=⋂t=τk+1;tˇτk+3;tˇ−1‖Δˇt‖Sˇ×Πˇ<Dk+1,Jk(tˇ):=⋂t=τk+1;tˇτk+3;tˇ−1⋂(μˇ,πˇ)∈Sˇ×Πˇ|Wt;k(μˇ,πˇ)|≤δˇ(2+δˇ)−1βˇDk. aligned I_k( t)&:= _t= _k+1; t _k+3; t-1 \\| _t\|_ S× <D_k+1 \,\\ J_k( t)&:= _t= _k+1; t _k+3; t-1 _( μ, π)∈ S× \|W_t;k( μ, π)|≤ δ(2+ δ)^-1 βD_k \. aligned Step 1. We claim that for any tˇ≥tˇ∗ t≥ t^* and n≥1n≥ 1, ∩k=1nJk(tˇ)⊆∩k=1nIk(tˇ). _k=1^nJ_k( t) _k=1^nI_k( t). Let tˇ≥tˇ∗ t≥ t^* be given. We first show that J1(tˇ)⊆I1(tˇ),J_1( t) _1( t), i.e., the case n=1n=1. By Lemma 4.9 and Lemma 5.1 (i), we have that for every t∈τ1;tˇ,…,τ3;tˇ−1t∈\ _1; t,…, _3; t-1\, ‖Δˇt‖Sˇ×Πˇ≤‖Qˇt‖Sˇ×Πˇ+‖Qˇ∗‖Sˇ×Πˇ≤D1=2Qˇmax.\| _t\|_ S× ≤\| Q_t\|_ S× +\| Q^*\|_ S× ≤ D_1=2 Q_max. Moreover, since tˇ≥tˇ1∗,⌈Tcov(Tcov−1)−1⌉ t≥\ t_1^*, T_cov(T_cov-1)^-1 \ and cˇ=maxcˇ1,1 c= \ c_1,1\ (see (5.31), (5.35)), we can apply Lemma 5.10 and Lemma 5.11 to have for every t≥τ2;tˇt≥ _2; t and (μˇ,πˇ)∈Sˇ×Πˇ( μ, π)∈ S× |Δˇt(μˇ,πˇ)|≤Yt;1(μˇ,πˇ)+|Wt;1(μˇ,πˇ)|≤(β+2βˇ(2+δˇ)−1)D1+|Wt;1(μˇ,πˇ)|, | _t( μ, π)|≤ Y_t;1( μ, π)+|W_t;1( μ, π)|≤(β+2 β(2+ δ)^-1)D_1+|W_t;1( μ, π)|, where the first inequality holds because (Yt;1)t≥τ1;tˇ(Y_t;1)_t≥ _1; t is nonnegative (see (5.18)). Moreover, since (β+2βˇ(2+δˇ)−1)D1+δˇ(2+δˇ)−1βˇD1=(1−βˇ)D1=D2(β+2 β(2+ δ)^-1)D_1+ δ(2+ δ)^-1 βD_1=(1- β)D_1=D_2 (see Definition 5.6), we have J1(tˇ)⊆I1(tˇ),J_1( t) _1( t), as claimed. Inductively, on I1(tˇ)I_1( t), we have ‖Δˇt‖Sˇ×Πˇ≤D2\| _t\|_ S× ≤ D_2 for every t∈τ2;tˇ,…,τ4;tˇ−1t∈\ _2; t,…, _4; t-1\. Repeating the arguments for the case n=1n=1 with (D2;τ2;tˇ,…,τ4;tˇ−1)(D_2;\ _2; t,…, _4; t-1\) in place of (D1;τ1;tˇ,…,τ3;tˇ−1)(D_1;\ _1; t,…, _3; t-1\), we obtain J2(tˇ)⊆I2(tˇ)J_2( t) _2( t) on I1(tˇ)I_1( t), and hence J2(tˇ)∩I1(tˇ)⊆I1(tˇ)∩I2(tˇ)J_2( t)∩\,I_1( t) _1( t)∩\,I_2( t). Combining this with J1(tˇ)⊆I1(tˇ)J_1( t) _1( t), we have J1(tˇ)∩J2(tˇ)⊆I1(tˇ)∩I2(tˇ).J_1( t)∩\,J_2( t) _1( t)∩\,I_2( t). By using the same arguments presented for the case n=2n=2 inductively, we have the desired inclusion property for any n≥1n≥ 1. Moreover, since tˇ≥tˇ∗ t≥ t^* is arbitrary, the claim follows. Step 2. Recalling that Dn∗≤ε^D_n^*≤ (by definition of n∗n^* in (5.30)), we have by Step 1 that for any tˇ≥tˇ∗ t≥ t^* (5.37) ℙ^0(⋂t=τn∗;tˇτn∗+2;tˇ−1‖Δˇt‖Sˇ×Πˇ<ε^)≥ℙ^0(In∗−1(tˇ))≥ℙ^0(⋂k=1n∗−1Ik(tˇ))≥ℙ^0(⋂k=1n∗−1Jk(tˇ))=:P^(tˇ). aligned P^0 ( _t= _n^*; t _n^*+2; t-1 \\| _t\|_ S× < \ )&≥ P^0 (I_n^*-1( t) )\\ &≥ P^0 ( _k=1^n^*-1I_k( t) )≥ P^0 ( _k=1^n^*-1J_k( t) )=: P( t). aligned Since Dn≥σ∗ε^D_n≥σ^* for any n=1,…,n∗n=1,…,n^*, and 2a(σ∗ε^)log(a(σ∗ε^))>12a(σ^* ) (a(σ^* ))>1 (see (5.34)) and tˇ≥tˇ3∗ t≥ t_3^* (see (5.35), (5.36)), we can apply Lemma 5.15 to have, for every tˇ≥tˇ∗ t≥ t^*, P^(tˇ)≥1−2|Sˇ||Aˇ||Sˇ|C3n∗exp(tˇw/a(σ∗ε^))≥1−δ^, P( t)≥ 1- 2| S|| A|^| S|C_3n^* ( t^w/a(σ^* ))≥ 1- δ, where the last inequality follows from tˇ≥tˇ4∗ t≥ t_4^*; see (5.35), (5.36). Step 3. Using n∗n^* and tˇ∗ t^* (see (5.30), (5.35)), we define T∗:=τn∗;tˇ∗T^*:= _n^*; t^*. Since (5.33) holds for all t≥tˇ∗t≥ t^* (by definition of tˇ∗ t^* in (5.35)), it holds that for all m≥0m≥ 0 τn∗;tˇ∗+m,…,τn∗+2;tˇ∗+m−1∩τn∗;tˇ∗+m+1,…,τn∗+2;tˇ∗+m+1−1≠∅.\ _n^*; t^*+m,…, _n^*+2; t^*+m-1\∩\ _n^*; t^*+m+1,…, _n^*+2; t^*+m+1-1\≠ . Hence, for any T≥T∗T≥ T^*, there exists mT≥0m_T≥ 0 such that T∈τn∗;tˇ∗+mT,…,τn∗+2;tˇ∗+mT−1.T∈\ _n^*; t^*+m_T,…, _n^*+2; t^*+m_T-1\. From this, we have by Step 2 and Step 3 that for any T≥T∗T≥ T^*, (5.38) ℙ^0(‖QˇT−Qˇ∗‖Sˇ×Πˇ≤ε^)=ℙ^0(‖ΔˇT‖Sˇ×Πˇ≤ε^)≥ℙ^0(⋂t=τn∗;tˇ∗+mTτn∗+2;tˇ∗+mT−1‖Δˇt‖Sˇ×Πˇ<ε^)≥P^(tˇ∗+mT)≥1−δ^. aligned P^0(\| Q_T- Q^*\|_ S× ≤ )= P^0(\| _T\|_ S× ≤ )&≥ P^0 ( _t= _n^*; t^*+m_T _n^*+2; t^*+m_T-1 \\| _t\|_ S× < \ )\\ &≥ P( t^*+m_T)≥ 1- δ. aligned Hence, the desired result in (2.14) follows from combining this with the discretization error estimates given in (5.11). Step 4. It remains to compute the order of T∗=τn∗;tˇ∗T^*= _n^*; t^*. To this end, we note that666For any nonnegative functions f,g:ℕ→ℝf,g:N , we write f(n)=Θ(g(n))f(n)= (g(n)) if and only if there exist some c,C>0c,C>0 and n¯∈ℕ n such that cg(n)≤f(n)≤Cg(n)cg(n)≤ f(n)≤ Cg(n) for all n≥n¯n≥ n. tˇ1∗=Θ(Tcov) t_1^*= (T_cov) and cˇ1∗=Θ(1) c_1^*= (1) (see (5.20)), hence cˇ c in (5.31) satisfies cˇ=Θ(1) c= (1). Recall that a(σ∗ε^)a(σ^* ) is given in (5.29) (with replacing D¯ D as σ∗ε^σ^* therein), C3>0C_3>0 is given in Lemma 5.14, and Qˇmax=Cr1−3β Q_max= C_r1-3β and βˇ=1−β2 β= 1-β2. Since β∈[0,13∧(2CF)−1)β∈[0, 13 (2C_F)^-1) (by Assumption 2.12 (i)), we have that a(σ∗ε^)=Θ(Nˇ1ε^2)a(σ^* )= ( N_1 ^2) and C3=Θ(Tcov1+3w),C_3= (T_cov^1+3w), where Nˇ1 N_1 is given in (2.15). Moreover, since n∗n^* in (5.30) satisfies n∗=Θ(log(Qˇmaxε^))n^*= ( ( Q_max )), tˇ∗ t^* in (5.35) can be expressed in terms of the algorithmic parameters as an order of tˇ∗=O((Nˇ1ε^2maxlog(Nˇ2ε^),log(Nˇ3δ^log(Qˇmaxε^)))1w+(Tcovlog(Qˇmaxε^))11−w), t^*=O ( ( N_1 ^2 \ ( N_2 ), ( N_3 δ ( Q_max ) ) \ ) 1w+ (T_cov ( Q_max ) ) 11-w ), where Nˇ2 N_2 and Nˇ3 N_3 are given in (2.15). From this and Lemma 5.7 (i), we have the order of the iteration number T∗T^* given by T∗=τn∗;tˇ∗=O(tˇ∗+(Tcovn∗)11−w)=O(tˇ∗), T^*= _n^*; t^*=O( t^*+(T_covn^*) 11-w)=O( t^*), as desired. Therefore, the proof of the asynchronous version of the Q-learning algorithm is complete. Finally, for the synchronous version of the Q-learning algorithm under Framework 2.9 (i),(i), the construction of the iteration number T∗∈ℕT^* is analogous to that for the asynchronous version but involves much simpler calculations, since the covering time condition in Assumption 2.12 (i) is no longer required. In particular, for any tˇ≥1 t≥ 1, the sequence (τn;tˇ)n≥0( _n; t)_n≥ 0 in Definition 5.6 can be redefined as τn+1;tˇ:=τn;tˇ+⌈cˇκˇτn;tˇw⌉,n≥0,with τ1;tˇ:=tˇ. _n+1; t:= _n; t+ c κ _n; t^w , n≥ 0, with $ _1; t:= t$. Moreover, in the resulting constants—such as tˇ1∗ t_1^* and cˇ1∗ c_1^* in (5.20), tˇ2∗ t_2^* in (5.32), C3C_3 in (5.14), and a(D¯)a( D) in (5.29)—the parameter TcovT_cov can be taken as 11 so that the results in Lemmas 5.10, 5.11, and 5.15 still hold, while (5.33) holds for all tˇ≥tˇ∗ t≥ t^*. As a consequence, all the arguments presented in the main proof for the asynchronous case also apply to the synchronous version. This completes the proof. ∎ 5.3. Proof of Corollary 2.19 We only present the proof for the asynchronous case, since the synchronous case can be proven analogously following the same argument. Proof. Let δ^∈(0,1) δ∈(0,1) be given. By the discretization error estimate in (5.11), it suffices to show that there exist some Cδ^>0C_ δ>0 and Tδ^≥1T_ δ≥ 1 such that (5.39) ℙ^0(‖QˇT−Qˇ∗‖Sˇ×Πˇ≤Cδ^logTTw)>1−δ^for any T≥Tδ^. P^0 (\| Q_T- Q^*\|_ S× ≤ C_ δ TT^w )>1- δ for any $T≥ T_ δ$. To this end, for every ε^∈(0,1) ∈(0,1), we denote by T∗(ε^,δ^)T^*( , δ) the iteration number T∗T^* in Theorem 2.17 (i) under the prescribed error level ε and confidence level δ δ. We recall from the proof of Theorem 2.17 (i), particularly Step 3, that T∗(ε^,δ^)=T∗=τn∗;tˇ∗,T^*( , δ)=T^*= _n^*; t^*, where n∗n^* and tˇ∗ t^*, given in (5.30) and (5.35), respectively, satisfy the following estimates: there exist constants Kδ^,1>0K_ δ,1>0 and εδ^,1∈(0,1) _ δ,1∈(0,1), where Kδ^,1K_ δ,1 depends on the parameters appearing in (2.15) and the fixed confidence level δ δ, but does not depend on ε , such that for every ε^∈(0,εδ^,1) ∈(0, _ δ,1), n∗≤Kδ^,1log(ε^−1)andtˇ∗≤Kδ^,1[ε^−2log(ε^−1)]1/w.n^*≤ K_ δ,1 ( ^-1) and t^*≤ K_ δ,1 [ ^-2 ( ^-1) ]^1/w. Moreover, by Lemma 5.7 there exists some Kδ^>0K_ δ>0 (depending on Kδ^,1K_ δ,1 but not on ε ) such that (5.40) T∗(ε^,δ^)≤Kδ^[ε^−2log(ε^−1)]1/wfor all ε^∈(0,εδ^,1). T^*( , δ)≤ K_ δ [ ^-2 ( ^-1) ]^1/w for all $ ∈(0, _ δ,1)$. Now, we let Cδ^:=Kδ^w/2C_ δ:=K_ δ^w/2 and define for every T≥2T≥ 2 by (5.41) Eδ^(T):=Cδ^logTTw. E_ δ(T):=C_ δ TT^w. Since the map [e1/w,∞):T↦logTTw[e^1/w,∞):T TT^w is decreasing, we can choose Tδ^,1≥max2,e1/wT_ δ,1≥ \2,e^1/w\ such that (5.42) Eδ^(T)≤εδ^,1for all T≥Tδ^,1. E_ δ(T)≤ _ δ,1 for all $T≥ T_ δ,1$. Moreover, since log(Eδ^(T)−1)=w2logT−12loglogT−logCδ (E_ δ(T)^-1)= w2 T- 12 T- C_ δ for all T>2T>2, there exists some Tδ^,2≥2T_ δ,2≥ 2 such that (5.43) log(Eδ^(T)−1)≤logTfor all T≥Tδ^,2. (E_ δ(T)^-1)≤ T for all $T≥ T_ δ,2$. Last, we let Tδ^:=maxTδ^,1,Tδ^,2T_ δ:= \T_ δ,1,T_ δ,2\. Then, we have by (5.40), (5.42), (5.43) that for every T≥Tδ^T≥ T_ δ, (5.44) T∗(Eδ^(T),δ^)≤Kδ^[Eδ^(T)−2log(Eδ^(T)−1)]1/w=Kδ^[Cδ^−2TwlogTlog(Eδ^(T)−1)]1/w≤Kδ^[Cδ^−2Tw]1/w=T, aligned T^*(E_ δ(T), δ)&≤ K_ δ [E_ δ(T)^-2 (E_ δ(T)^-1 ) ]^1/w\\ &=K_ δ [C_ δ^-2 T^w T (E_ δ(T)^-1 ) ]^1/w≤ K_ δ [C_ δ^-2T^w ]^1/w=T, aligned where the first equality follows from definition of Eδ^(T)E_ δ(T) and the last equality follows from the setting that Cδ^=Kδ^w/2C_ δ=K_ δ^w/2. Then, for each T≥Tδ^T≥ T_ δ, the estimate (5.38) (which follows from the Step 2 and Step 3 in the proof of Theorem 2.17) can be applied with the prescribed error level ε^:=Eδ^(T) :=E_ δ(T) (see (5.41)) and confidence level δ δ, which leads to ℙ^0(‖QˇT~−Qˇ∗‖Sˇ×Πˇ≤Eδ^(T))>1−δ^for any T~≥T∗(Eδ^(T),δ^). P^0 (\| Q_ T- Q^*\|_ S× ≤ E_ δ(T) )>1- δ for any $ T≥ T^*(E_ δ(T), δ).$ Since T≥T∗(Eδ^(T),δ^)T≥ T^*(E_ δ(T), δ) for every T≥Tδ^T≥ T_ δ by (5.44), the desired estimate (5.39) follows. This completes the proof. ∎ References [1] B. Anahtarci, C. D. Kariksiz, and N. Saldi. Q-learning in regularized mean-field games. Dyn. Games Appl., 13(1):89–117, 2023. [2] A. Angiuli, J.-P. Fouque, M. Laurière, and M. Zhang. Analysis of multiscale reinforcement Q-learning algorithms for mean field control games. Appl. Math. Optim., 93(2):27, 2026. [3] K. Azuma. Weighted sums of certain dependent random variables. Tohoku Math. J., Second Series, 19(3):357–367, 1967. [4] D. Bartl, S. Drapeau, and L. Tangpi. Computational aspects of robust optimized certainty equivalents and option pricing. Math. Finance, 30(1):287–309, 2020. [5] N. Bäuerle and A. Glauner. Distributionally robust Markov decision processes and their connection to risk measures. Math. Oper. Res., 47(3):1757–1780, 2022. [6] N. Bäuerle and U. Rieder. Markov decision processes with applications to finance. Springer Science & Business Media, 2011. [7] D. Bauso, H. Tembine, and T. Basar. Opinion dynamics in social networks through mean-field games. SIAM J. Control Optim., 54(6):3225–3257, 2016. [8] D. Bauso, H. Tembine, and T. Başar. Robust Mean Field Games. Dynam. Games Appl., 6(3):277–303, 2016. [9] C. L. Beck and R. Srikant. Error bounds for constant step-size Q-learning. Syst. Control Lett., 61(12):1203–1208, 2012. [10] A. Bensoussan, J. Frehse, and P. Yam. Mean field games and mean field type control theory, volume 101. New York: Springer-Verlag, 2013. [11] D. P. Bertsekas. Neuro-dynamic programming. In Encyclopedia of optimization, pages 1–6. Springer, 2025. [12] J. Blanchet, M. Lu, T. Zhang, and H. Zhong. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Adv. Neural Inf. Process. Syst., 36:66845–66859, 2023. [13] J. Blanchet and K. Murthy. Quantifying distributional model risk via optimal transport. Math. Oper. Res., 44(2):565–600, 2019. [14] R. Carmona and F. Delarue. Probabilistic theory of mean field games with applications I-I. Springer, 2018. [15] R. Carmona, K. Hamidouche, M. Laurière, and Z. Tan. Policy optimization for linear-quadratic zero-sum Mean-Field Type Games. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 1038–1043. IEEE, 2020. [16] R. Carmona, K. Hamidouche, M. Laurière, and Z. Tan. Linear-quadratic zero-sum Mean-Field Type Games: Optimality conditions and policy optimization. J. Dyn. Games, 8(4), 2021. [17] R. Carmona, M. Laurière, and Z. Tan. Model-free mean-field reinforcement learning: mean-field MDP and mean-field Q-learning. Ann. Appl. Probab., 33(6B):5334–5381, 2023. [18] K. Cui and H. Koeppl. Approximately solving Mean Field Games via entropy-regularized deep reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1909–1917. PMLR, 2021. [19] M. F. Djete. Extended mean field control problem: A propagation of chaos result. Electron. J. Probab., 27:1–53, 2022. [20] M. F. Djete, D. Possamaï, and X. Tan. McKean–Vlasov optimal control: limit theory and equivalence between different formulations. Math. Oper. Res., 47(4):2891–2930, 2022. [21] M. F. Djete, D. Possamaï, and X. Tan. McKean–Vlasov optimal control: The dynamic programming principle. Ann. Probab., 50(2):791–833, 2022. [22] A. Dvoretsky. On stochastic approximation. Mathematics Division, Office of Scientific Research, US Air Force, 1955. [23] K. Elamvazhuthi and S. Berman. Mean-field models in swarm robotics: A survey. Bioinsp. Biomim., 15(1):015001, 2019. [24] R. Elie, J. Pérolat, M. Laurière, M. Geist, and O. Pietquin. On the convergence of model free learning in Mean Field Games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7143–7150, 2020. [25] E. Even-Dar and Y. Mansour. Learning rates for Q-learning. J. Mach. Learn. Res., 5(Dec):1–25, 2003. [26] D. Firoozi and S. Jaimungal. Exploratory LQG mean field games with entropy regularization. Automatica, 139:110177, 2022. [27] J.-P. Fouque, R. Carmona, and L. Sun. Mean field games and systemic risk. Commun. Math. Sci, 13(4):911–933, 2015. [28] N. Frikha, M. Germain, M. Laurière, H. Pham, and X. Song. Actor-critic learning for mean-field control in continuous time. J. Mach. Learn. Res., 26(127):1–42, 2025. [29] S. Fujimoto, D. Meger, and D. Precup. Off-policy deep reinforcement learning without exploration. In ICML, pages 2052–2062. PMLR, 2019. [30] R. Gao and A. Kleywegt. Distributionally robust stochastic optimization with Wasserstein distance. Math. Oper. Res., 48(2):603–655, 2023. [31] N. Gast and B. Gaujal. A mean field approach for optimization in discrete time. Discrete Event Dyn. Syst., 21(1):63–101, 2011. [32] N. Gast, B. Gaujal, and J.-Y. Le Boudec. Mean field for Markov decision processes: from discrete to continuous optimization. IEEE. Trans. Autom. Control, 57(9):2266–2280, 2012. [33] H. Gu, X. Guo, X. Wei, and R. Xu. Mean-field controls with Q-learning for cooperative MARL: convergence and complexity analysis. SIAM J. Math. Data Sci., 3(4):1168–1196, 2021. [34] H. Gu, X. Guo, X. Wei, and R. Xu. Dynamic programming principles for mean-field controls with learning. Oper. Res., 71(4):1040–1054, 2023. [35] X. Guo, A. Hu, R. Xu, and J. Zhang. Learning Mean-Field Games. In Adv. Neural Inf. Process. Syst., volume 32, 2019. [36] R. Hu and M. Laurière. Recent developments in machine learning methods for stochastic control and games. arXiv preprint arXiv:2303.10257, 2023. [37] J. Huang and M. Huang. Robust mean field linear-quadratic-gaussian games with unknown L2L^2-disturbance. SIAM J. Control Optim., 55(5):2811–2840, 2017. [38] J. Huang, B.-C. Wang, and J. Yong. Social optima in mean field linear-quadratic-Gaussian control with volatility uncertainty. SIAM J. Control Optim., 59(2):825–856, 2021. [39] M. Huang, R. P. Malhamé, and P. E. Caines. Large population stochastic dynamic games: Closed loop McKean–Vlasov sysyems and the Nash certainity equivalence principle. Commun. Inf. Syst., 6(3):221–252, 2006. [40] T. Jaakkola, M. I. Jordan, and S. P. Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural Comput., 6(6):1185–1201, 1994. [41] B. Jeloka, Y. Guan, and P. Tsiotras. Learning large-scale competitive team behaviors with Mean-Field interactions. In The Seventeenth Workshop on Adaptive and Learning Agents, 2025. [42] M. Kearns and S. Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. Adv. Neural Inf. Process. Syst., 11, 1998. [43] A. Klenke. Probability Theory: A Comprehensive Course. Universitext. Springer, London, 2nd ed., 2014. [44] S. Lange, T. Gabel, and M. Riedmiller. Batch reinforcement learning. In Reinforcement learning: State-of-the-art, pages 45–73. Springer, 2012. [45] J. Langner, A. Neufeld, and K. Park. Markov-Nash equilibria in mean-field games under model uncertainty. preprint, arXiv:2410.11652, 2024. [46] J.-M. Lasry and P.-L. Lions. Mean field games. Japan. J. Math., 2(1):229–260, 2007. [47] M. Laurière. Numerical methods for Mean Field Games and Mean Field Type Control. In Proceedings of Symposia in Applied Mathematics, volume 78, pages 221–282. American Mathematical Society, 2021. [48] M. Laurière, A. Neufeld, and K. Park. Robust mean-field control under common noise uncertainty. arXiv preprint arXiv:2511.04515, 2025. [49] M. Laurière, S. Perrin, S. Girgin, P. Muller, A. Jain, T. Cabannes, G. Piliouras, J. Pérolat, R. Elie, O. Pietquin, et al. Scalable deep reinforcement learning algorithms for Mean Field Games. In ICML, pages 12078–12095. PMLR, 2022. [50] M. Laurière, S. Perrin, J. Pérolat, S. Girgin, P. Muller, R. Elie, M. Geist, and O. Pietquin. Learning in Mean Field Games: A survey. arXiv preprint arXiv:2205.12944, 2022. [51] M. Laurière and O. Pironneau. Dynamic programming for mean-field type control. J. Optim. Theory Appl., 169(3):902–924, 2016. [52] S. Levine, A. Kumar, G. Tucker, and J. Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020. [53] G. Li, L. Shi, Y. Chen, Y. Chi, and Y. Wei. Settling the sample complexity of model-based offline reinforcement learning. Ann. Stat., 52(1):233–260, 2024. [54] G. Li, Y. Wei, Y. Chi, and Y. Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Oper. Res., 72(1):203–221, 2024. [55] G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen. Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. Adv. Neural Inf. Process. Syst., 33:7031–7043, 2020. [56] M. Li, D. Kuhn, and T. Sutter. Policy gradient algorithms for robust MDP with nonrectangular uncertainty sets. SIAM J. Optim., 36(1):120–151, 2026. [57] Y. Liang, B.-C. Wang, and H. Zhang. Robust mean field linear quadratic social control: Open-loop and closed-loop strategies. SIAM J. Control Optim., 60(4):2184–2213, 2022. [58] Z. Liang, Z. Zhou, Y. Zhuang, and B. Zou. Mean-field games under model uncertainty. arXiv preprint arXiv:2601.12226, 2026. [59] M. L. Littman and C. Szepesvári. A generalized reinforcement-learning model: Convergence and applications. In ICML, volume 96, pages 310–318, 1996. [60] Z. Liu, Q. Bai, J. Blanchet, P. Dong, W. Xu, Z. Zhou, and Z. Zhou. Distributionally robust Q-learning. In ICML, pages 13623–13643. PMLR, 2022. [61] C. I. Lu, J. Sester, and A. Zhang. Distributionally robust deep Q-learning. preprint, arXiv:2505.19058, 2025. [62] P. Mohajerin Esfahani and D. Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Math. Program., 171(1):115–166, 2018. [63] J. Moon and T. Başar. Robust Mean Field Games for coupled Markov jump linear systems. Internat. J. Control, 89(7):1367–1381, 2016. [64] M. Motte and H. Pham. Mean-field Markov decision processes with common noise and open-loop controls. Ann. Appl. Probab., 32(2):1421–1458, 2022. [65] M. Motte and H. Pham. Quantitative propagation of chaos for mean field Markov decision process with common noise. Electron. J. Probab., 28:1–24, 2023. [66] A. Neufeld and J. Sester. Robust Q-learning algorithm for Markov decision processes under Wasserstein uncertainty. Automatica, 168:111825, 2024. [67] K. Panaganti, Z. Xu, D. Kalathil, and M. Ghavamzadeh. Robust reinforcement learning using offline data. Adv. Neural Inf. Process. Syst., 35:32211–32224, 2022. [68] H. Pham and X. Wei. Discrete time McKean–Vlasov control problem: A dynamic programming approach. Appl. Math. Optim., 74(3):487–506, 2016. [69] H. Pham and X. Wei. Dynamic programming for optimal control of stochastic McKean–Vlasov dynamics. SIAM J. Control Optim., 55(2):1069–1101, 2017. [70] G. Qu and A. Wierman. Finite-time analysis of asynchronous stochastic approximation and Q-learning. In COLT, pages 3185–3205. PMLR, 2020. [71] P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. IEEE Trans. Inf. Theory, 68(12):8156–8196, 2022. [72] Z. Ren, X. Wei, X. Yu, and X. Y. Zhou. Continuous-time q-learning for mean-field control with common noise, Part I: Theoretical foundations. arXiv preprint arXiv:2604.27372, 2026. [73] Z. Ren, X. Wei, X. Yu, and X. Y. Zhou. Continuous-time q-learning for mean-field control with common noise, Part I: q-learning algorithms. arXiv preprint arXiv:2604.27378, 2026. [74] H. Robbins and S. Monro. A stochastic approximation method. Ann. Math. Stat., pages 400–407, 1951. [75] A. Roy, H. Xu, and S. Pokutta. Reinforcement learning under model mismatch. Adv. Neural Inf. Process. Syst., 30, 2017. [76] S. Sanjari and S. Yüksel. Optimal solutions to infinite-player stochastic teams and mean-field teams. IEEE Trans. Autom. Control, 66(3):1071–1086, 2020. [77] J. Sester and C. Decker. Q-learning under finite model uncertainty. arXiv e-prints, pages arXiv–2407, 2024. [78] K. Shao, J. Shen, and M. Laurière. Reinforcement learning for finite space Mean-Field Type Game. In Reinforcement Learning Conference, 2025. [79] J. Subramanian and A. Mahajan. Reinforcement learning in stationary Mean-Field Games. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, pages 251–259, 2019. [80] C. Szepesvári. The asymptotic convergence-rate of Q-learning. Adv. Neural Inf. Process. Syst., 10, 1997. [81] A. Tamar, S. Mannor, and H. Xu. Scaling up robust MDPs using function approximation. In ICML, pages 181–189. PMLR, 2014. [82] H. Tembine, Q. Zhu, and T. Başar. Risk-sensitive Mean-Field Games. IEEE. Trans. Autom. Control, 59(4):835–850, 2013. [83] C. Villani. Optimal Transport: Old and New, volume 338. Springer Science & Business Media, 2008. [84] B.-C. Wang and J. Huang. Social optima in robust mean field LQG control. In 2017 11th Asian Control Conference (ASCC), pages 2089–2094. IEEE, 2017. [85] B.-C. Wang, J. Huang, and J.-F. Zhang. Social optima in robust mean field LQG control: From finite to infinite horizon. IEEE Trans. Autom. Control, 66(4):1529–1544, 2020. [86] C. J. Watkins and P. Dayan. Q-learning. Mach. Learn., 8(3):279–292, 1992. [87] X. Wei and X. Yu. Continuous time q-learning for mean-field control problems. Appl. Math. Optim., 91(1):10, 2025. [88] X. Wei, X. Yu, and F. Yuan. Unified continuous-time q-learning for mean-field game and mean-field control problems. arXiv preprint arXiv:2407.04521, 2024. [89] W. Wiesemann, D. Kuhn, and B. Rustem. Robust Markov decision processes. Math. Oper. Res., 38(1):153–183, 2013. [90] H. Xu and S. Mannor. Distributionally robust Markov decision processes. Math. Oper. Res., 37(2):288–301, 2012. [91] M. A. U. Zaman, M. Laurière, A. Koppel, and T. Başar. Robust cooperative multi-agent reinforcement learning: A Mean-Field Type Game perspective. In 6th Annu. Learn. Dyn. Control Conf., pages 770–783. PMLR, 2024. [92] H. Zhang, H. Chen, C. Xiao, B. Li, M. Liu, D. Boning, and C.-J. Hsieh. Robust deep reinforcement learning against adversarial perturbations on state observations. Adv. Neural Inf. Process. Syst., 33:21024–21037, 2020.