contextual bandit問題の概要とアルゴリズム/実装例について

Contextual banditとは

Contextual banditは、強化学習の一種であり、複数の選択肢の中から最適な選択をする”マルチアームドバンディット問題の概要と適用アルゴリズム及び実装例について“でも述べているマルチアームドバンディット問題を解決するための枠組みとなる。この問題は、現在の状況(コンテキスト)に基づいて最適な選択をする必要がある場合に適用されるものとなる。Contextual bandit問題は以下の要素から構成される。

• コンテキスト(状況)：各選択肢の選択に関連する情報や特徴量を表すコンテキストが与えられる。例えば、ウェブサイト上で広告を表示する場合、コンテキストはユーザーの属性、ページの内容、その他の利用可能な情報といったものになる。
• 選択肢(アーム)：複数の選択肢(アーム)がある。例えば、広告を表示する場合、各アームは異なる広告のバリエーションを表す。
• 報酬(リワード)：各アームには、選択された場合に得られる報酬が関連付けられている。報酬は、目的に応じて異なる方法で定義することができ、例えば、広告の場合、報酬はユーザーのクリック率や購入率などと関連付けられることがある。

Contextual banditの目標は、与えられたコンテキストに基づいて、各状況で最も報酬の高い選択肢を見つけることであり、この問題を解決するために、様々なアルゴリズムが開発されている。代表的なアルゴリズムには、”ε-グリーディ法（ε-greedy）の概要とアルゴリズム及び実装例について“で述べているε-greedy法、”UCB（Upper Confidence Bound）アルゴリズムの概要と実装例“で述べているUpper Confidence Bound (UCB)法、”Thompson Samplingアルゴリズムの概要と実装例“で述べているThompson samplingなどがある。

Contextual banditの適用事例

Contextual banditは、多くの適用事例が存在している。以下に、いくつかの具体的な事例について述べる。

• オンライン広告配信: Contextual banditは、ウェブサイトやモバイルアプリでの広告配信に利用され、ユーザーの属性や行動履歴などのコンテキスト情報を考慮し、最適な広告を表示するために使用されている。各広告は選択肢(アーム)となり、ユーザーの反応やクリック率などの報酬を最大化するための選択を行うものとなる。
• 推薦システム: Contextual banditは、オンラインショッピングや音楽ストリーミングサービスなどの推薦システムにも適用され、ユーザーの特徴や過去の行動を考慮し、最適なアイテムやコンテンツを推薦するために使用されている。推薦するアイテムが選択肢(アーム)となり、ユーザーの満足度やクリック率などの報酬を最大化するための選択を行うものとなる。
• メディアパーソナライゼーション: メディア(記事、ニュース、動画など)のパーソナライズドな提供にもContextual banditが応用され、ユーザーの興味や嗜好を考慮し、最適なコンテンツを選択して提供するために使用されている。異なるコンテンツが選択肢(アーム)となり、ユーザーのエンゲージメントやクリック率などの報酬を最大化するための選択を行うものとなる。
• 臨床試験: 医療の分野でもContextual banditが活用されている。臨床試験では、異なる治療法の選択肢を患者に提案する必要があり、患者の特徴や病状を考慮し、最適な治療法を選択するためにContextual banditが使用される。治療法が選択肢（アーム）となり、患者の快復率や健康指標の改善などの報酬を最大化するための選択を行われている。

Contextual banditは選択問題が発生する多くの応用領域で活用され、コンテキストに応じて最適な選択をすることで、報酬の最大化やパフォーマンスの向上を実現することができるものとなる。

Contextual banditに用いられるアルゴリズム

Contextual bandit問題を解決するためには、さまざまなアルゴリズムが開発されている。以下に代表的なアルゴリズムについて述べる。

• ε-greedy法:

“ε-グリーディ法（ε-greedy）の概要とアルゴリズム及び実装例について“でも述べているε-greedy法は、強化学習(Reinforcement Learning)における一般的な探索手法の一つであり、簡単かつ効果的なContextual banditアルゴリズムでもある。強化学習は、環境と相互作用しながら、試行錯誤を通じて最適な行動を学習する機械学習の手法であり、ε-greedy法は、特に行動価値の推定が必要な場合によく使われる手法で、探索と活用(Exploration and Exploitation)のトレードオフを扱うために用いられている。ε-greedy法のアルゴリズムは以下のように概要できる。

