다중 슬롯머신 문제 (Multi-Amred Bandits, MAB) with Epsilon-Greedy

다중 슬롯머신 문제 (Multi-Amred Bandits, MAB)

여러 개의 팔을 가진 슬롯머신이 있다. 슬롯머신의 팔마다 코인이 나오는 확률은 정해져 있지만, 확률값은 미리 알 수 없다. 제한된 횟수 안에서 가장 많은 코인을 얻으려면 어떤 순서로 팔을 선택해야 할까?

 

어떤 슬롯머신의 팔을 당겨야 가장 많은 돈을 벌 것인지에 대한 문제를 푸는 다중 슬롯머신 문제는 강화 학습의 예시로 흔히 알려져 있다. 이 글에서는 Epsilon-Greedy 입실론 그리디 학습 방법으로 이 문제를 해결해 본다.

 

'알파제로를 분석하며 배우는 인공지능' 책을 참고한 글임을 밝힌다.

 

강화 학습 사이클

다중 슬롯머신 문제의 목적은 '코인은 많이 얻는다'이고, 행동은 '어떤 팔을 선택하는가?', 보상은 '코인이 나오면 +1'이다. 행동 1회마다 파라미터를 변경한다.

코인이 나올 확률이 높은 팔은 처음부터 알 수 없으므로 정보 수집을 위한 탐색(exploration)이 필요하다. 또한 탐색한 정보를 가지고 보상이 높다고 판단한 팔을 선택하는 이용(exploitation)이 있다.

이익을 최대화하기 위해서는 탐색과 이용의 균형을 맞추어야 한다. 탐색만 계속하면 보상이 높은 팔을 알 수 있지만 실제로 이용하지 않는다. 이용만 계속하면 현시점보다 더 높은 보상의 팔이 있을 가능성이 있다.

 

E-greedy 계산 처리

#Calculation epsilon-Greedy
class EpsilonGreedy():
  #init e-greedy
  def __init__(self, epsilon):
    self.epsilon = epsilon #Probability of exploration

  #init n, v (n_arms: number of arms)
  def initialize(self, n_arms): 
    self.n = np.zeros(n_arms) #number of attempts for each arm - list
    self.v = np.zeros(n_arms) #value of each arm - list (평균보상)

  #Select arm
  def select_arm(self):
    if self.epsilon > random.random():
      return np.random.randint(0, len(self.v)) #select random
    else:
      return np.argmax(self.v) #select high value arm

탐색과 이용의 균형을 잡는 방법으로 Epsilon-Greedy를 사용한다.
E-greedy는 E 확률(0 이상 1이하의 정수)로 랜덤하게 행동을 선택, 1-E 확률로 초기 보상이 최대가 되는 행동을 선택한다. 그리고 팔의 번호를 반환한다.

 

파라미터 업데이트

  #Update parameter
  def update(self, chosen_arm, reward, t):
    self.n[chosen_arm] += 1 #number of attempts of the selected arm + 1

    #update the value of the selected arm
    n = self.n[chosen_arm]
    v = self.v[chosen_arm]
    self.v[chosen_arm] = ((n-1) / float(n)) * v + (1 / float(n)) * reward

  #get string info
  def label(self):
    return 'E-greedy('+str(self.epsilon)+')'

파라미터를 다음 순서에 따라 갱신한다

(1) 선택한 팔의 시행 횟수+1

(2) 선택한 팔의 가치 갱신

 

선택한 팔의 가치(평균 보상)는 수식에 따라 갱신한다.

$$V_t = \frac{n-1}{n} \times V_{t-1} + \frac{1}{n} \times R_t$$

(이번 시행의 가치:평균 보상) = (시행횟수-1)/(시행횟수) * (이전 시행의 가치 :평균 보상) + 1/시행횟수 * (이번 시행의 보상)

 

슬롯 게임 생성

#Make slot arm
class SlotArm():
  def __init__(self, p):
    self.p = p #Probability of getting a coin
  
  #Get a reward for choosing an arm
  def draw(self):
    if self.p > random.random():
      return 1.0
    else:
      return 0.0

코인이 나올 확률인 p를 생성자 인수로 둔다. 팔을 선택했을 때의 보상을 취득한다.

 

시뮬레이션 실행

#run
def play(algo, arms, num_sims,num_time):
  times = np.zeros(num_sims*num_time) #game times
  rewards = np.zeros(num_sims*num_time) #rewards

  #roop simulation
  for sim in range(num_time):
    algo.initialize(len(arms))

    #roop game
    for time in range(num_time):
      #calculate index
      index = sim * num_time + time

      times[index] = time + 1
      chosen_arm = algo.select_arm()
      reward = arms[chosen_arm].draw()
      rewards[index] = reward

      #update parameter
      algo.update(chosen_arm, reward, time+1)

  return [times, rewards]

play()는 시뮬레이션을 실행한 뒤 게임 횟수 중 몇 번째인지와 보상을 반환한다.

다중 슬롯머신 문제는 결정된 게임 회수 내에서 가능한 많은 보상을 얻어내는 문제이다. 결정된 게임 횟수를 몇 번 시뮬레이션할지를 인수 num_times로, 결정된 게임 횟수가 인수 num_time이다. 시뮬레이션 횟수가 많을수록 정밀도가 올라간다.

 

코드 실행 및 그래프 표시

#select arm
arms = (SlotArm(0.3), SlotArm(0.5), SlotArm(0.9))

#set algorithm
algo = EpsilonGreedy(0.1)

#run
result = play(algo, arms, 1000, 250)

#draw graph
df = pd.DataFrame({'times': result[0], 'rewards': result[1]})
mean = df['rewards'].groupby(df['times']).mean()
plt.plot(mean, label = algo.label())

plt.xlabel('Step')
plt.ylabel('Average Reward')
plt.legend(loc = 'best')
plt.show()

확률이 0.3, 0.5, 0.9인 팔 3개를 준비한다. 250회를 1세트로, 1000세트의 시뮬레이션을 실행한다.

시뮬레이션 결과는 다음과 같다.

 

전체 코드

https://github.com/proqk/MAB-with-Epsilon-Greedy-and-UCB1