🤖 machine learning

A Broader View of Thompson Sampling

본 논문은 잔여 불확실성으로 탐욕성을 규제하는 정적 벨만 최적 정책을 모방하는 온라인 최적화 알고리즘으로 톰슨 샘플링을 재정의함으로써 그 성공 메커니즘을 규명하여 동역학을 이해하고 정책을 개선하기 위한 새로운 틀을 제시한다.

원저자: Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

게시일 2026-05-28

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

"Thompson Sampling 에 대한 더 넓은 시각"이라는 논문에 대한 설명을 일상적인 비유를 곁들인 쉬운 언어로 번역한 것입니다.

큰 그림: 유명한 알고리즘의 "미스터리"를 해결하다

새로운 요리를 만들기 위해 최고의 레시피를 찾아야 하는 요리사를 상상해 보세요. 두 가지 재료 (Arm 1 과 Arm 2 라고 부르겠습니다) 가 있지만, 어느 것이 더 맛있는지 알 수 없습니다. 배움을 위해 계속 요리해야 하지만, 동시에 지금 당장 고객에게 최고의 요리를 제공하고 싶어 합니다. 이것이 바로 탐색(배우기 위해 새로운 것을 시도함)과 활용(가장 잘 작동하는 것을 활용함) 사이의 균형을 맞추는 고전적인 **"멀티-암드 밴딧"**문제입니다.

수십 년 동안 Thompson Sampling이라는 특정 방법이 금표준으로 여겨져 왔습니다. 실제로 놀라울 정도로 잘 작동하기 때문에 유명합니다. 하지만 "가장 높은 신뢰도 점수를 가진 옵션을 항상 선택하라"와 같이 규칙이 명확한 다른 방법들과 달리, Thompson Sampling 은 약간 마법처럼 느껴졌습니다. 작동은 하지만, 왜 학습과 수익을 이렇게 완벽하게 균형 있게 조절하는지 설명할 수는 없었습니다.

이 논문은 그 베일을 벗깁니다. 저자들은 Thompson Sampling 이 단순한 운 좋은 추측이 아니라, 사실은 정교한 온라인 최적화 알고리즘임을 보여줍니다. 그들은 이 알고리즘이 "후회"(얻은 것과 얻을 수 있었을 것 사이의 차이) 의 특정 유형을 최소화하면서 불확실성의 척도에 의해 "규제"(지침을 받음) 되어 작동한다는 사실을 발견했습니다.

핵심 아이디어: "후회"를 측정하는 새로운 방법

논문을 이해하려면 그들이 성공을 어떻게 측정하는지 살펴봐야 합니다.

기존 방식(할인된 보상)
지금 얻는 점수가 100% 의 가치가 있지만, 나중에 얻는 점수는 90%, 그다음은 81% 등으로 가치가 떨어진다고 가정해 보세요. 이를 "할인"이라고 합니다. 유명한 Gittins Index정책은 이를 사용합니다. 게임에는 훌륭하지만 결함이 있습니다. 미래의 점수가 위험을 감수할 가치가 없어 보일 때, 잠재적으로 더 나은 옵션을 일찍 탐색을 중단하게 만들 수 있다는 점입니다. 장기적으로 가능한 모든 것을 배우고 싶은 현실 세계에서는 이것이 실수가 될 수 있습니다.

논문의 새로운 방식(제곱된 후회)
저자들은 문제를 바라보는 새로운 방식을 제안합니다. 미래를 할인하는 대신 후회의 제곱을 살펴봅니다.

비유: 자동차를 운전한다고 상상해 보세요.
- 선형 후회: 1 마일 길을 잘못 들면 1 마일 어긋난 것입니다. 10 마일 길을 잘못 들면 10 마일 어긋난 것입니다.
- 제곱된 후회: 1 마일 길을 잘못 들면 1 마일 어긋난 것입니다. 하지만 10 마일 길을 잘못 들면 이제 100단위의 나쁜 운전이 됩니다.
- 왜 중요한가: 오류를 제곱함으로써 알고리즘은 큰 실수에 매우 민감해집니다. 이는 시스템이 큰 실수를 피하도록 강제하여, 나쁜 길에 갇히지 않도록 충분히 탐색하되 시간을 낭비하지 않을 정도로만 탐색하는 전략을 자연스럽게 이끌어냅니다.

