Jilles S Dibangoye
email: gdibango@ift.ulaval.ca

Brahim Chaib-Draa

Abdel-Illah Mouaddib

Policy Iteration Algorithms for DEC-POMDPs with Discounted Rewards

Over the past seven years, researchers have been trying to find algorithms for the decentralized control of multiple agent under uncertainty. Unfortunately, most of the standard methods are unable to scale to real-world-size domains. In this paper, we come up with promising new theoretical insights to build scalable algorithms with provable error bounds. In the light of the new theoretical insights, this research revisits the policy iteration algorithm for the decentralized partially observable Markov decision process (DEC-POMDP). We derive and analyze the first point-based policy iteration algorithms with provable error bounds. Our experimental results show that we are able to successfully solve all tested DEC-POMDP benchmarks: outperforming standard algorithms, both in solution time and policy quality.

INTRODUCTION

In recent years, there has been increasing interest in finding scalable algorithms for solving multiple agent systems where agents cooperate to optimize a joint reward function, while having different individual observations. To formalize and solve such problems, [START_REF] Daniel | The complexity of decentralized control of Markov decision processes[END_REF] suggest a model that enables a set of n agents to cooperate in order to control a partially observable Markov decision process. This framework can model environments under three constraints: uncertainty, partial observability and decentralization: uncertainty relies on the fact that the agents are imperfectly informed about action effects during the simulation; partial observability means that agents are imperfectly informed about the state of the process during the execution; and decentralization signifies that the agents are differently imperfectly informed during the execution. An environment that concurrently involves these three constraints is known as a decentralized partially observable Markov decision process (DEC-POMDP). Unfortunately, finding either optimal or even ε-approximate solutions of such problems has been shown to be particularly hard [START_REF] Seuken | Formal models and algorithms for decentralized decision making under uncertainty[END_REF].

While some important progress has been made for solving finite horizon DEC-POMDPs, we still lack efficient algorithms with provable error bounds for the infinite horizon case. Indeed, the unique ε-optimal algorithm for the infinite horizon case runs quickly out of memory [START_REF] Daniel | Policy iteration for decentralized control of Markov decision processes[END_REF], as do optimal algorithms for the finite horizon case. This is mainly because they require the exhaustive enumeration of all possible joint policies at each time step, i.e., the exhaustive backup. Unfortunately, the resulting set of joint policies requires an exponential space with respect to the number of joint AAMAS 2009 Workshop on Multi-agent Sequential Decision-Making in Uncertain Domains, May 11, 2009, Budapest, Hungary. observations and the number of agents. As a result, many attempts to solve infinite horizon DEC-POMDPs rely on memorybounded algorithms [START_REF] Amato | Optimizing memory-bounded controllers for decentralized POMDPs[END_REF][START_REF] Daniel | Bounded policy iteration for decentralized POMDPs[END_REF][START_REF] Szer | An optimal best-first search algorithm for solving infinite horizon DEC-POMDPs[END_REF]. These locally optimal algorithms use a fixed amount of memory, i.e., the size of the solution is fixed prior to the execution of the algorithm. Even though the size of the solution is bounded, memory-bounded algorithms still suffer from the proved complexity of the problem. Moreover, choosing the right size for the solution is not obvious and dynamically adjusting it may raise non-negligible computation costs. Furthermore, though these algorithms tackle the space complexity efficiently, the time complexity remains too high and limits their ability to scale to medium solution sizes. Even more importantly, they fail to provide guarantees on the policy quality. Rather than constraining the size of the solution prior to the execution of the algorithm, it is equally possible to come up with a policy within a bound of the optimal policy.

In this paper, we design policy iteration (PI) algorithms that provide many desirable properties that current infinite horizon solvers lacked. First of all, we define exact and approximate Dynamic Programming (DP) backup operators that enable us to compute an improved value function. Secondly, we build up the joint policy based on the improved value function, this circumvents the problem of the exhaustive backup. Finally, we state and prove approximation error bounds on the resulted policy quality. The difficulty of this work lies in the definition of backup operators that guarantee: (1) the decentralization is preserved over the updates of the value function and the transformations of the corresponding policy while avoiding the exhaustive backup; (2) the updates of the value function are essentially DP updates. To leverage the first issue, we introduce new multi-agent concepts namely basis objects and sets, i.e., partial joint information of the team that is sufficient to satisfy the decentralization. Even more importantly, these concepts help circumventing the problem of the exhaustive backup. To handle the second point, we perform essentially a single-agent DP update and keep track only on the value function that satisfies the decentralization.

BACKGROUND AND RELATED WORK

We review the DEC-POMDP model and the associated notation, and provide a short overview of the state-of-the-art algorithms.

The DEC-POMDP Model

DEFINITION 1. A n-agent DEC-POMDP can be represented using a tuple (I , S, {A i }, P, {Ω i },O, R), where: I is a finite set of agents indexed by 1 • • • n; S = {s} is a finite set of joint states; A i denotes a finite set of actions available for agent i , and A = ⊗ i ∈I A i is the set of joint actions, where a = (a 1 , • • • , a n ) denotes a joint action; P : S × A → △S is a Markovian transition function. P (s ′ |s, a) denotes the probability of transiting from state s to state s ′ when taking action a; Ω i defines a finite set of observations available for agent i , and

Ω = ⊗ i ∈I Ω i is the set of joint-observations, where o = (o 1 , • • • , o n ) is a joint observation; O : A × S → △Ω is an ob- servation function. O(o|a, s ′
) denotes the probability of observing joint observation o given that joint action a was taken and led to state s ′ ; R : A × S → ℜ is a reward function. R(a, s) denotes the reward signal received when executing action a in state s; Optimization criterion. The DEC-POMDP model is parameterized by: b 0 ∈ △S, the initial belief distribution, i.e., the team belief over its initial state. The belief state (belief for short) b ∈ △S defines a probability distribution of the team over the underlying states. The next belief, denoted b a,o = τ(b, a, o), that incorporates the latest joint action-observation pair (a, o) and the current belief b, is updated as follows:

