Average-Reward Decentralized Markov Decision Processes

Marek Petrik, Shlomo ZilbersteinIJCAI 2007 · OpenReview

Abstract: Formal analysis of decentralized decision making has become a thriving research area in recent years, producing a number of multi-agent extensions of Markov decision processes. While much of the work has focused on optimizing discounted cumulative reward, optimizing average reward is sometimes a more suitable criterion. We formalize a class of such problems and analyze its characteristics, showing that it is NP complete and that optimal policies are deterministic. Our analysis lays the foundation for designing two optimal algorithms. Experimental results with a standard problem from the literature illustrate the applicability of these solution techniques.

Introduction

In multi-agent systems, agents often need to coordinate their actions to achieve a common goal within an uncertain environment. While centralized Markov Decision Processes (MDPs) are well-understood and computationally tractable, their decentralized counterparts (DEC-POMDPs) are notoriously difficult, often categorized as NEXP-complete or even undecidable for infinite horizons.

Most existing research focuses on "discounted rewards," where immediate gains are prioritized over future ones. However, for long-running systems meant to operate indefinitely—such as sensor networks, computer networks, or autonomous robot fleets—the average reward over the long run is a more appropriate measure of success. This paper explores a specific, practical subclass: agents with independent transitions and observations that share a common reward function (DEC2-MDPs), providing a formal framework to analyze and solve these average-reward problems.

Methods

The authors introduce several key technical contributions to the field of decentralized control:

  1. Formalization: They define the DEC2-MDP model for two agents where transitions are independent ($P(s'|s,a) = P_1 \times P_2$), but the reward depends on the joint state and action. This structure allows for a more focused analysis of coordination without the complexity of coupled dynamics.
State transition diagram illustrating independent agent dynamics in a DEC-MDP.
  1. Complexity Analysis: By employing a reduction from the 3-SAT problem, the authors prove that finding the optimal stationary (Markov) policy for this class of problems is NP-complete. While still difficult, this is a significant improvement over the NEXP-complete complexity of more general decentralized models.
  2. Policy Characterization: A critical finding is that for this specific class of problems, there always exists an optimal policy that is deterministic. This means agents do not need to employ randomized strategies to achieve maximum average reward, significantly narrowing the search space for algorithms.
  3. Algorithmic Approach: The problem is first formulated as a Quadratic Program (QP). Because the objective function involves the product of two agents' probability distributions, it is non-linear. To resolve this, the authors apply Karush-Kuhn-Tucker (KKT) conditions to transform the QP into a Mixed Integer Linear Program (MILP). This transformation allows the use of powerful, off-the-shelf branch-and-bound solvers to find global optima efficiently.

Experimental Setup

The paper evaluates the proposed algorithms using a classic benchmark in decentralized control: the Multiple Access Broadcast Channel (MABC). In this scenario, two devices share a single communication channel. If both devices attempt to send a message simultaneously, a collision occurs, and the message is lost. The authors adapted the MABC to include message buffers of various sizes (5, 8, 10, and 15 states per agent). The objective is to maximize throughput (average reward) while minimizing collisions and buffer overflows.

Key Results

The experimental results demonstrate the practical viability of the MILP approach. The solver successfully handled problems with up to 15 states per agent—representing a joint state space of 225 states—in under 10 seconds on a standard PC.

Performance results for the MILP approach on the MABC benchmark.

Key insights from the results include:

  • Steady-State Simplicity: Average-reward analysis can be simpler than discounted-reward analysis because systems often settle into a repetitive "steady state" over time, bypassing the complexity of initial transient behaviors.
  • The Power of Independence: Focusing on transition and observation independence moves the problem from the realm of "undecidable" to "NP-complete," making it computationally expensive but practically solvable for many real-world applications.
  • KKT as a Bridge: Using KKT conditions to convert a non-convex quadratic problem into a MILP effectively bypasses the issue of local minima that often plagues iterative optimization methods.

Limitations and Future Work

Despite the success of the MILP approach, scalability remains a concern. As an NP-complete problem, the runtime will grow exponentially as the number of agents or states increases, potentially limiting the method to smaller agent groups. Furthermore, the model assumes observation independence, meaning agents cannot see each other's states or communicate. Relaxing this assumption is a major hurdle, as it would break the mathematical structure that enables the MILP formulation. Finally, the focus on stationary policies (decisions based only on the current state) leaves open the question of whether non-Markovian policies considering a longer history might yield higher rewards, though finding such policies is significantly more complex.

Summary updated

Abstract

Formal analysis of decentralized decision making has become a thriving research area in recent years, producing a number of multi-agent extensions of Markov decision processes. While much of the work has focused on optimizing discounted cumulative reward, optimizing average reward is sometimes a more suitable criterion. We formalize a class of such problems and analyze its characteristics, showing that it is NP complete and that optimal policies are deterministic. Our analysis lays the foundation for designing two optimal algorithms. Experimental results with a standard problem from the literature illustrate the applicability of these solution techniques.
BibTeX
@inproceedings{petrik2007average,
  author = {Marek Petrik and Shlomo Zilberstein},
  title = {{Average-Reward Decentralized Markov Decision Processes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=ryb9GmMdbH},
}
Figure