CS Paper Radar

Evolutionary Stability Does Not Guarantee Learning Accessibility: A Multi-Agent Reinforcement Learning Perspective on Cooperation Emergence

Yijie Wang

cs.AI ·submitted 2026-09-23 10:35 UTC · v1

Abstract

Cooperation emergence is a central problem in multi-agent systems because decentralized agents must coordinate while adapting to the changing behavior of others. Evolutionary game theory identifies strategically stable outcomes, but stability under a population adjustment dynamic need not imply that finite-sample learning agents can reach the same outcome through local reward feedback. We study this distinction in a transparent three-agent governance-motivated game involving a government, a platform firm, and users. We derive replicator dynamics for the fixed stage-game incentives, evaluate the cooperative evolutionary basin on a symmetric initial-condition grid, and compare it with learning-basin estimates for three decentralized value-based learners. The learning analysis uses independent Q-learning with $\varepsilon$-greedy action selection, scaled Boltzmann exploration, and SA--EA BQL under the same payoff environment and outcome criterion. The evolutionary basin has volume $V_E=1.00$ on the sampled grid. The empirical learning basin is $0.88$ for $\varepsilon$-IQL and $0.00$ for both scaled Boltzmann and SA--EA BQL. Diagnostic traces show that broader action diversity and nonzero value separation can coexist with failure to sustain the cooperative joint action in this fixed configuration. These results indicate that evolutionary stability and learning accessibility are distinct properties of a coupled game--learning system. The shared-bike setting is a motivating application; the broader contribution is a framework for comparing population-level stability with the finite-sample accessibility of cooperation under specified multi-agent learning dynamics.

Closest papers

Nearest neighbours by meaning across the whole index.

Multi-Agent Learning of Reactive Strategies in Iterated Games

cs.GT physics.soc-phq-bio.PE ·2026-10-10 ·James P. Wolfe, Joshua B. Plotkin
theorycode/data similarity 0.69
Abstract · 27 pages, 14 figures (12 pages + 3 figures main text; 15 pages + 11 figures Supplemental Material). Code: https://github.com/james-wolfe/rea…

Learning agents, whether humans or algorithms, adapt to one another rather than to a fixed environment. Selfish learning need not produce a good outcome for the group, especially when learners face a social dilemma. The iterated prisoner's dilemma (IPD) is the classical example, but it is usually studied in populations of agents who imitate successful strategies. Here, we instead study selfish gradient ascent learners on the two-dimensional space of reactive strategies. A reactive strategy is described by two continuous traits: reciprocity, the chance of cooperating after the co-player cooperates, and forgiveness, the chance of cooperating after the co-player defects. Each learner updates its strategy in the direction that most rapidly improves its payoff against all other learners, by an amount governed by its learning rate. We show that heterogeneity in learning rates can qualitatively change the long-term outcome: a population with uniform learning rates converges to always-defect (ALLD), whereas a population with variable learning rates approaches generous-tit-for-tat (GTFT), which produces nearly optimal collective payoffs. In simulations, every population passes through a transient state of minimal forgiveness, in which the distribution of reciprocity determines the outcome. Variable learning rates promote cooperation because slow learners preserve high reciprocity until the population reaches this state. We prove sufficient conditions on the distribution of reciprocity for convergence to ALLD or to tit-for-tat (TFT). Variable learning rates also allow cooperation to recover from perturbation, which is provably impossible under uniform learning. These results suggest that purely selfish and myopic learning can produce persistent cooperation provided the population has intrinsic variability in learning rates.

0.40

Exploiting Aggregate Feedback for Decentralized Equilibrium Learning in Markov Games: A Smart Grid Application

cs.GT ·2026-11-17 ·Siying Huang, Yifen Mu, Ge Chen, Qingshan Jia
similarity 0.67
Abstract

In many multi-agent systems, an agent's payoff depends on its own action and an aggregate of other agents' actions, rather than their individual decisions. This paper investigates decentralized equilibrium learning in Markov games (MGs) with such aggregative reward structures. However, existing decentralized learning algorithms for general MGs typically rely on bandit feedback, without exploiting the additional information available from aggregate observations. To exploit this information, we develop an aggregation-predictive stage-based V-learning algorithm with hybrid-feedback Exp3-IX. Using known local reward functions and observed aggregate quantities, each agent evaluates the immediate rewards of all candidate actions and predicts their immediate losses from historical aggregate feedback, while continuation values are learned from selected-action state transitions. The algorithm requires neither opponents' individual information nor knowledge of the transition kernel. We establish a high-probability regret bound that explicitly depends on aggregate prediction errors and retains the standard worst-case order. Under a regularity condition on adaptive stage lengths, the algorithm learns an $ε$-approximate coarse correlated equilibrium (CCE) within $\widetilde O(SA_{\max}T^5/ε^2)$ episodes and extends to correlated equilibrium (CE) learning. We further apply the algorithm to a renewable-rich microgrid with strategic prosumers and shared energy storage. Numerical results show smaller deviation gaps and lower gap-AUC than three learning baselines. Compared with representative demand-response rules, the learned policies exhibit weaker incentives for unilateral deviations while maintaining favorable user rewards, high renewable utilization, and relatively stable electricity prices.

