
| Algorithm      | MABC   | MA-tiger   |      |      |      |
|----------------|--------|------------|------|------|------|
| κ              | 3      | 4          | 5    | 3    | 4    |
| MILP-Dec       | 0.86   | 900        | −    | 3.7  | ·    |
| MILP-Dec(u)    | 1.03   | 907        | −    | 3.5  | ·    |
| MILP-Dec(ℓ)    | 0.93   | 900        | −    | 4.9  | 72   |
| MILP-Pr-Dec    | 0.84   | 80         | ·    | 6.4  | ·    |
| MILP-Pr-Dec(u) | 0.93   | 10.2       | 25   | 6.2  | ·    |
| MILP-Pr-Dec(ℓ) | 0.84   | 120        | ·    | 7.6  | 175  |
| DP             | 5      | 103        |      |      |      |
| MAA∗           | t3     | t4         | t3   | t4   |      |
| PBDP           | 1.0    | 2.0        | 105  | t3   | t4   |
| DP-JESP        | 0      | 0.02       |      |      |      |
| Approx-DP      | 0.05   | 1.0        |      |      |      |
| MBDP           | 0.01   | 0.01       | 0.02 | 0.46 | 0.72 |

the set of joint-sequences of length t. Let qoa denote the joint-sequence obtained on appending the joint-observation o and the joint-action a to the joint-sequence q.

$$\begin{array}{r l}{{\mathrm{maximize}}}&{{u=\sum_{q\in{\mathcal{S}}^{*}}y[q]\quad{\mathrm{s.t.}}\colon}}\\ {{}}&{{}}\\ {{\sum_{a\in A}y[a]=1}}\\ {{}}&{{}}\\ {{y[q]-\sum_{a\in A}y[q o a]=0,\forall\,t<\kappa,\,q\in{\mathcal{S}}^{t},\,o\in\Omega}}\\ {{}}&{{}}\\ {{y\geq0}}\end{array}$$
$$(32)$$
$$(33)$$
(34)  $\binom{35}{2}$  . 
A bound is added to MILP-Dec by adding a constraint. The constraint f(y) ≥ ℓ is added for adding the lower bound and the constraint f(y) ≤ u is added for adding the upper bound.

## 7 Experiments

We formulated the MABC problem and MA-tiger problem as MILPs, and solved it using the ILOG Cplex 10 solver on an Intel P4 machine with 3.40 gigahertz processor speed and 2.0 GB ram. The runtime in seconds of MILP-Dec and MILP-Pr-Dec for different values of κ is shown in Table 1. In the first column, a parenthesis, if present indicates which bound is used. The runtime includes the time taken to identify dominated sequences and compute the bound (for e.g., solve the LP for the Pomdp),