Speeding Up Exact Solutions of Interactive Dynamic Influence Diagrams Using Action Equivalence

1 Introduction

Interactive dynamic influence diagrams (I-DIDs) [Doshi et al., 2009] are graphical models for sequential decision making in uncertain settings shared by other agents. I-DIDs may be viewed as graphical counterparts of I-POMDPs [Gmytrasiewicz and Doshi, 2005]. They generalize DIDs [Tatman and Shachter, 1990], which may be viewed as graphical counterparts of POMDPs, to multiagent settings analogously to how I-POMDPs generalize POMDPs. Importantly, I-DIDs have the advantage of decomposing the state space into variables and relationships between them by exploiting the domain structure which allows computational benefits in comparison to I-POMDPs [Doshi et al., 2009].

I-DIDs contribute to a growing line of work that includes multiagent influence diagrams (MAIDs) [Koller and Milch, 2001], and more recently, networks of influence diagrams (NIDs) [Gal and Pfeffer, 2003]. MAIDs objectively analyze the game, efficiently computing the Nash equilibrium profile by exploiting the independence structure. NIDs extend MAIDs to include agents' uncertainty over the game being

∗Prashant Doshi acknowledges partial support from grant #FA9550-08-1-0429 from US AFOSR.

Prashant Doshi

Dept. of Computer Science University of Georgia Athens, GA 30602 pdoshi@cs.uga.edu

played and over models of other agents. Both MAIDs and NIDs provide an analysis of the game from an external viewpoint, and adopt Nash equilibrium as the solution concept. Specifically, MAIDs do not allow us to define a distribution over non-equilibriumbehaviors of other agents. Furthermore, their applicability is limited to static single play games. Interactions are more complex when they are extended over time, where predictions about others' future actions must be made using models that change as the agents act and observe. IDIDs seek to address this gap by offering an intuitive way to extend sequential decision making to multiagent settings.

As we may expect, I-DIDs acutely suffer from both the curses of dimensionality and history [Pineau et al., 2006]. This is because the state space in I-DIDs includes the models of other agents in addition to the traditional physical states. These models encompass the agents' beliefs, actions and sensory capabilities, and preferences, and may themselves be formalized as I-DIDs. The nesting is terminated at the 0th level where the other agents are modeled using DIDs. As the agents act, observe, and update beliefs, I-DIDs must track the evolution of the models over time. Consequently, I-DIDs not only suffer from the curse of history that afflicts the modeling agent, but more so from that exhibited by the modeled agents. The exponential growth in the number of models over time also further contributes to the dimensionality of the state space. This is complicated by the nested nature of the space.

While we may solve I-DIDs exactly if the number of models of others is finite, we are unable to scale to large problems or even longer horizons for small problems. One way to mitigate the intractability is to group together behaviorally equivalent models [Rathnas et al., 2006; Pynadath and Marsella, 2007] thereby reducing the cardinality of the model node. Doshi et al. [2009] proposed an approximation technique for solving I-DIDs based on clustering models that are likely to be behaviorally equivalent. Solutions of multiagent problems up to six horizons were shown using these approaches.

Although exact approaches face significant hurdles in scaling to realistic problems, nevertheless exact solutions play an important role: they serve as optimal benchmarks for solutions provided by approximation techniques. In this paper, we improve on the previous approach of exactly solving I-DIDs. We reduce the model space by grouping behaviorally equivalent models. A behavioral equivalence class contains models that exhibit identical solutions for all time steps. We further compact the space of models in the model node by observing that behaviorally distinct models may prescribe identical actions at a single time step. We may then group together these models into a single equivalence class. In comparison to behavioral equivalence, the definition of our equivalence class is different: it includes those models whose prescribed action for the particular time step is the same, and we call it action equivalence. Since there are typically additional models than the behaviorally equivalent ones that prescribe identical actions at a time step, an action equivalence class often includes many more models. Consequently, the model space is partitioned into lesser number of classes than previously [Rathnas et al., 2006] and is bounded by the number of actions of the other agent.

