CS Paper Radar

Suboptimality Loss for Inverse Learning from Imperfect Equilibria

Andreas Feik, Pierre Pinson, Dario Paccagnan

cs.GT ·submitted 2026-09-19 20:00 UTC · v1

Abstract

Many modern systems involve the strategic interaction of multiple agents. In such settings, observed actions typically reflect equilibrium behavior under utilities that are only partially known. Recovering these hidden utilities from data - the central goal of inverse game theory - is key for prediction, counterfactual analysis, and mechanism design. However, existing approaches based on inverse variational inequalities are highly sensitive to noisy and inconsistent equilibrium observations, thus limiting their applicability. In this paper, we resolve this issue by introducing a game-theoretic suboptimality loss that measures the aggregate utility gain players could obtain by unilaterally deviating from an observed strategy profile. First, we show that this loss is convex and admits an efficient decomposition into player-wise best-responses. Second, we show this loss is sandwiched between the predictability loss and the inverse variational inequality loss, making it a tractable surrogate for equilibrium prediction. Third, we develop a mirror descent algorithm to minimize it and demonstrate on a heterogeneous networked Cournot competition that our approach remains accurate under noisy observations and inconsistent equilibrium data while inverse variational inequality methods produce degenerate estimates.

Closest papers

Nearest neighbours by meaning across the whole index.

Learning in Inverse Games: Tractable Training with Probabilistic Guarantees

eess.SY math.OC ·2026-10-02 ·Arghya Mallick, Reza Rahimi Baghbadorani, Peyman Mohajerin Esfahani, Sergio Grammatico
similarity 0.70
Abstract

Inverse game theory seeks to learn agents' unknown objectives from observed equilibrium behavior. Existing residual-based approaches can lead to non-convex problems and need not ensure strong monotonicity of the learned game, limiting reliable equilibrium prediction. We develop a tractable convex framework for learning static and dynamic non-cooperative games using first-order and Nikaido-Isoda (NI) loss. Specialized operator parameterizations, including a Helmholtz--Hodge decomposition in a reproducing kernel Hilbert space (RKHS), enforce strong monotonicity for quadratic, nonparametric, non-quadratic, and linear-quadratic dynamic games. We establish finite-sample out-of-sample prediction guarantees, using Rademacher complexity to match existing bounds for the non-quadratic setting. For noisy sequential data, we develop a robust receding-horizon learning scheme whose adaptive regularization admits a maximum a posteriori (MAP) interpretation and is computed using randomized trace estimation. Numerical experiments, including a stylized autonomous-vehicle collision-avoidance application, demonstrate predictive accuracy and robustness to measurement noise.

0.43

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

Outperformance Inverse Optimization: Learning Objective Functions that Outperform Agent Decisions

cs.AI math.OCmath.STstat.ML ·2026-10-07 ·Akira Kitaoka
theory similarity 0.66
Abstract · 81 pages

Inverse optimization estimates the weights of an objective function that explain observed decisions as optimal solutions, and is used in a variety of fields. For mixed-integer linear programs (MILPs), existing methods aim to reproduce the observations as optimal solutions, and thus learn compromise weights when the observations are suboptimal. We propose outperformance inverse optimization, which instead seeks weights that induce, at each state, an optimal solution outperforming the observed action in every component. We give a loss function that can be evaluated with forward-problem oracles alone and is thus applicable to MILPs, together with gradient-based and DC optimization algorithms for minimizing it. For weights inducing a unique outperforming optimal solution at all observations, we prove that the probability of failing to induce such a solution at a new state (the generalization error) is bounded by a quantity inversely proportional to the number of observations, and that this bound is tight in the number of observations up to logarithmic factors. In experiments on synthetic and real data, the proposed methods improve the prediction of solutions outperforming the actions over existing methods.

0.18

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

cs.GT cs.LGmath.OC ·2026-08-10 ·Panayotis Mertikopoulos
publishedtheory similarity 0.63
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

Learning monotone game-theoretic linear MPC

eess.SY math.OC ·2026-11-12 ·Alberto Bemporad, Tatiana Tatarenko
similarity 0.61
Abstract · 15 pages, 1 figure

