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

Dear Reviewer,

Thank you for your valuable feedback and for carefully checking the proofs of our theorems.

Concerns about the Asymptotic Notation

We appreciate your observation regarding the use of asymptotic notation in Theorems 2.3, 2.4, and 2.5. To streamline presentation, we omitted terms that implicitly depend on the problem size—specifically, action space sizes $m,n$, feature dimension $d$, and the regularization parameter $\eta$. We agree that these quantities affect the sample complexity and convergence rates and are not truly constant. In the revised version, we will explicitly include these dependencies in the theorem statements and discuss their implications.

Questions

(Q1) Contribution to the Broader Litterature

The idea of inverse reinforcement learning under entropy regularization is well known and dates back to Ziebart et al.

Ziebart et al., 2008 focuses on imitation learning in single-agent Markov Decision Processes. In comparison, our work addresses IRL in two-player zero-sum Markov games, where the objective is to recover the reward functions given observed equilibrium strategies (QRE). Additionally, we deal with both strong and partial identifiability, which introduces new theoretical challenges not covered in Ziebart et al.

More recent works about inverse game theory under entropy regularization include, for example, Wu et al and Chen et al. 

These studies focus on inverse game theory for Stackelberg games and quantal Stackelberg equilibrium (QSE). These methods primarily deal with leader-follower interactions, where one player commits to a strategy first, and the follower responds optimally. The difference between QRE and QSE is crucial:

• QRE models simultaneous decision-making under entropy regularization, where both players make noisy best responses.
• QSE models sequential decision-making, where the leader’s strategy is announced, and the follower best responds.

Our theoretical framework leverages QRE constraint, which fundamentally differs from the QSE setting explored by Wu et al. and Chen et al.

The idea of using MLE to estimate the unknown reward functions for such problems is also standard. 

We are sorry about causing the confusion. To clarify, we do not directly apply MLE for reward estimation. Instead, the key to our identification method is using the linear assumption to transform the QRE constraints into linear systems like (2), (11). We then employ least square to construct confidence sets. MLE is only used to estimate QRE from data (e.g., Appendix E), not to estimate rewards directly.

To summarize, our contribution includes:

• We introduce a complete framework that addresses reward identification and estimation in two-player zero-sum games and Markov games. To the best of our knowledge, no existing work addresses these specific problems.
• We establish necessary and sufficient conditions for strong and partial identification under linear parameterization.
• We provide theoretical guarantees for the sample complexity and convergence of the constructed confidence sets.
• Through experiments, we verify the behavioral consistency between the recovered reward functions and the observed QRE.

(Q2) Zero-Sum Game Restriction

Our framework is currently specific to zero-sum games because of their minimax structure, which enables QRE to yield tractable linear constraints on the reward parameter. General-sum games lack this structure and may admit multiple equilibria, complicating both identification and estimation.

Though extending our methods to general-sum settings is nontrivial, we view this as an exciting direction for future work and appreciate your suggestion to explore this aspect.

(Q3) Assumption of Known Regularization Parameter $\eta$

We acknowledge that our method assumes a known entropy regularization parameter $\eta$, which reflects our modeling of agents . In practice, agents may use different or unknown $\eta$'s. We address this in two parts:

• If players use different $\eta_1$ and $\eta_2$, our linear formulation and results still hold by adjusting the vectors $c(\mu)$ and $d(\nu)$ accordingly.
• If $\eta$ is unknown, one could treat it as a hyperparameter and select it via cross-validation. In estimation, the choice of $\eta$ is not a problem since we can scale the reward functions, so the identifiability and consistency of strategies remain unaffected.

We will discuss this in the revised version as an important direction for future research.

(Q4) Derivation in the Proof of Theorem 2.3

Thank you for pointing out this issue. We apologize for the confusion caused by the notation. There was a minor typo in the proof where the inequality sign $\leq$ should have been $\lesssim$, which absorbs a constant factor of $2$. The estimate is a consequence of Cauchy-Schwartz inequality. We appreciate your careful attention to detail, and we will correct this in the final version of the paper.

