Bayesian Bandit·탐색의 미래 가치

보상은 수익인 동시에 정보다

Bandit은 평균 보상을 모르는 여러 arm 중 하나를 선택합니다. 활용은 현재 기대 보상이 높은 arm을 선호합니다. 탐색은 관측 결과가 이후 선택을 개선할 수 있다는 점을 평가합니다. 따라서 탐색이 단순히 무작위로 고르는 것과 같은 뜻은 아닙니다. 유한 Bayesian 계획은 미래 정보 가치 때문에 불확실한 arm을 의도적으로 선택할 수 있습니다.

이 단원은 앞 관측·중단 예제의 비용 최소화와 달리 기대 보상을 최대화합니다. 값이 클수록 좋습니다. 모든 조건부 기대를 계산할 수 있는 작은 모형을 사용하며 한 표본 경로를 최적값의 추정치로 삼지 않습니다.

고정된 평균과 그에 대한 불확실성을 구분한다

두 arm의 Bernoulli 평균 theta0,theta1은 고정되어 있지만 알려져 있지 않으며 독립 Beta 사전을 갖습니다. 한 arm의 평균을 조건으로 하면 보상들은 IID입니다. 매번 평균 자체를 사전에서 새로 뽑는 것이 아닙니다. 사전으로 평균을 적분한 보상들은 같은 미지의 평균을 공유하므로 서로 의존할 수 있습니다.

Beta(a,b)의 밀도는 theta^(a-1)(1-theta)^(b-1)에 비례하고, 예측 성공 확률은 a/(a+b), 분산은 ab/((a+b)²(a+b+1))입니다. 양의 a,b는 사전 hyperparameter이며 실제로 관측한 성공·실패 수일 필요는 없습니다. 성공하면 (a+1,b), 실패하면 (a,b+1)로 바꾸며 선택한 arm만 갱신합니다.

두 쌍의 사후 매개변수와 남은 예산 H가 의사결정 상태입니다. 정수 매개변수와 최대 여섯 pull로 정확한 기대 계산을 대화형으로 실행합니다. 이 범위는 실습 모형의 계산 한계이며 실제 bandit 학습을 여섯 번으로 제한한다는 뜻이 아닙니다.

행동 가치에 미래 학습을 넣는다

두 사후 쌍을 포함한 상태를 s라고 합시다. Arm i의 예측 성공 확률을 p_i, 성공·실패 뒤 상태를 s_i+,s_i-라고 하면 V0=0에서

입니다. 첫 항은 즉시 기대 보상이고 나머지는 결과를 관측한 뒤 최적으로 결정하는 가치입니다. 어떤 arm을 선택하느냐가 미래에 무엇을 알게 되는지를 바꾸므로 belief 상태의 Bellman 계산입니다. 서로 다른 이력에서 같은 사후 상태에 도달하면 memoization으로 계산을 재사용합니다. 부동소수점 반올림을 제외하면 모형의 유한 기대를 직접 계산하며 Monte Carlo 근사가 아닙니다.

이 정책은 H를 명시적으로 사용합니다. 한 번만 남으면 정보의 미래 용도가 없으므로 큰 예측 평균을 고릅니다. 여러 번 남으면 현재 평균의 손해를 더 나은 이후 결정이 상쇄할 수 있습니다. Q가 부동소수점에서 정확히 같으면 arm0을 택하며 동률 근처의 아주 작은 차이를 강한 실질적 우위로 해석하지 마세요.

Greedy 비교 정책에도 같은 데이터를 준다

적응형 myopic greedy는 매 단계 사후 평균이 높은 arm을 선택하고 관측 결과로 다시 갱신합니다. 처음 좋아 보인 arm만 끝까지 고정하는 정책이 아닙니다. 같은 결과 확률로 전체 기대 보상을 계산하되, 행동은 미래 최적 가치가 아닌 현재 평균으로 정합니다.

두 정책은 같은 모형과 관측 기회를 받으며 미래 정보의 가치를 평가하는 방식이 다릅니다. 다음 단원의 posterior sampling은 또 다른 규칙입니다. 그럴듯한 평균을 표본 추출해 가장 좋은 arm을 고르는 것과 이 유한 Bellman 식을 푸는 것은 일반적으로 같지 않습니다.

밀도와 가상 사후를 올바르게 읽는다