저자들은 이를 "Faithful Stationarization(신실한 정상화)이라고 부릅니다. 이는 "시간에 따라 변하지 않는 (정상적인) 수학적 규칙을 찾았지만, 여전히 장기적인 실수를 최소화한다는 목표를 완벽하게 포착한다"는 것을 의미하는 고급스러운 표현입니다.

"비밀 소스": 불확실성 vs 긴장감

이 논문은 Thompson Sampling 이 다음과 같은 수학 문제를 해결함으로써 작동함을 밝혀냅니다.

실수 최소화 + 불확실성 페널티

저자들은 이를 두 가지 경쟁하는 힘으로 분해합니다.

탐욕성(활용) 지금 당장 가장 좋은 것처럼 보이는 암을 선택하여 보상을 최대한 얻고자 합니다.
규제(탐색) 탐욕스러워지지 않도록 막아주는 "페널티"가 필요합니다. 이 페널티는 당신이 얼마나 모르는지에 기반합니다.

발견:
저자들은 Thompson Sampling 이 Biserial Covariance(이분산 공분산) 라는 특정 유형의 페널티를 사용한다는 사실을 발견했습니다.

비유: 경마에 베팅한다고 상상해 보세요.
- Thompson Sampling 의 논리: "어떤 말이 이길지 확신이 없습니다. 내가 얼마나 확신이 없는지 (말들이 얼마나 비슷해 보이는지) 가 클수록, 그들이 이길 수 있는지 확인하기 위해 약세인 말에 더 많이 베팅해야 합니다." 이는 불확실성을 측정합니다.
- "Bellman-Optimal"논리(이상적인 것) 저자들은 완벽한 알고리즘이 무엇을 할지 계산했습니다. 그들은 완벽한 알고리즘이 불확실성만 보는 것이 아니라 긴장감(Tension)을 본다는 사실을 발견했습니다.
- 비유: "나는 확신이 없지만, 그렇다면 전환할 가치가 있을까요? 선두 주자가 실제로 매우 강력하고 약세인 말이 약하다면, 내가 조금 확신이 없더라도 전환해서는 안 됩니다. 하지만 선두 주자가 흔들리고 약세인 말이 강력하다면, 긴장감이 높아 전환해야 합니다."

문제점:
Thompson Sampling 은 때로 "너무 호기심 많게" 됩니다. 전환의 이득인 "긴장감"이 실제로 낮을지라도, 약간의 불확실성만 있어도 성적이 좋지 않은 옵션을 계속 탐색합니다. 마치 케이크가 괜찮다고 레시피가 말해주는데도 불안해서 30 초마다 오븐을 확인하는 것과 같습니다.

해결책: "한 단계" 수정

이 논문은 Thompson Sampling 을 비판하는 데 그치지 않고, "완벽한" 알고리즘을 구동하는 동일한 논리를 사용하여 이를 수정할 방법을 제시합니다.

그들은 정책 개선(Policy Improvement) 단계를 제안합니다.

비유: 시험을 치르는 학생이라고 상상해 보세요.
- Thompson Sampling: 현재의 직감에 기반하여 질문에 답합니다.
- 개선: 답안지를 제출하기 전에 잠시 멈춰서 답을 살펴보고 "이 질문에 답한 후에 알게 된 것을 미리 알았다면, 답을 바꿨을까?"라고 묻습니다.
- 결과: 저자들은 이렇게 단 한 번의 "앞을 내다보는" 단계를 수행함으로써 Thompson Sampling 의 결함 대부분을 해결할 수 있음을 보여줍니다. 이는 알고리즘을 순수하게 "불확실성"에 의해 구동되는 것에서 "긴장감"에 의해 구동되도록 변환합니다.

실험에서 이 단일 조정으로 유명한 Thompson Sampling 과 이론적 "완벽한" 알고리즘 사이의 성능 격차를 90% 줄였습니다.

주요 교훈 요약

Thompson Sampling 은 최적화기입니다: 단순한 휴리스틱이 아니라 특정 유형의 제곱 오차를 최소화하는 알고리즘입니다.
결함: "불확실성"(내가 얼마나 혼란스러운지) 이 아니라 "긴장감"(전환할 가치가 있는가?) 에 의존합니다. 이로 인해 때때로 과도하게 탐색합니다.
해결책: 표준적인 "정책 개선" 단계 (한 단계 앞을 내다봄) 를 적용함으로써 알고리즘이 "긴장감"에 집중하도록 변경할 수 있습니다.
결과: 이 간단한 조정으로 알고리즘은 거의 완벽해져서 복잡한 새로운 수학 없이도 이론상 최선의 전략과 거의 동일한 성능을 발휘합니다.

