Safe Exploitative Play with Untrusted Type Beliefs

Thank you so much for your feedback. We appreciate your recognition of the strengths in our paper.

Alternative Forms of Beliefs:

Regarding the issues addressed, we understand the need to discuss alternative approaches to decision-making based on trust in other forms of beliefs. Specifically, we recognize that many uncertainty quantification methods such as the Bayesian neural networks or Gaussian process regression etc. can be used to provide uncertainty bounds or estimates that provide more structured and informative beliefs for strategic players. Our initial exploration of this problem focused on a specific form of type beliefs that we found to be one of the most natural and fundamental setups. Considering these more realistic forms of beliefs (for example, with additional uncertainty quantification) is important and will be an interesting future direction. In the revised manuscript, we will include a discussion.

Here are our 1-1 responses to address each question raised in the comments:

Question 1. It’s hard to understand how tight the bounds and the estimates in the theorems 3.1 and 3.2 are. Some additional examples with explicit bound computations would be beneficial.

Thank you for the great suggestion. We provide additional plots of the opportunity-risk tradeoff in the evaluation of the 2 × 2 games using an algorithm that has varying trust of type beliefs in 100 and 1,000 runs. In each case, the algorithm is presented with a type prediction and takes a convex combination of the best response to the type prediction and the minimax strategy with the trust parameter λ, determining how much to weigh the best response. Fully trusting (λ = 1) and distrusting (λ = 0) type beliefs yield a best response strategy and a minimax strategy correspondingly. The agent then samples from their resulting mixed strategy an action to play while the opponent also samples from whatever mixed strategy they are using an action to play. We sample this interaction for the number of runs and gather empirical payoff information, which we use to plot the opportunity risk trade-off.

We include as plots the bounds on the opportunity risk tradeoff and show the tightness or looseness of these bounds in the two games we pick. In particular, in an Adjusted Matching Pennies game, we see that the upper bound is loose, and the empirical opportunity-risk tradeoff matches the lower bound we derive. This example illustrates the looseness in the upper bound we derive. In the canonical Matching Pennies game, we find that the lower and upper bounds are tight with the empirical tradeoff matching these theoretical bounds.

Below are payoff matrices for the zero-sum Matching Pennies and Adjusted Matching Pennies games, respectively:

$\begin{bmatrix} 1 & -1 \\\\ -1 & 1 \end{bmatrix}; \begin{bmatrix} 1.2 & -0.8 \\\\ -0.8 & 1.2 \end{bmatrix}$

The plots can be found in the attached PDF. In addition, details of the settings of the additional experiments are presented in the Global Rebuttal section, due to space limitations. Further, we will incorporate these examples in the experimental section to illustrate scenarios where the current bounds may become less tight.

Question 2. Section 4.3 could be reworked to provide first the strategy so that Theorem 4.1 can be read in this context.

We agree that introducing the strategy before presenting Theorem 4.1 will increase the readability. We will restructure this section to detail the strategy first, setting a context that makes Theorem 4.1 more understandable.

Question 3. Line 173. Seems like a word is missing there.

Thank you for highlighting this aspect. In line 173, the phrase "we define the maximum and value of the game by" is indeed referring to the introduction of two distinct quantities: $\mu_{\Theta}(A)$, which we call the maximum of the game, and $\nu_{\Theta}(A)$, which we refer to as the value of the game. To ensure clarity, we will revise this statement to more explicitly differentiate these two important concepts.

Question 4. Line 196. It is not clear what requirement can be relaxed.

Thank you for addressing this point. We acknowledge the ambiguity in our initial explanation regarding the assumptions in Corollary 3.1 about the hypothesis set $\Theta$. In Corollary 3.1, we stated that $\Theta = \mathsf{P}_b$, implying that $\Theta$ consists of all possible mixed strategies for Player 2. However, this requirement can be relaxed to $\Theta$ simply satisfying $\kappa(\Theta) = 1$, a condition already implied by $\Theta = \mathsf{P}_b$. To clarify our discussion and remove any confusion, we will revise our manuscript to make these conditions and their implications more explicit.

Question 5. Lines 593-594. A typo in reward assignment.

Thank you for catching this typo. The sentence should read "Defender gets n while attacker gets -2".

