Temporal Induced Self-Play for Stochastic Bayesian Games

1 Introduction

Many real-world problems involve multiple decision-makers interacting strategically. Over the years, a significant amount of work has focused on building game models for these problems and designing computationally efficient algorithms to solve the games [Serrino et al., 2019; Nguyen et al., 2019]. While Nash equilibrium (NE) is a well-accepted solution concept, the players' behavior prescribed by an NE can be irrational off the equilibrium path: one player can threaten to play a suboptimal action in a future decision point to convince the other players that they would not gain from unilateral deviation. Such "non-credible threats" restrict the practical applicability of these strategies as in the real world, one may make mistakes unexpectedly, and it is hard to enforce such threats. Thus it is important to find strategy profiles such that each player's strategy is close to optimal (in expectation) from any point onward given the other players' strategies.

∗Equal Contribution

To find such strategy profiles, researchers have proposed equilibrium refinement concepts such as subgame perfect equilibrium and perfect Bayesian equilibrium (PBE) [Cho and Kreps, 1987] and studied the computational complexity [An et al., 2011; Etessami et al., 2014; Hansen and Lund, 2018]. However, existing methods for computing refined equilibria have limited scalability and often require full access to the game environment, thus can hardly apply to complex games and real-world problems (as detailed in Section 2). On the other hand, deep reinforcement learning (RL) has shown great promise in complex sequential decision-making problems for single-agent and multi-agent settings [Mnih et al., 2015; Silver et al., 2018]. Deep RL leverages a compact representation of the game's state and the players' action space, making it possible to handle large games that are intractable for non-learning-based methods. Despite the promise, to our knowledge, no prior work has applied deep RL to equilibrium refinements.

In this paper, we focus on two-player stochastic Bayesian games with finite horizon as they can be used to model various long-term strategic interactions with private information [Albrecht and Ramamoorthy, 2013]. We propose Temporal-Induced Self-Play (TISP), the first RL-based framework to find strategy profiles with decent performances from any decision point onward. There are several crucial challenges in using RL for this task. First, in these games, a player's action at a decision point should be dependent on the entire history of states and joint actions. As the number of histories grows exponentially, a tabular approach that enumerates all the histories is intractable. Although recurrent neural networks (RNNs) can be used to encode the history, RNNs are typically brittle in training and often fail to capture long-term dependency in complex games. Second, using standard RL algorithms with self-play suffers from limited exploration. Hence, it is extremely hard to improve the performance on rarely visited decision points. Our framework TISP tackles these two challenges jointly. We use a beliefbased representation to address the first challenge, so that the policy representation remains constant in size regardless of the number of rounds. Besides, we use backward induction to ensure exploration in training. TISP also uses nonparametric approximation in the belief space. Building upon TISP, we design TISP-PG approach that uses policy gradient (PG) for policy learning. TISP can also be combined with other game-solving techniques such as counterfactual regret minimization (CFR) [Zinkevich et al., 2007]. Further, we prove that TISP-based algorithms can find approximate PBE in zero-sum stochastic Bayesian games with onesided incomplete information and finite horizon. We evaluate TISP-based algorithms in different games. We first test them in finitely repeated security games with unknown attacker types whose PBE can be approximated through mathematical programming (MP) under certain conditions [Nguyen et al., 2019]. Results show that our algorithms can scale to larger games and apply to more general game settings, and the solution quality is much better than other learning-based approaches. We also test the algorithms in a two-step matrix game with a closed-form PBE. Our algorithms can find close-to-equilibrium strategies. Lastly, we test the algorithms in a grid-world game, and the experimental results show that TISP-PG performs significantly better than other methods.

2 RelatedWork

