Kアームドバンディット問題の解決
1. 序章
このチュートリアルでは、武装した盗賊と強化学習との関係について学びます。 次に、探査と搾取の用語を調べ、探査と搾取の用語を調査することで、それらのバランスを取る必要があることを理解します。 搾取のトレードオフ。
最後に、武装した盗賊の設定から最大の報酬を得るためのさまざまな戦略と、後悔を使用してさまざまなアルゴリズムを比較する方法を調査します。
2. 強化学習とKアームドバンディット
片腕バンディットは、スロットマシンの俗語です。 チャンスはわずかですが、片腕バンディットを回転させると勝つ可能性があることを私たちは知っています。 これは、十分な試行があれば、ある時点で勝つことを意味します。 確率分布がわからないだけで、限られた回数の試行でそれを見つけることはできません。
今、私たちがカジノにいて、10台の異なるスロットマシンの前に座っていると想像してみてください。 スロットマシンのそれぞれが勝つ可能性があります。 プレイするコインがある場合、どれを選びますか？ すべてのチャンスを1台のマシンで費やしますか、それとも異なるマシンの組み合わせでプレイしますか？
最高の報酬を獲得するための最適なプレイ戦略を見つけることは簡単な作業ではありません。
強化学習では、エージェントが環境と相互作用しています。 利用可能なアクションの結果を見つけようとしています。 その究極の目標は、最後に報酬を最大化することです。
多腕バンディット問題は強化学習設定の簡略化です。状態は1つだけです。 私たち（エージェント）はkスロットマシンの前に座っています。 アクションがあります：別個の腕の1つを引っ張る。 アクションの報酬値は、アクションを実行した直後に利用できます。
-武装した盗賊は、シンプルで強力な表現です。 それでも、以前に実行したアクションの結果を無視して、複雑な問題をモデル化することはできません。
実際の問題をより適切にモデル化するために、「コンテキスト」を導入します。エージェントは、コンテキストを指定してアクションを選択します。 つまり、エージェントには状態があり、アクションを実行すると、エージェントは状態間を移行し、報酬が得られます。 簡単に言えば、コンテキストは以前に実行されたアクションの結果です。
それでも、実際の問題とは異なり、コンテキストバンディットモデルでアクションを選択した直後に報酬が発生します。 時々、私たちはしばらくしてから、または一連の行動をとった後に報酬を受け取ります。 たとえば、三目並べのような単純なゲームでも、ゲームの終了時に一連の動きを行った後に報酬を受け取ります。 したがって、コンテキストバンディットは単純化されすぎて、いくつかの問題をモデル化できません。
3. 探索対。 搾取
武装した盗賊の設定では、エージェントは最初は環境に関する知識をまったく持っていないか、限られています。 その結果、試行錯誤しながら環境を発見します。
武装した盗賊の設定を考えてみましょう。 ここでは、確率分布に基づいて、各スロットマシンが即座に報酬を与えることがわかります。 報酬は、負または正の実数になります。 次の図は、=10の設定例を示しています。
各スロットマシンの報酬配分はこの設定で決定されますが、私たちはそれらについて知りません。 そこで、試行錯誤しながら発見していきます。
この未知の設定でランダムなアクションを選択するとします（探索）。 その結果、しばらくすると、各スロットマシンの報酬について最初のアイデアが得られます。 試行回数が少ないため、期待値に自信が持てません。 それでも、私たちはこの時点で環境について何かを知っています。
この設定例では、青い点は、スロットマシンから期待される報酬が何であるかをエージェントが信じていることを示しています。 水色のマークは実際の分布を示していますが、現時点ではまだエージェントにはわかりません。 一部のマシンでは、エージェントの期待値は平均に近いですが、一部のマシンでは、限られた調査の後、極端なものになります。
問題のサイズに応じて、十分な試行の後、エージェントはスロットマシンの期待される報酬値をより正確に見積もることができます。 探索の結果、エージェントの期待は実際の報酬と非常に一致します。
多くの状態とアクションを伴う現実的な強化学習の問題では、実際に環境を学習し、期待される報酬を正確に予測するには、無限の試行回数が必要です。 時々、環境は変化しているかもしれません（非定常）。 したがって、私たちがすでに学んだことに固執することは良い考えではありません。 エージェントが最適ではない選択で立ち往生する可能性があるため、リスクが高く、場合によっては危険ですらあります。
一方、常に環境を探索するということは、ランダムな行動を取ることだけを意味します。 良い報酬の機会を利用しないことは、単に最大の全体的な報酬を得るという全体的な目標に反します。
不完全な情報を含むこのような設定では、バランスを取る必要があります。 最良の長期戦略には、短期的なリスクを取ることが含まれる場合があります。 探索は、短期的な報酬を犠牲にしながら、長期的にはより高い報酬につながる可能性があります。 逆に、悪用することで、短期的には即時の報酬が保証され、長期的には不確実性が生じます。
武装した盗賊環境には不確実性が含まれています。 探検対。 情報が不完全なため、悪用のトレードオフが発生します。 環境についてすべてを知っていれば、最適な解決策を見つけることができます。 ただし、実際の問題には多くの未知数が含まれます。
4. Kアームドバンディットアクション選択戦略
武装した盗賊戦略を評価する1つの方法は、予想される後悔を測定することです。 名前が示すように、後悔の値は低いほど良いです。
各アクションで予想される後悔を測定します。 アクションが実行されると、可能な限り最高のアクションの期待される報酬の概算が得られます。 その上、私たちは取られた行動に対する報酬を即座に受け取ります。 期待される最高の報酬と実際の報酬の違いは、期待される後悔を与えます。 それは、最善の行動を取るのではなく、探索することによって私たちが失ったものを示しています。
後悔の値を累積的に加算し、結果を比較することで、特定の問題に関するさまざまな戦略を比較できます。
それでは、多腕バンディット問題の良い解決策を概算するためのいくつかの戦略を探りましょう。
4.1. 探索-最初
探索優先（またはイプシロン優先、優先）戦略は、探索と活用の2つのフェーズで構成されます。
名前が示すように、探索フェーズでは、エージェントはすべてのオプションを数回試行します。 次に、それらの試行に基づいて最適なアクションを選択します。 最後に、悪用フェーズでは、最良の結果をもたらすアクションを実行します。
このアルゴリズムの活用フェーズは、後悔を最小限に抑えるという点で完全に機能します。 ただし、非効率性は探索段階にあります。 全体的なパフォーマンスは、ほとんどのアプリケーションにとって満足のいくものではありません。
4.2. イプシロン-欲張り
イプシロングリーディ（-greedy）アプローチでは、純粋な探索フェーズではなく、時間の経過とともに探索を広げます。
最初に、小さなイプシロン値を選択します （通常、を選択します）。
イプシロン欲張りアルゴリズムは、理解と実装が簡単です。 これは、Q-learningによる基本的な強化学習の機能強化の1つです。
4.3. 崩壊したイプシロン-欲張り（イプシロン-減少戦略）
イプシロン欲張り戦略の欠点は、探索フェーズが時間の経過とともに均一に分散されることです。
アイデアは非常に簡単に実装できます。 減衰係数（通常は約0.95）を導入します。 各アクションの後、epsilonをepsilon*decayに更新します。 したがって、イプシロン値は時間の経過とともに徐々に減少します。 これにより、イプシロン欲張りアルゴリズムと比較して後悔が少なくなります。
4.4. Softmax （ボルツマン）
ソフトマックスアプローチにより、期待値に応じた確率でアクションを選択できます。 イプシロン欲張りアプローチは、探索中に均一なランダムアクションを選択することを忘れないでください。 したがって、次善のオプションと最悪のオプションが選択される確率は同じです。
softmax探索では、エージェントはほとんどの場合、依然として最良のアクションを選択します。 ただし、他のアクションはそれに応じてランク付けされ、選択されます。 結果として、イプシロン欲張りよりも優れた動作をします。 それでも、後悔には限界がありません。
4.5. 追跡方法
追跡方法は、現在の状態のアクション値の見積もりとアクションの優先度の両方を維持します。 彼らの好みは、現在の見積もりによれば、継続的に最良の（貪欲な）行動を「追求」します。
アクション設定の確率は、アクションを選択する前に更新されます。 最良の行動を選択する確率が高くなり、他の人の確率が低くなります。
4.6. 信頼限界の上限
信頼上限（UCB）は、探索と活用のバランスをとろうとするアルゴリズムのファミリーです。
最初に、各アクションがすべての状態に対して少なくとも1回実行されるようにします。 次に、再び選択に直面したときに、信頼限界の上限を最大化するアクションを選択します。
その全体的な後悔は対数的になり、限界があります。 したがって、理論的には、長期的には最高のパフォーマンスを発揮する戦略になります。
4.7. トンプソンサンプリング（ベイジアンバンディット）
これまでに説明したアルゴリズムは、以前の試行の平均を使用して、アクションごとに期待される報酬を更新します。 トンプソンサンプリングアルゴリズムは、異なるアプローチを採用しています。
各アクションがベータ確率分布に基づいて報酬を提供すると想定し、信頼区間内で分布の推定を試みます。 アクションの優先度の分布は、アクションの実行後に更新されます。 次に、アルゴリズムは、期待される報酬を最大化するアクションを選択します。
この意味で、トンプソンサンプリングアルゴリズムはベイズ推定アプローチを採用しており、より多くの証拠が利用可能になると設定が更新されます。
5. アクション選択戦略の遺憾な比較
次の図は、いくつかのアルゴリズムの最悪の場合の境界を比較しています。
ほとんどの設定では、イプシロングリーディは打ち負かされません。 UCBおよびThompsonSamplingメソッドは、探索をより効果的に使用します。 十分な試行回数があれば、トンプソンのサンプリングはより安定します。 ただし、UCBはノイズの多いデータに対してより耐性があり、より迅速に収束します。
6. 結論
このチュートリアルでは、武装した盗賊の設定と強化学習との関係について説明しました。 次に、探査と搾取について学びました。 最後に、多腕バンディット問題を解決するためのさまざまな近似手法と、後悔を使用してそれらを評価および比較する方法を調査しました。
