Planning for Weakly-Coupled Partially Observable Stochastic Games

1 Introduction

Partially observable stochastic games (POSGs) provide a powerful framework for modeling multi-agent interactions. While elegant and expressive, the framework has been shown to be computationally intractable [Bernstein et al., 2002]. An exact dynamic programming algorithm for POSGs has been developed recently, but due to high computational demands, it has only been demonstrated to work on extremely small problems. Several approximate approaches have been developed [Emery-Montemerlo et al., 2004; Nair et al., 2003], but they lack strong theoretical guarantees. In light of these theoretical and practical limitations, there is a need to identify special classes of POSGs that can be solved tractably.

One dimension along which computational gain can be leveraged is by exploiting the independence present in the problem dynamics. In this paper, we examine a class of POSGs where the agents only interact loosely by restricting one another's available actions. Specifically, rather than having fixed action sets, each agent's action set is a function of the global state. The agents are independent from one another otherwise, i.e. they have separate transition and reward functions that do not interact. This class of problems arises frequently in practice. Many real world domains are inhabited by self-interested agents that act to achieve their individual goals. They may not affect each other in any way, except for occasionally putting restrictions on what each other can do.

The best-known solution concepts in game theory are that of computing Nash equilibrium and performing strategy elimination. Our work addresses both of these solution concepts. First, we show that finding a Nash equilibrium where each agent achieves reward at least k is NP-hard. Another contribution of this work is that we present an exact algorithm for performing iterated elimination of dominated strategies. It is able to solve much larger problems than exact algorithms for the general class by exploiting problem structure.

2 POSGs with State-Dependent Action Sets

In this section, we will present a formal definition of our model. An n-agent POSG with state-dependent action sets can be defined as 〈{Si}, {s0i }, {Ai}, {Bi}, {Pi}, {Ri}〉, where,

• Si is the state space of agent i. S = S1 ×S2 × . . . ×Sn denotes the joint state set.

G = 〈{Si}, {s0i }, {Ai}, {Bi}, {Pi}, {Ri}〉, does there exist a Nash equilibrium where all agents have expected utility at least k?

Theorem 1 POSG-NE is NP-hard even in problems involving 2 agents and a horizon of 2.

4 Iterated Action Elimination Algorithm

We present an algorithm that performs iterated elimination of dominated strategies. The algorithm is able to work directly with the compact representation of a POSG without first converting it to the double exponentially large normal form representation. In this algorithm, first, we first fix the action sets of each agent at each state to the optimistic and pessimistic action sets. The idea behind this is that although an agent cannot predict exactly what actions will be available at each state, it can find out what actions would be available in the best and worst case scenario. In the best case, none of the actions that can be restricted by the state of the other agents are, and in the worst case, all of the actions that can be restricted are in fact unavailable.

For each agent i:

1. For each state sk, compute the optimistic and pessimistic action sets. Here s = 〈s1 , s2 , . . . , sn 〉 and si = sik .

1. Compute the value functions of the 2MDPs that correspond to alternately fixing the available action sets to the Aopt and Apes.

1. For each action in each state, derive upper and lower bounds on the action value from the value function bounds U(s) and L(s).

1. At each state, eliminate all actions a′ whose action value is dominated by another action a, QL(s, a) ≥ QU (s, a′ ).
2. Repeat steps 1 to 4 until no more actions can be eliminated at any state.

Table 2: Average size of the policy space before and after action elimination for problems with 3 constrained states.

Once we fix the available action sets of each agent at all the states, the agents no longer depend on each other in any way. Our model decomposes to a set of MDPs. For each agent, we solve two MDPs, one using the optimistic action sets and the other using the pessimistic action sets. The solutions will provide us with an upper and a lower bound on the actual value function of each agent. With these upper and lower bounds on the expected values of each state, we can now derive bounds on the expected action values. At each state, dominated actions are pruned. We iterate the action elimination procedure until no more actions can be pruned. Since the number of actions at each state is finite, the procedure will eventually converge.

Theorem 2 The iterated action elimination algorithm corresponds to the iterated elimination of very weakly dominated strategies.

5 Experiments

We tested the algorithm on a simplified 2-agent autonomous rover exploration scenario. The size of each agent's local state space varies from 6 to 16. We introduced up to three constrained states in each agent's state space. 100 trials were run for each size of state space and number of constraints. Table 2 shows detailed results for problems with three constrained states. For problems with one and two constrained states, the final policy space ranges from 3 to 106 and 8 to 252 respectively. In all three cases, the iterated action elimination algorithm is able to reduce the size of the policy space by several orders of magnitude.