The study of equilibrium refinements is not new in economics [Kreps and Wilson, 1982]. In addition to the backward induction method for perfect information games, mathematical programming (MP)-based methods [Nguyen et al., 2019; Farina and Gatti, 2017; Miltersen and Sørensen, 2010] have been proposed to compute refined equilibria. However, the MPs used are non-linear and often have an exponential number of variables or constraints, resulting in limited scalability. A few works use iterative methods [Farina et al., 2017; Kroer et al., 2017] but they require exponentiation in game tree traversal and full access to the game structure, which limits their applicability to large complex games.

Stochastic Bayesian games have been extensively studied in mathematics and economics [Forges, 1992; Sorin, 2003; Chandrasekaran et al., 2017; Albrecht and Ramamoorthy, 2013]. [Albrecht et al., 2016] discussed the advantage of using type approximation to approximate the behaviors of agents to what have already been trained, to reduce the complexity in artificial intelligence (AI) researches. We focus on equilibrium refinement in these games and provide an RLbased framework.

Various classical multi-agent RL algorithms [Littman, 1994; Hu et al., 1998] are guaranteed to converge to an NE. Recent variants [Heinrich et al., 2015; Lowe et al., 2017; Iqbal and Sha, 2019] leverage the advances in deep learning [Mnih et al., 2015] and have been empirically shown to find well-performing strategies in large-scale games, such as Go [Silver et al., 2018] and StarCraft [Vinyals et al., 2019]. We present an RL-based approach for equilibrium refinement.

Algorithms for solving large zero-sum imperfect information games like Poker [Moravˇc´ık et al., 2017; Brown and Sandholm, 2018] need to explicitly reason about beliefs. Many recent algorithms in multi-agent RL use belief space policy or reason about joint beliefs. These works assume a fixed set of opponent policies that are unchanged [Shen and How, 2019], or consider specific problem domains [Serrino et al., 2019; Woodward et al., 2020]. Foerster et al.[2019] uses public belief state to find strategies in a fully cooperative partial information game. We consider stochastic Bayesian games and use belief over opponents' types.

3 Preliminaries

3.1 One-Sided Stochastic Bayesian Game

For expository purposes, we will mainly focus on what we call one-sided stochastic Bayesian games (OSSBG), which extends finite-horizon two-player stochastic games with type information. In particular, player 1 has a private type that affects the payoff function. Hence, in a competitive setting, player 1 needs to hide this information, while player 2 needs to infer the type from player 1's actions. Our algorithms can be extended to handle games where both players have types, as we will discuss in Section 6. Formally, an OSSBG is defined by a 8-tuple Γ = 〈Ω, µ0 , Λ, p0 , A, P, {uλi }, L, γ〉. Ω is the state space. µ0 is the initial state distribution. Λ = {1, . . . , |Λ|} is the set of types for player 1. p0 is the prior over player 1's type. A = ∏i Ai is the joint action space with Ai the action space for player i. P : Ω ×A → ∆|Ω| is the transition function where ∆|Ω| represents the |Ω|- dimensional probability simplex. uλi : Ω × A → R is the payoff function for player i given player 1's type λ. L denotes the length of the horizon or number of rounds. γ is the discount factor.

One play of an OSSBG starts with a type λ sampled from p0 and an initial state s0 sampled from µ0 . Then, L rounds of the game will rollout. In round l, players take actions al1 ∈ A1 and al2 ∈ A2 simultaneously and independently, based on the history hl := {s0 , (a01 , a02 ), . . . , (al-1 1 , al-1 2 ), sl }. The players will then get payoff uλi (st , al1 , al2 ). Note that the payoff uλi (sl , a1, a2) at every round l will not be revealed until the end of every play on the game to prevent type information leakage. The states transit w.r.t. P(sl+1 |sl , al1 , al2 ) across rounds.

Let Hl denote the set of all possible histories in round l and H = ⋃l Hl . Let π1 : Λ×H→∆A1 , π2 : H→∆A2 be the players' behavioral strategies. Given the type λ, the history hl and the strategy profile π = (π1, π2), player i's discounted accumulative expected utility from round l onward is

