of Koller's approach (and therefore of our approach) is that the size of the set of sequences from each subset is drawn is only exponential in the horizon and not doubly exponential in it, as is the case with the size of the set of policy trees. This allows us to formulate an MILP whose size is exponential in κ and n. For small problems such as MA-Tiger and MABC, it is feasible to represent the MILP in memory. Furthermore, and equally importantly, the constraints matrix of the MILP is *sparse*. The consequence of this is that in practice the MILP is solved very quickly (in the order of seconds). Thus, we have an effective method to compute an optimal deterministic finite-horizon joint-policy. Restricting attention to deterministic joint-policies does not limit the applicability of our approach in any way since in every finite-horizon DecPomdp there exists at least one optimal joint-policy that is deterministic. It is also not evident that relaxing this restriction has any benefit. Implicitly, existing algorithms also restrict attention to deterministic joint-policies. In this paper 'policy' and 'joint-policy' shall mean deterministic policy and deterministic joint-policy respectively unless otherwise specified.

## 2 The Finite-Horizon Dec-Pomdp Problem

A finite-horizon Dec-Pomdp problem is defined by the following elements. We are given N, a set of n agents and S, a set of states. The n agents in N are numbered from 1 to n. The states are numbered from 1 to |S|. For each ith agent, we are given Ai, the agent's set of actions and Ωi, his set of observations. The cross-product A1 × A2 **. . .** ×
An is called the set of *joint-actions* and it is denoted by A. Similarly, the cross-product Ω1 × Ω2 **. . .** × Ωn is called the set of *joint-observations* and it is denoted by Ω. The joint-actions are numbered from 1 to |A| and the joint-observations are numbered from 1 to |Ω|. Then, we are given for each ath joint-action, the matrices T
a, Z
aand the vector Ra:
(a) T
a ss′ is the probability of transitioning to the s
′th state if the agents take the ath joint-action in sth state.

(b) Z
a s
′o is the probability of the agents receiving the oth joint-observation and transitioning to s
′th if they take the ath.

(c) Ra s is the real-valued reward the agents obtain if they take the ath joint-action in the sth state.

We are given b0, which represents the initial *belief state* and it is common knowledge amongst the agents. A belief state is a probability distribution over S. In a belief state b, the probability of the sth state is denoted by b[s]. Finally, we are given κ ≥ 1, a finite number that is the *horizon* of the control. The control of the Dec-Pomdp is described as follows. At each step t of κ steps: the agents take a joint-action, they receive a joint-observation, they receive a common reward rt, and the process transitions to a new belief state as a function of the previous belief state, the joint-action and the jointobservation. However, at each step, agents do not reveal to one another the actions they take and observations they receive at that step or at previous steps. Since an agent does not know the actions taken by the other agents and the observations received by the