[RL] MAB, Epsilon, 낙관적 초기화

Multi-Armed Bandit

슬롯머신이 여러 개 있을 때 슬롯머신마다 터지는 비율이 다름, 어떤 슬롯머신을 당길 것인가

MAB문제는 강화학습의 일종

다음 상태로 전이가 없으므로, 지평=1 → 이번 행동의 결과는 이후 상태와 무관

행동은 주어진 대안 중 하나를 선택하는 것

 

탐색-활용 교환(exploration-exploitation trade off)

1) 탐색 : 새로운 시도를 해보는 것

2) 활용 : 기존에 알려진 최선을 반복하는 것

3) 탐색만 하는 전략 :

- 모든 슬롯머신을 골고루 당겨본다. 

- 각 슬롯머신의 수익률을 가장 정확히 파악할 수 있음

- 돈은 모든 슬롯머신의 평균만큼만 벌 수 있음

4) 활용만 하는 전략

- 슬롯머신을 하나 정해서 무조건 그것만 당겨본다. 

- 다른 슬롯머신의 수익률은 알 수 없음

- 운좋게 잘 터지는 슬롯머신을 고를 경우 대박, 그렇지 않으면 망함

5) 강화학습에서는 탐색과 활용이 모두 보상이 따르는 행동이므로 탐색을 늘리면 그만큼 활용을 적게 하게 됨

 

MAB 문제의 활용

- 홈페이지/광고 디자인

- 제품 추천

- 약물 적용

- 기존에는 전문가 의견, A/B 테스트와 같은 방법 사용

- A/B 테스트 : 고객 또는 환자를 A군과 B군으로 나누어 다른 방법을 적용

 

후회(regret)

강화학습의 목표 : 가치(할인된 보상의 합)의 기댓값을 최대화

MAB는 한 행동이 이후 상태에 영향을 주지 않음 → 보상만 고려

후회 : 한번의 행동의 기회비용

전체 후회 : 에피소드 전체에서 후회의 합계

누적 보상의 최대화 = 전체 후회의 최소화

 

입실론 퍼스트(epsilon first method)

일정 비율만큼 탐색

이후로는 가장 가치가 높은 행동만 한다.(활용)

일상적으로 많이 하는 방법

 

입실론 퍼스트의 문제점

- 충분히 탐색을 하지 못할 가능성

  100번으로는 슬롯머신의 가치를 충분히 정확히 추정하기에 부족하다면?

- 시간에 따라 변화하는 상황에 대응하지 못함

  여름에 실험한 결과는 겨울에 통하지 않는다면?

 

입실론 탐욕법(epsilon greedy method)

- 가장 가치가 높은 행동만 한다. (활용 중심)

- 매번 일정비율만큼은 탐색, 그 외에는 활용

- 예시 

  주사위를 굴려서 1이 나오면 무작위로 아무 슬롯머신이나 당겨보고, 그 외에 는 이제까지 가치가 가장 높은 슬롯 머신을 당긴다

  20%의 고객에게는 A안과 B안 중에 무작위로 보여주지만, 나머지 80%의 고객에게는 이제까지 가치가 가장 높은 슬롯 머신을 당긴다. 

 

감쇠 입실론 탐욕법

- 행위자가 환경에 대해 충분히 탐색하지 못한 초기에는 탐색을 많이

- 후반에는 탐색을 적게하는 방법

 

모의 담금질(Simulated Annealing)

- 전역 최적화를 찾기 위한 확률적 기법

- SA 알고리즘은 초기 고온에서 시작하여 서서히 온도를 낮추며 최적해를 찾아가는 방식

 

낙관적 초기화

각 대안의 초기 가치를 낙관적으로 크게 산정

적게 탐색한 대안은 초기 가치가 많이 반영되어 있으므로 가치가 높음

입실론 탐욕법은 가치가 높은 대안을 주로 활용

 

소프트 맥스 전략

가치에 따라 확률을 결정

 

톰슨 샘플링

가치 대신 각 행동의 가치의 분포를 추정

분포에서 무작위로 샘플링하여 높은 가치가 추정된 행동을 선택

행동 후 보상을 얻으면 분포를 수정

 

예측문제

전이 함수없이 가치함수를 추정하는 문제

cf) 제어문제 : 전이 함수 없이 정책을 최적화하는 문제

요약

현재 상태 가치 = 이번에 받을 보상 + 할인* 다음상태가치

반복적 정책평가 = 동적계획법 + 부트스트랩 (주어진 정책 내에서 가치 추정)

정책 개선 : 상태마다 가치가 가장 큰 행동

정책반복 : 평가 ↔ 개선

가치반복 : 현재 추정된 가치가 가장 큰 행동을 하는 것으 로 하자 → 가치 추정도 바뀜

전이확률 : 어떤 행동을 했을 때 다음 상태가 어떻게 될까? > 이 확률을 모르면 동적계획법 X

몬테카를로 법 : 많이 하면 결국 그 확률대로 됨

예측문제 : 전이 확률을 모를때 가치 추정, "많이"해보면 결국 실제 가치로 수렴

Day2.ipynb

0.51MB