
| Individually   | Collectively   | Collectively         | Non-                 |      |
|----------------|----------------|----------------------|----------------------|------|
| Observable     | Observable     | Partially Observable | Observable           |      |
| No Comm        | 2(1)           | 2(1)                 | 2(1)                 | 2(1) |
| General Comm.  | 2(1)           | 0(|S| · | Ω a |) 7   | 0((| S| - | Ω α |) 7 | 2(1) |
| Free Comm.     | 2(1)           |                      | Q(1)                 | Q(1) |

expression that accounts for the difference in future communication costs as well. Thus, the left-hand side captures our intuition that, when not communicating, the team will incur a cost if the agents other than i are unaware of G 's achievement. The right-hand side of the inequality is a summation of the cost of sending the σς message over possible current states and belief states.

We can use Theorem 7 to derive the locally optimal communication decision across various classes of problem domains. Under no communication, we cannot send σς. Under free communication, the right-hand side is 0, so the inequality is always true, and we know to prefer sending σς . Under no assumptions about communication, the determination is more complicated. When the domain is individually observable , the left-hand side becomes 0, because all of the agents know that G has been achieved (and thus there is no difference in execution when sending σ G ). Therefore, the inequality is always false (unless under free communication ), and we prefer not sending σς . When the environment is not individually observable and communication is available but not free, then, to be locally optimal at time to, agent i must evaluate Inequality 16 in its full complexity.  Since the inequality sums rewards over all possible sequences of states and observations, the time complexity of the corresponding algorithm is O (( | S | · | ) T ). While this complexity is unacceptable for most real-world problems, it still provides an exponential savings over searching the entire policy space for the globally optimal policy, where any agent could potentially send σ G at times other than T G . Table 3 provides a table of the complexity required to determine the locally optimal policy under the various domain properties.

We can now show that although Theorem 7's algorithm for locally optimal communication provides a significant computational savings over finding the global optimum, it still outperforms existing teamwork models, as exemplified by our π x and π δ x policies. First, we can use the criterion of Theorem 7 to evaluate the optimality of the policy, π j x . If AT (to,i, β) ≥ 0 for all possible times to, agents i, and belief states β that are consistent with the achievement of the goal G, then the locally optimal policy will always specify sending σ G . In other words, π f x will be identical to the locally optimal policy. However, if the inequality of Theorem 7 is ever false, then π g x is not even locally, let alone globally, otimal.

Second, we can also use Theorem 7 to evaluate STEAM by viewing STEAM's inequality, T C mt > C c t as a crude approximation of Inequality 16. In fact, there is a clear correspondence between the terms in the two inequalities. The left-hand side of Inequality 16 computes an exact expected cost of miscoordination. However, unlike STEAM's monolithic r parameter, the optimal criterion evaluates a complete probability distribution over all possible states of miscoordination by considering all possible past sequences consistent with