Robust $Q$-learning for mean-field control under Wasserstein uncertainty in common noise

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Robust $Q$-learning for mean-field control under Wasserstein uncertainty in common noise

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

ROBUST Q-LEARNING FOR MEAN-FIELD CONTROL UNDER WASSERSTEIN UNCERTAINTY IN COMMON NOISE

arXiv:2606.20356v1 [math.OC] 18 Jun 2026

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

Abstract. In this article, we present a robust Q-learning algorithm for discrete-time meanfield 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.

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 [39, 46], 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., [7, 23, 27, 33]). 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, 19, 20, 64, 65, 69]. 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 Date: June 19, 2026. 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

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

corresponding optimality conditions take the form of Bellman equations or forward-backward equations defined on spaces of probability measures (see, e.g., [17, 20, 21, 64]). 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, 60, 61, 66, 67, 75, 77, 92], 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 Q 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, an action processes (ait )t≥0 ⊆ A, and a probability measure P ∈ Q, the state of agent i ∈ N evolves according to (1.1)

sit+1 := F(sit , ait , Λit , εit+1 , ε0t+1 )

for t ≥ 0,

with si0 := ξ i ,

where F denotes the transition function, εit+1 ∈ E and ε0t+1 ∈ E 0 denote the idiosyncratic and common noise, respectively, and Λit denotes the conditional law of (sit , ait ) given (ε01 , . . . , ε0t ). Here, the idiosyncratic noise process (εit )t≥1 has the fixed law pε ∈ P(E), while the common noise process (ε0t )t≥1 is uncertain in the following sense: Fix m ≥ 0, q ∈ N. For any t ≥ 1, the conditional law of ε0t given (ε01 , . . . , ε0t−1 ) under P belongs to (1.2)

0 Bm,q (b pε0 ) := {p ∈ P(E 0 ) : Wq (p, pbε0 ) ≤ m},

where pbε0 is a fixed reference measure and Wq denotes the Wasserstein q-distance (see (2.1)). In this setting, the robust MFC problem is then defined by X ∞ sup inf EP (1.3) β t r(sit , ait , Λit ) , (ait )t≥0 P∈Q

t=0

where r denotes the one-step reward function and β ∈ [0, 1) is the discount factor. Following MFC terminology, the conditional law of sit and that of (sit , ait ) 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∗ defined on P(S) × Π, where P(S) denotes the lifted state space and Π denotes the set of Markov kernels

inducing randomized actions. More precisely, the optimal Q-function Q∗ is the unique fixed point of the following lifted state-action operator, defined by solving for every (µ, π) ∈ P(S) × Π Z ˆ π) + β ˆ π, e0 ), π ′ p(de0 ), (1.4) inf sup Q∗ F(µ ⊗ Q∗ (µ, π) = r(µ ⊗ 0 p∈Bm,q (b p ε0 )

E 0 π ′ ∈Π

where r and F denote the lifted reward and lifted transition functions, induced by the one-step reward function r in (1.1) and transition function F in (1.3), respectively; see Definition 2.1 in Section 2 for the precise definitions of Π, r and 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 0 which the nonlinear expectation over the set Bm,q (b pε0 ) in (1.4) is replaced by a linear expectation under the reference measure pbε0 . We remark that dynamic programming principles on spaces of probability measures have already appeared in existing non-robust discrete-time MFC frameworks [33, 34, 51, 68, 69]. Notably, the corresponding reinforcement learning algorithms have been developed in [2, 17, 33, 34]. 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) are assumed to be finite, the lifted state space 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 0 (b pε0 ). Together, these features make the incorporation of robustness into a sample-based Bm,q learning procedure nontrivial. To address these challenges, we introduce two key ingredients. The first is a quantization-andprojection scheme for the domain (P(S), Π) of 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 0 (b pε0 ) to a one-dimensional optimization problem involving a single expectation under the over Bm,q reference law pbε0 . Furthermore, the dual reformulation enables the use of independent commonnoise 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.

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

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 discretetime mean-field frameworks. For discrete-time mean-field control (MFC) and related mean-field Markov decision/control formulations, we refer to [2, 17, 31–34, 64]. 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., [1, 18, 24, 35, 49, 79] and [15,16,41,76,78]. 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,28,72,73,87,88]. 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 [36, 47, 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 [8,37,45,48,57,58,63,82,91]. 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, 56, 89, 90] for robust Markov decision processes (MDPs) and to [12, 60, 61, 66, 67, 75, 77, 92] for robust Qlearning algorithms. These robust MDPs and Q-learning works do not address the lifted stateaction 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 [42, 53–55, 70]. 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 E 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) for the set of all Borel probability measures on X. We endow X with the topology induced by the 1-Wasserstein distance, which we recall to be the following: For any µ, ν ∈ X, we write Cpl(µ, ν) ⊂ X × X for the subset of probability measures on X ×X with marginals µ and ν, called couplings. For q ∈ N, the q-Wasserstein distance between µ and ν is defined by 1/q Z (2.1) Wq (µ, ν) := inf |x − y|q γ(dx, dy) . γ∈Cpl(µ,ν)

X×X

Since X is finite, for any q ∈ N the topology induced by Wq 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 × E 0 → S, the one-step reward function r : S × A × S × A → R, the discount factor β ∈ [0, 1), and the fixed law of the idiosyncratic noise pε ∈ E. Definition 2.1.

(i) Define F : S × A × E 0 ∋ (Λ, e0 ) 7→ F(Λ, e0 ) ∈ S by F(Λ, e0 )(ds′ ) := (Λ ⊗ pε ) ◦ F(·, ·, Λ, ·, e0 )−1 (ds′ ),

i.e., the push-forward of the product measure Λ ⊗ pε := Λ(ds, da)pε (de) ∈ S × A × E by the mapping F(·, ·, Λ, ·, e0 ) : S × A × E → S. (ii) Define r : S × A ∋ Λ 7→ r(Λ) ∈ R by Z r(Λ) := r(s, a, Λ)Λ(ds, da). S×A

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

(iii) Let Π := {π : S ∋ s 7→ π(·|s) ∈ A} denote the policy set (i.e., the set of Markov kernels), endowed with the metric dΠ (π, π ′ ) := max W1 (π(da|s), π ′ (da|s)) s∈S

for π, π ′ ∈ Π.

In mean-field control frameworks [17, 34, 48, 64], the space S and S × A are referred to as the lifted state and state-action spaces, respectively. The mappings F and 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 and 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 F, the reward function r, and the discount factor β. Assumption 2.2. There are some constants CF > 0 and Cr > 0 such that (i) for every (s, a, Λ, e0 ) and (s̃, ã, Λ̃, ẽ0 ) ∈ S × A × S × A × E 0 Z | F(s, a, Λ, e, e0 ) − F(s̃, ã, Λ̃, e, ẽ0 )|pε (de) E

≤ CF |s − s̃| + |a − ã| + W1 (Λ, Λ̃) + |e0 − ẽ0 | , (ii) for every (s, a, Λ) and (s̃, ã, Λ̃) ∈ S × A × S × A |r(s, a, Λ) − r(s̃, ã, Λ̃)| ≤ Cr |s − s̃| + |a − ã| + W1 (Λ, Λ̃) . (iii) β is in [0, 1 ∧ (2CF )−1 ). Remark 2.3. Since S and A are finite and S × A is compact, Assumption 2.2 (ii) implies that Cr,∞ :=

|r(s, a, Λ)| < ∞.

sup (s,a,Λ)∈S×A×S×A

Moreover, we have by [48, Lemma 5.2] that under Assumption 2.2 (i), (ii), the following properties on the lifted components F and r in Definition 2.1 hold: (i) for every (Λ, e0 ), (Λ̃, ẽ0 ) ∈ S × A × E 0 , W1 (F(Λ, e0 ), F(Λ̃, ẽ0 )) ≤ CF (2W1 (Λ, Λ̃) + |e0 − ẽ0 |), (ii) for every Λ, Λ̃ ∈ S × A, |r(Λ)| ≤ Cr,∞

and

|r(Λ) − r(Λ̃)| ≤ 2Cr .

To introduce the Bellman–Isaacs operator T , let Cb (S) denote the set of bounded, continuous functions v : S → R, endowed with the supremum norm ∥v∥S := supµ∈S |v(µ)|. Moreover, for any L ≥ 0, let Lipb,L (S) ⊂ Cb (S) denote the set of bounded, L-Lipschitz continuous functions. 0 Using the components introduced in Definition 2.1 together with the uncertainty set Bm,q (b p ε0 ) defined in (1.2), we define the Bellman–Isaacs operator T by setting, for any v ∈ Cb (S), Z 0 0 ˆ ˆ (2.2) T v(µ) := sup r(µ ⊗ π) + β inf v(F(µ ⊗ π, e ))p(de ) , µ ∈ S, 0 π∈Π

p∈Bm,q (b pε0 )