b a,o (s ′ ) = ηO(o|s ′ , a) s b(s)P (s ′ |s, a) ( 1
)
where η is a normalizing constant. When the agents operate over an unbounded number of time-steps, the DEC-POMDP has a discount factor, γ ∈ [0, 1). This model is coined by the term infinitehorizon DEC-POMDP with discounted rewards. Solving such a DEC-POMDP means finding a joint policy δ that yields the highest expected value V δ (b 0 ) = max δ E ∞ τ=0 γ τ R(a τ , s τ )|b 0 , δ where V δ (b) denotes the expected sum of discounted rewards obtained given that joint policy δ is executed starting in belief b. Given the definition, the true value of a starting belief b at time step τ, which we write V τ (b), is just V δ * τ (b) -where δ * τ is an optimal policy at time step τ. Since finding an ε-optimal joint policy is known to be intractable, we therefore state our optimization criterion as finding the best joint policy based on a small set of representative beliefs B and the amount of time that is allotted to the algorithm. With this criterion, we want to design novel infinite horizon DEC-POMDP algorithms that update alternatively all, a belief set B τ , the optimal value function V τ over B τ and the corresponding joint policy δ τ , until Bellman residual, i.e., V τ -V τ-1 ∞ , is less or equal to 2εγ/(1 -γ). That is the returned joint policy is an ε-optimal policy with respect to belief space B .

Policy representation. Throughout the paper, a policy for single agent i , deterministic finite state controller (DFSC), can be represented as policy graph δ i = (X i , π, η, x i 0 ), where X i = {x i } denotes a set of machine states; π(x i ) is the individual action a i selected in machine state x i ; η(x i , o i ) is the successor machine state when individual observation o i is perceived in machine state x i ; and x i 0 is the starting machine state. We denote a joint policy, deterministic joint finite-state controllers ( DJFSC ) by δ. A DJFSC can also be represented as joint policy graph δ = (X , π, η, x 0 ), where: X := ⊗ n i =1 X i denotes a set of machine states; π(x), η(x, o) and x 0 are defined as for DFSCs. This contrasts with the standard representation based on policy vectors, i.e., vectors of individual policies, one for each agent. Each joint machine state x is associated to a hyperplane α x -that is the vector value that denotes the expected sum of discounted rewards obtains when executing δ starting in machine state x.

Related Work

In this section, we first present POMDP relevant work that we use as a foundation for our PI algorithms. Then, we discuss the state-of-the-art ε-optimal approach to solving infinite horizon DEC-POMDPs.

Policy Iteration for POMDPs. A special case of DEC-POMDP, in which each agent shares its private information with its teammates at each time step, is called a multi-agent POMDP (MPOMDP). Because all the information available to the team at each time step is known, MPOMDPs can be solved using single-agent POMDP techniques. Over the past few years, exact and approximate PI algorithms have been proposed for POMDPs by [START_REF] Sondik | The optimal control of partially observable Markov decision processes over the infinite horizon : Discounted cost[END_REF][START_REF] Hansen | An improved policy iteration algorithm for partially observable mdps[END_REF] and [START_REF] Ji | Point-based policy iteration[END_REF], respectively. These algorithms, summarized in Algorithm 1, share the same structure that consists of a threefold method: first, compute the value function V τ of the current DJFSC δ τ (policy evaluation); secondly, update the value function V τ represented by a set Γ τ+1 of hyperplanes into an improved value function V τ+1 represented by a set Γ τ of hyperplanes (policy improvement); and finally, transform the current DJFSC δ τ-1 into an improved DJFSC δ τ (policy transformation) with respect to Γ τ+1 . These processes alternate until a convergence criterion is reached. The policy evaluation step is straightforward when a policy is represented as a DJFSC [START_REF] Hansen | An improved policy iteration algorithm for partially observable mdps[END_REF]. This can be achieved by solving the system of linear equations:

α x (s) = R(s, π(x)) + γ s ′ ,o P (s ′ |s, π(x))O(o|s ′ , π(x))α η(x,o) (2)
where x and η(x, o) are machine states. In addition, the policy improvement step relies on the fact that a POMDP can be reformulated as a belief MDP. Indeed, it is well-known that in POMDPs the belief is a sufficient statistic for a given history. Therefore, the value function V τ can be updated using DP. [START_REF] Smallwood | The optimal control of partially observable Markov decision processes over a finite horizon[END_REF] show how to implement the DP update of a value function V τ by exploiting its piece-wise linearity and convexity. Because the value function is a mapping over a continuous |S|-dimensional space, V τ+1 cannot be directly computed. Instead, the corresponding set Γ τ+1 can be generated through a sequence of operations over Γ τ .

Algorithm 1 Policy Iteration 1: procedure PI(initial policy: δ 0 , belief space: B ) 2:

Initialization: δ τ+1 = δ τ = δ 0 3: repeat 4:
% policy evaluation

5:

Compute Γ τ ← {α i }, i.e., value function of δ τ

6:

% policy improvement

7:

Γ τ+1 ← BACKUP(Γ τ , B ) where B may be △S

8:

% policy transformation: δ τ → δ τ+1

9:

Re-initialization: τ = τ + 1 10:

