Figure 2: Influence diagram for a POMDP with information states and corresponding

![0_image_0.png](0_image_0.png)

information-state MDP. Information states ( I t and I t +1 ) are represented by double-circled nodes. An action choice (rectangle) depends only on the current information state.
Definition 1 (Complete information state). The complete information state at time t (denoted If ) consists of:
- a prior belief bo on states in S at time 0;

- a complete history of actions and observations {00,00,01,01, a1, . . ,0{-1,0{-1,0{} starting from time t = 0.
A sequence of information states defines a controlled Markov process that we call an information-state Markov decision process or information-state MDP. The policy for the information-state MDP is defined in terms of a control function µ : I → A mapping information state space to actions.  The new information state ( I t ) is a deterministic function of the previous state ( I t − 1 ), the last action ( a t − 1 ) and the new observation ( o t ):

## It = T(It-1, Ot, At-1).

T : I × Θ × A → I is the update function mapping the information state space, observations and actions back to the information space. 1 It is easy to see that one can always convert the original POMDP into the information-state MDP by using complete information states.

The relation between the components of the two models and a sketch of a reduction of a POMDP to an information-state MDP, are shown in Figure 2.

## 2.3  Bellman Equations For Pomdps

An information-state MDP for the infinite-horizon discounted case is like a fully-observable MDP and satisfies the standard fixed-point (Bellman) equation:

$$V^{*}(I)=\max_{a\in\bar{A}}\left\{\rho(I,a)+\gamma\sum_{I^{\prime}}P(I^{\prime}|I,a)V^{*}(I^{\prime})\right\}.\tag{1}$$
