Bounded Policy Iteration for Decentralized POMDPs

1 Introduction

The Markov decision process (MDP) framework has proven to be useful for solving problems of sequential decision making under uncertainty. For some problems, an agent must base its decision on partial information about the system state. In this case, it is often better to use the more general partially observable Markov decision process (POMDP) framework. Though POMDPs are difficult to solve in the worst case, much progress has been made in the development of practical dynamic programming algorithms [Smallwood and Sondik, 1973; Cassandra et al., 1997; Hansen, 1998; Poupart and Boutilier, 2003; Feng and Zilberstein, 2004].

Even more general are problems in which a team of decision makers, each with its own local observations, must act together. Domains in which these types of problems arise include networking, multi-robot coordination, e-commerce, and space exploration systems. To model such problems, we can use the decentralized partially observable Markov decision process (DEC-POMDP) framework. Though this model has been recognized for decades (see, e.g., [Witsenhausen, 1971]), there has been little work on efficient algorithms for it.

Recently, an exact dynamic programming algorithm was proposed for DEC-POMDPs [Hansen et al., 2004]. Though the algorithm was presented in the context of finite-horizon

Shlomo Zilberstein

Dept. of Computer Science University of Massachusetts Amherst, MA 01003 shlomo@cs.umass.edu

problems, there are various ways to extend it to the infinitehorizon case. However, in both cases, it suffers from the fact that the memory requirements grow quickly with each iteration, and in practice it has only been used to solve very small problems. It is likely that any optimal algorithm would suffer this problem, as finite-horizon DEC-POMDPs have been shown to be NEXP-complete, even for just two agents [Bernstein et al., 2002].

In this paper, we present a memory-bounded dynamic programming algorithm for infinite-horizon DEC-POMDPs. The algorithm uses a stochastic finite-state controller to represent the joint policy for the agents. A straightforward approach is to use a set of independent local controllers, one for each agent. We provide an example to illustrate that higher value can be obtained through the use of shared randomness. As such, we define a joint controller to be a set of local controllers along with a correlation device. The correlation device is a finite-state machine that sends a signal to all of the agents on each time step. Its behavior can be determined prior to execution time, and thus it does not require that the agents exchange information after receiving local observations.

Our algorithm generalizes bounded policy iteration for POMDPs [Poupart and Boutilier, 2003] to the multi-agent case. On each iteration, a node is chosen from one of the local controllers or the correlation device, and its parameters are updated through the solution of a linear program. The generalization has the same theoretical guarantees as in the POMDP case. Namely, an iteration is guaranteed to produce a new controller with value at least as high for every possible initial state distribution.

In our experiments, we applied our algorithm to idealized networking and robot navigation problems. Both problems are too large for exact dynamic programming, but could be handled by our approximation algorithm. We found that the addition of a correlation device gives rise to better solutions. In addition, larger controllers most often lead to better solutions.

A number of approximation algorithms have been developed previously for DEC-POMDPs [Peshkin et al., 2000; Nair et al., 2003; Emery-Montemerlo et al., 2004]. However, the previous algorithms do not guarantee both bounded memory usage and monotonic value improvement for all initial state distributions. Furthermore, the use of correlated stochastic policies in the DEC-POMDP context is novel. The importance of correlation has been recognized in the game theory community [Aumann, 1974], but there has been little work on algorithms for finding correlated policies.

2 Background

In this section, we present our formal framework for multi-agent decision making. A decentralized partiallyobservable Markov decision process (DEC-POMDP) is a tuple 〈I, S, {Ai}, {Oi}, P, R〉, where

• I is a finite set of agents indexed 1, . . . , n
• S is a finite set of states
• Ai is a finite set of actions available to agent i and ⃗A = ×i∈IAi is the set of joint actions, where ⃗a = 〈a1, . . . , an〉 denotes a joint action
• Oi is a finite set of observations for agent i and ⃗O = ×i∈IOi is the set of joint observations, where ⃗o = 〈o1, . . . , on〉 denotes a joint observation
• P is a set of Markovian state transition and observation probabilities, where P (s′ , ⃗o|s, ⃗a) denotes the probability that taking joint action ⃗a in state s results in a transition to state s′ and joint observation ⃗o
• R : S × ⃗A → ℜ is a reward function

In this paper, we consider the case in which the process unfolds over an infinite sequence of stages. At each stage, all agents simultaneously select an action, and each receives the global reward and a local observation. The objective of the agents is to maximize the expected discounted sum of rewards received. We denote the discount factor γ and require that 0 ≤ γ < 1.

3 Finite-State Controllers

