Approximating Value Equivalence in Interactive Dynamic Influence Diagrams Using Behavioral Coverage

1 Introduction

Extending single-agent dynamic influence diagrams (DIDs) [Howard and Matheson, 1984], interactive DIDs (I-DIDs) [Doshi et al., 2009; Zeng and Doshi, 2012] are a graphical framework for sequential multiagent decision making (planning) under uncertainty. Since I-DIDs deal with decision problems from an individual agents' perspective, they become a general decision making framework in both competitive and cooperative multiagent settings. Emerging I-DID applications include supplying control policies in automated vehicle routing problems [Luo et al., 2011], developing adversarial models in money laundering activities [Ng et al., 2010], designing intelligent non-player characters in real-time strategy games [Conroy et al., 2015] and so on.

From a subject agent's viewpoint, I-DIDs need to predict behavior of other agents. The prediction is generally conducted by solving a set of candidate models ascribed to other agents since the true model of the other agents is often unknown particularly in a competitive multiagent setting. The candidate models could be many and are updated when the other agents act and receive new observations over time. Consequently, the subject agent needs to maintain an exponentially growing space of candidate models, which is the main computational complexity towards solving I-DIDs.

Most of the previous I-DID solutions focus on behavioural equivalence (BE) techniques and reduce the model space by grouping candidate models that generate identical policies for other agents [Zeng and Doshi, 2012]. More recently, a fresh idea of model reduction resorts to the concept of value equivalence (VE) and groups models that bring identical expected value to a subject agent [Conroy et al., 2016]. Compared to the BE techniques, the VE method groups models that are either behaviorially equivalent or distinct. Conceptually, VE exhibits large potential to improve the scalability of I-DID solutions. However, identifying VE seems not to be applicable since it requires to compute optimal policies in an I-DID that needs to be built for the subject agent. In an initial investigation, Conroy et al. [2016] learn VE from available data of agents' interaction by recording their policies as well as values assigned to the policies. In this paper, we compute VE in a general setting where candidate models of other agents are known and an I-DID needs to be built to compute expected values for the subject agent.

Ideally, expected values received by the subject agent are calculated in a complete I-DID that expands all candidate models of other agents. However, this is a bit contradictory since we can't build the complete model due to computational and memory limits. Hence the challenge is: given the limited model space, how can we compute VE in a sufficiently good manner? To address this, we need to first select a subset of candidate models to build an I-DID for the subject agent, then calculate expected values of optimal policies resulting from the incomplete I-DID.

The model selection is important since it impacts the solution quality of the incomplete I-DID. Intuitively, the resulting I-DID model may generate near optimal policies if the selected models can sufficiently represent the entire set of candidate models. We measure the model representativeness in terms of its solution that prescribes agent's behavior, and propose a behavioral coverage function to facilitate the model selection process. As the policies resulting from the incomplete I-DID don't reflect a complete profile of the subject agent, we cannot simply retrieve the expected value from the model. Instead, we calculate the expected values for the subject agent in a simulated environment: given the (sub)-optimal policies, the subject agent interacts with other agents who use policies calculated from any of their candidate models. In this context, we make the following contributions:

• ÷ We develop a principled framework for VE identification given limited model space. It includes two phases: model selection and value computation.
• ÷ We focus on the model selection and propose a behavioral coverage function to choose top-K models in order to build an incomplete I-DID. We theoretically analyze the proposed function and develop a greedy algorithm for the top-K model selection.
• ÷ We empirically examine VE identification framework, discussing improvements driving a new line of I-DID research.

2 Background: Interactive Dynamic Influence Diagram

We briefly review the I-DID framework with elaboration in the well-studied multiagent tiger problem [Gmytrasiewicz and Doshi, 2005]. We then describe two types of I-DID solutions, namely behavioral equivalence (BE) and value equivalence (VE). For details we refer to [Zeng and Doshi, 2012]

2.1 Representation

