{"id":"664e391f-d476-44f1-ba0c-697e3b739acb","arxiv_id":"2506.21079","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under uniform ergodicity and Lipschitz assumptions, the rescaled parameter process of multi-agent RL learners in a finite-state Markov game converges weakly to the ODE that averages each update against the stationary distribution of the fast game state.","lead":"This paper proves that the learning dynamics of several reinforcement-learning agents playing a finite-state Markov game converge, after a careful time-and-learning-rate rescaling, to a deterministic ordinary differential equation. This gives analysts a tractable substitute for expensive simulations when studying questions like algorithmic collusion in dynamic markets.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4.2's verification of Assumption 3 is invalid for finite Markov games with sparse transition kernels, so the paper does not establish that its central theorem applies to its motivating class.","rationale":"The reader's weakest assumption, Assumption 3, is also the place I find the most load-bearing problem, but the issue is sharper than a mere limitation: the paper's own verification of Assumption 3 in Section 4.2 is internally invalid. The Q-table example asserts that uniform exploration guarantees a Doeblin minorization in two steps, but this requires the state transition kernel T to have a positive lower bound κ on every transition. For deterministic or sparse transition kernels, which include many finite-state Markov games, the wrapped chain decomposes into periodic or multiple communicating classes, so the unique invariant measure μ_x used to define β does not exist. The theorem itself remains a conditional statement, and the proof gaps the reader notes (Step 4's limit mixing, Lemma 3's perturbation step, the passage from pointwise to sup) appear fixable with standard arguments. Thus the conditional-accept verdict is appropriate, but the claimed practical scope should be narrowed or the example revised to environments with full-support transition kernels.","tokens_in":14870,"tokens_out":22345,"duration_ms":255725,"concrete_test":"Take the two-state deterministic alternating Markov game with S={1,2}, A={a,b}, T(1,a)=2 and T(2,a)=1 for all a, and a Q-table with softmax policy and ε-exploration. For several N and a grid of x-values in D, compute (P^N_x)^2 on E and check for a Doeblin minorization with common c and q. Alternatively, compute the spectral gap of P^N_x; if the chain is reducible or periodic, or the spectral gap is zero for some x, then the §4.2 verification fails and Assumption 3 is not satisfied by the claimed example.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 3 requires a uniform Doeblin minorization (P^N_x)^k(i,j) ≥ c q(j) on the wrapped-state space E = S×A×S, uniformly in x∈D and N. The only worked application, the Q-table example in §4.2, claims this follows from ε-uniform exploration because 'in two iterations the chain has a positive probability to explore any state of the wrapped game' and asserts (P^N_x)^2(i,j) ≥ (κε/#S)^2. This verification is not valid as written: the chain's transition is constrained by 1{s_n = s'_c}, so if T contains a zero-probability transition, e.g., a deterministic gridworld or the alternating game T(1,a)=2, T(2,a)=1, the wrapped chain is reducible or periodic and no uniform minorization over all of E exists. The displayed lower bound also swaps S for E and requires κ, the minimum of T, to be positive; for any sparse T, κ=0. Hence β(x), defined as the average against the unique invariant measure μ_x, is not even well-defined for such environments. This does not refute Theorem 1 under Assumption 3, but it undercuts the paper's central claim that the assumptions are mild and that Q-tables automatically satisfy them.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a homogenization limit for multi-agent reinforcement learning in finite-state Markov games. The agents' parameters are updated with step size N^{-1} while the wrapped state process (state-action-next-state) evolves at N times the base frequency. Under Lipschitz continuity of the update and policy and a uniform Doeblin condition on the wrapped-state transition matrices, the authors claim that the scaled parameter process X^N_{⌊Nt⌋} converges weakly to the solution of the ODE y' = β(y), where β is the update function averaged against the invariant measure of the fast chain. The paper also gives a Q-table/softmax example intended to satisfy the assumptions, and it provides a GitHub implementation. The main theorem is Theorem 1 in Section 3.2, with the proof in Section 3.3 and auxiliary lemmas in Section 3.4 and Appendix A.","tokens_in":15060,"tokens_out":10910,"duration_ms":123763,"significance":"If the result is correct, the paper provides a tractable deterministic approximation of MARL dynamics in stateful environments, which is directly relevant to the algorithmic-collusion literature and to the analysis of learning dynamics beyond stateless games. The wrapped-state construction is a useful modeling device, the limit ODE is defined from the primitives rather than fitted to data, and the paper includes a public implementation. However, the proof of Theorem 1 has several load-bearing gaps, and the verification that standard Q-tables satisfy the main assumption is not valid as written. These issues must be resolved before the result can be considered established.","major_comments":[{"comment":"The proof does not establish weak convergence of the process. Step 6 obtains, for each fixed n ∈ {0,...,tN}, an L1 bound E||X^N_n - y^N_n|| = O(N^{-1/5}), and then states that 'we pass to the sup to get the final result.' Passing from pointwise expectation bounds to a bound on E sup_{0≤t≤T} ||X^N_{⌊Nt⌋} - y^N_{⌊Nt⌋}|| requires a maximal inequality or a tightness/oscillation argument, which is not provided. The initial decomposition in the proof explicitly involves E sup, but all subsequent estimates only control fixed times. Without tightness of the sequence of processes in the Skorokhod topology, the claimed weak convergence to the ODE solution is not established; at most the argument yields convergence of finite-dimensional marginals in L1.","section":"Section 3.3, Step 6 (proof of Theorem 1)"},{"comment":"The verification that the Q-table example satisfies Assumption 3 is invalid for sparse transition kernels. The displayed bound (P^N_x)^2(i,j) ≥ (κε/#S)^2 is not justified: the wrapped transition P^N_x(g,g') contains the factor 1{s_n = s'_c}, so if the underlying game transition T has a zero-probability transition, the wrapped chain is reducible or periodic and no uniform Doeblin minorization over all of E can hold. The constant κ is defined as the minimum of T, so for any sparse T one has κ=0 and the lower bound degenerates. Even for positive κ, the bound uses #S instead of #E and ignores the deterministic constraint imposed by the indicator. This undercuts the paper's claim that the assumptions are mild and that standard Q-tables automatically satisfy them; Theorem 1 remains conditional on Assumption 3, but the motivating class may fail it.","section":"Section 4.2 (verification of Assumption 3)"},{"comment":"The rate derivation contains a flawed asymptotic condition and an unjustified reduction of constants. The text states 'when N = o(M^{-2})', but the expansion requires N/M^2 → 0, i.e. N = o(M^2); as printed, the condition is inverted. In addition, the expression with the positive part, 1 - (1 - C t/M)_+^{tN/M}, is replaced by 1 - (1 - M^{-1})^{N/M} without tracking the constants C and t. This may be fixable, but as written the optimization over M = N^α and the claimed N^{-1/5} rate are not rigorously derived from Lemma 4.","section":"Section 3.3, Step 5 and Lemma 4"},{"comment":"The definition κ(N) = max_{n∈{1,...,tN}} [E||X^N_n - y^N_n|| - (1/N) E||Σ_{k=0}^{n-1} β(X^N_k) - β(y^N_k)||] does not support the subsequent Grönwall argument. Inequality (6) has the form A_n ≤ C N^{-1/5} + B_n, and to apply discrete Grönwall one needs A_n ≤ C N^{-1/5} + (Lβ/N) Σ_{k=0}^{n-1} A_k, which requires first replacing the norm of the sum by the sum of norms. The current definition subtracts the norm of the sum, not the sum of norms, and does not imply the bound A_n ≤ κ(N) + (Lβ/N) Σ A_k. This is a gap in the final step of the proof, though it appears repairable by a straightforward triangle-inequality modification.","section":"Section 3.3, definition of κ(N) in Step 6"},{"comment":"Lemma 3 relies on 'classical perturbation theory for finite state Markov chains' with the assertion ||μ^N_x - μ_x||_TV ≤ C ||P^N_x - P^∞_x||_op, but no statement of the required conditions or a proof is given. In particular, the unperturbed chain P^∞_x must itself satisfy the uniform Doeblin condition; this follows from Assumption 3 by taking N→∞, but the argument is not made. The constant C in the perturbation bound may depend on the Doeblin constants, which are uniform by assumption, but this should be stated explicitly.","section":"Appendix A.3, Lemma 3"}],"minor_comments":[{"comment":"The statement says 'for any i, j ∈ S' but the state space of the wrapped chain is E = S × A × S; the minorization should be quantified over i, j ∈ E.","section":"Assumption 3"},{"comment":"The notation μ^N_x is defined in (3), but the theorem uses μ_x(g) without defining μ_x; the authors should define μ_x as the invariant measure of the N→∞ chain P_x (or as the limit of μ^N_x).","section":"Equation (3) and Theorem 1"},{"comment":"The lower bound on the joint policy is written as π(x,s) ≥ ε/#S, but with the given softmax-plus-exploration policy the per-agent lower bound is ε/#A_i, and the joint policy lower bound is a product over agents; the displayed bound is not dimensionally consistent.","section":"Section 4.2"},{"comment":"The notation (x)_+ is used but not defined in the statement, and the phrase 'et' in the lemma statement is a French word that should be 'and'.","section":"Lemma 4"},{"comment":"The asymptotic condition is printed as 'when N = o(M^{-2})'; this should read 'when N = o(M^2)' (or equivalently N/M^2 → 0) for the expansion 1 - exp(-N/M^2) ~ N/M^2 to be valid.","section":"Section 3.3, Step 5"},{"comment":"In Section 1.1, 'scientists wander' should be 'scientists wonder'.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":"The paper is a promising master's-level contribution with a clear modeling idea and a plausible averaging mechanism. The main theorem may well be true under Assumption 3, but the proof as written does not establish process-level weak convergence, and the worked Q-table example does not show that the assumptions hold for sparse games. These are load-bearing issues, so I recommend major revision rather than rejection. The authors should either prove tightness or explicitly weaken the claimed mode of convergence, and they should correct the Assumption 3 verification so that the paper's applicability claims match what is actually proved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something real: it gives a weak-convergence ODE limit for the parameter dynamics of MARL agents in finite-state Markov games, using a wrapped-state construction that turns the joint parameter-state process into a single inhomogeneous Markov chain. The averaging strategy is classical, as the paper honestly acknowledges, and the wrapped Markov game is a clean and legitimate extension to stateful MARL. No parameters are fitted; the limit β is defined from the primitives, so the result is falsifiable and reproducible.\n\nThat said, the soft spots are real, and one of them is more than cosmetic. The verification of Assumption 3 in Section 4.2 is wrong as written. The bound (P^N_x)^2(i,j) ≥ (κε/#S)^2 uses the wrong cardinality (it should be #E, not #S) and requires κ, the minimum of the transition kernel T, to be positive. For any sparse or deterministic transition kernel, κ = 0, and for deterministic cycles the wrapped chain is periodic, so no uniform Doeblin minorization holds over all of E. The paper therefore does not establish that its motivating Q-table class satisfies the theorem's central assumption. The theorem itself is conditional and remains plausible, but the “mild assumptions” claim is overstated.\n\nThe proof gaps flagged by the reader check out: Step 4 mixes β^N and β and uses the limit invariant measure μ where the frozen-chain measure μ^N belongs; Lemma 3 invokes unproved perturbation theory with no reference; and the passage from pointwise grid estimates to weak convergence of the continuous-time process is sketched too quickly. These look fixable rather than fatal. The bias from the β^N vs β difference is already accounted for in the block decomposition, so a careful rewrite should close the gap.\n\nThe paper has no experiments, so the claimed practical value for algorithmic collusion is asserted rather than demonstrated. The intended reader is someone working on fluid limits or ODE approximations of RL dynamics, who will find the wrapped-state framework useful even if the application section needs rework. It deserves a serious referee, but the referee should expect to require major revision, especially of Section 4.2 and the proof details.","headline":"A promising but rough paper: the ODE limit theorem is plausible, but the proof has fixable gaps and the Q-table example does not satisfy its own mixing assumption for sparse transition kernels.","tokens_in":15637,"tokens_out":6257,"would_cite":false,"duration_ms":66226,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J20","60F17","91A26"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a rescaled multi-agent reinforcement learning process converges weakly to a deterministic ODE whose drift is the update function averaged against the stationary distribution of the fast state.","keywords":["multi-agent reinforcement learning","Markov games","homogenization","averaging principle","ODE limit","Q-learning","stochastic approximation","Doeblin condition"],"falsifier":"Take a two-state, two-agent Markov game with Q-table learners whose softmax policy has zero uniform exploration in one state, so the Doeblin condition fails, and simulate the scaled process for increasing N; if the empirical paths X^N_{⌊Nt⌋} do not coalesce onto a single deterministic curve, the theorem's premise is violated. Alternatively, with positive exploration, compute β numerically from the invariant measures of the frozen chains and solve the ODE; if the scaled paths do not approach that solution at roughly the predicted $N^{{-1/5}}$ rate, the result is refuted.","tokens_in":14598,"feed_emoji":"🎲","tokens_out":6339,"duration_ms":67384,"temperature":0.7,"pith_summary":"This paper aims to show that the stochastic parameter updates of multiple reinforcement-learning agents playing a finite-state Markov game can, under a proper rescaling, be approximated by a single deterministic ordinary differential equation. The rescaling divides each parameter update by N and multiplies the update frequency by N, so the agents' parameters evolve slowly while the game state mixes fast. The limit ODE's drift at each parameter vector x is β(x) = Σ_g µ_x(g) f(x, g), the update function averaged against the stationary distribution of the fast wrapped-state chain. If the theorem holds, algorithm behaviour in dynamic environments—such as algorithmic pricing and potential collusion—can be studied with ODE tools instead of repeated stochastic simulation.","feed_headline":"Learning dynamics in finite-state games have an ODE limit","feed_subtitle":"Dividing updates and multiplying frequency averages fast state noise into a deterministic differential equation.","key_machinery":"The load-bearing construction is the wrapped Markov game: each period's (current state, joint action, next state) is packaged as a single wrapped state g ∈ E = S × A × S, so that the joint process (X_n, G_n) is a time-inhomogeneous Markov chain with transition kernel δ_{x+f(x,g)} ⊗ P_x(g, ·). Under the N-scaling, P^N_x depends on x + $N^{{-1}}$ f(x, g). The uniform Doeblin condition guarantees each frozen-parameter chain P^N_x has a unique stationary measure µ^N_x, and Lipschitz continuity of updates and policies makes the map x ↦ µ_x Lipschitz. The proof then splits the drift into blocks, couples the true chain to a chain with parameters frozen at block start, bounds the coupling error and the ergodic fluctuation by $N^{{-1/2}}$ per block, and uses an Euler scheme with a Grönwall argument to get the ODE limit at rate $N^{{-1/5}}$.","core_discovery":"The paper's central claim is Theorem 1: under continuity and Lipschitz assumptions on updates and policies and a uniform Doeblin mixing condition on the state-transition matrices, the sequence of scaled processes X^N_{⌊Nt⌋} converges weakly, as N→∞, to the solution of y'(t) = β(y(t)) with y(0) = X0. The drift β averages the agent's update function f(x, g) over the unique invariant measure µ_x of the wrapped Markov chain on E = S × A × S, which is the chain obtained when parameters are held fixed. The result is not a two-timescale stochastic approximation statement: it covers the transient learning period and does not assume convergence to an equilibrium. A worked example shows that Q-tables with a softmax policy and a positive uniform exploration rate satisfy the assumptions.","pith_inferences":["A natural extension is to stochastic rewards and batched updates, which the wrapped-state construction can accommodate by enlarging E; the same homogenization argument should carry over if the augmented chain still mixes uniformly.","The uniform Doeblin assumption excludes deterministic or near-deterministic exploration, common in late-stage deployed agents; treating exploration as vanishing with N might yield a different limiting object, such as a switched or piecewise-deterministic ODE rather than a single averaged one.","The N^{-1/5} rate suggests the averaged ODE is the zero-order picture; a functional central limit theorem around the ODE path would capture fluctuations and could give confidence bands for finite-N simulations.","If applied to pricing algorithms, one concrete use would be to compute β for a given game and check whether the ODE has stable collusive fixed points, then compare their basin of attraction with the stochastic process's empirical behaviour."],"forward_implications":["If the theorem is correct, the transient learning trajectory of any MARL algorithm satisfying the assumptions can be simulated by solving a deterministic ODE, avoiding repeated runs of the stochastic game.","The framework applies directly to Q-tables with softmax policies and positive exploration, a standard MARL setup, so the ODE approximation is relevant to deployed learners.","Because β is an average over the stationary measure, the ODE is invariant under proportional rescaling of the learning rate; the approximation removes a sensitive hyperparameter's transient influence.","The ODE's long-horizon accuracy is tied to the stability of its attractors: fixed points and limit cycles keep trajectories close, while diverging ODE dynamics indicate the approximation can break down.","For algorithmic collusion studies, the ODE provides an analytical tool to examine whether learning dynamics lead to non-competitive pricing, complementing simulation-heavy approaches."],"supporting_citations":[{"why":"Supplies the reinforcer formalism that the paper extends from stateless games to finite-state Markov games.","marker":"[4]"},{"why":"Provides the hydrodynamic scaling limit for pure jump Markov processes that motivates the N-scaling.","marker":"[5]"},{"why":"Offers the practical fluid-limit technique for Markov chains used as the starting point.","marker":"[6]"},{"why":"Gives differential-equation approximations for Markov chains that the paper adapts to stateful games.","marker":"[8]"},{"why":"Supplies the multiscale averaging theory whose homogenization result is specialized here.","marker":"[11]"},{"why":"Provides the Doeblin-mixing and total-variation bounds used for the ergodic concentration estimate.","marker":"[12]"}],"fun_headline_variants":["ODE limit for multi-agent learning in Markov games","Finite-state Markov games: learning dynamics converge to ODE","Multi-agent RL dynamics homogenize to a single ODE","Rescaled learning in Markov games yields deterministic ODE","Learning dynamics in Markov games become ODE under scaling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The assumption that the fast game state mixes uniformly, from every starting state, for every parameter value and every N; if some states are never visited with positive probability, the stationary measure used to define β may not exist or may vary discontinuously, and the ODE limit can fail.","fun_headline_variants_meta":{"raw":{"variants":["ODE limit for multi-agent learning in Markov games","Finite-state Markov games: learning dynamics converge to ODE","Multi-agent RL dynamics homogenize to a single ODE","Rescaled learning in Markov games yields deterministic ODE","Learning dynamics in Markov games become ODE under scaling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000177,"raw_usage":{"total_tokens":1233,"prompt_tokens":828,"completion_tokens":405,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":444,"completion_tokens_details":{"reasoning_tokens":326}},"tokens_in":444,"tokens_out":405,"duration_ms":4425,"temperature":1.0,"reasoning_tokens":326,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:35:36.990569+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-state, two-agent Markov game with Q-table learners whose softmax policy has zero uniform exploration in one state, so the Doeblin condition fails, and simulate the scaled process for increasing N; if the empirical paths X^N_{⌊Nt⌋} do not coalesce onto a single deterministic curve, the theorem's premise is violated. Alternatively, with positive exploration, compute β numerically from the invariant measures of the frozen chains and solve the ODE; if the scaled paths do not approach that solution at roughly the predicted $N^{{-1/5}}$ rate, the result is refuted.","supporting_citations":[{"cited_title":"Solutions of ordinary differential equat ions as limits of pure jump markov processes","cited_arxiv_id":null,"evidence_quote":"Provides the hydrodynamic scaling limit for pure jump Markov processes that motivates the N-scaling."},{"cited_title":"Fluid Limits of Pure Jump Markov Processes: a Practical Guide","cited_arxiv_id":"math/0210109","evidence_quote":"Offers the practical fluid-limit technique for Markov chains used as the starting point."},{"cited_title":"Differential equation approximati ons for markov chains","cited_arxiv_id":null,"evidence_quote":"Gives differential-equation approximations for Markov chains that the paper adapts to stateful games."},{"cited_title":"Multiscale methods: averaging and homogenization , volume 53","cited_arxiv_id":null,"evidence_quote":"Supplies the multiscale averaging theory whose homogenization result is specialized here."},{"cited_title":"Lectures on finite markov chains","cited_arxiv_id":null,"evidence_quote":"Provides the Doeblin-mixing and total-variation bounds used for the ergodic concentration estimate."}],"review_version":1}