Our algorithm uses stochastic finite-state controllers to represent policies. In this section, we first define a type of controller in which the agents act independently. We then provide an example demonstrating the utility of correlation, and show how to extend the definition of a joint controller to allow for correlation among agents.

3.1 Local Finite-State Controllers

In a DEC-POMDP, each agent must select an action based on its history of local observations. Finite-state controllers provide a way to represent local policies using a finite amount of memory. The state of the controller is based on the observation sequence, and the agent's actions are based on the state of its controller. We allow for stochastic transitions and stochastic action selection, as this can help to make up for limited memory. This type of controller has been used previously in the single-agent context [Platzman, 1980; Meuleau et al., 1999; Poupart and Boutilier, 2003].

Formally, we define a local finite-state controller for agent i to be a tuple 〈Qi, ψi, ηi〉, where Qi is a finite set of controller nodes, ψi : Qi →∆Ai is an action selection function, and ηi : Qi ×Ai ×Oi → ∆Qi is a transition function. The functions ψi and ηi parameterize the conditional distribution P (ai, q′i |qi, oi).

Taken together, the agents' controllers determine the conditional distribution P(⃗a, ⃗q ′ |⃗q, ⃗o). This is denoted an independent joint controller. In the following subsection, we show that independence can be limiting.

3.2 The Utility of Correlation

The joint controllers described above do not allow the agents to correlate their behavior via a shared source of randomness. We will use a simple example to illustrate the utility of correlation in partially observable domains where agents have limited memory. This example generalizes the one given in [Singh et al., 1994] to illustrate the utility of stochastic policies in single-agent partially observable settings.

Consider the DEC-POMDP shown in Figure 1. This problem has two states, two agents, and two actions per agent (A and B). The agents each have only one observation, and thus cannot distinguish between the two states. For this example, we will consider only memoryless policies.

Suppose that the agents can independently randomize their behavior using distributions P(a1) and P(a2), and consider the policy in which each agent chooses either A or B according to a uniform distribution. This yields an expected reward of - R2 per time step, which results in an expected long-term reward of -R 2(1-γ) . It is straightforward to show that no independent policy yields higher reward than this one for all states.

Next, let us consider the larger class of policies in which the agents may act in a correlated fashion. In other words, we consider all joint distributions P(a1, a2). Consider the policy that assigns probability 1 2 to the pair AA and probability 12 to the pair BB. This yields an average reward of 0 at each time step and thus an expected long-term reward of 0. The difference between the rewards obtained by the independent and correlated policies can be made arbitrarily large by increasing R.

3.3 Correlated Joint Controllers

In the previous subsection, we established that correlation can be useful in the face of limited memory. In this subsection, we extend our definition of a joint controller to allow for correlation among the agents. To do this, we introduce an additional finite-state machine, called a correlation device, that provides

Table 1: The linear program used to find new parameters for agent i's node qi. The variable x(c, ai) represents P(ai|qi, c), and the variable x(c, ai, oi, q′i ) represents P (ai, q′i |c, qi, oi).

extra signals to the agents at each time step. The device operates independently of the DEC-POMDP process, and thus does not provide the agents with information about the other agents' observations. In fact, the random numbers necessary for its operation could be determined prior to execution time.

Formally, a correlation device is a tuple 〈C, ψ〉, where C is a set of states and ψ : C → ∆C is a state transition function. At each step, the device undergoes a transition, and each agent observes its state.

We must modify the definition of a local controller to take the state of the correlation device as input. Now, a local controller for agent i is a conditional distribution of the form P(ai, q′i |c, qi, oi). The correlation device together with the local controllers form a joint conditional distribution P(c′ ,⃗a, ⃗q ′ |c, ⃗q, ⃗o). We will refer to this as a correlated joint controller. Note that a correlated joint controller with |C| = 1 is effectively an independent joint controller.

The value function for a correlated joint controller can be computed by solving the following system of linear equations, one for each s ∈ S, ⃗q ∈ ⃗Q, and c ∈ C:

We sometimes refer to the value of the controller for an initial state distribution. For a distribution δ, this is defined as

It is assumed that, given an initial state distribution, the controller is started in the joint node which maximizes value from that distribution.

4 Bounded Policy Iteration

We now describe our bounded policy iteration algorithm for improving correlated joint controllers. To improve a correlated joint controller, we can either change the correlation device or one of the local controllers. Both improvements can be done via a bounded backup, which involves solving a linear program. Following an improvement, the controller can be reevaluated through the solution of a set of linear equations. Below, we describe how a bounded backup works, and prove that it always produces a new controller with value at least as high for all initial state distributions.

4.1 Improving a Local Controller

We first describe how to improve a local controller. To do this, we choose an agent i, along with a node qi. Then, we search for new parameters for the conditional distribution P (ai, q′i |c, qi, oi).