0.11

An Evolutionary Computation Framework for Multi-Agent Q-Learning with Mean-Field Environmental Feedback

cs.MA cs.AI ·2026-09-05 ·Lichen Wang, Shijia Hua, Linjie Liu
similarity 0.66
Abstract

Multi-agent reinforcement learning in networked populations is governed by the interaction between individual adaptation, local encounters, and changing environmental conditions. To study this interaction, we formulate a coupled learning--environment model in which agents update stateless $Q$-values on a fixed graph, while their population-average behavior drives an environmental variable that dynamically modifies the payoff matrix. Under a first-order mean-field closure, we derive a deterministic transport equation for the population distribution of $Q$-values and couple it with a projected discrete update for the environmental state. The resulting model is evaluated against finite-network Monte Carlo simulations on random regular, Erdős--Rényi, Barabási--Albert, and random geometric graphs. Across the tested parameter ranges, the mean-field system reproduces the main macroscopic cooperation and environmental trajectories, and the trajectory-level root-mean-square error generally decreases with population size and average degree. The analysis further shows that environmental feedback reshapes the learned action-value ordering, while reinforcing feedback can produce pronounced dependence on the initial learning bias and resource level. The environmental timescale also plays an important role: a rapid response can drive the resource state to a boundary before learning adapts, whereas a slower response preserves the interaction between behavioral learning and environmental recovery. These results provide a population-level description of coupled reinforcement learning and environmental dynamics and characterize the performance of the mean-field approximation within the tested network and parameter ranges.

0.20

Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning

cs.GT math.OCcs.LG ·2026-10-11 ·Gunes Akbas, Naci Saldi, Berkay Anahtarci, Can Deha Kariksiz
theory similarity 0.65
Abstract · 37 pages, 1 figure, 2 tables

We study stationary discrete-time mean-field games with finite state and action spaces under the average-reward criterion, with an entropy-regularized objective and population-dependent dynamics and rewards. Under a minorization condition, the soft Q-operator is a span-seminorm contraction for the full transition kernel, so relative value iteration does not require the minorizing measure. When the Lipschitz constant of the kernel is below the minorization mass and the temperature exceeds an explicit threshold, the equilibrium fixed-point operator is a contraction: an equilibrium exists, its population distribution is unique, and a fixed-point iteration converges to it geometrically. We then learn the equilibrium model-free from a simulator, combining soft Q-learning at a fixed population distribution with an empirical transition kernel. We prove a finite-sample bound for soft Q-learning in the span seminorm, with temperature-independent constants, and derive convergence rates for the learned population distribution and policy. A congestion-aware routing game illustrates the results.

0.26

Finite-Sample Convergence in Networked Average Reward MARL: Decentralization Pitfalls and Entropy Remedies

cs.LG cs.MA ·2026-11-02 ·Yizhou Zhang, Yashaswini Murthy, Laixi Shi, Adam Wierman
similarity 0.64
Abstract

We study the problem of average reward Multi-Agent Reinforcement Learning (MARL) where agents interact within a network. Each agent in the network conducts local updates with information within its $k$-hop neighborhood and collaboratively maximizes the overall reward of the entire network. We first provide impossibility results in achieving convergence to the global optimal joint policies in our setting. These impossibility results highlight the challenges of decentralized learning with local information in multi-agent systems, namely the issues of multiagency, where each agent independently optimizes its policy, and partial observability, where agents have limited visibility into the global state. Given these challenges which indicate that decentralized policy optimization can generally be certified only up to stationarity, we provide finite-sample convergence guarantees for a decentralized actor-critic algorithm with linear function approximation that converges to an approximate stationary point with small gradient norm. To overcome such impossibility results, we further show that adding fixed-state entropy regularization reshapes the objective landscape which leads to even stronger global convergence guarantees for our proposed actor-critic algorithm.

0.18

A learner-free swarm approximates the explore-exploit equilibrium allocation: A self-organized attractor in place of reinforcement-learning machinery

