Policy Iteration란?
Policy(정책)를 업데이트하는 과정이다. Iterative Policy Evaluation을 말하며,
Bellman Expectation Equation으로 지금가지고 있는 Policy를 이용해 V를 업데이트 해준 후에 다시 Evaluation을 반복한다.
* 단, 업데이트 후에 Improvement 로 넘어가는 것이 아니라, V파이에 수렴할때까지 계속 Evaluate 해준다.
즉, value가 바뀌지 않을때까지 Evaluate해야 한다. 그 결과, Policy파이가 주어졌을때, V파이에 수렴할때까지
Iterative하게 value를 evaluation 시키는 것이다.
Policy Iteration : Policy Evaluation(Prediction) x ?+ Policy Improvement(Control)
Policy Evaluation 이란?
Prediction을 푸는 것으로, 현재 Policy에 대한 True Function을 구하고 Bellman equation을 사용한다.
Bellman Equation과 다른점은 Value Function에 Iteration을 추가했다.
Policy Improvement 란?
Policy Evaluation에서 구한 V, Bellman Expectation Equation을 이용하여 Q를 구한다.
Q를 최대로 만드는 Action 에 1 나머지 Action에는 0을 부여하고 Policy를 업데이트한다.
이 과정을 Converge 할때까지 진행한다.
Value Iteration이란?
Bellman Optimality Equation을 이용해, Evaluation을 단 한 번만 한다.
Policy Iteration는 반대로 Evaluation을 수차례 반복해야하는 단점이 있다.
따라서, 현재 Value Function을 계산하고 Update(갱신)할 때 Max를 얻어 Greedy하게 개선해주는 효과를 가졌다.
Value Iteration : Policy Evaluation(Prediction) x 1 + Policy Improvement(Control)
Value Iteration은 Max를 사용하기 때문에 Policy파이의 영향을 받지 않고, 움직여서 Value를 계산해보고 큰 쪽의 Policy를 1로 맞춰가며 학습한다.
Policy Iteration vs Value Iteration
Policy Iteration 예제
출처 : https://sumniya.tistory.com/10
Reward = -1
Start = 0, 0
Goal = 3, 3
상하좌우로 이동할 확률 25%
V(s) 함수 (가치 함수)는 확률 곱하기 Reward 와 이동할 위치의 이전 State 가치값을 더해 확률을 곱한다.
그리고 Reward와 이동할 곳의 가치를 더한 갯수만큼 각각 곱해 더해준다.
그럼 현재위치의 가치값 산출된다.
4곳 모두 -1 + 0이기 때문에 4 x 0.25 x -1 을 해주었다.
모든 좌표 평면에 반복하면 출발지와 도착지만 0이고 나머지는 -1이 된다.
(1, 2)에서 결과 값을 보면 왼쪽으로 돌아가는 구간만 빼고 y + s(이전)의 값이 같다.
3 x 0.25(-2)[총 세개] + 0.25 x (-1) = -1.75
이런식으로 계산하면 아래와 k=2 와 같은 값이 채워진다.
무한히 반복하면 마지막 그림처럼 완성되며 Policy Improvement를 진행한다.
현재 s위치에서 상하죄우의 값 = y x s를 해서 가장 값이 큰 쪽의 방향을 Q-Function으로 만든다.
결과
Value Iteration 예제
상하좌우 네 방향의 모든 것을 더해서 V값을 산출하지 않고, Max값을 취해 갱신한다.
y(감가) + 이전 State를 더한 4개중에 최대 값을 저장한다.
1 라운드가 끝나면, 모두 -1로 채워진다.
수렴하게되면 세번째 그림처럼 숫자가 채워진다.
여기서 Value Iteration과 다른점은 3라운드만에 Converge 하게 된다.
Value Iteration 예제 2
여기서 주어진 Reward는 0 이며, Noise는 0.2, 그래고 감가율은 0.9이다.
V0의 경우 모든 좌표의 값이 0으로 설정이되며, V1에서 리워드 +1, 과 -1를 넣어주었다.
이는 마지막 위치를 의미한다. 0.8 은 이미 주어진 MDP의 확률을 뜻한다. 화면에는 나오지 않았지만
각각 0.8, 0.1, 0.1이다. 최적의 action은 오른쪽으로 가는게 된다.
0.8(확률) x [ 0 (Reward) + 0.9(감가율y) x 1(S'이전 상태) ]
문제의 자세한 설명은 아래 사진에 나와있다.
'AI Master Degree > AI and Data engineering' 카테고리의 다른 글
| Chap 5. Decision Making 의사결정 - Policy and Value Iteration Part1. (0) | 2021.10.03 |
|---|---|
| Chap 5. Decision Making 의사결정 (0) | 2021.10.02 |
| Chap 4-2. Parameter learning & Introduction to Simple Decision Making (0) | 2021.10.01 |
| Chap 4. Parameter learning & Introduction to Simple Decision Making (0) | 2021.09.30 |