9 Markov Decision Processes II

Admin

proj 1 due jul 6 (today!!!)
hw 3 due tuesday the 7th
hw 4 due thursday the 9th
proj2 due friday the 10th
midterm on the 20th

Recap: the grid world

maze like problem
agent lives in a grid
walls block the agents path
Noisy movement
80% of the time goes north if you want
10% east, 10% west, if you want to go north
the agent receives rewards each time step
small living reward each step
big rewards come at the end (good or bad)
goal: maximize sum of (discounted) rewards

Recap: MDPs

States \(S\)
Actions \(A\)
Transitions \(P(s'|s, a)\) or \(T(s, a, s')\)
rewards \(R(s, a, s')\)
start state \(s_0\)

Quantities

policy = map of states to actions
\(\pi(i)\)
utility = sum of discounted rewards (in an episode of a game)
values = expected future utility from a state (max node)
Q-values = expected future utility from a q-state (chance node)

ok so stars denote optimality

the value (utility) of a state \(s\):
\(V^*(s)\) = expected utility starting in \(s\) and acting optimally
the value (utility) of a q-state \((s, a)\):
\(Q^*(s)\) = expected utility starting out having taken action \(a\) from state \(s\) and (thereafter) acting optimally
the optimal policy
\(\pi^*(s)\) = optimal action from state \(s\)
\(s\) is a state
\((s, a)\) is a transition
\((s, a, s')\) is a transition from a q-node

the bellman equations

How to be optimal 1. take correct first action 2. keep being optimal

funny

definition of "optimal utility" via expectimax recurrence gives a simple one-step look ahead relationships amongst optimal utility values

\(V^*(s) = \max_a Q^*(s, a)\)

\(Q^*(s, a) = \sum_{s'} T(s, a, s')[R(s, a, s') + \gamma V^*(s')]\) (\(\gamma\) is discount) (action will happen with prob \(T(s, a, s')\))

so then:

\(V^*(s) = \max_a \sum_{s'} T(s, a, s')[R(s, a, s') + \gamma V^*(s')]\)

VALUE ITERATION

bellman equations characterize the optimal values
\(V^*(s) = \max_a \sum_{s'} T(s, a, s')[R(s, a, s') + \gamma V^*(s')]\)
value iteration computes them
\(V_{k+1}(s) \leftarrow \max_a \sum_{s'} T(s, a, s')[R(s, a, s') + \gamma V^*(s')]\)
value iteration is just a fixed point solution instead
... though the \(V_k\) vectors are also interpretable as time-limited values

time limited values

define \(V_k(s)\) to be the optimal value if the game ends in more time steps
equivalently it's what a depth \(k\) expectimax would give from \(s\)

if \(V\) ends in \(k\) timesteps, then it will solve the game perfectly.

Computing time limited values

if i wanted to actually solve this then i can actually catch specific values

what is the value at this state we can just put 0 for all of these states

what the bellman eqns require is \(V_1\) is made of \(V_0\), \(V_2\) is made of \(V_1\), etc. it actually becomes very easy to compute this tree.

usually you can solve the game in \(k\) timesteps but if you have a suboptimal policy then maybe not.

VALUE ITERATIONS

start with \(V_0 = 0\) for all states: no timesteps left means an expected reward sum of zero
given vector \(V_k(s)\) values, do one ply of expectimax from each state
\(V_{k+1}(s) \leftarrow \max_a \sum_{s'} T(s, a, s')[R(s, a, s') + \gamma V^*(s')]\)
repeat until convergence
complexity of each iteration: \(O(S^2 A)\)
\(S\) is states
\(A\) is actions
theorem: will converge to unique optimal values
basic idea: approximations get refined towards optimal values
policy may converge long before values do

policies might converge way before values do, because after many timesteps the changes might change by a little little bit while policies will remain the same.

car example (going fast going slow)

going fast 2 pts
going slow 1 pts
go fast when it's cold
go slow when it's hot
will overheat if you go fast while hot

state - action	outcomes
Hot - slow	50% cold, 50% hot
hot - fast	100% overheated
cold - slow	100% cold
cold - fast	50% cold, 50% hot
overheated	can't do anything

table:

Utility	cold	hot	overheated
\(V_0\)	0	0	0
\(V_1\)	2	1	0

v2 is where it gets weird what are the \(s'\)?

if i go slow, if i go fast? it gets pretty hefty to compute

\(V_2\) = 3.5, 2.5, 0

# V_{k+1}(s) = max over actions of sum over s' of T(s,a,s') * (R + V_k(s'))
# rewards: slow +1, fast +2 (gamma = 1)

# V_1 from V_0 = 0 everywhere
v1_cold_slow = 1 * (1 + 0)
v1_cold_fast = 0.5 * (2 + 0) + 0.5 * (2 + 0) =>
# hot: fast overheats, so slow wins
v1_hot_slow = 0.5 * (1 + 0) + 0.5 * (1 + 0) =>

# V_2 from V_1 = (cold 2, hot 1, overheated 0)
v2_cold_slow = 1 * (1 + 2)
v2_cold_fast = 0.5 * (2 + 2) + 0.5 * (2 + 1) =>
# hot: fast overheats, so slow wins
v2_hot_slow = 0.5 * (1 + 2) + 0.5 * (1 + 1) =>

Convergence*

how do we know the \(V_k\) vectors are going to converge?
Case 1: if the tree has maximum depth \(M\) then \(V_M\) has the actual untruncated values
Case 2: if the discount (\(\gamma\)) is less than 1
sketch: for any state \(V_k\) and \(V_{k+1}\) can be viewed as depth \(k+1\) expectimax results in nearly identical search trees
the difference is that on the bottom layer \(V_{k+1}\) has actual rewards while \(V_k\) has zeros
that last layer is at best all \(R_{max}\)
it is at worst all \(R_{min}\)
but everything is discounted by \(\gamma^k\) that far out
so \(V_k\) and \(V_{k+1}\) are at most \(\gamma^k \max(R)\) different
so as \(k\) increases the values will eventually converge

fairly simple proof by cases

POLICY METHODS

know the state values, i know what they do i know how they converge
but i don't know how to use them to pick the best action!

Policy evaluation

lets take a policy and compute the \(V\) values and identify if the values are optimal or not.

Fixed policies

do the optimal action
expectimax trees max over all actions to compute the optimal values
if we fixed some policy \(\pi(s)\), then the tree would be simpler - only one action per state
though the trees value would depend on which policy we fixed

instead of going through all the possible actions, computing all the \(\pi(s, a)\) we only compute one action per state. goes from branching factor \(a\) to branching factor 1

the \(Q\) values is going to iterate over all possible actions that's what each of the actions represents, the red lines in the diagram.

instead of doing this optimal thing, we will have only one like through the graph

we can compute the utilities for an optimal policy

another basic operation: compute the utility of a state \(s\) under a fixed (generally non-optimal) policy
define the utility of a state \(s\), under a fixed policy \(\pi\)
\(V^\pi(s)\) = expected total discounted rewards starting in \(s\) and following \(\pi\)
recursive relation (one step look ahead / bellman eqn)
\(V^\pi(s) = \sum_{s'} T(s, \pi(s), s')[R(s, \pi(s), s') + \gamma V^\pi(s')]\)

so that's policy evaluation: lets give an example

in this corridor where there are pits on either side we have 2 policies - always go right - because it's bad, all the numbers are really low cuz you keep jumping into the pit - always go forward - numbers are much higher because you're more likely to make it, know it's an optimal policy - because you get higher numbers because it's more optimal then it makes sense.

Policy evaluation

how do we calculate the \(V\)'s for a fixed policy \(\pi\)
idea 1: turn recursive bellman equations into updates (like value iteration)
\(V_0^\pi(s) = 0\)
\(V_{k+1}^\pi(s) \leftarrow \sum_{s'} T(s, \pi(s), s')[R(s, \pi(s), s') + \gamma V^\pi(s')]\)
efficiency: \(O(S^2)\) per iteration
it's better cuz we r not going through all possible \(A\)
Idea 2: without the maxes, the bellman eqns are just a linear system
solve with your favorite linear system solver (matrices!!!)

policy extraction

how do i find out what policy should i follow in order to get optimal values
how should we act
we need to mini expectimax (one step)
\(\pi^*(s) = \arg\max \dots\)