Incremental Least Squares Policy Iteration for POMDPs

Hui Li, Xuejun Liao, Lawrence CarinAAAI 2006

Introduction

Planning in uncertain environments is typically modeled using Partially Observable Markov Decision Processes (POMDPs). Unlike standard Markov Decision Processes, a POMDP agent does not know the exact state; instead, it receives noisy observations and maintains a "belief state"—a probability distribution over all possible real states. However, the continuous and infinite nature of the belief space leads to the "curse of dimensionality," making exact solutions computationally intractable for real-world applications.

While "point-based" Value Iteration (VI) methods have improved scalability by focusing on finite belief sets, Policy Iteration (PI) has remained difficult to scale because it traditionally requires policy improvement across the entire belief simplex. This paper introduces Incremental Least Squares Policy Iteration (ILSPI), a novel algorithm that adapts the efficiency of Least Squares Policy Iteration to the POMDP framework.

Methodology: The ILSPI Algorithm

ILSPI overcomes the complexity of POMDPs through four key components:

  1. Reachable Belief Sampling: The algorithm samples a set of belief points that the agent is likely to encounter during execution. By focusing only on reachable states, the continuous problem is reduced to a manageable discrete set.
  2. Least Squares Policy Evaluation: The value function is represented as a linear combination of basis functions: $V^\pi(b) = w^T \phi(b)$. ILSPI uses a least-squares approach to minimize the Bellman residual, ensuring an accurate approximation of the policy's value.
  3. Incremental Basis Selection: To maintain a lean model, ILSPI adds basis functions one by one. It uses a specific mathematical criterion to select functions that most significantly reduce the Bellman error.
  4. Pointwise Policy Improvement: Once the value function is approximated, the policy is updated by selecting the optimal action for each sampled belief point.

Key Insights: Rapid Convergence

A significant advantage of ILSPI is its convergence speed. While Value Iteration may require hundreds of iterations to refine a value function, Policy Iteration often reaches a near-optimal policy in very few steps.

Convergence of the value function and policy over iterations 0 to 5 for the Tiger problem.

As shown in the figure above, the initial noisy value function (Iteration 0) rapidly stabilizes. By Iteration 3, the policy and value function closely resemble the optimal solution, demonstrating the efficiency of the incremental least-squares approach.

Experimental Results

The authors evaluated ILSPI on several classic POMDP benchmarks, including Tiger-grid, Hallway, and Tag.

  • Efficiency: In the Hallway navigation task, ILSPI achieved a reward of 0.54 in 66 seconds, significantly faster than the original PBVI (288s).
  • Performance: On the Tiger-grid problem, ILSPI reached a reward of 2.21, comparable to state-of-the-art results (2.25–2.35) while utilizing a simpler implementation.
  • Scalability: The algorithm was tested on the Tag problem, which features a large state space of 870 states.
Performance comparison on the Tag problem benchmark ($|S|=870$).

While ILSPI remained functional on the Tag problem, it was slightly less accurate than specialized solvers like HSVI2. However, it maintained a competitive profile regarding the number of belief points or iterations required to reach its solution.

Conclusion and Future Work

ILSPI provides a robust bridge between least-squares methods and partially observable environments. Its strength lies in its ability to find high-quality policies with minimal iterations by focusing on reachable belief states and smart basis selection.

Future research may address the algorithm's dependence on the initial basis function library and the computational bottlenecks associated with matrix inversions in extremely large state spaces. Additionally, improving exploration strategies during belief sampling could further enhance the robustness of the generated policies in unvisited regions of the state space.

Summary updated

BibTeX
@inproceedings{li2006incremental,
  author = {Hui Li and Xuejun Liao and Lawrence Carin},
  title = {{Incremental Least Squares Policy Iteration for POMDPs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure