11. The multi-Armed Bandit Problem

the simpler version

 

3개의 밴딩 머신이 있을 때, best ram 은

어떻게 best arm을 찾을 것인가?

best arm을 결정할 때까지 드는 cost를 regret이라고 한다.

regret을 적게해서 best arm을 찾는 것이 최적이다

 

state의 변화가 없음 항상 똑같은 state로 돌아온다.

 

The multi-armed bandit problem

 

4가지 전략이 어떻게 다르고 코드를 읽고 어떤 건지 판단

Exploration Strateges

Epsilon-greedy

Softmax exploration

softmax를 사용한 탐색

epsilon greedy가 1등만 기억하는 더러운 세상이었다면 softmax는 점수에 따라 가중치를 부여한다.

모든 합이 1이 되도록 Softmax function를 이용하여 확률로 바꾼 뒤 Q value를 업데이트 한다.

 

탐색을 높이기 위해 파라미터 T를 사용한다.

T를 높이면 확률이 비슷해짐 (0.25, 0.24, 0.245 ...)

T를 낮추면 확률이 차이가 많이 난다(0.99 , 0.005. 0.0023....)

 

특정 vector/ vetor sum 을 distribution해주고 T를 이용해 decay

 

Upper Confidence bound(UCB)

Optimism in the face of uncertainty

언제나 각 범위 내에서 더 높은 값을 가지는 arm을 선택한다.

arm1 을 선택했다가 점점 줄어들어 arm2의 최댓값이 커지면 arm2를 선택, 이런식으로 두 arm을 줄여나감

만약, 두 arm의 최댓값이 같다면 랜덤으로 선택해서 점점 그 폭을 줄여나감

N(a)는 시도 횟수, 많이 당길 수록 UCB는 낮아진다.

 

Thompsom Sampling

beta distribution

1. Beta 파라미터 2개 (a, b)

2. 모양은 위로 볼록한 포물선 a가 높으면 높은 x값이 나올 확률이 높은 분포, b가 높으면 낮은 x값이 나올 확률이 높은 분포(각각의 분포 적분은 1이다)

이기면 a를 올리고 지면 b를 내림