Finally, we greatly appreciate your insightful questions and valuable suggestions for improving the manuscript!

Thank you for your feedback! We're glad you found the plots informative.

In the plots, some of the simulated risk and opportunity values fall outside the bounds since the bounds presented in Theorem 3.1 and 3.2 are applicable to expected payoff gaps. The simulated values shown in the plots are sample means averaged from 100 and 1000 runs respectively, which can naturally deviate from the expected bounds. As demonstrated by comparing the top two and bottom two figures, increasing the number of runs leads to more accurate simulated values. While it's expected that the simulated values will converge within the theoretical bounds as the number of runs goes to infinity, there remains a possibility that even with 10,000 runs, some results may still fall outside these bounds (we haven't tried 10,000 runs before though). Your suggestion is quite helpful and we will include additional results with 10,000 runs in the revised manuscript.

Thank you for your thoughtful and detailed review. Your positive comments on the fundamental contribution of the paper are greatly appreciated.

1. Abstract and Introduction Clarity:

We acknowledge the need for clearer exposition in the abstract and introduction to better communicate the core ideas. We will revise the language to make the core concepts more accessible and intuitive. For example, instead of saying, The idea is to plan an agent’s own actions with respect to those types which it believes are most likely to maximize the payoff, we will clarify by stating, The core idea is to strategically optimize an agent's actions based on its beliefs about opponent types to maximize its own payoff.

2. Explanations of Technical Results and Definitions:

As suggested, in the section on matching pennies, we will enhance the discussion by explicitly linking the computations to strategic motivations within the game to help the readers better understand.

Furthermore, for theorems and definitions, we will incorporate more intuitive explanations and motivations. We will restate Theorem 4.1 (using Big O notation to highlight the critical parameters) to provide a clearer sense of the scale and implications of the results, and discuss the rationale behind the specific formulations of definitions. In particular, regarding the definition of $d(\rho,y^{\star}):=\\|\mathbb{E}_{\rho}[y]-y^{\star}\\|\_1$, it compares $\\mathbb{E}\_{\\rho}[y]$ with the true strategy $y^{\star}$ since the belief $\\rho$ in general is a distribution over the strategies in the hypothesis set $\Theta$. We will clarify this in the revised manuscript.

3. Minimax Strategy:

We have acknowledged the limitations of minimax strategies in general-sum games. In fact, in this work we primarily focus on a single player's perspective, evaluating the risk and opportunity tradeoff with respect to the individual payoff of a considered player, but not for all players (even if they hurt each other). Your comment actually suggests expanding our perspective to an interesting future direction of considering the effects of belief broadcasting on all players within a game. We are currently looking into these problems. E.g., investigate the impact of inaccuracies in type beliefs on a larger scale, such as how they would affect strategies in the context of correlated equilibria or impact social welfare measures like the PoA.

Overall, your suggestions help significantly enhance the manuscript's clarity and the accessibility of its technical content. Thank you again for your constructive feedback and the detailed questions.

Below, we present detailed responses to each of the questions.

Question 1. In Fig 5, the two baselines $\lambda=0$ and $\lambda=1$ are actually two extreme cases (corresponding to the values shown on the left top and the right bottom). We vary the value of $\lambda\in [0,1]$ to generate the other pairs of opportunity and risk values. Similarly, in Fig 6, the instances are obtained by selecting different $\lambda$'s.

Question 2. Figure 1: I think the arrow in the diagram on the right goes in the wrong direction. It should be higher = less risk?

Thank you for highlighting this issue. We recognize that the x-axis label, originally termed "opportunity," can be confusing. We initially used "loss of opportunity" but simplified it to "opportunity." To enhance clarity, we will update the label to "Missed Opportunity."

Question 3. Maybe this is obvious but it might be helpful to define a fair game, especially since you include general-sum games as far as I can tell. I think you just define it as a game where the minimax values for both players are zero.

Exactly. This corresponds to when the value of the game $\nu_{\Theta}(A) =\min_{y\in\Theta}\max_{x\in\mathsf{P}_a}x^{\top}A y=0$. We will explicitly clarify this in the revised manuscript.

Question 4. Line 133: Can you give an intuition for why you use the distance of the expected strategy $\mathbb{E}_p[y]$ to the true strategy here? Is this because the best response to belief $\rho$ depends on this expectation?