We begin by solving the individual models in the initial model node to obtain the policy trees. These trees are merged bottom-up to obtain a policy graph. As a result, behaviorally equivalent models, which have identical policy trees, are merged. We further group models at each time step whose prescribed actions at that step are identical. We show how we may compute the probability with which an equivalence class is updated to another class in the next time step. These probabilities constitute the new conditional probability distribution of the model node. We discuss computational savings and theoretically show that the approach preserves optimality. We demonstrate the performance of our approach on two problem domains and show significant time savings in comparison to previous approaches.

2 Background: Interactive DID

We briefly describe interactive influence diagrams (I-IDs) for two-agent interactions followed by their extensions to dynamic settings, I-DIDs, and refer the reader to [Doshi et al., 2009] for more details.

2.1 Syntax

In addition to the usual chance, decision, and utility nodes, IIDs include a new type of node called the model node (hexagonal node, Mj,l-1, in Fig. 1(a)). The probability distribution over the chance node, S, and the model node together represents agent i's belief over its interactive state space. In addition to the model node, I-IDs differ from IDs by having a chance node, Aj, that represents the distribution over other agent's actions, and a dashed link, called a policy link.

The model node contains as its values the alternative computational models ascribed by i to the other agent. We denote the set of these models by Mj,l-1. A model in the model node may itself be an I-ID or ID, and the recursion terminates when a model is an ID or a simple probability distribution over the actions. Formally, we denote a model of j as, mj,l-1 = 〈bj,l-1, ˆ θj〉, where bj,l-1 is the level l - 1 belief, and ˆ θj is the agent's frame encompassing the action, observation, and utility nodes. We observe that the model node and the dashed policy link that connects it to the chance node, Aj , could be represented as shown in Fig. 1(b). The decision node of each level l - 1 I-ID is transformed into a chance node. Specifically, if OPT is the set of optimal actions obtained by solving the I-ID (or ID), then Pr(aj ∈ A1j ) = 1 |OP T |

if aj ∈ OPT , 0 otherwise. The conditional probability table (CPT) of the chance node, Aj, is a multiplexer, that assumes the distribution of each of the action nodes (A1j ,A2j ) depending on the value of Mod[Mj]. The distribution over Mod[Mj], is i's belief over j's models given the state.

I-DIDs extend I-IDs to allow sequential decision making over several time steps. We depict a general two time-slice IDID in Fig. 2. In addition to the model nodes and the dashed policy link, what differentiates an I-DID from a DID is the model update link shown as a dotted arrow in Fig. 2. We briefly explain the semantics of the model update next.

The update of the model node over time involves two steps: First, given the models at time t, we identify the updated set of models that reside in the model node at time t + 1. Because the agents act and receive observations, their models are updated to reflect their changed beliefs. Since the set of optimal actions for a model could include all the actions, and the agent may receive any one of |Ωj| possible observations, the updated set at time step t + 1 will have up to |Mtj,l-1 ||Aj||Ωj| models. Here, |Mtj,l-1 | is the number of models at time step t, |Aj| and |Ωj| are the largest spaces of actions and observations respectively, among all the models. The CPT of Mod[M t+1 j,l-1 ] encodes the function,

τ (btj,l-1 , atj , ot+1 j , bt+1 j,l-1 ) which is 1 if the belief btj,l-1 in the model mtj,l-1 using the action atj and observation ot+1 j updates to bt+1 j,l-1 in a model mt+1 j,l-1 ; otherwise it is 0. Second, we compute the new distribution over the updated models, given the original distribution and the probability of the agent performing the action and receiving the observation that led to the updated model. The dotted model update link in the I-DID may be implemented using standard dependency links and chance nodes, as in Fig. 3, transforming it into a flat DID.

2.2 Solution

Solution of an I-DID (and I-ID) proceeds in a bottom-up manner, and is implemented recursively. We start by solving the level 0 models, which may be traditional IDs. Their solutions provide probability distributions which are entered in the corresponding action nodes found in the model node of the level 1 I-DID. The solution method uses the standard look-ahead technique, projecting the agent's action and observation sequences forward from the current belief state, and finding the possible beliefs that i could have in the next time step. Because agent i has a belief over j's models as well, the lookahead includes finding out the possible models that j could have in the future. Each of j's level 0 models represented using a standard DID in the first time step must be solved to obtain its optimal set of actions. These actions are combined with the set of possible observations that j could make in that model, resulting in an updated set of candidate models (that include the updated beliefs) that could describe the behavior of j. Beliefs over these updated set of candidate models are calculated using the standard inference methods through the dependency links between the model nodes.

