PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning in Inverse Games: Tractable Training with Probabilistic Guarantees

Arghya Mallick, Reza Rahimi Baghbadorani, Peyman Mohajerin Esfahani, Sergio Grammatico

arXiv:2610.03481v1eess.SYcs.SYmath.OC

TL;DR

Inverse game theory seeks agents’ unknown objectives from observed equilibrium behavior, but existing approaches can be non-convex and do not ensure monotonicity. This paper develops convex, monotonicity-enforcing formulations for several game classes and reports finite-sample guarantees for equilibrium prediction.

  • Problem

    Learning agents’ objectives from equilibrium observations remains challenging because existing residual-based inverse-game approaches can be non-convex and do not ensure monotonicity of the learned game.

    Source: §1 · p. 1

  • Method

    The paper formulates inverse games with first-order and Nikaido–Isoda losses and uses structured operator parameterizations to enforce strong monotonicity.

    Source: §1 · p. 2, §4 · p. 9, §4.1 · p. 11

  • Results

    Strong monotonicity supports accurate equilibrium prediction across quadratic, non-quadratic, and linear-quadratic dynamic games, with finite-sample guarantees.

    Source: §7 · p. 20

  • Takeaways & Limitations

    The learned games retain strong monotonicity, a property the paper identifies as important for compatibility with Nash equilibrium-seeking algorithms.

    Source: §4 · p. 9

    The offline guarantees remain to be extended beyond i.i.d. data to dynamically correlated trajectories.

    Source: §7 · p. 21

Abstract

from arXiv · show

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.

1. Introduction

Inverse game theory asks whether agents’ objectives can be learned from observed equilibrium behavior, enabling an operator to anticipate equilibrium profiles. This paper develops convex formulations and finite-sample prediction guarantees for several classes of games, including noisy dynamic games.

1. Introduction

  • Existing inverse-game methods can be non-convex and do not inherently ensure monotonicity of the learned game, while one approach is limited to unconstrained two-player dynamic games.Monotonicity is identified as important for convergence of standard Nash equilibrium-seeking algorithms.Source: §1 · p. 2
  • For linear-quadratic games, the paper introduces a Nikaido–Isoda loss with an exact convex reformulation using LMI constraints.The reformulation is stated in Proposition 3.4.Source: §1 · p. 2
  • For non-quadratic monotone games, the paper parameterizes the game operator in an RKHS using Helmholtz–Hodge decomposition, yielding a finite-dimensional convex program with second-order cone constraints.The reduction is stated in Theorem 4.3.Source: §1 · p. 3
  • For noisy linear-quadratic dynamic games, LMIs enforce strong monotonicity and a receding-horizon Tikhonov update mitigates sequential noise propagation.With an appropriate dynamic penalty update, the solution coincides with the Bayesian MAP estimate of the noise-free parameter.Source: §1 · p. 3
  • The paper establishes finite-sample out-of-sample prediction guarantees for inverse quadratic and non-quadratic monotone games, with the latter matching a best-known inverse-variational-inequality bound.The matching bound uses strong monotonicity and Rademacher complexity.Source: §1 · p. 3

Notation

  • The notation section defines matrix norms, inner product and trace, column stacking and block diagonalization, probability and expectation, and the variational inequality problem.It also specifies that R and R^n denote the reals and n-dimensional Euclidean space.Source: Notation · p. 3

2. Problem Description

The problem setting treats observed actions as Nash equilibria of signal-dependent games and learns a forward game from signal–equilibrium pairs. The goal is accurate equilibrium prediction for new signals, not exact identification of agents’ objective parameters.

2. Problem Description

  • Each agent chooses a decision vector from a signal-dependent feasible set and minimizes a cost that may depend on the other agents’ decisions.The collective feasible set is the product of the agents’ local feasible sets.Source: §2 · p. 3
  • For each observed signal, the realized joint strategy is assumed to be a Nash equilibrium in which no agent can improve unilaterally within its feasible set.The dataset consists of signal and Nash-equilibrium pairs collected over T forward games.Source: §2 · pp. 3–4
  • The learning objective is to predict the true Nash equilibrium for a new signal, rather than recover the exact parameters of the agents’ objective functions.The approach is supervised learning over a restricted, finitely parameterized function space for the costs.Source: §2 · p. 4
  • The setup assumes i.i.d. training and testing signal–equilibrium samples and known, nonempty local feasible sets described by bounded linear inequalities.The data-generation assumptions include consistency between the loss and equilibrium solutions.Source: §2 · p. 4
  • The i.i.d. assumption supports predictive statistical guarantees, while known polytopic feasibility sets support tractable convex training formulations.Other convex feasibility sets could replace polytopes, though polytopes offer an easier dual reformulation.Source: §2 · p. 4

3. Inverse Formulation for Linear Quadratic Games

The section formulates inverse learning for linear-quadratic games using equilibrium-based losses and a convex semidefinite program, then gives probabilistic bounds on prediction error. Strong monotonicity links the training loss to equilibrium prediction, while the bounds account for inconsistency in the training data.

