Exploiting Opponents under Utility Constraints in Sequential Games
Year: 2022

Abstract:
Recently, game-playing agents based on AI techniques have demonstrated superhuman 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.

heading: 1 Introduction
text: Algorithmic game theory and machine learning have recently contributed to groundbreaking achievements in artificial intelligence, leading to 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 et 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 learn 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. A direct effect of this methodology is that the resulting artificial agents do not ∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
adapt to the actual capabilities of humans, potentially leading to an impressive gap in performances compared to the case in 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 is 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-exploitation 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 Egri-Nagy and Törmänen [2020] sharply observe, it 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., 2017] for examples in computer games). In our framework, the human’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 are 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., 2018], transportation [Rossetti et al., 2013], urban planning [Poplin, 2011], and healthcare [Wang et al., 2016], and can be modeled as general-sum games between a human learner and a 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 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 strategy such that his/her actual strategy stays within it 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 strategy, made by the human’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 a 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 sequence-form strategy space such that, for every possible human’s strategy in the confidence region, the human’s expected utility is within the given thresholds. We also derive a linear program with a 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 on standard testbeds and show that our bounds are asymptotically tight. All the omitted proofs are provided in Appendices A, B, and C.
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, Mealing and Shapiro [2017] and Foerster et al. [2018] propose a 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 a fine set of opponents’ types distinguishing for their behavior: Albrecht and Ramamoorthy [2014] treat types as black-box mappings, Albrecht and Stone [2017] infer parameters for the types, Barrett 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, Wu et al. [2021] propose a learning-to-exploit 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 [2011], who propose a game-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 are [Ganzfried and Sandholm, 2015; Ganzfried and Sun, 2018], which deal with safe opponent exploitation, i.e., guaranteeing a certain agent’s payoff in expectation, given any opponent’s strategy. Differently, in our setting, the goal is to guarantee a certain human’s expected utility.

