cannot divulge to the other agents. The agents' private information can have an impact on what they collectively do. Thus, *before* the control begins, each agent must reason not only about the possible states of the process during the control (as in a Pomdp) but he must also reason about the information that *could* be held by other agents during the control. In effect, the agent must also reason about which policies the other agents would use. Partial observability and decentralization make Dec-Pomdps very difficult to solve. Finding an optimal solution to a Dec-Pomdp is NEXP-hard in the number of agents [1]; finding a locally optimal solution to a Dec-Pomdp is NP-hard in the size of the Dec-Pomdp problem (determined by κ and the sizes of the sets of joint-actions and joint-observations) [5].

## 1.1 Motivation For A New Approach

The three existing exact algorithms DP [4], MAA∗[11] and PBDP [10] are able to solve only very small Dec-Pomdps in reasonable time (2 agents, horizon ≤ 4, action and observation set sizes ≤ 3). Their lack of scalability is predictable from the negative complexity results. Therefore, the question is not so much whether these algorithms can be improved upon in the absolute, but rather if a relative improvement can be achieved. In other words, can we push the computational envelop a bit further on this problem? In this paper, we present a new approach based on *integer programming*, which does manifest a much superior performance in practice than the existing algorithms. For instance, through our approach, the multi-agent Tiger problem [8] for horizon 4 can be solved in 72 seconds as against the few hours required by the PBDP
algorithm [10] (the only current algorithm able to solve this instance). Similarly, the MABC problem [4] for horizon 5 is solved in 25 seconds as against the 105seconds required by PBDP. So we might tentatively answer in the positive to the above question. There is of course a more relevant reason for pushing this envelop. The three algorithms serve as a basis for approximate algorithms such as Approximate-DP [3]
and MBDP [9], and these seem to scale to much longer horizons and to much larger problems. So, a more efficient exact algorithm is important from this perspective as well. We discuss this in more detail in the last section.

## 1.2 A New, Mixed Integer Programming Approach

Existing Dec-Pomdp algorithms represent an agent's policy as a *tree* and a joint-policy as a tuple of policy-trees. The size of the set of policy-trees of each agent is doubly exponential in the horizon. Hence, the set of joint-policies is doubly exponential in the horizon and exponential in the number of agents. This adversely impacts the space and time requirements of the algorithms. In our approach we discard the tree representation in favor of the *sequence-form* representation which was introduced in a seminal paper on computational game theory [6]. In the sequence-form, every finite-horizon deterministic policy of an agent can be represented as a *subset* of the set sequences of actions and observations of the agent. The problem of finding an optimal *deterministic* joint-policy is thus equivalent to the problem of finding for each agent a subset from a larger set. This problem thus becomes an instance of *combinatorial optimization* and we conceive a mixed integer linear program (MILP) to solve it. The key insight