Multi-Armed Bandits: タスクに最適な強化学習ソリューション

Multi-Armed Bandits (MAB) は強化学習の世界の基礎を形成し、探索と活用の間の最適な均衡を必要とするシナリオを交渉するための強力なメカニズムを提供します。探索は新しいオプションを試すことを指しますが、活用は現在の最良のオプションに固執することを意味します。このような状況では、インテリジェントな学習メカニズムにより、MAB が優れた選択肢であることが証明されることがよくあります。

まず、MAB の背後にある概念を理解しましょう。それぞれが「片腕の盗賊」として知られる、多数のスロット マシンに囲まれたギャンブラーを想像してください。ここで行う重要な決定には、どのマシンでプレイするか、プレイの順序、およびプレイの頻度を決定することが含まれます。問題は、各マシンが提供する報酬が異なり、不確実であることです。最終的な目標は、一連のプレイ全体で最高の累積報酬を蓄積することです。

多腕盗賊とは何ですか？

「多腕バンディット」という名前は、スロット マシンの列に並ぶギャンブラー (「片腕バンディット」として知られる) に関する思考実験に由来しています。ギャンブラーは、総報酬を最大化することを目的として、どのマシンをプレイするか、各マシンを何回、どの順序でプレイするかを決定する必要があります。

より正式な定義では、MAB 問題はタプル (A, R) です。

MAB 問題の目標は、指定されたラウンド数にわたって予想される総報酬Qを最大化するポリシーπ (履歴データからアクションへのマッピング) を見つけることです。

MAB における重要なジレンマは、「探索」と「悪用」の間のトレードオフです。

1. 探索には、さまざまな武器を試して、それらがもたらす可能性のある報酬について詳しく知ることが含まれます。これには次善のアームを使用する必要があるかもしれませんが、システムに関する情報を収集するのに役立ちます。
2. 悪用には、エージェントがこれまでに収集した情報に基づいて、期待される報酬が最も高いと現時点で信じている腕を引っ張る行為が含まれます。

探索と活用のバランスを取ることは、強化学習と MAB の問題における中心的な課題です。

この問題に対処するために、Epsilon-Greedy、Upper Confidence Bound (UCB)、Thompson Sampling 戦略などの多数のアルゴリズムが開発されています。

MAB の拡張機能としての Contextual Bandits の詳細なレビューについては、次の記事で説明します。

イプシロン(ε)-貪欲

Epsilon(ε)-Greedy 戦略は単純な原則に準拠しています。ほとんどの場合、(1 - ε) として定量化され、最も高い推定報酬をもたらすアクションを選択し、それによって最もよく知られているオプションを活用します。ただし、ε として定量化される残りの時間はランダムなアクションを選択し、新しい可能性を模索します。この戦略の創意工夫は、探索フェーズ中に最も報酬の少ないアクションを同じ確率で選択する可能性があり、ε の値が探索と活用のバランスを決定するという注意点にもかかわらず、そのシンプルさと有効性にあります。

数学的には次のように定義できます。

これは次の疑似コードで定義できます。

 Initialize Q(a) for all a Repeat: Generate a random number p between 0 and 1 If p < epsilon: Select a random action a Else: Select action a with the highest Q(a) Execute action a and observe reward r Update Q(a) = Q(a) + alpha * (r - Q(a))

Epsilon-Greedy 戦略の Python 実装は非常に簡単です。

 import numpy as np class EpsilonGreedy: def __init__(self, epsilon, counts, values): self.epsilon = epsilon self.counts = counts self.values = values def select_arm(self): if np.random.random() < self.epsilon: return np.random.choice(len(self.values)) 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] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

ε-greedy アルゴリズムには、単純さと、多くのステップを経た後でも (少しは) 探索を続けることが保証されるという利点があります。ただし、UCB やトンプソン サンプリングとは異なり、探索するときに各アクションについてどれだけのことが知られているかは考慮されません。

UCB

