Introduction
- 3장에서는 다이나믹 프로그래밍(Dynamic Programming)을 이용한 Planning에 대하여 알아보았습니다.
- Planning이란 모델(Model)을 알고있을 경우 어떤 행동(Action)을 취하는데 있어 좋은 보상(Reward)을 얻게끔 정책(Policy)를 수정하여 최적 정책을 도출하는 것입니다.
- 모델(Model)을 알고 있다는 것은 MDP를 알고 있다는 것으로 Model-based라고 표현합니다. MDP는 환경에 대한 Model이고 에이전트가 환경(Environment)으로부터 제공 받는 정보인 보상(Reward)과 상태전이확률($ P_{ss'}^a $, 상태 $s$에서 행동 $a$를 했을때 상태 $s'$으로 이동할 확률)에 대하여 알고 있다는 것을 의미합니다.
- 4장에서는 MDP를 모르는 경우인 Model-free한 상황에서의 문제를 다루며, 구체적으로는 Prediction에 대하여 알아보겠습니다.
- MDP를 모르는 경우란 앞서 말했듯이 환경의 모델에 해당하는 보상과 상태전이확률을 모른다는 뜻입니다.
- 즉, 에이전트가 어떤 상태에서 어떤 행동을 했을때 얻게 되는 값에 대한 정확한 값을 알수 없어 예측(추론)을 해야합니다.
- 예측(Prediction)은 MDP를 알수없는 상태에서 가치 함수의 값을 예측하는 것을 의미합니다. 즉, 어떤 상태에서 어떤 행동을 했을때 예상되는 가치 함수의 값을 추론합니다.
- 4장에서는 Model-free prediction의 하나인 MC와 TD에 대하여 알아보겠습니다.
- 5장에서는 MDP를 모르는 경우인 Model-free한 상황에서 정책을 학습 시키는 방법인 Control에 대하여 알아보겠습니다.
[정리]
- MDP를 아는 경우 : Model-based
- MDP를 모르는 경우 (보상과 상태전이확률을 모르는 경우) : Model-free
- Prediction : Model-free에서 가치 함수 값을 예측하는 것
- Control : Model-free에서 정책을 학습 시키는 방법
Monte-Carlo Learning (MC)
- 몬테카를로(Monte-Carlo,MC)란?
정의 : 반복된 무작위 추출(repeated random sampling)을 이용하여 함수의 값을 수리적으로 근사하는 알고리즘
(위키백과 : 몬테카를로 방법)
- 즉, 직접 구하기 어려운 값을 여러번의 반복된 행위를 통하여 얻게된 실제값을 바탕으로 추론하는 것을 의미합니다.
- 예를 들어, 아래의 그림과 같이 다각형의 면적을 구하는 문제에서 실제 면적값을 계산하기 어려운 경우 일정한 행동(잉크를 떨어트리는 행동)을 반복하여 다각형의 면적을 추정할 수 있습니다.
- 강화학습에서는 몬테카를로(MC)를 이용하여 보상을 추론하여 가치함수를 예측하는데 사용합니다.
- MC는 에피소드의 경험으로부터 직접적으로 학습을 합니다.
- MC는 상태변환확률(transitions)과 보상(rewards)값을 알 수 없는 model-free(MDP를 모를때)에서 사용합니다.
- MC는 완전히 종료된 에피소드로부터 학습을 합니다.
몬테카를로 정책 평가(Monte-Carlo Policy Evaluation)
[목표] 정책( $\pi$)을 따르는 에피소드의 경험으로부터 가치함수($v_{\pi}$)를 학습한다.
- 가치함수를 학습하기 위해서 반환값에 대하여 상기시켜 보겠습니다. 반환값은 아래 수식과 같습니다.
- $G_{t} = R_{t+1} + \gamma R_{t+2} + \cdot\cdot\cdot+\gamma ^{T-1}R_{T}$
- 가치함수는 어떤 상태에서 예상되는 반환값의 기댓값이었습니다.
- $v_\pi(s) = E_\pi[G_t|S_t=s]$
- 몬테카를로 정책 평가에서는 기댓값(expected return) 대신 empricial mean(경험적인 평균)을 사용합니다. 즉, 여러번 반복실행하여 얻게된 실제 반환값들의 평균을 사용합니다.
First-Visit / Every-Visit Monte Carlo Policy Evaluation
- 몬테카를로 정책 평가에는 어떤 상태에 대하여 첫번째 방문만 고려하는 방법(First-visit)과 에피소드에서 발생한 모든 방문(Every-visit)을 모두 고려하는 방법이 있습니다.
- 두 방법의 차이는 First-visit은 에피소드에서 어떤 상태($s$)에 대하여 첫번째 방문한 경우만 계산을 하는 것이고, Every-visit은 에피소드에서 어떤 상태($s$)에 대하여 여러번 방문한 경우를 모두 계산에 포함하는 것입니다.
- 방법은 다음과 같습니다.
- 상태($s$)를 평가하기 위하여 에피소드 내에서 상태($s$)에 방문 한 경우를 고려한다.
- 상태($s$)에 방문했을시 방문 횟수($N(s)$)를 추가합니다. $N(s) \leftarrow N(s)+1$
- 반환값 합계를 업데이트 합니다. ($S(s)$는 상태($s$)에서의 반환값 합계) $S(s) \leftarrow S(s)+G_{t}$
- 가치는 경험에 의하여 얻게된 총 반환값 합계를 방문횟수로 나눈 평균으로 간주합니다. $V(s) = S(s)/V(s)$
- $N(s)$가 커질수록 가치값은 실제값에 근접하게 됩니다. $V(s) \rightarrow V_{\pi}(s)$ as $N(s) \rightarrow \infty$
MC Policy Evaluation 예시 : 블랙잭
- 몬테카를로를 적용한 정책 평가에 대한 예시로 블랙잭을 들어보겠습니다.
- 블랙잭은 카드의 합계가 21에 가까운 사람이 이기는 게임으로 최초 2장의 카드를 받습니다. 플레이어의 행동은 카드를 계속 받거나 멈추거나 두가지의 선택지가 있습니다. 행동에 따른 보상은 아래 그림(좌측)과 같습니다.
- 문제를 쉽게하기 위하여 받은 카드가 12보다 작으면 무조건 카드를 받는것으로 상태변화확률(Transition)을 적용하여 현재의 합계는 12-21사이가 되겠습니다.
- 정책을 카드의 합계가 20이상일때에만 더이상 카드를 받지않고(stick) 그 외의 경우에는 카드를 받도록(twist) 정책을 설정했을때 상태에 따른 가치함수의 값은 위 그림 우측과 같습니다.
- 카드의 합계가 20이하일 경우에는 무조건 카드를 받기 때문에 카드의 합계가 21일 경우를 제외하고는 딜러에게 질수 밖에 없습니다.
- 따라서, 50만번의 에피소드가 진행된 후의 가치함수를 살펴보면 상태가12~20($S_{12}~S_{20})의 가치함수는 -1인 것을 알 수 있습니다.
- 에피소드가 진행됨에 따른 경과를 보면 10,000번의 에피소드(좌측)에서는 가치함수가 울퉁불퉁하여 일정값에 수렴하지 않은 것을 알수 있으나 500,000번의 에피소드(우측)가 진행되었을때에는 가치함수의 값이 수렴한 것을 알 수 있습니다.
- 이처럼 MC기반 정책 평가는 반복 시행의 결과를 토대로 실제 가치함수 값을 추정합니다.
Incremental Monte-Carlo Update
- 몬테 카를로 업데이트를 위해서 Incremental(증분) 방법을 적용합니다.
- Incremental이란 일정 시간과 단위로 수치 등을 ‘증가시켜’간다라는 의미(출처 : 컴퓨터인터넷IT용어대사전)입니다.
- Incremental Mean은 이전 평균값($\mu_{k-1}$)을 알고있을 때, 새로운 값($x_{k}$)이 들어왔을때 이전의 모든값($x_1,x_2,\cdot\cdot\cdot,x_{k-1}$)을 이용하지 않고, $\mu_{k-1}$만을 이용하여 새로운 평균($\mu_{k}$)를 도출하는 방법입니다. 세부적인 공식은 아래와 같습니다.
- $ \mu_{k} = \frac{1}{k}\sum_{j=1}^kx_j $
- $\mu_{k} = \frac{1}{k}\left(x_k+\sum_{j=1}^{k-1}x_j\right)$
- $\mu_{k} = \frac{1}{k}(x_k+(k-1)\mu_{k-1})$
- $\mu_{k} = \mu_{k-1} + \frac{1}{k}(x_k-\mu_{k-1})$
- Incremental을 Monte-Carlo에 적용하면 다음과 같이 식을 변형할 수 있습니다.
- $N(S_t) \leftarrow N(S_t) + 1$
- $V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)}(G_t-V(S_t))$
- 강화학습에선 에피소드마다 정책이 업데이트되어 바뀌는 경우를 Non-stationary (시점에 따라 달라지는 데이터, 확률분포가 시간에 따라 일정하지 않은 데이터)라고 할 수 있고 이 경우에는 $1/N(S_t)$ 대신에 $\alpha$를 적용할 수 있습니다.
- $V(S_t) \leftarrow V(S_t) + \alpha(G_t-V(S_t))$
- 가중치를 $1/N(S_t)$로 놓을경우 $N(S_t)$가 커짐에 따라 0으로 수렴하기 때문에 나중에 얻은 값과 처음에 얻은 값을 동등하게 고려합니다.
- 반면, $\alpha$로 가중치를 놓을 경우 나중에 얻은 값의 가중치가 더 크게 고려됩니다.
Temporal-Difference Learning (TD)
- TD 방식은 에피소드의 경험으로부터 직접적으로 학습합니다.
- TD 방식은 model-free(MDP를 모르는 경우)에서 사용합니다.
- TD방식은 MC와 다르게 종료되지않은(incomplete) 에피소드에 적용이 가능합니다. (부트스트랩 방식)
- 부트스트랩(bootstrapping)이란 사전적으론 “현재 상황에서 일단 어떻게든 한다!”의 의미로 강화학습에선 현재 가지고 있는 결과값을 이용하여 다른 정보를 추론하는데 사용하는 방법이라 할 수 있다.
- MC에서는 한 에피소드가 모두 종료되고 종료 후에 얻은 반환값을 통하여 가치함수를 업데이트 했다면, TD에서는 에피소드가 종료되지 않은 상태에서 얻은 보상값을 이용하여 가치함수를 업데이트 합니다. 즉, ‘현재 상황에서 사용 가능한 정보(=얻은 보상값)를 이용하여 가치함수를 일단 업데이트 한다.’ 라고 할수 있습니다.
- 추측(a guess)으로 추측(a guess)을 업데이트 한다고 정리하는 방법이 되겠습니다.
[목표] : 가치함수($V_{\pi}$)를 현재의 정책($\pi$)을 적용하여 얻은 경험으로부터 실시간(online)으로 업데이트
- Every-visit MC 적용시 : $V(S_t) \leftarrow V(S_t) + \alpha(G_t-V(S_t))$
- 에피소드가 종료되야 얻을수 있는 반환값($G_t$)이 있어야 업데이트가 가능
- TD(0) 적용시
- 반환값($G_t$)대신 실시간 얻을 수 있는 값인 ($R_{t+1}+\gamma V(S_{t+1})$)을 사용합니다.
- 이때 $G_t$를 actural return(실제 반환값)이라 하고 $R_{t+1}+\gamma V(S_{t+1})$를 estimate return(추정 반환값)이라 합니다.
- 따라서, 가치함수는 다음 공식과 같이 업데이트 할 수 있습니다.
- $ V(S_t) \leftarrow V(S_t) + \alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t))$
- 여기서 $R_{t+1}+\gamma V(S_{t+1})$를 TD target이라 부릅니다.
- $\delta_{t} = R_{t+1}+\gamma V(S_{t+1})-V(S_t)$라 하고 $\delta_{t}$를 TD error라고 합니다.
- 반환값($G_t$)대신 실시간 얻을 수 있는 값인 ($R_{t+1}+\gamma V(S_{t+1})$)을 사용합니다.
Driving Home Example
- MC와 TD를 비교하기 위하여 예제를 하나 살펴보겠습니다.
- 사무실에서 집으로 가는 차가 있다고 생각해보겠습니다.
- 문제에서 상태는 사무실, 자동차, 고속도로 등 현재 에이전트(퇴근하는 사람)의 위치가 상태($S$)가 되겠습니다.
- 예상소요시간은 현재 에이전트(퇴근하는 사람)가 집까지 도착하는데 걸릴거라 예상되는 총 시간을 의미합니다. 사무실에서는 30분이면 집에 도착할 것이라 예상했고, 고속도로를 이동하는 중에 트럭 뒤에서는 10분정도 걸리면 집에 도착할것이라 예상했습니다.
- 소모시간은 현재 상태까지 오기위해 소모된 시간을 의미합니다. 고속도로 상태에 있기 위해서는 사무실과 자동차 상태를 거쳤고 5+15=20분의 시간이 소모된 것을 알 수 있습니다.
- 도착 예상시간은 현재 상태까지 오기까지 소모된 소모시간과 현 상태에서부터 목적지(집)까지 예상되는 시간을 더한 값이 되겠습니다.
- 예를들어 자동차에 탑승한 자동차 상태에서는 사무실에서 출발했을때부터 40분 후면 도착할것으로 예상한 것이 되겠습니다.
- 도착 예상시간을 가치함수 $V(s)$로 설정하겠습니다.
- 우선 MC를 적용했을 때를 알아보겠습니다. (그림 Driving Home Example #2 좌측)
- $\alpha=1$로 적용하면 $V(S_{t}) = V(S_t) + (G_t-V(S_t)) = G_t$가 됩니다.
- 현재 에피소드에서 반환값($G_t$)는 집에 도착하기 위해 소모된 시간인 43이 $G_t$가 됩니다.
- 따라서, 학습을 하게되면 모든 상태에서 도착 예상시간이 43분이 됩니다.
- 다음으로 TD(0)을 적용해보겠습니다. (그림 Driving Home Example #2 우측)
- $\alpha, \gamma=1$로 적용하면 $V(S_{t}) = V(S_t) + (R_{t+1}+V(S_{t+1} -V(S_t)) = R_{t+1}+V(S_{t+1})$가 됩니다.
- 보상은 집에 도착하기 전까지 0으로 가정한다면 $V(S_{t}) = V(S_{t+1})$이 됩니다.
- 한 step 씩 살펴보면 다음과 같이 $V(S_{t})$가 업데이트 되는 것을 알 수 있습니다.
- TD의 경우 에피소드가 종료되지 않아도 한 step당 해당하는 상태가치함수($V(s)$)를 업데이트 할 수 있습니다.
- MC와 TD의 결과를 그래프로 나타내면 아래와 같습니다.
- MC의 경우 1 에피소드에 43으로 모두 수렴하였지만, TD의 경우 각자 다른 값으로 업데이트 됨을 알수있습니다.
MC와 TD의 장단점
| 구분 | MC | TD |
| 장점 | 편향이 없다. (high variance, zero bias) - 우수한 수렴성을 갖는다. - 초기값에 민감하지 않다. - 이해 및 사용이 쉽다. 마르코프 특성(Markov Property)를 사용하지 않는다. - non-Markov 환경에서 더욱 효과적이다. |
최종 산물(final outcome)이 나오기 전에 학습이 가능하다. - 에피소드가 종료되기 전에 학습이 가능 - 연속적인 환경(종료가 없는, non-terminating)에서 학습이 가능하다. 일반적으로 MC보다 효율적이다. 마르코프 특성(Markov Property)를 사용한다. - Markov 환경에서 효과적이다. |
| 단점 | 최종산물이 나온후에 학습이 가능하다. - 에피소드가 종료되기 전까지 기다려야 한다. - 에피소드 형태(종료가 되는, terminating) 환경에서만 적용 가능하다. |
편향이 있다. (low variance, some bias) - 초기값에 민감하다. |
- MC는 반환값(return, $ G_{t}$)을 학습에 사용합니다. 반환값은 많은 수의 행동, 상태변환확률, 보상을 포함하고 있습니다. 따라서, 편향성이 적고 실제값에 가까울 확률이 높습니다. 따라서 MC는 편향이 없고 분산이 큰 경향이 있습니다.
- 반면, TD의 경우 TD target값($R_{t+1}+\gamma V(S_{t+1})$) 을 사용하는데 TD target은 하나의 랜덤한 행동, 상태변환확률, 보상을 포함하고 있기 때문에 분산(variance)은 작으나 수집된 값에 따른 편향성이 존재합니다.
TD($\lambda$)
n-Step Return
- 위의 TD에서는 다음 상태에서의 가치함수($V(S_{t+1})$)만 고려했습니다. 그러나, 더 뒤의 상태까지도 고려할 수 있습니다. 우리는 $n=1$인 상황만 살펴봤는데 뒤의 상태까지 고려(n-step returns을 고려)한다면 다음과 같이 수식으로 표현할 수 있습니다.
- $n=1$ : $G_{t}^{(1)} = R_{t+1}+\gamma V(S_{t+1})$ (TD)
- $n=2$ : $G_{t}^{(2)} = R_{t+1}+\gamma R_{t+2} +\gamma^2 V(S_{t+2})$
- $n=\infty$ : $G_{t}^{(2)} = R_{t+1}+\gamma R_{t+2} \cdot\cdot\cdot+\gamma^{T-1} R_{T}$ (MC)
- $n$에 따라 TD와 MC로 나눌수 있고 n-step TD learning은 다음 수식과 같이 표현할 수 있습니다.
- $G_{t}^{(n)} = R_{t+1}+\gamma R_{t+2} \cdot\cdot\cdot+\gamma^{n-1} R_{t+n}+\gamma^{n}V(S_{t+n})$
- $V(S_t) \leftarrow V(S_t)+\alpha (G_{t}^{(n)}-V(S_t))$
$\lambda$-return
- n-Step Return에서 한발 더 나아가, 등비수열의 합 공식을 이용하여 뒤의 상태에 대한 가중치를 줄여 나가는 방식으로 학습을 조정할 수 있습니다. 이를 TD($\lambda$)라고 하고 이때 반환값은 아래 수식과 같이 표현할 수 있습니다.
- $G_t^{\lambda} = (1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_t^{(n)}$
- 아래 우측 그림과 같이 현재 상태에서 멀어질수록 가중치의 값이 작아집니다. 가중치의 합은 1이 됩니다.
- $\lambda = 0$일때는 다음 상태에 대한 값만 업데이트 되기 때문에 TD(0)와 동일합니다.
- 반면, $\lambda = 1$일때는 모든 상태에 대한 보상값이 필요하기 때문에 에피소드가 종료되어야만 측정이 가능하고 그 값은 MC와 동일합니다.
정리(Summary)
- Model-free prediction에 대하여 살펴보았습니다. Model-free란 말은 MDP를 모르는 경우에 해당되었으며, prediction은 가치함수를 추정하는 것을 의미했습니다.
- Model-free prediction의 대표적인 방법으로는 몬테카를로(MC)와 시간차예측(TD)가 있었습니다.
- MC의 경우 에피소드가 종료되고 얻게 되는 반환값($G_t$)을 이용하여 업데이트를 실시하기 때문에 offline 업데이트 방식이었습니다.
- 반면, TD의 경우 일정한 스텝을 진행하였을 때 얻은 보상과 다음 상태에서의 상태가치함수를 이용한 TD target($R_{t+1}+\gamma V(S_{t+1})$)을 이용하여 실시간(online)으로 업데이트 하는 방식입니다.
- TD($\lambda$)는 TD방식의 하나로 업데이트에 가중치를 부여하여 효율적으로 업데이트를 실시하는 방법으로 $\lambda=0$이면 TD(0)와 같고, $\lambda=1$이면, MC와 동일합니다.
※ 해당 내용은 David Silver 교수님의 Introduction to Reinforcement Learning 강의를 기반으로 강화학습에 대하여 정리한 자료입니다.
- 강의 영상(Lecture) : https://www.youtube.com/watch?v=2pWv7GOvuf0&list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ
- 강의 슬라이드(Slide) : https://www.davidsilver.uk/teaching/
댓글