heading: 2 Preliminaries
text: 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 [2008] 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 c denotes a chance player that selects actions according to fixed known probabilities, representing exogenous stochasticity. An EFG is usually defined by means of a game tree, where H is the set of nodes of the tree and Z ⊆ H is the subset of terminal nodes, which are the leaves of the game tree. A node h ∈ 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 ∈ H \ Z, we let P (h) ∈ P ∪ {c} be the unique player who acts at h and A(h) be the set of actions he/she has available. We let ui, uj : Z → R be the payoff functions of players i and j, respectively. Moreover, we denote by pc : H → [0, 1] the function assigning each node h ∈ H to the product of probabilities of chance moves on the path from the root of the game tree to h. Imperfect information is encoded by using information sets (infosets for short). A player i’s infoset I groups nodes belonging to player i that are indistinguishable for him/her, that is, I ⊆ H \ Z is such that P (h) = P (k) = i and A(h) = A(k) for any pair of nodes h, k ∈ I . 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 ∈ H \ Z | P (h) = i}. Moreover, with a slight abuse of notation, we let A(I) be the set of actions available at all the nodes in infoset I ∈ I. Analogously, we define J as the set of player j’s infosets, while, for any infoset J ∈ 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 a 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 ∈ H defines a sequence σi(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 ∈ I of player i define the same player i’s sequence, which, by overloading notation, we denote by σi(I). Sequence σi(I) can be extended by appending any action a ∈ A(I) available at I at its end, obtaining another valid player i’s sequence that we denote as σi(I)a. Then, the set of player i’s sequences is Σi := {σi(I)a | I ∈ I, a ∈ A(I)} ∪ {∅}, where ∅ is 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(J)a | J ∈ J , a ∈ A(J)} ∪ {∅} 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-form strategy of player i is denoted by a vector x ∈ [0, 1]|Σi|, with x[σi] being the realization probability of sequence σi ∈ Σi.2 To be well defined, a sequence-form strategy must
2In this work, we denote vectors by bold symbols. Given a finite set S of dimension |S| = d, we denote by v ∈ R|S| a d-dimensional vector indexed over S, with v[s] being its component corresponding to s ∈ S.
satisfy a set of linear constraints, ensuring that realization probabilities of sequences encode a valid probability distribution over actions at each infoset. Formally, any x ∈ [0, 1]|Σi| must satisfy:
x[∅] = 1, and x[σi(I)] = ∑
a∈A(I)
x[σi(I)a] ∀I ∈ I. (1)
Constraints (1) can be written as F ix = f i, where F i ∈ {−1, 0, 1}(|I|+1)×|Σi| and f i ∈ {0, 1}|I|+1 are a suitably-defined matrix and vector, respectively (see [Von Stengel, 1996] for their definitions). Analogously, we denote sequence-form strategies of player j as vectors y ∈ [0, 1]|Σj | that satisfy the condition F jy = f j , which is defined by linear constraints analogous to Constraints (1). For the ease of presentation, we let X := { x ∈ [0, 1]|Σi| | F ix = f i } and Y := { y ∈ [0, 1]|Σj | | F jy = f j } be the sets of all sequence-form strategies of players i and j, respectively. Finally, given two strategies x ∈ X and y ∈ Y , it is easy to check that player i’s expected payoff can be written as the bilinear form x>U iy, where U i ∈ R|Σi|×|Σj | is player i’s sequence-form utility matrix, defined as:
U i[σi, σj ] := ∑
z∈Z:σi(z)=σi∧σj(z)=σj
pc(z)ui(z) ∀σi ∈ Σi,∀σj ∈ Σj .
Analogously, the sequence-form utility matrix of player j is U j ∈ R|Σi|×|Σj |, and, thus, x>U jy is his/her expected payoff given two sequence-form strategies x ∈ X and y ∈ Y .
Additional notation. Given two sequences σi, σ′i ∈ Σi of player i, we write σi v σ′i to denote that σi is a sub-sequence of σ′i; formally, this is the case whenever the ordered list of actions identified by σi is a prefix of that of σ′i. Similarly, we use notation σj v σ′j for two sequences σj , σ′j ∈ Σj of player j. Moreover, given a player i’s sequence-form strategy x ∈ X and a player j’s infoset J ∈ J , we let ρ−j(J,x) be the probability of reaching J given that player j plays so as to reach it and player i plays x (also accounting for chance probabilities); formally ρ−j(J,x) := ∑ h∈J x[σi(h)]pc(h).