until V τ+1 -V τ ∞ ≤ 2εγ/(1 -γ)
DP update. We now describe the straightforward implementation of DP update for POMDPs [START_REF] Sondik | The optimal control of partially observable Markov decision processes[END_REF]. First, we generate intermediate sets Γ a, * and Γ a,o ∀a, o (Step 1): Γ a, * ← α a, * (s) = R(s, a) and

Γ a,o ← α a,o i (s) = s ′ P (s ′ |s, a)O(o|s ′ , a)α i (s ′ ), ∀α i ∈ Γ τ . Next, we create Γ a (∀a ∈ A), the cross-sum over joint observations, which includes one α a,o from each Γ a,o (Step 2): Γ a ← Γ a, * ⊕ o∈Ω Γ a,o .
Finally, we take the union of Γ a sets (Step 3):

Γ τ+1 = ∪ a∈A Γ a .
It is often the case that a hyperplane in Γ τ+1 is completely dominated by another hyperplane (α•b ≤ α ′ •b, ∀b) or by combination of other hyperplanes. Those hyperplanes can be pruned away at each steps of the update without affecting the policy quality. Finally, [START_REF] Hansen | An improved policy iteration algorithm for partially observable mdps[END_REF] suggests a number of rules that enables us to transform the current policy δ τ into an improved one δ τ+1 . To the best of our knowledge, there is no known techniques that extend completely this approach to multiple agent settings.

Policy Iteration for DEC-POMDPs. [START_REF] Daniel | Policy iteration for decentralized control of Markov decision processes[END_REF] proposed recently an attempt to extend PI from single-agent into decentralized multiagent settings. This algorithm builds over a series of steps a vector of stochastic finite state controllers, one for each agent. Each step consists of a twofold method: the exhaustive backup and the pruning of dominated stochastic machine states. For each agent i , the exhaustive backup takes as input the current set of stochastic machine states X i τ . Then, it builds new stochastic machine states X i τ+1 for all possible joint actions, such that the successor links of the new stochastic machine state are associated only to stochastic machine states that appear in the current sets. The resulted set of stochastic machine states X i τ+1 is exponential with respect to the number of observation, i.e.,

|X i τ+1 | = |A i ||X i τ | |Ω i | + |X i τ |. Thus, the joint stochastic controller grows by n i =1 |A i ||X i τ | |Ω i |
, which grows exponentially with n. Thereafter, a pruning step eliminates dominated stochastic machine states without loosing the ability to eventually converging to an ε-optimal controller. Performing this pruning step, however, can be extensive since they require a linear program and its dual. While interesting, this PI algorithm laks many desirable properties of the PI algorithm in single-agent settings. Among many, the algorithm fails to define a DP backup operator for the decentralized multi-agent case. This would enable us to derive the Bellman residual V τ -V τ-1 ∞ -distance between two successive value functions and even more importantly approximation error bounds. Furthermore, as already discussed in the POMDP section, dominated stochastic machine states can be pruned away at earlier steps of the backup. Doing so, would avoid the exhaustive generation of all possible stochastic machine states which is expensive.

POLICY ITERATION REQUIEREMENTS

In order to extend PI algorithms along with its properties from single-agent to the decentralized multi-agent settings, we need to face two key issues. As we aim at finding a policy for DEC-POMDPs, we need to make sure that our backup operator H B transforms set Γ τ into an improved set Γ τ+1 while preserving the decentralization -that is all hyperplanes α ∈ Γ τ+1 and the improved policy δ τ+1 satisfy the decentralization constraint. On the other hand, to inherit POMDP properties our backup operator need essentially to be the DP backup operator -that is the value

V τ+1 (b) at belief b depends on values V τ (b ′ ) of its successor be- liefs b ′ : V τ+1 (b) = H B V τ (b) = max a E R(a, b) + γ o V τ (τ(b, a, o)) .

Satisfying the Decentralization

In this section, we introduce new multi-agent planning concepts namely basis objects and sets. These concepts help preserving the decentralization while updating hyperplanes or transforming policies.

Preliminary definitions. A set of basis joint observations also called basis set and denoted Ω ⊆ Ω is a set of joint observations of the smallest size where each individual observation of any agent, e.g., o i ∈ Ω i , is included in at least one joint observation of the basis set, e.g.,

(• • • , o i , • • • ) ∈ Ω.
Because all individual observations of all agents are represented in at least one joint observation of the basis set, the cardinality of a basis set Ω, denoted κ(Ω) (κ for short), is given by:κ = | Ω| = max i ∈I |Ω i |. This holds for any basis set and even more importantly for any number of agents. In the remainder of the paper, we assume that each agent has the same number of individual observations 1 . Therefore, a straightforward way of building a basis set Ω is to include the largest set of joint observations such that any pair of joint observations is component-wise different, e.g., (o 1 , o 2 ) and (o 2 , o 1 ). A basis object is any object, e.g., policy or hyperplane, defined only over basis observations. A basis joint policy δ B : Ω * → A is a DJFSC defined only over basis joint observations. A basis hyperplane is a vector of hyperplanes, one for each basis joint observation. We call the complement hyperplane, a vector of hyperplanes, one hyperplane for each non basis joint observation o ∈ Ω\ Ω. Any object that satisfies the decentralization constraint is said to be valid.

Valid policies. We introduce below a criterion that checks whether a DJFSC δ satisfies the decentralization constraint, i.e., it is a valid policy. LEMMA 1. A DJFSC δ = (X , π, η, x 0 ) satisfies the decentralization constraint if and only if it corresponds to a vector of DFSCs

