---

date: 2021-10-17 22:00:00

---

우리가 방금까지 policy iteration을 실제로 계산 까지 해보았다.

잠시 저번 포스트의 policy iteratoin을 6번 한 결과를 보겠다.

s1 (v = 0.512)	s2 (v = 0.64)	s3 (v = 0.512)
s4 (v = 0.64)	s5 (v = 0.8)	s6 (v = 1)
s7 (v = 0.8)	s8 (v = 1)	s9 (v = 0)

↓	↓	←
↓	↓	↓
→	→

이렇게 보니 value값만 보고 증가하는 추세를 따라 agent가 이동하면 될것 같아 보인다.

정책의 필요성을 굳이 못느끼게 된다.

그래서 나오게 된것이 value iteration 인 것이다.

value itertation은 벨만 최적 방정식을 통해 푸는것인데, 따로 정책이 필요 없다.

이 벨만 최적 방정식을 계산하는 방법인 value iteartion을 이번 포스트에서 설명할 예정이다.

Value Iteration

저번 포스트에서 우리는 벨만 기대 방정식과 벨만 최적 방정식에 대해서 배우고 policy iteration 까지 배웠었다.

Vπ(s) = E[Rt+1 + γVπ(St+1) | St = s]

벨만 기대 방정식을 계산하면 현재 policy의 참 value 값을 구할 수 있으며,

우리는 policy iteration을 통해 다시 policy를 업데이트 하고 value를 구하고를 반복해서 최적의 정책을 구하였다,

그러나 벨만 최적방정식은 바로 최적 가치함수를 구할 수 있으며 최적 정책도 찾을 수 있다.

V(s) = maxaE[Rt+1 + γV (St+1) | St = s, At = a]

한마디로 policy없이 구할 수 있다는 것이다. 또한 식에서 π 가 없으니 정책이 필요 없다는 것도 알 수 있다.

그럼 어떻게 구할까??

value iteration은 현재 state에서 policy를 고려하지 않고 가장 유리한 state로 갈때의 가치함수를 사용하여 현재 state의 value를 추정한다.

한마디로 가능한 action중 가장 좋은 action이 결정되었을때 value를 추정하게 된다.

Value Iteration in grid-world

Iteration

현재 grid world의 상황이다.

v = 0	v = 0	v = 0
v = 0	v = 0	v = 0 Trap(R = -1)
v = 0	v = 0	v = 0 Goal(R = 1)

