Safe Exploitative Play with Untrusted Type Beliefs
Authors: Tongxin Li
Tinashe Handina
Shaolei Ren
Adam Wierman
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian games
type beliefs
opportunity and risk tradeoff
Primary area: algorithmic_game_theory
TL;DR: We investigate the impact of incorrect type beliefs on an agent’s payoff in Bayesian games, defining a trade-off between risk and opportunity, and providing upper and lower bounds on the payoff gap for both normal-form and stochastic settings.

Abstract: The combination of the Bayesian game and learning has a rich history, with the idea of controlling a single agent in a system composed of multiple agents with unknown behaviors given a set of types, each specifying a possible behavior for the other agents. 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. However, the type beliefs are often learned from past actions and likely to be incorrect. With this perspective in mind, we consider an agent in a game with type predictions of other components, and investigate the impact of incorrect beliefs to the agent’s payoff. In particular, we formally define a tradeoff between risk and opportunity by comparing the payoff obtained against the optimal payoff, which is represented by a gap caused by trusting or distrusting the learned beliefs.Our main results characterize the tradeoff by establishing upper and lower bounds on the Pareto front for both normal-form and stochastic Bayesian games, with numerical results provided.

Safe Exploitative Play with Untrusted Type Beliefs
Tongxin Li
Tinashe Handina²
Shaolei Ren
Adam Wierman
School of Data Science
The Chinese University of Hong Kong, Shenzhen, China litongxin@cuhik edu.
#Computing + Mathematical Sciences California Institute of Technology, Pasadena, USA (thandina, (atam))@caleee edu
'Electrical & Computer Engincering University of California, Riverside, USA Staolei@uck .dd
Abstract
The combination of the Bayesian game and learning has a rich history, with the idea of controlling single agent system composed of multiple agents with unknown behaviors given a set of types, each specifying a possible behavior for the other agents. 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. However, the type beliefs are often learned from past actions and likely be incorrect. With this perspective in mind, we consider an agent in game with type predictions of other components, and investigate the impact of incorrect beliefs the agent's s payoff. In particular, we formally define a tradeoff between risk and opportunity by comparing the payoff obtained against the optimal payoff, which is represented by a gap caused by trusting or distrusting the learned beliefs. Our main results characterize the tradeoff by establishing upper and lower bounds on the Pareto front for both normal-form and stochastic Bayesian games, with numerical results provided.
Introduction
"The Chinese symbol for crisis is composed of two elements: one signifies danger and the other opportunity." - Lewis Mumford, 1944
The famous interpretation of the Chinese word for 'crisis' (known as fe. 12). although based on mistaken etymology, captures the dual nature of risk and opportunity. It provides an interesting metaphor for the inherent complexities within real-world multi-agent systems. These systems, where risk and opportunity are often inextricably linked, play pivotal role across diverse domains, ranging from human-Al collaboration and cyber-physical systems 22 to highly competitive environments like real-time strategy games and poker 4.
In conventional applied and theoretical frameworks, it typically assumed that all agents either cooperate or adhere to pre-defined policies simplifications, presenting agents that display a spectrum of behaviors ranging from cooperative, to heterogencous, irrational, or even adversarial ( This deviation from expected behavior patterns
8] However, real-world scenarios often defy these
"Correspondence to: Tongxin <litongginneuhk..ceo edu, en>.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