3. Inverse Formulation for Linear Quadratic Games

  • The quadratic-game formulation parameterizes unknown cost-function terms and constrains the pseudogradient Jacobian to be positive definite.This Jacobian condition is used to restrict the learned game to strongly monotone games.Source: §3 · p. 5

3.1. Loss functions

  • The NI loss is based on unilateral objective improvements and is nonnegative, reaching zero exactly at a Nash equilibrium.Minimizing it at observed signal-equilibrium pairs drives parameters toward equilibrium conditions.Source: §3.1 · pp. 5–6
  • For a monotone pseudogradient, the Nikaido-Isoda loss has a dominance property over the first-order loss.The framework favors NI loss on this basis.Source: §3.1 · p. 6

3.2. Tractable formulation

  • The empirical Nikaido-Isoda loss problem for the quadratic candidate is equivalent to a semidefinite program under Assumption 2.2.Its LMI count scales with the dataset size T and number of agents N.Source: §3.2 · p. 7
  • Modern interior-point solvers are described as efficient for the semidefinite programs, despite their LMI count growing with T and N.The formulation’s statistical analysis concerns prediction on an unseen testing dataset.Source: §3.2 · p. 7, §3.3 · p. 7

3.3. Probabilistic performance guarantees

  • Under strong monotonicity and Assumption 2.2, the section establishes a probabilistic prediction-error bound from the learned game’s approximate variational inequality.The argument connects chance-constraint and variational-inequality bounds to the distance from the true solution.Source: §3.3 · pp. 7–8
  • The training-loss tolerance can be zero for pure or consistent data, while other training-data inconsistencies accumulate in that tolerance.The probabilistic bound can remain tight even when the training loss is zero.Source: §3.3 · pp. 8–9

4. Inverse Formulation for Non-Quadratic Monotone Games

The section extends inverse-game learning to non-quadratic objectives by parameterizing a strongly monotone pseudogradient with a convex potential and a rotational component. It gives a finite-dimensional convex approximation and analyzes out-of-sample prediction error using Rademacher complexity.

4. Inverse Formulation for Non-Quadratic Monotone Games

  • The section motivates nonparametric function classes as a way to broaden expressivity while preserving tractability and strong monotonicity.The learned operator is structured to remain compatible with Nash equilibrium-seeking algorithms.Source: §4 · p. 9

4.1. Proposed formulation

  • The proposed pseudogradient combines the gradient of a strictly convex scalar potential with a feature-scaled skew-symmetric rotational component.The skew-symmetric component is divergence-free, allowing a richer operator structure while retaining the convex-potential component.Source: §4.1 · pp. 9–10
  • The decomposition separates the field into irrotational and rotational components, illustrated by the gradient and φ(s)Su terms in Figure 1.A two-player example shows these components contributing different terms to the same pseudogradient.Source: §4.1 · p. 9, Figure 1 · p. 10
  • The RKHS formulation yields an approximate, finite-dimensional convex reformulation under a squared-exponential kernel, rather than the exact reformulation used for the quadratic case.It learns pseudogradient operators rather than objective functions.Source: §4.1 · pp. 10–11

4.2. Probabilistic performance guarantees

  • For the non-quadratic RKHS setting, the analysis bounds mean out-of-sample prediction error using Rademacher complexity.Theorem 4.4 assumes a strongly monotone operator, a feasible set contained in a ball of radius V almost surely, and Assumption 2.2.Source: §4.2 · p. 11
  • For the squared-exponential kernel, Tr(K)=O(T), and the paper reports that its bound and the comparison bound in [8, Theorem 8] achieve the same overall rate.The comparison concerns the corresponding terms in the bounds.Source: §4.2 · p. 13

5. Inverse formulation for linear-Quadratic dynamic games

The paper extends its inverse-game formulation to finite-horizon open-loop linear-quadratic dynamic games, with a convex training formulation that enforces strong monotonicity. For noisy sequential observations, it adds a robust receding-horizon update and develops probabilistic guarantees and a local MAP interpretation.

5. Inverse formulation for linear-Quadratic dynamic games

  • The dynamic formulation targets finite-horizon open-loop Nash equilibria in linear-quadratic games, using observed signal and equilibrium pairs to learn a predictive forward game.The initial state is treated as a signal; the aim is equilibrium prediction rather than exact recovery of objective parameters.Source: §5 · p. 13, §5.1 · p. 13

5.1. Finite-horizon linear-quadratic dynamic game

  • Strong monotonicity is enforced through a matrix inequality, yielding an exact convex reformulation of the empirical inverse problem.For the dynamic operator, the Jacobian-based constraint simplifies to an LMI; Proposition 5.2 establishes equivalence to a convex program.Source: §5.1 · p. 14
  • Imposing the cited stability condition on open-loop equilibrium trajectories was conservative and did not improve solutions in the authors’ numerical experience.The initial state is treated as a signal in the formulation.Source: §5.1 · p. 15
  • The out-of-sample guarantee is distribution-free for i.i.d. episodic data, while guarantees for temporally correlated sliding windows remain open.The result relies on the stated assumptions, including strong monotonicity; continuous ego-centric trajectory windows violate the i.i.d. condition.Source: §5.1 · p. 15

