Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularization

AI summary

Authors: Junyi Liao (Duke ECE), Zihan Zhu (UPenn Statistics and Data Science), Ethan X. Fang (Duke Biostatistics and Bioinformatics), Zhuoran Yang (Yale Statistics and Data Science), Vahid Tarokh (Duke ECE) arXiv: 2601.12707v2 [cs.LG]

Overview

Research area: Machine learning / game theory — specifically inverse reinforcement learning and inverse game theory, with entropy regularization and quantal response equilibrium (QRE) as the modeling backbone.

Technical level: Advanced. The paper is primarily a theoretical treatment built on linear systems, rank conditions, confidence-set construction, Hausdorff distance, and finite-sample concentration bounds.

Scope: The paper develops a unified framework for recovering the reward (payoff) functions that drive agents in two-player zero-sum matrix games and Markov games, given only observations of the players' strategies and actions.

Note on completeness: the provided paper content is truncated mid-sentence in Section 2.3 ("Parameter Selection."). Sections 3 (Markov games), 4 (numerical experiments), and 5 (conclusion/future work) are described in the paper's outline but their details are not present in the supplied content, so this summary reports only what the content contains.

What This Paper Is About

Standard reinforcement learning takes a reward function as given and solves for the best policy; this paper does the reverse, asking what reward function must have been in place to produce the strategies we actually observe in a competitive game. The authors study this "inverse game" problem for two-player zero-sum matrix games and entropy-regularized Markov games, where players' behavior is modeled as a quantal response equilibrium (QRE) rather than a perfectly rational Nash equilibrium. The goal is to reconstruct the underlying payoffs — and, when a unique payoff cannot be pinned down, to characterize the entire set of payoffs consistent with the observed data.

Key Contributions

1. Identifiability of reward functions. Using the QRE under a linear parametric assumption, the authors derive the conditions under which a reward function's parameters are identifiable, and characterize the feasible parameter set when they are not uniquely identifiable.

2. Algorithm for reward estimation. Building on the identifiability results, they propose an algorithm that estimates reward functions by constructing confidence sets intended to capture all feasible reward parameters (Algorithm 1).

3. Extension to Markov games. The framework is extended to entropy-regularized zero-sum Markov games, combining reward recovery with transition kernel estimation, and is designed to be sample-efficient and adaptable to methods such as Maximum Likelihood Estimation (MLE).

4. Theoretical and empirical validation. The paper provides theoretical guarantees on reliability and efficiency of the algorithm, and reports extensive numerical experiments across competitive scenarios.

Main Findings

• A rank condition exactly characterizes when payoffs are recoverable. Under the linear payoff assumption (Assumption 2.1: Q(a,b) = ⟨φ(a,b), θ*⟩ with ‖θ*‖² ≤ M), the authors prove that a unique θ exists if and only if rank([A(ν*); B(μ*)]) = d (Proposition 2.2). Intuitively, the observed equilibrium play must provide sufficiently diverse information about the game.

• Parameter estimation error scales with QRE estimation error. If the estimated equilibrium strategies satisfy TV(μ̂, μ*) ≤ ε₁/2 and TV(ν̂, ν*) ≤ ε₂/2, then ‖θ̂ − θ*‖² ≲ ε₁²·(1 + m·(ε₂²+1)) + ε₂²·(1 + n·(ε₁²+1)) (Theorem 2.3). The presence of m and n shows that larger action spaces amplify the error.

• Finite-sample payoff recovery rate. With N samples from the true QRE and a frequency estimator for the QRE, the payoff matrix error satisfies ‖Q̂ − Q‖²_F ≲ O((m² + n² + (m+n)log(1/δ))/N) with probability at least 1 − δ (Theorem 2.4) — a 1/N rate consistent with standard empirical process results.

• The confidence set contains the full feasible set. When the rank condition fails, the feasible set Θ is infinite and unbounded. Lemma 2.6 shows that with an appropriately chosen threshold κ (given explicitly in the paper), the constructed confidence set satisfies Θ ⊆ Θ̂, and d_H(Θ, Θ̂) ≲ √κ.

• Consistency of the confidence set. With κ_N = O(N⁻¹), the Hausdorff distance between Θ and Θ̂_N converges to zero in probability, and with probability at least 1 − δ, d_H(Θ, Θ̂_N) ≲ √((m² + n² + (m+n)log(1/δ))/N) (Theorem 2.7). This rate depends on m and n, again showing larger action spaces need more samples.

• Payoff functions converge too. Remark 2.8 notes that convergence of the parameter confidence set implies convergence of the associated payoff function Q_θ, since the feature map φ is bounded.

• Partial identifiability is a realistic regime, not an edge case. Increasing the parameter dimension d raises representational power but also raises the risk of violating the rank condition, since the data may not supply enough independent constraints.

• Frequency estimation may become inefficient in large action spaces, which the authors say motivates maximum likelihood estimators for parametric models (they point to results in Section 3.4, whose content is not in the provided excerpt).

Methodology in Plain English

The authors set up a two-player zero-sum game with finite action sets A = {1,...,m} and B = {1,...,n} and a payoff matrix Q, then add entropy regularization: each player's objective includes a Shannon entropy term weighted by a parameter η. The solution concept is the quantal response equilibrium, which yields fixed-point equations linking the players' mixed strategies to the payoffs — a way of modeling behavior that is "mostly rational" but not perfectly so.

