Skip to content

Scaling Internal-State Policy-Gradient Methods for POMDPs

🕒 Published (v1): 2025-12-02 20:03 UTC · Source: Arxiv · Venue: ICML 2002 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper presents three policy-gradient algorithms—GAMP, IState-GPOMDP, and Exp-GPOMDP—for learning memory-augmented policies in infinite-horizon POMDPs using finite state controllers (FSCs). The model-based GAMP scales to POMDPs with tens of thousands of states via iterative matrix approximations, while the model-free variants use Monte-Carlo trajectory sampling with variance reduction. All three are evaluated on noisy robot navigation and multi-agent cooperation tasks.

Problem

Existing policy-gradient methods for POMDPs either assume memoryless policies (inadequate for tasks requiring history) or rely on full belief-state representations (intractable for large state spaces). Model-based gradient methods at the time were limited to ~hundreds of states, and model-free methods with memory suffered from high variance and zero-gradient failure modes at initialization.

Method

All three algorithms parameterize policies as stochastic finite state controllers (FSCs) with internal states (I-states) governed by softmax-parameterized transition distributions (φ) and action distributions (θ).

  • GAMP (model-based): Computes the exact gradient ∇η = π′(∇P)[I−P+eπ′]⁻¹r via Richardson/series matrix iteration (xN = ΣPⁿr), avoiding the O(|S|³|G|³) direct inversion. Uses the power method for the stationary distribution π. Exploits sparsity of P to achieve O(c|S||G|N) practical complexity.
  • IState-GPOMDP (model-free): Extends REINFORCE to infinite-horizon POMDPs with memory by maintaining eligibility traces over both I-state transitions and action choices, discounted by β to handle temporal credit assignment.
  • Exp-GPOMDP (model-free, variance-reduced): A partially Rao-Blackwellized variant that computes exact expectations over I-state trajectories via recursive belief updates α_t(g) rather than sampling them, reducing gradient variance at O(|G|(k+|U|)) cost per step.
  • Sparse FSC trick: Using out-degree k≪|G| in the FSC avoids zero-gradient regions at initialization where uniform I-state distributions make gradient w.r.t. φ vanish.

Key Contributions

  • GAMP: scales model-based POMDP policy gradient to ~21,632-state problems (order of magnitude larger than prior art) on commodity hardware via iterative gradient approximation with convergence bounds
  • IState-GPOMDP: first model-free infinite-horizon policy gradient with memory; convergence proof showing ∆_T → ∇η as T→∞, β→1
  • Exp-GPOMDP: Rao-Blackwellized variant that computes I-state expectations exactly, achieving better performance with fewer simulation steps than IState-GPOMDP
  • Formal characterization (Theorem 4) of zero-gradient failure regions and sparse FSC remedy
  • First reported model-free solution to the Heaven/Hell delayed-memory benchmark

Results

  • Multi-agent factory (21,632 states): GAMP achieves mean η=0.0651, matching the hand-designed policy (η=0.0651); converges in 1035 s on a 1.3 GHz CPU
  • Heaven/Hell (memory + delayed reward, 20 I-states, k=3): GAMP converges in 10/10 runs (34 s); IState-GPOMDP 8/10 runs (11,436 s on 94-CPU cluster); dense FSC variants: 0/10 runs for both
  • Pentagon robot navigation (|S|=209, up to |G|=20, k=3): GAMP best mean η=0.0289 (|G|=20, k=3); IState best η=0.0215; Exp best η=0.0226; Belief state upper bound η≈0.0365; MDP (fully observable) η≈0.0493
  • Exp-GPOMDP reaches higher η than IState-GPOMDP in fewer simulation steps for |G|=20, k=3 (Figure 6)
  • GAMP gradient approximation reaches 0.42° angular error from true gradient at N=500 iterations, using 11.3% of exact computation time

Limitations

  • GAMP requires a known environment model; impractical when dynamics must be learned from data
  • Convergence proofs are to local optima only; no global optimality guarantees
  • Sparse FSC (k≪|G|) mitigates zero-gradient regions but setting k>3 empirically causes failures
  • Exp-GPOMDP per-step cost is O(|G|²) vs O(|G|) for IState-GPOMDP, limiting scalability to very large FSCs
  • Wall-clock comparisons between model-based and model-free methods are confounded by vastly different hardware (1 Athlon vs. 94-CPU cluster)
  • Exp-GPOMDP's two-day runtime per run on Heaven/Hell precluded formal evaluation

Relevance to Agentic AI / LLM Agents

This work is foundational for agents operating under partial observability—a defining challenge for real-world LLM agents that receive incomplete, noisy context windows rather than full environment state. The FSC framework is a principled antecedent to modern recurrent/stateful agent architectures, and the sparse I-state transition trick anticipates selective attention and gating mechanisms. The multi-agent cooperation experiment (two robots coordinating without explicit communication) directly prefigures decentralized multi-agent LLM systems. The model-free variants' scalability (constant per-step cost, sublinear in |S|) is the property modern RL-from-interaction agent training pipelines require.