Python으로 오목 게임 AI를 처음부터 만들기 그 248: 그래프를 이용한 다중 팔 밴딧 문제 알고리즘의 특성 시각화와 고찰

본 기사의 프로그램은 Python 버전 3.13에서 실행하고 있습니다. 또한, numpy 버전은 2.3.5입니다.

지난 기사에서는 다중 팔 밴딧 문제(Multi-armed Bandit Problem)에서의 탐색(Exploration)과 활용(Exploitation)의 트레이드오프에 대해 설명했습니다. 지난 기사에서 진행했듯이, 그 특성을 수식이나 수치만으로 설명해도 직관적으로 이해하기 어렵다는 문제가 있습니다. 따라서 다양한 알고리즘 소개는 다음 기사부터 진행하고, 이번 기사에서는 탐색과 활용을 수행하는 알고리즘의 특성을 그래프로 시각화하는 프로그램을 구현합니다.

구체적으로는 '원시 몬테카를로법(原始モンテカルロ法)'으로 다중 팔 밴딧 문제를 해결한 경우를 그래프화합니다. 그리고 지난 기사에서 설명했던 '탐색에 전념한 원시 몬테카를로법'의 특성이 실제로 그래프 위에서 어떻게 나타나는지를 시각적으로 쉽게 보여줍니다.

다중 팔 밴딧 문제에서의 '활용(Exploitation)'이란 '가장 당첨될 것 같은 슬롯머신의 레버를 당기는 것'입니다. 이 활용으로 벌 수 있는 코인의 기대값은 지난 기사에서 설명했듯이 활용을 수행하기 전에 수집한 '경험(데이터)'이 많을수록 높아집니다.

이 경험은 슬롯머신의 레버를 당길 때마다 축적됩니다. 따라서 다중 팔 밴딧 문제를 해결하는 일반적인 알고리즘에서는 시도 횟수(레버를 당긴 총 횟수)가 많아질수록, 활용을 통해 얻는 코인의 기대값도 높아집니다1. 즉, 다중 팔 밴딧 문제의 목적 함수(얻게 되는 코인 총 횟수의 기대값)는 횟수를 늘릴수록 이론상의 최대값인 $f_{max}$2에 가까워져 갑니다.

지난 기사처럼 수식만으로 설명하는 방식으로는 '목적 함수가 $f_{max}$를 향해 어떻게, 어느 정도까지 다가가는지'를 상상하기 어렵습니다. 하지만 '레버를 당긴 횟수'와 '목적 함수'의 관계를 그래프화함으로써 그 관계를 직관적으로 파악할 수 있게 됩니다.

또한, 알고리즘의 특성을 더 깊이 이해하기 위해서는 목적 함수의 추이뿐만 아니라, 최고 슬롯머신을 추정하는 데 사용되는 '각 슬롯머신의 당첨 평균값(추정 확률)'이 어떻게 진정한 확률로 수렴해 가는가 하는 특성도 중요합니다. 그래서 이번 기사에서는 각 슬롯머신의 내부 상태의 추이 또한 그래프로 시각화하기로 합니다.

그래프화를 진행하려면 시뮬레이션 조건을 구체적으로 설정해야 합니다. 이번 기사에서는 슬롯머신 레버를 당기는 총 횟수 $m$을 1회부터 1만 회까지 변화시킨 각각의 케이스에 대해 실제로 문제를 해결하고, 결과를 그래프화합니다.

또한, 본 기사에서는 강화학습(RL) 용어에 따라 다음과 같이 정의합니다.

에피소드: 어느 $m$회에 걸쳐 슬롯머신의 레버를 선택하여 당기는 일련의 처리 -
스텝: 에피소드 내에서 레버를 실제로 1회 당기는 단일 처리. 강화학습의 관례에 따라, 스텝 수는 0부터 계산합니다.

이번 기사에서는 다중 팔 밴딧 문제를 '탐색을 수행한 후 마지막에 활용하는' 원시 몬테카를로법으로 해결하는 알고리즘의 시각화를 진행하고, 지난 기사에서 설명했던 '탐색에 전념했을 경우의 특성'이 실제로 그래프에서 어떻게 나타나는지 확인해 보겠습니다.

