강가 산책로의 두 방법은 모두 열 스텝에 한 번꼴로 아무 쪽으로나 걸었다. 왓킨스와 다얀의 증명도 「모든 상태에서 모든 행동을 거듭 시험한다」는 조건을 붙였다. 그런데 무작위 스텝은 값을 치러서, Q-러닝은 그 무작위 스텝 때문에 에피소드 네 번에 한 번꼴로 강물에 빠졌다. 아예 시험하지 않으면 어떻게 되고, 시험한다면 얼마나 자주 해야 할까?
같은 고민은 점심시간마다 한다. 회사 근처 식당 다섯 곳을 한 번씩 가 보고 나면, 가장 맛있었던 곳만 계속 가고 싶다. 그런데 그 한 끼가 그 식당의 평소 맛이었을까? 마침 주방장이 쉬는 날이었다면, 가장 좋은 식당을 한 번의 나쁜 기억 때문에 다시는 안 가게 된다.
역사: 환자를 덜 잃는 배정에서 슬롯머신까지
이 고민을 처음 수학으로 다룬 사람으로 흔히 윌리엄 톰프슨(William R. Thompson)이 꼽힌다. 예일 대학 병리학과의 톰프슨은 1933년 『Biometrika』에 「On the likelihood that one unknown probability exceeds another in view of the evidence of two samples」를 냈다. 그는 두 치료법을 비교하는 연구를 어떻게 계획할지를 물었다. 관찰을 많이 모은 뒤에야 판단하는 대신, 지금까지의 적은 자료로도 「첫째 치료가 더 나을 확률 P」를 셈해, 다음 환자들 가운데 몇 명에게 어느 치료를 줄지 나누자고 했다. 예를 들어 환자의 P만큼에게 첫째 치료를, 나머지에게 둘째 치료를 주면, 한쪽을 일찍 버리지도 않으면서 못한 치료를 받는 환자를 꽤 줄일 수 있다고 적었다. 자료가 천천히 쌓이거나 환자 한 명 한 명이 소중할수록 이 일이 중요하다는 것이다.
1952년에는 허버트 로빈스(Herbert Robbins)가 『미국 수학회 회보(Bulletin of the American Mathematical Society)』에 「Some aspects of the sequential design of experiments」를 냈다. 그는 미리 정한 수만큼 샘플을 모은 뒤 분석하던 통계를, 앞의 결과를 보며 다음 샘플을 어디서 뽑을지 고르는 설계로 넓히자고 했다. 그 본보기로 내놓은 것이 두 모집단 가운데 어느 쪽에서 다음 샘플을 뽑을지 고르는 문제다. 이런 문제는 뒤에 슬롯머신에 빗대 불리게 된다. 팔이 하나인 슬롯머신의 별명이 「외팔이 강도(one-armed bandit)」라서, 팔이 여럿인 기계 가운데 어느 팔을 당길지 고르는 문제를 「여러 팔 슬롯머신 문제(multi-armed bandit)」라 부른다. 이 문제가 얼마나 풀기 어려웠는지를 두고는, 2차 대전 때 연합국 과학자들이 이 문제에 머리를 너무 빼앗겨 「지적 사보타주의 궁극 무기로 독일 상공에 떨어뜨리자」는 말까지 나왔다는 이야기가 통계학자 피터 휘틀(Peter Whittle)의 1979년 토론문을 거쳐 전해진다.
식당 다섯 곳
예제를 정하자. 왜 식당 다섯 곳일까? 상태가 하나뿐이라 「다음 칸」이 없고 고르는 일과 시험하는 일만 남으므로, 산책로에서 무작위 스텝이 하는 일을 따로 떼어 보기에 가장 단순한 무대이기 때문이다.
식당 A~E의 참 만족도 평균을 3.0, 3.4, 3.8, 3.2, 2.6으로 두자(이 책이 정한 숫자). 한 끼의 만족도는 그 평균에 표준편차 1의 노이즈가 더해진 값이다. 첫 닷새에 다섯 곳을 한 번씩 가 보고, 그 뒤 260일(평일로 1년쯤) 동안 매일 한 곳을 고른다. 식당마다의 어림값은 그 식당에서 먹은 끼니들의 평균이고, 고르는 규칙은 산책로와 같아서 확률 ε로는 다섯 곳 가운데 아무 곳에나 가고, 나머지 날은 어림값이 가장 높은 곳에 간다.
어림값이 가장 큰 행동이 무작위 차례에도 뽑힐 수 있으므로 그 확률은 1−ε에 ε/K가 더해진다. 이렇게 고르는 규칙을 ε-그리디 (확률 ε로만 아무거나, 나머지는 가장 좋아 보이는 것 / ε-greedy)라 한다. ε = 0이면 늘 가장 좋아 보이는 것만 고르는 그리디 규칙이 된다. 지금 아는 가장 좋은 것을 고르는 일을 「활용(exploitation)」, 아는 것이 맞는지 다른 것을 시험하는 일을 「탐색(exploration)」이라 부르고, 둘 사이에서 줄을 타는 고민을 탐색과 활용의 갈등이라 한다. ε-그리디는 그 줄타기를 숫자 하나로 정한다.
이 일을 4,000번 되풀이해 ε마다 평균을 냈다(난수 씨앗 20261023).
ε
260일 동안 하루 평균 만족도
가장 좋은 식당 C에 간 날의 비율
0 (늘 그리디)
3.623
0.655
0.01
3.633
0.670
0.1
3.645
0.725
0.3
3.574
0.665
늘 C에만 가면 하루 3.80이고, 아무 데나 고르면 3.20이다. 늘 그리디로 고르면 C를 첫날 한 번 가 본 뒤로 1년 내내 다시 가지 않는 경우가 22.5%나 나왔다. 가장 좋은 식당이 왜 1년 내내 돌아오지 못하는지는 아래 문제 8에서 메뉴 두 개로 따져 본다. ε = 0.3은 반대로 너무 많이 헤매서, 이미 C가 가장 좋다는 것을 안 뒤에도 열흘에 사흘은 아무 데나 간다.
그림에서 ε = 0.1의 곡선은 그 사이에 시험 삼아 간 끼니가 값을 치르기 때문에 처음 몇십 일 동안 늘 그리디보다 낮지만, 그 대가로 C를 찾아내는 경우가 늘어 1년 내내 오른다. 늘 그리디는 일찍 자리를 잡지만 잘못 잡은 자리에서 내려오지 못한다. 탐색은 지금의 만족도를 조금 내주고 앞날의 만족도를 사는 일이고, 지금의 만족도를 얼마나 내줄지가 ε다.
ε-그리디가 처음 쓰인 자리는 분명하지 않다. 서튼과 바토의 교과서는 왓킨스의 1989년 논문이 처음일 수도 있지만, 생각이 워낙 단순해 더 이른 쓰임이 있었을 것이라고 적는다.
ML에서: 언어 모델은 샘플링으로 탐색한다
언어 모델을 강화학습으로 다듬을 때는 ε-그리디를 거의 쓰지 않는다. 언어 모델은 다음 토큰의 확률 분포 전체를 내놓고, 응답을 그 분포에서 샘플링해 만든다. 탐색은 그 샘플링에서 저절로 나온다. 1등 토큰만이 아니라 2등, 3등 토큰도 확률만큼 뽑히고, 샘플링 온도를 올리면 덜 그럴듯한 토큰이 더 자주 뽑힌다. 늘 1등 토큰만 고르는 그리디 디코딩은 ε = 0의 그리디 규칙과 같다. 어휘가 수만 개인 곳에서 「아무 토큰이나」 고르는 ε-그리디가 왜 맞지 않는지는 아래 문제 9에서 셈한다.
샘플링으로 탐색하는 정책에도 식당의 늘 그리디와 같은 위험이 있다. 학습이 진행되며 정책의 확률이 몇몇 토큰에 몰려 분포의 엔트로피(확률이 여러 토큰에 고르게 퍼진 정도)가 급히 줄어드는 엔트로피 붕괴가 일어나면, 샘플링이 사실상 그리디 디코딩이 된다. 그러면 지금은 확률이 낮지만 더 나은 풀이는 다시 뽑히지 않는다. 식당에서 C를 1년 내내 다시 찾지 않은 늘 그리디처럼, 더 나은 풀이를 다시 시험할 기회가 사라진다.
문제 7. 다 알고 나서도 헤맨다
식당 다섯 곳(참 만족도 평균 A 3.0, B 3.4, C 3.8, D 3.2, E 2.6)의 어림값이 이미 참값과 같다고 하자. (가) ε = 0.1로 고르면 C에 갈 확률과 하루의 기대 만족도는? (나) 늘 C에 갈 때보다 하루에 얼마를 잃는가? (다) 이 손해를 줄이려면 어떻게 하면 좋은가?
선생님
서연 학생, (가)는요?
이서연
C 에 갈 확률은 0.9 + 0.1/5 = 0.92 예요. 나머지 0.08 은 아무 데나 가는 거니까 다섯 곳 평균 3.2 를 붙여서, 0.92 × 3.8 + 0.08 × 3.2 = 3.752 예요.
선생님
그 0.08 에 C 가 들어 있나요?
이서연
아니요. 0.08 은 C 가 아닌 네 곳에 가는 확률이에요. C 로 가는 무작위 차례는 이미 0.92 에 넣었으니까요.
선생님
그럼 0.08 에는 어떤 평균을 붙여야 하죠?
이서연
C 를 뺀 네 곳 평균 3.05 요. 0.92 × 3.8 + 0.08 × 3.05 = 3.74 예요.
김민준
차례로 나눠서 셈하면 더 쉬워. 그리디 차례 0.9 에 3.8, 무작위 차례 0.1 에 다섯 곳 평균 3.2. 0.9 × 3.8 + 0.1 × 3.2 = 3.74. 같은 값이네.
김민준
그럼 (나)는 3.80 − 3.74 = 0.06. 하루 0.06 이면 1년 260일에 15.6 이네. 다 아는 걸 확인하느라 쓰는 값치고는 아깝다.
선생님
1년을 다녀 어림값이 다 맞게 된 뒤에도 하루 0.06 씩 잃는 까닭은 무엇이죠?
김민준
ε 가 처음과 똑같이 0.1 이라서요. 다 알게 된 뒤에는 시험할 까닭이 줄었는데 헤매는 비율은 그대로예요.
선생님
그럼 (다)는 어떻게 하면 좋을까요?
김민준
처음엔 많이 헤매고, 어림값이 믿을 만해지면 ε 를 줄이면 돼요.
선생님
0 으로 딱 끊으면요?
김민준
C 를 첫날 뒤로 다시 안 간 늘 그리디처럼 영영 못 고칠 수 있겠네요. 천천히 줄여야겠죠.
이서연
줄이되 모든 식당을 끝없이 가끔은 가 보게 하는 거네요. 수열 1/n 처럼 0 으로 가지만 더하면 끝없이 커지는 꼴로 줄이면 되겠어요.
김민준
학기 초에는 여러 스터디에 다 나가 보고, 맞는 곳을 찾으면 거기만 나가되 가끔 다른 데도 얼굴을 비추는 거랑 같네요.
정리 (가) 0.9 + 0.1/5 = 0.92, 기대 만족도 0.9 × 3.8 + 0.1 × 3.2 = 3.74(C를 뺀 네 곳 평균 3.05로 셈하면 0.92 × 3.8 + 0.08 × 3.05로 같다). (나) 하루 0.06(260일에 15.6)으로, 고정된 ε는 다 알고 난 뒤에도 탐색 값을 계속 치른다. (다) ε를 점점 줄이되, 모든 행동이 끝없이 가끔은 시험되게 줄인다.
문제 8. 첫 끼에 갇히다
메뉴가 둘이다. A는 0.6의 확률로, B는 0.4의 확률로 맛있다(맛있음 1, 아님 0). 둘을 한 번씩 먹어 본 뒤, 늘 어림값(지금까지 먹은 끼니의 평균)이 큰 쪽을 고르되, 어림값이 같으면 A를 고른다. (가) 그 뒤로 A를 영영 다시 먹지 않게 될 확률은? (나) 왜 「영영」인가? (다) ε = 0.1의 ε-그리디라면 어떻게 달라지나?
선생님
민준 학생, A 를 영영 안 먹게 되는 경우가 있을까요?
김민준
B 가 더 맛있게 나와도 B 를 몇 번 먹다 보면 평균이 0.4 쪽으로 내려오니까, 결국 A 로 돌아오지 않을까요?
선생님
A 의 어림값은 그동안 얼마에 머물러 있죠? 첫 끼에 A 가 맛없었다면요.
김민준
0 이요. A 를 다시 안 먹으니 계속 0 이에요. B 는 첫 끼가 맛있었으면 그 뒤로 아무리 맛없어도 평균이 0 보다는 커요. 1을 한 번 더했으니까요. 그럼 B 가 늘 이겨요.
이서연
그러면 (가)는 A 첫 끼 0 이고 B 첫 끼 1 일 확률, (1 − 0.6) × 0.4 = 0.16 이야. 스크립트로 200 끼를 20만 번 돌려 보니 0.161 이었어.
선생님
(다)는요?
이서연
끼니마다 무작위 차례에서 A 가 뽑힐 확률이 0.1 × 1/2 = 0.05 니까, 끼니 스무 번에 한 번꼴로 A 를 먹어요.
선생님
A 를 다시 먹으면 무엇이 바뀌죠?
이서연
A 의 어림값이요. 몇 번 먹다 보면 0.6 쪽으로 올라가서 B 를 넘어요. 「영영」이 없어져요.
이서연
확률론의 흡수 상태 같아요. 그리디만 쓰면 「A 의 값 0, B 의 값 양수」가 한 번 들어가면 나올 수 없는 상태인데, ε 가 그 상태에서 나가는 문을 열어 두는 거예요.
정리 (가) 0.4 × 0.4 = 0.16(모의실험 0.161). (나) 다시 먹지 않는 메뉴의 어림값은 고쳐지지 않으므로, 한 번 밀린 쪽은 그리디 규칙으로는 다시 뽑히지 않는다. (다) 끼니마다 A가 적어도 0.05의 확률로 뽑혀 어림값이 고쳐질 기회가 끝없이 생긴다. 모든 행동을 거듭 시험하라는 수렴 조건이 막는 것이 바로 이런 갇힘이다.
문제 9. 어휘 5만 개의 ε-그리디
어휘가 50,000개인 언어 모델이 어느 자리에서 그럴듯한 후보 토큰 다섯 개에 확률 0.50, 0.25, 0.12, 0.06, 0.03을, 나머지 49,995개에 모두 합쳐 0.04를 준다. (가) 1등 토큰을 그리디로 고르고 ε = 0.1로 어휘 전체에서 아무 토큰이나 고르는 ε-그리디라면, 2~5등 후보가 뽑힐 확률과 엉뚱한 토큰이 뽑힐 확률은? (나) 모델 분포 그대로 샘플링하면? (다) 이 규칙으로 100토큰짜리 응답을 쓰면 엉뚱한 토큰이 하나도 없을 확률은?
선생님
민준 학생, ε-그리디로 하면 탐색이 열 번에 한 번이니까 2등 후보도 꽤 시험해 보겠죠?
김민준
네, 0.1 이면 넉넉하죠.
선생님
무작위 차례에 뽑히는 토큰은 5만 개 가운데 하나예요. 그게 2~5등 넷 가운데 하나일 확률은요?
김민준
4/50,000 이요. 0.1 을 곱하면 0.000008 이에요. 탐색 차례의 거의 전부, 0.09999 가 엉뚱한 토큰에 가요.
이서연
샘플링이면 2~5등 합이 0.46, 엉뚱한 토큰은 0.04 야. 모델이 「그럴듯하다」고 본 곳 안에서 시험하니까 탐색이 훨씬 쓸모 있어.
선생님
(다)는요?
이서연
토큰마다 엉뚱한 게 안 나올 확률이 1 − 0.09999 니까, 100 번이면 (1−0.09999)100 ≈ 0.000027 이에요. 응답마다 거의 반드시 엉뚱한 토큰이 섞여요.
선생님
그래요. 행동이 몇 개뿐인 산책로나 식당에서는 「아무거나」가 쓸 만한 탐색이지만, 행동이 수만 개면 「아무거나」는 거의 늘 쓸모없는 시험이에요. 그래서 언어 모델은 모델 자신의 분포로 샘플링해서 탐색해요.
김민준
조사 과제 주제를 고를 때 도서관 책을 무작위로 한 권 뽑기보다, 교수님이 추천한 목록 안에서 골고루 읽어 보는 게 나은 거랑 같네요.
정리 (가) 2~5등: 0.1 × 4/50,000 = 0.000008, 엉뚱한 토큰: 0.1 × 49,995/50,000 = 0.09999. (나) 2~5등 0.46, 엉뚱한 토큰 0.04. (다) (1−0.09999)100 ≈ 0.000027. 행동이 아주 많으면 균일한 무작위 탐색은 거의 늘 엉뚱한 곳을 시험하므로, 언어 모델은 자기 분포에서 샘플링하는 것으로 그럴듯한 후보 안에서 탐색한다.
