Policy is a rule according to which actions are decided. In POMDPs, a policy is a map from beliefs to actions. This is an optimal way to decide about an action, since the current belief, as inferred by past actions and observations within a Bayesian context, contains all the information collected up to the current step (sufficient statistic of the history of actions and observations). Such a policy is induced by the optimal value function, i.e. the expected life-cycle cost, which is thus also defined over the belief space.

Although a belief is defined on a continuous space, the optimal value function is a set of finite vectors forming a piecewise linear and convex hyper-surface. Extending dynamic programming value iteration directly in this space to compute these vectors is feasible, however, it comes with an exponential complexity with the number of possible observations at every step. Point-based value iteration alleviates this complexity by operating on the equivalent belief-MDP problem, thus leveraging the polynomial complexity of value iteration in MDPs.

The basic concept of point-based value iteration is: (i) start from an initial probability distribution over states and/or parameters; (ii) traverse a trajectory of posterior beliefs by sampling, or selecting according to a pre-defined rule, actions and observations; (iii) perform vector backups over the collected beliefs to update the value function. Pruning techniques of dominated vectors and leverage of double-sided bounds in the exploration are also common in this approach. The basic steps are illustrated below.