POMDP Tutorial

Preliminaries: Problem Definition

• Agent model, POMDP, Bayesian RL

Markov Decision Process

Transition
Dynamics -X: set of states [xs,xr]
• state component
WORLD
• reward component

Observation --A: set of actions

Action
-T=P(x’|x,a): transition
Belief b Policy and reward probabilities
π -O: Observation function
-b: Belief and info. state
ACTOR
-π: Policy
Sequential decision making with uncertainty in a changing world
• Dynamics- The world and agent change over time. The
agent may have a model of this change process
• Observation- Both world state and goal achievement are
accessed through indirect measurements (sensations of
state and reward)
• Beliefs - Understanding of world state with uncertainty
• Goals- encoded by rewards! => Find a policy that can
maximize total reward over some duration
• Value Function- Measure of goodness of being in a belief
state
• Policy- a function that describes how to select actions in
each belief state.
 Markov Decision Processes (MDPs)

In RL, the environment is a modeled as an MDP,

defined by
S – set of states of the environment
A(s) – set of actions possible in state s within S
P(s,s',a) – probability of transition from s to s' given a
R(s,s',a) – expected reward on transition s to s' given a
g – discount rate for delayed reward
discrete time, t = 0, 1, 2, . . .
... rt +1 rt +2 rt +3 s ...
st st +1 st +2 t +3
at at +1 at +2 at +3
 MDP Model

Process:
Agent • Observe state st in S
• Choose action at in At
State Reward Action
• Receive immediate
Environment reward rt
• State changes to st+1

a0 a1 a2 MDP Model <S, A, T, R>

s0 s1 s2 s3
r0 r1 r2
 The Objective is to Maximize
Long-term Total Discounted Reward

Find a policy π : s∈ S → a∈ A(s) (could be stochastic)

that maximizes the value (expected future reward) of each s :

π
V (s) = E {rt +1 + γ rt +2 + γ2 rt +3 + ... st =s, π }

and each s,a pair: rewards

π
Q (s,a) = E {rt +1+ γ rt +2 + γ 2rt +3+ ... s t =s, a t=a, π }

These are called value functions - cf. evaluation functions

 Policy & Value Function
• Which action, a, should the agent take?
– In MDPs:
• Policy is a mapping from state to action, π: S → A

• Value Function Vπ,t(S) given a policy π

– The expected sum of reward gained from starting in
state s executing non-stationary policy π for t steps.

• Relation
– Value function is evaluation for policy based on the
long-run value that agent expects to gain from
executing the policy.
Optimal Value Functions and Policies

There exist optimal value functions:

V * (s) = max V ! (s) Q* (s, a) = max Q! (s,a)

! !

And corresponding optimal policies:

! * (s) = arg max Q* (s, a)

a

π* is the greedy policy with respect to Q*

 Optimization (MDPs)
• Recursively calculate expected long-term reward for each state/belief:

$ %
Vt * (s ) = max & R (s, a ) + ! * T (s, a, s ')Vt *"1 (s ')'
a
( s '#S )

• Find the action that maximizes the expected reward:

% &
! t * (s ) = arg max ' R( s, a) + " + T (s, a, s ')Vt #1 * (s ')(
a ) s '$S *
 Policies are not actions

• There is an important difference between policies

and action choices
• A Policy is a (possibly stochastic) mapping
between “states” and actions (where states can be
beliefs or information vectors). Thus a policy is a
strategy, a decision rule that can encode action
contingencies on context, etc.
Example of Value Functions
4Grid Example
Policy Iteration
 Classic Example: Car on the hill

Goal: Top of the hill, final

velocity =0 in minimum time

Optimal Value function

Optimal
Trajec.
 Ball-Balancing
• RL applied to a real physical system-illustrates online learning
• An easy problem...but learns as you watch
 Smarts Demo
• Rewards ?
• Environment state space?
• Action state space ?
• Role of perception?
• Policy?
 1-Step Model-free Q-Learning
A model of the environment is not necessary to learn to act in a stationary domain

On each state transition:

rt +1
st st +1
at
Update:

[
Q(st ,at ) ! Q(st , at ) + " rt +1 + # max Q(st +1 ,a) $ Q(st ,at )
a ]
a table
entry TD Error

lim Q(s, a) ! Q* (s,a) Optimal behavior found without a

t! " model of the environment!
lim # t ! # * (Watkins, 1989)
t! "
Assumes finite MDP
RL Theory: Generalized Policy Iteration

policy
evaluation
value
learning
Value
Policy Function
! V, Q
policy
improvement
greedification

* * *
! V,Q
 Rooms Example

4 rooms
4 hallways
4 unreliable
ROOM HALLWAYS primitive actions
up

left right Fail 33%

of the time
O1
down

G? 8 multi-step options
O2 G? (to each room's 2 hallways)

Given goal location,

quickly plan shortest route

Goal states are given All rewards zero

a terminal value of 1 γ = .9
 Action representation matters: Value functions learned
faster for macro-actions
with primitive actions (cell-to-cell)

V (goal )=1

Iteration #1 Iteration #2 Iteration #3

with behaviors (room-to-room)

V (goal )=1

Iteration #1 Iteration #2 Iteration #3

 MDP Model

Process:
Agent • Observe state st in S
• Choose action at in At
State Reward Action
• Receive immediate
Environment reward rt
• State changes to st+1

a0 a1 a2 MDP Model <S, A, T, R>

s0 s1 s2 s3
r0 r1 r2
 POMDP: UNCERTAINTY

Case #1: Uncertainty about the action outcome

Case #2: Uncertainty about the world state due to

imperfect (partial) information
 A broad perspective

Belief OBSERVATIONS
state

STATE
AGENT
WORLD + AGENT

ACTIONS

GOAL = Selecting appropriate actions

 What are POMDPs?

Components:
S2 Set of states: s∈S
0.5 Pr(o1)=0.9
0.5 Pr(o2)=0.1 Set of actions: a∈A
S1 Set of observations: o∈Ω
Pr(o1)=0.5
a1
Pr(o2)=0.5 a2 1 S3
Pr(o1)=0.2
Pr(o2)=0.8

POMDP parameters:
Initial belief: b0(s)=Pr(S=s)
Belief state updating: b’(s’)=Pr(s’|o, a, b)
Observation probabilities: O(s’,a,o)=Pr(o|s’,a)
Transition probabilities: T(s,a,s’)=Pr(s’|s,a)
Rewards: R(s,a) MDP
 Belief state

• Probability distributions over

Action states of the underlying MDP
World • The agent keeps an internal
belief state, b, that summarizes
Observation
its experience. The agent uses
a state estimator, SE, for
SE
b
! updating the belief state b’
based on the last action at-1, the
Agent current observation ot, and the
previous belief state b.
• Belief state is a sufficient
statistic (it satisfies the Markov
proerty)
 1D belief space for a 2 state POMDP
with 3 possible observations

Zi = Observations

P (o | s j , a )" P (s j | si , a )b (si )
si !S
b ' (s j ) = P (s j | o, a, b ) =
" P (o | s , a )" P (s
s j!S
j
si !S
j | si , a )b (si )
 A POMDP example: The tiger problem

S0 S1
“tiger-left” “tiger-right”
Pr(o=TL | S0, listen)=0.85 Pr(o=TL | S0, listen)=0.15
Pr(o=TR | S1, listen)=0.15 Pr(o=TR | S1, listen)=0.85

Actions={ 0: listen,
1: open-left,
2: open-right}

Reward Function Observations

- Penalty for wrong opening: -100 - to hear the tiger on the left (TL)
- Reward for correct opening: +10 - to hear the tiger on the right(TR)
- Cost for listening action: -1
 POMDP ≡ Continuous-Space Belief MDP
• a POMDP can be seen as a continuous-space “belief MDP”, as the
agent’s belief is encoded through a continuous “belief state”.
A1 A2 A3

S0 S1 S2 S3

O1 O2 O3

• We may solve this belief MDP like before using value iteration
algorithm to find the optimal policy in a continuous space. However,
some adaptations for this algorithm are needed.
 Belief MDP
• The policy of a POMDP maps the current belief state into an action. As the
belief state holds all relevant information about the past, the optimal policy of
the POMDP is the the solution of (continuous-space) belief MDP.
• A belief MDP is a tuple <B, A, ρ, P>:
B = infinite set of belief states
A = finite set of actions
ρ(b, a) = " b (s ) R (s, a ) (reward function)
s!S

P(b’|b, a) = " P(b ' | b, a, o) P(o | a, b)

o!O
(transition function)

Where P(b’|b, a, o) = 1 if SE(b, a, o) = b’,

P(b’|b, a, o) = 0 otherwise;
 A POMDP example: The tiger problem

S0 S1
“tiger-left” “tiger-right”
Pr(o=TL | S0, listen)=0.85 Pr(o=TL | S0, listen)=0.15
Pr(o=TR | S1, listen)=0.15 Pr(o=TR | S1, listen)=0.85

Actions={ 0: listen,
1: open-left,
2: open-right}

Reward Function Observations

- Penalty for wrong opening: -100 - to hear the tiger on the left (TL)
- Reward for correct opening: +10 - to hear the tiger on the right(TR)
- Cost for listening action: -1
 Tiger Problem (Transition Probabilities)
•

Prob. (LISTEN) Tiger: left Tiger: right Doesn’t change

Tiger: left 1.0 0.0 Tiger location
Tiger: right 0.0 1.0

Prob. (LEFT) Tiger: left Tiger: right

Tiger: left 0.5 0.5 Problem reset
Tiger: right 0.5 0.5

Prob. (RIGHT) Tiger: left Tiger: right

Tiger: left 0.5 0.5
Tiger: right 0.5 0.5
 Tiger Problem (Observation Probabilities)
•
Prob. (LISTEN) O: TL O: TR

Tiger: left 0.85 0.15

Tiger: right 0.15 0.85

Prob. (LEFT) O: TL O: TR Any observation

Tiger: left 0.5 0.5 Without the listen action

Tiger: right 0.5 0.5 Is uninformative

Prob. (LEFT) O: TL O: TR

Tiger: left 0.5 0.5

Tiger: right 0.5 0.5
 Tiger Problem (Immediate Rewards)
•

Reward (LISTEN)
Tiger: left -1
Tiger: right -1

Reward (LEFT)
Tiger: left -100
Tiger: right +10

Reward (RIGHT)
Tiger: left +10
Tiger: right -100
 The tiger problem: State tracking
b0

Belief vector

S1 S2
“tiger-left” “tiger-right”

Belief
 The tiger problem: State tracking
b0

Belief vector

S1 S2
“tiger-left” “tiger-right”

Belief
obs=hear-tiger-left
action=listen
 The tiger problem: State tracking
b1 b0 P(o | si , a )! P (si | s j , a )b0 (s j )
s j "S
b1 (si ) =
P(o | a, b )

Belief vector

S1 S2
“tiger-left” “tiger-right”

Belief

obs=growl-left
action=listen
 Tiger Example Optimal Policy t=1
• Optimal Policy for t=1
α0(1)=(-100.0, 10.0) α1(1)=(-1.0, -1.0) α0(1)=(10.0, -100.0)

left listen right

[0.00, 0.10] [0.10, 0.90] [0.90, 1.00]

open-left listen open-right

Optimal policy:

Belief Space:

S1 S2
“tiger-left” “tiger-right”
 Tiger Example Optimal Policy for t=2
• For t=2
[0.00, 0.02] [0.02, 0.39] [0.39, 0.61] [0.61, 0.98] [0.98, 1.00]

listen listen listen listen listen

TL/TR TR TL TL/TR TR TL TL/TR

left listen right

 Can we solving this Belief MDP?
• The Bellman equation for this belief MDP is
# $
V * (b ) = max % ) b (s ) R (s, a ) +! ) Pr (o | b, a )V * (boa )&
a" A
' s"S o"O (

