Abstract
The value function of a POMDP exhibits the piecewise-linear-convex (PWLC) property and can be represented as a finite set of hyperplanes, known as $\alpha$-vectors. Most state-of-the-art POMDP solvers follow the point-based value iteration scheme, which performs Bellman backups on $\alpha$-vectors at reachable belief points until convergence. However, since each $\alpha$-vector is $|S|$-dimensional, these methods quickly become intractable for large-scale problems. In this work, we demonstrate that the PWLC property allows a POMDP's value function to be alternatively represented as a finite set of neural networks. This insight enables a novel POMDP planning algorithm called Neural Value Iteration (NVI), which combines the generalization capability of neural networks with the classical value iteration framework. Our approach achieves near-optimal solutions even in extremely large POMDPs that are intractable for existing offline solvers.
Introduction
Decision-making under uncertainty is often modeled as a Partially Observable Markov Decision Process (POMDP). In these environments, an agent maintains a "belief"—a probability distribution over all possible states—because it cannot observe the true state directly. While theoretically robust, solving POMDPs is notoriously difficult due to the "curse of dimensionality."
Traditionally, the optimal value function for a POMDP is represented as a set of $\alpha$-vectors. Because each vector's dimension equals the number of states $|S|$, memory requirements explode for large problems. For instance, a problem with one million states would require 8MB per $\alpha$-vector; a complex policy requiring thousands of such vectors quickly exceeds the capacity of modern hardware. Neural Value Iteration (NVI) addresses this by replacing these high-dimensional vectors with compact neural networks.
Methodology: Neural Value Iteration
NVI introduces two primary components to overcome the limitations of traditional point-based value iteration: the Finite-Network Controller and Neural Bellman Backups.
Finite-Network Controller (FNC)
The FNC is a policy representation that evolves the standard Finite-State Controller (FSC). In a typical FSC, nodes represent actions and transitions occur based on observations. In an FNC, each node additionally stores a small neural network ($\alpha_{NN}$) that approximates an $\alpha$-vector. This allows the policy to remain compact while predicting values for any specific state, effectively treating $\alpha$-vectors as functions rather than literal arrays.
Neural Bellman Backups
NVI performs "Neural Bellman Backups" by exploring the environment to collect representative belief points and then updating the value function. Unlike prior sampling-based methods that require long simulations, NVI uses its stored neural networks to "bootstrap" the value of future states. This significantly accelerates the backup process. For each new node in the controller, a Multi-Layer Perceptron (MLP) is trained to represent the value contribution across the state space.
Experimental Evaluation
The researchers evaluated NVI on three benchmark domains: RockSample(20, 20) (featuring over 419 million states), Light Dark, and Lidar Roomba.
Key Results
NVI demonstrates unprecedented scalability and performance. It is the first offline solver to successfully solve RockSample(20, 20), achieving a score of 11.63, significantly higher than the next best sampling-based solver, POMCGS (4.0).
Key advantages observed include:
- Memory Efficiency: By treating $\alpha$-vectors as functions, memory usage drops from gigabytes to megabytes.
- Stability: By maintaining the "maximum of a set" structure (PWLC property), NVI remains more stable than standard Reinforcement Learning approaches like Recurrent PPO.
- Compact Execution: The final policies use tiny 3-layer MLPs, making them suitable for deployment on resource-constrained hardware.
Conclusion and Future Work
Neural Value Iteration successfully bridges the gap between classical POMDP theory and modern deep learning. By leveraging the geometric structure of value functions, it enables offline planning for massive state spaces that were previously unreachable. Future work includes extending NVI to handle continuous action and observation spaces without discretization and improving planning speed through advanced belief selection heuristics.
Summary updated