강화 학습(Reinforcement learning)

로봇 하나가 가로 4칸, 세로 3칸짜리 방에 있습니다. 오른쪽 위 칸은 출구(보상 +1), 그 아래 칸은 함정(보상 −1)이고, 가운데에는 벽이 하나 있습니다. 로봇은 매번 위·아래·왼쪽·오른쪽 가운데 하나를 고르지만 바닥이 미끄러워서, 고른 쪽으로 갈 확률⁠(probability)⁠은 0.8이고 그 양옆으로 미끄러질 확률이 0.1씩입니다. 벽이나 방 끝에 부딪히면 제자리에 머뭅니다. 출구나 함정이 아닌 칸에서는 한 걸음마다 보상 r(처음 값 −0.04)을 받습니다. 음수 보상은 걸음마다 내는 비용인 셈입니다. 누구도 '이 칸에서는 위로 가라'는 정답을 알려 주지 않고, 주어지는 것은 보상뿐입니다. 이렇게 보상으로 행동을 배우는 것이 강화 학습입니다. 이 방은 스튜어트 러셀과 피터 노빅의 인공지능⁠(artificial intelligence)⁠ 교과서에 나오는 예입니다. 아래에서는 먼저 방의 규칙(미끄러질 확률)을 안다고 치고 가장 좋은 행동을 계산한 뒤, 규칙을 모를 때 겪으면서 배우는 방법으로 넘어갑니다.

문제를 수학으로 적으면 마르코프 결정 과정⁠(Markov decision process)⁠이 됩니다. 상태(칸), 행동, 행동했을 때 다음 상태의 확률 $P(s' \mid s, a)$, 보상, 그리고 할인율⁠(discount factor)⁠ γ(감마)로 이루어집니다. $P(s' \mid s, a)$는 '상태 s에서 행동 a를 했을 때 상태 s′(s 프라임)에 도착할 확률'로 읽습니다. 이를테면 출구 바로 왼쪽 칸에서 오른쪽을 고르면 출구에 도착할 확률이 0.8입니다. 다음 상태가 지금 상태와 행동에만 달려 있으니 마르코프 연쇄⁠(Markov chain)⁠에 선택을 더한 것입니다. 목표는 받을 보상의 합 $r_0 + \gamma r_1 + \gamma^2 r_2 + \cdots$의 기댓값⁠(expected value)⁠을 가장 크게 하는 행동 규칙(정책)을 찾는 것입니다. γ가 1보다 작으면 먼 미래의 보상일수록 덜 칩니다. 상태 s의 가치 V(s)는 s에서 출발해 가장 잘 행동할 때 받을 합의 기댓값이고, 다음 식(벨먼 방정식)을 만족합니다.

