01. 강화학습
이전 포스팅에서 다이나믹 프로그래밍은 강화학습의 근간이지만 사용하는 방법론은 아니라고 했다. 다이나믹 프로그래밍은 보상 함수와 상태 전이 함수에 근거해 가능한 모든 경우의 수를 '계산'한다. 그러나 강화학습은 가치 함수를 '계산'하지 않고 model-free한 방식으로 작동하여 환경과 에이전트의 상호 작용으로 얻은 상태, 행동, 보상을 하나의 '경험'으로 쌓아 이것에 근거해 가치 함수를 '학습'한다.
사람도 어떤 순간에 선택을 할 때 이후에 일어날 모든 일들을 고려하여 하지 않고, 가장 괜찮아 보이는 것을 일단 해본다. 만약 결과가 좋다면 다음 이 순간에도 이 선택을 하고자 할 것이고, 결과가 나쁘다면 다음에는 이 선택을 하지 않을 것이다. 강화학습도 마찬가지다. 가능한 모든 경우의 수를 고려하지 않고, 일단 어떤 행동을 해본다. 그 결과 (보상)에 따라 행동의 가치를 평가한 뒤, 다음에는 똑같은 상황에서 어떻게 행동할 지 정책을 업데이트한다. 이때 다이나믹 프로그래밍에서 행동의 가치를 평가하는 것인 정책 평가가 강화학습에서는 예측에 대응되고, 평가된 가치를 바탕으로 정책을 발전시키는 것인 정책 발전이 제어에 대응된다.
그렇다면 강화학습의 '일단 해본다'를 통해 어떻게 최적 가치 함수와 최적 정책에 다다를 수 있는지, 몬테 카를로 예측과 시간차 예측을 통해 살펴본다.
02. 몬테 카를로 예측
몬테 카를로 근사는 어떤 값을 구하기 위해 '계산'이 아니라 무수히 많은 '경험'을 통해 그 값에 '근사'한다. 경험, 즉 표본을 많이 많이 모으다 보면 그 평균값이 구하고자 하는 값과 같아진다는 것이다.
몬테 카를로 근사의 대표적인 예시를 들어보자. 면적이 1인 정사각형 종이에 원이 있다고 가정하고, 우리는 원의 넓이를 구하는 방정식이 \(\pi r^2\)이라는 것을 알고 있지만 이를 모른다고 가정하자. 대신에 몬테 카를로 근사를 이용해 원의 넓이를 추정할 것이다. 보라색 점 하나를 종이에 뿌린다. 또 뿌린다. 계속, 무한히 뿌리다 보면 어느새 종이는 보라색 점으로 가득찰 것이다. 이때 원 안에 들어가 있는 점도 있을 것이고 원 밖에 있는 점도 있을 것이다. 이때 원의 면적은 (원 안에 있는 점의 개수 / 종이에 뿌린 전체 점의 개수)로 근사할 수 있다. 만약 점이 무수히 많이 뿌려져 종이를 가득 채웠다면, 이 근사값은 실제 값과 같아질 것이다. 즉, 원의 넓이를 구하는 방정식을 몰라도 원의 넓이에 근사할 수 있다. (여기서 원의 넓이는 강화학습의 참 가치 함수로 이해할 수 있다.)
위 예시에서는 점을 한 번 뿌리는 것이 하나의 경험, 즉 하나의 샘플이다. 강화학습은 한 번의 에피소드가 하나의 샘플이다. 또 하나의 에피소드 내에서는 여러 상태를 거친다. 예를 들어 그리드 월드에서 1번째 에피소드 내에서 (0, 0) -> (1, 0) -> (1, 1) -> (1, 2)...처럼 여러 개의 상태를 거칠 수 있다. 샘플링을 통해 얻은 샘플의 평균으로 참 가치함수를 추정할 때 몬테 카를로 근사를 사용하는 것을 몬테카를로 예측이라고 한다. (아까 예측은 다이나믹 프로그래밍의 정책 평가에 대응하는, 참 가치함수를 구하는 것이라고 했다.)
상태 s가 있다고 해보자. 다이나믹 프로그래밍에서는 상태 s의 가치 함수를 \(v_{\pi}(s) = \sum_{a \in A} \pi(a|s) [r(s, a) + \gamma v_{\pi}(s')]\)라는 식을 통해 '계산'한다. 그러나 우리가 원하는 것은 각 상태에 대한 가치 함수를 어떻게 '계산'하지 않고 '예측'할 것이냐다. 위에서 언급했듯 강화학습에서는 '경험'을 통해 가치 함수를 '예측'한다고 했다. 무수히 많은 에피소드를 진행하면 어떤 상태 s 역시 무수히 많이 거쳐질 것이다. 각 에피소드마다 상태 s에 있을 때의 반환값 \(G_t\), 즉 상태 s에 있을 때 받으리라 기대하는 보상의 총합이 존재한다. $$G_t = R_{t+1} + \gamma R_{t+2} + ...+ \gamma^{T-t+1} R_{T}$$ N번의 에피소드를 진행했다고 하면 상태 s에 대한 반환값 역시 N개가 존재할 것이다. 상태 s의 가치 함수는 N개의 반환값의 평균을 통해 추정할 수 있다.$$v_{\pi}(s) \sim \frac{1}{N} \sum_{i=1}^{N} G_{i}(s)$$ 즉, 상태 s에서 정책 \(\pi\)를 따랐을 때의 가치 함수 \(v_{\pi}(s)\)는 상태 s에서 시작한 N개의 총보상의 평균으로 추정할 수 있다.
위 식을 더 뜯어보자. n번째 에피소드까지 진행했을 때 상태 s에 대한 가치 함수를 \(V_{n+1}\)라고 하자. (n번째 시점에서 행동하면 n+1번째 시점에서 보상을 받기 때문)
$$V_{n+1} = \frac{1}{n} \sum_{i=1}^{n} G_i$$
$$=\frac{1}{n} (G_n + \sum_{i=1}^{n-1} G_i)$$
\[
= \frac{1}{n} \left( G_n + (n-1) \cdot \frac{1}{n-1} \sum_{i=1}^{n-1} G_i \right)
\]
$$=\frac{1}{n} (G_n + (n-1) V_n)$$
$$=\frac{1}{n} (G_n + nV_n - V_n)$$
$$=V_n + \frac{1}{n}(G_n - V_n)$$
즉, n번째 에피소드를 끝냈을 때 상태 s가 가지는 가치 함수 \(V_{n+1}\)은 원래 가치 함수 \(V_n\)에 \(\frac{1}{n}(G_n - V_n)\)를 더함으로써 업데이트한다. 이때 \(\frac{1}{n}\)은 스텝 사이즈로, 상수 \(\alpha\)를 이용해 고정하는 것이 좋다. 스텝 사이즈가 클수록 과거의 반환값보다 현재 에피소드로부터 얻은 반환값을 더 중요하게 본다는 의미다 (\(\alpha\)가 클수록 과거 반환값의 영향이 지수적으로 감소한다). 따라서 몬테 카를로 근사를 이용한 가치 함수 추정 최종식은 아래와 같다. $$V(s) \leftarrow V(s) + \alpha (G(s) - V(s))$$ V(s)의 업데이트의 목표는 G(s)이고 업데이트 크기는 \(\alpha (G(s) - V(s))\)이다. 따라서 \(\alpha\)가 클수록 더 크게 업데이트를 하기 때문에 과거 에피소드의 반환값에서 더 많이 벗어난다는 의미로 해석한다.
몬테 카를로 예측은 한 번의 에피소드가 끝날 때마다 모든 상태의 가치 함수를 업데이트한다. 최종 에피소드까지 수행하고 나면 모든 상태 s에 대해 근사된 참 가치 함수가 구해져 있을 것이다.
03. 시간차 학습
몬테 카를로 예측을 이용해 가치 함수를 업데이트하는 것은 하나의 에피소드가 끝나지 않거나 에피소드의 수가 매우 많을 때 문제가 발생한다. 몬테 카를로 예측은 한 번의 에피소드가 끝나야지 가치 함수를 업데이트할 수 있기 때문이다.
시간차 예측 (Time Difference; TD)은 몬테 카를로 예측과는 다르게 타임 스텝마다 실시간으로 가치 함수를 업데이트한다. 시간차 예측은 몬테 카를로 예측과는 다르게 에피소드가 끝날 때까지의 정보가 필요한 반환값 \(G_t\)를 사용하지 않고 대신에 현재 에이전트가 갖고 있는 \(R_{t+1} + \gamma v_{\pi}(S_{t+1})\)를 사용한다. 즉, 원래 가치 함수는 \(v_{\pi}(s) = E[G_t|S_t = s]\)와 같이 정의하지만 시간차 예측은 가치 함수를 \(v_{\pi}(s) = E[R_{t+1} + \gamma v_{\pi}(s_{t+1})|S_t = s]\)와 같이 정의한다. 이때 \(R_{t+1}\)은 상태 s에서 행동 a를 했을 때 얻을 수 있는 보상이기 때문에 알 수 있고, \(v_{\pi}(s_{t+1})\)은 주변 상태의 가치 함수이기 때문에 마찬가지로 에이전트가 아는 정보다. 따라서 실시간으로 상태 s에 대한 가치 함수를 업데이트할 수 있다. 시간차 학습은 다음과 같이 업데이트된다. $$V(S_t) \leftarrow V(S_t) + \alpha (R_{t+1} + \gamma V(S_{t+1}) - V(S_t))$$ 이때 \(V(S_t)\)의 업데이트 목표는 \(R_{t+1} + \gamma V(S_{t+1})\)이고 \(\alpha (R_{t+1} + \gamma V(S_{t+1}) - V(S_t))\)의 크기로 업데이트된다.
그러나, 여기에서 봐야 할 점은 가치 함수의 업데이트 목표 \(R_{t+1} + \gamma V(S_{t+1})\) 역시 고정값이 아니라 계속 업데이트되는 값이라는 것이다. 즉, 예측해야 하는 값 역시 예측되어야 한다. 이런 방식을 부트스트랩이라고 한다. 즉, 업데이트 목표가 정확하지 않은 상황에서 이를 목표로 가치 함수를 업데이트해야 한다. 불안정해 보이지만 충분히 많은 샘플링을 통해 업데이트하면 참 가치 함수에 근접할 수 있다. 바로 다음 타임 스텝의 정보만 있으면 되기 때문에 가치 함수를 실시간으로 업데이트할 수 있다는 장점이 있지만, 실제값이 아니라 예측값을 사용하기 때문에 초기 설정에 따라 성능이 결정된다는 단점이 있다.
시간차 예측은 한 번의 에피소드 안에서 보상 \(R_{t+1}\)와 다음 상태의 가치 함수 \(V(S_{t+1})\)을 이용해 상태 s의 보상 함수가 실시간으로 업데이트된다. 최종 에피소드까지 수행하고 나면 상태 s에 대한 근사된 참 가치 함수가 구해져 있을 것이다.
04. 살사 (SARSA)
사실 지금까지 배운 방법론 (정책 이터레이션, 가치 이터레이션)은 강화학습이 아니다. 살사부터 강화학습이라고 부른다. 그럼에도 이전의 방법론들은 현재 강화학습의 토대가 되었기 때문에 중요하게 다뤄야 한다.
이전 포스팅에서 GPI (Generalized Policy Iteration)에 대해 간단히 정의했다. GPI란 정책 이터레이션으로, 정책 평가와 정책 발전으로 이루어져 있다. 정책 평가 과정에서 구한 가치 함수가 참 가치 함수에 수렴하지 않아도 정책 발전을 하다 보면 현재 정책을 따랐을 때의 가치 함수는 참 가치 함수로 수렴한다.
GPI를 강화학습의 관점에서 보자. GPI는 정책 평가에서 벨만 기대 방정식을 이용해 가치 함수를 '계산'한다. 강화학습에서는 몬테 카를로 예측이나 시간차 예측을 이용해 '추정'한다. 우리는 시간차 예측에 대해서만 생각할 것이다.
일단 시간차 예측을 통해 현재 상태의 가치 함수를 실시간으로 업데이트한다. 그럼 어떻게 정책을 갱신하는가? 가치 이터레이션에서처럼 별도의 정책을 두지 않고, 그때그때 가장 큰 가치를 지니는 행동을 탐욕적으로 선택한다. 시간차 예측을 통해 가치 함수를 추정하고, 탐욕 정책을 이용하는 것을 합쳐 시간차 제어라고 한다.
탐욕 정책을 이용할 때는 현재 상태에서 가능한 행동들이 가지는 큐함수 중 최대를 선택하도록 정책이 조정된다. $$ \pi(s) = argmax_{a \in A} Q(s, a) $$ 이때의 큐함수 Q(s, a) = r(s, a) + \(\gamma v_{\pi} (s_{t+1})\)는 실제값이 아니라 예측값이므로 대문자로 표현한다.
시간차 제어는 아래 식과 같이 가치 함수가 아니라 큐함수를 업데이트한다. $$ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)) $$
시간차 제어에서 한 번 큐함수를 업데이트할 때 \([S_t, A_t, S_{t+1}, R_{t+1}, A_{t+1}]\)을 하나의 샘플로 사용한다. 에이전트가 상태 \(S_t\)에 있을 때 탐욕 정책에 따라 행동 \(A_t\)를 하면 환경은 에이전트에게 다음 상태 \(S_{t+1}\)과 보상 \(R_{t+1}\)을 준다. 이후 상태 \(S_{t+1}\)에서도 에이전트는 탐욕 정책에 따라 행동 \(A_{t+1}\)을 한다. 이 5가지 요소를 하나의 샘플로 사용하여 큐함수를 업데이트하는 시간차 제어를 살사 (SARSA)라고 한다.
그러나, 살사는 가치 이터레이션과 다르게 모든 경우의 수를 계산하고 알지 못하고 샘플의 축적이라는 경험으로 상황을 판단해야 한다. 따라서 학습 초기에 무조건적으로 탐욕 정책을 따르게 되면 잘못된 학습을 할 수도 있다. 따라서, 살사는 학습 초기에 충분한 '탐험'이 필요하다. 살사는 \(\epsilon\)-탐욕 정책을 이용해 \(\epsilon\)의 확률만큼 에이전트가 랜덤하게, 즉 탐욕적이지 않도록 하여 다양한 경험을 탐험하게 한다.
위 식에 따르면 에이전트는 1-\(\epsilon\)의 확률로 탐욕적으로 행동하고 \(\epsilon\)의 확률로 랜덤하게 행동한다. 학습 초기에는 \(\epsilon\)을 크게 설정해 에이전트에게 충분히 경험하도록 하다가 에피소드가 지날 수록 \(\epsilon\)을 감소시켜 점점 탐욕적으로 행동하게 한다.
정리하자면 살사는 GPI (정책 이터레이션)의 상위 호환 버전이다. GPI의 정책 평가 (상태 s에서의 가치 함수를 계산하는 것)를 큐함수를 이용한 시간차 제어 (실시간으로 상태 s에서 행동 a를 했을 때의 가치를 업데이트)로, 정책 발전 (가장 높은 큐함수를 가지는 행동을 택하도록 정책 갱신)을 \(\epsilon\)-탐욕 정책 (\(\epsilon\)의 확률로 랜덤하게 행동, 아니면 탐욕적으로 행동)으로 대체했다. 또한 GPI (다이나믹 프로그래밍)에서는 모든 상태의 가치 함수를 업데이트했지만 살사는 에이전트가 방문한 상태의 큐함수만을 업데이트한다.
05. 큐러닝 (Q-Learning)
살사는 실시간 업데이트가 가능하고, 모든 상태의 가치 함수를 계산하지 않으며, 충분한 탐험을 가능하게 하지만 역시나 한계가 있다. 예를 들어 보자. 에이전트가 상태 \(s_t\)에 있고 1-\(\epsilon\)의 확률로 에이전트는 탐욕적으로 행동 \(a_t\)를 했다. 에이전트는 보상 \(r_{t+1}\)을 받고 다음 상태 \(s_{t+1}\)에서는 \(\epsilon\)의 확률로 랜덤하게 행동했다. 그런데 그 행동이 낮은 큐함수를 가진다고 해보자. 일단, 5개의 요소가 다 주어졌으니 큐함수 \(Q(s_t, a_t)\)를 한 번 업데이트할 수 있다. 그런데 살사에서는 다음 행동의 큐함수가 현재 행동의 큐함수에 영향을 미치고 이 경우에서는 \(Q(s_{t+1}, a_{t+1}\)이 낮기 때문에 결국 상태 \(s_t\)에서 행동 a의 큐함수가 낮게 업데이트된다. 따라서 이후 에이전트가 똑같은 상태에 오게 되면 '아, 이 상태에서 행동 a를 했을 때의 큐함수가 낮으니까 행동 a를 하면 안되는구나'라고 판단한다. 행동 a는 탐욕 정책을 만족시키는 행동인데도 말이다.
정리하자면, 살사는 현재 행동의 큐함수가 다음 행동의 큐함수에 영향을 받기 때문에 잘못된 방향으로 학습될 수 있다는 한계를 지닌다. 달리 말하면, 살사는 온 폴리시 (On-Policy) 시간차 제어이다. 온 폴리시 제어란 행동 정책과 목표 정책이 같기 때문에 당장 에이전트가 행동하는 대로 목표가 학습된다.
이런 살사의 한계를 극복한 방법론이 바로 오프 폴리시 (Off-Policy) 시간차 제어인 큐러닝이다. 오프 폴리시는 온 폴리시와는 반대로 행동 정책과 목표 정책을 구분하여 학습한다. 에이전트는 행동 정책에 따라 행동하며 탐험하고, 동시에 별도의 목표 정책을 두어 학습은 목표 정책에 따른다.
행동 정책과 목표 정책을 분리한다는 게 무슨 뜻일까? 큐러닝에서도 여전치 \(\epsilon\)-탐욕 정책을 따른다. 에이전트가 상태 \(s_t\)에서 \(\epsilon\)-탐욕 정책에 따라 행동 \(a_t\)를 하고 보상 \(r_{t+1}\)를 받고 다음 상태 \(s_{t+1}\)에 왔다고 해보자. 이때 에이전트가 상태 \(s_{t+1}\)에서 어떤 행동을 하든, 큐함수 업데이트에 사용될 \(Q(s_{t+1}, a_{t+1})\)는 상태 \(s_{t+1}\)에서의 최대값을 사용한다. 즉, 살사와는 다르게 큐러닝은 현재 상태의 큐함수를 계산할 때 다음 상태에서의 행동을 고려하지 않는다. 큐러닝에서 필요한 샘플은 \([S_t, A_t, R_{t+1}, S_{t+1}]\)이다. 즉, 큐러닝에서는 실제 에이전트는 \(\epsilon\)-탐욕 정책이라는 행동 정책을 따라 행동하지만, 실제 학습은 목표 정책인 벨만 최적 방정식에 기반함으로써 행동 정책과 목표 정책을 분리해 에이전트가 잘못된 방향으로 학습되는 것을 방지할 수 있다.
정리하면, 살사는 벨만 기대 방정식을 사용하고 큐러닝은 벨만 최적 방정식을 사용한다고 볼 수 있다. 각각 정책 이터레이션과 가치 이터레이션의 연장선인 셈이다.
06. 정리
- 몬테 카를로 예측: 다이나믹 프로그래밍 (가치 함수를 계산)에서 강화학습 (가치 함수를 평균으로 근사)으로 넘어가는 터닝 포인트이다. 몬테 카를로 예측은 가치 함수, 즉 총보상의 기댓값을 여러 번의 에피소드를 통한 반환값의 평균으로 대체하여 추정한다. 에피소드를 하나 진행하면 에피소드 동안 지나온 상태의 반환값 하나가 나온다. 이 반환값은 하나의 샘플이 되어 나머지 에피소드에서 나온 다른 반환값들과 함께 평균 내어지고, 그럼 상태 s에 대한 가치 함수를 추정할 수 있다.
- 시간차 예측: 그러나 몬테 카를로 예측은 가치 함수의 업데이트가 에피소드와 에피소드 사이에서만 이루어져야 한다는 단점이 존재한다. 이와 다르게 시간차 예측은 한 번의 에피소드 내에서 각 타임 스텝마다 상태 s에 대한 가치 함수를 업데이트한다. 실시간 업데이트가 가능한 이유는 하나의 에피소드가 끝나야 값을 알 수 있는 반환값 \(G_t\) 대신에 \(R_{t+1} + \gamma V(S_{t+1})\)를 업데이트 목표로 두기 때문이다. 업데이트 목표 역시 \(R_{t+1} + \gamma V(S_{t+1})\)로, 정확하지 않은 값이기 때문에 초기 설정에 영향을 크게 받는다는 단점이 있다.
- 살사 (SARSA): 몬테 카를로 예측과 시간차 예측은 가치 함수를 추정하는 방법이었다. 이제 이 추정된 가치 함수를 이용해 정책을 구해야 한다. 업데이트에 가치 함수를 이용하려면 환경의 모델을 알아야 하기 때문에 살사는 가치 함수 대신 큐함수를 업데이트한다. 업데이트에 필요한 샘플은 \([S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}]\)이다.
- 큐러닝 (Q-Learning): 살사는 온 폴리시로, 행동 정책과 목표 정책이 같다. 그러나 큐러닝은 오프 폴리시로, 에이전트는 행동 정책인 \(\epsilon\)-탐욕 정책에 따라 행동하지만 학습은 탐욕적인 목표 정책에 의해 이루어진다. 살사와 다른 점은, 살사는 다음 상태에서의 행동을 업데이트에 고려하는 반면 큐러닝은 다음 상태에서 어떤 행동을 하든 다음 상태에서의 최대 큐함수를 이용해 업데이트한다는 것이다.
07. 퀴즈
- 강화학습과 GPI의 구성을 설명하시오. - 강화학습은 예측과 제어로, GPI는 정책 평가와 정책 발전으로 이루어져 있다.
- 몬테 카를로 방법에서 발생하는 편향과 오류는 무엇인가? - 몬테 카를로 예측에서의 가치 함수 업데이트는 에피소드와 에피소드 사이에서만 일어난다. 에피소드가 무한히 길다면 비효율적이다.
- 몬테 카를로 기법에서 샘플을 쌓는 방법은 무엇인가? - 몬테 카를로 예측에서는 한 번의 에피소드가 하나의 샘플이다.
- 몬테 카를로, SARSA, 큐러닝을 비교해 설명하시오. - 몬테 카를로 예측은 가치 함수의 업데이트 목표가 반환값 \(G_t\)이기 때문에 한 번의 에피소드가 끝난 이후에야 가치 함수의 업데이트가 가능하다. SARSA와 큐러닝은 가치 함수가 아닌 큐함수를 업데이트한다. SARSA는 벨만 기대 방정식의 연장선으로, 다음 상태의 행동을 업데이트에 이용한다. 그러나 큐러닝은 벨만 최적 방정식의 연장선으로, 다음 상태의 행동이 무엇이든 다음 상태에서의 최대의 큐함수를 이용한다.
- 왜 스텝 사이즈를 상수로 고정해야 하는가? - 스텝 사이즈를 고정한다는 것은 과거의 반환값보다 현재의 반환값을 더 중요하게 여긴다는 의미다. 또한 스텝 사이즈가 크다는 것은 그만큼 과거의 반환값을 지수적으로 감소시킨다는 의미다.
- \(\epsilon\)-탐욕 정책에 대해 설명하시오. - SARSA와 큐러닝은 모두 \(\epsilon\)-탐욕 정책을 이용한다. 에이전트는 \(\epsilon\)의 확률로 랜덤하게 행동하고 1-\(\epsilon\)의 확률로 탐욕적으로 행동한다.
'RL' 카테고리의 다른 글
| 강화학습: 정리 (0) | 2025.02.21 |
|---|---|
| 강화학습: DQN (0) | 2025.02.21 |
| 강화학습: 가치 그래디언트 (딥살사)와 정책 그레디언트 (REINFORCE 알고리즘) (0) | 2025.02.20 |
| 강화학습: 다이나믹 프로그래밍으로 최적 정책 구하기 (0) | 2025.02.18 |
| 강화학습: 강화학습이란? (0) | 2025.02.17 |