Research map / Learning theory and algorithms / Submodular and game algorithms
Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that under hierarchical information sharing (HIS), single-stage Dec-POMDP subgames can be solved as perfect-information extensive-form games with linear-time backward/forward induction, introduces nested-occupancy states, and proposes hPBVI, which scales point-based backups to up to 10 players.
Problem
Global (optimal or epsilon-approximate) solution of Dec-POMDPs is double-exponentially expensive in the number of players because single-stage subgames entangle all players' decision variables; scaling to many players is a major obstacle.
Approach
Under the hierarchical information-sharing (HIS) assumption, the single-stage subgame can be decomposed player-by-player into a perfect-information common-payoff extensive-form game, solved by backward induction in linear time in players, nodes and actions; nested-occupancy states compress histories further.
Key results
- hPBVI performs a point-based backup for 10 players on mabc(10) in about 139.82 s at horizon 30, whereas PBVI^enum times out at 4 players and PBVI^milp at 5 players.
- On grid3x3(2) at horizon 30, hPBVI converges in 0.61 s versus 1329.33 s for PBVI^milp.
- hPBVI attains equal or better values than A2C and IQL on most benchmarks, with exceptions mabc(4) and grid3x3(3) where local methods match the global optimum.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HIS-based extensive-form subgame backups in place of standard PBVI^milp backups | PBVI under HIS · grid3x3(2) | backup time (seconds): 1329.33 -> 0.61 | Helped |
| Use HIS-based extensive-form subgame backups rather than PBVI^milp | PBVI under HIS · recycling(3) | best value: 252.83 -> 252.83 | Helped |
| Use HIS-based extensive-form subgame backups rather than A2C | PBVI under HIS · mabc(4) | best value: 24.36 -> 24.94 | Hurt |
| Use HIS-based extensive-form subgame backups rather than IQL | PBVI under HIS · grid3x3(3) | best value: 28.16 -> 28.16 | No clear effect |
| Use HIS-based backups instead of standard global PBVI methods | PBVI under HIS · multi-player benchmarks | scalability to player count | Helped |
| Use HIS-based backups instead of A2C and IQL | PBVI under HIS · tested benchmarks other than mabc(4) and grid3x3(3) | best value | Helped |
Surprising findings
- Local methods A2C and IQL perform very well on weakly coupled domains such as mabc(4) and grid3x3(3), matching the global optimum there.
Limitations
- Results hold only under the hierarchical information-sharing structure, which is a restrictive assumption.
- Global hPBVI still has a complexity that grows exponentially with horizon, and experiments are limited to small benchmarks with up to 10 players.
- Experiments on the multi-player variants are limited to medium-sized domains; only the tree-like and line structures are discussed.
Experimental setup
Datasets: masplan.org Dec-POMDP benchmarks (mabc, recycling, grid3x3, boxpushing, mars, tiger) and their multi-player variants
Benchmarks: mabc recycling grid3x3 boxpushing mars tiger
Metrics: time per backup (seconds) best value at horizon 30 anytime value
Baselines: PBVI^enum PBVI^milp A2C IQL
Builds on: point-based value iteration occupancy-state MDP reformulation of Dec-POMDPs one-sided partially observable stochastic games FB-HSVI
Closest papers by meaning
- Optimally Solving Two-Agent Decentralized POMDPs Under One-Sided Information Sharing (ICML 2020 · similarity 0.88)
- History Filtering in Imperfect Information Games: Algorithms and Complexity (NeurIPS 2023 · similarity 0.87)
- On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games (NeurIPS 2024 · similarity 0.86)
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.86)
- Extensive-Form Game Solving via Blackwell Approachability on Treeplexes (NeurIPS 2024 · similarity 0.85)
- Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.