5 July 2021 / REINFORCEMENT

Reinforcement Learning - Slot machine

첫 AI 모델 만들기 - Slot machine

다중 슬롯머신 문제

5개의 슬롯머신이 있는 방에 있다. 각 슬롯머신은 특정 금액을 걸고 손잡이를 당기면 판돈을 가져가거나 판돈의 두배를 되돌려 준다. 슬롯머신이 판돈을 가져가면 보상은 -1이 될것이고, 두배를 돌려주면 보상은 +1이 된다. 그중 하나가 다른 것보다 a+1 보상을 줄 확률이 높다고 가정한다. 게임을 1000번 했을 때 딸 수 있는 최대 금액을 얻으려면 어떤 전략을 사용해야할까?

첫번째 전략은 최소로 게임을 했을 때 5개 슬롯머신 중 어느 슬롯멋니이 보상으로 1을 줄 확률이 가장 높은지 파악하는 것이다. 즉 성공률이 가장 높은 슬롯머신을 빨리 찾아야 한다. 그 후 이 슬롯머신에서 계속 게임을 하면 된다.

가장 어려운 부분은 최소한의 시도로 최고의 슬롯머신을 찾아내야 한다.

톰슨 샘플링 모델

톰슨 샘플링이 2개의 인수를 취하는 베타분포함수를 사용한다고 하자. 첫번째 인수가 높을수록 슬롯머신이 더 좋고 두번째 인수가 높을수록 슬롯머신이 더 나빠진다고 가정하자. 이 함수를 정의하면,

$x=\beta(a,b)$

이다.

import numpy as np
import matplotlib.pyplot as plt

conversionRates = [0.15, 0.04, 0.13, 0.11, 0.05]
N = 2000
d = len(conversionRates)

다섯개의 슬롯머신의 승률이 있다. 그후 샘플 수 N을 생성한다. 다음으로 각 샘플마다 모든 슬롯머신에 대한 승패의 집합을 정의한다.

X = np.zeros((N, d))
for i in range(N):
    for j in range(d):
        if np.random.rand() < conversionRates[j]:
            X[i][j] = 1

데이터셋 X의 N개 샘플 중 하나가 [0, 1, 0, 0, 1]이라고 한다면 2번이나 5번 슬롯머신에서 게임을 하면 된다. 다음으로 슬롯머신마다 게임한 결과 승패의 수를 셀 두 개의 배열을 생성하고 이긴횟수와 진횟수로 이름을 부여한다.

nPosReward = np.zeros(d)
nNegReward = np.zeros(d)

다음으로 데이터셋의 샘플마다 반복할 for 루프를 초기화하고 가장 좋은 슬롯머신을 선택한다. 그후 베타분포에서 난수를 취해 전체 슬롯머신에서 가장 높은 값을 찾는다.

for i in range(N):
    selected = 0
    maxRandom = 0
    for j in range(d):
        randomBeta = np.random.beta(nPosReward[j] + 1, nNegReward[j] + 1)
        if randomBeta > maxRandom:
            maxRandom = randomBeta
            selected = j
            
        if X[i][selected] == 1:
            nPosReward[selected] += 1
        else:
            nNegReward[selected] += 1

nSelected = nPosReward + nNegReward
for i in range(d):
    print('Machine number ' + str(i+1) + ' ws selected ' + str(nSelected[i]) + ' times')
print('Best machine is ' + str(np.argmax(nSelected) + 1))

Machine number 1 ws selected 9398.0 times
Machine number 2 ws selected 136.0 times
Machine number 3 ws selected 318.0 times
Machine number 4 ws selected 103.0 times
Machine number 5 ws selected 45.0 times
Best machine is 1

이 문제를 해결할 때 처음으로 할 일은 다섯대의 슬롯머신을 차례로 시도하는것이다.

라운드	Machine Number	보상
1	1	0
2	2	+1
3	3	0
4	4	0
5	5	+1

라고 가정하면,

각 슬롯머신에 대해 두 개의 새 변수를 도입한다. 하나는 슬롯머신이 보상으로 0을 반환한 횟수를 세고 다른 변수는 그 슬롯머신이 보상으로 1을 반환한 횟수를 센다.

