the belief MDP is defined as a tuple where is the set of belief states over the POMDP states, is the same finite set of action as for the original POMDP, is the belief state transition function, is the reward function on belief states, is the discount factor equal to the in the original POMDP. Of these, and need to be derived from the original POMDP. is where is the value derived in the previous section and The belief MDP reward function () is the expected reward from the POMDP reward function over the belief state distribution: . The belief MDP is not partially observable anymore, since at any given time the agent knows its belief, and by extension the state of the belief MDP. Policy and value function Unlike the "originating" POMDP (where each action is available from only one state), in the corresponding Belief MDP all belief states allow all actions, since you (almost) always have some probability of believing you are in any (originating) state. As such, specifies an action for any belief . Here it is assumed the objective is to maximize the expected total discounted reward over an infinite horizon. When defines a cost, the objective becomes the minimization of the expected cost. The expected reward for policy starting from belief is defined as where is the discount factor. The optimal policy is obtained by optimizing the long-term reward. where is the initial belief. The optimal policy, denoted by , yields the highest expected reward value for each belief state, compactly represented by the optimal value function . This value function is solution to the Bellman optimality equation: For finite-horizon POMDPs, the optimal value function is piecewise-linear and convex. It can be represented as a finite set of vectors. In the infinite-horizon formulation, a finite vector set can approximate arbitrarily closely, whose shape remains convex. Value iteration applies dynamic programming update to gradually improve on the value until convergence to an -optimal value function, and preserves its piecewise linearity and convexity. By improving the value, the policy is implicitly improved. Another dynamic programming technique called policy iteration explicitly represents and improves the policy instead. Approximate POMDP solutions In practice, POMDPs are often computationally intractable to solve exactly, so computer scientists have developed methods that approximate solutions for POMDPs. Grid-based algorithms comprise one approximate solution technique. In this approach, the value function is computed for a