퇴근 없는 택시(γ = 0.95)에서 가치 반복의 표를 다시 보자. 표 A에서 시작하면, 가치 반복 첫 스텝의 표로 고른 그리디 정책이 벌써 「늘 승차장」이고 그 뒤로 바뀌지 않는다. 그런데 표의 값이 참값과 1원(0.001천 원) 안으로 맞기까지는 229스텝이 걸린다. 결정은 첫 스텝에 났는데 나머지 228스텝은 숫자를 다듬는 데 썼고, 정책만 알면 그 정책의 가치는 벨먼 기대 방정식으로 한 번에 풀 수 있었다. 그렇다면 정책을 풀고, 고치고, 다시 푸는 방법이 빠르지 않을까?
역사: 가치 반복 없이 곧장 최적 정책으로
시어스 카탈로그 일을 마친 하워드에게는 표를 한없이 되풀이해 고치지 않고 곧장 가장 좋은 정책으로 가는 방법이 있지 않을까 하는 의심이 남았다. 그는 지도교수 킴벌 박사(Dr. Kimball)의 지도를 받으며 여섯 달쯤 이 문제에 매달렸고, 정책을 평가하고 고치기를 되풀이하는 방법을 얻었다. 이 방법은 그의 MIT 박사 논문을 다듬은 1960년 책 『Dynamic Programming and Markov Processes』에 실렸다.
하워드는 2002년의 회고에서 아쉬움도 적었다. 시어스와 한 일은 회사의 비밀이라 책에서 그 문제를 쓸 수 없었고, 그래서 택시 문제 같은 지어낸 예로 방법을 설명했다는 것이다. 세 구역 택시도 그 책의 택시 문제를 본뜬 것인데, 원래의 응용으로 설명했다면 이 방법이 더 널리 쓰였을지 모른다고 그는 덧붙였다. 글 끝에 발표 뒤 토론의 질의응답이 붙어 있다. 한 질문자가 벨먼의 동적 계획법과 정책 공간에서의 되풀이가 1957년에 이미 나와 있었다고 짚자, 하워드는 1957년에는 이미 박사 논문을 쓰고 있었고 벨먼의 그 생각은 알지 못했다고 답했다. 다만 지도교수 킴벌 박사가 그 연구를 알았을 수 있고, 그래서 자신이 간접으로 영향을 받았을 수는 있다고 덧붙였다.
세 번의 평가
정책 반복을 「늘 배회」에서 시작하자(퇴근 없음, γ = 0.95). 한 바퀴는 두 단계로 이루어진다. 「평가」: 지금 정책의 가치를 벨먼 기대 방정식으로 푼다. 「고치기」: 그 가치로 구역마다 두 행동의 행동 가치 Qπ를 셈하고, 큰 쪽으로 바꾼다(둘이 같으면 지금 행동을 둔다). 고칠 곳이 없으면 멈춘다.
첫 평가에서 「늘 배회」의 가치는 (102.87, 101.47, 103.31)이다. 이 가치로 역의 승차장을 셈하면 104.56으로 배회 102.87보다 크고, 대학가도 승차장 104.13이 배회 103.31보다 크다. 시장은 배회 101.47, 승차장 101.43으로 배회가 근소하게 크므로 「승·배·승」으로 고친다. 둘째 평가에서 가치는 (119.93, 116.41, 119.73)으로 오르고, 이번에는 시장의 승차장이 116.99로 배회 116.41을 앞선다. 역과 대학가가 좋아지자, 손님을 역과 대학가로 데려다주는 시장 승차장의 값이 오른 것이다. 셋째 평가에서 「늘 승차장」의 가치 (122.54, 119.59, 122.37)는 가치 반복이 다가가던 V∗와 같고, 더 고칠 곳이 없어 멈춘다. 평가 세 번, 고치기 두 번이다.
평가와 고치기를 번갈아 하며 정책을 키워 가는 이 방법을 정책 반복 (평가하고 고치기를 되풀이하는 방법 / policy iteration)이라 한다. 고칠 때마다 가치가 정말 오른다는 보장은 아래 부등식이 준다.
이 부등식을 정책 개선 정리라 부르는데, 왜 성립하는지는 한 스텝씩 펼치면 보인다. 첫 스텝만 π′를 따르고 그 뒤는 π를 따르면 가정에 따라 Vπ 이상을 받는다. 둘째 스텝에서도 π′로 바꾸면 둘째 스텝의 상태에서 같은 부등식이 다시 성립하니 또 줄지 않는다. 모든 스텝을 π′로 바꾸면 그것이 Vπ′다. 택시에서 첫 고치기는 가치를 구역마다 (17.06, 14.93, 16.42), 둘째 고치기는 (2.61, 3.18, 2.64)만큼 올렸고, 줄어든 칸은 없다. 정책의 수가 유한하고 고칠 때마다 가치가 줄지 않으며, 같은 가치에서 멈추면 그 가치가 벨먼 최적 방정식을 만족하므로, 정책 반복은 유한한 바퀴 안에 최적 정책에서 멈춘다.
평가 세 번이 229스텝보다 늘 싸다는 뜻은 아니다. 평가 한 번은 연립방정식 풀기라 상태가 n개면 곱셈이 대략 n3/3번 들고, 가치 반복 한 스텝은 대략 (행동 수) × n2번이다. 상태 1,000개에 행동 둘이면 평가 한 번이 3.3억 번, 한 스텝이 200만 번으로 평가 한 번이 대략 167스텝 값이다. 그래서 실제로는 평가를 정확히 끝내지 않고 가치 반복 몇 스텝으로 대신한 뒤 고치는, 두 방법을 섞은 방식도 많이 쓴다.
ML에서: 평가하는 쪽과 고치는 쪽
정책 반복은 지금 정책이 얼마나 좋은지 재는 일과, 잰 값을 보고 정책을 낫게 고치는 일로 나뉜다. 언어 모델처럼 상태가 셀 수 없이 많으면 두 일 모두 정확히 할 수 없다. 평가는 이어 쓰기 몇 번이나 학습한 가치 모델로 어림하고, 고치기는 모든 자리의 행동을 한꺼번에 바꾸는 대신 정책의 파라미터를 조금 움직이는 것으로 대신한다. 가치를 재는 모델과 정책을 고치는 모델을 따로 두고 번갈아 학습하는 틀이 뒤에서 다시 나온다. 그때 평가가 거칠면 고치기가 엉뚱한 쪽으로 갈 수 있다는 것이 문제 12다.
문제 10: 야근할까, 정시에 갈까
직장인의 하루는 컨디션 「좋음」이나 「나쁨」으로 시작한다. 그날 해낸 일의 양(보상)은 좋음 + 야근 3, 좋음 + 정시 퇴근 2, 나쁨 + 야근 1, 나쁨 + 정시 퇴근 0.5다. 다음 날 컨디션이 좋음일 확률은 좋음 + 야근 0.3, 좋음 + 정시 0.9, 나쁨 + 야근 0.1, 나쁨 + 정시 0.6이다. 할인율은 0.9다. (가) 「늘 야근」 정책을 평가하면 V(좋음) = 14.63, V(나쁨) = 12.20이다. 이 값으로 두 상태에서 정시 퇴근의 행동 가치를 구하고 정책을 고치시오. (나) 고친 정책을 평가하고, 더 고칠 곳이 있는지 보시오.
선생님
민준 학생, 어느 정책이 나을 것 같아요?
김민준
야근이요. 컨디션이 좋든 나쁘든 야근하는 날 일을 더 많이 하잖아요. 3 대 2, 1 대 0.5요.
음, 이 값으로 한 번 더 견줘 봐야겠네요. 좋음에서 야근 18.04 대 정시 18.15, 나쁨에서 야근 15.67 대 정시 16.10이라 고칠 곳이 없어요. 평가 두 번 만에 끝났어요.
선생님
처음 정책보다 얼마나 나아졌죠?
이서연
좋음에서 14.63이 18.15로, 나쁨에서 12.20이 16.10으로요. 고친 뒤 두 상태 모두 올랐어요. 고칠 때 「오늘 양」이 아니라 「오늘 양 + 내일 컨디션의 값」으로 견줬으니까요.
김민준
시험 전날 밤새우면 그날 공부량은 많은데 다음 날 시험을 망치는 거랑 같네요. 하루치만 보면 밤샘이 이기고요.
정리 (가) Q(좋음, 정시) = 14.95 > 14.63, Q(나쁨, 정시) = 12.79 > 12.20이라 「늘 정시」로 고친다. (나) 「늘 정시」의 가치 18.15, 16.10. 다시 셈한 행동 가치(좋음: 야근 18.04, 정시 18.15 / 나쁨: 야근 15.67, 정시 16.10)로는 고칠 곳이 없어 평가 두 번에 끝난다. 고치기는 오늘 보상이 아니라 행동 가치로 한다.
문제 11: 이번 보상으로 고치면
퇴근 없는 택시(γ = 0.95)에서 「늘 승차장」 정책의 가치는 (122.54, 119.59, 122.37)이다(역, 시장, 대학가). 시장의 이번 손님 보상은 배회 4.50, 승차장 3.80이다. (가) 누군가 「시장에서는 배회가 이번에 0.70 더 버니까 배회로 고치자」며 시장만 바꿨다. 정책 개선 정리대로라면 가치가 줄 수 없다. 바꾼 정책 「승·배·승」의 가치 (119.93, 116.41, 119.73)는 정리와 어긋나는가? (나) 정책 반복을 「배·승·배」에서 시작하면 첫 평가의 시장 행동 가치가 배회 101.26, 승차장 101.24다. 둘의 차이가 0.02뿐일 때 고치기를 어떻게 하면 좋은가?
선생님
서연 학생, (가)는 정리와 어긋나나요?
이서연
어긋나요. 정리는 고치면 가치가 줄지 않는다고 했는데 세 구역 모두 2.6에서 3.2쯤 줄었어요. 정리에 단서가 빠진 것 같아요.
이번 보상 0.70을 보고 바꾸면 안 되고, 다음 구역까지 넣은 Qπ로 견줘야 하는 거예요. 배회하면 0.6 확률로 싼 시장에 남으니까요.
선생님
(나)는요?
김민준
0.02 차이면 그냥 큰 쪽, 배회로 바꾸면 되죠.
선생님
둘이 정확히 같았다면, 바꿀 때마다 같은 값의 두 행동 사이를 오갈 수 있지 않을까요?
김민준
그러면 정책이 바뀌었으니 멈추지 않고 계속 돌 수도 있겠네요. 같으면 지금 행동을 그대로 두기로 정해 두면, 바뀌지 않을 때 멈출 수 있어요. 0.02처럼 작은 차이도 반올림 오차보다 크면 큰 쪽으로 바꾸고요.
이서연
함수의 최대점을 찾을 때 「같은 값이면 움직이지 않는다」는 규칙이 없으면 평평한 곳에서 왔다 갔다 하는 거랑 같아요.
정리 (가) 어긋나지 않는다. Qπ(시장, 배회) = 119.22 < Vπ(시장) = 119.59라 정리의 가정이 깨졌다. 정책 개선 정리는 행동 가치로 고칠 때만 가치가 줄지 않음을 보장하므로, 이번 보상으로 고치면 가치가 줄 수 있다. (나) 큰 쪽(배회)으로 고치되, 행동 가치가 정확히 같으면 지금 행동을 둔다는 규칙을 둔다. 그래야 정책이 바뀌지 않을 때 멈춘다.
문제 12: 이어 쓰기 몇 번으로 고칠까
언어 모델의 한 자리에서 다음 토큰 후보가 둘이고, 실제 행동 가치(그 토큰을 쓴 뒤 결국 맞힐 확률)는 0.70과 0.75다. 정책 반복의 평가를 이어 쓰기로 한다. 토큰마다 n번씩 이어 써서 정답 비율을 재고, 고치기에서는 비율이 큰 토큰을 고른다(같으면 반반). (가) n = 16, 64, 256일 때 고치기가 더 나쁜 토큰(0.70)을 고를 확률을 구하시오. (나) (가)의 확률들이 정책 개선 정리에 대해 말하는 것은 무엇인가?
선생님
민준 학생, n = 16이면 틀릴 확률이 얼마쯤일까요?
김민준
0.75가 0.70보다 크니까 대부분 맞게 고르겠죠. 틀릴 확률은 10%쯤?
선생님
정답 비율 하나의 표준오차는 얼마였죠? 16번이면요.
김민준
√(0.7 × 0.3 / 16) = 0.115쯤이요.
김민준
차이 0.05보다 두 배나 크네요.
선생님
그럼 두 비율을 견줬을 때 순서가 뒤집힐 확률은 어떻게 어림해요?
김민준
두 비율의 차이를 보면 되겠죠. 차이의 표준오차는 √(0.7 × 0.3/16 + 0.75 × 0.25/16) = 0.158이고, 정규분포로 어림하면 차이가 0보다 작을 확률이 0.376이에요. 모의실험으로 20만 번 해 보면 0.378이고요.
이서연
64번이면 표준오차 0.079에 틀릴 확률 0.263, 256번이면 0.039에 0.102야. 256번을 써도 열 번에 한 번은 나쁜 쪽으로 고쳐.
선생님
(나)는요?
이서연
정리는 정확한 Qπ로 고칠 때의 이야기였어요. 평가가 거칠면 가정이 확률로만 성립하니까, 고친 정책이 나빠질 수도 있어요. 고치기를 믿으려면 평가부터 믿을 만해야 하고요.
김민준
조교가 답안 몇 장만 보고 채점 기준을 바꾸면, 기준이 오히려 나빠질 수 있는 거랑 같아요.
정리 (가) 차이의 표준오차 0.158, 0.079, 0.039. 틀릴 확률(정규 어림) 0.376, 0.263, 0.102. 모의실험(씨앗 0, 20만 번)은 0.378, 0.264, 0.103. (나) 정책 개선 정리는 정확한 평가를 가정한다. 이어 쓰기 몇 번으로 어림한 행동 가치로 고치면 정책이 나빠질 확률이 남고, 행동 가치의 차이가 작을수록 평가에 드는 비용이 커진다.
