이 글은 Claude Opus 5.5 을 이용해 초안이 작성되었으며, 이후 퇴고를 거쳤습니다.


1979년 영국 왕립통계학회 학술지에 존 기틴스의 논문 한 편이 토론문과 함께 실렸습니다. 토론자 가운데 피터 휘틀은 그 논문이 다룬 문제의 내력을 이렇게 전했습니다. 전쟁 중에 만들어진 문제인데 연합국 분석가들의 머리를 하도 빨아들여서, 차라리 독일에 떨어뜨리자는 말까지 나왔다는 것입니다. 휘틀의 표현으로는 “the ultimate instrument of intellectual sabotage”, 궁극의 지적 사보타주 무기였습니다.

문제 자체는 한 문단이면 설명할 수 있습니다. 슬롯머신이 여러 대 있고, 대마다 돈이 나올 확률이 다르며, 그 확률은 아무도 모릅니다. 당길 수 있는 횟수는 정해져 있습니다. 어느 머신을 몇 번씩 당길지를 정하는 것이 문제의 전부입니다.

그리고 휘틀이 이 말을 남긴 곳은, 바로 그 문제의 중요한 한 갈래를 푼 논문의 토론란이었습니다.

외팔이 강도#

슬롯머신을 영어로 one-armed bandit 이라고 부릅니다. 레버가 하나 달렸고 돈을 털어 가니 외팔이 강도라는 것으로, 1930년대 미국 속어입니다. 1950년대 프레더릭 모스텔러와 로버트 부시는 동물의 학습을 연구하면서 생쥐를 T자 미로에 넣었습니다. 생쥐는 왼쪽과 오른쪽 가운데 어디에 먹이가 있을지 모르는 채 매번 고릅니다. 같은 상황을 사람에게 주려고 레버가 둘인 기계를 만들었고, 그 기계에 두 팔 강도라는 이름이 붙었습니다. 여러 팔 강도 문제, 줄여서 밴딧 문제라는 이름은 거기서 왔습니다.

문제는 이름보다 스무 해 먼저 나왔습니다. 1933년 예일대 병리학과의 윌리엄 톰프슨은 두 치료법 가운데 어느 쪽이 나은지 아직 모를 때 다음 환자에게 무엇을 줄지를 물었습니다. 그는 이것을 연구 계획의 문제로 보았고, 열등한 치료에 희생될 사람을 줄이는 것을 목표로 삼았습니다. 그가 낸 답은 지금까지 본 결과로 “치료 1이 더 나을 확률” P 를 계산하고, 그 확률에 따라 배정하라는 것이었습니다. P 가 0.7 이면 열에 일곱은 치료 1을 받습니다. 앞의 베이즈 시리즈에서 다룬 사후 확률이 그대로 배정 규칙이 된 셈이고, 이 방법은 지금 톰프슨 샘플링이라고 불립니다.

1952년 허버트 로빈스는 톰프슨의 논문을 몰랐던 것으로 보이는데, 같은 문제를 빈도주의 통계의 언어로 세웠습니다. 동전이든 항아리든 치료법이든, 성질을 모르는 두 모집단에서 하나씩 골라 관찰을 이어 가며 합계를 최대로 만드는 문제입니다. 로빈스의 규칙은 대체로 지금까지 평균이 높은 쪽을 고르되, 미리 정한 드문 시점에는 양쪽을 억지로 한 번씩 고르는 것이었습니다. 억지로 고르는 시점이 없으면, 초반에 운이 나빴던 쪽은 다시는 기회를 얻지 못합니다.

알아볼 것인가, 써먹을 것인가#

포커를 치는 저에게 이 문제는 익숙한 모양입니다. 처음 앉은 테이블에서 상대가 블러프를 얼마나 섞는지 알려면 콜을 몇 번 해 봐야 하고, 그 콜은 대개 칩을 내주는 값을 치릅니다. 알아낸 뒤에는 그 정보로 칩을 벌어야 하는데, 언제 알아보기를 그만둘지에는 정해진 답이 없습니다. 너무 일찍 멈추면 잘못 본 상대를 끝까지 잘못 상대하고, 너무 오래 알아보면 알아낸 것을 써먹을 판이 남지 않습니다.

밴딧 문제는 이 줄다리기를 숫자로 옮겨 놓은 것입니다. 알아보기를 탐색, 써먹기를 활용이라고 부릅니다. 머신 하나를 당길 때마다 둘 중 하나를 하는 셈이고, 대개는 둘을 조금씩 동시에 합니다.

