Pruning for Monte Carlo Distributed Reinforcement Learning in Decentralized POMDPs

Bikramjit BanerjeeAAAI 2013 · DOI

Abstract

Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) represent a significant challenge in multi-agent coordination, characterized by NEXP-complete complexity. While recent reinforcement learning (RL) approaches like MCQ-ALT have enabled model-free learning, they are often hindered by extreme sample requirements. This paper introduces IMCQ-ALT, an iterative algorithm that utilizes adaptive pruning to focus exploration on promising regions of the experience tree. By mathematically deriving a pruning threshold $\alpha(\tau)$, the algorithm ensures that suboptimal actions are discarded only when statistical confidence is high. Our evaluation across four benchmark domains shows that IMCQ-ALT achieves sample reductions of up to 91% while maintaining or improving policy performance.

Introduction

In multi-agent systems, agents must often cooperate to achieve a global objective under conditions of partial observability and limited communication. Dec-POMDPs provide a formal framework for these scenarios, but finding optimal policies is computationally daunting. Traditional solvers typically require a complete model of the environment's transitions and rewards, which is often unavailable in real-world applications.

Reinforcement learning offers a path forward by allowing agents to learn through interaction. However, existing methods like MCQ-ALT explore the entire action-observation space uniformly, leading to a "sample complexity" explosion. This paper addresses this inefficiency by proposing a method to "prune" the search space, focusing learning efforts where they matter most.

Methods: Iterative Pruning and IMCQ-ALT

The core innovation of this work is Iterative MCQ-ALT (IMCQ-ALT). Building on the "turn-taking" best-response framework of MCQ-ALT, the iterative version performs multiple passes over the time horizon $T$.

The Experience Tree and Pruning

The learning process can be visualized as exploring an "experience tree," where nodes represent sequences of actions and observations. In standard RL, every branch is explored. IMCQ-ALT, however, evaluates the quality (Q-values) of actions at each node. If an action's value falls below a specific threshold $\alpha(\tau)$, it is pruned, and the agent ceases to explore that branch.

The experience tree showing how a policy focuses on a specific subset of the available action-observation space.

The pruning threshold $\alpha(\tau)$ is designed to decrease as more samples are collected. This ensures that pruning is "opportunistic" yet safe: early in training, the agent is cautious, but as confidence grows, it aggressively discards clearly suboptimal strategies. This focused exploration allows the agent to allocate its limited sample budget to refining the most promising policies.

Key Results and Empirical Performance

The algorithm was tested on four classic Dec-POMDP benchmarks: Dec-Tiger, Recycling-Robots, Box-Pushing, and Mars-Rovers.

Sample Efficiency

The most striking result is the massive reduction in required training episodes. Across all domains, IMCQ-ALT reduced sample complexity by 61% to 91% compared to the original MCQ-ALT. For instance, in the Recycling-Robots domain, the algorithm achieved a 91% reduction. In Box-Pushing, it reached an optimal policy (zero error) while saving approximately 70% of the episodes.

Average relative error vs. log number of episodes. IMCQ-ALT (squares and circles) converges to lower error levels significantly faster than the baseline MCQ-ALT (crosses and stars), especially as the horizon T increases.

The Pruning Bonus

Beyond efficiency, the researchers observed a "pruning bonus." By eliminating suboptimal "noise" early in the learning process, the value estimates for the remaining high-quality actions became more accurate. This often resulted in a final policy that outperformed the one learned by the non-pruning baseline, particularly in longer-horizon problems where the search space is exponentially larger.

Conclusion

IMCQ-ALT demonstrates that intelligent pruning is a powerful tool for scaling multi-agent reinforcement learning. By focusing exploration on the most relevant parts of the experience tree, the algorithm drastically reduces the data burden of solving Dec-POMDPs. Future work will look into addressing "rare histories"—events with very low probability that still pose challenges for sample-based learners—to further enhance the robustness of decentralized coordination.

Summary updated

BibTeX
@inproceedings{banerjee2013pruning,
  author = {Bikramjit Banerjee},
  title = {{Pruning for Monte Carlo Distributed Reinforcement Learning in Decentralized POMDPs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8670},
}
Figure