Similarly, we can define the Q function by Qλi (π, hl , a) = uλi (sl , a1, a2) + γEs′ [V λ i (π, hl ∪ {(a1, a2), s′ })].

An OSSBG can be converted into an equivalent extensiveform game (EFG) with imperfect information where each node in the game tree corresponds to a (type, history) pair (see Appendix F). However, this EFG is exponentially large, and existing methods for equilibrium refinement in EFGs [Kroer et al., 2017] are not suitable due to their limited scalability.

3.2 EquilibriumConcepts in OSSBG

Let Πi denote the space of all valid strategies for Player i.

Definition 3.1 (ϵ-NE) A strategy profile π = (π1, π2) is an ϵNE if for i = 1, 2, and all visitable history hl corresponding to the final policy,

where πi|hl→π′i means playing πi until hl is reached, then playing π′i onwards.

Definition 3.2 (ϵ-PBE) A strategy profile π = (π1, π2) is an ϵ-PBE if for i = 1, 2 and all histories hl ,

where πi|hl→π′i means playing πi until hl is reached, then playing π′i onwards.

It is straightforward that an ϵ-PBE is also an ϵ-NE.

4 Temporal-Induced Self-Play

Our TISP framework (Alg. 1) considers each player as an RL agent and trains them with self-play. Each agent maintains a policy and an estimated value function, which will be updated during training. TISP has four ingredients. It uses belief-based representation (Sec. 4.1), backward induction (Sec. 4.2), policy learning (Sec. 4.3) and belief-space approximation (Sec. 4.4). We discuss test-time strategy and show that TISP converges to ϵ-PBEs under certain conditions in Sec. 4.5.

4.1 Belief-Based Representation

Instead of representing a policy as a function of the history, we consider player 2's belief b ∈ ∆|Λ| of player 1's type and represent πi as a function of the belief b and the current state sl in round l, i.e., π1,l(·|b, sl , λ) and π2,l(·|b, sl ). The belief b represents the posterior probability distribution of λ and can be obtained using Bayes rule given player 1's strategy:

where blλ is the probability of player 1 being type λ given all its actions up to round l -1. This belief-based representation avoids the enumeration of the exponentially many histories. Although it requires training a policy that outputs an action for any input belief in the continuous space, it is possible to use approximation as we show in Sec. 4.4. We can also define the belief-based value function for agent i in round l by

The Q-function Qλi,l (π, bl , sl , al ) can be defined similarly. We assume the policies and value functions are parameterized by θ and φ respectively with neural networks.

4.2 Backward Induction

Standard RL approaches with self-play train policies in a topdown manner: it executes the learning policies from round 0 to L - 1 and only learns from the experiences at visited decision points. To find strategy profiles with decent performances from any decision point onward, we use backward induction and train the policies and calculate the value functions in the reverse order of rounds: we start by training πi,L-1 for all agents and then calculate the corresponding value functions V λ i,L-1 , and then train πi,L-2 and so on.

The benefit of using backward induction is two-fold. In the standard forward-fashioned approach, one needs to roll out the entire trajectory to estimate the accumulative reward for policy and value learning. In contrast, with backward induction, when training πi,l, we have already obtained V λ i,l+1 . Thus, we just need to roll out the policy for 1 round and directly estimate the expected accumulated value using V λ i,l+1 and Eq. (5). Hence, we effectively reduce the original Lround game into L 1-round games, which makes the learning much easier. Another important benefit is that we can uniformly sample all possible combinations of state, belief and type at each round to ensure effective exploration. More specifically, in round l, we can sample a belief b and then construct a new game by resetting the environment with a uniformly randomly sampled state and a type sampled from b. Implementation-wise, we assume access to an auxiliary function from the environment, called sub reset(l, b) that produces a new game as described. This function takes two parameters, a round l and a belief b, as input and produces a new game by drawing a random state from the entire state space Ω with equal probability and a random type according to the belief distribution b. This function is an algorithmic requirement for the environment, which is typically feasible in practice. For example, most RL environments provides a reset function that generates a random starting state, so a simple code-level enhancement on this reset function can make existing testbeds compatible with our algorithm. We remark that even with such a minimal environment enhancement requirement, our framework does NOT utilize the transition information. Hence, our method remains nearly model-free comparing to other methods that assume full access to the underlying environment transitions - this is the assumption of most CFR-based algorithms. Furthermore, using customized reset function is not rare in the RL literature. For example, most automatic curriculum learning algorithms assumes a flexible reset function that can reset the state of an environment to a desired configuration.