heading: 3 Exploiting opponents under utility constraints
text: We study settings in which the agent player i repeatedly faces the human opponent j in a 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 expected utility remains under control during the entire repeated interaction.3 In the rest of this section, we formally introduce our problem and provide a general overview of the approach we undertake to tackle it.
We let T be the number of times the EFG is played. Player j plays according to the same sequenceform strategy y∗ ∈ Y at each iteration t ∈ [T ].4 This strategy is unknown to player i. On the other hand, at iteration t, player i selects and plays a strategy xt ∈ X . Then, at the end of the iteration, player i receives as feedback a sequence of player j’s actions σtj ∈ Σj , which is defined by the path in the game tree followed during game playing at that iteration (notice that σtj is made of actions sampled according to player j’s strategy y∗). In the following, for t ∈ [T ], we letHt be the history of feedbacks received by the agent player i up to iteration t (included), namelyHt := ( σ1j , σ 2 j , . . . σ t j ) .
To ensure that player j’s utility is kept under control during the repeated interaction, player i must play strategies xt 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.Formally, we require xt ∈ X t, where the subset X t ⊆ X is defined as follows: Definition 1 (Utility-constrained Strategy Set). Let t ∈ [T ] and δ ∈ (0, 1). Given a lower limit α ∈ R and an upper limit β ∈ R, we define the utility-constrained strategy set X t ⊆ X at iteration t as the set of player i’s sequence-form strategies x ∈ X such that P ( α ≤ x>U jy∗ ≤ β ) ≥ 1− δ, with respect to the randomness of the historyHt−1 of feedbacks observed by player i up to iteration t− 1 (included).5
3The 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.
4In this work, given n ∈ N+ we denote by [n] the set {1, . . . , n} of the first n natural numbers. 5In the rest of this work, we make implicit the dependency of X t from δ, α, and β, as the values of these
parameters will be clear from context.
After T game repetitions, given the strategies xt ∈ X t played by the agent player i during iterations t ∈ [T ], we measure his/her performance by means of the following notion of regret:
RT := T∑ t=1 [ max x∗∈X t (x∗) > U iy ∗ − ( xt )> U iy ∗ ] ,
which represents how much player iwould have gained in expectation by playing a utility-maximizing strategy in the utility-constrained strategy set X t rather than xt, at each iteration t ∈ [T ]. The goal that we pursue in the rest of this work is to achieve sublinear regret, that is RT = o(T ), while at the same time guaranteeing that the played strategies xt satisfy the constraints defined by the sets X t.
Overview of our results. In what follows, we give a brief sketch of the approach we 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 on two core components. The first one deals with the construction of the utility-constrained strategy set X t at each iteration t ∈ [T ]. It works by building a confidence region Yt−1 ⊆ Y for player j’s strategy, using the history Ht−1 of feedbacks observed up the previous iteration t − 1. This is such that the true (unknown) strategy y∗ lies within Yt−1 with probability at least 1− δ, for some fixed confidence level δ ∈ (0, 1). Then, the utility-constrained strategy set X t can be characterized by a set of linear inequalities that exploits the structure of the confidence region Yt−1. A detailed formal treatment of this first component is provided in Section 4. The second core component consists in a rule to select the strategy xt ∈ X t to play at each iteration t ∈ [T ]. 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 to Algorithm 1 for a general sketch of our COX-UCB algorithm, where two alternative implementations of the procedure SELECTSTRATEGY(X t,Yt−1) will be given in Algorithms 2 and 3 in Section 5.
Algorithm 1 COX-UCB 1: t← 1 2: while t ≤ T do 3: Build confidence region Yt−1 from history of past feedbacksHt−1 . Subsection 4.1 4: Use Yt−1 to build the utility-constrained strategy set X t . Subsection 4.2 5: xt ← SELECTSTRATEGY(X t,Yt−1) . Section 5 6: Play the game according to strategy xt
7: Observe player j’s sequence σtj , obtained from the path in the game tree followed during play 8: Ht ← Ht−1 ∪ {σtj} 9: t← t+ 1

heading: 4 How to control the human’s expected utility
text: In this section, we provide the formal details on the construction of the utility-constrained strategy set X t at each iteration t ∈ [T ] (Definition 1). We split the section into two main parts:
• Subsection 4.1 shows how to use the history Ht of feedbacks observed by player i up to iteration t to derive a confidence region Yt ⊆ Y for player j’s strategy y∗, such that y∗ lies within Yt with probability at least 1− δ for some fixed confidence δ ∈ (0, 1); • Subsection 4.2 describes how to exploit the confidence region Yt−1 built using feedbacks
observed up to iteration t− 1 to construct a set of linear constraints that fully characterize sequence-form strategies in the utility-constrained strategy set X t at iteration t.
All the proofs omitted from this section are reported in Appendices A and B.

