<figure><img src="image_1.png" /></figure>

HAL
open science

# Homogenization of Multi-agent Learning Dynamics in Finite-state Markov Games

Yann Kerzreho

<figure><img src="image_2.png" /></figure>

## To cite this version:

Yann Kerzreho. Homogenization of Multi-agent Learning Dynamics in Finite-state Markov Games.
2025. hal-05129706

HAL Id: hal-05129706

https://hal.science/hal-05129706v1

Preprint submitted on 25 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# HOMOGENIZATION OF MULTI-AGENT LEARNING DYNAMICS IN FINITE-STATE MARKOV GAMES

**Yann Kerzreho**

École Normale Supérieure de Paris-Saclay
91190 Gif-sur-Yvette, France

yann.kerzreho@ens-paris-saclay.fr

## ABSTRACT

This paper introduces a new approach for approximating the learning dynamics of multiple re-inforcement learning (RL) agents interacting in a finite-state Markov game. The idea is to rescale the learning process by simultaneously reducing the learning rate and increasing the update frequency, effectively treating the agent's parameters as a slow-evolving variable influenced by the fast-mixing game state. Under mild assumptions—ergodicity of the state process and continuity of the updates—we prove the convergence of this rescaled process to an ordinary differential equation (ODE). This ODE provides a tractable, deterministic approximation of the agent's learning dynamics. An implementation of the framework is available at : https://github.com/yannKerzreho/MarkovGameApproximation

**Keywords** Markov Game · Stochastic Game · Reinforcement Learning · Multiscale Homogenization

## 1 Introduction

### 1.1 Background and Motivation

The study of multi-agent reinforcement learning (MARL) interacting over time in structured settings, such as Markov games ([1]), is a challenging task due to the high variance and non-stationarity of the learning process. Recently, an emergent literature faces this problem when trying to tackle the issue of algorithmic collusion [2, 3, 4]. With the rise of algorithmic pricing on online market places, scientists wander if these algorithms might learn to cooperate on price and behave non-competitively. The first paper to introduce analytical tools in addition to intensive simulations was [4]. However, they applied their method to a stateless games, which is a huge simplification as RL methods are created to solve Markov decision process which include states.

In their framework, the parameters defining the agents' behavior evolve according to a stochastic process whose updates depend on chosen actions. By rescaling time (increasing the update rate by a factor $N$) and reducing the update size accordingly (dividing the update magnitude by $N$), this approach, also known as hydrodynamic scaling, yields convergence to a deterministic ODE ([5]). An accessible introduction to this fluid limit technique for Markov chains is given in [6]. However, applying this method to games with state dependence is non-trivial. The state evolution, being discrete and rapidly fluctuating, is not suited for fluid approximations. One common workaround is to replace the state with a probability distribution on states, by introducing a population structure representation (see [7, 8]). Then we could update the agent's parameters with an average update across states weighted by the distribution. A population structure would be useful for approximating agents playing many different games simultaneously and in parallel. However, our case is different as we want to approximate what happen for a single game.

Moreover, this work differs from the two-scale stochastic approximation of [9] as our aim is to provide a means of analyzing the agent's learning period, even if the agents do not converge to a fixed strategy. The work of [10] is closely related, but does not apply to our case because the assumptions made are different: since they assume the existence of an exponentially stable attractor for the ODE, their dynamics cannot explode. In MARL, such an assumption cannot
be made, as there is no guarantee of convergence to a fixed point for the traditional algorithm. In this way, they use stochastic approximation where we use homogenization techniques.

## 1.2 Contributions

The paper propose a novel homogenization-based method for approximating the learning dynamics of RL agents in a finite-state Markov game. Specifically, we model the agent's parameters as a slow variable and the game's state as a fast-mixing variable. By simultaneously scaling down the learning rate and scaling up the update frequency, we show that the stochastic process describing the agent's behavior converges to an ODE.

This ODE describes the evolution of the agent's parameters averaged over the stationary distribution of the fast state variable. This type of result is known from multi-scale homogenization (e.g. [11]), though we have not found any existing frameworks that apply directly to our case. Therefore, we provide a new proof and framework tailored to our context.

To our knowledge, this approximation is original and offers new analytical tools for studying algorithmic behavior in dynamic environments. In particular, it has promising applications in the study of algorithmic collusion, where simulation-heavy methods currently dominate. Our framework allows for robust and reproducible analysis using ODEs, facilitating the design and testing of novel learning strategies.

## 1.3 Structure

In section 2, we will present the modeling framework for a reinforcement agent playing a finite-state Markov game and how we can derive a Markov chain from it. Section 3 presents the assumptions and the main convergence theorem. Section 4 showcases how Q-tables equipped with a right policy can be used in our framework. Finally, Section 5 discusses the approximation and its usage.

# 2 Framework

## 2.1 Definitions

Let us start by defining a Markov game, even if this object is often used, its notation and formal definition varies across the literature. Intuitively, a finite-state Markov game is just a multi-player Markov decision process where everyone's action jointly determines the next state.

**Definition 1 (Markov Game).** A finite state and action Markov game is a tuple $G = (\mathcal{I}, \mathcal{S}, \nu_0, (A^i)_{i \in \mathcal{I}}, T, (R^i)_{i \in \mathcal{I}})$ where,

* $\mathcal{I} = \{1, \dots, N\}$ is the set of $N$ players,

* $\mathcal{S} = \{1, \dots, S\}$ is the finite state space,

* $\nu_0$ is the initial distribution of state of the game,

* $A^i = \{1, \dots, A^i\}$ is the finite set of player $i$'s actions, with $A = \times_{i \in \mathcal{I}} A^i$ the joint actions space,

