Robust POMDPIBM Research – Tokyo
Takayuki Osogami

1Planning with erroneous parameters leads topoor results
Modelingwith POMDP

Estimatingparameters

Finding the
optimal policyof POMDP

for POMDP

Actingaccording to the
optimal policy

True
Dialog management[Pietquin 2004]

Error

Poor results

Estimated

Helping disabled[Hoey+ 2007]

Goal: Robustness against uncertainties in parameters2This talk• POMDP and Robust POMDP• Main results on Robust POMDP• Numerical experiments

3

POMDP models sequential decision making・・・

Observation, znReward, rn

Observation, zn+1StatesnAction
anStatesn+1

Reward function

rn = r(sn, an)

Transition & observation probability・・・pn(sn+1, zn+1|sn, an)Parameters of POMDP

Policy: History (of prior actions and observations) → Action

Objective: Find the policy maximizing E𝑛𝜆𝑛𝑟𝑛4

In POMDP, the belief state captures essential
information about history
Time 0Time nHistory: Actions and observations

Belief stateb0

Updated via Bayes rulebnbn(s): Probability that the state is s

Policy: History Belief state → Action

POMDP’s key property: Convex value functionValue function
Expected cumulative reward obtained with theoptimal policy from the belief state b at time n𝑉𝑛 𝒃 = max𝛼𝛼 𝑠 𝒃(𝑠)𝑠Belief state, bPlanning with POMDP relies on convexity• Exact value iteration [Smallwood+ 1973]• Point-based value iteration [Pineau+ 2003]

6

Robust POMDP: Find the optimal policy for theworst case when parameters have uncertainties
POMDP

Robust POMDP

pp

Completely known

Known to be in an uncertainty set

Values of parameters

Objective of planningmax 𝔼𝜋

𝜆𝑛 𝑟𝑛𝑛Optimize for the known casemax min 𝔼𝜋𝑝𝜆𝑛 𝑟𝑛𝑛

Optimize for the worst caseThis talk• POMDP and Robust POMDP• Main results on Robust POMDP• Numerical experiments

8

Result #1: Robust value function is convex ifthe uncertainty set is convex
Robust value function
The maximum expected cumulative reward
obtained from the belief state b at time nfor the worst casep𝑉𝑛 𝒃 = max𝛼Parameter of POMDP isin convex uncertainty set

𝛼 𝑠 𝒃(𝑠)𝑠

Robust value function
is convex

Belief state, b

Proof relies on Loomis’ minimax theorem
9Result #2: Robust value iteration(impractical, but a basis of the following)
Finite operations only find a lower boundΛn𝑉𝑛 𝒃 = max𝛼∈Λ𝑛𝛼 𝑠 𝒃(𝑠)𝑠Λn+1
𝑉𝑛+1 𝒃 = max𝛼∈Λ𝑛+1𝛼 𝑠 𝒃(𝑠)𝑠10

Result #3: Robust Point-Based Value Iteration,
extending [Pineau+ 2003] to Robust POMDP
For each b in 𝔹,
1. Convex optimization to find worst p
2. Construct an α based on the pΛ𝑛𝑉𝑛 𝒃 = max
𝛼∈Λ𝑛b0b1
𝔹𝛼 𝑠 𝒃(𝑠)Λ 𝑛+1
𝑉𝑛+1 𝒃 = max𝛼∈Λ𝑛+1𝑠b2b0b1𝛼 𝑠 𝒃(𝑠)𝑠b2

𝔹11

Robust Heuristic Search Value Iteration,extending [Smith+ 2004] to Robust POMDP
Upper bound updated
as in [Smith+ 2004]

Lower bound updated
via Robust Point-Based
Value Iteration
12

Result #4: Initial bounds for Robust Heuristic
Search Value Iteration
Robust Initial Upper Bound
1. Choose arbitrary p’

Robust Initial Lower Bound
1. Choose arbitrary action, a0
Robust POMDP with fixed a0 = POMDP of finding worst pp’

2.

Initialize with the p’[Hauskrecht 2000]

2.

Solve MDP of finding worst p

3.

Interpolate the bounds

13Result #5: Robust belief update

Belief stateTime nTime n+1bnbn+1
Robust Belief Update
1. Convex optimization to find worst p*
2. Belief update based on the p*p*14

Special case: Convex optimization reduces tolinear program
Uncertainty set

Optimization problem solved in• Robust Point-Based Value Iteration• Robust Belief Updatep

Convex optimization

pLinear program

Example:p(t, z|s, a) ≤ c p0(t, z|s, a)
Can deviate fromnominal p0 by factor c15

This talk• POMDP and Robust POMDP• Main results on Robust POMDP• Numerical experiments

16

Experiments with “robust” Heaven & Hell?

123?
Initial belief:
Heaven or Hell with probability 0.5

45
Reward:-1: each step
+1: reaching Heaven-10: reaching Hell

6Can observe which “?” is heaven.
Uncertainty in observation error (0<pe<0.5)

7!
17Results with “robust” Heaven & Hell
HSVI (baseline) is optimized for pe = 0.1

Quality of policy

Time to search policy
18

Summary of Robust POMDP
p

Uncertainty in POMDP parameters

Robust policy (optimal for worst case)

Robust value function is convex⇒ Robust value iteration⇒ Robust point-based value iteration⇒ Robust heuristic-search value iteration⇒ Robust belief update

19

Proof sketch (convexity of robust value function)
Inductive hypothesis: 𝑉𝑛+1 𝐛 = max

𝛼 𝑠 𝐛(𝑠)𝛼∈Λ𝑠∈𝑆𝐛

Robust Bellman equation:
𝑉𝑛 𝐛 = max min𝑎𝑎𝑎∈𝐴 𝑝𝑛 ∈𝑃= max min𝑎𝑎𝑎∈𝐴𝑝𝑛 ∈𝑃𝐛 𝑠

𝑝𝑛𝑎 𝑡, 𝑧 𝑠 𝑉𝑛+1 (𝐛′ )𝑟 𝑠, 𝑎 + 𝛾𝑠𝑡,𝑧max

𝛼𝑧 ∈Λ𝑧 , 𝑧∈𝑍𝐛 𝑠𝑠,𝑧𝑟 𝑠, 𝑎+𝛾|𝑍|

Loomis’ Minimax Theorem:

𝑝𝑛𝑎 𝑡, 𝑧 𝑠 𝛼𝑧 (𝑡)𝑡minmax𝑎 ∈𝑃 𝑎 𝛼 ∈Λ , 𝑧∈𝑍𝑝𝑛𝑧𝑧

Mixed Strategy(Pa: convex)

𝑉𝑛 (𝐛) = max𝑎∈𝐴max𝛼𝑧 ∈ConvexHull Λ𝑧 , 𝑧∈𝑍min𝒔𝑎,𝑠𝑝𝑛∈𝑃𝑎,𝑠𝑀 =maxmin 𝑀𝑎 ∈𝑃 𝑎𝛼𝑧 ∈ConvexHull Λ𝑧 , 𝑧∈𝑍 𝑝𝑛~ Probabilistic Mixture~ Mixed Strategy

𝑝𝑛𝑎 𝑡, 𝑧 𝑠 𝛼𝑧 (𝑡) 𝐛 𝑠𝑟 𝑠, 𝑎 + 𝛾𝑡,𝑧Convex w.r.t. b

20

Robust POMDPIBM Research – Tokyo
Takayuki Osogami
Supported by CREST, JST21