Markov Decision Processes
and
Exact Solution Methods:
Value Iteration
Policy Iteration
Linear Programming
Pieter Abbeel
UC Berkeley EECS
Markov Decision Process
Assumption: agent gets to observe the state
[Drawing from Sutton and Barto, Reinforcement Learning: An Introduction, 1998]
Markov Decision Process (S, A, T, R, H)
Given
n
S: set of states
A: set of actions
T: S x A x S x {0,1,,H} [0,1],
Tt(s,a,s) = P(st+1 = s | st = s, at =a)
R: S x A x S x {0, 1, , H} <
Rt(s,a,s) = reward for (st+1 = s, st = s, at =a)
H: horizon over which the agent will act
Goal:
n
Find : S x {0, 1, , H} A that maximizes expected sum of rewards, i.e.,
Examples
MDP (S, A, T, R, H),
q
Cleaning robot
Walking robot
Pole balancing
Games: tetris, backgammon
Server management
Shortest path problems
Model for animals, people
goal:
Canonical Example: Grid World
The agent lives in a grid
Walls block the agents path
The agents actions do not
always go as planned:
80% of the time, the action North
takes the agent North
(if there is no wall there)
10% of the time, North takes the
agent West; 10% East
If there is a wall in the direction
the agent would have been taken,
the agent stays put
Big rewards come at the end
Solving MDPs
n
In an MDP, we want an optimal policy *: S x 0:H A
n
A policy gives an action for each state for each time
t=5=H
t=4
t=3
t=2
t=1
t=0
An optimal policy maximizes expected sum of rewards
Contrast: In deterministic, want an optimal plan, or sequence of actions,
from start to a goal
Outline
n
Optimal Control
=
given an MDP (S, A, T, R, , H)
find the optimal policy *
Exact Methods:
n
Value Iteration
Policy Iteration
Linear Programming
For now: discrete state-action spaces as they are simpler to get the main
concepts across. Will consider continuous spaces later!
Value Iteration
n
Algorithm:
n
n
Start with
for all s.
For i=1, , H
Given Vi*, calculate for all states s 2 S:
This is called a value update or Bellman update/back-up
= the expected sum of rewards accumulated when
starting from state s and acting optimally for a horizon of i steps
Value Iteration in Gridworld
noise = 0.2, =0.9, two terminal states with R = +1 and -1
Value Iteration in Gridworld
noise = 0.2, =0.9, two terminal states with R = +1 and -1
Value Iteration in Gridworld
noise = 0.2, =0.9, two terminal states with R = +1 and -1
Value Iteration in Gridworld
noise = 0.2, =0.9, two terminal states with R = +1 and -1
Value Iteration in Gridworld
noise = 0.2, =0.9, two terminal states with R = +1 and -1
Value Iteration in Gridworld
noise = 0.2, =0.9, two terminal states with R = +1 and -1
Value Iteration in Gridworld
noise = 0.2, =0.9, two terminal states with R = +1 and -1
Exercise 1: Effect of discount, noise
(a) Prefer the close exit (+1), risking the cliff (-10)
(1) = 0.1, noise = 0.5
(b) Prefer the close exit (+1), but avoiding the cliff (-10)
(2) = 0.99, noise = 0
(c) Prefer the distant exit (+10), risking the cliff (-10)
(3) = 0.99, noise = 0.5
(d) Prefer the distant exit (+10), avoiding the cliff (-10)
(4) = 0.1, noise = 0
Exercise 1 Solution
(a) Prefer close exit (+1), risking the cliff (-10) --- = 0.1, noise = 0
Exercise 1 Solution
(b) Prefer close exit (+1), avoiding the cliff (-10) -- = 0.1, noise = 0.5
Exercise 1 Solution
(c) Prefer distant exit (+1), risking the cliff (-10) -- = 0.99, noise = 0
Exercise 1 Solution
(d) Prefer distant exit (+1), avoid the cliff (-10) -- = 0.99, noise = 0.5
Value Iteration Convergence
Theorem. Value iteration converges. At convergence, we have found
the optimal value function V* for the discounted infinite horizon
problem, which satisfies the Bellman equations
Now we know how to act for infinite horizon with discounted rewards!
Run value iteration till convergence.
This produces V*, which in turn tells us how to act, namely following:
Note: the infinite horizon optimal policy is stationary, i.e., the optimal action at
a state s is the same action at all times. (Efficient to store!)
25
Convergence and Contractions
n
Define the max-norm:
Theorem: For any two approximations U and V
I.e. any distinct approximations must get closer to each other,
so, in particular, any approximation must get closer to the true U
and value iteration converges to a unique, stable, optimal
solution
Theorem:
I.e. once the change in our approximation is small, it must also
be close to correct
26
Outline
n
Optimal Control
=
given an MDP (S, A, T, R, , H)
find the optimal policy *
Exact Methods:
n
Value Iteration
Policy Iteration
Linear Programming
For now: discrete state-action spaces as they are simpler to get the main
concepts across. Will consider continuous spaces later!
Policy Evaluation
n
Recall value iteration iterates:
Policy evaluation:
At convergence:
Exercise 2
Policy Iteration
n
Alternative approach:
n
Step 1: Policy evaluation: calculate utilities for some
fixed policy (not optimal utilities!) until convergence
Step 2: Policy improvement: update policy using onestep look-ahead with resulting converged (but not
optimal!) utilities as future values
Repeat steps until policy converges
This is policy iteration
n
Its still optimal!
Can converge faster under some conditions
Policy Evaluation Revisited
n
Idea 1: modify Bellman updates
Idea 2: it s just a linear system, solve with
Matlab (or whatever),
variables: V(s),
constants: T, R
Policy Iteration Guarantees
Policy Iteration iterates over:
Theorem. Policy iteration is guaranteed to converge and at convergence, the current policy
and its value function are the optimal policy and the optimal value function!
Proof sketch:
(1) Guarantee to converge: In every step the policy improves. This means that a given policy can be
encountered at most once. This means that after we have iterated as many times as there are different
policies, i.e., (number actions)(number states), we must be done and hence have converged.
(2) Optimal at convergence: by definition of convergence, at convergence k+1(s) = k(s) for all states s.
This means
Hence
satisfies the Bellman equation, which means
is equal to the optimal value function V*.
34
Outline
n
Optimal Control
=
given an MDP (S, A, T, R, , H)
find the optimal policy *
Exact Methods:
n
Value Iteration
Policy Iteration
Linear Programming
For now: discrete state-action spaces as they are simpler to get the main
concepts across. Will consider continuous spaces later!
Infinite Horizon Linear Program
n
Recall, at value iteration convergence we have
LP formulation to find V*:
0 is a probability distribution over S, with 0(s)> 0 for all s 2 S.
Theorem. V* is the solution to the above LP.
Theorem Proof
Dual Linear Program
Interpretation:
n
Equation 2: ensures has the above meaning
Equation 1: maximize expected discounted sum of rewards
Optimal policy:
Outline
n
Optimal Control
=
given an MDP (S, A, T, R, , H)
find the optimal policy *
Exact Methods:
n
Value Iteration
Policy Iteration
Linear Programming
For now: discrete state-action spaces as they are simpler to get the main
concepts across. Will consider continuous spaces later!
Today and forthcoming lectures
n
Optimal control: provides general computational approach to tackle control
problems.
n
Dynamic programming / Value iteration
n
n
n
n
n
n
Optimal Control through Nonlinear Optimization
n
n
Exact methods on discrete state spaces (DONE!)
Discretization of continuous state spaces
Function approximation
Linear systems
LQR
Extensions to nonlinear settings:
n Local linearization
n Differential dynamic programming
Open-loop
Model Predictive Control
Examples:
