[알기쉬운 AI - 22] 강화학습과 도적 알고리즘

 

강화 학습과 밴디트(도적) 알고리즘

강화 학습은 감독 학습처럼 '해답'이 주어지는 것이 아니고, 보수를 얻기 위해 스스로 배우고 영리해지는 학습법입니다. 바둑이나장기와 같은 게임에서 압도적인 힘을 보여 주므로, "빙상의 체스"라 부르는 컬링을 예로 들어 설명해 봅시다.

 
컬링은 4명이 한 팀으로 10 엔드 싸움으로 합계 점수가 많은 쪽이 승리하는 스포츠입니다. 엔드마다 선공과 후공이 있어 후공이 유리한 게임입니다. 엔드에서 이기면 다음 엔드는 선공이 되기 때문에 일부러 무승부로 끝내서 후공을 계속한다거나 선공 때는 1점 차이로 일부러 져서 후공을 얻기도 합니다. 이 스포츠는 어떻게 싸워나갈 것인지 전술적인 면이 큰 경기입니다.  

일반적으로 컬링은 코치가 있습니다. 8 엔드에서 선공으로 2점 리드시 취해야 할 전략, 다양한 스톤의 배치 상태에서 어떤 투구를 해야 할지, 선수의 역량에 따라 어떻게 해야 할지, 이런식으로 각 상황에서 코치가 최적의 조언을 가르쳐주는 것이 '감독 학습'입니다.(진짜 규칙에서는 5 엔드 종료 후의 휴식 시간과 타임 시간 이외에 코치와의 대화는 인정되지 않습니다)

한편 '강화 학습'은 코치가 없습니다. 엔드 10의 투구가 끝나고 승리하지 못했을 때, 엔드 9가 어떻게 잘못되었는지를 반성하고 전술을 검토합니다. 엔드 9의 나쁜 원인이 엔드 8에 있는 경우, 엔드 8에 채택했던 전술을 검토하고 이쪽도 개선합니다. 따라서 어떻게 하면 더 보상을 얻을 수 있을지 스스로 반성하고 강해져 가는 것입니다.  

바둑이나 장기, 체스의 대국이 끝난 후에 함께 복기를 하면서 서로 어떤 수가 나빴는지 논의하고 최선의 수를 검토합니다. 강화 학습은 이 복기와 같이 자기반성을 스스로 실시해, 그 내용을 기록해야 합니다. 다음 경기에서는 그 기록 내용을 참고로 하면서 겨루고, 지면 또 반성하고 기록을 갱신합니다. 이 작업을 반복하는 중에 점점 강해져 가는 학습 방법입니다. 

도적 알고리즘과 AB 테스트

강화 학습에서 보수를 최대로 하는 방법 중 하나로 도적 알고리즘이라는 것이 있습니다. 사실 도적 알고리즘 강화 학습이 주목받기 이전부터 Web마케팅에서 고객에게 더 많은 클릭을 얻거나 게임에서 이기기 위한 방법으로 사용되고 있었습니다. 예를 들어 간단히 설명해 보겠습니다.

무대는 메이드 카페에서 아르바이트를 하는 영희와의 가위 바위 보 승부입니다. 코인을 50개 구입했기 때문에 50회 가위 바위 보를 할 수 있습니다. 코인 하나를 내고 가위 바위 보에서 영희를 이기면 코인은 3배로, 비기거나 지는 경우는 빼앗겨 버립니다. 그밖에 패스라는 것이 가능하며, 이 경우는 코인 1개가 그대로 남아 있습니다. 

50회 가위 바위 보를 하여 수중에 얻은 코인으로 영희와 만날 수 있습니다. 이 행복한 시간(보상)을 극대화하기 위해 활용하는 것이 도적 알고리즘입니다.

사람에게는 각각의 버릇이 있고, 영희는 보를 낼 확률이 50%, 바위 30%, 가위 20%입니다. 만약 그것을 알았다면 처음부터 가위를 계속 내겠죠, 그때의 기대 값은 50회 × 0.5 × 3개 = 75개가 됩니다. 그리고 전부 패스한다면 50장입니다.  

 

그림 1 : 영희와 가위 바위 보 승부

(1) AB 테스트

우선, 도적 알고리즘을 설명할 때 자주 비교되는 AB테스트를 살펴보겠습니다. AB테스트는 패턴 A와 패턴 B를 준비하여 둘 중 어느 패턴이 효과가 높은(보상이 큰) 가를 조사하는 테스트 방법입니다. e커머스나 Web광고에서 사용되는 경우, 디자인 A와 디자인 B 중 어느 쪽이 더 클릭되는지 일정기간 테스트하여 클릭이 많았던 쪽의 디자인을 채용하는 식으로 사용됩니다. Facebook에 광고를 낼 경우에도 광고주가 여러 광고 세트를 준비하고 AB테스트를 할 수 있으며, Facebook 자신도 새로운 기능의 평가 검증에 AB 테스트를 자주 사용하고 있습니다. 

영희와의 가위 바위 보 승부에 AB테스트를 사용해 봅시다. 처음에 10회씩 가위 바위 보를 고르게 내고 영희의 버릇을 탐구하여 '보'를 많이 낸다고 판단하여 나머지 20회는 가위를 계속 냅니다.

 

