Q러닝

최적설계 게임 개발 소프트웨어 마지막 수정: 2026-07-27 04:38:52

1. 개요[편집]

Q러닝 Q-learning
제안	Chris Watkins (1989), 수렴 증명 1992
계열	모형 프리 · 가치 기반 · 오프폴리시
학습 대상	행동가치 Q(s, a)
온폴리시 짝	SARSA
대표 확장	DQN, 이중 Q러닝, 분포형 Q학습

나쁜 짓을 실컷 하면서도 착한 정책을 배울 수 있다. 그것도 증명까지 있다.

Q러닝(Q-learning)은 환경의 전이확률 $P$ 와 보상함수 $R$ 을 전혀 모르는 상태에서, 경험한 전이 $(s, a, r, s')$ 만으로 최적 행동가치함수 $Q^{*}(s,a)$ 를 직접 추정하는 오프폴리시 시간차 학습 알고리즘이다. 1989년 크리스 왓킨스의 박사논문에서 나왔고, 1992년 왓킨스와 데이언이 확률근사 이론으로 수렴을 증명하면서 강화 학습의 이론적 초석이 됐다.

마르코프 결정 과정의 형식화나 할인율의 의미 같은 배경은 해당 문서에 있고, RL 전반의 지형도는 강화 학습 쪽이다. 여기서는 알고리즘 자체 — 갱신식 한 줄이 왜 그렇게 생겼고, 무엇을 보장하며, 어디서 터지는가 — 만 본다.

2. 행동가치와 벨만 최적 방정식[편집]

상태가치 $V(s)$ 대신 행동가치 $Q(s,a)$ 를 배우는 데는 실용적인 이유가 있다. $V$ 만 알면 행동을 고를 때 $\arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V(s')]$ 를 계산해야 하고, 여기엔 $P$ 가 필요하다. 모형을 모르면 못 쓴다. 반면 $Q$ 를 알면 그냥 $\arg\max_a Q(s,a)$ 면 끝이다. ** $Q$ 는 모형을 미리 흡수해 놓은 $V$ **라고 보면 된다.

$Q^{*}$ 가 만족하는 벨만 최적 방정식은 다음과 같다.

Q^{*}(s,a) = \mathbb{E}_{s' \sim P(\cdot|s,a)}\Big[\, R(s,a) + \gamma \max_{a'} Q^{*}(s',a') \,\Big]

우변의 연산자 $\mathcal{T}$ 는 $\gamma$ -수축 사상이라 유일한 고정점을 갖는다( $\|\mathcal{T}Q_1 - \mathcal{T}Q_2\|_\infty \le \gamma \|Q_1 - Q_2\|_\infty$ ). $P$ 를 알면 이 방정식을 동적 계획법으로 반복해 풀면 그만이다. Q러닝은 기대값을 표본 하나로 갈아치운 버전이다.

3. 갱신식 한 줄[편집]

Q(s,a) \leftarrow Q(s,a) + \alpha \Big[\, r + \gamma \max_{a'} Q(s',a') - Q(s,a) \,\Big]

대괄호 안이 TD 오차 $\delta$ 다. “지금 추정치”와 “한 스텝 실제로 겪고 나서 본 추정치”의 차이를 보고, 그 방향으로 학습률 $\alpha$ 만큼 끌어당긴다. 자기 자신의 추정치를 목표로 삼는 것을 부트스트랩이라 부른다. 몬테카를로 방식처럼 에피소드가 끝날 때까지 기다려 실제 수익을 재는 게 아니라 한 스텝만에 갱신하므로 분산이 작고, 대신 현재 추정이 틀리면 그 편향이 그대로 전파된다.

여기서 진짜 핵심은 $\max_{a'}$ 다. 갱신에 쓰는 다음 행동 $a'$ 가 실제로 무엇을 했는지와 무관하다. 그래서 Q러닝은 오프폴리시다.

행동 정책(behavior policy) $\mu$ — 실제로 환경에서 행동을 고르는 정책. 탐험 때문에 무작위 행동을 섞는다.
목표 정책(target policy) $\pi$ — 학습하는 대상. $Q$ 에 대한 탐욕 정책, 즉 최적 정책.

이 분리 덕분에 사람이 조종한 로그, 예전 정책이 남긴 재생 버퍼, 심지어 순수 무작위 탐험 데이터로도 최적 정책을 배울 수 있다. 갱신식에서 $\max_{a'} Q(s',a')$ 를 실제로 취한 행동의 $Q(s', a')$ 로 바꾸면 SARSA(SARSA)가 되고, 이건 온폴리시라 자기가 쓰는 탐험 정책의 가치를 배운다.

절벽 걷기(cliff walking) 예제가 이 차이를 잔인하게 보여준다. 절벽 바로 옆이 최단 경로인 격자에서, Q러닝은 절벽 가장자리를 따라가는 최적 경로를 배운다. SARSA는 $\epsilon$ 확률로 발을 헛디뎌 떨어지는 것까지 가치에 반영하므로 한 칸 물러선 안전 경로를 배운다. 학습 중 누적 보상은 SARSA가 낫고, 최종 정책의 최적성은 Q러닝이 낫다. 실기에서 탐험 중 사고가 실제 손실이라면 이건 취향이 아니라 안전 요구사항이다.¹

4. 수렴 조건 — 표에서만 참인 정리[편집]

표 형태(tabular) Q러닝의 수렴 정리가 요구하는 것은 두 가지다.

모든 $(s,a)$ 쌍을 무한히 자주 방문한다. 탐험이 이론의 전제 조건이지 옵션이 아니라는 뜻이다.
학습률이 로빈스-먼로 조건을 만족한다.

\sum_{t=1}^{\infty} \alpha_t(s,a) = \infty, \qquad \sum_{t=1}^{\infty} \alpha_t^2(s,a) < \infty

첫 조건은 “초기 오차를 끝까지 지울 만큼 크게 움직여라”, 둘째는 “잡음이 누적되지 않게 결국 줄여라”는 뜻이다. $\alpha_t = 1/t$ 는 만족하고, 흔히 쓰는 고정 $\alpha = 0.1$ 은 둘째 조건을 어긴다. 그래서 고정 학습률 Q러닝은 최적 $Q^{*}$ 로 수렴하지 않고 그 주변에서 $\alpha$ 에 비례하는 폭으로 계속 진동한다. 비정상(non-stationary) 환경에서는 오히려 그게 원하는 성질이라 실무에서 그냥 고정으로 둔다. 정리를 어기고 있다는 자각만 있으면 된다.

5. 탐험 전략[편집]

UCB1 다중 슬롯머신을 실제로 돌린다 — 매 스텝 표본평균에 신뢰구간 보너스를 더한 값이 최대인 팔을 당기고, 막대 투명도가 방문 비중, 빨간 눈금이 감춰진 참 평균이다. 밴딧은 상태가 하나뿐인 MDP라서 Q러닝 갱신식의 gamma·max 항이 통째로 사라진 특수 케이스이고, 남는 것은 순수한 탐험-이용 선택뿐이다. c=0.5는 UCB1의 교과서값보다 한참 인색한 설정이라, 초반에 운 좋게 높은 표본평균을 낸 팔에 눌러앉아 참 최적 팔을 늦게까지 못 찾는 장면이 자주 나온다 — 탐험을 아끼면 무슨 일이 벌어지는지에 대한 실측 데모다.

$\epsilon$ -그리디 — 확률 $\epsilon$ 로 균등 무작위, 아니면 탐욕. 단순하고 튼튼해서 여전히 기본값. 보통 1.0에서 0.05까지 감쇠시킨다.
볼츠만(소프트맥스) — $\pi(a|s) \propto \exp(Q(s,a)/\tau)$ . 나쁜 행동과 그저 그런 행동을 구분해서 찔러본다는 점이 $\epsilon$ -그리디보다 낫지만, 온도 $\tau$ 가 $Q$ 의 스케일에 민감해서 손이 많이 간다.
UCB — 방문이 적은 행동에 신뢰구간 보너스를 얹는다. 밴딧에서는 후회 상한이 증명되어 있고, 같은 규칙이 트리에 붙으면 몬테카를로 트리 탐색의 UCT가 된다.
낙관적 초기화 — $Q$ 를 도달 불가능하게 높은 값으로 초기화한다. 안 해본 행동이 자동으로 매력적으로 보이므로 탐욕 정책만으로도 초반 탐험이 일어난다. 공짜에 가까운 트릭이지만 비정상 환경에서는 한 번 낮아진 값이 다시 안 올라간다는 한계가 있다.

6. 최댓값 편향과 이중 Q러닝[편집]

$\max$ 연산은 공짜가 아니다. 참값은 전부 0인데 추정치에 평균 0의 잡음만 얹혀 있어도, $\mathbb{E}[\max_a \hat Q] \ge \max_a \mathbb{E}[\hat Q] = 0$ 이다(옌센 부등식). 잡음의 최댓값은 항상 양수 쪽으로 치우친다. 그래서 Q러닝은 체계적으로 가치를 과대평가하고, 그 과대평가가 부트스트랩으로 다시 전파된다.

처방은 우아하다. 이중 Q러닝(double Q-learning)은 추정량을 $Q^A$ , $Q^B$ 둘로 나눠 행동 선택과 가치 평가를 서로 다른 표에 맡긴다.

Q^A(s,a) \leftarrow Q^A(s,a) + \alpha\Big[\, r + \gamma\, Q^B\big(s',\ \arg\max_{a'} Q^A(s',a')\big) - Q^A(s,a) \,\Big]

$A$ 가 고른 행동을 $B$ 가 채점하니, $A$ 의 잡음이 운 좋게 컸다는 이유만으로 그 값이 그대로 목표에 들어가지 않는다. 이 아이디어를 신경망판에 옮긴 것이 Double DQN이고, 아타리 벤치마크에서 가치 과대평가 곡선이 눈에 띄게 눌리는 것이 보고됐다.

7. 함수 근사와 치명적 삼중주[편집]

상태가 연속이거나 고차원이면 표를 못 쓴다. $Q_\theta(s,a)$ 를 심층 학습 신경망으로 근사하는 순간 위의 수렴 정리는 전부 무효가 된다. 서턴이 이름 붙인 치명적 삼중주(deadly triad) — (1) 부트스트랩, (2) 오프폴리시, (3) 함수 근사 — 가 동시에 모이면 발산하는 반례가 존재하기 때문이다. 셋 중 하나라도 빼면 대체로 안전한데, Q러닝은 태생적으로 셋을 다 갖고 있다.²

DQN(2015)은 이걸 정면 돌파하는 대신 두 개의 안정화 장치로 눌렀다.

경험 재현(replay buffer) — 전이를 큰 버퍼에 쌓아 무작위로 뽑아 학습한다. 연속한 표본의 상관을 깨서 기울기 추정을 i.i.d.에 가깝게 만든다. 오프폴리시이기 때문에 가능한 사치다.
타깃 네트워크 — 목표 $r + \gamma \max_{a'} Q_{\theta^{-}}(s',a')$ 의 파라미터 $\theta^{-}$ 를 수천 스텝마다만 복사한다. 목표가 매 스텝 같이 움직이면 회귀가 자기 꼬리를 무는 꼴이 되는데, 그 되먹임 고리를 느리게 만든 것.

이후 우선순위 재현, 듀얼링 구조, 분포형 Q학습(C51, QR-DQN) 등이 얹혀 Rainbow로 묶였다. 다만 표본 효율은 여전히 나쁘다. 아타리 한 게임에 수천만 프레임을 쓰는데, 환경 모형을 학습해 상상 속에서 롤아웃을 도는 모형 기반 방법이 같은 성능을 훨씬 적은 실환경 표본으로 내는 사례가 계속 보고된다. 시뮬레이터가 무료로 돌아가는 판이라면 Q러닝의 표본 낭비는 큰 죄가 아니지만, 실기 데이터 한 판이 비싸다면 이야기가 완전히 달라진다.³

한 스텝만 부트스트랩하는 대신 $n$ 스텝 수익을 쓰거나 적격 흔적(eligibility trace)으로 여러 지평을 섞으면 편향-분산 저울을 손으로 조절할 수 있다. 다만 오프폴리시에서 흔적을 그대로 쓰면 행동 정책이 탐욕 정책을 벗어나는 순간 목표가 오염되므로, 탐욕에서 이탈할 때 흔적을 끊는 왓킨스의 $Q(\lambda)$ 나 중요도 비율을 가중하는 Retrace 계열이 필요하다. 공학 문제에 붙일 때 실제로 시간을 잡아먹는 것은 이런 이론적 변형보다 상태·행동의 이산화인 경우가 많다. 연속 제어를 억지로 격자로 자르면 행동 수가 차원의 지수로 늘고, 그 순간 $\max_{a'}$ 하나가 병목이 된다. 그래서 연속 행동에는 Q러닝을 그대로 쓰지 않고 액터가 $\arg\max$ 를 대신 근사하는 DDPG·TD3·SAC 계열로 넘어간다.

관측이 상태를 온전히 말해주지 않는 경우에는 $Q(s,a)$ 의 전제 자체가 무너진다. 그때는 부분관측 마르코프 결정 과정으로 문제를 다시 세워야 하고, 실무에서는 관측 몇 프레임을 쌓아 상태를 대신하는 편법으로 넘어가는 경우가 많다.⁴

8. 관련 문서[편집]

“Q러닝이 더 좋은 정책을 배우는데 왜 SARSA를 쓰냐”는 질문의 답은 대개 하드웨어 값이다. 학습 중에 로봇 팔이 벽을 치면 그건 통계량이 아니라 수리비다. ↩
학습률 $\alpha$ 를 잘못 잡아 $Q$ 값이 발산할 때, 로그를 보면 대개 몇몇 상태의 값이 $10^{6}$ 단위로 튀어 있다. 부트스트랩·오프폴리시·함수근사 삼종 세트를 다 켜 놓고 “일단 돌려”를 시전한 대가다. 그 세 개 중 뭘 끌지 고르는 게 디버깅의 시작이다. ↩
벨만 방정식이 자기참조라서 생기는 문제들은 결국 전부 같은 뿌리다 — 목표가 학습 대상의 함수라는 것. 지도학습이 부러워지는 순간이 하루에 한 번씩은 온다. ↩
아타리에서 최근 4프레임을 채널로 쌓는 그 관용구가 정확히 이것이다. 정지 화면 한 장으로는 공이 어느 쪽으로 가는지 알 수 없으니, 관측을 쌓아 마르코프성을 억지로 복구한 것. 이론적으로는 POMDP를 유한 이력 MDP로 근사한 셈이다. ↩

Q러닝