3 Aggregating Models Using Action Equivalence

As mentioned before, we seek to group at each step those models that prescribe identical actions at that time step. We describe our approach below.

3.1 Policy Graph and Behavioral Equivalence

Solutions of individual I-DIDs and DIDs that represent the models of other agents may be merged to obtain a policy graph. First, note that solutions of the models could be represented as policy trees. Each node in the policy tree represents an action to be performed by the agent and edges represent the agent's observations. The policy trees may be merged bottom-up to obtain a policy graph, as we demonstrate in Fig. 4 using the well-known tiger problem [Kaelbling et al., 1998]. Analogous to a policy graph in POMDPs, each node in the graph is associated with a set of models for which the corresponding action is optimal.

Implicit in the procedure of merging policy trees is the fact that if pairs of policy trees are identical - resulting from behaviorally equivalent models - they are merged into a single representative tree. The following proposition gives the complexity of merging the policy trees to obtain the policy graph.

Proposition 1 (Complexity of tree merge). Worst-case complexity of the procedure for merging policy trees to form a policy graph is O((|Ωj |T-1 )|M0j,l-1 | ) where T is the horizon.

Proof. Complexity of the policy tree merge procedure is proportional to the number of comparisons that are made between parts of policy trees to ascertain their similarity. As the procedure follows a bottom-up approach, the maximum number of comparisons are made between leaf nodes and the worst case occurs when none of the leaf nodes of the different policy trees can be merged. Note that this precludes the merger of upper parts of the policy trees as well. Each policy tree may contain up to |Ωj|T-1 leaf nodes, where T is the horizon. The case when none of the leaf nodes merge must occur when the models are behaviorally distinct. Hence, at most O((|Ωj |T-1 )|M0j,l-1 | ) comparisons are performed.

Intuitively, merging policy trees is analogous to grouping behaviorally equivalent models, whose entire policy trees are similar. The utility of grouping behaviorally equivalent models toward reducing the model space is well known [Rathnas et al., 2006; Pynadath and Marsella, 2007].

3.2 Action Equivalence

Definition

Notice from Fig. 4(b) that the policy graph contains multiple nodes labeled with the same action at time steps t = 0 and t = 1. The associated models while prescribing actions that are identical at a particular time step, differ in the entire behavior. We call these models actionally equivalent. Action equivalence further partitions the model space, Mtj,l-1 , into classes, as we show in Fig. 5(a). If more than one action is optimal for a model, we may break ties randomly.

From Fig. 5(a), the partition of the model set, Mtj,l-1 , induced by action equivalence at time step 0 is {Mt=0,1 j,l-1 , Mt=0,2 j,l-1 }, where Mt=0,1 j,l-1 is the class of models in the model space whose prescribed action at t = 0 is L, and Mt=0,2 j,l-1 is the class of models whose prescribed action at t = 0 is OL. Note that these classes include the behaviorally equivalent models as well. Thus, all models in a class prescribe an identical action at that time step. Furthermore at t = 1, the partition consists of 3 action equivalence classes and, at t = 2, the partition also consists of 3 classes.

Revised CPT of Mod Node

As we mentioned previously, the node Mod[M t+1 j,l-1 ] in the model node M t+1 j,l-1 , has as its values the different models ascribed to agent j at time t + 1. The CPT of Mod[M t+1 j,l-1 ] implements the function τ(btj,l-1 , atj , ot+1 j , bt+1 j,l-1 ), which is 1 if btj,l-1 in the model mtj,l-1 updates to bt+1 j,l-1 in model mt+1 j,l-1 using the action-observation combination, otherwise it is 0. However, now that the models have been aggregated into action equivalence classes, this CPT is no longer valid.