1. 1. 初期化: 探索確率ε(0から1の値)を設定する。通常、εは比較的小さな値(例：0.1)に設定される。
   2. 行動選択: ε-greedy法では、確率εでランダムな行動を選択し、確率1-εで現在の最適な行動(行動価値が最大となる行動)を選択する。
   3. 探索と活用: ε-greedy法では、探索確率εによって、探索と活用のバランスを取っている。εの値が小さい場合は、ほとんどの場合に最適な行動を選択し、既に得られた知識を活用する。一方、εの値が大きい場合は、ランダムに行動を選択することで、未知の領域を探索しようとする。
   4. εの減衰: 通常、学習が進むにつれてεを徐々に小さくする減衰スケジュールを設定する。このようにすることで、初期段階では多くの探索を行い、徐々に活用を重視するようになる。

ε-greedy法はシンプルかつ効果的な探索戦略だが、探索確率εの設定には注意が必要となる。εが小さすぎると、十分な探索が行われず、局所的な最適解に陥る可能性がある。逆にεが大きすぎると、無駄なランダム探索が多くなり、効率的な学習が妨げられることがある。

ε-greedy法は、Q学習や”SARSAの概要とアルゴリズム及び実装例について“でも述べているSARSAなど、強化学習のさまざまな手法と組み合わせて使われ、適切なεの設定や減衰スケジュールは、具体的な問題に応じて調整されている。

• Upper Confidence Bound (UCB)法:

“UCB（Upper Confidence Bound）アルゴリズムの概要と実装例“でも述べているUpper Confidence Bound (UCB)法は、強化学習やマルチアームバンディット問題などの探索・活用問題において、効率的な行動選択を行うためのアルゴリズムであり、不確かさを考慮しながら選択を行うContextual banditアルゴリズムとなる。UCB法は、過去の情報を利用して、最も有望な行動を選択する手法であり、各アームの価値の推定値に不確かさの項を加えて、最適な選択を行い、不確かさの項は、選択回数や報酬の分散などの指標を使用して計算されるものとなる。

UCB法の基本的なアイデアは、各行動に対して上限信頼区間（Upper Confidence Bound）を計算し、その区間の上限が最も高い行動を選択するというものとなる。以下に具体的な手順を示す。

1. 1. 初期化: 各行動の試行回数を0とし、初期化する。
   2. UCB値の計算: 各行動のUCB値を計算する。UCB値は、行動の平均報酬に対する上限信頼区間の大きさを考慮して算出し、一般的に以下のように表される。UCB値 = 平均報酬 + 探索項（exploration term）探索項は、行動の試行回数に応じて増加することで、未知の行動に対して探索を促進する役割を果たす。
   3. 行動選択: UCB値が最大の行動を選択する。つまり、UCB値が最も大きい行動が「最も有望」とみなされる。
   4. 行動実行と報酬観測: 選択された行動を実行し、得られた報酬を観測する。
   5. 行動試行回数の更新: 選択された行動の試行回数を1増やす。
   6. UCB値の再計算: 新しい報酬情報をもとに、UCB値を再計算する。

これらの手順を繰り返すことで、より高い報酬が期待できる行動を効率的に探索・活用していくことが可能となる。UCB法は、マルチアームバンディット問題など、試行回数の少ない探索・活用問題において特に有効であり、UCB法は理論的にも効率的で、多くの場合、適切な報酬を最小限の試行回数で得ることができるとされている。ただし、UCB法にもパラメータ調整の重要性や問題によっては性能が変わる可能性があることを念頭に置く必要がある。

• Thompson sampling:

“Thompson Samplingアルゴリズムの概要と実装例“でも述べているThompson samplingは、マルチアームバンディット問題などの探索・活用問題において、効率的な行動選択を行うための確率的なアルゴリズムであり、確率的な選択を行うContextual banditアルゴリズムとなる。UCB法と同様に、報酬を最大化するための最適な行動を見つけることを目指すが、アプローチが異なる。