• In general case: Very Hard to solve continuous space MDPs. Unfortunately,

DP updates cannot be carried out because there are uncountably many of belief
states. One cannot enumerate every equation of value function. To conduct DP
steps implicitly, we need to discuss the properties of value functions.

• Some special properties can be exploited first to simplify this problem

– Policy Tree
– Piecewise linear and convex property

• And then find an approximation algorithm to construct the optimal t-step

discounted value function over belief space using value iteration…
 Policy Tree
• With one step remaining, the agent must take a single action. With 2 steps to go, it takes
an action, make an observation, and makes the final action. In general, an agent t-step
policy can be represented as a policy tree.

A T steps to go
O1 Ok
O2
T-1 steps to go
A A A

2 steps to go
A
O1 Ok (T=2)
O2
1 step to go
A A A (T=1)
 Value Function for policy tree p
• If p is one-step policy tree, then the value of executing that action in
state s is
Vp(s) = R(s, a(p)).
• More generally, if p is a t-step policy tree, then
Vp(s) = R(s, a(p)) + r (Expected value of the future)
= R(s, a(p)) + r # T ( s ' | s, a ( p ), s ') # T (s ', a ( p ), oi )Vo ( p ) (s ')
i
s '!S oi !"

• Thus, Vp(s) can be thought as a vector associated with the policy trees
p since its dimension is the same as the number of states. We often
use notation αp to refer to this vectors.

