Improve as you go

Value iteration gives every state the value of its best move, sweeps until the values stop changing, then reads off the optimal policy once.

Part of Planning.

Read first

  • Better, then best

    Policy iteration alternates judging a policy and switching every state to its best-looking move; each round is never worse, and it reaches the optimal policy.

Read next

  • Skip the sweep

    Asynchronous dynamic programming backs up one state at a time in any order; values still settle, so you can back up only the states play reaches.

  • Two pulls, one answer

    Generalized policy iteration: evaluation pulls values toward the policy, improvement pulls the policy toward the values, and both meet at the best policy.