Thompson samplingの基本的なアイデアは、各アームの価値の分布を事前に設定し、コンテキストが与えられた際に各アームの価値のサンプルを取得、その後、報酬の期待値が高いアームを選択するものとなる。このアルゴリズムは、不確実性を考慮しつつも、報酬の最大化を目指す。具体的な手順は以下のようになる。

1. 1. 初期化: 各行動の報酬分布のパラメータを適当な事前分布で初期化する。通常はベータ分布などが使用される。
   2. 報酬分布の更新: 過去の行動実行と報酬観測をもとに、各行動の報酬分布を更新する。例えば、成功回数と失敗回数をカウントして、ベータ分布のパラメータを更新することが一般的となる。
   3. サンプリング: 各行動の報酬分布からサンプリングを行い、サンプルされた報酬が最も高い行動を選択する。
   4. 行動実行と報酬観測: 選択された行動を実行し、得られた報酬を観測する。
   5. 報酬分布の再更新: 新しい報酬情報をもとに、報酬分布を再更新する。

これらの手順を繰り返すことで、より高い報酬が期待できる行動を確率的に探索・活用していくことができる。Thompson samplingは、UCB法と比較して、確率的な要素を持つため、探索と活用のバランスが自然に取られるとされている。UCB法においては、探索項の調整やεの設定が重要だったが、Thompson samplingではそれらのパラメータ調整が不要であり、また理論的にも良好な性能を持つことが知られている。

Thompson samplingはベイズ的なアプローチを用いるため、不確実性を考慮して探索を行うことができ、実世界の問題に対して有効な手法とされている。ただし、報酬分布の事前分布や更新の方法などによって性能が変わることもあるため、具体的な問題に応じて適切な設計が必要となる。

Contextual bandit問題の実装手順

Contextual bandit問題の実装手順は、次のようになる。

1. データの収集: Contextual banditを解決するためには、コンテキスト、選択肢、報酬のデータを収集する必要がある。例えば、広告配信の場合、ユーザーの属性や行動、広告のバリエーション、ユーザーの反応などのデータを収集する。
2. モデルの設計: Contextual banditの解決には、選択肢(アーム)ごとに報酬の予測値を計算するモデルが必要となる。一般的には、機械学習アルゴリズム（例えば、線形モデルやニューラルネットワーク）を使用して、コンテキストと報酬の関係をモデル化する。
3. アルゴリズムの実装: 選択肢を決定するアルゴリズムを実装する。これには例えば、ε-greedy法やUCB法、Thompson samplingなどを選択することができ、各アルゴリズムは、モデルから得られた報酬の予測値を使用して、最適な選択を行う。
4. 学習と更新: アルゴリズムを実行する際には、収集したデータを使用してモデルを学習し、報酬の予測値を更新する必要がある。新しいコンテキストが与えられた場合には、モデルを使用して最適な選択を行い、報酬の予測値を更新する。
5. 評価と改善: 実装されたContextual banditシステムを評価し、パフォーマンスを測定する。報酬の最大化や他の評価指標に基づいて、アルゴリズムやモデルの改善を行い、新たなデータの収集やモデルの調整が必要な場合は、サイクルを繰り返して改善を続ける。

このように、Contextual bandit問題の実装手順は、データ収集、モデルの設計、アルゴリズムの実装、学習と更新、評価と改善というステップで構成される。

ε-greedy法を用いたContextual bandit問題のpythonによる実装例

以下に、Pythonを使用したContextual bandit問題の簡単な実装例を示す。この例では、ε-greedy法を使用した最適な選択について述べている。

import numpy as np

class ContextualBandit:
    def __init__(self, num_arms, num_features):
        self.num_arms = num_arms
        self.num_features = num_features
        self.true_rewards = np.random.randn(num_arms, num_features)
    
    def get_reward(self, arm, context):
        true_reward = np.dot(self.true_rewards[arm], context)
        noisy_reward = np.random.normal(true_reward, 1.0)
        return noisy_reward

