Value Iteration

Algorithms for MDP Planning

Shivaram Kalyanakrishnan

Department of Computer Science and Engineering Indian Institute of Technology Bombay

shivaram@cse.iitb.ac.in

August 2019

Overview

1. Value Iteration

2. Linear Programming

3. Policy Iteration

Policy Improvement Theorem

Overview

1. Value Iteration

2. Linear Programming

3. Policy Iteration

Policy Improvement Theorem

Value Iteration

V0←Arbitrary, element-wise bounded,n-length vector.t←0.

Repeat:

Fors∈S:

Vt+1(s)←maxa∈AP

s⁰∈ST(s,a,s⁰) (R(s,a,s⁰) +γVt(s⁰)).

t←t+1.

UntilVt ≈Vt−1(up to machine precision).

Convergence toV^?guaranteed using a max-norm contraction argument.

Value Iteration

V0←Arbitrary, element-wise bounded,n-length vector.t←0.

Repeat:

Fors∈S:

Vt+1(s)←maxa∈AP

s⁰∈ST(s,a,s⁰) (R(s,a,s⁰) +γVt(s⁰)).

t←t+1.

UntilVt ≈Vt−1(up to machine precision).

Convergence toV^?guaranteed using a max-norm contraction argument.

Overview

1. Value Iteration

2. Linear Programming 3. Policy Iteration

Policy Improvement Theorem

Linear Programming

Minimise X

s∈S

V(s)

subject to V(s)≥X

s⁰∈S

T(s,a,s⁰) R(s,a,s⁰) +γV(s⁰)

,∀s∈S,∀a∈A.

Let|S|=nand|A|=k. nvariables,nkconstraints.

Can also be posed asdual withnk variables andnconstraints.

Linear Programming

Minimise X

s∈S

V(s)

subject to V(s)≥X

s⁰∈S

T(s,a,s⁰) R(s,a,s⁰) +γV(s⁰)

,∀s∈S,∀a∈A.

Let|S|=nand|A|=k.

nvariables,nkconstraints.

Can also be posed asdual withnk variables andnconstraints.

Linear Programming

Minimise X

s∈S

V(s)

subject to V(s)≥X

s⁰∈S

T(s,a,s⁰) R(s,a,s⁰) +γV(s⁰)

,∀s∈S,∀a∈A.

Let|S|=nand|A|=k.

nvariables,nkconstraints.

Can also be posed asdual withnk variables andnconstraints.

Linear Programming

Minimise X

s∈S

V(s)

subject to V(s)≥X

s⁰∈S

T(s,a,s⁰) R(s,a,s⁰) +γV(s⁰)

,∀s∈S,∀a∈A.

Let|S|=nand|A|=k.

nvariables,nkconstraints.

Can also be posed asdual withnk variables andnconstraints.

Overview

1. Value Iteration

2. Linear Programming

3. Policy Iteration

Policy Improvement Theorem

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s_{1 2 3 4 5 6 7 8}

π

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else (2) ifπ⁰is obtained as above, then

∀s∈S:V^π0(s)≥V^π(s)and∃s∈S:V^π0(s)>V^π(s).

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s_{1 2 3 4 5 6 7 8}

π

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else (2) ifπ⁰is obtained as above, then

∀s∈S:V^π0(s)≥V^π(s)and∃s∈S:V^π0(s)>V^π(s).

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s1 2 3 4 5 6 7 8

π

Q (s , ) π Q (s , ) π 3

3

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else (2) ifπ⁰is obtained as above, then

∀s∈S:V^π0(s)≥V^π(s)and∃s∈S:V^π0(s)>V^π(s).

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s1 2 3 4 5 6 7 8

π

Q (s , ) π Q (s , ) π

7 7

Q (s , ) π Q (s , ) π 3

3

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else (2) ifπ⁰is obtained as above, then

∀s∈S:V^π0(s)≥V^π(s)and∃s∈S:V^π0(s)>V^π(s).

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s1 2 3 4 5 6 7 8

π

Improvable states

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else (2) ifπ⁰is obtained as above, then

∀s∈S:V^π0(s)≥V^π(s)and∃s∈S:V^π0(s)>V^π(s).

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s1 2 3 4 5 6 7 8

π

Improvable states Improving actions

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else (2) ifπ⁰is obtained as above, then

