[RL] Policy Iteration

week 3 구성 :

(1) Policy Iteration
(2) Value Iteration
(3) Dynamic Programming
中 Policy Iteratiion Review

---

1-1. Policy Evaluation

• Problem : 임의의 policy가 주어진 채, state-value function v_π 를 계산하는 것 (Prediction문제)
• Solution : For all s ∈ S , 

∑Pss'*Rss' = Rs 등호 성립

위에 회색박스친 것과 같은 의미로, k+1번째 state-value function update!

 
이렇게 반복을 통해 value function v_π를 계산하고 업데이트하는 것을 Iterative Policy Evaluation단계라고 한다.
 
 

• (예제) Evaluating a Random Policy in the Small Grid World

상황 설정 :

1. Episodic MDP(discount factor = 1)
2. Reward of -1 on all transitions until termination.(모든 움직임에 대해 -1 만큼의 보상)
3. 모든 action a에 대해, π(a|s) = 0.25로 고정 => Random Policy
4. 검정색 색칠되어있는 부분이 목표지점(Goal)

k = 2부터 v_k를 계산하려면 transition probability가 필요하므로, 직접 계산하는 법은 잘 모르겠지만. 아마 코딩

왼쪽의 v_k값을 계산하는 과정이 Policy Evaluation단계라고 보면되고, 오른쪽의 Greedy Policy라고 되어있는 부분은 다음에 설명할 Improvement단계이다. 이 두 단계를 합쳐서 <Policy Iteration>이라고 함.
 
 

1-2. Policy Improvement

π ′ = greedy(v_π)
즉, 최적의 policy를 찾아가는 과정을 Policy Improvement라고 한다.

여기서는 greedy search를 제안하였지만, 더 다양한 알고리즘이 사용될 수 있다.(Generalized Policy Iteration) 

 
Iteration을 거치며 Evaluation에서 구해가는 value-function이 향상되어 감을 다음과 같이 증명할 수 있다.

 

1-3. Policy Iteration

Policy Evaluation과 Improvement단계를 반복하며 최적의 v_π와 π를 찾아가는 것
문제가 Control로 바뀝니다. (Evaluation에서는 Prediction문제였음)

(결과적으로 v_π는 v_*가 될 것이고, π도 π_*로 수렴하게 됨) 

이때, v가 v_π로 수렴할 때까지 계속 k를 늘려가야 하는가?
small grid world에서는 일반적으로 k = 3이면 optimal policy를 구하는 데에 충분한 숫자이다.
따라서, number of iterations k를 적당히 끊어서 반복을 돌리는 것을 Value Iteration이라고 한다.
즉, 매 iteration(k = 1만큼 증가할때)마다 policy를 업데이트해주는 것이다. (다음 장에 계속)
 

---

연휴 때 교재 정독 & 연습문제 4장까지.......