4.3 Policy Learning

Each time a game is produced by sub reset(l, b), we perform a 1-round learning with self-play to find the policies πi,l. TISP allows different policy learning methods. Here we consider two popular choices, policy gradient and regret matching.

Policy Gradient

PG method directly takes a gradient step over the expected utility. For notational conciseness, we omit the super/subscripts of i, l, λ in the following equations and use s, b and s′ , b′ to denote the state and belief at current round and next round.

Theorem 4.1 In the belief-based representation, the policy gradient derives as follows:

Comparing to the standard policy gradient theorem, we have an additional term in Eq.(6) (the second term). Intuitively, when the belief space is introduced, the next belief b′ is a function of the current belief b and the policy πθ in the current round (Eq.(4)). Thus, the change in the current policy may influence future beliefs, resulting in the second term. The full derivation can be found in Appendix E. We also show in the experiment section that when the second term is ignored, the learned policies can be substantially worse. We refer to this PG variant of TISP framework as TISP-PG.

Regret Matching

Regret matching is another popular choice for imperfect information games. We take inspirations from Deep CFR [Brown et al., 2019] and propose another variant of TISP, referred to as TISP-CFR. Specifically, for each training iteration t, let Rt (s, a) denote the regret of action a at state s, πt (a|s, b) denote the current policy, Qt (πt , s, b, a) denote the Q-function and V t φ (πt , s, b) denote the value function corresponding to πt . Then we have

where Rt+1 (s, b, a) = ∑tτ=1 Qτ (πτ , s, b, a) - V τ φ (πτ , s, b) and (·)+ := max(·, 0). Since the policy can be directly computed from the value function, we only learn V t φ here. Besides, most regret-based algorithms require known transition functions, which enables them to reset to any infomationset node in the training. We use the outcome sampling method [Lanctot et al., 2009], which samples a batch of transitions to update the regret. This is similar to the value learning procedure in standard RL algorithms. This ensures our algorithm to be model-free. Although TISP-CFR does not require any gradient computation, it is in practice much slower than TISP-PG since it has to learn an entire value network in every single iteration.

4.4 Belief-Space Policy Approximation

A small change to the belief can drastically change the policy. When using a function approximator for the policy, this requires the network to be sensitive to the belief input. We empirically observe that a single neural network often fails to capture the desired belief-conditioned policy. Therefore, we use an ensemble-based approach to tackle this issue.

At each round, we sample K belief points {b1, b2, ..., bK} from the belief space ∆|Λ| . For each belief bk, we use selfplay to learn an accurate independent strategy πθk (a|s; bk)

Algorithm 1 Temporal-Induced Self-Play

Algorithm 2 Compute Test-Time Strategy

1: function GETSTRATEGY(hl , πθ1 , . . . , πθL ) 2: b0 ← p0 3: for j ← 0, . . . , l - 1 do 4: update bj+1 using bj , sj , aj and πθj with Eq.(4)

• 5: return π(a|bl , sl ) with Eq.(7)

and value Vφk (π, s; bk) over the state space but specifically conditioning on this particular belief input bk. When querying the policy and value for an arbitrary belief b different from the sampled ones, we use a distance-based non-parametric method to approximate the target policy and value. Specifically, for any two belief b1 and b2, we define a distance metric w(b1, b2) = 1 max(ϵ,‖b-b′ ‖2 ) and then for the query belief b, we calculate its policy π(a|b, s) and value V (π, b, s) by