! p = V p (s1 ), V p (s2 ),..., V p (sn )

 Value Function Over Belief Space
• As the exact world cannot be observed, the agent must compute an expectation over
world states of executing policy tree p from belief state b:
Vp(b) = " b (s )V p (s )
s!S

• If we let ! = V (s ), V (s ),..., V (s ) , then

p p 1 p 2 p n

V p (b ) = b ! p
• To construct an optimal t-step policy, we must maximize over all t-step policy trees P:

Vt (b ) = max b ! p
p"P

• As Vp(b) is linear in b for each p∈P, Vt(b) is the upper surface of those functions. That
is, Vt(b) is piecewise linear and convex.
 Illustration: Piecewise Linear Value Function
• Let Vp1Vp2 and Vp3 be the value functions induced by policy trees
p1, p2, and p3. Each of these value functions are the form

V pi (b ) = b ! pi
• Which is a multi-linear function of b. Thus, for each value function
can be shown as a line, plane, or hyperplane, depending on the
number of states, and the optimal t-step value

• Vt (b ) = max b ! pi
pi "P

• Example– in the case of two states (b(s1) = 1- b(s2)) – be illustrated

as the upper surface in two dimensions:
Picture: Optimal t-step Value Function

Vp1
Vp3

Vp2

Belief
0 1
S=S0 B(s0) S=S1
 Optimal t-Step Policy
