強化学習におけるコンテキストマルチアームバンディット問題

コンテキスト バンディットは、学習者が最大の報酬をもたらすアクションを選択する必要がある意思決定モデルで使用される強化学習アルゴリズムのクラスです。これらは、ギャンブルの古典的な「片腕盗賊」問題にちなんで名付けられました。この問題では、プレイヤーはどのスロット マシンをプレイするか、各マシンを何回プレイするか、どの順序でプレイするかを決定する必要があります。

コンテキストバンディットの特徴は、意思決定プロセスがコンテキストによって情報を与えられることです。この場合のコンテキストは、アクションの結果に影響を与える可能性がある一連の観察可能な変数を指します。この追加により、バンディットの問題は、個別の推奨事項、臨床試験、広告の掲載など、決定が特定の状況に依存する現実世界のアプリケーションに近づきます。

コンテキストバンディット問題の定式化

コンテキスト バンディット問題は、さまざまなアルゴリズムを使用して実装できます。以下に、コンテキスト バンディット問題のアルゴリズム構造の概要を示します。

ここでの次のアルゴリズムは、コンテキスト バンディット問題の基礎となる数学です。

上記をまとめると、一般的に言えば、アルゴリズムの目標は、一定の期間にわたる累積報酬を最大化することです。各ラウンドでは、選択したアクションに対する報酬のみが観察されることに注意してください。これは部分フィードバックとして知られており、バンディット問題と教師あり学習を区別します。

コンテキスト バンディット問題を解決するための最も一般的なアプローチには、探索と活用のバランスを取ることが含まれます。活用とは、現在の知識を使用して最善の決定を下すことを意味しますが、探索には、より多くの情報を収集するためにあまり確実ではないアクションを実行することが含まれます。

探索と活用の間のトレードオフは、LinUCB、Neural Bandit、Decision Tree Bandit など、コンテキスト バンディット問題を解決するために設計されたさまざまなアルゴリズムに現れています。これらのアルゴリズムはすべて、このトレードオフに対処するために独自の戦略を採用しています。

Bandit のこのアイデアのコード表現は次のとおりです。

 class Bandit: def __init__(self, n_actions, n_features): self.n_actions = n_actions self.n_features = n_features self.theta = np.random.randn(n_actions, n_features) def get_reward(self, action, x): return x @ self.theta[action] + np.random.normal() def get_optimal_reward(self, x): return np.max(x @ self.theta.T) # Usage example # Define the bandit environment n_actions = 10 n_features = 5 bandit = Bandit(n_actions, n_features) # Define the model agent model_agent = model(n_features, *args) # Define the context (features) x = np.random.randn(n_features) # The agent makes a prediction pred_rewards = np.array([model_agent.predict(x) for _ in range(n_actions)]) # The agent chooses an action action = np.argmax(pred_rewards) # The agent gets a reward reward = bandit.get_reward(action, x) # The agent updates its parameters model_agent.update(x, reward)

LinUCB アルゴリズム

LinUCB アルゴリズムは、コンテキストが与えられたアクションの期待される報酬を線形関数としてモデル化するコンテキスト バンディット アルゴリズムであり、上限信頼限界 (UCB) 原則に基づいてアクションを選択して探索と活用のバランスをとります。現在のモデル (線形モデル) に従って利用可能な最良のオプションを活用しますが、モデルの推定値の不確実性を考慮して、より高い報酬を提供できる可能性のあるオプションも探索します。数学的には次のように表すことができます。

このアプローチにより、アルゴリズムは不確実性の高いアクションを確実に探索します。

アクションを選択して報酬を受け取った後、LinUCB はパラメーターを次のように更新します。

