우선순위 경험 재생

우선순위 경험 재생

재생 메모리에서 경험을 무작위로 고르게 뽑던 DQN의 방식을 바꿔, "배울 것이 많은" 경험(TD 오차가 큰 경험)을 더 자주 다시 보게 한 논문입니다. 확률적 우선순위와 중요도 샘플링 보정으로 부작용을 막았고, 학습 속도를 약 두 배로 높이며 아타리에서 당시 최고 성적을 냈습니다.

들어가기 전에

이 해설은 아래 내용을 안다고 보고 씁니다. 처음이라면 먼저 읽고 오면 수식과 손계산을 훨씬 쉽게 따라올 수 있습니다.

• 딥 강화학습으로 사람 수준의 제어 (DQN, Nature 판) — 목표 네트워크를 더한 DQN으로 아타리 49개 게임에서 사람 수준에 다가선 Nature 논문

한눈에 보기

• 경험 재생에서 "무엇을 다시 볼지"를 고르는 기준으로 TD 오차의 크기를 쓰는 이유를 이해합니다.
• 오차가 큰 것만 고르는 탐욕적 방식의 문제와, 이를 푸는 확률적 우선순위(비례 방식 · 순위 방식)를 손계산으로 확인합니다.
• 뽑는 확률을 바꾸면 왜 학습이 치우치는지, 중요도 샘플링 가중치로 어떻게 바로잡는지 압니다.
• 큰 메모리에서도 빠르게 뽑는 자료구조(합 트리, 이진 힙)와 아타리 결과를 압니다.

초록 (번역)

경험 재생은 온라인 강화학습 에이전트가 과거의 경험을 기억하고 다시 쓸 수 있게 해 줍니다. 이전 연구에서는 경험 전이(transition)를 재생 메모리에서 균등하게 무작위로 뽑았습니다. 그러나 이 방식은 경험의 중요도와 상관없이, 원래 겪은 빈도 그대로 전이를 재생할 뿐입니다. 이 논문에서는 경험에 우선순위를 매겨 중요한 전이를 더 자주 재생하고, 그래서 더 효율적으로 배우는 틀을 개발합니다. 우선순위 경험 재생을 여러 아타리 게임에서 사람 수준 성능을 달성한 강화학습 알고리즘인 심층 Q-네트워크(DQN)에 적용합니다. 우선순위 경험 재생을 쓴 DQN은 49개 게임 중 41개에서 균등 재생을 쓴 DQN을 앞서며 새로운 최고 성능을 달성합니다.

무엇을 풀었나

온라인 강화학습 에이전트는 가장 단순한 형태에서 경험을 한 번 쓰고 바로 버립니다. 그러면 (가) 연속된 갱신끼리 상관이 강하고, (나) 드물지만 나중에 쓸모 있을 경험을 빨리 잊습니다. 경험 재생은 경험을 메모리에 쌓아 섞어 쓰는 방식으로 두 문제를 풀었습니다. DQN은 큰 슬라이딩 윈도 메모리에서 균등하게 뽑았고, 전이 하나를 평균 여덟 번 다시 봤습니다.

남은 문제는 모든 경험을 똑같이 대한다는 점입니다. 어떤 전이는 놀랍고(예측과 크게 다름), 어떤 전이는 이미 다 배운 뻔한 것입니다. 균등 재생은 겪은 빈도 그대로 다시 보므로, 드문 성공 경험이 수많은 실패 경험 속에 묻힙니다.

논문은 이를 보여 주는 '눈먼 절벽 걷기(Blind Cliffwalk)' 환경을 만들었습니다. 상태 $n$개를 따라 매번 '맞는' 행동을 해야 끝에서 보상 1을 받고, '틀린' 행동을 하면 즉시 끝납니다. 무작위 행동으로 보상에 닿을 확률은 $2^{-n}$입니다. 학습 순서를 잘 고르는 가상의 '오라클'은 균등 재생보다 지수적으로 빠르게 배웠습니다. 이 큰 격차가 "실제로 쓸 수 있는 좋은 재생 순서"를 찾게 한 동기입니다.

핵심 아이디어

1234567flowchart LR
  A[새 경험] -->|최대 우선순위로 저장| B[(재생 메모리 + 우선순위)]
  B --> C[확률 P i ∝ p_i^α 로 미니배치 뽑기]
  C --> D[TD 오차 δ 계산 · Double DQN 목표]
  D --> E[중요도 가중치 w_i로 기울기 보정]
  E --> F[Q-네트워크 갱신]
  D -->|δ 크기로 우선순위 갱신| B