이 변수들을 $N_{i}^{0}(n)$과 $N_{i}^{1}(n)$으로 표기하며 여기에서 $N_{i}^{0}(n)$은 $i$번째 슬롯머신이 $n$번째 라운드까지 보상으로 0을 반환한 횟수이며, $N_{i}^{1}(n)$은 $i$번째 슬롬섯니이 $n$번째 라운드까지 보상으로 1을 반환한 횟수이다. 구체적으로 살펴보면

$N_{1}^{0}(1) = 1$은 슬롯머신 1이 1라운드에 1패를 반환함을 뜻한다.

$N_{1}^{0}(1) = 0$은 슬롯머신 1이 1라운드에 0승을 반환함을 뜻한다.

$N_{5}^{1}(4) = 1$은 슬롯머신 5가 4라운드에 1승을 반환함을 뜻한다.

분포

변수의 분포는 변수가 취할 수 있는 가능한 값 범위의 각 값에 대해 이 변수가 해당 값과 같을 확률을 제공하는 함수다. 매 회 게임에서 각 슬롯머신을 특정 베터 분포와 연결시키면

$\beta(N_{i}^{1}(n)+1, N_{i}^{0}(n)+1)$

베타분포 $\beta(a,b)$에서 매개변수 a가 클수록 분포가 오른쪽으로 더 많이 이동한다. 매개변수 $b$가 클수록 분포는 왼쪽으로 더 많이 이동한다. 따라서 매 게임 $n$마다 각 슬롯머신에 대해 매개변수 $a$는 $n$번째 게임까지 그 슬롯머신이 1을 반환한 횟수(+1)이고 매개변수 $b$는 $n$번째 게임까지 그 슬롯머신이 0을 반환할 횟수(+1)이다. 정리하면 슬롯머신이 1(성공)을 더 많이 반환하면 분포가 오른쪽으로 더 많이 이동하고, 슬롯머신이 0(실패)을 더 많이 반환하면 분포가 왼쪽으로 더 많이 이동한다.

톰슨 샘플링 전략

처음 다섯 번의 게임에서 다섯대의 슬롯머신 각각으로 게임한 다음 매 게임 $n$마다 AI가 할 일은

각 슬롯머신 $i(i=1,2,3,4,5)$에 대해 해당 슬롯머신의 베타 분포에서 무작위 추첨한 값 $\theta_{i}(n)$을 취한다.

$\theta_{i}(n) \sim \beta(N_{i}^{1}(n)+1, N_{i}^{0}(n)+1)$

가장 높은ㅇ 샘플링된 값 $\theta_{i}(n)$을 가진 슬롯머신 $s(n)$에서 게임한다

$s(n) = argmax_{i=1,2,3,4,5}(\theta_{i}(n))$

$N_{s(n)}^{i}(n)$ 이나 $N_{s(n)}^{0}(n)$을 업데이트한다.

게임했던 슬롯머신 $s(n)$이 보상으로 1을 반환하면,

$N_{s(n)}^{1}(n) : = N_{s(n)}^{1}(n) + 1$

게임했던 슬롯머신 $s(n)$이 보상으로 0을 반환하면,

$N_{s(n)}^{0}(n) : = N_{s(n)}^{0}(n) + 1$

그 다음 모든 돈을 쓸때까지 매 게임에서 이 세단계를 반복한다. 이 전략은 톰슨 샘플링이라 하며 기본적이지만 강력한 모델이다.

톰슨 샘플링 마무리

각 슬롯머신에는 자체 베타 분포가 있다. 게임이 진행되는 동안 전환율이 가장 높은 해당 슬롯머신의 베타 분포는 점차 오른쪽으로 이동하고 전환율이 낮은 전략의 베타 분포는 점차 왼쪽으로 이동한다. 따라서 이러한 단계를 반복해 전환율이 가장 높은 슬롯머신이 점점 더 많이 선택된다.

참고 : 아들랑 드 폰테베 『강화학습/심층강화학습특강』, 위키북스(2021), p38-54