CS Paper Radar

Fictitious Play When Agents Are Not Expected-Utility Maximizers: A Geometric Analysis in $2$-Action Games

Hao Liang, Solaleh Mohammadi, Kaiqing Zhang

cs.GT eess.SYmath.OC ·submitted 2026-11-12 18:52 UTC · v1

Abstract

Fictitious play (FP) is one of the earliest and most fundamental learning procedures in games, where each agent independently chooses a best response to the empirical distribution of opponents' past actions by maximizing the expected payoff with respect to it. However, learning agents may not always be expected-utility maximizers: they may use nonlinear evaluation functionals to account for the uncertainty induced by the opponents, e.g., via risk measures. In this work, we study nonlinear fictitious play (NL-FP), in which each pure action is evaluated by a general, possibly nonlinear functional of the payoff distribution induced by the opponent's empirical belief. To analyze NL-FP, we first identify a single-crossing property (SCP) of evaluation functionals that preserves the classical geometry of FP in $2\times2$ games. Furthermore, we conduct a novel geometric analysis of the convergence behavior of NL-FP in $2\times2$ games, even when the SCP fails. Beyond $2\times2$ games, we show that the convergence of NL-FP in $2\times n$ ($n\ge3$) games may fail even for continuous-time NL-FP, when the two-action player uses conditional value-at-risk (CVaR) in a $2\times3$ game. In addition, we identify a finite-crossing condition that ensures convergence of the selected continuous-time dynamics and the discrete-time iterates in general $2\times n$ games, which also provides new insights into the global landscape of continuous-time classical FP in such games.

Closest papers

Nearest neighbours by meaning across the whole index.

Regret, equilibrium, and learning in games: A guided tour

cs.GT cs.LGmath.OC ·2026-08-10 ·Panayotis Mertikopoulos
publishedtheory similarity 0.71
Abstract · 44 pages, 3 figures; to appear as a chapter in "Equilibria in Games: Existence, Selection, and Dynamics", edited by Sylvain Sorin and Bernha…

This note aims to serve as an entry point to the literature on learning in games, a topic with significant theoretical appeal and a wide range of applications -- from machine learning and data science to economics and beyond. Our presentation is structured around two complementary viewpoints: We first consider a single agent -- the learner -- engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment. We then examine what happens when the environment is shaped by the decisions of several interacting agents, not necessarily aware of each other's actions or goals, and all seeking to improve their individual rewards. In this general context, we examine a family of regularized learning policies based on best-responding to the past history of play, up to a regularization penalty intended to encourage exploration and prevent over-commitment to suboptimal choices. In the single-agent setting, we present some basic regret bounds for regularized learning in adversarial multi-armed bandits; in the multi-agent setting, we describe an ergodic equilibrium convergence result for zero-sum games in the spirit of classical results on fictitious play, as well as a "folk theorem" linking strategic and dynamic notions of stability -- Nash equilibria and attracting points of regularized learning, respectively. We pay special attention to the information available to the players and, through a unified analysis framework, we study both oracle- and payoff-based (bandit) methods. Our goal is to provide a coherent and comprehensible -- albeit, by necessity, not comprehensive -- account of some recent ideas in the field, and to discuss their implications for the study of rationality.

0.25

On the Convergence of First-Order Methods in Signaling Games

cs.GT ·2026-11-07 ·Rilind Sahitaj, Artem Tsikiridis, Martin Bichler
top venue similarity 0.68
Abstract · Accepted at NeurIPS 2026

We study first-order learning dynamics in Bayesian signaling games, a minimal extensive-form model of strategic interaction under asymmetric information. In these games, a Sender observes a private type and chooses a signal, after which a Receiver forms a posterior belief and selects an action. This Bayesian belief update makes the induced learning field fundamentally different from the affine game-gradient fields of normal-form games. Empirically, we find a sharp dichotomy: standard online learning algorithms reliably converge to strict Perfect Bayesian Equilibria (PE), but not to non-strict ones. We show that this behavior cannot be explained by the global geometric conditions commonly used to prove last-iterate convergence, such as monotonicity or the Minty variational inequality. Indeed, these conditions can fail even in binary signaling games. Instead, we identify the relevant local geometry. Our main result characterizes variational stability in finite signaling games: a PE is variationally stable if and only if it is strict. This yields local last-iterate convergence guarantees for online mirror descent and regularized dual averaging near every strict PE. We then study global average-iterate convergence and identify a class of signaling games in which coarse-trigger regret-minimizing dynamics converge to the unique PE. Finally, we complement the theory with experiments comparing projected gradient ascent, mirror-based methods, optimistic variants, and PPO across canonical signaling-game families. The results position signaling games as a compact testbed for understanding how Bayesian belief formation reshapes the convergence geometry of multi-agent learning.