1. 무엇이 "중요한" 경험인가: TD 오차

직관: 문제집을 복습할 때, 이미 맞힌 문제보다 틀린 문제를 다시 보는 게 효율적입니다. "얼마나 틀렸나"가 우선순위가 됩니다.

단계:

1. 이상적인 기준은 "이 경험에서 지금 얼마나 배울 수 있나(기대 학습 진전)"지만 직접 잴 수 없습니다.
2. 대신 TD 오차의 크기 $|\delta|$를 씁니다. 지금 가치 추정이 한 단계 뒤의 부트스트랩 추정과 얼마나 다른지, 즉 "얼마나 놀라운 경험인가"입니다.
3. Q-러닝 · SARSA는 어차피 TD 오차를 계산하므로 추가 비용이 거의 없습니다.

Double DQN 기준으로 전이 $j$의 TD 오차(논문 알고리즘 1의 표기를 따름):

주의: 보상에 잡음이 많으면 TD 오차가 '배울 수 없는 무작위성'까지 반영해 좋은 기준이 아닐 수 있다고 논문이 직접 적습니다(부록에서 대안 논의).

2. 탐욕적 우선순위의 문제 → 확률적 우선순위

가장 단순한 방법은 매번 $|\delta|$가 가장 큰 전이를 뽑는 것(탐욕적 우선순위)입니다. 새 전이는 아직 오차를 모르므로 최대 우선순위로 넣어 적어도 한 번은 보게 합니다. 눈먼 절벽 걷기에서는 이것만으로도 크게 빨라졌지만, 문제가 세 가지 있습니다.

1. 다시 본 전이의 오차만 갱신되므로, 처음에 오차가 작았던 전이는 오래(슬라이딩 윈도 메모리에서는 사실상 영원히) 안 뽑힙니다.
2. 보상이 확률적일 때 생기는 잡음 튀는 값에 민감합니다.
3. 오차가 큰 소수의 전이만 반복해 다양성이 떨어지고 과적합되기 쉽습니다.

직관: 틀린 문제를 더 자주 보되, 맞힌 문제도 가끔은 섞어 봅니다. 순수 탐욕과 균등 추출 사이를 오가는 손잡이를 둡니다.

우선순위 $p_i$를 정하는 두 방식이 있습니다.

• 비례 방식(proportional): $p_i = |\delta_i| + \epsilon$. 작은 양수 $\epsilon$은 오차가 0이 된 전이도 다시 볼 기회를 남깁니다.
• 순위 방식(rank-based): $p_i = 1/\text{rank}(i)$. $\text{rank}(i)$는 $|\delta|$ 크기순으로 정렬했을 때의 순위입니다. 이러면 $P$는 지수 $\alpha$인 거듭제곱 분포가 되고, 오차의 절대 크기에 휘둘리지 않아 이상값에 강할 것으로 기대했습니다.

숫자로 해 보기(해설용 예): 메모리에 전이 3개, $|\delta| = [2,\ 1,\ 0.5]$라 합시다($\epsilon$은 무시).

• 균등 추출: 각각 $1/3 \approx 0.333$.
• 비례 방식, $\alpha = 0.5$: $p^\alpha = [1.414,\ 1,\ 0.707]$, 합 3.121 → $P = [0.453,\ 0.320,\ 0.227]$.
• 순위 방식, $\alpha = 0.7$: $p = [1,\ 1/2,\ 1/3]$ → $p^\alpha \approx [1,\ 0.616,\ 0.463]$, 합 2.079 → $P \approx [0.481,\ 0.296,\ 0.223]$. 오차가 큰 전이를 더 자주 보지만, 가장 작은 전이도 0이 아닌 확률로 뽑힙니다.

3. 치우침 바로잡기: 중요도 샘플링 가중치

직관: 설문조사에서 특정 집단을 일부러 많이 뽑았다면, 결과를 낼 때 그 집단의 응답 비중을 낮춰야 전체를 공정하게 대표합니다.

단계:

1. 확률적 갱신은 "기댓값과 같은 분포에서 뽑았다"는 가정에 기대는데, 우선순위 추출은 이 분포를 바꿔 수렴하는 답 자체를 바꿉니다(편향).
2. 많이 뽑힌 전이의 갱신은 줄이고, 적게 뽑힌 전이의 갱신은 키우는 가중치를 곱합니다.
3. 안정성을 위해 가중치를 최댓값으로 나눠, 갱신을 줄이는 방향으로만 조정합니다.
4. 기울기에 $\delta_i$ 대신 $w_i \delta_i$를 씁니다.