레버를 당기는 총 횟수($m$)가 1부터 1만까지 각각의 경우에 대해 원시 몬테카를로법을 그대로 실행하려고 하면, 계산량이 너무 방대하다는 문제에 직면합니다. 구체적으로는 총 약 5,000만 번의 탐색 처리를 수행해야 합니다. 이유는 다음과 같습니다.

원시 몬테카를로법의 1 에피소드는 '$m-1$회의 탐색과, 1회의 활용'으로 구성되기 때문에, $m$ 의 값이 변하면 탐색과 활용의 할당 방법이 완전히 바뀌어 버립니다 -
따라서 1부터 1만까지 모든 $m$에 대해 각각 독립적으로 원시 몬테카를로법을 실행할 필요가 있습니다 -
1 에피소드당 탐색 횟수는 $m - 1$회이므로, 모든 $m$을 합산한 탐색의 총합은 아래 식에서 약 $rac{10000^2}{2} =$ 약 5,000만 번이 됩니다.

$$0 + 1 + o 9999 = rac{{(0 + 9999)} imes 10000}{2} = rac{9999 imes 10000}{2} \ \ \approx rac{10000^2}{2}$$

에피소드당 발생하는 활용(exploitation) 횟수는 마지막 1회뿐이므로, 총 활용 횟수는 1만 회가 됩니다.

목적 함수인 '누적 보상 기대값 그래프'를 그리기 위해서는 여러 에피소드의 시뮬레이션을 거쳐 '누적 보상 평균값'을 계산해야 합니다. 따라서 에피소드당 시뮬레이션 처리 시간이 길면, 전체 시뮬레이션에 너무 많은 시간이 걸린다는 심각한 문제가 발생합니다.

지난 기사에서 설명했듯이, 마지막 행동을 제외하고 탐색(exploration)에 모든 것을 집중하는 원시 몬테카를로법(原始モンテカルロ法)의 경우, 목적 함수(얻은 코인의 총 기대값)의 값은 '마지막 1회에서 발생하는 활용'으로부터 거의 영향을 받지 않습니다.

예를 들어 $m = 10,000$인 경우, 마지막 1회의 활용이 목적 함수에 미치는 영향은 겨우 1만 분의 1입니다. 따라서 항상 슬롯머신을 무작위로 선택하는 '탐색만 수행하는 알고리즘(exploration-only algorithm)'은 원시 몬테카를로법의 거의 정확한 근사치로 간주할 수 있습니다.

게다가, 탐색만 수행하는 알고리즘에는 '$m$ 값에 관계없이 항상 무작위 탐색만 한다'는 큰 장점이 있습니다. 이를 통해 1만 번의 '탐색만 수행하는 시뮬레이션'을 단 한 번 실행하고, 그 중간(예: 1~5,000회까지)의 데이터를 추출하는 것만으로 $m = 5,000$인 경우의 시뮬레이션 결과로 그대로 재활용할 수 있습니다.

즉, $m=10,000$으로 탐색만 수행하는 시뮬레이션을 단 한 번 실행하는 것만으로, $m$이 1부터 10,000까지인 모든 경우의 결과(마지막 활용을 제외한 원시 몬테카를로법의 근사치)를 동시에 계산할 수 있다는 의미입니다.

이 경우 탐색 횟수는 겨우 1만 회에 불과하며, 원시 몬테카를로법을 시뮬레이션했을 때(약 5천만 회)와 비교하면 5,000분의 1로 급감합니다. 그 결과, 프로그램 실행 속도 또한 약 5,000배 빨라집니다. 이에 본 기사에서는 이 '탐색만 수행하는 알고리즘'을 원시 몬테카를로법의 대용(근사치)으로 사용하여 시각화를 진행하겠습니다.

원시 몬테카를로법의 경우, 1만 번의 시뮬레이션 데이터에서 1~5,000번째 데이터를 추출하더라도 $m = 5,000$ 시뮬레이션 결과가 되지 않습니다. 그 이유는 추출된 데이터에 '5,000회째 마지막 활용을 수행한다'는 원시 몬테카를로법 특유의 처리가 포함되어 있지 않고, 단순히 탐색만 한 데이터가 되기 때문입니다.

