AI Research Portal

This paper introduces Deterministic Decentralized POMDPs (Det-Dec-POMDPs), a subclass of Dec-POMDPs where transitions and observations are deterministic, with uncertainty only in the initial state distribution. The authors propose Iterative Deterministic POMDP Planning (IDPP), a scalable solver based on the Joint Equilibrium Search for Policies (JESP) framework. IDPP optimizes for large-scale Det-Dec-POMDPs by iteratively computing each agent's best-response policy using an efficient Det-POMDP planner. The main empirical claim is that IDPP significantly improves scalability and enables efficient planning in large Det-Dec-POMDPs, outperforming existing Dec-POMDP solvers in terms of computation time and achieving competitive returns.

The paper addresses several bottlenecks in solving multi-agent planning problems:

High Complexity of Dec-POMDPs: Solving Dec-POMDPs optimally is NEXP-complete, even for finite horizons, due to their expressiveness.
Scalability Issues with Stochastic Observations: While Quasi-Deterministic Dec-POMDPs (QDet-Dec-POMDPs) simplify some aspects by assuming deterministic transitions, stochastic observations still significantly hinder scalability.

Formalization of Det-Dec-POMDPs: Introduction of Deterministic Decentralized POMDPs (Det-Dec-POMDPs), a new subclass of Dec-POMDPs with deterministic transitions and observations, extending single-agent Det-POMDPs to multi-agent settings.
Iterative Deterministic POMDP Planning (IDPP) Solver: Proposal of a practical and scalable solver, IDPP, specifically optimized for large-scale Det-Dec-POMDPs by leveraging their fully deterministic structure.
Scalability Enhancement: IDPP improves upon prior JESP frameworks by exploiting deterministic system dynamics, invoking an efficient Det-POMDP planner in each iteration to compute best-response policies, leading to significantly improved scalability.
New Scalable Benchmarks: Introduction of two scalable Det-Dec-POMDP benchmarks (Multi-Agent Canadian Traveler Problem and Collecting Problem) that scale to millions of states and thousands of observations per agent, to facilitate future research on algorithm scalability.

The proposed method, Iterative Deterministic POMDP Planning (IDPP), is an iterative best-response approach for solving Det-Dec-POMDPs.

Method Flow:

Heuristic Initialization: The process begins by initializing each agent's policy using a heuristic. This involves replacing other agents' FSC nodes with a default MDP policy that maps states to actions (a_i ← π_MDP(s_t)). This yields a deterministic model POMDP_init,i for each agent, which is then solved using standard Det-POMDP methods to compute an initial policy.
Iterative Best-Response Loop: After initialization, IDPP enters an iterative loop where agents update their policies until convergence to a Nash equilibrium policy set.
Agent Selection: In each iteration, an optimizing agent i is selected.
Fix Other Agents' Policies: The policies of all other agents (π_≠i) are fixed as deterministic Finite-State Controllers (FSCs).
Construct Best-Response Det-POMDP: For the selected agent i, a best-response model POMDP_BR,i is constructed. This model is proven to be a Det-POMDP when other agents' policies are fixed as deterministic FSCs. The extended state space e_t for agent i includes the current environment state (s_t), the current nodes of other agents' FSCs (n_≠i), and agent i's current observation (õ).
Solve Best-Response Det-POMDP: The constructed Det-POMDP_BR,i is solved efficiently using Det-MCVI (Schutz et al. 2025), a solver tailored for deterministic POMDPs.
Update Agent's Policy: Agent i's policy (π_i) is updated with the newly computed best-response policy.
Evaluation and Convergence Check: The joint policy set is evaluated, and the loop continues until policies have converged.

