1. 序章

一部の機械学習アプリケーションでは、問題を解決するための一連の手順を定義することに関心があります。 いくつかの障害物と壁がある迷路の出口を見つけようとするロボットの例を考えてみましょう。

私たちのモデルの焦点は、ロボットを迷路の外の望ましい状態にする初期状態からの一連のアクション全体をどのように分類するかということです。

機械学習では、このタイプの問題は通常、マルコフ決定過程を利用してアーキテクチャの一部をモデル化する強化学習（RL）サブフィールドによって対処されます。 RLの課題の1つは、タスクを解決するための最適なポリシーを見つけることです。

このチュートリアルでは、マルコフモデルの基本に焦点を当て、この最適なソリューションを見つけるために値の反復と呼ばれるアルゴリズムを使用することが理にかなっている理由を最後に説明します。

2. マルコフモデル

サンプル間に存在する依存関係をモデル化するために、マルコフモデルを使用します。 この場合、モデルの入力は、パラメトリックランダムプロセスによって生成される一連のアクションになります。

この記事では、表記法は、可能な状態を持つシステムが一度に状態になると見なします。 したがって、等式は、その時点で、システムが状態になることを示します。

下付き文字は時間と呼ばれることを強調する必要がありますが、それはスペースなどの他の次元である可能性があります。

しかし、システム内のすべての可能な状態間の関係をどのようにまとめることができますか？ 答えは、マルコフモデリング戦略を適用することです。

2.1. 理論的基礎

その時点の状態にある場合、前の状態に依存する特定の確率または計算された確率でその時点の状態に進むことができます。

(1)  

モデルを少し単純にするために、直前のすべての状態ではなく、直前の状態のみが次の状態に影響を与えると考えることができます。 現在の状態のみが将来の状態の定義に関連し、1次マルコフモデルがあります：

(2)  

モデルをもう少し単純化するために、時間依存性を削除し、状態から遷移確率を使用して状態に移行することを定義します。

(3)  

これらの概念を理解するための最も簡単な方法の1つは、4つの遷移によって接続された2つの状態を持つマルコフモデルを視覚化することです。

変数は、状態で開始する確率を表します。 モデルから時間依存性を削除したため、いつでも、状態からへの遷移確率は、の値に関係なく等しくなります。

さらに、特定の状態の遷移確率は、次の1つの条件を満たす必要があります。

(4)  

この場合、すべての可能な初期状態の合計は次のようになるはずなので、同等の条件があります。

(5)  

最後に、すべての状態がわかっている場合、出力は初期状態から最終状態までの状態のシーケンスになり、このシーケンス観測シーケンスと呼びます。 シーケンスの確率は次のように計算できます。

(6)  

ここで、は初期確率の合計を表し、遷移確率のベクトルです。 状態で開始する確率を表します。 Whileは、からの到達状態の確率を表します。

このすべての理論を説明するために、遷移確率の定義された値を考慮してみましょう。

観測シーケンスを検討します。 このシーケンスの確率は次のように計算できます。

(7)  

定義された値を置き換えた後：

(8)  

2.2. 隠れマルコフモデル

前の例では、すべての状態がわかっていたため、それらを監視可能と呼びます。 状態が観測できない場合、隠れマルコフモデル（HMM）があります。

状態の確率を定義するには、最初にこの状態にアクセスしてから、観測の確率を書き留める必要があります。 私たちは、実際のデータを正しく使用してソースをシミュレートするモデルを作成する、優れたHMMモデルを検討します。

このタイプのモデルでは、ある状態での観測と、ある状態から別の状態への移動という2つのランダム性の原因があることを覚えておくことが重要です。

通常、HMMには2つの主な問題があります。

  1. モデルを考慮して、確率を計算することに関心があります。これは、任意の観測シーケンスの確率を意味します。
  2. 観測シーケンスを生成する可能性が高い状態シーケンスを見つける

3. 強化学習

この記事の冒頭で述べたように、機械学習のいくつかの問題には、解決策として、数値やラベルではなく一連のアクションが必要です。

強化学習では、環境内のアクションを選択するための意思決定を担当する機関があります。

3.1. 例

どの状態でも、エージェントはアクションを実行し、環境は報酬またはペナルティを返します。 一連のアクションはポリシーと呼ばれ、RL問題の主な目標は、総報酬を最大化するための最適なポリシーを見つけることです。

