hemisus
참고한 자료
이전 글에서 순차적 행동 결정 문제를 MDP로 정의하고, 벨만 기대 방정식과 최적 방정식을 얻었다. 이제 이 방정식을 풀 차례이다.
벨만 방정식을 푼다는 것은 방정식을 만족하는 가치함수를 찾는 것이다. 벨만 기대 방정식을 풀면 주어진 정책 $\pi$의 가치함수 $v_\pi$를 얻고, 벨만 최적 방정식을 풀면 최적 가치함수 \(v_*\)와 최적 큐함수 \(q_*\)를 얻는다.
에이전트는 정책에 따라 각 상태에서 어떤 행동을 할지 결정한다. 따라서 최종 목표는 가치함수 자체를 구하는 것이 아니라, 기대 반환값을 최대로 만드는 최적 정책 $\pi_*$를 찾는 것이다. 최적 큐함수를 알고 있다면, 각 상태에서 큐함수가 가장 큰 행동을 고르기만 하면 최적 정책을 얻을 수 있다.
\[\pi_*(s) = \arg\max_{a \in A} q_*(s, a)\]1. Dynamic Programming
다이내믹 프로그래밍(DP)은 큰 문제를 한 번에 풀지 않는다. 대신 문제를 작은 문제로 나누어 풀고, 그 해를 이용해 큰 문제의 해에 도달한다. MDP에서는 벨만 방정식을 통해 이러한 분할이 가능하다. 현재 상태의 가치가 다음 상태의 가치로 재귀적으로 표현되므로, 다음 상태들의 가치를 이용해 현재 상태의 가치를 계산할 수 있다.
따라서 DP에서는 가치함수를 한 번에 정확히 구하지 않는다. 임의의 초기값 $v_0$에서 시작하여, 벨만 방정식을 이용해 가치함수를 반복적으로 업데이트한다.
\[v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_k \rightarrow \cdots \rightarrow v_\pi\]DP로 벨만 방정식을 푸는 방법은 두 가지이다. 벨만 기대 방정식을 이용하는 정책 이터레이션(Policy Iteration)과, 벨만 최적 방정식을 이용하는 가치 이터레이션(Value Iteration)이다.
DP를 적용할때 유의할 점은, 환경의 모델, 즉 상태 변환 확률 $P_{ss’}^a$과 보상함수 $R_s^a$를 알고 있어야 한다는 것이다. 벨만 방정식의 기댓값을 계산하려면 다음 상태가 어떤 확률로 나타나는지 알아야 하기 때문이다. 따라서 DP는 환경과 상호작용하며 배우는 학습(learning)이라기보다, 알려진 모델을 바탕으로 계산하는 계획(planning)에 가깝다.
책에서는 그리드월드 예제를 통해 내용을 설명한다. 그리드월드에서 에이전트는 격자 위를 상하좌우로 이동하며 장애물을 피해 목표 지점에 도달해야 한다.
2. Policy Iteration (정책 이터레이션)
정책 이터레이션은 임의의 정책에서 시작한다. 책에서는 모든 행동을 같은 확률로 선택하는 무작위 정책을 초기 정책으로 사용한다. 무작위 정책은 당연히 최적 정책이 아니므로, 현재 정책이 얼마나 좋은지 평가하고, 그 평가를 바탕으로 더 나은 정책으로 발전시켜야 한다. 이 두 과정을 반복하면 정책은 점점 개선되어 최적 정책에 수렴한다.
\[\pi_0 \xrightarrow{\text{평가}} v_{\pi_0} \xrightarrow{\text{발전}} \pi_1 \xrightarrow{\text{평가}} v_{\pi_1} \xrightarrow{\text{발전}} \cdots \rightarrow \pi_*\]정책 평가 (Policy Evaluation)
정책이 얼마나 좋은지를 판단하는 기준으로 가치함수를 사용할 수 있다.
\[v_\pi(s) = \mathbb{E}_\pi\left[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \mid S_t = s\right]\]가치함수는 상태 $s$에서 정책 $\pi$를 따라 행동했을 때 앞으로 받을 보상의 할인된 합(반환값)의 기댓값이다. 같은 상태에서 출발하더라도 어떤 정책을 따르느냐에 따라 받게 될 보상이 달라지므로, 가치함수는 그 자체로 정책의 좋고 나쁨을 판단하는 기준이 된다.
정책 이터레이션에서는 이 가치함수를 DP로 계산하기 위해 벨만 기대 방정식을 사용한다.
\[v_\pi(s) = \mathbb{E}_\pi\left[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s\right]\]이 식의 핵심은 미래의 모든 보상을 직접 더하지 않는다는 것이다. 대신 현재 상태에서 행동했을 때 받는 보상과 그 행동으로 도달할 수 있는 다음 상태들의 가치함수만으로 현재 상태의 가치함수를 표현한다. 기댓값 $\mathbb{E}_\pi$를 풀어 쓰면, 다음과 같이 계산 가능한 형태가 된다.
\[v_\pi(s) = \sum_{a \in A} \pi(a \mid s) \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_\pi(s') \right)\]각 행동을 선택할 확률 $\pi(a \mid s)$로, 그 행동을 했을 때의 보상과 다음 상태 가치의 합을 가중평균한 형태이다.
그런데 우리는 아직 참 가치함수 $v_\pi$를 모른다. 따라서 위 식의 우변에 참값 대신 현재까지 계산한 $k$번째 가치함수 $v_k$를 넣고, 그 결과를 $k+1$번째 가치함수 $v_{k+1}$로 삼는다.
\[v_{k+1}(s) = \sum_{a \in A} \pi(a \mid s) \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_k(s') \right)\]$v_k$는 참값이 아니므로 한 번 계산한 $v_{k+1}$ 역시 참값이 아니다. 하지만 이 업데이트를 모든 상태에 대해 반복하면, 실제 보상 $R_s^a$에 대한 정보가 매 반복마다 주변 상태로 전파되면서 $v_k$는 $v_\pi$에 수렴한다.
위 수식은 모든 상태의 $v_{k+1}$을 이전 반복의 값 $v_k$만으로 계산하는 동기식 업데이트를 나타낸다. 이를 위해 $v_k$와 $v_{k+1}$을 저장할 테이블을 따로 두며, 책의 코드도 이 방식을 따른다. 반면 테이블을 하나만 두고 계산 즉시 값을 덮어쓰는 제자리 업데이트(in-place update)에서는 이웃 상태 중 일부는 이미 갱신된 $v_{k+1}$, 일부는 $v_k$를 참조하게 된다. 이 경우에도 모든 상태가 반복적으로 갱신되기만 하면 $v_\pi$로 수렴하며, 최신 값을 바로 활용하므로 보통 더 빠르게 수렴한다.
그리드월드는 어떤 상태에서 행동 $a$를 하면 항상 정해진 다음 상태 $s’$로 이동한다고 가정한다. 즉 상태 변환 확률이 해당 $s’$에 대해서만 1이고 나머지는 0이므로, $s’$에 대한 합이 사라져 식이 다음과 같이 단순해진다.
\[v_{k+1}(s) = \sum_{a \in A} \pi(a \mid s) \left( R_s^a + \gamma \, v_k(s') \right)\]이것이 한 번의 정책평가 과정이다. 한 번의 정책평가로는 제대로 정책이 평가될 수 없으므로 여러 번 반복한다.
정책 발전 (Policy Improvement)
정책 평가로 현재 정책의 가치함수를 구했다면, 이제 이를 바탕으로 정책을 발전시킬 차례이다. 정책을 발전시키는 방법은 여러 가지가 있지만, 책에서는 기본적인 방법인 탐욕 정책 발전(greedy policy improvement)을 사용한다.
정책은 각 상태에서 어떤 행동을 할지 정하는 것이다. 그런데 가치함수 $v_\pi(s)$는 상태 하나의 가치만 알려 줄 뿐, 그 상태에서 어떤 행동이 더 좋은지는 직접 알려 주지 않는다. 행동을 비교하려면 상태와 행동의 쌍에 대한 가치, 즉 큐함수가 필요하다.
\[q_\pi(s, a) = \mathbb{E}_\pi\left[R_{t+1} + \gamma\, v_\pi(S_{t+1}) \mid S_t = s, A_t = a\right]\]큐함수는 상태 $s$에서 행동 $a$를 한 뒤, 그 이후로는 정책 $\pi$를 따랐을 때의 기대 반환값이다. 기댓값을 풀어 쓰면 다음과 같이 계산 가능한 형태가 된다.
\[q_\pi(s, a) = R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_\pi(s')\]이 식에서 알 수 있듯이, 큐함수는 정책 평가에서 구한 가치함수만으로 계산할 수 있다. 따라서 큐함수를 별도로 저장할 필요가 없다. 그리드월드처럼 행동에 따라 다음 상태가 하나로 정해지는 환경에서는 식이 더 단순해진다.
\[q_\pi(s, a) = R_s^a + \gamma\, v_\pi(s')\]탐욕 정책 발전은 상태 $s$에서 선택 가능한 모든 행동의 큐함수를 비교하고, 그중 큐함수가 가장 큰 행동을 선택한다. 이렇게 발전된 정책 $\pi’$는 다음과 같다.
\[\pi'(s) = \arg\max_{a \in A} q_\pi(s, a)\]큐함수가 최대인 행동이 여러 개라면, 그 행동들에 확률을 균등하게 나누어 준다. 예를 들어 두 행동의 큐함수가 같은 최댓값을 가지면 각각 $0.5$의 확률로, 세 행동이면 각각 $\frac{1}{3}$의 확률로 정책을 수정한다.
탐욕 정책 발전으로 얻은 정책은 이전 정책보다 나빠지지 않는다. 즉 모든 상태 $s$에 대해 다음이 성립한다.
\[v_{\pi'}(s) \geq v_\pi(s)\]정책 평가와 정책 발전을 반복하다가 정책이 더 이상 바뀌지 않는 순간이 온다. 이때는 각 상태에서 고르는 행동이 이미 큐함수를 최대로 만드는 행동이라는 뜻이다. 즉 이 시점의 가치함수는 벨만 최적 방정식을 만족하고, 그때의 정책이 최적 정책 $\pi_*$이다. 또한 유한 MDP에서는 정책의 개수가 유한하므로, 이 과정은 유한 번의 반복 안에 끝난다.
3. Value Iteration (가치 이터레이션)
정책 이터레이션에서는 정책과 가치함수가 명확히 분리되어 있었다. 정책 $\pi$는 별도로 저장되어 있고, 가치함수는 그 정책이 얼마나 좋은지를 평가하는 도구로만 쓰였다. 정책 평가를 아무리 반복해도 정책은 바뀌지 않으며, 정책은 정책 발전 단계에서만 바뀐다.
가치 이터레이션은 정책을 따로 두지 않는다. 대신 현재의 가치함수가 최적 가치함수라고 가정한다. 이 가정 하에, 최적 정책은 각 상태에서 큐함수가 가장 큰 행동을 고르는 것이므로 가치함수로부터 바로 얻을 수 있다.
\[\pi(s) = \arg\max_{a \in A} \left( R_s^a + \gamma\, v_k(s') \right)\]이 정책은 가장 좋은 행동 하나만을 선택하는 결정적(deterministic) 정책이다. 무작위 정책처럼 확률적으로 행동을 고르는 정책 이터레이션의 초기 정책과 대비된다. 이 결정적 정책을 벨만 기대 방정식에 대입하면, 행동에 대한 가중평균이 최댓값 하나로 바뀌어 결국 벨만 최적 방정식을 이용한 업데이트가 된다.
물론 처음의 가치함수는 최적이 아니므로 이 가정은 사실이 아니다. 하지만 업데이트를 반복하면 가치함수는 최적 가치함수에 수렴하고 최적 정책을 구할 수 있다. 따라서 가치 이터레이션은 정책을 따로 발전시키는 단계 없이 가치함수만 반복해서 업데이트하고, 정책은 수렴한 가치함수로부터 마지막에 한 번 꺼내 쓰면 된다. 가치함수 안에 정책이 내재적으로 포함되어 있다는 것이다.
벨만 최적 방정식은 다음과 같다.
\[v_*(s) = \max_{a \in A} \mathbb{E}\left[R_{t+1} + \gamma\, v_*(S_{t+1}) \mid S_t = s, A_t = a\right]\]벨만 기대 방정식과 비교하면, 정책 $\pi$에 대한 기댓값 $\mathbb{E}_\pi$ 대신 행동에 대한 최댓값 $\max_a$가 들어가 있다. 기댓값을 풀어 쓰면 다음과 같이 계산 가능한 형태가 된다.
\[v_*(s) = \max_{a \in A} \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_*(s') \right)\]정책 평가에서와 마찬가지로, 우리는 아직 참값 $v_*$를 모른다. 따라서 우변에 현재까지 계산한 $v_k$를 넣고, 그 결과를 $v_{k+1}$로 삼아 반복한다.
\[v_{k+1}(s) = \max_{a \in A} \left( R_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \, v_k(s') \right)\]그리드월드에서는 행동에 따라 다음 상태가 하나로 정해지므로, $s’$에 대한 합이 사라져 다음과 같이 단순해진다.
\[v_{k+1}(s) = \max_{a \in A} \left( R_s^a + \gamma\, v_k(s') \right)\]정책 평가의 업데이트 식과 나란히 놓으면 차이가 분명해진다.
\[\begin{aligned} \text{정책 이터레이션 (평가)} &: \quad v_{k+1}(s) = \sum_{a \in A} \pi(a \mid s) \left( R_s^a + \gamma\, v_k(s') \right) \\ \text{가치 이터레이션} &: \quad v_{k+1}(s) = \max_{a \in A} \left( R_s^a + \gamma\, v_k(s') \right) \end{aligned}\]정책 평가는 정책이 정한 확률로 각 행동의 값을 가중평균하는 반면, 가치 이터레이션은 그중 최댓값만 취한다. 업데이트 식 자체에 “가장 좋은 행동을 고른다”는 정책 발전이 이미 포함되어 있는 셈이다.
이 업데이트를 모든 상태에 대해 반복하면 $v_k$는 $v_*$에 수렴한다. 이렇게 얻은 가치함수로부터, 앞서 본 $\arg\max$ 식으로 각 상태의 최적 행동을 꺼내면 최적 정책이 된다.
\[\pi_*(s) = \arg\max_{a \in A} \left( R_s^a + \gamma\, v_*(s') \right)\]| 정책 이터레이션 | 가치 이터레이션 | |
|---|---|---|
| 사용하는 방정식 | 벨만 기대 방정식 | 벨만 최적 방정식 |
| 정책 저장 | 명시적으로 저장 | 저장하지 않음 (가치함수에 내재) |
| 반복 단위 | 정책 평가 + 정책 발전 | 가치함수 업데이트 |
| 업데이트 연산 | 정책에 따른 가중평균 | 최댓값 |
| 정책을 얻는 시점 | 매 정책 발전마다 | 가치함수 수렴 후 $\arg\max$로 추출 |