0.35

Arbitrarily Slow Polynomial Convergence of Fictitious Play

cs.GT ·2026-10-06 ·Jacob Abernethy, John Lazarsfeld, Andre Wibisono
similarity 0.66
Abstract

We show that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games. For every integer $k \ge 2$, we construct a payoff matrix with $(k+1)^2 - 5$ actions per player for which the duality gap of the empirical strategies decays as $Θ(t^{-1/k})$ after $t$ steps. The family starts from the standard rock-paper-scissors matrix, with each higher-order game constructed recursively from the preceding one. After a prescribed common initial action, every subsequent best response under fictitious play is unique. For $k \ge 3$, these games give counterexamples to Karlin's conjectured $O(t^{-1/2})$ convergence rate, and they extend the recent $Θ(t^{-1/3})$ construction of Wang (2025) to arbitrarily slow polynomial rates.

0.41

Near-Optimal $\sqrt{K}$-Regret for Online Learning in Uninformed Markov Games

cs.LG stat.ML ·2026-11-01 ·Junyan Liu, Haipeng Luo, Lillian J. Ratliff, Zihan Zhang
similarity 0.66
Abstract

We study online learning in two-player uninformed Markov games, where the opponent may follow an arbitrary, unknown policy in each episode and the learner does not observe the opponent's actions. [TWYS21] showed that achieving sublinear external regret requires an exponential dependence on the episode length $H$. Motivated by this limitation, they studied the weaker notion of Nash-value regret and obtained an $\widetilde{O}(K^{2/3})$ regret bound, where $K$ is the number of episodes. More recently, [LLZR26] introduced a stronger notion called empirical Nash-value regret and achieved an $\widetilde{O}(\sqrt{K})$ bound when the opponent's non-stationarity is moderate, including the case where the opponent follows a fixed policy. However, whether the $\sqrt{K}$ rate is achievable in the worst case remained open. In this paper, we resolve this open question by developing an algorithm that achieves $\widetilde{O}(H^{3/2}S\sqrt{AK})$ empirical Nash-value regret against arbitrary opponent policies, where $S$ is the number of states and $A$ is the number of learner's actions. Specifically, our algorithm combines global and local planning by maintaining a collection of candidate predictions of future losses, each associated with a policy. Global planning learns which candidates to favor across episodes, while local planning combines their policies differently at each state to make decisions. A key ingredient is to coordinate these two components to control the discrepancy between local loss estimates and the total loss of the executed policy, using only the learner's observed trajectories.

0.12

Learning Rewards in Strategic Games

cs.GT cs.AIcs.LGcs.MA ·2026-10-15 ·Antoine Bergerault, Cyrille Kone, Giorgia Ramponi
similarity 0.66
Abstract

Understanding the objectives that drive agents' behavior is crucial in strategic environments, where multiple agents interact and adapt to one another. This challenge arises in domains such as cybersecurity, autonomous driving, and online markets, where agents' underlying incentives are typically unknown and must be inferred from their observed behavior. Inverse reinforcement learning (IRL) provides a natural framework for this problem, but extending IRL to strategic multi-agent settings introduces a fundamental challenge: a reward that explains observed behavior does not necessarily induce optimal strategies when used for decision-making. In this work, we study this problem through the lens of \emph{strategic identifiability}, and show that learning from a fixed policy pair can be insufficient to strategically identify rewards, independent of the number of expert samples $K$. Motivated by this, we introduce an active IRL algorithm for two-player repeated Stackelberg games, in which the leader adaptively selects policies to elicit informative responses about the follower's reward. Combining maximum-likelihood estimation with experimental design, we derive finite-sample guarantees on the Stackelberg sub-optimality induced by the learned reward, matching up to polylogarithmic factors a new minimax learning rate of $K^{-1/2}$. Finally, we evaluate our approach in a realistic anti-poaching setting, demonstrating the benefits of active exploration for reward recovery and downstream strategic performance.

0.21