Dear Reviewer,

Thank you for thoroughly evaluating our work and for your valuable comments. We hope our reply will address your concerns and questions.

(Q1) Substantive Implications of the Non-singularity Assumption

The non-singularity assumption on the feature covariance matrix $\Psi_h$ ensures that the feature vectors are linearly independent, meaning that no feature can be expressed as a linear combination of others, so we have sufficient information for parameter recovery. This is a standard assumption of coverage in many related literatures [1, Corollary 4.2; 2, Assumption 2.3]. One practical way for users to check this assumption is to examine the condition number of the matrix $\Psi_h$. If the condition number is extremely large, it indicates that the matrix is nearly singular. Additionally, principal component analysis (PCA) can help detect high collinearity among features.

If the assumption does not hold, the problem becomes ill-posed, meaning that there exist multiple solutions for the estimated reward function. In such cases, our method may produce arbitrarily large or unstable estimates, as the problem becomes underdetermined. Nevertheless, in parctice,we can take proactive measures to avoid rank deficiency:

• Reducing feature dimension to avoid over-parameterization.
• Removing redundant features to ensure numerical stability and identifiability.

(Q2) Parameter Choice

We chose $m=n=5$, $H=6$ to strike a balance between model complexity and computational feasibility. The setup provides sufficient structure to validate both static and dynamic cases. We will add this explanation in the revised version.

(Q3) Number of Replications and Confidence Bounds

In the revised version, we repeat experiments 100 times and report 95% confidence intervals. Below we list the results on the QRE error:

In Figure 1, we compare reconstructed and assigned rewards. Since the true reward is not uniquely identifiable, different reward functions may induce the same QRE. Thus, even with large $N$, we may observe limited improvement in raw reward error. Our true goal is behavioral consistency, which we assess in Figure 2 via the QRE induced by the recovered reward. This metric better reflects algorithm performance and convergence.

(Q4) Quantitative Differences and Theoretical Validation:

Thank you for raising this important point. We acknowledge that the empirical results presented in the main text may not fully demonstrate consistency with the theoretical convergence rates.

In fact, we did compare the empirical convergence rate with the theoretical result in the matrix game setting and verified their consistency (both $\mathcal{O}(N^{-1/2})$). This comparison and analysis are detailed in Appendix E. While we had limited Markov game replication before submission, we have since conducted 100-run experiments and observed consistent convergence rates. These additional results with confidence intervals will be added to the revision to strengthen empirical validation. We will update the revised version of the paper to include these new experimental results and confidence intervals, and explicitly discuss the consistency between empirical and theoretical results.

Thank you once again for pointing out this important aspect. We believe that this additional empirical evidence will significantly strengthen the experimental validation of our theoretical findings.

About Undiscussed Essential References

Thank you for pointing out the recent work. While Chui et al. (2023) also explore preference estimation in games, their focus is fundamentally different from ours. They investigate non-strategic or imperfectly rational players, proposing models that better fit human behavior by relaxing equilibrium assumptions like Nash equilibrium and QRE. In contrast, our work assumes strategic agents playing QRE and studies the identification and estimation of reward functions under this equilibrium assumption. Moreover, Chui et al. do not address the identifiability or sample complexity of their estimation procedure, while a key contribution of our work lies in formally characterizing when the reward function is identifiable and how to estimate it reliably from finite data. Finally, their analysis is limited to static games, whereas our framework extends to finite-horizon Markov games.

We will include a discussion of this work in the Related Work section.

References

[1] Tu, S. and Recht, B. (2017). Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator.

[2] Min, Y., Wang, T., Zhou, D. and Gu, Q. (2022). Variance-aware off-policy evaluation with linear function approximation.

Dear Reviewer,

Thank you for your thoughtful and constructive feedback! We greatly appreciate your positive assessment of the theoretical soundness and methodological consistency of our work. Below, we address your specific concerns and suggestions.