The search for new parameters works as follows. We assume that the original controller will be used from the second step on, and try to replace the parameters for qi with better ones for just the first step. In other words, we look for the best parameters satisfying the following inequality:

for all s ∈ S, q-i ∈ Q-i, and c ∈ C. Note that the inequality is always satisfied by the original parameters. However, it is often possible to get an improvement.

Finding new parameters can be done using linear programming, as shown in Table 1. We note that this linear program is the same as that of Poupart and Boutilier [2003] for POMDPs, with the nodes of the other local controllers and correlation device considered part of the hidden state. Its size is polynomial in the sizes of the DEC-POMDP and the joint controller, but exponential in the number of agents.

4.2 Improving the Correlation Device

The procedure for improving the correlation device is very similar to the procedure for improving a local controller. We

Variables: ϵ, x(c′ )

Objective: Maximize ϵ

Improvement constraints:

Probability constraints:

Table 2: The linear program used to find new parameters for the correlation device node c. The variable x(c′ ) represents P (c′ |c).

first choose a device node c, and consider changing its parameters for just the first step. We look for the best parameters satisfying the following inequality:

for all s ∈ S and ⃗q ∈ ⃗Q.

As in the previous case, the search for parameters can be formulated as a linear program. This is shown in Table 2. This linear program is also polynomial in the sizes of the DEC-POMDP and joint controller, but exponential in the number of agents.

4.3 Monotonic Improvement

We have the following theorem, which says that performing either of the two updates cannot lead to a decrease in value for any initial state distribution.

Theorem 1 Performing a bounded backup on a local controller or the correlation device produces a correlated joint controller with value at least as high for every initial state distribution.

Proof. Consider the case in which some node qi of agent i's local controller is changed. Let Vo be the value function for the original controller, and let Vn be the value function for the new controller. Recall that the new parameters for P(ai, q′i |c, qi, oi) must satisfy the following inequality for all s ∈ S, q-i ∈ Q-i, and c ∈ C:

Notice that the formula on the right is the Bellman operator for the new controller, applied to the old value function. Denoting this operator Tn, the system of inequalities implies that TnVo ≥ Vo. By monotonicity, we have that for all k ≥ 0, T k+1 n (Vo) ≥ T k n (Vo). Since Vn = limk→∞T k n (Vo), we have that Vn ≥ Vo. Thus, the value of the new controller is higher than that of the original controller for all possible initial state distributions.

The argument for changing nodes of the correlation device is almost identical to the one given above. ✷

4.4 Local Optima

Although bounded backups give nondecreasing values for all initial state distributions, convergence to optimality is not guaranteed. There are a couple of factors contributing to this. First is the fact that only one local controller, or the correlation device, is improved at once. Thus, it is possible for the algorithm to get stuck in a suboptimal Nash equilibrium in which each of the controllers and the correlation device is optimal with the others held fixed. It is an open problem whether there is a linear program for updating more than one controller at a time.

Of course, a bounded backup does not find the optimal parameters for one controller with the others held fixed. Thus, a sequence of such updates may converge to a local optimum without even reaching a Nash equilibrium. For POMDPs, Poupart and Boutilier [2003] provide a characterization of these local optima, and a heuristic for escaping from them. This could be applied in our case, but it would not address the suboptimal Nash equilibrium problem.

5 Experiments

We implemented bounded policy iteration and tested it on two different problems, an idealized networking scenario and a problem of navigating on a grid. Below, we describe our experimental methodology, the specifics of the problems, and our results.

5.1 Experimental Setup

Although our algorithm guarantees nondecreasing value for all initial state distributions, we chose a specific distribution to focus on for each problem. Experiments with different distributions yielded qualitatively similar results.

We define a trial run of the algorithm as follows. At the start of a trial run, a size is chosen for each of the local controllers and the correlation device. The action selection and transition functions are initialized to be deterministic, with the outcomes drawn according to a uniform distribution. A step consists of choosing a node uniformly at random from the correlation device or one of the local controllers, and performing a bounded backup on that node. After 50 steps, the run is considered over. In practice, we found that values usually stabilized within 15 steps.