∀s∈S:V^π0(s)≥V^π(s)and∃s∈S:V^π0(s)>V^π(s).

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s1 2 3 4 5 6 7 8

π

Improvable states Improving actions

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else (2) ifπ⁰is obtained as above, then

∀s∈S:V^π0(s)≥V^π(s)and∃s∈S:V^π0(s)>V^π(s).

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s1 2 3 4 5 6 7 8

π

s s s s s s s

s1 2 3 4 5 6 7 8

π

Policy Improvement

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else (2) ifπ⁰is obtained as above, then

∀s∈S:V^π0(s)≥V^π(s)and∃s∈S:V^π0(s)>V^π(s).

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s1 2 3 4 5 6 7 8

π

s s s s s s s

s1 2 3 4 5 6 7 8

π

Policy Improvement

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else

Policy Improvement

Givenπ,

Pickone or moreimprovable states, and in them, Switch to anarbitraryimproving action.

Let the resulting policy beπ⁰.

s s s s s s s

s1 2 3 4 5 6 7 8

π

s s s s s s s

s1 2 3 4 5 6 7 8

π

Policy Improvement

Policy Improvement Theorem:

(1) Ifπhas no improvable states, then it is optimal, else

Definitions and Basic Facts

ForX:S→RandY :S→R, we defineXYif∀s∈S:X(s)≥Y(s), and we defineXYifXY and∃s∈S:X(s)>Y(s).

For policiesπ1, π2∈Π, we defineπ1π2ifV^π1V^π2, and we defineπ1π2ifV^π1 V^π2.

Bellman Operator.Forπ∈Π, we defineB^π: (S→R)→(S→R)as follows: forX:S→Rand∀s∈S,

(B^π(X))(s)^def=X

s⁰∈S

T(s, π(s),s⁰) R(s, π(s),s⁰) +γX(s⁰) .

Fact 1. Forπ∈Π,X:S→R, andY :S→R:

ifXY, thenB^π(X)B^π(Y).

Fact 2. Forπ∈ΠandX:S→R:

l→∞lim(B^π)^l(X) =V^π.(from Banach’s FP Theorem)

Definitions and Basic Facts

ForX:S→RandY :S→R, we defineXYif∀s∈S:X(s)≥Y(s), and we defineXYifXY and∃s∈S:X(s)>Y(s).

For policiesπ1, π2∈Π, we defineπ1π2ifV^π1V^π2, and we defineπ1π2ifV^π1V^π2.

Bellman Operator.Forπ∈Π, we defineB^π: (S→R)→(S→R)as follows: forX:S→Rand∀s∈S,

(B^π(X))(s)^def=X

s⁰∈S

T(s, π(s),s⁰) R(s, π(s),s⁰) +γX(s⁰) .

Fact 1. Forπ∈Π,X:S→R, andY :S→R:

ifXY, thenB^π(X)B^π(Y).

Fact 2. Forπ∈ΠandX:S→R:

l→∞lim(B^π)^l(X) =V^π.(from Banach’s FP Theorem)

Definitions and Basic Facts

ForX:S→RandY :S→R, we defineXYif∀s∈S:X(s)≥Y(s), and we defineXYifXY and∃s∈S:X(s)>Y(s).

For policiesπ1, π2∈Π, we defineπ1π2ifV^π1V^π2, and we defineπ1π2ifV^π1V^π2.

Bellman Operator.Forπ∈Π, we defineB^π: (S→R)→(S→R)as follows:

forX :S→Rand∀s∈S, (B^π(X))(s)^def=X

s⁰∈S

T(s, π(s),s⁰) R(s, π(s),s⁰) +γX(s⁰) .

Fact 1. Forπ∈Π,X:S→R, andY :S→R:

ifXY, thenB^π(X)B^π(Y).

Fact 2. Forπ∈ΠandX:S→R:

l→∞lim(B^π)^l(X) =V^π.(from Banach’s FP Theorem)

Definitions and Basic Facts

ForX:S→RandY :S→R, we defineXYif∀s∈S:X(s)≥Y(s), and we defineXYifXY and∃s∈S:X(s)>Y(s).

For policiesπ1, π2∈Π, we defineπ1π2ifV^π1V^π2, and we defineπ1π2ifV^π1V^π2.

Bellman Operator.Forπ∈Π, we defineB^π: (S→R)→(S→R)as follows:

forX :S→Rand∀s∈S, (B^π(X))(s)^def=X

