ai theory

강화학습 기초 (6) - Monte Carlo Prediction

Junyoung Park · 2024-04-19 · 6 min

들어가며...

앞 글의 Dynamic Programming은 MDP의 Transition probability와 Reward function을 알고 있다고 가정했다.

Pss′a,Rsa\mathcal{P}_{ss'}^a, \qquad \mathcal{R}_s^a

이 Model을 알면 현재 State에서 가능한 모든 Next State를 확률로 평균내 Bellman backup을 수행할 수 있다.

하지만 처음 해보는 Game이나 현실의 Robot에서는 “이 Action을 하면 다음 State가 될 확률”을 미리 알기 어렵다. Environment를 직접 경험하기 전까지 Transition matrix를 채울 수 없다.

Monte Carlo 방법은 여기서 상당히 솔직한 전략을 사용한다.

Model을 모르면 Episode를 실제로 끝까지 해보고, 받은 Return으로 Value를 고친다.

주사위의 각 면이 나올 확률을 모를 때 주사위를 여러 번 던져 평균을 내는 것과 비슷하다. 가능한 모든 결과의 확률을 계산하는 대신, 실제 Sample을 모아서 Expectation을 근사한다.

이번 글에서는 정해진 Policy π\pi의 Value를 경험으로 추정하는 Monte Carlo Prediction을 살펴본다.

Prediction과 Control을 먼저 구분하기

강화학습에서 Prediction은 정해진 Policy가 얼마나 좋은지 평가하는 문제다.

Prediction: given π, estimate vπ\text{Prediction: given } \pi, \text{ estimate } v_\pi

Control은 좋은 Policy 자체를 찾는 문제다.

Control: find π∗\text{Control: find } \pi_*

이번 글의 Monte Carlo Prediction에서는 Policy를 바꾸지 않는다. Policy π\pi로 여러 Episode를 실행하면서 각 State에서 얻은 Return을 관찰하고 vπ(s)v_\pi(s)를 추정한다.

평가와 개선을 한꺼번에 시작하면 수식이 어디를 고치는지 헷갈리기 쉽다. 우선 고정된 행동 습관의 성적표를 만드는 것부터 시작하는 셈이다.

Value의 Expectation을 경험의 평균으로 바꾸기

State value의 정의는 다음과 같다.

vπ(s)=Eπ[Gt∣St=s]v_\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t=s \right]

Expectation을 정확히 계산하려면 가능한 모든 경로의 확률을 알아야 한다. Monte Carlo는 State ss에서 실제로 관찰한 Return들을 모아 평균낸다.

V(s)=1N(s)∑i=1N(s)G(i)(s)V(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G^{(i)}(s)
  • N(s)N(s): State ss를 평가에 사용한 횟수
  • G(i)(s)G^{(i)}(s): ii번째 Sample에서 State ss 이후 얻은 Return
  • V(s)V(s): 경험으로 추정한 Value

Sample이 충분히 많아지면 경험 평균 V(s)V(s)가 실제 기대값 vπ(s)v_\pi(s)에 가까워진다.

Episode가 끝나야 Return을 알 수 있다

다음과 같은 짧은 Episode를 생각해보자.

S0→+1S1→−1S2→+5TerminalS_0 \xrightarrow{+1} S_1 \xrightarrow{-1} S_2 \xrightarrow{+5} \text{Terminal}

γ=0.9\gamma=0.9라고 하자. Episode가 끝난 뒤 마지막 State부터 거꾸로 Return을 계산한다.

G2=5G_2=5 G1=−1+0.9×5=3.5G_1=-1+0.9\times5=3.5 G0=1+0.9×3.5=4.15G_0=1+0.9\times3.5=4.15
Monte Carlo는 Terminal에 도착한 뒤 실제 Reward를 뒤에서부터 정산한다.

S0S_0에서 바로 받은 Reward는 +1+1이지만 Return은 4.154.15다. 이후에 받은 −1-1과 +5+5까지 포함되었기 때문이다.

이제 S0S_0의 Value 추정값을 G0=4.15G_0=4.15 쪽으로, S1S_1은 G1=3.5G_1=3.5 쪽으로 고친다.

평균을 다시 계산하지 않는 Incremental update

Return이 하나 추가될 때마다 지금까지의 모든 Return을 다시 더할 필요는 없다. 평균은 다음 식으로 조금씩 업데이트할 수 있다.

V(St)←V(St)+1N(St)[Gt−V(St)]V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)} \left[ G_t-V(S_t) \right]

괄호 안의

Gt−V(St)G_t-V(S_t)

는 이번에 관찰한 Return과 기존 예상의 차이다.

예를 들어 V(S0)=3V(S_0)=3이고 이번 Return이 G0=4.15G_0=4.15, 지금까지 방문 횟수가 N(S0)=5N(S_0)=5라면,

V(S0)←3+15(4.15−3)=3.23\begin{aligned} V(S_0) &\leftarrow 3 + \frac{1}{5}(4.15-3) \\ &= 3.23 \end{aligned}

기존 예상 33에서 새 관찰 4.154.15 쪽으로 전체 거리의 1/51/5만큼 이동했다.

방문 횟수 대신 고정된 Learning rate α\alpha를 사용할 수도 있다.

V(St)←V(St)+α[Gt−V(St)]V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t-V(S_t) \right]

고정된 α\alpha는 오래된 경험을 완전히 같은 비중으로 유지하지 않고 최근 경험에 계속 일정한 비중을 준다. 환경이 시간에 따라 바뀌는 Non-stationary 문제에서 유용하다.

First-Visit와 Every-Visit

한 Episode 안에서 같은 State를 여러 번 방문할 수 있다.

