数式とPython実装から理解するバンディットアルゴリズム

バンディットアルゴリズムは、限られた情報の中で最適な選択を見つけるための強力な手法として、多くの分野で注目されています。特に、広告の最適表示や推薦システム、オンライン学習などリアルタイムに意思決定を行う場面で応用されています。しかし、名前だけ聞くと難しそうに感じるかもしれません。

この記事では、バンディットアルゴリズムの基本的な考え方を数式とPythonコードを通じてわかりやすく解説します。初めてバンディットに触れる方でも理解しやすいよう、理論と実装をバランスよく学べる構成です。

この記事で学べること:

バンディット問題とは何か、その背景と課題
代表的なアルゴリズムの数式と直感的な解釈
Pythonでの簡単な実装例

例えば、あるアーム（選択肢）を選んだときの期待報酬を $\mu_i$、選択回数を $n_i$ とすると、基本的なアルゴリズムの一つであるUCB（Upper Confidence Bound）は以下のように定義されます。

\[
\text{UCB}_i = \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}}
\]

この式は、現在の報酬の推定値 $\hat{\mu}_i$ に加えて、探索のための不確実性を考慮している点がポイントです。

バンディットアルゴリズムを数式で理解し、Pythonコードで実装することで、理論と実践の両面からアルゴリズムの動きを把握できました。特に、探索と活用のトレードオフという難しいテーマを、具体的な式とコードを通じてイメージしやすくなったのではないでしょうか。

今回紹介したUCBをはじめ、他にも確率的アプローチやベイズ的手法など多様なバンディットアルゴリズムがあります。実際の問題に応じて適切なアルゴリズムを選び、試してみることが重要です。

次に読むと良い関連記事候補の観点は、「バンディットアルゴリズムの応用事例や実データを使った評価方法」です。具体的な応用例に触れることで、理解がさらに深まるでしょう。

実データを用いたバンディットアルゴリズムの比較検証
強化学習との違いと共通点
ベイズバンディットアルゴリズムの基礎

バンディットアルゴリズムとは何か

バンディットアルゴリズムは、不確実な環境下で「どの選択肢（アーム）を選ぶべきか」を学習し、最適な意思決定を目指すアルゴリズムです。名前は「多腕スロットマシン（multi-armed bandit）」という問題設定に由来します。複数のスロットマシンのレバー（アーム）があり、それぞれ異なる確率で報酬が得られるとします。この中で最も高い報酬を得るレバーを見つけることが目的です。

初心者の方にとっては「試行錯誤しながら最善策を見つける方法」とイメージすると分かりやすいでしょう。単純に毎回ランダムに選ぶのではなく、過去の結果を活かしながら、より良い選択肢を見つけていく仕組みです。

バンディット問題の数式表現

それぞれのアーム $ i $ は未知の報酬期待値 $ \mu_i $ を持っています。目標は、複数の選択肢から最大の期待報酬を得ることです。時間ステップ $ t $ で選択したアームを $ A_t $、得られた報酬を $ R_t $ とすると、累積報酬は次のように表されます。

\[
S_T = \sum_{t=1}^T R_t
\]

しかし、最適な戦略は未知のため、期待報酬の最大値 $ \mu^* = \max_i \mu_i $ と比較して、どれだけ差があるか（後悔 regret）を最小化することが重要です。

簡単なPython実装例

まずは、2つのアームを持つ単純なバンディット問題を考えましょう。各アームの報酬は正規分布に従うと仮定し、ε-グリーディ法で選択します。

import numpy as np

class SimpleBandit:
    def __init__(self, true_means):
        self.true_means = true_means  # 各アームの真の平均報酬
        self.n_arms = len(true_means)
        self.counts = np.zeros(self.n_arms)  # 各アームの選択回数
        self.values = np.zeros(self.n_arms)  # 各アームの推定平均報酬

    def select_arm(self, epsilon=0.1):
        if np.random.rand() &lt; epsilon:
            return np.random.randint(self.n_arms)  # 探索
        else:
            return np.argmax(self.values)  # 活用

    def update(self, chosen_arm, reward):
        self.counts[chosen_arm] += 1
        n = self.counts[chosen_arm]
        value = self.values[chosen_arm]
        # 新しい平均値を逐次更新
        self.values[chosen_arm] = ((n - 1) / n) * value + (1 / n) * reward

# 使用例
bandit = SimpleBandit([1.0, 1.5])  # アーム0は平均1.0、アーム1は平均1.5
for _ in range(1000):
    arm = bandit.select_arm()
    reward = np.random.randn() + bandit.true_means[arm]  # ノイズ付き報酬
    bandit.update(arm, reward)

print("推定平均報酬:", bandit.values)

この例では、一定確率でランダムに選択（探索）し、それ以外は現在の推定値が最大のアームを選ぶ（活用）という単純な戦略を使っています。実際のバンディットアルゴリズムはこの基本形を改良して、より効率的に報酬を最大化します。

関連記事

バンディット問題の基本概念

バンディット問題は、複数の選択肢（腕、アーム）から最適なものを選び続ける問題で、強化学習やオンライン学習の基礎となる課題です。例えば、スロットマシンの複数のレバー（アーム）があり、それぞれ異なる確率で報酬が得られます。目的は、限られた回数の試行で最大の報酬を獲得することです。

この問題の核心は「探索（exploration）」と「活用（exploitation）」のバランスをどう取るかにあります。探索とは未知のアームを試して情報を得ること、活用とは既に高評価のアームを選び続けることを指します。