(δ 1 , • • • , δ n ) such that: ∀x ∈ X , ∃(x 1 , • • • , x n ) : π(x) = (π(x 1 ), • • • , π(x n )) and η(x, o) = (η(x 1 , o 1 ), • • • , η(x n , o n )) where o = (o 1 , • • • , o n ) and δ i = (X i , π, η, x i 0 ).
This lemma states that the joint action taken for a given sequence of joint observations when the vector of DFSCs (δ 1 , • • • , δ n ) is executed is exactly the joint action taken when δ is executed after perceiving the same sequence of joint observations. Now we are ready to claim our main theorem. THEOREM 1. The basis DJFSC δ B is the sufficient information to build a DJFSC δ that is valid. To prove this we suggest a constructive two-step method that builds a unique DJFSC δ based on δ B : first, we build the unique vector of DFSCs associated with a basis δ B . To do so, we extract from δ B the DFSC δ i for each agent i = 1 • • • n. This is achieved by removing from δ B the components related to the other agents, such that only nodes and arcs that are labeled by individual actions and observations of agent i are kept. This step provides us with the vector of DFSCs (δ 1 , • • • , δ n ). We then build DJFSC δ based on the vector of DFSCs (δ 1 ,

x 1 0 x 2 0 x 1 1 x 2 2 x 1 2 x 2 1 o 1 o 2 o 2 o 1 o 2 o 1 x 1 0 x 1 1 x 1 2 x 2 0 x 2 2 x 2 1 o 2 1 o 2 2 o 2 2 o 2 1 o 2 2 o 2 1 o 1 2 o 1 1 o 1 1 o 1 2 o 1 1 o 1 2
• • • , δ n ) by using Lemma 1: ∀x ∈ X , π(x) = (π(x 1 ), • • • , π(x n )) and η(x, o) = (η(x 1 , o 1 ), • • • , η(x n , o n )), where o = (o 1 , • • • , o n ) and X = ⊗ n i =1 X i .
One can merge together machine states x ∈ X where the associated action π(x) and the successor links η(x, o) are the same. This two-step method proves the existence of such a DJFSC . But, we still need to prove that δ B is the sufficient information to build δ. This is achieved by removing either a node or an arc from δ B . In that case, the vector of DFSCs (δ 1 , • • • , δ n ) will consist of DFSCs δ i that lack a node or an arc. In accordance with this two-step method, we illustrate in Figure 1 the vector of DFSCs (down) extracted from a basis DJFSC (up) where the basis set is Ω

= {o 1 = (o 1 1 , o 2 2 ), o 2 = (o 1 2 , o 2 1 )
}. Valid hyperplanes. A similar result for a basis hyperplane can be easily derived from the above theorem. COROLLARY 1. Let {α o } o∈ Ω be a basis hyperplane. There exists a unique complement hyperplane {α o } o∈Ω\ Ω, such that hyperplane α = o∈Ω α o is valid. One can look at {α o } o∈ Ω as a set of hyperplanes that represents leaf nodes of a one-step basis joint policy δ B . Therefore, using Theorem 1, we are able to build the one-step joint policy δ associated to δ B and thus the corresponding hyperplane. Consider the example depicted in Figure 2, where each agent has observation set

x 1 3 x 2 3 start x 1 2 x 2 2 x 1 1 x 2 1 x 1 1 x 2 2 x 1 2 x 2 1 o 1 o 2 o 3 o 4
Ω i = {o i 1 , o i 2 } for i = 1, 2. Let Ω := {o 1 = (o 1 1 , o 2 2 ), o 2 = (o 1 2 , o 2 1 )} be the basis set, therefore its complement is Ω\ Ω := {o 3 = {o 1 1 , o 2 1 }, o 4 = {o 1 2 , o 2 2 }}. We know α (x 1 3 ,x 2
3 ) is built based on basis hyperplanes α (x 1 2 ,x 2 2 ) and α (x 1 1 ,x 2 1 ) that are associated to machine states

η(x, o 1 ) = (x 1 2 , x 2 2 ) and η(x, o 2 ) = (x 1 1 , x 2 1 )
, respectively. Thus, using Theorem 1, it turns out that the DFSC of agent 1 is transformed by adding machine state x 1 3 where η(

x 1 3 , o 1 2 ) = x 1 2 and η(x 1 3 , o 1 1 ) = x 1 1
, and the DFSC of agent 2 is transformed by adding machine state x 2 3 where η(

x 2 3 , o 2 2 ) = x 2 2 and η(x 2 3 , o 2 1 ) = x 1 2 .
As a consequence, the complement hyperplane {α η(x,o 3 ) , α η(x,o 4 ) } is a vector of hyperplanes associated to machine states (x 1 1 , x 2 2 ) and (x 1 2 , x 2 1 ), respectively. For instance to determine the machine state associated to α η(x,o 3 ) , we use η(x, o 3 ) = (η(x 1 3 , o 1 1 ), η(x 2 3 , o 2 1 )), i.e., (x 1 1 , x 2 2 ). We call this procedure the construction of valid hyperplanes.

Preserving the decentralization. We are now ready to state the update and transformation rules that preserve the decentralization. It is straightforward to see that the construction of valid hyperplanes discussed above preserves the decentralization. Therefore, an update that preserves the decentralization consists in generating hyperplanes in Γ τ+1 using the construction of valid hyperplanes based on hyperplanes in the current set Γ τ . On the other hand, we identify two transformation rules that preserve the decentralization. The first rule is to remove individual machine states x i along with all joint machine states x = x i x -i and hyperplanes α x associated. The second rule is to replace an individual machine state x i by another one xi every where x i appears. Because these are essentially transformations of individual controllers, the resulting joint controller is still valid.

The Sufficient Statistic

In this section, we explain how planning only over reachable beliefs allows the optimal policy of a DEC-POMDP to be found.

