- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies a finite-state continuous-time mean field game with congestion-dependent action-completion rates. Under a convex congestion potential, it derives an Eisenberg-Gale-type equilibrium characterization and analyzes several exact best-response dynamics. The key equilibrium-recovery result for the physical population is mainly a rare-revision limit result.
Critical strengths
- The paper is technically substantial, and the equilibrium characterization is developed carefully under the stated assumptions.
- The event-driven formulation is meaningful, and the paper correctly distinguishes policy convergence from convergence of the physical state-policy population.
Critical weaknesses
- The central 'learning' mechanism assumes exact stationary payoffs H(ν) for all policies from the current policy distribution, even while the actual population is not stationary. This oracle assumption removes payoff estimation and exploration, which are central to learning in MFGs. The paper itself leaves model-free learning from observed transitions and rewards as future work. I therefore view the main result as convergence of exact best-response dynamics rather than a convincing learning result for ICLR.
- For fixed positive κ or ε, the paper generally proves convergence only of the policy marginal, not of the full state-policy population to a stationary MFG equilibrium. Recovery of the physical equilibrium is obtained mainly as κ or ε tends to zero, and event-driven dynamics can be nonconvergent at ties. The restrictive potential/unichain assumptions and a single illustrative Manhattan experiment without learning baselines further limit the contribution's generality and empirical support.
Questions for authors
- What guarantees survive when H(ν) must be estimated from trajectories rather than computed exactly from the known model?
- For fixed nonzero κ or ε, when does the full state-policy population converge to an MFG equilibrium beyond the strict-pure-equilibrium case?
3 comments
Response to Reviewer pBmn Part 2
Q2&W2
Q2. For fixed nonzero κ or ε, when does the full state-policy population converge to an MFG equilibrium beyond the strict-pure-equilibrium case?
W2. For fixed positive κ or ε, the paper generally proves convergence only of the policy marginal, not of the full state-policy population to a stationary MFG equilibrium. Recovery of the physical equilibrium is obtained mainly as κ or ε tends to zero, and event-driven dynamics can be nonconvergent at ties.
Thank you for asking about convergence beyond strict pure equilibria. For the original best-response revision rules, an agent can switch between equally good policies even at a policy equilibrium. Such switches can change the state–policy population and disturb state balance, so convergence of the policy marginal alone does not ensure population convergence. Remark 37 gives a periodic event-driven trajectory illustrating this issue. This motivates making acceptance of a revision opportunity depend on the payoff improvement. Tempered best-response acceptance and our Brown–von Neumann–Nash (BNN) protocols give state–policy equilibrium-set convergence at fixed positive opportunity parameters. Both mechanisms combine policy improvement with a revision term that vanishes as the incentive to switch disappears.
Specifically, fix an exogenous opportunity rate or an event-driven opportunity probability . An agent using policy accepts a revision opportunity with probability
and, upon acceptance, draws a best response with probability distribution , where is a common measurable best-response selection. In the event-driven model, this decision is made at the arrival state after action completion. This is a normalized tempered best-response rule [1]. An optimal policy is kept, while a small payoff improvement leads to a small acceptance probability.
For exogenous revision, the policy potential satisfies
=\kappa\sum_\pi\nu_\pi \left(1-\frac{H_\pi(\nu)}{\max_{\pi'}H_{\pi'}(\nu)}\right) \log\frac{\max_{\pi'}H_{\pi'}(\nu)}{H_\pi(\nu)}\ge0.$$ For event-driven revision, replace $\kappa\nu_\pi$ by $\varepsilon\chi_\pi$, where $\chi_\pi$ is the policy completion rate. The uniform payoff and completion-rate bounds imply that the rate of increase of $\Phi$ is at least a positive constant times the squared potential gap. Since $\Phi$ is bounded above by $\Phi^{\ast}$, the gap must tend to zero. At a policy equilibrium, every policy with positive mass is optimal. Consequently, the total revision term tends to zero even though the opportunity parameters remain fixed. The frozen state–policy convergence argument then gives, from every initial state–policy population, $$\\|\eta(t)-\bar\eta^{\nu(t)}\\|_1\to0, \qquad \operatorname{dist}\bigl(\eta(t),\mathcal E_{\mathcal S\times\Pi}^{\ast}\bigr)\to0.$$ The same principle applies to the BNN protocols. For exogenous BNN, policy improvement is measured by the positive payoff excess $$\left[H_\pi(\nu)-\frac1m\sum_{\pi'}\nu_{\pi'}H_{\pi'}(\nu)\right]^+.$$ The event-driven version uses an average payoff weighted by policy completion shares. These excesses vanish at policy equilibrium, so the revision term also vanishes. Propositions 33(i) and 39(i), in Appendices D.5 and E.6, establish convergence to the state–policy equilibrium set for every fixed $\kappa>0$ or $\varepsilon\in(0,1]$, respectively. If the equilibrium policy distribution is unique, convergence is to its single associated stationary population. We have added the tempered best-response acceptance argument in Appendix F.1, following the reciprocal revision schedules. ### **W1** > **W1.** The central 'learning' mechanism assumes exact stationary payoffs H(ν) for all policies from the current policy distribution, even while the actual population is not stationary. This oracle assumption removes payoff estimation and exploration, which are central to learning in MFGs. The paper itself leaves model-free learning from observed transitions and rewards as future work. I therefore view the main result as convergence of exact best-response dynamics rather than a convincing learning result for ICLR. Thank you for raising this point. Model-free multi-agent learning with congestion-dependent dynamics is a key motivation for this study, and we agree that estimation and exploration are central to that goal. The oracle assumption allows us to take a foundational first step: understanding the population and policy dynamics when the model is known and stationary payoffs can be evaluated accurately. We believe our model-based analysis provides the convergence framework for studying learning from observations.W2 Cont.
W2. The restrictive potential/unichain assumptions and a single illustrative Manhattan experiment without learning baselines further limit the contribution's generality and empirical support.
Thank you for these comments. We clarify the model assumptions and their scope, and explain the purpose of the numerical study below.
Potential assumptions. The potential-congestion assumption applies to a broad class of games with shared-resource congestion. In traffic routing, an action uses a route and its mean travel time is the sum of the delays on its roads. Two routes sharing a road experience the same marginal effect from an increase in that road's flow. Integrating each road's smooth, nondecreasing delay over its flow and summing over roads produces the required convex potential. The same construction applies to packet routes sharing communication links and processing actions sharing service pools. It permits overlapping resource use and nonseparable congestion between different actions and states. This shared-resource structure is classical in congestion games and traffic models [2, 3], and throughput-dependent sojourn times also appear in approximations for closed queueing networks [4].
Unichain assumptions. The unichain restriction applies only to the policy space explored by the revision process. A policy is unichain when its induced Markov chain has exactly one recurrent class; transient states are allowed. This gives each policy a unique invariant probability distribution and a stationary payoff independent of the agent's initial state, as in standard average-reward MDP analysis [5]. We take to contain all deterministic unichain policies. Even with this restriction, agents can have a very large policy space to explore. For example, when every deterministic policy is unichain, contains all deterministic policies, so the number of available policies grows exponentially with the number of states. The assumption on the underlying MDP is only weak communication. Apart from states that are transient under every stationary policy, each state can reach any other under a suitable deterministic stationary policy. This condition also allows multichain policies in the underlying model. Weakly communicating MDPs form a standard, general class in average-reward reinforcement learning, including the analyses of Wan, Yu and Sutton [6], REGAL [7], and Wei et al. [8]. Under this condition, Lemma 22 guarantees that contains an optimal policy for every positive sojourn-time vector. Thus restricting policy revision to this family preserves the optimal average reward in every stationary environment.
Empirical support. The purpose of the numerical study is to demonstrate convergence and provide numerical support for the paper's theoretical results in a concrete congestion-dependent model. The four dynamics illustrate convergence toward population stationarity under a fixed policy, decreasing exploitability under best-response policy dynamics, and improvement in both quantities under the two state–policy systems. The revision-frequency comparison further shows that less frequent revision reduces residual flow imbalance, consistent with the rare-revision results; this comparison uses a fixed slow-time window.
Thank you again for your constructive comments. We have revised the paper as described above, with the manuscript changes highlighted in blue. We hope our responses address your questions and concerns. We welcome any further questions.
References
- Dai Zusai. 2018. Tempered best response dynamics. International Journal of Game Theory 47, 1–34.
- Robert W. Rosenthal. 1973. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 2, 65–67.
- Tim Roughgarden and Éva Tardos. 2002. How Bad Is Selfish Routing? Journal of the ACM 49(2), 236–259.
- Frank P. Kelly. 1989. On a Class of Approximations for Closed Queueing Networks. Queueing Systems 4, 69–76.
- Martin L. Puterman. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons.
- Yi Wan, Huizhen Yu, and Richard S. Sutton. 2024. On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes. arXiv preprint arXiv:2408.16262.
- Peter L. Bartlett and Ambuj Tewari. 2009. REGAL: A Regularization Based Algorithm for Reinforcement Learning in Weakly Communicating MDPs. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI '09). AUAI Press, 35–42.
- Chen-Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. 2020. Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020). Proceedings of Machine Learning Research 119, 10170–10180.
Response to Reviewer pBmn Part 1
Thank you for your comments on the information needed for learning, population convergence, and empirical support. Our point-by-point responses are as follows.
Q1
Thank you for raising this question. Our key convergence results remain valid when agents choose best responses to increasingly accurate estimates of H(ν) obtained from trajectories. At any fixed positive revision rate or probability, the policy marginal converges to the equilibrium set as the estimation errors tend to zero uniformly across policies. With the diminishing revision schedules described below, the state–policy population also converges to the stationary MFG equilibrium set.
To make this precise, let Hπ(t) estimate the stationary payoff Hπ(ν(t)), and suppose that, for almost every t,
\le c_{\rm err}(t),$$ where $c_{\rm err}$ is nonnegative, measurable, and locally bounded. Agents choose policies maximizing these estimates, using a common measurable selection $\gamma(t)\in\mathcal M_m(\Pi)$ supported on $\arg\max_\pi\widetilde H_\pi(t)$ and revision probabilities $\gamma(t)/m$. Under Assumptions 1 and 4, consider a global absolutely continuous trajectory with a continuous revision rate $\kappa(t)>0$ or revision probability $\varepsilon(t)\in(0,1]$, in physical time. The key observation is that a best response to the estimates loses at most $2c_{\rm err}(t)$ in true payoff: one estimation error concerns the chosen policy, and the other concerns a true best response. Since the true payoffs have a uniform positive lower bound $c_{H,\min}$, the corresponding loss in logarithmic payoff is at most $2c_{\rm err}(t)/c_{H,\min}$. This gives a direct perturbation of the policy-potential argument. The potential gap $\Delta(\nu)=\Phi^{\ast}-\Phi(\nu)$ measures how far the policy potential $\Phi(\nu)$ is below its maximum $\Phi^{\ast}$. Since the maximizers of $\Phi$ are exactly the equilibrium policy distributions, this gap is zero precisely at policy equilibrium. We obtain $$\begin{aligned} \dot\Delta(\nu(t)) &\le-\kappa(t)\Delta(\nu(t)) +\frac{2m\kappa(t)}{c_{H,\min}}c_{\rm err}(t), &&\text{exogenous revision},\\\\ \dot\Delta(\nu(t)) &\le-\varepsilon(t)\underline\lambda\Delta(\nu(t)) +\frac{2m\varepsilon(t)\overline\lambda}{c_{H,\min}}c_{\rm err}(t), &&\text{event-driven revision}. \end{aligned}$$ Here $m$ is the population mass, and $\underline\lambda,\overline\lambda$ are the uniform lower and upper bounds on individual completion rates. The first term gives the exact-payoff decrease of the potential gap; the second quantifies the effect of payoff-estimation errors. If $\int_0^\infty\kappa(t')\\,dt'=\infty$ or $\int_0^\infty\varepsilon(t')\\,dt'=\infty$, respectively, integrating these inequalities yields $$\limsup_{t\to\infty}\Delta(\nu(t))\le \begin{cases} \displaystyle\frac{2m}{c_{H,\min}} \limsup_{t\to\infty}c_{\rm err}(t),&\text{exogenous revision},\\\\[4pt] \displaystyle\frac{2m\overline\lambda}{\underline\lambda c_{H,\min}} \limsup_{t\to\infty}c_{\rm err}(t),&\text{event-driven revision}. \end{cases}$$ The bounds quantify the effect of imperfect payoff estimates: halving the long-run payoff-error bound halves the corresponding upper bound on the potential's shortfall from its equilibrium value. When $c_{\rm err}(t)\to0$, the bounds give $\Delta(\nu(t))\to0$, so the policy marginal approaches $\mathcal E_\Pi^{\ast}$, including at fixed positive revision parameters. If the respective revision rate or probability also tends to zero under the same integral condition, the population tracks $\bar\eta^{\nu(t)}$ and approaches $\mathcal E_{\mathcal S\times\Pi}^{\ast}$. Thus vanishing payoff errors give policy optimality, while diminishing revision allows the state–policy population to approach stationarity. We have added these direct payoff-error bounds and convergence conclusions as Proposition 41, “Payoff-estimation errors,” in Appendix F.2.