We introduce a density parameter d to ensure the sampled points are dense and has good coverage over the belief space. d is defined as the farthest distance between any point in ∆|Λ| and its nearest sampled points, or formally d = sup{min{‖b, bi‖ | i = 1, . . . ,K} | b ∈ ∆|Λ| }. A smaller d indicates a denser sampled points set.

Note that the policy and value networks at different belief points at each round are completely independent and can be therefore trained in perfect parallel. So the overall training wall-clock time remains unchanged with policy ensembles. Additional discussions on belief sampling are in Appx. A.

4.5 Test-time Strategy

Note that our algorithm requires computing the precise belief using Eq. 4, which requires the known policy for player 1, which might not be feasible at test time when competing against an unknown opponent. Therefore, at test time, we update the belief according to the training policy of player 1, regardless of its actual opponent policy. That is, even though the actions produced by the actual opponent can be completely different from the oracle strategies we learned from training, we still use the oracle policy from training to compute the belief. Note that it is possible that we obtain an infeasible belief, i.e., the opponent chooses an action with zero probability in the oracle strategy. In this case, we simply use a uniform belief instead. The procedure is summarized in Alg. 2. We also theoretically prove in Thm. 4.2 that in the zero-sum case, the strategy provided in Alg. 2 provides a bounded approximate PBE and further converges to a PBE with infinite policy learning iterations and sampled beliefs. The poof can be found in Appendix F.

Theorem 4.2 When the game is zero-sum and Ω is finite, the strategies produced by Alg. 2 is ϵ-PBE, where ϵ = L(dU +c · T -1/2 ), d is the distance parameter in belief sampling, U = L · ( maxi,s,a1,a2 ui(s, a1, a2)-mini,s,a1,a2 ui(s, a1, a2)), n is the number of iterations in policy learning and c is a positive constant associated with the particular algorithm (TISPPG or TISP-CFR, details in Appendix F). When T → ∞ and d → 0, the strategy becomes a PBE.

We remark that TISP is nearly-model-free and does not utilize the transition probabilities, which ensures its adaptability.

5 Experiment

We test our algorithms in three sets of games. While very few previous works in RL focus on equilibrium refinement, we compare our algorithm with self-play PG with RNN-based policy (referred to as RNN) and provide ablation studies for the TISP-PG algorithm: BPG uses only belief-based policy without backward induction or belief-space approximation; BI adopt backward induction and belief-based policy but does not use belief-space approximation. Full experiment details can be found in Appx. D.

5.1 Finitely Repeated Security Game

Game Setting

We consider a finitely repeated simultaneous-move security game, as discussed in [Nguyen et al., 2019]. Specifically, this is an extension of a one-round security game by repeating it for L rounds. Each round's utility function can be seen as a special form of matrix game and remains the same across rounds. In each round, the attacker can choose to attack one position from all A positions, and the defender can choose to defend one. The attacker succeeds if the target is not defended. The attacker will get a reward if it successfully attacks the target and a penalty if it fails. Correspondingly, the defender gets a penalty if it fails to defend a place and a reward otherwise. In the zero-sum setting, the payoff of the defender is the negative of the attacker's. We also adopt a general-sum setting described in [Nguyen et al., 2019] where the defender's payoff is only related to the action it chooses, regardless of the attacker's type.

Evaluation

We evaluate our solution by calculating the minimum ϵ so that our solution is an ϵ-PBE. We show the average result of 5 different game instances.

(d) Zero-sum result, with |Λ| = 3.

Table 2: Comparing mathematical-programming and our methods, i.e., TISP-PG and TISP-CFR, with known model. These results are averaged over 21 starting prior distributions of the attacker ([0.00, 1.00], [0.05, 0.95], . . . , [1.00, 0.00]).

Results