数学的には、$K$ 本のアームがあり、それぞれのアーム $i$ は確率分布 $P_i$ に従う報酬を生み出すとします。時刻 $t$ にアーム $A_t$ を選択し、報酬 $X_{t}$ を受け取ります。目標は、累積報酬の期待値を最大化することです。

ここで、最適なアームの期待報酬を $\mu^* = \max_i \mathbb{E}[X_i]$、選択したアームの期待報酬を $\mathbb{E}[X_{A_t}]$ とすると、「後悔（regret）」は以下の式で表されます。

\[ R(T) = T \mu^* – \sum_{t=1}^{T} \mathbb{E}[X_{A_t}] \]

後悔とは、もし常に最適なアームを選べていた場合と比較して、どれだけ報酬を逃したかの指標です。バンディットアルゴリズムはこの後悔を最小化することを目指します。

簡単なPythonコードで、期待報酬の平均を更新しながらアームを選択する例を示します。

import numpy as np

# アームの数
K = 3
# 各アームの期待報酬（本来は未知）
true_means = [0.3, 0.5, 0.7]
# 選択回数カウント
counts = np.zeros(K)
# 推定平均報酬
estimated_means = np.zeros(K)

def pull_arm(i):
    return np.random.binomial(1, true_means[i])

# 初期に各アームを1回ずつ試す
for i in range(K):
    reward = pull_arm(i)
    counts[i] += 1
    estimated_means[i] = reward

# 以降は最も期待報酬が高いアームを選択
for _ in range(10):
    arm = np.argmax(estimated_means)
    reward = pull_arm(arm)
    counts[arm] += 1
    # 新しい平均を計算
    estimated_means[arm] += (reward - estimated_means[arm]) / counts[arm]
    print(f"選択アーム: {arm}, 報酬: {reward}, 推定平均: {estimated_means[arm]:.2f}")

このように、バンディット問題は試行錯誤を通じて最適な選択肢を見つけるためのモデルであり、数式と実装の両方で理解することが重要です。

バンディットアルゴリズムの応用例

バンディットアルゴリズムは、限られたリソースの中で最適な選択を見つける問題に非常に有効です。具体的な応用例としては、以下のような場面で使われています。

オンライン広告の最適化
複数の広告案の中から、クリック率が高い広告を自動的に選び続けることにより、収益を最大化します。
レコメンドシステム
ユーザーの嗜好に合わせて、最適な商品やコンテンツを提示するためにバンディットアルゴリズムが活用されます。
臨床試験のデザイン
複数の治療法の効果を比較する際に、有効な治療法を早期に見つけるために利用されます。

ここで、バンディットアルゴリズムの基本的な考え方を数式で示しましょう。あるアーム（選択肢） $i$ の期待報酬を $\mu_i$ とします。実際には $\mu_i$ は未知ですが、試行を重ねることで報酬の平均 $\hat{\mu}_i$ を計算できます。

例えば、UCB1（Upper Confidence Bound 1）アルゴリズムでは、次に選ぶアーム $i$ は以下のスコアを最大化するものを選びます。

\[
\text{UCB}_i = \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}}
\]

ここで、

$\hat{\mu}_i$ はアーム $i$ の平均報酬
$t$ はこれまでの総試行回数
$n_i$ はアーム $i$ の試行回数

この式は、「平均報酬が高いアームを優先しつつ、試行回数が少ないアームも探索する」というバランスを表します。探索（Exploration）と活用（Exploitation）のトレードオフをうまく取るための仕組みです。

以下は、PythonでUCB1アルゴリズムのスコアを計算する簡単な実装例です。

import math

def ucb_score(mean_reward, total_counts, arm_counts):
    if arm_counts == 0:
        return float('inf')  # 未試行のアームは優先的に選ぶ
    return mean_reward + math.sqrt(2 * math.log(total_counts) / arm_counts)

# 例: 3つのアームの平均報酬と試行回数
mean_rewards = [0.5, 0.6, 0.4]
arm_counts = [10, 5, 2]
total_counts = sum(arm_counts)

scores = [ucb_score(m, total_counts, n) for m, n in zip(mean_rewards, arm_counts)]
print(scores)

このように、バンディットアルゴリズムは現実の問題において、効率的に最適な選択肢を探し出す強力な手法として広く利用されています。初心者の方も、数式の意味を理解しながらPythonコードで試してみることで、より深く理解できるでしょう。

数式で理解するバンディットアルゴリズムの仕組み

バンディットアルゴリズムは、限られた回数の中で最も良い選択肢（アーム）を見つけるための方法です。例えば、スロットマシンのどのレバーを引くかを決める問題に似ています。ここでは、最も基本的なアルゴリズムの一つである「ε-グリーディ法」を数式とPythonコードで解説します。

まず、バンディット問題の基本的な考え方は、各アーム$a$に対して「期待報酬」を推定し、それをもとに次に引くアームを決めることです。報酬の期待値を $\mu_a$ とすると、理想的には最大の $\mu_a$ を持つアームを常に選びたいですが、実際には未知のため試行錯誤が必要です。

ε-グリーディ法では、次のように行動を決めます。

確率 $1-\varepsilon$ で、現在の推定期待報酬が最大のアームを選ぶ（活用）。
確率 $\varepsilon$ で、ランダムにアームを選ぶ（探索）。

この仕組みは以下の式として表せます。

\[
a_t =
\begin{cases}
\arg\max_a \hat{\mu}_a & \text{with probability } 1-\varepsilon \\
\text{random arm} & \text{with probability } \varepsilon
\end{cases}
\]

ここで、$\hat{\mu}_a$はアーム$a$のこれまでの試行で得られた報酬の平均値です。つまり、プレイヤーはほとんどの場合で最も良さそうなアームを選びつつ、時々別のアームを試して新しい情報を得ることで、より良い選択肢を見つけていくのです。

この考え方をPythonで実装してみましょう。以下は、3つのアームを持つ簡単な例です。

import numpy as np

class EpsilonGreedy:
    def __init__(self, n_arms, epsilon):
        self.n_arms = n_arms
        self.epsilon = epsilon
        self.counts = np.zeros(n_arms)
        self.values = np.zeros(n_arms)

    def select_arm(self):
        if np.random.rand() &lt; self.epsilon:
            return np.random.randint(self.n_arms)  # 探索
        else:
            return np.argmax(self.values)  # 活用

    def update(self, chosen_arm, reward):
        self.counts[chosen_arm] += 1
        n = self.counts[chosen_arm]
        value = self.values[chosen_arm]
        # 新しい平均値の計算
        self.values[chosen_arm] = ((n - 1) / n) * value + (1 / n) * reward

このクラスでは、select_armメソッドでアームを選択し、updateメソッドで選択後の報酬を反映させています。報酬の平均値を更新する式は、オンライン平均の計算式で効率的に期待値を推定します。

まとめると、バンディットアルゴリズムは「試行錯誤」の問題を数学的にモデル化し、期待報酬の推定と探索・活用のバランスをとることで、最適な選択肢を効率よく見つける仕組みです。初歩的なε-グリーディ法から理解を深めていくことで、より高度なアルゴリズムへのステップアップが可能になります。

ε-グリーディ法の数式と特徴

バンディットアルゴリズムの中でも、特に初心者に理解しやすい手法の一つが「ε-グリーディ法」です。このアルゴリズムは、探索（exploration）と活用（exploitation）のバランスを取るシンプルな方法として知られています。ここでは、ε-グリーディ法の数式的な定義とその特徴について詳しく解説します。

ε-グリーディ法の数式

ε-グリーディ法では、各アクションの期待報酬の推定値をもとに行動を選択します。具体的には、確率 $1 – \epsilon$ で現在の推定値が最も高いアクション（グリーディなアクション）を選び、確率 $\epsilon$ でランダムに別のアクションを選びます。ここで、$\epsilon$ は探索の割合を示すパラメータで、通常は小さな正の値（例えば0.1や0.01）に設定されます。

数式で表すと、時刻 $t$ における行動 $a_t$ の選択は次のようになります。

\[
a_t =
\begin{cases}
\arg\max_{a} Q_t(a) & \text{with probability } 1 – \epsilon \\
\text{randomly chosen action} & \text{with probability } \epsilon
\end{cases}
\]

ここで、$Q_t(a)$ はアクション $a$ の期待報酬の推定値であり、過去の報酬の平均などで更新されます。

特徴とメリット・デメリット

シンプルで実装が容易：探索と活用を確率的に切り替えるだけなので、コード量も少なく理解しやすいです。
探索の割合を調整可能：パラメータ $\epsilon$ を小さくすれば活用重視、大きくすれば探索重視になります。
局所最適のリスク：固定の $\epsilon$ だと、探索が十分でない場合に最適解に到達しにくい可能性があります。
報酬の変化に弱い：環境が変化すると、固定の $\epsilon$ では適応が遅れることがあります。

Pythonによる簡単な実装例

以下は、2つのアクションの中から報酬が大きい方を選びつつ、確率 $\epsilon$ でランダムなアクションを選ぶ簡単なPythonコード例です。

import numpy as np

class EpsilonGreedy:
    def __init__(self, n_actions, epsilon):
        self.n_actions = n_actions
        self.epsilon = epsilon
        self.counts = np.zeros(n_actions)
        self.values = np.zeros(n_actions)
    
    def select_action(self):
        if np.random.rand() &gt; self.epsilon:
            return np.argmax(self.values)
        else:
            return np.random.randint(self.n_actions)
    
    def update(self, action, reward):
        self.counts[action] += 1
        n = self.counts[action]
        value = self.values[action]
        # 新しい推定値の更新（平均の逐次計算）
        self.values[action] = ((n - 1) / n) * value + (1 / n) * reward

この実装では、選択したアクションの報酬をもとに逐次的に期待報酬の推定値を更新しています。初心者でも理解しやすく、実際のバンディット問題で基本的な動作を体験することができます。

UCB（上限信頼境界）アルゴリズムの数式解説

バンディットアルゴリズムの代表的な手法であるUCB（Upper Confidence Bound）アルゴリズムは、探索（explore）と活用（exploit）のバランスをとるために「信頼区間の上限」を利用します。具体的には、各アーム（選択肢）の期待報酬の推定値に、その推定の不確かさを加味した上限値を計算し、その値が最も高いアームを選ぶ戦略です。

UCBの基本的な数式は次の通りです。アーム $i$ の選択回数を $N_i$、総試行回数を $t$、そしてアーム $i$ の平均報酬を $\hat{\mu}_i$ とします。すると、UCB値は以下のように表されます。

\[
\text{UCB}_i(t) = \hat{\mu}_i + \sqrt{\frac{2 \ln t}{N_i}}
\]

この式の意味は次の通りです：

$\hat{\mu}_i$：これまでの試行で得られたアーム $i$ の平均報酬（活用の要素）
$\sqrt{\frac{2 \ln t}{N_i}}$：不確実性の大きさを表す項。アームをあまり選んでいない場合は大きくなり、探索の要素を担う

