Q学習と動的計画法
1. 序章
このチュートリアルでは、動的計画法とQ学習の違いについて説明します。 どちらも、特定の環境に基づいてモデルを作成するアルゴリズムのクラスです。 これらはポリシーを作成するために使用され、どのアクションが最適な結果をもたらすかを決定します。
2. 動的計画法
動的計画法アルゴリズムを使用するには、環境を記述するための有限マルコフ決定過程(MDP)が必要です。したがって、アクションの確率を知る必要があります。 結果は決定論的です。たとえば、動的計画法アルゴリズムを使用して取得するポリシーは常に同じです。 もう1つの利点は、常に収束することです。
これは、マルコフ決定過程と動的計画法がどのように機能するかについてのかなり抽象的な説明なので、例から始めましょう。
2.1. 動的計画法の例
マルコフ決定過程の簡単な例は、赤ちゃんの状態を説明することです。 私たちが見ることができるように、赤ちゃんは眠るか、落ち着くか、泣くか、幸せになることができます。 眠っている状態と落ち着いた状態から、歌うか待つかの2つのアクションから選択することができます。
すべての確率が与えられていることがわかります。 アクションを選択すると、どの確率でどの状態に着地するかが正確にわかります。たとえば、待つことは、幸福をもたらす可能性が非常に低く、泣く可能性も低くなります。
それとは反対に歌っています。 それは幸福の可能性が高くなりますが、赤ちゃんが泣くリスクも高くなります。 動的計画法で達成したい結果は、どの決定が最高の報酬をもたらすかを知ることです。 これは、子供が幸せになる可能性が高いことの組み合わせを意味します。 しかし、子供が泣き始める可能性も低いです。
私たちの最終的な方針は、どの州でどの行動を取るべきかを教えてくれます。 これを数学的な意味で見るために、値関数を見てみましょう。
値関数は、ポリシーに従った状態から開始して、期待収益を記述します。
2.2. 動的計画法で例を解く
MDPを解決するために、どの状態でどのアクションを実行する必要があるかを示すポリシーを取得する必要があります。 動的計画法には、さまざまなアルゴリズムが含まれています。 MDPを解決するために値反復アルゴリズムを選択します。 値の反復は、値関数を受け取り、開始値をプラグインして、それを繰り返し最適化します。
この時点で、動的計画法の重要な特性を確認できます。問題をより小さな部分に分割し、それらを個別に解決します。 つまり、MDPに最適なソリューションを見つけるには、まず落ち着いた状態から幸せな状態へ、次に睡眠から幸せな状態へと最適なポリシーを見つけます。 次に、ソリューションを組み合わせて主な問題を解決できます。
2.3. 動的計画法のユースケース
漁業の文脈では、収穫される魚の数を最大化しながら、個体数のサイズを維持するという課題に直面しています。 このため、私たちの一連の行動は、私たちが釣りをする鮭の数で構成されており、私たちの州はさまざまな釣りの季節です。 鮭の個体数がどのように減少および増加するかを知っているので、これを特にうまくモデル化できます。
別のユースケースは、オンラインマーケティングの分野に存在します。 10万人のメーリングリストと、直接オファー、製品プレゼンテーション、定期的なニュースレターなどの広告オプションのリストがあると想像します。 ここで、顧客を無関心な州から購入して満足している顧客に導くものを見つけたいと思います。 私たちはたくさんのデータを持っており、顧客があなたのウェブサイトにアクセスしたり何かを購入したりするタイミングを知っているので、マルコフ決定問題を簡単に作成できます。
動的計画法のもう1つの利点は、決定論的に機能するため、同じ環境で常に同じ結果が得られることです。したがって、非常に規制されているため、金融業界で非常に人気があります。
3. Q学習
動的計画法とは異なり、Q学習はマルコフ決定過程を期待していません。どのアクションがより高い報酬を返すかを評価することによってのみ機能します。これは、私たちが期待していないため、大きな利点として際立っています。常に環境の完全なモデルがあり、モデルが特定の方向に収束することは必ずしも確実ではありません。
3.1. Q学習の例
この考えをより明確にするために、幸せな赤ちゃんの同じ例を見てみましょう。 今回は、各アクションの確率はありません。 どのアクションがどの状態になるかさえわかりません。
このモデルの方が現実的かもしれません。 多くの実際のケースでは、アクションの結果の確率がありません。
3.2. Q学習で例を解く
Qラーニングの原則は、将来の報酬を受け取り、それらの報酬の一部を直前のステップに追加することです。 したがって、報酬への「パス」を作成します。このパスでは、期待される報酬が高いアクションのみを選択します。 しかし、どのようにしてそれらの期待される報酬を保存し、正しい道を選ぶのでしょうか?
この目的のために、Q-Tableを利用します。 Qテーブルでは、アクションと状態に関して期待されるすべての報酬を保存します。 ただし、最初に、ランダムな値で初期化します。 これをさらに視覚化するために、例のQテーブルを見てみましょう。
泣いたり幸せになったりすることで期待される報酬は確かにわかっているので、ランダムに初期化する必要はありません。 次に、テーブルを評価します。 最初の状態で歌うことが最も価値が高いので、歌うことを選択します。
歌うことは私たちをランダムに泣いている状態に導きます。 したがって、睡眠の期待報酬を77から60に下げます。 この期待される報酬を計算する式は次のとおりです。
現在の状態を説明します
私たちが取っている行動を説明します
学習率を説明します
割引係数
次の州から期待される報酬
この式は、新しい期待される報酬が、古いものと、学習率や割引係数などのさまざまなパラメーターと組み合わされた新しい値の組み合わせの構成である方法を示しています。 学習率は、新しい値が古い値をどの程度オーバーライドするかを示します。 割引係数は、遠く離れた報酬が現在の状態にどの程度影響するかを示します。
泣いている状態は終了状態です。 そのため、環境をリセットし、最初の睡眠状態から再開します。 さて、もちろん、待つことの期待される報酬71は、歌う60よりも高いので、待つことを選択します。
この学習プロセスは、一定数のエピソードで継続されます。 エピソードの数は、環境のコンテキストによって異なります。 私たちの例は非常に小さいので、200話でも十分です。 山岳車環境など、その他のより一般的な例では、25000回以上の学習エピソードが必要です。
この方法を適用した後、各プロセスでどの決定を行うかを示すqテーブルを取得します。
眠っている状態で待つことを選択し、穏やかな状態で歌うことを選択すると、最高の報酬が得られることがわかります。
3.3. フローチャート
この学習プロセスを視覚化するために、次のフローチャートを見てみましょう。
まず、Qテーブルをランダムな数字で初期化します。 次に、最初の学習エピソードを開始し、前述のように、Q-Functionを使用して期待される報酬を評価します。
学習フェーズがまだ終了していない限り、終了状態になるとすぐに、次の学習エピソードを開始します。 学習フェーズがすでに終了している場合は、Qテーブルから最適な決定ポリシーを取得します。 これを行うには、各行で最も高い値を持つセルを選択します。
3.4. Q学習のユースケース
多くのユースケースでは、アクションと状態が与えられた場合に特定の状態に変化する確率がないため、強化学習は動的計画法よりも優れた結果をもたらします。 さらに、マルコフ決定過程が非常に大きくなり、リソースまたは時間の問題が発生する可能性があります。
後者は、Qラーニングがゲームで人工知能を作成するための優れたツールである理由です。 最大の例は、GoogleによるAlphaGoとOpenAIのOpenAIGiveです。 彼らは両方とも、これまでアルゴリズムが達成できなかった世界をリードするチャンピオンを打ち負かすことができました。
別のアプリケーションはロボット工学に見られます。強化学習により、ロボットは歩き方を学ぶことができます。 このプロセスの物理学は非常に複雑であるため、ここでもマルコフ決定プロセスの確率はありません。
4. アプローチの比較
動的計画法は、その環境のすでに与えられたモデルに基づいて最適なポリシーを作成します。それとは反対にQ学習があります。 環境との対話によって受け取る報酬のみに基づいてポリシーを作成します。
したがって、Q学習アルゴリズムが機能するためには、モデル内のどのパラメーターを最適化するかを知る必要があるだけです。 DPアルゴリズムが機能するには、環境をより深く理解する必要があります。 どちらのモデルでも、一連の状態、アクション、および報酬が必要です。
5. 他の機械学習およびデータサイエンスアルゴリズムとの比較
動的計画法とQ学習は、どちらも強化学習アルゴリズムです。 したがって、それらは与えられた環境で報酬を最大化するために開発されています。 これとは対照的に、SVMやNeuralNetworks などの従来の機械学習方法では、特定のデータセットがあり、それらに基づいて結論が導き出されます。 ただし、 Deep Q-Learning の例では、両方の組み合わせが可能です。
深いQ学習では、Q-Tableがすぐに非常に大きくなる可能性があるため、Q-Tableをニューラルネットワークと交換します。時間または位置を含む状態空間を想像してみてください。 これにより、アルゴリズムが決定論的ではなくなります。
6. 結論
この記事では、動的計画法とQ学習の違いについて説明しました。
どちらも、環境のさまざまなモデルを使用して、意思決定のためのポリシーを作成します。 一方では、動的計画法が決定論的であることがわかりました。 それは私たちに最適な解決策を与えてくれます。
そのため、その強度は、基礎となるマルコフ決定過程の強度に依存します。 一方、強化学習は、その環境と相互作用し、期待される報酬が高いアクションを選択することによって機能します。