17장 - MDP와 가치 및 정책 반복

17장. MDP와 가치 및 정책 반복

이번 강의에서는 마르코프 결정 과정(MDP)의 핵심 개념인 가치 함수를 정의하고, 최적 정책을 구하기 위한 두 가지 알고리즘인 가치 반복과 정책 반복을 배운다. 나아가 상태 전이 확률을 데이터로부터 추정하여 실제 강화 학습 시스템을 구축하는 방법까지 다룬다.

17.1 MDP 복습

이전 강의에서 다룬 마르코프 결정 과정(Markov Decision Process, MDP)의 핵심 요소를 복습한다. MDP는 다섯 가지 요소로 구성된 튜플이다.

11개 상태로 구성된 격자 세계(grid world) 예제에서 로봇이 북쪽으로 이동을 시도하면 80% 확률로 실제로 북쪽으로 가고, 10% 확률로 왼쪽으로, 10% 확률로 오른쪽으로 벗어난다.

MDP의 작동 방식은 다음과 같다. 초기 상태 \(s_0\)에서 시작하여 행동 \(a_0\)을 선택하면, 다음 상태 \(s_1\)은 \(P_{s_0 a_0}\)에 따라 결정된다. 다시 행동 \(a_1\)을 선택하면 \(s_2\)가 \(P_{s_1 a_1}\)에 따라 결정되며, 이 과정이 반복된다. 총 보상(total payoff)은 다음과 같다.

\[R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots\]

정책(policy) \(\pi\)는 상태에서 행동으로의 매핑 \(\pi: S \to A\)이며, 목표는 기대 총 보상을 최대화하는 정책을 찾는 것이다.

최적 정책을 찾는 것이 왜 어려운가? 11개 상태에 4개 행동이 있다면 가능한 정책의 수는 \(4^{11}\)이다. 상태 수가 작으면 큰 수가 아니지만, 일반적으로 가능한 정책의 수는 \(|A|^{|S|}\)로 조합적으로 폭발한다.

17.2 가치 함수

최적 정책을 계산하는 알고리즘을 개발하기 위해 세 가지 개념을 정의해야 한다: \(V^\pi\)(정책의 가치 함수), \(V^*\)(최적 가치 함수), \(\pi^*\)(최적 정책).

17.2.1 정책의 가치 함수 \(V^\pi\)

정책 \(\pi\)에 대한 가치 함수 \(V^\pi\)는 상태에서 실수로의 함수로, 다음과 같이 정의된다.

\[V^\pi(s) = E\left[R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots \mid \pi,\; s_0 = s\right]\]

즉, \(V^\pi(s)\)는 상태 \(s\)에서 출발하여 정책 \(\pi\)를 실행했을 때 얻을 수 있는 기대 총 보상이다.

구체적인 예를 들어보자. 격자 세계에서 어떤 (그다지 좋지 않은) 정책을 실행한다고 하자. 이 정책이 일부 상태에서 로봇을 \(-1\) 보상 쪽으로 효율적으로 안내한다면, 해당 상태들의 가치는 음수가 된다. 반대로 \(+1\) 보상 쪽으로 효율적으로 안내하는 상태들은 양수 가치를 갖는다. 예를 들어 상태 \((1,1)\)에서 출발하면 기대 총 보상이 \(-0.88\) 정도가 될 수 있다.

격자 세계에서 \(+1\)과 \(-1\) 보상이 있는 상태는 **흡수 상태(absorbing state)**라고 부른다. 로봇이 이 상태에 도달하면 세계가 종료되어 이후 보상이나 패널티가 없다.

17.2.2 벨만 방정식 (정책 버전)