왜 $\beta$를 점점 키우나: 강화학습은 정책 · 상태 분포 · 부트스트랩 목표가 계속 바뀌어 원래 비정상적이므로, 편향이 없어야 하는 것은 주로 학습 막바지(수렴 근처)라고 봤습니다. 그래서 $\beta$를 초기값에서 시작해 학습이 끝날 때 1이 되도록 선형으로 늘립니다.

또 하나의 이점: 오차가 큰 전이를 여러 번 보되 가중치로 한 번의 걸음을 줄여 주므로, 심층 신경망처럼 매우 비선형인 손실 지형에서 큰 걸음이 학습을 망치는 일을 줄여 줍니다.

숫자로 해 보기(위 비례 방식 예에 이어서): $N=3$, $\beta=1$이면 $w = 1/(3P) \approx [0.736,\ 1.042,\ 1.468]$, 최댓값으로 나누면 $\approx [0.50,\ 0.71,\ 1.0]$입니다. 가장 자주 뽑히는 전이(오차 2)는 갱신이 절반으로 줄고, 가장 드물게 뽑히는 전이는 그대로입니다.

4. 큰 메모리에서 빠르게 뽑기

메모리가 100만 개($10^6$) 전이일 때도 뽑는 비용이 메모리 크기에 비례하면 안 됩니다.

• 비례 방식: '합 트리(sum-tree)'를 씁니다. 잎에는 우선순위를, 각 부모 노드에는 자식들의 합을 둡니다. 루트가 전체 합 $p_{\text{total}}$이고, 갱신 · 추출이 $O(\log N)$입니다. 미니배치 $k$개를 뽑을 때는 $[0, p_{\text{total}}]$을 $k$등분하고 각 구간에서 하나씩 뽑습니다.
• 순위 방식: 누적 분포를 확률이 같은 $k$개 구간의 계단 함수로 근사하고, 구간마다 하나씩 뽑습니다(층화 추출). 미니배치에 오차가 큰 것 · 중간 · 작은 것이 고르게 섞입니다. 정렬 상태는 배열 기반 이진 힙으로 근사하고 $10^6$단계마다 한 번 정렬했으며, 실행 시간은 2~4% 늘었습니다.

왜 새 전이를 최대 우선순위로 넣나: 오차를 아직 모르는 새 경험을 적어도 한 번은 보게 하려는 것입니다. 논문은 분석 중에 균등 재생에서는 방문한 전이 일부가 한 번도 재생되지 못한 채 메모리에서 밀려나고, 많은 전이가 한참 뒤에야 처음 재생된다는 점을 발견했는데, 이 보너스가 그 문제를 직접 고칩니다.

결과

설정: 기준선은 Nature DQN과 조정된 Double DQN입니다. 메모리는 최근 $10^6$개 전이, 미니배치 32, 새 전이 4개마다 미니배치 갱신 1번(평균 8번 재생), 보상과 TD 오차는 $[-1, 1]$로 자릅니다. 신경망 · 알고리즘 · 평가는 기준선과 같고 뽑는 방식만 바꿨습니다. 오차가 큰 전이를 자주 뽑아 기울기가 커지므로 학습률만 4분의 1로 줄였습니다. 8개 게임에서 대략적인 격자 탐색으로 순위 방식은 $\alpha = 0.7$, $\beta_0 = 0.5$, 비례 방식은 $\alpha = 0.6$, $\beta_0 = 0.4$를 골랐습니다.

평가: 사람 플레이 궤적에서 뽑은 시작점, 30분 게임 시간, 100번 평가의 평균 점수를 정규화 점수(무작위 0%, 사람 100%)로 나타냈습니다.

(논문 표 1을 요약한 표입니다.)

• DQN에 더했을 때: 49개 중 41개 게임에서 크게 나아졌고, 중앙값이 48%에서 106%로 올랐습니다.
• Double DQN과 상호 보완: Double DQN 위에 얹어도 더 좋아져, 리버 레이드 · 시퀘스트 · 서라운드가 처음으로 사람 수준에 올랐습니다. 평균은 비디오 핀볼 한 게임이 크게 좌우하므로 믿을 만한 지표가 아니라고 논문이 덧붙입니다.
• 학습 속도: 전체적으로 약 두 배 빨라졌습니다. Double DQN의 중앙값 최고 성능에 도달하는 시점이 순위 방식은 전체 학습 시간의 47%, 비례 방식은 38%였습니다.
• 두 방식 비교: 순위 방식이 더 견고할 것으로 예상했지만 실제로는 비슷했습니다. 저자들은 DQN이 보상과 TD 오차를 이미 잘라 이상값이 없어졌기 때문으로 짐작합니다. 다만 게임에 따라 한쪽만 크게 좋아지는 경우가 있었습니다.
• 지도학습 실험: 숫자 0~4의 학습 표본을 99% 지운 불균형 MNIST에서도 우선순위 추출이 도움이 됐습니다.