complicates the dynamics of multi-agent systems, agents cannot reliably predict the actions of their counterparts. The uncertainty regarding whether to trust or distrust predictions naturally leads to a critical tradeoff between the coexisted risk and opportunity, reflecting the dual aspects highlighted in Mumford's ss remark.
As critical examples, Bayesian games [10 [ provide an approach for modeling differing types of agents in strategic environments. In these games, players form belief's about others' types and update belief's in response to observed actions and choose their actions accordingly. For example, in competitive settings like poker or even in simple games like matching pennies, deviating from the to exploit weaker opponents can be beneficial, but this approach also relies on potentially flawed type beliefs [[],, making it risky to take advantage of such andeiinformation. Similarly, in real-world problems like security games, having a prior distribution of attackers' behavioral types in Bayesian game setting leads to advantages. However, exploiting incorrect types can be risky compared to just using minimax strategies. Despite the ubiquity of incorrect type beliefs in practical scenarios, limited attention has been paid to explore such tradeoff, with exceptions in designing heuristically safe and exploitative strategies in specific contexts, such as with Byzantine adversaries [ and sequential games (14)
game theoretic optimal (GTO) strategy [12 B
Inaccuracies in beliefs about others' types may arise from factors such as using
data to generate priors, changes in opponents' behaviors, or mismatches between hypothesized types and the optimal type space, etc. As noted in [15], it is evident that prior beliefs significantly affect the long-term performance of type-based learning algorithms like the Harsanyi- Ad Hoc Coordination (HBA). Although algorithms like HBA demonstrate asymptotic convergence to correct predictions or type distributions through various methods of estimating posterior beliefs, and methods exist for detecting inaccuracies in type beliefs using empirical behavioral hypothesis testing [15] the theoretical capabilities of general algorithms remain uncertain.
In general, relying on learned beliefs presents a fundamental tradeoff' between the potential payoff's from exploitative play and the risk of incorrect type beliefs. Given the potential inaccuracies in these type beliefs, using them to exploit opponents could lead to high-risk strategies. Conversely, not exploiting these beliefs might result in overly cautious play. Therefore, is natural to investigate the impact of incorrect beliefs on the agent's 's payoff, in terms of a tradcoff between trusting or distrusting the beliefs of types provided by type-based learning algorithms (e.g.. Bayesian learning [16], best response dynamics [17], and policy iteration with neural networks [18) etc.) in multi-agent systems. To summarize the focus of this paper, we aim to address the following critical question:
What is the fundamental tradeoff between trusting/distruusinng type beliefs in games?
Contributions. Motivated by the above question, we analyze the following payoff gup that arises from erroneous type beliefs:
(ee; = max d(o
max (ayoff(f 0*) - (T)) (payoff gap) &Ell
where O and 8* are predicted and true type beliefs respectively; d(..-) measures the distance between 9 and 8* bounded from above by e and will be formally specified with concrete model contexts in Section and Section 4 together with the payoff, denoted by Payoff(.;)) type 0* and the deployed strategy æ E II. We denote the given strategy space by II. The agent's strategy (f) may depend on the type belief 0. Overall, the payoff difference (1) above quantifies the worst-case gap between the optimal payoff (obtained by an optimal strategy in IT that maximizes Payoff(.,00)) and the payoff corresponding to π.
function of the true
In particular, when the agent's strategy π trusts the belief 0, it takes the opportunity to close the gap in when the belief error is small. However, when increases, such a strategy incurs high risk since it trusts the incorrect 8. Evaluating the payoff gap in (T) naturally yields a tradeoff between opportunity and risk, illustrated the right of Figure To be more precise, measure the tradeoff between two important quantities:
(Missed) Opportunity: (00; T.) corresponding to the case when the type belief's are correct; Risk: max A(E; T) measuring the payoff difference incurred by worst-case incorrect beliefs.
In summary, the (missed) opportunity measures the discrepancy of strategy π from the optimal strategy, which is aligned with the ground truth belief 0* of other players terms of the obtained payoff. Additionally, the risk quantifies how inaccurate beliefs impact the difference in terms of

---

Env
Action
Actions
State
Risk
Trusting
Type belief A +
Type
Distrusting
Agent
Trusting vs Distrusting?
Opponents d*
Missed Opportunity
Figure I: Left: A stochastic Bayesian game where an agent interacts with environment and opponents, with a belief of their types 0 E O. Right: The tradeoff between trusting and distrusting type beliefs, with trust leading to higher risk and opportunity and distrust resulting in lower risk and opportunity, implying an opportunity-rist tradcoff with varying strategy x.
payoffs in the worst case. The goal of this paper is to investigate safe and exploitative strategies in Bayesian games that achieve near-optimal opportunity and risk.
Our main results are two-fold. Firstly, in normal-form Bayesian games, we characterize tradeoff' between the opportunity and risk. We consider a strategy as convex combination of a safe strategy and the best response given type beliefs. Upper bounds Theorem 3.1 Conversely, lower bounds that hold for any mixed strategy are shown in Theorem 3.2 Notably, when the game is fair, and the hypothesis set è is sufficiently large, these bounds tightly converge. Secondly, we explore a dynamic setting in stochastic Bayesian games, where an agent, provided with type beliefs about other players, engages interactions over time, illustrated in Figure I Unlike the normal-forn approach, we utilize a value-basee strategy that establishes upper bounds on opportunity and risk, as outlined in Theorem Additionally, [hheorem442]prvvii// bounds on opportunity and risk that differ from the upper bounds by multiplicative constants, yielding a characterization of the opportunity-risk tradeoff. Finally, a case study of security game, simulating a defender protecting an elephant population from illegal poachers, is provided in Section 5
opportunity and risk are provided in
lower
2 Related Work
Learning Types in Games. The concept of type-based methods dates back to the development of Bayesian games, as first established by Harsanyi in the late 1960s [1]. The concepts of learning and updating beliefs appear in pioneering works like the adaptive learning [19]. While much game theory research, including work by Kalai et al. 200). focuses on equilibrium analysis through Bayesian belief-based learning, other studies, such as those by Nachbar et al. 21 22 and 23
24 reveal the
challenges players face in making correct predictions while playing optimally under certain game conditions and assumptions. From an application perspective, Southey al. (25 applied type-based methods to poker, where players' hands are partially hidden. They demonstrated how to maintain and use beliefs to determine the best strategies in this setting. Besides classic results exemplified above, closely related to our results, the recent work by Milec et al. (14) addresses the limitations of Nash cquilibrium strategies two-player extensive-form games, particularly their inability to exploit the weaknesses of sub-optimal opponents. They defined the exploitability of a strategy as the expected payoff that fully rational opponent can gain beyond the game's base value and introduced method that ensures safety, defined as upper limit on exploitability compared to the payoff obtained using a Nash equilibrium strategy. However, the proposed tradeoff between the exploitation of the opponent given the correct model and safety against an opponent who can deviate arbitrarily from the predicted model is applicable specifically to an algorithm that employs a continual depth-limited restricted Nash response.
Online Decision-Making with Predictions. The tradcoff between opportunity and risk analyzed in this work is motivated by the recent progress in algorithms with predictions, also known as aaggene- algorithms (26 27 for online decision-making problems such as caching 28
29 30 bipartite matching 31 online optimization [32 33), control (34 35 36
37], valued-based This line of
reinforcement learning [38 39 40), and real-world applications
work investigates the impact of untrusted predictions on two key metrics known as consistency and robustness, which are defined based on the competitive ratio of the considered contexts. is also worth highlighting that previous works in decision-making often provide
wotoooff-ootwoollll guarantees for both stochastic and adversarial environments [45 46). while the results in this work shed light on studying the intermediate regimes that do not fully align with either stochastic or
3

---

adversarial settings and delves into interactive environments formed by players whose behaviors may deviate from the type beliefs.
Stochastic Bayesian Games. Our results presented in Section draw on foundational concepts from stochastic Bayesian games outlined by Albrecht et al. [47 15], which merge concepts of the Bayesian games [10] [T] and the stochastic games (48), with applications in cooperative multi-agent reinforcement learning [2]. In [15]. three methods-produuc sum, and correlated- integrating observed evidence into posterior beliefs have been explored. Specifically, it has been demonstrated that the Dersanni-BBlllman Ad Hoc Coordination (HBA) eventually make right future predictions under specific conditions using the product posterior beliefs. However, while HBA may eventually not guaranteed to learn it with the product posterior
align with the correct type distribution, beliefs. Under certain conditions, HBA with the sum and correlated posterior converges to the correct type distribution. Nonetheless, even though methods like empirical behavioral hypothesis testing are available to detect inaccuracies in type beliefs, a comprehensive theoretical analysis is still lacking.
3 Normal-Form Bayesian Games with Untrusted Type Beliefs
Let || |/2 denote the fz-norm and |lmax denote the (clement-wise) max norm.
3.1 Problem Setting, Opportunity, and Risk
Consider a normal-form game (NFG) with two players: Player possesses a payoff matrix A e gaxb with ||A||max < a, where the first player has choices of the rows and the second player has b choices of the columns of A. Player I forms a belief about Player 2's mixed strategy, denoted by a distribution p over set of hypothesized strategies θ that contains a ground truth strategy y"
As concrete example of the payoff gap proposed in ( the following benchmark characterizes the gap between payoffs obtained by strategy with the machine-learned belief and an optimal strategy knowing y" beforehand:
ANFa(e: T) max
max Ay" xD) At)) (NFG payoff gap)
d(p.9')Sc )
=EP.
given a fixed policy π. Pe + Pa that outputs mixed strategy of the first player knowing where (p.y²) = [ - y |1. Pe and Pa are the sets of probability distributions on and a different choices of rows respectively.
In particular, we focus on measuring a tradeoff between two important quantities, the (missed) op- portunity ANF)(0; and the risk max;>0 ANFG(S;T)) T). The former measures how far the considered strategy is away from the optimal strategy knowing the ground truth type y² of Player 2 in terms of the payoff obtained; the latter quantifies the worst-case impact of inaccurate belief on the payoff difference.
3.2 Motivating Example: Matching Pennies
Before presenting general results, we illustrate the underlying concepts through a simple normal-fome game. Consider the classic matching pennies game as an example, where the mixed strategies for the players are defined as follows.
Suppose a = b 2 and each of the two players has the option choose either Heads (H) Tails (T). Let y" E [0, 1] be the true probability that Player plays H and 1 - y" the probability of playing T. Suppose the hypothesis set θ contains all possible mixed strategies, each corresponding to a type of Player 2. Then, Player 1 receives a belief of y", denoted by y, and chooses strategy that depends on y. Similarly, let x (3) be the probability that Player plays H and 1 x the probability of playing T. If two players' actions match, Player I will receive 1 and -1 otherwise. The problem setting summarized in Figure 2 Given y² and x, the expected payoff is therefore (2y* 1)(2x 1). The best response of Player 1, depending on y, is characterized by:
0
if y 2
BR(y)
0. 1]
if 2'
if y
> 2'
"Note that we assume y" E θ for the ease of presentation aligning with Assumption in 15] and our results can be easily generalized to the case when @ does not contain y" by modifying the definition of e to incorporate incomplete incorrect hypothesized types.

---

H
1,-1
-1,1
Risk
max Apple;
Trusting
1,1
1,
y
Opporrttttn
Row Player
Column Player
Distrusting
xty)
xt))
Player
belief
Player
Trusting vs Distrusting?
Op x) Missed Opportunity
Figure 2: Left: Matching Pennies payoff matrix for Player (row player) with type belief y and Player (column player) whose strategy is defined by y². Right: Opportunity-risk tradeoff that satisfies AMP(0; π) max; AMP(s;T) 2.
Given strategy π [0, > [0, 1], the payoff gap in (2 for this example is instantiated as
MP (5; = max 2 (2y* 1)BR(y") (2y" - ())(()) (MP payoff gap).
(4)
Iw-y" E
Impossibility. We first consider an arbitrary strategy π : [0, 1] + [0, 1] that misses at most (1 A) opportunity. Suppose æ chooses H with probability =(y) and T with probability 1--(y). Therefore, setting = 0, the payoff gap must satisfy
AMP x) max 2(2y - 1) (BR(g) = 1 0E(0,1]
which implies и (0) < (1 - 2 and и (1) 2 (1+ 2)/2 2/ by setting y = 0 and y = respectively. Thus, plugging in y 1 and y
conclude that
max MP (E; π)
max 2 (BR(y)) (v)) 2 2 (BR(1) x (0)) 21+1,
ly V--v-ls
since BR(1) = by 3 This implies that a has at least (1 + A) risk. Note that this argument holds for any arbitrarily chosen æ. In a word, any strategy misses at most À opportunity must incur at least 1 + À risk, in terms of the payoff.
Mixed Strategy Existence. Now, us construct a concrete strategy to derive upper bounds on the (missed) opportunity and risk. The idea is to combine the strategy BR(y), which exploits the belief of types, and the Nash equilibrium strategy of this game, known as = 1/2, which is a solution of the minimax problem min 1] (0.))()
1)(2x - 1) that enhances safety.
Fix (gy) = ABR(y) + (1 - \) a mixed strategy as a convex combination of the two strategies.
The payoff gap in satisfies
AMP ( π)
max
2(2y* - (1 - BR())) + A) (BR(v") - 1/2)
1l ls-
Opportunity: Therefore, there exists a mixed strategy æ such that when = (i.e., BR(y) = BR()")) its (missed) opportunity is bounded by
AMP (0; T) = max 2(2y - 11 X) (BR(y) - 1/2) 11-
yE
Risk: Moreover, maximizing over such that = 0, y = 1, BR( - BR(y) = 1, the risk for m always satisfies max, AMP(E: T) < 1 X.
In word, we find strategy that misses
opportunity and meanwhile has + À risk.
Pareto Optimality In conclusion, above construction shows that there is mixed strategy for the matching pennies that misses (1 (1-X) A) opportunity and incurs (1 A) risk. Conversely, any strategy that misses at most (1 - X) opportunity must have at least (1 + X) risk. The segment on the Pareto front, and the strategy constructed as convex combination confirmed to be Pareto optimal following the arguments above. This motivating example indicates tight tradeoff between opportunity and risk for matching pennies. In the sequel, we further generalize this result to normal-form games.
right of represeett
5

---

3.3 Opportunity-Riss Tradeoff for Normal-Form Games
In general, the opportunity -iik tradeoff depends on the hypothesis set θ that contains a subset of candidate strategies and the payoff matrix of the game. We state useful definitions to characterize properties of the hypothesis set θ and the considered normal-form game.
Definition Given a hypothesis set θ we let the diameter of θ with respect to the &mnnrrm be n =a ly 2||1- Define the following type intensity
((+) = max 8.2E6
Σ S.
Σ
subject to
Σ
Σ
yi.
(5)
Eigs To
Furthermore, with fixed O and A, we define the maximum and value of the game by
(A(A)= = max max |x Ayl (maximum)) ve(A) = min max x Ay (value). WEB zEP
(6)
yEB =EP_
The type intensity, as defined in 5). quantifies the divergence between two distributions within the set O, specifically those that maximize the given objective. As the density of @ increases, the value of n() approaches 1.
Theorem 3.1 (NFG EXISTENCE). Fix any θ and consider general-sue normal-form game where Player has a payoff matrix A E Ra with (e(A S y and ve (e(A) 2 v. For any S X A 1, there exists a mixed strategy Pe + Pa for Player I that misses (1 A) (p 1/) opportunity and has
(1 - X) (u v) + (f) risk.
To show Theorem 3.1
we construct mixed strategy as follows. Denote by I as the following safe/minimax strategy of Player 1, which is the Nash equilibrium when the game is zero-sum:
min T5' Ay = max min x "Ay. yE
zEP, E
Motivated by the matching pennies example in Section 3.2 Player 1 implements a mixed strategy (p) == A +1 (1
\) given the predicted belief p as a distribution over types O where ã E P
best response strategy given p such that x AEEpy is maximized. The detailed proof of Theorem 3.1 is provided in Appendix
Moreover, we further show the following impossibility result, indicating that the tradeoff in Theo- rem 3.1 is tight. We relegate the proof of Theorem 3.2 to Appendix B
Theorem 3.2 (NFG IMPOSSIBILITY). For any e satisfying s(O) 2 O. there is a payeff matrix
A E Raxb with (e(A) S Ju and (A) v such that for any 0 S if any mixed strategy
Pe P. for Player misses at most (1 (1- X) (1 -v) opportunity, then it incurs at least (n(O)μ - v) (1+ X) risk.
In particular, Theorem 3.1 and 3.2 together imply the following special case when hypothesis set @ contains all possible mixed strategies in P This corollary highlights that for a fair game, the tradeoff is tight and the mixed strategy π (p) == AZ + (1 A) with E [0, 1] is Pareto optimal when the hypothesis set contains all possible mixed strategies.
Corollary 3.1 (NFG PARETO OPTIMALITY). Suppose θ P; and the game fair. where Player I has payoff matrix A E Raxb with || S a. For any 0 < X < 1, there exists a mixed strategy π for Player that misses (1 A)a opportunity and has (1 + X)a risk. Furthermore, there is a payoff matrix A E To with ||||]] max I a such that for any < X < 1 if any mixed strategy for Player 1 misses at most (1 X) opportunity, then it incurs at least (1 + X) a risk.
is worth noting that the requirement can be relaxed straightforwardly so that as long as the hypothesis contains two mixed strategies such that ss()) = 1 in (5). the statement holds. The proof of Corollary 3.1 can be found in C
Stochastic Bayesian Games with Untrusted Type Beliefs
In many real-world applications. agents are coupled through shared state in stochastic Bayesian games (SBG) 15), which combines standard Bayesian games [10 II with the stochastic games 48 In this section, we consider an infinite-horizon time-varying discounted n-player stochastic Bayesian game, represented by a tuple M == (S, A, O a. P. 7), and analyze the impact of beliefs on the opportunity-rist tradeoff.

---

4.1 Preliminaries: MDP for Stochastic Bayesian Games
Let S be finite set of states. Write N := (1, n). Let A(t) be the set of finitely many actions that player i E N can take at any state E S. Furthermore, == A(1) :=
x ... x A(n) denotes the (a(i) : E N) with a(i) E A(i). The types of other players are unknown
set of action profiles to the i-th player. The set θ = I jæz {(j) is product type space where each opponent j chooses types from Ø-- We focus on the decision Decision-making of the i-th player, considering stationary (Markov)
strategies F At each time t 2 0 each player # uses mixed strategy Ty : :S x O()) + PAC) parameterized by a type that depends on the current state and the true type 0z E O We use r: x A + IR to denote the reward function for the i-th player, which is assumed to be bounded, as formally defined below.
Assumption 1. The reward r: S A - R satisfies that (r(s, a)) S. &max for all E S, E A.
For any pair of states (s, 8') and action profile a E A, we define p(s"|s,uu a) as a transition probability from to s' given an action profile a. Finally, let y E (0, 1) be discount factor. We define the expected utility of the i-th player using a strategy Ty as the expected discounted total payoff
J 0m. = E Σ rrr (8t,
(8)
where 64, = (0) ((()) i), with respect to stochastic processes (s; ~ ~p (c-1; 1)) 1)
and (u.(1) Ti (2:) which generate the state and the action trajectories. The expectation in ( is taken with respect to all randomness induced by the initial state distribution state transition kernel p. and strategy profile ı (as well as opponents' types in +).
Po E Ps. the
4.2 Opportunity, Risk, and Type Beliefs
Suppose the i-th player has beliefs of the other players' types, provided by a machine-learned forecaster, denoted by 0-,- For notational simplicity, write mi, the strategy for the i-th player as т, and the strategies -- for the opponents as a (parameterized by 9-1). Furthermore, we omit the subscripts and denote the type beliefs and true types as I and 6*, and write the payoff in (8) J (œ) if there is no ambiguity. The i-th player uses a strategy x S x θ + PA((). which is function of the type beliefs of the other players. Given a strategy æ used by the agent and strategies by other players, denoted by a, we define the following useful value functions of the game:
(s) = E
y- 'r (82, at) 1sc =
which satisfies the Bellman equation V (s) Ea-n(s) [(r + PPV (s, (a. where define an operator PV (s, (a, a')) = E. (3'' [V (s')).
The following worst-case payoff gap is defined similarly as the one in for normal-form games, which in our context can be considered as the dynamic regret for strategy म. against an optimal strategy. Note that an optimal strategy is also a best response strategy x knowing the true types of all players in hindsight maximizing (9). The optimal value function given a and n² is denoted by V+ (s), whose Bellman optimality equation is V*. = max (r + yF V* (s)
Definition 2 (SBG PAYOFF GAP). Given a stochastic Bayesian game M (8, (,,,A.,,, f). a fixed strategy ग, the payoff gap is defined as
ASBG(E; T)
sup d(0,0 See SOES
sup
-=00)_=)0)00000)) (SBG payoff gap)
(10)
where 8o denotes an initial state and d (0,0*) == max.es [|o[(; 0) (s; 0*) S.
Similar to normal-form Bayesian games, we define the (missed) opportunity and risk below.
Definition 3. Given payoff gap ASBO(E: т) in 10 the (missed) opportunity of π is 3(x) =
Assa(Os (0; 2)) and the risk is ((T) == max ASBG (5:
'Note that if all the other players use Markov strategies, then the considered player has a best response that is Markov strategy.
7

---

10
Upper bound. y- 0.0
Lower bound. --00
bound. 7-0
Lower bound. 7-03
bound p00
16
tound. y=
tound, y
bound,
Nisied Oppertuiiy 560.5)
Figure 3: Comparison of upper (Theorem 4.1 and lower (Theorem 4.2 bounds on (missed) opportu- nity and risk with a varying discount factor = 0.0, 0.3, 0.5, 0.8, with // = and Fmax
Our goal is to characterize tradeoff between the opportunity and risk for stochastic Bayesian games. Finally, we define the value of the game.
Definition 4. Given hypothesis set O and a stochastic Bayesian game M = A5,A. we denote the value of M by
(M(M) = max min [T; 0-s) (value). 8_.
(1I)
4.3 Opportunity-Rinn Tradeoff for Stochastic Bayesian Games
Based on the definitions above, our first result states upper bound on the opportunity and risk for stochastic Bayesian games. Proving the bounds in Theorem 4.1 is nontrivial because the players coupled by shared state. Consequently, the analysis used in Section 3 for simple convex combination of the best response to type beliefs and safe strategy in normal-fora games cannot be directly applied the stochastic setting.
Theorem 4.1 (SBG EXISTENCE). Consider stochastic Bayesian game M = AS. with ve (M) 2 V. For any < 1, there exists strategy т whose (missed) opportunity and risk satisfy
72 - 6
((T)
(Ci(7) - -7v) (1 A), with C1(7)
1 1- A7
(1 7)
8(T)
(C2(7) mmax 720) (1 + A), with C2(1) max (Ca(7),
X7
C2(7) 72 +y and C1(r) 2 2-2 27 +1
1
(1 71
where Fmax is defined Assumption
The proof of Theorem 4.1 is given in Appendix D which constructs the following strategy.
Given type beliefs 9, denote a parameterized strategy Ø (0)), and let (0) be the safe strategies of the opponents, with being an optimal solution of the minimax optimization in (TT). Denote V V*,0 and V == V*,5 the optimal value functions with the opponents' strategies being and ō respectively. Unlike the convex combination used to show Theorem (31] for normal-form Bayesian games, the strategy constructed for proving Theorem 4.1 is value-based strategy below
(0:s)= max (ARx(s)ō(s)) (1- ()))())
(12)
aC))
where \ a parameter that indicates the level of trusts on type beliefs, and for fixed state s E S and given value function V S - R, Rv is an A(i) x I A(j) matrix defined as
Ry ((a;, a a. :) = r (a: a)) + Σ p (s'ls, (a,, a)) (s).. V()).
.'ES
As indicated by Theorem 4. through the case studies presented in Section [ Finally, the following lower bounds can be derived, implying that the upper bounds on (xx) and ((T) are tight and value-based strategy formed (12)
this design ensures safe and exploitative play, with its efficacy validated
are Parcto optimal up to multiplicative constants. Together, the bounds are illustrated in Figure

---

11
23
25
25
15
23
11
2.
14
25
25
23
Acan:
G4i
0.4
25
Adlen
Adlen
16
11
12
A 0.5
T1
88
200
25
38
24
20
24
20 23
25 23
2.%
Figure 4: Comparison of average payoff for player when varying values of À and 6 potential discrete types for an instantiation of 2 2 game.
Theorem 4.2 (SBG IMPOSSIBILITY). There is a stochastic Bayesian game M A,,AA
whose value satisfies ve (M( v such that for any 0 S X 1, any strategy π misses at most (Tmax 2) (1 X) opportunity, then it incurs at least T-x (Tmax 11 (1 X) risk.
In Theorem 4.2] the bounds on (missed) opportunity and risk differ from those Theorem 4. by multiplicative constants. Theorem 4.2 can be derived by applying Theorem 3.2 for normal form games to stateless MDP. We relegate the proof of Theorem 4.2 to Appendix
Case Studies
2 x Game We provide set of numerical evaluations showcase the opportunity-risk tradcoff
across range of game theoretic scenarios. We begin with focus on 2 x 2 games and to that end we sample games spanning the topology
matrix games as shown in [4 This topology
includes the comprehensive set of 78 strictly ordinal 2 x 2 games introduced by [50]. We formulate
our evaluation as single state Stochastic Bayesian Game with the state being a specific 2 x game.
This evaluation is helpful in providing a concrete illustration of the tradeoff dynamics on wide range of games within a particular topology given the comprehensive bench-marking done on the set of 2 games.
We make use of 3 broad type classes (Markovian, Neural Networks) inspired from work by [5T]. It is from these classes that we construct our types which are then used in simulations with a player leveraging a strategy that a convex combination of a safe strategy and the best response give type beliefs predictions. Figs 5 shows the tradeoff in one particular game as an agent moves from being fully robust as indicated by 0 to fully trusting of the advice when À 1. In Appendix[1 F we provide further information on the particular types as well as illustrations on a couple other games sampled from the topology of 2 x games to showcase the range of tradeoffs which exist in this landscape.
and Co-evoloved
Security Game. Extending our empirical study real world settings, we also provide an evaluation of the opportunity-risk tradeoff using data from wildlife tracking studies. Security games are a clear domain wherein the tradeoff between opportunity and risk is very critical to the application. Building on a large body of work that has sought to understand the implications of game theoretic analysis in the environmental conservation domain, we formulate and explore the opportunity -iik tradeoff using data from real world wildlife movements, In particular, we formulate green security game motivated by works such as (52) wherein we simulate defender who is trying to protect an elephant population from attackers who are illegal poachers. The defender and attacker engage multi-state Stochastic Bayesian Game where the states are constructed from historic elephant movement data sourced from
[33] Our evaluation shows the practicality and wide ranging impact of this investigation. Figure

---

6 Behavioral Typas
@larovibnn Types)
Row Player
Colurri Playee
Rlwas adio
Player1
Type
Player
Marruc stottg
2x Ganes
Leste-ollwee-liigg
Crovived Nearal Notwkks
Opporuitty
Figure 5: Left: 2 x games considered in our case study; Right: Opportunity- risk tradeoff in the evaluation of 2 game using an algorithm that has varying trust type beliefs 1,000 random runs. Fully trusting (A = 1) and distrusting (A = 0) type belief's yield a best response strategy and minimax strategy correspondingly.
Exarrple state Mean dlephann location (Ap Sept 2013)
12
24
04 1.
23 24
62 02 04
65
02
04
-
A 0.75
1
0.
02
02
13
01
64 36 02
81 82
82
04
00
00
13
19
1p
Andicted 100
Jueraa
Figure 6: Comparison of average payoff for the defender in a security game protecting an elephant population against illegal poachers when varying values and potential discrete attacker types.
shows the tradeoff for this setting evaluated for each particular type. We include implementation details on this game in Appendix
Concluding Remarks
In this study, we explored the fundamental limits of safe and exploitative strategies within both normal-form and stochastic Bayesian games, where pre-established type beliefs about opponents are considered. Given that these type beliefs may inaccurate, relying on them to exploit opponents can result in high-risk strategies. Conversely, not leveraging these beliefs yields overly cautious play, leading to missed opportunities. We have quantified these dynamies by providing upper and lower bounds on the payoff gaps corresponding to different type belief inaccuracies, thereby characterizing the tradcoff's between opportunity and risk. These bounds are consistent up to multiplicative constants.
Limitations and Future Directions. In our current problem setting, the dynamics of a stochastic Bayesian game is assumed be stationary, aligning with the canonical models in the related literature (for example (51)). To address this limitation, we plan to extend our framework to include time- vareing type beliefs, addressing the absence of analysis for MDPs with dynamic transition probabilities and reward structures. Additionally, refining the opportunity and risk bounds to make them tighter would provide more precise strategic insights.
10

---

Acknowledgement
We would like to thank all the anonymous reviewers for their helpful comments.
Tongxin Li was supported in part by the National Natural Science Foundation of China (NSFC) under grant No.72301234, the GuangDong Basic and Applied Basic Research Foundation, NSFC under grant No. 62336005, the PengCheng Peacock Supporting Scientific Research Fund Category C (2024TC0024), the GuangDong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2023B 2 2010001), and the Shenzhen Key Lab of Crowd Intelligence Empowered Low-Carbon Energy Network (No. ZDS Z20S220220006 0000600000000000100000 100001002..
Adam Wierman was supported in part by the U.S. NSF under grants CNS-2146814, CPS-2136197, CNS-2106403,, NGSDI-21056411
References
[1] Xue Yan, Jiaxian Guo. Xingzhou Lou, Jun Wang, Haifeng Zhang, and Yali Du. An efficient end- to-end training approach for zero-shot human-ai coordination. Advances in Neural Information Processing Systems, 36, 2024.
[2] Shiyong Wang. Jiafu Wan, Daqiang Zhang, Di Li, and Chunhua Zhang. Towards smart factory for industry 4.0: a self-organized multi-agent system with big data based feedback and coordination. Computer networks, 101: 11::15888.,, 2016
[3] Oriol Vinyals, Igor Babuschkin, Wojciech M Czamneki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 575(7782)3350-333 35400,34,255 2019.
[4] Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456):885-899) 2019.
[5] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Picter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competiiiee environments. Advances in neural information processing systems, 30, 2017.
[6] Stefano Albrecht and Peter Stone. Autonomous agents modelling other agents: A compre- hensive survey and open problems. Artificial Intelligence, 258:66-99 00669,,425 2018
[7] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement learning. Journal of Machine Learning Research, 1111))) 2020.
[8] Joannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On the convergence of no-regret learning dynamics in time-varying games. Advances in Neural Information Processing Systems, 36, 2024.
[9] Simin Li, Jun Guo, Jingqiao Xiu, Ruixiao Xu, Xin Yu, Jiakai Wang, Aishan Liu, Yaodong Yang, and Xianglong Liu. Byzantine robust cooperative multi-agent reinforcement learning as bayesian game. In The Twelfth International Conference on Learning Representations, 2023.
[10] John C Harsanyi. Games with incomplete information played by "bayesian" players, i-iii part i.
the basic model. Management science, 14(3):159- 182, 1967.
[11] John C Harsanyi. Games with incomplete information played by "bayesian" players part ii bayesian equilibrium points. Management science, 14(5):320-335 1968.
[12] Lawrence Friedman. Optimal bluffing strategies in poker. Management Science, 17(12):B-764 1971.
[13] Norman Zadeh. Computation of optimal poker strategies. Operations Research, 25(4):541-562 1977.
[14] David Milec, Ondřej Kublček, and Viliam Lisy. Continual depth-limited responses for comput- ing counter-strategies in sequential games. arXiv preprint 21Xiv:2112.12594, 2021.
11

---

[15] Stefano V Albrecht, Jacob W Crandall, and Subramanian Ramamoorthy, Belief and truth in hypothesised behaviours. Artificial Intelligence, 235:63-8 94, 2016.
[16] James S Jordan. Bayesian learning in normal form games. Games and Economic Behavior, 3(1):60-81, 1991.
[17] Martin Bichler, Max Fichtl, and Matthias Oberlechner. Computing bayes-nash equilibrium strategies in auction games via simultaneous online dual averaging. Operations Research, 2023.
[18] Martin Bichler, Maximilian Fichtl, Stefan Heidekrüger. Nils Kohring, and Paul Sutterer. Learn- ing equilibria in symmetric auction games using artificial neural networks. Nature machine intelligence, 3(8):687-695, 2021.
[19] Paul Milgrom and John Roberts. Adaptive and sophisticated learning in normal form games. Games and economic Behavior, 3(1):82-100, 1991.
[20] Ehud Kalai and Ehud Lehrer. Rational learning leads to nash equilibrium. Econometrica: Journal of the Econometric Society, pages 1019-1045, 1993.
[21] John H Nachbar. Prediction, optimization, and learning in repeated games. Econometrica: Journal of the Econometric Society, pages 275-309, 1997.
[22] John H Nachbar. Beliefs in repeated games. Econometrica, 73(2):459-480, 2005.
[23] Dean P Foster and H Peyton Young. On the impossibility of predicting the behavior of rational agents. Proceedings of the National Academy of Sciences, 18822): 2001.
[24] Eddie Dekel, Drew Fudenberg, and David K Levine Learning to play bayesian games. Games and economic behavior, 46(2):282-30) 2004.
[25] Finnegan Southey, Michael P Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. arXiv preprint arXiv: /207. 1, 2012.
[26] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Online optimization with uncertain information. ACM Transactions on Algorithms (TALG), 8(1):1-29, 2012.
[27] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pages 9661-9670, 2018
[28] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM- SIAM Symposium on Discrete Algorithmss, pages 1834-1844 SIAM, 2020.
[29] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
[30] Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious beaning--augment caching. In International Conference on Machine Learning, pages 9588-9601. PMLR, 2022.
[31] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In International Conference on Machine Learning, pages 345-355. PMLR, 2020.
[32] Nicolas Christianson, Tinashe Handina, and Adam Wierman. Chasing convex bodies and functions with black-box advice. In Conference on Learning Theory, pages 867-908. PMLR, 2022.
[33] Pengfei Li, Jianyi Yang, Adam Wierman, and Shaolei Ren. Robust learning for smoothed online convex optimization with feedback delay. Advances Neural Information Processing Systems, 36, 2024.
[34] Tongxin Li, Yue Chen, Bo Sun, Adam Wierman, and Steven Low. Information aggregation for constrained online control. ACM SIGMETRICS Performance Evaluation Review, 49(1):7-8 2021.
12

---

[35] Tongxin Li, Ruixiao Yang. Guannan Qu, Guanya Shi, Chenkai Yu, Adam Wierman, and Steven Low. Robustness and consistency in linear quadratic control with untrusted predictions. ACM SIGMETRICS Performance Evaluation Review, 50(1): 1007:1077118, 2022.
[36] Yiheng Lin, Yang Hu, Guannan Qu, Tongxin Li, and Adam Wierman. Bounded-regret mpc via perturbation analysis: Prediction error, constraints, and nonlinearity. Advances in Neural Information Processing Systems, 35:36174-361881 2022.
[37] Tongxin Li, Ruixiao Yang, Guannan Qu, Yiheng Lin, Adam Wierman, and Steven H Low. Certifying blx policies with stability for nonlinear control. IEEE Open Journal of Control Systems, 2:49-66 62, 2023.
[38] Noah Golowich and Ankur Moitra. Can q-learning be improved with advice? In Conference on Learning Theory, pages 4548-4619. PMLR, 2022.
[39] Tongxin Li, Yiheng Lin, Shaolei Ren, and Adam Wierman. Beyond black-box advice: Learning- augmented algorithms for mdps with q-value predictions. Advances in Neural Information Processing Systems, 36, 2024.
[40] Jianyi Yang, Pengfei Li, Tongxin Li, Adam Wierman, and Shaolei Ren. Anytime-competinne reinforcement learning with policy prior. Advances in Neural Information Processing Systems, 36, 2024.
[41] Tongxin Li, Bo Sun, Yue Chen, Zixin Ye, Steven H Low, and Adam Wierman. Learning- based predictive control via real-time aggregate flexibility. IEEE Transactions on Smart Grid, 12(6):4897449133 2021.
[42] Nicolas Christianson, Christopher Yeh, Tongxin Li, Mahdi Torabi Rad, Azarang Golmoham- madi, and Adam Wierman. Robustifying machine-learned algorithms for efficient grid operation. In NeurlPS 2022 Workshop on Tackling Climate Change with Machine Learning, 2022.
[43] Tongxin Li. Sreniing-uugmnnted Control and Decision- Making: Theory and Applications in Smart Grids. PhD thesis, California Institute of Technology, 2023.
[44] Tongxin Li and Chenxi Sun. Out-of-diisrrbutioonavaaa electric vehicle charging. IEEE Trans- actions on Trunsportation Electrification, 2024.
[45] Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. Advances in Neural Information Processing Systems, 11-20491-20502. 2021.
[46] Idan Amir, Guy Azov, Tomer Koren, and Roi Livni. Better best of both worlds bounds for bandits with switching costs. Advances in neural information processing systems, 35:15800-15810, 2022.
[47] Stefano V Albrecht and Subramanian Ramamoorthy. A game-theoretic model and best- response learning method for ad hoc coordination in multiagent systems. arXiv preprint 1rXiv:1506.01170, 2015.
[48] Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):1095-1100 1100, 1953.
[49] Bryan Bruns. Names for games: Locating 2 x 2 games. Games, 6(4):495-520, October 2015.
[50] Anatol Rapoport and Melvin Guyer. A taxonomy of 2 2 games. General Systems: Yearbook of the Society for General Systems Research, 11:203-214, 1966.
[51] Stefano Albrecht, Jacob W. Crandall, and Subramanian Ramamoorthyc. Belief and truth in hypothesised behaviours. arXiv preprint arXiv:1507.076888 2015.
[52] Fei Fang, Peter Stone, and Milind Tambe. When security games go green: Designing defender strategies to prevent poaching and illegal fishing. IJCAI, 2015.
[53] Chamaille-Jammer African elephant (migration) chamaillé- jammee hwange np, 2009-2017.
13

---

[54] Satinder P Singh and Richard C Yee. An upper bound on the loss from approximate optimal- value functions. Machine Learning, 16:227-233 1994.
[55] Jacob W. Crandall. Towards minimizing disappointment in repeated games. Journal of Artificial Intelligence Research (JAIR), 49:111-142, 2014.
[56] John R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. The MIT Press, 1992.
14

---

Broader Impacts. The implications of our research extend beyond theoretical interests and have practical significance in fields such as economies. cybersecurity, and strategic planning, where decision-making under uncertainty is crucial. By improving the understanding of how predictive information can be used safely and effectively in competitive environments, our work supports the development of more robust strategies in these areas. This can lead to better risk management practices and enhance the ability of systems to make informed decisions even when faced with unreliable incomplete information. However, there are potential negative impacts, such as the risk of misuse of predictive models that may lead to biased or unfair decisions if the underlying data or assumptions flawed. Future research could focus reducing these risks, ensuring Al systems remain reliable and safe.
A Proof of Theorem 3.1
We first consider bounding the opportunity, focusing on the case when the predicted belief contains no error, i.e., y² =Epyy) By the definition of x (p), for any payoff matrix A with (a(A) )) S / and ve (A) 2 we get
ANFG((;
max E6
max Ay" - =(D)Ag)) zEP.
<(1 A)
max max x Ay" min :- Ay" E'
(13)
TEPa V'
where we have maximized the two terms maX x Ay" and T Ay" separately y" θ to obtain (33. Therefore, noting the definition of the safe strategy x in
(1 (1 ANFG (0; 5(1 - X) max max x. A'y max min I Ay" s E0
A) (u v)). (14)
=EP. EB
Now, consider bounding the risk. By the definition of the following mixed strategy (pp) used by Player 1, for any payoff matrix A with (e(A) S μ. (A) 2 v, and ||A]] max I a,
ANFG(E;T))
max d(o.s" SE
max Ay" - (pp)) Av" xEP
m AEplvl AE Any - -11- (1- TcP,
min T AAAA
(15)
d(p.v))Se
SS=
Er
In (15). we replace maxzeP, x" Ay" by maxzeP, x² AEE since y" E θ and there exists a feasible P with Ep [b] y* that always satisfies the constraint (p. (p.y")= SE.
Since T is best response strategy given p. holds that maxzeP, xT AEAElyl = posing max Ay (1 - X) maxxep. IT "yy" + AmmxxEEP, x Ayy and maximizing the two terms (1 A) maxxep, xr. Ay and À maxxeP, x. Ay" over d (p.v²) s respectively, A (();0 can be further bounded from above by
AEply). Decom-
max A:IlAl|max
(a->)
max x AAy + A xEPa.y'E6
max (i A[E - -")) - (1 A)w) (16) (S
Since d (p,0") = |Eplyl yr 11
16
yields
ANFO(E;T) S(1 X) (p v) Ape.
(17)
Maximizing over e < ())) for [17.. conclude the theorem.
B Proof of Theorem 3.2
We first suppose mixed strategy π Pe -> Pa for Player misses most (1 2) (n v) opportunity, given belief of types p Pe.
15

---

Let y and y" be two mixed strategies in θ that achieve x(O) are multiple to break the tic), i.e.,
2 0 (select arbitrary strategies if there
x<()
Σ v S
Σ 3/ subject "0
Σ 1/4 Σ "n,/""!
36
Let =i
3/ and I_ { : S 8. be two indices of actions with Consider payoff matrix Ap
non-negative and positive coordinates of where [b] : 1.....1 b). with the following form. Suppose without loss of generality that a is even; otherwise, we append an all-zero row to Ag. Let 3 = μ V. For the i-th column of Ano we set it as (3, -8.-...... -8) if
i I+ and (-B.p..... 3) i Formally, we define:
3
-B
B
A Ap
+ Av,
++1ET_
where (Ap)is = for all i E [a] and j E [6]. Clearly, with this A, (e(A) S and (A(A) 2 u. Then, by definition, setting 0 with Epyl y" (the type belief contains error), the payoff gap satisfies
ANFO (0;
max 5
max x Ay" -())))))))))))))))))))))())))- (1- -)(( -v). PEP.
(18)
Now, plugging in sf into 18) above. This implies
max E SEP
max Ay" xpp) AU") A 2 m Ay' -(p)) Ay' -Tp))Ay' = [pp) Ay'. zEP.
(19)
For notational convenience, denote / (9) = Einsso 11 Evig V.. Combining 18 and
(p) Ay' = ((p) + Ad)u' 2 (1 A)v + Ap. Thus, (p) Aud 2 A(u v). Equivalently,
(9) (+ (μ- 1) T(p) A( v), where = (1, 11,1, 1, -1) By the construction of A.
we get
S --> - v) x(O)
(T))"AW)" - - (F(D) f) f) ( (4- v).
Σ SN!
Σ
Vi
r())
Therefore, since 0 < <(9) 1,
=pp) (An, Av)y" T And Sv ( k(O) -xpu((t) (1 An(O))u
Hence, we get
T max Ay" TP) Agg) 5* E zEP.
> max T Asy" (Pp) Ay" zEP.
max
2 x(() (1 + A) (1+ Ac(O))
2 (m(0) v) () (1+
C Proof of Corollary 3.1
If r Рs, then x(O) 1. Furthermore, by definition, we get
HA (P²) = max max Jx: T Ay] = || VA (P&) = min max x. Ay = 0, yEP, zEP.
yEP. xEP_
where the equality on the RHS holds since the game is fair. Applying Theorem the corollary.
and
we obtain
16

---

D Proof of Theorem 4.1
Given type beliefs, we denote strategies ō == o(0). o o (0)), and let J = = be the safe strategies of the opponents, with 0 being an optimal solution of the minimax optimization in (II). Denoting V = V+. V == V.. V = V the value functions with the opponents' strategies being a 0, and a, respectively. Given the strategy π defined in ( we first state two useful bounds.
Lemma 1. Given the strategy defined in (1), the following bounds on the reward function hold:
BOUND 1:
Ex [r] -n,, [r] S SX (Bp.a [V* - Eppa [V*(s)) + 2A (ETmax + 7m)
+7(1 A) p.p [V()] Bp..r [v()))
+(1 X) (RT [r] E (r]) + (1 - A) (E,,, [r] - ETT [r]); (20)
where vj == max
V* (s) - (s)) and
BOUND 2: E [r] - E [r] S y (Ep, [V()] - Ey, [V(s]]
(E,, [r] E [r]) + Ep, [(s)] - E2, (V(+))) (21)
Proof of Lemmal
7 First, we prove BOUND 1 in (0
Based on the definition of the policy x in (12). it follows that for any fixed state E S,
XEg a [r] + (1 - A [r] + >E p. [V(s)] + 7(1 E) oo [V))]
<XE,,5 [r] + (1 >) [r] p.E [v()] + 7 A) [V+)]
(22)
Furthermore, considering the difference between the expected rewards corresponding to implementing n² and the strategy defined in 12). since by Assumption |r| I Tmax for all i E (7] and any strategy π E 11,
E [r] - E., [r]] < max ( (s)ll Tmax S ETmax-
(23)
SES
Therefore, using 23
Ex,,, .o [r] Ex, [r] => (Bir+ [r] - Ex, [r]) + (1 X) (Ex+ [r] - Ex, [r])
A (ETT,,a [r] Ex,5 [r]) + (1 - A) (Ext, aa [r] Ex, [r]) 2XeTmax
+ (1 - X) (Emr, [r] Ex.,, (r])
+ (1 >) (Bn,7
[r])
(AL . [r] + (1- +1-A)) [r]) (AlE,, [r] + (1 A)E [r]
+ (1 A) (F....o [r] Ex . (r))
+ (1 - A) (E.,,r [r] En,g [r]) + 2A5Y
(24)
Combining (22 and 24 we obtain
Byr, a [r] E [r] 27er max
Sx \ (B 3 [(s) -p..r . (s))) + (1 ()) [V<)] - Ep.r + [(s)))
+11 A) (Ex [r] [T1. (r)) + (1 - X) (Ex. [r] Ex, [r)).
(25)
By definition,
Ep. [*(]]] Ep. [[s]]]
S Σ Σ
( p(s'ls, ls (3)))
s'ES a.''EA
and similarly, E -
[s)] - Eppor o [[(s]]
$ 5n thus, 25 yields
Eg,,a [r] - Ex [r] <>> ( V (s)) - pp . V (s)) + 2X (STmax + +7m)
+ 7 A) (B [Bp,,.7 [T()) Ep,, , [[()))
+ (1 >) (E,r, [r] - E [r]) + (1 - A) (Er.o [r] - Er [r]).
17

---

Next, we show BOUND 2 in 21
By the definition of the policy in 11). it follows that for any fixed state E S, similarly we obtain
A [r] + =,, ir] + yb R, [s)] + 7(1 1 p.F V(s)
SXEx a [r] + (1 X)EE [r] + AB p. [[s)] + +1(1 - V(s)]
(26)
Rearranging the terms in (26)
P [r] E [r] S 7 (Ep. [V()) B.p, [V(s)]
(Bxra [r] BT, [r]) + (Ep., [v()] p. [(s))))
Using Lemmal 1 the following lemma provides bound on ASBG(E; x), from which bounds on both risk and (missed) opportunity can be directly derived.
Lemma 2. The payoff gap for the policy æ defined in 12) satisfies
Tmax
2(1 - X)
2A
(1 (1- A)(2 (1- (112-1) 7) 2)
+ 7 - v)
ASBG(S; T) <
+ min
xy
1-7
1
7
1-7
X7
Proof. By definition of the payoff gap (see Definition 2 and the value function in (). we get
AsBG(e;a)=
sup max )se #ES
(V** (s) V=(0)
Our first goal is to derive an upper bound on ASBG R), aligning with the classic loss bound of approximate value functions [54]. However, the policy considered in our context is not directly maximizing the approximate value function, but mixed strategy defined by an optimization as in (12). For notational convenience, write for E S.
E Ep, [V(s)]
Σ p(sl|s, (a, ()) G.''ES
For notational simplicity, we denote V=(() == (s))s). For any state s E S and strategies (a, ō) satisfying d (0,00) max.es [o{s;;) o(s; 0s;00)) 0*) I applying BOUND 1 in Lemma the Bellman equations corresponding to x and π imply
(s) (s) =E,,, [r] - [r + (Ep.rs [V' E.,,o [V* (s)))
S A7 Bpp. (s)] E.p. [>)] E,,x [V* B. [V (s))
+7(1 - A) (Ep,r,77 [V()] Ep.r. [+(()] + Eppor [s(ss) - By [()))
+(1 A) (E,, [r] E,, [r]) + (1 A) (E.r., [r] Ex [r])
+2A (ETmux + 77).
(27)
Applying the Bellman equations, for any E S
(*()) =Bawa(e), (8) ) [(r + yPV* (s, (a, d'))
= Er,, [r] + ++ 7.p... [V*(s)]
(28)
Similarly, it also holds that
(s) = Ex [r] + BBpr . [V (s))
(29)
Plugging
28 and
29
into 27
V' (*) (s) (s) >
E E [V* (s)] - Ep. . (s)] + Ep [V]]]] Ep [s)])
+ (1 1)
((E,, [r] + TBp.p [(s)] V*(
(30)
+ (1 2) 2)(( (s) (E.., [r] B.. [V()])
(31)
+ 2A (Ermax + +m))
(32)
18

---

Let VV (8) = (s) for any E S. For the term in 30 we always have (= 2 V' (s) (c.f.
48
thus,
(En [r] + t.p [V()]) - (5) EY Epp... [V()) E., [((ss]
=yBpp V(s) - V'(())) (8)
Furthermore, the Bellman equation implies
((s) V (8) [E [r] En, (r]) +2 E Ep.55 [(s)]
E V (s))
(33)
Applying BOUND 2 in Lemma
V(s) V (s) v B B [(s)] B,, a V (s)] + E Ep, [V(s] Ep ,
[(s)]
(Bn, [r] - E [r]) +7 (E... [ss) Ep.z,ö [((s)
+ 1- x
2 Epp o [V(s] - -Ep V (s)]
2A
((1 1+ 1--)) ))
Tmax.
(34)
1-X
Since above holds for any state E S, let s' be a state such that the value gap (*(s) - V*((s is maximized. Therefore, (34) implies
2
V(s)
(1 - 7)2 maxx
(35)
Then, for the term in 31 by definition (*)) S Tmax / - 7). and
E [r] + 7.p.pr [V(s]] 2 Tv Tmax-
(36)
Combing the bounds in 335 and
36 with 32
conclude that
(*(s)- - (s) SXy
Ep (+) Ep [*((s) + Ep.rr. [V((s) - Ep.,o (+)()))
+ (1 7) Mimax + (1 - 2) (2 -
1 1-77 Tmax -gu) + 2A (Ermax + ym) (37)
Now, noting that by definition we have
E Ep,r,o
[v]] - Ep. [v]]
Σ p(s'ls, (a)) - S
Tmax
1-7
and similarly,
Ep [*] E.. . [V*]|
<s Tmax
1
Therefore, rearranging the terms and simplifying above,
37 becomes
2X
2
('(8) - V" <
7)2 Tmax + (1 (1-
mmax 7V)
+ 2X (Ermax +
2 27Armax E + 72 (Ep.r.o [V]] (
(38)
Since above holds for any state E S, let s* be a state such that the value gap V*(s) - V*(() is maximized. Thus,
E [s*) (V=x.o(V((s"))
Σ Ep(''ss x a)) (7))
-
E''ES
19

---

Continuing from 38
(V*
(=())) - X7 (V* - (*())))
(1 7]- + 71 8 + A8
+2 + +(1 -1) (2 -
2 2 mmax - 77
ma
1-9
+ (1 -1)) (1 11-7"
2-72
max
(1-
+
+
mmax - 7u)
Therefore, rearranging the terms obtain
ASBG(E;
Tiaxx
2
2x
(1 - 2)(2 2)(2-7))
+ (2Xr) (1- - A)v)
1-My xy
1-7 (1 (1-7)² 7)2
1 1-9
1 xy
Now, the terms in (30) can be bounded alternatively as
<2 1-X
(1 -
A) () ((E,, [r] + 7.Eppn -
T T'ax.
1 1-7
Using this and following the same steps, obtain
Tmax
2λ 2(1 -1 A)
(1- (1-1)(2-7))
7 7(211 (1- (1-A)p)
ASBG(E; T)
xy 1- 1
1-7
1 1-7
1- x7
Part I: Proof of Risk Bound
Since d (0, max.es (lo(s; -s(;)))) S 17
setting the worst = 2, and noticing that
2mmax.
1-y
T m'ax
(4(1-12)+2)
71- + (1- ()2 -112-1))
7(1 71- ~A)
ASBG T) S xy
1 1-7
1 xy
Rearranging above leads to the result.
Part II: Proof of (Missed) Opportunity Bound Finally, setting 1) 0, we obtain
1
(g2 37 +6) (1 7)2 -7
) (1-
ASBC (0; S 11 by
T'mxx
E Proof of Theorem 4.2
We prove the theorem by considering a stateless MDP, which reduces a stochastic Bayesian game
M (S, A, Q a, p, 7) to normal-form game in Theorem 3.2
Let L (1, 11.... II 1i 1461). We fix a strategy kernel a such that
<(0) = max +E
Σ
01(3;0)- -
Σ
a(s0:0)) = 1.
LE (s:0)0))
Therefore, the construction of the payoff matrix A E RIA LAGil in the proof of Theorem 3.2
with (A) < I-
Tmaz and (A) 2 yields that for any 0 < X < 1, if any mixed strategy π misses
(Tmax v) (1 - A) opportunity, then since
(Tmax v) (1-1)
1-- v) (1 (1-2), A),
Tmax
the strategy π has at least
Fmax - w) (1 (1+ 2) risk. Furthermore, since 1-7
Tinax
Tmax
V/
1-- 1 (1 + 1)
by 1- 1->7 (1+
has at least X (Tmax v) (1 A) risk.
20

---

F Details on Experiments
F.1
Details on 2 Game simulations
F.1.1
Game definition
We define a Stochastic Bayesian game with one state: particular 2 x 2 game sampled from the topology of x 2 games.
The payoff's for each player are stipulated by the 2 game. We set the time horizon for the game be 1,000 giving us an empirical evaluation of the expected payoff for each strategy
F.1.2 Type definitions
As mentioned we have classes of types and below we provide description of the general classes as well as the specific types we used in our evaluation.
1. Markovian Types: These are types whose strategy only depends on the current state. We made use of 4 types of Markovian strategies
Type Always play action 0
Type 2: Always play action 1
Type 3: The minimax strategy for the player
Type 4: Returns a random strategy
2. Leader- Foligeer-Trigger Agents:
Inspired by [55], these agents have a preferred sequence of play they seek to enforce. Importantly they have access history of play and when the other player does not play according to their preferred sequence the alter their strategy by engaging in "punishing" behavior such as playing the minimax strategy by resetting to previous action. In our case, we evaluated against simple versions of such agents, wherein our agent had preferred mixed strategy and when the empirical observed strategy over preset number of previous plays from the opponent did not match their preferred strategy, they "punished" the opponent by playing minimax strategy. In particular, we had an agent look at the previous 4 actions of the opponent and if they selected action 1 more than twice, they chose to play a minimax strategy for the next round.
3. Co-evolved Neural Networks: Inspired by work in [51) we use ideas of genetic program- ming [56]. to generate agents from neural networks. We randomly initialized 10 neural networks with single hidden layer for both the row and column player. All networks would take as input the previous 4 actions of both players and the corresponding state information. We sample randomly from populations of the row and column players and simulate the game. After simulation we calculate a fitness score based on average payoff's for each agent and similarity score so to ensure diversity the models. We "evolve" the populations by selecting random portions of both populations to mutate whilst also having cross-over between members of the populations selected by fitness (this is done for both populations hence "co-evolve"). We then proceed to create new populations using the most fit agents from previous generation (i.e., we take the top 50% of a population pre-evolution and 50% post evolution and then create a new population if the average fitness of this new constructed population greater than the average fitmess of the previous population.)
F.1.3 Experimental illustration of tightness of bounds
We have included additional adversarial examples to demonstrate the tightness of the bounds presented in Theorems 3.1 and 3.2 particular, we consider the zero-sum Matching Pennies (MP) and an Adjusted Matching Pennies (AMP) our two examples. We assume the hypothesis set + for Player contains behavioral types:
Markovian Types:
Type 1: Always play action 0
Type 2: Always play action 1
-yye 3: Minimax strategy
Type 4: Random strategy
21

---

Type 5: Trigger Agents
Type 6: Co-evolved Neural Networks
The payoff matrices for the MP and AMP, respectively are
[ 1 and
L
1.2
-0.8
1
1
0.2
0.2
0.8
1.2
0.2
0.2
It's worth mentioning that the AMP payoff matrix constructed above is an adversarial example that follows the same construction of the adversarial payoff matrix A used in the proof of Theorem 3.2 Given the considered e we know that x()) = and n7)) = 2. The upper and lower bounds in
Theorem 3.1 and 3.2 therefore read:
Upper Bound: (1- x) 1), y= (1- A) 1) + 2Aμ, A E [0,1],
Lower Bound: I = (1 2)(1-)1 (olu-v), v), y (1+ A) - D) X [0, 1].
where for MP, fr = 1,
for AMP, μr =122, 1=2,v=00 0.2.
Besides the bounds above, we also plot simulated risk and opportunity values in the figures using an algorithm that has varying trust of type belief's 100 and 1,000 runs. 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 weigh the best response. is the same as x, the mixed strategy used to prove Theorem 3.1 Fully trusting (A = 1) and distrusting (A 0) type beliefs yield a best response strategy and minimxx 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 numher of runs and gather empirical payoff information, which we to plot the opportunity risk tradeoff. The variance of the risk and opportunity values decreases as the number of runs increases, as illustrated by the error bars in the attached figures. Moreover, we include plots the bounds on the opportunity risk tradeoff and show the tightness or looseness of these bounds in two games we pick. Please note that some of the simulated risk and opportunity values fall outside the bounds. This because the bounds are applicable only expected payoff' gaps, and individual simulations may deviate from these expected values.
In the Fig 7 the top two figures display the results from 100 runs, while the bottom two figures present the results from 1,000 runs. The left two figures correspond to the MP example, while the right two figures for the AMP example, demonstrating the gap between the lower and upper bounds. In particular, an AMP game, we see that the upper bound loose, and the empirical opportunity-rist tradeoff matches the lower bound derive. In future work, will investigate if this gap can be closed. 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, coinciding with Corollary 3.1
22

---

Upp bound
2.4
Upper bured
bound
Lawer
22-
24-
18-
12-
1.0
04
6.6
88
1.0
Opperianily
Opportunty
Upper 33rnd
Lower bound
22-
18-
2.-
1.-
14-
12-
1.0
1.a
1.
0.0
Opportueniy
Opportanity
Figure 7: Opportunity-risk tradeoff for Matching Pennies (MP) and Adjusted Matching Pennies (AMP) games over 100 (top) and 1,000 (bottom) runs. Left: Matching Pennis. Right: Adjusted Matching Pennies. As the number of runs increases, the variance of both risk and opportunity values decreases.
F.2
Detaíls on Green Security Game simulations
E22.1
Data description
The data is from study tracking geo-location information of 32 African elephants in the Hwange National Park in Zimbabwe, Africa. The data was collected from 2009 to 2017 and includes time stamp information well as longitudinal and latitudinal information of the elephants
F.2.2 Data processing
We divided each year into two based the seasons in Zimbabwe which would affect the location of the elephants as they migrate given changes in the environment. A year was divided into a "Rainy" season which runs from October to March and "Dry" season which runs from April to September.
We divided the area covered the dataset into 9 locations and thus had 3 3 grid which served as a surveillance area. For each elephant in the season, we calculated its mean location and so for each of the seasons we had a mean location for the elephants. is important to note, given migratory nature of elephants across national borders, each season does not necessarily have all 32 elephants as they move as a result of a wide range of factors (c.g., availability of water). Some seasons, also notably, do not have any recorded elephant presence in the area under surveillance. We do not see this as a limitation as the dynamic environment presents changes in the game which the defender has to take into account.
F.2.3 Green Security Game
Each of the seasonal elephant information presents us with state for our Stochastic Bayesian Game We define the game in the following manner:
State: We have 16 states from the seasonal information we get from the data
Actions: Each player (attacker or defender) has available actions each corresponding to a selection of an area in the 3 x 3 grid defined above.
Payoffs: Let n be the number of elephants recorded in particular grid square:
23

---

If the attacker and defender select the same grid square, the defender gets n while the attacker gets -2
If the attacker and defender select different grid squares, Rott be the number of elephants in the grid square selected by the attacker. The defender gets payoff -attt while the attacker gets payoff Natt
These payoffs were designed model the asymmetric nature of the defending task. offender often will get a fixed penalty stipulated by law, whilst the defender always depends on number of elephants the attacker has access to.
Transitions: To take into account the effect of changes in weather whilst also bringing in some stochasticity, we made it such that there is some transition probability between any "Rainy" state to any "Dry" state and vice-versa. We do however, slightly, increase the probability of transition between adjacent historical states, to reflect historical data. We have the probability of transitioning between any two "Rainy" or "Dry" states be zero. Our transition probabilities do not depend on the actions taken by the agents.
F.2.4 Type definitions
We make use of the same types as in the 2 x 2 game simulations. We make adjustments to the Markovian types in that Types and 2 now select the grid with the highest population of elephants and second highest population of elephants, respectively. The Seader-Followerr Trigger Agents now looks to see if the other player is selecting the grid with the highest number of elephants for more than 50% of the historic play in which case they turn to play their minimax strategy
F.3 Additional 2 game evaluations
We include an illustration as well as for completeness couple of other 2 x 2 games we also evaluated against. This helpful shows the variety tradeoffs that exist within the topology of 2 x 2 games. In particular, we see some games exhibiting gradation as the agent moves from fully robust fully trusting whilst in others there does not exist such tradeoff because of the existence of dominant strategy for the row player regardless of the type of the column player (e.g., the last game we show this section). We note that the games provided this file not exhaust the entire topology of 2 x games. They are however added to show the range of tradeoffs that could exist in games.
24

---

7x2
A=
0.99
11
200
11
(0)
Adtinn
[231
13.4
380
380
300
XX
3M
3.0
340
300
300
280
280
200
290
26
280
0.00
0.0
000
240
700
741
14
251 040
741
Acton
11.11
180
160
180
16
180
180
380
160
16-
1:00
2.0 030
230
01
1.0 037 039 239
231
4clen2
72
13
13
T1
T2
T3
15
TE
ProfAted byp
280
700
T1
Trakinsthes
Trakoer
73
71
12
70
13
Prodeced Tpe
Prodeced Tpp
Prodectdd Type
10
2.0
40
Petlogo USikt
0.25
T1
745
Adban
PM 760
741
74h
140
160
340 900
943
Adton
199 1.6 74h 941
2.41 200 947 941
160 744 3:0 345
7.4 145
Producted Ryp
Predeted Typ
375
Poskeed Sye
Prokect
Proficto
Profktol
Profeciol
60
Aussage triilyy
Acticn
Fredicted 1pp
Predicted Type
A
2 075
Preducted
Assinage U1
25

---

7x2
A=
0.999
11
250
055
11
Adtin
[1.4]
M422
1:0
251
240
250
251
XX
253
0.00
252
230
250
241
240
240
24
250
240
053
040
140
210
74) 74
Actonn
0331
12.3
351
251
254 251
751
253
16-
1:41 240 240 040
250
050 231
A0011
72
13
14
13
T2
T2
T3
13
Frstkttd hye
Proftted bye
2214
200 253
T1-
(23) 299
Trakind
Trakeee
73 74
13
70
13
Prodeced Opp
Produced Tpp
Prodectdd Type
1.
2.0
50
4.0
Petlogo USiit
2x2
A
C
-- 0.25
72
120
100
T1-
Actinn
12.4]
11:33
4.0 200
1.0
130
120
73
1.0
22
1.0 100
10
V1
72
1.5
Adtonn
13:11
1422
1.0
1.0
100
T6-
135
191
539
V11
T6
530
130
537
536
4cten22
12
14
11
12
106
130 von
T1
1.00
190
390
390 390
180
15)
140
34 300
100
118 1/8
180
156
100
136 191 136 135
T6
15
12 13 14
15
12 13
15
Prediceed Nie
Predicted Tye
Predkted Tym
NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The claims made in the abstract and introduction align with our theoretical and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
26

---

Answer: [Yes]
Justification: The limitations of this work are discussed in our last concluding remark section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell--pecfiicaion. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
We have clearly stated our model assumptions for the derived results to hold.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have detailed the settings and parameters used in the experiments, and we will further release our code after the anonymous review stage.
27

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-sonnee open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Our contributions focus on the theoretical side. The experimental results shown in the submitted manuscript do not depend on private datasets and can be reproduced using the provided settings and parameters.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.
ssionooiccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
28

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have clearly stated our experimental settings and details to reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: When there is randomness in experiments, characterize the variability. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our contributions focus on the theory side, and the experimental setup is sufficiently basic that it does not require intense computing resources such as GPUs.
Guidelines:
29

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The research conducted conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have discussed both positive and negative societal impacts in our conclud- ing remark section.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications,
authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
30

---

Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
31

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "vM1K9tirF7", "reviewer": "Reviewer_m4Kj", "summary": "This paper characterizes the trade-off between risk and opportunity in the games where the player need to infer other participants types. Upper and lower bounds in normal-form and stochastic Bayesian games are proved.", "questions": "Please see weakness section.", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper provides a solid theoretical foundation for normal-form and stochastic Bayesian games with type uncertainty. The presentation is clear with good examples.", "weaknesses": "While the overall presentation is good, the problem, by its nature, can be notation-heavy. I would suggest the authors to add more recall to the previously defined quantities when involving them several pages later, and/or make a notation table.\n\nAs the authors mentioned, tightening the upper and lower bounds is a future direction. However, it is not clear how much the current results are off from the tight ones. Thus, including the comparison between the true opportunity/risk vs. theoretical bounds would be helpful for evaluation of the currents results. If possible, also including adversarial examples in the experiment section to show how current bound can come loose in some scenarios would strengthen the completeness of the work more.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate all the suggestions and questions received. Below, we provide 1-1 responses to the issues raised.\n\n***1. Heavy Notation***\n\nThank 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.\nTo 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.\n\n***2. Tightness of Upper and Lower bounds***\n\nWe 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. \nIn 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.\n\nWe 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.\n\nIn 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.\n\nWe 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.\n\nBelow are payoff matrices for the zero-sum Matching Pennies and Adjusted Matching Pennies games, respectively:\n\n$\n\\begin{bmatrix}\n  1 & -1 \\\\\\\\\n  -1 & 1\n\\end{bmatrix};\n\\begin{bmatrix}\n  1.2 & -0.8 \\\\\\\\\n  -0.8 & 1.2\n\\end{bmatrix}\n$\n\nMore discussions regarding the matrices above and the tightness of the bounds are provided in the global rebuttal section.\nThank 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8FEDrt6QGY", "reviewer": "Reviewer_caR8", "summary": "The paper explores the dynamics of Bayesian games where players form beliefs about other players' types and update these beliefs based on observed actions. It specifically examines the risks associated with relying on potentially inaccurate type beliefs and how these inaccuracies impact the payoffs of strategies. The main focus is on quantifying the tradeoff between opportunity (the potential payoff when beliefs are accurate) and risk (the potential loss when beliefs are incorrect). The paper provides theoretical bounds on this tradeoff for both normal-form and stochastic Bayesian games.", "questions": "No", "limitations": "Authors did discuss the limitations of this work.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper tackles the under-explored area of safe and exploitative strategies in Bayesian games with incorrect type beliefs, contributing new theoretical insights. The authors provide upper and lower bounds on the payoff gap, which characterises formally the interesting tradeoff between opportunity and risk.", "weaknesses": "Although the paper is fair well-structured, the paper's notation is quite dense and could be simplified for better readability, especially for those not very familiar with Bayesian games.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n***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. \n\nWe 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. \n\nThank you once again for your valuable feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FEvm6RDj29", "reviewer": "Reviewer_4mAk", "summary": "The paper explores how players in Bayesian games can manage the inherent uncertainty about other players in a strategic way, aiming to maximize their outcomes (exploitative) while minimizing potential risks (safe).\n\nThe main theme of the paper is the tradeoff between the opportunity and risk of exploiting unreliable beliefs. The paper discusses the balance between the safe yet conservative strategy and the risky yet exploitative strategy, with parameters in the mixed strategies indicating the level of trust on type belief.\n\nFor both normal-form games (simpler, static games) and stochastic Bayesian games (more complex, dynamic games), the paper provides upper and lower bounds on the payoff gaps between the optimal possible strategy and the actual strategy of trusting/distrusting the beliefs.\n\nFor normal-form games, in Theorem 3.1, the authors establish upper bounds on the payoff gap, indicating limits on potential gains or losses based on the accuracy of type beliefs. In Theorem 3.2, the authors provide lower bounds, showing fundamental risk levels that cannot be mitigated through strategic adjustments alone.\n\nFor stochastic Bayesian games, in Theorem 4.1, the authors offer upper bounds on opportunity and risk over an infinite horizon, accounting for the evolving nature of the game states and strategies. In Theorem 4.2, they affirm the lower bounds in dynamic settings, reinforcing the existence of inherent trade-offs between exploiting accurate type beliefs for higher returns and safeguarding against errors to minimize losses.", "questions": "I do not have more questions. Please feel free to comment on anything you do not agree with my review.", "limitations": "The authors have adequately addressed the limitations.", "rating": 4, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "-The characterization for the trade-offs between opportunity and risk is neat and relatively complete. \n-The research direction of this paper is interesting to me.", "weaknesses": "Both the technical novelty and the importance of the results are unclear to me. For the technical novelty, it seems to me that the analysis in this paper, although non-trivial, is standard in machine learning theory. The authors did not mention about the new technical tools used in this paper. I would recommend the authors briefly summarize about the technical novelty of this paper, compared with existing work.\n\nI am also uncertain about the impact of the results. While I agree that the research direction of this paper is interesting, I am not sure the specific choice of studying the trade-off between “opportunity” and “risk” is the most natural one.\n\nIn addition, this paper exceeds the page limit!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We are glad that you find the research direction of this paper interesting. \n\n***1. Technical Novelty***\n\n***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:\n$$\n    \\\\Delta\\_{\\\\mathsf{NFG}}(\\\\varepsilon;\\\\pi) := \\\\max\\_{d\\\\left(\\\\rho,y^{\\\\star}\\\\right)\\\\leq \\\\varepsilon} \\\\left(\\\\max_{x\\\\in\\\\mathsf{P}\\_{a}}x^{\\\\top}A y^{\\\\star} - \\\\pi(\\\\rho)^{\\\\top}A y^{\\\\star}\\\\right).\n$$\nThe 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}$. \nDeriving 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).\n\n***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 \nin 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). \n\nTogether, 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.\n\n***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 \n$$\n    \\\\pi\\\\left(\\\\theta;s\\\\right) \\\\in \\\\text{argmax}\\_{a\\\\in\\\\mathsf{P}\\_{\\\\mathcal{A}(i)}} a^{\\\\top} \\\\left(\\\\lambda R\\_{\\\\widetilde{V}}(s)\\\\widetilde{\\\\sigma}(s)+(1-\\\\lambda)R\\_{\\\\overline{V}}(s)\\\\overline{\\\\sigma}(s)\\\\right).\n$$\n\nOur 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. \n\nWe 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. \n\n***2. Importance of our Results***\n\nWe appreciate your feedback and understand your concerns. \n\nThe 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. \n\nFor 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.\n\n***3. Page Limit***\n\nWe have provided a detailed explanation in the following official comment.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X9pLB7nfJj", "reviewer": "Reviewer_iunt", "summary": "The paper studies a setting in which an agent is trying to exploit opponents in a game based on uncertain beliefs about the opponents' strategies. In this setting, exploiting opponents can be risky if the beliefs might be wrong. The paper studies the trade-off between exploiting as much as possible, while minimizing the risk in case the opponent beliefs are wrong. The paper explicitly characterizes this trade-off for normal form and stochastic games, and they provide strategies that achieve theoretically optimal trade-offs. Finally, the authors provide an experimental study in 2x2 games and in a security game.", "questions": "- Are there more baselines one could compare the set of strategies in figures 5 and 6 to? I guess $\\lambda =1$ and $\\lambda = 0$ can be viewed as the two baselines?\n- Figure 1: I think the arrow in the diagram on the right goes in the wrong direction. It should be higher = less risk?\n- 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. It seems less obvious to me what a fair general-sum game is (I think you just define it as a game where the minimax values for both players are zero?).\n- Line 133: Can you give an intuition for why you use the distance of the expected strategy $E_\\rho[y]$ to the true strategy here? Is this because the best response to belief $\\rho$ depends on this expectation?\n- It would be helpful to say in words what is going on with the strategies in Matching Pennies in Section 3.2. As far as I understand, the idea is that when choosing $\\lambda=1$, in the worst case, you get -1 payoff but could have achieved payoff 1 (if your opponent is deterministic and you have exactly the opposite belief), leading to 2 risk in this case. In the case $\\lambda =0$, one gets the equilibrium payoff 0, but maximal exploitation could get a payoff of 1, so in this case the opportunity would be 1.\n- Can you provide more intuition for Definition 1? Why is $\\kappa$ chosen the way it is?\n\n- In lines 70-71: repetition \"in normal-form Bayesian games\", we characterize ... \"for the normal-form game\".", "limitations": "The authors adequately address limitations.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Characterizing the trade-off between exploitation of beliefs and being robust to wrong beliefs seems like an important and fundamental contribution to me. I am somewhat surprised that this apparently hasn't been done before.\n- The overall approach of the paper seems substantial and comprehensive to me. I like both the thorough theoretical analysis and empirical study.\n- Overall I found the paper clear and easy to follow.\n- I think it's great that the paper discusses matching pennies as a motivating example\n- Formal definitions are properly introduced and mathematical statements are rigorous", "weaknesses": "- I think the abstract and introduction could be written more clearly. E.g., lines 4-5 \"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\" this confuses me rather than explaining the core idea (which is best responding given the belief about opponent types?). Or lines 20-21 \"players may not be fully trustworthy and thus do not know the behaviors of the others\" this sentence doesn't really compute/make sense to me.\n- One could improve some of the explanations of technical content. E.g., in matching pennies, explicitly discuss the motivation in terms of the strategies in the game (rather than just computing the different quantities). In the different definitions and theorem statements, one could give a bit more intuition for the results (e.g., can one state Theorem 4.1 in terms of rough order of magnitudes/Big O notation, and give some intuitive explanation why it has to be that way?) and why definitions are chosen one way and not another way (e.g., why is $d(\\rho,y^*)$ defined the way it is).\n- Minor comment: the minimax strategy can be very bad for a player in general sum games where players can harm each other without benefit to themselves. In that case, being better than minimax might not be that useful (e.g., in a great power conflict, the minimax strategy corresponds to all out nuclear war). Hence, I think the results here make most sense for zero-sum games or other games where the minimax strategy is a reasonable strategy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and detailed review. Your positive comments on the fundamental contribution of the paper are greatly appreciated.\n\n***1. Abstract and Introduction Clarity:***\n\nWe 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.```\n\n***2. Explanations of Technical Results and Definitions:***\n\nAs 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. \n\nFurthermore, 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.\n\n***3. Minimax Strategy:***\n\nWe 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.\n\nOverall, 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. \n\nBelow, we present detailed responses to each of the questions.\n\n**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.\n\n**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?*\n\nThank 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.\"\n\n**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.*\n\nExactly. 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.\n\n**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?*\n\nYes, 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.\n\n**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.\n\n**Question 6.** *Can you provide more intuition for Definition 1? Why is $\\kappa$ chosen the way it is?*\n\nRoughly 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.\n\n**Question 7.** *In lines 70-71: repetition \"in normal-form Bayesian games\", we characterize ... \"for the normal-form game\".*\n\nThank you for the suggestion. We have removed the redundant \"*for the normal-form game*\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Vr8vtq1yM8", "reviewer": "Reviewer_Ui8p", "summary": "The paper considers a setting of stochastic bayesian games where the beliefs of the opponents’ strategies may not be fully trusted. The authors first analyze the problem in the stationary setting and then move to an MDP setting. The main outcome is that there is a trade-off between risk and opportunity depending on the trust in the belief.", "questions": "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\n1. Section 4.3 could be reworked to provide first the strategy so that Theorem 4.1 can be read in this context.\n1. Line 173. Seems like a word is missing there\n1. Line 196. It is not clear what requirement can be relaxed\n1. Lines 593-594. A typo in reward assignment", "limitations": "limitations are discussed", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and can be understood by a non-expert such as myself. \n1. There are few examples that explain well the trade-offs and the design choices \n1. The case studies underline the practical implications of this theoretical work.", "weaknesses": "While it is interesting to consider and make the decision based on the trust in the belief, I think a discussion on alternatives is needed. For example, many machine learning algorithms would provide uncertainty bounds or estimates. One can similarly derive strategies based on these bounds", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your feedback. We appreciate your recognition of the strengths in our paper.\n\n***Alternative Forms of Beliefs:***\n\nRegarding 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. \n\nHere are our 1-1 responses to address each question raised in the comments:\n\n**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.*\n\nThank 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.\n\nWe 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.\n\nBelow are payoff matrices for the zero-sum Matching Pennies and Adjusted Matching Pennies games, respectively:\n\n$\n\\begin{bmatrix}\n  1 & -1 \\\\\\\\\n  -1 & 1\n\\end{bmatrix};\n\\begin{bmatrix}\n  1.2 & -0.8 \\\\\\\\\n  -0.8 & 1.2\n\\end{bmatrix}\n$\n\nThe 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. \n\n**Question 2.** *Section 4.3 could be reworked to provide first the strategy so that Theorem 4.1 can be read in this context.*\n\nWe 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.\n\n**Question 3.** *Line 173. Seems like a word is missing there.*\n\nThank 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.\n\n**Question 4.** *Line 196. It is not clear what requirement can be relaxed.*\n\nThank 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. \n\n**Question 5.** *Lines 593-594. A typo in reward assignment.*\n\nThank you for catching this typo. The sentence should read \"*Defender gets n while attacker gets -2*\".\n\nFinally, we greatly appreciate your insightful questions and valuable suggestions for improving the manuscript!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We greatly appreciate all the questions received from the reviewers. 

In this global rebuttal, we provide detailed discussions below regarding the additional experimental results, which can be found in the attached **PDF**.

***Tightness of Bounds:***

Thanks to the suggestions by **Reviewer** **m4Kj** and **Ui8p**, we have included additional adversarial examples to demonstrate the tightness of the bounds presented in Theorems 3.1 and 3.2. In particular, we consider the zero-sum Matching Pennies (MP) and an Adjusted Matching Pennies (AMP) as our two examples. Aligning with our experiments presented in our manuscript (e.g., Figure 5), we assume the hypothesis set $\Theta$ for Player 2 contains 6 behavioral types:

* Markovian Types:
  - Type 1: Always play action 0
  - Type 2: Always play action 1
  - Type 3: Minimax strategy
  - Type 4: Random strategy

* Type 5: Leader-Follower-Trigger Agents

* Type 6: Co-evolved Neural Networks

The payoff matrices for the MP and AMP, respectively are
$
\begin{bmatrix}
  1 & -1 \\\\
  -1 & 1
\end{bmatrix};
\begin{bmatrix}
  1.2 & -0.8 \\\\
  -0.8 & 1.2
\end{bmatrix}=\begin{bmatrix}
  1 & -1 \\\\
  -1 & 1
\end{bmatrix} + \begin{bmatrix}
  0.2 & 0.2 \\\\
  0.2 & 0.2
\end{bmatrix}
$

It's worth mentioning that the AMP payoff matrix constructed above is an adversarial example that follows the same construction of the adversarial payoff matrix $A$ used in the proof of Theorem 3.2 (see Appendix B in the manuscript for more details). Given the considered $\Theta$, we know that $\kappa(\Theta)=1$ and $\eta(\Theta)=2$. The upper and lower bounds in Theorem 3.1 and 3.2 therefore read:

$$\textsf{Upper Bound: } x=(1-\lambda)(\mu-\nu), \ y=(1-\lambda)(\mu-\nu)+2\lambda\mu, \lambda\in [0,1]$$

$$\textsf{Lower Bound: } x=(1-\lambda)(\mu-\nu), \ y=(1+\lambda)(\mu-\nu), \lambda\in [0,1]$$
where for MP, $\mu=1$, $\nu=0$; for AMP, $\mu=1.2$, $\nu=0.2$. 

Besides the bounds above, we also plot simulated risk and opportunity values in the figures using an algorithm that has varying trust of type beliefs in 100 and 1,000 runs. 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. It is the same as $\pi$, the mixed strategy described in Lines 180-181 used to prove Theorem 3.1.  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. The variance of the risk and opportunity values decreases as the number of runs increases, as illustrated by the error bars in the attached figures. Moreover, 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. Please note that some of the simulated risk and opportunity values fall outside the bounds. This is because the bounds are applicable only to expected payoff gaps, and individual simulations may deviate from these expected values.
 
In the attached **PDF**, the **top** two figures display the results from 100 runs, while the  **bottom** two figures present the results from 1,000 runs. The **left** two figures correspond to the MP example, while the **right** two figures are for the AMP example, demonstrating *the gap between the lower and upper bounds*. In particular, in an AMP game, we see that the upper bound is loose, and the empirical opportunity-risk tradeoff matches the lower bound we derive. In future work, we will investigate if this gap can be closed. 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, coinciding with Corollary 3.1.

Meta-review: The paper aims to provide a theoretical characterization of the impact of incorrect beliefs on an agent's payoff in Bayesian games. The reviewers generally find the direction explored in this paper interesting: the formal analysis appears to be standard, but the set of results was deemed conceptually novel and thorough by some of the reviewers. Several reviewers raised concerns about the presentation quality. I therefore strongly encourage the authors to revise their paper accordingly. It would be valuable if the authors added additional explanations and results from the rebuttal, especially examples to illustrate the tightness of the bounds.
Decision: Accept (poster)