Python でのコード実装は次のとおりです。

 import numpy as np class LinUCB: def __init__(self, n_actions, n_features, alpha=1.0): self.n_actions = n_actions self.n_features = n_features self.alpha = alpha # Initialize parameters self.A = np.array( [np.identity(n_features) for _ in range(n_actions)] ) # action covariance matrix self.b = np.array( [np.zeros(n_features) for _ in range(n_actions)] ) # action reward vector self.theta = np.array( [np.zeros(n_features) for _ in range(n_actions)] ) # action parameter vector def predict(self, context): context = np.array(context) # Convert list to ndarray context = context.reshape( -1, 1 ) # reshape the context to a single-column matrix p = np.zeros(self.n_actions) for a in range(self.n_actions): theta = np.dot( np.linalg.inv(self.A[a]), self.b[a] ) # theta_a = A_a^-1 * b_a theta = theta.reshape(-1, 1) # Explicitly reshape theta p[a] = np.dot(theta.T, context) + self.alpha * np.sqrt( np.dot(context.T, np.dot(np.linalg.inv(self.A[a]), context)) ) # p_t(a|x_t) = theta_a^T * x_t + alpha * sqrt(x_t^T * A_a^-1 * x_t) return p def update(self, action, context, reward): self.A[action] += np.outer(context, context) # A_a = A_a + x_t * x_t^T self.b[action] += reward * context # b_a = b_a + r_t * x_tx

デシジョン ツリー アルゴリズム

デシジョン ツリー バンディットは、報酬関数をデシジョン ツリーとしてモデル化します。各リーフ ノードはアクションに対応し、ルートからリーフ ノードまでの各パスはコンテキストに基づく決定ルールを表します。統計的フレームワークを通じて探索と活用を実行し、統計的有意性テストに基づいてデシジョン ツリーで分割とマージを行います。

目的は、期待される累積報酬を最大化する最適なデシジョン ツリーを学習することです。

決定木の学習には通常、次の 2 つのステップが含まれます。

1. ツリーの成長: 単一のノード (ルート) から開始して、期待される報酬を最大化する特徴としきい値に基づいて各ノードを再帰的に分割します。このプロセスは、最大深度またはリーフあたりのサンプル数の最小値に達するなど、何らかの停止条件が満たされるまで継続します。
2. ツリーの枝刈り: 完全に成長したツリーから開始して、期待される報酬が大幅に増加または減少しない場合、各ノードの子を再帰的にマージします。このプロセスは、それ以上マージを実行できなくなるまで継続されます。

分割基準と結合基準は通常、改善の統計的有意性を確認するための統計的テストに基づいて定義されます。

 from sklearn.tree import DecisionTreeRegressor class DecisionTreeBandit: def __init__(self, n_actions, n_features, max_depth=5): self.n_actions = n_actions self.n_features = n_features self.max_depth = max_depth # Initialize the decision tree model for each action self.models = [ DecisionTreeRegressor(max_depth=self.max_depth) for _ in range(n_actions) ] self.data = [[] for _ in range(n_actions)] def predict(self, context): return np.array( [self._predict_for_action(a, context) for a in range(self.n_actions)] ) def _predict_for_action(self, action, context): if not self.data[action]: return 0.0 X, y = zip(*self.data[action]) self.models[action].fit(np.array(X), np.array(y)) context_np = np.array(context).reshape( 1, -1 ) # convert list to NumPy array and reshape return self.models[action].predict(context_np)[0] def update(self, action, context, reward): self.data[action].append((context, reward))

DecisionTreeBandit の場合、 predictメソッドは現在のモデル パラメーターを使用して、コンテキストが与えられた各アクションの期待される報酬を予測します。 updateメソッドは、選択したアクションから観察された報酬に基づいてモデル パラメーターを更新します。この実装では、DecisionTreeBandit にscikit-learnを使用します。

ニューラルネットワークによるコンテキストバンディット

深層学習モデルを使用すると、高次元または非線形の場合の報酬関数を近似できます。このポリシーは通常、コンテキストと利用可能なアクションを入力として受け取り、各アクションが実行される確率を出力するニューラル ネットワークです。

一般的なディープ ラーニングのアプローチは、アクター - クリティカル アーキテクチャを使用することです。このアーキテクチャでは、一方のネットワーク (アクター) が実行するアクションを決定し、もう一方のネットワーク (クリティカル) がアクターによって実行されたアクションを評価します。

コンテキストと報酬の間の関係が線形ではない、より複雑なシナリオの場合は、ニューラル ネットワークを使用して報酬関数をモデル化できます。一般的な方法の 1 つは、REINFORCE や Actor-Critic などのポリシー勾配法を使用することです。