Deterministic Decentralized POMDP (Det-Dec-POMDP) Definition: A Det-Dec-POMDP is formally defined as a tuple (I, S, A, Ω, T, O, R, γ, b_0), where:
- I is the finite set of agents, with i ∈ I.
- S is the set of states, s ∈ S.
- A = ×_i∈I A_i is the set of joint actions, where A_i is the action set of agent i.
- Ω = ×_i∈I Ω_i is the set of joint observations, where Ω_i is the observation set of agent i.
- T(s, a, s') : S × A × S → {0, 1} is the deterministic transition function, mapping a state and joint action to a unique next state.
- O(a, s', o) : A × S × Ω → {0, 1} is the deterministic observation function, mapping a joint action and next state to a unique joint observation.
- R : S × A → R is the immediate reward function.
- γ ∈ (0, 1) is the discount factor for future rewards.
- b_0 ∈ Δ(S) is the initial belief, a probability distribution over initial states.
Finite-State Controllers (FSCs): Policies for agents in POMDPs and Dec-POMDPs are represented as FSCs, defined by a tuple (N, ψ, η, n_0), where N is a finite set of controller nodes, ψ: N → A is the action selection function, η: N × O → N is the node transition function, and n_0 ∈ N is the initial node.
Best-Response Det-POMDP Dynamics: When policies π_≠i of other agents are fixed as deterministic FSCs, agent i's best-response model POMDP_BR,i has the following dynamics for its extended state e_t = (s_t, n_≠i, õ):
- Transition Function: T_e(e_t, a, e_t+1) = Σ_s_t+1 T(s_t, (ψ_≠i(n_≠i), a), s_t+1) ⋅ 1_n_≠i_t+1=η_≠i(n_≠i_t, o_t+1) ⋅ O(s_t+1, (ψ_≠i(n_≠i), a), (õ_t, o_t+1)). This simplifies to 1 for exactly one e_t+1 due to deterministic transitions and observations.
- Observation Function: O_e(a, e_t+1, o_t+1) = Pr(o_t+1 | a, e_t+1) = Pr(o_t+1 | a, (s_t+1, n_≠i_t+1, õ_t+1)). This is deterministic.
- Reward Function: r_e(e_t, a) = r(s_t, a, ψ_≠i(n_≠i)).
Optimization: The best-response Det-POMDP for the selected agent i is solved using Det-MCVI (Schutz et al. 2025).
Implementation: All planning methods are implemented in C++.

Datasets:
- Multi-Agent Canadian Traveler Problem (MACTP): Configurable with grid size (N), number of agents (na), and number of stochastic edges (ne). Instances tested include (3,2,5), (4,2,8), (4,2,12), (5,2,14). State space |S| ranges from ~2.6k to >10M. Observations |Ω_i| range from 279 to ~1.83k.
- Collecting Problem: Configurable with grid height (H), width (W), number of agents (na), and number of boxes (nb). Instances tested include (4,3,2,2), (4,4,2,3), (5,5,2,4). State space |S| ranges from ~4.7k to ~2.82M. Observations |Ω_i| range from 166 to ~1.75k.
Metrics: Discounted accumulated rewards (Return) and computation time (in seconds). Memory usage (MB) for average and peak memory.
Baselines:
- InfJESP (You et al. 2021)
- MCJESP (You et al. 2023)
- MAA* (Szer, Charpillet, and Zilberstein 2012)
- Deterministic POMDP Heuristic (baseline described in Section 5)
- IQL (Tan 1993)
- MAPPO (Yu et al. 2021)
Numeric Results:
- MACTP(3,2,5): IDPP achieved a Return of 912.71 ± 0.32 with a Time of 1.8 ± 0.4 seconds. InfJESP achieved 918.37 ± 0.28 Return in 23.8 ± 1.4 seconds. MCJESP achieved 874.39 ± 34.93 Return in 159.2 ± 71.1 seconds.
- MACTP(5,2,14): IDPP achieved a Return of 873.16 ± 5.21 with a Time of 1706.6 ± 298.4 seconds. InfJESP was infeasible due to memory constraints. MCJESP achieved 531.13 ± 82.86 Return in 4115.8 ± 659.6 seconds.
- Collecting(5,5,2,4): IDPP achieved a Return of 315.56 ± 2.81 with a Time of 4662.3 ± 488.6 seconds. InfJESP was infeasible due to memory constraints. MCJESP achieved 237.09 ± 32.80 Return in 8509.6 ± 684.3 seconds.
- Memory Usage (MACTP(3,2,5)): MAA* (horizon 20 and 10) quickly exhausted memory. IDPP maintained consistently low memory usage, avoiding reasoning over every possible joint history.
Runtime/Training Cost:
- All planning methods had a time limit of 10,000 seconds.
- MARL methods (IQL, MAPPO) adopted a fixed training budget of 10,000 episodes (each episode lasting up to 100 steps).
- IDPP consistently outperforms other methods with significantly less computation time on large instances where InfJESP fails.

Applicability to General Dec-POMDPs: IDPP is not suitable for general Dec-POMDPs with stochastic transitions or observations; it should only be applied when environment dynamics are deterministic.
Single-Threaded Implementation: The current IDPP implementation is single-threaded, suggesting that further speedups could be achieved through parallelization.

Method evidence: "We then propose a practical solver, Iterative Deterministic POMDP Planning (IDPP), based on the classic Joint Equilibrium Search for Policies framework, specifically optimized to handle large-scale Det-Dec-POMDPs that existing Dec-POMDP solvers cannot handle efficiently." (section: Abstract)
Result evidence: "On large instances where InfJESP fails, IDPP consistently outperforms other methods with significant less computation time." (section: Results)
Limitation evidence: "While IDPP is efficient for Det-Dec-POMDPs, it is not suitable for general Dec-POMDPs with stochastic transitions or observations. Therefore, it should be applied only when environment dynamics are deterministic. Another limitation is that our current IDPP implementation is single-threaded, so further speedups may be achieved through parallelization." (section: Weaknesses / Limitations)

Scalable Solution Methods for Dec-POMDPs with Deterministic Dynamics

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures