Exploiting Opponents Under Utility Constraints in Sequential Games
Authors: Martino Bernasconi
Federico Cacciamani
Simone Fioravanti
Nicola Gatti
Alberto Marchesi
Francesco Trovò
Venue: NeurIPS 2021 Poster (2021)
Keywords: Sequential games
online learning
opponent exploitation

Abstract: Recently, game-playing agents based on AI techniques have demonstrated super-human performance in several sequential games, such as chess, Go, and poker. Surprisingly, the multi-agent learning techniques that allowed to reach these achievements do not take into account the actual behavior of the human player, potentially leading to an impressive gap in performances. In this paper, we address the problem of designing artificial agents that learn how to effectively exploit unknown human opponents while playing repeatedly against them in an online fashion. We study the case in which the agent's strategy during each repetition of the game is subject to constraints ensuring that the human's expected utility is within some lower and upper thresholds. Our framework encompasses several real-world problems, such as human engagement in repeated game playing and human education by means of serious games. As a first result, we formalize a set of linear inequalities encoding the conditions that the agent's strategy must satisfy at each iteration in order to do not violate the given bounds for the human's expected utility. Then, we use such formulation in an upper confidence bound algorithm, and we prove that the resulting procedure suffers from sublinear regret and guarantees that the constraints are satisfied with high probability at each iteration. Finally, we empirically evaluate the convergence of our algorithm on standard testbeds of sequential games.

Exploiting Opponents under Utility Constraints in Sequential Games
Martino Bernasconi-de-LLcea
Federico Cacciamani"
Politecnico di Milano
Politecnico di Milano
martino lerraasson.delllcaalllll...
federico. cacci aeneiiimanniimm @polimi it
Simone Fioravanti
Nicola Gatti
Gran Sasso Science Institute
Politecnico di Milano
simone. www.neffforaaaaiiiiiaa aagpaaaaantnniiiiiaaaeee
Alberto Marchesi Politecnico di Milano
Francesco Trovò Politecnico di Milano francesco1 trovo@polimi..c
alberto. marchesi@poll imi it
Abstract
Recently, game-playing agents based on Al techniques have demonstrated super- human performance in several sequential games, such as chess, Go and poker. Sur- prisingly, the multi-agent learning techniques that allowed to reach these achieve- ments do take into account the actual behavior of the human player, potentially leading to an impressive gap in performances. In this paper, we address the problem of designing artificial agents that learn how effectively exploit unknown human opponents while playing repeatedly against them in an online fashion. We study the case in which the agent's 's strategy during each repetition of the game is subject to constraints ensuring that the human's 's expected utility is within some lower and upper thresholds. Our framework encompasses several real-world problems, such as human engagement in repeated game playing and human education by means of serious games. As first result, we formalize a set of linear inequalities encoding the conditions that the agent's 's strategy must satisfy at each iteration in order to do not violate given bounds for the human's 's expected utility. Then, we use such formulation in an upper confidence bound algorithm, and we prove that the resulting procedure suffers from sublinear regret and guarantees that the constraints are satisfied with high probability at each iteration. Finally, empirically evaluate the convergence of our algorithm on standard testbeds of sequential games.
Introduction
Algorithmic game theory and machine learning have recently contributed to groundbreaking achieve- ments in artificial intelligence, leading the deployment of artificial agents that defeated top human professionals in several recreational games. See, for example, the well-known milestones achieved in chess [Campbell al. 2002] Go [Silver et al. 2016). and poker [Brown and Sandholm 2018 2019 Surprisingly, multi-agent learning techniques that have been recently employed in such settings leam how to defeat humans without taking into account their actual behavior. Indeed, they learn strategies by simulating millions of plays in a self-play approach, without including any human player in the learning process. direct effect of this methodology is that the resulting artificial agents not
Eqqua contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

adapt to the actual capabilities of humans, potentially leading to an impressive gap in performances compared to the case which the agent learns strategies while taking them into account.
In this paper, we address the problem of designing artificial agents that learn how to effectively exploit unknown human opponents while playing repeatedly against them in an online fashion. In particular, we study the case in which the strategy that the agent plays during each repetition of the game is subject to constraints ensuring that the human's ' expected utility within some lower and upper thresholds, Our framework models several real-world human-agent interactions, and it begets additional technical challenges compared to simple pure-exploitee exrloxixlitttiin scenarios.
One prominent application of our framework is when the artificial agent's goal is not only exploiting the human opponent, but also ensuring that he/she remains engaged in the game. Guaranteeing humans' engagement is crucial when designing artificial agents that play repeatedly against humans. Indeed, when playing against a super-human agent, most human players drop out from game playing, since they realize they are losing too often against it. As Eagi--aaay and Törmänen (2020) sharply observe, is "hopeless and frustrating to play against an AI, since it is practically impossible to win". Different forms of engagement can be imagined (see, e.g., [Abbasi et al. [017] for examples in computer games). In our framework, the human's 's engagement is modeled with the threshold constraints over his/her expected utility, with the following rationale. If the utility value falls under a given satisfaction threshold, then the human will get bored playing, as he/she loses too much and believes he/she has no hope to win. On the other hand, if such value raises above another given threshold, then the human will get bored since he/she is winning too often.
Another application scenario for our framework is that of serious games [Dörner et al. 2016). whose purpose is to educate humans by asking them to perform tasks engagingly. If some tasks excessively hard for the actual human's capabilities, then the human will give up the training of the entire set of tasks, since he/she is sure that he/she will never be able to address them. On the other hand, if some tasks are excessively easy, the human will give up the training since he/she is sure that he/she can solve all remaining tasks. Serious games are used in many different fields, such as, e.g., military [DeFalco et al.) [2188). transportation [Rossetti et al.) [0033). urban planning (Poplin 2011] and healthcare [Wang et al. (0166), and can be modeled as general-sume games between a human learner and computer teacher Mayer 2012).
Original contributions. We study two-player sequential (i.e., extensive-form) games in which an artificial agent repeatedly plays against an unknown human opponent. We assume that the human has a fixed stochastic behavior and he/she does not learn over time. We do not make any structural assumption on the human's 's strategy, which requires the agent learning a probability distribution for each decision point of the human. While this is a crucial first step towards a more complex setting in which the human learns over time, the resulting model still presents several technical challenges that are worth to be investigated. First, we show how to derive, after each game repetition, a confidence region for the human's 's strategy such that his/her actual strategy stays within with high probability. We show that such region is characterized by a set of linear constraints defined over the sequence form strategy space. Notice that, during each game repetition, the agent only observes a partial sample of the human's 's strategy, made by the human's 's actions on the path in the game tree followed during play. By exploiting strong duality and the specific structure of the confidence region, we show that the thresholds constraints on the human's ' expected utility can be formulated as set of linear inequalities, whose cardinality is linear in the size of the game tree. In particular, these constraints describe a subspace of the agent's 's sequence-form strategy space such that, for every possible human's 's strategy in the confidence region, the human's 's expected utility is within the given thresholds. We also derive a linear program with linear number of constraints and variables to find the best agent's strategy satisfying the constraints. Then, we design an upper confidence bound algorithm, called COX-UCB and we prove that it suffers from a sublinear regret and guarantees that the aforementioned constraints are satisfied with high probability at every iteration. Finally, we empirically evaluate the convergence of our algorithm standard testbeds and show that bounds are asymptotically tight. All the omitted proofs are provided in Appendices A and
Related works. Our work is mainly related to opponent modeling, whose primary goal is to build
models describing the behavior of one or multiple opponents from past interactions. Many methods are known in the literature. Specifically, MMaling and Shapiro [2017] and Foerster el al. (018 propose method to infer the parameters of the opponents policies from the data collected during

---

past interactions. Instead, several other works propose methods that use beliefs over fine set of opponents' types distinguishing for their behavior: Albrecht and Ramamoorthy [2014] treat types as black-box mappings, Albrecht and Stone [217)] infer parameters for the types, |arrettt and Stone [2015) use deep learning to explicitly learn models, while He and Boyd-Graber [2016] do the same implicitly. These methods usually require huge amount of training data to be precise and adaptable to new opponents. In a recent work, [u et al. [2021) propose a eearning-to-exple deep framework for implicit opponent modeling and an adversarial training procedure to automatically generate opponents so as to reduce the data needed for training. An approach that has more common ground with ours is the one adopted by Ganzfried and Sandholm [011]. who propose a game sume-theoretic approach to develop a deviation based best-response algorithm. In particular, the work builds an opponent model based on the deviations between the opponent's strategy and a precomputed approximate equilibrium, and, then, computes a best response in real-time. The only works providing theoretical guarantees [Ganzfried and Sandholm 2013; Ganzfried and Sun 2018). which deal with safe opponent exploitation, ie., guaranteeing a certain agent's 's payoff in expectation, given any opponent's s strategy. Differently, in our setting, the goal is to guarantee certain human's 's expected utility.
2 Preliminaries
In this section, we review the basic concepts and definitions related to sequential games that we need in the rest of this work (see the book by (Shoham and Leyton-Brown (0088) for more details).
Extensive-form games. We focus on two-player extensive-form games (EFGs) with imperfect information in which an artificial agent faces a human opponent. We denote by i the agent player, while j is the human. Then, the set of players is P {c}. where we let P == [i,j] and e denotes a chance player that selects actions according to fixed known probabilities, representing exogenous stochasticity. An EFG is usually defined by means of game free, where H is the set of nodes of the tree and Z C H is the subset of terminal nodes, which are the leaves of the game tree. A node h E H is identified by the ordered list of actions encountered on the path from the root of the game tree to the node. Given a non-terminal node h E H \ Z, we let (h) E PU {c} be the unique player who acts at h and A(h) be the set of actions he/she has available. We let U; Uj : Z + R be the payoff functions of players and j. respectively. Moreover, we denote by Pe : H - [0, 1] the function assigning each node h H to the product of probabilities of chance moves the path from the root of the game tree to h. Imperfect information is encoded by using information sets (infosets for short). player i's infoset I groups nodes belonging to player i that are indistinguishable for him/her, that is, C H \ Z is such that P(h)= = P(k) = i and A(h)= = A(k) for any pair of nodes h, k E T. We let I be the set of player i's infosets, which define a partition of the set of player i's non-terminal nodes {h E H \ Z P(h)- = i}. Moreover, with slight abuse of notation, we let A(f) be the set of actions available at all the nodes in infoset 1 E I. Analogously, we define J as the set of player j's infosets, while, for any infoset J E J, we let A(J) be the set of actions available at nodes in J. We focus on games with perfect recall in which infosets are such that no player forgets information once acquired.
The sequence form of EFGs. The sequence form is compact way of representing EFGs with perfect recall (Von Stengel 1996; Koller et al. 1996). where the pure strategies of a player- specifying an action at each infoset of that player-are replaced by the concept of sequence. Any node h E Il defines a sequence o, (h) of player i, which is identified by the ordered list of player i's actions on the path from the root of the game tree to h. In perfect-recall EFGs, all the nodes belonging to an infoset I E I of player i define the same player i's sequence, which, by overloading notation, we denote by (I). Sequence (I) can be extended by appending any action E A(I) available at I at its end, obtaining another valid player i's sequence that we denote as a, (a). Then, the set of player i's sequences is Σ,, == (T)( T E I, a E A(T)) U (0), where 2 the empty sequence (defined by all the nodes such that player i never plays before them in the game tree). Analogously, we define Σ, == (J)(J)a | J E J,a E A(J)) U {e) as the set of all player j's sequences. Mixed strategies in the sequence form are specified by defining the realization probability of each sequence. A sequence-fore strategy of player i is denoted by vector E [0. 1) with æ[a;;] being the realization probability of sequence oi E Σ, To be well defined, a sequence-form strategy must
II this work, we denote vectors by bold symbols. Given a finite set S of dimension [S] = d, we denote by E || d-dimensional vector indexed over S, with v[s] being its component corresponding S.
3

---

satisfy set of linear constraints, ensuring that realization probabilities of sequences encode valid probability distribution over actions at each infoset. Formally, any x E [0, 1j18, must satisfy:
a x|0] = 1, and x[o,(1)) = Σ x[ox(1)a) II
(1)
aEA(1)
Constraints ① can be written as F, = f; where F; E (-1,0, and f: E {0. 1 are a suitably-defined matrix and vector, respectively (see [Von Stengel 1996] for their definitions). Analogously, we denote requence-form strategies of player j as vectors y E [0, 1| that satisfy the condition F j. which is defined by linear constraints analogous to Constraints ① For the ease of presentation, we let X == (0 E [o, 1| F.æ f:} and y == {y E [0, 1||5,| Ffy - f be the sets of all sequence-form strategies of players and j. respectively. Finally, given two strategies E X' and y E V, it is easy to check that player i's expected payoff can be written as the bilinear form x T U.y where U, E TR. [R, is player i's sequence- utility matrix, defined as:
U.] =
Σ
Pe(z)u:(z) Ya, E Ex, Vo, E Eg.
(3)
Analogously, the sequence-form utility matrix of player j is U, E ER and, thus, x T U,y his/her expected payoff given two sequence-form strategies æ E X' and E y
Additional notation. Given two sequences o; of E E, of player i, write o; E of denote that o; is a sub-sequence of a:: formally, this is the case whenever the ordered list of actions identified by a, is a prefix of that of of. Similarly, player j. Moreover, given a player i's sequence-form strategy x: E X and a player j's infoset J E J. we let (_,(J, æ)) be the probability of reaching given that player j plays so as to reach it and player i plays æ (also accounting for chance probabilities); formally p_j(J, Φ) == Enes x ofo; (H)...)))
notation σj [ o' for two sequences jj. o' E Σ, of
3 Exploiting opponents under utility constraints
We study settings in which the agent player repeatedly faces the human opponent in two-player EFG. Our goal is the design of agents that learn the strategy of the human so as to effectively exploit it, while at the same time guaranteeing that the human's 's expected utility remains under control during the entire repeated interaction 3) In the rest of this section, we formally introduce our problem and provide general overview of the approach we undertake tackle it.
We let T be the number of times the EFG is played. Player j plays according to the same sequence- form strategy y" E Y' at each iteration E [T]] This strategy is unknown to player i. On the other hand, at iteration f. player i selects and plays a strategy x E X. Then, at the end of the itcration, player i receives feedback a sequence of player j's actions of E Ej, which is defined by the path in the game tree followed during game playing that iteration (notice that of is made of actions sampled according to player j's strategy y In the following, for t E [T], we let HC be the history of feedbacks received by the agent player up iteration (included), namely H (a). of......... .f))
To ensure that player j's utility is kept under control during the repeated interaction, player must play strategies x' such that the resulting player j's expected utilities are within some given thresholds. The lower limit of the range ensures that the agent does not over-exploit the human. On the other hand, the upper limit of the range guarantees that the expected payoff of the human is not too high. Hormally we require x' E 2', where the subset X C X' is defined as follows:
Definition 1 ctnittyyconstraaieed Strategy Set). Let L E [T] and 8 (0, 1). Given a lower limit a E R and an upper limit 3 E R, we define the
strategy set X C X at iteration 1. as the set of player i's sequence-fore strategies x E X such that P (a x. UUY"" S B) > 1 8, with respect to the randomness of the history H11 of feedbacks observed by player i up to iteration t (included)
'The methodology that we propose in this paper can also be adapted to control the agent's expected utility, rather than the one of the human player.
'In this work, given n E N+ we denote by [n] the set (L....,n) n) of the first n natural numbers. "I the rest of this work, we make implicit the dependency of X from d, a, and B. as the values of these parameters will be clear from context.

---

After T' game repetitions, given the strategies x' E X' played by the agent player i during iterations t [T], we measure his/her performance by means the following notion of regret:
T Σ max
R
( (x') U EX
which represents how much player i would have gained in expectation by playing uillit-maximizing strategy in the utility-constrained strategy set X' rather than æ', each iteration E [7]. The goal that we pursue in the rest of this work is to achieve sublinear regret, that is R o(T), while at the same time guarantecing that the played strategies x' satisfy the constraints defined by the sets X².
Overview of our results. In what follows, give brief sketch of the approach adopt to tackle the problem. We propose a learning algorithm for the agent player i, which we call Constrained Opponent eXploitation with Upper Confidence Bounds (COX-UCB), It builds two components. The first one deals with the construction of the utility-conee culitt-constrained strategy set X at each iteration t e [2]. works by building a confidence region y C y for player j's strategy, using the history H' of feedbacks observed up the previous iteration - 1. This is such that the true (unknown) strategy y lies within y"-1 with probability at least Then, the utility- constt--cont strategy set 2 can be characterized by set of linear inequalities that exploits the structure of the confidence region y"-1 A detailed formal treatment of this first component is provided in Section 4 The second core component consists in rule to select the strategy x' E X to play each iteration E [7]. We propose an approach based on the optimism in face of uncertainty principle. More details on this second component can be found in Section 5 together with the regret bounds attained by the algorithm. We refer the reader Algorithm | for general sketch of our COX-UCB algorithm, where two alternative implementations of the procedure SELECTSTRATEGY y(-1) will be given in Algorithms and in Section
for some fixed confidence level 5 E (0. 1).
Algorithm 1 COX-UCB
1:
f f
2: while t < T do
3: Build confidence region y" from history of past feedbacks H -1 Use y'- to build the utility-constraing strategy X
> Subsection Subsection P. Section
4.1
4:
x' + SELECTSTRATEGY' (2' (X","""
6:
Play the game according to strategy x²
7:
Observe player j's sequence oj. obtained from the path in the game tree followed during play
H' 1 H' {a}}
9:
t ++++1
How to control the human's expected utility
In this section, we provide the formal details on the construction of the utility-oonstrained strategy set x' at each iteration & E [7'] (Definition 13. We split the section into two main parts:
shows how to use the history H' of feedbacks observed by player up to iteration / to derive a confidence region y C y for player j strategy y" such that y lies within ) with probability at least 8 for some fixed confidence E (0, 1):
Subsection 4.1
Subsection 4.2 describes how to exploit the confidence region y built using feedbacks observed up to iteration t to construct set of linear constraints that fully characterize sequence-form strategies in the
strategy set X at iteration t.
All the proofs omitted from this section are reported in Appendices and
4.1 Building a confidence region for the human's 's strategy
Let us recall that, each iteration /. E [T], player i observes player j's sequence of determined by selecting actions to play during the game according to the sequence-form strategy y". We build the desired probbbbtbbbblitty confidence region y by exploiting information provided by observed
5

---

sequences to derive. for each player j's infoset J E J, appropriate confidence intervals for the realization probabilities y y (J)a) of sequences (J)a terminating with an action (J) at J
The case of a single infoset. Before showing our general technique, it is useful to present the easier setting in which player j has a unique infoset, and, thus, his/her strategy is defined as a probability distribution p AlA, where, with abuse of notation, A denotes the finite set of actions available the infoset. In this case, player i observes actions a .....,,, a² E A sampled independently according to p. Then, a natural estimator for p is the empirical frequency of actions p' E AIAi, defined so that pa[a] == Er= 1fa" = a} for every a E A. By noticing that t p' is a random variable following a multinomial distribution with parameters and p. that is Ep' ~ .M(t;P) (t), the following lemma by Devroye 1983) can be used to derive the desired confidence intervals for the probabilities p(a]
Lemma (Lemma 3 by Devroye (. Let p E A and a² ,....,. a² E A be t actions sampled independently according to Then, for any 0 < 5 S eex ( (-4 [|/55,, it holds:
In (3/5) < 5
PP
Σ LEEA
p [a] -pla|
plal
2 1
1
By exploiting the fact that p AIAI, can refine the result in Lemma 1 by giving bounds that hold for each component of p separately (see Lemma 2 below). This additional step is crucial when building confidence intervals for realization probabilities y² [J,([)a] at infoset J in general.
Lemma 2.
Let p E A and ......'' at E A be actions sampled independently according to p.
Then, for any 0 < 5 < 3 exx (-4[A]5)), it holds:
IP
n aEd
p'la|
plal
S 2
5
In (3/0)
2 1 5.
Next, we generalize the approach described above to the general case of any infosets structure.
First, we introduce some useful random variables. For every iteration E [T], player j's infoset J E J. and action E A(J), we let O',,, a) = (V)a = of be a random variable that is equal to 1 if and only if player j played action
infoset during iteration t, while it is equal to 0 otherwise. It is easy to check that O'(J, a) follows a Bernoulli distribution with parameter (J. == y" (J)aa p²,((J), where, for the ease of presentation, we let (J= = (J](Ja x') be the contribution to the probability of reaching infoset J due to player i's strategy x' and chance prob- abilities, R The random variables O' (J. a) are instrumental for defining N' a) = Σ O (J.a), which represents the number of times is played at up iteration t. Intuitively, variables N (J, of infoset J E J play the same role as the random vector t p' in the single-infoset case.
We follow an approach analogous to that of the single-infoset case at each player j's infoset, and, then, put all the resulting confidence intervals together to define y", To do so, we need to circumvent the following issue: at each infoset J E J, the random variables (², a) for a E AJ) are not jointly distributed as a multinomial, preventing a direct application of Lemma [ We deal with this by adding fictitious action at each infoset, so that random variables NJJ, a) are multinomially distributed for each J E J. Then, the fictitious action can be easily factored out by using Lemma 2
Let (J) = A(J) U }ao} be the new action set at J E J, with ag denoting the fictitious action. For E [T]. we define O'(J, a.) = (J)a Z } as a random variable equal to 1 if and only if
'Let us remark that deriving yd is made considerably challenging by the fact that, at each E [T]. only the sequence of of actions actually played by player is observed. On the other hand, if player would be able to observe the actual pure strategy selected by player at I, the problem would admit much easier solution consisting in building a single confidence interval for player j's average strategy.
In this work, we denote by A 18! the (IS) - 1) -i-dimensional simplex indexed over the finite set S. Morcover, we denote by 1() the indicator function for the event enclosed in curly braces, while M(n; u) denotes a multinomial probability distribution, where n E N2 is the number of trials and v E 181 is a vector defining the probabilities of observing each element in the finite set S.
"In the rest of this work, we assume w.l.o.g. that (²) > for any and J. This is possible thanks to the fact that strategies x' selected by the algorithm proposed in Section always ensure that such conditions hold.

---

it is nor the case that a is played at J during iteration t (this also includes all the cases in which J not reached), and otherwise. Clearly, O' (J, a.) follows a Berouulli distribution with parameter (J, = 1 1-1--an A(E) p' Moreover, we let N (J, = -i=1 O' ao). Then, for each player j's infoset J J, we define n' NIAa(() for every a (J). By letting (J- - : Σ (_)(J), we have:
random vector such that n'j [a] = N (J,
1 [ = -
- (100
while is easy check that E (J, a.)] = conclude that nz' follows a multinomial distribution, circumventing our initial issue. Formally:
- EeE(J)) (J)a) As result, we
p- (J)y" n' ~ (t, E AlAo s.t. v|a] = 1 - (1)) E EaEA(S) y [J)(aa]]
if E A(J) if do
By exploiting this last observation and using Lemmas D and 2 we provide confidence intervals defined locally each infoset J I for the realization probabilities y" (J)) of sequences (J()) terminating with an action a E A(J) at J. By letting y' R 1a be such that:
(J)o, = (J,0)) 1p (J)
W J,Ya A()),
we have the following lemma:
Lemma 3. Let J E I be a player j's infoset. Then, for any 0 < 5 S {3exp(-4[A(])/5) it holds:
{ | - (J)os (EA(J)
5
In (3/6)
T
n
2 1
(J) t
Lemma 3 shows that one can use y"(o,(JJa) to estimate the realization probability ("[or[()) of some sequence (J)a, where y' (J)aa represents the observed frequency of action infoset J, adjusted by the average probability of reaching J due to other players, namely (J() Thus, yy generalizes the empirical frequency p' in the single-infoset case to the sequence-form setting. Moreover, Lemma 3 gives high-probability confidence intervals for probabilities y" [Jr(()a at every infoset E J, which used in the following theorem that gives us the desired high-probability confidence region )
Theorem 1. For every player iss infoset J E J. let 8 (0, 1) be such that the condition in Lemma 3 is satisfied and Eser 5, < 1. Then, TP (v" E e)²) 2 1 - 6, where = Eser 5, and
In (3/5,) y E :: v - [Jaa S 2p' 2p'
LJ e J. A(1)
yr
t
4.2 Constructing the utility-constrained strategy set
We show how to construct the utility- calltt-coostrained strategy set for some ô E (0. 1) and a, B E R by exploiting the high-probability confidence region y> (see Theorem []. Our approach is to force the condition that each æ in the utility wunitt-constrained strategy set must satisly with high probability (see Definition 1 for such condition) for every y E y²-1; formally, we require S x U,Y S B for all y y By definition of y this guarantees that such constraint holds also for y with probability at least 1 - 8. Formally, we define
x²
E X: max x6 T UU 5
A min xF UU 2 a
DE)
weyt-1
so that, for any X², the upper limit 3 and the lower limit are satisfied for every y E 31-1
7

---

In what follows, we characterize the set X' by means of a set of linear inequalities. We formulate the constrained maximization problem, i.e. maxyeyt- j.y, using the following linear program:
max x U s.t. y20
(3a)
F = fj
(3b)
y S y 1-1 e'1
(3c)
y y -²-
(3d)
where we let c²-l E IR be such that ('))( = 2 V In(3/55) for J E J and
a E A(J), for some 8, E (0, that satisfy the condition Lemma 3 and EJET oz <
Notice that, by recalling the definition of y in Equation (2) and that of y in Theorem
Constraints 3b (3c) and (3d) correctly encode the fact that y must belong to the set )
The dual of Problem 3 reads as: min bJ s.t. A UJ x, where
R((SH])xaEE is a vector of dual variables, while and A are suitably-defined vector and matrix, respectively. By strong duality, the optimal dual objective equates the optimal primal objective, and, thus, given any player i's strategy x E X, the condition maxyey1-1 x UU I 3 holds there exists a dual feasible solution u that satisfies the additional constraint that b u S B.
By following an analogous reasoning for mingey'- U yy. and letting E [(131+1)x2(E1 be vector of variables of the dual problem corresponding to its linear programming formulation (similar Problem B)), we state the following main result:
Theorem 2. Lert E [T] and å E (0,1). Given a E R and B E R, it holds:
X² -x { (co, u.) u. 2 0. B, A Auuus UU. wa
2a, -T STJSa
From Theorem 2] it follows that X' can be characterized by a polynomially-sized set of linear constraints, which achieves initial goal. Notice that, in general, the set X defined in Theorem 2 could be empty. This occurs when the linear program used to build X is unfeasible. In practice, this not an issue, since is always guaranteed be feasible for & large enough. A complete discussion on this point is deferred to Appendix
How to select the strategy to play
In this section, we provide the implementation of the procedure SELECTSTRATEGY )x-1) in Algorithm 1 To guarantee that COX-UCI attains sub-linear regret after T iterations, i.e., Rid = o(T) (with high probability), we adopt approach inspired from arm-selection strategies used in linear multi-armed bandit problems [Aurr 2002]. In particular, we propose one that uses upper confidence bounds, which is inspired by the Lin UCB algorithm [Abbasi-
al. 2011].
As first step, we need to ensure that the algorithm performs enough exploration during game playing. This is crucial to lower bound the probabilities (J) that appear in the bounds defining the set ye (see Theorem Db. and, ultimately, to obtain sub-linear regret. In particular, at each t [T]. the COX-UCB algorithm selects a strategy x² that belongs to the following subset X
x x: E x ala,(=)) 2 at Vz E Z},
where the a's are suitably-defined parameters that decrease with the iteration number 1
Notice that naïve way of adding exploration the algorithm would be to use e-greedy policy that plays the selected strategy x' X with prohability approach does not work our setting, as would result a violation the constraints on the human's 's expected utility. On the other hand, picking X assures that such constraints satisfied.
and random with prohability However, this

---

Algorithm Strategy selection of 1/-COX-UCB
Algorithm 2 Strategy selection of COX-UCB
1:
function SELSTRAT- UCBC' , with probability 1 do:
2:
I: function SELSTRAT-UCB((* )(-+)
3:
x² + argmax max UUy =c wEy
2: w' argmnax max x U.y
mERt DEyt-1
4: with probability & do:
3: return x²'
5: x' +- argmax Uyy me
6: return
The strategy selection mechanism implemented by COX-UCB is provided in Algorithm 2 It is based on the optimism in face of uncertainty principle, and, thus, it selects a strategy x' E X that maximizes player i's expected payoff x' U yy under the assumption that, for every æ E X', strategy y is an optimistic estimate of y taken from the confidence region y that is, y E y maximizes the same player i's expected payoff æ U.y The following theorem provides high-probabill sub-linear regret guarantee for COX- COX-UCB (its complete formal proof can be found in Appendix
Theorem 3. Let a' 1| Vin (In t+11 for every 1 E [T], where (0, 1), and let 5 E (0, The COX-UCB algorithm attains the following regret bound with probability at least - 6:
2nn 14 14-1
5 Ku. C (lo,,C(++2Tiin (1++VTITT)
Rd
S
27
where Ku, == ||0s| and C is a ciltubly-deiined constant.
Let us remark that to obtain sub-linear regret only the term 1/vlogt is required in the definition of a"; the other terms added that COX- -CCB needs to solve a which can be done efficiently by cutting-hedge solvers (see Section
to obtain analytical formula for the regret. Moreover, notice bilinear optimization problem at each iteration,
6 Experimental evaluation
We empirically evaluate the convergence of our COX-UCB algorithm on a standard testbed of Kuhn and Ledue poker games (Kuhn 2016]. We report here the evaluation on rank Kuhn poker (kuhn 7)
and rank 2 Leduc poker (leduc 2), while other experiments and details are deferred to Appendix D
6.1 Approximated version of the COX-UCB algorithm
The COX-UCB algorithm presented in Section 5 (Algorithm solves bilinear optimization problem at every iteration, with the optimization done over the whole utility-constrained strategy set. Furthermore, let us recall that such set directly built from the high-confidence region for the human's 's strategy, which is specified at time by an estimate y and bounds e'. Empirical evidence from early experiments showed that, despite having the same worst-case convergence rate, in practice the estimate y' converges much faster to y" than the bound et does to O. We propose a simple modification of COX-UCB, called th-approximated COX-UCB (Ú-COX-UCH) convergence of the strategy estimation. The only difference between COX-UCB and wi-COX-UCB is in the strategy selection procedure, specified in Algorithm This simple variation has a twofold effect the overall algorithm: (i) in some iterations it avoids solving the bilinear program, by solving much simpler linear program instead, and (ii) leverages the fast empiric convergence of y to converge faster. In the remaining part of this section, we empirically evaluate COX-UCB and al- Ji-CO--UCE for different values the parameter th.
exploiting the faster
6.2 Experimental results
Experimental setting. In order to compare the performances of COX-UCB with those of its approximated version, we consider three versions of vi-COX-UBB, respectively with & 0.5, = 0.7 and rb = 0.9. We evaluate the performances of the algorithms against 10 different randomly generated strategies for each game instance considered. For each strategy, we execute different algorithm runs. The values (a, 3) needed for the utility constraints are set to -0.3 and B = 0.3 in

---

10
Random
02
COX.UCR
(er) Uy
0-
14
-02
2
-10P
-10'
-1P
(b)
(C)
90-
Racdum
0.2
COX-UCD
R7-V/ V//12
40
AL-OO--CH
DOCOX-UCB
0-
2-
15
-0.2-
20
10
10F
-10F
105
(d)
(c)
(f)
Figure 1: Performances of COX-UCB in Kuhn poker with ranks (first row) and Ledue poker with ranks (second row). From left to right: player j's utility, cumulative regret, and cumulative regret divided by vt t.
all the experiments. We use Gurobi for solving bilinear optimization problems [Gurobi Optimization 2021]. As a baseline for comparisons, we use a random algorithm that, at each iteration f. E [T]] returns strategy randomly picked from the utility- constraiedd strategy set X For further details on the implementation of the algorithm and on the values of the syper-parameterd see Appendix D
Convergence results. Figure [ shows the results of the experiments kuhn and leduc_2 2. We observe that, in kulm_7, 7, the performances of COX-UCB and those of its approximated versions are comparable, thus showing that the rate of convergence of the opponent's 's strategy estimation plays a negligible role in this instance. On the other hand, the analysis of leduc_2 highlights a different behavior, suggesting that, in bigger game instances, the dimension of the confidence bound on the opponent's 's strategy and the rate with which such dimension reduces become crucial in order to achieve good performances. Furthermore, Figures La and Id show how the algorithm manages to maintain the expected utility of the opponent in the utility range [-0.3, 0.3]. On the other hand, we can see how the random algorithm, which plays a random strategy at each iteration, does indeed maintain the utility constraints satisfied (as they are below the threshold of 3 = 0.3), but it does not result sublinear regret R²,, as one can observe from Figures 1b and Ie| Interestingly, in Figures and the ratio between the regret and /t representing asymptotic dependence on t, converges to a constant as f increases, thus showing that our upper bound on the regret is tight.
7 Conclusions and future directions
In this paper, we studied, for the first time, the problem of designing artificial agents that learn how to exploit an unknown human opponent in an online fashion while, at the same time, guaranteeing that the human's 's expected utility remains bounded within some upper and lower thresholds. This framework finds application in several real-world buman-agen interactions, such repeated human- agent game playing in which the agent's goal is also to keep the human engaged in the repeated interaction, and human teaching by means of serious games. Our results hold up under the assumption that the human player adopts a fixed (unknown) stochastic strategy. This is a first crucial step towards more complex models of the human behavior. Nevertheless, even this basic case begets considerable technical challenges, which make the theoretical study of the problem interesting in its own, while also constituting a starting point for the analysis of more complex scenarios.
An interesting direction for future research is assuming a more complex human behavior, such as the case in which the human is learning over time. Another line of research is the enhancement of the scalability of the COX-UCE algorithm, so as to enable its application in real-world sequential games. Finally, it could be of general interest framing our algorithm in serious games scenarios, which have been largely ignored by the research community in artificial intelligence so far.
10

---

Acknowledgments and Disclosure of Funding
This work has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Market".
References
Amir Zaib Abbasi, Ding Hooi Ting, and Helmut Hlavacs. Engagement in games: developing an instrument measure consumer videogame engagement and its validation. International Journal of Computer Games Technology, 2017,
Yasin Abbasi-Yadkorf Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Proceedings of the conference on Neural Information Processing Systems (NeurIPS), volume 11, pages 23 2312-2320, 2011.
Stefano V. Albrecht and Subramanian Ramamoorthy. On convergence and optimality of best-response learning with policy types in multiagent systems. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pages 12-21, 2014.
Stefano V. Albrecht and Peter Stone. Reasoning about hypothetical agent behaviours and their parameters. In Proceedings of the Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 547-555, 2017.
Peter Auer. Using confidence bounds for exploitaiion-exxllraaiin trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Samuel Barrett and Peter Stone. Cooperating with unknown teammates in complex domains: A robot soccer case study of ad hoc teamwork. In Proceedings of the Conference on Artificial Intelligence (AAAT), pages 2010-2016, 2015.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424,, 2018.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456):885- 890, 2019.
Murray Camphell, J.Joseph Hoane, and Feng hsiung Hsu. 134(1):57-83, 2002.
Deep blue.
Artificial Intelligence,
Jeanine A. DeFalco, Jonathan Rowe, Lue Paquette, Vasiliki Georgoulas- Sherry, Keith Brawner, Bradford W. Mott, Ryan S. Baker, and James C. Lester. Detecting and addressing frustration in serious game for military training. International Journal of Artificial Intelligence Education, 1832 2018.
Lue Devroye. The equivalence of weak, strong and complete convergence in 11 for kernel density estimates. The Annals of Statistics, 11(3):896-900 904, 1983.
Ralf Dörner, Stefan Göbel, Wolfgang Effelsberg, and Josef Wiemeyer. Serious Games. Springer, 2016.
Attila Egri-Nagy and Antti Törmänen. The game not over go in the post-alphago era. Philosophies, 5(4):37, 2020.
yet-go
Jakob N. Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Picter Abbeel, and Igor Mordatch. Learning with opponent-learning awareness. In Proceedings of Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 122- 130, 2018
Sam Ganzfried and Tuomas Sandholm. Game theory-based opponent modeling in large imperfect- information games. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 533-540, 2011.
Sam Ganzfried and Tuomas Sandholm. Safe opponent exploitation. ACM Transaction on Economics and Computations, 3(2):8:1-8:2) 2015.
11

---

Sam Ganzfried and Qingyun Sun. Bayesian opponent exploitation in imperfect innerfecctiiformationn games. In AAAI Spring Symposia, 2018.
LLC Gurobi Optimization. Gurobi optimizer reference manual, 2021.
He He and Jordan Boyd-Graber. Opponent modeling in deep reinforcement learning. In Proceed-
ings of the International Conference Machine Learning (ICML), volume 48, pages 1804-1813, 2016.
Daphne Koller, Nimrod Megiddo, and Bernhard Von Stengel. Efficient computation of equilibria for extensive two-person games. Games and economic behavior, 14(2):247-259, 1996.
Harold W Kuhn. simplified two-person poker. Contributions to the Theory of Games (AM-24).
Volume I, pages 97-104. Princeton University Press, 2016.
Igor Mayer. Towards comprehensive methodology for the research and evaluation of serious games. Procedia Computer Science, 15:233-247, 2012.
Richard Mealing and Jonathan L. Shapiro. Opponent modeling by
and sequence prediction in simplified poker. IEÉE Transaction Compututational Intelligence Al Games, 9(1): 2017.
Alenka Poplin. Games and serious games in urban planning: study cases. In International Conference on Computational Science and Its Applications, pages 1-14. Springer, 2011.
Rosaldo JF Rossetti, João Emílio Almeida, Zafeiris Kokkinogenis, and Joel Gonçalves. Playing transportation seriously: Applications of serious games to artificial transportation systems. IEEE Intelligent Systems, 2874)1107-112, 2013.
Yoav Shoham and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, loannis Antonogiou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
Bernhard Von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-246, 1996.
Ryan Wang, Samuel DeMaria Jr, Andrew Goldberg, and Daniel Katz. A systematic review of serious games in training health care professionals. Simulation in Healthcare, 11(1):41-51, 2016.
Zhe Wu, Kai Li, Enmin Zhao, Hang Xu, Meng Zhang, Haobo Fu, Bo An, and Junliang Xing. L2E: learning exploit your opponent. CoRR, abs/2102.00381, 2021.
12


Reviews:
[{"review_id": "rAT9mSd1NTs", "reviewer": "Reviewer_gLaM", "summary": "The paper addresses the problem of maintaining the engagement of a human player when interacting with an AI agent within the context of a game. To do so, the paper proposes a method by which an AI agent learns online the behaviour of the human agent and acts in such a way to keep the reward of the human within some interval so as to ensure the game is neither too difficult nor too easy. Theoretical results are established that bound the probability that the reward lies within this interval as well as regret bounds for the performance of the AI agent.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I think the paper is well motivated and the problem undoubtedly has important applications. The authors have established nice results that bound the regret and violations. Overall, while I find the framework to be skillfully developed with interesting results, it feels to me to be poorly matched with the problem. Perhaps the authors could consider if there are applications within safety problems e.g. humans in the loop with assistive AI agents which require this sort of treatment (but without the zero-sum assumption).\n\n**Detailed Comments**\n\nIn the authors’ treatment of the problem, the human is assumed to have a fixed stochastic behaviour and not to learn over time. Given this, I find the setup somewhat incompatible with the aims of the paper and the problem. In particular, part of what I would think keeps a human engaged is progressive learning at the correct pace – including a second learner (with some means of modelling human behaviour e.g. a boundedly rational learner) seems like a requirement for this setting.\n\nThe paper also does not include experiments to test the main claim that the framework promotes prolonged engagement. This further makes it difficult to confidently understand if the modelling assumptions of the paper are suitable for the task at hand. While I understand performing experiments that involve human agents carries its difficulties, considering that the entire premise of the paper is that there is a need for algorithms that keeps humans engaged, it seems to me that human experiments should have been included.\n\nAdditionally, though the problem being targeted is one in which two interested players engage in a strategic interaction, the human is fixed the strategic interaction aspect is removed. This somewhat renders the exposition on extensive form games, which takes up an appreciable part of the paper somewhat redundant .\n\nThe theoretical analysis contains nice results, many of the key results are stated without accompanying explanation of their importance and relevance which undermines the analysis somewhat.\n\n**Questions**\n\n*Why can’t we just insert a term in the agent’s payoff which penalises it for taking actions that give the other agent a reward outside of a given range?\n\n*If the goal of the agent is to simply ensure that the human’s payoff lies within a certain range – why do we need to care about the zero-sum objective (i.e. why can’t we just maximise engagement)?\n\n*How does using a bandit method compare to tree search methods? Particularly in the way of scaling with the size of the tree.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think this is covered satisfactorily.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "nb4mHN2gNSM", "reviewer": "Reviewer_1aGH", "summary": "This work proposes EXO-UCB that achieves sublinear regret in 2-player games while ensuring an  opponent's utility remains in a specified interval. The motivation lies in applications such as serious games where human users need to be engaged while participating in some task with an AI and may drop off if their utility is too low/high. The contributions of the work are largely theoretical; the authors model the scenario as 2-player EFG and derive an algorithm that uses an \"engaging\" set of strategies based on an incrementally updated confidence interval over the opponent's (fixed) strategy. The experiments on Kuhn's poker validates that the algorithm works as expected, i.e., it achieves sublinear regret while guaranteeing the utility constraints.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Overall, the paper makes an interesting contribution towards better human-AI interaction. Given the assumptions and problem formulation, the derived results and subsequent EXO-UCB method appear sound. The generalization to infosets, i.e., the imperfect information setting, and its use to construct the engaging set was interesting to me. The experiments are sufficient to validate the overall methodology (at least up to the assumptions). \n\nOn the downside, it is difficult to judge the significance and potential impact of the work. The theoretical contributions appear divorced from the practical motivation (e.g., serious games). The assumptions in the problem formulation are unrealistic; in real settings, humans learn and do not have perfect recall. Furthermore, engaging a human is likely more complex than just introducing a bound over the obtained utilities. For example, in serious games or educational settings, a sense of accomplishment and progression is important to keep humans engaged. Potentially, the paper can be strengthened with references that support the constraint-based setup or by adding a discussion of other constraints can be formulated as bounds over obtained utility. \n\nA second concern is about the scalability of the approach. EXO-UCB requires repeatedly solving a billinear program. The authors claim that the method is computationally low cost but a short discussion on its computational properties (e.g., how the method scales with the size of the game tree) or experimental evidence would help support the claim. \n\nI believe this work is a good first step and I am supportive of the direction, but the paper appears preliminary at this stage. I am willing to adjust my score based on the authors' response. \n\n### Post-Response Comments.\nThank for your response and I have raised my score to a 6. I hope the authors will modify the paper as discussed in the response. A key concern is the disconnect between the motivation and the presented results, which is shared by a majority of the reviewers; I hope that the authors will amend their motivation accordingly. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, limitations and societal impact are discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "XUHAYoR1yEO", "reviewer": "Reviewer_zQhR", "summary": "\nThis paper addresses the problem of learning a strategy in an extensive-form game that maximizes utility gained, subject to constraints on that strategy.  These constraints are that the expected utility of the fixed opponent strategy be within some bounds with high probability on each iteration of the game. The authors proceed by precisely characterizing the region of the opponent's strategy space where the true opponent strategy lies, with high probability, given the observations of the opponents action choices thus far in the interaction.  This region is then used to generate a set of constraints on the agent's strategy, and finally, the agent's strategy is chosen to maximize its own utility, subject to the constraints and with under the optimistic assumption that the opponent will utilize also play to maximize the agent's utility (within the characterized strategy region). This strategy choice by the agent is shown to have sub-linear regret. Experimental results are provided for the domain of kuhn poker, showing that the proven bounds on opponent utility and regret of the agent utility hold in practice. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper addresses a fairly novel problem in an effective way. It is generally well-written and clear.  I found the setting well-motivated and the potential for impact of this problem formulation and approach good.  I think that the idea of engagement with players is one that has not seen enough focus thus far within the AI/ML communities, and this work does a good job of addressing it. The work appears to be high quality, and I enjoyed reading it and thinking about the problem they are addressing. \n\nComments: \n- I had a few minor concerns with the ways some previous work was missing that might be relevant to the paper at hand.  For example, while it is true that most efforts in extensive-form games (I am most familiar with poker) have focused on equilibrium strategies that ignore the opponent, there was a portion of the Annual Computer Poker Competition (I believe it was called the bankroll competition) where agents were evaluated based on how much they could exploit opponents, as opposed to just beating them.  I am not certain how many competitors specifically utilized other (i.e. non-equilibrium) strategies for this competition, but I know some work focused on opponent-modeling (for example N. Bard, et. al, Decision-theoretic Clustering of Strategies, AAMAS, 2015, and other work by Nolan Bard), and seems relevant for inclusion in the discussion in this paper. On a similar note, I would argue that the first major break-through in poker (for the first paragraph of the paper) was (M. Bowling, N. Burch, M. Johanson, O. Tammelin, Heads-up limit hold’em poker is solved, Science, 2015). \n- Another work I am familiar with that also seems related is (Davis, T., Waugh, K., & Bowling, M. Solving Large Extensive-Form Games with Strategy Constraints. AAAI, 2019).  In this they present a method for learning an optimal strategy for extensive form games subject to convex constraints.  This seems to be the same problem faced during the final step (strategy selection) in this paper, and its relevance should be addressed.  \n- The experimental results that were included in the paper are solid, but a bit brief.  I would have appreciated just a bit more exposition on how the opponent strategies were generated.  In the discussion of the results, it states that Figure 1a shows the expected utility convering to 0.3, 0.28, and 0.24, but I don't see how that is the case from the figure.  The blue and green lines appear to be converging to ~0.25 and ~0.2, while the orange and yellow lines are around ~-0.2  The results do clearly show how the utility stays within the specified bounds though.  \n- Without thinking about it too much, I might expect a random strategy (from the constrained X) to perform more in the middle of the utility bounds, while these results show that it is closer to the worst case for the agent, within the bounds.  I wonder why this occurs? \n\nMinor/Typos: \n- In Theorem 1 there is a reference to Theorem 3.  I think that this should be Lemma 3 instead. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A negative societal impact that I can imagine is that agents could get too good at engagement and humans might not ever want to stop playing against them, but this is not necessarily a new problem with this work, I think it applies to all kinds of computer games and interactions in general.  The possibility of positive engagement benefits in serious games, for example, are well worth the effort.  The authors don't address this and I would encourage them to think about mentioning it. \n", "review_text": "", "extra_scores": {"ethical_concerns": "No. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "PAUw_K39-K", "reviewer": "Reviewer_26mD", "summary": "The paper describes a novel approach for exploiting an unknown human opponent while ensuring that the human's expected payoff remains within a certain interval, thereby keeping them \"engaged.\" The setting is for 2-player zero-sum imperfect-information games where the public actions and private information of the human opponent agent are observed after each round.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I think the paper is pretty good overall. I have two major criticisms, and some minor comments.\n\nFirst, I don’t think the paper does a good job motivating the problem. What is a setting where we want to create an AI agent that can exploit a human opponent while still keeping the human “engaged”? The motivation seems very abstract and hypothetical. Why not just let the human play against other humans? Maybe some humans want to play against a very strong opponent? Why “exploit” the human at all, and why not just play a static strategy that is around the same level as the human? The paper needs to do a much better job motivating why this problem is interesting and provide at least one concrete example problem.\n\nI could think of one motivating scenario, though it is likely not what the authors had in mind. If one wanted to develop a poker bot to play online against humans (which is against the rules of the sites), then on the one hand they would like the bot to win as much as possible, but they do not want the humans and/or the site to detect that they are using a bot. So they want to ensure that they do not win so much as to arouse suspicion. \n\nThe second major issue is that the paper makes the significant assumption that the entire sequence of the opponent’s actions is observed. This is very unrealistic in imperfect-information games. For example, in poker, often the public actions of the opponents are observed, but not their private cards. (In some cases the hand goes to a “showdown” and opponent’s private cards are revealed, but frequently there is no showdown and they are not revealed). The authors are implicitly assuming that the opponents’ private information is observed at each iteration, since otherwise we would not what the sequence of the opponent’s information sets and actions are. If the authors want to use this model, they need to be honest about its limitations and be clear that it does not apply to typical imperfect-information games.\n\n \n\n15: be -> are\n29: quote outside period\n29: More in general -> More generally\n29: “humans are interested in repeatedly playing against an (artificial or human) opponent when they are sufficiently engaged in the competition” – citation for this?\n64: Citation Ganzfried & Sun ’18 doesn’t provide theoretical guarantees for safe opponent exploitation. It presents an exact opponent modeling approach for the setting with a Dirichlet prior and observed public actions but unobserved private information.\n\nSeems to be a contradiction:\n70: “We do not make any assumption on the human strategy”\nAppendix E.q: “In order to guarantee that the engaging set is non-empty at the beginning of the repeated interaction, we assume to have access to some prior information on the strategy employed by the human player, so as to reduce the initial uncertainty encoded by the confidence region.”\nWhat exactly is assumed about the human strategy?\n\n74: merit to be investigated -> merit investigation\n76: Notice that, -> Notice that\nFootnote 1: empiric -> empirical\nFootnote 1: “However, its empiric performance being very poor, we” -> “However, since its empirical performance is very poor, we:\n179: observed up the -> observed up to the\n310: cutting-hedge -> cutting-edge\n311: empiric -> empirical\nThe rules of Kuhn poker are never described, not even in the appendix.\n316: levels--, and -> levels—\n\nIn the experiments, it would be interesting to include a static Nash equilibrium strategy as a benchmark, and to see whether the opponent’s payoff falls within the “engagement” threshold range for it. It would also be interesting to include a full best response strategy to see how far outside of the engagement range the payoff is.\n\nIs there any precedent for the selection of the opponent strategies by using the ranges of entropy? If so, are there references for other works that use this approach? Or if not, can you elaborate on why this selection is interesting?\n\n351: startegy -> strategy\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't really see any major limitations or potential negative societal impact. \nThe only issue I can think of is that developers could use the algorithm to develop bots that play against humans illegally\non gaming websites that can avoid being easily detected.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses the problem of human engagement in repeated games, developing a novel algorithm that guarantees payoffs to the human can be kept within particular bounds over time with high probability. All reviewers agree that the problem is interesting and relevant. The topic is particularly important as the number of applications of human-computer interaction rise.

After the response there was some discussion. There are a few problems with the paper in its current form: (a) the problem is not well-motivated, (b) the contribution is mainly theoretical and not practically tied to human engagement since the "human strategy" is fixed, (c) the relationship between human engagement and utilities being within a certain range is not firmly backed by real evidence, and (d) the experimental results are not well-matched to the main problem being motivated by the paper (i.e. no evidence of actual increased human engagement).

The reviewers appreciated the thorough responses and satisfied by clarifying of technical points. Three of the four reviewers agreed post-response that (a) is easily fixed in a final copy. This is also true for (c) by adding (and perhaps discussing) the references mentioned in the responses more prominently. (b) and (d) are valid outstanding criticisms, which make the impact unclear at this point. But, a proper theoretical investigation on a fixed policy does act as an important stepping stone toward these eventual goals. Taking this into account, combined with the novelty and interest this paper could generate, the positives outweigh the shortcomings. Still, it is important to take all the critical feedback strongly into consideration when revising the paper.


Decision: Accept (Poster)