On the Fragility of Efficiency: Uncoupled Learning with a Deviant

cs.GT ·2026-10-05 ·Vade Shah, Jason R. Marden
hot direction similarity 0.66
Abstract

An important question in learning in games is whether players can learn to achieve efficient outcomes, those that maximize the sum of their utilities, without communication or coordination. Completely uncoupled learning algorithms, which use only each player's own past actions and utilities, can guarantee this in broad classes of games, but they typically require every player to follow the same algorithm. In this work, we ask whether one can design welfare-maximizing learning algorithms that are robust to a deviant player. To study this question, we take a well-studied welfare-maximizing learning algorithm as a testbed and consider what happens when every player except one follows it. First, we consider a deviant player who either (i) always plays the same action or (ii) selects their action uniformly at random. We show that such a player can significantly alter the long-run behavior of this algorithm, leading to states that are far from welfare-maximizing, and that no completely uncoupled learning algorithm is robust to such a player in every game. Next, we consider a strategic deviant player who acts in their own interest and show that this player can adopt a different learning algorithm to shift the long-run outcome in their favor. Moreover, we show that under any completely uncoupled welfare-maximizing learning algorithm, there is a game in which some player benefits from switching to a different completely uncoupled learning algorithm. These results show that completely uncoupled welfare-maximizing learning is fragile, even to a single deviant player, suggesting that robustness may require communication or coordination.

0.26

From Scalar Games to Unconstrained Network Zero-Sum Games: Transfer Principles for Gradient-Based Learning

cs.GT ·2026-10-30 ·Gaoqi Xue, James P. Bailey
similarity 0.65
Abstract

We show that, for a broad class of gradient-based learning rules, scalar zero-sum games form a complete test family for convergence in unconstrained network zero-sum games. Specifically, suppose a learning rule achieves last-iterate or time-average convergence on every scalar game of magnitude $a$ whenever $η\leq f(a)$, where $f$ is nonincreasing. Then the same guarantee holds on an arbitrary network zero-sum game with stacked game operator $\mathbf{G}$ whenever $η\leq f(\lVert\mathbf{G}\rVert_2)$. More generally, finite-time rate guarantees transfer mode by mode: the network response is bounded by the largest response of its scalar canonical games, and under compatible linear initialization conventions the worst-case finite-time network response is exactly the largest scalar canonical rate. Thus, understanding the learning dynamics on scalar games is sufficient to characterize universal convergence and worst-case rates over the corresponding class of network games. The result follows from the classical planar decomposition of real skew-symmetric game operators. Related mode-wise reasoning has appeared implicitly in spectral analyses of particular learning algorithms and in prior work using these decompositions for game representation and visualization; here we isolate the resulting transfer principle for gradient-based learning. We discuss implications for simplifying convergence analysis, time-average guarantees, low-dimensional geometric arguments, accelerated-method design, and worst-case numerical testing.

0.18

DiffNash: Finding Nash Equilibrium in High-Dimensional Continuous Action Spaces with Diffusion Policies

cs.LG cs.AIcs.GTcs.MA ·2026-10-11 ·Haichuan Wang, Anagha Satish, Jiale Zheng, Saisneha Ghatti, Lingkai Kong +2 more
similarity 0.65
Abstract · 41 pages, 11 figures

Computing equilibria in high-dimensional continuous games requires learning and representing rich, multi-modal strategy distributions, something conventional neural policies struggle to achieve. Diffusion models offer a natural solution, but standard diffusion training requires direct samples from a fixed target distribution, which are generally unavailable under iterative game-solving updates. We propose a diffusion-based framework for equilibrium computation that enables diffusion-based variants of Online Mirror Descent (OMD) and Fictitious Play (FP). Our approach derives a reweighted score-matching objective that trains diffusion policies without requiring direct samples from each updated policy. Our main method, DiffNash, combines the fast convergence of OMD with the sample efficiency of FP by reusing past actions through a replay buffer. To correct the resulting distribution shift from sample reuse, we derive an unbiased estimator of the difference between current and past policies' Evidence Lower Bounds, whose exponential provides a tractable proxy for the corresponding importance weight without evaluating diffusion likelihoods. We evaluate our approach on forest protection games and continuous Colonel Blotto games, reducing the Nash gap over the strongest baseline by 35.6% and 24.7%, respectively, with minimal hyperparameter tuning.

0.27