Relation to Single-Agent IRL Identification

We appreciate the suggestion to connect our results with identifiability in single-agent IRL. In particular, works such as Cao et al. [1], Rolland et al. [2], and Schlaginhaufen & Kamgarpour [3] explore how observing behavior under varying transition dynamics or discount factors can lead to identifiability, typically through rank or subspace conditions. These insights align with our own setting, where we identify necessary and sufficient rank conditions on linear systems derived from QRE constraints in zero-sum Markov games.

Unlike the single-agent case, we address multi-agent, strategic interactions where agents follow a quantal response equilibrium. Nevertheless, the underlying intuition is similar: entropy regularization and structured assumptions (e.g., linear parameterization) enable us to derive strong identifiability and sample-efficient estimation. We will incorporate this discussion in the Related Work section to better position our contributions.

Experimental Design

We have now conducted additional experiments in the Markov game setting with 100 replications per sample size and computed 95% confidence intervals. These results align closely with our theoretical rates. Below are some results on the QRE error $\mathrm{TV}(\widehat{\mu},\mu)+\mathrm{TV}(\widehat{\nu},\nu)$:

(Q1) Theoretical Insights on When the Rank Condition (12) Is Satisfied

The rank condition (12) ensures the linear system (11) has a unique solution, which is the strongly identifiable case. Here the matrices $A_h(s,\nu_h^*)$ and $B_h(s,\mu_h^*)$ are derived from differences between feature vectors weighted by the corresponding equilibrium strategies, which means that distinct action pairs should lead to linearly independent differences. The rank condition also implicitly requires that the QRE policies $(\mu_h^*,\nu_h^*)$ do not degenerate and effectively captures the difference between different action pairs.

In the tabular case, where $\phi$ is the canonical map and $d=Smn$, this condition does not hold in general, since the system (11) has only $S(m+n-2)$ equations. Nevertheless, our theory for the partially identifiable case ensures that we can still learn an acceptable estimate for the reward function even when the rank condition is not satisfied.

In practice, we recommend using low-dimensional, non-redundant feature maps and applying tools like PCA to remove collinearity, which helps maintain full rank and improves sample efficiency.

(Q2) QREs Corresponding to the Recovered Reward

Theoretically, our algorithm aims to recover a confidence set of feasible reward functions rather than a single one, due to the partial identifiability inherent in inverse game learning. In practice, our focus is on behavioral consistency rather than exact reward matching.

In the entropy-regularized setting, small variations in rewards result in proportionally small variations in QRE, according to the Lipschitzness of softmax. Consequently, when the error between the recovered reward and the true reward is small, the QRE induced by the recovered reward function is guaranteed to be close to the true QRE.

Our experimental results consistently show that even when the recovered reward function differs from the assigned one (due to partial identifiability), the QRE derived from the recovered reward still closely matches the observed QRE. This indicates that the estimated reward is close to another feasible reward.

Other Strengths And Weaknesses

Thank you for your positive feedback on the theoretical results and for suggesting ways to build more intuition. Below, we address the specific point you raised.

The distance measure quantifies the Hausdorff distance between the estimated feasible set $\widehat{\mathcal{R}}$ and the true feasible set $\mathcal{R}$. In practice, when it is sufficiently small, we know that

• The estimated reward set $\widehat{\mathcal{R}}$ almost captures all feasible rewards $r\in\mathcal{R}$;
• For any estimated reward $\widehat{r}$, there exists a feasible reward $r$ close to it, so the confidence set $\widehat{\mathcal{R}}$ is not too conservative.

If the rank condition (12) holds, our confidence set $\widehat{\mathcal{R}}$ converges to a single point, which is the uniquely feasible reward $r$. Indeed, even if the rank condition does not hold, our algorithm still efficiently recovers all feasible reward functions.

Dear Reviewer,

Thank you for your valuable feedback and for recognizing the relevance and significance of our contributions. Below, we address your concerns regarding the necessity of the rank condition (Proposition 2.2), comparisons with related works, and competing methods in experiments.

