Multi-Armed Bandits: 작업을 위한 최고의 강화 학습 솔루션

MAB(Multi-Armed Bandits)는 강화 학습 세계의 초석을 형성하며 탐색과 활용 사이의 최적의 균형을 요구하는 시나리오를 협상하는 강력한 메커니즘을 제공합니다. 탐색은 새로운 옵션을 시도하는 것을 의미하고, 활용은 현재 최선의 옵션을 고수하는 것을 의미합니다. 이러한 상황에서 MAB는 지능형 학습 메커니즘으로 인해 탁월한 선택이 되는 경우가 많습니다.

먼저 MAB의 개념을 살펴보겠습니다. "외팔이 도둑"으로 알려진 일련의 슬롯 머신에 둘러싸인 도박꾼을 상상해 보십시오. 여기에서 내려야 할 중요한 결정에는 플레이할 기계, 플레이 순서 및 플레이 빈도를 결정하는 것이 포함됩니다. 문제는 각 기계가 서로 다르고 불확실한 보상을 제공한다는 것입니다. 궁극적인 목표는 일련의 플레이에서 가장 높은 누적 보상을 모으는 것입니다.

다중 무장 도적이란 무엇입니까?

"다중 무장 도적(multi-armed bandit)"이라는 이름은 일렬로 늘어선 슬롯머신에서 도박꾼(종종 "외팔 도적"으로 알려짐)과 관련된 사고 실험에서 유래되었습니다. 도박꾼은 총 보상을 최대화하기 위해 어떤 기계를 플레이할지, 각 기계를 몇 번 플레이할지, 어떤 순서로 플레이할지 결정해야 합니다.

보다 공식적인 정의에서 MAB 문제는 튜플(A, R)입니다.

MAB 문제의 목표는 주어진 라운드 수에 걸쳐 예상되는 총 보상 Q 를 최대화하는 정책 π (과거 데이터를 행동으로 매핑)를 찾는 것입니다.

MAB의 주요 딜레마는 "탐색"과 "착취" 사이의 균형입니다.

1. 탐색에는 다양한 부문을 시도하여 이들이 얻을 수 있는 보상에 대해 자세히 알아보는 작업이 포함됩니다. 여기에는 최적이 아닌 팔을 끌어오는 것이 포함될 수 있지만 시스템에 대한 정보를 수집하는 데 도움이 됩니다.
2. 익스플로잇(Exploitation)은 에이전트가 지금까지 수집한 정보를 기반으로 현재 가장 높은 기대 보상을 받을 것으로 믿는 팔을 당기는 것을 포함합니다.

탐색과 활용의 균형을 맞추는 것은 강화 학습 및 MAB 문제의 핵심 과제입니다.

이 문제를 해결하기 위해 Epsilon-Greedy, UCB(Upper Confidence Bound) 및 Thompson Sampling 전략을 포함한 다양한 알고리즘이 개발되었습니다.

MAB의 확장으로서 Contextual Bandits에 대한 자세한 검토는 다음 기사에서 다루겠습니다.

엡실론(ε)-탐욕

Epsilon(ε)-Greedy 전략은 간단한 원칙을 따릅니다. 대부분의 경우 (1 - ε)로 정량화되어 가장 높은 추정 보상을 산출하는 작업을 선택하여 가장 잘 알려진 옵션을 활용합니다. 그러나 나머지 시간은 ε으로 정량화되어 무작위 행동을 선택하여 새로운 가능성을 탐색합니다. 이 전략의 독창성은 탐색 단계에서 가장 보람 있는 행동과 동일한 확률로 덜 보람 있는 행동을 선택할 수 있다는 경고에도 불구하고 단순성과 효율성에 있습니다. 그리고 ε의 값은 탐색과 활용 사이의 균형을 결정합니다.

수학적으로는 다음과 같이 정의할 수 있습니다.

이는 다음 의사코드로 정의할 수 있습니다.

 Initialize Q(a) for all a Repeat: Generate a random number p between 0 and 1 If p < epsilon: Select a random action a Else: Select action a with the highest Q(a) Execute action a and observe reward r Update Q(a) = Q(a) + alpha * (r - Q(a))