ˆ π(ds, da) := π(da|s)µ(ds) ∈ S × A. where µ ⊗ We now state the fixed-point theorem associated with the operator T 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 ). Then there exists a unique fixed point v ∗ ∈ Lipb,L∗ (S) of T such that v ∗ = T v ∗ . Moreover, for any v ∈ Lipb,L∗ (S), limn→∞ T n v = v ∗ . Using v ∗ from Proposition 2.4, we define the optimal Q-function Q∗ : S × Π → R by Z ∗ ˆ ˆ π, e0 ))p(de0 ), (µ, π) ∈ S × Π. (2.3) Q (µ, π) := r(µ ⊗ π) + β inf v ∗ (F(µ ⊗ 0 p∈Bm,q (b p ε0 )

∗

It is optimal in the sense that supπ∈Π Q (µ, π) = v ∗ (µ) for any µ ∈ 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 meanfield 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∗ defined in (2.3). We emphasize that although the state and action spaces (S, A) are finite, the corresponding lifted spaces of measures S and kernels Π are not. Therefore, from a numerical view point, two key ingredients are required: (i) quantization and projection of the domain (S, Π) of Q∗ and (ii) computation of worst-case expectations over the Wasserstein 0 uncertainty set Bm,q (b pε0 ) in Q∗ . These two enable a finite-dimensional approximation of Q∗ : the discretization of (S, Π) enables a tractable tabular representation of Q∗ , while the evaluation of 0 (b pε0 ) is properly worst-case expectations ensures that the robustness with respect to the set Bm,q incorporated into the learning procedure. We begin by introducing the quantization and projection for (S, Π), following the approach in Section 5.3 of [17]. Definition 2.5. Let Š ⊂ S be a finite subset such that for any µ ∈ S, min W1 (µ, µ̌) ≤ εŠ µ̌∈Š

for some εŠ > 0,

representing an εŠ -net of S under W1 . Analogously, let Ǎ ⊂ A be a finite subset such that for any ν ∈ A, minν̌∈Ǎ W1 (ν, ν̌) ≤ εǍ for some εǍ > 0. (i) Let pjŠ : S ∋ µ 7→ pjŠ (µ) ∈ Š be a mapping satisfying W1 (µ, pjŠ (µ)) = min W1 (µ, µ̌). µ̌∈Š

(ii) Define Π̌ := {π̌ : S ∋ s 7→ π̌(da|s) ∈ Ǎ} so that it is a finite subset of Π; see Definition 2.1 (iii). Then let pjΠ̌ : Π ∋ π 7→ pjΠ̌ (π) ∈ Π̌ be a mapping satisfying dΠ (π, pjΠ̌ (π)) = min dΠ (π, π̌). π̌∈Π̌

Remark 2.6. (i) We present a construction of Š below; an analogous construction applies to Ǎ. Denote S := {s1 , . . . , s|S| } and let ∆S := maxs̸=s′ ∈S |s − s′ | < ∞. For k ∈ N, define |S| X bi bi = k , Š := µ ∈ S : µ({si }) = , bi ∈ N ∪ {0} ∀i = 1, . . . , |S|, k i=1 . which is finite with |Š| = k+|S|−1 |S|−1 P|S| For any µ ∈ S, set ℓ := k − i=1 ⌊kµ({si })⌋ and define µ̌′ ∈ Š by

µ̌′ ({si }) :=

⌊kµ({si })⌋ + 1 k

if i = 1, . . . , ℓ;

µ̌′ ({si }) :=

⌊kµ({si })⌋ k

else.

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

Then |µ({si }) − µ̌′ ({si })| ≤ k1 for all i = 1, . . . , |S|. Hence by [83, Theorem 6.15], W1 (µ, µ̌′ ) ≤ ∆S ∥µ − µ̌′ ∥TV =

|S| ∆S X ∆S |S| |µ({si }) − µ̌′ ({si })| ≤ , 2 i=1 2k

where ∥ · ∥TV denotes the total variation and the equality holds because S is finite. Thus, S |S| ⌉ ensures minµ̌∈Š W1 (µ, µ̌) ≤ εŠ . choosing k ≥ ⌈ ∆2ε Š

Finally, once the construction of Ǎ is obtained as above, the set Π̌ is naturally induced as the set of mappings from S to Ǎ, and hence satisfies |Π̌| = |Ǎ||S| . (ii) A construction of the measurable mapping pjŠ in Definition 2.5 (i) is given as follows. Fix an arbitrary ordering Š = {µ̌1 , . . . , µ̌N } for some N ∈ N. For any µ ∈ S, define n o pjŠ (µ) := µ̌i∗,µ , where i∗,µ := min i ∈ {1, . . . , N } : W1 (µ, µ̌i ) = min W1 (µ, µ̌ℓ ) , 1≤ℓ≤N

i.e., the nearest element of Š, with tie-breaking according to the fixed ordering. Since Π̌ in Definition 2.5 (ii) is finite, we can construct the mapping pjΠ̌ analogously by replacing (S, Š; W1 ) with (Π, Π̌; dΠ ). 0 Next, to enable the tractable computation of worst-case expectations over the set Bm,q (b pε0 ), we exploit a convex duality representation that expresses worst-case expectations in terms of linear expectations with respect to the reference measure pbε0 , as established, e.g., in [4, 13, 30, 62]. To this end, we recall the notion of λc-transform on the common noise space E 0 ; see Section 2 in [4], Section 5 in [83].

Definition 2.7. For f : E 0 → R and λ ≥ 0, let (f )λ : E 0 ∋ e0 7→ (f )λ (e0 ) ∈ R denote the λc-transform of f with the cost function c : E 0 × E 0 ∋ (e0 , ẽ0 ) 7→ c(e0 , ẽ0 ) := |e0 − ẽ0 |q defined by (f )λ (e0 ) := max {f (ẽ0 ) − λ|e0 − ẽ0 |q }. 0 0

(2.4)

ẽ ∈E

We next recall the convex duality result established, e.g., in Theorem 2.4 of [4]. Lemma 2.8. For any mapping f : E 0 → R, the following convex duality holds: Z Z 0 0 λ 0 0 q inf f (e )p(de ) = sup − (−f ) (e ) pbε0 (de ) − m λ . 0 p∈Bm,q (b pε0 )

λ≥0

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]. b0 ) be a probability space supporting a family of independent Framework 2.9. Let (Ω0 , F 0 , P and identically distributed random variables (ε0t,(µ̌,π̌) )t≥1,(µ̌,π̌)∈Š×Π̌ ⊆ E 0 , with law pbε0 . Both synchronous and asynchronous frameworks share the Q-learning update rule in (iii) and differ only in the choice of learning rates specified in (i) and (ii). Fix w ∈ ( 21 , 1). (i) (Synchronous learning rate) Define the synchronous learning rates by αt,(µ̌,π̌) := (t + 1)−w for every t ≥ 0 and (µ̌, π̌) ∈ Š × Π̌. (ii) (Asynchronous learning rate) Let (µ̌t , π̌t )t≥0 ⊆ Š × Π̌ be a pre-sampled, projected dataset. Then we define for every (µ̌, π̌) ∈ Š × Π̌ (2.5)

T(µ̌,π̌) := {t ≥ 0 : (µ̌, π̌) = (µ̌t , π̌t )}, representing the set of times t ≥ 0 at which (µ̌, π̌) is visited along (µ̌t , π̌t )t≥0 . Finally, we define the asynchronous learning rates as follows: for every t ≥ 0 and (µ̌, π̌) ∈ Š × Π̌,

(2.6)

αt,(µ̌,π̌) := (Nt,(µ̌,π̌) + 1)−w

if t ∈ T(µ̌,π̌) ;

αt,(µ̌,π̌) (µ̌, π̌) := 0

else,

where Nt,(µ̌,π̌) denotes the number of times 0 ≤ ℓ < t at which (µ̌, π̌) = (µ̌ℓ , π̌ℓ ), with the convention that N0,(µ̌,π̌) = 0. (iii) Under either choice of learning rates in (i) or (ii), the Q-learning algorithm is defined by the following stochastic iteration: For every t ≥ 0 and every pair (µ̌, π̌) ∈ Š × Π̌, (2.7) (2.8)

Q̌0 (µ̌, π̌) :=Q̌0 ,

for some Q̌0 ∈ R,

Q̌t+1 (µ̌, π̌) :=(1 − αt,(µ̌,π̌) )Q̌t (µ̌, π̌) h i ∗ ˆ π̌) + β − − Jt,(µ̌,π̌) λt,(µ̌,π̌) (ε0t+1,(µ̌,π̌) ) − mq λ∗t,(µ̌,π̌) , + αt,(µ̌,π̌) r(µ̌ ⊗ where Jt,(µ̌,π̌) : E 0 ∋ e0 7→ Jt,(µ̌,π̌) (e0 ) ∈ R is defined by

(2.9)

ˆ π̌, e0 ) , π̌ ′ , Jt,(µ̌,π̌) (e0 ) := max Q̌t pjŠ F(µ̌ ⊗ π̌ ′ ∈Π̌

where λ∗t,(µ̌,π̌) appearing in (2.8) is an optimizer of the dual problem Φt,(µ̌,π̌) defined by

(2.10)

Φt,(µ̌,π̌) := sup ϕt,(µ̌,π̌) (λ), λ≥0 Z ϕt,(µ̌,π̌) (λ) := − (−Jt,(µ̌,π̌) )λ (e0 ) pbε0 (de0 ) − mq λ,

λ ≥ 0.

Remark 2.10. For the synchronous Q-learning algorithm under Framework 2.9 (i) and (iii), the update Q̌t+1 in (2.8) occurs at all pairs in Š × Π̌. In contrast, under the asynchronous Q-learning algorithm under Framework 2.9 (ii) and (iii), Q̌t+1 is updated only for the visited pair (µ̌t , π̌t ) at time t, since α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 ≥ 0 and (µ̌, π̌) ∈ Š × Π̌, (i) λ∗t,(µ̌,π̌) in (2.8) is well-defined under certain conditions on β and Q̌0 in (2.7); see Assumption 2.12 and Remark 2.13. (ii) We have by Lemma 2.8 that Φt,(µ̌,π̌) in (2.10) satisfies Z ˆ π, e0 )), π̌ ′ p(de0 ). (2.11) ⊗ Φt,(µ̌,π̌) = inf max Q̌ pj (F(µ t Š 0 p∈Bm,q (b p ε0 )

E 0 π̌ ′ ∈Π̌

Moreover, when m = 0 (i.e., the non-robust case), the update rule (2.8) reduces to i h ˆ π̌) + β max Q̌t (µ̌′t+1,(µ̌,π̌) , π̌ ′ ) , Q̌t+1 (µ̌, π̌) = (1 − αt,(µ̌,π̌) )Q̌t (µ̌, π̌) + αt,(µ̌,π̌) r(µ̌ ⊗ π̌ ′ ∈Π̌

ˆ π̌, ε0t+1,(µ̌,π̌) )) ∈ Š represents the lifted-state transition where µ̌′t+1,(µ̌,π̌) := pjŠ (F(µ̌ ⊗ from the pair (µ̌, π̌) at time t. Therefore, this case corresponds to the standard tabular Q-learning algorithm on the finite space Š × Π̌ (see, e.g., [11, 40, 59, 86]). Remark 2.11. The asynchronous Q-learning algorithm under Framework 2.9 (ii) and (iii) adopts an offline-learning, independent-sampling setting. The pre-sampled, projected data (µ̌t , π̌t )t≥0 in Framework 2.9 (ii) is obtained by applying the projection mappings pjŠ and pjΠ̌ given in Definition 2.5 to a historically collected lifted trajectory (µt , πt )t≥0 ⊆ S ×Π, and is therefore regarded as b0 ). fixed or, more generally, as defined on an auxiliary probability space independent of (Ω0 , F 0 , P 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 (ε0t,(µ̌,π̌) )t≥1, (µ̌,π̌)∈Š×Π̌ . These are directly sampled from a simulator with law pbε0 , constructed from the original (unprojected) historical lifted trajectory (µt , πt )t≥0 ⊆ S × Π, for instance, via filtering or direct empirical b0 ) is then understood estimation of the common noise processes. The probability space (Ω0 , F 0 , P

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

Algorithm 1 Q-learning algorithm for robust MFC problem −1 Require: Number of iteration T ∈ N. pre-sampled, projected dataset (µ̌t , π̌t )Tt=0 ⊆ Š × Π̌ used in the asynchronous Q-learning algorithm under Framework 2.9 (ii),(iii). 1: Initialize Q̌0 (µ̌, π̌) := Q̌0 for all (µ̌, π̌) ∈ Š × Π̌ for some Q̌0 ∈ R. 2: if Framework 2.9 (i),(iii) (i.e., the synchronous Q-learning) then 3: Set αt,(µ,π̌) := (t + 1)−w for all t = 0, . . . , T − 1 and (µ̌, π̌) ∈ Š × Π̌. 4: for t = 0, . . . , T − 1 do 5: for every (µ̌, π̌) ∈ Š × Π̌ do ˆ π̌) and ε0t+1,(µ̌,π̌) . 6: Execute action π̌ in state µ̌, and observe r(µ̌ ⊗ ∗ 7: Compute the optimizer λt,(µ̌,π̌) of Φt,(µ̌,π̌) ; see (2.10). ∗

Compute the λc-transform value (−Jt,(µ̌,π̌) )λt,(µ̌,π̌) (ε0t+1,(µ̌,π̌) ); see (2.4) and (2.9). 9: Update Q̌t+1 (µ̌, π̌) according to (2.8). 10: end for 11: end for 12: else −1 −1 13: Use (µ̌t , π̌t )Tt=0 to compute (αt,(µ̌t ,π̌t ) )Tt=0 according to (2.6) (i.e., the asynchronous Qlearning algorithm under Framework 2.9 (ii),(iii)). 14: for t = 0, . . . , T − 1 do 15: Set Q̌t+1 (µ̌, π̌) := Q̌t (µ̌, π̌) for all (µ̌, π̌) ∈ Š × Π̌. 16: Apply Steps 6–9 with (µ̌t , π̌t ) in place of (µ̌, π̌) to update only Q̌t+1 (µ̌t , π̌t ). 17: end for 18: end if 19: return Q̌T ∗ 8:

b0 the law it induces on Ω0 . This is conas the canonical space supporting this simulator, with P sistent with the batch/offline Q-learning paradigm, in which learning is carried out from static, previously collected data; see, e.g., [29, 44, 52, 53, 71]. 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 (ii) related to the covering time) are satisfied. 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 > 0 and Cr > 0 in Assumption 2.2. C

r,∞ . (i) β is in [0, 31 ∧ (2CF )−1 ). Moreover, Q̌0 in (2.7) satisfies |Q̌0 | ≤ Q̌max := 1−3β (ii) There exists a finite covering time Tcov > 1 such that for every s ≥ 0

Š × Π̌ ⊆ (µ̌t , π̌t )t=s,...,s+Tcov −1 , where (µ̌t , π̌t )t≥0 is the pre-sampled, projected dataset used for Framework 2.9 (ii). Remark 2.13. The condition on β in Assumption 2.12 (i) is stronger than that in Assumption 2.2 (iii). We impose this stronger condition, together with the assumption on Q̌0 , in order to establish the existence of λ∗t,(·,·) for all t ≥ 0 in (2.10), as well as to obtain uniform-in-time bounds for (λ∗t,(·,·) )t≥0 and (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 [75, 81], 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 (ii) ensures that under the asynchronous learning rates in Framework 2.9 (ii), every pair in Š × Π̌ is visited at least once within any time window of length greater than the covering time Tcov . 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 − s′ | > 0 and ∆S := min ′ s̸=s ∈S

∆A := max |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∗ from Proposition 2.4. Theorem 2.15. Under Assumptions 2.2 (i),(ii) and 2.12 (i), the following statements hold: (i) the synchronous version of the Q-learning algorithm in Framework 2.9 (i),(iii) satisfies, for every (µ, π) ∈ S × Π, (2.13)

lim |Q̌t (pjŠ (µ), pjΠ̌ (π)) − Q∗ (µ, π)| ≤ C1 εŠ + C2 εǍ ,

t→∞

b0 -a.s., P ∗

2(Cr +βL CF ) β ∗ ∗ where C1 := 2(1 + ∆A ∆−1 > 0. S )(Cr + βL CF ) + 1−β L > 0 and C2 := 1−β (ii) Moreover, if Assumption 2.12 (ii) also holds, then the asynchronous version of the Qlearning algorithm in Framework 2.9 (ii),(iii) satisfies (2.13) for every (µ, π) ∈ S × Π.

Remark 2.16. The error term “C1 εŠ +C2 ε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 Qfunction. 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),(ii) and 2.12 (i) are satisfied. Then the following statements hold for any εb > 0 and δb ∈ (0, 1). (i) There exists an iteration number T ∗ ∈ N of order1 1 Q̌ Q̌ Q̌ w1 1−w Q̌max 2 |Š||Ǎ||Š| max max max log O max log , log + log , εb εb εb εb δb such that the synchronous version of the Q-learning algorithm in Framework 2.9 (i),(iii) satisfies, for every T ≥ T ∗ , ∗ 0 b b Q̌T (pjŠ (µ), pjΠ̌ (π)) − Q (µ, π) ≤ C1 εŠ + C2 εǍ + εb (2.14) P sup ≥ 1 − δ, (µ,π)∈S×Π

with the constants C1 and C2 given in Theorem 2.15. (ii) Moreover, if Assumption 2.12 (ii) is satisfied and we let (2.15)

1+5w 2 Ň1 := Tcov Q̌max ,

1We denote by O(·) the Landau symbol.

Ň2 := Tcov Q̌max ,

Ň3 := Tcov |Š||Ǎ||Š| ,

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

then there exists an iteration number T ∗ ∈ N of order 1 Ň Q̌ w1 1−w Q̌ Ň3 Ň1 2 max max max log , log log O + T log , cov εb2 εb εb εb δb such that the asynchronous version in Framework 2.9 (ii),(iii) also satisfies (2.14) for every 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 ∗ of the stated order such that, for every T ≥ T ∗ , the corresponding Q-learning iterate Q̌T has error bounded by the prescribed error plus the discretization error C1 εŠ + C2 ε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 [42, 53–55, 70]. 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),(ii) and 2.12 (i) are satisfied. Then the synchronous version of the Q-learning algorithm in Framework 2.9 (i),(iii) satisfies,2 as T → ∞, r log T ∗ Q̌T (pjŠ (µ), pjΠ̌ (π)) − Q (µ, π) ≤ C1 εŠ + C2 εǍ + ObP0 (2.16) sup , Tw (µ,π)∈S×Π with the constants C1 and C2 given in Theorem 2.15. Moreover, if Assumption 2.12 (ii) is satisfied, then the asynchronous version in Framework 2.9 (ii),(iii) also satisfies (2.16). 3. Numerics In this section we illustrate the robust Q-learning algorithm on three finite-grid mean-field control examples. 3 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 (ii),(iii), 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 E 0 . In all experiments reported below, we set q = 1 and |E 0 | = 3, and the reference common-noise law is pbε0 = (0.1, 0.8, 0.1). The pre-sampled lifted state–policy pairs (µ̌t , π̌t )t≥0 used by the asynchronous implementation are generated by repeated random permutations of Š × Π̌. Hence the visitation pattern is independent of the current 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 2We denote by O

b0 -probability; that is, for a sequence of random variables (Xn )n≥1 (·) the Landau symbol in P b P0

and a deterministic sequence (an )n≥1 , we write Xn = ObP0 (an ) as n → ∞, if for every δb > 0, there exists a finite b0 (| Xn | > M ) ≤ δb for every n ≥ N . M > 0 and N ∈ N such that P an

3The code is available at https://github.com/mlauriere/RobustMeanFieldControlQLearning.

on Š × Π̌. Below, for radius m, the resulting finite-grid fixed point is denoted by Q̌∗,m , while the iterated Q-function at iteration T is denoted by Q̌m T . The Bellman-iteration procedure to obtain 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, Ssys , SSIS , and SSEIR denote concrete individual state spaces S in the notation of Section 2; these should be distinguished from the finite projected lifted-state grid Š. Robustness profiles are evaluated under perturbed common-noise laws pζeval = (1 − ζ)b pε0 + ζ padv ,

ζ ∈ {0, 0.125, . . . , 1},