cs.LG cs.AIcs.SImath-ph+2 ·2026-10-18 ·Galen J. Wilkerson
code/data similarity 0.63
Abstract · 26 pages, 13 figures, 5 tables, code and data: https://github.com/galenwilkerson/self-organizing-reinforcement-learning

Reinforcement learning (RL) solves the explore-exploit problem by training a learner on reward; its multi-agent, resource-sharing form has an equilibrium allocation as its optimum -- the ideal-free distribution (IFD), the Nash equilibrium of a congestion game. We show a minimal swarm approximates it with no learner at all. We present a decentralized, learner-free method for this problem: agents explore by heavy-tailed (Levy) flights, recruit neighbours to a discovery through a degree-normalized threshold cascade, and disperse as a patch crowds. The method drives the collective to the shape of the equilibrium allocation (pooled spatial matching slope 1.14, R^2=0.61) with no training, no stored parameters, and no reward in its dynamics; it reaches this as a self-organized attractor and holds it, re-finding it when the resources move -- though it reaches the shape, not the exact equilibrium, and stays measurably exploitable (Nash-gap 1.46). Coupling recruitment to movement causes the allocation: removing it collapses the matching (slope 0.006). Against Proximal Policy Optimization (PPO) learners (feedforward, centralized-critic, graph message-passing, and recurrent) trained in the same sensing-limited environment, the method at zero training is the only arm left unbiased w.r.t. the IFD gradient (slope ~1, CI containing 1, vs learners 0.69-0.97, all under-concentrating) and ties the best learner's harvest where resource is clustered, while the learner collects more where resource is scarce (0.33 vs 0.22) and holds a tighter per-capita intake. Learning buys precision and transfer across reward structures, not a better allocation shape. A companion paper develops the mechanism.

0.42

Mitigating Retaliatory Algorithmic Collusion in Repeated Games

cs.LG cs.AI ·2026-09-17 ·Karthik Sivachandran, Rohan Paleja
similarity 0.63
Abstract

Reinforcement learning agents trained to maximize their own reward in repeated interactions can converge to supra-competitive outcomes resembling explicit collusion, without communication or shared design. Existing mitigation approaches are largely tied to specific economic settings, like two-sided platforms and auctions, leaving open how to design interventions for general repeated games. We address this gap by formalizing the connection between empirical observations from prior work on Q-learning collusion and classical theory of Simple Penal Codes (SPCs). We show any non-trivial SPC induces a quantifiable conditional dependence in agents' policies, detectable via the total variation distance between an agent's action distributions across cooperation and defection histories. Building on this connection, we propose CURB (Collusion Unwinding via Reward shaping and Belief injection), a reward-shaping framework that penalizes this Total Variation (TV) distance signal during Q-learning and is guaranteed to convert any SPC fixed point of the dynamics into a trivial one, thus precluding collusive equilibria sustained by punishment threats. Empirically, CURB substantially reduces collusion by Q-learning agents in both Bertrand and Cournot Competition Repeated Games. We further demonstrate that CURB extends to deep Q-network agents in Bertrand competition, suggesting the mechanism generalizes beyond tabular Q-learning.

0.43

Cooperation Without Shared Rewards via Reciprocal Q-Augmentation

cs.GT cs.AIcs.MA ·2026-10-17 ·Francesco Morri, Adel Abusitta, Quentin Cappart, Margarida Carvalho
similarity 0.63
Abstract

General-sum games are more challenging than fully cooperative or adversarial settings because agents may deceive or exploit one another. Achieving high social welfare requires sustained cooperation, while a single defection can drive agents toward a welfare suboptimal Nash equilibrium. Moreover, assuming access to other agents' rewards or internal states is often unrealistic and implicitly introduces additional cooperation into the setting. To address this issue, we introduce \textit{Reciprocal Q-Augmentation} (RQA), a method that uses a latent-variable opponent model to augment the Q-function with estimates of how one's actions affects other agents. RQA allows agents to learn both cooperative and defective policies using only their own Q-function. We show that, in social dilemmas, agents that all follow the cooperative policy of RQA learn to cooperate faster and reach higher levels of cooperation than fully cooperative algorithms. Moreover, a single RQA agent that switches appropriately between its cooperative and defecting policies can induce cooperation in agents trained with standard RL algorithms, which would otherwise end up defecting. We evaluate our approach on the Iterated Prisoner's Dilemma, Iterated Traveler's Dilemma, Iterated Stag Hunt, and \texttt{CleanUp-Lite}. Our experiments show that the algorithms implementing RQA outperforms fully cooperative methods with shared rewards and enables cooperation with algorithms that otherwise fail to reach high social welfare.

0.16