축약 사상: 가치 반복은 왜 한 점에 모이나

벨먼 기대 방정식은 연립일차방정식이라 역행렬로 풀었지만, 벨먼 최적 방정식에는 max가 들어 있어 일차식이 아니고, 역행렬로 풀 수 없다. 택시는 정책이 여덟뿐이라 모두 풀어 비교했지만, 정책을 모두 푸는 방법이 늘 통하지는 않는다. 그렇다면 아무 표에서 시작해 식의 오른쪽을 계산하고, 나온 값을 다시 오른쪽에 넣는 일을 되풀이하면 어떨까? 그 되풀이가 정말 답에 닿을까, 처음에 넣은 표가 다르면 다른 곳에 닿지는 않을까?

역사: 진공관으로 돌린 되풀이

이 되풀이를 실제 장사에 처음 쓴 사람 가운데 하나로 로널드 하워드(Ronald Howard)가 꼽힌다. MIT에서 박사 과정을 밟던 무렵, 그는 컨설팅 회사 아서 D. 리틀(Arthur D. Little)과 함께 백화점 시어스 로벅(Sears, Roebuck and Company)의 우편 주문 카탈로그 일을 했다. 손님에게 카탈로그를 어떻게 보낼지가 행동이었고, 손님을 50개쯤의 상태로 나누어 철마다 상태가 옮겨 간다고 보았다. 한 번 옮겨 갈 때의 보상은 그 옮김에서 나는 이익에서 보낸 카탈로그의 비용을 뺀 값이었다. 옮겨 갈 확률은 손님 주소판을 다루던 주소 인쇄 장치(Addressograph)의 기록을 특별히 돌려 셈했다. 하워드는 그 기록이 있었기에 이 방법 전체가 가능했다고 적었다.

최적의 발송 정책은 표를 되풀이해 고치는 방법으로 구했다. 컴퓨터가 아직 진공관으로 돌던 때라 한 번 돌리는 데 시간이 꽤 걸렸지만 비용은 감당할 만했다고 한다. 나온 정책은 이번 철의 수익을 가장 크게 하는 정책이 아니라, 그 수익과 손님이 다음 철에 옮겨 갈 상태 사이에서 균형을 잡는 정책이었다. 예측된 수익 개선은 몇 퍼센트였지만 금액으로는 해마다 수백만 달러였고, 전체 손님에게 적용한 결과도 예측과 가깝게 맞았다고 하워드는 회고했다(『Operations Research』 2002년 50주년 특집호에 다시 실린 글. 처음 실린 곳은 1978년 퍼터먼(Martin Puterman)이 엮은 책).

두 처음 표