5.2. Robust receding horizon learning

  • The online learner uses a fixed-length sliding window, discarding its oldest sample so the number of LMIs per update stays constant over time.This is intended to avoid unbounded error accumulation and growing computational complexity during sequential deployment.Source: §5.2 · p. 15
  • A robust Tikhonov update regularizes structural game parameters to reject noise while tracking parameter drift; auxiliary variables are re-optimized but not regularized across windows.The penalty is adaptive rather than a static, heuristically tuned hyperparameter.Source: §5.2 · pp. 15–16
  • In the small-noise regime, the regularized update is locally MAP-equivalent up to second-order terms, under a local quadratic approximation and isotropic covariance matching.This is not a global equivalence: active-set changes or optimizer non-differentiability can make the MAP interpretation heuristic.Source: §5.2 · p. 17
  • Randomized trace estimation avoids evaluating the full sensitivity matrix, with one additional solve using globally perturbed observations reducing the mapping’s complexity from O(dim(yt)) to O(1).A single Monte Carlo realization provides an unbiased estimate of the penalty variance.Source: §5.2 · pp. 17–18

6. Numerical Experiments

The experiments evaluate out-of-sample prediction for quadratic and non-quadratic monotone games, then test robust learning in a stylized collision-avoidance game. The results report prediction-error trends, a learned yielding maneuver, and performance under noise and varying horizons.

6. Numerical Experiments

  • The numerical section presents two game examples and a stylized application, solving forward VIs with aGRAAL and inverse SDPs with MOSEK in MATLAB.The quadratic and non-quadratic instances use two players with three decision variables each, and training datasets of 50 and 80 samples, respectively.Source: §6 · p. 18, §6.1 · p. 18

6.1. Quadratic and non-quadratic monotone games

  • For the quadratic game, NI and FO methods have comparable mean prediction error, with lower variance for NI; non-quadratic error decays sublinearly as training size grows.Figure 3 plots mean prediction error against training dataset size; the non-quadratic trend empirically validates the statistical bounds in Theorem 4.4.Source: §6.1 · pp. 18–19, Figure 3 · p. 19

6.2. Stylized application: collision avoidance game

  • On an unseen test episode, the robust prediction tracks the ground-truth Nash equilibrium, reproducing the yielding maneuver and asymmetric braking profiles.The trajectory comparison covers absolute position, velocity, and acceleration profiles.Source: Figure 4 · p. 20, §6.2 · p. 20
  • As measurement noise and horizon length vary, the MAP-Tikhonov estimator maintains lower median MAE and tighter variance bounds, while its MAE decreases with longer horizons.The unregularized estimator degrades with increasing noise and accumulates noise over longer horizons.Source: §6.2 · p. 20

7. Conclusion

The paper concludes that convex inverse-game formulations support equilibrium prediction across quadratic, non-quadratic, and linear-quadratic dynamic games, with finite-sample guarantees. It also identifies extensions needed beyond the current data, feasibility-set, and noise settings.

  • The paper's convex formulations support accurate equilibrium prediction across quadratic, non-quadratic, and linear-quadratic dynamic games, with finite-sample guarantees.Source: §7 · p. 20
  • The robust estimator outperforms the baseline in prediction MAE over 30 test episodes as measurement noise and receding horizon length vary.Source: Figure 5 · p. 21
  • Future work includes extending offline guarantees beyond i.i.d. data, jointly inferring objectives and unknown feasibility sets, and handling non-Gaussian, heavy-tailed, and adversarial disturbances.Source: §7 · p. 21

8. Appendix

The appendix supplies proof steps for the convexity and tractability claims, the RKHS guarantee, the complexity bound, and the MAP interpretation of the online update.

8.1. Proof of Lemma 3.3

  • Monotonicity implies convexity in each agent's action, allowing the Nikaido–Isoda loss to upper-bound the summed objective suboptimality.Source: §8.1 · p. 21

8.2. Proof of Proposition 3.4

  • The proof converts the Nikaido–Isoda inner minimization into an LMI using an epigraph variable and a Schur complement.Source: §8.2 · pp. 21–22

8.3. Proof of Theorem 4.3

  • Theorem 4.3's proof uses an RKHS representation and bounded derivative operators to address the strong-convexity constraint.Source: §8.3 · p. 22

8.4. Auxiliary Lemma

  • The auxiliary lemma bounds empirical Rademacher complexity for the function class, relating the classes through the Lipschitz continuity of the first-order loss.Source: §8.4 · pp. 22–23

8.5. Proof of Proposition 5.7

  • Under the stated approximation, update rule (39) makes the receding-horizon estimator coincide locally with the MAP solution, up to a second-order remainder.Source: §8.5 · p. 23
Loading 2610.03481v1…