Abstract
Partially observable Markov decision processes (POMDPs) are an intuitive and general way to model sequential decision making problems under uncertainty. Unfortunately, even approximate planning in POMDPs is known to be hard, and developing heuristic planners that can deliver reasonable results in practice has proved to be a significant challenge. In this paper, we present a new approach to approximate value-iteration for POMDP planning that is based on quadratic rather than piecewise linear function approximators. Specifically, we approximate the optimal value function by a convex upper bound composed of a fixed number of quadratics, and optimize it at each stage by semidefinite programming. We demonstrate that our approach can achieve competitive approximation quality to current techniques while still maintaining a bounded size representation of the function approximator. Moreover, an upper bound on the optimal value function can be preserved if required. Overall, the technique requires computation time and space that is only linear in the number of iterations (horizon time).
Introduction
Partially Observable Markov Decision Processes (POMDPs) provide a robust framework for modeling agents acting under uncertainty. However, solving them remains a significant computational hurdle. The core challenge lies in Value Iteration: the optimal value function is convex and typically represented as the maximum of a set of linear functions known as $\alpha$-vectors. In standard algorithms, the number of these vectors can grow exponentially with each time step, leading to a "state explosion" that forces a trade-off between accuracy and computational feasibility.
Methodology: Convex Quadratic Upper Bounds
This paper introduces CQUB (Convex Quadratic Upper Bound) iteration. Instead of representing the value function with an ever-growing collection of linear facets, CQUB approximates it using a fixed number of quadratic forms:
$$\hat{V}_n(b) = b^\top W_n b + w_n^\top b + \omega_n$$
Key technical innovations include:
- Convexity Preservation: The authors prove that the Bellman backup of a quadratic function remains convex, allowing for efficient optimization.
- Semidefinite Programming (SDP): To find the tightest possible upper bound, the update step is formulated as an SDP. This ensures the matrix $W$ remains positive semidefinite, guaranteeing global convexity.
- Dirichlet Integration: To minimize error across the belief simplex, the authors minimize the integral of the upper bound using a Dirichlet distribution, which makes the calculation mathematically tractable.
Experimental Evaluation
The CQUB method was evaluated on several standard POMDP benchmarks, including Maze, Tiger-grid, Hallway, Hallway2, and the high-dimensional Aircraft identification problem. These tasks represent various levels of state-space complexity and observational noise.
Performance and Efficiency
CQUB was compared against state-of-the-art point-based solvers, Perseus and PBVI. The results demonstrate that CQUB achieves competitive or superior rewards, particularly in complex domains.
As shown in the results table, in the Aircraft domain, CQUB achieved a reward of 16.70, outperforming Perseus (12.73) and matching PBVI (16.37). Crucially, CQUB maintained a significantly more compact representation. In the Aircraft task, CQUB used a representation size of 5,151, whereas PBVI required 47,000.
Key Insights
- Compactness: A single quadratic can often capture the "curvature" of a complex value function better than hundreds of linear facets, leading to constant space complexity relative to the number of iterations.
- Scalability: Because the representation size is fixed, computation time per iteration remains constant, resulting in total planning time that scales linearly with the horizon.
- Robustness: CQUB performed well even with fewer belief point constraints (e.g., 100 points) compared to the 1,000 points typically required by competing methods.
Conclusion
CQUB offers a promising alternative to traditional $\alpha$-vector methods by leveraging the efficiency of quadratic approximations and semidefinite programming. While SDP solvers currently introduce higher computational overhead per iteration than linear solvers, the bounded representation size makes CQUB highly attractive for long-horizon planning in complex environments. Future work may explore piecewise quadratic functions to further enhance accuracy in highly non-linear value landscapes.
Summary updated