그래프화에 필요한 데이터를 모으기 위해, 지난 기사와 동일한 아래 설정의 다중 팔 밴디트 문제(Multi-Armed Bandit problem)에 대한 시뮬레이션 데이터를 수집하는 프로그램을 구현하겠습니다.

슬롯머신 대수: 3대 -
각 슬롯머신의 당첨 확률: $0.3, 0.5, 0.7$ -
슬롯머신 레버를 당기는 총 횟수: 1만 회

수집할 데이터는 각 단계별로 아래의 5가지 값입니다. 이 데이터를 굳이 기록해 두는 구체적인 이유는 나중에 그래프화할 때 자세히 설명하겠습니다.

누적 보상(Cumulative Reward): 그 단계까지 얻은 코인의 총합 -
1단계당 누적 보상: 누적 보상 $ ext{÷}$ 해당 시점의 단계 수 각 슬롯머신에서 얻은 코인의 총수****각 슬롯머신를 당긴 횟수-
각 슬롯머신에서 얻은 코인의 평균: 얻은 코인의 총수 $ ext{÷}$ 슬롯머신를 당긴 횟수

프로그램은 지난 기사에서 작성한 '원시 몬테카를로법 데이터 기록 프로그램'과 매우 유사하지만, 다음 점에서 크게 다릅니다.

• 시도(탐색) 횟수를 '1 ~ 4회'에서 1만 회로 대폭 증가함
• 탐색 후의 '활용'은 수행하지 않음 (탐색에 모든 것을 집중)
• 매 단계의 경과 과정을 모두 리스트에 기록함

프로그램에서 사용되는 주요 변수 목록은 다음과 같습니다. 다중 팔 밴디트 문제를 다루는 MAB 클래스에 대해 잊으신 분은 이전 기사를 복습해 주십시오.

아래는 1만 번의 탐색을 수행하며 데이터를 수집하고 기록하는 프로그램입니다.

4 ~ 17행: 초기 설정을 수행합니다. 14 ~ 16행에서는 슬롯머신의 대수만큼 빈 list를 요소로 하는 2차원 list를 생성하여 할당합니다. 이전 기사에서 설명했듯이, 여기서 [[]] * mab.num와 같이 작성하면 모든 요소가 같은 빈 리스트의 객체를 공유하게 되어(연동해서 수정되어 버리는) 문제가 발생한다는 점에 주의해야 합니다 -
19 ~ 32행: stepnum(1만)번 탐색을 수행하는 반복 처리-
20행: 탐색에서는 무작위로 슬롯머신을 선택하므로, 항상 np.random.choice(mab.num)으로 슬롯머신을 선택합니다 -
26 ~ 28행: 레버를 선택한 슬롯머신의 데이터(총수, 횟수, 평균)를 업데이트합니다 -
29 ~ 32행: 해당 스텝에서의 모든 슬롯머신의 상태를 리스트에 기록합니다. 선택되지 않은 머신 상태를 포함하여 매 스텝 모든 슬롯머신의 데이터를 계속 기록할 필요가 있다는 점에 주의해야 합니다

1 from ai import MAB
2 import numpy as np
3 ...

행 번호 없는 프로그램

from ai import MAB
import numpy as np
mab = MAB(p=[0.3, 0.5, 0.7])
...

실행 결과 (난수가 사용되었기 때문에 실행 결과는 매번 아래 내용과 약간 다릅니다)

얻은 코인의 총수 = 5024
얻은 코인의 평균 = 0.502
슬롯머신 0 (p=0.30)
...

실행 결과로부터, 대수의 법칙에 따라 아래와 같은 기대되는 데이터가 수집되었음을 확인할 수 있습니다.

• 1 스텝당 얻는 코인의 평균은 3개의 슬롯머신의 당첨 확률의 평균인 $p_{mean} = rac{0.3 + 0.5 + 0.7}{3} = 0.5$와 거의 같은 값이 됩니다
• 총 스텝 수는 1만 회이므로, 얻은 코인의 총수는 그 1만 배인 약 5000개입니다
• 3개의 슬롯머신이 모두 거의 균등하게 약 3300회 선택되었고, 얻은 코인의 평균은 슬롯머신의 당첨 확률(p)과 거의 같은 값이 되고 있습니다.