以下にまとめると、Neural Bandit はニューラル ネットワークを使用して、ニューラル ネットワークのパラメーターの不確実性を考慮して報酬関数をモデル化します。さらに、ポリシーの勾配による探索を導入し、より高い報酬の方向にポリシーを更新します。この形式の探索はより方向性があり、大規模なアクション スペースで有益です。

最も単純なコード実装は次のとおりです。

 import torch import torch.nn as nn import torch.optim as optim class NeuralNetwork(nn.Module): def __init__(self, n_features): super(NeuralNetwork, self).__init__() self.layer = nn.Sequential( nn.Linear(n_features, 32), nn.ReLU(), nn.Linear(32, 1) ) def forward(self, x): return self.layer(x) class NeuralBandit: def __init__(self, n_actions, n_features, learning_rate=0.01): self.n_actions = n_actions self.n_features = n_features self.learning_rate = learning_rate # Initialize the neural network model for each action self.models = [NeuralNetwork(n_features) for _ in range(n_actions)] self.optimizers = [ optim.Adam(model.parameters(), lr=self.learning_rate) for model in self.models ] self.criterion = nn.MSELoss() def predict(self, context): context_tensor = torch.tensor(context, dtype=torch.float32) # Convert to tensor with torch.no_grad(): return torch.cat( [model(context_tensor).reshape(1) for model in self.models] ) def update(self, action, context, reward): self.optimizers[action].zero_grad() context_tensor = torch.tensor(context, dtype=torch.float32) # Convert to tensor reward_tensor = torch.tensor(reward, dtype=torch.float32) # Convert to tensor pred_reward = self.models[action](context_tensor) loss = self.criterion(pred_reward, reward_tensor) loss.backward() self.optimizers[action].step()

predictの場合、現在のモデル パラメーターを使用して、コンテキストが与えられた各アクションの期待される報酬を予測し、選択されたアクションから観察された報酬に基づいてモデル パラメーターを更新する、predict メソッドとupdateメソッドを備えた同じ画像です。この実装では、NeuralBandit に PyTorch を使用します。

モデルの性能比較

各モデルには固有の長所と短所があり、モデルの選択は当面の問題の特定の要件によって異なります。これらのモデルのいくつかの詳細を詳しく調べてから、そのパフォーマンスを比較してみましょう。

リンUCB

線形上限信頼限界 (LinUCB) モデルは、線形回帰を使用して、コンテキストが与えられた各アクションに対して期待される報酬を推定します。また、これらの推定値の不確実性を追跡し、それを使用して調査を促進します。

利点:

• シンプルで計算効率が高いです。

• それは、後悔の限界に対する理論的な保証を提供します。

  
  

短所:

• 報酬関数はコンテキストとアクションの線形関数であると想定していますが、より複雑な問題には当てはまらない可能性があります。

デシジョンツリーバンディット

デシジョン ツリー バンディット モデルは、報酬関数をデシジョン ツリーとして表します。各リーフ ノードはアクションに対応し、ルートからリーフ ノードまでの各パスはコンテキストに基づく決定ルールを表します。

利点:

• 解釈可能な決定ルールを提供します。

• 複雑な報酬関数を処理できます。

  
  

短所:

• 特に大きなツリーの場合、過剰適合が発生する可能性があります。
• ツリーの最大深さなどのハイパーパラメータを調整する必要があります。

ニューラルバンディット

Neural Bandit モデルは、ニューラル ネットワークを使用して、コンテキストが与えられた各アクションに対して期待される報酬を推定します。ポリシー勾配手法を使用して探索を促進します。

利点:

• 複雑な非線形報酬関数を処理できます。

• 指示された探索を実行できるため、大規模なアクション スペースで有益です。

  
  

短所:

• ニューラルネットワークのアーキテクチャや学習率などのハイパーパラメータを調整する必要があります。
• 特に大規模なネットワークや大規模なアクション スペースの場合、計算コストが高くなる可能性があります。

コードの比較と一般的な実行例:

以下は、各モデルのシミュレーションを実行して、前に説明および定義したこれらすべてのモデルのバンディットのパフォーマンスを比較する Python コードです。

 import matplotlib.pyplot as plt # Define the bandit environment n_actions = 10 n_features = 5 bandit = Bandit(n_actions, n_features) # Define the agents linucb_agent = LinUCB(n_actions, n_features, alpha=0.1) neural_agent = NeuralBandit(n_actions, n_features, learning_rate=0.01) tree_agent = DecisionTreeBandit(n_actions, n_features, max_depth=5) # Run the simulation for each agent n_steps = 1000 agents = [linucb_agent, tree_agent, neural_agent] cumulative_rewards = {agent.__class__.__name__: np.zeros(n_steps) for agent in agents} cumulative_regrets = {agent.__class__.__name__: np.zeros(n_steps) for agent in agents} for agent in agents: print(agent) for t in range(n_steps): x = np.random.randn(n_features) pred_rewards = agent.predict([x]) action = np.argmax(pred_rewards) reward = bandit.get_reward(action, x) optimal_reward = bandit.get_optimal_reward(x) agent.update(action, x, reward) cumulative_rewards[agent.__class__.__name__][t] = ( reward if t == 0 else cumulative_rewards[agent.__class__.__name__][t - 1] + reward ) cumulative_regrets[agent.__class__.__name__][t] = ( optimal_reward - reward if t == 0 else cumulative_regrets[agent.__class__.__name__][t - 1] + optimal_reward - reward ) # Plot the results plt.figure(figsize=(12, 6)) plt.subplot(121) for agent_name, rewards in cumulative_rewards.items(): plt.plot(rewards, label=agent_name) plt.xlabel("Steps") plt.ylabel("Cumulative Rewards") plt.legend() plt.subplot(122) for agent_name, regrets in cumulative_regrets.items(): plt.plot(regrets, label=agent_name) plt.xlabel("Steps") plt.ylabel("Cumulative Regrets") plt.legend() plt.show() 

アプリケーションシナリオ

1. パーソナライズされた推奨事項: このシナリオでは、コンテキストはユーザー情報 (年齢、性別、過去の購入など) およびアイテム情報 (アイテム カテゴリ、価格など) です。アクションは推奨するアイテムであり、報酬はユーザーがアイテムをクリックしたか購入したかどうかです。コンテキスト バンディット アルゴリズムを使用して、クリックスルー率や収益を最大化するパーソナライズされた推奨ポリシーを学習できます。
2. 臨床試験: 臨床試験では、コンテキストは患者情報 (年齢、性別、病歴など) であり、アクションはさまざまな治療法であり、報酬は健康結果です。コンテキストバンディットアルゴリズムは、治療効果と副作用のバランスをとりながら、患者の健康成果を最大化する治療方針を学習できます。
3. オンライン広告: オンライン広告では、コンテキストはユーザー情報と広告情報、アクションは表示する広告、報酬はユーザーが広告をクリックしたかどうかです。コンテキスト バンディット アルゴリズムは、広告の関連性とユーザーの好みを考慮して、クリックスルー率や収益を最大化するポリシーを学習できます。

これらの各アプリケーションでは、探索と活用のバランスをとることが重要です。活用は現在の知識に基づいて最適なアクションを選択することですが、探索はより多くの知識を得るためにさまざまなアクションを試すことです。コンテキスト バンディット アルゴリズムは、この探索と活用のトレードオフを形式化して解決するためのフレームワークを提供します。

結論

コンテキストバンディットは、フィードバックが限られた環境での意思決定のための強力なツールです。意思決定においてコンテキストを活用できるため、従来のバンディット アルゴリズムよりも複雑で微妙な意思決定が可能になります。

パフォーマンスを明示的に比較しませんでしたが、アルゴリズムの選択は問題の特性に影響される必要があることに注意しました。単純な関係の場合は、LinUCB とデシジョン ツリーが優れている可能性がありますが、複雑なシナリオではニューラル ネットワークの方が優れている可能性があります。それぞれの手法には独自の強みがありました。LinUCB は数学的単純さ、デシジョン ツリーは解釈可能性、そしてニューラル ネットワークは複雑な関係を処理する能力を備えています。この刺激的な分野で効果的に問題を解決するには、適切なアプローチを選択することが重要です。

全体として、コンテキストベースのバンディット問題は強化学習の中でも魅力的な領域であり、それらに対処するために利用できる多様なアルゴリズムがあり、これらの強力なモデルのさらに革新的な使用法が期待できます。