← all posts
AI 2026.05.03 · 12 min read Advanced

Monte Carlo RL은 왜 두 가지 방문 방식을 갖는가

First-visit과 every-visit의 bias 차이부터 off-policy importance sampling의 분산 폭발까지, MC 계열 알고리즘이 공유하는 하나의 긴장을 추적한다.

📚 Model Free Rl Deep Dive 2 / 7
  1. 01 Model-Free RL의 네 가지 근본 질문
  2. 02 Monte Carlo RL은 왜 두 가지 방문 방식을 갖는가
  3. 03 TD Learning은 왜 MC와 DP 사이에 서 있는가
  4. 04 Q-Learning 수렴 증명의 통일된 구조
  5. 05 n-step Return에서 TD(λ)까지: 하나의 스펙트럼
  6. 06 Actor-Critic은 왜 두 역할로 나뉘는가
  7. 07 Model-Free RL의 수렴은 왜 이렇게 까다로운가

Monte Carlo RL의 핵심 아이디어는 단순하다 — episode를 끝까지 굴려 얻은 실제 return GtG_t로 value를 추정한다. 그런데 이 단순한 원칙 위에서 five가지 알고리즘(first-visit, every-visit, MC control with ES, ϵ\epsilon-soft, off-policy IS)이 서로 다른 선택을 한다. 그 선택들을 관통하는 공통 긴장은 무엇인가?

출발점: return의 sample mean

Value function의 정의는 기대값이다.

Vπ(s)=Eπ[Gt∣St=s]V^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]

추정 전략은 뻔하다 — 많은 episode에서 ss를 방문할 때마다 return GtG_t를 모아 평균을 낸다. Law of Large Numbers에 의해 이 평균은 Vπ(s)V^\pi(s)로 수렴한다.

문제는 “방문할 때마다”라는 부분에서 생긴다. 하나의 episode 안에서 같은 state를 여러 번 지날 수 있다. 그 방문들을 모두 쓸 것인가, 첫 번째만 쓸 것인가.

First-visit vs Every-visit — unbiased와 asymptotically unbiased의 차이

First-visit MC는 각 episode에서 state ss의 첫 번째 방문 T(s,n)=min⁡{t:St(n)=s}T(s,n) = \min\{t : S_t^{(n)} = s\}의 return만 수집한다.

V^NFV(s)=1N(s)∑n: s∈τnGT(s,n)(n)\hat{V}_N^{\text{FV}}(s) = \frac{1}{N(s)} \sum_{n:\, s \in \tau_n} G_{T(s,n)}^{(n)}

서로 다른 episode들은 독립이므로, 수집된 return들은 i.i.d.다. LLN이 직접 적용되고, 각 sample은 즉시 unbiased다.

Every-visit MC는 같은 episode 내의 모든 방문 {t:St(n)=s}\{t : S_t^{(n)} = s\}에서 return을 수집한다. Sample 수는 늘어나지만, 같은 episode 안의 return들은 trajectory를 공유하므로 상관성이 생긴다.

명제 1 · Every-visit intra-episode correlation

같은 episode (n)(n)에서 t<t′t < t'일 때, 두 방문의 return은 다음과 같이 상관된다.

ρ(Gt(n), Gt′(n))≈γ2(t′−t)\rho(G_t^{(n)},\, G_{t'}^{(n)}) \approx \gamma^{2(t'-t)}
▷ 증명

