the agent's current beliefs. Likewise, unlike STEAM's monolithic Cmt parameter, the optimal criterion looks ahead over all possible future sequences of states to determine the true expected cost of miscoordination. Furthermore, we can view STEAM's parameter, C c , as an approximation of the communication cost computed by the right-hand side of Inequality 16. Again, STEAM uses a single parameter, while the optimal criterion computes an expected cost over all possible states of the world.

STEAM does have some flexibility in its representation, because C mt, τ, and C c are not necessarily fixed across the entire domain. For instance, C mt may vary based on the specific joint plan that the agents may have jointly committed to (i.e., there may be a different C mt for each goal G ). Thus, while Theorem 7 suggests significant additional flexibility in computing C mt through explicit lookahead, the optimal criterion derived with the COM-MTDP model also provides a justification for the overall structure behind STEAM's approximate criterion. Furthermore, STEAM's emphasis on on-line computation makes the computational complexity of Inequality 16 (as presented in Table 3) unacceptable, so the approximation error may be acceptable given the gains in efficiency. For a specific domain, we can use empirical evaluation (as demonstrated in the next section) to quantify the error and efficiency to precisely judge this tradeoff.

## 5.  Empirical Policy  Evaluation

In addition to providing these analytical results over general classes of problem domains, the COM-MTDP framework also supports the analysis of specific domains. Given a particular problem domain, we can construct an optimal communication policy or, if the complexity of computing an optimal policy is prohibitive, we can instead evaluate and compare candidate approximate policies. To provide a reusable tool for such evaluations, we have implemented the COM-MTDP model as a Python class with domain-independent methods for the evalution of arbitrary policies and for the generation of both locally optimal policies using Theorem 7 and globally optimal policies through brute-force search of the policy space. This software is available in Online Appendix 1.

This section presents results of a COM-MTDP analysis of an example domain involving agent-piloted helicopters, where we focus on the key communication decision faced by many multiagent frameworks (as described in Section 4), but vary the cost of communication and degree of observability to generate a space of distinct domains with different implications for the agents' performance. By evaluating communication policies over various configurations of this particular testbed domain, we demonstrate a methodology by which one can use the COM-MTDP framework to model any problem domain and to evaluate candidate communication policies for it.

## 5.1 Experimental Setup

Consider two helicopters that must fly across enemy territory to their destination, as illustrated in Figure 1. The first, piloted by agent Transport, is a transport vehicle with limited firepower. The second, piloted by agent Escort, is an escort vehicle with significant firepower. Somewhere along their path is an enemy radar unit, but its location is unknown
(a priori) to the agents. Escort is capable of destroying the radar unit upon encountering it. However, Transport is not, but it can escape detection by the radar unit by traveling