Scaling Internal-State Policy-Gradient Methods for POMDPs

AI summary

Overview

• Research area: Reinforcement learning / decision-making under uncertainty, specifically policy-gradient and finite-state-controller methods for partially observable Markov decision processes (POMDPs).
• Technical level: Advanced.
• Scope: The paper develops and empirically compares three policy-gradient algorithms (GAMP, IState-GPOMDP, Exp-GPOMDP) for learning memory-based policies in infinite-horizon POMDPs, both with a known model and through simulation only.

What This Paper Is About

Agents acting under noisy or partial observation cannot rely on their current sensory input alone; they need memory of the past. Policy-gradient methods have worked well for memoryless policies but have been less successful when memory is required. This paper builds three algorithms that learn policies with memory, represented as finite state controllers, and tests them on large POMDPs including noisy robot navigation and a multi-agent task with 21,632 states.

Key Contributions

1. GAMP (Gradient Approximation of Modelled POMDPs): a model-based algorithm that computes the average-reward gradient using a series matrix expansion (essentially Richardson iteration) of an exact gradient expression, making it feasible for problems with many thousands of states rather than the hundreds typically handled by existing model-based algorithms.
2. IState-GPOMDP: a model-free algorithm that estimates the gradient stochastically by sampling from the POMDP and the internal-state trajectories of the finite state controller, extending Williams' REINFORCE with memory to the infinite-horizon case.
3. Exp-GPOMDP: a partly Rao-Blackwellised variant of IState-GPOMDP that computes true expectations over internal-state trajectories (maintaining a belief over I-states) rather than sampling them, reducing gradient variance.
4. Convergence theory and empirical comparisons: theorems for each algorithm (theorems 1–4), including a result identifying "zero gradient regions" that cause finite-state-controller learning to fail, plus experiments on Pentagon navigation, Heaven/Hell, and a 21,632-state multi-agent factory problem.

Main Findings

• GAMP is far faster than exact gradient computation on Pentagon: with |S| = 209 and |G| = 5, exact computation of the gradient took 315 s for the stationary distribution π, 10.5 s for the matrix inverse [I − P + eπ′]⁻¹, and 36 s for ∇P (Pentium II @ 433 MHz). The approximate gradient took 3.50 s for π (ε = 0.0001, 1319 iterations) and 1.41 s for Richardson matrix inversion (N = 500), i.e. 11.3% of the time the true gradient required, with an angular error of 0.420° at N = 500. Approximating π accounted for 0.016° of that error.
• The Pentagon transition matrix is very sparse: even the noisy transition probabilities had only 2.4% of P containing non-zero elements, which the authors exploit for efficiency.
• GAMP scales to a 21,632-state multi-agent problem: two robots on a factory floor, 13 locations, 4 orientations, 16 joint actions, 1024 observations, 10% action failure and 10% sensor failure. GAMP used less than 47 Mb of RAM (AMD Athlon @ 1.3 GHz) and matched the hand-designed policy, with mean and maximum η of 6.51 (η values multiplied by 10²) and 1035 seconds to reach η = 5, over 10 runs.
• Sparse internal-state transitions are necessary: on Heaven/Hell (1540 parameters, 20 I-states, |S||G| = 400, T = 10⁷ gradient estimation steps, β = 0.99), GAMP with out-degree k = 3 reached mean η 9.01 (maximum 9.09), while dense fully connected FSCs produced gradient estimates within machine tolerance of 0 and mean η of 0.005. IState-GPOMDP with k = 3 reached mean 6.49 and maximum 9.09, while the dense version reached mean 0.018. The optimum is 9.09.
• A zero-gradient failure mode exists: theory (Theorem 4) shows that under symmetric parameters where I-state transition and action probabilities do not depend on the current I-state, the gradient with respect to the internal-state parameters is exactly zero, formalising why small random initialisations fail.
• Exp-GPOMDP trades per-step cost for lower variance: each gradient estimation step costs at least O(|G|(|G| + |U|)) versus O(|G| + |U|) for IState-GPOMDP, reduced to O(|G|(k + |U|)) with sparse transitions. On Pentagon with |G| = 20 and k = 3 it produced a superior result in fewer steps than IState-GPOMDP (mean η 2.26 vs 2.15).
• I-states outperform memoryless policies but not full belief states on Pentagon: IState-GPOMDP with |G| = 1 (memoryless) achieved η 1.35 (mean), while the Belief baseline reached η 3.65 maximum (mean 2.67), and the fully observable MDP reached η 4.93 mean. GAMP was second highest in maximum η at 20 I-states (2.80), and for |G| = 20 its mean (2.50) exceeded Belief.
• Comparison against prior published results: the best Belief agent (η = 3.65) achieved a discounted reward of 0.764 with an average of 27 steps to the goal, bracketed by Cassandra's results of 0.791 (known start state) and 0.729 (uniform initial belief state).
• Model-free scale: IState-GPOMDP required a minimum of 2 × 10⁶ gradient estimation steps on Pentagon, while Exp-GPOMDP required 10⁶ steps. Setting k > 3 caused failures due to small initial gradients.
• First model-free solution of Heaven/Hell: the authors state this is the first time Heaven/Hell has been solved using a model-less algorithm. Exp-GPOMDP was verified able to learn to visit the signpost, but one run takes more than 2 days on their cluster, preventing a formal comparison.
• Wall-clock comparisons are not directly comparable: IState-GPOMDP ran on 94 processors of a 550 MHz dual CPU PIII Beowulf cluster, while GAMP ran on a 1.3 GHz Athlon, roughly equivalent to 3 CPUs of the cluster.
• Theory links the stochastic estimate to the exact gradient: IState-GPOMDP's estimate Δ_T converges to π′(∇P)J_β with probability 1, and as β → 1, π′(∇P)J_β converges to ∇η. The variance of Δ_T scales as 1/[T(1 − β)], so π′(∇P)J_β is a good approximation to ∇η provided 1/(1 − β) exceeds the mixing time τ.