가치 함수를 지배하는 핵심 방정식이 바로 **벨만 방정식(Bellman's equation)**이다.

\[V^\pi(s) = R(s) + \gamma \sum_{s'} P_{s\pi(s)}(s') \, V^\pi(s')\]

이 방정식의 직관은 다음과 같다. 로봇이 상태 \(s\)에서 깨어나면:

1. 즉시 보상(immediate reward) \(R(s)\)를 받는다. 이것은 해당 상태에 있다는 사실만으로 받는 보상이다.
2. 정책 \(\pi\)에 따라 행동 \(a = \pi(s)\)를 취한다.
3. 다음 상태 \(s'\)로 전이되며, \(s'\)는 \(P_{s\pi(s)}\)에 따라 결정된다.
4. 상태 \(s'\)에서의 기대 미래 보상은 \(V^\pi(s')\)이고, 이를 \(\gamma\)로 할인한다.

이를 풀어서 유도하면 다음과 같다. \(V^\pi(s)\)를 전개하면:

\[V^\pi(s) = R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots\]

여기서 \(\gamma\)를 하나 인수로 묶어내면:

\[V^\pi(s) = R(s_0) + \gamma \left[R(s_1) + \gamma R(s_2) + \cdots\right]\]

대괄호 안의 항은 바로 \(V^\pi(s_1)\), 즉 \(V^\pi(s')\)이다. 따라서 벨만 방정식이 성립한다.

표기법에 대해 잠시 정리하면, 긴 상태 수열을 나타낼 때는 \(s_0, s_1, s_2, \ldots\)를 사용하고, 현재 상태와 다음 상태 두 개만 다룰 때는 \(s\)와 \(s'\)를 사용한다.

17.2.3 가치 함수를 연립방정식으로 풀기

벨만 방정식은 \(V^\pi(s)\)를 미지수로 보면 연립일차방정식을 형성한다. 구체적인 예를 들면, 상태 \((3,1)\)에서 정책이 북쪽으로 가라고 지시한다면:

\[V^\pi(3,1) = R(3,1) + \gamma \left[0.8 \cdot V^\pi(3,2) + 0.1 \cdot V^\pi(2,1) + 0.1 \cdot V^\pi(4,1)\right]\]

11개 상태가 있으면 11개의 벨만 방정식이 생기고, 이는 11개 미지수에 대한 11개 연립일차방정식이 된다. 선형대수 풀이기(linear algebra solver)를 사용하면 \(V^\pi\)의 모든 값을 명시적으로 구할 수 있다.

정리하면, 어떤 정책 \(\pi\)가 주어지면(좋은 정책이든 나쁜 정책이든) 다음 절차로 가치 함수를 구한다:

1. 11차원 벡터 \((V^\pi(1,1),\; V^\pi(1,2),\; \ldots,\; V^\pi(4,3))\)를 미지수로 설정한다.
2. 각 상태에 대해 벨만 방정식을 하나씩 세운다.
3. 연립일차방정식을 풀어 모든 가치를 구한다.

17.3 최적 가치 함수와 최적 정책

17.3.1 최적 가치 함수 \(V^*\)

최적 가치 함수(optimal value function) \(V^*\)는 모든 가능한 정책에 대해 가치 함수의 최댓값을 취한 것이다.

\[V^*(s) = \max_\pi V^\pi(s)\]

강화 학습 용어에서 "가치 함수"라는 말은 두 가지 의미로 쓰인다. 하나는 특정 정책 \(\pi\)에 대한 가치 함수 \(V^\pi\)이고, 다른 하나는 최적 가치 함수 \(V^*\)이다. 전자는 좋은 정책일 수도 나쁜 정책일 수도 있지만, 후자는 가능한 모든 정책 중 최선의 가치를 나타낸다.

17.3.2 벨만 방정식 (최적 버전)

최적 가치 함수에 대한 벨만 방정식은 정책 버전과 다른 형태를 갖는다.

\[V^*(s) = R(s) + \max_a \gamma \sum_{s'} P_{sa}(s') \, V^*(s')\]

이 방정식의 직관은 다음과 같다. 상태 \(s\)에서 최선의 기대 총 보상은:

1. 즉시 보상 \(R(s)\)를 받는다.
2. 기대 미래 보상을 최대화하는 행동 \(a\)를 선택한다.
3. 해당 행동을 취했을 때의 기대 미래 보상은 \(\gamma \sum_{s'} P_{sa}(s') V^*(s')\)이다.

정책 버전의 벨만 방정식에서는 \(\pi(s)\)가 행동을 결정했지만, 최적 버전에서는 모든 행동 중 최선을 선택한다는 점이 핵심적인 차이다.

17.3.3 최적 정책 \(\pi^*\)

\(V^*\)를 알고 있다면, 각 상태에서의 최적 행동은 다음과 같이 구할 수 있다.

\[\pi^*(s) = \arg\max_a \sum_{s'} P_{sa}(s') \, V^*(s')\]

\(\gamma\)는 양수 상수이므로 argmax에 영향을 주지 않아 생략할 수 있다. 이 공식은 \(V^*\)를 알면 최적 정책을 효율적으로 계산할 수 있음을 보여준다.

다음 관계가 성립한다(증명 없이 제시):

\[V^*(s) = V^{\pi^*}(s) \geq V^\pi(s), \quad \forall \pi,\; \forall s\]

즉, 최적 가치 함수는 최적 정책의 가치 함수와 같으며, 다른 어떤 정책의 가치 함수보다 크거나 같다.

따라서 최적 정책을 찾는 전략은 두 단계로 구성된다:

1. \(V^*\)를 계산한다.
2. argmax 공식으로 \(\pi^*\)를 구한다.

2단계는 위 공식으로 바로 수행할 수 있으므로, 핵심 과제는 \(V^*\)를 계산하는 것이다.

17.3.4 최적 행동 계산 예제

격자 세계에서 \(V^*\)를 구한 뒤, 특정 상태의 최적 행동을 계산하는 과정을 살펴보자. 어떤 상태에서 서쪽(왼쪽)으로 갈 때의 기대 미래 보상을 계산하면:

\[\sum_{s'} P_{s,\text{west}}(s') \, V^*(s') = 0.8 \times 0.75 + 0.1 \times 0.69 + 0.1 \times 0.71 = 0.740\]

같은 상태에서 북쪽으로 갈 때의 기대 미래 보상은:

\[\sum_{s'} P_{s,\text{north}}(s') \, V^*(s') = 0.8 \times 0.69 + 0.1 \times 0.75 + 0.1 \times 0.49 = 0.676\]

서쪽의 기대 미래 보상(0.740)이 북쪽(0.676)보다 상당히 높으므로, 이 상태에서의 최적 행동은 서쪽이다. 실제로는 동서남북 모든 방향에 대해 이 계산을 수행하여 가장 높은 값을 주는 행동을 선택한다.

17.4 가치 반복 (Value Iteration)

가치 반복은 \(V^*\)를 계산하는 반복 알고리즘이다.

17.4.1 알고리즘

1. 모든 상태 \(s\)에 대해 \(V(s) = 0\)으로 초기화한다.
2. 수렴할 때까지 다음을 반복한다:

\[V(s) := R(s) + \max_a \gamma \sum_{s'} P_{sa}(s') \, V(s'), \quad \forall s\]

구현 관점에서 보면, 11차원 벡터를 생성하여 모든 상태의 가치를 저장하고, 벨만 방정식(최적 버전)을 사용하여 이 값들을 반복적으로 갱신한다.

17.4.2 동기식 갱신과 비동기식 갱신

경사 하강법에서와 마찬가지로, 가치 반복에도 두 가지 갱신 방식이 있다.

동기식 갱신(synchronous update): 모든 상태의 오른쪽 값을 먼저 계산한 뒤, 11개 값을 동시에 덮어쓴다. 새로운 추정값을 계산할 때 이전 반복의 값만 사용한다.

\[V_{\text{new}}(s) = B(V_{\text{old}})(s), \quad \forall s\]

여기서 \(B\)는 **벨만 백업 연산자(Bellman backup operator)**라 부른다.

비동기식 갱신(asynchronous update): \(V(1,1)\)을 계산하여 즉시 덮어쓰고, 그 갱신된 값을 사용하여 \(V(1,2)\)를 계산하고, 이를 다시 즉시 덮어쓰는 방식이다. 나중에 갱신하는 상태는 이미 갱신된 최신 값을 사용하게 된다.

가치 반복은 동기식과 비동기식 갱신 모두에서 수렴한다. 행렬 연산을 더 효율적으로 활용할 수 있는 동기식 갱신이 실무에서 더 많이 사용된다.

17.4.3 수렴 성질

가치 반복이 반복적으로 벨만 방정식을 적용하면 \(V\)는 \(V^*\)로 수렴한다. 수렴 속도는 기하급수적(exponentially fast)이다.

• 할인 인자 \(\gamma = 0.99\)이면, 매 반복마다 오차가 \(0.99\)배로 줄어든다. 약 100~수백 회 반복이면 \(V^*\)에 매우 가까워진다.
• 할인 인자 \(\gamma = 0.9\)이면, 10~수십 회 반복만으로 충분하다.

단, 가치 반복은 경사 하강법과 마찬가지로 \(V^*\)에 점근적으로 수렴할 뿐 정확히 \(V^*\)에 도달하지는 않는다. 실용적으로는 이 차이가 문제가 되지 않는다.

17.4.4 흡수 상태의 처리

\(+1\)이나 \(-1\) 보상을 받으면 세계가 종료되는 흡수 상태는 어떻게 표현하는가? 두 가지 방법이 있다:

1. 해당 상태에서 다른 모든 상태로의 전이 확률을 0으로 설정한다. 즉, \(P_{sa}(s') = 0\)으로 둔다.
2. 12번째 상태를 추가하여 항상 자기 자신으로 돌아가며 보상이 0인 상태로 설정한다.

실무에서는 첫 번째 방법이 수학적으로 더 간편하여 주로 사용된다.

17.5 정책 반복 (Policy Iteration)

정책 반복은 MDP를 풀기 위한 또 다른 고전적 알고리즘이다. 가치 반복이 \(V^*\)에 초점을 맞추는 반면, 정책 반복은 정책 \(\pi\) 자체에 초점을 맞춘다.

17.5.1 알고리즘

1. \(\pi\)를 무작위로 초기화한다 (각 상태에 임의의 행동을 배정).
2. 수렴할 때까지 다음 두 단계를 반복한다:
   • *(a) 정책 평가*: 현재 정책 \(\pi\)에 대한 가치 함수 \(V^\pi\)를 계산한다. 이는 벨만 방정식으로부터 얻어지는 연립일차방정식을 풀어서 구한다.
   • *(b) 정책 개선*: \(V^\pi\)를 마치 최적 가치 함수인 것처럼 취급하여 정책을 갱신한다:

\[\pi(s) := \arg\max_a \sum_{s'} P_{sa}(s') \, V^\pi(s'), \quad \forall s\]

가치 반복은 끝까지 \(V^*\)를 풀고 나서 정책을 계산하는 반면, 정책 반복은 매 반복마다 새로운 정책을 계산한다.

17.5.2 가치 반복 vs 정책 반복

정책 반복에서 연립방정식 풀기는 행렬 역행렬 계산에 해당하므로, 상태가 11개면 사실상 순식간에 끝나지만, 100만 개 상태라면 100만 개의 방정식을 풀어야 하므로 상당히 비싸진다.

정책 반복의 또 다른 장점은 유한 번 반복 후 정책이 더 이상 변하지 않는다는 것이다. 정규 방정식이 경사 하강법과 달리 한 단계에 최적해를 구하는 것처럼, 정책 반복은 유한 시간 내에 정확히 최적 정책에 수렴한다. 반면 가치 반복은 경사 하강법처럼 점점 더 가까워질 뿐 정확한 값에는 도달하지 않는다. 다만 이 차이는 학술적 관심사에 가깝고, 실무에서는 큰 문제가 되지 않는다.

실무에서는 상태 공간이 큰 경우가 대부분이므로 가치 반복이 더 많이 사용된다.

17.6 상태 전이 확률의 추정

실제 로봇이나 시스템에서는 상태 전이 확률 \(P_{sa}\)를 사전에 알지 못하는 경우가 많다. 로봇을 만들거나, 헬리콥터를 날리거나, 체스에서 상대와 대국할 때 전이 확률은 미리 주어지지 않으므로 데이터로부터 추정해야 한다.

17.6.1 최대 우도 추정

상태 전이 확률의 자연스러운 추정 방법은 **최대 우도 추정(maximum likelihood estimation)**이다.

\[P_{sa}(s') = \frac{\text{상태 } s \text{에서 행동 } a \text{를 취해 } s' \text{에 도달한 횟수}}{\text{상태 } s \text{에서 행동 } a \text{를 취한 총 횟수}}\]

만약 상태 \(s\)에서 행동 \(a\)를 한 번도 취한 적이 없다면 (분모가 0이면), 일반적인 휴리스틱은 전이 확률을 \(1/|S|\)로 설정하는 것이다. 즉, 어떤 상태로든 균등하게 전이한다고 가정한다.

라플라스 스무딩을 사용할 수도 있다. 분자에 1을 더하고 분모에 \(|S|\)를 더하면 0/0 문제를 피할 수 있다. 그러나 나이브 베이즈와 달리 MDP 풀이기는 확률값이 정확히 0인 것에 민감하지 않으므로, 실무에서 라플라스 스무딩은 잘 사용되지 않는다.

17.6.2 전체 강화 학습 알고리즘

상태 전이 확률을 모르는 상황에서 최적 정책을 찾기 위한 전체 워크플로우는 다음과 같다.

1. 어떤 정책 \(\pi\)에 따라 행동을 취하면서 MDP에서 경험을 수집한다.
2. 관찰된 데이터를 바탕으로 \(P_{sa}\)의 추정치를 갱신한다.
3. 가치 반복(또는 정책 반복)으로 벨만 방정식을 풀어 \(V^*\)를 구하고, 정책 \(\pi\)를 갱신한다.
4. 1~3단계를 반복한다.

이 과정을 반복하면 상태 전이 확률의 추정이 점점 정확해지고, 정책도 점차 개선된다.

보상 함수는 보통 문제의 일부로 주어지지만, 때로는 보상 자체가 확률적일 수 있다. 예를 들어 주식 거래 시스템에서 보상은 특정 날의 수익률이므로 상태만의 결정적 함수가 아니다. 자율주행차가 도로의 움푹 파인 곳을 만날 때도 마찬가지다. 이런 경우에는 각 상태에서의 기대 보상도 함께 추정할 수 있으며, 위 알고리즘의 프레임워크 안에서 자연스럽게 처리된다.

17.7 탐색 대 활용

위에서 설명한 알고리즘에는 한 가지 중요한 문제가 남아 있다. 바로 탐색 대 활용(exploration vs exploitation) 문제다.

17.7.1 문제의 본질

다음과 같은 상황을 생각해보자. 로봇이 출발점에서 오른쪽에 \(+1\) 보상이 있고, 먼 왼쪽 아래에 \(+10\) 보상이 숨겨져 있다. 우연히 로봇이 처음 몇 번의 시행에서 \(+1\) 보상을 찾으면, 앞서 설명한 알고리즘은 \(+1\)로 가는 것이 좋은 전략이라고 판단한다. 매 단계마다 \(-0.02\)의 연료 비용이 있으므로, \(+1\)에 빨리 도달하면 세계가 종료되어 연료 비용도 멈춘다.

이 알고리즘은 **탐욕적(greedy)**이다. 현재 추정된 상태 전이 확률과 보상을 바탕으로 기대 보상을 최대화하는 행동만 취한다. 로봇은 \(+10\) 보상의 존재를 모르기 때문에 왼쪽을 탐색할 동기가 없다. 결과적으로 국소 최적(local optimum)에 수렴하게 된다.

**활용(exploitation)**은 현재 알고 있는 정보를 바탕으로 보상을 최대화하는 행동을 취하는 것이고, **탐색(exploration)**은 당장 최적이 아닌 것처럼 보이는 행동을 취하여 새로운 정보를 얻는 것이다.

이 문제는 학술적 문제만이 아니다. 대형 온라인 광고 플랫폼에서도 동일한 딜레마가 존재한다. 순수한 활용 전략은 사용자가 클릭할 가능성이 가장 높은 광고만 보여주어 단기 수익을 극대화한다. 하지만 탐색 전략을 함께 사용하면, 사용자가 클릭할 가능성이 낮아 보이는 광고도 때때로 보여줌으로써 사용자의 관심사에 대한 새로운 정보를 학습할 수 있다. 이를 통해 장기적으로 더 관련성 높은 광고를 매칭하는 능력을 향상시킬 수 있다.

17.7.2 엡실론 탐욕 탐색 (Epsilon-Greedy Exploration)

탐색 대 활용 문제를 해결하는 간단하고 널리 쓰이는 방법이 엡실론 탐욕(epsilon-greedy) 탐색이다.

• 확률 \(1 - \epsilon\)로 현재 최선이라고 생각되는 정책 \(\pi\)에 따라 행동한다.
• 확률 \(\epsilon\)로 완전히 무작위 행동을 취한다.

예를 들어 \(\epsilon = 0.1\)이면, 90%의 시간에는 현재 최선의 정책을 따르고, 10%의 시간에는 무작위 행동을 한다. 이렇게 하면 가끔씩 우연히 \(+10\) 보상을 발견하게 되어, 상태 공간을 더 철저히 탐색할 수 있다.

(이름이 다소 혼란스러울 수 있다. "엡실론 탐욕"이라고 하면 \(\epsilon\)만큼 탐욕적이라는 뜻 같지만, 실제로는 \(\epsilon\)만큼 무작위로 행동하고 \(1 - \epsilon\)만큼 탐욕적이라는 뜻이다.)

엡실론 탐욕 탐색을 적용하면, 이 알고리즘은 임의의 이산 상태 MDP에 대해 최적 정책으로 수렴한다. 다만 숨겨진 보상을 우연히 발견하는 데 오랜 시간이 걸릴 수 있으므로, 수렴 속도는 문제에 따라 다르다.

17.7.3 볼츠만 탐색

엡실론 탐욕의 대안으로 **볼츠만 탐색(Boltzmann exploration)**이 있다. 완전히 무작위로 행동을 선택하는 대신, 각 행동의 추정 가치에 비례하는 확률로 행동을 선택한다. 예를 들어 북쪽으로 가는 가치가 10이고 남쪽으로 가는 가치가 1이라면, 북쪽을 강하게 선호하되 남쪽으로도 약간의 확률을 부여한다.

\[P(a) \propto e^{V(s') / \tau}\]

여기서 \(\tau\)는 온도(temperature) 파라미터로, 탐색의 정도를 조절한다.

17.7.4 실용적 고려사항

• \(\epsilon\)을 크게 시작하여 점진적으로 줄이는 것이 합리적인 전략이다. 초기에는 많이 탐색하고, 점차 활용에 집중한다.
• 정책을 갱신하기 전에 몇 번의 행동을 취해야 하는지에 대해서는 정해진 규칙이 없다. 가능한 한 자주 갱신하는 것이 성능에 해가 되지 않는다. 실제 로봇의 경우 물리적 제약(예: 헬리콥터를 날리러 나가 하루 종일 데이터를 수집한 뒤 실험실에서 알고리즘을 재실행)이 갱신 주기를 결정하는 경우가 많다.

17.7.5 내재적 동기 (Intrinsic Motivation)

한 가지 흥미로운 연구 방향으로 **내재적 강화 학습(intrinsic reinforcement learning)**이 있다. 에이전트가 이전에 방문하지 않은 새로운 상태에 도달하면 보상을 부여하는 방법이다. 이를 통해 에이전트가 세계에 대한 새로운 것을 발견하도록 동기를 부여한다. "intrinsic motivation"이라는 키워드로 관련 연구를 찾을 수 있다.

17.8 이산 상태 MDP의 한계

지금까지 다룬 내용은 모두 유한 개의 이산 상태를 갖는 MDP에 해당한다. 상태 수가 항상 유한해야 하는지에 대한 질문에 답하면, 지금까지 논의한 프레임워크에서는 그렇다. 그러나 연속 상태 MDP를 다루는 방법도 존재한다. 일반적인 접근법은 연속 상태 공간을 유한 개의 상태로 이산화(discretize)하는 것이며, 연속 상태에 직접 적용되는 가치 반복의 변형도 있다. 이에 대해서는 다음 강의에서 다룬다.

핵심 정리

이전 장: 16장 - 독립 성분 분석과 강화 학습 다음 장: 18장 - 연속 상태 MDP와 모델 시뮬레이션