Planning over reachable beliefs. In order to be optimal, the Markov assumption requires that a policy depends on all the information available to the team at each time step. In DEC-POMDPs, at the execution time the agents are unaware of private information of their team-mates. However, in simulation each agent can divulge its private information to its team-mates. Therefore, the agents can maintain a complete joint history trace of all joint ob-servations and joint actions they ever simulated. This joint history can get very long as time goes on. A well-known fact is that this joint history can be summarized via a belief. Unfortunately, because of the decentralization constraint a belief alone is not sufficient to condition the selection of a joint action. Nevertheless, we can still show that planning only over reachable beliefs allows the optimal policy to be computed. To better understand this, let b 0 be an initial belief we need to compute the optimal value. We know that the machine state x whose hyperplane α x yields the highest value for belief b 0 depends on machine states whose hyperplanes {α η(x,o) } o∈Ω are selected for its successor beliefs {b π(x),o } o∈Ω . Because of the decentralization constraint, the hyperplanes selected for successor beliefs {b π(x),o } o∈Ω are dependent on each other -that is the selection of hyperplanes for some successor beliefs in {b π(x),o } o∈Ω constrains the selection of hyperplanes for the remaining. As previously discussed, if we select a basis hyperplane for successor belief b ′ ∈ {b π(x),o } o∈ Ω associated to basis joint observations, we determine directly the hyperplanes that are assigned to the remaining successor beliefs {b π(x),o } o∈Ω\ Ω. A similar argument can be used to show that successor beliefs of beliefs {b π(x),o } o∈Ω are also dependent on each other, and so on. Thus, in the decentralized multi-agent settings, the value of any belief b τ+1 depends on the value of all beliefs reachable starting in its precedent belief b τ . It is worth noting that because the initial belief b 0 does not have a precedent belief, its value depends only on all reachable beliefs starting in b 0 . This permits us to claim that planning only over reachable beliefs allow us to compute the optimal policy for a given initial belief. Although, the optimal value V τ+1 (b) cannot be computed directly for each reachable belief (since it may depends on infinitely many other beliefs), the corresponding set Γ τ+1 , that includes the hyperplane that is maximal for b while satisfying the decentralization constraint, can be generated through a sequence of operations on the set Γ τ .

Selection of belief set B . Since the selection of a finite set of beliefs B is crucial to the solution quality of all point-based algorithms, we rely on sampling techniques whose efficiency has been proven. In particular, [START_REF] Pineau | Point-based value iteration: An anytime algorithm for POMDPs[END_REF] described a forward simulation that generates the sample belief set. The procedure starts by selecting the initial belief set B 0 := {b 0 } including the initial belief b 0 at time τ = 0. Then, for time τ = 1, 2, • • • , it expands B τ to B τ+1 by adding all possible b a,o produced, and this ∀b ∈ B τ , ∀a ∈ A, ∀o ∈ Ω, such that pr (o|b, a) > 0. Then, the belief set △ := ∪ ∞ τ=0 B τ is the set of beliefs reachable during the simulation time. It is therefore sufficient to plan only over these beliefs in order to find an optimal joint policy customized for a team of agents that starts from belief b 0 , since △ constitutes a closed inter-transitioning belief set. Unfortunately, it is likely that △ is infinitely large. Thus, rather than keeping all possible b a,o we keep only a single b a, * that is the one that has the maximum L 1 distance to the current B . And we add it into B only if its L 1 distance is beyond a given threshold ε.

POLICY ITERATION FOR DEC-POMDPS

Our PI (H B -PI) algorithm is summarized in Algorithm 1, with the principal structure shared with its POMDP counterparts [START_REF] Hansen | An improved policy iteration algorithm for partially observable mdps[END_REF][START_REF] Ji | Point-based policy iteration[END_REF]. Similarly to the single-agent case, H B -PI consists of a threefold method: policy evaluation; policy improvement; and policy transformation. While the policy evaluation step is straightforward as previously discussed, processing the two later steps while providing guarantees on the satisfaction of the decentralization constraint is not trivial.

Policy Improvement. To show the importance of using basis objects and sets for DP updates in decentralized multi-agent settings, we first consider state-of-the-art alternative strategies from either single-agent or multi-agent cases. In the single-agent case, we need first to generate the whole set Γ τ+1 and thereafter prune non valid hyperplanes [START_REF] Sondik | The optimal control of partially observable Markov decision processes[END_REF]. This approach is, of course, hopelessly computationally intractable, as it requires the generation of |A||Γ τ | κ n hyperplanes which is doubly exponential in κ and n.

In the multi-agent case, we build first all possible individual policies, that induces set Γ τ+1 of valid hyperplanes and thereafter prune dominated hyperplanes [START_REF] Daniel | Policy iteration for decentralized control of Markov decision processes[END_REF]. While this approach is more tractable than the previous one, the exhaustive backup limits its scalability. Indeed, set Γ τ+1 grows by

|A| n i =1 |X i τ | |Ω i |
, which grows exponentially with n.

We are now ready to present the implementation of our backup operator H B . Similarly to the single-agent case, we start by creating intermediate sets Γ a, * and Γ a,o , ∀a ∈ A, ∀o ∈ Ω (step 1): s,a). Next we create Γ a (∀a ∈ A), the cross-product over basis joint-observations, which includes one α a,o from each