つまり、まだ試していないアームや試行回数が少ないアームは不確かさの項が大きくなり、試行回数が増えるとこの項は減少します。これにより、未知のアームを積極的に探索しながら、報酬の良いアームを活用していく仕組みになっています。

次に、簡単なPython実装例でUCB値の計算を示します。

import math

def calculate_ucb(mean_reward, total_counts, arm_counts):
    if arm_counts == 0:
        return float('inf')  # まだ試していないアームは無限大に設定して必ず選ぶ
    return mean_reward + math.sqrt((2 * math.log(total_counts)) / arm_counts)

# 例として3つのアームの平均報酬と選択回数がある場合
mean_rewards = [0.5, 0.6, 0.4]
arm_counts = [10, 5, 0]
total_counts = sum(arm_counts)

ucb_values = [calculate_ucb(m, total_counts, n) for m, n in zip(mean_rewards, arm_counts)]
print(ucb_values)

このコードでは、まだ選択していないアームに対しては無限大のUCB値を返すことで、必ず一度は選ぶようにしています。これにより、すべてのアームの評価が公平に行われ、最適解に近づくことが期待されます。

まとめると、UCBは「現在の平均報酬＋探索のための不確かさの上限値」というシンプルな数式を使い、バンディット問題における効果的な意思決定を実現しています。初心者の方も、この数式の意味とコード例を理解することで、バンディットアルゴリズムの基礎を掴みやすくなるでしょう。

トンプソンサンプリングの数式と直感的理解

バンディットアルゴリズムの中でも、トンプソンサンプリングは特に直感的で効果的な手法として知られています。ここでは、トンプソンサンプリングの基本的な数式と、その背後にある考え方を初心者向けにわかりやすく解説します。

まず、トンプソンサンプリングはベイズ推定の考え方を用いて、各アーム（選択肢）の成功確率の分布を更新しながら最適なアームを選択します。通常、成功確率はベルヌーイ分布で表されるため、事後分布はベータ分布で表現されます。具体的には、アーム $i$ の成功回数を $\alpha_i – 1$、失敗回数を $\beta_i – 1$ とすると、事後分布は次のようになります。

\[
\theta_i \sim \text{Beta}(\alpha_i, \beta_i)
\]

ここで、$\theta_i$ はアーム $i$ の成功確率の推定値です。トンプソンサンプリングでは、この事後分布からサンプリングした値を使って、最も高い値を持つアームを選びます。つまり、各アームからランダムに成功確率を1回ずつサンプリングし、その中で最大のものを選択するのです。

このプロセスを数式で表すと、アルゴリズムの1ステップでの選択は以下のようになります。

\[
a_t = \arg\max_i \theta_i, \quad \text{where} \quad \theta_i \sim \text{Beta}(\alpha_i, \beta_i)
\]

この仕組みの直感的な理解としては、「まだ試していないアームや成功回数が少ないアームは分布のばらつきが大きく、たまたま高いサンプルが出やすい」ため、探索が自然に促されるという点が挙げられます。一方、成功回数が多いアームは分布のばらつきが小さく、成功確率の推定が安定しているため、頻繁に選ばれやすくなります。

以下は、Pythonでトンプソンサンプリングの選択部分を実装した例です。

import numpy as np

def thompson_sampling(alpha, beta):
    """
    alpha: 各アームの成功回数+1 のリスト
    beta: 各アームの失敗回数+1 のリスト
    """
    sampled_theta = np.random.beta(alpha, beta)
    return np.argmax(sampled_theta)

この関数は、各アームのベータ分布からランダムサンプリングし、最大値を持つアームのインデックスを返します。実際には、報酬を得た後に $\alpha_i$ または $\beta_i$ の値を更新していくことで、逐次的に学習が進んでいきます。

まとめると、トンプソンサンプリングはベイズ的な不確実性の扱いを活用し、単純ながらも効果的に探索（exploration）と活用（exploitation）をバランスさせるバンディットアルゴリズムの代表的手法です。直感的にも「成功しそうなアームを確率的に選ぶ」イメージで理解できるため、初心者にもおすすめです。

Pythonでバンディットアルゴリズムを実装する準備

バンディットアルゴリズムは、不確実な環境で最適な選択肢を見つけるための方法です。Pythonで実装する前に、必要な基本的な準備を整えましょう。特に初心者の方は、まずは環境設定と基礎的な数学的理解を押さえることが重要です。

1. 開発環境の準備

Pythonの実装には以下の環境があると便利です。

Python 3.x: 最新の安定版を推奨します。公式サイトからインストール可能です。
Jupyter Notebook: 実験やデバッグに便利な対話型環境です。
必要なライブラリ: 数学計算やデータ操作に使う numpy と matplotlib を準備しましょう。

これらは以下のコマンドでインストール可能です。

pip install numpy matplotlib jupyter

2. バンディット問題の数理モデルの理解

バンディットアルゴリズムの基本は「複数の選択肢（アーム）があり、それぞれの報酬確率は未知」という設定です。例えば、各アーム $i$ の報酬確率を $\theta_i$ とします。このとき、目標は累積報酬を最大化するために最適なアームを選び続けることです。

数学的には、時刻 $t$ での選択 $a_t$ と得られる報酬 $r_t$ に対して、期待累積報酬は

\[
\mathbb{E}\left[\sum_{t=1}^T r_t\right]
\]

で表されます。ここでの課題は、各アームの $\theta_i$ を事前に知らないため、探索（Exploration）と活用（Exploitation）のバランスを取ることです。

3. 簡単な実装例：イプシロン・グリーディー法の準備