Yes, Player 1's belief about Player 2’s mixed strategy $\rho$ is a probability distribution over a set of hypothesized strategies $\Theta$ that contains a ground truth strategy $y^{\star}$. Therefore, the expected strategy $\mathbb{E}_p[y]$ is taken into account. We will simplify our notation to avoid confusion.

Question 5. Thank you for the great comment. Your understand is correct. We will add a narrative description in the manuscript to as suggested to detail how the choice of strategy affects potential payoffs and risks.

Question 6. Can you provide more intuition for Definition 1? Why is $\kappa$ chosen the way it is?

Roughly speaking, $\kappa(\Theta)$ quantifies the mass difference between the two "furthest" strategies within the hypothesis set $\Theta$. As $\Theta$ becomes denser, this mass difference would increase. This allows for the construction of a specialized payoff matrix, where columns are indexed by comparing the values from the two selected strategies to derive the lower bound. The core idea is that Player 1 is unaware of the actual strategy Player 2 uses. Thus, if the potential opportunity is high when the belief error $\varepsilon=0$, the corresponding risk escalates if Player 2 shifts from a strategy $y$ to the other $z$, where $y$ and $z$ are two strategies maximizes $\kappa(\Theta)$. In particular, if $\Theta=\mathsf{P}_b$, the set of all possible mixed strategies, $\kappa(\Theta)=1$. For this case, the opportunity and risk tradeoff is tight when the game is fair as shown by Corollary 3.1.

Question 7. In lines 70-71: repetition "in normal-form Bayesian games", we characterize ... "for the normal-form game".

Thank you for the suggestion. We have removed the redundant "for the normal-form game".

Thank you once again for the comments! Please let us know if there are any additional concerns or suggestions.

3. Page Limit

We apologize for any confusion caused by the placement of our discussion on broader impacts. According to this year's submission guidelines, including a separate "Broader Impacts" section is not mandatory. To avoid exceeding the page limit, we incorporated this discussion into the appendix/supplementary material. To prevent further confusion, we will revise the manuscript to move this discussion to the appendix after the references. Thank you for your understanding and feedback.

Further responses to other questions, including those regarding technical novelty and importance of the results, are included in the formal rebuttal and will be revealed on August 6, 11:59 PM AoE, after the rebuttal period.

REFERENCES

[David Milec et al.] Continual depth-limited responses for computing counter-strategies in sequential games. arXiv preprint arXiv:2112.12594, 2021.

[Satinder P Singh et al.] An upper bound on the loss from approximate optimal value functions. Machine Learning, 16:227–233, 1994.

Thank you for your comments. We are glad that you find the research direction of this paper interesting.

1. Technical Novelty

1.a Performance Benchmark: First, we'd like to highlight that the performance benchmark considered in this work is new. In particular, we focus on a payoff gap below induced by erroneous type beliefs:

The closest definition, to the best of our knowledge appears in the recent work by [David Milec et al.], where safety and gain have been defined for exploiting the opponent. But they haven't characterized a tradeoff systematically as we did based on the new payoff gap $\Delta_{\mathsf{NFG}}(\varepsilon;\pi)$. Analyzing this new payoff gap requires novel techniques. For instance, to bound the risk and opportunity in Theorem 3.1, we design a novel strategy construction of the mixed strategy $\pi(\rho) \coloneq \lambda \widetilde{x} + (1-\lambda)\overline{x}$. Deriving the bounds also requires nontrivial treatments such as the use of the definition of the safe strategy $\\min\_{y^{\\star}\\in \\Theta}\\overline{x}^{\\top} A y^{\\star}=\\max_{x\\in\\mathsf{P}\_a} \\min\_{y^{\\star}\\in\\Theta} x^{\\top} A y^{\\star}$ to derive the opportunity bound in Eq. (14), and the replacement of $\\max\_{x\\in\\mathsf{P}\_a}x^{\\top} A y^{\\star}$ by $\\max\_{x\\in\\mathsf{P}\_a}x^{\\top} A \\mathbb{E}\_{\\rho}[y]$ to obtain the risk bound in Eq. (15).