되풀이가 어떻게 움직이는지 택시로 보자. 이번에는 퇴근이 없는 택시에 할인율 $\textcolor{#7a1f5a}{\gamma}$ 를 둔다. 손님마다 1/10 확률로 퇴근하는 하루가 할인율 0.9와 평균이 같았다는 것을 떠올리면, $\textcolor{#7a1f5a}{\gamma}$ = 0.95는 대략 20스텝 앞까지 보는, 퇴근이 더 늦은 하루에 해당한다. 이 설정에서도 최적 정책은 「늘 승차장」이고 $\textcolor{#00897b}{V^*}$ = (122.54, 119.59, 122.37)이다(순서는 역, 시장, 대학가).

벨먼 최적 방정식의 오른쪽을 표 하나에 적용하는 일을 연산자로 적자. 표 $\textcolor{#00897b}{V}$ 를 받아 새 표를 내놓는 이 연산을 벨먼 연산자라 부르고 $\textcolor{#ff0059}{\mathcal{T}}$ (필기체 T)로 쓴다. 두 표 A = (0, 0, 0)과 B = (200, 50, 120)에서 시작해 $\textcolor{#ff0059}{\mathcal{T}}$ 를 거듭 적용했다. A에 한 번 적용하면 (6.80, 4.50, 6.80), 곧 구역마다 이번 손님의 보상 가운데 큰 쪽이 나온다.

스텝 $k$	0	1	2	3	10	50	100
두 표의 가장 큰 칸 차이	200	147.25	135.84	128.33	89.29	11.47	0.88
앞 스텝 대비	해당 없음	0.736	0.923	0.945	0.950	0.950	0.950

두 표의 차이는 스텝마다 줄고, 몇 스텝 뒤부터는 꼭 0.95배씩 준다. 200스텝 뒤 두 표는 A가 (122.538, 119.586, 122.370), B가 (122.543, 119.591, 122.375)로 소수 둘째 자리까지 같고, $\textcolor{#00897b}{V^*}$ 와 같다. 처음 표가 달라도 같은 곳에 닿는다. 이렇게 벨먼 최적 방정식의 오른쪽을 되풀이해 적용해 $\textcolor{#00897b}{V^*}$ 를 찾는 방법을 가치 반복(value iteration)이라 한다.

배율이 왜 하필 0.95인지는 한 스텝을 세 조각으로 쪼개 보면 보인다. 두 표의 칸 차이 가운데 가장 큰 것이 200이라 하자. 첫째, 다음 구역의 확률로 평균을 내면 평균의 차이는 가장 큰 칸 차이를 넘을 수 없다. 표 A와 B로 여섯 (구역, 행동) 칸의 평균 차이를 셈하면 147, 114, 102, 138, 122, 155로 모두 200 이하다. 둘째, 그 평균에 $\textcolor{#7a1f5a}{\gamma}$ = 0.95를 곱하는데, 이번 보상은 두 표에 똑같이 더해지니 차이에 들어가지 않는다. 셋째, 행동 둘 가운데 큰 것을 고르면, 두 묶음의 최댓값끼리의 차이는 짝지은 차이 가운데 가장 큰 것을 넘지 않는다. 세 조각을 거치면 새 차이는 0.95 × 200 = 190 이하이고, 실제 차이는 147.25였다.

\lVert \textcolor{#ff0059}{\mathcal{T}}\textcolor{#00897b}{V} - \textcolor{#ff0059}{\mathcal{T}}\textcolor{#00897b}{U} \rVert_\infty \le \textcolor{#7a1f5a}{\gamma}\, \lVert \textcolor{#00897b}{V} - \textcolor{#00897b}{U} \rVert_\infty, \qquad \lVert \textcolor{#00897b}{V_k} - \textcolor{#00897b}{V^*} \rVert_\infty \le \textcolor{#7a1f5a}{\gamma}^k\, \lVert \textcolor{#00897b}{V_0} - \textcolor{#00897b}{V^*} \rVert_\infty

\small\begin{array}{ll} \textcolor{#ff0059}{\mathcal{T}} & \text{벨먼 연산자: }(\textcolor{#ff0059}{\mathcal{T}}\textcolor{#00897b}{V})(\textcolor{#0093b8}{s}) = \max_{\textcolor{#1c9c60}{a}} \big[\textcolor{#d9670b}{r}(\textcolor{#0093b8}{s}, \textcolor{#1c9c60}{a}) + \textcolor{#7a1f5a}{\gamma} \sum_{\textcolor{#0093b8}{s'}} \textcolor{#8877ff}{P}(\textcolor{#0093b8}{s'} \mid \textcolor{#0093b8}{s}, \textcolor{#1c9c60}{a}) \textcolor{#00897b}{V}(\textcolor{#0093b8}{s'})\big] \\ \textcolor{#00897b}{V},\ \textcolor{#00897b}{U} & \text{아무 가치 표 두 개 (택시: 구역마다 한 칸)} \\ \lVert \cdot \rVert_\infty & \text{무한 노름: 칸마다의 차이의 크기 가운데 가장 큰 것} \\ \textcolor{#00897b}{V_k},\ \textcolor{#00897b}{V^*} & \text{처음 표에 }\textcolor{#ff0059}{\mathcal{T}}\text{를 }k\text{번 적용한 표, 그리고 최적 가치} \\ \textcolor{#7a1f5a}{\gamma} & \text{할인율 (이 부등식의 배율)} \end{array}

두 표의 거리를 일정한 배율(1보다 작은 수) 이하로 줄이는 연산을 축약 사상 (거리를 일정 비율 이상 줄이는 사상 / contraction mapping)이라 한다. 첫 부등식은 벨먼 연산자가 배율 $\textcolor{#7a1f5a}{\gamma}$ 의 축약 사상이라는 말이고, $\textcolor{#00897b}{V^*}$ 는 $\textcolor{#ff0059}{\mathcal{T}}\textcolor{#00897b}{V^*} = \textcolor{#00897b}{V^*}$ , 곧 연산자를 적용해도 바뀌지 않는 표다. 둘째 부등식은 첫 부등식에 $\textcolor{#00897b}{U} = \textcolor{#00897b}{V^*}$ 를 넣고 $k$ 번 되풀이한 것으로, 처음 오차가 얼마든 $k$ 스텝 뒤 오차는 $\textcolor{#7a1f5a}{\gamma}^k$ 배 이하가 된다. 오차를 처음의 1/1000로 줄이려면 $\textcolor{#7a1f5a}{\gamma}^k \le 1/1000$ , 곧 $k \ge \ln 1000 / \ln(1/\textcolor{#7a1f5a}{\gamma})$ 스텝이면 넉넉하다.

$\textcolor{#7a1f5a}{\gamma}$	대략 몇 스텝 앞까지 보나 $1/(1-\textcolor{#7a1f5a}{\gamma})$	1/1000 스텝 수 상한 $\ln 1000 / \ln(1/\textcolor{#7a1f5a}{\gamma})$	택시 두 표의 실제 스텝 수
0.5	2	9.97	10
0.8	5	30.96	30
0.95	20	134.67	129

멀리 볼수록 되풀이가 느려서, 상한의 스텝 수는 1/(1 − $\textcolor{#7a1f5a}{\gamma}$ )에 거의 비례해 늘어난다. 앞날을 많이 칠수록 먼 곳의 정보가 한 스텝에 한 칸씩 전해져야 하기 때문이다.

아래 위젯에서 할인율과 처음 표를 바꿔 가며 두 표의 차이를 보자. 세로가 로그 눈금이라, 일정한 배율로 줄어드는 차이는 곧은 내리막으로 보인다.

ML에서: 표가 아닌 가치 모델의 되풀이

언어 모델에 가치 모델을 붙여 학습할 때는 한 자리의 목표값을 흔히 「이번 보상 + 다음 자리에 대한 지금 모델의 예측」으로 둔다. 벨먼 연산자를 한 번 적용한 값을 목표로 삼는 것인데, 축약의 보장은 표의 칸을 모두 새 값으로 바꿔 넣을 때의 이야기다. 가치 모델은 신경망이라 한 자리를 고치면 다른 자리의 예측도 함께 움직이고, 목표값 자체도 그 모델이 낸다. 그때도 되풀이가 한 점으로 모이는지는 이 절의 부등식이 말해 주지 않는다.

문제 7: 용돈 통장

민과 서는 매달 통장 잔액의 절반을 쓰고, 달마다 10만 원을 새로 받는다(다음 달 잔액 = 0.5 × 이번 달 잔액 + 10). 처음 잔액은 민이 0원, 서가 100만 원이다. (가) 1, 2, 3달 뒤 두 사람의 잔액과 차이를 구하시오. (나) 두 잔액은 어디로 가는가? (다) 차이가 0.1만 원 이하가 되려면 몇 달이 걸리는가?

민준 학생, 서는 100만 원을 들고 시작했어요. 몇 달 뒤에도 서가 더 부자일까요?

당연하죠. 둘 다 같은 규칙인데 서가 100만 원 앞서 있으니까 그 차이는 계속 남아요.

한 달 뒤에 두 사람의 잔액을 셈해 보면요?

민은 0.5 × 0 + 10 = 10, 서는 0.5 × 100 + 10 = 60이요. 차이가 50이네요.

반으로 줄었어요. 두 달 뒤는 15와 40으로 25, 세 달 뒤 17.5와 30으로 12.5요.

10만 원은 둘 다 똑같이 받으니까 차이에 안 들어가고, 차이에는 0.5만 곱해져. 그러니까 매달 반으로 줄어. 둘 다 x = 0.5x + 10 을 만족하는 x = 20만 원으로 가.

(다)는요?

100 × 0.5ᵏ ≤ 0.1 이면 0.5ᵏ ≤ 1/1000 이라 k ≥ ln 1000 / ln 2 = 9.97, 열 달이에요. 실제로 열 달 뒤 차이가 0.0977만 원이에요.

처음에 얼마를 들고 있었는지는 열 달이면 거의 잊히네요. 학기 초에 과제를 몰아서 해 둬도, 매주 절반만 남기고 새로 받는 과제가 쌓이면 학기 말엔 다 비슷해지는 거랑 같아요.

정리 (가) 1달 10과 60(차이 50), 2달 15와 40(25), 3달 17.5와 30(12.5). (나) 둘 다 x = 0.5x + 10의 해 20만 원으로 간다. 똑같이 더해지는 10만 원은 차이에 들어가지 않고, 차이에는 배율 0.5만 곱해진다. (다) ln 1000 / ln 2 = 9.97이라 10달. 배율이 1보다 작은 되풀이는 처음을 잊는다.

문제 8: 퇴근이 할인율 노릇을 하나

세 구역 택시에서 표 A = (0, 0, 0)과 B = (200, 50, 120)에 벨먼 연산자 $\textcolor{#ff0059}{\mathcal{T}}$ 를 거듭 적용한다. (가) 손님마다 1/10 확률로 퇴근하고 $\textcolor{#7a1f5a}{\gamma}$ = 1이면, 두 표의 차이는 스텝마다 몇 배씩 줄어드는가? 위젯의 「문제 8 설정 불러오기」로 확인하라. (나) 퇴근도 할인도 없으면( $\textcolor{#7a1f5a}{\gamma}$ = 1) 어떻게 되는가? 표 A와, 모든 칸이 100인 표로도 해 보라.

(가)부터요. 서연 학생?

\textcolor{#7a1f5a}{\gamma}

= 1이면 할인이 없으니까 축약이 아니에요. 줄어들지 않을 것 같아요.

벨먼 연산자 안에서 다음 구역 가치에 곱해지는 수를 다 모으면 무엇이죠?

\textcolor{#7a1f5a}{\gamma}

곱하기 다음 구역의 확률인데, 퇴근이 있으니까 확률의 합이 0.9예요. 평균 내는 조각에서 이미 0.9가 곱해지네요.

위젯에서도 그렇게 나오는지 볼까요. 민준 학생?

앞 스텝 대비 비율이 0.6975, 0.8739로 가다가 0.9000에 붙어요.

(나)는요?

퇴근도 없고 할인도 없으니 배율이 1이에요. 그래도 줄기는 줄던데요? 위젯에서 200이 155, 150.53으로 내려가요.

50스텝 뒤에는요? 그리고 표 A와 모두 100인 표로 하면요?

149.17에서 멈춰요. 0으로 안 가요. 모두 100인 표는 처음부터 끝까지 차이가 100 그대로고요.

모두 100인 표가 이상해요. 모든 칸에 같은 수를 더한 표는 확률로 평균 내도 같은 수만큼 더해지잖아요.

max를 하면요?

max를 해도 그대로예요. 그래서 차이가 안 줄어요. 차이의 모양은 잊는데 높이는 못 잊는 거예요.

A와 B도 결국 칸마다 같은 차이 149.17로 굳는 거네.

그래요. 퇴근도 할인도 없으면 표의 값 자체도 열 스텝 뒤 61.8쯤에서 쉰 스텝 뒤 305쯤으로 한없이 커져요. 붙잡을 한 점이 없는 거예요.

행렬로 말하면 행 합이 1인 확률 행렬은 (1, 1, 1)을 그대로 두니까, 그 방향의 차이는 줄일 수 없어요. 고윳값 1이 하나 남는 거죠.

정리 (가) 0.9배씩. 퇴근 확률 1/10이 「다음 구역 가치에 곱하는 수」를 0.9로 만들어 할인율 0.9처럼 다음 구역 가치를 0.9배로 줄인다. (나) 차이가 0으로 가지 않는다. A와 B의 차이는 149.17에서 멈추고, 모든 칸이 100만큼 다른 두 표는 차이 100이 그대로 남는다. 확률로 평균 내기만 하면 모든 칸에 같은 수를 더한 차이는 줄지 않으므로, 퇴근이든 할인이든 1보다 작은 배율이 있어야 벨먼 연산자가 축약 사상이 된다.

문제 9: 할인율 0.99와 길이 제한

(가) 언어 모델 강화학습의 한 설정이 $\textcolor{#7a1f5a}{\gamma}$ = 0.99를 쓴다. 표로 가치 반복을 한다면 오차를 처음의 1/1000로 줄이는 데 상한 식으로 몇 스텝이 필요한가? (나) 다른 설정은 $\textcolor{#7a1f5a}{\gamma}$ = 1이고 응답 길이를 3토큰으로 제한한다. 토큰은 두 종류이고 정책은 반반으로 고르며, 3토큰을 쓴 뒤 받는 끝 보상은 여덟 가지 응답에 대해 (1, 1, 1, 0, 0, 0, 0, 0)이다(첫 토큰이 첫째 종류이면 앞의 넷). 모든 자리의 가치를 0으로 두고, 벨먼 기대 방정식의 오른쪽을 모든 자리에 한꺼번에 거듭 적용하면(가치 반복과 같은 되풀이를 max 대신 정책의 평균으로 한다) 첫 자리의 가치는 몇 스텝 만에 정확해지는가? 이때 축약 사상의 부등식은 쓸모가 있는가?

(가)는 민준 학생이 셈해 볼까요.

ln 1000 / ln(1/0.99) = 687.32니까 688스텝이요. 0.95일 때 135스텝이었는데 다섯 배가 넘네요.

(나)는요?

\textcolor{#7a1f5a}{\gamma}

= 1이면 배율이 1이에요.

그럼 축약이 아니니까 아까 퇴근 없는 택시처럼 모이지 않겠죠.

퇴근 없는 택시는 끝이 없었어요. 이 응답에는 끝이 있나요?

3토큰에서 반드시 끝나요. 그런데 끝이 있다는 게 되풀이에 어떻게 쓰이는지는 아직 모르겠어요.

되풀이 첫 스텝에 정확해지는 자리가 있을까요?

음… 2토큰을 쓴 자리들이요. 거기서는 다음이 바로 끝 보상이라, 평균만 내면 정확한 값이 돼요.

그다음 스텝은요?

1토큰 자리가 정확한 값을 받아서 정확해지고, 셋째 스텝에 첫 자리가 정확해져요.

돌려 보니까 첫 자리 값은 0, 0, 0.375로 가서 셋째 스텝에 0.375에 닿고 그 뒤로 안 바뀌어요.

끝이 있으면 끝에서 정확한 값이 한 칸씩 거슬러 올라오니까, 길이만큼 되풀이하면 끝나네요. 배율 부등식은 0.375까지 가는 동안 아무 말도 안 해 주고요.

그래요. 끝나는 에피소드에서는 「길이만큼이면 정확해진다」는 다른 보장이 일해요. 할인 있는 끝없는 문제에서는 축약 사상의 부등식이 일하고요.

유한 수열의 합은 항 수만큼 더하면 끝나고, 무한급수는 수렴 판정이 필요한 것과 같아요.

정리 (가) ln 1000 / ln(1/0.99) = 687.32, 688스텝. 멀리 보는 할인율일수록 가치 반복이 느리다. (나) 3스텝. 첫 자리 값은 0, 0, 0.375로 셋째 스텝에 참값 0.375에 닿는다. $\textcolor{#7a1f5a}{\gamma}$ = 1이라 축약 사상의 부등식은 쓸 수 없지만, 응답이 길이 3에서 반드시 끝나므로 끝의 정확한 값이 한 스텝에 한 칸씩 거슬러 올라와 길이만큼의 스텝이면 정확해진다.