まずは代表的な手法の一つ、イプシロン・グリーディー法の基本構造を理解してみましょう。このアルゴリズムでは、確率 $\epsilon$ でランダムにアームを選択し、それ以外は現在のベストアームを選びます。数学的には次のように表されます。

選択確率 $P(a_t = i)$ は

\[
P(a_t = i) =
\begin{cases}
\frac{\epsilon}{k} + (1 – \epsilon) & \text{if } i = \arg\max_j \hat{\mu}_j \\
\frac{\epsilon}{k} & \text{otherwise}
\end{cases}
\]

ここで、$k$ はアーム数、$\hat{\mu}_j$ はアーム $j$ の推定平均報酬です。

Pythonでの準備コードは以下のようになります。

import numpy as np

# アーム数
k = 5
# イプシロンの設定
epsilon = 0.1
# 各アームの選択回数と報酬合計を記録
counts = np.zeros(k)
values = np.zeros(k)

def select_action():
    if np.random.rand() &lt; epsilon:
        # 探索: ランダムに選択
        return np.random.randint(k)
    else:
        # 活用: 現在の最良アームを選択
        return np.argmax(values / (counts + 1e-5))

このコードは、探索と活用の基本的な切り替えを実装するための基盤です。次のステップでは、選択後の報酬更新処理と実験シミュレーションに進みます。

関連記事

Pythonによるε-グリーディ法の実装例

バンディットアルゴリズムの中でも、ε-グリーディ法は最も基本的かつ理解しやすい戦略の一つです。ここでは、数式での定義からPythonコードまで順を追って解説します。

まず、ε-グリーディ法の基本的な考え方は「ほとんどの場合は現在最も期待報酬が高い行動を選びつつ、確率εでランダムな行動を選択し探索も行う」というものです。これにより、既知の情報を活用しながら未知の行動も試すバランスを取ります。

数式で表すと、ある時点での行動選択 $ a_t $ は次のようになります。

\[
a_t =
\begin{cases}
\arg\max_a Q_t(a) & \text{確率 } 1-\varepsilon \\
\text{ランダムな行動} & \text{確率 } \varepsilon
\end{cases}
\]

ここで、$ Q_t(a) $ はこれまでの試行から得た行動 $ a $ の推定期待報酬を表します。この推定値は、行動を選択した際の報酬の平均として更新されていきます。

Pythonコードでは、各行動の平均報酬を記録し、乱数を使って探索と活用を切り替えます。以下はその実装例です。

import numpy as np

class EpsilonGreedy:
    def __init__(self, n_actions, epsilon):
        self.n_actions = n_actions
        self.epsilon = epsilon
        self.counts = np.zeros(n_actions)  # 各行動の選択回数
        self.values = np.zeros(n_actions)  # 各行動の平均報酬

    def select_action(self):
        if np.random.rand() &lt; self.epsilon:
            # 探索: ランダムに行動を選択
            return np.random.randint(self.n_actions)
        else:
            # 活用: 期待報酬が最大の行動を選択
            return np.argmax(self.values)

    def update(self, action, reward):
        # 選択した行動の回数を増やす
        self.counts[action] += 1
        # 平均報酬を更新 (オンライン平均)
        n = self.counts[action]
        value = self.values[action]
        self.values[action] = value + (reward - value) / n

このクラスを使うことで、バンディット環境においてε-グリーディ法の行動選択と学習が簡単に行えます。例えば、報酬が得られるたびに update() メソッドで期待値を更新し、次の行動は select_action() で決定します。

まとめると、ε-グリーディ法は探索と活用のバランスを確率的に調整しながら、試行を重ねて期待報酬の推定を改善していくシンプルで効果的なバンディットアルゴリズムです。Pythonでの実装も直感的なので、まずはこの手法から理解を深めることをおすすめします。

PythonでUCBアルゴリズムを実装する方法

バンディットアルゴリズムの中でも、UCB（Upper Confidence Bound）アルゴリズムは「探索と活用」のバランスを数学的に取ることで知られています。ここでは、UCBの基本的な数式を理解し、それをPythonで実装する手順を初心者向けに解説します。

まず、UCBアルゴリズムの選択基準は以下の数式で表されます。

各アーム（選択肢）$ i $に対し、時刻$ t $でのスコアは

\[
UCB_i(t) = \hat{\mu}_i(t) + \sqrt{\frac{2 \ln t}{n_i(t)}}
\]

$ \hat{\mu}_i(t) $：アーム$ i $の平均報酬（これまで得られた報酬の平均）
$ n_i(t) $：アーム$ i $が選択された回数
$ t $：現在の総試行回数（全アームの選択回数の合計）

この式の解釈は、平均報酬に「信頼区間の幅」を足すことで、まだ試していないアームや試行回数が少ないアームを優先的に探索しつつ、報酬が高いアームも活用する仕組みです。

では、この数式をPythonで実装してみましょう。以下は、シンプルなUCBアルゴリズムのサンプルコードです。

import math

class UCB:
    def __init__(self, n_arms):
        self.n_arms = n_arms
        self.counts = [0] * n_arms        # 各アームの選択回数
        self.values = [0.0] * n_arms       # 各アームの平均報酬

    def select_arm(self, total_counts):
        for arm in range(self.n_arms):
            if self.counts[arm] == 0:
                return arm  # 一度も選んでいないアームを優先
        ucb_values = [
            self.values[i] + math.sqrt((2 * math.log(total_counts)) / self.counts[i])
            for i in range(self.n_arms)
        ]
        return ucb_values.index(max(ucb_values))

    def update(self, chosen_arm, reward):
        self.counts[chosen_arm] += 1
        n = self.counts[chosen_arm]
        value = self.values[chosen_arm]
        # 平均報酬の更新（オンライン平均）
        new_value = ((n - 1) / n) * value + (1 / n) * reward
        self.values[chosen_arm] = new_value