We varied the sizes of the local controllers from 1 to 7 (the agents' controllers were always the same sizes as each other), and we varied the size of the correlation device from 1 to 2. Thus, the number of joint nodes ranged from 1 to 98. Memory limitations prevented us from using larger controllers. For each combination of sizes, we performed 20 trial runs. We recorded the highest value obtained across all runs, as well as the average value over all runs.

5.2 Multi-Access Broadcast Channel

Our first domain is an idealized model of control of a multiaccess broadcast channel [Ooi and Wornell, 1996]. In this problem, nodes need to broadcast messages to each other over a channel. Only one node may broadcast at a time, otherwise a collision occurs. The nodes share the common goal of maximizing the throughput of the channel.

At the start of each time step, each node decides whether or not to send a message. The nodes receive a reward of 1 when a message is successfully broadcast and a reward of 0 otherwise. At the end of the time step, each node observes its own buffer, and whether the previous step contained a collision, a successful broadcast, or nothing attempted.

The message buffer for each agent has space for only one message. If a node is unable to broadcast a message, the message remains in the buffer for the next time step. If a node i is able to send its message, the probability that its buffer will fill up on the next step is pi. Our problem has two nodes, with p1 = 0.9 and p2 = 0.1. There are 4 states, 2 actions per agent, and 5 observations per agent. The discount factor is 0.9. The start state distribution is deterministic, with the buffer for agent 1 containing a message and the buffer for agent 2 being empty.

5.3 Meeting on a Grid

In this problem, we have two robots navigating on a twoby-two grid with no obstacles. Each robot can only sense whether there are walls to its left or right, and the goal is for the robots to spend as much time as possible on the same square. The actions are to move up, down, left, or right, or to stay on the same square. When a robot attempts to move to an open square, it only goes in the intended direction with probability 0.6, otherwise it either goes in another direction or stays in the same square. Any move into a wall results in staying in the same square. The robots do not interfere with each other and cannot sense each other.

This problem has 16 states, since each robot can be in any of 4 squares at any time. Each robot has 4 observations, since it has a bit for sensing a wall to its left or right. The total number of actions for each agent is 5. The reward is 1 when the agents share a square, and 0 otherwise, and the discount factor is 0.9. The initial state distribution is deterministic, placing both robots in the upper left corner of the grid.

5.4 Results

For each combination of controller sizes, we looked at the best solutions found across all trial runs. The values for these solutions were the same for all controller sizes except for the few smallest.

It was more instructive to compare average values over all trial runs. Figure 2 shows graphs of average values plotted against controller size. We found that, for the most part, the average value increases when we increase the size of the correlation device from one node to two nodes (essentially moving from independent to correlated).

For small controllers, the average value tends to increase with controller size. However, as the controllers get larger, there is no clear trend. This behavior is somewhat intuitive, given the way the algorithm works. For new node parameters to be acceptable, they must not decrease the value for any combination of states, nodes for the other controllers, and nodes for the correlation device. This becomes more difficult as controllers get larger, and thus it is easier to get stuck in a local optimum.

Improving multiple controllers at once would help to alleviate the aforementioned problem. As mentioned earlier, we do not currently have a way to do this using linear programming, and it thus remains an interesting topic for future work.

6 Conclusion and FutureWork

We have presented a bounded policy iteration algorithm for DEC-POMDPs. Besides the fact that it uses finite memory, the algorithm has a number of other appealing theoretical guarantees. First, by using correlated joint controllers, we can achieve higher value than with independent joint controllers of the same size. Second, assuming a constant number of agents, each iteration of the algorithm completes in polynomial time. Finally, monotonic value improvement is guaranteed for all states on each iteration.

Our empirical results are encouraging. By bounding the size of the controller, we are able to achieve a tradeoff between computational complexity and the quality of the approximation. Up to a point, increasing the sizes of the local controllers leads to higher values on average. After this point, average values tend to level off or decrease. Increasing the size of the correlation device leads to higher value, which is consistent with our theoretical results.

For future work, there are many more experiments that can be done with bounded policy iteration. For instance, in moving to a larger controller, we could use the previous controller as a starting point, rather than starting over with a random controller. Poupart and Boutilier's [2003] escape technique could be useful here. Also, rather than choosing nodes uniformly at random for updating, we could develop a principled way to order the nodes.

We are also looking into ways of extending the algorithm to handle problems with large numbers of agents. In many problems, each agent interacts with only a small subset of the other agents. This additional structure can be exploited to reduce the size of the problem representation, and it should be possible to extend our algorithm to take advantage of these local interactions.

Finally, it would be interesting to extend bounded policy iteration to the noncooperative setting, where each agent has a separate reward function. One approach is to require that a change in parameters does not lead to a decrease in value for any agent. Another approach is to consider just the value function for the agent whose node is being updated. This should move the joint controller towards a Nash equilibrium.

7 Acknowledgments

We thank Martin Allen and ¨Ozg¨ ur S¸ ims¸ek for helpful discussions of this work. This work was supported in part by the National Science Foundation under grants IIS-0219606 and IIS-9984952, by NASA under cooperative agreement NCC

• 2-1311, and by the Air Force Office of Scientific Research under grant F49620-03-1-0090.