As we see from Fig. 5(a), updating an equivalence class given an action-observation combination may lead into multiple classes at the next time step. For example, updating Mt=0,1 j,l-1 (left class at t = 0) with action L and observation GR leads into the left class with action OL and the middle class with action L at t = 1. Similarly, updating Mt=0,1 j,l-1 with action L and observation GL leads into the middle class with action L and the singleton class with action OR at t = 1. Consequently, the update function, τ, and therefore the CPT of Mod[M t+1 j,l-1 ], is no longer deterministic (an indicator function) but is probabilistic.

The probability, P r(Mt+1,p j,l-1 |Mt,q j,l-1 , atj, ot+1 j ), is zero trivially if atj is not the optimal action for class Mt,q j,l-1 . Otherwise, we show how we may derive the probability of class, Mt+1,p j,l-1 , given Mt,q j,l-1 and an action-observation combination:

P r(mt+1 j,l-1 |mtj,l-1 , atj , ot+1 j ) is equivalent to the τ function and P r(mtj,l-1 |atj , ot+1 j ) simplifies toPr(mtj,l-1 ) after a few simple steps. Hence, we get:

(1)

where bi(mtj,l-1 ) is i's belief over the model of j at t , btj,l-1 is the belief in the model mtj,l-1 , and bt+1 j,l-1 is in model mt+1 j,l-1 . Intuitively, Eq. 1 gives the proportion of the total probability mass assigned to individual models in the class, Mt,q j,l-1 , that update to models in the class,Mt+1,p j,l-1 .

What remains now is how we compute bi(mtj,l-1 ) in Eq. 1. If t = 0, this is straightforward and may be obtained as: bi(m0j,l-1 ) = ∑s Pr(m0j,l-1 |s)Pr(s), where Pr(m0j,l-1 |s) is given in the CPT of the Mod node at time 0. For subsequent time steps, this is a challenge since we have aggregated the individual models into action equivalence classes at time t and have obtained the probability of each class. We may overcome this obstacle by computing the distribution over the individual updated models as in the original I-DID as well and caching it. This is done, of course, before we begin computing the probabilities of equivalence classes. A marginal of the previously cached values over all physical states for the particular model results in the required probability.

We illustrate the application of Eq. 1 to the policy graph of Fig. 5(a) below:

Example For simplicity, let the left action equivalence class, Mt=0,1 j,l-1 , comprise of two models, m1j,l-1 and m2j,l-1 , both of which prescribe action L. Let i's marginal belief over these two models be 0.35 and 0.3, respectively (see Fig. 5(b)). Updating Mt=0,1 j,l-1 using the action-observation combination (L, GR) leads into two classes, Mt=1,1 j,l-1 and Mt=1,2 j,l-1 with the probabilities 0.54 and 0.46, respectively (see Fig. 5(c)). This is because the model m1j,l-1 which updates to the model in Mt=1,1 j,l-1 using (L, GR) has the probability proportion 0.35 0.35+0.3 = 0.54. Model m2j,l-1 which updates to a model in Mt=1,2 j,l-1 has the probability proportion 0.3 0.35+0.3 = 0.46. Similarly, updatingMt=0,1 j,l-1 using the action-observation combination of (L, GL) leads into Mt=1,2 j,l-1 and Mt=1,3 j,l-1 with the probabilities 0.54 and 0.46 respectively.

We point out that the likelihood of performing the action and receiving the observation do not play a role in these probability computations, which are used to populate the revised CPTs of the Mod nodes. Instead, they are used while solving the I-DID for inferring the updated distribution over the aggregated model space at each time step.

In summary, we implement our exact method by revising the model update phase in the procedure for solving IDIDs [Doshi et al., 2009]. We aggregate actionally equivalent models and represent their probabilistic update using the new CPT for the node Mod[M t+1 j,l-1 ].

4 Computational Savings and Optimality

The complexity of exactly solving a level l I-DID is, in part, due to solving the lower-level models of the other agent, and given the solutions, due to the exponentially growing space of models. In particular, at some time step t, there could be at most |M0j,l-1 |(|Aj||Ωj|)t many models, whereM0j,l-1 is the set of initial models of the other agent. Although |M0j,l-1 | models are solved, considering action equivalence bounds the model space to at most |Aj| distinct classes. Thus, the cardinality of the interactive state space in the I-DID is bounded by |S||Aj| elements at any time step. This is a significant reduction in the size of the state space. In doing so, we additionally incur the computational cost of merging the policy trees, which is O((|Ωj|T-1 )|M0j,l-1 | ) (from Proposition 1). We point out that our approach is applied recursively to solve I-DIDs at all levels down to 1.