후회라는 잣대#

전략이 얼마나 잘했는지는 후회로 잽니다. 처음부터 가장 좋은 머신만 당겼다면 기대할 수 있었던 보상에서, 실제로 고른 머신들의 기대 보상을 뺀 값입니다. 나쁜 머신을 한 번 당길 때마다 그 머신과 최선의 차이만큼 후회가 쌓입니다.

1985년 라이와 로빈스는 이 후회에 바닥이 있다는 것을 보였습니다. 어떤 머신 배치에서도 쓸 만한 규칙이라면, 당긴 횟수 n 이 커질 때 후회는 적어도 log n 에 비례해 자랍니다. 비례 상수는 머신들 사이의 차이가 작을수록 커집니다. 비슷한 머신일수록 둘을 가려내는 데 더 많이 당겨 봐야 하니 당연한 결과입니다. 두 사람은 이 바닥에 닿는 규칙도 함께 만들었는데, 각 머신의 평균에 “아직 덜 당겨서 모르는 몫” 을 얹은 상한으로 고르는 방식이었습니다.

휘틀이 토론을 붙인 기틴스의 논문은 다른 쪽에서 문제를 풀었습니다. 미래의 보상을 일정 비율로 깎아 계산하고 머신끼리 서로 독립이라면, 머신마다 그 머신만 보고 지수 하나를 계산해 지수가 가장 큰 머신을 당기는 것이 최적이라는 정리입니다. 1974년 기틴스와 존스가 발표하고 1979년 논문에서 정리한 이 값은 기틴스 지수라고 불립니다. 정해진 횟수 안에서 합계를 겨루는 문제에서는 최적 규칙이 대개 이런 지수 꼴이 되지 않으므로, 전쟁 중의 그 문제가 모두 풀린 것은 아닙니다.

2002년 아우어, 체사-비앙키, 피셔가 낸 UCB1 은 상한 방식을 가장 짧은 식으로 줄였습니다. 보상이 0과 1 사이일 때, 지금까지 n 번 당겼고 머신 j 를 n_j 번 당겼다면 다음 값이 가장 큰 머신을 당깁니다.

평균_j + √(2 ln n / n_j)

덜 당긴 머신일수록 뒤의 항이 커서 기회를 더 받습니다. 불확실한 쪽을 좋게 봐 주는 낙관이고, 이 식으로 정해진 끝 없이 어느 n 에서나 후회가 log n 꼴로 묶인다는 것이 그 논문의 결과였습니다.

A/B 테스트는 밴딧인가#

개발자에게 가장 가까운 밴딧은 A/B 테스트입니다. 2013년 구글 애널리틱스는 콘텐츠 실험 기능을 밴딧 방식으로 돌린다고 발표했습니다. 글을 쓴 스티븐 스콧의 설명에 따르면, 어떤 변형이 가장 좋을 확률이 70% 로 계산되면 다음 트래픽의 70% 를 그 변형에 보냅니다. 실험은 적어도 두 주 동안 돌리고, 한 변형이 원본보다 나을 확률이 95% 에 이르거나 더 돌려서 얻을 값이 1% 아래로 내려가면 멈춥니다. 1933년 톰프슨의 규칙이 웹 트래픽 위에서 다시 돌아간 셈입니다.

론 코하비 등은 2020년 책에서 밴딧이 고전적인 A/B 실험보다 대개 효율적이라고 하면서도 한계 둘을 적었습니다. 트래픽을 다시 나눌 때마다 잴 수 있는 지표 하나가 있어야 하는데, 클릭률은 되지만 방문 횟수처럼 오래 지켜봐야 하는 지표는 어렵습니다. 그리고 나쁜 변형을 본 사용자를 다른 쪽으로 옮기는 과정이 결과를 치우치게 할 수 있습니다.

결과가 치우치면 어떤 일이 생기는지는 의학에 극단적인 예가 있습니다. 1985년 미시간 대학의 바틀렛 등은 호흡 부전으로 사망 위험이 높은 신생아에게 체외막산소공급(ECMO)을 시험하면서, 앞 환자의 결과가 좋았던 쪽에 다음 환자가 배정될 확률을 높이는 방식을 썼습니다. 열두 명 가운데 기존 치료를 받은 아이는 한 명이었고 그 아이는 숨졌습니다. ECMO 를 받은 열한 명은 모두 살았습니다. 실험하는 동안 희생을 줄인다는 목표는 이뤘지만, 대조군이 한 명뿐인 결과로는 ECMO 가 낫다는 것을 다른 의사들에게 설득하기 어려웠습니다. 하버드에서는 오루크 등이 다시 시험을 설계했고, 무작위 단계에서 기존 치료 10명 가운데 4명이 숨지고 ECMO 9명은 모두 살았습니다. 1989년 학술지 Statistical Science 에는 이 시험의 윤리를 두고 긴 토론이 실렸습니다.