Γ a,o ← α a,o i (s) = s ′ P (s ′ |s, a)O(o|s ′ , a)α i (s ′ ), ∀α i ∈ Γ τ and Γ a, * ← α a, * (s) = R(
Γ a,o (step 2): Γ a = ⊗ o∈ Ω Γ a,o ⊗ Γ a, * . Then, we create for each basis hyperplane α = {α a,o 1 , • • • , α a,o κ , α a, * } ∈ Γ a its complement hyperplane {α a,o κ+1 , • • • , α a,o |Ω| }
with respect to Corollary 1 discussed above. We therefore replace in Γ a , the hyperplane α by the hyperplane built as a cross-sum over hyperplanes in (step 3): ∀α ∈ Γ a , Γ a ← Γ a \{α} and Γ a ← α ′ = α a, * + γ o α a,o . Afterwards, we take the union of Γ a sets (step 4): Γ τ+1 = ∪ a Γ a . Finally, we include the initial set of hyperplanes (step 5): Γ τ+1 = Γ τ+1 ∪ Γ τ to preserve the integrity of the solution. In practice, many of the hyperplanes α i in the final set Γ τ+1 may be completely dominated by another hyperplane. To prune away those hyperplanes while preserving the decentralization, we rely on an individual machine state dominance criterion: THEOREM 2. Let X i and X -i be sets of machine states of agent i and the other agents except agent i , respectively. A machine state

x i ∈ X i is dominated iff: ∃ xi ∈ X i \x i : α xi x -i • b ≥ α x i x -i • b, ∀b ∈ B, ∀x -i ∈ X -i .
PROOF. We rely on a proof by contradiction. Assume (1) machine state x i ∈ X i is non dominated and (2)

∃ xi ∈ X i \x i : α xi x -i • b ≥ α x i x -i •b, ∀b ∈ B, ∀x -i ∈ X -i .
From the first claim, we derive that some of the reachable beliefs yield their optimal values under the decentralization constraint at hyperplanes α x i x -i , where

x -i ∈ X -i . From the second argument, we derive that there exists a machine state xi ∈ X i such that hyperplane α xi x -i point-wise dominates hyperplane α x i x -i for any machine state x -i ∈ X -i . In addition, by replacing machine state x i by machine state xi the decentralization constraint still holds. As a result, this modification transforms the initial policy into a policy with a value function that increases for at least one belief state b ∈ B and decreases for no b ∈ B -which is a contradiction.

The pruning then alternates from one agent to another until no more machine states are pruned. We extend the machine state dominance criterion to prune successively intermediate sets Γ a,o and Γ a , for all a ∈ A and o ∈ Ω and set Γ τ+1 . As κ and |Γ τ | grow the overhead of performing these pruning mechanisms is nonnegligible.

The point-based B&B backup HB . This method aims at building the next set of hyperplanes Γ τ+1 using hyperplanes in Γ τ . The problem of finding the next set of hyperplanes Γ τ+1 given a finite set of beliefs B and intermediate sets Γ a, * and Γ a,o (∀a ∈ A and ∀o ∈ Ω), corresponds to the problem of finding basis hyperplane

(α a,o 1 b , • • • , α a,o κ b
) such that the corresponding valid hyperplane α b ∈ Γ τ+1 is maximal for belief b, and this for each belief in B . One may suggest to solve such a problem using essentially the single-agent point-based backup operator while preserving the decentralization. That is, solving the problem by selecting hyperplane α a,o b that is maximal at b, one hyperplane for each basis joint observation. Then, we build the corresponding valid hyperplane. Unfortunately, the resulting hyperplane yields a lowerbound value. This is because its complement hyperplane can provide poor rewards. As a result, the overall contribution of the basis hyperplane is diminished by the poor contribution from its complement hyperplane. If we relax the problem by skipping the decentralization constraint, we build hyperplane α b that is an upper-bound value at belief b and potentially a non valid hyperplane. Hence, applying single-agent point-based methods do not lead to the best valid hyperplane for each belief. As this is essentially a combinatorial problem, we rely on a point-based branch-and-bound backup operator.

To describe this method, the following definitions are required: (a) α a is a vector of hyperplanes one for each joint-observation; (b) α a (o) is the selected hyperplane α a,o i ∈ Γ a,o . The forward search in the space of vectors of hyperplanes can be considered as an incremental construction of the best vector of hyperplanes based on optimistic evaluations of only partially completed vectors of hyperplanes. In each step of the search, the most promising partially completed vector of hyperplanes is selected and further developed, hence the best first approach. For a completely defined vector of hyperplanes α a , we are able to find the corresponding hyperplane α = α a, * + γ o α a (o). We then state our maximization problem as follows:

α b = arg max α (α • b).
Notice that a partially completed vector of hyperplane is a vector where α a is only partially defined. Moreover, any partially completed vector of hyperplanes can be completed by assigning hyperplane α a,o ∈ Γ a,o that yields the highest value for belief b at points α a (o) where α a is not constrained. In order to determine whether or not to expand the leaf node of the search tree corresponding to a partially completed vector of hyperplanes, we compute an upper-bound value of any partially completed vector of hyperplanes for a given belief b. We define the upperbound based on the decomposition of the exact estimate into two estimates. The first estimate, G( α a , b), is the exact estimate coming from points α a (o) where α a is constrained. The second estimate, H ( α a , b), is the upper-bound value coming from points α a (o) where α a is not constrained. We introduce sets of jointobservations Ω 1 and Ω 2 (such that Ω = Ω 1 ∪ Ω 2 ) that correspond to joint-observations that lead to constrained points and nonconstrained points, respectively.

V ( α a , b) = α a, * + γ o∈Ω 1 α a (o) • b G( α a ,b) + γ o∈Ω 2 max α a,o (α a,o • b) H ( α a ,b)
In the following, we draw our attention to a single search tree of our point-based B&B backup operator with the following entries: a belief b; a joint action a and intermediate sets Γ a,o (∀o ∈ Ω), see Algorithm 2. We start by initializing the pool of live nodes with a partially defined vector α a 0 where none of the points α a 0 (o) (∀o ∈ Ω) is defined, and the value hereof is used as the value (called incumbent) of the current best solution (line 1). In each iteration of the heuristic, the node α a i that yields the highest upperbound is selected for exploration from the pool of live nodes (lines 3 -4). Then, a branching is performed: two or more children of the node are constructed through the definition of a single point α a i (o) (line 5), for o ∈ Ω. Furthermore, for each of the generated child nodes α a i , points α a i (o) for o ∈ Ω\ Ω that can be defined based on already constrained points are defined and the upper-bound is calculated. In case the node corresponds to a completely defined vector of hyperplanes its upper-bound is its exact estimate value, the value hereof is compared to the incumbent, and the best solution and its value are kept (lines 7 -10). If its upper-bound is not better than the incumbent, the node is discarded, since no completely defined descendant nodes of that node can be better than the incumbent. Otherwise the possibility of a better solution in the descendant nodes cannot be ruled out, and the node is then joined to the pool of live nodes (line 11). When the search tree has been completely explored, the heuristic starts a new search tree with a new joint-action and the current best solution, until all joint-actions have been processed and this for each belief b ∈ B .

Select α a i ∈ Live : ∀ α a j ∈ Live, V ( α a j , b) ≤ V ( α a i , b)

5:

Live := Live \ { α a i }

6:

Branch on α a i generating α a 1 , • • • , α a i k 7:

for 1 ≤ p ≤ k do 8: if V ( α a i p , b) > Incumbent then 9: if α a i p
is completely defined then 10:

Incumbent := V ( α a i p , b)
11:

Solution := α a, * + o α a i p (o) 12:
else Live := Live ∪ { α a i p } 13:

until Live =

14:

return Solution Policy Transformation. [START_REF] Hansen | An improved policy iteration algorithm for partially observable mdps[END_REF] describes a policy transformation mechanism based on a simple comparison of Γ τ+1 and Γ τ , for the single-agent case. These rules are extended here for multiple agent settings. The procedure below iterates between agents until no more machine states can be eliminated. Notice that these transformation rules preserve the decentralization and decrease the value for no b ∈ B .

For all y i ∈ X i τ+1 :

• rule 1: If the action and successor links associated with y i duplicate those of a machine state of δ i , then keep that machine state unchanged in δ i τ+1 ; • rule 2: Else if the machine y i dominates a machine state x i ∈ X i τ associated with a machine state in δ i τ , change the action and successor links of that machine state to those that correspond to x i ;

• rule 3: Else add a machine state to δ i τ+1 that has the action and successor links associated with y i ; Finally, prune any machine state for which there is no corresponding hyperplane in Γ τ+1 , as long as it is not reachable from a machine state to which an hyperplane in Γ τ+1 does correspond.

Transformation rules

♣

THEORETICAL ANALYSIS

This section presents convergence, error bound and the complexity arguments that draw on earlier approaches in single agent settings.

Convergence Properties. Point-based PI algorithms, despite being approximate methods, inherit many desirable properties of PI algorithms from POMDPs [START_REF] Hansen | An improved policy iteration algorithm for partially observable mdps[END_REF][START_REF] Ji | Point-based policy iteration[END_REF], including: (1) If a DJFSC has not converged, the policy improvement transforms it into a DJFSC with a value function that increases for at least on belief b ∈ B and decreases for no b ∈ B ; (2) Point-based PI algorithms converge to an approximate DJFSC after a finite number of iterations; (3) the exact PI H-PI algorithm (B = △S) converges to an ε-optimal policy.

Error bounds. We now show that the error between V τ and the optimal value function V * is bounded. The bound depends on how densely B samples the belief set △; with denser sampling, V τ converges to V * . Cutting off the point-based PI (H B -PI) iterations at any sufficiently large time step, we know that the difference between V τ and the optimal value function V * is not too large. The overall error in [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]). The remainder of this section states and proves a bound on the first term V τ -V * τ ∞ . We prove that [START_REF] Pineau | Point-based value iteration: An anytime algorithm for POMDPs[END_REF]'s bound stated for POMDPs holds for DEC-POMDPs. in the remainder of this paper, we state