逆に、UCB 戦略では、アクションを決定する際に、推定報酬と、それに関連する不確実性または差異の両方が考慮されます。不確実性の高い行動を好み、不確実性を軽減し、より生産的な探査段階を確保しようとします。 UCB 戦略は数学的に次のように定義されます。

その Python 実装は次のとおりです。

 class UCB: def __init__(self, counts, values): self.counts = counts self.values = values def select_arm(self): n_arms = len(self.counts) for arm in range(n_arms): if self.counts[arm] == 0: return arm ucb_values = [0.0 for arm in range(n_arms)] total_counts = sum(self.counts) for arm in range(n_arms): bonus = sqrt((2 * log(total_counts)) / float(self.counts[arm])) ucb_values[arm] = self.values[arm] + bonus return np.argmax(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) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

UCB における探査と活用のバランスは、その公式によって決まります。つまり、アクションの推定値に期間を加えたもので、時間の経過とともに (アクションについての学習が進むにつれて) 減少しますが、そのアクションに関する不確実性が増すにつれて増加します。したがって、アルゴリズムは、不確実性が高く、潜在的な報酬が高いアームを探索する傾向があります。

トンプソンサンプリング

トンプソン サンプリングは、マルチアーム バンディット問題のためのベイジアンにヒントを得たアルゴリズムです。各バンディット (または各アクション) の報酬確率に事前分布を割り当て、報酬が観察されるとこれらの事前分布を更新します。アクションの選択は、最良のアクションの事後分布に従って確率的に行われます。

ベータ ベルヌーイ フレームワークでは、各バンディットの報酬分布をベルヌーイ分布 (つまり、2 値の報酬 0 または 1) として考慮します。次に、報酬を獲得する確率の前にベータを割り当てます。ベータ分布はベルヌーイ分布の事前共役であり、事後更新が容易になります。

論理：

1. 各バンディットに、パラメータ α=1、β=1 (均一事前分布) を持つベータ分布を割り当てます。

2. 各ラウンドについて:

   1. 各バンディットの現在のベータ分布から乱数をサンプリングします。
   2. サンプリングされた数値が最も高いバンディットを選択し、そのバンディットを引き出します。
   3. 引いた山賊からの報酬を観察してください。成功(1)の場合、盗賊のαを1増やす。失敗(0)の場合、盗賊のβを1増やす。
   4. 手順 2 と 3 を繰り返します。

 import numpy as np from scipy.stats import beta class Bandit: def __init__(self, true_probability): self.true_probability = true_probability self.alpha = 1 self.beta = 1 def pull(self): return np.random.random() < self.true_probability def sample(self): return np.random.beta(self.alpha, self.beta) def update(self, reward): self.alpha += reward self.beta += (1 - reward) def Thompson(bandits, num_trials): rewards = np.zeros(num_trials) for i in range(num_trials): # Thompson sampling j = np.argmax([b.sample() for b in bandits]) # Pull the arm for the bandit with the largest sample reward = bandits[j].pull() # Update rewards log rewards[i] = reward # Update the distribution for the bandit whose arm we just pulled bandits[j].update(reward) return rewards # Suppose we have 3 bandits with these true probabilities true_probabilities = [0.2, 0.5, 0.75] bandits = [Bandit(p) for p in true_probabilities] # Run experiment rewards = Thompson(bandits, num_trials=10000) # Print the total reward print("Total reward earned:", rewards.sum()) print("Overall win rate:", rewards.sum() / len(rewards))

したがって、トンプソン サンプリングは、不確実なアクション (値の分布が分散しているもの) を「探索」し、高い価値があると思われるアクション (分布が高い値に偏っているもの) を「活用」します。

時間の経過とともに、各アクションについてより多くのことが学習されるにつれて、分布はよりピークになり、アルゴリズムによって選択されたアクションは、最も高い期待値を持つアクションに収束する傾向があります。

トンプソン サンプリングにおける探索と活用のバランスは、分布の形状から自然に得られます。この方法は非常に効果的ですが、特に大規模または連続的なアクション スペース、または複雑な報酬構造の問題の場合、UCB や ε-greedy よりも実装が複雑になる可能性があります。

