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

SymbolMeaning
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.

QuestionQuit value before itValue if all correct
Q1 ($100)9/100
Q2 ($1,000)3/4100
Q3 ($10,000)1/21,100
Q4 ($50,000)1/1011,10061,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.