I-DIDs are used to represent sequential multiagent decision making problems when a subject agent interacts with other agents under uncertainty and partial observability. I-DIDs model the predicted behavior of other agents by solving a set of their candidate models. Actions of both the agents influence state S and rewards R. In Fig. 1 we show a level l I-DID representation for agent i modeling another agent j in level l - 1. Level refers to the recursive reasoning of both agents, where level 0 is the lowest by not modeling the actions of others. I-DIDs achieve this by introducing a new node to the framework, the model node, Mj↪l-1, modeling the decision making process of agent j at level l - 1. This is accomplished by Mj↪l-1 containing a candidate set of j's models from which their expected behavior can be calculated Aj. The connection between the model node and the predicted behavior is represented by a policy link (the dashed line) connecting Mj↪l-1 and Aj. Each candidate model contained within Mj↪l-1 can itself be a level l - 1 I-DID or level 0 DID.

Complexity arises towards modeling with I-DIDs due to the update of the model node built up of all of j's candidate models. Such models require updating with every time step via the model update link (the dotted arrow from M t j↪l-1 to M t+1 j↪l-1 in Fig. 1), as agent j acts and receives observations over time. The updated models differ in the beliefs that are obtained for a pair of j's actions and observations. Agent i tracks the updates of j models with the number of models growing in a new model node. The number of models grows exponentially for each time step. The number of models in M t+1 j↪l-1 is up to ♣Mtj↪l-1 ♣♣Aj♣♣⌦j♣ where ♣Mtj↪l-1 ♣ is the number of models at time step t, and ♣Aj♣ and ♣⌦j♣ are the largest spaces of actions and observations respectively.

To solve I-DIDs we replace the model nodes and update links with chance nodes and dependency links. This converts the I-DID into a regular DID allowing for any DID solving technique to be applied. Below we show the multiagent tiger problem to elaborate the I-DID framework.

We show a level 1 I-DID for agent i considering two candidate models of agent j , mt↪1 j↪0 andmt↪2 j↪0 at Level 0 in Fig 2. The I-DID has been converted to a regular DID where the chance node Mod[Mj↪0] represents j's candidate models differing in beliefs of the tigers location. Solving all candidate models obtains j expected optimal decisions. The conditional probability table (CPT) in Fig. 4 show agent j's optimal decisions of OL and L when the candidate models have been solved for level 0. These optimal decisions can then be mapped into the predicted actions of j in Atj .

In Fig. 3 we show the model update of mt↪1 j↪0 and mt↪2 j↪0 as agent j receives one of two possible observations (either GL or GR). This requires four new models to be generated in the model node M t+1 j↪0 .

Fig. 4 shows he CPT of Mod[M t+1 j↪0 ]. For example, the first row of the CPT shows mt↪1 j↪0 is updated into the model mt+1↪1 j↪0 when agent j takes the action OL at time t and observes GL at t + 1. As neither OR nor L is the optimal decision for mt↪1 j↪0 , we assign a uniform distribution to indicate mt↪1 j↪0 does not transform into any of the new models for these actions.

CPT of Mod[Mj,0 t+1 ]

Figure 4: The CPTs of the chance nodes Atj and Mod[M t+1 j↪0 ].

2.2 Solutions

Solving a level l I-DID includes two steps. We first need to solve j's candidate models at level l-1 and expand them in the I-DID, converting the I-DID into a regular DID (as shown in Fig. 2). After that, we can use any conventional DID technique to solve the converted model. The main complexity is the exponential growth in the number of models over time. Most existing research focuses on two types of model reduction techniques to compress the model space in I-DIDs.

Behavioral Equivalence (BE) groups candidate models with identical policies for agent j at level l - 1, as defined below.

Definition 1 (BE) Two models, mj and ˆmj, of agent j, are behaviorally equivalent if OPT(mj) = OPT( ˆmj), where OPT(·) denotes the solution of the model.

A model solution is generally represented by a policy tree. A depth-T policy tree contains a set of policy paths, T T j =S hTj where the policy path, hTj , is an action-observation sequence over T planning horizons. We let hTj = ¶atj ↪ ot+1 j ♦T-1 t=0 , where oTj is null with no observations following the final action.

Value Equivalence (VE) groups models that generate the same expected value for agent i at level l, as defined below.

Definition 2 (Value Equivalence) Two models of agent j, mj↪l-1 and ˆmj↪l-1, are value equivalence if V T ( ˆmi↪l♣mj↪l-1 ˆmj↪l-1) = V T (mi↪l♣ ˆmj↪l-1 mj↪l-1), where V T (·) is the expected values for agent i given that the model ˆmi↪l is expanded by replacing mj↪l-1 with ˆmj↪l-1 (mj↪l-1 ˆmj↪l-1 or vice versa) in a set of j's candidate models.