class EpsilonGreedy:
    def __init__(self, num_arms, epsilon):
        self.num_arms = num_arms
        self.epsilon = epsilon
        self.arm_counts = np.zeros(num_arms)
        self.arm_rewards = np.zeros(num_arms)
    
    def select_arm(self):
        if np.random.random() < self.epsilon:
            # Exploration: Choose a random arm
            arm = np.random.randint(self.num_arms)
        else:
            # Exploitation: Choose the arm with the highest average reward
            arm = np.argmax(self.arm_rewards)
        return arm
    
    def update(self, arm, reward):
        self.arm_counts[arm] += 1
        self.arm_rewards[arm] += (reward - self.arm_rewards[arm]) / self.arm_counts[arm]

# パラメータの設定
num_arms = 5
num_features = 10
epsilon = 0.2
num_rounds = 1000

# Contextual banditの作成
bandit = ContextualBandit(num_arms, num_features)

# ε-greedy法の作成
agent = EpsilonGreedy(num_arms, epsilon)

# 実行ループ
for _ in range(num_rounds):
    # コンテキストの生成
    context = np.random.randn(num_features)
    
    # アームの選択
    chosen_arm = agent.select_arm()
    
    # 報酬の取得
    reward = bandit.get_reward(chosen_arm, context)
    
    # アームの報酬の更新
    agent.update(chosen_arm, reward)

この例では、ContextualBanditクラスがContextual banditを表し、EpsilonGreedyクラスがε-greedy法を実装している。ContextualBanditクラスでは、各アームの真の報酬をランダムに生成し、EpsilonGreedyクラスでは、アームの選択と報酬の更新を行っている。実行ループでは、指定した回数のラウンドを実行し、各ラウンドでコンテキストを生成し、アームの選択と報酬の取得・更新を行っている。

Upper Confidence Bound (UCB)法を用いたContextual bandit問題のpythonによる実装例

Contextual bandit問題では、環境（Context）に応じて行動の報酬が変化する場合に、最適な行動を見つけることが求められる。Upper Confidence Bound (UCB)法は、このような問題において効果的なアルゴリズムの一つとなる。以下に、PythonでContextual bandit問題をUCB法で解くための簡単な実装例を示す。

import numpy as np

class UCBContextualBandit:
    def __init__(self, num_actions, num_context_features):
        self.num_actions = num_actions
        self.num_context_features = num_context_features
        self.total_rewards = np.zeros(num_actions)
        self.num_actions_selected = np.zeros(num_actions)
        self.context_action_values = np.zeros((num_actions, num_context_features))

    def select_action(self, context_features):
        # UCB値の計算
        ucb_values = self.context_action_values.dot(context_features) + np.sqrt(2 * np.log(sum(self.num_actions_selected) + 1) / (self.num_actions_selected + 1e-6))

        # UCB値が最大の行動を選択
        action = np.argmax(ucb_values)

        return action

    def update(self, context_features, action, reward):
        # 選択した行動の試行回数を更新
        self.num_actions_selected[action] += 1

        # 選択した行動の報酬を更新
        self.total_rewards[action] += reward

        # 行動価値の更新
        self.context_action_values[action] = self.total_rewards[action] / self.num_actions_selected[action]

def simulate_contextual_bandit(context_features_matrix, true_action_rewards, num_actions, num_context_features, num_rounds):
    bandit = UCBContextualBandit(num_actions, num_context_features)

    for t in range(num_rounds):
        context_features = context_features_matrix[t]
        optimal_action = np.argmax(true_action_rewards[t])

        # 行動を選択
        selected_action = bandit.select_action(context_features)

        # 実際の報酬を取得
        reward = true_action_rewards[t][selected_action]

        # 行動価値の更新
        bandit.update(context_features, selected_action, reward)

        print(f"Round {t+1}: Selected Action = {selected_action}, Optimal Action = {optimal_action}, Reward = {reward}")

# テスト用のデータ生成
np.random.seed(42)
num_rounds = 1000
num_actions = 5
num_context_features = 10
context_features_matrix = np.random.rand(num_rounds, num_context_features)
true_action_rewards = np.random.rand(num_rounds, num_actions)