Necessity of the Rank Condition (Proposition 2.2)

We apologize for our unclear statement in Proposition. The submitted version of the paper may not clarify the necessary conditions and their assumptions. In fact, the reward parameter is uniquely solvable if and only if the rank condition holds, and the logic is derived in previous contents.

• $(\mu^*,\nu^*)$ is the quantal response equilibrium (QRE) corresponding to $Q$ if and only if the following QRE constraint is satisfied:

$$\mu^*(a)= \frac{e^{\eta Q(a,\cdot)\nu^*}}{\sum_{a\in\mathcal{A}}e^{\eta Q(a,\cdot)\nu^*}}\ \text{for all}\ a\in\mathcal{A},\quad \nu^*(b)= \frac{e^{-\eta Q(\cdot,b)^\top\mu^*}}{\sum_{b\in\mathcal{B}}e^{-\eta Q(\cdot,b)^\top\mu^*}}\ \text{for all}\ b\in\mathcal{B}.$$

• Under the linear assumption, the above non-linear system is equivalent to the linear system (2).
• According to our model assumption, this linear system has at least one solution $\theta=\theta^*$. The solution is unique if and only if the rank condition (3) is satisfied.

We will correct our statement in a later version. We hope this clarification solves your confusion.

Comparisons with Prior Works

We understand your concern regarding related works that do not impose a linear condition. The works [1,2,3] you listed explore nonlinear settings and adopt different model assumptions. In particular:

[1] (Reward Identification in Inverse Reinforcement Learning) studies the problem of reward identifiability in IRL from a graph perspective, focusing on single-agent MDPs. It primarily addresses identifiability conditions without discussing the problem of reward estimation in identifiable cases.

[2] (Reward-Consistent Dynamics Models for Offline Reinforcement Learning) focuses on model-based offline RL, where the goal is to learn a dynamics model that generalizes well to unseen transitions. It is applied to single-agent settings, and the problem of reward identification is not addressed.

[3] (Deep PQR: Solving Inverse Reinforcement Learning using Anchor Actions) works on inverse reinforcement learning (IRL) with deep energy-based policies. The key innovation is the introduction of an anchor action, which is a known, zero-reward action (e.g., doing nothing), to facilitate reward identification. Compared with our linear assumption, this method is based on an Anchor-Action Assumption (See Assumption 1), which helps to uniquely determine the reward function.

These works differ significantly from our approach and share limited similarities with our problem setting. In our work, the linearity assumption is crucial to transform the non-linear QRE constraint into a tractable linear problem. This enables us to derive rigorous theoretical guarantees on both identification and estimation of reward functions. Moreover, we provide a thorough theoretical analysis including convergence guarantees and confidence set construction, which is not covered in above works. We will include a more detailed discussion of these related works in the final version. Thank you for pointing out these references and helping us improve the clarity of our presentation.

Lack of Competing Methods

We would like to clarify that our paper introduces a totally novel framework for inverse game theory, covering both identification and estimation of reward functions in competitive game settings. To the best of our knowledge, there are no existing methods specifically designed for inverse reinforcement learning (IRL) in two-player zero-sum Markov games that are directly comparable to our approach. Most prior works in IRL focus on single-agent settings or non-competitive scenarios. Furthermore, the entropy-regularized QRE setting that we address is particularly unique, as it requires handling the complexity of equilibrium strategies and partial identifiability.

While there are some works that address inverse RL with deep policies or anchor actions (e.g., [3]) or model-based RL for offline settings (e.g., [2]), these methods do not address the competitive, game-theoretic setting we focus on. Our approach leverages linear parametrization and QRE modeling, which makes it fundamentally different from existing IRL techniques that do not incorporate game-theoretic interactions or entropy regularization.

We would greatly appreciate it if the reviewer could suggest any closely related methods that might have been overlooked or not covered in our paper. We are committed to enhancing our work by incorporating relevant comparisons, if available, and we value your input in guiding us toward potential improvements.