제 생각은 목적에 따라 다르다는 쪽입니다. 둘 중 무엇이 얼마나 나은지를 남에게 보여 줘야 한다면 대조군을 지키는 A/B 테스트가 맞습니다. 실험하는 동안 잃는 것을 줄이는 것이 목적이라면 밴딧이 맞습니다. 2010년 오디베르 등은 논문 서두에서 같은 구분을 다른 예로 들었습니다. 임상시험은 시험하는 동안이 곧 치료하는 동안이라 당길 때마다의 손실이 중요합니다. 화장품 회사는 출시 전에 시험을 따로 하고, 시험이 끝난 뒤 고른 제품 하나만 팝니다. 둘은 같은 밴딧 문제처럼 보이지만, 무엇을 후회로 셀지가 다릅니다.

바둑판 위의 슬롯머신#

2006년 레벤테 코치시와 차바 세페슈바리는 게임 트리의 마디마다 밴딧 문제를 하나씩 두자고 제안했습니다. 마디에서 어느 수를 더 읽어 볼지를 UCB1 으로 고르는 것으로, 트리에 쓴 UCB 라는 뜻에서 UCT 라고 불렀습니다. 같은 해 레미 쿨롱은 몬테카를로 트리 탐색이라는 이름을 널리 알린 논문을 냈고, 그의 프로그램 Crazy Stone 은 토리노에서 열린 컴퓨터 올림피아드의 9×9 바둑에서 금메달을 땄습니다.

2016년 알파고도 같은 뼈대 위에 섰습니다. 탐색에서 수를 고르는 식은 평균 가치 Q 에, 정책망이 준 사전 확률 P 에 비례하는 탐색 보너스를 더하는 PUCT 의 변형이었습니다. 알파고는 2015년 10월 판후이 2단을 5대 0으로, 2016년 3월 이세돌 9단을 4대 1로 이겼습니다. 오목 엔진을 다룬 Rapfi Part 2 의 KataGo 도 이 계열입니다.

벌기와 고르기#

그런데 게임 트리의 뿌리에서 하는 일은 슬롯머신과 조금 다릅니다. 탐색 중에 굴려 본 판은 돈이 아닙니다. 롤아웃 천 번 가운데 나쁜 수를 몇 번 굴렸는지는 아무도 셈하지 않고, 남는 것은 마지막에 고른 수 하나입니다. 앞에서 본 화장품 회사의 처지와 같습니다.

2009년 뷔벡, 뮈노, 스톨츠는 이 차이에 이름을 붙였습니다. 당길 때마다 쌓이는 후회를 누적 후회, 예산을 다 쓴 뒤 추천한 머신 하나와 최선의 차이를 단순 후회라고 부릅니다. 그리고 둘이 서로 맞선다는 정리를 증명했습니다. 누적 후회를 작게 묶는 전략일수록 단순 후회를 빨리 줄일 수 없고, UCB 류의 단순 후회는 기껏해야 다항식 속도로 줄어듭니다. 모든 머신을 똑같이 당기는 균등 배분은 누적 후회로는 최악이지만, 단순 후회는 지수 속도로 줄어듭니다.

2012년 톨핀과 시모니는 이것을 몬테카를로 트리 탐색에 가져왔습니다. 뿌리에서는 마지막 선택만 보상을 받으므로 단순 후회를 줄이는 규칙을 쓰고, 그 아래 마디에서는 UCT 를 그대로 쓰자는 제안이었습니다. 2013년 카르닌 등은 이 목적에 맞는 간단한 알고리즘을 냈습니다. Sequential Halving 은 예산을 ⌈log₂ K⌉ 라운드로 나누고, 라운드마다 살아남은 후보를 똑같이 당긴 뒤 평균이 높은 절반만 남깁니다. 손볼 상수가 하나도 없습니다. 2022년 딥마인드의 다니헬카 등은 알파제로·뮤제로 계열의 뿌리 탐색을 이 방식으로 바꿨고, 9×9 바둑에서 수마다 시뮬레이션 두 번만으로도 학습이 된다고 보고했습니다. 같은 조건에서 기존 뮤제로는 열여섯 번 이하로는 학습하지 못했습니다.