# シミュレーション実行
simulate_contextual_bandit(context_features_matrix, true_action_rewards, num_actions, num_context_features, num_rounds)

この実装例では、UCBContextualBanditクラスにUCB法に必要な処理を実装し、simulate_contextual_bandit関数でテストデータを用いてUCB法を実行している。注意すべき点として、コンテキストの特徴量や報酬の真の値がランダムに生成されているため、実際の問題に応じて適切なデータを用意する必要があり、また、UCB法のパフォーマンスはパラメータや設計に依存するため、実際の問題に適したパラメータの調整や他のアルゴリズムとの比較が必要となる。

Thompson samplingを用いたContextual bandit問題のpythonによる実装例

Thompson samplingを用いたContextual bandit問題のPythonによる実装例を以下に示す。

import numpy as np

class ThompsonSamplingContextualBandit:
    def __init__(self, num_actions, num_context_features):
        self.num_actions = num_actions
        self.num_context_features = num_context_features
        self.context_action_successes = np.ones((num_actions, num_context_features))
        self.context_action_failures = np.ones((num_actions, num_context_features))

    def select_action(self, context_features):
        # 各行動の報酬分布をベータ分布でモデル化
        sampled_rewards = np.zeros(self.num_actions)
        for action in range(self.num_actions):
            sampled_rewards[action] = np.random.beta(self.context_action_successes[action].dot(context_features),
                                                     self.context_action_failures[action].dot(context_features))
        
        # サンプリングされた報酬が最大の行動を選択
        action = np.argmax(sampled_rewards)

        return action

    def update(self, context_features, action, reward):
        # 選択した行動の報酬を更新
        if reward == 1:
            self.context_action_successes[action] += context_features
        else:
            self.context_action_failures[action] += context_features

def simulate_contextual_bandit(context_features_matrix, true_action_rewards, num_actions, num_context_features, num_rounds):
    bandit = ThompsonSamplingContextualBandit(num_actions, num_context_features)

    for t in range(num_rounds):
        context_features = context_features_matrix[t]
        optimal_action = np.argmax(true_action_rewards[t])

        # 行動を選択
        selected_action = bandit.select_action(context_features)

        # 実際の報酬を取得
        reward = true_action_rewards[t][selected_action]

        # 行動価値の更新
        bandit.update(context_features, selected_action, reward)

        print(f"Round {t+1}: Selected Action = {selected_action}, Optimal Action = {optimal_action}, Reward = {reward}")

# テスト用のデータ生成
np.random.seed(42)
num_rounds = 1000
num_actions = 5
num_context_features = 10
context_features_matrix = np.random.rand(num_rounds, num_context_features)
true_action_rewards = np.random.randint(0, 2, size=(num_rounds, num_actions))

# シミュレーション実行
simulate_contextual_bandit(context_features_matrix, true_action_rewards, num_actions, num_context_features, num_rounds)

この実装例では、ThompsonSamplingContextualBanditクラスにThompson samplingに必要な処理を実装し、simulate_contextual_bandit関数でテストデータを用いてThompson samplingを実行している。報酬をベータ分布でモデル化し、報酬をサンプリングして最適な行動を選択し、実際の問題に応じて、コンテキストの特徴量や報酬の分布を適切にモデル化することが重要となる。また、Thompson samplingの性能はパラメータや設計に依存するため、実際の問題に適したパラメータの調整や他のアルゴリズムとの比較が必要となる。

参考情報と参考図書

バンディット問題に対する詳細は”バンディット問題の理論とアルゴリズム“に述べている。そちらも参照のこと。

ウェブ上の情報としては”Netflixも使っている！Contextual Banditアルゴリズムを徹底解説“、”Contextual Bandit LinUCB LinTS“、”バンディットアルゴリズムを用いた推薦システムの構成について“、”Contextual Bandit を用いた賃貸物件検索システム“等がある。

参考図書としては”バンディット問題の理論とアルゴリズム“

“Bandit problems: Sequential Allocation of Experiments“.

“Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems“

“Conservation Laws, Extended Polymatroids and Multi-armed Bandit Problems: A Unified Approach to Indexable Systems“