Analogous to [Rathnas et al., 2006], which showed that considerations of behavioral equivalence do not upset the solution of I-DIDs, we show that aggregating actionally equivalent models preserves the optimality. Since the aggregation affects j's model space only, we prove that the predictive distribution over j's actions remains unchanged at any time step.

Proposition 2 (Optimality). The predictive distribution over j's actions on aggregating the model space due to action equivalence is preserved.

Proof. We prove by showing that for some action, at+1 j , P r(at+1 j ) remains unchanged when Mt+1 j,l-1 is replaced by a partition. Let Mt+1,p j,l-1 be the set of models whose optimal action is at+1 j with probability 1:

Here, we do not show the sum over all atj and ot+1 j for clarity. Notice that Pr(mt+1 j,l-1|mtj,l-1, atj , ot+1 j ) is equivalent to τ(·).

P r(mtj,l-1, atj , ot+1 j ) simplifies to Pr(mtj,l-1) and analogously for P r(Mt,q j,l-1 , atj , ot+1 j ).

Using Eq. 1 we get:

Recall that Mt+1,p j,l-1 is the set whose optimal action is at+1 j . Thus, the last line (with summations not shown) is used to obtain P r(at+1 j ) given the action equivalence classes.

5 Experimental Results

We evaluate our improvement to the exact approach using action equivalence (Exact-AE) in the context of both the multiagent tiger [Nair et al., 2003; Gmytrasiewicz and Doshi, 2005] and a multiagent version of the machine maintenance (MM) problem [Smallwood and Sondik, 1973]. We compare its performance with the previous exact method that uses behavioral equivalence (Exact-BE) [Rathnas et al., 2006] and the exact approach with no refinement (Exact) [Doshi et al., 2009]. We show that Exact-AE solves the I-DIDs more efficiently than its counterparts by comparing the time taken in achieving a level of expected reward. We experimented with both level 1 and level 2 I-DIDs.

In Figs. 6(a) and (b), we show the reward gathered by executing the policy trees obtained from exactly solving the IDIDs for level 1. The time consumed is a function of the initial number of models and the horizon of the I-DID, both of which are varied beginning with |M0 | = 50. We observe that the approaches which aggregate the model space perform significantly better than the traditional exact approach. In particular, these approaches obtain the same reward in much less time because they are able to solve the same I-DID more quickly. However, the time difference between Exact-AE and Exact-BE is not significant, although Exact-AE maintains significantly less number of model classes at each horizon as is evident from Figs. 6(b). This is because solution of level 0 models in our problem domains is fast and Exact-AE incurs the overhead of computing the update probabilities.

The reduced time needed to obtain a level of reward is more evident for level 2 I-DIDs, as we see in Figs. 6(c). Level 2 IDIDs for both the problem domains show a significant speed up in solving them when models are aggregated using action equivalence in comparison to behavioral equivalence. Here, the approaches are recursively applied to the lower level IDIDs that represent models of j, as well.

Finally, as we show in Table 1, we were able to exactly solve level 2 I-DIDs over more than 10 horizons using ExactAE (|M0|=25), improving significantly over the previous approach which could comparably solve only up to 6 horizons.

6 Discussion

I-DIDs provide a general formalism for sequential decision making in the presence of other agents. The increased complexity of I-DIDs is predominantly due to the exponential growth in the number of candidate models of others, over time. These models may themselves be represented as I-DIDs or DIDs. We introduced the concept of action equivalence which induces a partition of the model space. The resultant number of classes is often significantly less in comparison to those obtained by considerations of behavioral equivalence. The empirical performance demonstrates the computational savings provided by this approach and its significant improvement over the previous exact technique. We note that action equivalence could be seen as a less stringent criteria for model aggregation compared to behavioral equivalence, leading to more models in a class and less classes.