Source-linked AI summary
Policy Iteration for Decentralized Control of Markov Decision Processes
Daniel S. Bernstein, Christopher Amato, Eric A. Hansen, Shlomo Zilberstein
TL;DR
Optimal dynamic programming algorithms have been elusive for multiagent DEC-POMDPs, where agents must coordinate using local observations. This paper presents policy iteration with stochastic finite-state controllers and value-preserving transformations. On the test problems, its heuristic version with NLP improvements reached at least the highest value obtained by the other approaches, and sometimes exceeded them markedly.
Problem
Multiagent DEC-POMDPs require coordination from local observations, yet optimal algorithms have been elusive despite extensive work on single-agent dynamic programming.
Source: §1 · p. 2Method
The policy-iteration algorithm uses stochastic finite-state controllers and alternates exhaustive backups with value-preserving transformations, with a heuristic variant for improved scalability.
Source: §4 · p. 15, §7 · pp. 37–38Results
On the test problems, heuristic policy iteration with NLP improvements reached at least the highest value obtained by each problem’s other approaches and was sometimes markedly higher.
Source: §6.5 · p. 37Takeaways & Limitations
Controller reductions combined with exhaustive backups use memory more efficiently than exhaustive backups alone, while the heuristic approach produced the highest published values reported for the three test domains.
Source: §6.5 · pp. 36–37The multiagent algorithm lacks an error bound derived from successive value functions; bounding distance to optimality instead requires the discount rate and iteration count.
Source: §4.4.1 · p. 26
Abstract
from arXiv · showhide
Coordination of distributed agents is required for problems arising in many areas, including multi-robot systems, networking and e-commerce. As a formal framework for such problems, we use the decentralized partially observable Markov decision process (DEC-POMDP). Though much work has been done on optimal dynamic programming algorithms for the single-agent version of the problem, optimal algorithms for the multiagent case have been elusive. The main contribution of this paper is an optimal policy iteration algorithm for solving DEC-POMDPs. The algorithm uses stochastic finite-state controllers to represent policies. The solution can include a correlation device, which allows agents to correlate their actions without communicating. This approach alternates between expanding the controller and performing value-preserving transformations, which modify the controller without sacrificing value. We present two efficient value-preserving transformations: one can reduce the size of the controller and the other can improve its value while keeping the size fixed. Empirical results demonstrate the usefulness of value-preserving transformations in increasing value while keeping controller size to a minimum. To broaden the applicability of the approach, we also present a heuristic version of the policy iteration algorithm, which sacrifices convergence to optimality. This algorithm further reduces the size of the controllers at each step by assuming that probability distributions over the other agents actions are known. While this assumption may not hold in general, it helps produce higher quality solutions in our test problems.
1. Introduction
DEC-POMDPs model teams whose agents act on local observations, but multiagent uncertainty makes standard single-agent dynamic programming difficult to extend. The paper develops policy iteration with stochastic controllers, value-preserving transformations, and a heuristic variant for settings where the optimal algorithm is impractical.
1. Introduction
- Agents must coordinate using local observations, and multiagent uncertainty complicates belief-state reasoning compared with single-agent POMDPs.Even the finite-horizon two-agent problem is complete for a higher complexity class than its single-agent counterpart (Bernstein, Givan, Immerman, & Zilberstein, 2002).Source: §1 · p. 2
- The paper extends single-agent policy iteration to infinite-horizon DEC-POMDPs, where prior approaches were only locally optimal.The algorithm converges in the limit and is presented as the first nontrivial optimal algorithm for this setting.Source: §1 · p. 2
- Policies use stochastic finite-state controllers, optionally coordinated by shared randomness that does not require agents to share observations.The paper introduces this use of correlated stochastic policies in the DEC-POMDP context.Source: §1 · p. 2
- Each iteration alternates exhaustive backups, which add controller nodes, with value-preserving transformations that change the controller without sacrificing value.The paper frames the multiagent extension using this two-phase view.Source: §1 · pp. 2–3
- Linear-programming transformations can remove controller nodes or improve value while keeping controller size fixed.The reported empirical results show their usefulness for obtaining high values while keeping controller size to a minimum.Source: §1 · p. 3
- A heuristic variant focuses search from the initial-state distribution, assuming fixed policies for other agents; it is non-optimal but produced more concise, higher-valued solutions before resources ran out.The assumption guides node removal using belief points found by forward search for each agent.Source: §1 · p. 3
2. Formal Model of Distributed Decision Making
The formal model describes cooperative agents acting simultaneously under shared rewards but with separate local observations. The paper represents their policies with finite-state controllers, which can compactly express infinite-horizon behavior.
2. Formal Model of Distributed Decision Making
- A DEC-POMDP extends distributed decision-making models to agents whose actions jointly affect the system while each acts only on local information.The model includes agents, states, joint actions, transitions, rewards, joint observations, and an observation function.Source: §2 · p. 3, §2.1 · pp. 3–4
2.1 Decentralized POMDPs
- In the infinite-horizon cooperative setting, agents act simultaneously, receive local observations, and maximize expected discounted reward with 0 ≤ β < 1.Transitions, rewards, and observations depend on all agents’ actions.Source: §2.1 · p. 4
- Because agents have separate observations, they may lack a common state estimate or an estimate of other agents’ decisions, making optimal solution difficult.The finite-horizon problem with at least two agents is NEXP-complete.Source: §2.1 · pp. 4–5
2.2 Solution Representations
- A joint policy combines one local policy per agent, and an optimal solution maximizes expected reward from the initial state.For infinite-horizon problems, rewards are discounted to keep the sum finite.Source: §2.2 · p. 5
- Finite-horizon local policies can be represented as policy trees that branch on observations, but infinite-horizon problems would require trees of infinite height.Each tree records an agent’s local history up to the fixed horizon and can be executed independently.Source: §2.2 · pp. 5–6
- Finite-state controllers select actions at a designated node and transition between nodes according to observations, supporting ongoing policies.Controller states are called nodes to distinguish them from system states.Source: §2.2 · p. 6
- An infinite-horizon optimal policy may require infinitely many nodes, while fixed-size stochastic controllers can represent policies within ε of optimal.Random action selection and node transitions may help with limited memory by allowing agents to break out of costly loops caused by forgetfulness.Source: §2.2 · p. 6
- Stochastic controllers compactly remember aspects of local history, with action and node-transition probabilities defining how a policy continues.For example, the described two-node controller uses probabilities for actions and observation-conditioned transitions.Source: §2.2 · p. 6
3. Centralized Dynamic Programming
For single-agent POMDPs, dynamic programming operates over belief states and exploits piecewise-linear, convex value functions. The section develops vector pruning and backup methods, then explains value iteration and its convergence-related tools.
3.1.1 Belief State MDPs
- POMDP value iteration uses the equivalent belief-state MDP, whose state is a distribution over system states, but its continuous state space prevents straightforward use of traditional MDP methods.The belief state is a sufficient statistic for observation history, and Bayesian updating gives successor beliefs.Source: §3.1.1 · p. 7
- The Bellman operator preserves piecewise linearity and convexity, allowing value functions to be represented by vectors evaluated at belief states.Finite-horizon optimal value functions are piecewise linear and convex; infinite-horizon functions are convex and can be approximated arbitrarily closely by piecewise-linear convex functions.Source: §3.1.1 · pp. 7–8
3.1.2 Pruning Vectors
- Dominated vectors can be pruned without changing the represented value function, and linear programming provides an efficient test for dominance.Dominance can also be characterized by a convex combination of vectors that dominates the candidate across states.Source: §3.1.2 · pp. 8–9
3.1.3 Dynamic Programming Update
- A dynamic-programming update constructs candidate vectors from an action and assignments of existing vectors to observations, then can prune the candidates.Exhaustive backup evaluates all |A||Γt||Ω| possible one-step policies; other approaches prune during generation or identify useful belief states.Source: §3.1.3 · pp. 9–10
- Under widely believed complexity assumptions, no dynamic-programming update algorithm is worst-case polynomial in all relevant quantities.Despite this barrier, updates have been implemented in value-iteration and policy-iteration algorithms.Source: §3.1.3 · p. 10
3.1.4 Value Iteration
- Value iteration repeatedly applies dynamic-programming updates and converges to an ε-optimal value function after finitely many iterations.The Bellman residual, the maximum distance between successive value functions over belief states, bounds distance to optimality and can be computed using linear programming.Source: §3.1.4 · p. 11
3.2 Policy Iteration for POMDPs
The POMDP policy-iteration approach represents policies with finite-state controllers and alternates controller expansion with transformations that do not decrease value.
3.2.1 Finite-State Controllers
- Finite-state controllers use internal nodes to select actions and transition on observations, providing limited memory without requiring the agent to retain its full observation history.The controller is initialized at the node with greatest value for the initial distribution; it does not update a belief state during execution.Source: §3.2.1 · pp. 11–12
3.2.2 Algorithmic Framework
- Each iteration evaluates the controller, adds nodes for one-step policies through an exhaustive backup, then applies transformations that do not decrease value.The algorithm is guaranteed to reach an ϵ-optimal controller for all belief states in finitely many steps.Source: §3.2.2 · pp. 12–13
3.2.3 Controller Reductions
- Controller reduction removes a node by redirecting transitions to a probability distribution over other nodes that dominates it for every state.A linear program finds the distribution; using it for merging preserves value.Source: §3.2.3 · pp. 13–14
3.2.4 Bounded Backups
- A bounded backup changes one node’s action and transition parameters to improve its value while keeping controller size fixed.A linear program finds the parameters; the update considers new parameters for the first step and uses the original controller thereafter.Source: §3.2.4 · p. 14, Table 4 · p. 15
- Repeated bounded backups can reach a local optimum where each node’s value function touches the value function from a full dynamic-programming backup.A bounded backup is a value-preserving transformation.Source: §3.2.4 · pp. 14–15
4. Decentralized Dynamic Programming
The lack of a shared belief state in DEC-POMDPs motivates a multiagent policy-iteration algorithm with correlated stochastic controllers.
4. Decentralized Dynamic Programming
- Because DEC-POMDPs lack a known equivalent shared belief-state MDP, the paper develops an optimal policy-iteration algorithm that includes the POMDP version as a special case.The section introduces correlated controllers and gives a convergence proof with efficient value-preserving transformations.Source: §4 · pp. 15–16
- A shared source of randomness lets agents correlate their actions without communication and can increase solution quality while minimally increasing representation size.The policy iteration alternates exhaustive backups with value-preserving transformations.Source: §4 · pp. 15–16
- Figure 5 contrasts a controller’s value function with the result of a full dynamic-programming update at a local optimum for bounded backups.The solid line is the controller value; the dotted line is the full-update value.Source: Figure 5 · p. 16
4.1 Correlated Finite-State Controllers
Local finite-state controllers describe independent agent policies, while a correlation device permits shared randomization. The example shows that correlation can improve reward with limited memory, though larger uncorrelated controllers can match its value.
4.1.1 Local Finite-State Controllers
- Independent joint controllers combine local stochastic finite-state controllers, with each agent choosing actions and transitioning nodes based on its own node and observations.The agents’ local controllers determine a joint conditional distribution over actions and next nodes.Source: §4.1.1 · pp. 16–17
4.1.2 The Utility of Correlation
- Uniform independent choices between A and B yield expected reward −R/2 per step and −R/[2(1−β)] long-term, which no independent policy exceeds for all states; correlated AA/BB choices yield 0, with a gap that grows arbitrarily with R.Source: §4.1.2 · p. 17
4.1.3 Correlated Joint Controllers
- A correlation device is a finite-state machine that shares random signals with agents at each step without conveying information about their observations.The device and local controllers together form a correlated joint controller; a one-node device is equivalent to an independent joint controller.Source: §4.1.3 · p. 18
- Correlation can improve value for fixed-size controllers, but a finite uncorrelated controller can match or exceed that value; how much extra memory is needed generally remains open.In the example, two-node uncorrelated controllers for each agent suffice to remove the correlation device.Source: §4.1.3 · pp. 18–19
4.2 Policy Iteration
DEC-POMDP policy iteration alternates exhaustive backups with value-preserving transformations. The result is ϵ-optimal for all initial states after finitely many iterations.
4.2.1 Exhaustive Backups
- An exhaustive backup adds one-step-policy nodes to every agent’s local controller while leaving the correlation device unchanged.Repeated exhaustive backups amount to brute-force search over deterministic policies and converge to optimality, but are inefficient.Source: §4.2.1 · p. 19
4.2.2 Value-Preserving Transformations
- A multiagent value-preserving transformation requires dominating convex combinations for nodes in the local controllers and correlation device.The relation between controllers is defined by mappings from old nodes to distributions over new nodes and is transitive.Source: §4.2.2 · p. 20
4.2.3 Algorithmic Framework
- Each iteration evaluates the controller, performs an exhaustive backup, and then applies value-preserving transformations.The algorithm terminates when the discounted reward bound β^(t+1)|Rmax|/(1−β) is at most ϵ.Source: §4.2.3 · p. 20
- Exhaustive backups preserve the ordering induced by value-preserving transformations, so applying a transformation before a backup does not lose value after that backup.This ordering supports the convergence argument for alternating the two operations.Source: §4.2.3 · p. 21
- For any ϵ, policy iteration returns a correlated joint controller that is ϵ-optimal for all initial states in finitely many iterations.The convergence argument relates policy iteration to exhaustive backups, which are optimal over a sufficiently long finite horizon.Source: §4.2.3 · p. 21
4.3 Efficient Value-Preserving Transformations
The section extends two value-preserving operations to multiagent controllers: removing dominated nodes and improving controller parameters without increasing size. Both operations can be applied to local controllers or the correlation device, with their searches formulated as linear programs.
4.3.1 Controller Reductions
- A local or correlation-device node can be removed when a distribution over other nodes preserves at least its value across relevant states and other controllers’ nodes.For a local node, the other agents’ nodes are treated as hidden state; successful replacement redirects incoming links so the removed node is no longer reached.Source: §4.3.1 · p. 22
4.3 Efficient Value-Preserving Transformations
- The linear programs for reductions and bounded updates are polynomial in problem and controller sizes but exponential in the number of agents.The reduction programs cover local and correlation-device nodes; the bounded-update programs likewise handle both node types.Source: §4.3.1 · p. 22, §4.3.2 · p. 24
4.3.2 Bounded Dynamic Programming Updates
- Bounded backups change a local or correlation-device node’s parameters for the first step while retaining the original controller thereafter, and preserve value.The new parameters are found by a linear program; the value-preservation result applies to either type of node.Source: §4.3.2 · pp. 24, 26
4.4 Open Issues
The authors identify limits to extending desirable single-agent POMDP methods to DEC-POMDPs: they lack an equivalent belief-state MDP, residual-based error bounds, and general pruning methods that avoid exhaustive backups.
4.4 Open Issues
- Although policy iteration converges, the authors have not extended other desirable POMDP properties to the multiagent case, and no equivalent belief-state MDP is known.The absence of an equivalent belief-state MDP is identified as an open issue.Source: §4.4 · p. 26
4.4.1 Error Bounds
- The method provides no Bellman-residual error bound; distance to optimality must instead be bounded using the discount rate and iteration count.In the single-agent case, two successive value functions can provide such a bound.Source: §4.4.1 · p. 26
4.4.2 Avoiding Exhaustive Backups
- Without a DEC-POMDP Bellman equation, the authors cannot generalize POMDP pruning methods that rule out nodes before exhaustive backups.A limited exception allows POMDP node generation after exhaustive backups for all but one agent; generally, the other agents’ nodes must first be generated.Source: §4.4.2 · pp. 26–27
5. Heuristic Policy Iteration
Heuristic policy iteration focuses pruning on belief points generated from an initial state under assumptions about other agents’ actions. It can yield more concise controllers and higher solution quality for a given initial distribution, but does not retain optimality guarantees.
5. Heuristic Policy Iteration
- The heuristic sacrifices optimality to prune at selected centralized belief points, often producing more concise controllers with higher solution quality for a given initial distribution.The optimal method may generate large controllers and unnecessary nodes because it must improve value for any initial state.Source: §5 · p. 27
5.1 Directed Pruning
- Belief-point pruning can remove nodes simultaneously, but pruning each agent while holding others fixed retains policies useful only alongside other agents’ suboptimal policies.Simultaneous removal of such policy sets could reduce controller size, but an automated value-preserving approach that maintains optimality remains open.Source: §5.1 · p. 28
5.2 Belief Set Generation
- For each agent, belief points are generated from the initial state by updating beliefs over action-observation pairs while assuming fixed action distributions for the other agents.Given those distributions and the transition and observation models, the belief-state update can be calculated.Source: §5.2 · pp. 29–30
5.3 Algorithmic Framework
- At each of k belief points, the algorithm selects the best initial-node combination, prunes nodes that do not contribute, then uses linear programs to prune further.It repeats backup and pruning while controller parameters change; nonlinear optimization over the belief points can also be used to improve solution quality.Source: §5.3 · p. 30
6. Dynamic Programming Experiments
Experiments compared policy-iteration variants on the two-agent tiger, meeting-in-a-grid, and box-pushing problems. Exhaustive backups were resource-intensive; bounded and heuristic updates enabled higher-valued controllers, with heuristic policy iteration plus NLP optimization producing the strongest reported results.
6.1 Test Domains
- The experiments used three domains—the two-agent tiger, meeting in a grid, and box pushing—with 2, 16, and 100 states, respectively.All domains used a discount factor of 0.9.Source: §6.1 · pp. 31–32
6.2 Exhaustive Backups and Controller Reductions
- Controller reductions produced smaller controllers than exhaustive backups alone, while bounded updates improved value at each step in some cases.Exhaustive backups quickly exhausted memory, allowing only a few iterations on the test problems.Source: Table 10 · p. 33, §6.2 · p. 33
6.3 Bounded Dynamic Programming Updates
- Bounded-only runs found higher-valued solutions than exhaustive backups in all three problems, although the comparison was not exhaustive.For the most part, increasing the correlation device from one node to two increased value; larger controllers could make acceptable bounded updates harder and lead to local optima.Source: §6.3 · pp. 34–35, Figure 8 · p. 35
6.4 Heuristic Dynamic Programming Updates
- Heuristic policy iteration completed more iterations than the optimal methods and consequently produced higher values; NLP optimization further raised values, with a small time overhead.The six-node-per-agent tiger-problem controller was known to be suboptimal.Source: §6.4 · p. 36
6.5 Discussion
- Heuristic policy iteration with NLP optimization achieved at least the highest value obtained in each test problem, and sometimes markedly exceeded other approaches.The authors report these as the highest published values they knew of for all three domains.Source: Figure 9 · p. 37, §6.5 · p. 37
7. Conclusion
The paper presents policy iteration for DEC-POMDPs, alternating exhaustive backups with value-preserving transformations to converge to optimality. It also identifies scalability limits and possible extensions for structured problems and general-sum games.
7. Conclusion
- The algorithm alternates exhaustive backups with value-preserving transformations, extending controller reductions and bounded backups to the multiagent case and converging to optimality.The authors describe it as the first nontrivial exact algorithm for DEC-POMDPs and a bridge to POMDP dynamic programming.Source: §7 · pp. 37–38
- The heuristic version is more scalable and produces higher values on the authors’ test problems, but sacrifices convergence to optimality.Source: §7 · p. 38
- The paper frames its approach as a foundation, while noting that more challenging problem instances and structure-specific solution techniques remain open challenges.Source: §7 · p. 38
- The authors identify general-sum games as an extension, proposing transformations that preserve value for all agents or target individual agents as possible routes toward Pareto optimality or Nash equilibrium.These directions remain to be developed for the noncooperative case.Source: §7 · pp. 38–39
- The general DEC-POMDP representation grows exponentially with the number of agents, making it infeasible for large agent populations.With local interactions, factored transitions, and cluster-local rewards, problem size can instead be exponential in the maximum number of directly interacting agents.Source: §7 · p. 39
- With compact representations, value-preserving transformations can treat other agents’ controller nodes as hidden state, while avoiding that state when transitions and rewards do not depend on those agents.A compact representation and algorithm extensions were proposed by Nair et al. (2005).Source: §7 · p. 39
Appendix A. Proof of Theorem 1
The proof shows that a finite-size joint controller without a correlation device can match or exceed the value of a correlated joint controller at a given initial state. It uses approximation by regular sequences and embeds a suitable sequence in the agents’ controllers.
Appendix A. Proof of Theorem 1
- Any sequence’s value can be approximated within any ϵ by another sequence, using the infinite-horizon discount factor to bound the effect of its remaining suffix.The construction retains a finite prefix and replaces the rest with an arbitrary sequence.Source: Appendix A · pp. 39–40
- A finite-size joint controller without a correlation device always exists that achieves at least the correlated controller’s value for a given initial state.A regular sequence can be implemented by a finite-state controller embedded within each agent’s controller.Source: Appendix A · p. 40
- The proof reduces the claim to finding a regular correlation sequence whose value is at least the expected value of the correlated controller.The argument divides into cases based on the expectation’s relation to the supremum of sequence values.Source: Appendix A · p. 40
- When no regular sequence has value equal to the expectation, the proof argues that the expectation is below the supremum and uses a prefix neighborhood to obtain a regular sequence of at least equal value.The authors describe this case argument as somewhat informal and note that cylinder sets can formalize it.Source: Appendix A · p. 40
Appendix B. Proof of Lemma 1
Lemma 1 establishes that exhaustive backups preserve the ordering between correlated joint controllers. Its proof maps old and newly added controller nodes between the backed-up controllers.
Appendix B. Proof of Lemma 1
- The proof assumes no correlation device for ease of exposition, stating that including one is straightforward but tedious.Source: Appendix B · p. 40
- If correlated joint controller C is no better than D, their exhaustive backups preserve that ordering.Source: Appendix B · p. 41
- For nodes added by exhaustive backup, the proof maps new nodes in one backed-up controller to distributions involving only new nodes in the other.The newly added nodes are deterministic, with actions and transition rules used to specify the mappings.Source: Appendix B · p. 41