실습 · 연습문제 2개

정책 $\pi$를 고정하면 Bellman 기대 방정식은 선형이다.

$$\mathbf{v}^\pi = \mathbf{r}^\pi + \gamma \mathbf{P}^\pi \mathbf{v}^\pi, \qquad P^\pi_{ss'} = \sum_a \pi(a \mid s) P(s' \mid s, a), \qquad r^\pi_s = \sum_a \pi(a \mid s) R(s, a).$$

함수 evaluate_policy(P, R, pi, gamma)를 완성해 $V^\pi$를 반환한다.

인자	shape	뜻
P	(S, A, S)	P[s, a, s2] = 상태 s에서 행동 a를 했을 때 다음 상태가 s2일 확률
R	(S, A)	기대 즉시 보상
pi	(S, A)	pi[s, a] = 상태 s에서 행동 a를 고를 확률
gamma	스칼라	할인율, 0 <= gamma < 1

반환하는 V의 shape은 (S,)이다. 테스트는 손으로 푼 작은 MDP, 본문의 격자 세계(무작위 정책의 값 0.248, −0.531), Bellman 잔차를 확인한다.

힌트: np.einsum("sa,sat->st", pi, P)가 $\mathbf{P}^\pi$다. 반복 대신 np.linalg.solve로 한 번에 푼다.

Bellman 최적 연산자

$$(\mathcal{T}V)(s) = \max_a \Big[R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V(s')\Big]$$

는 $\gamma < 1$이면 최대 노름에서 수축 사상이므로, $V_{k+1} = \mathcal{T}V_k$를 반복하면 $V^*$로 수렴한다. 함수 value_iteration(P, R, gamma, tol=1e-10, max_iter=100_000)를 완성한다.

• 연속한 두 반복의 최대 차이 $\lVert V_{k+1} - V_k \rVert_\infty$가 tol보다 작아지면 멈춘다.
• 반환값은 (V, pi)다. V는 shape (S,)의 실수 배열, pi는 shape (S,)의 정수 배열로 상태마다 $\arg\max_a \big[R(s, a) + \gamma \sum_{s'} P V\big]$를 담는다.
• 배열 규약은 본문과 같다: P[s, a, s2], R[s, a].

테스트는 할인율에 따라 최적 행동이 바뀌는 2상태 MDP, 본문의 격자 세계(시작 칸 $V^* = 0.703$과 화살표 정책), Bellman 최적 방정식의 잔차, 무작위 MDP에서 $V^*$가 다른 결정적 정책들의 가치보다 작지 않은지를 확인한다.

힌트: P @ V는 shape (S, A)이고 [s, a] 원소가 $\sum_{s'} P(s' \mid s, a) V(s')$다.