열 대를 6,400번#

둘이 정말 다른 문제인지는 직접 돌려 보면 압니다. 돈이 나올 확률이 0.40 부터 0.58 까지 0.02 씩 다른 슬롯머신 열 대를 두고, 방법 다섯으로 6,400번씩 당깁니다. 당기는 동안 쌓인 누적 후회와, 다 당긴 뒤 평균이 가장 높았던 머신을 골랐을 때 그것이 정말 0.58 짜리였는지를 함께 셉니다. Sequential Halving 은 마지막까지 살아남은 머신을 고릅니다.

package main

import (
	"fmt"
	"math"
	"math/rand/v2"
	"sort"
)

// 당기면 확률 p 로 1, 아니면 0 을 주는 슬롯머신 10대. 9번이 가장 좋다(0.58).
var probs = []float64{0.40, 0.42, 0.44, 0.46, 0.48, 0.50, 0.52, 0.54, 0.56, 0.58}

const (
	pulls  = 6400
	trials = 2000
)

type state struct {
	n   []int
	sum []float64
}

func (s *state) mean(i int) float64 {
	if s.n[i] == 0 {
		return 0
	}
	return s.sum[i] / float64(s.n[i])
}

func (s *state) bestMean() int {
	best := 0
	for i := range s.n {
		if s.mean(i) > s.mean(best) {
			best = i
		}
	}
	return best
}

// strategy 는 pulls 번을 다 쓰고 마지막에 하나를 고른다. pull 은 머신 i 를 당긴다.
type strategy func(s *state, pull func(i int), rng *rand.Rand) int

func roundRobin(s *state, pull func(int), _ *rand.Rand) int {
	for t := range pulls {
		pull(t % len(s.n))
	}
	return s.bestMean()
}

func epsGreedy(s *state, pull func(int), rng *rand.Rand) int {
	for t := range pulls {
		switch {
		case t < len(s.n):
			pull(t)
		case rng.Float64() < 0.1:
			pull(rng.IntN(len(s.n)))
		default:
			pull(s.bestMean())
		}
	}
	return s.bestMean()
}

func ucb1(s *state, pull func(int), _ *rand.Rand) int {
	for t := range pulls {
		if t < len(s.n) {
			pull(t)
			continue
		}
		best, bestU := 0, math.Inf(-1)
		for i := range s.n {
			u := s.mean(i) + math.Sqrt(2*math.Log(float64(t))/float64(s.n[i]))
			if u > bestU {
				best, bestU = i, u
			}
		}
		pull(best)
	}
	return s.bestMean()
}

func gammaSample(rng *rand.Rand, shape float64) float64 {
	d := shape - 1.0/3
	c := 1 / math.Sqrt(9*d)
	for {
		x := rng.NormFloat64()
		v := 1 + c*x
		if v <= 0 {
			continue
		}
		v = v * v * v
		if math.Log(rng.Float64()) < 0.5*x*x+d-d*v+d*math.Log(v) {
			return d * v
		}
	}
}

// thompson 은 머신마다 Beta(1+성공, 1+실패) 에서 하나씩 뽑아 가장 큰 머신을 당긴다.
func thompson(s *state, pull func(int), rng *rand.Rand) int {
	for range pulls {
		best, bestDraw := 0, -1.0
		for i := range s.n {
			a := gammaSample(rng, 1+s.sum[i])
			b := gammaSample(rng, 1+float64(s.n[i])-s.sum[i])
			if draw := a / (a + b); draw > bestDraw {
				best, bestDraw = i, draw
			}
		}
		pull(best)
	}
	return s.bestMean()
}

// halving 은 Sequential Halving 이다: ⌈log2 10⌉ = 4 라운드, 라운드마다 살아남은 머신에 예산을 고르게 나눠 당기고 위 절반만 남긴다.
func halving(s *state, pull func(int), _ *rand.Rand) int {
	alive := make([]int, len(s.n))
	for i := range alive {
		alive[i] = i
	}
	rounds := int(math.Ceil(math.Log2(float64(len(s.n)))))
	for len(alive) > 1 {
		per := pulls / (len(alive) * rounds)
		for _, i := range alive {
			for range per {
				pull(i)
			}
		}
		sort.SliceStable(alive, func(a, b int) bool { return s.mean(alive[a]) > s.mean(alive[b]) })
		alive = alive[:(len(alive)+1)/2]
	}
	return alive[0]
}

