Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Markov Property
The Markov property: transition probabilities depend only on the current state, not on the history of how that state was reached. A sequential decision problem with this property is a Markov decision process (MDP).
Components
| Symbol | Meaning |
|---|---|
| states, starting from initial state | |
| actions available in state | |
| transition model: probability of reaching from by doing | |
| reward function: reward for being in | |
| policy: the action to take in each state, the solution of the MDP |
Example: Game Show
Four questions of rising difficulty. Before each one you can quit with your winnings so far, but a wrong answer loses everything.
| Question | Quit value before it | Value if all correct | |
|---|---|---|---|
| Q1 ($100) | 9/10 | 0 | |
| Q2 ($1,000) | 3/4 | 100 | |
| Q3 ($10,000) | 1/2 | 1,100 | |
| Q4 ($50,000) | 1/10 | 11,100 | 61,100 |
Work backwards from the last question:
- Q4: continue gives quit , so quit,
- Q3: continue gives quit , so continue,
- Q2: continue gives quit , so continue
- Q1: continue gives , so continue
Optimal policy: answer Q1 to Q3, then quit before Q4.
Example: Grid World
A robot on a grid moves in the intended direction with probability 0.8 and slips to each side with probability 0.1. Every non-terminal state has (a small cost per step), and two terminal cells give and . The optimal policy heads for while keeping away from the cell. Since the game can go on forever, backward induction does not work here.
Utility of a State Sequence
The optimal policy maximises the expected utility over all state sequences it can produce:
Summing rewards fails for infinite sequences, so rewards are discounted by :
Effects of discounting:
- sooner rewards count more than later ones
- the total utility stays bounded
- algorithms converge
The true utility of a state is the expected discounted reward when following the optimal policy from . It is computed with Value Iteration and Policy Iteration.