このクラスの使い方は以下のようにシンプルです。まず、アーム数を指定してインスタンスを作り、選択→報酬観測→更新を繰り返します。

select_arm(total_counts)：現在までの総試行回数を渡し、次に選ぶアームの番号を返します。
update(chosen_arm, reward)：選んだアームと得られた報酬を渡して、平均報酬と回数を更新します。

このようにUCBアルゴリズムは、単純な数学的ルールに基づくため、コードも直感的でわかりやすいのが特徴です。これを基に、より複雑な環境や報酬構造に対応する実装も可能です。

トンプソンサンプリングのPython実装手順

バンディットアルゴリズムの中でも特に人気の高いトンプソンサンプリングは、ベイズ推定を用いてアームの報酬分布を逐次的に更新しながら最適な選択を行う方法です。ここでは、初心者の方でも理解しやすいように、数式とPythonコードを交えて実装手順を解説します。

1. ベータ分布による事後分布のモデル化

トンプソンサンプリングは、各アームの成功確率をベータ分布で表現します。成功回数を $\alpha$、失敗回数を $\beta$ とすると、アーム $i$ の成功確率の事後分布は次のようになります。

\[
\theta_i \sim \mathrm{Beta}(\alpha_i, \beta_i)
\]

ここで、$\theta_i$ はアーム $i$ の成功確率のサンプル値を指し、トンプソンサンプリングはこの値を使ってどのアームを選ぶか決定します。

2. トンプソンサンプリングの基本アルゴリズム

各アームの $\alpha_i$ と $\beta_i$ を初期化（通常は1,1のベータ分布で非情報的事前分布）
各ラウンドで、各アームから $\theta_i$ をベータ分布からサンプリング
最も大きな $\theta_i$ を持つアームを選択し、報酬を観測
観測した報酬に応じて、対応するアームの $\alpha_i$ または $\beta_i$ を更新（成功なら $\alpha_i += 1$、失敗なら $\beta_i += 1$）

3. Pythonコード例

以下は、2つのアームを持つ簡単なトンプソンサンプリングの実装例です。

import numpy as np

# アーム数
n_arms = 2

# ベータ分布のパラメータ初期化
alpha = np.ones(n_arms)
beta = np.ones(n_arms)

# 実際の成功確率（環境）
true_probs = [0.3, 0.6]

# シミュレーション回数
n_rounds = 1000

for _ in range(n_rounds):
    # 各アームから成功確率をサンプリング
    theta = np.random.beta(alpha, beta)
    # 最大のthetaを持つアームを選択
    chosen_arm = np.argmax(theta)
    # 選択したアームで報酬を取得（成功:1, 失敗:0）
    reward = np.random.rand() &lt; true_probs[chosen_arm]
    # パラメータ更新
    if reward:
        alpha[chosen_arm] += 1
    else:
        beta[chosen_arm] += 1

このコードでは、成功確率が高いアームのベータ分布が次第に集中していき、最適なアームを選択する確率が高まっていきます。初心者の方はこの流れを理解し、パラメータの更新とサンプリングの関係性を確認すると良いでしょう。

バンディットアルゴリズムの性能評価方法

バンディットアルゴリズムの性能を評価する際に最も重要なのは「後悔（Regret）」の概念です。後悔とは、アルゴリズムが最適な選択をした場合に比べて、どれだけ報酬を逃したかを表す指標です。これにより、アルゴリズムがどれだけ賢く行動しているかを定量的に評価できます。

後悔は一般的に次のように定義されます。

時刻 $ t $ までに選択されたアームの報酬を考えると、最適なアームの期待報酬を $ \mu^* $、時刻 $ t $ に選択したアームの期待報酬を $ \mu_{a_t} $ とすると、累積後悔 $ R(T) $ は以下の式で表せます。

\[
R(T) = \sum_{t=1}^T (\mu^* – \mu_{a_t})
\]

この式の意味は、最適なアームを選び続けた場合の報酬と、実際にアルゴリズムが選んだアームの報酬との差の合計です。後悔が少ないほど、アルゴリズムは良い選択をしていると言えます。

次に、簡単なPythonコードで累積後悔を計算する例を示します。ここでは、報酬の期待値を既知として扱い、選択履歴から後悔を計算します。

# 最適アームの期待報酬
mu_star = 0.8

# 各時刻で選択したアームの期待報酬（例）
mu_selected = [0.5, 0.7, 0.6, 0.8, 0.4]

# 累積後悔の計算
cumulative_regret = 0
regret_list = []
for mu in mu_selected:
    regret = mu_star - mu
    cumulative_regret += regret
    regret_list.append(cumulative_regret)

print(regret_list)  # [0.3, 0.40000000000000013, 0.6000000000000001, 0.6000000000000001, 1.0]

この例では、最適アームの期待報酬を0.8とし、5回の選択での期待報酬を記録しています。出力の配列は各時刻での累積後悔を示しており、時刻が進むにつれて後悔が増える様子がわかります。

まとめると、バンディットアルゴリズムの性能評価は累積後悔を用いて行い、後悔が小さいほどアルゴリズムの性能が良いと言えます。これにより、実際の問題にアルゴリズムを適用する際の比較や改善が可能になります。

シミュレーションによるアルゴリズム比較