We propose a method to learn a game-theoretic model predictive control (GT-MPC) law by imitation from input and output data of a running multi-agent system. By interpreting the recorded inputs as the first moves of the equilibria of a game played by the agents, we learn the GT-MPC weights under hard input constraints and soft output constraints, without requiring the agents to reveal their objectives. We also impose that the resulting generalized Nash equilibrium (GNE) problem is strongly monotone, which ensures the existence and uniqueness of the equilibrium and, hence, that the learned GT-MPC law is well defined and can be evaluated efficiently online by variational GNE-seeking algorithms for linear-quadratic games. Moreover, strong monotonicity implies that the equilibrium is almost everywhere differentiable with respect to the references and the weights, which enables automatic differentiation for gradient-based optimization. In addition, we promote closed-loop stability of the unconstrained equilibrium feedback by incorporating a penalty that involves a jointly learned quadratic Lyapunov function. Learning a GT-MPC formulation enables us to explain the agents' objectives, reproduce their behavior in simulation in new scenarios, optimize their set-points, design mechanisms, and enforce additional constraints. A numerical example illustrates the approach.

0.27

Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation

cs.LG cs.AI ·2026-09-25 ·Debamita Ghosh, George K. Atia, Yue Wang
similarity 0.61
Abstract · 62 pages, 3 figures

Model misspecification poses a fundamental challenge in multi-agent reinforcement learning, where transition uncertainty can be amplified by strategic interactions among agents. Distributionally robust Markov games (DRMGs) provide a principled framework for addressing such uncertainty, yet existing methods often rely on restrictive assumptions or scale poorly to large state and joint action spaces. We study online learning in general-sum DRMGs with general function approximation and $φ$-divergence uncertainty sets. We propose RoMEX-$φ$, a model-free framework that integrates equilibrium-based exploration with dual fitted learning. Through a functional dual representation of the robust multi-agent Bellman operator, RoMEX-$φ$ enables tractable worst-case value estimation from nominal interaction data using a centered empirical robust discrepancy. We introduce the robust Multi-Agent Decoupling Coefficient (robust MADC) to characterize the intrinsic exploration complexity arising from strategic interactions and adversarial transition uncertainty. We establish sublinear robust regret guarantees governed by the robust MADC rather than explicitly by the state and joint action space sizes, replacing tabular dependence with intrinsic function-class complexity. Numerical experiments on a scalable general-sum DRMG under total variation uncertainty show that RoMEX-$φ$ is substantially more resilient to transition shifts than its non-robust counterpart while remaining competitive with an exact tabular robust baseline. Our results provide a scalable framework for distributionally robust multi-agent reinforcement learning with general function approximation.

0.28

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

cs.GT eess.SYmath.OC ·2026-11-12 ·Hao Liang, Solaleh Mohammadi, Kaiqing Zhang
similarity 0.61
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.

0.13

Inverse Learning of the Altruism and Cost Level in Mixed-Individual Mean Field Games

cs.LG math.OC ·2026-09-11 ·Haoyang Cao, Gökçe Dayanıklı, Xiaofei Shi
publishedbenchmark similarity 0.61
Abstract · To appear in the 65th IEEE Conference on Decision and Control

Understanding how humans respond to incentives, both at the individual and collective levels, is crucial to the design of effective policies. Within the continuous-time stochastic framework for large interacting populations, mean field games (MFGs) model populations of non-cooperative agents, whereas mean field control (MFC) describes the fully cooperative benchmark, interpreted in our setting as fully altruistic behavior. Mixed-individual MFGs interpolate between these two extremes through a parameter governing the degree of altruism. A central challenge for regulators and policymakers, however, is that intrinsic altruism levels and other private structural parameters, such as individual labor costs, are typically unobservable. To address this challenge, we develop an inverse learning framework for mixed-individual MFGs. Our approach enables the recovery of (latent) altruism and labor cost levels from noisy observations, with experiments demonstrating the feasibility and accuracy of our method. These findings underscore the promise of inverse MFG methodologies for uncovering latent preference structures in large populations, with important implications for incentive design, empirical behavioral modeling, and data-driven policy analysis.

0.39