Markov Decision Processes in Reinforcement Learning
(Chapter 17)
Image source: P. Abbeel and D. Klein
Markov Decision Processes
Markov Decision Processes
•
In HMMs, we see a sequence of observations and
try to reason about the underlying state sequence
–
There are no actions involved
•
But what if we have to take an action at each step
that, in turn, will affect the state of the world?
Markov Decision Processes
•
Components:
–
S
t
a
t
e
s
s
,
b
e
g
i
n
n
i
n
g
w
i
t
h
i
n
i
t
i
a
l
s
t
a
t
e
s
0
–
A
c
t
i
o
n
s
a
•
Each state
s
has actions
A(s)
available from it
–
T
r
a
n
s
i
t
i
o
n
m
o
d
e
l
P
(
s
’
|
s
,
a
)
•
Markov assumption
: the probability of going to
s’
from
s
depends only on
s
and
a
and not on any other past
actions or states
–
R
e
w
a
r
d
f
u
n
c
t
i
o
n
R
(
s
)
•
P
o
l
i
c
y
(
s
)
:
t
h
e
a
c
t
i
o
n
t
h
a
t
a
n
a
g
e
n
t
t
a
k
e
s
i
n
a
n
y
g
i
v
e
n
s
t
a
t
e
–
The “solution” to an MDP
Overview
•
First, we will look at how to “solve” MDPs,
or find the optimal policy when the
transition model and the reward function
are known
•
S
e
c
o
n
d
,
w
e
w
i
l
l
c
o
n
s
i
d
e
r
r
e
i
n
f
o
r
c
e
m
e
n
t
l
e
a
r
n
i
n
g
,
w
h
e
r
e
w
e
d
o
n
’
t
k
n
o
w
t
h
e
r
u
l
e
s
o
f
t
h
e
e
n
v
i
r
o
n
m
e
n
t
o
r
t
h
e
c
o
n
s
e
q
u
e
n
c
e
s
o
f
o
u
r
a
c
t
i
o
n
s
Game show
•
A series of questions with increasing level of
difficulty and increasing payoff
•
Decision: at each step, take your earnings and
quit, or go for the next question
–
If you answer wrong, you lose everything
Q1
Q2
Q3
Q4
Correct
Incorrect:
$0
Correct
Incorrect:
$0
Quit:
$100
Correct
Incorrect:
$0
Quit:
$1,100
Correct:
$61,100
Incorrect:
$0
Quit:
$11,100
$100
question
$1,000
question
$10,000
question
$50,000
question
Game show
•
Consider $50,000 question
–
Probability of guessing correctly: 1/10
–
Quit or go for the question?
•
What is the expected payoff for continuing?
0.1 * 61,100 + 0.9 * 0 = 6,110
•
What is the optimal decision?
Q1
Q2
Q3
Q4
Correct
Incorrect:
$0
Correct
Incorrect:
$0
Quit:
$100
Correct
Incorrect:
$0
Quit:
$1,100
Correct:
$61,100
Incorrect:
$0
Quit:
$11,100
$100
question
$1,000
question
$10,000
question
$50,000
question
Game show
•
What should we do in Q3?
–
Payoff for quitting: $1,100
–
Payoff for continuing: 0.5 * $11,100 = $5,550
•
What about Q2?
–
$100 for quitting vs. $4,162 for continuing
•
What about Q1?
Q1
Q2
Q3
Q4
Correct
Incorrect:
$0
Correct
Incorrect:
$0
Quit:
$100
Correct
Incorrect:
$0
Quit:
$1,100
Correct:
$61,100
Incorrect:
$0
Quit:
$11,100
$100
question
$1,000
question
$10,000
question
$50,000
question
1/100
3/4
1/2
1/10
U = $11,100
U = $5,550
U = $4,162
U = $3,746
Grid world
R(s) = -0.04 for every
non-terminal state
Transition model:
0.8
0.1
0.1
Source: P. Abbeel and D. Klein
Goal: Policy
Source: P. Abbeel and D. Klein
Grid world
R(s) = -0.04 for every
non-terminal state
Transition model:
Grid world
Optimal policy when
R(s) = -0.04 for every
non-terminal state
Grid world
•
Optimal policies for other values of R(s):
Solving MDPs
•
MDP components:
–
S
t
a
t
e
s
s
–
A
c
t
i
o
n
s
a
–
T
r
a
n
s
i
t
i
o
n
m
o
d
e
l
P
(
s
’
|
s
,
a
)
–
R
e
w
a
r
d
f
u
n
c
t
i
o
n
R
(
s
)
•
The solution:
–
P
o
l
i
c
y
(
s
)
:
m
a
p
p
i
n
g
f
r
o
m
s
t
a
t
e
s
t
o
a
c
t
i
o
n
s
–
How to find the optimal policy?
Maximizing expected utility
•
The optimal policy should maximize the
expected
utility
over all possible state sequences produced
by following that policy:
•
How to define the utility of a state sequence?
–
Sum of rewards of individual states
–
Problem: infinite state sequences
Utilities of state sequences
•
Normally, we would define the utility of a state sequence
as the sum of the rewards of the individual states
•
P
r
o
b
l
e
m
:
i
n
f
i
n
i
t
e
s
t
a
t
e
s
e
q
u
e
n
c
e
s
•
S
o
l
u
t
i
o
n
:
d
i
s
c
o
u
n
t
t
h
e
i
n
d
i
v
i
d
u
a
l
s
t
a
t
e
r
e
w
a
r
d
s
b
y
a
f
a
c
t
o
r
b
e
t
w
e
e
n
0
a
n
d
1
:
–
Sooner rewards count more than later rewards
–
Makes sure the total utility stays bounded
–
Helps algorithms converge
Utilities of states
•
Expected utility obtained by policy
starting in state
s
:
•
The “true” utility of a state, denoted
U(s)
, is the expected
sum of discounted rewards if the agent executes an
optimal
policy starting in state
s
•
Reminiscent of minimax values of states…
Finding the utilities of states
U(s’)
Max node
Chance node
P(s’ | s, a)
•
W
h
a
t
i
s
t
h
e
e
x
p
e
c
t
e
d
u
t
i
l
i
t
y
o
f
t
a
k
i
n
g
a
c
t
i
o
n
a
i
n
s
t
a
t
e
s
?
•
How do we choose the optimal
action?
•
W
h
a
t
i
s
t
h
e
r
e
c
u
r
s
i
v
e
e
x
p
r
e
s
s
i
o
n
f
o
r
U
(
s
)
i
n
t
e
r
m
s
o
f
t
h
e
u
t
i
l
i
t
i
e
s
o
f
i
t
s
s
u
c
c
e
s
s
o
r
s
t
a
t
e
s
?
The Bellman equation
•
Recursive relationship between the utilities of
successive states:
End up here with
P(s’ | s, a)
Get utility
U(s’)
(discounted by
)
Receive reward
R(s)
Choose optimal action
a
The Bellman equation
•
Recursive relationship between the utilities of
successive states:
•
For
N
states, we get
N
equations in
N
unknowns
–
Solving them solves the MDP
–
We could try to solve them through expectiminimax
search, but that would run into trouble with infinite
sequences
–
Instead, we solve them algebraically
–
T
w
o
m
e
t
h
o
d
s
:
v
a
l
u
e
i
t
e
r
a
t
i
o
n
a
n
d
p
o
l
i
c
y
i
t
e
r
a
t
i
o
n
Method 1: Value iteration
•
Start out with every
U
(
s
) = 0
•
Iterate until convergence
–
During the
i
th iteration, update the utility of each state
according to this rule:
•
In the limit of infinitely many iterations, guaranteed
to find the correct utility values
–
In practice, don’t need an infinite number of iterations…
Value iteration
•
What effect does the update have?
Value iteration demo
Value iteration
Utilities with discount factor 1
Final policy
Input (non-terminal R=-0.04)
Method 2: Policy iteration
•
Start with some initial policy
0
and alternate
between the following steps:
–
P
o
l
i
c
y
e
v
a
l
u
a
t
i
o
n
:
c
a
l
c
u
l
a
t
e
U
i
(
s
)
f
o
r
e
v
e
r
y
s
t
a
t
e
s
–
P
o
l
i
c
y
i
m
p
r
o
v
e
m
e
n
t
:
c
a
l
c
u
l
a
t
e
a
n
e
w
p
o
l
i
c
y
i
+
1
b
a
s
e
d
o
n
t
h
e
u
p
d
a
t
e
d
u
t
i
l
i
t
i
e
s
Policy evaluation
•
Given a fixed policy
,
calculate
U
(
s
) for every
state
s
•
The Bellman equation for the optimal policy:
–
How does it need to change if our policy is fixed?
–
Can solve a linear system to get all the utilities!
–
Alternatively, can apply the following update:
Appendix: Linear Solution to the
Fixed Policy Utility Calculation
Markov Decision Processes (MDPs) involve states, actions, transition models, reward functions, and policies to find optimal solutions. This concept is crucial in reinforcement learning, where agents interact with environments based on actions to maximize rewards. MDPs help in decision-making processes and strategizing actions for desired outcomes. The process involves solving MDPs with known models and exploring reinforcement learning in uncertain environments for effective decision-making strategies.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Markov Decision Processes (Chapter 17) Image source: P. Abbeel and D. Klein
Markov Decision Processes In HMMs, we see a sequence of observations and try to reason about the underlying state sequence There are no actions involved But what if we have to take an action at each step that, in turn, will affect the state of the world?
Markov Decision Processes Components: States s, beginning with initial state s0 Actions a Each state s has actions A(s) available from it Transition model P(s | s, a) Markov assumption: the probability of going to s from s depends only on s and a and not on any other past actions or states Reward function R(s) Policy (s): the action that an agent takes in any given state The solution to an MDP
Overview First, we will look at how to solve MDPs, or find the optimal policy when the transition model and the reward function are known Second, we will consider reinforcement learning, where we don t know the rules of the environment or the consequences of our actions
Game show A series of questions with increasing level of difficulty and increasing payoff Decision: at each step, take your earnings and quit, or go for the next question If you answer wrong, you lose everything $100 question $1,000 question $10,000 question $50,000 question Correct: $61,100 Correct Correct Correct Q1 Q2 Q3 Q4 Incorrect: $0 Incorrect: $0 Incorrect: $0 Incorrect: $0 Quit: $100 Quit: $1,100 Quit: $11,100
Game show Consider $50,000 question Probability of guessing correctly: 1/10 Quit or go for the question? What is the expected payoff for continuing? 0.1 * 61,100 + 0.9 * 0 = 6,110 What is the optimal decision? $100 question $1,000 question $10,000 question $50,000 question Correct: $61,100 Correct Correct Correct Q1 Q2 Q3 Q4 Incorrect: $0 Incorrect: $0 Incorrect: $0 Incorrect: $0 Quit: $100 Quit: $1,100 Quit: $11,100
Game show What should we do in Q3? Payoff for quitting: $1,100 Payoff for continuing: 0.5 * $11,100 = $5,550 What about Q2? $100 for quitting vs. $4,162 for continuing What about Q1? U = $3,746 U = $4,162 U = $5,550 U = $11,100 $100 question $1,000 question $10,000 question $50,000 question 1/10 1/100 3/4 1/2 Correct: $61,100 Correct Correct Correct Q1 Q2 Q3 Q4 Incorrect: $0 Incorrect: $0 Incorrect: $0 Incorrect: $0 Quit: $100 Quit: $1,100 Quit: $11,100
Grid world Transition model: 0.1 0.8 0.1 R(s) = -0.04 for every non-terminal state Source: P. Abbeel and D. Klein
Goal: Policy Source: P. Abbeel and D. Klein
Grid world Transition model: R(s) = -0.04 for every non-terminal state
Grid world Optimal policy when R(s) = -0.04 for every non-terminal state
Grid world Optimal policies for other values of R(s):
Solving MDPs MDP components: States s Actions a Transition model P(s | s, a) Reward function R(s) The solution: Policy (s): mapping from states to actions How to find the optimal policy?
Maximizing expected utility The optimal policy should maximize the expected utility over all possible state sequences produced by following that policy: sequences state sequence ( ) sequence ( ) P U starting from 0 s How to define the utility of a state sequence? Sum of rewards of individual states Problem: infinite state sequences
Utilities of state sequences Normally, we would define the utility of a state sequence as the sum of the rewards of the individual states Problem: infinite state sequences Solution: discount the individual state rewards by a factor between 0 and 1: = + + + 2 ([ , , , ]) ( ) ( ) ( ) U s s s R s R s R s 0 1 2 0 1 2 R = t = ) 1 t max ( ) 0 ( R s t 1 0 Sooner rewards count more than later rewards Makes sure the total utility stays bounded Helps algorithms converge
Utilities of states Expected utility obtained by policy starting in state s: sequences U = ( ) sequence ( ) sequence ( ) s P U state starting from s The true utility of a state, denoted U(s), is the expected sum of discounted rewards if the agent executes an optimal policy starting in state s Reminiscent of minimax values of states
Finding the utilities of states What is the expected utility of taking action a in state s? Max node s ( | ' s , ) ( ) ' s P s a U ' Chance node How do we choose the optimal action? P(s | s, a) s = * ( ) arg max s A ( | ' s , ) ( ) ' s s P s a U ( ) a ' U(s ) What is the recursive expression for U(s) in terms of the utilities of its successor states? + = max ) ( ) ( s R s U s ( | ' s , ) ( ) ' s P s a U a '
The Bellman equation Recursive relationship between the utilities of successive states: s = + ( ) ( ) max A a ( | ' s , ) ( ) ' s U s R s P s a U ( ) s ' Receive reward R(s) Choose optimal action a End up here with P(s | s, a) Get utility U(s ) (discounted by )
The Bellman equation Recursive relationship between the utilities of successive states: s = + ( ) ( ) max A a ( | ' s , ) ( ) ' s U s R s P s a U ( ) s ' For N states, we get N equations in N unknowns Solving them solves the MDP We could try to solve them through expectiminimax search, but that would run into trouble with infinite sequences Instead, we solve them algebraically Two methods: value iteration and policy iteration
Method 1: Value iteration Start out with every U(s) = 0 Iterate until convergence During the ith iteration, update the utility of each state according to this rule: s + ( ) ( ) max A a ( | ' s , ) ( ) ' s U s R s P s a U + 1 i i ( ) s ' In the limit of infinitely many iterations, guaranteed to find the correct utility values In practice, don t need an infinite number of iterations
Value iteration What effect does the update have? s + ( ) ( ) max A a ( | ' s , ) ( ) ' s U s R s P s a U + 1 i i ( ) s ' Value iteration demo
Value iteration Input (non-terminal R=-0.04) Utilities with discount factor 1 Final policy
Method 2: Policy iteration Start with some initial policy 0 and alternate between the following steps: Policy evaluation: calculate U i(s) for every state s Policy improvement: calculate a new policy i+1 based on the updated utilities ' ) ( s s A a i + = 1 i ( ) arg max ( | ' s , ) ( ) ' s s P s a U
Policy evaluation Given a fixed policy , calculate U (s) for every state s The Bellman equation for the optimal policy: s = + ( ) ( ) max A a ( | ' s , ) ( ) ' s U s R s P s a U ( ) s ' How does it need to change if our policy is fixed? ' s = + ( ) ( ) ( | ' s , ( )) ( ) ' s U s R s P s s U Can solve a linear system to get all the utilities! Alternatively, can apply the following update: 1 ) ( ) ( s + ( | ' s , ( )) ( ) ' s U s R s P s s U + i i i '
Appendix: Linear Solution to the Fixed Policy Utility Calculation ? = ? + ? ??, where ?= [u(1), u(2), , u(N)]^T This is the same as the equation on the previous slide ?(?) = ?(?) + ? ? ?(?,? ) ?(? ) The solution is: ? = (? ??) 1 ? Solution computational cost is O{N^3} if N is the number of distinguishable states
