Bellman optimality equation

The Bellman optimality equation is the expectation equation with the averaging replaced by a maximum. It says the optimal value of a state equals the reward from the single best action plus the discounted optimal value of where that action leads. The phrase act optimally hides a self-referential truth: to be optimal now you take the best immediate action and then behave optimally forever after.

For action values it says Q-star at a state-action pair equals the expected immediate reward plus the discounted maximum optimal action value at the next state. Unlike the expectation equation it is nonlinear because of that maximum, but it has a unique solution, and that solution is the optimal value function. Value iteration and Q-learning both work by repeatedly applying this relation as an update; each sweep pulls the estimates closer to Q-star, and from Q-star an optimal policy falls out by choosing the maximizing action.