Expected value of agent i's model mi↪l computed in Eq. 1.

Here, bi↪l(s↪ mj↪l-1) is the agent i's belief over the physical states and possible models of j at level l-1, a⇤i is i's optimal action and m0i↪l is the updated model of agent i containing the updated belief at the next time step.

Note that agent i assigns some probability mass to every candidate model of agent j in the model node (Mod[M t j ]). When the replacement (mj↪l-1 $ ˆmj↪l-1) occurs, we transfer the probability mass over the two models. According to Eq. 1, the VE models could be either behaviorally equivalent or distinct. Hence using VE, compared to BE, could lead to more reduction in the model space of agent j. The most recent I-DID research [Conroy et al., 2016] proposes the VE concept, but doesn't develop applicable I-DID solutions.

3 Model Selection and Value Computation

VE determination needs to compute the expected value of agent i, which requires building an I-DID for i and solve the model accordingly. An exact solution expands all candidate models of agent j to build a complete I-DID. However, this is not applicable. In this paper, we approximate the VE identification given the limited model space in an incomplete I-DID.

3.1 Value Equivalence Identification Framework

Let Mj↪l-1 be the set of all candidate models of agent j. Through VE, we aim to reduce the set into the limited space containing K models MKj↪l-1 . Alg. 1 shows a principled framework for identifying VE of candidate models, which results in the compressed model space.

Algorithm 1 VE Identification Framework

1: function FRAMEWORK(mi↪l,Mj↪l-1, K, N) 2: InitializeMKj↪l-1 ;, Ite=0 3: while ♣MKj↪l-1♣ <K ^ (Ite + ♣MKj↪l-1♣ < ♣Mj↪l-1♣) do 4: NewMKj↪l-1 SelectModel(Mj↪l-1, K) 5: for all mj↪l-1↪ ˆmj↪l-1 2MKj↪l-1 do 6: Build ˆmi↪l given ˆmj↪l-1 mj↪l-1 7: Build mi↪l given mj↪l-1 ˆmj↪l-1 8: ˆ Ti ˆmi↪l▷Solve, Ti mi↪l▷Solve 9: V ( ˆmi↪l♣mj↪l-1 ˆmj↪l-1) ComputeValue( ˆ Ti , Mj↪l-1, N) 10: V (mi↪l♣ ˆmj↪l-1 mj↪l-1) ComputeValue(Ti, Mj↪l-1, N) 11: if V ( ˆmi↪l♣mj↪l-1 ˆmj↪l-1) = V (mi↪l♣ ˆmj↪l-1 mj↪l-1) then 12: MKj↪l-1 - ¶ ˆmj↪l-1♦ 13: Ite = Ite + 1 14: return MKj↪l-1

In this framework, we first develop a model selection function to choose a subset of j's candidate models based on which we can build incomplete I-DIDs for agent i (line 4). We then retrieve optimal policies of agent i by solving the built I-DIDs when a mutual replacement is conducted in the subset (lines 6-8). We can use the previous I-DID techniques to solve the models (line 8). Subsequently, we compute the expected values of agent i's policies through a value computation function that evaluates the policies over N simulations (lines 9-10). The value comparison may prune the VE models and further compress the subset (lines 11-12). We repeat the process until the limited model space is filled with K models or all the candidate models have been searched.

3.2 Top-K Model Selection

Without a complete I-DID built by expanding all candidate models, we can't guarantee an optimal policy will be used to compute the expected values of agent i. Given the limited model space, we aim to provide reasonably good policies by selecting a proper subset of j's candidate models to build IDIDs. We proceed to develop such a selection mechanism.