위 그림은 선택 arm의 가상 보상 전후 Beta 밀도입니다. 파랑은 그 갱신 전, 주황은 갱신 후입니다. 선택한 arm·보상은 최적 첫 행동이나 실제로 발생한 결과와 같을 필요가 없습니다. 밀도의 높이는 1보다 클 수 있으며 확률은 곡선의 높이가 아니라 면적입니다.

아래 그래프는 예산에 따른 기대 총보상을 비교합니다. 파랑은 Bayesian 최적값, 주황은 적응형 greedy입니다. 실제 누적 보상의 표본 경로가 아닙니다. 차이가 작더라도 실제 값의 차이이므로 Q와 전체 우위를 수치로 함께 표시합니다. 가상 보상만 바꾸면 밀도 비교가 바뀌며 처음의 의사결정 문제는 바뀌지 않습니다.

손계산 문제: 두 균등 사전

두 arm에 Beta(1,1) 사전을 주고 두 번 뽑을 수 있다고 합시다. 첫 선택이 arm0이고 두 번째는 사후 평균이 높은 쪽을 선택할 때 기대 총보상을 구하세요.

해설. 즉시 평균은 1/2입니다. 확률 1/2로 성공하면 arm0 평균이 2/3이 되어 arm1의 1/2보다 큽니다. 실패하면 arm0 평균이 1/3이므로 다음에는 arm1을 택합니다. 전체 기대는

입니다. 한 arm에 고정하면 두 번의 기대 보상은 1입니다. 학습으로 H*초기 최대 평균을 넘을 수 있으므로 그 값을 적응형 Bayesian 정책의 상한이라고 부르면 안 됩니다. 한 보상이 최대 1이므로 이 모형의 보편적인 상한은 H입니다.

낮은 평균을 탐색하는 예제

Arm0에는 Beta(4,3), arm1에는 Beta(1,1)을 줍니다. 평균은 4/7과 1/2, 분산은 3/98과 1/12입니다. H=1에서는 arm0을 택하지만 H=4의 유한 계산은

입니다. 두 번째가 1/42만큼 크므로 현재 평균이 더 작은 arm1부터 선택합니다. 최적 총가치는 50/21, 적응형 greedy는 65/28이므로 전체 정책의 기대 보상 차이는 5/84입니다. 첫 행동의 Q 차이와 다른 정책 전체의 보상 차이는 서로 다른 양입니다.

두 번째 안내 예제에서 이 비교를 확인하세요. 이어 arm1의 가상 실패를 선택하면 그 사후는 Beta(1,2), arm0은 Beta(4,3) 그대로입니다. 알 수 없는 arm의 평균은 1/3으로 떨어집니다. 불확실성으로 실험을 정당화한 뒤 그 결과로 이후 선택을 바꾸는 구조입니다.

같은 재귀를 다시 쓰지 않고 계획을 검산한다

작은 예산에서는 모든 조건부 행동 트리를 별도로 열거합니다. 트리와 보상열을 고정하면 arm별 사전 예측 우도는 Beta 함수의 비율로 적분할 수 있습니다. 각 열의 보상을 그 확률로 평균하면 실제 사후 재귀와 다른 경로로 정책을 평가합니다. 정확한 분수 fixture로 네 번 예제를 확인하고 밀도 적분으로 정규화와 모멘트를 검산합니다.

이는 현재 유한 구현의 근거입니다. Arm이 많거나 예산이 길고, 보상이 연속이거나 사전이 틀리면 정확한 계획은 더 어려워집니다. 다른 할인·무한 시간 모형의 Gittins index 결과를 이 유한 계산의 최적성 주장으로 그대로 가져오지 않습니다.

AI 연구로의 연결

탐색은 보상뿐 아니라 데이터도 배분합니다. 학습한 모형이나 사전이 어떤 데이터를 수집할지 바꾸므로 다른 arm의 데이터가 많다고 잘못된 사전이 자동으로 교정되는 것은 아닙니다. Bayesian 기대 보상은 지정한 사전으로 평균하며 고정된 실제 평균에서의 regret와 다릅니다. 다음 seed 시뮬레이션에서는 그 평가 기준을 구분하면서 실용적인 탐색 규칙을 비교합니다.

원전과 읽을거리

Lattimore·Szepesvari의 Bandit Algorithms은 Bayesian bandit의 넓은 틀을 제공합니다. 유한 두 arm 예제, 분수 검산, 조건부 트리 비교, 밀도 도식과 적응형 greedy 비교는 이 교재를 위해 직접 구성했습니다.