왜 중요한가 · 이후 영향

• 재생 버퍼의 기본 옵션: 우선순위 재생은 이후 DQN 계열의 표준 부품이 됐고, 듀얼링 DQN과 합쳐 당시 최고 기록을 냈으며, Rainbow의 구성 요소가 됐습니다.
• "데이터를 고르는 것도 학습이다": 무엇을 다시 볼지 고르는 문제는 지도학습의 어려운 표본 위주 학습, 불균형 데이터 재표본 추출과 같은 줄기입니다. 논문도 이 연결을 직접 실험했습니다.
• 신경과학과의 연결: 쥐의 해마에서 보상과 관련된 경험, TD 오차가 큰 경험이 더 자주 재생된다는 연구를 근거로 듭니다. Nature DQN 논문이 결론에서 제안한 "중요한 사건 쪽으로 치우친 재생"을 구체화한 셈입니다.
• 개발자 관점: 합 트리 · 층화 추출 · 가중치 정규화처럼 대규모 버퍼를 다루는 구현 요령이 함께 정리돼 있어, 실무 구현의 참고서 역할도 합니다.

한계 · 주의할 점

• TD 오차는 대리 지표입니다. 확률적 보상이나 부분 관측처럼 "배울 수 없는" 오차가 큰 전이를 과대평가할 수 있습니다.
• 오래된 우선순위: 우선순위는 다시 볼 때만 갱신되므로, 목표 신경망이 바뀌면 저장된 우선순위가 금방 낡습니다.
• 하이퍼파라미터가 늘어납니다. $\alpha$, $\beta$와 그 일정, 학습률 조정이 필요하고, $\alpha$를 키우면 $\beta$도 함께 조정해야 합니다.
• 다른 요령과의 상호작용: 듀얼링 논문이 지적했듯 우선순위 재생은 기울기 자르기 등과 미묘하게 얽힙니다.
• 편향 보정은 완전하지 않습니다. 학습 대부분 동안 $\beta < 1$이라 치우침을 일부만 보정합니다.

이어서 읽을 것

• 앞: 딥 강화학습으로 아타리 게임하기 (DQN) — 논문 스스로 "중요한 전이를 더 자주 뽑는 방식"을 과제로 남김 · Double DQN
• 함께: 듀얼링 네트워크 구조 (Dueling DQN)
• 뒤: Rainbow: DQN 개선 기법 결합
• 배경: 강화학습 입문 8.4절 우선순위 스위핑(prioritized sweeping)

용어 정리

스스로 점검

1. TD 오차가 가장 큰 전이만 계속 뽑으면 어떤 문제가 생기나?

   처음에 오차가 작았던 전이는 거의 다시 뽑히지 않고, 잡음에 민감해지며, 소수의 전이만 반복해 다양성이 떨어지고 과적합되기 쉽습니다.

2. 우선순위로 뽑으면 왜 중요도 샘플링 보정이 필요한가?

   뽑는 분포가 경험이 실제로 일어난 분포와 달라져, 갱신의 기댓값이 바뀌고 수렴하는 답이 치우치기 때문입니다. 가중치 $w_i$로 자주 뽑힌 전이의 영향을 줄여 바로잡습니다.

3. $\alpha = 0$, $\beta = 1$이면 어떻게 되나?

   $\alpha = 0$이면 모든 전이의 확률이 같아 균등 재생이 되고, 이때 모든 가중치도 같아져 보정의 효과가 없습니다. 즉 원래 DQN의 재생과 같습니다.

다음에 볼 것

이 글을 이해했다면 이어서 보면 좋은 항목입니다.

• Rainbow: DQN 개선 기법 결합 — DQN 개선 6가지를 한데 합친 Rainbow — 아타리 57게임 최고, 핵심은 우선순위 재생 · 다단계

출처

• 원문: arxiv.org/abs/1511.05952 (2015 · Tom Schaul 외)