s⁰∈S

T(s, π(s),s⁰) R(s, π(s),s⁰) +γX(s⁰) .

Fact 1. Forπ∈Π,X :S→R, andY :S→R:

ifXY, thenB^π(X)B^π(Y).

Fact 2. Forπ∈ΠandX:S→R:

l→∞lim(B^π)^l(X) =V^π.(from Banach’s FP Theorem)

Definitions and Basic Facts

ForX:S→RandY :S→R, we defineXYif∀s∈S:X(s)≥Y(s), and we defineXYifXY and∃s∈S:X(s)>Y(s).

For policiesπ1, π2∈Π, we defineπ1π2ifV^π1V^π2, and we defineπ1π2ifV^π1V^π2.

Bellman Operator.Forπ∈Π, we defineB^π: (S→R)→(S→R)as follows:

forX :S→Rand∀s∈S, (B^π(X))(s)^def=X

s⁰∈S

T(s, π(s),s⁰) R(s, π(s),s⁰) +γX(s⁰) .

Fact 1. Forπ∈Π,X :S→R, andY :S→R:

ifXY, thenB^π(X)B^π(Y).

Fact 2. Forπ∈ΠandX:S→R:

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ lim

l→∞(B^π0)^l(V^π) · · · (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ V^π0 V^π.

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ lim

l→∞(B^π0)^l(V^π) · · · (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ V^π0 V^π.

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ lim

l→∞(B^π0)^l(V^π) · · · (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ V^π0 V^π.

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ lim

l→∞(B^π0)^l(V^π) · · · (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ V^π0 V^π.

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ lim

l→∞(B^π0)^l(V^π) · · · (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ V^π0 V^π.

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ lim

l→∞(B^π0)^l(V^π) · · · (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ V^π0 V^π.

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ lim

l→∞(B^π0)^l(V^π) · · · (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ V^π0 V^π.

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ lim

l→∞(B^π0)^l(V^π) · · · (B^π0)²(V^π)B^π0(V^π)V^π

=⇒ V^π0 V^π.

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

⇒ ^{π0 l π} · · · ^{π0 2 π π0 π π}

=⇒ V^π0 V^π.

Proof of Policy Improvement Theorem

Observe that forπ, π⁰∈Π,∀s∈S:B^π0(V^π)(s) =Q^π(s, π⁰(s)).

πhas no improvable states

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π)

=⇒ ∀π⁰∈Π :V^πB^π0(V^π)(B^π0)²(V^π) · · · lim

l→∞(B^π0)^l(V^π)

=⇒ ∀π⁰∈Π :V^πV^π0.

πhas improvable states and policy improvement yieldsπ⁰

=⇒ B^π0(V^π)V^π

=⇒ (B^π0)²(V^π)B^π0(V^π)V^π

⇒ ^{π0 l π} · · · ^{π0 2 π π0 π π}

Policy Iteration Algorithm

π←Arbitrary policy.

Whileπhas improvable states:

π←PolicyImprovement(π).

Number of iterations depends onswitching strategy. Current bounds quite loose.

Policy Iteration Algorithm

π←Arbitrary policy.

Whileπhas improvable states:

π←PolicyImprovement(π).

Number of iterations depends onswitching strategy. Current bounds quite loose.

Policy Iteration Algorithm

π←Arbitrary policy.

Whileπhas improvable states:

π←PolicyImprovement(π).

Number of iterations depends onswitching strategy. Current bounds quite loose.

Policy Iteration Algorithm

π←Arbitrary policy.

Whileπhas improvable states:

π←PolicyImprovement(π).

Number of iterations depends onswitching strategy. Current bounds quite loose.

Policy Iteration Algorithm

π←Arbitrary policy.

Whileπhas improvable states:

π←PolicyImprovement(π).

Number of iterations depends onswitching strategy. Current bounds quite loose.

Policy Iteration Algorithm

π←Arbitrary policy.

Whileπhas improvable states:

π←PolicyImprovement(π).

Number of iterations depends onswitching strategy. Current bounds quite loose.

Policy Iteration Algorithm

π←Arbitrary policy.

Whileπhas improvable states:

π←PolicyImprovement(π).

Number of iterations depends onswitching strategy. Current bounds quite loose.

Policy Iteration Algorithm

π←Arbitrary policy.

Whileπhas improvable states:

π←PolicyImprovement(π).