• The optimal t-step policy is determined by projecting the optimal value
function back down onto the belief space.

Vp1 Vp3
Vp2

A(p1) A(p2) A(p3)

Belief
0 1
B(s0)
• The projection of the optimal t-step value function yields a partition into
regions, within each of which there is a single policy tree, p, such that
is maximal over the entire region. The optimal action in that region a(p), the
action in the root of the policy tree p.
 First Step of Value Iteration
• One-step policy trees are just actions: a0 a1
• To do a DP backup, we evaluate every possible 2-step policy tree

a0 a0 a0 a0

O0 O1 O0 O1 O0 O1 O0 O1

a0 a0 a0 a1 a1 a0 a1 a1

a1 a1 a1 a1

O0 O1 O0 O1 O0 O1 O0 O1

a0 a0 a0 a1 a1 a0 a1 a1
 Pruning
• Some policy trees are dominated and are never useful

Vp3
Vp1

Vp2

Belief
0 1
B(s0)
• They are pruned and not considered on the next step.
• The key idea is to prune before evaluating (Witness and Incremental
Pruning do this)
 Value Iteration (Belief MDP)
• Keep doing backups until the value function doesn’t change much
anymore

• In the worst case, you end up considering every possible policy tree

• But hopefully you will converge before this happens

 More General POMDP: Model uncertainty

Belief state b=P(θ)

meta-level state Meta-level MDP

sb
decision
a
Choose action actions a
to maximize
long term reward
s b +a
outcome Meta-level Model
r rewards
r, s’, b’ P(r,s’b’|s b,a)
s’ b’
decision
actions a’
a’
s’ b’ +a’
rewards r’
outcome Meta-level Model
r’, s’’, b’’ P(r’,s’’b’’|s’ b’,a’)
s’’ b’’

Tree required to compute optimal

solution grows exponentially
 Multi-armed Bandit Problem

Bandit “arms”

(unknown reward
m1 m2 m3
probabilities)
Most complex problem for which optimal solution fully
specified - Gittins index
-More general than it looks
-“Projects” with separable state spaces
-Projects only change when worked on.
-Key Properties of Solution
-Each project’s value can be separately computed
-Optimal policy permanantly retires projects less valuable
projects
 Learning in a 2-
armed bandit

Arm1 Arm2
Problem difficulty
Policies must specify actions
For all possible
information states

Action dependent tree of Beta

sufficient statistics
 Value Function

Optimal value function for learning while acting for k step

look-ahead

The reason information is valuable is the ability to use the

information to follow the optimal policy: By distinguishing the
arms, future best actions have higher expected payoffs.
 More reading…
• Planning and acting in partially Observable stochastic domains
Leslie P. Kaelbling
• Optimal Policies for partially Observable Markov Decision Processes
Anthony [Link] 1995
• Hierarchical Methods for Planning under Uncertainty Joelle Pineau
• POMDP’s tutorial in Tony's POMDP Page
[Link]