Methodology in Plain English

The agent is modelled as a finite state controller: a small set of internal memory states plus rules for moving between them based on observations and for picking actions. Two parameter sets govern these rules (θ for actions, ϕ for internal-state transitions), and the agent's goal is to adjust them to maximise the long-term average reward. The authors take three different routes to compute the direction in which to adjust those parameters. GAMP uses a known model of the world, writing the gradient in closed form and then replacing an expensive matrix inverse with an iterative series of matrix-vector multiplications, with the stationary distribution found by the power method. IState-GPOMDP instead interacts with the world, sampling trajectories and accumulating discounted "traces" of how each parameter affected recent choices, with rewards multiplied into those traces, in the style of REINFORCE. Exp-GPOMDP keeps the same interaction but, instead of sampling the internal memory state, tracks a probability distribution over internal states and averages over it, leaving only the world interaction stochastic. All experiments use softmax distributions over lookup tables initialised to zero, optimised with Polak-Ribiére conjugate-gradient ascent with a line search. To avoid the near-zero gradient problem, the authors use sparse controllers where each internal state connects to only k other states.

Why This Matters

This work sits between two extremes: memoryless policies that are too weak for most POMDPs, and belief-state methods that become intractable for large state spaces. It shows that finite state controllers can be learned at scale, and that where a model is available, gradient estimates can be computed with low bias and effectively zero variance, without needing slow or risky real-world sampling.

Real-world applications suggested by or implied in the paper:

• Manufacturing plants, which the authors note are often well modelled and are therefore natural candidates for the model-based GAMP algorithm.
• Noisy robot navigation, as tested in the Pentagon maze problem where actions and sensors fail.
• Multi-agent coordination tasks, such as the two-robot factory floor requiring cooperation without explicit communication.
• Any setting where random world interactions are slow, expensive or dangerous, where the authors argue model-based gradients are preferable because fewer samples are needed to estimate the model than to run model-free algorithms.

Industry relevance: the algorithms run on ordinary desktop hardware for problems an order of magnitude larger than competing methods, and the sparse-transition trick keeps per-step running time constant, which matters for deployment in real-time control settings.

Future Directions

• Developing factored-state policy-gradient algorithms, as named by the authors as future work.
• Incorporating further variance-reduction methods beyond the Rao-Blackwellisation used in Exp-GPOMDP.
• Investigating advanced iteration techniques such as Krylov subspace methods for computing x and the Lanczos method for the stationary distribution π, which the authors flag as worthy of further investigation.
• Completing a formal comparison of Exp-GPOMDP on Heaven/Hell, which was prevented by runs taking more than 2 days on their cluster, and understanding why setting k > 3 causes failures due to small initial gradients.

Target Audience

Researchers and graduate students in reinforcement learning, decision theory and robotics who are already familiar with POMDPs, policy-gradient methods and finite state controllers. The theoretical content (convergence theorems under four technical assumptions) and the complexity analysis make it most useful to those working on scalable policy-search algorithms; the empirical comparisons against belief-state and memoryless baselines will also interest practitioners evaluating how much memory a task actually requires.

Authors’ abstract

Policy-gradient methods have received increased attention recently as a mechanism for learning to act in partially observable environments. They have shown promise for problems admitting memoryless policies but have been less successful when memory is required. In this paper we develop several improved algorithms for learning policies with memory in an infinite-horizon setting -- directly when a known model of the environment is available, and via simulation otherwise. We compare these algorithms on some large POMDPs, including noisy robot navigation and multi-agent problems.