We first experiment with the zero-sum setting where we have proved our model can converge to an ϵ-PBE. The comparison are shown in Table 1a,1c. We use two known model variants, TISP-PG and TISP-CFR, and a model-free version of TISP-PG in this comparison. TISP-PG achieves the best results, while TISP-CFR also has comparable performances. We note that simply using an RNN or using belief-space policy performs only slightly better than a random policy.

Then we conduct experiments in general-sum games with results shown in Table 1b,1c. We empirically observe that the derived solution has comparable quality with the zero-sum setting. We also compare our methods with the Mathematical-Programming-based method (MP) in [Nguyen et al., 2019], which requires full access to the game transition. The results are shown in Table 2. Although when L is small, the MP solution achieves superior accuracy, it quickly runs out of memory (marked as "N/A") since its time and memory requirement grows at an exponential rate w.r.t. L. Again, our TISP variants perform the best among all learning-based methods. We remark that despite of the performance gap between our approach and the MP methods, the error on those games unsolvable for MP methods is merely 0.1% comparing to the total utility.

In our experiments, we do not observe orders of magnitudes difference in running time between our method and baselines: TISP-PG and TISP-CFR in the Tagging game uses 20 hours with 10M samples in total even with particle-based approximation (200k samples per belief point) while RNN and BPG in the Tagging game utilizes roughly 7 hours with 2M total samples for convergence.

Regarding the scalability on the number of types, as the number of types increases, the intrinsic learning difficulty increases. This is a challenge faced by all the methods. The primary contribution of this paper is a new learning-based framework for PBNE. While we primarily focus on the case of 2 types, our approach generalizes to more types naturally with an additional experiment conducted for 3 types in Table. 1d. Advanced sampling techniques can potentially be utilized for more types, which we leave for future work.

5.2 Exposing Game

Game Setting

We also present a two-step matrix game, which we call Exposing. In this game, player 2 aims to guess the correct type of player 1 in the second round. There are two actions available for player 1 and three actions available for player 2 in each round. Specifically, the three actions for player 2 means guessing player 1 is type 1, type 2 or not guessing at all. The reward for a correct and wrong guess is 10 and -20 respectively. The reward for not guessing is 0. Player 1 receives a positive 5 reward when the player 2 chooses to guess in the second round, regardless of which type player 2 guesses. In this game, player 1 has the incentive to expose its type to encourage player 2 to guess in the second round. We further add a reward of 1 for player 1 choosing action 1 in the first round regardless of its type to give player 1 an incentive to not exposing its type. With this reward, a short-sighted player 1 may pursue the 1 reward and forgo the 5 reward in the second round. The payoff matrices for this game are in Appx. D.

The equilibrium strategy for player 2 in the second round w.r.t. different types of player 1 is:

In this game, the equilibrium values in the second round for both types of player 1 are highly discontinuous with regard to player 2's belief, as shown in Fig. 1a, which makes the belief-space gradient term in Eq. 6 ineffective. However, the approximation introduced in Sec. 4.4 can serve as a soft representation of the true value function, as shown in Fig. 1b. This soft representation provides an approximated gradient in the belief space, which allows for belief-space exploration. We will show later that this belief-space exploration cannot be achieved otherwise.

1 The optimal solution refers to the Pareto-optimal PBE in this game. Note that there are two symmetric optimal solutions. We choose to only show one here for easy comparison and simplicity.

Results

We compare the training result between TISP-PG and TISPCFR to exhibit the effectiveness of our non-parametric approximation. We further add an ablation study that removes the belief-space gradient term in TISP-PG, which we call TISP-PG-. The results are shown in Table 3. We can see that TISP-PG is the only algorithm that successfully escapes from the basin area in Fig. 1 as it is the only algorithm that is capable of doing belief-space exploration. We also show the obtained policies Table 3. The training curves can be found in Appx. D. Note that the policies trained from TISP-CFR and TISP-PG- are also close to a PBE where player 1 takes action 1 regardless of its type in the first round, and player 2 chooses not to guess in the second round, although it is not Pareto-optimal.

