구역마다 배회나 승차장 하나를 고르는 정책은 2 × 2 × 2 = 8가지이고, 벨먼 기대 방정식이 있으니 여덟 정책을 하나씩 연립방정식으로 풀어 비교하면 된다. 그런데 비교해 보면 물음이 하나 생긴다. 역에서 가장 좋은 정책과 시장에서 가장 좋은 정책이 다르면 어느 쪽을 「최선」이라 불러야 할까? 그리고 상태가 수백만 개인 문제에서는 정책을 하나하나 풀 수 없으니, 최선의 가치를 곧장 적는 식은 없을까?
역사: 엄밀하지 않은 원리
벨먼은 동적 계획법을 엄밀한 바탕 위에 세우려다가, 문제마다 같은 방법으로 함수방정식을 끌어내고 있다는 것을 알아챘다. 그는 그 방법에 「최적성의 원리(principle of optimality)」라는 이름을 붙였고, 1957년 책에 이렇게 적었다. 최적의 정책은 처음 상태와 처음 결정이 무엇이든, 남은 결정들이 처음 결정이 만든 상태에서 다시 최적의 정책을 이루는 성질을 가진다.
자서전에는 그 무렵의 대화가 남아 있다. 랜드의 동료 올리버 그로스(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∗가 이미 그 뒤의 최선을 다 담고 있으므로, 한 스텝만 보고 고르는 그리디 정책이 곧 최적 정책이다.
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분 더 걸려서 지는 거네요. 첫 구간만 보면 안 되는 이유가 「남은 최단 시간」에 다 들어 있어요.
이서연
수열의 점화식이랑 같아요. 앞의 항을 다 몰라도 바로 뒤 항만 알면 셈이 되니까요.
정리 (가) 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∗에 대한 그리디(최적 정책)는 다른 길로 간다.
