Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach
<|reference_start|>Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach: A recent theory shows that a multi-player decentralized partially observable Markov decision process can be transformed into an equivalent single-player game, enabling the application of \citeauthor{bellman}'s principle of optimality to solve the single-player game by breaking it down into single-stage subgames. However, this approach entangles the decision variables of all players at each single-stage subgame, resulting in backups with a double-exponential complexity. This paper demonstrates how to disentangle these decision variables while maintaining optimality under hierarchical information sharing, a prominent management style in our society. To achieve this, we apply the principle of optimality to solve any single-stage subgame by breaking it down further into smaller subgames, enabling us to make single-player decisions at a time. Our approach reveals that extensive-form games always exist with solutions to a single-stage subgame, significantly reducing time complexity. Our experimental results show that the algorithms leveraging these findings can scale up to much larger multi-player games without compromising optimality.<|reference_end|>
@article{peralez2024solving,
    title={Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form
  Game Approach},
    author={Johan Peralez, Aur'elien Delage, Olivier Buffet, Jilles S. Dibangoye},
    journal={arXiv preprint arXiv:2402.02954},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.02954},
    primaryClass={cs.GT cs.LG}
}