Forward and Backward Bellman Equations Improve the Efficiency of the EM Algorithm for DEC-POMDP

Area of Science:

• Artificial Intelligence
• Computer Science
• Operations Research

Background:

• Decentralized partially observable Markov decision processes (DEC-POMDPs) model complex team decision-making scenarios.
• Existing Expectation-Maximization (EM) algorithms for DEC-POMDPs face computational inefficiencies due to infinite-horizon forward-backward calculations.

Purpose of the Study:

• To develop more computationally efficient algorithms for solving DEC-POMDPs.
• To enhance the planning capabilities in decentralized multi-agent systems.

Main Methods:

• Introduction of the Bellman EM (BEM) algorithm, incorporating forward and backward Bellman equations.
• Development of the modified Bellman EM (MBEM) algorithm to address BEM's computational bottleneck (matrix inversion) for large problems.
• Utilizing numerical experiments to compare the convergence rates of EM, BEM, and MBEM.

Main Results:

• BEM offers potential efficiency gains over EM by replacing infinite-horizon forward-backward computations with Bellman equations.
• MBEM overcomes BEM's limitations by avoiding matrix inversion, leading to improved efficiency for larger problem instances.
• Numerical experiments confirm that MBEM converges faster than the standard EM algorithm.

Conclusions:

• The proposed MBEM algorithm provides a significant improvement in computational efficiency for solving DEC-POMDPs.
• MBEM enhances the practical applicability of DEC-POMDP models in complex, large-scale decentralized decision-making scenarios.