バンディットアルゴリズムは理論的な性質だけでなく、実際の環境での性能を比較することが重要です。ここでは、代表的なアルゴリズムであるε-greedy法とUCB1（Upper Confidence Bound）をシミュレーションで比較し、その特徴を初心者にもわかりやすく解説します。

まず、バンディット問題の報酬期待値を最大化するために、各アームの選択回数と報酬の平均から次のアームを選ぶ方針を定めます。UCB1では、次のアーム $ i $ の選択基準を以下の式で表します。

\[ a_t = \arg\max_{i} \left( \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}} \right) \]

ここで、
$ \hat{\mu}_i $ はアーム $ i $ のこれまでの平均報酬、
$ n_i $ はアーム $ i $ の選択回数、
$ t $ は現在の総試行回数です。
この式は「平均報酬」と「探索のための不確実性の幅」を足し合わせており、まだあまり試していないアームにもチャンスを与える仕組みになっています。

次に、Pythonで簡単なシミュレーションコード例を示します。ここでは、3つのアームの報酬確率が異なる設定で、1000回の試行を行い、各アルゴリズムの累積報酬を比較します。

import numpy as np

np.random.seed(0)

# 各アームの報酬確率
true_probs = [0.3, 0.5, 0.7]
n_arms = len(true_probs)
n_trials = 1000

def epsilon_greedy(epsilon):
    counts = np.zeros(n_arms)
    rewards = np.zeros(n_arms)
    total_reward = 0
    for t in range(1, n_trials+1):
        if np.random.rand() &lt; epsilon:
            arm = np.random.choice(n_arms)
        else:
            arm = np.argmax(rewards / (counts + 1e-5))
        reward = np.random.rand() &lt; true_probs[arm]
        counts[arm] += 1
        rewards[arm] += reward
        total_reward += reward
    return total_reward

def ucb1():
    counts = np.ones(n_arms)
    rewards = np.zeros(n_arms)
    for i in range(n_arms):
        rewards[i] = np.random.rand() &lt; true_probs[i]
    total_reward = rewards.sum()
    for t in range(n_arms+1, n_trials+1):
        ucb_values = rewards / counts + np.sqrt(2 * np.log(t) / counts)
        arm = np.argmax(ucb_values)
        reward = np.random.rand() &lt; true_probs[arm]
        counts[arm] += 1
        rewards[arm] += reward
        total_reward += reward
    return total_reward

# 実行例
eg_reward = epsilon_greedy(0.1)
ucb_reward = ucb1()

print(f"ε-greedy法の累積報酬: {eg_reward}")
print(f"UCB1の累積報酬: {ucb_reward}")

この結果から、一般的にはUCB1が探索と活用のバランスをうまく取り、より高い累積報酬を得る傾向があります。ただし、状況によっては単純なε-greedy法も安定した結果を示すことがあり、問題の性質やパラメータ設定によって最適なアルゴリズムは変わります。

シミュレーションを通じて、バンディットアルゴリズムの動作原理やパフォーマンスの違いを体感し、より実践的な理解を深めましょう。

バンディットアルゴリズムの課題と改善点

バンディットアルゴリズムは、限られた試行回数で最適な選択を見つけるための強力な手法ですが、いくつかの課題も存在します。特に初心者が理解しやすいよう、代表的な問題点とその改善策について解説します。

主な課題

探索と活用のバランス調整の難しさ
バンディット問題の核心は「探索（Exploration）」と「活用（Exploitation）」のバランスを取ることにあります。探索は未知の選択肢を試す行為であり、活用は既に良い結果が得られている選択肢を繰り返すことです。どちらかに偏ると、最適解に到達しづらくなります。
非定常環境への対応
実際の問題では報酬の分布が時間とともに変化する場合があります（非定常環境）。従来のバンディットアルゴリズムは報酬が固定と仮定しているため、この変化に追随できず性能が低下します。
計算コストの問題
複雑なアルゴリズムや多くの選択肢がある場合、計算量が増大し、リアルタイム性が求められる場面での適用が難しくなることがあります。

改善点と具体例

ここでは、代表的な改善手法として「アッパー信頼限界（UCB）アルゴリズム」の数式と簡単なPythonコードを示し、探索と活用のバランスをどのように取っているか解説します。

UCBアルゴリズムでは、各選択肢 $i$ のスコアを次の式で計算します。

\[
\text{UCB}_i = \hat{\mu}_i + \sqrt{\frac{2 \ln t}{n_i}}
\]

ここで、

$\hat{\mu}_i$：選択肢 $i$ の平均報酬
$t$：これまでの総試行回数
$n_i$：選択肢 $i$ が選ばれた回数

この式の意味は、平均報酬に加えて「探索項」と呼ばれる不確実性の指標を加えることで、まだ十分に試されていない選択肢を積極的に探索できるようにしている点です。

import math

def ucb_score(mean_reward, total_count, choice_count):
    if choice_count == 0:
        return float('inf')  # まだ試していない選択肢は優先的に選ぶ
    return mean_reward + math.sqrt((2 * math.log(total_count)) / choice_count)

このように数式を用いて探索と活用のバランスを動的に調整することで、バンディットアルゴリズムのパフォーマンス向上が期待できます。加えて、非定常環境には報酬の重み付けを変えるなどの工夫や、計算コスト削減のための近似手法も研究されています。

実践で使えるバンディットアルゴリズムの選び方

バンディットアルゴリズムは、多様な問題に適用できる一方で、どのアルゴリズムを選ぶかは状況によって異なります。初心者が実践でバンディットアルゴリズムを使う際には、以下のポイントを押さえることが重要です。