迷路の出口を見つけようとするロボットの最初の例に戻ると、ロボットは学習者エージェントになり、環境は迷路になります。

この点から、この問題の解決策は一連のアクションであるため、マルコフモデルとの類似性を示すことができます。

エージェント自体が一連のアクションを生成することを考慮して、マルコフ決定過程を使用してエージェントをモデル化します。 現実の世界では、アプリケーションに応じて、観察可能な状態、非表示の状態、または部分的に観察された状態を持つことができます。

3.2. 数学モデル

この説明では、エージェントが特定の離散時間の状態にあると見なします。 変数は、すべての可能な状態を表します。 使用可能なアクションはとして表され、アクションが実行されてからエージェントがに移行した後、報酬が計算されます。

前に定義したように、次の状態と報酬は現在の状態とアクションにのみ依存するため、ここに1次マルコフモデルがあります。

これからは、ポリシーが状態からアクションへのマッピングを定義することを検討します。 したがって、ある状態にある場合、ポリシーは実行するアクションを示します。

と呼ばれるポリシーの値は、から始まるポリシーのすべての報酬が合計された後の期待値です。 数学モデルに入れると：

(9)  

上記の式は、実行するステップ数が定義されている場合にのみ機能することを強調する必要があります。 この値がない場合は、割引率によって将来の報酬にペナルティを課す無限の範囲のモデルがあります。

(10)  

私たちの主な目標は、累積報酬を最大値に導く最適なポリシーを見つけることです。

(11)  

状態とアクションのペアを使用して、アクションを実行した場合の影響を示すこともできます。 の使用は、状態にあることのパフォーマンスを単に示すために残します。

状態の値が可能な限り最良のアクションの値に等しいという知識から始めます。

(12)  

(13)  

これは、確率で移動することを考慮した場合の予想累積報酬を表します。

状態とアクションのペア表記を使用すると、次のようになります。

(14)  

4. 価値の反復

最後に、特定のシナリオに最適なポリシーを見つけるために、以前に定義された値関数と、モデルの収束を保証するアルゴリズムである値反復と呼ばれるアルゴリズムを使用できます。

アルゴリズムは反復的であり、2つの連続する反復間の最大差がしきい値未満になるまで、実行を継続します。

次に、環境をシミュレートする値反復アルゴリズムの簡単な例を示します。

完全なマップはグリッドですが、簡単にするために、値がゼロに初期化された中央に報酬があるグリッドで構成される迷路の小さな部分を検討します。

私たちのロボットは、上、下、左、右の4つのアクションしか実行できません。ロボットが壁にぶつかると、次のペナルティが発生します。

確率モデルをシミュレートしているため、アクションに関連する確率があります。 この場合、ロボットが実際に定義された方向に進む可能性と、他の3つの動作オプションの可能性があります。

したがって、エージェントが上に行くことを決定した場合、上に行く確率は70 % cで、右または左に下がる確率は10% cです。 ロボットは、移行中ではなく、アクションが完了したときにのみ報酬を受け取ります。

最初の反復では、各セルは即座に報酬を受け取ります。 セルの最適値が壁にぶつかる確率で下がっているので、即時報酬をとして計算でき、マップは次のようになります。

次のステップでは、割引レートを使用します。 2回目の反復では、最初にセルを検討し、最適なアクションを実行することの値を計算します。これは左に移動します。

状態の値は、報酬と次の値の合計にすべてのアクションの確率を掛けたものになります。

(15)  

同様に、セルに対して、最適なアクションは右に進むことであり、他のすべての方向はゼロの期待される報酬を与えることを観察します。したがって、状態値は単純に次のようになります。

(16)  

すべてのセルを計算すると、マップは次のようになります。

2回の反復のみを実行しましたが、アルゴリズムは、しきい値の目的の反復回数に達するまで続行されます。

5. 結論

この記事では、動的計画法アルゴリズムを実装して、RL問題の最適なポリシー、つまり値の反復戦略を見つける方法について説明しました。

このタイプのモデルで報酬を最大化するタスクは実際のアプリケーションの中核であるため、これは対処すべき非常に関連性の高いトピックです。 このアルゴリズムは最適な値を見つけて収束することが保証されているため、ソリューションを実装する際に考慮する必要があります。