세 구역 택시를 다시 떠올려 보자. 운전사는 역, 시장, 대학가 가운데 손님을 내려 준 구역에서 배회(거리를 돌며 손님 태우기)나 승차장(줄에 서서 기다리기, 기다리는 비용 2천 원)을 고르고, 손님을 내려 줄 때마다 1/10 확률로 퇴근한다. 「늘 승차장」 정책(구역마다 무엇을 고를지 정한 규칙)으로 시장에서 하루를 1만 번 돌려 리턴(앞으로 받을 보상의 합)을 평균 내니 59.41이 나왔고, 표준오차(다시 돌리면 평균이 달라지는 정도를 잰 표준편차)가 0.59였다. 시장에서 배회와 승차장의 행동 가치(첫 행동을 정해 두고 그 뒤로 정책을 따를 때의 리턴 기댓값) 차이 0.34가 우연이 아님을 보이는 데는 하루 200만 번이 들었다.
그 셈을 하는 동안 우리는 같은 숫자 세 개(구역마다의 가치. 그 구역에서 시작해 앞으로 받을 돈의 기댓값)를 알고 싶었을 뿐이다. 그리고 상태의 가치는 바로 아래 상태들의 가치를 확률로 섞은 평균이라는 것도 알고 있었다. 숫자 세 개가 서로를 붙들고 있다면, 하루를 수백만 번 돌리지 않고 그 관계만으로 셈할 수는 없을까?
가치를 에피소드(하루처럼 시작과 끝이 있는 한 판) 평균으로 재면 느리고, 잴 때마다 값이 달라진다. 숫자들 사이의 관계를 식으로 적어 한 번에 풀 수는 없을까?
정책을 하나씩 평가하는 대신, 가장 좋은 정책의 가치를 곧장 구하는 식도 있을까? 있다면 max가 든 그런 식은 어떻게 풀까?
이 장은 가치를 「이번 스텝」과 「그 뒤」로 쪼개는 식 하나에서 출발한다. 그 식으로 정책 하나의 가치를 연립방정식으로 풀고, 최선의 가치를 적고, 최선의 가치 식을 되풀이로 푸는 방법이 왜 늘 한 점에 닿는지 보고, 평가와 고치기를 번갈아 하는 둘째 방법을 본다.
벨먼 기대 방정식: 지금 보상 + 다음 상태 가치
시장에 있는 운전사가 「늘 승차장」 정책을 따른다고 하자. 이번 손님에게서 평균 3.80(천 원)을 받고, 손님을 내려 준 뒤에는 확률 0.36으로 역에, 0.18로 시장에, 0.36으로 대학가에 있고, 0.10으로 퇴근한다. 다음 구역에 닿은 운전사는 거기서 또 같은 정책을 따른다. 그렇다면 시장에서 앞으로 받을 돈은 「이번 3.80」에 「다음 구역에서 앞으로 받을 돈」을 확률로 섞어 더한 것이어야 한다. 다음 구역에서 앞으로 받을 돈은 바로 그 구역의 가치이므로, 가치가 다시 가치로 적힌다. 「가치 = 이번 보상 + 다음 가치의 평균」이라는 관계가 쓸모 있는 식이 될까?
역사: 벨먼의 쪼개기
1949년 여름, 스탠퍼드 대학교 수학과 부교수였던 리처드 벨먼(Richard Bellman)은 두 번째 여름을 미국 공군의 연구를 맡던 랜드 연구소(RAND)에서 자문으로 보내고 있었다. 해석적 정수론에 마음이 있던 그가 랜드의 에드 팩슨(Ed Paxson)에게 랜드가 무엇에 관심이 있는지 묻자, 팩슨은 여러 단계에 걸쳐 결정을 내리는 문제를 권했다. 한 번의 선택이 다음 선택의 처지를 바꾸므로, 가능한 선택의 줄을 모두 늘어놓고 견주면 단계가 늘 때마다 셈이 불어난다. 벨먼이 붙든 수는 한 단계씩 떼어 보는 것이었다. 한 처지의 가치를 「이번 선택으로 받는 것 + 다음 처지의 가치」로 적으면, 긴 문제가 한 단계짜리 문제의 되풀이로 바뀐다. 1957년 책 『Dynamic Programming』이 이 쪼개기를 여러 단계 결정 문제의 기본 도구로 정리했고, 오늘날 이 꼴의 식을 그의 이름을 따 벨먼 방정식이라 부른다.
이 방법의 이름 「동적 계획법(dynamic programming)」에는 벨먼 자신이 남긴 일화가 있다. 그는 자서전 『Eye of the Hurricane』(1984)에서, 1950년 가을 학기를 랜드에서 보낼 때 첫 일이 여러 단계 결정 문제에 붙일 이름을 찾는 것이었다고 회고했다. 당시 국방장관 윌슨은 「연구(research)」라는 말만 들어도 얼굴이 붉어질 만큼 그 말을 싫어했고, 공군은 사실상 윌슨의 지휘를 받았다. 그래서 랜드 안에서 수학을 한다는 사실을 가릴 이름이 필요했다는 것이다. 계획을 뜻하는 「programming」에, 여러 단계에 걸쳐 시간에 따라 변한다는 뜻을 담아 「dynamic」을 붙였다. 그는 「dynamic」은 나쁜 뜻으로 쓸 수 없는 형용사라서 국회의원도 반대하지 못할 이름이라고 덧붙였다.
다만 이 회고를 그대로 믿기는 어렵다는 지적이 있다. 러셀(Stuart Russell)과 노빅(Peter Norvig)은 교과서 『Artificial Intelligence: A Modern Approach』에서, 벨먼이 이 말을 쓴 첫 논문(1952)이 윌슨의 국방장관 취임(1953)보다 앞서므로 이야기가 글자 그대로 사실일 수는 없다고 적었다. 해럴드 쿠슈너(Harold Kushner)는 자신이 같은 물음을 했을 때 벨먼이 조지 댄치그의 「선형 계획법(linear programming)」보다 앞서 보이려고 「dynamic」을 붙였다고 답했다는 다른 이야기를 전했다.
세 줄의 연립방정식
시장에서 한 셈을 세 구역 모두에 적어 보자. 「늘 승차장」 정책에서 구역마다 이번 손님의 기대 보상은 역 6.80, 시장 3.80, 대학가 6.80이고, 다음 구역의 확률(퇴근 0.10을 뺀 나머지)은 아래 표와 같다.
지금 \ 다음
역
시장
대학가
퇴근
역
0.09
0.18
0.63
0.10
시장
0.36
0.18
0.36
0.10
대학가
0.63
0.27
0
0.10
퇴근한 뒤에는 더 받을 돈이 없으니 퇴근 칸의 가치는 0이다. 구역마다 「이번 보상 + 다음 구역 가치의 확률 평균」을 적으면 미지수 셋, 식 셋이 나온다.
가치를 「이번 스텝의 보상 + 할인한 다음 상태 가치의 평균」으로 적은 첫 식을 벨먼 기대 방정식 (정책 하나의 가치를 한 스텝으로 쪼갠 식 / Bellman expectation equation)이라 한다. 「기대」는 정책과 세상이 뽑는 다음 상태에 대한 평균이라는 뜻이다. 오른쪽 꼴은 같은 식을 세 구역을 한꺼번에 담는 행렬로 적은 것이고, 미지수가 일차로만 들어 있으니 연립일차방정식이다. 「늘 승차장」 정책의 행렬을 넣고 풀면 다음 값이 나온다.
하루를 1만 번 돌려 얻은 시장의 평균 59.41(표준오차 0.59)과 식으로 푼 58.70의 차이는 0.71, 표준오차의 1.2배다. 모의실험의 표준오차 범위 안에서 같은 값이다. 「늘 배회」 정책도 식으로 풀면 시장의 가치가 50.30이고, 1만 번 돌린 평균 49.96(표준오차 0.49)과 표준오차 안에서 맞는다. 수백만 번의 하루가 하던 일을 3 × 3 연립방정식 하나가 한다.
그림은 백업 나무(상태 → 행동 → 다음 상태로 갈라지는 나무)를 한 층만 잘라 숫자를 단 것이다. 끝까지 내려가며 길 하나의 리턴을 재던 모의실험과 달리, 벨먼 기대 방정식은 바로 아래 층의 가치만 본다. 아래 층의 가치가 다시 위층의 가치로 적히니, 세 구역의 가치가 서로를 붙드는 고리가 되고, 그 고리를 한꺼번에 푸는 것이 연립방정식이다.
풀이에 쓴 역행렬 (I−Pπ)−1에도 읽을 거리가 있다. (I−Pπ)−1=I+Pπ+(Pπ)2+⋯ 이므로, 이 행렬의 칸 (s,s′)은 「s에서 출발해 하루 동안 s′에서 손님을 태우는 횟수의 기댓값」이다. 「늘 승차장」 정책에서 시장 줄은 (3.547, 3.102, 3.351)이고 세 칸을 더하면 정확히 10이다. 손님마다 1/10 확률로 퇴근하는 하루에 태우는 손님 수의 평균 1/0.1 = 10이 그대로 나온다. 가치는 「구역마다 몇 번 들르는가 × 그 구역에서 한 번에 받는 돈」의 합이다.
ML에서: 토큰 하나만큼 쪼개기
언어 모델이 응답을 쓰는 MDP(마르코프 결정 과정: 상태, 행동, 전이 확률, 보상으로 적은 결정 문제)에서는 토큰 a를 고르면 다음 상태가 「지금 문장 뒤에 a를 붙인 문장」 하나로 정해진다. 그래서 벨먼 기대 방정식의 다음 상태 평균이 정책의 평균 하나로 줄어든다. 보상이 응답 끝에만 오고 γ = 1이면, 중간 자리의 가치는 「다음 토큰을 붙인 자리들의 가치를 정책의 확률로 섞은 평균」이고, 마지막 자리의 가치는 끝 보상의 기댓값이다.
그렇다고 언어 모델의 가치를 연립방정식으로 풀 수는 없다. 상태는 「프롬프트 + 지금까지 쓴 토큰」이라 어휘가 수만 개면 몇 토큰만 지나도 칸 수가 감당할 수 없이 늘어나고, 행렬 Pπ를 적을 수조차 없다. 대신 벨먼 기대 방정식은 학습한 가치 모델(상태를 넣으면 그 가치를 예측하는 신경망)이 지켜야 할 조건이 된다. 가치 모델이 매긴 숫자들이 서로 벨먼 기대 방정식을 지키는지 따져 볼 수 있는데, 그 검사가 아래 문제 3이다.
문제 1: 빵집의 단골
동네 빵집의 손님은 「단골」과 「뜸한 손님」으로 나뉜다. 단골은 한 달에 3만 원을 쓰고, 다음 달에 0.8 확률로 단골로 남고 0.1 확률로 뜸한 손님이 되며 0.1 확률로 발길을 끊는다. 뜸한 손님은 한 달에 1만 원을 쓰고, 다음 달에 0.3 확률로 단골이 되고 0.5 확률로 뜸한 손님으로 남으며 0.2 확률로 발길을 끊는다. 할인은 하지 않는다. (가) 지금 단골인 손님 한 명이 앞으로 쓸 돈의 기댓값과, 지금 뜸한 손님 한 명의 기댓값을 구하시오. (나) 뜸한 손님이 다시 단골이 되는 일이 없다면(0.3 → 0, 그만큼 발길을 끊는다) 단골 한 명의 기댓값은 얼마로 줄어드는가?
선생님
민준 학생, 단골 한 명의 값은 어떻게 셈했어요?
김민준
이번 달 3만 원에, 다음 달에도 단골이면 또 3만 원, 뜸해지면 1만 원이니까 3 + 0.8 × 3 + 0.1 × 1 = 5.5만 원이요.
선생님
다음 달에도 단골로 남은 사람은 그다음 달에 무엇을 하죠?
김민준
또 3만 원을 쓰고 또 0.8로 남죠. 두 달만 셈하고 끊은 거네요. 그런데 끝까지 다 더하려면 달마다 갈래가 늘어나서 셈이 끝이 없어요.
이서연
잠깐, 끝까지 안 더해도 될 것 같아. 「다음 달에 단골인 사람의 앞으로의 값」은 지금 단골인 사람의 값이랑 같지 않아? 다음 달부터 보면 그 사람도 그냥 단골이잖아.
선생님
좋아요. 그 생각을 식으로 적어 볼 수 있어요?
이서연
단골의 값을 V(단골), 뜸한 손님의 값을 V(뜸)이라 하면 V(단골) = 3 + 0.8 V(단골) + 0.1 V(뜸)이요. 뜸한 손님도 같은 꼴로 V(뜸) = 1 + 0.3 V(단골) + 0.5 V(뜸)이고요.
V(단골) = 3 + 0.8 V(단골) + 0.1 × 2 를 풀면 16만 원이에요. 뜸한 손님을 다시 단골로 만드는 일이 단골 한 명의 값을 6.86만 원이나 올리고 있었네요.
김민준
조별 과제 기여도를 셀 때 이번 주 한 일만 보지 않고, 그 사람이 다음 주에도 남아 있을지까지 넣으면 이런 식이 되겠어요.
정리 (가) V(단골) = 3 + 0.8 V(단골) + 0.1 V(뜸), V(뜸) = 1 + 0.3 V(단골) + 0.5 V(뜸)을 풀어 22.86만 원과 15.71만 원. 두 달만 더한 5.5만 원은 그 뒤를 버린 값이다. (나) 16만 원. 상태끼리 서로를 붙드는 고리가 가치를 키운다.
문제 2: 퇴근이 없으면
세 구역 택시의 「늘 배회」 정책을 본다. 배회할 때 이번 손님의 기대 보상은 역 5.50, 시장 4.50, 대학가 5.60이고, 일이 이어질 때 다음 구역의 확률은 역에서 (0.6, 0.3, 0.1), 시장에서 (0.3, 0.6, 0.1), 대학가에서 (0.2, 0.2, 0.6)이다(순서는 역, 시장, 대학가). (가) 손님마다 1/10 확률로 퇴근하고 γ = 1일 때 벨먼 기대 방정식의 역 줄을 적고, 세 구역의 가치를 구하시오. (나) 퇴근이 없고 γ = 1이면 연립방정식 (I−Pπ)Vπ=rπ은 풀리는가? (다) 퇴근이 없고 γ = 0.9이면?
선생님
(가)부터요. 서연 학생, 역 줄은요?
이서연
다음 구역의 확률에 일이 이어질 확률 0.9를 곱해서 넣으면 되겠죠. V(역) = 5.50 + 0.54 V(역) + 0.27 V(시장) + 0.09 V(대학가) 예요.
선생님
시장과 대학가 줄도 같은 꼴이죠. 세 줄을 함께 풀면요?
김민준
돌려 보니까 역 51.67, 시장 50.30, 대학가 52.07이에요.
선생님
(나)는요? 민준 학생.
김민준
0.9를 1로 바꾸기만 하면 되잖아요. 같은 방법으로 풀면 숫자가 좀 커지겠죠.
선생님
그 행렬 I−Pπ에 (1, 1, 1)을 곱해 보면 무엇이 나와요?
김민준
행마다 1에서 확률 합 1을 빼니까 (0, 0, 0)이에요. 0이 아닌 벡터를 0으로 보내는 행렬이니 역행렬이 없어요. 풀리지 않네요.
이서연
리턴으로 보면 당연해. 퇴근 없이 끝없이 배회하면 역에서 손님 10명이면 51.7, 100명이면 512.5, 1,000명이면 5,120.5로 받을 돈이 한없이 커지잖아. 유한한 답이 있을 수가 없어.
선생님
그래요. (다)는요?
이서연
이번에는 행렬이 I−0.9Pπ라 (1, 1, 1)을 곱하면 (0.1, 0.1, 0.1)이 나와서 역행렬이 있어요. 풀면 51.67, 50.30, 52.07. (가)랑 똑같아요.
등비급수 1 + q + q2 + ⋯ 이 ∣q∣ < 1 일 때만 모이는 것과 같아. 행렬 버전에서는 행 합이 1보다 작아야 하고, 행 합을 1보다 작게 만드는 일을 퇴근이나 할인이 맡는 거지.
정리 (가) V(역) = 5.50 + 0.54 V(역) + 0.27 V(시장) + 0.09 V(대학가), 풀면 (51.67, 50.30, 52.07). (나) (I−Pπ)(1,1,1)=0 이라 역행렬이 없으므로 풀리지 않고, 리턴도 한없이 커진다. (다) 풀리고, 답은 (가)와 같은 값이다. 벨먼 기대 방정식이 답을 하나 가지려면 퇴근 확률이나 할인율이 행 합을 1보다 작게 만들어야 한다.
문제 3: 가치 모델의 맞춤 검사
수학 문제를 푸는 언어 모델에 가치 모델을 붙였다(정답 1점, 오답 0점, γ = 1, 보상은 끝에만). 가치 모델은 풀이의 한 자리 s에 0.80을 매겼다. 자리 s에서 언어 모델은 다음 토큰으로 「그러므로」와 「잠깐」을 각각 0.5 확률로 고르고, 가치 모델은 「그러므로」를 붙인 자리에 0.55, 「잠깐」을 붙인 자리에 0.85를 매겼다. (가) 세 숫자는 벨먼 기대 방정식을 지키는가? (나) 셋 가운데 어느 숫자가 틀렸는지 이 방정식만으로 가려낼 수 있는가? (다) 응답의 마지막 토큰을 쓴 자리처럼, 가치를 확실히 아는 자리는 어디인가?
선생님
민준 학생, (가)는요?
김민준
「잠깐」 쪽이 0.85라 0.80보다 크고 「그러므로」 쪽은 작으니까, 평균 내면 비슷하게 0.8 근처일 것 같아요. 지키는 것 같아요.
(나)는 못 가려. 0.80이 틀려서 0.70이 맞을 수도 있고, 0.55가 너무 낮아서 0.75가 맞을 수도 있어. 방정식 하나에 미지수가 셋이니까 「셋이 서로 안 맞는다」까지만 말할 수 있어.
선생님
그래요. 그럼 (다)는요? 어디서는 숫자가 틀렸는지 바로 알 수 있죠?
이서연
응답이 끝난 자리요. 거기서는 보상이 이미 나와서 가치가 그 보상 그 자체예요. 끝에서 확실한 값을 받고, 거기서부터 방정식을 한 칸씩 거슬러 올라가며 맞추면 앞선 토큰 자리의 숫자들도 붙잡을 수 있겠네요.
김민준
조교가 채점 기준표를 맞출 때 「부분 점수의 합이 총점과 맞는지」만 봐서는 어느 칸이 틀렸는지 모르지만, 정답이 확실한 마지막 문항부터 거꾸로 맞춰 가면 되는 거랑 같네요.
정리 (가) 0.5 × 0.55 + 0.5 × 0.85 = 0.70 ≠ 0.80. 차이 0.10. (나) 벨먼 기대 방정식은 숫자들이 서로 맞는지만 따지므로 가려낼 수 없다. (다) 끝 보상이 나온 자리다. 끝에서 확실한 값을 받아 방정식을 거슬러 올라가면 앞선 토큰 자리의 가치도 붙잡을 수 있다. 끝을 모를 때 이 방정식을 어떻게 학습에 쓰는지는 아직 남은 물음이다.