Epsilon-Greedy 전략의 Pythonic 구현은 매우 간단합니다.

 import numpy as np class EpsilonGreedy: def __init__(self, epsilon, counts, values): self.epsilon = epsilon self.counts = counts self.values = values def select_arm(self): if np.random.random() < self.epsilon: return np.random.choice(len(self.values)) else: return np.argmax(self.values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

ε-탐욕 알고리즘은 단순성이라는 이점과 여러 단계 이후에도 계속 탐색할 것이라는 보장(약간)을 제공합니다. 그러나 UCB나 Thompson Sampling과 달리 탐색할 때 각 작업에 대해 얼마나 알려진지는 고려하지 않습니다.

UCB

반대로, UCB 전략은 행동을 결정할 때 예상 보상과 관련 불확실성 또는 분산을 모두 고려합니다. 불확실성이 높은 행동을 선호하고 불확실성을 줄이고 보다 생산적인 탐사 단계를 보장합니다. UCB 전략은 수학적으로 다음과 같이 정의됩니다.

Python 구현은 다음과 같습니다.

 class UCB: def __init__(self, counts, values): self.counts = counts self.values = values def select_arm(self): n_arms = len(self.counts) for arm in range(n_arms): if self.counts[arm] == 0: return arm ucb_values = [0.0 for arm in range(n_arms)] total_counts = sum(self.counts) for arm in range(n_arms): bonus = sqrt((2 * log(total_counts)) / float(self.counts[arm])) ucb_values[arm] = self.values[arm] + bonus return np.argmax(ucb_values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

UCB의 탐색과 활용 사이의 균형은 해당 공식에서 비롯됩니다. 즉, 행동의 추정 가치와 시간이 지남에 따라 감소하지만(행동에 대해 더 많이 학습됨에 따라) 해당 행동에 대한 불확실성이 증가함에 따라 증가하는 항입니다. 따라서 알고리즘은 불확실성이 높고 잠재적 보상이 높은 부문을 탐색하는 경향이 있습니다.

톰슨 샘플링

Thompson Sampling은 다중 무장 적기 문제에 대한 베이지안에서 영감을 받은 알고리즘입니다. 각 적기(또는 각 행동)의 보상 확률에 사전 분포를 할당한 다음 보상이 관찰되면 이러한 사전 분포를 업데이트합니다. 행동 선택은 최선의 행동에 대한 사후 분포에 따라 확률적입니다.

Beta-Bernoulli 프레임워크에서는 각 적기의 보상 분포를 Bernoulli 분포(즉, 이진 보상 0 또는 1)로 간주합니다. 그런 다음 보상을 받을 확률 이전에 베타를 할당합니다. 베타 분포는 베르누이 분포의 공액 사전 분포이므로 사후 업데이트가 쉽습니다.

논리:

1. 각 적기에게 매개변수 α=1, β=1(균일 사전)을 사용하여 베타 분포를 할당합니다.

2. 각 라운드마다:

   1. 각 적기의 현재 베타 분포에서 난수를 샘플링합니다.
   2. 샘플링된 숫자가 가장 높은 적기를 선택하고 해당 적기를 끌어옵니다.
   3. 끌어낸 적기의 보상을 관찰하세요. 성공(1)이라면 적기의 α를 1만큼 증가시킨다. 실패(0)이면 적기의 β를 1 증가시킨다.
   4. 2단계와 3단계를 반복합니다.

 import numpy as np from scipy.stats import beta class Bandit: def __init__(self, true_probability): self.true_probability = true_probability self.alpha = 1 self.beta = 1 def pull(self): return np.random.random() < self.true_probability def sample(self): return np.random.beta(self.alpha, self.beta) def update(self, reward): self.alpha += reward self.beta += (1 - reward) def Thompson(bandits, num_trials): rewards = np.zeros(num_trials) for i in range(num_trials): # Thompson sampling j = np.argmax([b.sample() for b in bandits]) # Pull the arm for the bandit with the largest sample reward = bandits[j].pull() # Update rewards log rewards[i] = reward # Update the distribution for the bandit whose arm we just pulled bandits[j].update(reward) return rewards # Suppose we have 3 bandits with these true probabilities true_probabilities = [0.2, 0.5, 0.75] bandits = [Bandit(p) for p in true_probabilities] # Run experiment rewards = Thompson(bandits, num_trials=10000) # Print the total reward print("Total reward earned:", rewards.sum()) print("Overall win rate:", rewards.sum() / len(rewards))

따라서 Thompson Sampling은 불확실한 작업(값 분포가 분산된 작업)을 "탐색"하고 높은 가치를 가질 수 있다고 생각되는 작업(분포가 높은 값 쪽으로 치우쳐 있는 작업)을 "이용"합니다.

시간이 지남에 따라 각 작업에 대해 더 많이 학습할수록 분포는 더욱 정점에 도달하고 알고리즘에 의해 선택된 작업은 가장 높은 기대 값을 가진 작업으로 수렴되는 경향이 있습니다.

Thompson Sampling의 탐색/이용 균형은 분포 형태에 따라 자연스럽게 나타납니다. 이 방법은 매우 효과적이지만 특히 크거나 연속적인 행동 공간 또는 복잡한 보상 구조와 관련된 문제의 경우 UCB 또는 ε-탐욕보다 구현하기가 더 복잡할 수 있습니다.

Multi-Armed Bandits가 귀하의 작업에 가장 적합한 RL인 이유는 무엇입니까?

1. 단순성 : MAB 알고리즘은 잠재적으로 큰 상태-동작 값 테이블 또는 근사치를 유지하고 업데이트해야 하는 본격적인 RL 알고리즘보다 더 간단하고 계산상 효율적입니다.
2. 탐색과 활용의 균형 : MAB 알고리즘은 새로운 작업을 시도하는 것과 알려진 좋은 작업을 고수하는 것 사이의 균형을 관리하기 위한 강력한 방법을 제공합니다.
3. 실시간 적응성 : MAB 알고리즘은 행동의 보상 분포 변화에 실시간으로 적응할 수 있습니다.
4. 간편한 통합 : MAB의 단순성과 효율성 덕분에 기존 시스템에 쉽게 통합할 수 있어 중단을 최소화하면서 즉각적인 이점을 제공할 수 있습니다.
5. 광범위한 적용 가능성 : MAB는 광고(클릭률을 극대화하기 위해 표시할 광고 선택), 의료(개인화 치료 전략), 웹 페이지 최적화(A/B 테스트) 등 다양한 분야에 성공적으로 적용되었습니다.

MAB의 응용

MAB(Multi-Armed Bandits)는 다양한 산업과 영역에 걸쳐 폭넓게 응용됩니다. 다음은 사용 방법에 대한 몇 가지 예입니다.

1. 온라인 광고 : MAB는 상호 작용을 기반으로 사용자에게 표시할 광고 선택을 동적으로 조정하는 데 사용될 수 있습니다. 이는 시간이 지남에 따라 클릭률이나 전환을 극대화하는 데 도움이 됩니다.
2. 임상 시험 : 의학 연구에서 MAB 알고리즘을 사용하여 환자를 다양한 치료법에 동적으로 할당할 수 있습니다. 이를 통해 더 많은 환자가 가장 효과적인 치료법을 받을 수 있게 되어 항상 최선의 치료법을 선택하지 않아 발생하는 후회, 즉 손실을 줄일 수 있습니다.
3. 뉴스 기사 추천 : 뉴스 웹사이트에서는 MAB를 사용하여 각 사용자에게 표시되는 기사를 개인화할 수 있습니다. MAB 알고리즘은 시간이 지남에 따라 각 사용자가 어떤 유형의 기사에 관심이 있는지 학습하고 그에 따라 추천을 조정할 수 있습니다.
4. 동적 가격 책정 : 전자상거래 플랫폼이나 항공사는 MAB 알고리즘을 사용하여 가격 책정 전략을 실시간으로 최적화하고 고객 행동과 시장 역학을 기반으로 수익을 극대화할 수 있습니다.
5. 네트워크 라우팅 : 컴퓨터 네트워킹에서 MAB 알고리즘은 정체를 관리하고 패킷 라우팅을 최적화하는 데 사용될 수 있습니다. 각 경로는 하나의 팔로 처리될 수 있으며, 알고리즘은 패킷 손실이나 대기 시간을 최소화하기 위해 경로를 동적으로 선택할 수 있습니다.
6. 기계 학습 하이퍼파라미터 조정 : MAB는 기계 학습 모델에서 하이퍼파라미터 선택을 최적화하는 데에도 사용할 수 있습니다. 각 하이퍼파라미터 세트는 팔(arm)로 처리될 수 있으며, 알고리즘은 최적의 모델 구성을 찾기 위해 선택 항목을 반복적으로 세분화할 수 있습니다.

본질적으로 MAB의 유용성은 기존 강화 학습 작업을 훨씬 뛰어넘습니다. 이는 불확실한 환경에서 의사결정 프로세스를 강화하고 다양한 영역에 걸쳐 실제 문제에 대한 실용적인 솔루션을 제공하기 위한 효과적인 프레임워크를 상징합니다. 따라서 당면한 작업에 탐색과 활용의 균형이 포함될 때 MAB는 종종 의사 결정 난제에 대한 다재다능하고 강력하며 적응력이 뛰어난 솔루션을 제공하는 선택 옵션으로 등장합니다.

결론

다중 무장 도적(Multi-Armed Bandits)은 탐색과 활용의 균형을 효과적으로 맞추는 능력을 갖추고 있어 실제 세계의 많은 의사 결정 문제에 대한 강력한 솔루션을 제공합니다. 고유한 적응성과 다양성으로 인해 강화 학습 영역뿐만 아니라 의료에서 온라인 광고에 이르기까지 광범위한 애플리케이션에 걸쳐 귀중한 도구가 됩니다. 데이터 과학자, 기계 학습 애호가 또는 의사 결정 프로세스를 향상시키려는 전문가이든 MAB 전략을 이해하고 구현하는 것은 풍부하고 보람 있는 경험이 될 수 있습니다.