The key modeling move is to assume the payoff matrix is linear in a known feature map: Q(a,b) = ⟨φ(a,b), θ*⟩ for an unknown vector θ*. Under this assumption, the nonlinear QRE fixed-point equations become an ordinary linear system with m + n − 2 equations in θ (Equation 2.3). Whether that system has a unique solution is decided by the rank of a stacked matrix built from the true equilibrium strategies — this gives the paper's sufficiency-and-necessity result.

The estimation procedure is two steps: (1) estimate the QRE (μ*, ν*) from observed action pairs using a simple frequency estimator; (2) plug those estimates into the linear system and solve by least squares, which has a closed form. When the rank condition holds, this yields a point estimate θ̂; when it fails, the authors instead build a confidence set — a set of θ values that nearly satisfy the estimated linear constraints and whose norm is bounded by M — and map every θ in that set to a candidate payoff matrix. The threshold κ controlling the set's size is chosen explicitly to account for QRE estimation error so that valid payoffs are never excluded.

Why This Matters

Impact on research. The paper adds identifiability theory to a literature that has mostly focused on learning equilibria rather than recovering payoffs. Its distinguishing feature is replacing regret-based rationality constraints (as in prior inverse equilibrium work) with entropy-regularized QRE, and extending the entropy-regularization-as-identification-device idea — previously used in single-agent IRL — to competitive multi-agent settings. It also delivers guarantees rather than only heuristics: an exact identifiability condition, confidence sets that provably contain the feasible set, and finite-sample rates.

Real-world applications (as described in the paper):

• Economics and marketing: observing how competing pricing algorithms respond to rivals over time to infer underlying incentives (profit priorities, market positioning, risk aversion), then simulating alternative market scenarios or auditing pricing behavior.
• Cybersecurity: inferring a defender's objectives directly from observed attacker–defender interactions — as in sequential models where the defender must infer an attacker's hidden strategy from noisy security alerts — instead of assuming those objectives are known.
• Operations research / logistics: recovering the incentives behind competing carriers' routing decisions on shared freight networks, where one player minimizes transportation costs and another maximizes profit from traffic on controlled routes, to inform policy design and evaluation.
• Robotics and autonomous systems: designing better AI systems for competitive tasks by understanding the reward structures behind adversarial behavior.

Industry relevance. Any setting where a firm can log the actions of a competitor or adversary but not their objectives — algorithmic pricing, security operations, logistics platforms, competitive AI agents — is a candidate application. The confidence-set formulation is especially relevant operationally: it tells a practitioner which reward parameters are ruled out by the data and which remain plausible, rather than reporting a single number that may be arbitrary under rank deficiency.

Future Directions

• Extending beyond the zero-sum case. The paper's formal treatment is for two-player zero-sum games; general-sum or multiplayer competitive settings would require a different identification framework.

• Relaxing the linear payoff assumption. Identifiability here rests on Assumption 2.1 (Q(a,b) = ⟨φ(a,b), θ*⟩); richer, nonlinear parameterizations of the payoff would need new identifiability and estimation theory.

• Better estimators for large action spaces. The authors explicitly note that their finite-sample bound grows like m² + n² and that the frequency estimator may become inefficient, suggesting MLE for parametric models as an alternative — though the details of that result are not in the provided content.

• Handling insufficient exploration / partial identifiability in practice. The paper raises but does not settle the design question of how to choose among infinitely many feasible parameters when the rank condition fails; the truncated "Parameter Selection" discussion appears to address this, and Section 5 is said to discuss future research directions, but neither is included in the supplied content.

Target Audience

This paper is aimed at researchers and graduate students in machine learning theory, reinforcement learning, and game theory who work on inverse reinforcement learning, inverse optimization, or equilibrium learning. It will also be useful to mathematically trained practitioners in industrial and computational economics, security modeling, and algorithmic-marketplace analysis who want formal identifiability guarantees before trusting recovered reward functions. A reader needs comfort with linear algebra, minimax formulations, entropy regularization, and statistical learning theory to follow the results; the problem motivation and application sections are accessible to a broader audience.

Authors’ abstract

Estimating the unknown reward functions driving agents' behaviors is of central interest in inverse reinforcement learning and game theory. To tackle this problem, we develop a unified framework for reward function recovery in two-player zero-sum matrix games and Markov games with entropy regularization, where we aim to reconstruct the underlying reward functions given observed players' strategies and actions. This task is challenging due to the inherent ambiguity of inverse problems, the non-uniqueness of feasible rewards, and limited observational data coverage. To address these challenges, we establish the reward function's identifiability using the quantal response equilibrium (QRE) under linear assumptions. Building upon this theoretical foundation, we propose a novel algorithm to learn reward functions from observed actions. Our algorithm works in both static and dynamic settings and is adaptable to incorporate different methods, such as Maximum Likelihood Estimation (MLE). We provide strong theoretical guarantees for the reliability and sample efficiency of our algorithm. Further, we conduct extensive numerical studies to demonstrate the practical effectiveness of the proposed framework, offering new insights into decision-making in competitive environments.