Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Expected Utility of an Action

In state , doing action gives the expected next state utility . The best action is:

Bellman Equation

The utilities of successive states are linked recursively:

Read it as:

  • receive the reward of the current state
  • choose the optimal action
  • end up in with probability
  • get the utility of that next state, discounted by

For states this is equations in unknowns. Because of the they are not linear, and expectimax search fails on infinite sequences, so they are solved iteratively.

Method 1: Value Iteration

  1. Start with for every state
  2. Update every state using the Bellman equation as a rule:
  1. Repeat until the values stop changing (convergence)

With infinitely many iterations it is guaranteed to reach the true utilities; in practice far fewer are enough. Each round spreads reward information one more step outwards from the rewarding states.

Method 2: Policy Iteration

Start with any policy and alternate:

  • policy evaluation: compute for every state under the current policy (no , so these equations are linear)
  • policy improvement: update the policy greedily

Stop when the policy no longer changes.

Code Sketch

def value_iteration(states, actions, P, R, gamma=0.9, tol=1e-6):
    U = {s: 0.0 for s in states}
    while True:
        U_new = {}
        for s in states:
            best = max(sum(p * U[s2] for s2, p in P(s, a).items())
                       for a in actions(s)) if actions(s) else 0.0
            U_new[s] = R(s) + gamma * best
        if max(abs(U_new[s] - U[s]) for s in states) < tol:
            return U_new
        U = U_new

Both methods need the transition model . When it is unknown, the agent must learn from experience, see Temporal Difference Learning.