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
- Start with for every state
- Update every state using the Bellman equation as a rule:
- 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_newBoth methods need the transition model . When it is unknown, the agent must learn from experience, see Temporal Difference Learning.