1.b Proof Techniques for Normal-Form Games: Proving Theorem 3.2 with a general hypothesis set $\Theta$ (consisting of candidate strategies) is not standard either, and to the best of our knowledge, has not appeared in existing literature. It's worth emphasizing that the nontrivial contribution behind is that we need to establish lower bounds on opportunity and risk that hold for any mixed strategies. The constructive proof of Theorem 3.2 introduces an interesting form of the payoff matrix (see Appendix B for more details). Furthermore, we believe that the characterization of the type intensity $\kappa(\Theta)$ defined in Eq. (5) yet simple, is of some independent interests to the communities of algorithmic game theory and ML theory. Different from classic complexity measures of a hypothesis set $\Theta$, such as the VC dimension or Rademacher complexity, type intensity measures how "intense" the candidate strategies (distributions on the action space of Player 2) in the hypothesis set $\Theta$ are. For example, if $\Theta$ is intense enough and contains two opposite strategies that have no overlaps, then $\kappa(\Theta)$ attains its maximal value $1$, where the risk and opportunity tradeoff becomes tight for fair games (see Corollary 3.1).

Together, Theorem 3.1 and Theorem 3.2 imply a fundamental risk and opportunity tradeoff, and they can not be derived from routine techniques in machine learning theory.

1.c Proof Techniques for SBG: For stochastic Bayesian games (SBG) discussed in Section 4, there is an underlying MDP coupling the strategic decisions made at each time, necessitating new analysis techniques compared to normal-form games (NFG) in Section 3. For instance, upper bounds on opportunity and risk provided in Theorem 4.1 are derived based on a highly nonstandard mixed strategy

Our first goal, bounding the payoff gap $\Delta_{\mathsf{SBG}}(\varepsilon;\pi)$ from above in Theorem 4.1 aligns with the classic loss bound due to approximate value functions in Singh et al. However, unlike Singh et al. and the follow-up papers, the policy considered in our context is not directly maximizing the approximate value function, but a mixed strategy defined by an optimization above. To handle the loss induced by the mixed strategy above, we developed two technical bounds in Lemma 1 on the per-step expected rewards with respect to different mixed strategies of the considered player and the opponents. To the best of our knowledge, we haven't observed similar results in the existing literature. Please let us know if there are any critical references we may have missed. Finally, similar to the opportunity and risk lower bounds we have derived for NFG in Theorem 3.2, the proof of the bounds for SBG draws an interesting technical connection between NFG and SBG in our context since the lower bounds in Theorem 4.2 are shown by constructing a particular stateless MDP and applying Theorem 3.2.

We thank again the reviewer for the great suggestion. We will add a section that explicitly outlines the new technical tools and methodologies we developed, and compare them with existing work to highlight their significance to help future readers.

2. Importance of our Results

We appreciate your feedback and understand your concerns.

The choice to study the trade-off between opportunity and risk was made to address a critical aspect of interactive decision-making processes that we believe is quite underexplored. As aforementioned, our work is among the first to formally consider such a tradeoff between opportunity and risk caused by erroneous type beliefs. By focusing on this trade-off, we aim to provide new insights that could have practical implications across various applications.

For example, characterizing this tradeoff helps players understand what is fundamentally achievable with untrusted beliefs. We are open to discussing alternative approaches that might be more intuitive or better aligned with your perspective, and your input is greatly valued.

3. Page Limit

We have provided a detailed explanation in the following official comment.

Thanks very much for the detailed explanations. I admit that I did not carefully go through all the proofs in the appendix. I had the impression that the proofs of Theorem 3.1 and 3.2 are ad-hoc which are based on specific constructions, while the proofs of Theorem 4.1 consist of bound analyses which are common in ML theory. The authors' rebuttal is informative and helps me understand the technical novelty better. I would recommend the authors try to elaborate more about this in the main part of the paper, especially about your point 1b (while I understand this may not be possible given the page limit).

Given that all the technical proofs are in the appendix and I did not check the appendix carefully, my assessment of the technical novelty may be unfair. I appreciate the authors' detailed response on this point, and I will be happy to see the paper's acceptance if the other reviewers like the paper.

Thank you for your feedback. We appreciate your recognition of the strengths in our paper, particularly the contribution of new theoretical insights into safe and exploitative strategies in Bayesian games with incorrect type beliefs, and the formal characterization of the trade-off between opportunity and risk.

