4.1 정책 평가와 반복 정책 평가

📘 2장 이론 (3): 정책 평가와 반복 정책 평가

🎯 정책과 최적 정책

• 정책 π: 상태 ( s )에서 행동 ( a )를 선택할 확률 분포
• 최적 정책 ( π^* ): 모든 상태에서 가장 높은 기대 수익을 가져오는 행동만을 선택하는 정책

최적 정책이란, 어떤 상태에 있든지 최적의 행동을 이미 알고 있는 상태를 의미한다.

최적 정책은 상태가치 함수와 행동가치 함수를 통해 정의된다:

V^*(s) = max_π V_π(s)       # 식 2.18 (최적 상태가치 함수)
Q^*(s,a) = max_π Q_π(s,a)   # 식 2.19 (최적 행동가치 함수)

• ( V^*(s) ): 가능한 모든 정책 중에서 상태 ( s )의 기대 수익이 가장 큰 값
• ( Q^*(s,a) ): 가능한 모든 정책 중에서 상태 ( s )에서 행동 ( a )를 했을 때 기대 수익이 가장 큰 값

---

🔁 최적 정책의 수렴 과정

정책은 다음과 같은 순서를 통해 최적 정책으로 발전한다:

1. 초기 정책 ( π_0 ): 임의로 시작
2. 정책 평가: ( πk )에 대한 상태가치 ( V{π_k}(s) ) 계산
3. 정책 개선: ( V_{πk}(s) )를 기반으로 더 나은 정책 ( π{k+1} ) 도출
4. 반복…

평가와 개선을 반복하면 최적 정책 ( π^* )과 최적 가치 함수에 수렴한다.

📌 그림 2.33은 이 과정을 시각적으로 보여준다.
→ 정책 → 가치 평가 → 정책 개선 → … → 수렴

---

🧪 정책 평가

• 특정 정책 ( π )에 대해 상태가치 ( V_π(s) )를 계산하는 과정
• 이전에 구현했던 state_value_function()은 재귀적으로 이 과정을 계산한 것

📌 문제:
재귀적 방식은 가능한 행동과 상태를 무한히 탐색하므로, 계산량이 커지고 수렴이 어려움

---

🔁 반복 정책 평가 (Iterative Policy Evaluation)

이 문제를 해결하기 위한 방법이 반복 정책 평가이다.

반복 정책 평가는 연결된 다음 상태의 가치만을 이용해 반복적으로 계산을 갱신한다:

V_{k+1}(s) = ∑_a π(a|s) ∑_{s'} P(s'|s,a)[r(s,a,s') + γV_k(s')]    # 식 2.29

• ( k ): 반복 횟수
• ( V_k(s) ): k번째 계산 결과
• ( V_{k+1}(s) ): 다음 반복에서 갱신된 상태가치

📌 그림 2.35는 재귀 방식과 반복 정책 평가의 차이를 비교한 그림이다.

---

💾 반복 정책 평가의 구현 방식

▶ a) 상태가치 테이블 2개 사용

• 이전 ( V_k )를 따로 저장한 후, 새로운 ( V_{k+1} ) 계산
• 계산이 끝나면 ( V_{k+1} )을 복사해 ( V_k )로 덮어씀

정확한 k-step 계산 보장
메모리 소모 큼

▶ b) 상태가치 테이블 1개 사용

• 하나의 테이블을 계속 덮어쓰며 계산

메모리 절약
단, k번째 계산에서 일부 상태는 이미 갱신된 값을 사용할 수 있음

📌 예시:

• ( V_1(s_0) ) 계산 후 바로 ( V_1(s_1) )을 계산하면 ( V_0(s_0) )이 아닌 ( V_1(s_0) )을 참조하게 됨

→ 하지만 이 방식도 수렴은 보장되므로 상황에 따라 선택 가능

📌 그림 2.36은 두 방법을 시각적으로 비교한 그림이다.

---

🧮 2장 코드 구현 (3): 반복 정책 평가

🔁 반복 정책 평가 알고리즘 개요

앞서 본 정책 평가의 재귀적 방식은 계산량이 크고 느리다는 단점이 있었다.
이를 해결하기 위해 반복 정책 평가 (Iterative Policy Evaluation) 알고리즘을 사용한다.

다음은 반복 정책 평가 알고리즘의 기본 구조이다:

1. 임의의 정책 π를 입력
2. 모든 상태 s ∈ S⁺에 대해 V(s) = 0으로 초기화
3. 반복:
    Δ ← 0
    모든 상태 s ∈ S에 대해:
        v ← V(s)
        V(s) ← ∑_a π(a|s) ∑_{s'} P(s'|s,a)[r(s,a,s') + γV(s')]
        Δ ← max(Δ, |v - V(s)|)
    Δ < θ (작은 양수)일 때 종료

---

🧪 상태가치 테이블 하나를 사용하는 구현

다음 코드는 상태가치 테이블을 하나만 사용하는 방식의 반복 정책 평가를 구현한 것이다:

# 반복 정책 평가
np.random.seed(0)
env = Environment()
agent = Agent()
gamma = 0.9

# 1. 상태가치 테이블 초기화
v_table = np.zeros((env.reward.shape[0], env.reward.shape[1]))
k = 1  # 반복 횟수

# 2. 반복 시작
while True:
	delta = 0  # 변화량 초기화
	
	# 3. 현재 가치 복사 (변화량 계산을 위해)
	temp_v = copy.deepcopy(v_table)
	
	# 4. 모든 상태에 대해 반복
	for i in range(env.reward.shape[0]):
		for j in range(env.reward.shape[1]):
			G = 0
			
			# 5. 가능한 모든 행동에 대해 기대값 계산
			for action in range(len(agent.action)):
				agent.set_pos([i, j])
				observation, reward, done = env.move(agent, action)
				
				G += agent.select_action_pr[action] * (reward + gamma * v_table[observation[0], observation[1]])
			
			v_table[i, j] = G  # 상태가치 업데이트
	
	# 6. 최대 변화량 계산
	delta = np.max([delta, np.max(np.abs(temp_v - v_table))])
	k += 1
	
	# 7. 변화량이 설정값보다 작으면 수렴
	if delta < 0.000001:
		break

---

📈 결과 해석: 반복 정책 평가 수렴 과정

그림 2.37은 위 알고리즘이 작동하는 과정을 시각적으로 보여준다.

예: 상태 s0s_0에 대해 계산한 첫 번째 상태가치 V₁(s₀)는 다음과 같다:

V₁(s₀) = π(up|s₀) * [r(out|s₀, up) + γV₀(s₀)] +
         π(right|s₀) * [r(s₁|s₀, right) + γV₀(s₁)] +
         π(down|s₀) * [r(s₃|s₀, down) + γV₀(s₃)] +
         π(left|s₀) * [r(out|s₀, left) + γV₀(s₀)]
       = -2.00

• 이동이 미로 밖이면 현재 상태의 가치 V(s₀)를 다시 참고한다.
• 이 계산을 모든 상태에 대해 반복하면 V1(s)V_1(s)이 완성되고, 변화량 Δ가 계산된다.

---

⏱ 수렴 속도 비교

• k = 1일 때 Δ = 2.438750 → 변화량 큼
• k = 2일 때 Δ = 1.57 → 감소함
• ...
• k = 133일 때 수렴 (Δ < 0.000001)

→ 계산 시간 약 4초

📌 비교:

• 재귀 방식에서 max_step=12일 때 계산 시간은 약 25분
• 반복 정책 평가는 같은 상태가치 수렴을 훨씬 빠르게 달성