$$V(s) = R(s) + \gamma \max_{a} \sum_{s'} P(s' \mid s, a)\, V(s')$$

Σ(시그마)는 도착할 수 있는 칸 s′ 모두에 대해 '도착할 확률 × 그 칸의 가치'를 더하라는 뜻이고, 그 합이 행동 a를 했을 때 앞으로 받을 가치의 평균입니다. $\max_a$(맥스)는 행동 a 가운데 이 평균⁠(mean)⁠이 가장 큰 것을 고르라는 뜻입니다. 말로 하면, 이 칸의 보상을 받고, 가장 좋은 행동으로 한 걸음 가서, 도착한 곳에서부터 다시 가장 잘 행동한다고 생각하면 됩니다. 이 식은 1950년대 리처드 벨먼이 동적 계획법⁠(dynamic programming)⁠을 세우며 쓴 최적성의 원리⁠(principle of optimality)⁠를 적은 것입니다. 최적 계획의 뒷부분은 그 자체로 (그 지점에서 출발하는) 최적 계획이라는 원리입니다. 모든 칸의 값을 식의 오른쪽으로 한꺼번에 다시 계산하는 일을 되풀이하는 것이 가치 반복입니다. 할인율 γ = , 한 걸음의 보상 r = , 바닥: .

처음 설정으로 첫 갱신을 보면, 출구 바로 왼쪽 칸 (1, 3)만 −0.04 + 0.9 × 0.8 × 1 = 0.68을 얻고 나머지 칸은 모두 r = −0.04입니다. 이 0.68이 벨먼 방정식을 한 칸에 한 번 적용한 결과입니다. 처음에는 모든 칸의 값을 0으로 두고 시작하므로, (1, 3)에서 '오른쪽'을 고르면 도착할 수 있는 칸은 출구(확률 0.8, 가치 1), 위쪽 벽에 막혀 제자리(0.1, 가치 0), 아래 칸(0.1, 가치 0)입니다. Σ는 0.8 × 1 + 0.1 × 0 + 0.1 × 0 = 0.8이고, 다른 행동은 이보다 작으니 max도 0.8입니다. 여기에 R(s) = −0.04와 γ = 0.9를 넣으면 −0.04 + 0.9 × 0.8 = 0.68입니다. 함정 옆 칸들도 r인 것은, 함정에 빠질 위험이 없는 행동을 고를 수 있어서입니다. 그 뒤로는 갱신할 때마다 출구와 함정의 소식이 한 칸씩 멀리 퍼집니다. k번 갱신한 값은 k걸음 안의 계획까지만 따진 값이기 때문입니다. 칸에 마우스를 올리면 지금 값으로 계산한 행동별 값이 뜨고, 그 가운데 가장 큰 것이 다음 단계의 그 칸 값이 됩니다. 수렴하면 화살표가 정책입니다. 처음 설정에서는 함정 바로 왼쪽 칸 (2, 3)의 화살표가 위를 가리킵니다. 오른쪽을 고르면 곧장 함정에 빠질 수 있으니, 위로 가다 옆으로 미끄러지는 위험(0.1)만 지는 쪽을 고른 것입니다.

이제 보상 r을 바꿔 봅니다. r을 −1 가까이 내려 보세요. 한 걸음이 너무 비싸져서, 오른쪽 아래 칸 (3, 4)의 화살표가 함정 쪽인 위를 가리킵니다. 먼 출구까지 걷는 비용보다 함정의 −1이 덜 나쁘니 빨리 끝내려는 것입니다.

반대로 r을 0.2로 올리면 출구 바로 옆 칸 (1, 3)조차 출구를 등지고 왼쪽을 가리킵니다. 끝나는 칸에 들어가지 않고 방 안에 머무는 동안 걸음마다 보상을 받으니, 영원히 머무는 값 r + γr + γ²r + ⋯ = r/(1 − γ)(γ = 0.9, r = 0.2라면 2)가 출구의 +1보다 크기 때문입니다. 이때 모든 칸의 값이 2가 되고, 화살표가 없는 칸은 어느 행동이든 값이 같은 칸입니다.

두 실험이 보여 주는 것은 하나입니다. 흔히 보상은 목표를 알려 주는 신호일 뿐이라고 생각하지만, 실제로는 보상을 정하는 일이 무엇을 원하는지 적는 일 그 자체입니다. 로봇은 우리가 원한 것이 아니라 적힌 것을 최적화⁠(optimization)⁠합니다.

왜 반드시 수렴하는가. 식의 오른쪽을 계산하는 연산을 T라 하면 가치 반복⁠(value iteration)⁠은 V ← TV의 되풀이이고, 벨먼 방정식은 V = TV, 곧 V가 T의 고정점⁠(fixed point)⁠이라는 말입니다. 두 값의 표 U, V가 어느 칸에서도 δ보다 더 다르지 않다고 합시다. 확률로 가중한 평균의 차이는 δ를 넘을 수 없고, 행동마다의 값 가운데 가장 큰 것을 고르는 일도 차이를 키우지 못합니다($|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$). f의 최댓값을 내는 행동을 a*라 하면, 거기서 g(a*)는 f(a*)보다 기껏해야 둘의 차이만큼 작고, g의 최댓값은 g(a*) 이상이기 때문입니다. f와 g를 바꿔도 같은 논리가 성립합니다. 거기에 γ가 곱해지므로 TU와 TV는 어느 칸에서도 γδ보다 더 다르지 않습니다.

$$\max_s \bigl|TU(s) - TV(s)\bigr| \le \gamma\, \max_s \bigl|U(s) - V(s)\bigr|$$

이렇게 거리를 1보다 작은 일정한 비율 이하로 줄이는 연산을 축소 사상이라 하고, 여기서는 $\gamma \lt 1$이라서 T가 축소 사상입니다. 칸이 유한개인 값의 표들은 완비 공간(서로 한없이 가까워지는 표의 열이 늘 어떤 표로 수렴하는 공간)을 이루고, 이런 공간에서 축소 사상은 고정점을 정확히 하나 가지며, 어디서 출발하든 오차가 걸음마다 γ배 이하로 줄어 그 고정점에 다가갑니다(바나흐 고정점 정리⁠, Banach fixed-point theorem⁠). γ = 0.9라면 처음 오차를 1,000분의 1로 줄이는 데 66번이면 충분합니다(0.9⁶⁶ ≈ 0.00096). 걸음마다 뜨는 설명에서 최대 변화가 앞 단계의 γ배를 넘지 않는 것을 확인할 수 있습니다. 수렴한 값에서 칸마다 가장 좋은 행동을 고르면 그것이 최적 정책입니다. γ가 1에 가까울수록 줄어드는 비율이 느려지는 것도 볼 수 있습니다.

모형을 모를 때. 가치 반복은 확률 P와 보상을 모두 안다고 가정합니다. 실제 로봇이나 게임에서는 이것을 모르고, 해 보면서 겪은 것만 압니다. 1988년 리처드 서튼이 정리한 시간차(TD) 학습은 정해진 정책을 따르며 한 걸음을 겪을 때마다, 그 정책의 벨먼 방정식(max가 없는 꼴)의 양쪽이 어긋난 만큼 값을 고칩니다.

$$V(s) \leftarrow V(s) + \alpha\,\bigl[\,r + \gamma V(s') - V(s)\,\bigr]$$

기댓값을 계산하는 대신 실제로 한 번 일어난 일로 어림하는 것이니, 몬테카를로 방법처럼 표본⁠(sample)⁠으로 평균을 대신하는 셈입니다. α(알파)는 한 번에 얼마나 고칠지 정하는 학습률입니다. 이를테면 V(s) = 0.5인데 한 걸음 겪어 보니 r + γV(s′)가 0.7이었다면, α = 0.1일 때 차이 0.2의 10분의 1만큼 고쳐 V(s)는 0.52가 됩니다.

1989년 크리스 왓킨스의 Q 학습⁠(Q-learning)⁠은 상태와 행동의 짝마다 값 Q(s, a)를 두고, 목표에 $r + \gamma \max_{a'} Q(s', a')$를 써서 같은 방식으로 고칩니다. max가 들어 있어서, 탐험하느라 다른 행동을 하는 동안에도 최적 정책의 값을 배웁니다. 값을 표로 적는 경우, 모든 짝을 무한히 자주 겪고 α를 알맞게 줄여 가면 확률 1로 최적의 Q에 수렴한다는 것을 1992년 왓킨스와 피터 다얀이 증명했습니다. '알맞게'란 n번째 고칠 때의 α를 모두 더하면 끝없이 커지고, 제곱해서 더하면 유한하다는 뜻입니다. α = 1/n이 그런 예입니다. 1 + 1/2 + 1/3 + ⋯은 끝없이 커지므로 아무리 오래 겪어도 값을 고칠 힘이 남아 있고, 1 + 1/4 + 1/9 + ⋯은 유한하므로(약 1.64) 표본마다 다른 우연한 흔들림이 결국 잦아듭니다.

여기서 탐험과 활용⁠(exploration and exploitation)⁠의 저울질이 생깁니다. 지금까지 가장 좋았던 행동만 하면(활용) 더 좋은 행동을 영영 모르고, 새 행동을 너무 자주 시험하면(탐험) 보상을 잃습니다. 흔한 해법은 대개 가장 좋아 보이는 행동을 하되 작은 확률 ε(엡실론)로 아무 행동이나 해 보는 것이고, 이것을 ε-탐욕이라 부릅니다. 값을 표 대신 신경망⁠(neural network)⁠으로 어림하면 이런 수렴 보장은 일반적으로 사라지고, 실제로 값이 발산⁠(divergence)⁠하는 예도 알려져 있습니다.

역사. 1959년 아서 새뮤얼의 체커 프로그램은 지금 국면의 평가를 몇 수 뒤 국면의 평가에 가깝게 고쳐 나갔는데, 이것이 시간차 학습⁠(temporal-difference learning)⁠의 선구로 꼽힙니다. 벨먼은 1950년대 초 미 공군이 지원하던 RAND 연구소에서 결정을 여러 단계에 걸쳐 차례로 내리는 문제를 연구하며 '동적 계획법'이라는 이름을 지었고, 1957년 책 『동적 계획법』에서 이 문제를 정식화했습니다. 1960년 로널드 하워드는 정책을 평가하고 고치기를 되풀이하는 정책 반복⁠(policy iteration)⁠을 내놓았습니다. 서튼과 앤드루 바토는 1980년대에 강화 학습을 하나의 분야로 묶었습니다. 1992년 제럴드 테사우로의 TD-개먼은 자기 자신과 둔 판으로 백개먼을 배워 최상급 선수에 가까운 수준에 이르렀고, 2015년 딥마인드의 DQN은 화면의 픽셀과 점수만 보고 아타리 게임 49개를 배워 그 가운데 29개에서 사람 전문 시험자 점수의 75% 이상을 냈습니다. 2016년 알파고는 사람의 기보로 배운 신경망을 자기 대국 강화 학습으로 다듬고 몬테카를로 트리 탐색⁠(Monte Carlo tree search)⁠과 엮었습니다. 언어 모델⁠(language model)⁠을 사람의 선호에 맞추는 인간 피드백 강화 학습도 이 틀을 씁니다. 서튼과 바토는 2024년도 튜링상⁠(Turing Award)⁠을 받았습니다.

한계. 강화 학습은 대개 아주 많은 경험을 먹습니다. DQN은 게임 하나마다 5천만 프레임을 학습했는데, 논문의 계산으로 게임 시간 약 38일어치입니다. 시뮬레이터에서 배운 정책이 현실에서 그대로 통하지 않는 문제도 있습니다. 가장 까다로운 것은 보상 설계입니다. 에이전트(행동하며 배우는 주체)는 적어 준 보상을 최적화할 뿐이라서, 설계자가 예상하지 못한 허점을 찾아 점수만 올리는 일이 자주 보고됩니다. 이것을 보상 해킹⁠(reward hacking)⁠이라 하고, 재는 값을 목표로 삼으면 그 값이 더는 좋은 잣대가 아니게 된다는 굿하트의 법칙⁠(Goodhart's law)⁠의 한 모습입니다.

이어지는 곳.

• 마르코프 연쇄: 다음 상태가 지금에만 달려 있다는 가정이 여기서 왔습니다.
• 동적 계획법: 가치를 뒤에서부터 채워 가는 계산은 동적 계획법의 표 채우기와 같습니다.
• 고정점: 가치 반복이 왜 한 답으로 수렴하는지, 되풀이가 한 점으로 모이는 조건.
• 기댓값: 가치가 왜 평균인지.
• 몬테카를로 방법⁠(Monte Carlo method)⁠과 큰 수의 법칙⁠(law of large numbers)⁠: 겪은 표본으로 기댓값을 대신하는 생각의 근거.
• 신경망, 경사 하강법⁠(gradient descent)⁠, 확률적 경사 하강법⁠(stochastic gradient descent)⁠: 값을 신경망으로 어림하고 기울기⁠(slope)⁠로 고치는 부분.
• 게임 트리⁠(game tree)⁠ 탐색: 상대가 있는 게임에서 같은 계산을 하면 미니맥스⁠(minimax)⁠가 됩니다.
• 인간 피드백 강화 학습: 사람의 선호를 보상으로 삼은 강화 학습.
• 추론 모델: 수학 문제의 답이나 코드의 테스트처럼 기계적으로 채점할 수 있는 결과를 보상으로 삼아, 언어 모델이 긴 풀이를 쓰도록 학습시킨 것.
• 벨먼: 벨먼 방정식과 동적 계획법을 세운 사람.
• 새뮤얼: 스스로와 두며 배우는 기계의 시작.
• 서튼: 시간차 학습과 이 분야의 교과서.