대부분의 강화 학습 알고리즘은 밸류를 구하는 것에서 출발한다. 그리고 밸류를 구하는 데 뼈대가 되는 수식이 바로 벨만 방정식이다.
이번 챕터에서는 벨만 기대 방정식과 벨만 최적 방정식이라는 두 가지 종류의 방정식을 배울 예정이다.
벨만 기대 방정식 = 주어진 정책 아래에서 상태 가치를 계산하는 방정식
상태 가치 함수에 대한 방정식으로 현재 상태에서 특정 정책 \(\pi\)를 따랐을 때 예상되는 기대 반환값을 나타낸다.
벨만 최적 방정식 = 최적 정책을 찾기 위한 방정식
최적 가치 함수를 계산하는 것이 목표이다.
재귀함수
벨만 방정식은 기본적으로 재귀적 관계에 대한 식이다.
재귀 함수는 자기 자신을 호출하는 함수를 가리킨다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
이 수열의 이름은 피보나치 수열이다. 이 수열은 앞의 두 항을 더해서 그 다음 항이 만들어진다.
일반적인 함수를 이용해 피보나치 수열을 표현하면 다음과 같다.
이런 상황에서는재귀 함수를 이용하면 위의 수열을 쉽게 표현할 수 있다.
fib(n) = fib(n-1) + fib(n-2)
이처럼 재귀 함수는 자기 자신과의 관계를 이용해 자기 자신을 표현한다.
3.1 벨만 기대 방정식
벨만 기대 방정식은 편의상 세 단계로 나눌 수 있다.
단계를 차근차근 알아보자
- 0단계
\(v_{\pi}(s_t) = \mathbb{E}_{\pi}[r_{t+1} + \gamma v_{\pi}(s_{t+1})]\)
수식으로 위의 식을 증명하면 이렇다.
\( \begin{equation} \begin{split} v_{\pi}(s_t) &= \mathbb{E}[G_t] \\ &= \mathbb{E}[r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + ...] \\ &= \mathbb{E}[r_{t+1} + \gamma (r_{t+2} + \gamma r_{t+3} + ...)] \\ &= \mathbb{E}[r_{t+1} + \gamma G_{t+1}] \\ &= \mathbb{E}[r_{t+1} + \gamma v_{\pi}(s_{t+1})] \end{split} \end{equation} \)
말로 풀어 설명하자면 현재 상태 \(s_t\)의 밸류는 리턴의 기댓값인데 이를 쪼개서 생각해보자는 것이다.
리턴이 먼저 한 스텝만큼 진행하여 보상을 받고, 그 다음 상태인 \(s_{t+1}\)부터 미래에 받을 보상을 더해줘도 똑같지 않겠느냐 하는 것이다.
퀴즈로 확인해보자
(1)을 보면 벨만 방정식에서 기댓값 연산자가 빠져있다.
기댓값 연산자가 없어지면 식은 성립되지 않는다. 다음 상태인 \(s_{t+1}\)이 어디가 되느냐에 따라 그 뒤에 값들이 모두 달라지기 때문이다.
다음 상태 \(s_{t+1}\)은 언제 알 수 있을까?
\(s_t\)에서 시작하여 \(s_{t+1}\)이 정해지기까지는 두 번의 확률적인 과정을 거쳐야 한다. ( 1. 정책이 액션을 선택할 때, 2. 액션이 선택되고 나면 전이 확률에 의해 다음 상태가 정해질 때 )
- 1. 첫 번째 동전 던지기는 정책이 액션을 선택할 때 일어난다.
- 해당 확률에 따라 \(a_1\)이 뽑히면 이제 환경에 의한 두 번째 동전 던지기를 한다.
- 2. 두 번째 동전 던지기는 환경이 실행한다.
- 상태 \(s_t\)에서 액션 \(a_t\)를 선택했을 때 다음 상태 \(s_{t+1}\)가 어디가 될지는 전이 확률\(P_{ss'}^a\)에 따라 동전 던지기를 하게 된다.
- \(P_{s_ts_1}^{a_1} = 0.7, P_{s_ts_2}^{a_1} = 0.3, P_{s_ts_3}^{a_2} = 0.5, P_{s_ts_4}^{a_2} = 0.5\)
따라서 위의 퀴즈를 한번 더 설명해보면 강화 학습은 선택된 액션에 의해 다음 상태가 어디가 되는지에 따라 값이 바뀐다. 기댓값 연산자가 여러 번의 확률적 동전 던지기의 과정을 퉁쳐주는 셈이기에 기댓값 연산자가 없다면 식이 성립되지 않는다.
- 1단계
차례대로 살펴보자
1단계 -Ⅰ\(q_\pi\)를 이용해 \(v_\pi\) 계산하기
위의 식을 이해하기 위해 상태 s에서 선택할 수 있는 액션이 \(a_1\)과 \(a_2\) 2개가 있는 상황을 생각해보자.
- 정책 \(\pi\)가 두 액션을 선택할 확률은 각 60%와 40%이다.
- 이때 상태 s의 밸류를 계산하고 싶다.
- 당장 s의 밸류는 모르지만 s에서 \(a_1\)과 \(a_2\)를 선택하는 것의 밸류는 알고 있다고 가정해보자. (= 액션 밸류의 값이 각각 1과 2임을 알고 있다.)
s의 밸류는 계산 가능하다.
\(\begin{equation} \begin{split} v_{\pi}(s) & = \pi(a_1|s) * q_{\pi}(s, a_1) + \pi(a_2|s) * q_{\pi}(s, a_2) \\ & = 0.6 * 1 + 0.4 * 2 \\ & = 1.4 \end{split} \end{equation}\)
- 즉, 어떤 상태에서 선택할 수 있는 모든 액션의 밸류를 모두 알고 있다면 해당 상태의 밸류 계산 가능
- 일반적으로 표현해보자 : \(v_{\pi}(s)=\sum_{a \in A} \pi(a|s) q_{\pi}(s, a)\)
1단계 - Ⅱ \(v_\pi\)를 이용해 \(q_\pi\) 계산하기
이번에는 반대로 해보자. 상태 밸류를 이용해 액션 밸류를 평가할 수 있을까?
전이 확률은 70%와 30%이고 각 상태의 밸류 v(\(s_1\))과 v(\(s_2\))를 알고 있다.
앞과 마찬가지 방법으로 계산할 수 있다.
\(\begin{equation} \begin{split} q_{\pi}(s, a_1) & = r_s^{a_1} + P_{ss_1}^{a_1} * v_{\pi}(s_1) + P_{ss_2}^{a_1} * v_{\pi}(s_2) \\ & = 0.5 + 0.7 * 1.5 + 0.3 * (-1) \\ & = 1.25 \end{split} \end{equation}\)
- 일반적으로 표현해보자 : \(q_{\pi}(s,a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s')\)
- 2단계
지금까지 벨만 기대 방정식의 0단계, 1단계 식을 배웠다.
2단계는 앞서 배웠던 1단계 수식들을 그냥 대입만 하면 된다.
1단계 \(q_\pi\)에 대한 식을 \(v_\pi\)에 대한 식에 대입한다.
반대로 \(v_\pi\)에 대한 식을 \(q_\pi\)에 대한 식에 대입한다.
이렇게 얻은 최종 수식은 각각 다음과 같다. 벨만 기대 방정식 2단계 수식이다.
- \(v_{\pi}(s)\)에 대한 벨만 기대 방정식을 0단계 식과 나란히 써보자.
- 0단계 : \(v_{\pi}(s)=\mathbb{E}_{\pi}[r' + \gamma v_{\pi}(s')]\)
- 2단계 : \(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)\)
0단계 식은 현재 상태의 밸류와 다음 상태의 밸류를 기댓값 연산자를 통해 연결해 놓은 식이다.
그래서 그 기댓값을 어떻게 계산하지?에 대한 대답은 2단계 수식이다.
2단계 수식도 현재 상태의 밸류와 다음 상태의 밸류 사이 연결고리를 나타내며 0단계의 기댓값 연산자를 모두 확률과 밸류의 곱 형태로 풀어서 쓴 형태이다.
- 2단계 식을 계산하기 위해서 다음 2가지를 반드시 알아야 한다.
- 보상 함수 \(r_s^a\) : 각 상태에서 액션을 선택하면 얻는 보상
- 전이 확률 \(P_{ss'}^a\) : 각 상태에서 액션을 선택하면 다음 상태가 어디가 될지에 관한 확률 분포
- 실제로는 대부분의 경우 MDP를 모르기 때문에 경험(experience)을 통해 학습한다.
- 모델 프리(model-free): MDP를 모를 때 학습하는 접근법 -> 0단계 식 사용
- 모델 베이스(model-based): MDP를 알고 있을 때 학습하는 접근법 -> 2단계 식 사용
3.2 벨만 최적 방정식
최적 밸류와 최적 정책에 대해 배우고, 그 관계를 나타내는 벨만 최적 방정식에 대해 알아보자.
최적 밸류와 최적 정책
벨만 기대 방정식이 \(v_\pi\)(s)와 \(q_\pi\)(s,a)에 대한 수식
벨만 최적 방정식은 \(v_*\)(s)와 \(q_*\)(s,a)에 대한 수식이다.
최적 밸류의 정의
\(\begin{equation} \begin{split} v_{*}(s) &= \underset{\pi}{\mathrm{max}} \; v_{\pi}(s) \\ q_{*}(s, a) &= \underset{\pi}{\mathrm{max}} \; q_{\pi}(s, a) \end{split} \end{equation}\)
말로 풀어 설명해보면, 어떤 MDP가 주어졌을 때 그 MDP 안에 존재하는 모든 \(\pi\)들 중에서 가장 좋은 \(\pi\)를 (즉 \(v_\pi\)(s)의 값을 가장 높게 하는) 선택해 계산한 밸류가 곧 최적 밸류 \(v_*\)(s)라는 뜻이다.
상태 \(s_0\)의 최적 밸류 \(v_*\)(\(s_0\))가 어떤 의미를 가지는지 이해해보자.
아이 재우기 MDP에서 무수히 많은 정책 \(\pi\)를 생각해 볼 수 있다.
항상 \(a_0\)를 택한다든지 등의 가능한 정책들의 집합을 \(\pi_1, \pi_2, \pi_3, ..., \pi_\infty \)로 표현한다면 각각의 정책 \(\pi_n\)을 따랐을 때 \(s_0\)의 밸류 \(v_{\pi_n}\)(\(s_0\))을 정의할 수 있다.
이중 238번째 정책 \(\pi_{238}\)의 밸류 \(v_{\pi_{238}}(s_0)\)의 값이 가장 크다고 해보자. 우리는 \(v_*\)(\(s_0\))를 찾은 것이다.
이 과정을 한 줄로 표현하면 \(v_*\)(\(s_0\)) = \(v_{\pi_{238}}\)(\(s_0\)) 즉, 가 된다.
최적 정책의 정의?- 다른 정책을 따를 때보다 최적의 정책 \(\pi_*\)를 따를 때 얻는 보상의 총 합이 가장 크다는 뜻이다.- MDP 내의 모든 \(\pi\)에 대해 \(\pi_*\) > \(\pi\)를 만족하는 \(\pi_*\)가 반드시 존재한다.
최적의 정책만 정의되고 나면 최적 밸류, 최적의 액션 밸류는 다음과 같은 등식이 성립한다.
- 최적의 정책 : \(\pi_*\)
- 최적의 밸류 : \(v_{*}(s) = v_{\pi_{*}}(s)\)
- 최적의 액션 밸류 : \(q_{*}(s, a) = q_{\pi_{*}}(s, a)\)
이제 최적 밸류가 무엇인지, 최적 정책이 무엇인지에 대해 이해가 되었으니 이들 사이 재귀적 관계를 나타내는 벨만 최적 방정식에 대해 알아보자.
벨만 최적 방정식
- 0단계
원래는 주어진\(\pi\)가 있어서 \(\pi\)가 액션을 선택했지만 이제는 모든 액션들 중 max값을 따라야하기 때문에 \(\pi\)가 사라졌다.
- 1단계
1단계 - Ⅰ \(q_*\)를 이용해 \(v_*\) 계산하기
\(v_{*}(s) = \underset{a}{\mathrm{max}} \; q_{*}(s, a)\)
상태 s의 최적 밸류는 s에서 선택할 수 있는 액션들 중에 밸류가 가장 높은 액션의 밸류와 같다는 뜻이다.
상태 s에서 둘 중 가치가 더 높은 액션인 \(a_2\)를 선택하는 것이 최적의 액션이고 그때 s의 최적 밸류인 \(v_*\)(s)는 2이다.
\(\begin{equation} \begin{split} v_{*}(s) &= \underset{a}{\mathrm{max}} \; q_{*}(s, a) \\ &= \mathrm{max}(q_{*}(s, a_1), q_{*}(s, a_2)) \\ &= \mathrm{max}(1, 2) = 2 \end{split} \end{equation}\)
1단계 - Ⅱ \(v_*\)를 이용해 \(q_*\) 계산하기
\(q_{*}(s, a)=r_s^a + \gamma \sum_{s' \in S} P_{ss'}^av_{*}(s')\)
벨만 기대 방정식의 1단계와 같은 구조이다. 원래의 \(\pi\) 자리에 *가 들어갔다는 점이 다르다.
- 2단계
2단계 수식 또한 벨만 기대 방정식 때와 마찬가지로 1단계의 수식 2개를 조합하여 만들 수 있다.
\(v_*\)(s)의 식에 \(q_*\)(s,a)의 식을 대입하면 된다.
반대로 \(q_*\)(s,a)의 식에 \(v_*\)(s)의 식을 대입하면 벨만 최적 방정식 2단계의 두 번째 식을 얻게 된다.
최종 식이다.
이번 챕터에서는 벨만 기대 방정식과 벨만 최적 방정식에 대해 알아보았다.
무언가 정책 \(\pi\)가 주어져 있고, \(\pi\)를 평가하고 싶을 때에는 벨만 기대방정식을 사용한다.
최적의 밸류를 찾는 일을 할 때에는 벨만 최적 방정식을 사용한다.
'바닥부터 배우는 강화 학습' 카테고리의 다른 글
| [ 바닥부터 배우는 강화 학습 ] 05. MDP를 모를 때 밸류 평가하기 (3) | 2024.01.02 |
|---|---|
| [ 바닥부터 배우는 강화 학습 ] 06. MDP를 모를 때 최고의 정책 찾기 (0) | 2023.11.23 |
| [ 바닥부터 배우는 강화 학습 ] 04. MDP를 알 때의 플래닝 (0) | 2023.11.10 |
| [ 바닥부터 배우는 강화 학습 ] 02. 마르코프 결정 프로세스 (0) | 2023.09.28 |
| [ 바닥부터 배우는 강화 학습 ] 01. 강화 학습이란 (0) | 2023.09.18 |