func main() {
	best := len(probs) - 1
	fmt.Printf("머신 %d대, %d번 당기기, %d회 평균\n", len(probs), pulls, trials)
	fmt.Printf("%-14s %10s %12s %10s\n", "방법", "누적 후회", "최선을 고름", "단순 후회")
	for _, st := range []struct {
		name string
		run  strategy
	}{{"균등", roundRobin}, {"ε-greedy(0.1)", epsGreedy}, {"UCB1", ucb1}, {"Thompson", thompson}, {"Seq. Halving", halving}} {
		rng := rand.New(rand.NewPCG(2026, 1118))
		cumulative, simple, hits := 0.0, 0.0, 0
		for range trials {
			s := &state{n: make([]int, len(probs)), sum: make([]float64, len(probs))}
			pull := func(i int) {
				s.n[i]++
				if rng.Float64() < probs[i] {
					s.sum[i]++
				}
				cumulative += probs[best] - probs[i]
			}
			chosen := st.run(s, pull, rng)
			if chosen == best {
				hits++
			}
			simple += probs[best] - probs[chosen]
		}
		fmt.Printf("%-14s %10.1f %11.1f%% %10.4f\n", st.name, cumulative/trials, 100*float64(hits)/trials, simple/trials)
	}
}

ε-greedy 는 열 번 가운데 한 번은 아무 머신이나 당기고 나머지는 지금까지 평균이 가장 높은 머신을 당기는, 가장 흔한 방법입니다. Thompson 의 베타 분포는 감마 분포 둘로 만들었습니다. 결과는 아래와 같습니다.

방법누적 후회최선을 고름단순 후회
균등576.074.1%0.0062
ε-greedy(0.1)149.866.4%0.0087
UCB1345.884.0%0.0035
Thompson151.487.5%0.0026
Seq. Halving282.386.7%0.0028

ε-greedy 는 버는 쪽에서 Thompson 과 거의 같은 성적을 냈습니다. 그런데 마지막에 최선을 고른 비율은 66.4% 로 다섯 가운데 가장 낮았고, 머리를 전혀 쓰지 않는 균등 배분(74.1%)보다도 못했습니다. 평균이 앞선 머신에 몰아서 당기다 보니 그 머신의 평균은 정확해지지만, 덜 당긴 머신들의 평균은 흔들리는 채로 남습니다. 0.56 짜리가 초반에 앞서 나가면 0.58 짜리는 끝까지 제 실력을 보일 기회를 얻지 못합니다.

Sequential Halving 은 반대입니다. 벌 생각이 없으니 누적 후회는 282 로 컸지만, 고르기에서는 Thompson 에 바짝 붙었습니다. 이 판에서는 Thompson 이 둘 다 잘했습니다. 뷔벡 등의 정리는 예산이 충분히 커질 때의 이야기라, 6,400번에서는 Thompson 이 그 값을 아직 크게 치르지 않았습니다.

같은 방법의 순위가 무엇을 세느냐에 따라 뒤집힌다는 것, 이 표에서 볼 것은 그것 하나입니다. 게임 봇이 뿌리에서 굴리는 롤아웃은 두 번째 문제에 속합니다. 수 하나를 고르기 위해 쓰는 예산이고, 굴리는 동안 잃는 것은 없습니다.

자료에 대해#

논문과 책은 원문으로 확인했습니다. 다만 휘틀의 말은 원문 쪽을 직접 보지 못해 그 말을 인용한 2차 자료에 기댔고, 두 팔 강도라는 이름이 모스텔러와 부시의 실험에서 왔다는 대목도 래티모어와 세페슈바리의 책에 기댄 것입니다. 구글 애널리틱스의 도움말 문서는 지금 없어져서 같은 내용을 담은 2013년 블로그 글로 확인했습니다. 예제의 확률과 횟수는 설명을 위해 정한 값이고, 예산을 400번으로 줄이면 Sequential Halving 이 UCB1 보다 조금 못하는 등 순위가 바뀝니다.


편제목
Part 1벌 것인가, 고를 것인가 (지금 글)
Part 2열여섯 번을 어디에 쓸까

References#

고전과 이론#

단순 후회와 게임 트리#

A/B 테스트와 임상시험#

이 블로그의 관련 글#