heading: 4.1 Building a confidence region for the human’s strategy
text: Let us recall that, at each iteration t ∈ [T ], player i observes a player j’s sequence σtj determined by selecting actions to play during the game according to the sequence-form strategy y∗. We build the desired high-probability confidence region Yt by exploiting information provided by observed
sequences to derive, for each player j’s infoset J ∈ J , appropriate confidence intervals for the realization probabilities y∗[σj(J)a] of sequences σj(J)a terminating with an action a ∈ A(J) at J .6
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 ∈ ∆|A|, where, with an abuse of notation, A denotes the finite set of actions available at the infoset. In this case, player i observes t actions a1, . . . , at ∈ A sampled independently according to p. Then, a natural estimator for p is the empirical frequency of actions pt ∈ ∆|A|, defined so that pt[a] := 1t ∑t τ=1 1{aτ = a} for every a ∈ A. By noticing that tpt is a random variable following a multinomial distribution with parameters t and p, that is tpt ∼ M(t;p), the following lemma by Devroye [1983] can be used to derive the desired confidence intervals for the probabilities p[a].7
Lemma 1 (Lemma 3 by Devroye [1983]). Let p ∈ ∆|A| and a1, . . . , at ∈ A be t actions sampled independently according to p. Then, for any 0 < δ ≤ 3 exp (−4|A|/5), it holds:
P (∑ a∈A ∣∣∣pt[a]− p[a]∣∣∣ ≤ 5√ ln (3/δ) t ) ≥ 1− δ.
By exploiting the fact that p ∈ ∆|A|, we 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(J)a] at infoset J in general.
Lemma 2. Let p ∈ ∆|A| and a1, . . . , at ∈ A be t actions sampled independently according to p. Then, for any 0 < δ ≤ 3 exp (−4|A|/5), it holds:
P (⋂ a∈A {∣∣∣pt[a]− p[a]∣∣∣ ≤ 5 2 √ ln (3/δ) t }) ≥ 1− δ.
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 t ∈ [T ], player j’s infoset J ∈ J , and action a ∈ A(J), we let Ot(J, a) := I { σj(J)a v σtj } be a random variable that is equal to 1 if and only if player j played action a at infoset J during iteration t, while it is equal to 0 otherwise. It is easy to check that Ot(J, a) follows a Bernoulli distribution with parameter pt(J, a) := y∗[σj(J)a] ρ t −j(J), where, for the ease of presentation, we let ρ t −j(J) := ρ−j(J,x
t) be the contribution to the probability of reaching infoset J due to player i’s strategy xt and chance probabilities.8 The random variables Ot(J, a) are instrumental for defining N t(J, a) := ∑t τ=1O
τ (J, a), which represents the number of times a is played at J up to iteration t. Intuitively, variables N t(J, a) of infoset J ∈ J play the same role as the random vector tpt 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 Yt. To do so, we need to circumvent the following issue: at each infoset J ∈ J , the random variables N t(J, a) for a ∈ A(J) are not jointly distributed as a multinomial, preventing a direct application of Lemma 1. We deal with this by adding a fictitious action at each infoset, so that random variables N t(J, a) are multinomially distributed for each J ∈ J . Then, the fictitious action can be easily factored out by using Lemma 2. Let A (J) := A(J) ∪ {a } be the new action set at J ∈ J , with a denoting the fictitious action. For t ∈ [T ], we define Ot(J, a ) := 1 { σj(J)a 6v σtj } as a random variable equal to 1 if and only if
6Let us remark that deriving Yt is made considerably challenging by the fact that, at each t ∈ [T ], only the sequence σtj of actions actually played by player j is observed. On the other hand, if player i would be able to observe the actual pure strategy selected by player j at t, the problem would admit a much easier solution consisting in building a single confidence interval for player j’s average strategy.
7In this work, we denote by ∆|S| the (|S| − 1)-dimensional simplex indexed over the finite set S. Moreover, we denote by 1{·} the indicator function for the event enclosed in curly braces, while M(n;v) denotes a multinomial probability distribution, where n ∈ N+ is the number of trials and v ∈ ∆|S| is a vector defining the probabilities of observing each element in the finite set S.
8In the rest of this work, we assume w.l.o.g. that ρt−j(J) > 0 for any t and J . This is possible thanks to the fact that strategies xt selected by the algorithm proposed in Section 5 always ensure that such conditions hold.
it is not the case that a is played at J during iteration t (this also includes all the cases in which J is not reached), and 0 otherwise. Clearly, Ot(J, a ) follows a Bernoulli distribution with parameter pt(J, a ) := 1− ∑ a∈A(J) p t(J, a). Moreover, we let N t(J, a ) := ∑t τ=1O
τ (J, a ). Then, for each player j’s infoset J ∈ J , we define ntJ ∈ N|A (J)| as a random vector such that ntJ [a] := N t(J, a) for every a ∈ A (J). By letting ρ̄t−j(J) := 1t ∑t τ=1 ρ τ −j(J), we have:
E [ N t(J, a) ] = t∑ τ=1 E [Oτ (J, a)] = y∗[σj(J)a] t∑ τ=1 ρτ−j(J) = t ρ̄ t −j(J)y ∗[σj(J)a],
while it is easy to check that E [N t(J, a )] = t − t ρ̄t−j(J) ∑ a∈A(J) y
∗[σj(J)a]. As a result, we conclude that ntJ follows a multinomial distribution, circumventing our initial issue. Formally:
ntJ ∼M (t,v) ,v ∈ ∆|A (J)| s.t. v[a] = {
ρ̄t−j(J)y ∗[σj(J)a] if a ∈ A(J) 1− ρ̄t−j(J) ∑ a∈A(J) y ∗[σj(J)a] if a = a .
By exploiting this last observation and using Lemmas 1 and 2, we provide confidence intervals defined locally at each infoset J ∈ J for the realization probabilities y∗[σj(J)a] of sequences σj(J)a terminating with an action a ∈ A(J) at J . By letting yt ∈ R|Σj | be such that:
yt[σj(J)a] := N t(J, a)
tρ̄t−j(J) ∀J ∈ J ,∀a ∈ A(J), (2)
we have the following lemma:
Lemma 3. Let J ∈ J be a player j’s infoset. Then, for any 0 < δ ≤ 3 exp(−4|A(J)|/5) it holds:
P  ⋂ a∈A(J) {∣∣∣yt[σj(J)a]− y∗[σj(J)a]∣∣∣ ≤ 5 2ρ̄t−j(J) √ ln (3/δ) t } ≥ 1− δ. Lemma 3 shows that one can use yt[σj(J)a] to estimate the realization probability y∗[σj(J)a] of some sequence σj(J)a, where yt[σj(J)a] represents the observed frequency of action a at infoset J , adjusted by the average probability of reaching J due to other players, namely ρ̄t(J). Thus, yt generalizes the empirical frequency pt in the single-infoset case to the sequence-form setting. Moreover, Lemma 3 gives high-probability confidence intervals for probabilities y∗[σj(J)a] at every infoset J ∈ J , which is used in the following theorem that gives us the desired high-probability confidence region Yt. Theorem 1. For every player j’s infoset J ∈ J , let δJ ∈ (0, 1) be such that the condition in Lemma 3 is satisfied and ∑ J∈J δJ < 1. Then, P (y∗ ∈ Yt) ≥ 1− δ, where δ := ∑ J∈J δJ and
Yt := { y ∈ Y : ∣∣∣yt[σj(J)a]− y∗[σj(J)a]∣∣∣ ≤ 5 2ρ̄t−j(J) √ ln (3/δJ) t ∀J ∈ J ,∀a ∈ A(J) } .

heading: 4.2 Constructing the utility-constrained strategy set
text: We show how to construct the utility-constrained strategy setX t—for some δ ∈ (0, 1) and α, β ∈ R— by exploiting the high-probability confidence region Yt−1 (see Theorem 1). Our approach is to force the condition that each x in the utility-constrained strategy set must satisfy with high probability (see Definition 1 for such condition) for every y ∈ Yt−1; formally, we require α ≤ x>U jy ≤ β for all y ∈ Yt. By definition of Yt−1, this guarantees that such constraint holds also for y∗ with probability at least 1− δ. Formally, we define
X t := { x ∈ X : max
y∈Yt−1 x>U jy ≤ β ∧ min y∈Yt−1 x>U jy ≥ α
} ,
so that, for any x ∈ X t, the upper limit β and the lower limit α are satisfied for every y ∈ Yt−1.
In what follows, we characterize the set X t by means of a set of linear inequalities. We formulate the constrained maximization problem, i.e., maxy∈Yt−1 x>U jy, using the following linear program:
max y≥0
x>U jy s.t. (3a)
F jy = f j (3b) y ≤ yt−1 + t−1 (3c) y ≥ yt−1 − t−1, (3d)
where we let t−1 ∈ R|Σj |+ be such that t−1[σj(J)a] := 52ρ̄t−j(J) √ ln(3/δJ ) t for J ∈ J and
a ∈ A(J), for some δJ ∈ (0, 1) that satisfy the condition in Lemma 3 and ∑ J∈J δJ ≤ δ. Notice that, by recalling the definition of yt−1 in Equation (2) and that of Yt−1 in Theorem 1, Constraints (3b), (3c), and (3d) correctly encode the fact that y must belong to the set Yt−1. The dual of Problem (3) reads as: minu≥0 b>u s.t. A>u ≥ U>j x, where u ∈ R(|J |+1)×2|Σj | is a vector of dual variables, while b 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 ∈ X , the condition maxy∈Yt−1 x>U jy ≤ β holds if there exists a dual feasible solution u that satisfies the additional constraint that b>u ≤ β. By following an analogous reasoning for miny∈Yt−1 x>U jy, and letting ω ∈ R(|J |+1)×2|Σj | be a vector of variables of the dual problem corresponding to its linear programming formulation (similar to Problem (3)), we state the following main result:
Theorem 2. Let t ∈ [T ] and δ ∈ (0, 1). Given α ∈ R and β ∈ R, it holds:
X t = X ∩ { (x,u,ω) : u,ω ≥ 0, b>u ≤ β, A>u ≥ U>j x, −b>ω ≥ α, −A>ω ≤ U>j x } .
From Theorem 2, it follows that X t can be characterized by a polynomially-sized set of linear constraints, which achieves our initial goal. Notice that, in general, the set X t defined in Theorem 2 could be empty. This occurs when the linear program used to build X t is unfeasible. In practice, this is not an issue, since it is always guaranteed to be feasible for t large enough. A complete discussion on this point is deferred to Appendix B.

heading: 5 How to select the strategy to play
text: In this section, we provide the implementation of the procedure SELECTSTRATEGY(X t,Yt−1) in Algorithm 1. To guarantee that COX-UCB attains sub-linear regret after T iterations, i.e., RT = o(T ) (with high probability), we adopt an approach inspired from arm-selection strategies used in linear multi-armed bandit problems [Auer, 2002]. In particular, we propose one that uses upper confidence bounds, which is inspired by the LinUCB algorithm [Abbasi-Yadkori et al., 2011].
As a first step, we need to ensure that the algorithm performs enough exploration during game playing. This is crucial to lower bound the probabilities ρ̄t−j(J) that appear in the bounds defining the set Yt (see Theorem 1), and, ultimately, to obtain sub-linear regret. In particular, at each t ∈ [T ], the COX-UCB algorithm selects a strategy xt that belongs to the following subset of X t:
X̃ t := { x ∈ X t : x[σi(z)] ≥ αt ∀z ∈ Z } ,
where the αts are suitably-defined parameters that decrease with the iteration number t.9
9Notice that a naïve way of adding exploration to the algorithm would be to use an -greedy policy that plays the selected strategy xt ∈ X t with probability 1− and a random one with probability . However, this approach does not work in our setting, as it would result in a violation of the constraints on the human’s expected utility. On the other hand, picking x ∈ X̃ t assures that such constraints are satisfied.
Algorithm 2 Strategy selection of COX-UCB 1: function SELSTRAT-UCB(X t,Yt−1) 2: xt ← argmax
x∈X̃ t max y∈Yt−1 x>U iy
3: return xt
Algorithm 3 Strategy selection of ψ-COX-UCB 1: function SELSTRAT-ψ-UCB(X t,Yt−1) 2: with probability 1− ψ do: 3: xt ← argmax
x∈X̃ t max y∈Yt−1 x>U iy
4: with probability ψ do: 5: xt ← argmax
x∈X̃ t x>U iy t−1
6: return xt
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 xt ∈ X̃ t that maximizes player i’s expected payoff x>U iy under the assumption that, for every x ∈ X̃ t, strategy y is an optimistic estimate of y∗ taken from the confidence region Yt−1, that is, y ∈ Yt−1 maximizes the same player i’s expected payoff x>U iy. The following theorem provides a high-probability sub-linear regret guarantee for COX-UCB (its complete formal proof can be found in Appendix C).
Theorem 3. Let αt := η 2 ln 2 t+ln t+1√ ln t (ln t+1)2 for every t ∈ [T ], where η ∈ (0, 1), and let δ ∈ (0, 1). The COX-UCB algorithm attains the following regret bound with probability at least 1− δ:
RT ≤ 5 2η KUi C
( 1 + 2 √ T lnT ) ,
where KUi := ||U i||∞ and C is a suitably-defined constant. Let us remark that to obtain sub-linear regret only the term 1/ √
log t is required in the definition of αt; the other terms are added so as to obtain an analytical formula for the regret. Moreover, notice that COX-UCB needs to solve a linearly-constrained bilinear optimization problem at each iteration, which can be done efficiently by cutting-hedge solvers (see Section 6).

heading: 6 Experimental evaluation
text: We empirically evaluate the convergence of our COX-UCB algorithm on a standard testbed of Kuhn and Leduc poker games [Kuhn, 2016]. We report here the evaluation on rank 7 Kuhn poker (kuhn_7) and rank 2 Leduc poker (leduc_2), while other experiments and details are deferred to Appendix D.

heading: 6.1 Approximated version of the COX-UCB algorithm
text: The COX-UCB algorithm presented in Section 5 (Algorithm 2) solves a bilinear optimization problem at every iteration, with the optimization done over the whole utility-constrained strategy set. Furthermore, let us recall that such set is directly built from the high-confidence region for the human’s strategy, which is specified at time t by an estimate yt and bounds t. Empirical evidence from early experiments showed that, despite having the same worst-case convergence rate, in practice the estimate yt converges much faster to y∗ than the bound t does to 0. We propose a simple modification of COX-UCB, called ψ-approximated COX-UCB (ψ-COX-UCB), exploiting the faster convergence of the strategy estimation. The only difference between COX-UCB and ψ-COX-UCB is in the strategy selection procedure, as specified in Algorithm 3. This simple variation has a twofold effect on the overall algorithm: (i) in some iterations it avoids solving the bilinear program, by solving a much simpler linear program instead, and (ii) it leverages the fast empiric convergence of yt to converge faster. In the remaining part of this section, we empirically evaluate COX-UCB and ψ-COX-UCB for different values of the parameter ψ.

heading: 6.2 Experimental results
text: Experimental setting. In order to compare the performances of COX-UCB with those of its approximated version, we consider three versions of ψ-COX-UCB, respectively with ψ = 0.5, ψ = 0.7 and ψ = 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 5 different algorithm runs. The values (α, β) needed for the utility constraints are set to α = −0.3 and β = 0.3 in
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 t ∈ [T ], returns a strategy randomly picked from the utility-constrained strategy set X t. For further details on the implementation of the algorithm and on the values of the hyper-parameters, see Appendix D.
Convergence results. Figure 1 shows the results of the experiments on kuhn_7 and leduc_2. We observe that, in kuhn_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 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 strategy and the rate with which such dimension reduces become crucial in order to achieve good performances. Furthermore, Figures 1a and 1d 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 β = 0.3), but it does not result in sublinear regret RT , as one can observe from Figures 1b and 1e. Interestingly, in Figures 1c and 1f the ratio between the regret and √ t ln t, representing its asymptotic dependence on t, converges to a constant as t increases, thus showing that our upper bound on the regret is tight.

heading: 7 Conclusions and future directions
text: 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 expected utility remains bounded within some upper and lower thresholds. This framework finds application in several real-world human-agent interactions, such as repeated humanagent 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-UCB 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.
Acknowledgments and Disclosure of Funding
This work has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Market”.

Review summaries:
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.

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. 

 This 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.