Intuitively, we need to choose K models whose joint solutions (representing agent j's behavior) have the largest coverage of solutions of an entire set of j's candidate models. In other words, the quality of i's policies resulting from the I-DID may not be significantly compromised if agent i considers as many as possible representative behaviors of j. The representative behavior occurs frequently in agents' interactions. Inspired by this, we introduce a behavioral coverage function that measures the similarity between models.

The similarity between models mj and m0j , denoted by w(mj↪m0j ), is defined by how similar the policy generated by mj is to that of m0j . It is calculated in Eq. 2.

where sim(hTmj ↪ hTm0j ) counts the number of identical actions given same observations at each time step.

Then, Pm0j 2MKj↪l-1 w(mj ↪ m0j ) measures how much of the model mj is covered by the selected K models. We aim to find a set of top-K models, MKj↪l-1 , that have the largest behavioral coverage of the entire model space Mj↪l-1. Formally the top-K model selection is formulated as one optimization problem below.

We observe that the model selection is a complex combinatorial optimization problem with a single objective. We prove it to be NP-hard.

Proposition 1 The top-K model selection problem formulated in Eq. 3 is NP-hard.

Proof. We prove it by converting Eq. 3 into a unit cost version of the budgeted maximum coverage problem (UBMC) [Khuller et al., 1999]. Given a unit cost version of the UBMC problem instance ' : a collection of sets S = ¶S1↪ S2↪ · · · ↪ Sm♦ with a unit cost C, a domain of elements X = ¶x1↪ x2↪ · · · ↪ xn♦ with associated weights ¶z1↪ z2↪ · · · ↪ zn♦, and a budget B, we can construct a top-K

model selection instance ! by setting K = bB◁Cc and σ(S0 ) corresponds to the total weight of the elements covered by S0 . Hence, S0 is the set having a maximum weight in ' iff S0 is the top-K model set of !. As the UBMC problem has been proved to be NP-hard, the top-K model selection problem is NP-hard as well. ⌅

It is rather hard to solve the model selection problem. Meanwhile, we notice that the selection function σ(MKj↪l-1 ) is a monotone submodular function [Nemhauser et al., 1978]. Let V be a finite set. A set of function F: V ! R is called submodular if it satisfies the diminishing returns property, F(B S s)-F(B) ≥ F( ˆB S s)-F( ˆB), for all B ✓ ˆB ✓ V and s 62 B. F(B S s) - F(B) is the marginal increase of F when an element s is added into B. Submodularity characterizes the notion that supplementing elements to a small set B provides more than doing it to a larger set ˆB.

Naturally, σ(MKj↪l-1 ) is monotone as the model coverage increases with a larger set of candidate models. It is also submodular. Intuitively, the increment when adding a newmodel into a small set of top-K1 models will be larger than the increment when adding it to a large set of top-K2 models, where K1 < K2, since the behavior exhibited by the new model might have already covered by those models that are in the larger set but not in the small set. This is the diminishing returns property. We present the property of σ(MKj↪l-1 ) in Proposition 2.

Proposition 2 The model selection function σ(MKj↪l-1 ) is monotone and submodular.

The monotone submodular property suggests a greedy algorithm with theoretical guarantees for optimizing the model selection function [Nemhauser et al., 1978]. In Alg. 2, the greedy algorithm starts with an empty set and computes behavioral coverage of every model (lines 2-4). Then repeatedly adds the model incurring the largest marginal coverage increasing the model set until ♣MKj↪l-1 ♣ = K (lines 5-7). The algorithm achieves near-optimal solutions of top-K models with a (1- 1e ) approximation on optimal behavioral coverage.

Since the greedy algorithm needs to check all of the candidate models in every round (line 6), the time complexity is O[K♣Mj↪l-1♣B(σ(·)), where B(σ(·)) the run time for computing the model coverage.

Algorithm 2 Model Selection

Remarks. We note that many previous BE techniques[Zeng and Doshi, 2012] have the same purpose of selecting a subset of candidate models to develop I-DIDs of high quality. However, the techniques prune the

Algorithm 3 Value Computation

models through a pair check of behavioral equivalence and don't consider impact of individual models on the global behavioral coverage. As demonstrated in empirical study (in Section 4.1), top-K model selection technique provides better I-DID solutions.

Selection of K value often depends on model space allowed in I-DIDs so that the I-DIDs can be solved for a specific planning horizon. A trade-off between quality and scalability.

.

3.3 Value Computation

Given top-K models, we build an I-DID based on which we proceed to identify VE of models in the selected set. As the incomplete I-DID is built from a subset of j's candidate models, the resulting policy for agent i may not be the same as that computed from a complete I-DID expanded by all j's models. The expected value of the incomplete I-DID is not a good measurement of agent i's policy since unexpected behavior of agent j that may occur in their interactions may not be considered by agent i. Thus, we compute the expected value for agent i by simulating how i interacts with agent j. The value is counted as the average rewards that agent i receives when it interacts with agent j over a number of times. This is well matched with how I-DID solutions are evaluated in the previous I-DID research. To have the self-contained paper, we present a value computation in Alg. 3

Given agent i's beliefs over j's models, we sample a model of j and solve the model to obtain its policies (lines 4-5). Then, agents follow their policies in the interactions (lines 6-7). We conduct N simulations and compute the expected value of i's policies as the average reward of the simulations.

4 Experimental Results

We implemented the framework (in Alg. 1) to prune VE models of agent j. The implementation replaces the previous BE pruning methods in solving agent i's I-DID [Zeng and Doshi, 2012]. We first verify the performance of the top-K model selection in Alg. 2, which itself can be used to solve I-DID, in comparison to the state-of-art BE methods. We then evaluate the entire VE identification framework in two large problem domains. One is the UAV benchmark (♣S♣=81, ♣A♣=5 and ♣⌦♣=5) [Zeng and Doshi, 2012] - currently the largest problem domain studied in I-POMDP/I-DID based multiagent planning research while the other is a real-world game domain of StarCraft 1 (♣S♣=16, ♣A♣=3 and ♣⌦♣=4). We build level 1 I-

1 http://eu.blizzard.com/en-gb/games/sc/

(a) T = 6 and ♣Mj↪l-1♣=50

(b) T = 10 and ♣Mj↪l-1♣=40

Figure 5: Performance of top-K model selection in Tiger.

DIDs for agent i. To compare different I-DID techniques, we compute the average rewards of agent i when it plays against agent j by executing their policies solved from the I-DIDs.

4.1 Top-K Models as I-DID Solutions

We build level 1 I-DID for the multiagent tiger problem since the problem is small and allows an intensive study of the model selection algorithm. In solving I-DIDs, we replace the entire set of j's models with top-K models selected by the greedy algorithm (GS) in Alg. 2. We compare the top-K model selection technique with both the exact BE approach - discriminative model update (DMU)- and the approximate one (ABE) [Zeng and Doshi, 2012]. Note that no VE models are pruned in these experiments since the model selection is conducted for a single round.

In Fig. 5, we show agent i's average rewards over 500 simulations for T=6 and 10 respectively. For a fair comparison, we let top-K and ABE maintain the same number of j's models at each time step in the I-DIDs. We observe that topK consistently outperforms ABE when K varies in different cases. As expected, the top-K model selection technique approaches DMU when more models are selected. This is because ABE doesn't consider joint effect of agent j's behavior and may keep redundant models in the limited model space. The top-K models maintain a global coverage particularly on the representative behaviors. Hence the top-K models selected by GS develop a good quality of I-DID subject with the limited model space.

4.2 Value Equivalence Performance

In this set of experiments, we prune VE models using the implementation in Alg. 1, denoted by VE+GS. To confirm the performance of GS, we also implemented a random search (RS) algorithm to find top-K models. RS randomly chooses a set of K models for a number of times and keeps the one with the largest behavioral coverage. It may replace GS in the model selection function and the resulting I-DID solution is labeled by VE+RS.

UAV Problem Domain

In Fig. 6, we show the performance of VE approaches for solving I-DIDs in UAV. The rewards of agent i are averaged over 100 simulations. VE+GS exhibits very competitive performance compared to DMU and performs significantly better than VE+RS. The random selection doesn't generate a good set of top-K models, which impacts the VE determination resulting in poor I-DID solutions. Since VE prunes more models than DMU, it has a better scalability to solve more complex I-DIDs like T=7 in Fig. 6b.

(a) T = 5 and ♣Mj↪l-1♣=25

(b) T = 7 and ♣Mj↪l-1♣=20

(a) T=5 and ♣Mj↪l-1♣=10

Figure 7: Performance of VE techniques in StarCraft.

StarCraft Application

The real-world domain we choose to model for testing VE+GS is StarCraft. We choose StarCraft because the domain has partial observability by hiding the true state of the game to the player, requiring the player to make observations influenced by the true state. Human vs Human games are incredibly complex with players required to maintain focus in many problem areas such as resource management and battle tactics. In this paper, we focus on a typical 3 vs 3 unit battle.

As a small number of j's candidate models are tested, we implemented an optimal search algorithm (OS) to select topK models. OS compares behavioral coverage values for every combination of K models. Fig. 7a shows that VE+GS performs closely with VE+OS for solving I-DIDs. It has slightly better performance than VE+OS in some cases. This is because the approximation of VE+GS may introduce models that concentrate on a very small number of representative behaviors. However, OS distributes the focus (i's beliefs) over multiple types of behaviors to optimize the coverage. Particularly in game-play, players often focus on a specific gaming pattern, which is confirmed in the available game replay data. Agent i will be highly rewarded by successfully predicting this single type of behavioral pattern.

Fig. 7b compares model selection time. RS is much faster than others, but results in the lowest rewards. OS starts with similar durations; however, as K increases it increases much faster than GS. We don't show the time of computing values in Alg. 3 since it is similar among all the three methods due to similarly sized I-DIDs generated. Although DMU model selection is compared in model selection, the resulting I-DID's model space is too large to be solved. Thus showing the improved scalability of our model reduction method.

5 RelatedWorks

I-DIDs are a graphical representation of finitely-nested interactive partially observable Markov decision processes(IPOMDPs) [Gmytrasiewicz and Doshi, 2005]. Exponential growth in candidate models of other agents adds significant complexity to solving I-DIDs.

Currently the accepted methods exploit BE to reduce the model space within I-DID solutions [Zeng and Doshi, 2012]. Multiple works examine policy trees to develop methods to reduce the model space. Doshi et al. [Doshi et al., 2010] introduces an ✏-subjective equivalence method. ✏-subjective equivalence seeks to prune the model space of I-DIDs by pruning equivalent models comparing agents future action observation paths. Zeng et al. [Zeng et al., 2011] cluster models by comparing only a partial set of paths within the policy trees of other agents j. Online I-DID solutions of expand the true behavior of other agents from interactions pioneered by Chen et al. [Chen et al., 2015]. Learning behavior of agents from available data [Conroy et al., 2015] provides knowledge towards refining the model space in I-DIDs. BE techniques have aided in the usefulness of I-DIDs and shown potential data-driven learning towards real-world applications [Luo et al., 2011; Conroy et al., 2015]. In line with the recent work of Albrecht et al. [Albrecht et al., 2015] with type based methods our method of model reduction can be generalised as an example of such a method.

Most relevant work of utility equivalence techniques in a social simulation setting of class bullying [Pynadath and Marsella, 2007], shows a minimal number of mental models that could be maintained through grouping utility equivalent models. In the same vein, Conroy el al. 2016 show benefit of VE-based I-DID solutions where VE models can be found from available interaction data without building I-DIDs.

Graphical models of cooperative decision making scenarios utilizing frameworks such as decentralized POMDPs [Seuken and Zilberstein, 2008] remain relatively unexplored while factored representations of the state space are becoming prevalent [Oliehoek et al., 2008]. Such factored representations allow for solutions to decentralized POMDPs amongst multiple agents by exploiting the structure of interactions amongst such agents [Oliehoek et al., 2013]. Factored representations in dynamic Bayesian networks to project agents' beliefs foreward, then expectationmaximization learning of stochastic finite state machines was utilized by Pajarinen and Peltonen [2011].

6 Conclusion and FutureWork

Value equivalence exhibits scalability improvement over the BE techniques for solving I-DIDs. More importantly, VE methods are developed in consideration of expected values of a subject agent so that they can directly measure the solution quality. Given the limited model space, the VE techniques can't avoid approximation in the VE identification. However, as demonstrated in the empirical study, the top-K model selection provides sufficiently good I-DID solutions.

Immediate VE-based I-DID research may consider improving either effectiveness of the top-K model selection or efficiency of value computation. The behavioral coverage function can be extended to include other factors. For example, as suggested in the above tests in Starcraft, it is worth focusing on highly rewarded behavioral patterns. However, holding a monotone submodular function is important since it introduces efficient approximation with theoretical guarantee on solution quality. Another interesting direction is the improvement of computing expected values of agents' policies in multiagent settings by reducing the number of samples.