강화 학습: 상한 신뢰 구간 (UCB) 알고리즘 이해하기

강화 학습 (Reinforcement Learning, RL)은 에이전트가 환경과 상호 작용하며 보상을 최대화하도록 학습하는 머신 러닝의 한 분야입니다. 탐험 (exploration)과 이용 (exploitation) 사이의 균형을 맞추는 것은 강화 학습에서 중요한 과제입니다. 에이전트는 새로운 정보를 탐색하고 더 많은 보상을 받을 수 있는 행동을 시도해야 하지만, 이미 좋은 결과를 보이는 행동을 최대한 활용하여 보상을 극대화해야 합니다. 본 글에서는 탐험과 이용의 균형을 맞추기 위한 방법 중 하나인 상한 신뢰 구간 (Upper Confidence Bound, UCB) 알고리즘에 대해 자세히 알아보겠습니다.
—

🤔 UCB란 무엇인가요? (What is UCB?)

UCB는 탐험과 이용의 균형을 맞추기 위한 알고리즘입니다. 각 행동의 평균 보상과 불확실성을 고려하여, 현재까지 얻은 정보로부터 가장 좋은 행동을 선택합니다. UCB는 각 행동에 대한 '상한 신뢰 구간'을 계산하여, 이 구간이 가장 높은 행동을 선택합니다. 상한 신뢰 구간은 평균 보상, 방문 횟수, 그리고 신뢰도 계수를 사용하여 계산됩니다.
—

💡 UCB 알고리즘 작동 방식 (How UCB Algorithm Works)

UCB 알고리즘은 다음과 같은 단계로 작동합니다:

1. 초기화 (Initialization): 각 행동에 대한 초기 보상, 방문 횟수, 그리고 상한 신뢰 구간을 초기화합니다. 일반적으로, 각 행동에 대한 초기 보상은 0으로 설정하고, 방문 횟수는 0으로 설정합니다.
2. 행동 선택 (Action Selection): 각 행동의 상한 신뢰 구간을 계산합니다. 상한 신뢰 구간이 가장 높은 행동을 선택합니다.
3. 보상 획득 및 업데이트 (Reward Acquisition and Update): 선택된 행동을 수행하고, 환경으로부터 보상을 얻습니다. 선택된 행동의 평균 보상과 방문 횟수를 업데이트합니다.
4. 반복 (Iteration): 2단계와 3단계를 반복하여 학습을 진행합니다.

UCB의 핵심은 각 행동의 불확실성을 측정하는 것입니다. 더 적은 횟수로 선택된 행동은 불확실성이 높으므로, UCB는 이러한 행동을 더 자주 선택하여 탐험을 장려합니다. 반면, 더 많은 횟수로 선택되어 높은 보상을 얻은 행동은 상한 신뢰 구간이 높아져 이용을 장려합니다.
—

💻 UCB 알고리즘 구현 (UCB Algorithm Implementation) - Python 코드 예시

다음은 UCB 알고리즘을 Python으로 간단하게 구현한 예시입니다. 이 코드는 여러 슬롯 머신 (bandit machine)을 탐험하는 상황을 시뮬레이션합니다.

import numpy as np

class UCB:
    def __init__(self, num_arms, c=2):
        self.num_arms = num_arms
        self.counts = np.zeros(num_arms)
        self.values = np.zeros(num_arms)
        self.c = c  # 탐험 정도를 조절하는 상수

    def select_arm(self):
        for i in range(self.num_arms):
            if self.counts[i] == 0:
                return i  # 각 슬롯 머신을 한 번씩 시도

        ucb_values = self.values + self.c * np.sqrt(np.log(np.sum(self.counts)) / self.counts)
        return np.argmax(ucb_values)

    def update(self, arm, reward):
        self.counts[arm] += 1
        n = self.counts[arm]
        value = self.values[arm]
        new_value = ((n - 1) / n) * value + (1 / n) * reward
        self.values[arm] = new_value

# 슬롯 머신 시뮬레이션 (예시)
num_arms = 10
# 각 슬롯 머신의 평균 보상 (알 수 없음)
true_means = np.random.rand(num_arms)
num_trials = 1000

# UCB 알고리즘 실행
ucb = UCB(num_arms)
rewards = np.zeros(num_trials)

for t in range(num_trials):
    arm = ucb.select_arm()
    # 실제 보상 (평균 보상 주변의 랜덤 값)
    reward = np.random.normal(true_means[arm], 0.1)  # 정규 분포
    ucb.update(arm, reward)
    rewards[t] = reward

print("선택된 각 슬롯 머신의 횟수:", ucb.counts)
print("각 슬롯 머신의 평균 보상 추정치:", ucb.values)

이 코드에서 UCB 클래스는 UCB 알고리즘을 구현합니다. select_arm() 메서드는 UCB 값을 계산하고 가장 높은 값을 가진 슬롯 머신을 선택합니다. update() 메서드는 선택된 슬롯 머신으로부터 얻은 보상을 기반으로 평균 보상과 방문 횟수를 업데이트합니다. c 값은 탐험의 정도를 조절하는 하이퍼파라미터입니다. 이 예시에서는 각 슬롯 머신에서 얻은 보상이 정규 분포를 따른다고 가정했습니다.
—