A→B→A→C→A→TerminalA \rightarrow B \rightarrow A \rightarrow C \rightarrow A \rightarrow \text{Terminal}

이때 어느 방문의 Return을 사용할지에 따라 두 방법으로 나뉜다.

First-Visit는 Episode의 첫 방문만, Every-Visit는 모든 방문을 별도 Sample로 사용한다.

First-Visit Monte Carlo

한 Episode에서 State AA가 처음 등장한 시점의 Return만 사용한다. 위 Episode에서는 첫 번째 AA만 Update한다.

Every-Visit Monte Carlo

State AA가 등장한 모든 시점의 Return을 사용한다. 같은 Episode 안의 세 AA가 각각 다른 남은 미래를 가지므로 세 번 Update한다.

두 방법 모두 충분한 조건 아래 vπ(s)v_\pi(s)로 수렴한다. 처음 공부할 때는 이름을 외우기보다 “한 Episode 안에서 같은 State가 반복되면 어떤 방문을 셀 것인가?”에 대한 선택이라고 이해하면 된다.

Monte Carlo는 Bootstrapping하지 않는다

Monte Carlo의 Target은 실제 Return GtG_t다.

MC target=Gt\text{MC target}=G_t

Target 안에 현재의 Value 추정값 VV가 들어 있지 않다. 이런 방식을 Bootstrapping하지 않는다고 말한다.

Bootstrapping은 아직 실제로 확인하지 않은 미래 일부를 현재의 추정값으로 대신하는 것이다. Monte Carlo는 끝까지 기다려 실제 Reward sequence를 모두 확인하므로 추정값을 Target에 빌리지 않는다.

이 특징에는 장단점이 함께 있다.

장점

  • Transition과 Reward Model이 필요 없다.
  • 현재 Value 추정이 틀렸더라도 Target에 그 오차를 직접 재사용하지 않는다.
  • 실제 Episode의 Return이라는 이해하기 쉬운 Target을 사용한다.

단점

  • Episode가 끝날 때까지 기다려야 한다.
  • 끝나지 않는 Continuing task에는 그대로 적용하기 어렵다.
  • Return이 많은 Action, Transition, Reward의 우연에 영향을 받아 Variance가 클 수 있다.

같은 State에서도 Return이 크게 흔들릴 수 있다

같은 State ss에서 시작한 다섯 Episode의 Return이 다음과 같다고 하자.

10,  −4,  7,  0,  1210,\;-4,\;7,\;0,\;12

평균은 55다.

V(s)=10−4+7+0+125=5V(s)=\frac{10-4+7+0+12}{5}=5

하지만 Sample 하나하나는 −4-4부터 1212까지 크게 흔들린다. Policy가 확률적으로 Action을 고르고 Environment도 확률적으로 움직이면 전체 Episode의 우연이 Return에 모두 쌓인다.

Monte Carlo는 이 흔들리는 Return을 여러 번 평균내 Value를 찾는다. 편향되지 않은 실제 Return을 쓰지만, 한 번의 Update가 noisy할 수 있다는 뜻이다.

뒤에서 살펴볼 TD는 Episode 전체 대신 한 Step의 Reward와 Next State Value만 사용한다. 실제 미래를 덜 보는 대신 Variance를 줄이고 즉시 Update할 수 있다.

Monte Carlo Prediction의 순서

알고리즘의 흐름을 문장으로 적으면 다음과 같다.

  1. V(s)V(s)와 방문 횟수 N(s)N(s)를 초기화한다.
  2. Policy π\pi를 따라 Episode 하나를 끝까지 생성한다.
  3. Terminal에서 시작해 각 시점의 Return GtG_t를 계산한다.
  4. First-Visit 또는 Every-Visit 기준으로 사용할 방문을 고른다.
  5. V(St)V(S_t)를 GtG_t 쪽으로 Update한다.
  6. 여러 Episode에서 반복한다.

여기서 중요한 점은 2번에서 Policy를 개선하지 않는다는 것이다. 현재는 Policy Evaluation만 수행한다.

Action value Q(s,a)Q(s,a)도 같은 방식으로 학습할 수 있다. State 방문 대신 State-Action pair의 방문을 세고 그 시점의 Return을 평균낸다.

Q(St,At)←Q(St,At)+α[Gt−Q(St,At)]Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ G_t-Q(S_t,A_t) \right]

이 Q값으로 Policy를 ϵ\epsilon-greedy하게 개선하면 Monte Carlo Control로 이어진다. 다만 이 시리즈에서는 Control을 TD 방식인 SARSA와 Q-Learning에서 자세히 다룬다.

이번 글에서 기억할 것

이번 글의 핵심은 다음과 같다.

Monte Carlo Prediction은 Episode가 끝난 뒤 실제 Return을 Sample로 사용해 Policy의 Value를 추정한다.

조금 더 나누면 다음과 같다.

  1. Model을 몰라도 Policy를 따라 생성한 경험으로 Value를 학습한다.
  2. vπ(s)v_\pi(s)의 Expectation을 관찰된 Return의 평균으로 근사한다.
  3. Target은 실제 Return GtG_t다.
  4. First-Visit는 Episode의 첫 방문만, Every-Visit는 모든 방문을 사용한다.
  5. Bootstrapping하지 않으며 Episode 종료를 기다려야 한다.
  6. 실제 Return을 사용하지만 Variance가 클 수 있다.

다음 글에서는 “Episode가 끝날 때까지 꼭 기다려야 할까?”라는 질문에서 시작한다. Temporal-Difference Learning은 Next State의 Value 추정을 빌려 한 Step마다 즉시 Update한다.

참고 자료