Solving POMDPs: RTDP-Bel vs. Point-based Algorithms

Blai Bonet, Hector GeffnerIJCAI 2009 · OpenReview

Abstract

Point-based algorithms and RTDP-Bel are approximate methods for solving POMDPs that replace the full updates of parallel value iteration by faster and more effective updates at selected beliefs. An important difference between the two methods is that the former adopt Sondik's representation of the value function, while the latter uses a tabular representation and a discretization function. The algorithms, however, have not been compared up to now, because they target different POMDPs: discounted POMDPs on the one hand, and Goal POMDPs on the other. In this paper, we bridge this representational gap, showing how to transform discounted POMDPs into Goal POMDPs, and use the transformation to compare RTDP-Bel with point-based algorithms over the existing discounted benchmarks. The results appear to contradict the conventional wisdom in the area showing that RTDP-Bel is competitive, and sometimes superior to point-based algorithms in both quality and time.

Introduction

Partially Observable Markov Decision Processes (POMDPs) provide a robust framework for planning under uncertainty. However, solving them is computationally intensive because the "belief state"—the probability distribution over possible states—is continuous and high-dimensional. Historically, two distinct approaches emerged: point-based algorithms, which use geometric $\alpha$-vectors to approximate value functions in discounted POMDPs, and RTDP-Bel, which uses belief-state discretization for Goal POMDPs. Due to these different problem targets, the two methods were rarely compared directly, with a general assumption that point-based methods were superior. This research challenges that assumption by providing a mathematical bridge between the two models.

Methodology: Bridging the Gap

The core contribution of this work is a transformation that converts a discounted reward-based POMDP into an equivalent Goal POMDP. This is achieved by introducing a "dummy" target state. To account for the discount factor $\gamma$, the agent transitions to this target state with a probability of $1-\gamma$ at each step.

Transformation of a standard POMDP into a Goal POMDP by adding a target state.

With this transformation, the RTDP-Bel algorithm can be applied to standard discounted benchmarks. RTDP-Bel operates through real-time dynamic programming, running trials from an initial belief state and updating values greedily. To handle the infinite belief space, it employs a discretization function $d(b) = \text{ceil}(D \cdot b)$ to map beliefs into a hash table. This allows the algorithm to focus its computational resources only on the belief states actually encountered during simulation.

Experimental Evaluation

The authors compared RTDP-Bel against state-of-the-art point-based algorithms like HSVI2, PBVI+GER, and Perseus across several benchmarks, ranging from the classic Tiger-Grid to large-scale problems like RockSample and LifeSurvey1.

Comparative performance of RTDP-Bel and point-based algorithms across various POMDP benchmarks.

The results, summarized in the table above, reveal that RTDP-Bel is remarkably effective. In large-scale benchmarks such as Tag, RockSample[5,5], RockSample[5,7], and LifeSurvey1, RTDP-Bel achieved the highest Average Discounted Reward (ADR). Furthermore, it demonstrated significant speed advantages. For instance, in the LifeSurvey1 problem (over 7,000 states), RTDP-Bel found a superior policy in just 170 seconds, compared to nearly 12,000 seconds for PBVI+GER.

Discussion and Key Insights

The success of RTDP-Bel suggests several important takeaways for the POMDP community:

  1. Simplicity and Scalability: While $\alpha$-vectors offer a principled geometric approximation, the overhead of managing them becomes a bottleneck in large state spaces. RTDP-Bel’s simple hashing is computationally inexpensive, allowing for many more updates per unit of time.
  2. Effective Focus: By using stochastic simulation, RTDP-Bel naturally concentrates its updates on the "relevant" parts of the belief space—those the agent is likely to visit.
  3. Discretization Viability: Contrary to the belief that discretization would lead to poor policies due to "collapsing" distinct beliefs, the experiments show that a moderate discretization parameter (e.g., $D=15$) is sufficient for high-quality results in practice.

However, RTDP-Bel is not without weaknesses. It struggled in the Hallway benchmarks, where the specific geometric structure of the environment is better captured by the $\alpha$-vector representations of point-based methods.

Conclusion

This study demonstrates that RTDP-Bel is a powerful and often overlooked alternative for solving large-scale POMDPs. By bridging the gap between discounted and Goal POMDPs, the authors have shown that simpler, simulation-based discretization methods can outperform more complex geometric approximations in both speed and policy quality. Future research may explore hybrid approaches that combine the focused simulation of RTDP-Bel with the robust value representations of point-based algorithms.

Summary updated

Abstract

Point-based algorithms and RTDP-Bel are approximate methods for solving POMDPs that replace the full updates of parallel value iteration by faster and more effective updates at selected beliefs. An important difference between the two methods is that the former adopt Sondik's representation of the value function, while the latter uses a tabular representation and a discretization function. The algorithms, however, have not been compared up to now, because they target different POMDPs: discounted POMDPs on the one hand, and Goal POMDPs on the other. In this paper, we bridge this representational gap, showing how to transform discounted POMDPs into Goal POMDPs, and use the transformation to compare RTDP-Bel with point-based algorithms over the existing discounted benchmarks. The results appear to contradict the conventional wisdom in the area showing that RTDP-Bel is competitive, and sometimes superior to point-based algorithms in both quality and time.
BibTeX
@inproceedings{bonet2009solving,
  author = {Blai Bonet and Hector Geffner},
  title = {{Solving POMDPs: RTDP-Bel vs. Point-based Algorithms}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=ry-D1SMdWr},
}
Figure