The Bellman Optimality Equation

The Bellman optimality equation replaces the policy average with a maximum, characterizing the value of acting optimally.

The value of best behavior

The Bellman optimality equation characterizes the optimal value function directly, without reference to any particular policy. It states that the optimal value of a state equals the immediate reward plus discounted optimal value obtained by taking the best action, rather than averaging over a fixed policy's actions.

The equations

For state values: V*(s) = max over a of sum over s' of P(s' | s, a) [ R(s, a, s') + gamma V*(s') ]. For action values: Q*(s, a) = sum over s' of P(s' | s, a) [ R(s, a, s') + gamma max over a' of Q*(s', a') ]. The max operator is what distinguishes optimality from mere prediction.

Recovering the optimal policy

Once Q* is known the optimal policy is greedy: pi*(s) = argmax over a of Q*(s, a). This is why learning Q* is so attractive — the policy falls out with a single maximization and no model of the dynamics is needed.

Existence and uniqueness

For a finite MDP with gamma below 1, the Bellman optimality equation has a unique solution V*, and value iteration converges to it because the optimality operator is also a contraction. This guarantees that an optimal policy exists and can be found in principle.

From theory to practice

The optimality equation is exact only when the dynamics are known and the state space is small enough to enumerate. Value iteration solves it by repeated application; Q-learning approximates it from sampled transitions when the model is unknown; deep RL approximates Q* with a neural network for large spaces.