1강에서 정의한 강화학습 문제를 담는 그릇이 마르코프 결정 과정(MDP)이다. 거의 모든 강화학습 문제가 MDP로 형식화된다. 마르코프 연쇄에서 시작해 보상을 얹고 행동을 더하는 식으로, 한 층씩 쌓아 올린다. 실버는 강의 내내 하나의 예, ‘학생’을 끌고 가는데 우리도 그 예를 따라간다.
강의 슬라이드: PDF
마르코프 성질과 마르코프 과정
상태가 마르코프라는 건, 미래를 정하는 데 지금 상태만으로 충분하다는 뜻이다(1강). 과거를 다 알아도 지금보다 나은 예측을 못 한다.
$$\mathbb{P}[S_{t+1} \mid S_t] = \mathbb{P}[S_{t+1} \mid S_1, \dots, S_t]$$상태들 사이를 오가는 확률을 모으면 전이 행렬 $\mathcal{P}$가 된다. $\mathcal{P}_{ss'} = \mathbb{P}[S_{t+1}=s' \mid S_t=s]$이다. 상태 집합 $\mathcal{S}$와 이 $\mathcal{P}$만으로 이루어진, 기억 없는 무작위 과정이 마르코프 과정(마르코프 연쇄)이다.
여기서 실버의 학생 예가 등장한다. 상태는 수업 1, 수업 2, 수업 3, 합격, 술집, 페이스북, 그리고 잠이다. 학생은 확률적으로 이 상태들을 오간다. 수업 중에 페이스북에 빠지기도 하고, 합격을 앞두고 술집에 들렀다가 앞 수업으로 되돌아가기도 한다. 이 오감의 확률이 전이 행렬이고, ‘잠’은 한번 들어가면 나오지 않는 종료 상태다.
학생 마르코프 연쇄. “▶ 에피소드 샘플링"을 누르면 수업 1에서 출발해 전이 확률을 따라 무작위로 상태를 밟다가 ‘잠’에서 끝난다. 돌릴 때마다 다른 경로가 나온다.
마르코프 보상 과정 (MRP)
마르코프 과정에 보상과 할인율을 더하면 MRP다. 각 상태에 보상 $\mathcal{R}_s = \mathbb{E}[R_{t+1} \mid S_t=s]$를 매기고, 할인율 $\gamma \in [0,1]$를 둔다. 학생 예라면 수업은 힘드니 음의 보상, 술집은 잠깐 즐거우니 작은 양의 보상, 합격은 큰 양의 보상을 주는 식이다.
리턴은 지금부터 받을 보상의 할인 합이다.
$$G_t = R_{t+1} + \gamma R_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$$\gamma$가 0에 가까우면 눈앞의 보상만 챙기는 근시안이고, 1에 가까우면 먼 미래까지 내다본다. 할인을 두는 이유는 여럿이다. 무한히 이어지는 합을 수렴시키고, 먼 미래의 불확실성을 반영하며, 수학을 깔끔하게 만든다.
가치함수는 리턴의 기댓값, 곧 그 상태에서 출발했을 때 앞으로 받을 보상의 평균이다.
$$v(s) = \mathbb{E}[G_t \mid S_t = s]$$이걸 한 걸음과 다음 상태 가치로 쪼갠 것이 벨만 방정식이다.
$$v(s) = \mathcal{R}_s + \gamma \sum_{s'} \mathcal{P}_{ss'}\, v(s')$$지금 받을 보상에, 갈 수 있는 다음 상태들의 가치를 확률로 가중해 더한 것이다. 여기엔 최댓값이 없다. 그래서 선형 방정식이고, 손으로 풀 수 있다. 모든 상태를 한꺼번에 벡터로 쓰면 이렇다.
$$v = \mathcal{R} + \gamma \mathcal{P} v$$$v$를 한쪽으로 모으면
$$(I - \gamma \mathcal{P})\,v = \mathcal{R}$$이고, 역행렬을 곱하면 한 번에 풀린다.
$$v = (I - \gamma \mathcal{P})^{-1}\mathcal{R}$$다만 역행렬 계산이 상태 수 $n$에 대해 $O(n^3)$이라, 이 직접 풀이는 상태가 적은 MRP에서만 쓸 만하다. 큰 MRP는 앞으로 볼 반복법(동적 계획법, 몬테카를로, TD)으로 푼다. 그리고 뒤의 MDP에서 최댓값이 끼어드는 순간 이 선형 풀이가 깨지고, 반복법이 반드시 필요해진다.
같은 연쇄에 각 상태의 보상이 붙었다. 할인율 γ를 바꿔 가며 에피소드를 뽑으면, 같은 경로라도 리턴 G가 어떻게 달라지는지 볼 수 있다. γ가 작을수록 눈앞의 보상만, 클수록 먼 미래까지 반영한다.
마르코프 결정 과정 (MDP)
MRP에 행동을 더하면 MDP다. 이제 상태가 저절로 흘러가는 게 아니라, 매 상태에서 에이전트가 행동을 고르고 그 선택이 전이와 보상을 바꾼다. 학생 예로 치면, 페이스북에 빠질지 수업을 들을지, 술집에 갈지 공부할지를 학생이 정하는 것이다.
행동을 고르는 규칙이 정책 $\pi(a \mid s) = \mathbb{P}[A_t = a \mid S_t = s]$다. 정책을 고정하면 두 가지 가치를 잴 수 있다. 상태 가치 $v_\pi(s)$는 그 상태에서 정책 $\pi$를 따를 때의 기대 리턴이고, 행동 가치 $q_\pi(s,a)$는 그 상태에서 행동 $a$를 한 뒤 정책을 따를 때의 기대 리턴이다.
둘은 서로를 통해 정의되고, 이것이 벨만 기대 방정식이다.
$$v_\pi(s) = \sum_a \pi(a\mid s)\, q_\pi(s,a), \qquad q_\pi(s,a) = \mathcal{R}_s^a + \gamma\sum_{s'}\mathcal{P}_{ss'}^a\, v_\pi(s')$$실버가 벨만 방정식을 설명하는 백업 다이어그램이다. 밝고 큰 원이 상태, 검은 점이 행동이다. 위 식을 그림으로 옮긴 것으로, 상태 $s$의 가치 $v_\pi(s)$는 정책 $\pi$로 각 행동을 고른 뒤의 행동 가치 $q_\pi(s,a)$를 평균한 값이고, 행동 가치는 보상 $r$을 받고 전이 확률 $\mathcal{P}$를 따라 도달한 다음 상태들의 가치 $v_\pi(s')$를 되짚어 올린 값이다. 가치가 아래에서 위로 백업되는 흐름을 그린 셈이다.
이제 상태마다 행동을 직접 고른다. 수업 1에서 출발해 ‘공부’와 ‘페이스북’ 중 하나를 누르면 그 행동의 보상을 받고 다음 상태로 간다. ‘술집’은 결과가 확률적이라 어디로 튈지 모른다. 정책이란 결국 각 상태에서 어떤 버튼을 누를지 정하는 규칙이다.
최적 가치와 벨만 최적 방정식
우리가 원하는 건 아무 정책이 아니라 가장 좋은 정책이다. 최적 상태 가치 $v_*(s) = \max_\pi v_\pi(s)$와 최적 행동 가치 $q_*(s,a) = \max_\pi q_\pi(s,a)$는 도달할 수 있는 최선의 가치다.
$q_*$를 알면 최적 정책은 거저 얻는다. 각 상태에서 $q_*(s,a)$가 가장 큰 행동을 결정적으로 고르면 된다. 모든 MDP에는 이런 결정적 최적 정책이 하나 이상 존재한다.
기댓값 자리에 최댓값이 들어가면 벨만 최적 방정식이다.
$$v_*(s) = \max_a \left( \mathcal{R}_s^a + \gamma \sum_{s'}\mathcal{P}_{ss'}^a\, v_*(s') \right)$$$\max$ 때문에 비선형이라 앞의 MRP처럼 한 번에 풀리지 않는다. 반복법이 필요하고, 그것이 다음 강의 동적 계획법이다.
확장
실버는 마지막에 확장들을 짚는다. 무한·연속 상태, 부분관측(POMDP), 할인 없는 평균 보상 같은 경우다. 뼈대는 같고, 다루기가 조금씩 더 까다로워질 뿐이다.
다음 강에서는 MDP를 완전히 안다고 가정하고, 이 벨만 방정식들을 반복으로 풀어 최적 정책을 찾는 동적 계획법으로 들어간다.