Gt(n)G_t^{(n)}과 Gt′(n)G_{t'}^{(n)}은 t′t' 이후의 reward를 공유한다. 공유 부분의 크기는 γt′−t\gamma^{t'-t}로 감쇠하므로, covariance의 지배항은 γ2(t′−t)⋅Var(Gt′)\gamma^{2(t'-t)} \cdot \text{Var}(G_{t'})가 된다. 따라서 correlation은 거리 t′−tt'-t에 대해 기하급수적으로 감소한다. □\square

∎

이 상관성 때문에 every-visit은 LLN을 직접 적용할 수 없다. Singh & Sutton (1996)의 Lemma 2–3은 ergodic theorem을 경유해 극한에서 수렴을 보장하지만, 각 sample이 즉시 unbiased라고는 말할 수 없다 — asymptotically unbiased에 그친다.

실무에서는 every-visit이 더 빠르다. Correlation factor보다 sample 수의 증가가 수렴 속도를 지배하기 때문이다.

수렴 속도 — O(1/N)O(1/\sqrt{N})과 그 함의

i.i.d. 가정 하에 CLT를 적용하면,

N(V^N−Vπ)→dN(0, σ2(s))\sqrt{N}\bigl(\hat{V}_N - V^\pi\bigr) \xrightarrow{d} \mathcal{N}(0,\, \sigma^2(s))

여기서 σ2(s)=Var(Gt∣St=s)\sigma^2(s) = \text{Var}(G_t \mid S_t = s)는 return의 분산이다. 표준오차 σ/N\sigma/\sqrt{N}은 정확도 ϵ\epsilon을 반으로 줄이려면 episode를 4배 더 필요로 한다는 뜻이다. Return 분산이 크면 — 예를 들어 long-horizon task나 γ≈1\gamma \approx 1인 환경 — 수렴이 극도로 느려진다.

Bounded return Gt∈[a,b]G_t \in [a, b]라면 Hoeffding 부등식이 distribution-free 보장을 준다.

P ⁣(∣V^N−Vπ∣>ϵ)≤2exp⁡ ⁣(−2Nϵ2(b−a)2)P\!\left(|\hat{V}_N - V^\pi| > \epsilon\right) \leq 2\exp\!\left(-\frac{2N\epsilon^2}{(b-a)^2}\right)

CLT 기반 신뢰구간보다 훨씬 느슨하지만, return 분포를 모를 때의 안전한 선택이다.

Control로의 확장 — Exploring Starts의 이상과 현실

Value 추정에서 policy 최적화로 넘어가면, 문제가 하나 추가된다. Greedy policy는 deterministic하므로, 선택받지 못한 action의 Qπ(s,a)Q^\pi(s, a)를 영원히 추정할 수 없다.

**Exploring Starts(ES)**는 각 episode를 균등 분포에서 뽑은 (s0,a0)(s_0, a_0)로 시작해 모든 state-action pair의 무한 방문을 보장한다. 이 조건 아래 MC control은 Q^k→Q∗\hat{Q}_k \to Q^*, πk→π∗\pi_k \to \pi^*를 a.s. 보장한다.

⚠ Exploring Starts의 비현실성

환경을 임의의 state에서 시작하도록 제어할 수 없는 경우 — 로봇, 위험 환경, 실세계 시스템 — ES는 적용 불가능하다. 이 가정을 완화하는 것이 ϵ\epsilon-soft 계열의 출발점이다.

ϵ\epsilon-greedy policy는 policy 자체에 exploration을 내장한다.

πeg(a∣s)={1−ϵ+ϵ/∣A∣a=arg⁡max⁡aQ(s,a)ϵ/∣A∣otherwise\pi_{\text{eg}}(a|s) = \begin{cases} 1 - \epsilon + \epsilon/|\mathcal{A}| & a = \arg\max_a Q(s,a) \\ \epsilon/|\mathcal{A}| & \text{otherwise} \end{cases}

ϵ>0\epsilon > 0이 유지되는 한 모든 (s,a)(s,a)의 방문이 보장되고, GPI 단계마다 value가 단조 증가한다. 단, 고정 ϵ\epsilon이면 수렴점은 πϵ∗\pi^*_\epsilon — unrestricted optimal π∗\pi^*가 아니다. ϵk→0\epsilon_k \to 0 스케줄을 쓰면 π∗\pi^*에 접근하지만, exploration-exploitation 균형을 직접 설계해야 한다.

Off-Policy IS — bias와 variance의 새로운 긴장

On-policy의 한계는 behavior policy와 target policy가 같아야 한다는 것이다. Off-policy는 데이터를 생성한 policy bb와 평가하려는 policy π\pi를 분리한다.

ρt:T−1=∏k=tT−1π(ak∣sk)b(ak∣sk)\rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(a_k|s_k)}{b(a_k|s_k)}

이 importance ratio를 return에 곱하면 분포의 차이를 보정할 수 있다.

**Ordinary IS(OIS)**는 V^OIS=1N∑nρnGn\hat{V}^{\text{OIS}} = \frac{1}{N}\sum_n \rho_n G_n으로 정의되며 unbiased다. 그러나 π\pi와 bb가 멀수록 ρ\rho의 분산이 폭발한다 — bb가 잘 탐험하지 않는 행동을 π\pi가 선호할수록 ρ≫1\rho \gg 1인 outlier가 추정값을 흔든다.

**Weighted IS(WIS)**는 ρ\rho를 정규화해 분산을 억제한다.

V^WIS=∑nρnGn∑nρn\hat{V}^{\text{WIS}} = \frac{\sum_n \rho_n G_n}{\sum_n \rho_n}

각 sample은 biased하지만, N→∞N \to \infty에서 a.s. 수렴한다. 현대 Deep RL의 PPO가 쓰는 clipped IS ratio는 이 아이디어의 직접적 계승이다.

트레이드오프

다섯 가지 알고리즘이 공유하는 하나의 긴장은 탐험의 비용을 누가 어디서 부담하는가다.

방법탐험 보장최적성주요 비용
First-visit MC없음 (평가만)VπV^\pi 수렴높은 분산
MC ES외부 제어π∗\pi^*비현실적 가정
ϵ\epsilon-softpolicy 내장πϵ∗\pi^*_\epsilonexploration 비용, ϵ\epsilon 설계
Off-policy OISbehavior policyVπV^\pi 또는 Q∗Q^*분산 폭발
Off-policy WISbehavior policyasymptotic편향, coverage 필요
✎ 분산 vs 편향

MC 계열 전반에서 unbiasedness를 고집할수록 분산이 올라가고, 분산을 낮추려 하면 편향이 끼어든다. First-visit이 every-visit보다 깔끔하고, OIS가 WIS보다 정확하지만, 실무에서 더 자주 선택되는 것은 always 후자다.

정리

  • First-visit MC는 i.i.d. sample을 이용한 unbiased 추정이고, every-visit MC는 correlated sample을 활용해 더 빠르게 수렴하지만 asymptotically unbiased에 그친다.
  • 수렴 속도는 O(1/N)O(1/\sqrt{N})이며, return 분산 σ2(s)\sigma^2(s)이 병목이다 — variance가 큰 task는 episode를 기하급수적으로 더 필요로 한다.
  • Exploring Starts는 이론적으로 π∗\pi^*를 보장하지만 비현실적이고, ϵ\epsilon-greedy는 현실적이지만 optimal에서 ϵ\epsilon만큼 떨어진 정책에 수렴한다.
  • Off-policy IS는 OIS(unbiased, 고분산)와 WIS(biased, 저분산)의 트레이드오프로 귀결된다 — 이 긴장은 다음 장의 TD learning에서 bootstrap이라는 전혀 다른 방식으로 해소된다.
REF
# reinforcement-learning # monte-carlo # importance-sampling # policy-iteration