이 논문은 본질적으로 다음과 같이 말합니다: "우리는 Thompson Sampling 의 비밀 레시피를 알아냈습니다. 그것은 훌륭하지만, 올바른 종류의 긴장감에 초점을 맞추도록 약간의 향신료 (규제) 를 살짝 조정하면 더 좋아집니다."

기술적 요약: 톰슨 샘플링에 대한 더 넓은 관점

문제 제기
톰슨 샘플링 (TS) 은 경험적 성공과 이론적 후회 (regret) 한계로 잘 알려진 다중 팔 밴딧 (MAB) 문제에 널리 사용되는 휴리스틱입니다. 그러나 상한 신뢰 구간 (UCB) 또는 깃틴스 지수 정책과 달리, TS 의 탐색과 활용 사이의 균형을 규율하는 명시적 최적화 원칙은 불투명합니다. 깃틴스 (1979) 는 최적 정책을 유도하기 위해 베이지안 MAB 를 마르코프 결정 과정 (MDP) 으로 공식화했지만, 이 접근법은 무한 시간 범위 할인 보상에 의존합니다. 이러한 공식화는 "불완전한 학습"(최적의 팔을 무한히 자주 식별하지 못함) 을 초래하여, MAB 문헌의 핵심인 유한 시간 범위 후회 최소화 목표와 모순됩니다 (Robbins 1952; Lai and Robbins 1985). 본 논문은 동적 프로그래밍의 실용성을 유지하면서 유한 시간 범위 후회 최소화와 정렬되는 "신뢰할 수 있는" 정적 (stationary) 공식을 모색함으로써 TS 이해의 격차를 해소합니다.

방법론
저자들은 비정적 유한 시간 범위 후회 최소화 문제를 정적 온라인 최적화 문제로 재구성하기 위해 신뢰할 수 있는 정적화 (faithful stationarization) 프레임워크를 제안합니다.

제곱 후회 목적 함수: 누적 후회 $R_T$ 를 직접 최소화하거나 할인 보상을 사용하는 대신, 저자들은 누적 제곱 후회 $R_2$ 를 최소화하는 것을 도입합니다. 그들은 $R_T \leq \sqrt{R_2 \cdot T}$ 라는 한계를 설정합니다. 무한 시간 범위 제곱 후회의 합 $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ 을 최소화함으로써 정책이 최적의 $O(\sqrt{T})$ 후회율을 달성하면서도 정적 목적 함수를 제공함을 입증합니다.
정적 벨만 방정식: 이 새로운 목적 함수는 가치 함수 $V(\pi_t)$ (최소 미래 제곱 후회) 에 대한 정적 벨만 방정식을 산출합니다:
$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$
깃틴스 지수 (선형 할인 보상을 최대화함) 와 달리, 이 최소화는 행동 확률에 대해 이차적이므로 결정론적이 아닌 확률적 최적 정책을 유도합니다.
온라인 최적화 형태: 다음 라운드 기대 보상 $x_t$ 에 초점을 맞춘 변수 변환을 통해, 저자들은 $R_2$ 최적 정책 ( $Q_{R2}$ ) 이 다음과 같은 온라인 최적화 문제 형태를 취함을 유도합니다:
$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$
여기서 첫 번째 항은 즉각적 활용 (탐욕성) 을 나타내고, 두 번째 항은 탐색을 나타내는 선형 정규화 항입니다. 정규화 항 $\nu_{R2}(\pi_t)$ 는 벨만 방정식에서 유도되며, 팔을 당기는 것 사이의 미래 가치 차이를 통해 탐색과 활용 사이의 **긴장 (tension)**을 측정합니다.
톰슨 샘플링의 재해석: 저자들은 톰슨 샘플링이 정확히 동일한 온라인 최적화 형태를 허용함을 보여줍니다:
$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$
그러나 그 정규화 항 $\nu_{TS}(\pi_t)$ 는 보상 차이 ( $\theta_1 - \theta_2$ ) 와 최적 팔의 정체성 ( $\text{sign}(\theta_1 - \theta_2)$ ) 사이의 **이분산 공분산 (biserial covariance)**입니다. 이 정규화 항은 즉각적 보상과 미래 가치 사이의 긴장이 아니라, 어떤 팔이 더 나은지에 대한 불확실성을 측정합니다.

