What is the intuition behind grid-based solutions to POMDPs?

Question

After spending some time reading about POMDP, I'm still having a hard time understanding how grid-based solutions work.

I understand the finite horizon brute-force solution, where you have your current belief distribution, enumerate every possible collection of action/observation combinations for a given depth and find the expected reward.

I have tried to read some sources about grid-based approximations, for example, these slides describe the grid-based approach.

However, it's not clear to me what exactly is going on. I'm not understanding how the value function is actually computed. After you take an action, how do you update your belief states to be consistent with the grid? Does the grid-based solution simply reduce the set of belief states? How does this reduce the complexity of the problem?

I'm not seeing how this reduces the number of actions, observation combinations needed to be considered for a finite-horizon solution.

Answer 1

I will attempt to provide an answer to your questions based on the information you can find in the papers A Heuristic Variable Grid Solution Method for POMDPs (1997) by Ronen I. Brafman and Point-based value iteration: An anytime algorithm for POMDPs (2003) by Joelle Pineau et al.

A grid-based approximate solution to a POMDP attempts to estimate a value function only at a subset of the number of belief states. Why? Because estimating the value function for all belief states is typically computationally infeasible for non-small POMDPs, given that the belief-space MDP (i.e. an MDP where the state space consists of probability distributions over the original states of the POMDP) of a POMDP with $n$ states has an uncountably large state space. Why? Because of the involved probability distributions.

How do we compute the value for the belief states that do not correspond to a point of the grid? We can use e.g. interpolation, i.e. the value of a belief state that does not correspond to a point of the grid is computed as a function of the value of the belief states that correspond to other grid points (typically, the neighboring grid points).

Why is this approach feasible? The assumption is that interpolation is not as expensive as computing the value of a belief state. However, note that you may not need to interpolate at every step of your algorithm, i.e. interpolation could be performed only when the value of a certain belief state is required.

How do you compute the value of a belief state that corresponds to a grid point? It can be computed with a value iteration (dynamic programming) algorithm for POMDPs. An overview of a value iteration algorithm can be found in section 2 of the paper Point-based value iteration: An anytime algorithm for POMDPs. Here's an example of the application of the value iteration algorithm for POMDPs.

The grid-based approach, introduced in Computationally Feasible Bounds for Partially Observed Markov Decision Processes (1991) by William S. Lovejoy, is very similar to the point-based approach, which was introduced in Point-based value iteration: An anytime algorithm for POMDPs. The main differences between the two approaches can be found in section 3 of Point-based value iteration: An anytime algorithm for POMDPs.

The idea of discretizing your problem or simply computing the desired value at a subset of the domain has been applied in other contexts too. For example, in the context of computer vision, you can approximate the derivative (or gradient) of an image (which is thus considered a function) at discrete points of the domain (i.e. the pixels).

There's a Julia implementation of the first grid-based approximative solution to POMDP. There's also a Python implementation of the point-based approach. These implementations may help you to understand the details of these approaches.