Multi-Armed Bandits

K-armed Bandit Problem

K-armed bandit 문제는 강화학습에서 다루는 고전적인 문제 중 하나입니다. 이 문제는 슬롯 머신과 유사한 환경에서 에이전트가 최대의 보상을 얻기 위해 여러 선택지 중 최적의 선택지를 찾는 상황을 모델링합니다.

문제 정의

• K개의 선택지(팔): 에이전트는 매 시간 단위로 K개의 선택지 중 하나를 선택할 수 있습니다.
• 보상: 각 선택지는 확률적으로 보상을 제공하며, 각 선택지의 보상 분포는 다를 수 있습니다.
• 가치 (Value): 각 선택지의 가치는 해당 선택지를 선택했을 때 기대되는 평균 보상으로 정의됩니다.
  • 참 가치 (True Value): 선택지 ($a$)에 대해 참 가치 ($q_*(a)$)는 해당 선택지의 실제 평균 보상을 의미합니다.
  • 추정 가치 (Estimated Value): 선택지 ($a$)에 대해 추정 가치 ($\hat{q}(a)$)는 에이전트가 현재까지 관찰한 보상으로부터 추정한 평균 보상을 의미합니다.
• 목표: 장기적으로 최대의 누적 보상을 얻기 위해 최적의 선택지를 찾는 것입니다.

탐험과 활용 (Exploration and Exploitation)

• 탐험 (Exploration): 아직 충분한 정보를 얻지 못한 선택지들을 시도하여 보상에 대한 이해를 높이는 과정입니다.
• 활용 (Exploitation): 현재까지 얻은 정보를 바탕으로 가장 높은 보상을 줄 것으로 예상되는 선택지를 선택하는 과정입니다.
• 탐험과 활용의 갈등: 탐험과 활용 사이에는 본질적인 갈등이 존재합니다. 탐험을 통해 새로운 정보를 얻는 동안에는 단기적인 보상을 희생할 수 있지만, 이를 통해 장기적으로 더 나은 선택을 할 수 있는 기회를 얻습니다. 반면, 활용을 통해 당장의 높은 보상을 얻을 수 있지만, 최적의 선택지를 놓칠 위험이 있습니다.

탐험과 활용의 관계

• 탐험의 중요성: 충분한 탐험을 통해 각 선택지의 가치를 정확히 추정할 수 있습니다. 새로운 정보를 지속적으로 얻음으로써 에이전트는 불확실성을 줄이고 최적의 선택을 할 가능성을 높입니다.
• 활용의 중요성: 현재까지의 정보로 최적의 선택지를 선택함으로써 단기적으로 높은 보상을 얻을 수 있습니다. 이는 실제 환경에서 빠르게 성과를 내는 데 중요합니다.

아래의 장들에서 이것들을 어떻게 잘 적절하게 선택해서 활용할 것인지에 대해 중점적으로 다뤄진다.

Action-value Methods

Action-value Method

Action-value method는 강화학습에서 에이전트가 각 행동(action)에 대한 가치를 추정하는 방법입니다. 이 방법은 각 행동이 얼마나 좋은지에 대한 정보를 바탕으로 최적의 행동을 선택하는 데 사용됩니다.

Action-value Function (Q-function)

• 정의: Action-value function ($Q(a)$)는 특정 행동 ($a$)를 선택했을 때 기대되는 평균 보상을 나타냅니다. 즉, ($Q(a)$)는 행동 ($a$)의 가치를 의미합니다.
• 추정: 에이전트는 각 행동에 대한 보상을 관찰하고, 이를 바탕으로 ($Q(a)$)를 추정합니다. 이 추정 값은 시간이 지남에 따라 갱신됩니다.

그리디 방법 (Greedy Method)

그리디 방법은 현재까지의 Q-value를 바탕으로 항상 가장 높은 가치를 가진 행동을 선택하는 탐욕적 방법입니다.

그리디 정책

• 정의: 그리디 정책은 현재 추정된 Q-value가 가장 높은 행동을 선택합니다. 즉,

  $( a_t = \arg\max_a Q(a) )$

  이 정책은 항상 최적의 행동을 선택하려고 하지만, 탐험을 하지 않기 때문에 초기에는 최적의 행동을 찾지 못할 수 있습니다.

장점과 단점

• 장점: 그리디 방법은 단기적으로 높은 보상을 얻을 수 있습니다.
• 단점: 탐험을 하지 않으므로, 최적의 행동을 찾지 못할 수 있습니다. 초기 Q-value가 잘못 설정되었거나, 보상 분포가 변할 경우에는 성능이 저하될 수 있습니다.

$\epsilon$-그리디 방법 ($\epsilon$-greedy Method)

탐험과 활용의 균형을 맞추기 위해 (\epsilon)-그리디 방법이 사용됩니다.

• 정의: 확률 ($\epsilon$)으로 무작위로 탐험하고, 확률 ($1 - \epsilon$)으로 그리디 정책을 따릅니다.
• 절차:
  1. 확률 ($\epsilon$)으로 무작위 행동을 선택합니다.
  2. 확률 ($1 - \epsilon$)으로 현재 Q-value가 가장 높은 행동을 선택합니다.
  $a_t = \begin{cases} \text{random\ action} & \text{with\ probability\ } \epsilon \\ \arg\max_a Q(a) & \text{with\ probability\ } 1 - \epsilon \end{cases}$