Notation Issues Regarding the weakness pointed out, we understand that the dense notation can make the paper challenging to read. In fact, numerous subtleties arise when considering the meanings of signals and types in relation to making predictions within a stochastic Bayesian game, represented as $\mathcal{M}= \langle \mathcal{S}, \mathcal{A}, \Theta, \sigma, p, r, \gamma\rangle$. Understanding these elements is crucial for accurately interpreting game dynamics and player behaviors.

We have worked to simplify this and we will additionally work to simply the notation in the future. To address this concretely, we will review the notation used throughout the paper and simplify it wherever possible to enhance readability. Additionally, we will include brief reminders of key symbols when they are used again later in the paper to help maintain clarity. We will also add a comprehensive notation table in the appendix to serve as a quick reference to make our results more accessible and easier to follow for a broader audience.

Thank you once again for your valuable feedback.

Thank you once again for your valuable feedback. We hope our plan to address the notation issues is satisfactory. Please don't hesitate to share any further concerns or suggestions you may have.

We greatly appreciate all the suggestions and questions received. Below, we provide 1-1 responses to the issues raised.

1. Heavy Notation

Thank you for your constructive feedback. We understand that the notation-heavy nature of the problem can make our paper challenging to follow. There are many important subtleties involved in understanding the meanings of signals and types within the context of predictions in stochastic Bayesian games $\mathcal{M}= \langle \mathcal{S}, \mathcal{A}, \Theta, \sigma, p, r, \gamma\rangle$. We have worked to simplify these concepts, and we plan to further optimize the notation in future revisions to enhance clarity. To address this concretely, we will include brief reminders of previously defined quantities when they are referenced again several pages later. Additionally, we will create a comprehensive notation table to be included in the appendix, serving as a quick reference for readers. We appreciate your suggestion and believe these changes will enhance the readability and overall presentation of our manuscript. Thank you for your valuable input.

2. Tightness of Upper and Lower bounds

We agree that demonstrating how close our current results are to the tight bounds is essential for a thorough evaluation. To address this, we will include a detailed discussion in the revised manuscript. In particular, the bound is tight when the type intensity $\kappa(\Theta)=1$ (see Definition 1 in the manuscript) for fair normal-form games. Moreover, for SBGs, the bounds are tight up to multiplicative constants and a comparison is shown in Figure 3.

We provide additional plots of the opportunity-risk tradeoff in the evaluation of the 2 × 2 games using an algorithm that has varying trust of type beliefs in 100 and 1,000 runs. The plots can be found in the attached PDF. In addition, details of the settings of the additional experiments are presented in the Global Rebuttal section, due to space limitations.

In each case, the algorithm is presented with a type prediction and takes a convex combination of the best response to the type prediction and the minimax strategy with the trust parameter $\lambda$ determining how much to weigh the best response. Fully trusting ($\lambda=1$) and distrusting ($\lambda=0$) type beliefs yield a best response strategy and a minimax strategy correspondingly. The agent then samples from their resulting mixed strategy an action to play while the opponent also samples from whatever mixed strategy they are using an action to play. We sample this interaction for the number of runs and gather empirical payoff information, which we use to plot the opportunity risk trade-off.

We include as plots the bounds on the opportunity risk tradeoff and show the tightness or looseness of these bounds in two games we pick. In particular, in an Adjusted Matching Pennies game, we see that the upper bound is loose, and the empirical opportunity-risk tradeoff matches the lower bound we derive. This ‘adversarial’ example illustrates the looseness in the upper bound we derive. In the canonical Matching Pennies game, we find that the lower and upper bounds are tight with the empirical tradeoff matching these theoretical bounds.

Below are payoff matrices for the zero-sum Matching Pennies and Adjusted Matching Pennies games, respectively:

$\begin{bmatrix} 1 & -1 \\\\ -1 & 1 \end{bmatrix}; \begin{bmatrix} 1.2 & -0.8 \\\\ -0.8 & 1.2 \end{bmatrix}$

More discussions regarding the matrices above and the tightness of the bounds are provided in the global rebuttal section. Thank you once again for all the comments. We will incorporate further adversarial examples in Section 5 to illustrate scenarios where the current bounds may become less tight.