Vk+1(s) = maxa∈A(r(St = s, At = a) + γV k(s'))

1st Iteration

s1 (v = 0)	s2 (v = 0)	s3 (v = 0)
s4 (v = 0)	s5 (v = 0)	s6 (v = 1)
s7 (v = 0)	s8 (v = 1)	s9 (v = 0)

V(s1) = 0 + 0.8 * 0 = 0

V(s2) = 0 + 0.8 * 0 = 0

V(s3) = 0 + 0.8 * 0 = 0

V(s4) = 0 + 0.8 * 0 = 0

V(s5) = 0 + 0.8 * 0 = 0

V(s6) = 1 + 0.8 * 0 = 1 (q(down))

V(s7) = 0 + 0.8 * 0 = 0

V(s8) = 1 + 0.8 * 0 = 1 (q(right))

2nd Iteration

s1 (v = 0)	s2 (v = 0)	s3 (v = 0)
s4 (v = 0)	s5 (v = 0.8)	s6 (v = 1)
s7 (v = 0.8)	s8 (v = 1)	s9 (v = 0)

V(s1) = 0 + 0.8 * 0 = 0

V(s2) = 0 + 0.8 * 0 = 0

V(s3) = 0 + 0.8 * 0 = 0

V(s4) = 0 + 0.8 * 0 = 0

V(s5) = 0 + 0.8 * 1 = 0.8 (q(down))

V(s6) = 1 + 0.8 * 0 = 1 (q(down))

V(s7) = 0 + 0.8 * 1 = 0.8 (q (right))

V(s8) = 1 + 0.8 * 0 = 1 (q(right))

3rd Iteration

s1 (v = 0)	s2 (v = 0.64)	s3 (v = 0)
s4 (v = 0.64)	s5 (v = 0.8)	s6 (v = 1)
s7 (v = 0.8)	s8 (v = 1)	s9 (v = 0)

V(s1) = 0 + 0.8 * 0 = 0

V(s2) = 0 + 0.8 * 0.8 = 0.64 (q(down))

V(s3) = 0 + 0.8 * 0 = 0

V(s4) = 0 + 0.8 * 0.8 = 0.64 (q(right or down))

V(s5) = 0 + 0.8 * 1 = 0.8 (q(down))

V(s6) = 1 + 0.8 * 0 = 1 (q(down))

V(s7) = 0 + 0.8 * 1 = 0.8 (q (right))

V(s8) = 1 + 0.8 * 0 = 1 (q(right))

4th Iteration

s1 (v = 0.512)	s2 (v = 0.64)	s3 (v = 0.512)
s4 (v = 0.64)	s5 (v = 0.8)	s6 (v = 1)
s7 (v = 0.8)	s8 (v = 1)	s9 (v = 0)

V(s1) = 0 + 0.8 * 0.64 = 0.512 (q(right or down))

V(s2) = 0 + 0.8 * 0.8 = 0.64 (q(down))

V(s3) = 0 + 0.8 * 0.64 = 0.512 (q(left))

V(s4) = 0 + 0.8 * 0.8 = 0.64 (q(right or down))

V(s5) = 0 + 0.8 * 1 = 0.8 (q(down))

V(s6) = 1 + 0.8 * 0 = 1 (q(down))

V(s7) = 0 + 0.8 * 1 = 0.8 (q (right))

V(s8) = 1 + 0.8 * 0 = 1 (q(right))

Print Policy

s1 (v = 0.512)	s2 (v = 0.64)	s3 (v = 0.512)
s4 (v = 0.64)	s5 (v = 0.8)	s6 (v = 1)
s7 (v = 0.8)	s8 (v = 1)	s9 (v = 0)

s1

q(s1, right) = 0 + 0.8(0.64) = 0.512

q(s1, down) = 0 + 0.8(0.64) = 0.512

s2

q(s2, left) = 0 + 0.8(0.512) = 0.4096

q(s2, down) = 0 + 0.8(0.8) = 0.64

q(s2, down) = 0 + 0.8(0.512) = 0.4096

s3

q(s3, left) = 0 + 0.8(0.64) = 0.512

q(s3, down) = -1 + 0.8(1) = -0.2

s4

q(s4, up) = 0 + 0.8(0.512) = 0.4096

q(s4, right) = 0 + 0.8(0.8) = 0.64

q(s4, down) = 0 + 0.8(0.8) = 0.64

s5

q(s5, up) = 0 + 0.8(0.64) = 0.512

q(s5, down) = 0 + 0.8(1) = 0.8

q(s5, left) = 0 + 0.8(0.64) = 0.512

q(s5, right) = -1 + 0.8(1) = -0.2

s6

q(s6, up) = 0 + 0.8(0.512) = 0.4096

q(s6, down) = 1 + 0.8(0) = 1

q(s6, up) = 0 + 0.8(0.8) = 0.64

s7

q(s7, up) = 0 + 0.8(0.64) = 0.512

q(s7, right) = 0 + 0.8(1) = 0.8

s8

q(s8, up) = 0 + 0.8(0.8) = 0.64

q(s8, left) = 0 + 0.8(0.8) = 0.64

q(s8, right) = 1 + 0.8(0) = 1

Value Iteration으로 얻은 정책

↓ →	↓	←
↓ →	↓	↓
→	→

---

제가 올린 글에서 잘못된 부분이 있으면 제 메일로 연락주세요!

Reference : 파이썬과 케라스로 배우는 강화학습

이승수의 저작물인 이 저작물은(는) 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제 라이선스에 따라 이용할 수 있습니다.