問題の性質を理解する
例えば、報酬の分布が既知か未知か、報酬が連続か離散かによって適切なアルゴリズムは変わります。シンプルな問題ならば「ε-greedy」や「UCB（Upper Confidence Bound）」が扱いやすいでしょう。
探索と活用のバランス
バンディット問題の核心は「探索（Exploration）」と「活用（Exploitation）」のバランスです。例えば、「ε-greedy」では確率 $ \varepsilon $ で探索を行い、それ以外は最も良いと判断された選択肢を使います。

「ε-greedy」の基本的な数式は以下の通りです：

選択戦略 $ A_t $ は時刻 $ t $ において、

\[
A_t = \begin{cases}
\text{ランダムに選択} & \text{確率 } \varepsilon \\
\arg\max_a Q_t(a) & \text{確率 } 1-\varepsilon
\end{cases}
\]

ここで、$ Q_t(a) $ はアーム $ a $ の推定報酬期待値です。

この戦略をPythonで実装する例を示します：

import numpy as np

class EpsilonGreedy:
    def __init__(self, n_arms, epsilon):
        self.n_arms = n_arms
        self.epsilon = epsilon
        self.counts = np.zeros(n_arms)
        self.values = np.zeros(n_arms)

    def select_arm(self):
        if np.random.rand() &lt; self.epsilon:
            return np.random.randint(self.n_arms)
        else:
            return np.argmax(self.values)

    def update(self, chosen_arm, reward):
        self.counts[chosen_arm] += 1
        n = self.counts[chosen_arm]
        value = self.values[chosen_arm]
        # 新しい平均の計算
        self.values[chosen_arm] = ((n - 1) / n) * value + (1 / n) * reward

このクラスは、アーム数と探索率 $ \varepsilon $ を指定し、select_arm() で行動を選び、update() で報酬フィードバックを受け取り推定値を更新します。初心者でも理解しやすく、かつ実用的なバンディットアルゴリズムの入門に最適です。

まとめると、問題の特性と探索・活用のバランスを考慮しつつ、まずはシンプルなアルゴリズムから試し、徐々に複雑な手法へとステップアップすることが実践での成功につながります。

関連記事

まとめ：数式とPythonで学ぶバンディットアルゴリズムのポイント

バンディットアルゴリズムは「探索と活用」のバランスを取るための強力な手法であり、数式を通じてその理論的背景を理解し、Pythonコードで実践的に学ぶことができます。特に初心者にとっては、抽象的な理論だけでなく、具体的な実装例を見ることで理解が深まります。

今回取り上げたアルゴリズムの中で代表的なものに「ε-greedy法」があります。これは確率εでランダムに探索（未確認の選択肢を試す）し、残りの1-εの確率で現在最も良いと判断される選択肢を活用するシンプルな戦略です。数式で表すと以下のようになります。

選択確率は

\[
P(a) = \begin{cases}
1 – \epsilon + \frac{\epsilon}{K} & \text{if } a = \arg\max_{a’} Q(a’) \\
\frac{\epsilon}{K} & \text{otherwise}
\end{cases}
\]

ここで、$K$ は選択肢の数、$Q(a)$ はアクション $a$ の期待報酬の推定値です。この式は、「最も期待値の高い選択肢を優先しつつ、一定割合で他の選択肢も試す」ことを意味します。

この考え方をPythonで実装すると以下のようになります。

import numpy as np

def epsilon_greedy(Q, epsilon):
    K = len(Q)
    if np.random.rand() &lt; epsilon:
        # 探索：ランダムに選択
        return np.random.randint(K)
    else:
        # 活用：最も期待値の高い行動を選択
        return np.argmax(Q)

この実装では、乱数を用いて探索か活用かを判断し、探索の場合はランダムに選択肢を選び、活用の場合は期待値が最大の選択肢を返します。初心者でも理解しやすく、実際に動かしながら試せる形となっています。

バンディットアルゴリズムの学習では、理論的な数式の理解と同時に、こうした簡単なコード実装を繰り返すことが重要です。これにより、単なる知識の暗記ではなく、実際のデータに対する応用力が身につきます。今後は、より複雑な手法や応用例にも挑戦し、実践的なスキルを高めていきましょう。

バンディットアルゴリズムとは何か

バンディット問題の数式表現

簡単なPython実装例

バンディット問題の基本概念

バンディットアルゴリズムの応用例

数式で理解するバンディットアルゴリズムの仕組み

ε-グリーディ法の数式と特徴

ε-グリーディ法の数式

特徴とメリット・デメリット

Pythonによる簡単な実装例

UCB（上限信頼境界）アルゴリズムの数式解説

トンプソンサンプリングの数式と直感的理解

Pythonでバンディットアルゴリズムを実装する準備

1. 開発環境の準備

2. バンディット問題の数理モデルの理解

3. 簡単な実装例：イプシロン・グリーディー法の準備

Pythonによるε-グリーディ法の実装例

PythonでUCBアルゴリズムを実装する方法

トンプソンサンプリングのPython実装手順

1. ベータ分布による事後分布のモデル化

2. トンプソンサンプリングの基本アルゴリズム

3. Pythonコード例

バンディットアルゴリズムの性能評価方法

シミュレーションによるアルゴリズム比較

バンディットアルゴリズムの課題と改善点

主な課題

改善点と具体例

実践で使えるバンディットアルゴリズムの選び方

まとめ：数式とPythonで学ぶバンディットアルゴリズムのポイント

コメントする コメントをキャンセル

コメントするコメントをキャンセル