多腕バンディット問題
多腕バンディット問題（Multi-Armed Bandit Problem）は、機械学習における強化学習の一分野です。
多腕バンディットとは実際にはスロットマシンのことで、レバー（腕）を引くと、ランダムに生成された確率分布に基づいて報酬が得られます。一つのスロットマシンを「ワンアームドバンディット」と呼び、複数のスロットマシンがある場合は「マルチアームドバンディット」と呼ばれます。プレイヤーはどのレバー（腕）が最も高い報酬をもたらすか事前には知らず、各レバー（腕）を試しながらその情報を収集し、どれを選ぶのが最も良いかの推定を行います。このアルゴリズムは、ウェブページのA/Bテスト、臨床試験、広告配信最適化、レコメンデーションシステムといった場面に応用されています。
この問題に対する主な戦略やアルゴリズムには以下のようなものがあります。
・Epsilon-greedy policy
一定の確率εでランダムに行動を選択し、残りの1-εの確率で現時点で最も良いと評価される行動を選択します。
・Softmax exploration
レバー（腕）の推定値のソフトマックス関数を用いて、確率的に行動を選択する。推定値が高いレバー（腕）ほど選ばれやすくなるが、全ての腕がある程度の確率で選ばれるため、探索が促される。
・UCB（Upper Confidence bound algorithm）
推定された報酬の不確実性を考慮に入れ、それぞれのレバー（腕）の上限信頼境界を計算して行動選択を行う。時間が経つにつれて、不確実性を減らしながら最適なレバー（腕）を効率的に特定する。
・Thomson sampling technique
ベイズ推定を用いて、各レバー（腕）の報酬分布に対する事後分布を更新し、その分布からサンプリングして行動を選択する。報酬の不確実性を自然に取り入れた探索が可能。
この記事では、多腕バンディット問題をPythonで実装してみたいと思います。
インストール
今回は強化学習アルゴリズムの開発と評価をするためのツールキットであるOpenAI Gymの後継として開発されたGymnasiumを利用して多腕バンディット問題を実装してみます。
Gymnasiumをインストールします。
!pip install gymnasiumカスタム環境の定義
まずは多腕バンディット問題をシミュレートするための環境を定義します。
import numpy as np
import gymnasium as gym
from gymnasium import spaces
class MultiArmedBanditEnv(gym.Env):
def __init__(self, n_arms=10):
super(MultiArmedBanditEnv, self).__init__()
self.n_arms = n_arms
self.action_space = spaces.Discrete(n_arms)
self.observation_space = spaces.Discrete(1)
self.means = np.random.normal(0, 1, n_arms)
def reset(self):
return 0, {}
def step(self, action):
assert self.action_space.contains(action), "Invalid action"
reward = np.random.normal(self.means[action], 1)
done = True
return 0, reward, done, False, {}__init__メソッドでは、腕の数を指定できるようにし（n_arms)、エージェントが取れる行動（action_space）や各腕の平均報酬（means）を設定しています。spaces.Discrete(n_arms)によって設定した腕の数の分だけ選ぶアクションを取る事ができます。n_armsにはデフォルトで10を設定しているので、１０種類のアクションがあるという事になります。またnp.random.normal(0, 1, n_arms)で各腕の平均報酬をランダムに設定しています。各腕の報酬は、この平均値を中心とした正規分布に従って決まるため、ある腕は平均して高い報酬を提供し、別の腕は低い報酬を提供することになります。
step メソッドは実際にエージェントが選択したアクションに基づいて報酬を計算し、その結果を返しています。
環境の登録
定義したカスタム環境をGymnasiumの環境として利用できるようにするためにgym.envs.registration.registerで環境の登録を行います。
gym.envs.registration.register(
id='MultiArmedBandit-v0',
entry_point=MultiArmedBanditEnv,
max_episode_steps=1,
)環境の作成とパラメーターの設定
登録したカスタム環境から環境を作成し、パラメーターの設定を行います。
今回はEpsilon-greedy policyによるシミュレーションなので、確率（epsilon）を設定しています。またn_episodesでエピソードの数を指定しており、エージェントが1000回、腕を引く（アクションを選択する）ことを意味しています。
env = gym.make('MultiArmedBandit-v0', n_arms=10)
epsilon = 0.1
n_actions = env.action_space.n
n_episodes = 1000
n_steps = 1多腕バンディット問題のシミュレーション
それでは、多腕バンディット問題のシミュレーションを行っていきます。
各エピソード毎にアクションの選択を行い、報酬によって価値推定値の更新を行っていきます。
Q = np.zeros(n_actions)
N = np.zeros(n_actions)
rewards = []
for episode in range(n_episodes):
state, info = env.reset()
total_reward = 0
for step in range(n_steps):
if np.random.rand() < epsilon:
action = np.random.randint(n_actions)
else:
action = np.argmax(Q)
state, reward, done, truncated, info = env.step(action)
N[action] += 1
Q[action] += (reward - Q[action]) / N[action]
total_reward += reward
if done or truncated:
break
rewards.append(total_reward)
print(f"平均報酬: {np.mean(rewards)}")
print(f"価値推定値: {Q}")アクションの選択は下記の部分にあります。
if np.random.rand() < epsilon:
action = np.random.randint(n_actions)
else:
action = np.argmax(Q)先ほど定義したパラメーターの確率（epsilon）でランダムにアクションを選択（探索）し、それ以外は現在の価値推定値が最も高いアクションを選択しています。その後選択したアクションを実行（env.step）し、価値推定値を更新します。
結果は下記のようになりました。
平均報酬: 1.0929123578670734
価値推定値: [ 0.26206251 0.21219351 -1.73397044 -0.46798491 1.25156886 -0.91549809
-2.18608351 1.15511442 -1.39691308 -0.55778289]10個の腕の価値推定値と全体の平均報酬を示しています。
エピソード全体を通して得られた報酬の平均が約1.09であることは、エージェントが比較的良いアームを選択できていることを示しています。
価値推定値に大きなばらつきがあることから、エージェントは異なるアームの報酬分布をある程度学習し、良いアームと悪いアームを区別できていそうです。