Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912175395700736 |
|---|---|
| author | Peralez, Johan Delage, Aurélien Buffet, Olivier Dibangoye, Jilles S. |
| author_facet | Peralez, Johan Delage, Aurélien Buffet, Olivier Dibangoye, Jilles S. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02954 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach Peralez, Johan Delage, Aurélien Buffet, Olivier Dibangoye, Jilles S. Computer Science and Game Theory Machine Learning 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. |
| title | Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach |
| topic | Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2402.02954 |