📐 UCB 계산식 (UCB Formula)

UCB는 다음과 같은 공식을 사용하여 각 행동의 상한 신뢰 구간을 계산합니다.

UCB(action) = (평균 보상) + c * √(ln(총 방문 횟수) / (해당 행동의 방문 횟수))

여기서:

• 평균 보상은 해당 행동을 수행했을 때 얻은 보상의 평균입니다.
• c는 탐험 정도를 조절하는 하이퍼파라미터입니다. c 값이 클수록 탐험을 더 많이 하고, 작을수록 이용을 더 많이 합니다.
• ln은 자연 로그입니다.
• 총 방문 횟수는 모든 행동을 수행한 총 횟수입니다.
• 해당 행동의 방문 횟수는 특정 행동을 수행한 횟수입니다.

이 공식은 평균 보상과 불확실성을 모두 고려합니다. 평균 보상이 높을수록 UCB 값이 높아지고, 방문 횟수가 적을수록 (즉, 불확실성이 높을수록) UCB 값이 높아집니다. 이로 인해 UCB는 탐험과 이용 사이의 균형을 맞출 수 있습니다.
—

🤔 UCB의 장점 (Advantages of UCB)

• 이론적 보장 (Theoretical Guarantees): UCB는 일정한 조건 하에서 최적 행동을 선택하는 데 수렴하는 이론적 보장을 제공합니다. 이는 다른 휴리스틱 방법보다 강력한 장점입니다.
• 간단한 구현 (Simple Implementation): UCB 알고리즘은 비교적 간단하게 구현할 수 있습니다. 위에 제시된 Python 코드 예시에서 볼 수 있듯이, 핵심 로직은 몇 줄의 코드로 표현됩니다.
• 효율적인 탐험 (Efficient Exploration): UCB는 각 행동의 불확실성을 고려하여 효율적으로 탐험합니다. 불확실성이 높은 행동을 더 자주 선택하여 탐험을 장려합니다.
  —

👎 UCB의 단점 (Disadvantages of UCB)

• 탐험 정도 조절 (Exploration Tuning): UCB 알고리즘의 성능은 탐험 정도를 조절하는 하이퍼파라미터 c 값에 민감하게 영향을 받습니다. 적절한 c 값을 선택하는 것은 문제에 따라 어려울 수 있습니다.
• 과도한 탐험 (Excessive Exploration): UCB는 초기에 방문 횟수가 적은 행동을 과도하게 탐험할 수 있습니다. 이는 초기 단계에서 성능을 저하시킬 수 있습니다.
• 환경에 대한 사전 정보 필요 (Prior Knowledge About Environment): UCB는 환경에 대한 사전 정보를 필요로 할 수 있습니다. 예를 들어, 보상의 범위나 분산에 대한 추정이 필요할 수 있습니다. 이러한 정보가 없을 경우 성능이 저하될 수 있습니다.
  —

📝 핵심 용어 정리 (Key Terms Summary)

• 강화 학습 (Reinforcement Learning, RL): 에이전트가 환경과 상호 작용하며 보상을 최대화하도록 학습하는 머신 러닝의 한 분야입니다.
• 탐험 (Exploration): 새로운 정보를 탐색하고 더 많은 보상을 받을 수 있는 행동을 시도하는 과정입니다.
• 이용 (Exploitation): 이미 좋은 결과를 보이는 행동을 최대한 활용하여 보상을 극대화하는 과정입니다.
• 상한 신뢰 구간 (Upper Confidence Bound, UCB): 탐험과 이용의 균형을 맞추기 위한 알고리즘입니다. 각 행동의 평균 보상과 불확실성을 고려하여, 현재까지 얻은 정보로부터 가장 좋은 행동을 선택합니다.
• 슬롯 머신 (Bandit Machine): 여러 개의 레버가 있는 가상의 기계로, 각 레버를 당기면 다른 보상을 얻을 수 있습니다. (예시에서 사용)
• 평균 보상 (Average Reward): 특정 행동을 수행했을 때 얻은 보상의 평균입니다.
• 불확실성 (Uncertainty): 행동에 대한 정보가 얼마나 부족한지를 나타내는 척도입니다. UCB에서는 방문 횟수가 적을수록 불확실성이 높다고 판단합니다.
• 하이퍼파라미터 (Hyperparameter): 알고리즘의 성능을 조절하는 데 사용되는 매개변수입니다. UCB에서는 c 값이 해당됩니다.

—

결론적으로, UCB 알고리즘은 강화 학습에서 탐험과 이용의 균형을 맞추는 효과적인 방법입니다. 각 행동의 불확실성을 고려하여, 에이전트가 환경과 효율적으로 상호 작용하며 보상을 최대화하도록 돕습니다. UCB는 이론적인 보장과 간단한 구현으로 인해 널리 사용되며, 다양한 강화 학습 문제에 적용될 수 있습니다. 다만, 하이퍼파라미터 조절의 어려움과 과도한 탐험의 가능성을 고려하여 문제에 맞는 적절한 설정을 해야 합니다.