where ζ = 0 is the reference law and ζ = 1 is an example-specific adverse endpoint used only for evaluation. The law padv 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 pζeval as the true law for the common noise, which is, however, unknown to the agent, forcing him to optimize robustly. If ζ = 0, then the reference law pbε0 coincides with the true law pζeval , whereas if ζ > 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̌ table. For each fixed value of ζ, this is an ordinary evaluation under the fixed common-noise law pζeval , not an additional robust infimum over laws. Since the primitive dynamics are given by the map F, the law pζeval enters only through the finite average over commonnoise values in the display below. For a fixed evaluation law pζeval and greedy finite-grid policy π̌Q̌ (µ̌) ∈ arg maxπ̌∈Π̌ Q̌(µ̌, π̌), this reward is computed by solving the finite linear system X ζ ˆ π̌Q̌ (µ̌)) + β ˆ π̌Q̌ (µ̌), e0 )) , µ̌ ∈ Š, peval (e0 )VQ̌ pjŠ (F(µ̌ ⊗ VQ̌ (µ̌) = r(µ̌ ⊗ e0 ∈E 0

and averaging VQ̌ with respect to the uniform measure on the finite projected state grid Š. Larger plotted values in Figures 2 and 3 therefore correspond to better performance. In Figures 2 and 3, solid curves show means over 20 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 = {0, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.75, 1}, Repi = {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}. Here Rsys and Repi denote the choices for Wasserstein robustness radii m used in the robustnessprofile experiments. The construction of Š and Π̌ is explained in each example. Example

|Š|

|Π̌|

Updates per m

Robustness radii m

Systemic Risk 0.5 21 216 5,000,000 0.75 Rsys SIS 0.5 13 11 1,000,000 0.7 Repi SEIR 0.9 165 11 3,000,000 0.7 Repi 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

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

schedule is generated by repeated random permutations of Š × Π̌, hence the covering-time condition in Assumption 2.12 (ii) holds with Tcov = |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. 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̌ iterates on the same finite grids used in the robustness profiles. For each displayed robustness radius m, let Q̌∗m denote the corresponding idealized finite-grid fixed point. At iteration time T , the plotted error is ∗,m ∗,m ET (m) = ∥Q̌m ∥Š×Π̌ = max |Q̌m (µ̌, π̌)|. T − Q̌ T (µ̌, π̌) − Q̌ (µ̌,π̌)∈Š×Π̌

The line is the median over p10 seeds and the band is the 10–90 percentile range. The black dashed guide is proportional to log(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. Systemic Risk m=0 logT/T 0.75 m = 0.3 m = 0.6

SIS

100

SEIR m=0 logT/T 0.7 m = 0.05 m = 0.3

10 1

QT Qm*

100

m=0 logT/T 0.7 m = 0.1 m = 0.3

100

10 2 10 3

104

105 106 sampled updates

10 4

102

103

104 105 sampled updates

106

104

105 sampled updates

106

Figure 1. Asynchronous Q-function convergence. Error ET (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},

E 0 = {−1, 0, 1}.

The states 0, 1, 2 represent distressed, normal, and well-capitalized agents. Given individual state x, action a, and common shock e0 , the next state is x′ = min{2, max{0, x + a + e0 }}. 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′ when x ∼ µ and a ∼ π(·|x). The lifted one-step reward is ˆ π) = −∥µ − (0, 1, 0)∥22 − 2µ0 . r(µ ⊗ where µ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), which puts all mass on the negative common shock.

The projected state grid is the uniform probability-simplex grid k0 k1 k2 Šsys = , , : k0 , k1 , k2 ∈ N ∪ {0}, k0 + k1 + k2 = 5 . 5 5 5 Thus |Šsys | = 72 = 21. The individual action set has three actions, A = {−1, 0, 1}. We discretize local randomized actions by ℓ−1 ℓ0 ℓ1 Ǎsys = , , : ℓ−1 , ℓ0 , ℓ1 ∈ N ∪ {0}, ℓ−1 + ℓ0 + ℓ1 = 2 , 2 2 2 so |Ǎsys | = 42 = 6. A finite-grid population policy assigns one element of Ǎsys to each individual state x ∈ Ssys , hence Π̌sys = {π̌ : Ssys → Ǎsys },

|Π̌sys | = 63 = 216.

With the configuration in Table 1, Figure 2 shows a clear hedging effect: under the adverse law ζ = 1, the mean reward from Algorithm 1 increases from −5.119 at m = 0 to −3.230 at m = 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 = 0 reflects slower finite-time learning in this example. eval. drift =0 = 0.125 = 0.25 = 0.375 = 0.5 = 0.625 = 0.75 = 0.875 =1

expected discounted reward

2.5 3.0 3.5 4.0 4.5 5.0 0.0

0.2

0.4 0.6 robustness radius m

0.8

1.0

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.

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

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 E 0 = {0.5, 0.81, 1.8}, interpreted as the transmission-rate state. The last point, 1.8, is the high-transmission state. The adverse law is padv = (0, 0, 1), so the interpolation defining 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, D}, where U denotes unrestricted behavior and D denotes distancing. Thus π(D|s) denotes the probability that policy π assigns to the distancing action in individual state s ∈ 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 for non-susceptible states and varies π(D|s) only at susceptible states. 3.3.1. SIS. The individual state space is SSIS = {S, I} corresponding to susceptible and infected states. With µ = (µS , µI ), common noise e0 = b, and u = π(U |S), the finite-grid mean-field transition used in the computation is 1 µ′I = 0.7µI + b µI µS u 0 ,

µ′S = 1 − µ′I ,

where [z]10 = min{1, max{0, z}}. This corresponds to recovery probability 0.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 X ˆ π) = −µI − 0.5 r(µ ⊗ µs π(D|s). s∈SSIS

In this example, the projected state grid is kS kI , : kS , kI ∈ N0 , kS + kI = 12 , ŠSIS = 12 12 so |ŠSIS | = 13. The individual action set is A = {U, D}, where U denotes unrestricted behavior and D denotes distancing. The susceptible-state action distribution is discretized as ℓU ℓD Ǎepi = , : ℓU , ℓD ∈ N0 , ℓU + ℓD = 10 , 10 10 with coordinates corresponding to (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 . Therefore |Π̌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, the mean reward from Algorithm 1 increases from −1.089 at m = 0 to −1.080 at m = 0.03, then decreases to −1.098 at m = 1. At the severe law ζ = 1, high robustness remains beneficial, with the mean reward from Algorithm 1 increasing from −1.175 at m = 0 to −1.138 at m = 0.75.

eval. drift =0 = 0.125 = 0.25 = 0.375 = 0.5 = 0.625 = 0.75 = 0.875 =1

1.000

expected discounted reward

1.025 1.050 1.075 1.100 1.125 1.150 1.175 0.0

0.2

0.4 0.6 robustness radius m

0.8

1.0

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, 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 = b is again the transmission rate. Let θS (π) = π(U |S) + (1 − η)π(D|S). Here η is the efficacy of distancing for susceptible agents, σ is the incubation probability, and ρrec is the recovery probability. For µ = (µS , µE , µI , µR ), the lifted transition map is described by the population mass transfers dSE = min{µS , bµI µS θS (π)}, dEI = σµE , Equivalently,

dIR = ρrec µI .

µ′S = µS − dSE , µ′E = µE + dSE − dEI , µ′I = µI + dEI − dIR ,

µ′R = µR + dIR , followed by clipping and renormalization on the finite population grid. The numerical experiments use η = 1, σ = 0.5, and ρrec = 0.2. The one-step reward is X ˆ π) = −µI − 0.85 r(µ ⊗ µs π(D|s). s∈SSEIR

Under the reduced policy class, this distancing term is µS π(D|S). In this example, the projected state grid is kS kE kI kR ŠSEIR = , , , : kS , kE , kI , kR ∈ N0 , kS + kE + kI + kR = 8 . 8 8 8 8

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

Thus |ŠSEIR | = 11 3 = 165. As in the SIS example, A = {U, D} and the susceptible-state action distribution is discretized on ℓU ℓD , : ℓU , ℓD ∈ N0 , ℓU + ℓD = 10 . Ǎepi = 10 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) = δU for s ∈ {E, I, R} . Therefore |Π̌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, the mean reward from Algorithm 1 increases from −2.680 at m = 0 to −2.641 at m = 0.15, then decreases slightly to −2.646 at m = 1. At ζ = 1, robustness increases the mean reward from Algorithm 1 from −2.775 at m = 0 to −2.650 at m = 0.5. 2.55

eval. drift =0 = 0.125 = 0.25 = 0.375 = 0.5 = 0.625 = 0.75 = 0.875 =1

expected discounted reward

2.60

2.65

2.70

2.75

0.0

0.2

0.4 0.6 robustness radius m

0.8

1.0

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, 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 ∗ established in Proposition 2.4. In particular, the optimal Q-function Q∗ defined in (2.3), constructed from v ∗ , serves as the learning target for our Q-learning algorithm. Building on this connection, we then introduce a discretized approximation of 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). Recalling from Section 2 the idiosyncratic noise space E and common noise space E 0 , define G := [0, 1] and Θ := [0, 1], which represent the initial information space and randomization source space, respectively. We let the space Ω be defined by ( ) (g i , θti ) ∈ G × Θ, for t ≥ 0, i ∈ N; i i i 0 Ω := ω := (g )i∈N , (θt )t≥0,i∈N , (et )t≥1,i∈N , (et )t≥1 : i 0 . (et , et ) ∈ E × E 0 , for t ≥ 1, i ∈ N Then define, for every ω ∈ Ω, γ i (ω), ϑi0 (ω) := (g i , θ0i ) ∈ G × Θ ϑit (ω), εit (ω) := (θti , eit ) ∈ Θ × E

(4.1)

ε0t (ω) := e0t ∈ E 0

i ∈ N, t ≥ 1, i ∈ N, t ≥ 1,

so that γ and (ϑit )t≥0 represent the initial state information of agent i and her randomization source process, respectively. Moreover, (εit )t≥1 represents her idiosyncratic noise process, whereas (ε0t )t≥1 represents the common noise process for all agents. Last, we let the σ-algebra F be defined by F := σ((γ i )i∈N , (ϑit )t≥0,i∈N , (εit )t≥1,i∈N , (ε0t )t≥1 ). Under this setting, we introduce the following filtrations: for each i ∈ N · F0 := (Ft0 )t≥0 is given by F00 := {∅, Ω} and Ft0 := σ(ε01:t ) for any t ≥ 1. · Fi := (Fti )t≥0 is given by F0i := σ(γ i ) and Fti := σ(γ i , ϑi0:t−1 , εi1:t , ε01:t ) for any t ≥ 1. · Gi := (Gti )t≥0 is given by Gti := Fti ∨ σ(ϑit ) for all t ≥ 0 so that Fi ⊆ Gi . While Ft0 represents the common noise information shared by all agents at time t, Fti and Gti represent the information of agent i at time t for her state and action processes, respectively (see Definition 4.4). In particular, Gti contains the current randomization source ϑit whereas Fti does not. Consequently, these filtrations satisfy F0 ⊂ Fi ⊂ Gi . 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. 0 To this end, we recall from Section 1 the set Bm,q (b pε0 ) in (1.2), together with the law pε ∈ E. Definition 4.1. Let pγ := pϑ := L[0,1] , where L[0,1] denotes the Lebesgue measure on [0, 1]. (i) Let K0 be the set of (pt )t≥1 consisting of a measure and sequence of kernels such that 0 p1 ∈ Bm,q (b pε0 );

0 pt : (E 0 )t−1 ∋ e01:t−1 7→ pt (de0t |e01:t−1 ) ∈ Bm,q (b p ε0 )

for all t ≥ 2,

inducing distributional uncertainty in the law of the common noise process (ε0t )t≥1 .

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

(ii) Let Q be defined as the subset of all Borel probability measures P on Ω induced by some W W (pt )t≥1 ∈ K0 in the sense that4 for every B0 ∈ i∈N G0i and B1 ∈ i∈N G1i P (γ i , ϑi0 )i∈N ∈ B0 = Q̂0 (B0 ), P ((γ i , ϑi0:1 , εi1 )i∈N , ε01 ) ∈ B1 = (Q̂0 ⊗ Q̂p1 )(B1 ), where Q̂0 (dg i , dθ0i )i∈N := ⊗ pγ (dg i )pϑ (dθ0i ) ∈ P (G × Θ)N i∈N p1 i i 0 Q̂ (dθ1 , de1 )i∈N , de1 := ⊗ pϑ (dθ1i )pε (dei1 ) p1 (de01 ) ∈ P (Θ × E)N × E 0 , i∈N

whereas for every t ≥ 2 and Bt ∈ i∈N Gti ˆ Q̂p2 ⊗ ˆ ··· ⊗ ˆ Q̂pt )(Bt ), P (γ i , ϑi0:t , εi1:t )i∈N , ε01:t ∈ Bt = (Q̂0 ⊗ Q̂p1 ⊗ W

where the kernel Q̂pt : (E 0 )t−1 ∋ e01:t−1 7→ Q̂pt ((dθti , deit )i∈N , de0t |e01:t−1 ) ∈ P((Θ×E)N ×E 0 ) is defined by Q̂pt (dθti , deit )i∈N , de0t |e01:t−1 := ⊗ pϑ (dθti )pε (deit ) pt (de0t |e01:t−1 ). i∈N

Remark 4.2. The introduction of G and Θ, together with pγ and pϑ in Definition 4.1, allows each agent i ∈ N 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 P ∈ Q with corresponding (pt )t≥1 ∈ K0 (i) (γ i )i∈N is independent and identically distributed (i.i.d.) with law pγ . Moreover, (ϑit )t≥0,i∈N is i.i.d. with law pϑ , and (εit )t≥1,i∈N is i.i.d. with law pε . W (ii) ε01 is independent of i∈N G0i with law p1 , whereas for every t ≥ 2 ε0t is conditionally W i 0 independent of i∈N Gt−1 given Ft−1 , satisfying 0 LP (ε0t |Ft−1 ) = pt ( · |ε01:t−1 )

P-a.s..

Therefore, (ε0t )t≥1 is uncertain in the Wasserstein sense specified in (1.2). pt )t≥1 ∈ K0 be defined by Remark 4.3. Recall the reference measure pε ∈ E. Let (b pb1 := pbε0 ,

pbt : (E 0 )t−1 ∋ e01:t−1 7→ pbt (de0t |e01:t−1 ) := pbε0 (de0t )

for all t ≥ 2.

b ∈ Q the probability measure induced by (b Then we denote by P pt )t≥1 , representing the reference b i.e., in the absence of uncertainty), probability measure on (Ω, F). When m = 0 (so that Q = {P}, 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, β in (1.1) and (1.3). Definition 4.4. For each i ∈ N, let L0F i (S) denote the set of F0i -measurable, S-valued random 0 variables, representing the initial states of agent i. (i) Denote by ΠOL the set of all open-loop policies π := (πt )t≥0 in the sense that πt : G×Θt+1 × E t × (E 0 )t → A is a Borel measurable function for all t ≥ 0. For any π := (πt )t≥0 ∈ ΠOL , the corresponding action process of agent i is given by the open-loop control i i i 0 ai,π t := πt (γ , ϑ0:t , ε1:t , ε1:t )

t ≥ 1,

i i with ai,π 0 := π0 (γ , ϑ0 ).

i In other words, (ai,π t )t≥0 is a G -adapted process. 4For any set X and t ≥ 1, we use the notation X t := X × · · · × X for the t-times Cartesian product of X.

Moreover, we write X N for the countably infinite Cartesian product of X.

(ii) Let ξ i ∈ L0F i (S) be an initial state of agent i. For any π := (πt )t≥0 ∈ ΠOL , the state 0 process of agent i under P ∈ Q is governed by the conditional McKean–Vlasov dynamics: (4.2)

i,π,P i,π , at , Λi,π,P , εit+1 , ε0t+1 ) si,π,P t t+1 := F(st

t ≥ 0,

:= ξ i , with si,π,P 0

i,π,P where (ai,π is the t )t≥0 is the open-loop control of agent i as defined in (i), and Λt i,π,P i,π conditional joint law of (st , at ) under P given the common noise trajectory ε01:t , i.e., 0 Λi,π,P := LP (si,π,P , ai,π t ≥ 1, t t t )|ε1:t

, ai,π := LP ((si,π,P with the convention that Λi,π,P 0 )). 0 0 (iii) The contribution of agent i to the social planner’s gain under π := (πt )t≥0 ∈ ΠOL and P ∈ Q is defined by (4.3)

i,π,P

(ξ ) :=

∞ X

i,π,P β t r(si,π,P , ai,π ). t t , Λt

t=0

Then the social planner’s robust MFC problem is defined by (4.4)

V i (ξ i ) := sup J i,π (ξ i ),

where J i,π (ξ i ) := inf EP [Ri,π,P (ξ i )]. P∈Q

π∈ΠOL

Remark 4.5. Recall F, r defined in Definition 2.1. The following statements hold for any i ∈ N. (i) By construction of the set Q in Definition 4.1, the law of the initial state ξ i ∈ L0F i (S) 0 is invariant w.r.t. the choice of supporting measure P ∈ Q (see also [48, Section 2.4, footnote 3]). Therefore, we can and do write L (ξ i ) := LP (ξ i ) ∈ S for any P ∈ Q. (ii) For t ≥ 1, let µi,π,P be the conditional law of si,π,P under P given ε01:t , with µi,π,P := L (ξ i ). t t 0 i,π,P i,π,P Then both (µt )t≥0 and (Λt )t≥0 in (4.2) are F0 -adapted, satisfying i,π,P 0 , εt+1 ) µi,π,P t+1 = F(Λt

P-a.s., for all t ≥ 0.

Moreover, under the boundedness condition on r in Assumption 2.2 (ii), for any π := (πt )t≥0 ∈ ΠOL and P ∈ Q, Ri,π,P (ξ i ) in (4.3) satisfies X ∞ β t r(Λi,π,P EP [Ri,π,P (ξ i )] = EP ) . t t=0

This implies that the robust MFC problem V i in (4.4) can be formulated as a robust Markov decision process (MDP) on the probability space S, as shown in [48, Proposition 2.12 and Remark 2.13]. The following theorem shows that the robust MFC problem V i (ξ i ) in (4.4) is law invariant in the sense that V i (ξ i ) depends on its initial state ξ i only via its law L (ξ i ); see Remark 4.5 (i). Moreover, it is indistinguishable in the sense that for any i ∈ N, V i (ξ i ) coincides with the unique fixed point v ∗ of the Bellman–Isaacs operator T 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 ∈ N that 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∗ defined in (2.3), constructed from the fixed point v ∗ in Proposition 2.4, indeed serves as the learning target for the robust MFC problem.

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

4.2. Discretized Q-function. Since the optimal Q-function 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∗ living only on the finite subset 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 in Definition 2.1 (i) and the projection pjŠ in Definition 2.5 (ii), we define the projected version of F by ˆ π̌, e0 )) ∈ Š. F̌ : Š × Π̌ × E 0 ∋ (µ̌, π̌, e0 ) 7→ F̌(µ̌, π̌, e0 ) := pjŠ (F(µ̌ ⊗

(4.5)

Then we introduce a discretized version Ť of the Bellman–Isaacs operator T in (2.2), defined on the set ℓ∞ (Š) := {v̌ : Š → R} endowed with ∥v̌∥Š := maxµ̌∈Š |v̌(µ̌)|, by Z 0 0 ˆ (4.6) inf v̌ F̌(µ̌, π̌, e ) p(de ) , µ̌ ∈ Š. Ť v̌(µ̌) := max r(µ̌ ⊗ π̌) + β 0 p∈Bm,q (b pε0 )

π̌∈Π̌

The following lemma shows that 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̌) of Ť satisfying v̌ ∗ = Ť v̌ ∗ . Moreover, for any v̌ ∈ ℓ∞ (Š), limn→∞ Ť n v̌ = v̌ ∗ . Proof. We show that Ť is a contraction on (ℓ∞ (Š), ∥ · ∥Š×Π̌ ). Since v̌ ∈ ℓ∞ (Š) and the reward function r are bounded (see Remark 2.3), we have ∥Ť v̌∥Š ≤

sup

|r(s, a, Λ)| + β∥v̌∥Š = Cr,∞ + β∥v̌∥Š < ∞,

(s,a,Λ)∈S×A×S×A

hence, Ť v̌ ∈ ℓ∞ (Š). Moreover, for any v̌, w̌ ∈ ℓ∞ (Š) and any µ̌ ∈ Š |Ť v̌(µ̌) − Ť w̌(µ̌)| inf ≤ β max 0 π̌∈Π̌

p∈Bm,q (b pε0 )

Z ≤ β max

sup

v̌ F̌(µ̌, π̌, e ) p(de0 ) −

inf

0 p∈Bm,q (b pε0 )

w̌ F̌(µ̌, π̌, e ) p(de ) E0

v̌ F̌(µ̌, π̌, e0 ) − w̌ F̌(µ̌, π̌, e0 ) p(de0 )

0 π̌∈Π̌ p∈Bm,q (b p ε0 )

≤ β∥v̌ − w̌∥Š . Furthermore, since β ∈ [0, 1), 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̌ ∗ from Lemma 4.7, we define the discretized version of the optimal Q-function by setting for every (µ̌, π̌) ∈ Š × Π̌ Z ∗ 0 ˆ π̌) + β Q̌∗ (µ̌, π̌) := r(µ̌ ⊗ (4.7) inf v̌ F̌(µ̌, π̌, e ) p(de0 ). 0 p∈Bm,q (b pε0 )

We have by Lemma 4.7 that maxπ̌∈Π̌ Q̌∗ (µ̌, π̌) = v̌ ∗ (µ̌) for any µ̌ ∈ Š. We will refer to 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̌ and Π̌. To this end, we collect several preliminary results related to Š and Π̌. Lemma 4.8. The following hold: (i) supπ∈Π minπ̌∈Π̌ dΠ (π, π̌) ≤ εǍ , with the constant εǍ > 0 given in Definition 2.5.

(ii) For any (µ, π) ∈ S × Π and (µ̌, π̌) ∈ Š × Π̌, ˆ π̌, µ ⊗ ˆ π) ≤ (1 + ∆A ∆−1 W1 (µ̌ ⊗ S )W1 (µ̌, µ) + dΠ (π̌, π), with the constants ∆A and ∆S given in (2.12). Proof. We first prove (i). By Definition 2.5, for any π ∈ Π and s ∈ S, there exists νsπ ∈ Ǎ such that W1 (π(·|s), νsπ ) ≤ εǍ . Define π̌ ∈ Π̌ by π̌(·|s) := νsπ for each s ∈ S. Since S is finite, we have dΠ (π, π̌) = maxs∈S W1 (π(·|s), νsπ ) ≤ εǍ . Hence, minπ̌∈Π̌ dΠ (π, π̌) ≤ εǍ , which proves (i). We now prove (ii). Let (µ, π) ∈ S × Π and (µ̌, π̌) ∈ Š × Π̌. By the triangle inequality, (4.8)

ˆ π̌, µ ⊗ ˆ π) ≤ W1 (µ̌ ⊗ ˆ π̌, µ̌ ⊗ ˆ π) + W1 (µ̌ ⊗ ˆ π, µ ⊗ ˆ π) =: I + II . W1 (µ̌ ⊗

For each s ∈ S, let κs ∈ Cpl(π̌(·|s), π(·|s)) be an optimal5 coupling. Define ˆ π̌, µ̌ ⊗ ˆ π). Γ1 (ds, da, ds′ , da′ ) := κs (da, da′ )δs (ds′ )µ̌(ds) ∈ Cpl(µ̌ ⊗ Then, by the definition of W1 , Z (4.9)

I≤

W1 (π̌(·|s), π(·|s))µ̌(ds) ≤ dΠ (π̌, π). S

Next, let γ ∈ Cpl(µ̌, µ) be an optimal coupling. For each s, s′ ∈ S, let κs,s′ ∈ Cpl(π(·|s), π(·|s′ )) be an optimal coupling. ˆ π, µ ⊗ ˆ π). Then, Define Γ2 (ds, da, ds′ , da′ ) := κs,s′ (da, da′ )γ(ds, ds′ ) ∈ Cpl(µ̌ ⊗ Z II ≤ |s − s′ | + W1 (π(·|s), π(·|s′ )) γ(ds, ds′ ) ZS×S ≤ (|s − s′ | + ∆A 1{s̸=s′ } )γ(ds, ds′ ) (4.10) S×S Z −1 |s − s′ |γ(ds, ds′ ) = (1 + ∆A ∆−1 ≤ (1 + ∆A ∆S ) S )W1 (µ̌, µ). S×S

□

Combining (4.8), (4.9), and (4.10) yields (ii). Lemma 4.9. Under Assumption 2.2, we have for every (µ̌, π̌) ∈ Š × Π̌ that Cr,∞ , 1−β β |Q̌∗ (µ̌, π̌) − Q∗ (µ̌, π̌)| ≤ L∗ εŠ + 2(Cr + βL∗ CF )εǍ , 1−β |Q̌∗ (µ̌, π̌)| ≤

with the constant L∗ > 0 given in Proposition 2.4. Proof. We first show that the first estimate holds. Indeed, since maxπ̌′ ∈Π̌ Q̌∗ (µ̌′ , π̌ ′ ) = v̌ ∗ (µ̌′ ) for all µ̌′ ∈ Š (see (4.7)), by the boundedness of r (see Remark 2.3), for any (µ̌, π̌) ∈ Š × Π̌ Z ∗ ˆ |Q̌ (µ̌, π̌)| ≤ |r(µ̌ ⊗ π̌)| + β inf max Q̌∗ (F̌(µ̌, π̌, e0 ), π̌ ′ ) p(de0 ) 0 p∈Bm,q (b p ε0 )

≤ Cr,∞ + β

max

E 0 π̌ ′ ∈Π̌

|Q̌∗ (µ̌′ , π̌ ′ )|.

(µ̌′ ,π̌ ′ )∈Š×Π̌

This ensures the first estimate to hold. 5That is, κ is a coupling such that W (π̌(·|s), π(·|s)) = R ′ ′ s 1 A×A |a − a |κs (da, da ); see [83, Theorem 4.1].

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

Next we show that the other estimate holds. Let (µ̌, π̌) ∈ Š × Π̌ be given. For every e0 ∈ E 0 , ˆ π̌, e0 ) ∈ S. Then, define µ̌′ (e0 ) := F̌(µ̌, π̌, e0 ) ∈ Š and µ′ (e0 ) = F(µ̌ ⊗

(4.11)

|Q̌∗ (µ̌, π̌) − Q∗ (µ̌, π̌)| Z v̌ ∗ (µ̌′ (e0 )) − v ∗ (µ′ (e0 )) p(de0 ) ≤β sup 0 p∈Bm,q (b pε0 )

Z ≤β

sup 0 p∈Bm,q (b pε0 )

|v̌ ∗ (µ̌′ (e0 )) − v ∗ (µ̌′ (e0 ))| + |v ∗ (µ̌′ (e0 )) − v ∗ (µ′ (e0 ))| p(de0 ).

By the definitions of pjŠ and F̌ (see Definition 2.5 and (4.5)) and the L∗ -Lipschitz continuity of v ∗ (see Proposition 2.4), it holds that for every e0 ∈ E 0 |v ∗ (µ̌′ (e0 )) − v ∗ (µ′ (e0 ))| ≤ L∗ W1 µ̌′ (e0 ), µ′ (e0 ) ≤ L∗ εŠ . (4.12) We now claim that for every e0 ∈ E 0 (4.13)

|v̌ ∗ (µ̌′ (e0 )) − v ∗ (µ̌′ (e0 ))| ≤

max (µ̌′ ,π̌ ′ )∈Š×Π̌

|Q̌∗ (µ̌′ , π̌ ′ ) − Q∗ (µ̌′ , π̌ ′ )| + 2(Cr + βL∗ CF )εǍ .

To see this, note that maxπ̌′ ∈Π̌ Q̌∗ (µ̌′ , π̌ ′ ) = v̌ ∗ (µ̌′ ) for all µ̌′ ∈ Š and that Π̌ is finite. Thus, for any e0 ∈ E 0 , there exists an optimizer π̌ ∗ (e0 ) ∈ Π̌ such that v̌ ∗ (µ̌′ (e0 )) = Q̌∗ (µ̌′ (e0 ), π̌ ∗ (e0 )). Then, since v ∗ (µ̌′ (e0 )) ≥ Q∗ (µ̌′ (e0 ), π̌ ∗ (e0 )) for every e0 ∈ E 0 (see Proposition 2.4 and (2.3)), v̌ ∗ (µ̌′ (e0 )) − v ∗ (µ̌′ (e0 )) ≤ Q̌∗ (µ̌′ (e0 ), π̌ ∗ (e0 )) − Q∗ (µ̌′ (e0 ), π̌ ∗ (e0 )) (4.14)

≤

max

|Q̌∗ (µ̌′ , π̌ ′ ) − Q∗ (µ̌′ , π̌ ′ )|.

(µ̌′ ,π̌ ′ )∈Š×Π̌

Moreover, for any δ > 0 and any e0 ∈ E 0 , there exists a δ-optimizer π δ (e0 ) ∈ Π such that v ∗ (µ̌′ (e0 )) = sup Q∗ (µ̌′ (e0 ), π) ≤ Q∗ (µ̌′ (e0 ), π δ (e0 )) + δ. π∈Π ∗

Using π̌ (e ) ∈ Π̌ (which maximizes v̌ ∗ (µ̌′ (e0 ))), π δ (e0 ) ∈ Π, and the projection pjΠ̌ in Definition 2.5 (ii), we have 0

v̌ ∗ (µ̌′ (e0 )) − v ∗ (µ̌′ (e0 )) + δ ≥ Q̌∗ (µ̌′ (e0 ), π̌ ∗ (e0 )) − Q∗ (µ̌′ (e0 ), π δ (e0 )) = Q̌∗ (µ̌′ (e0 ), π̌ ∗ (e0 )) − Q̌∗ (µ̌′ (e0 ), pjΠ̌ (π δ (e0 ))) + Q̌∗ (µ̌′ (e0 ), pjΠ̌ (π δ (e0 ))) − Q∗ (µ̌′ (e0 ), pjΠ̌ (π δ (e0 )))

(4.15)

+ Q∗ (µ̌′ (e0 ), pjΠ̌ (π δ (e0 ))) − Q∗ (µ̌′ (e0 ), π δ (e0 )) =: I(e0 ) + II(e0 ) + III(e0 ). By the optimality of π̌ ∗ (e0 ), we have I(e0 ) ≥ 0. Moreover, II(e0 ) ≥ −

max

|Q̌∗ (µ̌′ , π̌ ′ ) − Q∗ (µ̌′ , π̌ ′ )|.

(µ̌′ ,π̌ ′ )∈Š×Π̌

Lastly, ˆ pjΠ̌ (π δ (e0 )) − r µ̌′ (e0 ) ⊗ ˆ π δ (e0 ) III(e0 ) ≥ − r µ̌′ (e0 ) ⊗ Z ˆ pjΠ̌ (π δ (e0 )) , ẽ0 − v ∗ F µ̌′ (e0 ) ⊗ ˆ π δ (e0 ) , ẽ0 p(dẽ0 ) −β sup v ∗ F µ̌′ (e0 ) ⊗ 0 p∈Bm,q (b pε0 )

ˆ pjΠ̌ (π δ (e0 )), µ̌′ (e0 ) ⊗ ˆ π δ (e0 ) ≥ −2(Cr + βL CF )W1 µ̌′ (e0 ) ⊗ ∗

≥ −2(Cr + βL∗ CF )dΠ (pjΠ̌ (π δ (e0 )), π δ (e0 )) ≥ −2(Cr + βL∗ CF )εǍ .

The second inequality follows from the apriori estimates for r and F given in Remark 2.3, together with the L∗ -Lipschitz continuity of v ∗ in Proposition 2.4. The third inequality follows from Lemma 4.8 (ii), and the last inequality follows from Lemma 4.8 (i). Combining the estimates for I(e0 ), II(e0 ) and III(e0 ) with (4.15), we have (4.16) v̌ ∗ (µ̌′ (e0 )) − v ∗ (µ̌′ (e0 )) + δ ≥ −

max (µ̌′ ,π̌ ′ )∈Š×Π̌

|Q̌∗ (µ̌′ , π̌ ′ ) − Q∗ (µ̌′ , π̌ ′ )| − 2(Cr + βL∗ CF )εǍ .

By letting δ ↓ 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∗ | established in Lemma 4.9 is measured on the quantized space Š × Π̌, rather than on the original space 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 ×Π onto Š × Π̌) and the estimate of |Q̌ − Q∗ | on the quantized spaces. The following lemma provides such an estimate, quantifying the gap between the optimal Qfunction 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 × Π that |Q̌∗ (pjŠ (µ), pjΠ̌ (π)) − Q∗ (µ, π)| ≤ C1 εŠ + C2 εǍ , with the constants C1 and C2 given in Theorem 2.15. Proof. We first claim that for any (µ, π) ∈ S × Π (4.17)