주요 기여

신뢰할 수 있는 정적화: 본 논문은 휴리스틱 샘플링과 원칙적인 동적 프로그래밍 사이의 격차를 메우는 유한 시간 범위 후회 최소화의 본질을 보존하는 정적 공식 (제곱 후회 최소화) 을 도입합니다.
구조적 통합: 톰슨 샘플링과 벨만 최적 정책 ( $Q_{R2}$ ) 모두 탐욕성과 정규화 항 사이의 균형을 맞추는 온라인 최적화 알고리즘의 사례임을 밝힙니다.
메커니즘 식별: 본 논문은 TS 를 주도하는 구체적인 메커니즘을 식별합니다: TS 는 불확실성(이분산 공분산) 을 기반으로 탐욕성을 정규화하는 반면, 최적 정책은 긴장(미래 가치 차이) 을 기반으로 정규화합니다.
정책 개선: 벨만 프레임워크를 활용하여 저자들은 TS 에 대한 표준 정책 개선 단계를 제안합니다. TS 의 가치 함수를 평가하고 이를 벨만 방정식에 다시 대입함으로써, 긴장 기반 정규화 항을 사용하는 개선된 정책 ( $Q_{TS'}$ ) 을 유도합니다.

결과

성능 격차: 가우시안 및 베르누이 밴딧에 대한 수치 실험은 $R_2$ 최적 정책 ( $Q_{R2}$ ) 이 톰슨 샘플링보다 현저히 낮은 누적 후회를 달성함을 보여줍니다. 이 격차는 TS 의 정규화 항이 선도 팔이 불확실하지만 비최적 팔이 과도하게 활용될 때 "긴장"을 포착하지 못하는 불확실성 측정치이기 때문으로 귀결됩니다.
정보 지향 샘플링 (IDS): 본 논문은 또 다른 휴리스틱인 IDS 가 $Q_{R2}$ 와 동일한 긴장 기반 정규화 항 구조를 공유하며 벨만 최적 정책과 거의 동일한 성능을 보임을 발견하여, 정보 이론적 관점과 동적 프로그래밍 관점을 연결합니다.
한 단계 개선: 톰슨 샘플링에 적용된 단일 정책 개선 단계는 TS 와 벨만 최적 기준 간의 성능 격차의 약 90% 를 해소합니다. 이 개선은 TS 의 정규화 항을 불확실성 측정에서 긴장 측정으로 효과적으로 변환합니다.
K-팔 사례의 구조적 속성: K-팔 설정에서 벨만 최적 정책 (및 개선된 TS) 은 어떤 라운드에서도 최대 두 개의 팔에만 양의 확률을 할당하는 반면, 표준 TS 는 모든 팔에 양의 확률을 할당할 수 있습니다. 정책 개선 단계는 TS 에 이러한 구조적 희소성을 부여합니다.

의의
본 논문은 ��슨 샘플링을 온라인 최적화 알고리즘으로 재구성함으로써 톰슨 샘플링에 대한 "더 넓은 관점"을 제공한다고 주장합니다. 이 렌즈는 다음과 같습니다:

휴리스틱 설명: TS 가 잔여 불확실성의 측정치로 탐욕성을 정규화함으로써 탐색과 활용의 균형을 맞춘다는 것을 명확히 합니다.
한계 식별: TS 가 긴장이 아닌 불확실성에 의존함으로써 특정 영역 (예: 최적 팔은 불확실하지만 비최적 팔은 명확히 과도하게 활용될 때) 에서 비최적 행동을 초래함을 지적합니다.
원칙적 개선 가능: 사후 샘플링 알고리즘을 개선하기 위한 엄격한 프레임워크를 제공합니다. 정규화 항을 벨만 최적 긴장 측정치와 정렬함으로써, 저자들은 TS 가 샘플링 기반 성격을 포기하지 않고도 최소한의 계산 오버헤드 (단일 정책 반복 단계) 로 크게 향상될 수 있음을 보여주며, 이를 이론적 최적에 더 가깝게 만듭니다.