구역마다 배회나 승차장 하나를 고르는 정책은 2 × 2 × 2 = 8가지이고, 벨먼 기대 방정식이 있으니 여덟 정책을 하나씩 연립방정식으로 풀어 비교하면 된다. 그런데 비교해 보면 물음이 하나 생긴다. 역에서 가장 좋은 정책과 시장에서 가장 좋은 정책이 다르면 어느 쪽을 「최선」이라 불러야 할까? 그리고 상태가 수백만 개인 문제에서는 정책을 하나하나 풀 수 없으니, 최선의 가치를 곧장 적는 식은 없을까?
역사: 엄밀하지 않은 원리
벨먼은 동적 계획법을 엄밀한 바탕 위에 세우려다가, 문제마다 같은 방법으로 함수방정식을 끌어내고 있다는 것을 알아챘다. 그는 그 방법에 「최적성의 원리(principle of optimality)」라는 이름을 붙였고, 1957년 책에 이렇게 적었다. 최적의 정책은 처음 상태와 처음 결정이 무엇이든, 남은 결정들이 처음 결정이 만든 상태에서 다시 최적의 정책을 이루는 성질을 가진다.
그림은 칸 사이 비용을 책이 정한 작은 그래프에서 칸마다 도착까지 남은 최소 비용을 뒤에서부터 셈해, 출발의 최적 경로 가운데 B2부터의 나머지가 B2에서 새로 시작한 최적 경로와 같음을 보여 준다(비용은 지어낸 값, 이 책이 직접 그림).
자서전에는 그 무렵의 대화가 남아 있다. 랜드의 동료 올리버 그로스(Oliver Gross)가 어느 날 「그 원리는 엄밀하지 않다」고 하자, 벨먼은 「물론 아니지. 정확하지도 않은걸」이라고 받았고, 좋은 원리는 직관을 이끌어야 한다고 적었다. 원리 자체는 길잡이였고, 엄밀한 일은 그 원리가 낳은 방정식들을 하나하나 다루는 데서 했다.
이서연
이름이 「원리」인데 엄밀하지 않다는 걸 본인이 받아들였다니, 수학으로는 좀 찜찜해요.
선생님
「남은 결정이 다시 최적」이라고 할 때, 최적인지 재는 값은 어디 정의돼 있었나요?
이서연
음, 그 처지에서 시작했을 때 낼 수 있는 가장 큰 값이요. 그런데 그 「가장 큰 값」이 늘 있는지부터 따져야겠네요. 선택이 끝없이 이어지면 최댓값이 없을 수도 있으니까요.
선생님
그래서 벨먼은 원리로 문제마다 방정식을 세우고, 엄밀한 일은 그 방정식들을 하나씩 따로 다루며 했어요. 모든 경우를 한 번에 덮는 증명이 손에 있었던 건 아니에요.
김민준
식부터 세우고 증명은 나중이라니, 제가 과제 하는 순서랑 같네요.
김민준
그럼 택시 여덟 정책을 다 풀어 보면, 원리 말대로 한 정책이 세 구역 모두에서 이기는지 직접 볼 수 있겠네요?
여덟 정책을 모두 풀어 보기
퇴근 1/10, γ = 1의 택시에서 여덟 정책의 가치를 모두 벨먼 기대 방정식으로 풀었다. 아래 그림의 줄 하나가 정책 하나이고, 점 셋이 세 구역의 가치다. 「승·배·승」은 역에서 승차장, 시장에서 배회, 대학가에서 승차장을 고르는 정책이다.
「늘 승차장」(승·승·승)이 역 61.65, 시장 58.70, 대학가 61.49로 세 구역 모두에서 가장 크다. 둘째는 「승·배·승」으로 각각 60.62, 57.19, 60.44다. 이번 손님의 보상만 보고 고르면(역 배회 5.50 대 승차장 6.80, 시장 4.50 대 3.80, 대학가 5.60 대 6.80) 바로 이 「승·배·승」이 나온다. 시장에서 이번 손님에게 0.70을 더 버는 배회가 하루 전체로는 1.51을 잃게 한다.
한 정책이 모든 구역에서 동시에 가장 크다는 것은 우연일까? 최적성의 원리로 보면 우연이 아니다. 역에서 최선을 다하려면, 역에서 무엇을 고르든 그 뒤에 닿는 구역에서도 최선을 다해야 한다. 그러니 구역마다 「그 구역에서 시작했을 때 최선」을 내는 행동을 모아 놓은 정책 하나가 어느 구역에서 출발해도 최선이 된다. 그 최선의 가치를 V∗라 쓰면, 한 구역의 최선은 「행동마다 이번 보상 + 다음 구역 최선의 평균」을 셈해 그중 큰 것을 고른 값이다.
가치를 「행동마다 셈한 이번 보상 + 할인한 다음 상태 최적 가치의 평균 가운데 가장 큰 것」으로 적은 첫 식을 벨먼 최적 방정식 (최선의 가치를 한 스텝으로 쪼갠 식 / Bellman optimality equation)이라 한다. 벨먼 기대 방정식과 다른 점은 하나다. 정책이 정해 둔 행동의 평균 대신, 행동 가운데 가장 큰 것을 고르는 max가 들어간다.
택시의 Q∗는 「늘 승차장」의 가치를 넣어 행동마다 셈하면 나온다.
구역
Q∗(·, 배회)
Q∗(·, 승차장)
더 큰 행동
V∗
역
60.17
61.65
승차장
61.65
시장
58.38
58.70
승차장
58.70
대학가
60.47
61.49
승차장
61.49
세 구역 모두에서 max를 내는 값이 V∗와 같으니 벨먼 최적 방정식이 맞는데, Q∗ 표가 손에 있으면 정책을 꺼내는 일은 칸마다 큰 쪽을 고르는 것뿐이다. Q∗에 대해 칸마다 가장 큰 행동을 고르는 정책을 그리디 정책(greedy policy, 지금 보이는 값이 가장 큰 쪽을 고르는 정책)이라 부른다. Q∗가 이미 그 뒤의 최선을 다 담고 있으므로, 한 스텝만 보고 고르는 그리디 정책이 곧 최적 정책이다.
로그라이크의 다익스트라 지도: 괴물이 가장 짧은 길로 쫓아오는 법
던전을 한 칸씩 걷는 로그라이크(roguelike) 게임을 해 봤다면, 벽 너머에 있던 괴물이 벽을 빙 돌아 가장 짧은 길로 다가오는 장면을 본 적이 있을지 모른다. 그 괴물은 길을 미리 찾아 두지 않고, 칸마다 적힌 숫자를 보고 이웃 칸 가운데 숫자가 가장 작은 칸으로 한 칸 옮길 뿐이다. 그런데도 벽을 빙 도는 길을 아는 듯 움직이는 것은 칸마다 적힌 숫자가 그 칸에서 플레이어까지 가장 짧게 가는 칸 수이기 때문이고, 그 숫자표가 방금 본 벨먼 최적 방정식의 해다.
로그라이크 게임 Brogue를 만들며 다듬었다는 이 방법은 게임 개발자들의 위키 RogueBasin의 글 「The Incredible Power of Dijkstra Maps」에 정리되어 있다. 이름은 최단 경로를 찾는 다익스트라 알고리즘에서 따왔는데, 다 만든 숫자표가 다익스트라 알고리즘으로 구한 플레이어까지의 최단 거리와 같기 때문이다. 만드는 법은 목표 칸(플레이어가 선 칸)에 0을, 나머지 칸에 아주 큰 수를 적는 데서 시작한다. 벽이 아닌 칸을 하나씩 보며, 위·아래·왼쪽·오른쪽 이웃 가운데 가장 작은 값보다 1 넘게 크면 「가장 작은 이웃의 값 + 1」로 고친다. 바뀌는 칸이 없을 때까지 이것을 되풀이한다.
아래 지도에서 모든 칸을 한꺼번에 고치는 판을 되풀이하면, 열 판 뒤로는 바뀌는 칸이 없다. 괴물 칸의 숫자는 9다. 벽을 무시하고 가로세로로 센 거리는 5칸이지만, 벽을 돌아야 하는 실제 스텝 수가 9다. 괴물은 9 → 8 → 7 → … → 1 → 0을 따라 9스텝 만에 플레이어에게 닿는다.
이 지도는 한 스텝마다 보상 −1, 할인율 γ = 1, 플레이어 칸에 닿으면 끝나는 MDP의 벨먼 최적 방정식을 푼 것이다. 이동이 확실해서(누른 방향으로 꼭 간다) 「다음 상태 가치의 평균」이 이웃 한 칸의 값이 되므로, 방정식은 V∗(s)=maxa[−1+V∗(s′)] 이 된다. 지도의 숫자를 −V∗(s) 로 읽으면 max가 min으로 바뀌어 「지도의 숫자 = 1 + 이웃 숫자 가운데 가장 작은 것」이 되는데, 이것이 위의 고치는 규칙이다(스크립트로 두 표가 모든 칸에서 같다는 것을 확인했다). 괴물이 숫자가 가장 작은 이웃으로 옮겨 가는 것은 V∗에 대한 그리디 정책이다. 괴물이 한 칸 앞만 보고도 가장 짧은 길로 오는 것은 택시의 Q∗ 표와 같은 이유에서다. 칸마다의 숫자가 그 뒤의 최선을 이미 다 담고 있다. RogueBasin의 글은 괴물을 달아나게 하는 지도도 모든 값에 −1.2쯤을 곱한 뒤 같은 되풀이로 다시 훑어 만드는데, 목표를 바꾸면 같은 방정식이 다른 행동을 낳는다는 것을 보여 준다.
비유가 깨지는 곳은 「누른 방향으로 꼭 간다」는 가정이다. 플레이어에게 가는 길이 둘인데, 4칸짜리 지름길은 얼음이라 디딜 때마다 확률 0.5로 미끄러져 제자리에 남고, 돌아가는 길은 마른 땅 6칸이라고 하자. 다익스트라 지도는 4 < 6이라 얼음 길을 고른다. 벨먼 기대 방정식으로 얼음 한 칸을 셈하면 V(s)=−1+0.5V(다음칸)+0.5V(s), 정리하면 V(s)=V(다음칸)−2 라서 한 칸에 평균 2스텝이 든다. 얼음 길은 평균 8스텝으로 마른 길 6스텝보다 길다. 미끄러질 확률이 1/3이면 얼음 길도 평균 4 ÷ (2/3) = 6스텝으로 마른 길과 같아진다. 전이 확률이 끼면 「가장 작은 이웃 + 1」로는 모자라고, 다음 상태들의 가치를 전이 확률 P로 평균하는 벨먼 최적 방정식 그 자체를 풀어야 한다.
ML에서: 그리디 정책과 그리디 디코딩
언어 모델에서 「그리디」라는 말은 이미 쓰이는데, 그리디 디코딩은 자리마다 확률 π(a∣s)가 가장 큰 토큰을 고르는 생성 방식이다. 이름은 같지만 무엇에 대해 그리디한지가 다르다. 그리디 디코딩은 정책 자신의 확률에 대해, Q∗의 그리디 정책은 「그 토큰을 쓴 뒤 최선을 다할 때 결국 받을 보상」에 대해 그리디하다. 가장 그럴듯한 토큰이 끝 보상을 가장 크게 받는 토큰이라는 보장은 없는데, 두 그리디가 얼마나 다른 답을 내는지가 문제 6이다.
문제 4: 갈아타는 길
집에서 학교까지 두 번 갈아타는데, 첫 구간은 환승역 X(10분)나 Y(14분)로 간다. X에서 둘째 환승역 Z까지 12분, W까지 11분이고, Y에서 Z까지 4분, W까지 7분이다. Z에서 학교까지 6분, W에서 학교까지 9분이다. (가) 구간마다 가장 짧은 것을 고르면 몇 분 걸리는가? (나) 가장 빠른 길과 그 시간을 구하시오. (다) 「Y에서 학교까지의 최단 시간」을 먼저 구해 두면 무엇이 편해지는가?
선생님
서연 학생, (가)는요?
이서연
첫 구간에서 X(10분), X에서 W(11분), W에서 학교(9분)니까 30분이에요.
선생님
민준 학생은 (나)를 어떻게 풀었어요?
김민준
길이 네 개뿐이니까 다 더했어요. X-Z 28분, X-W 30분, Y-Z 24분, Y-W 30분. Y-Z로 24분이요.
선생님
환승역이 단계마다 열 개씩이고 단계가 다섯이면 길은 몇 개죠?
김민준
10⁵ = 10만 개요. 다 더하기는 힘들겠네요.
이서연
뒤에서부터 하면 돼요. Z에서 학교 6분, W에서 9분은 정해져 있어요. 그러면 X에서 학교까지 최단은 min(12 + 6, 11 + 9) = 18분, Y에서는 min(4 + 6, 7 + 9) = 10분. 집에서는 min(10 + 18, 14 + 10) = 24분이에요.
선생님
그래요. 그게 (다)예요. Y에서 학교까지의 최단 10분을 알면 Y에 어떻게 왔는지는 더 볼 필요가 없어요.
김민준
X를 먼저 고른 게 4분 이득처럼 보였는데, X에서 학교까지가 8분 더 걸려서 지는 거네요. 첫 구간만 보면 안 되는 이유가 「남은 최단 시간」에 다 들어 있어요.
김민준
로그라이크 괴물의 지도랑 같네요. 학교 칸에 0을 적고 거꾸로 숫자를 채워 두면, 집에서는 숫자가 작아지는 쪽으로만 가면 되니까요.
이서연
거기는 칸 하나가 늘 1스텝이고, 여기는 구간마다 걸리는 분이 다를 뿐이야. 「가장 작은 이웃 + 1」 대신 「이웃까지 걸리는 시간 + 이웃의 숫자」 가운데 가장 작은 것을 적으면 돼. 집은 min(10 + 18, 14 + 10) = 24.
이서연
수열의 점화식이랑 같아요. 앞의 항을 다 몰라도 바로 뒤 항만 알면 셈이 되니까요.
정리 (가) 10 + 11 + 9 = 30분. (나) 집 → Y → Z → 학교, 24분. 환승역마다 「여기서 학교까지의 최단 시간」(Z 6, W 9, X 18, Y 10)을 뒤에서부터 적으면 집은 min(10 + 18, 14 + 10) = 24분. (다) Y에서 학교까지의 최단 시간 10분이 Y 뒤의 모든 길을 대신하므로, 길을 모두 늘어놓지 않고 갈림목 수만큼만 셈한다. 첫 구간만 보고 고르면 남은 시간이 긴 X로 간다.
문제 5: 할인율이 바꾸는 최선
퇴근 1/10의 세 구역 택시에서 할인율을 γ = 0.5로 낮춘다. 여덟 정책을 모두 풀어 보면 최적 정책은 「승·배·승」이고 그 가치는 역 11.855, 시장 9.082, 대학가 11.760이다. (가) 시장에서 두 행동의 Q∗를 구하시오. 시장 배회의 이번 보상은 4.50, 다음 구역 확률은 (0.27, 0.54, 0.09, 퇴근 0.10), 시장 승차장은 3.80과 (0.36, 0.18, 0.36, 퇴근 0.10)이다. (나) 「늘 승차장」 정책의 역의 가치는 11.816이고, 이 정책도 역에서는 최적 정책과 같은 행동(승차장)을 고른다. 그런데 왜 역의 가치가 더 작은가? 최적성의 원리로 설명하시오.
γ = 1에서는 시장 승차장이 58.70으로 배회 58.38보다 컸는데, 0.5에서는 뒤집혔네. 앞날을 덜 치니까 이번 손님 0.70 차이가 커 보이는 거야.
선생님
(나)는요? 서연 학생.
이서연
역에서 고르는 건 둘 다 승차장이니까 역의 가치도 같아야 할 것 같아요.
선생님
역에서 승차장에 선 뒤 시장에 닿으면, 두 정책은 시장에서 각각 무엇을 하죠?
이서연
최적 정책은 배회, 「늘 승차장」은 승차장이요. 시장에서 하는 일이 달라요.
선생님
시장에서 하는 일이 역의 가치에는 어떻게 들어와요?
이서연
역에서 승차장에 서면 0.18 확률로 시장에 닿으니까, 역의 가치에 「시장에서의 가치」가 그만큼 섞여요. 거기서 최선이 아닌 행동을 하면 역의 값까지 깎이고요.
이서연
첫 결정이 같아도 남은 결정이 최적이 아니면 최적이 아닌 거네요.
선생님
그게 최적성의 원리예요. 첫 결정 뒤에 닿는 모든 상태에서 남은 결정이 다시 최적이어야 해요.
김민준
1번 문제를 잘 풀어도 그 답을 쓰는 2번에서 실수하면 1번 배점까지 날아가는 시험이랑 같네요.
정리 (가) Q∗(시장, 배회) = 9.082, Q∗(시장, 승차장) = 8.868. γ = 0.5에서는 시장의 최선이 배회로 바뀐다. (나) 11.816 < 11.855. 역에서 같은 행동을 골라도 뒤에 닿는 시장에서 최선이 아닌 행동을 하면 그 손실이 확률만큼 역의 가치로 올라온다. 최적이려면 첫 결정 뒤 모든 상태의 결정이 다시 최적이어야 한다.
문제 6: 가장 그럴듯한 토큰, 가장 좋은 토큰
언어 모델이 수학 문제의 답을 쓰기 시작하면서 첫 토큰으로 「답은」을 0.7, 「먼저」를 0.3 확률로 고른다. 「답은」 뒤에는 곧바로 숫자를 쓰고, 그 숫자가 정답일 확률은 0.40이다. 「먼저」 뒤에는 둘째 토큰으로 「식을」과 「답을」을 반반으로 고르고, 「식을」로 이어 가면 결국 정답일 확률이 0.9, 「답을」로 이어 가면 0.5다(정답 1점, 오답 0점, γ = 1). (가) 그리디 디코딩은 어떤 길로 가고, 정답일 확률은? (나) 첫 자리의 두 토큰에 대해 지금 정책의 행동 가치와 Q∗를 구하시오. (다) 첫 자리의 가치를 지금 정책과 최선의 경우로 비교하시오.
선생님
민준 학생, (가)는요?
김민준
첫 자리에서 0.7인 「답은」을 고르고 바로 숫자를 쓰니까 정답 확률 0.40이에요.
선생님
(나)에서 「먼저」의 행동 가치는요?
김민준
「먼저」 뒤에 가장 좋은 건 「식을」의 0.9니까 0.9요.
선생님
지금 정책은 「먼저」 뒤에 무엇을 고르죠?
김민준
반반이요. 그러면 지금 정책의 행동 가치는 0.5 × 0.9 + 0.5 × 0.5 = 0.70이네요.
0.40이요. 가장 그럴듯한 토큰을 따라가서요. 그런데 Q∗의 그리디 정책은 확률이 0.3밖에 안 되는 「먼저」를 골라요.
김민준
둘 다 「그리디」인데 기준이 달라요. 하나는 지금 정책의 확률, 하나는 결국 받을 보상. 두 그리디가 같아지려면 정책의 확률이 끝 보상의 좋고 나쁨을 이미 알고 있어야 하네요.
선생님
그래요. 강화학습이 정책을 바꾸는 일은 결국 두 그리디를 가까이 붙이는 일로도 읽혀요.
김민준
보고서를 쓸 때 가장 먼저 떠오른 문장으로 시작하면 빨리 쓰긴 하는데, 개요부터 잡는 게 결국 점수가 잘 나오는 거랑 같아요.
정리 (가) 「답은」 → 숫자, 정답 확률 0.40. (나) 「답은」: 지금 정책의 행동 가치와 Q∗ 모두 0.40. 「먼저」: 지금 정책 0.5 × 0.9 + 0.5 × 0.5 = 0.70, Q∗ = 0.90. (다) 지금 정책 0.49, 최선 0.90. 정책의 확률에 대한 그리디(그리디 디코딩)와 Q∗에 대한 그리디(최적 정책)는 다른 길로 간다.