결론

Action-value method는 각 행동의 가치를 추정하여 최적의 행동을 선택하는 강화학습 방법입니다. 그리디 방법은 항상 현재의 Q-value가 가장 높은 행동을 선택하지만, 탐험을 하지 않기 때문에 최적의 행동을 찾지 못할 위험이 있습니다. $\epsilon$-그리디 방법은 탐험과 활용의 균형을 맞추어 더 나은 성능을 제공합니다. 이를 통해 에이전트는 장기적으로 최적의 행동을 찾을 수 있습니다.

연습2.1

탐욕적 행동을 선택할 확률 = $\frac{1}{2}$
무작위 선택 시 탐욕적 행동을 선택할 확률 = $\frac{1}{4}$
정답 : $\frac{3}{4}$

The 10-armed Testbed

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

탐욕적 행동 선택 방법은 현재 추정된 Q-value가 가장 높은 행동을 항상 선택하는 방법입니다. 이 방법은 단기적으로 높은 보상을 얻을 수 있지만, 새로운 행동을 탐험하지 않기 때문에 장기적으로는 최적의 행동을 찾지 못할 수 있습니다.

특징

• 정의: 현재까지의 Q-value 중 가장 높은 값을 가진 행동을 선택
  $( a_t = \arg\max_a Q(a) )$
• 장점: 단기적으로 높은 보상
• 단점: 탐험을 하지 않기 때문에 최적의 행동을 찾기 어려움

$\epsilon$-탐욕적 방법 $\epsilon$-Greedy Method

$\epsilon$-탐욕적 방법은 탐험과 활용의 균형을 맞추기 위해 설계된 방법입니다. 이 방법은 확률 $\epsilon$으로 무작위로 행동을 선택하고, 확률 $(1 - \epsilon)$으로 탐욕적 행동을 선택합니다.

특징

• 정의: 확률 $\epsilon$으로 무작위 행동을 선택하고, 확률 $1 - \epsilon$으로 탐욕적 행동을 선택
  $a_t = \begin{cases} \text{random\ action} & \text{with\ probability\ } \epsilon \\ \arg\max_a Q(a) & \text{with\ probability\ } 1 - \epsilon \end{cases}$
• 장점: 탐험과 활용의 균형을 맞추어 장기적으로 최적의 행동을 찾을 수 있음
• 단점: 단기적으로는 탐욕적 방법보다 낮은 보상

10-armed Bandit 테스트 결과

10-armed bandit 문제를 통해 두 가지 방법의 성능을 비교했습니다. 이 테스트에서 각 행동에 대한 보상은 정규분포를 따르며, 평균과 표준편차는 각각 0과 1입니다. 테스트는 1000번의 반복 실험으로 진행되었습니다.

실험 설정

• 행동 수: 10 (10-armed bandit)
• 보상 분포: 평균 0, 표준편차 1의 정규분포
• 반복 실험 횟수: 1000회
• 에피소드 수: 각 실험당 2000 에피소드

결과

• 탐욕적 행동 선택 방법: 초기에는 빠르게 높은 보상을 얻지만, 장기적으로는 최적의 행동을 찾지 못해 성능이 저하됨.
• $\epsilon$-탐욕적 방법 $(\epsilon = 0.1)$: 초기에는 탐험으로 인해 낮은 보상을 받지만, 장기적으로는 최적의 행동을 찾아 더 높은 성능을 보임.

결론

탐욕적 행동 선택 방법과 $\epsilon$-탐욕적 방법은 각각 단기적, 장기적 성능에 차이가 있습니다. 탐욕적 방법은 초기에는 높은 보상을 얻을 수 있지만, 최적의 행동을 찾지 못할 위험이 있습니다. 반면, $\epsilon$-탐욕적 방법은 초기에는 탐험으로 인해 낮은 보상을 받을 수 있지만, 장기적으로는 더 나은 성능을 보입니다.

근데 사실 이 부분이 저는 잘 이해가 가지 않았습니다. 해서 저만의 용어로 어떤식으로 이해했는지 간략하게 남겨보자면 A라는 사람과 B라는 사람이 있다고 가정하자. A는 매일 집을 갈 때마다 기존에 본인이 생각하기에 가장 빠른 길로 집을 간다. B라는 사람도 마찬가지로 본인이 기억하는 가장 빠른 길로 가지만 간혹가다(10%)의 확률로 랜덤한 길을 가본다. 아니 그런데 이게 뭔가 10%에서 좋은 길을 발견하면 본인의 DB를 업데이트하여 저장해두고 다음번엔 그 길을 가장 빠른 길이라고 인식하고 지나가는 것이다. 그러므로 최적의 선택을 모두 고를 확률이 91%에 수렴하게 되는 것이다.

연습문제 2.2

연습문제 2.3

장기적으로는 당연히 0.01이 가장 좋을 수 밖에 없다. 왜냐하면 아주 오랜 기간 학습하면 99%의 확률로 최적을 고를 것이고, 1%의 확률로 10개중 하나이니 99.1%의 확률로 최적을 고를것이다. 나머지는 91%, 40%미만이니 볼 것도 없다.

Incremental Implementation

Tracking a Nonstationary Problem

Optimistic Initial Values

Upper-Confidence-Bound Action Selection

Gradient Bandit Algorithms

Associative Search

Summary