팔, 당기기, 보상
한 줄로 늘어선 슬롯 머신들
K개의 슬롯 머신이 한 줄로 늘어선 것을 상상해 보세요. 각 머신은 다른 평균 보상을 지불하지만, 당신은 그 평균들을 모릅니다. 매 단계마다 하나의 머신을 선택하고, 레버를 당기며 지불금을 관찰합니다. 목표: 많은 당김에 걸쳐 총 보상을 최대화하는 것.
이 설정이 다중 팔 강도 문제를 정의합니다. K = 팔의 수. 당기기는 하나의 팔을 선택하는 것. 보상은 그 팔의 숨겨진 분포에서 나옵니다. 팔 k의 mean_reward(k)는 k의 당김에 걸친 누적 평균을 추적합니다.
탐색 vs 활용
서로 상반되는 두 가지 압력이 작용합니다:
활용은 관측된 평균 보상이 가장 높은 팔을 선택합니다. 탐욕적입니다. 위험: 2번 당긴 후 훌륭해 보였던 팔이 실제 낮은 평균으로 회귀할 수 있습니다.
탐색은 불확실성을 줄이기 위해 덜 테스트된 팔을 선택합니다. 위험: 탐색에 소비한 시간이 알려진 좋은 팔에서 얻을 수 있었던 보상을 잃게 합니다.
좋은 정책은 둘 다를 섞습니다. 순수한 exploitation은 초기 승자를 영원히 고정합니다. 순수한 exploration은 보상을 수집하지 않습니다.
ANDREA의 팔 = 데이터 소스
ANDREA는 훈련을 bandit으로 프레임합니다. 각 데이터 소스(hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk 등)가 팔 역할을 합니다. 각 훈련 단계에서 한 팔을 당깁니다: 해당 소스에서 문서를 로드하고, forward pass를 실행하며, 손실 감소를 관찰합니다. 소스당 평균 보상은 그 소스가 평균적으로 손실을 얼마나 개선하는지 추적합니다.
이것이 적합한 이유: 훈련 중 모델의 필요가 변합니다. 초기 단계는 광범위한 노출(많은 소스)로부터 이익을 봅니다. 후기 단계는 타겟팅된 다듬기(몇 개의 고보상 소스)로부터 이익을 봅니다. Bandit은 적응합니다; 고정 샘플링 비율은 할 수 없습니다.
구성 요소 이름 짓기
UCB1 점수
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer와 동료들은 2002년에 UCB1을 finite-time bandit 정책으로 발표했으며, regret bound는 O(log N)입니다. UCB1은 arm의 현재 평균 보상에 arm이 pull될수록 줄어드는 exploration bonus를 결합하여 arm을 선택합니다.
공식
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
항별로:
- mean_reward(k): 팔 k에 대해 n_k 번의 선택에서 관찰된 평균 보상. Exploitation 항.
- N: 지금까지 모든 팔에 대한 총 선택 횟수. 매 단계마다 증가.
- n_k: 팔 k에 대한 선택 횟수. k가 선택될 때만 증가.
- C: 탐색 상수. 표준 교과서 값: 1.4 (sqrt(2)). ANDREA는 C=0.5 사용.
- sqrt(ln(N) / n_k): 신뢰 반경. 드물게 선택된 팔은 n_k가 작아 큰 보너스를 받고, 잘 선택된 팔은 n_k가 커 작은 보너스를 받음.
공식이 작동하는 이유
ln(N)은 천천히 증가(로그 함수)하므로, 분자는 총 경험에 따라 완만히 상승. 분모의 n_k는 특정 팔에 대한 증거가 쌓일수록 항을 줄임. 제곱근은 반응을 부드럽게 하여, 단일 미탐색 팔이 영원히 지배하지 않도록 함.
각 단계에서 argmax_k UCB(k)로 선택하면 두 압력을 자동으로 균형 있게 맞춥니다. 엡실론 매개변수도, 스케줄도, 온도도 없습니다. 수학이 이를 처리합니다.
UCB 점수 계산하기
C=0.5를 1.4 대신 사용하는 이유
교과서 값
Auer, Cesa-Bianchi & Fischer는 보상이 [0, 1]에 있다고 가정하여 후회 한계를 도출합니다. 이 한계는 C = sqrt(2) 약 1.414에 대해 성립합니다. 대부분의 교과서는 C=1.4를 안전한 기본값으로 가르칩니다.
ANDREA의 보상 크기
ANDREA는 단계별 손실 개선을 보상으로 보고합니다. 원시 개선값은 약 0.001 정도입니다 (손실이 4.521에서 4.520으로 감소). 1000배 스케일링 팩터(활동 78, 보상 귀속에서 다룸) 적용 후, 스케일된 보상은 크기가 약 1.0 근처에 위치합니다. 팔의 이력에 걸친 평균 보상은 0.5에서 3.0 범위로 안정화됩니다.
이제 N=10000, n_k=100일 때 C=1.4에서의 탐색 보너스를 고려해 보십시오:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425는 보상 밴드 안에 위치합니다. 허용 가능. 이제 n_k=10 (드문 팔):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344는 대부분의 관측된 평균 보상보다 위에 위치합니다. 탐험이 지배적: 실제 평균과 상관없이 드문 팔이 승리합니다. 많은 소스와 긴 훈련 실행에서, 이는 낮은 평균 팔들로 스케줄을 가득 채웁니다.
해결책: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480은 대부분의 보상 평균보다 낮습니다. 탐색은 여전히 발생합니다 (희귀한 팔이 여전히 보너스를 받음), 하지만 mean_reward가 주도합니다. ANDREA는 더 많이 활용하고, 덜 탐색하며, 탐색 지배를 피합니다.
튜닝은 이론이 아닌 엔지니어링
교과서 경계는 보상이 [0, 1]에 있다고 가정합니다. ANDREA의 보상은 대략 [0, 5]에 있습니다. 상수를 스케일링하여 보상 크기에 맞춥니다. 동일한 알고리즘, 보정된 환경.
탐색 우위 진단
다음 내용
당신이 배운 것
UCB1은 가장 높은 상한 신뢰 구간을 가진 팔을 선택합니다. 이 구간은 mean_reward (활용)와 sqrt(ln(N) / n_k)를 C (탐색)로 스케일링한 것을 결합합니다. ANDREA는 C=0.5로 조정하는데, 단계당 보상이 0.5~3.0 범위에 있고 교과서 1.4는 낮은 평균 팔들로 일정을 가득 채우기 때문입니다.
남은 것
Vanilla UCB1은 한 번에 하나의 팔을 선택합니다. ANDREA는 각 단계별로 여러 포커스 팔을 선택하고, 먼저 랜덤 팔을 섞은 후, 각 단계를 7에서 42 스텝 동안 유지합니다. 그 구조(활동 77: 주사위 단계)는 UCB가 초기 승자에 과도하게 몰두하는 것을 방지하면서도 여전히 노력을 집중할 수 있게 합니다.
보상 귀속(활동 78)은 mean_reward(k)가 실제로 어디서 오는지 보여줍니다. 바닥값과 에포크 페널티(활동 79)는 UCB 출력 위에 보호 규칙을 추가로 적용합니다.
참고 문헌
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- ANDREA 화이트페이퍼, 3.1 및 3.4 섹션.