Multi-arm Bandits-1

n-Arm Bandit 문제

• n-Arm Bandit 문제는 에이전트가 여러 개의 팔(슬롯머신) 중 하나를 선택하여 보상을 받는 상황을 다룬다. 각 팔은 서로 다른 확률 분포에 따라 보상을 제공한다.
  이 문제는 탐색(Exploration)과 이용(Exploitation) 사이의 균형을 맞추는 것이 핵심이다:
• 탐색(Exploration): 아직 충분히 경험하지 않은 팔을 선택하여 새로운 정보를 얻는 과정이다. 이는 장기적으로 더 높은 보상을 얻기 위해 필요하다.
• 이용(Exploitation): 현재까지의 정보로 가장 높은 보상을 기대할 수 있는 팔을 선택하는 과정이다.

에이전트는 단기적인 보상 최적화보다는 장기적인 보상 기대치를 최대화하기 위해 탐색과 이용을 적절히 조절해야 한다.

행동 가치 방법

행동 가치 방법은 각 행동의 가치를 추정하는 데 사용되는 함수인 Q함수를 기반으로 한다. Q함수는 특정 행동을 취했을 때 얻을 수 있는 평균 보상을 추정하며, 이를 통해 에이전트는 각 행동의 가치를 평가할 수 있다.

\[ Q_t(a) = \frac{R_1 + R_2 + \cdots + R_{N_t(a)}}{N_t(a)} \]

여기서, \( Q_t(a) \)는 시간 \( t \)까지 행동 \( a \)의 평균 보상 추정값이다.

\( R_i \)는 \( i \)번째로 행동 \( a \)를 선택했을 때 얻은 보상이고,

\( N_t(a) \)는 시간 \( t \)까지 행동 \( a \)가 선택된 총 횟수이다.

탐욕적 행동 선택(Greedy Action Selection)

탐욕적 방법은 현재까지의 정보 중 가장 높은 Q값을 가지는 행동을 선택한다:
\[
A_t = \arg\max_a Q_t(a)
\]
그러나 이 방법만을 사용할 경우 최적의 행동이 아닌, 로컬 옵티마에 빠질 위험이 있다.

( \( \epsilon \) )-탐욕적 방법

이 문제를 해결하기 위해 ( \( \epsilon \)  )-탐욕적(ε-greedy) 방법이 사용된다. 이 방법은 대부분의 경우 탐욕적인 행동을 선택하지만, 일정 확률 ( \( \epsilon \) )로 무작위 행동을 선택하여 탐색을 진행한다. 이를 통해 모든 행동이 충분히 탐색될 수 있도록 하여 장기적인 성능 향상을 도모할 수 있다.

\( 1 - \epsilon \)과 \( \epsilon \)은 탐욕적 행동 선택과 탐색적 행동 선택 간의 비율을 조절하는 파라미터로 사용된다:

•  \( 1 - \epsilon \): 탐욕적 행동 선택의 확률을 나타내며, 현재까지의 정보로 가장 높은 가치가 있는 행동을 선택하는 비율이다.
•  \( \epsilon \): 무작위로 행동을 선택하여 새로운 정보를 탐색할 확률이다. 이 값이 클수록 탐색을 더 많이 하게 되며, 작을수록 탐욕적인 행동 선택을 더 많이 하게 된다.

탐색 확률 \( \epsilon \) 이 적절히 설정되면, 에이전트는 더 높은 평균 보상을 얻고 최적의 행동을 더 자주 선택할 수 있다. 너무 작은 \( \epsilon \)  값은 탐색 부족으로 인한 성능 저하를 가져올 수 있으며, \( \epsilon \)  = 0  인 완전한 탐욕적 방법은 장기적인 성능 향상에 한계가 있다.

 

 

점진적 업데이트(Incremental Implementation)

Q값을 효율적으로 업데이트하기 위해 점진적 업데이트 방법을 사용한다. 이는 새로운 샘플이 도착할 때마다 평균을 다시 계산하는 대신, 이전 Q값에 작은 변화를 주어 새로운 정보를 반영하는 방식이다. 점진적 업데이트 식은 다음과 같이 표현된다:
\[ Q_{k+1} = \frac{1}{k} \sum_{i=1}^{k} R_i \] \[ = \frac{1}{k} \left( R_k + \sum_{i=1}^{k-1} R_i \right) \] \[ = \frac{1}{k} \left( R_k + (k-1)Q_k + Q_k - Q_k \right) \] \[ = \frac{1}{k} \left( R_k + k Q_k - Q_k \right) \] \[ = Q_k + \frac{1}{k} \left[ R_k - Q_k \right], \]
여기서:

• \( Q_n \)은 현재까지의 Q값이다.
• \( R_n \)은 이번에 얻은 보상이다.
• \( \alpha \)는 학습률(step size = \(\frac{1}{k}\) )로, 새 정보가 기존 정보에 얼마나 영향을 미칠지를 결정한다.

이는 

\[ \text{NewEstimate} \leftarrow \text{OldEstimate} + \text{StepSize} \left[ \text{Target} - \text{OldEstimate} \right] \]

학습률 \( \alpha \)를 적절히 설정함으로써 과거 경험과 최신 정보 간의 균형을 맞추어 점진적으로 Q값을 개선할 수 있다.

 

 

 

출처: Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). The MIT Press.