* $T: \mathcal{S} \times A \to \Delta(\mathcal{S})$ is the state transition kernel, assigning a probability distribution over next states $(\Delta(\mathcal{S}))$ given a current state and joint action. Therefore, $T(s, a)(s')$ is the probability to jump at state $s'$ from the state $s$ when the joint action $a$ is played,

* $R^i: \mathcal{S} \times A \to \mathbb{R}$ is a reward function of player $i$.

At each iteration $k$ of the game, each agent chooses an action $a_k^i \in A^i$ according to the current state $s_k \in \mathcal{S}$, then the game transitions to state $s_{k+1}$ according to $T$, and each agent $i$ is rewarded by $r_k^i = R^i(s_k, a_k)$. Extending the formalism of [4], we define a *reinforcer*, an algorithm (e.g., a Q-table) that can play a Markov game, as follows:

**Definition 2 (Reinforcer).** A reinforcer indexed by $i$ is a tuple $(X_0^i, f^i, \pi^i)$ with,

* A initial vector of parameters $X_0^i$,

* An update function $f: A \times \mathbb{R} \times \mathbb{R}^{d_i} \times S \times S \to \mathbb{R}^{d_i}$ such that,

$$X_{k+1}^i = X_k^i + f^i(a_k, r_k, X_k^i, s_k, s_{k+1}),$$
* A policy $\pi^i: \mathbb{R}^{d_i} \times S \to \Delta(\mathcal{A}^i)$ that maps $X^i$ and state to the probability of playing each action.

I have $a_k \in \mathcal{A}$ the action played by players, $r_k^i$ the reward of player $i$, and $s_k \in S$ the state of the game, all at iteration $k$. When all players are reinforcers, we can aggregate them all in a single $d$-dimensional vector, $d = \sum_{i \in \mathcal{I}} d_i$, using a single update function $f$ and a single policy $\pi$. We create a new object to simplify the notation of reinforcers playing a Markov game by “wrapping” each period’s state-action-next-state tuple into a single enlarged state. We will see that the entire learning process (parameters plus environment) becomes a single Markov chain with such definition.

**Definition 3 ( Wrapped Markov Game).** Let a list of reinforcers (Def. 2) noted $RL = (X_0^i, f^i, \pi^i)_{i \in \mathcal{I}}$ playing a finite state Markov game (Def. 1) noted $G = (\mathcal{I}, S, \nu_0, (\mathcal{A}^i)_{i \in \mathcal{I}}, T, (R^i)_{i \in \mathcal{I}})$. The wrapped Markov game associated is $W(RL, G) = (f, P, X_0, \mu_0)$. We define $E = S \times \mathcal{A} \times S$ the wrapped-state space and $\mathcal{M}$ the space of stochastic matrix of dimension $\#E$.

* The aggregate update of the parameters is $f: \mathbb{R}^d \times E \to \mathbb{R}^d$ such that,

$$f(x, g) = \bigoplus_{i=1}^{n} f_i(x_i, g) = \begin{pmatrix} f_1(x_1, g) \\ \vdots \\ f_n(x_n, g) \end{pmatrix} \quad \text{with } x = (x_1, \dots, x_n), \ x_i \in \mathbb{R}^{d_i}$$

* A parametrized transition matrix for the wrapped-state $P: \mathbb{R}^d \to \mathcal{M}$, such that for $x \in \mathbb{R}^d$ and $g = (s_c, a, s_n), g' = (s'_c, a', s'_n) \in E$,