먼저, 스텝별 누적 보상(얻은 코인의 총수)의 추이를 나타내는 그래프를 그립니다. 이때 코인 총수의 상한선(이론상의 최대값)인 $f_{max}$와, 누적 보상의 내역(각 슬롯머신에서 얻은 코인의 총수)의 추이도 함께 그렸습니다.

6행: 슬롯머신의 당첨 확률의 최댓값(maxp)을 기준으로, 각 스텝별 누적 보상의 상한선(upper bound)을 계산하여 그래프를 그립니다. 눈에 띄게 이 그래프를 `c=

⚠️ [IMG:N] 형식 토큰은 이미지 placeholder 입니다. 번역하지 말고 원래 위치에 그대로 유지하세요.

import matplotlib.pyplot as plt
import japanize_matplotlib
plt.title(f"누적 보상의 추이 (원시 몬테카를로법의 근사)")
...

실행 결과

그래프에서 탐색에 전념한 알고리즘(원시 몬테카를로법의 근사)이 가진 다음 특성을 한눈에 알 수 있습니다. 이는 지난 기사에서 설명한 '탐색에 전념했을 경우의 고찰'을 그대로 뒷받침하는 결과입니다.

누적 보상이 이론상의 상한 $f_{max}$ 에 크게 미치지 못함

항상 최선의 슬롯머신(확률 0.7)을 계속 뽑을 수 있는 '신의 시점(검은색 직선)'과 비교했을 때, '코인의 총 개수(파란색 직선)'의 기울기가 현저히 낮습니다. 이는 실력이 낮은 하즈레 기계(확률 0.3 또는 0.5)에 대해서도 무식하게 균등한 횟수만큼 레버를 계속 할당하여 큰 손해를 보고 있기 때문입니다. -
누적 보상 및 세부 내역 그래프가 깨끗한 '직선'이 됨

모든 그래프가 완벽한 직선인 것으로 보아, 획득 코인의 매수가 시도 횟수(스텝 수)에 완전히 비례하고 있음을 알 수 있습니다. -
각 슬롯머신의 기울기가 '확률'에 대응함

점선 기울기에 주목하면, 가장 잘 맞는 arm 2(확률 0.7)가 가장 많은 코인을 벌고 있으며, 그 다음으로 arm 1(0.5), arm 0(0.3) 순서로 깔끔하게 배열되어 있습니다. 이는 대수의 법칙에 따라 각 슬롯머신의 획득 보상이 본래의 확률대로 기대값으로 수렴하고 있음을 시각적으로 보여줍니다.

앞서의 그래프는 누적 보상과 상한 모두 스텝 수가 증가함에 따라 우상향하는 성질을 가지고 있기 때문에, 두 값의 거리가 '가까워지고 있는지' 아니면 '멀어지고 있는지'를 직관적으로 파악하기 어렵습니다.

누적 보상의 상한 $f_{max}$는 아래와 같이 가장 잘 맞는 슬롯머신의 확률 $p_{max}$에 스텝 수를 곱한 값입니다.

$$f_{max} = p_{max} imes ext{스텝 수}$$

이 공식을 스텝 수로 나누면, '1 스텝당 얻을 수 있는 코인의 상한(기대값)'은 항상 $p_{max}$라는 일정한 상수가 됩니다. 이처럼 총합계가 아니라 스텝 수로 나눈 '1회당 평균값'으로 변환하여 비교하는 것이 알고리즘의 실제 실력을 직관적으로 평가하기 더 쉽습니다.

아래는 스텝당 누적 보상과 그 상한 및 평균의 추이를 그리는 프로그램입니다. 앞선 프로그램과의 차이점은 다음과 같습니다.

upperbounds

(상한 기준선)의 모든 요소를 상수인 maxp (0.7)로 변경했습니다 -
비교 기준으로, 3대 모든 머신의 확률 평균값인 $0.5$를 나타내는 '평균 적중' 선을 추가했습니다 -
1 스텝당 획득 코인의 추이를
mean_coins
으로 그렸습니다 -
그래프의 세로축 범위를 0 ~ 1에 고정하여 변화를 파악하기 쉽게 하기 위해,
plt.ylim(0, 1)
을 실행했습니다 -
각 슬롯머신의 개별 평균 추이(
`slot[

다음으로 소개할 똑똑한 강화학습(RL) 알고리즘에서는 스텝 수가 증가함에 따라 주황색 선이 '적중률 평균($0.5$)'을 돌파하고, 신의 시점인 '상한 $0.7$'을 향해 우상향하는 특성을 보입니다. 이번 그래프는 그 성능을 측정하기 위한 '최악의 기준선(Baseline)'으로서 중요한 의미를 가집니다.

그래프의 왼쪽 끝(스텝 수가 1~수백 회인 영역)에 주목하면, 선이 심하게 상하로 흔들리고 있습니다. 이는 시도 횟수가 적을 때는 데이터의 분산(Variance)이 커지지만, 횟수를 늘릴수록 참값에 수렴하는 대수의 법칙 때문입니다.

따라서 앞으로 어떤 천재적인 알고리즘을 도입하더라도, 데이터가 부족한 초기 몇 스텝부터 수백 스텝 사이에는 반드시 이렇게 그래프의 흔들림이 커집니다.

탐색(Exploration)과 활용(Exploitation) 알고리즘의 성질을 더 깊이 이해하기 위해서는 목적 함수(코인 개수)의 추이뿐만 아니라, 'AI가 각각의 슬롯머신을 얼마나 선택했는지'라는 상세한 데이터를 파악하는 것도 중요합니다.

각 슬롯머신이 선택된 횟수의 추이를 그래프화함으로써, 스텝 수가 늘어나 학습이 진행됨에 따라 AI가 우수한 슬롯머신을 어떻게 '편애(행동의 편향)'했는지를 시각적으로 알 수 있습니다.

아래는 그 그래프를 그리는 프로그램입니다.

plt.title(f"슬롯머신의 선택 횟수 (순수 몬테카를로법 근사)")
for arm in range(mab.num):
plt.plot(slot["selectnums"][arm], label=f"arm {arm} (p={mab.p[arm]:.2f})")
...

실행 결과

그래프를 확인하면, 탐색에만 전념한 알고리즘(순수 몬테카를로법 근사)의 행동에 대해 다음과 같은 특징을 알 수 있습니다.

• 세 개의 선이 완전히 겹쳐져 깨끗한 하나의 직선처럼 보인다
  arm 0부터 arm 2까지의 선택 횟수를 나타내는 그래프는 거의 완벽하게 겹쳐지며 우상향하고 있습니다. 이는 AI가 '편애'를 전혀 하지 않고, 1만 스텝이 끝날 때까지 모든 슬롯머신을 완전히 평등(확률 $rac{1}{3}$)하게 계속 선택했음을 의미합니다.
• 정보가 전혀 활용되지 않는다
  도중에 'arm 2 (확률 0.7)가 적중하기 쉽다'는 데이터가 모였다고 해도, 이 알고리즘에는 그 정보를 활용하는 장치가 없습니다. 결과적으로, 최악의 실패 기계인 arm 0 (확률 0.3)도 최고의 적중 기계와 같은 횟수(약 3,333회)만큼 쓸데없이 계속 당겨지게 됩니다.

앞으로 소개할 똑똑한 강화학습 알고리즘에서는 처음에는 세 개의 선이 나란하지만, 학습이 진행됨에 따라 '적중하기 쉬운 슬롯머신의 선만 급격히 위로 튀어 오르고, 실패 기계의 선은 바닥을 기듯이 수평으로 유지되는' 편애 그래프가 나타나게 됩니다. 이번 완벽하게 나란한 그래프는 그것들과 비교하기 위한 중요한 기준점이 됩니다.

지난번 글에서 설명했듯이, 강화학습의 '활용(Exploitation)'에서는 '각 슬롯머신이 얻은 코인 개수의 평균값(표본 평균)'을 그 슬롯머신의 실제 적중 확률에 대한 추정치로 간주하고, 그 값이 최대가 되는 슬롯머신을 선택합니다. 따라서 이 추정치가 스텝마다 어떻게 변화하는지는 알고리즘의 성질이나 추측의 정확도를 평가하기 위한 매우 중요한 요소입니다.

아래는 각 슬롯머신의 적중 확률 추정치를 그리는 프로그램입니다. 추정치의 정확도가 직관적으로 전달되도록, 각 슬롯머신의 '실제 적중 확률(참 확률)'을 나타내는 수평한 기준선을 검은색(`c=

시작 직후(단계 수가 적은 단계)에는 어떤 머신도 추정치가 심하게 오르내립니다. 하지만 단계 수가 1,000, 2,000으로 늘어날수록 변동이 급격히 줄어들어 검은 점선(진정한 확률: 0.3, 0.5, 0.7)에 깔끔하게 수렴해 갑니다. 이것이야말로 이전 기사에서 소개했던 '대수의 법칙'이 가져다주는 수학적 이점입니다. -
원시 몬테카를로법(原始モンテカルロ法)이 '쓸데없는 탐색'을 하고 있다는 증거

그래프의 '중반부터 후반(단계 수 3,000~10,000)'에 주목해 주세요. 3,000 단계를 넘어서자 세 대의 추정치는 진정한 확률과 거의 일치하며, '어떤 기계가 가장 우수한지(arm 2인 것)'는 거의 완전히 명확합니다. 그럼에도 불구하고 이번의 '탐색에만 전념한 알고리즘'은 나머지 7,000 단계 동안, 이미 알 수 있는 답을 확인하기 위해서만 완전 무작위 탐색을 어설프게 계속하고 있습니다.

이러한 '이미 실력 차이가 충분히 보임에도 불구하고, 안 좋은 기계를 공평하게 계속 당겨주는 낭비'를 없애고, '확률이 낮은 안 좋은 기계의 탐색은 일찍 중단하고, 잘 될 것 같은 우수한 기계의 '활용' 쪽으로 치우치는' 영리한 알고리즘이 앞으로의 기사에서 설명할 ε-greedy법(イプシロン・グリーディ法)이나 UCB1 알고리즘이 됩니다.

여기까지는 한 번의 에피소드(1만 단계)로 얻은 데이터를 그래프화했지만, 다중 팔 밴디트 문제의 목적 함수는 단 한 번의 우연한 결과가 아니라, **무한히 많은 에피소드를 반복했을 때의 평균값을 나타내는 '누적 보상의 기대값'**입니다. 따라서 단지 한 번의 에피소드 결과를 그래프로 그리는 것만으로는 해당 알고리즘의 진정한 성능을 올바르게 분석하기에 불충분합니다.

그렇다고 해서 현실적으로 무한히 많은 에피소드를 실행하는 것은 불가능하므로, 본 기사에서는 1,000번의 에피소드를 반복 실행하고 그 평균값을 시각화하여 분석할 예정입니다.

임의의 횟수의 에피소드 시뮬레이션을 쉽게 실행할 수 있도록, 먼저 한 번의 에피소드를 진행하고 그 결과를 반환하는 play_episode이라는 함수를 정의하려고 합니다.

play_episode는 앞으로 다양한 밴디트 문제에 대응할 수 있도록 아래와 같은 가상 인수를 가진 함수로 정의합니다. 또한, 반환값은 에피소드 내에서 수집한 각 데이터를 할당한 변수를 요소로 하는 tuple 타입입니다.

아래는 play_episode를 정의하는 프로그램입니다. 앞서의 1 에피소드를 진행하는 프로그램을 함수로 모았을 뿐이므로 설명은 생략합니다.

def play_episode(mab, stepnum):
total_coin = 0
total_coins = []
...

정의한 함수를 사용하여 앞서와 같은 설정의 다중 팔 밴디트 문제에 대한 1만 단계 에피소드 처리를 수행하면, 아래 실행 결과에서 앞서와 거의 같은 결과를 얻을 수 있음을 확인할 수 있었습니다.

total_coin, total_coins, mean_coin, mean_coins, slot = play_episode(mab, stepnum)
print(f