H B -PI, V τ -V * ∞ , is bounded by: V τ -V * τ ∞ + V * τ -V * ∞ . Because, H (resp. H B ) is a contraction mapping, HV τ (b) = max a E R(a, b) + γ o V * τ (b a,o ) , the second term V * τ -V * ∞ is bounded by γ τ V * 0 -V * (see
ε B = max b ′ ∈ △ min b∈B b -b ′ 1 ,
: η ≤ r ∞ 1-γ ε B PROOF.
To have an intuition of the proof we provide an illustrative example Figure 3. Let b ′ ∈ △\B be the belief where H B -PI makes its worst error in the value function update, and b ∈ B be the closest (L 1 norm) sampled belief to b ′ . Let α y the hyperplane that would be maximal at b ′ , where y = {y i } and y ∈ X . Let α x be the hyperplane that is maximal for b ′ , where x = {x i } and x ∈ X . By failing to include α y in its solution set, H B -PI makes an error of at most α y • b ′ -α x • b ′ . On the other hand, we know that α x • b ≥ α y • b. This is mainly because in order to remove hyperplane α y Theorem 2 requires each machine state y i to be dominated or equal to machine state x i over belief set B . So,

η ≤ α y • b ′ -α x • b ′ = α y • b ′ -α x • b ′ + (α y • b -α y • b) add zero ≤ α y • b ′ -α x • b ′ + α x • b -α y • b α x maximal at b ′ = (α y -α x ) • (b ′ -b) collect terms ≤ α y -α x ∞ b ′ -b 1 Holder inequality ≤ α y -α x ∞ ε B definition of ε B ≤ r ∞ 1-γ ε B
The remainder of this section states and proves a bound for H B -PI algorithm.

THEOREM 3. For any belief set B and any time step τ, the error of the H

B -PI algorithm η τ = V τ -V * τ ∞ is: η τ ≤ r ∞ (1-γ) 2 ε B . PROOF. η τ = V τ -V * τ ∞ (definition of η τ ) = H B V τ-1 -HV * τ-1 (definition of H B and H) ≤ H B V τ-1 -HV τ-1 ∞ + HV τ-1 -HV * τ-1 ∞ ≤ η + HV τ-1 -HV * τ-1 ∞ (definition of η) ≤ η + γ V τ-1 -V * τ-1 ∞ (contraction) ≤ η + γη τ-1 (definition of η τ-1 ) ≤ r ∞ (1-γ) 2 ε B (series sum)
Notice that a tighter approximation error bound of H B -PI can be derived. Indeed, we estimate only the pruning error that incurs during the policy improvement step and ignore the policy evaluation step as well as hyperplanes from the earlier updates that are kept for the integrity of the controller.

EXPERIMENTAL RESULTS

As memery-bounded algorithms, NLP and BPI, are known to perform better than other approximate solvers, we compare HB -PI. only to NLP and BPI. The comparison is made according to DEC-POMDP benchmarks from the literature: the multi-access broadcast channel (MABC) problem [START_REF] Hansen | Dynamic programming for partially observable stochastic games[END_REF], the multi-agent tiger problem [START_REF] Nair | Networked distributed POMDPs: A synthesis of distributed constraint optimization and POMDPs[END_REF], the MEETING GRID problem [START_REF] Daniel | Bounded policy iteration for decentralized POMDPs[END_REF], and the COOPERATIVE BOX-PUSHING problem [START_REF] Seuken | Improved Memory-Bounded Dynamic Programming for DEC-POMDPs[END_REF]. The COOPERATIVE BOX-PUSHING problem provides an opportunity for testing the scalability of different algorithms. The reader can refer to the references above for an exact specification of the benchmarks. The performances of memory-bounded algorithms where sent by the authors, and run on an Intel(R) Pentium(R) 4 CPU 3.4GHz with 2GB of memory. Our algorithm was run on a Intel Core Duo 2.4GHz with 2GB of memory.

Results. Figure 4 presents our experimental results. For each problem and solver, we report: the value V δ (b 0 ) at the initial belief b 0 , the CPU time (in seconds) and the size |B | belief set B used for HB -PI. We depict for each benchmark two graphs. On the right-hand side, we show the runtimes of all solvers over iterations. As performance results of memory-bounded solvers are built based on the solution size, we report on the x-axis the individual controller size. On the other hand, since HB -PI is an iterative algorithm we report on the x-axis the number of iterations performed so far. As a result, we use iteration -that is the label of the x-axis, either for the size of individual controllers or the number of iterations performed so far, depending on the solver. Because all solvers do not have the same x-axis, the reader should mostly focus on the best value obtained by the solver and the amount of time it takes to reach that value. On the left-hand side, we illustrate the value at the initial belief over the iterations. Overall it appears that HB -PI outperforms all NLP and BPI in all tested DEC-POMDP domains and in both computation time and solution quality. For problem of small-size, HB -PI reaches a fixed point quite fast while neither NLP nor BPI were able to even reach the same solution quality for TIGER-A, MEETING-GRID, and COOP-ERATIVE BOX-PUSHING. As an example, HB -PI takes 11.5 seconds to converge into a DJFSC of value 1.91 for the TIGER-A problem. The best memory-bounded solver, NLP, takes 1059 seconds to find its best joint stochastic controller of value -2.36. For this same problem, BPI could not find a stochastic joint controller of value higher than -52.63, this also explains why it does not appear in the graph. Even more importantly, HB -PI converges into a fixed-point for MABC, TIGER-A, and MEETING-GRID benchmarks. This suggests that it inherited some of the properties of single-agent solvers.

CONCLUSION AND FUTURE WORK

We have derived and analyzed the first PI algorithms with provable error bounds. This research also provides interesting new theoretical insights, including the ability to perform DP updates while preserving the decentralization. Even though the experiment results demonstrate impressive improvement over the current standard methods, we are still far from being able to deal with real-world-size DEC-POMDPs. To this end, we are planning to use the new theoretical insights exhibited in this paper as foundations of more scalable algorithms facing some of the bottlenecks of our approach.

Figure 1 :

 1 Figure 1: Extraction of vector of DFSCs.

Figure 2 :

 2 Figure 2: The construction of a valid hyperplane (in white) and the complement of basis hyperplane hyperplane (in gray) given the basis hyperplane (in black).

Algorithm 2

 2 Point-based branch and bound backup 1: procedure HB -BACKUP(a, b, {Γ a,o } o∈Ω ) 2: Initialize: Incumbent := V (b); Live := α a

Figure 3 :

 3 Figure 3: Errors made on a 2-states DEC-POMDP by H B -PI for beliefs b ′ with respect to their closest belief b.

MABC

Figure 4 :

 4 Figure 4: Performance results for DEC-POMDP benchmark problems from the literature.

  and r ∞ = max s,a R(s, a). First of all, let us prove the following lemma: LEMMA 2. The error introduced in H B -PI when performing one iteration of value function update over B , instead of △, is bounded by

Fictitious individual observations are added to agents if necessary such that the assumption always holds.

ADDITIONAL AUTHORS


Emmanuelle Mohamed Amine Hamila

Grislin-Le Strugeon

René Mandiau

Abdel-Illah Mouaddib

An algorithm for multi-robot planning: SGInfiniteVI