$$P_x(g, g') = 1\{s_n = s'_c\} \pi(x + f(x, g), s'_c)(a') T(s'_c, a')(s'_n),$$

where $\pi(x, s) = \bigotimes_{i=1}^n \pi_i(x_i, s)$. The element $s_c$ is the current state, $a$ is the joint action played and $s_n$ is the next state, which is also needed to update the parameters. The probability $\pi(x + f(x, g), s'_c)(a')$ is the one of the learners picking joint action $a'$ in the state $s'_c$, after updating parameters by $f$.

* The initial aggregated parameters $X_0 = (X_0^1, \dots, X_0^N)$,

* The initial distribution of the wrapped game on $E$ noted $\mu_0$, such that for $g = (s_c, a, s_n) \in E$,

$$\mu_0(g) = \nu_0(s_c) \pi(X_0, s_c)(a) T(s_c, a)(s_n).$$

The wrapped game is a way to simplify the processes produced by playing a Markov game (Def. 1). To update a reinforcer (Def. 2) we need the current state of the game, the joint action chosen by players and the next state. All this information is summarized by an element of the wrapped-state space $E$. Moreover, updating the wrapped-state is also very simple as it uses a single parametrized transition matrix $P_x$. Now, to define the trajectories of such wrapped game, we introduce a probability space $(\Omega, \mathcal{F}, \mathbb{P})$.

**Definition 4 ( Wrapped Trajectories).** The wrapped trajectories of a wrapped Markov game (Def. 3) is map,

$$(X_n, G_n)_{n \in \mathbb{N}}: \Omega \to (\mathbb{R}^d, E)^N$$

such that for all $x \in \mathbb{R}^d$ and $g, g' \in E$,

$$\begin{align}
X_{n+1} &= X_n + f(X_n, G_n), \nonumber \\
P_x(g, g') &= \mathbb{P}(G_{n+1} = g' | G_n = g, X_{n+1} = x + f(x, g)) \tag{1} \\
&= \mathbb{P}(G_{n+1} = g' | G_n = g, X_n = x). \nonumber
\end{align}$$

We see that $G_n = (s_n, a_n, s_{n+1})$ where $s_n$ and $s_{n+1}$ are the states of the game at iteration $n$ and $n+1$, while $a_n$ the joint actions played at iteration $n$. The joint actions $a_n$ is chosen with the state $s_n$ and the parameters $X_n$.

From the definition, we see that the chain $(X_n, G_n)_{n \in \mathbb{N}}$ is Markovian, but time-inhomogeneous. This motivated the definition of the wrapped game. On $(\Omega, \mathcal{F}, \mathbb{P})$, the process $(X_n, G_n)_{n \in \mathbb{N}}$ is the Markov chain of initial law $\delta_{X_0} \otimes \mu_0$ and transition kernel $(x, g) \mapsto \delta_{x+f(x,g)} \otimes P_x(g, \cdot)$.

## 2.2 Scaled process and Result Aimed

Our approach is to divide by $N$ the update of the reinforcers and multiply by $N$ the number of iteration. Thus, we are going to show the convergence of the trajectories of a wrapped game scaled by $N$ towards a deterministic ODE. Let
us define $(X_n^N, G_n^N)_{n \in \mathbb{N}}$ the trajectories when we changed the reinforcers to $(X_0^i, N^{-1}f^i, \pi^i)_{i \in \mathcal{I}}$. Then we have for all $x \in \mathbb{R}^d$ and $g, g' \in E$,

$$ 
\begin{aligned}
X_{n+1}^N &= X_n^N + N^{-1}f(X_n, G_n), \\
P_x^N(g, g') &= \mathbb{P}(G_{n+1}^N = g' | G_n^N = g, X_{n+1}^N = x + N^{-1}f(x, g)) \\
&= \mathbb{P}(G_{n+1}^N = g' | G_n^N = g, X_n = x).
\end{aligned} 
\quad (2) $$

Then, we are going to show the convergence of $X_{[Nt]}^N$ to the ODE defined by $y(0) = X_0$ and $y'(t) = \beta(y(t))$. The limit derivative $\beta$ is defined as,

$$ \beta = \lim_{N \to \infty} \beta^N, \quad \beta^N : x \in \mathbb{R}^d \mapsto \sum_{g \in E} \mu_x^N(g) f(x, g) \in \mathbb{R}^d, \quad (3) $$

where $\mu_x^N$ is the ergodic probability measure of the chain given by $P_x^N$ under an assumption of uniform ergodicity in $x$ and $N$.

## 2.3 Random Induction and change in Probability

This subsection is purely technical and can be avoided. To facilitate the analysis, we build an explicit expression for the wrapped game transitions. A function $h^N : \mathbb{R}^d \times E \times [0, 1] \to E$ can be built such that $G_{n+1}^N = h^N(X_n^N, G_n^N, \xi_{n+1})$ where $(\xi_n)_{n \in \mathbb{N}}$ are i.i.d. uniformly distributed on $[0, 1]$. This defines a process with the same distribution as the original Markov chain, but with an explicit sampling structure. Moreover $h$ can be written,

$$ h^N(x, g, \xi) = \begin{cases} 1 & \text{if } \xi \in [0, P_x^N(g, 1)] = I_{x,g}^N(1) \\ i & \text{if } \xi \in \left[ \sum_{j=1}^{i-1} P_x^N(g, j), \sum_{j=1}^i P_x^N(g, j) \right] = I_{x,g}^N(i), \text{ for } i > 1, \end{cases} $$

where $\#^E I_{x,g}^N(i) = [0, 1]$ and with $\lambda$ the Lebesgue measure, $\lambda(I_{x,g}^N(i)) = P_x^N(g, i)$. The intervals $I_{x,g}^N(i)$ are defining the inverse CDFs used for sampling transitions. To simplify notation, we will keep them unchanged despite this important underlying change. Therefore, if we prove the convergence of this new Markov chain (with changed probability) towards an ODE with $N \to \infty$, this will only prove the convergence in distribution between the initial Markov chain (with unchanged probability) and the ODE.

# 3 Theoretical Results

## 3.1 Set up and Assumptions

Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space, $\mathcal{G} = (\mathcal{I}, \mathcal{S}, (\mathcal{A}^i)_{i \in \mathcal{I}}, T, (\mathcal{R}^i)_{i \in \mathcal{I}})$ a Markov game (Def. 1) played by $(X_0^i, N^{-1}f^i, \pi^i)_{i \in \mathcal{I}}$ a set of reinforcers (Def. 2) parametrized by $N$. The associated wrapped Markov Game (Def. 3) is $\mathcal{W}^N = (N^{-1}f, P^N, X_0, \mu_0^N)$ and the wrapped trajectories (Def. 4) are $(X_n^N, G_n^N)_{n \in \mathbb{N}}$. From here we will make the following assumptions:

**Assumption 1.** The update function $f: \mathbb{R}^d \times E \to \mathbb{R}^d$ is Lipschitz in its first argument. Moreover, there exist a compact $D \subset \mathbb{R}^d$ such that for any $n, N \in \mathbb{N}, (X_n^N, G_n^N) \in D \times E$. Hence, $f$ is bounded on $D$ and we note $\sup_D f = \|f\|_\infty$.

**Assumption 2.** The joint policy $\pi: \mathbb{R}^d \times S \to \Delta(\mathcal{A})$ is $L_\pi$-Lipschitz in its first argument on $D$.

**Assumption 3.** For any $x \in D$, the transition matrix $P_x^N$ respects uniformly the Doeblin condition: there exist an integer $k$, a positive $c$ and a probability measure $q$ on $E$ such that $(P_x^N)^k(i, j) \ge c q(j)$ for any $x \in D$, any $N \in \mathbb{N}$, and any $i, j \in S$. Hence the transition matrix $P_x^N$ is ergodic and we note $\mu_x^N$ the ergodic probability measure of the chain given by $P_x^N$.

We will see in Section 4 that these assumptions are easy to verify for a Q table equipped with a continuous policy. Note that the existence of $D$ can be proven because the rewards are bounded. Whenever updates attempt to approximate the cumulative discounted rewards over the iterations of the game, such a compact space exists. The assumption 3 can be verified simply by taking a uniform exploration rate across actions.
## 3.2 Main Results

From these assumptions we can deduce the following lemmas:

**Lemma 1.** Under the assumptions 1 and 2, $P_x^N$ is Lipschitz in its argument $x$. This means that with the operator norm $\|\cdot\|_{op} = \sup_{\nu \in \mathcal{P}(E)} \|\nu(\cdot)\|_{TV}$ where $\mathcal{P}(E)$ is the set of probability distributions over $E$, there exist $L_P$ such that for any $x, y \in D$ and any $N \in \mathbb{N}$,

$$ \|P_x^N - P_y^N\|_{op} \le L_P \|x - y\|. $$

**Lemma 2.** Under the assumptions 1 and 3, the map $x \mapsto \mu_x^N$, where $\mu_x^N$ is the unique invariant measure of the Markov kernel $P_x^N$, is Lipschitz continuous. Hence $\beta^N$ and $\beta$ defined in (3) are Lipschitz continuous on $D$.

**Lemma 3.** Under the assumptions 1, 2 and 3, $\|\beta^N(x) - \beta(x)\| = \mathcal{O}(N^{-1})$.

The proofs can be found in appendix A.1, A.2 and A.3 respectively. Now we can pass to the main result of our paper:

**Theorem 1.** Under Assumptions 1, 2 and 3, the scaled process $X_{[Nt]}^N$ converges weakly to the solution of the ODE defined by $\dot{y}(t) = \beta(y(t))$ and $y(0) = X_0$, where $\beta$ is defined as,

$$ \beta = \sum_{g \in E} \mu_x(g) f(x, g). $$

## 3.3 Proof of the Main Theorem

*Proof.* Recall that we defined the Euler approximation by

$$ y_0^N = X_0, \quad y_{n+1}^N = y_n^N + \frac{1}{N} \beta(y_n^N). $$

By the triangular inequality, for any $T > 0$ we have

$$ \mathbb{E} \sup_{0 \le t \le T} \|X_{tN}^N - y(t)\| \le \mathbb{E} \sup_{0 \le t \le T} \|X_{tN}^N - y_{tN}^N\| + \sup_{0 \le t \le T} \|y_{tN}^N - y(t)\|, $$

and by standard results for the convergence of the Euler scheme, since $\beta$ is Lipschitz, we have

$$ \sup_{0 \le t \le T} \|y_{tN}^N - y(t)\| = \mathcal{O}\left(\frac{1}{N}\right). $$

Then, to prove the theorem, we just need to show that,

$$ \sup_{0 \le t \le T} \|X_n^N - y_{tN}^N\| = \ell(1). $$

**Step 1.** We will start by dividing the sum of updates into block of $M \in \mathbb{N}$ (s.t. $tN/M \in \mathbb{N}$) updates and a residual that can be treated with a Grönwall lemma,

$$ \begin{aligned} \mathbb{E} \|X_{tN}^N - y_{tN}^N\| &= \frac{1}{N} \mathbb{E} \left\| \sum_{n=0}^{tN-1} f(X_n^N, G_n^N) - \beta(y_n^N) \right\| \\ &\le \frac{1}{N} \mathbb{E} \left\| \sum_{n=0}^{tN-1} f(X_n^N, G_n^N) - \beta(X_n^N) \right\| + \frac{1}{N} \mathbb{E} \left\| \sum_{n=0}^{tN-1} \beta(X_n^N) - \beta(y_n^N) \right\| \quad (4) \\ &\le \frac{1}{N} \sum_{k=0}^{M-1} \mathbb{E} \left\| \sum_{n=ktN/M}^{(k+1)tN/M-1} f(X_n^N, G_n^N) - \beta(X_n^N) \right\| + \frac{1}{N} \mathbb{E} \left\| \sum_{n=0}^{tN-1} \beta(X_n^N) - \beta(y_n^N) \right\|. \end{aligned} $$
We add and subtract $\beta(X_n^N)$ before using the triangular inequality to pass to the second line. Each term of the sum over $k$ can be decomposed as follows, for simplicity we change indices to $k = 0$,

$$ 
\begin{aligned}
\mathbb{E} \left\| \sum_{n=0}^{tN/M-1} f(X_n^N, G_n^N) - \beta(X_n^N) \right\| &\le \mathbb{E} \left\| \sum_{n=0}^{tN/M-1} f(X_n^N, G_n^N) - f(X_n^N, \tilde{G}_n^N) \right\| \\
&\quad + \sum_{n=0}^{tN/M-1} \mathbb{E} \left\| \beta(X_0^N) - \beta(X_n^N) + f(X_n^N, \tilde{G}_n^N) - f(X_0^N, \tilde{G}_n^N) \right\| \\
&\quad + \mathbb{E} \left\| \sum_{n=0}^{tN/M-1} f(X_0^N, \tilde{G}_n^N) - \beta^N(X_0^N) \right\| \\
&\quad + \frac{tN}{M} \left\| \beta^N(X_0^N) - \beta(X_0^N) \right\|,
\end{aligned}
\quad (5) $$

where $(\tilde{G}_n^N)_{n \ge k}$ is the Markov chain defined by the kernel $P_{X_n^N}$ and $\tilde{G}_0^N = G_0^N$. Moreover $G_{n+1}^N = h(X_n^N, G_n^N, \xi_{n+1})$ and $\tilde{G}_{n+1}^N = h(X_0^N, \tilde{G}_n^N, \xi_{n+1})$. The chain $(\tilde{G}_n^N)_{n \in \mathbb{N}}$ is the homogeneous Markov chain of states when freezing the parameters to its first values.

**Step 2.** We bound $\mathbb{E} \left\| \sum_{n=0}^{tN/M-1} f(X_n^N, G_n^N) - f(X_n^N, \tilde{G}_n^N) \right\|$ by using this inequality,

$$ 
\begin{aligned}
\mathbb{E} \left\| \sum_{n=0}^{tN/M-1} f(X_n^N, G_n^N) - f(X_n^N, \tilde{G}_n^N) \right\| &\le \sum_{n=0}^{tN/M-1} \mathbb{E} \left\| \sum_{g \in E} f(X_n^N, g) (1\{G_n^N = g\} - 1\{\tilde{G}_n^N = g\}) \right\| \\
&\le \|f\|_{\infty} \sum_{n=0}^{tN/M-1} \mathbb{E} \left[ \sum_{g \in E} \left| 1\{G_n^N = g\} - 1\{\tilde{G}_n^N = g\} \right| \right] \\
&\le \|f\|_{\infty} \sum_{n=0}^{tN/M-1} \mathbb{P} (G_n^N \ne \tilde{G}_n^N).
\end{aligned}
$$

Now, by the Lemma 4 described and proven below with $T = tN/M$, there exist a positive $C > 0$ such that,

$$ \|f\|_{\infty} \sum_{n=0}^{tN/M-1} \mathbb{P}(G_n^N \neq \tilde{G}_n^N) \le \|f\|_{\infty} \sum_{n=0}^{tN/M-1} \left(1 - \left(1 - C \frac{t}{M}\right)_+^{\frac{tN}{M}}\right) \le \|f\|_{\infty} \frac{tN}{M} \left(1 - \left(1 - C \frac{t}{M}\right)_+^{\frac{tN}{M}}\right). $$

**Step 3.** To bound $\mathbb{E} \sum_{n=0}^{tN/M-1} \left\| \beta(X_n^N) - \beta(X_0^N) + f(X_n^N, \tilde{G}_n^N) - f(X_0^N, \tilde{G}_n^N) \right\|$, we start by noticing that for any $n \in \mathbb{N}$,

$$ \|X_{n+1}^N - X_n^N\| \le \frac{1}{N} \|f\|_{\infty} $$

then we have,

$$ \|X_L^N - X_0^N\| \le \sum_{l=0}^{L-1} \|X_{l+1}^N - X_l^N\| \le \frac{L}{N} \|f\|_{\infty} $$

and finally with $L_\beta$ and $L_f$ the Lipschitz constant of $\beta$ and $f$,

$$ 
\begin{aligned}
\mathbb{E} \sum_{n=0}^{tN/M-1} \left\| \beta(X_0^N) - \beta(X_n^N) + f(X_n^N, \tilde{G}_n^N) - f(X_0^N, \tilde{G}_n^N) \right\| &\le (L_\beta + L_f) \mathbb{E} \sum_{n=0}^{tN/M-1} \|X_n^N - X_0^N\| \\
&\le (L_\beta + L_f) \sum_{n=0}^{tN/M-1} \frac{n}{N} \|f\|_{\infty} \le (L_\beta + L_f) \frac{t^2 N}{M^2} \|f\|_{\infty} = \mathcal{O}\left(\frac{t^2 N}{M^2}\right).
\end{aligned}
$$

**Step 4.** To bound $\mathbb{E} \left\| \sum_{n=0}^{tN/M-1} f(X_0^N, \tilde{G}_n^N) - \beta(X_0^N) \right\|$ we rewrite,
$$
\begin{aligned}
\mathbb{E} \left\| \sum_{n=0}^{tN/M-1} f(X_0^N, \tilde{G}_n^N) - \beta(X_0^N) \right\| &\le \sum_{g \in E} \mathbb{E} \left\| \sum_{n=0}^{tN/M-1} f(X_0^N, g) \mathbb{1}\{\tilde{G}_n^N = g\} - f(X_0^N, g) \mu_{X_0^N}(g) \right\| \\
&\le \sum_{g \in E} \|f\|_{\infty} \mathbb{E} \left| \sum_{n=0}^{tN/M-1} \mathbb{1}\{\tilde{G}_n^N = g\} - \mu_{X_0^N}(g) \right|,
\end{aligned}
$$

then by the Lemma 5 described below, if $tN/M \to \infty$ the order of the sum is $(\frac{tN}{M})^{1/2}$.

**Step 5.** In this step we aggregate step 2, 3 and 4 and inject them into the inequalities of step 1. We use the Lemma 3 to get an order of magnitude for the last term of the inequality 5. Then we have an order for inequality 5 of:

$$O\left(\frac{N}{M}\left(1-\left(1-\frac{1}{M}\right)_{+}^{\frac{N}{M}}\right)\right)+O\left(\frac{N}{M^{2}}\right)+O\left(\left(\frac{N}{M}\right)^{1 / 2}\right)+O\left(\frac{1}{M}\right)$$

Then we can use this order into the inequality 4. To get the order of first term, we multiply the previous order of inequality 5 by $\frac{N}{M}$, this give an order of:

$$O\left(1-\left(1-\frac{1}{M}\right)_{+}^{\frac{N}{M}}\right)+O\left(\frac{1}{M}\right)+O\left(\left(\frac{M}{N}\right)^{1 / 2}\right)+O\left(\frac{1}{N}\right)$$

By using $1 - (1 - M^{-1})^{N/M} = 1 - \exp(NM^{-1} \ln(1 - M^{-1})) = 1 - \exp(NM^{-2} + o(NM^{-2})) \sim NM^{-2}$ when $N = o(M^{-2})$, we can find a $M$ optimizing the convergence rate. Let $M = N^{\alpha}$, then the order is:

$$N^{1-2\alpha}+N^{-\alpha}+N^{\alpha/2-1/2}+N^{-1}$$

The minimum is for $\alpha = 3/5$, this gives a final order of $N^{-1/5}$. Therefore,

$$\mathbb{E} \left\| X_{tN}^N - y_{tN}^N \right\| \le \mathcal{O} \left( N^{-1/5} \right) + \frac{1}{N} \mathbb{E} \left\| \sum_{n=0}^{tN-1} \beta(X_n^N) - \beta(y_n) \right\| \quad (6)$$

**Step 6.** As the inequality 6 is defined for any finite $t$, we can define $\kappa$, an error defined as,

$$\kappa(N) = \max_{n \in \{1, \dots, tN\}} \mathbb{E} \left\| X_n^N - y_n^N \right\| - \frac{1}{N} \mathbb{E} \left\| \sum_{k=0}^{n-1} \beta(X_k^N) - \beta(y_k^N) \right\|,$$

an application that allow to bound the error of order $N^{-1/5}$ independently of $n$. We denote $L_{\beta}$ the Lipschitz constant of $\beta$, then we have for $N$ large enough and for all $n \in \{0, \dots, tN\}$,

$$
\begin{aligned}
\mathbb{E} \|X_n^N - y_n^N\| &\le \kappa(N) + \frac{1}{N} \sum_{k=0}^{n-1} \mathbb{E} \|\beta(X_k^N) - \beta(y_k^N)\| \\
&\le \kappa(N) + L_{\beta} \frac{1}{N} \sum_{k=0}^{n-1} \mathbb{E} \|X_k^N - y_k^N\|
\end{aligned}
$$

By using this version of the Grönwall lemma: $u_n \le B + \sum_{k=0}^{n-1} \alpha_k u_k \implies u_n \le B \exp\{\sum_{k=0}^{n-1} \alpha_k\}$, we have for all $n \in \{0, \dots, tN\}$,

$$
\begin{aligned}
\mathbb{E} \| X_n^N - y_n^N \| &\le \kappa(N) \exp \left\{ \sum_{k=0}^{n-1} L_{\beta}/N \right\} \\
&\le \kappa(N) e^{tL_{\beta}} = \mathcal{O} \left( N^{-1/5} \right)
\end{aligned}
$$

As we have the inequality for all $n \in \{0, \dots, tN\}$ we pass to the sup to get the final result. $\square$

<figure><img src="image_4.png" /></figure>
## 3.4 Additional Lemmas

**Lemma 4.** For $N \in \mathbb{N}$ and under the assumptions 1, 2 and 3, with $(\xi_n)_{n \in \mathbb{N}} \sim \mathcal{U}[0, 1]$ i.i.d. we define two Markov chains induced by the same sequence of random variable, $G_{n+1}^N = h^N(X_n^N, G_n^N, \xi_{n+1})$ et $\tilde{G}_{n+1}^N = h^N(X_0^N, \tilde{G}_n^N, \xi_{n+1})$. Then for any $T \in \mathbb{N}$, there is $C > 0$ such that for all $n \in \{0, \dots, T\}$

$$ \mathbb{P}(G_n^N \neq \tilde{G}_n^N) \leq 1 - \left(1 - C \frac{T}{N}\right)_+^T $$

**Lemma 5.** $(G_n)_{n \in \mathbb{N}}$ is a Markov chain in $(E, \mathcal{P}(E))$ with $E$ finite. Its transition matrix is denoted $P$ and $\mu^n$ is the distribution of $G_n$ for all $n$. If the chain respects the Doeblin condition: there exist an integer $k$, a positive $c$ and a probability measure $q$ on $E$ s.t. $P^k(i, j) \geq c q(j)$ then,

$$ \|\mu^n - \mu\|_{TV} = \frac{1}{2} \sum_{g \in E} |\mu^n(g) - \mu(g)| \leq (1 - c)^{\lfloor n/k \rfloor} $$

$$ \mathbb{E} \left| \frac{1}{N} \sum_{n=1}^{N} 1\{G_n = g\} - \mu(g) \right| = \mathcal{O}(N^{-1/2}) \quad \text{for any } g \in E, $$

where $\mu$ is the invariant probability of the Markov chain.

The proof of the Lemma 4 and the second point of Lemma 5 can be found in appendix (A.4, A.5). The first point of the Lemma 5 can be found in [12].

# 4 Example: Q-table

## 4.1 Description

In this subsection, we present a classical reinforcer that satisfies the assumptions of the theorem. A Q-table assigns to each state-action pair $(a^i, s) \in \mathcal{A}^i \times S$ a Q-value, which is updated using the Bellman equation to approximate the expected discounted rewards of taking action $a^i$ in state $s$. We denote by $X_k^i(a^i, s)$ the Q-value at iteration $k$ for agent $i$.

When Q-tables are paired with a policy, they can be interpreted as reinforcers. The update rule is defined for all $(a^i, s)$ by:

$$ X_{k+1}^i(a^i, s) = \begin{cases} X_k^i(a^i, s) + \alpha \left( r_k^i + \gamma \max_{b \in \mathcal{A}^i} X_k^i(b, s_{k+1}) - X_k^i(a^i, s) \right), & \text{if } (a^i, s) = (a_k^i, s_k), \\ X_k^i(a^i, s), & \text{otherwise,} \end{cases} $$

where $\gamma \in [0, 1)$ is the discount factor and $\alpha$ the learning rate.

We define the policy $\pi^i$ as a softmax policy with temperature $\tau$, combined with uniform exploration at rate $\varepsilon$. For all $a^i \in \mathcal{A}^i$, we set:

$$ \pi^i(X_k^i, s_k)(a^i) = (1 - \varepsilon) \cdot \frac{\exp(X_k^i(a^i, s_k)/\tau)}{\sum_{b \in \mathcal{A}^i} \exp(X_k^i(b, s_k)/\tau)} + \frac{\varepsilon}{\#\mathcal{A}^i}. $$

## 4.2 Verification of the Assumptions

The verification of the set of assumptions will be briefly justified here. Assumption 1 holds thanks to the linear structure of the updates and noticing that the rewards are bounded. Note $\bar{r}$ the maximum absolute reward across the states, joint-actions and players. Then it holds from an induction that $X_k^i \in B(0, \|X_0\|_\infty \lor \bar{r}/(1-\gamma))$ for any $k$. As the rewards are bounded, the discounted sum of rewards across iterations of the game are also bounded. For assumption 2, the policy $\pi$ is $L_\pi$-Lipsichtz on $D$ as its Jacobian is a continuous function, hence bounded on a compact.

The uniform Doeblin of assumption 3 is fulfilled by to the $\varepsilon$-rate of uniform exploration. In two iteration, the chain have a positive probability to explore any state of the wrapped game. Let $\kappa$ the smallest probability in the state-transition function $T$. Then, for any $x \in D$ and $s \in S$, it holds that $\pi(x, s) \geq \varepsilon/\#S$ and for all $i, j \in S$, we have that $(P_x^N)^2(i, j) \geq (\kappa\varepsilon/\#S)^2$.
# 5 Discussion

The two-scale homogenization technique presented in this paper provides a meaningful and rigorous approximation of the original process dynamics. Approximating the learning process by an ordinary differential equation (ODE) offers both advantages and limitations, which we now discuss.

On the positive side, deriving the closed-form ODE enables further analytical insights and allows simulating the learning dynamics without repeatedly running the full stochastic game. This can significantly reduce computational cost and facilitate large-scale experimentation and parameter exploration. However, one challenge lies in computing the limit $\beta$, which requires determining the stationary distribution $\mu_x$ at each time step. For large state spaces, this may necessitate numerical methods, potentially offsetting some of the computational gains.

Another aspect is that our approximation is insensitive to proportional rescalings of the learning rate across reinforcement learning algorithms. While this may be seen as an advantage—removing the influence of a sensitive hyperparameter—it could also be a limitation, as learning rates often play a critical role in the early phases of training.

The method is also highly flexible: the definition of the wrapped game can be extended to include, for instance, batched updates or stochastic rewards, allowing a broader class of reinforcement learners to fit within the framework.

Finally, we note a fundamental limitation: the ODE approximation is valid over finite time horizons, but its long-term accuracy depends on the stability of the dynamics. If the ODE exhibits attractor sets (e.g., fixed points or limit cycles), trajectories would remain close to the true dynamics; otherwise, divergence may occur.

# Acknowledgments

I would like to express my gratitude to Pierre Cardaliaguet and Yannick Viossat for supervising this work, which I completed during my first year of master's studies at Paris-Dauphine University. I would also like to warmly thank Aldric Labarthe for all his helpful discussions.

# References

[1] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In *Machine learning proceedings 1994*, pages 157–163. Elsevier, 1994.

[2] Ulrich Schwalbe. Algorithms, machine learning, and collusion. *Journal of Competition Law & Economics*, 14(4):568–607, 2018.

[3] Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolo, and Sergio Pastorello. Artificial intelligence, algorithmic pricing, and collusion. *American Economic Review*, 110(10):3267–3297, 2020.

[4] Martino Banchio and Giacomo Mantegazza. Artificial intelligence and spontaneous collusion. *arXiv preprint arXiv:2202.05946*, 2022.

[5] Thomas Kurtz. Solutions of ordinary differential equations as limits of pure jump markov processes. *Journal of applied Probability*, 7(1):49–58, 1970.

[6] Darling. Fluid limits of pure jump markov processes: a practical guide. *arXiv preprint math/0210109*, 2002.

[7] Michalis Michaelides, Jane Hillston, and Guido Sanguinetti. Geometric fluid approximation for general continuous-time markov chains. *Proceedings of the Royal Society A*, 475(2229):20190100, 2019.

[8] Darling and Norris. Differential equation approximations for markov chains. *Probability Surveys*, 5(none), January 2008.

[9] Vivek S Borkar. Stochastic approximation with two time scales. *Systems & Control Letters*, 29(5):291–294, 1997.

[10] Sebastian Allmeier and Nicolas Gast. Computing the bias of constant-step stochastic approximation with markovian noise. *arXiv preprint arXiv:2405.14285*, 2024.

[11] Grigorias A Pavliotis and Andrew Stuart. *Multiscale methods: averaging and homogenization*, volume 53. Springer Science & Business Media, 2008.

[12] Laurent Saloff-Coste. Lectures on finite markov chains. *Lectures on probability theory and statistics: École d'été de Probabilités de Saint-Flour XXVI-1996*, pages 301–413, 1997.
# A Additional Proofs

## A.1 Lemma 1.

Under the assumptions 1 and 2, $P_x^N$ is Lipschitz in its argument $x$. This means that with the operator norm $\| \cdot \|_{op} = \sup_{\nu \in \mathcal{P}(E)} \|\nu(\cdot)\|_{TV}$ where $\mathcal{P}(E)$ is the set of probability distributions over $E$, there exist $L_P$ such that for any $x, y \in D$ and any $N \in \mathbb{N}$,

$$ \|P_x^N - P_y^N\|_{op} \le L_P \|x - y\|. $$

*Proof.* By decomposing the operator norm we have,

$$ \begin{aligned} \|P_x^N - P_y^N\|_{op} &= \sup_{\nu \in \mathcal{P}(E)} \|\nu P_x^N - \nu P_y^N\|_{TV} \\ &= \sup_{\nu \in \mathcal{P}(E)} \frac{1}{2} \sum_{g' \in E} \sum_{g \in E} \nu(g) [P_x^N(g, g') - P_y^N(g, g')] . \end{aligned} $$

We just need to bound the difference between the two probability, by noticing that,

$$ \begin{aligned} P_x^N(g, g') &= \mathbb{P}(G_{n+1}^N = g' | X_{n+1}^N = x + N^{-1}f(x, g), G_n^N = g) \\ &= 1\{s_n = s'_c\} \pi(x + N^{-1}f(x, g), s'_c)(a') T(s'_c, a')(s'_n). \end{aligned} $$

we have with the policy $\pi$ being $L_\pi$-Lipsichtz on $D$ and $f$ being bounded on $D$,

$$ \begin{aligned} |P_x^N(g, g') - P_y^N(g, g')| &\le T(s'_c, a')(s'_n) |\pi(x + N^{-1}f(x, g), s'_c)(a') - \pi(y + N^{-1}f(y, g), s'_c)(a')| \\ &\le L_\pi |x + N^{-1}f(x, i) - y - N^{-1}f(y, i)| \\ &\le L_\pi (1 + L_f/N) \|x - y\| \end{aligned} $$

This proves the $(\#E)^2 L_\pi(1 + L_f)$-Lipschitz continuity of the transition matrices for all $N$ on $D$. $\square$

## A.2 Lemma 2.

Under the assumptions 1 and 3, the map $x \mapsto \mu_x^N$ where $\mu_x^N$ is the unique invariant measure of the Markov kernel $P_x^N$, is Lipschitz continuous. Hence $\beta^N$ and $\beta$ defined in (3) are Lipschitz continuous on $D$.

*Proof.* Let $x, y \in D$. Since $E$ is finite and $P_x^N$ satisfies a uniform Doeblin condition, there exists an integer $k \ge 1$ and a constant $\theta \in (0, 1)$ such that for all probability measures $\mu, \nu \in \mathcal{P}(E)$,

$$ \|\mu(P_x^N)^k - \nu(P_x^N)^k\|_{TV} \le \theta \|\mu - \nu\|_{TV}. $$

To simplify the notation in this proof, we omit the exponent $N$, therefore $P_x^k$ mean $(P_x^N)^k$. Since $\mu_x P_x = \mu_x$, it holds that

$$ \|\mu_x - \mu_y\|_{TV} = \|\mu_x P_x^k - \mu_y P_y^k\|_{TV} \le \|\mu_x P_x^k - \mu_x P_y^k\|_{TV} + \|\mu_x P_y^k - \mu_y P_y^k\|_{TV}. $$

Since the second term can be bounded with the contraction property, we still have to bound the first term $\|\mu_x P_x^k - \mu_x P_y^k\|_{TV}$. Let us prove by induction that for all $k \in \mathbb{N}$,

$$ \|P_x^k - P_y^k\|_{op} \le kL_P \|x - y\|, $$

where $\| \cdot \|_{op} = \sup_{\mu \in \mathcal{P}(E)} \|\mu(\cdot)\|_{TV}$ and $L_P$ is the Lipschitz constant of $x \mapsto P_x$ on $D$ such that,

$$ \|P_x - P_y\|_{op} \le L_P \|x - y\|. $$

Assume the property holds for some $k \ge 1$. Then,

$$ \begin{aligned} \|P_x^{k+1} - P_y^{k+1}\|_{op} &= \|P_x P_x^k - P_y P_y^k\|_{op} \le \|P_x(P_x^k - P_y^k)\|_{op} + \|(P_x - P_y)P_y^k\|_{op} \\ &\le \|P_x\|_{op} \cdot \|P_x^k - P_y^k\|_{op} + \|P_x - P_y\|_{op} \cdot \|P_y^k\|_{op} \\ &\le kL_P \|x - y\| + L_P \|x - y\| = (k+1)L_P \|x - y\|. \end{aligned} $$
Therefore, using $\mu_x \in \mathcal{P}(E)$,

$$ \|\mu_x P_x^k - \mu_x P_y^k\|_{\text{TV}} \le \|P_x^k - P_y^k\|_{\text{op}} \le kL_P \|x - y\|. $$

Use the contraction property of $P_y^k$,

$$ \|\mu_x - \mu_y\|_{\text{TV}} \le kL_P \|x - y\| + \theta \|\mu_x - \mu_y\|_{\text{TV}}. $$

Which gives,

$$ \|\mu_x - \mu_y\|_{\text{TV}} \le \frac{kL_P}{1 - \theta} \|x - y\|. $$

□

### A.3 Lemma 3.

Under the assumptions 1, 2 and 3, $\|\beta^N(x) - \beta(x)\| = \mathcal{O}(N^{-1})$.

*Proof.* We start from the definition,

$$ \|\beta^N(x) - \beta(x)\| \le \left\| \sum_{g \in E} f(x, g) (\mu_x^N(g) - \mu_x(g)) \right\| \le 2 \|f\|_{\infty} \|\mu_x^N - \mu_x\|_{TV}, $$

then from classical perturbation theory for finite state Markov chain we have $C > 0$ such that,

$$ \|\mu_x^N - \mu_x\|_{TV} \le C \|P_x^N - P_x^\infty\|_{op}. $$

As the proof of the Lemma 1,

$$ \|P_x^N - P_x^\infty\|_{op} = \sup_{\nu \in \mathcal{P}(E)} \frac{1}{2} \sum_{g' \in E} \sum_{g \in E} \nu(g) [P_x^N(g, g') - P_x^\infty(g, g')]. $$

and,

$$ P_x^N(g, g') = 1\{s_n = s'_c\} \pi(x + N^{-1}f(x, g), s'_c)(a') T(s'_c, a')(s'_n). $$

Then we have,

$$ \begin{aligned} |P_x^N(g, g') - P_x^\infty(g, g')| &\le T(s'_c, a')(s'_n) |\pi(x + N^{-1}f(x, g), s'_c)(a') - \pi(x, s'_c)(a')| \\ &\le T(s'_c, a')(s'_n) \frac{L_\pi \|f\|_{\infty}}{N}, \end{aligned} $$

and by summing over $g$ and $g' \in E$ we can conclude,

$$ \|\mu_x^N - \mu_x\|_{TV} = \mathcal{O}(\|P_x^N - P_x^\infty\|_{op}) = \mathcal{O}(N^{-1}) $$

□

### A.4 Lemma 4.

For $N \in \mathbb{N}$ and under the assumptions 1, 2 and 3, with $(\xi_n)_{n \in \mathbb{N}} \sim \mathcal{U}[0, 1]$ i.i.d. we define two Markov chains induced by the same sequence of random variable, $G_{n+1}^N = h^N(X_n^N, G_n^N, \xi_{n+1})$ et $\tilde{G}_{n+1}^N = h^N(X_0^N, \tilde{G}_n^N, \xi_{n+1})$. Then for any $T \in \mathbb{N}$, there is $C > 0$ such that for all $n \in \{0, \dots, T\}$

$$ \mathbb{P} (G_n^N \neq \tilde{G}_n^N) \le 1 - \left(1 - C \frac{T}{N}\right)_+^T $$

For ease the reading of the following proof, we rewrite the induction map $h^N$,

$$ h^N(x, g, \xi) = \begin{cases} 1 & \text{if } \xi \in [0, P_x^N(g, 1)] = I_{x,g}^N(1) \\ i & \text{if } \xi \in \left[ \sum_{j=1}^{i-1} P_x^N(g, j), \sum_{j=1}^i P_x^N(g, j) \right] = I_{x,g}^N(i), \text{ for } i > 1. \end{cases} $$
Proof. We start by using the Bayes formula to write,

$$ \mathbb{P}(G_{n+1}^N = \tilde{G}_{n+1}^N) \geq \mathbb{P}(G_n^N = \tilde{G}_n^N) \mathbb{P}(G_{n+1}^N = \tilde{G}_{n+1}^N | G_n^N = \tilde{G}_n^N) $$

We are looking for a lower bound on $\mathbb{P}(G_{n+1}^N = \tilde{G}_{n+1}^N | G_n^N = \tilde{G}_n^N)$ to induce an upper bound of $\mathbb{P}(G_{n+1}^N \neq \tilde{G}_{n+1}^N)$. Remember that

$$ \mathbb{P}(G_{n+1}^N = g | G_n^N, X_n^N) = P_{X_n^N}(g, G_n^N). $$

Let us recall that the intervals $I_{x,g}^N(i)$ are defining the inverse CDFs used for the sampling transitions of $G_{n+1}^N$ when $G_n^N = g$ and $X_n^N = x$. Now, let us see that if we have $G_n^N = \tilde{G}_n^N$, then we have $G_{n+1}^N = \tilde{G}_{n+1}^N$ if and only if there exist a $i \in \{1, \dots, \#E\}$ such that the random variable $\xi_{n+1}$ is in both $I_{X_n^N, G_n^N}(i)$ and $I_{X_0^N, \tilde{G}_n^N}(i)$. At each step, the two chains will remain equals if the random variable $\xi$ lands in a common region of their respective transition partitions. Then we can write,

$$ \begin{aligned} \mathbb{P}(G_{n+1}^N = \tilde{G}_{n+1}^N | G_n^N = \tilde{G}_n^N) &= \lambda \left( \bigcup_{i=1}^{\#E} \left( I_{X_n^N, G_n^N}(i) \cap I_{X_0^N, \tilde{G}_n^N}(i) \right) \right) \\ &= \sum_{i}^{\#E} \lambda \left( I_{X_n^N, G_n^N}(i) \cap I_{X_0^N, \tilde{G}_n^N}(i) \right). \end{aligned} $$

As we need to control the intersection of two segment, let's look at the difference of their upper and lower bounds. Whenever $G_n^N = \tilde{G}_n^N = g$, with $P^N$ being $L_P$-Lipschitz and $\|X_m^N - X_n^N\| \le \frac{|m-n|}{N} \|f\|_\infty$, it holds for any $i > 1$ that,

$$ \begin{aligned} | \min I_{X_n^N, G_n^N}(i) - \min I_{X_0^N, \tilde{G}_n^N}(i) | &\le \sum_{j=1}^{i-1} | P_{X_n^N}(g,j) - P_{X_0^N}(g,j) | \\ &\le L_P \sum_{j=1}^{i-1} | X_n^N - X_0^N | \le L_P(i-1) \frac{n}{N} \|f\|_\infty, \end{aligned} $$

and for $i < \#E$ that,

$$ \begin{aligned} | \max I_{X_n^N, G_n^N}(i) - \max I_{X_0^N, \tilde{G}_n^N}(i) | &\le \sum_{j=1}^{i} | P_{X_n^N}(g,j) - P_{X_0^N}(g,j) | \\ &\le L_P \sum_{j=1}^{i} | X_n^N - X_0^N | \le L_P i \frac{n}{N} \|f\|_\infty, \end{aligned} $$

We also know that for any two intervals: $I_1 = [a_1, b_1]$, $I_2 = [a_2, b_2]$,

$$ \lambda(I_1 \cap I_2) = (\min\{b_1, b_2\} - \max\{a_1, a_2\})_+ . $$

Using our notation we have,

$$ \lambda(I_{X_n^N, g}^N(i) \cap I_{X_0^N, g}^N(i)) \ge (\min\{\max I_{X_n^N, g}^N(i), \max I_{X_0^N, g}^N(i)\} - \max\{\min I_{X_n^N, g}^N(i), \min I_{X_0^N, g}^N(i)\})_+ . $$

Therefore using our previous bounds,

$$ \begin{aligned} \lambda(I_{X_n^N, g}^N(i) \cap I_{X_0^N, g}^N(i)) &\ge \left( \left[ \max I_{X_0^N, g}^N(i) - L_P i \frac{n}{N} \|f\|_\infty \right] - \left[ \min I_{X_0^N, g}^N(i) + L_P (i-1) \frac{n}{N} \|f\|_\infty \right] \right)_+ \\ &= \underbrace{\left[ \max I_{X_0^N, g}^N(i) - \min I_{X_0^N, g}^N(i) \right]}_{= P_{X_0^N}^N(g,i)} - L_P (i-1) \frac{n}{N} \|f\|_\infty - L_P i \frac{n}{N} \|f\|_\infty)_+ \\ &= (P_{X_0^N}^N(g,i) - L_P (2i-1) \frac{n}{N} \|f\|_\infty)_+ . \end{aligned} $$
And finally, with $\sum_{i=1}^{\#E} P_{X_0^N}(g, i) = 1$, $\sum_{i=1}^{\#E}(2i-1) \le 2\#E$, and $n \le T$, there is a $C > 0$ such that,

$$ \begin{aligned} \mathbb{P} (G_{n+1}^N = \tilde{G}_{n+1}^N | G_n^N = \tilde{G}_n^N) &= \sum_{i=1}^{\#E} \lambda (I_{X_n^N, G_n^N}(i) \cap I_{X_0^N, \tilde{G}_n^N}(i)) \\ &\ge \left(1 - 2L_P \|f\|_{\infty} \frac{T}{N} \#E \right)_+ = \left(1 - C \frac{T}{N} \right)_+ . \end{aligned} $$

With this lower bound and $G_0^N = \tilde{G}_0^N$, an induction can be used to get,

$$ \begin{aligned} \mathbb{P} (G_{n+1}^N = \tilde{G}_{n+1}^N) &\ge \left(1 - C \frac{T}{N}\right)_+ \mathbb{P} (G_n^N = \tilde{G}_n^N) \\ \mathbb{P} (G_n^N = \tilde{G}_n^N) &\ge \left(1 - C \frac{T}{N}\right)_+^n \ge \left(1 - C \frac{T}{N}\right)_+^T . \end{aligned} $$

□

### A.5 Lemma 5.

$(G_n)_{n \in \mathbb{N}}$ is a Markov chain in $(E, \mathcal{P}(E))$ with $E$ finite. Its transition matrix is denoted $P$ and $\mu^n$ is the distribution of $G_n$ for all $n$. If the chain respects the Doeblin condition: there exist an integer $k$, a positive $c$ and a probability measure $q$ on $E$ s.t. $P^k(i, j) \ge c q(j)$ then,

$$ \begin{aligned} \|\mu^n - \mu\|_{TV} &= \frac{1}{2} \sum_{g \in E} |\mu^n(g) - \mu(g)| \le (1-c)^{\lfloor n/k \rfloor} \\ \mathbb{E} \left| \frac{1}{N} \sum_{n=1}^N 1\{G_n = g\} - \mu(g) \right| &= \mathcal{O}(N^{-1/2}) \quad \text{for any } g \in E, \end{aligned} $$

where $\mu$ is the invariant probability of the Markov chain.

*Proof.* The first point is classical results, we refer to [12] first section. Set

$$ \alpha_{\ell} = \sup_{i \in E} \| P^{\ell}(i, \cdot) - \mu(\cdot) \|_{TV} \le (1-c)^{\lfloor \ell/k \rfloor}, $$

so in particular, by recalling the definition of the total variation, $|\mathbb{P}(G_n = g) - \mu(g)| \le 2\alpha_n$ and also, $|\mathbb{P}(G_j = g | G_i = g) - \mu(g)| \le 2\alpha_{j-i}$. Let $S_N(g) = \sum_{n=1}^N 1\{G_n = g\}$.

The bias therm is,

$$ \left| \mathbb{E}[S_N(g)/N] - \mu(g) \right| = \frac{1}{N} \sum_{n=1}^{N} \left| \mathbb{P}(G_n = g) - \mu(g) \right| \le \frac{2}{N} \sum_{n=1}^{N} \alpha_n = O(N^{-1}). $$

The variance term is,

$$ \mathrm{Var}(S_N(g)) = \sum_{n=1}^{N} \mathrm{Var}(1\{G_n = g\}) + 2 \sum_{1 \le i < j \le N} \mathrm{Cov}(1\{G_i = g\}, 1\{G_j = g\}). $$

We have $\mathrm{Var}(1\{G_n = g\}) \le \frac{1}{4}$, and moreover, $|\mathrm{Cov}(1\{G_i = g\}, 1\{G_j = g\})| \le 2\alpha_{j-i} + 2\alpha_j$, as,

$$ \begin{aligned} \mathrm{Cov}(1\{G_i = g\}, 1\{G_j = g\}) &= \mathbb{P}(G_i = g) [\mathbb{P}(G_j = g | G_i = g) - \mathbb{P}(G_j = g)] \\ &\le |\mathbb{P}(G_j = g | G_i = g) - \mu(g)| + |\mathbb{P}(G_j = g) - \mu(g)|. \end{aligned} $$

Then we have,

$$ \mathrm{Var}(S_N(g)) \le \frac{N}{4} + 4 \sum_{h=1}^{N-1} (N-h) \alpha_h + 4 \sum_{j=2}^{N-1} (j-1) \alpha_j = O(N), $$
hence by Jensen (or Cauchy–Schwarz),

$$ \mathbb{E}|S_N(g)/N - \mathbb{E}[S_N(g)]/N| \le \frac{\sqrt{\mathrm{Var}(S_N(g))}}{N} = O(N^{-1/2}). $$

By combining the bias and the Jensen bound we conclude,

$$ \mathbb{E}\left|\frac{1}{N}S_N(g) - \mu(g)\right| = O(N^{-1/2}). $$

□