5.3 Tagging Game

Game Setting

We test our method in a gridworld game Tagging, as illustrated in Fig. 2. The game is inspired by [Shen and How, 2019]. Specifically, the game is on an 8 × 8 square, and player 1 has two types, i.e., ally and enemy, and each type corresponds to a unique target place. Each player will receive distance-based reward to encourage it to move towards its target place. There is a river in the top half part of the grids which Player 2 cannot enter. Player 1 starts from the bottom middle of the map and player 2 starts from a random position under the river. Both players can choose to move in one of the four directions, [up(U), down(D), left(L), right(R)], by one cell. Player 2 has an additional action, tag, to tag player 1 as the enemy type. The tag action is only available when player 1 has not entered the river and the euclidean distance between the two players is less than 2.5. The attackers get higher rewards for getting closer to their type-specified target, and the defenders get higher rewards for getting closer to the attacker. Moreover, if the defender chooses to tag, it will get a reward of 10 if the attacker is of the enemy type and a reward of -20 if the attacker is of the ally type, while the attacker will get a reward of -10 for being tagged no matter what its type is. More detail is provided in Appx. D.

Based on the game's rule, an enemy-typed player 1 is likely to go to its own target immediately to get a higher reward. However, such a strategy reveals its type straight away, which can be punished by being tagged. A more clever strategy of an enemy-typed player 1 is to mimic the behavior of the allytyped player 1 in most situations and never let player-2's belief of enemy type be larger than 2 3 , so that player 2 has no incentive to tag it. The ally-typed player 1 may simply go up in most states in order to get closer to its target for a reward while player 2 should learn to tag player 1 if its belief of enemy type is high enough and try to move closer to player 1 in other cases.

Evaluation

Although it is computationally intractable to calculate the exact exploitability in this gridworld game, we examine the results following [Gray et al., 2021] by evaluating the performances in induced games. We choose 256 induced games among all the induced games after the second round and check their exploitability. We get the best response in each induced game in two ways: in the first round of each game, we enumerate all the possible actions and manually choose the best action. We also train a new BPG player-2 from scratch. This new BPG-based player is trained in a single-agent-like environment and does not need to consider the change in the player-1 policy. We check how much reward agents can get after the learning process finishes. A high reward from player 2 would indicate that player 1 fail to hide its type. We also provide the detailed strategies from different baselines for the first round of the game for additional insight.

Results

We show the derived policy in the very first step in Table 4. The policy learned by our method successfully keeps the belief to be less than 13 , and keeps a large probability of going to the target of each type. The RNN policy shows no preference between different actions, resulting in not being tagged but also not getting a larger reward for getting closer to the target. The BPG policy simply goes straight towards the target and is therefore punished for being tagged. The exploitability results are shown in Table 5. From the training reward achieved by the new exploiter player 2, TISP-PG performs the best among all baselines and TISP-CFR also produces a robust player-1 policy. We remark that relative performances of different methods in the gridworld game are consistent with what we have previously observed in the finitely repeated security games, which further validates the effectiveness of our approach.

6 Discussion and Conclusion

We proposed TISP, an RL-based framework to find strategies with a decent performance from any decision point onward. We provided theoretical justification and empirically demonstrated its effectiveness. Our algorithms can be easily extended to a two-sided stochastic Bayesian game. The TISP framework still applies, and the only major modification needed is to add a for-loop to sample belief points for player 2. This extension will cost more computing resources, but the networks can be trained fully in parallel. The full version of the extended algorithm is in Appendix C.

Acknowledgements

We would like to thank Ryan Shi for some help in writing the early workshop version of this paper. Co-author Fang is supported in part by NSF grant IIS- 1850477, a research grant from Lockheed Martin, and by the U.S. Army Combat Capabilities Development Command Army Research Laboratory Cooperative Agreement Number W911NF-13-2-0045 (ARL Cyber Security CRA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the funding agencies.