이 경우의 기댓값은

10회 × 0.5 × 3개(가위) + 10회 × 0.2 × 3 개(바위) + 10 × 0.3 × 3개(보) + 20회 × 0.5 × 3개(가위) = 60개입니다.

뭐, 그런대로의 성과네요.

 

여기서 처음 30회는 영희의 버릇을 간파하기 위한 '탐색'입니다. 그리고 '보'가 많다고 생각한 후에 가위를 내는 것이 '활용'입니다. 이 '탐색(Explore)'과 '활용(Exploit)'은 트레이드오프 관계에 있습니다(그림 2). 버릇을 잘 식별하기 위해 '탐색'의 수를 늘려야 하지만 그렇게 되면 '활용'의 수는 줄어들어 버립니다.

 

그림 2 : 탐색과 활용의 트레이드오프

AB 테스트의 약점은 2가지가 있습니다.
① 탐색 시 확률이 나쁜 수도 균등하게 내야 한다.
② 탐색 결과 찾아낸 것이 정답이 아니라면 같은 수을 계속 내서 큰 손실을 입는다.   

방금 AB 테스트의 기대치를 60개로 했지만 정답을 잘못 쓴 경우를 고려하면 더 낮은 값이 되는 것입니다(그 이전에 '활용'에서 연속 20회 가위를 내고 있는데, 영희가 계속 보를 낼까요?)

(2) 도적 알고리즘

위의 두 과제를 해결하기 위한 방법이 도적 알고리즘입니다. AB테스트는 일정 기간의 탐색과 그 활용이 완전히 나뉘어 있지만 도적 알고리즘은 이 두 가지를 혼합하여 탐색하면서 활용합니다. 즉 '처음부터 지금까지 얻은 정보로 활용하면서 적당히 탐색도 계속한다'는 것으로, 그 균형을 찾는 방법으로 다음과 같은 것이 있습니다. 

· Greedy 

· UCB (Upper Confidence Bounds) 

· Softmax 

· Thompson Sampling

또한 처음에는 탐색을 많이 하고 점차 활용의 비율을 높이는 어닐링(annealing: 풀림 처리) 방법도 있고, 위 3 가지에 어닐링을 혼합하는 방법도 유력합니다.

 

Optimism in face of uncertainty

자, 세상은 그렇게 만만하지 않습니다. 파칭코 기계나 슬롯머신처럼 현실 세계에서도 이길 수 있는 확률을 보통은 잘 모릅니다.

 

Optimism in face of uncertainty에 대하여 알아봅시다. 먼저 영희의 가위에 한두 번 바위로 이겼다고 합시다. 그럼 '오, 바위가 잘 이기네'라고 생각하고 바위를 많이 내겠죠. 그러나 점차 지는 횟수가 늘어나면 바위는 별로라고 생각하고 내지 않게 됩니다. 즉 낙관적인 착각을 줄이고 다른 선택으로 옮겨갈 것입니다.  

한편, 처음 영희에게 한두 번 가위를 내서 졌다고 칩시다. 이번에는 '아, 가위는 별로구나'라고 생각해 점차 가위를 내지 않게 되어, 가위가 최선이라는 것을 깨닫지 못하게 됩니다. 즉 비관적인 착각을 멈추지 못하고 최적의 선택에 도달할 수 없게 됩니다.  

이 편차를 해결하려면 조금 낙관적인 측면에서 이길 필요가 있습니다. 이를, '불확실한 경우에는 낙관적인 선택을 한다'라는 원칙에서 Optimism in face of uncertainty라고 합니다. 방법은 여러 가지가 있지만, 그중 하나가 낙관적 초기치의 법입니다. 이것은 예를 들어 처음에 가위 바위 보 각각 10회 승리한다고 초기값을 주고 시작합니다. 초반 가위로 패배가 계속하더라도 10번 이긴다고 낙관하고 있기 때문에 끈질기게 가위를 내고, 그중에 가위로 이기는 횟수가 늘어나서 정답에 도달하게 되는 것입니다. 

 

몬테카를로 방법

AB테스트의 '탐색'관련 기술로 몬테카를로 법이 있습니다. 카지노로 유명한 모나코의 도시 이름이네요. 이 방법은 매우 간단합니다. 랜덤으로 시험을 하여 그 결과로부터 근사치를 구하는 시뮬레이션 방법입니다. 영희가 내는 가위 바위 보의 퍼센티지를 집계해 가는 와중에, 보가 50%, 바위가 30%, 가위가 20%라는 영희의 버릇이 점점 보이는 것입니다.

정리

여러분은 좌우명이 있습니까? 사실 저는 좌우명을 물어볼 때, '곤란한 경우에는 적극적인 길'이라고 대답했습니다. 도적 알고리즘의 Optimism in face of uncertainty라는 말을 만나고 '아, 똑같네'라고 깜짝 놀랐습니다. 게임에 이기는 알고리즘이므로, '인생이라는 게임에서 승리'하기 위한 중요한 말이었다는 것에 감회가 깊습니다.