Solving POMDPs by Searching in Policy Space
This addresses the computational challenge of solving POMDPs, which are critical for decision-making under uncertainty in fields like robotics and AI, by offering a potentially more efficient alternative to traditional value-based methods.
The paper tackles solving Partially Observable Markov Decision Processes (POMDPs) by explicitly representing policies as finite-state controllers and iteratively improving them through search in policy space, resulting in a policy iteration algorithm that can outperform value iteration for infinite-horizon problems and a heuristic search algorithm that promises speedup by focusing on reachable regions.
Most algorithms for solving POMDPs iteratively improve a value function that implicitly represents a policy and are said to search in value function space. This paper presents an approach to solving POMDPs that represents a policy explicitly as a finite-state controller and iteratively improves the controller by search in policy space. Two related algorithms illustrate this approach. The first is a policy iteration algorithm that can outperform value iteration in solving infinitehorizon POMDPs. It provides the foundation for a new heuristic search algorithm that promises further speedup by focusing computational effort on regions of the problem space that are reachable, or likely to be reached, from a start state.