satisfied by a vector in R
|Si|if it is to represent a κ-policy. Given a sequence p, an action a and an observation o, let poa denote the sequence obtained on appending o and a to the end of p. Let S
′
i denote the set S
1 i ∪ S2 i ∪ **. . .** S
κ−1 i.

Definition 2 Let |Si| = z*. A vector* w ∈ R
zis a κ*-step, possibly stochastic, policy of* the i*th agent if,*

$$\sum_{a\in A_{i}}w[a]=1\tag{1}$$ $$w[p]-\sum_{a\in A_{i}}w[poa]=0,\quad\forall\;p\in{\cal S}^{\prime}_{i},\,o\in\Omega_{i}$$ (2) $$w\geq0\tag{3}$$

We call the system of linear equations (1)-(3) the policy constraints of the i*th agent*.

Policy constraints recreate the tree structure of a policy. They appear in a slightly different form, as Lemma 5.1 in [6]. We can write the policy constraints in the matrix form as Ciw = bi, w ≥ 0, where Ciis the matrix of the coefficients of the variables in the equations (1)-(2) and biis a vector of appropriate length whose first element is 1 and the remaining elements are 0, representing the r.h.s of the equations. Note that it is implicit in the above definition that the value of each element of w is constrained to be in the interval [0,1]. Hence, we can define a deterministic κ-policy of the ith agent as follows.

## Definition 3 A Vector Xi ∈ Xiis A Κ-Policy Of The Ith Agent If Cixi = Bi.

We shall call a policy represented as a vector as a *policy-vector* just to distinguish it from a policy-tree. The representation of a policy as a policy-vector is in fact the sequence-form representation we have been alluding to. Given a vector from xi ∈ Xi which satisfies the policy constraints, the agent can use it just as he would use as a policy-tree without requiring any additional book-keeping. Let choosing a sequence mean taking the last action in the sequence. In using xi, at the first step, he chooses the action a such that xi[a**] = 1**. There will be only one such action. Then on receiving an observation, say o, he chooses the sequence aoa′such that xi[aoa′**] = 1**. Again there will be only one such sequence. In general, if at step t he has chosen the sequence p and then received the observation o, then he chooses the unique sequence poa′′ such that xi[poa′′**] = 1** at the (t **+ 1)**th step. Thus, at each step, the agent must know the sequence of actions he has taken and the sequence of observations he has received till that step in order to know which action to take according to xi. This requirement is called *perfect recall* in game theory, and it is implicit in the use of a policy-tree.

## 3.3 Advantage Of The Sequence-Form Representation

The size of S
t i is |Ai| t|Ωi| t−1. The size of Siis thus Pκ t=1 |Ai| t|Ωi| t−1, exponential in κ. Since every κ-policy is in theory available if the set Siis available, the latter serves as a *search space* for κ-policies of the ith agent. The good news is of course that this search space is only exponential in κ. This compares favorably with the search space represented by the set of κ-policy-trees which is doubly exponential in κ. We thus