|Q∗ (pjŠ (µ), pjΠ̌ (π)) − Q∗ (µ, π)| ≤ 2(Cr + βL∗ CF ) (1 + ∆A ∆−1 S )εŠ + εǍ .

Indeed, let (µ, π) ∈ S × Π and set µ̌ := pjŠ (µ) and π̌ := pjΠ̌ (π). Then, |Q∗ (µ̌, π̌) − Q∗ (µ, π)| ˆ π̌) − r(µ ⊗ ˆ π)| + β ≤ |r(µ̌ ⊗

Z sup 0 p∈Bm,q (b p ε0 )

ˆ π̌, e0 )) − v ∗ (F(µ ⊗ ˆ π, e0 )) p(de0 ) v ∗ (F(µ̌ ⊗

ˆ π̌, µ ⊗ ˆ π) ≤ 2(Cr + βL∗ CF )W1 (µ̌ ⊗ ≤ 2(Cr + βL∗ CF ) (1 + ∆A ∆−1 S )W1 (µ̌, µ) + dΠ (π̌, π) ∗ ≤ 2(Cr + βL CF ) (1 + ∆A ∆−1 S )εŠ + εǍ .

The second inequality follows from the apriori estimates for r and F given in Remark 2.3 , together with the L∗ -Lipschitz continuity of v ∗ (see Proposition 2.4). The third inequality follows from Lemma 4.8 (ii), and the last inequality follows from the definition of (µ̌, π̌) = (pjŠ (µ), 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 × Π |Q̌∗ (pjŠ (µ), pjΠ̌ (π)) − Q∗ (µ, π)| ≤ |Q∗ (pjŠ (µ), pjΠ̌ (π)) − Q∗ (µ, π)| + |Q̌∗ (pjŠ (µ), pjΠ̌ (π)) − Q∗ (pjŠ (µ), pjΠ̌ (π))| ≤ C1 εŠ + C2 ε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.

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

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ˇ∥ := max |fˇ(µ̌, π̌)| for any mapping fˇ : Š × Π̌ → R. Š×Π̌

(µ̌,π̌)∈Š×Π̌

The first lemma establishes the existence of the maximizer λ∗t,(µ̌,π̌) in (2.10) for any (µ̌, π̌) ∈ Š×Π̌ and t ≥ 0, and provides uniform-in-time bounds for the maximizers (λ∗t,(·,·) )t≥0 and the Q-functions (Q̌t )t≥0 introduced in Framework 2.9 (iii). Lemma 5.1. Suppose that Assumptions 2.2 (i),(ii) 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 ≥ 0 and (µ̌, π̌) ∈ Š × Π̌, (i) There exists a maximizer λ∗t,(µ̌,π̌) of Φt,(µ̌,π̌) in (2.10). (ii) All maximizers λ∗t,(µ̌,π̌) of Φt,(µ̌,π̌) satisfy λ∗t,(µ̌,π̌) ≤ 2Q̌mmax . q (iii) ∥Q̌t ∥Š×Π̌ ≤ Q̌max . Proof. We first consider the synchronous case under Framework 2.9 (i),(iii). (Step 1) Assume first that ∥Q̌t ∥Š×Π̌ ≤ Q̌max for some t ≥ 0. We first show the existence of the maximizer λ∗t,(µ̌,π̌) in (2.10) for any (µ̌, π̌) ∈ Š × Π̌. To see this, we recall the definition of Jt,(µ̌,π̌) in (2.9). For λ ≥ 0 and e0 ∈ E 0 , it holds that 0 ′ 0 0 q Q̌ ( F̌(µ̌, π̌, ẽ ), π̌ + λ|e − ẽ | . −(−Jt,(µ̌,π̌) )λ (e0 ) = min max t 0 0 ẽ ∈E

π̌ ′ ∈Π̌

Since E is finite, the map ∋ λ 7→ −(−Jt,(µ̌,π̌) )λ (e0 ) is concave and continuous for any e0 ∈ E 0 . Moreover, since for every λ ≥ 0 and e0 ∈ E 0 (5.1)

(−Jt,(µ̌,π̌) )λ (e0 ) ≤ ∥Q̌t ∥Š×Π̌ + λ min |e0 − ẽ0 |q ≤ Q̌M , 0 0 ẽ ∈E

the map ϕt,(µ̌,π̌) (·) in (2.10) is continuous and satisfies (5.2)

ϕt,(µ̌,π̌) (λ) ≤ Q̌max − mq λ =: ϕ(λ)

for all λ ≥ 0.

This implies lim supλ→∞ ϕt,(µ̌,π̌) (λ) = −∞. Therefore, λ∗t,(µ̌,π̌) exists for any (µ̌, π̌) ∈ Š × Π̌. Then we show the upper bound for λ∗t,(µ̌,π̌) . To see this, we note that for any (µ̌, π̌) ∈ Š × Π̌ (5.3)

Φt,(µ̌,π̌) ≥ ϕt,(µ̌,π̌) (0) = min Jt,(µ̌,π̌) (ẽ0 ) ≥ −∥Q̌t ∥Š×Π̌ ≥ −Q̌max . 0 0 ẽ ∈E

Since ϕ(λ) = −Q̌max < 0 with λ := 2Q̌mmax , we have by (5.2) that for every λ ≥ λ, q ϕt,(µ̌,π̌) (λ) ≤ ϕ(λ) ≤ −Q̌max . Combining this with (5.3) yields that λ∗t,(µ̌,π̌) ≤ λ for any (µ̌, π̌) ∈ Š × Π̌. (Step 2) We now establish the bounds for λ∗t,(µ̌,π̌) and Q̌t inductively over time t ≥ 0: The claim holds at t = 0 by assumption, hence we have by Step 1 that for any (µ̌, π̌) ∈ Š × Π̌, λ∗0,(µ̌,π̌) ≤ λ. Fix t ≥ 0 and suppose ∥Q̌t ∥Š×Π̌ ≤ Q̌max . Then for any (µ̌, π̌) ∈ Š × Π̌, we have ∗ ˆ π̌)| − β(−Jt,(µ̌,π̌) )λt,(µ̌,π̌) (ε0t+1,(µ̌,π̌) ) Q̌t+1 (µ̌, π̌) ≤ (1 − αt,(µ̌,π̌) )|Q̌t (µ̌, π̌)| + αt,(µ̌,π̌) |r(µ̌ ⊗ ∗ (5.4) ≤ (1 − αt,(µ̌,π̌) )Q̌max + αt,(µ̌,π̌) Cr,∞ + β (−Jt,(µ̌,π̌) )λt,(µ̌,π̌) (ε0t+1,(µ̌,π̌) )

≤ (1 − αt,(µ̌,π̌) )Q̌max + αt,(µ̌,π̌) (Cr,∞ + β 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,(µ̌,π̌) ≤ λ, we have for any (µ̌, π̌) ∈ Š × Π̌, Q̌t+1 (µ̌, π̌) ≥ − (1 − αt,(µ̌,π̌) )|Q̌t (µ̌, π̌)| h i ∗ ˆ π̌)| + β − (−Jt,(µ̌,π̌) )λt,(µ̌,π̌) (ε0t+1,(µ̌,π̌) ) − mq λ∗t,(µ̌,π̌) + αt,(µ̌,π̌) − |r(µ̌ ⊗ ∗ ≥ − (1 − αt,(µ̌,π̌) )Q̌max − αt,(µ̌,π̌) Cr,∞ + β (−Jt,(µ̌,π̌) )λt,(µ̌,π̌) (ε0t+1,(µ̌,π̌) ) + βmq λ∗t,(µ̌,π̌) ≥ − (1 − αt,(µ̌,π̌) )Q̌max − αt,(µ̌,π̌) (Cr,∞ + 3β Q̌max ) = −Q̌max , C

r,∞ where the last equality holds because Q̌max = 1−3β with β < 13 (see Assumption 2.12 (i)). Combining this with (5.4) yields ∥Q̌t+1 ∥Š×Π̌ ≤ Q̌max . By induction, the estimate in (iii) for Q̌t holds for all t and (µ̌, π̌) ∈ Š × Π̌. Step 1 then ensures that the other estimate in (ii) λ∗t,(µ̌,π̌) hold for all t and (µ̌, π̌) ∈ 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̌ × Π̌ in Framework 2.9 (ii). Therefore, the arguments of Steps 1 and 2 can directly be applied also for the asynchronous case, yielding the existence of (λ∗t,(·,·) )t≥0 and the bounds for (λ∗t,(·,·) )t≥0 and (Q̌t )t≥0 given in (ii) and (iii). This completes the proof. □

Using Remark 2.10 (ii), we can rewrite the update rule (2.8) in the standard form of stochastic iterative algorithms considered in [11]: for every t ≥ 0 and (µ̌, π̌) ∈ Š × Π̌, Q̌t+1 (µ̌, π̌) = (1 − αt,(µ̌,π̌) )Q̌t (µ̌, π̌) + αt,(µ̌,π̌) ȞQ̌t (µ̌, π̌) + βZt+1,(µ̌,π̌) , h i (5.5) ∗ where Zt+1,(µ̌,π̌) := − (−Jt,(µ̌,π̌) )λt,(µ̌,π̌) (ε0t+1,(µ̌,π̌) ) − mq λ∗t,(µ̌,π̌) − Φt,(µ̌,π̌) , where the operator Ȟ on the set {Q̌ : Š × Π̌ → R} is defined by setting for every (µ̌, π̌) ∈ Š × Π̌, Z 0 ′ ˆ π̌) + β (5.6) ȞQ̌(µ̌, π̌) := r(µ̌ ⊗ max Q̌ F̌(µ̌, π̌, e ), π̌ p(de0 ). inf 0 p∈Bm,q (b p ε0 )

E 0 π̌ ′ ∈Π̌

Next we let F̌0 := (F̌t0 )t≥0 be defined by (5.7)

F̌t0 := σ ε0s,(µ̌,π̌) : (µ̌, π̌) ∈ Š × Π̌, 1 ≤ s ≤ t ,

t ≥ 1,

with F̌00 := {∅, Ω0 }.

Remark 5.2. By definition of Q̌∗ in (4.7) and the operator Ȟ in (5.6), we have Q̌∗ = ȞQ̌∗ . b0 ) introduced in Framework 2.9 and the Remark 5.3. Recall the probability space (Ω0 , F 0 , P 0 filtration F̌ defined in (5.7). The following hold for every t ≥ 0 and every (µ̌, π̌) ∈ Š × Π̌. 0 (i) The random variable Zt+1,(µ̌,π̌) in (5.5) is F̌t+1 -measurable, ∗ λt,(µ̌,π̌) ∗ 0 : E → R are F̌t0 -measurable. (ii) Φt,(µ̌,π̌) , λt,(µ̌,π̌) , and (−Jt,(µ̌,π̌) ) Leveraging the convex duality result in Lemma 2.8, and the uniform-in-time bound result for (Q̌t )t≥0 in Lemma 5.1, it is possible to show that Zt+1,(·,·) defined in (5.5) is bounded and has conditional zero mean with respect to F̌t0 in (5.7). Lemma 5.4. Suppose that Assumptions 2.2 (i),(ii) 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 ≥ 0 and (µ̌, π̌) ∈ Š × Π̌, b0

EP [Zt+1,(µ̌,π̌) |F̌t0 ] = 0

b0 -a.s., P

and

|Zt+1,(µ̌,π̌) | ≤ 4Q̌max .

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK b0

b0 -a.s.. As a consequence, we also obtain that VarP [Zt+1,(µ̌,π̌) |F̌t0 ] ≤ 16Q̌2max P Proof. The proof presented below applies to both the synchronous and asynchronous versions. Let t ≥ 0 and (µ̌, π̌) ∈ Š × Π̌. By the definition of Zt+1,(µ̌,π̌) in (5.5) and the F̌t0 -measurability b0 -a.s., of Φt,(µ̌,π̌) and λ∗t,(µ̌,π̌) in (2.10) (see Remark 5.3 (ii)), we have that P h i ∗ b0 b0 (5.8) EP [Zt+1,(µ̌,π̌) |F̌t0 ] + Φt,(µ̌,π̌) = EP − (−Jt,(µ̌,π̌) )λt,(µ̌,π̌) (ε0t+1,(µ̌,π̌) ) F̌t0 − mq λ∗t,(µ̌,π̌) =: I . ∗

Moreover, since (−Jt,(µ̌,π̌) )λt,(µ̌,π̌) : E 0 → R is Ft0 -measurable (see Remark 5.3 (ii)) and the family (ε0t,(µ̌,π̌) )t≥1,(µ̌,π̌)∈Š×Π̌ ⊆ E 0 , is independent and identically distributed according to the b0 -a.s., law pbε0 (see Framework 2.9), we have by Remark 2.10 (ii) (see also Lemma 2.8) that P Z ∗ I= − (−Jt,(µ̌,π̌) )λt,(µ̌,π̌) (e0 ) pbε0 (de0 ) − mq λ∗t,(µ̌,π̌) = ϕt,(µ̌,π̌) (λ∗t,(µ̌,π̌) ) = Φt,(µ̌,π̌) , E0

where the last two equalities follow from definition of λ∗t,(µ̌,π̌) and (2.10). b0 b0 -a.s.. Combining this with (5.8) yields that EP [Zt+1,(µ̌,π̌) |F̌ 0 ] = 0 P t

Next we show that |Zt+1,(µ̌,π̌) | ≤ 4Q̌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,(µ̌,π̌) (ε0t+1,(µ̌,π̌) ) + mq λ∗t,(µ̌,π̌) +

Z sup 0 p∈Bm,q (b p0 )

max Q̌t (F̌(µ̌, π̌, e0 ), π̌ ′ ) p(de0 )

E 0 π̌ ′ ∈Π̌

≤ 3Q̌max + ∥Q̌t ∥Š×Π̌ ≤ 4Q̌max . b0 b0 b0 -a.s.. Last, we have VarP [Zt+1,(µ̌,π̌) |F̌t0 ] = EP [|Zt+1,(µ̌,π̌) |2 |F̌t0 ] ≤ 16Q̌2max P

□

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 established in Lemma 5.1 (iii), together with the properties of (Zt+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̌ × Π̌ b0 -a.s., lim |Q̌t (µ̌, π̌) − Q̌∗ (µ̌, π̌)| = 0 P

t→∞

where 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 on a probability measure e satisfying, for every t ≥ 0 and (x, y) ∈ X × Y e F, e P), space (Ω, e ∆t+1 (x, y) = 1 − αt (x, y) ∆t (x, y) + αt (x, y)Ft (x, y) P-a.s.. Let (Fet )t≥0 ⊆ Fe be a sequence of increasing σ-algebras such that ∆0 (x, y) and α0 (x, y) are Fe0 measurable for all (x, y) ∈ X ×Y , whereas ∆t (x, y), αt (x, y), and Ft−1 (x, y) are Fet -measurable for e all t ≥ 1 and (x, y) ∈ X ×Y . Furthermore, assume that for every t ≥ 0 and (x, y) ∈ X ×Y , P-a.s., P∞ P∞ 2 (i) 0 ≤ αt (x, y) ≤ 1, t=0 αt (x, y) = ∞, and t=0 αt (x, y) < ∞. e (ii) There exists some constant δ ∈ (0, 1) such that ∥EP [Ft (·, ·)|Fet ]∥X×Y ≤ δ ∥∆t ∥X×Y , where we denote by ∥f ∥X×Y := max(x,y)∈X×Y |f (x, y)| for any mapping f : X × Y → R.

29 e (iii) There exists some constant C > 0 such that ∥VarP [Ft (·, ·)|Fet ]∥X×Y ≤ C(1 + ∥∆t ∥2X×Y ), e Then limt→∞ ∆t (x, y) = 0 P-a.s. for any (x, y) ∈ X × Y .

Recalling the iterative Q-functions (Q̌t )t≥0 given in Framework 2.9 (iii) and the discretized optimal Q-function Q̌∗ given in (4.7), we define, for every t ≥ 0 and (µ̌, π̌) ∈ Š × Π̌, ˇ t (µ̌, π̌) := Q̌t (µ̌, π̌) − Q̌∗ (µ̌, π̌). ∆

(5.9)

By Remark 5.2 and (5.5), we can rewrite the update rule (2.8) as follows: for every t ≥ 0 and (µ̌, π̌) ∈ Š × Π̌, ˇ t+1 (µ̌, π̌) = (1 − αt,(µ̌,π̌) )∆ ˇ t (µ̌, π̌) + αt,(µ̌,π̌) F̌t (µ̌, π̌), ∆

(5.10)

where F̌t (µ̌, π̌) := ȞQ̌t (µ̌, π̌) − ȞQ̌∗ (µ̌, π̌) + βZt+1,(µ̌,π̌) .

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 ≥ 0 and (µ, π) ∈ S × Π, |Q̌t (pjŠ (µ), pjΠ̌ (π)) − Q∗ (µ, π)| (5.11)

≤ |Q̌t (pjŠ (µ), pjΠ̌ (π)) − Q̌∗ (pjŠ (µ), pjΠ̌ (π))| + |Q̌∗ (pjŠ (µ), pjΠ̌ (π)) − Q∗ (µ, π)| ˇ t∥ ≤ ∥∆ + C1 ε + C2 ε . Š×Π̌

Š

Ǎ

ˇ t (µ̌, π̌), αt,(µ̌,π̌) , F̌t (µ̌, π̌)) Thus, it suffices to show that (∆ t≥0,(µ̌,π̌)∈Š×Π̌ in (5.9) and (5.10) satisfy b0 -a.s. as t → ∞. ˇ t (µ̌, π̌) → 0 P all the conditions of Lemma 5.5, so that for any (µ̌, π̌) ∈ Š × Π̌, ∆ We first consider the synchronous version of the Q-learning algorithm. (Measurability) The synchronous learning rates (αt,(µ̌,π̌) )t≥0,(µ̌,π̌)∈Š×Π̌ in Framework 2.9 (i) are ˇ t (µ̌, π̌) and deterministic. Moreover, from Remark 5.3, we have for every (µ̌, π̌) ∈ Š × Π̌ that ∆ ˇ 0 (µ̌, π̌) is F̌ 0 -measurable. F̌t−1 (µ̌, π̌) are F̌t0 -measurable for any t ≥ 1, while ∆ 0 (Learning rates) Since αt,(µ̌,π̌) = (t + 1)−w for t ≥ 0 with w ∈ ( 21 , 1), for any (µ̌, π̌) ∈ Š × Π̌ ∞ X

αt,(µ̌,π̌) =

t=0

∞ X

(t + 1)−w = ∞

t=0

and

∞ X

2 αt,(µ̌,π̌) =

t=0

∞ X

(t + 1)−2w < ∞.

t=0

(Mean estimate of F̌t ) We note that for any t ≥ 0 and (µ̌, π̌) ∈ Š × Π̌ |ȞQ̌t (µ̌, π̌) − ȞQ̌∗ (µ̌, π̌)| Z ≤β sup max Q̌t (F̌(µ̌, π̌, e0 ), π̌ 1 ) − max Q̌∗ (F̌(µ̌, π̌, e0 ), π̌ 2 ) p(de0 ) 0 p∈Bm,q (b pε0 )

(5.12)

Z ≤β

sup 0 p∈Bm,q (b pε0 )

π̌ 1 ∈Π̌

π̌ 2 ∈Π̌

max Q̌t (F̌(µ̌, π̌, e0 ), π̌ 1 ) − Q̌∗ (F̌(µ̌, π̌, e0 ), π̌ 1 ) p(de0 )

E 0 π̌ 1 ∈Π̌

ˇ t∥ ≤ β∥∆ Š×Π̌ . b0 -a.s., Combining this with Lemma 5.4 yields that for any t ≥ 0 and (µ̌, π̌) ∈ Š × Π̌, P b0

(5.13)

EP [F̌t (µ̌, π̌)|F̌t0 ] = EP [ȞQ̌t (µ̌, π̌) − ȞQ̌∗ (µ̌, π̌)|F̌t0 ] b0 ˇ t∥ ≤ EP |ȞQ̌t (µ̌, π̌) − ȞQ̌∗ (µ̌, π̌)| F̌t0 ≤ β∥∆ Š×Π̌ .

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

b0 -a.s., Combining this with (5.13) yields that for any t ≥ 0, P b0

(5.14)

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̌ × Π̌ used in its definition is pre-sampled. Moreover, under Assumption 2.12 (ii), for any (µ̌, π̌) ∈ Š × Π̌, the set T(µ̌,π̌) in (2.5) satisfies |T(µ̌,π̌) | = ∞. Thus, we may P∞ enumerate the times in T(µ̌,π̌) as a strictly increasing sequence (tk )k≥0 such that t=0 αt,(µ̌,π̌) = P P P∞ P∞ ∞ ∞ 2 −w = ∞ and t=0 αt,(µ̌,π̌) = k=0 (k + 1)−2w < ∞. k=0 (k + 1) k=0 αtk ,(µ̌,π̌) = 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),(iii). 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 defined in (5.9) is controlled epoch-wise. Each epoch accounts for the covering time Tcov in (∆ ˇ t )t≥0 decays inductively over epochs Assumption 2.12 (ii). The epochs are constructed so that (∆ in the following way. ˇ t )t≥0 is decomposed into deterministic and stochastic components. The deThe process (∆ terministic component vanishes inductively across epochs, whereas the stochastic component is b0 -martingale difference terms characterized by (Zt+1,(·,·) )t≥0 defined represented as a sum of P in (5.5). Since (Zt+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 ∗ of the order of a sufficiently large epoch, we obtain that for every T ≥ T ∗ , ∗ b b0 ∥∆ ˇT∥ P b ≥ 1 − δ, Š×Π̌ = ∥Q̌T − Q̌ ∥Š×Π̌ ≤ ε where εb > 0 and δb ∈ (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̌ ) 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),(ii) with only minor modifications. The synchronous case is briefly elaborated at the end of the proof. Definition 5.6. Let Assumption 2.12 (ii) hold. Recall that w ∈ ( 21 , 1) is the exponent of the asynchronous learning rates and (µ̌t , π̌t )t≥0 ⊆ Š×Π̌ is the sampled trajectory in Framework 2.9 (ii). Fix κ̌ ∈ (0, 1) and let č ≥ 1. (i) Set τ0 := 0. For any n ≥ 1 and any ť ≥ 1, define č w τn+1;ť := τn;ť + Tcov τn; , with τ1;ť := ť, κ̌ ť where Tcov > 1 is the covering time given in Assumption 2.12 (ii), and ť represents the initial epoch’s length.

(ii) For any 0 ≤ t1 < t2 and (µ̌, π̌) ∈ Š × Π̌, define t1 ,t2 := {t ∈ [t1 , t2 ) : (µ̌, π̌) = (µ̌t , π̌t )} ⊆ T(µ̌,π̌) , T(µ̌,π̌)

with the set T(µ̌,π̌) defined in (2.5). (iii) For any n ≥ 1, define Dn+1 := (1 − β̌)n D1 , where D1 := 2Q̌max and β̌ := 1−β 2 . We first collect some elementary properties of the notions introduced in Definition 5.6 (i),(ii) and the learning rates in Framework 2.9 (ii). Lemma 5.7. Let Assumption 2.12 (ii) hold. Then for any ť ≥ 1, the sequence (τn;ť )n≥0 given in Definition 5.6 (i) satisfy, for every n ≥ 0, τ

ť ť ť w ≤ ⌈ Tn; ⌉ + ⌊ κ̌č τn; + 1. (i) Tn; ⌋ ≤ Tn+1; ť cov cov cov 1−w č 1−w (ii) τn+1;ť ≤ ť + n(1 − w)(Tcov κ̌ + ť−w ).

Moreover, for every n ≥ 1, t ∈ [τn+1;ť , τn+2;ť ), and (µ̌, π̌) ∈ Š × Π̌, τ

n;ť w (iii) |T(µ̌,π̌) | ≥ ⌊ κ̌č τn; ⌋. ť

n;ť ť ⌋ + 1)−w . (iv) Let i ∈ T(µ̌,π̌) be the smallest element in the set. Then αi,(µ̌,π̌) ≤ (⌊ Tn; cov

ť ť w Proof. For (i), the inequality Tn; ≤ ⌈ Tn; ⌉ + ⌊ κ̌č τn; ⌋ is obvious, while the other inequality follows ť cov cov from the definition of τn+1;ť in Definition 5.6 (i). Indeed, for any n ≥ 0

w w τn;ť + Tcov ⌊ κ̌č τn; τn;ť + ⌈Tcov κ̌č τn; ⌋ ⌉ τn;ť τn+1;ť č w ť ť τn;ť ≤ + +1≤ +1= + 1. Tcov κ̌ Tcov Tcov Tcov

For (ii), since by the concavity of the map R+ ∋ x → x1−w ∈ R+ , for any n ≥ 0, 1−w č w 1−w 1−w 1−w τn+1;ť − τn;ť ≤ τn;ť + Tcov τn;ť + 1 − τn; ť κ̌ č č w −w −w ≤ (1 − w)τn . Tcov τn + 1 ≤ (1 − w) Tcov + τ1 κ̌ κ̌ Hence, the desired estimate follows by iterating this inequality over n ≥ 0. For (iii), by Assumption 2.12 (ii), for every n ≥ 1, t ∈ [τn+1 , τn+2 ), and (µ̌, π̌) ∈ Š × Π̌, č w τn+1 − τn τn ,τn+1 τn ,t |T(µ̌,π̌) | ≥ |T(µ̌,π̌) | ≥ ≥ τ . Tcov κ̌ n τn ,t Last, for (iv), let n ≥ 1, t ∈ [τn+1 , τn+2 ), and (µ̌, π̌) ∈ Š × Π̌. Since i ∈ T(µ̌,π̌) satisfies i ≥ τn , n by Assumption 2.12 (ii), it holds that Ni,(µ̌,π̌) ≥ ⌊ Tτ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 (ii) hold. Let ň ≥ 1 be given. If the initial epoch length ť satisfies 1 1 2Tcov κ̌č w(ň − 1) 1−w 2ň + 1 w ť ≥ max , ,1 , log 2 2Tcov κ̌č then it holds that τň+2;ť − 1 ≥ τň;ť+1 .

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

Proof. For notational simplicity, set Č := Tcov č/κ̌, and write, for every n ≥ 1, dn := τn;ť+1 − τn;ť Then, it holds that for every n ≥ 1 (5.15)

w w w w dn+1 = τn;ť+1 + ⌈Čτn; ť+1 ⌉ − (τn;ť + ⌈Čτn;ť ⌉) ≤ dn + Č(τn;ť+1 − τn;ť ) + 1 w−1 ≤ dn (1 + Čwτn; ) + 1, ť

where the last inequality follows from the concavity of the map R+ ∋ x 7→ xw ∈ R+ . Since d1 = 1, iterating the estimate in (5.15) gives, for every 1 ≤ n ≤ ň, n−1 (5.16) dn ≤ n 1 + Čwťw−1 ≤ n exp Čw(n − 1)ťw−1 ≤ 2n, 1

) 1−w . where the last inequality follows from the condition on ť, namely, ť ≥ ( 2Čw(ň−1) log 2 On the other hand, w w τň+2;ť − 1 − τň;ť = ⌈Čτň; ť ⌉ + ⌈Čτň+1;ť ⌉ − 1

(5.17)

≥ 2Č ťw − 1 ≥ 2ň, 1

)w . where the last inequality follows from the condition on ť, namely, ť ≥ ( 2ň+1 2Č Combining (5.16) and (5.17) leads to τň+2;ť − 1 ≥ τň;ť + 2ň ≥ τň;ť + dň = τ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: Qt2 −t1 (i) For any w̃ ∈ (0, 1) and t1 , t2 ∈ N with t2 > t1 , i=t (1 − (i + 1)−w̃ ) ≤ exp(− (tt22+1) w̃ ). 1 2A A (ii) For any a > 0 satisfying 2a log a > 1, and any A > 2a log a, A exp(− a ) ≤ exp(− a ). Proof. Since 1 − x ≤ ex for all x ∈ [0, 1], we obtain (i), namely, X t2 t2 Y t2 − t 1 −w̃ −w̃ (i + 1) ≤ exp − (1 − (i + 1) ) ≤ exp − , (t2 + 1)w̃ i=t i=t 1

−w̃

where the last inequality holds because (i + 1) ≥ (t2 + 1)w̃ for all i = t1 , . . . , t2 . For (ii), let a > 0 satisfy 2a log a > 1. For each A ∈ (2a log a, +∞), define ϕ(A) := A a − log A, and show that ϕ ≥ 0 on the interval. ∗ Since ϕ′ (A) = a1 − A1 = A−a aA , ϕ attains the minimum at A = max{a, 2a log a}. Thus it suffices to verify that ϕ(A∗ ) ≥ 0. Suppose that A∗ = a. Then, since ϕ(a) = 1 − log a and 2a log a ≤ a, we have ϕ(A∗ ) ≥ 21 > 0. a Otherwise (i.e., A∗ = 2a log a), since ϕ(A∗ ) = log( 2 log a ), it suffices to show a ≥ 2 log a. ′ Define ψ(x) := x − 2 log x for x > 0. Then ψ (x) = 1 − x2 = x−2 x , so ψ attains the minimum at x = 2. Since ψ(2) = 2 − 2 log 2 > 0, we conclude ψ(x) > 0 for all x > 0, and thus a > 2 log a. A Therefore ϕ(A) ≥ 0 for all A > 2a log a, which implies A exp(− 2A □ a ) ≤ exp(− a ). Lemma 5.10. Suppose that Assumptions 2.2 (i),(ii) and 2.12 (i) are satisfied. Let (Zt+1,(·,·) )t≥0 ˇ t )t≥0 be given in (5.5) and (5.9), respectively. Let ť ≥ 1 be given. Let (τn;ť )n≥0 and (Dn )n≥1 and (∆ be given in Definition 5.6. Moreover, for any n ≥ 1, let (Wt;n , Yt;n )t≥τn;ť be sequences of mappings defined for every t ≥ τn;ť and (µ̌, π̌) ∈ Š × Π̌ by (5.18)

Wt+1;n (µ̌, π̌) := (1 − αt,(µ̌,π̌) )Wt;n (µ̌, π̌) + αt,(µ̌,π̌) βZt+1,(µ̌,π̌) , Yt+1;n (µ̌, π̌) := (1 − αt,(µ̌,π̌) )Yt;n (µ̌, π̌) + αt,(µ̌,π̌) βDn ,

ˇ t∥ with Wτn;ť ;n (µ̌, π̌) := 0 and Yτn;ť ;n (µ̌, π̌) := Dn . If ∥∆ Š×Π̌ ≤ Dn holds for all t ∈ [τn;ť , τn+2;ť ), then we have for every t ≥ τn;ť and (µ̌, π̌) ∈ Š × Π̌ that (5.19)

ˇ t (µ̌, π̌) ≤ Yt;n (µ̌, π̌) + Wt;n (µ̌, π̌). −Yt;n (µ̌, π̌) + Wt;n (µ̌, π̌) ≤ ∆

Proof. The proof uses an induction over t ≥ τn;ť . The estimate (5.19) holds at t = τn;ť because ˇτ ∥ ≤ Dn . Wτn;ť ;n (µ̌, π̌) = 0, Yτn;ť ;n (µ̌, π̌) = Dn and ∥∆ n;ť Š×Π̌ Assume that the estimate holds for some t ≥ τn;ť . Let (µ̌, π̌) ∈ Š × Π̌ be given. ˇ t∥ Since ȞQ̌∗ = Q̌∗ (see Remark 5.2), by the assumption that ∥∆ Š×Π̌ ≤ Dn , the upper bound in (5.19), and the estimate in (5.12), we have ˇ t+1 (µ̌, π̌) = (1 − αt,(µ̌,π̌) )∆ ˇ t (µ̌, π̌) + αt,(µ̌,π̌) ȞQ̌t (µ̌, π̌) − ȞQ̌∗ (µ̌, π̌) + βZt+1,(µ̌,π̌) ∆ ≤ (1 − αt,(µ̌,π̌) )Yt;n (µ̌, π̌) + Wt+1;n (µ̌, π̌) + αt,(µ̌,π̌) (ȞQ̌t (µ̌, π̌) − ȞQ̌∗ (µ̌, π̌)) ˇ t∥ ≤ (1 − αt,(µ̌,π̌) )Yt;n (µ̌, π̌) + Wt+1;n (µ̌, π̌) + αt,(µ̌,π̌) β∥∆ Š×Π̌

≤ Yt+1;n (µ̌, π̌) + Wt+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̌∗ (µ̌, π̌)) ∆ ˇ t∥ ≥ Wt+1;n (µ̌, π̌) − (1 − αt,(µ̌,π̌) )Yt;n (µ̌, π̌) − αt,(µ̌,π̌) β∥∆ Š×Π̌

≥ Wt+1;n (µ̌, π̌) − Yt+1;n (µ̌, π̌). Therefore, by the induction hypothesis, the desired bound holds at time t + 1.

□

Lemma 5.11. Suppose that Assumptions 2.2 (i),(ii) and 2.12 are satisfied. Let δ̌ ∈ (0, e − 2) be given. Moreover, assume that the initial epoch’s length ť ≥ 1 and č ≥ 1 in Definition 5.6 satisfy ť ≥ max{ť∗1 , ⌈Tcov (Tcov − 1)−1 ⌉}

and

č ≥ max{č∗1 , 1},

where (5.20)

1 1 ť∗1 := Tcov 2 w (1 − log(2 + δ̌))− w ,

č∗1 :=

log(2 + δ̌) + 2(Tcov /ť∗1 )w . 1 − (log(2 + δ̌) + 2(Tcov /ť∗1 )w )

ˇ t∥ Furthermore, for any n ≥ 1, let (Yt,n )t≥τn;ť be given in (5.18). If ∥∆ Š×Π̌ ≤ Dn holds for all t ∈ {τn;ť , . . . , τn+2;ť − 1}, then for every t ≥ τn+1;ť (5.21)

∥Yt;n ∥Š×Π̌ ≤ (β + 2β̌(2 + δ̌)−1 )Dn .

Proof. Note that (Yt;n )t≥τn;ť can be rewritten for every t > τn;ť and (µ̌, π̌) ∈ Š × Π̌ by Y (5.22) Yt;n (µ̌, π̌) = Dn (β + 2β̌ρt;n (µ̌, π̌)), where ρt;n (µ̌, π̌) := (1 − αi,(µ̌,π̌) ), τ

n;ť i∈T(µ̌,π̌)

with setting ρτn;ť ;n (µ̌, π̌) := (1 − β)Dn and recalling that Yτn;ť ;n = Dn . Then it holds for every t ≥ τn+1;ť and (µ̌, π̌) ∈ Š × Π̌ that τ

ť č w ⌉+⌊ κ̌ τn;ť ⌋−1 ⌈ Tn; cov

ρt;n (µ̌, π̌) ≤ (5.23)

(1 − (i + 1)−w ) ≤ exp(I),

ť i=⌈ Tn; ⌉ cov

−w τn;ť č w č w where I := − τn;ť − 1 + τn;ť . κ̌ Tcov κ̌

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

Here the first inequality follows from Lemma 5.7 (iii), (iv) and the fact that t ≥ τn+1;ť , whereas the second inequality follows from Lemma 5.9 (i). Therefore, it suffices to prove that I ≤ − log(2 + δ̌). By Lemma 5.7 (i), we have −w τn;ť č w č w I≤− τn;ť − 2 + τn;ť κ̌ Tcov κ̌ (5.24) −w w č τn+1;ť 1 Tcov ≤− + +2 := II . κ̌ Tcov τn;ť τn;ť τn;ť Moreover, it holds that w τn;ť + Tcov κ̌č τn; +1 τn+1;ť č 1 1 1 č 1 ť + ≤ + ≤ + + ≤ + 1, Tcov τn;ť τn;ť Tcov τn;ť τn;ť Tcov κ̌ κ̌ ť

where the last inequality follows from the assumption that ť ≥ Tcov (Tcov − 1)−1 . From this and the facts that τn;ť ≥ ť and ǩ, w < 1, we have −w w w Tcov Tcov č č −č +1 +2 +2 (5.25) II ≤ − ≤ ≤ − log(2 + δ̌), κ̌ κ̌ č + 1 ť ť where the last inequality holds because ť ≥ ť∗1 and č ≥ č∗1 (see (5.20)), together with the fact that log(2 + δ̌) < 1 (because of δ̌ ∈ (0, e − 2)). Combining (5.24) and (5.25) yields that I ≤ − log(2 + δ̌), as claimed. □ Next, we define, for every ť ≥ 1, n ≥ 1, t ∈ {τn+1;ť , . . . , τn+3;ť − 1}, l ∈ {−1, 0, · · · , t − 1 − τn;ť }, and (µ̌, π̌) ∈ Š × Π̌, τn;ť +l

l Xt;n (µ̌, π̌) := β

(5.26)

αi,(µ̌,π̌)

t−1 Y

(1 − αj,(µ̌,π̌) ) Zi+1;(µ̌,π̌) ,

l ≥ 0,

j=i+1

i=τn;ť

−1

n+3;ť −1 with Xt;n (µ̌, π̌) := 0. Then the sequence (Wt;n )t=τ given in (5.18) can be rewritten for every n+1;ť t ∈ {τn+1;ť , . . . , τn+3;ť − 1} and (µ̌, π̌) ∈ Š × Π̌ by

t−1−τn;ť t−1−τ Wt;n (µ̌, π̌) = Xt;n n;ť (µ̌, π̌) =

(5.27)

l−1 l Xt;n (µ̌, π̌) − Xt;n (µ̌, π̌) .

l=0

Lemma 5.12. Suppose that Assumptions 2.2 (i),(ii) and 2.12 are satisfied. Recall the probability b0 ) in Framework 2.9 and the filtration F̌0 in (5.7). Then for every ť ≥ 1, n ≥ 1, space (Ω0 , F 0 , P t ∈ {τn+1;ť , . . . , τn+3;ť − 1}, (µ̌, π̌) ∈ Š × Π̌, the following hold. k−1−τ

n;ť (i) For every k ∈ {τn;ť , . . . , t}, Xt;n (µ̌, π̌) in (5.26) is F̌k0 -measurable. k−1−τn;ť b0 -martingale w.r.t. (F̌ 0 )t (ii) (X (µ̌, π̌))t is a P .

t;n

k=τn;ť

k k=τn;ť k−1−τn;ť

k−τ

(iii) For every k ∈ {τn;ť , . . . , t − 1}, |Xt;n n;ť (µ̌, π̌) − Xt;n

(µ̌, π̌)| ≤ 4β Q̌max ( Tτcov )w . n;ť

Proof. Let ť ≥ 1, n ≥ 1, t ∈ [τn+1;ť , τn+3;ť ) and (µ̌, π̌) ∈ Š × Π̌. Indeed, since (αt,(µ̌,π̌) )t≥0 are deterministic for any (µ̌, π̌) ∈ Š × Π̌, we have by Remark 5.3 (ii) that for any k = τn;ť + 1, · · · , t, t−1 k−1 X Y k−1−τn;ť Xt;n (µ̌, π̌) = β αi,(µ̌,π̌) (1 − αj,(µ̌,π̌) ) Zi+1;(µ̌,π̌) i=τn;ť

j=i+1

−1 is F̌k0 -measurable, while Xt;n (µ̌, π̌) = 0 is F̌τ0n;ť -measurable. Thus, Part (i) holds.

b0 -a.s., Parts (ii) and (iii) follow from Lemma 5.4. Indeed, for any k ∈ {τn;ť , . . . , t − 1}, P k−1−τn;ť

k−τ

EP [Xt;n n;ť (µ̌, π̌) − Xt;n = βαk,(µ̌,π̌)

t−1 Y

(µ̌, π̌)|F̌k0 ] b0

(1 − αj,(µ̌,π̌) )EP [Zk+1;(µ̌,π̌) |F̌k0 ] = 0.

j=k+1

Moreover, for any k ∈ {τn;ť , . . . , t − 1}, k−τ

k−1−τn;ť

Xt;n n;ť (µ̌, π̌) − Xt;n

(µ̌, π̌) = βαk,(µ̌,π̌)

t−1 Y

(1 − αj,(µ̌,π̌) ) Zk+1;(µ̌,π̌)

j=k+1

≤ 4β Q̌max αk,(µ̌,π̌) ≤ 4β Q̌max (Tcov /τn;ť )w , τ

ť ť k ⌋ ≥ Tn; − 1 (by the covering time condition where the last inequality holds because N(µ̌,π̌) ≥ ⌊ Tn; cov cov in Assumption 2.12 (ii); 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. e P) e e F, e F, Lemma 5.13. If (Mn )n≥0 is a martingale with M0 = 0 on a filtered probability space (Ω, e and there exists a sequence (cn )n≥1 ⊆ [0, ∞) such that |Mn − Mn−1 | ≤ cn P-a.s. for all n ≥ 1, then Azuma’s inequality holds: λ2 e P P[|Mn | ≥ λ] ≤ 2 exp − for all λ ≥ 0. n 2 k=1 c2k Lemma 5.14. Suppose that Assumptions 2.2 (i),(ii) and 2.12 are satisfied. Recall the probability b0 ) in Framework 2.9 and the filtration F̌0 in (5.7). Then, for any ť ≥ 1, n ≥ 1, space (Ω0 , F 0 , P t ∈ {τn+1;ť , . . . , τn+3;ť − 1}, and (µ̌, π̌) ∈ Š × Π̌, the random variable Wt;n (µ̌, π̌) in (5.18) satisfies λ2 τnw b0 (|Wt;n (µ̌, π̌)| ≥ λ) ≤ 2 exp − , for all λ ≥ 0, P w )2 25 C3 (β Q̌max Tcov where C3 := C(č,κ̌,w,Tcov ) := Tcov κ̌č (7 + 5(Tcov κ̌č )w + (Tcov κ̌č )2w ) + 3. Proof. Let ť ≥ 1, n ≥ 1, t ∈ {τn+1;ť , . . . , τn+3;ť − 1}, and (µ̌, π̌) ∈ Š × Π̌ be given. Note that t−1−τn;ť

Wt;n (µ̌, π̌) = Xt;n

(µ̌, π̌); see (5.27). From this and Lemma 5.12, we apply Azuma’s inequality k−1−τn;ť

(µ̌, π̌))tk=τn;ť to have for all λ ≥ 0 λ2 b0 (|Wt;n (µ̌, π̌)| ≥ λ) ≤ 2 exp − P 2(t − τn;ť )(4β Q̌max ( Tτcov )w )2 n;ť λ2 ≤ 2 exp − . 2(τn+3;ť − τn;ť )(4β Q̌max ( Tτcov )w )2

(see Lemma 5.13) to (Xt;n

n;ť

w Therefore, it suffices to show that τn+3;ť − τn;ť ≤ C3 τn; . From the inequality that (a + b + c)w ≤ ť aw + bw + cw for all a, b, c ≥ 0 (as w < 1), we have w w č č w w b3 τ w , τn+1; ≤ τ + 1 + T (5.28) τ ≤ τ + 1 + T τ ≤C cov cov n;ť ť n;ť n;ť κ̌ n;ť κ̌ n;ť

b3 := 2 + (Tcov č )w > 0. Similarly, we have τ w b3 τ w b2 τ w . where C ≤C ≤C 3 n;ť κ̌ n+2;ť n+1;ť Thus, we have č w č b 2 b w w w w τn+3;ť − τn;ť ≤ Tcov (τn+2; ť + τn+1;ť + τn;ť ) + 3 ≤ Tcov (C3 + C3 + 1)τn;ť + 3 ≤ C3 τn;ť , κ̌ κ̌

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

□

as claimed. This completes the proof.

Lemma 5.15. Suppose that Assumptions 2.2 (i),(ii) and 2.12 are satisfied. Recall D1 = 2Q̌max (see Definition 5.6 (iii)) and let D ∈ (0, D1 ] be such that (5.29)

2a(D) log(a(D)) > 1,

where a(D) := a(č,κ̌,δ̌,w,Tcov ,β) (D) :=

w 2 26 C3 (β Q̌max Tcov ) > 0, −1 2 (δ̌(2 + δ̌) β̌D)

with δ̌ ∈ (0, e − 2) and C3 > 0 given in Lemma 5.11 and Lemma 5.14, respectively. Moreover, assume that the initial epoch’s length ť in Definition 5.6 satisfies l 1m ť ≥ 2a(D) log(a(D)) w . Then for any n ≥ 1 such that Dn ≥ D, the following holds: b0 P

\ n τn+3;ť −1 \

|Wt;n (µ̌, π̌)| < δ̌(2 + δ̌)−1 β̌Dn

≥1−

n=1 t=τn+1;ť (µ̌,π̌)∈Š×Π̌

2|Š||Ǎ||Š| C3 n . exp(ťw /a(D))

Proof. Let n ∈ N be such that Dn ≥ D. Then we have by Lemma 5.14 that b0 P

\ n τn+3;ť −1 \

|Wt;n (µ̌, π̌)| < δ̌(2 + δ̌)−1 β̌Dn

n=1 t=τn+1;ť (µ̌,π̌)∈Š×Π̌

≥1−

n τn+3;ť −1 X X

b0 (|Wt;n (µ̌, π̌)| ≥ δ̌(2 + δ̌)−1 β̌Dn ) P

n=1 t=τn+1;ť (µ̌,π̌)∈Š×Π̌

≥ 1 − 2|Š||Π̌|

n X n=1

č w w w Tcov (τn+2;ť + τn+1;ť ) + 2 exp(−2τn; ť /a(D)) =: I, κ̌

where the last inequality holds because Dn ≥ D for all 0 ≤ n ≤ n. Moreover, using the estimate in (5.28) and the constant C3 > 0 in Lemma 5.14, we have I ≥ 1 − 2|Š||Π̌|C3

n X

w w τn; ť exp(−2τn;ť /a(D)) =: II .

n=1 1

Moreover, since 2a(D) log(a(D)) > 1 and ť ≥ ⌈(2a(D) log(a(D))) w ⌉ by assumption, we apply Lemma 5.9 (ii) to have for every n = 1, · · · , n, w w w w τn; ť exp(−2τn;ť /a(D)) ≤ exp(−τn;ť /a(D)) ≤ exp(−ť /a(D)).

Thus, we conclude the proof by noting that |Π̌| = |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),(iii). The proof consists of four steps, which rely on the following preliminary settings. Let εb > 0 and δb ∈ (0, 1) be given. We first set (5.30)

n∗ := max{⌈β̌ −1 log(2Q̌max εb−1 )⌉, 1}.

Recalling ť∗1 ≥ 1 and č∗1 > 0 introduced in (5.20), we then define (5.31)

č := max{č∗1 , 1}.

Moreover, we define (5.32)

ť∗2 := max

2Tcov κ̌č w(n∗ − 1) log 2

1 1−w 1 2n∗ + 1 w , ,1 . 2Tcov κ̌č

Then by Lemma 5.8, we have for any t ≥ ť∗2 τn∗ +2;ť − 1 ≥ τn∗ ;ť+1 .

(5.33)

In what follows, we construct the (least) initial epoch length 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̌∗ . To this end, we let σ ∗ ∈ (0, 1) be so that (5.34)

Dn∗ < εb,

Dn∗ ≥ σ ∗ εb,

and

2a(σ ∗ εb) log(a(σ ∗ εb)) > 1,

where a(σ ∗ εb) > 0 is defined as in (5.29) (with replacing D by σ ∗ εb therein), we define ť∗ ≥ 1 by (5.35)

ť∗ := max{ť∗1 , ⌈Tcov (Tcov − 1)−1 ⌉, ť∗2 , ť∗3 , ť∗4 },

where ť∗1 and ť∗2 are given in (5.20) and (5.32), respectively, ť∗3 and ť∗4 are given by 1 ť∗3 := 2a(σ ∗ εb) log(a(σ ∗ εb)) w , (5.36) 2|Š||Ǎ||Š| C n∗ w1 3 ∗ ∗ ť4 := a(σ εb) log , b δ with the constant C3 > 0 given in Lemma 5.14, which depends on the constant č ≥ 1 in (5.31). Last, define, for every ť ≥ ť∗ and k ≥ 1, τk+3;ť −1

Ik (ť) :=

ˇ t∥ ∥∆ Š×Π̌ < Dk+1 ,

t=τk+1;ť τk+3;ť −1

Jk (ť) :=

|Wt;k (µ̌, π̌)| ≤ δ̌(2 + δ̌)−1 β̌Dk .

t=τk+1;ť (µ̌,π̌)∈Š×Π̌

Step 1. We claim that for any ť ≥ ť∗ and n ≥ 1, ∩nk=1 Jk (ť) ⊆ ∩nk=1 Ik (ť). Let ť ≥ ť∗ be given. We first show that J1 (ť) ⊆ I1 (ť), i.e., the case n = 1. By Lemma 4.9 and Lemma 5.1 (iii), we have that for every t ∈ {τ1;ť , . . . , τ3;ť − 1}, ∗ ˇ t∥ ∥∆ Š×Π̌ ≤ ∥Q̌t ∥Š×Π̌ + ∥Q̌ ∥Š×Π̌ ≤ D1 = 2Q̌max .

Moreover, since ť ≥ {ť∗1 , ⌈Tcov (Tcov − 1)−1 ⌉} and č = max{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̌ and (µ̌, π̌) ∈ Š × Π̌ ˇ t (µ̌, π̌)| ≤ Yt;1 (µ̌, π̌) + |Wt;1 (µ̌, π̌)| ≤ (β + 2β̌(2 + δ̌)−1 )D1 + |Wt;1 (µ̌, π̌)|, |∆ where the first inequality holds because (Yt;1 )t≥τ1;ť is nonnegative (see (5.18)). Moreover, since (β + 2β̌(2 + δ̌)−1 )D1 + δ̌(2 + δ̌)−1 β̌D1 = (1 − β̌)D1 = D2 (see Definition 5.6), we have J1 (ť) ⊆ I1 (ť), as claimed. ˇ t∥ Inductively, on I1 (ť), we have ∥∆ Š×Π̌ ≤ D2 for every t ∈ {τ2;ť , . . . , τ4;ť − 1}. Repeating the arguments for the case n = 1 with (D2 ; {τ2;ť , . . . , τ4;ť − 1}) in place of (D1 ; {τ1;ť , . . . , τ3;ť − 1}), we obtain J2 (ť) ⊆ I2 (ť) on I1 (ť), and hence J2 (ť) ∩ I1 (ť) ⊆ I1 (ť) ∩ I2 (ť). Combining this with J1 (ť) ⊆ I1 (ť), we have J1 (ť) ∩ J2 (ť) ⊆ I1 (ť) ∩ I2 (ť). By using the same arguments presented for the case n = 2 inductively, we have the desired inclusion property for any n ≥ 1. Moreover, since ť ≥ ť∗ is arbitrary, the claim follows.

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

Step 2. Recalling that Dn∗ ≤ εb (by definition of n∗ in (5.30)), we have by Step 1 that for any ť ≥ ť∗ τn∗ +2; \ť −1 0 b b0 In∗ −1 (ť) ˇ P ∥∆t ∥Š×Π̌ < εb ≥ P (5.37)

t=τn∗ ;ť

≥P

∗ n\ −1

Ik (ť)

≥P

∗ n\ −1

k=1

Jk (ť)

b ť). =: P(

k=1

Since Dn ≥ σ ∗ εb for any n = 1, . . . , n∗ , and 2a(σ ∗ εb) log(a(σ ∗ εb)) > 1 (see (5.34)) and ť ≥ ť∗3 (see (5.35), (5.36)), we can apply Lemma 5.15 to have, for every ť ≥ ť∗ , |Š|

∗

b b ť) ≥ 1 − 2|Š||Ǎ| C3 n ≥ 1 − δ, P( exp(ťw /a(σ ∗ εb)) where the last inequality follows from ť ≥ ť∗4 ; see (5.35), (5.36). Step 3. Using n∗ and ť∗ (see (5.30), (5.35)), we define T ∗ := τn∗ ;ť∗ . Since (5.33) holds for all t ≥ ť∗ (by definition of ť∗ in (5.35)), it holds that for all m ≥ 0 {τn∗ ;ť∗ +m , . . . , τn∗ +2;ť∗ +m − 1} ∩ {τn∗ ;ť∗ +m+1 , . . . , τn∗ +2;ť∗ +m+1 − 1} ̸= ∅. Hence, for any T ≥ T ∗ , there exists mT ≥ 0 such that T ∈ {τn∗ ;ť∗ +mT , . . . , τn∗ +2;ť∗ +mT − 1}. From this, we have by Step 2 and Step 3 that for any T ≥ T ∗ , ∗ +m −1 τn∗ +2;ť\ T 0 ∗ 0 0 b b b ˇ ˇ P (∥Q̌T − Q̌ ∥Š×Π̌ ≤ εb) = P (∥∆T ∥Š×Π̌ ≤ εb) ≥ P ∥∆t ∥Š×Π̌ < εb (5.38) t=τn∗ ;ť∗ +m T

b b ť∗ + mT ) ≥ 1 − δ. ≥ P( 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̌∗ . To this end, we note that6 ť∗1 = Θ(Tcov ) and č∗1 = Θ(1) (see (5.20)), hence č in (5.31) satisfies č = Θ(1). Recall that a(σ ∗ εb) is given in (5.29) (with replacing D as σ ∗ εb therein), C3 > 0 is given in Cr 1 −1 Lemma 5.14, and Q̌max = 1−3β and β̌ = 1−β ) (by Assumption 2.12 (i)), 2 . Since β ∈ [0, 3 ∧(2CF ) 1+3w 1 we have that a(σ ∗ εb) = Θ( Ň ε b2 ) and C3 = Θ(Tcov ), where Ň1 is given in (2.15).

∗ Moreover, since n∗ in (5.30) satisfies n∗ = Θ(log( Q̌max ε b )), ť in (5.35) can be expressed in terms of the algorithmic parameters as an order of 1 w1 1−w Ň1 Ň2 Ň3 Q̌max Q̌max ∗ ť = O max log , log log + Tcov log , εb2 εb εb εb δb

where Ň2 and Ň3 are given in (2.15). From this and Lemma 5.7 (ii), we have the order of the iteration number T ∗ given by 1

T ∗ = τn∗ ;ť∗ = O(ť∗ + (Tcov n∗ ) 1−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),(ii), the construction of the iteration number T ∗ ∈ N is analogous to that for the asynchronous version but involves much simpler calculations, since the covering time condition in Assumption 2.12 (ii) 6For any nonnegative functions f, g : N → R, we write f (n) = Θ(g(n)) if and only if there exist some c, C > 0

and n ∈ N such that cg(n) ≤ f (n) ≤ Cg(n) for all n ≥ n.

is no longer required. In particular, for any ť ≥ 1, the sequence (τn;ť )n≥0 in Definition 5.6 can be redefined as č w τ τn+1;ť := τn;ť + , n ≥ 0, with τ1;ť := ť. κ̌ n;ť Moreover, in the resulting constants—such as ť∗1 and č∗1 in (5.20), ť∗2 in (5.32), C3 in (5.14), and a(D) in (5.29)—the parameter Tcov can be taken as 1 so that the results in Lemmas 5.10, 5.11, and 5.15 still hold, while (5.33) holds for all 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 δb ∈ (0, 1) be given. By the discretization error estimate in (5.11), it suffices to show that there exist some Cδb > 0 and Tδb ≥ 1 such that r log T 0 ∗ b (5.39) > 1 − δb for any T ≥ Tδb. P ∥Q̌T − Q̌ ∥Š×Π̌ ≤ Cδb Tw b the iteration number T ∗ in TheoTo this end, for every εb ∈ (0, 1), we denote by T ∗ (b ε, δ) b We recall from the proof rem 2.17 (ii) under the prescribed error level εb and confidence level δ. ∗ ∗ b of Theorem 2.17 (ii), particularly Step 3, that T (b ε, δ) = T = τn∗ ;ť∗ , where n∗ and ť∗ , given in (5.30) and (5.35), respectively, satisfy the following estimates: there exist constants Kδ,1 b > 0 and εδ,1 ∈ (0, 1), where K depends on the parameters appearing in (2.15) and the fixed confidence b b δ,1 b but does not depend on εb, such that for every εb ∈ (0, εb ), level δ, δ,1

n∗ ≤ Kδ,1 ε−1 ) b log(b

−2 1/w and ť∗ ≤ Kδ,1 b log(b ε−1 ) . b ε

Moreover, by Lemma 5.7 there exists some Kδb > 0 (depending on Kδ,1 b) such that b but not on ε 1/w b ≤ Kb εb−2 log(b T ∗ (b ε, δ) ε−1 ) (5.40) for all εb ∈ (0, εδ,1 b ). δ w/2 and define for every T ≥ 2 by δ

Now, we let Cδb := Kb

r Eδb(T ) := Cδb

(5.41) Since the map [e1/w , ∞) : T 7→

log T Tw

1/w is decreasing, we can choose Tδ,1 } such that b ≥ max{2, e

Eδb(T ) ≤ εδ,1 b

(5.42)

log T . Tw

for all T ≥ Tδ,1 b .

Moreover, since log(Eδb(T )−1 ) = w2 log T − 21 log log T − log Cδb for all T > 2, there exists some Tδ,2 b ≥ 2 such that log(Eδb(T )−1 ) ≤ log T

(5.43)

for all T ≥ Tδ,2 b .

Last, we let Tδb := max{Tδ,1 b , Tδ,2 b }. Then, we have by (5.40), (5.42), (5.43) that for every T ≥ Tδ b, b ≤ Kb Eb(T )−2 log Eb(T )−1 1/w T ∗ (Eδb(T ), δ) δ δ δ (5.44) h i1/w 1/w Tw = Kδb Cb−2 log Eδb(T )−1 ≤ Kδb Cb−2 T w = T, δ log T δ where the first equality follows from definition of Eδb(T ) and the last equality follows from the w/2 setting that Cδb = Kb . δ

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

Then, for each T ≥ Tδb, 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 εb := Eδb(T ) (see (5.41)) and b which leads to confidence level δ, b b0 ∥Q̌ e − Q̌∗ ∥ ≤ E (T ) > 1 − δb for any Te ≥ T ∗ (Eδb(T ), δ). P b Š×Π̌ T δ b for every T ≥ Tb by (5.44), the desired estimate (5.39) follows. Since T ≥ T ∗ (Eδb(T ), δ) δ 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-II. 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 L2 -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-ofthe-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.

MATHIEU LAURIÈRE, ARIEL NEUFELD, AND KYUNGHYUN PARK

[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 II: 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. Shanghai Center for Data Science; NYU-ECNU Institute of Mathematical Sciences, NYU Shanghai Email address: [email protected] Division of Mathematical Sciences, Nanyang Technological University Email address: [email protected] Division of Mathematical Sciences, Nanyang Technological University Email address: [email protected]

Record · ID 290592 · SHA-256 8a1eedeae6b8ef45
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.