the set of possible belief states for the agent. Thus, we define the set of possible domainlevel policies as mappings from belief states to actions, π i A : B i → A i . We define the set of possible combined belief states over all agents to be Ba = Π i εα B i . The corresponding random variable, b t , represents the agents' combined belief state at time t . We elaborate on different types of belief states and the mapping of observations to belief states (i.e., the state estimator function) in Section 2.2.1.

## 2.1.5 Reward Function: R

A common reward function is central to the notion of teamwork in a MTDP: R : S × A o →
R. This function represents the team's joint preferences over states and the cost of domainlevel actions (e.g., destroying enemy is good, returning to home base with only 10% of original force is bad). We assume that, as selfless team members, each agent shares these preferences at the individual level as well. Therefore, each team member wants exactly what is best for the team as a whole.

## 2.2  Extension For Explicit Communication:  Σα

We make an explicit separation between domain-level actions ( A g ) and communicative actions. As defined in this section, communicative actions affect the receiving agents' individual belief states, but, unlike domain-level actions, they do not directly change the world state. Although this distinction is sometimes blurry in real-world domains, we make this explicit separation so as to isolate, as much as possible, the effects of the two types of actions. The leverage gained from this separation provides the basis for the informative, analytical results presented in the rest of this paper. To capture this separation, we extend our initial MTDP model to be a communicative multiagent team decision problem (COM- MTDP), that we define as a tuple, (S, Ag, Zg, P, Qg, Og, Bg, R), with a new component, Xa, and an extended reward function, R.

## 2.2.1 Communication: Σα

{}iea is a set of possible messages for each agent, implicitly defining a set of combined communications, Σ α ≡ Π iεα Σ i . An agent, i, may communicate message x ∈ Σ i to its teammates, who interpret the communication by updating their belief states in response. As a first step in this work, we assume that all of the agents receive the messages instantaneously and correctly (i.e., there is no lag or noise in the communication channels). This model is common knowledge among all of the team members, so once an agent has sent a message, it knows that its team members have received the message, and its team members know that it knows that they have all received the message, and so on.

With communication, we divide each decision epoch into two phases: the pre-communication and post-communication phases, denoted by the subscripts ●Σ and Σ●, respectively. In particular, the agents update their belief states at two distinct points within each decision epoch: once upon receiving observation Ω (producing the pre-communication belief state H x ), and again upon receiving the other agents' messages (producing the postcommunication beliefstate t x . ). The distinction allows us to differentiate between the belief state used by the agents in selecting their communication actions and the more "up-to-date" belief state used in selecting their domain-level actions. We also distinguish between the