マルチアームバンディットがあなたのタスクに最適な RL であるのはなぜですか?

1. シンプルさ: MAB アルゴリズムは、潜在的に大規模な状態アクション値テーブルまたは近似器の維持と更新を必要とする本格的な RL アルゴリズムよりもシンプルで計算効率が高くなります。
2. 探索と活用のバランス: MAB アルゴリズムは、新しいアクションを試すことと、既知の適切なアクションを継続することの間のトレードオフを管理するための堅牢な方法を提供します。
3. リアルタイムの適応性: MAB アルゴリズムは、アクションの報酬分布の変化にリアルタイムで適応できます。
4. 簡単な統合: MAB のシンプルさと効率性により、既存のシステムへの統合が容易になり、中断を最小限に抑えながら即座にメリットを得ることができます。
5. 幅広い適用性: MAB は、広告 (クリックスルー率を最大化するために表示する広告の選択)、ヘルスケア (治療戦略の個別化)、Web ページの最適化 (A/B テスト) など、さまざまな分野で成功裏に適用されています。

MAB のアプリケーション

Multi-Armed Bandits (MAB) は、さまざまな業界やドメインにわたって幅広い用途に使用できます。これらの使用方法の例をいくつか示します。

1. オンライン広告: MAB を使用すると、ユーザーのインタラクションに基づいて、ユーザーに表示する広告の選択を動的に調整できます。これは、時間の経過とともにクリックスルー率やコンバージョンを最大化するのに役立ちます。
2. 臨床試験: 医学研究では、MAB アルゴリズムを使用して患者を異なる治療法に動的に割り当てることができます。これにより、より多くの患者が最も効果的な治療を受けられるようになり、後悔、つまり必ずしも最善の治療を選択できるわけではないことで生じる損失が軽減されます。
3. ニュース記事のレコメンデーション: ニュース Web サイトは MAB を使用して、各ユーザーに表示される記事をパーソナライズできます。 MAB アルゴリズムは、各ユーザーがどのタイプの記事に興味があるかを時間の経過とともに学習し、それに応じて推奨事項を調整します。
4. 動的な価格設定: E コマース プラットフォームや航空会社は、MAB アルゴリズムを使用して価格設定戦略をリアルタイムで最適化し、顧客の行動や市場動向に基づいて収益を最大化できます。
5. ネットワーク ルーティング: コンピュータ ネットワークでは、MAB アルゴリズムを使用して輻輳を管理し、パケットのルーティングを最適化できます。各ルートはアームとして扱うことができ、アルゴリズムは動的にルートを選択してパケット損失や遅延を最小限に抑えることができます。
6. 機械学習のハイパーパラメーターの調整: MAB を使用して、機械学習モデルのハイパーパラメーターの選択を最適化することもできます。ハイパーパラメータの各セットはアームとして扱うことができ、アルゴリズムは選択を繰り返し調整して最適なモデル構成を見つけることができます。

本質的に、MAB の有用性は従来の強化学習タスクをはるかに超えています。これらは、不確実な環境における意思決定プロセスを強化し、さまざまな領域にわたる現実世界の問題に対する実用的な解決策を提供するための効果的なフレームワークを象徴しています。したがって、目前のタスクに探索と活用のバランスが含まれる場合、MAB が頼りになるオプションとして浮上し、意思決定の難題に対して多用途で堅牢かつ適応性のあるソリューションを提供することがよくあります。

結論

Multi-Armed Bandits は、探索と活用のバランスを効果的に調整できる能力を備えており、現実世界の意思決定に関する多くの問題に対して堅牢なソリューションを提供します。それらの固有の適応性と多用途性により、強化学習の領域だけでなく、ヘルスケアからオンライン広告までの幅広いアプリケーションにわたって貴重なツールとなっています。データ サイエンティストであっても、機械学習の愛好家であっても、意思決定プロセスの強化を目指す専門家であっても、MAB 戦略を理解して実装することは、豊かでやりがいのある経験となる可能性があります。