바닥부터 배우는 강화 학습 | 06. MDP를 모를 때 최고의 정책 찾기

'바닥부터 배우는 강화 학습' 6장에는 MDP를 모르고 있는 경우 최고의 정책을 찾는 방법에 대해서 설명하고 있습니다. 아래 내용은 공부하면서 핵심 내용을 정리한 것입니다.

참고자료

도서: 바닥부터 배우는 강화 학습 / 6장 MDP를 모를 때 최고의 정책 찾기
동영상: https://www.youtube.com/watch?v=2h-FD3e1YgQ&list=PLpRS2w0xWHTcTZyyX8LMmtbcMXpd3s4TU&index=5

첫 번째: 반복적인 정책평가를 사용할 수 없음
모델 프리 상황에서는 보상함수 $r_s^a$와 전이확률 $P_{ss'}^a$을 모르기 때문에 아래 벨만 기대 방정식을 사용할 수 없음

$$v_{\pi}(s) = \sum_{a \in A} \pi(a|s) \left( r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s') \right)$$

두 번째: 정책 개선 단계에서 그리디 정책을 만들 수 없음
각 상태의 밸류를 안다고 하더라도 전이확률 $P_{ss'}^a$을 모르기 때문에 액션을 취했을 때 어떤 상태에 도달할지 알 수 없음

1. 평가 자리에 MC

2. V 대신 Q

밸류 $v(s)$ 대신에 상태-액션 가치 함수 $q(s, a)$를 이용 (MDP를 몰라도 그리디 액션을 선택할 수 있음)
◦ MC를 이용하여 $q(s, a)$ 함수를 계산
◦ 평가된 $q(s, a)$를 이용하여 새로운 그리디 정책을 생성
◦ 위 두 과정을 반복
위 방법은 새로운 길을 탐색하지 못하므로 최적의 해를 찾지 못할 수 있음

3. greedy 대신 $\epsilon$ - greedy

$$\pi(a|s)=
\begin{cases}
1 - \epsilon, & \mbox{if } a* = \underset{a}{\mathrm{argmax}} \; q(s, a) \\
\epsilon, & \text{otherwise}
\end{cases}$$

이 부분은 아래 문제를 해결하기 위한 구현에 대한 코드가 설명되어 있습니다.
◦ S에서 출발 해서 G에 도착하면 끝
◦ 회색 영역은 지나갈 수 없는 벽이 놓여 있는 곳
◦ 보상은 스텝마다 -1 (즉 최단 거리로 G에 도달하는 것이 목적)

TD를 이용한 V 학습 및 Q 학습의 수식
◦ TD로 V 학습: $V(S) \gets V(S) + \alpha (R + \gamma V(S') - V(S))$
◦ TD로 Q 학습 (SARSA): $Q(S, A) \gets Q(S, A) + \alpha (R + \gamma Q(S', A') - Q(S, A))$
벨만 기대 방정식 0단계
◦ TD로 V 학습: $v_{\pi}(s_t) = \mathbb{E} [r_{t+1} + \gamma v_{\pi}(s_{t+1})]$
◦ TD로 Q 학습 (SARSA): $q_{\pi}(s_t, a_t) = \mathbb{E} [r_{t+1} + \gamma q_{\pi}(s_{t+1}, a_{t+1})]$

이 부분은 구현에 대한 코드가 설명되어 있습니다.

1 과거의 경험을 재사용할 수 있다

on-policy 방법은 $\pi_t$ 에서 $\pi_{t+1}$을 학습하기 위해서는 항상 $\pi_t$을 따르는 새로운 경험이 필요
off-policy 방법은 타깃 정책과 행동 정책이 달라도 되기 때문에 $\pi_t$ 에서 경험한 샘플들을 $\pi_{t+1}$ 및 $\pi_{t+n}$ 등 여러 정책에서 재사용 가능

2 사람의 데이터로부터 학습할 수 있다

3 일대다, 다대일 학습이 가능하다

최적의 액션 밸류: $q_{*}(s, a) = \underset{\pi}{\mathrm{max}} \; q_{\pi}(s, a)$
최적의 행동: $\pi_{*} = \underset{a}{\mathrm{argmax}} \; q_{*}(s, a)$
벨만 최적 방정식 2단계: $q_{*}(s, a) = r_s^a+ \gamma \sum_{s' \in S} P_{ss'}^a \underset{a'}{\mathrm{max}} \; q_{*} (s', a')$
MDP를 모르기 때문에 위 수식을 그대로 이용할 수 없음
벨만 최적 방정식 0단계: $q_{*}(s, a) = \mathbb{E}_{s'} [r + \gamma \; \underset{a'}{\mathrm{max}} \; q_{*} (s', a')]$
위 수식은 TD 학습이 가능
SARSA: $Q(S, A) \gets Q(S, A) + \alpha (R + \gamma Q(S', A') - Q(S, A))$
Q러닝: $Q(S, A) \gets Q(S, A) + \alpha (R + \gamma \; \underset{A'}{\mathrm{max}} \; Q(S', A') - Q(S, A))$

SARSA의 경우는 행동 정책과 타깃 정책이 같지만 Q러닝의 경우 행동 정책과 타깃 정책이 다름
SARSA: $q_{\pi}(s_t, a_t) = \mathbb{E}_{\pi} [r_{t+1} + \gamma q_{\pi}(s_{t+1}, a_{t+1})]$
Q러닝: $q_{*}(s_t, a_t) = \mathbb{E}_{s'} [r + \gamma \; \; \underset{a'}{\mathrm{max}} \; q_{*}(s', a')]$
$\mathbb{E}_{\pi}$는 정책 함수 $\pi$를 따라가는 경로에 대한 기댓값이 필요
$\mathbb{E}_{s'}$는 정책 함수 $\pi$와 상관없음

이 부분은 구현에 대한 코드가 설명되어 있습니다.