

![0_image_0.png](0_image_0.png)

other agents during the κ steps, at each step he takes actions strictly as a function of the actions he has taken previously and observations he has received previously. This function is called his *policy*. To control the Dec-Pomdp for κ steps, each agent requires a κ-step policy, henceforth written as κ-policy. The tuple of the agents' policies forms a *joint-policy*. An optimal joint-policy is one which maximizes E(Pκ t=1 rt), the sum of expected rewards the agents obtain for the κ steps.

## 2.1 Policy In The Tree-Form

The canonical representation of a policy, used in existing Dec-Pomdp algorithms, is the tree-form. In this form, a κ-policy of the ith agent can be represented as a rooted tree with κ levels in which each non-terminal node has |Ωi| children. This tree is called a κ-policy-tree. Each node is labeled by an action to take and each edge is labeled by an observation that may occur. Using a policy-tree, during the control, the agent follows a path from the root to a leaf depending on the observations he receives. An example of a policy-tree is shown in Figure 1. The number of nodes in a κ-policy-tree of the ith agent is |Ωi| κ−1 |Ωi|−1
. It is thus exponential in κ. For example, with |Ωi| = 2, a 3-policytree, as the one shown in Figure 1, has 2 3−1 2−1 = 7 nodes. The set of κ-policy-trees of the ith agent is the set of all the |Ωi| κ−1 |Ωi|−1 sized permutations of the actions in Ai. Therefore,

```
the size of the set of κ-policy-trees of the ith agent is |Ai|
                                                               |Ωi
                                                                 
                                                                  |κ−1
                                                               |Ωi
                                                                  
                                                                  |−1, doubly exponential

```

in κ.

## 3 Policy In The Sequence-Form

The double exponentiality associated with the set of policy-trees can be avoided by using the *sequence-form* representation of a policy. We begin a description of this representation by defining a sequence.

Definition 1 A sequence of length t of the ith agent is an ordered list of 2t *- 1 elements,*
t ≥ 1, in which the elements in odd positions are actions from Ai and those in even positions are observations from Ωi.

Thus, in a sequence of length t there are t actions and t - 1 observations. The shortest possible sequence is of length 1, which consists of just an action and no observations.