REINFORCE js

グリッドワールド: 動的プログラミング法デモ

セルの報酬変更:(セルを1つ選択)

### セットアップこのページは強化学習の文献では「おもちゃモデル」としてしばしば使用される **グリッドワールド** というおもちゃの仮想環境です。ここでは以下のような仮定が置かれます: - **状態空間** グリッドワールドには 10x10=100 の状態があります。開始状態は左上のセルです。灰色のセルは壁です。壁を突き抜けて移動することはできません。 - **行為** エージェントは最大 4 つの行為を選択することができます。上例ではエージェントは最大 4 つの行為から一つの行為を選択して移動することができます。 - **環境ダイナミクス** グリッドワールドは決定論的です各状態と行動が与えられるごとに，同じ新しい状態になります。 - **報酬** エージェントは中央のマス（R 1.0を示すマス）にいるときに +1 の報酬を受け取ります。いくつかの状態では -1 の報酬を受け取ります（R -1.0 と表示）。報酬が +1.0 の状態がゴール状態です。ゴールするとエージェントをスタート状態に戻してリセットします。この例は決定論的有限マルコフ決定過程 (MDP) です。エージェントの目標は常に将来の割引された報酬を最大化するエージェントの方策 (矢印で示されている)を見つけることです。私のお気に入りの部分は価値反復を収束させ、セルの報酬を変更して、方策が調整されるのを見ることです。 **インターフェース** セルの色（最初はすべて白）は現在の方策でその状態の価値（割引報酬）の現在の推定値を示しています。任意のセルを選択して **セルの報酬変更** スライダーを使って報酬を変更することができます。 ### 動的プログラミング法 (Dynamic Programming) 興味のある方は **リチャード=スットン Richard Sutton** の強化学習の教科書（オンライン版は無料）の [第 4 章](http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node40.html) を参考にしてください。簡潔に言うとエージェントはその方策(policy) $\pi(a \mid s)$ に基づいて環境と対話します。方策とは状態 $s$ から行為 $a$ を導く関数です。ある行為が行われた後えージェーンとは環境から報酬 $r$ を受取ります。それゆえエージェントと環境との相互作用は $s\_t, a\_t, r\_t, s\_{t+1}, a\_{t+1}, r\_{t+1}, s\_{t+2} \dots$ ここで $t$ (時刻) を指標とした形になります。動的プログラミング (DP) のアプローチでは方策 $\pi^*$ とは「価値関数」 $\pi$ に従って，環境と相互作用し，状態 $s$ から始まって期待報酬の最適値時間を指標とした最大値を与え得る最適方略です。 $$ V^\pi(s) = E \left\{ r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \ldots \mid s_t = s \right\} $$ 期待値は 1. 確率的な方策と 2. 環境のダイナミクスの両方を超えていることに注意してください。定数 $\Gamma$ は早い方の報酬の方が重視される割引係数です。状態 $s$ で行動 $a$ を起こしたときに環境がどのように変化しそのときに得られる報酬がどのようなものになるのかということです。定数 ($\gamma$) は、後のものよりも先の報酬に重みを与える割引係数です。では、期待値を書き出してみましょう。状態を得るために期待値を書き出してみると，態を得るためにそうすると、次のようなことがわかります。 $$ \pi(s) = \sum\_{a} \pi(s,a) \sum\_{s'} \mathcal{P}_{ss'}^{a} \left[ \mathcal{R}_{ss'}^{a} + \gamma V^\pi(s') \right] $$ 上式 $\mathcal{P}_{ss'}^{a}, \mathcal{R}_{ss'}^{a}$ は特定の環境については定数です。次の状態 $s'$ は，状態 $s$ で行動 $a$ をとることで繰り返し与えられます。この方程式は **ベルマン方程式** と呼ばれ、与えられた方策の価値関数が満たすべき再帰的な関係を記述しています。目標は、すべての状態から最も多くの価値を得る最適な政策 \$\pi^\*(s,a))\$ を見つけることです。戦略は **方略反復 policy Iteration** スキームに従うことになります。初期方策から始めてその方策下でベルマン方程式を更新して各状態の価値関数を評価します。価値関数は現在の方策によって与えられ、環境のダイナミクスとエージェントの期待される行動とを通して効果的に後方に報酬を拡散させます。一旦すべての状態の値を推定したら、価値関数に関して貪欲に方策を更新します。その後各状態の値を再推定し最適な方策に収束するまで反復を繰り返しますこのプロセスは収束することを示すことができます。この 2 つのステップは，インタフェースのボタンで制御できます。 - **方策評価（1回のスィープ）** ボタンはベルマン方程式を同期更新に変え価値関数推定の 1 つのステップを実行します。直感的にはこの更新では 1. 環境のダイナミクスと 2. 現在のポリシーとを介して、各状態での生の報酬を他の近くの状態に拡散します。 - **方策更新** ボタンは、すべての状態を反復処理し、各状態で方策を更新します。最高の価値を持つ状態につながる行動を取るようにします。各行動のための環境の次の状態分布を積分します。 - **価値反復** ボタンは 2 つのボタンを交互に押すタイマーを開始します。特に価値反復は価値関数が完全に推定されるのを待たずにベルマン更新の単一の同期スイープのみが実行されることに注意してください。完全な方策反復では、方策が更新される前にバックアップのスイープ（収束まで）が何度も行われます。 ### コードの概要 **ポリシー評価** の目的は世界と現在の方策のダイナミクスを介して報酬を後方に拡散させることですべての状態の値を更新することです（これを **バックアップ**と呼びます）。コードは以下のようになっています。


evaluatePolicy: function() {
  // 価値関数の同期的更新の実行 
  var Vnew = zeros(this.ns); // initialize new value function array for each state
  for(var s=0;s < this.ns;s++) {
    var v = 0.0;
    var poss = this.env.allowedActions(s); // 可能な全行動について
    for(var i=0,n=poss.length;i < n;i++) {
      var a = poss[i];
      var prob = this.P[a*this.ns+s]; // 現時点での方策の元での行動確率 
      var ns = this.env.nextStateDistribution(s,a); // 次の状態をルックアップ
      var rs = this.env.reward(s,a,ns); // s->a->ns 遷移の報酬を取得 
      v += prob * (rs + this.gamma * this.V[ns]);
    }
    Vnew[s] = v;
  }
  this.V = Vnew; // swap
},

ここでは `this.ns` (状態の数)、現在のポリシーを格納する `this.P`、環境オブジェクトへのポインタ `this.env` があります。この実装では方策の配列は一次元です。ですが、任意の状態で何かの行動を起こす確率を格納しています。このコードは各状態に対する同期的な値のバックアップを実装しています。 \begin{align} V^\pi(s) & = E_\pi \left\{ r_t + \\gamma r_{t+1} + \gamma^2 r_{t+2} + \ldots \mid s_t = s \right\} \\ & = E_\pi \left\{ r_t + \gamma V^\pi(s_{t+1}) \mid s_t = s \left\} \\ & = \sum_a \pi(s,a) \sum_{s'} \mathcal{P}_{ss'}^a \left[ \mathcal{R}_{ss'}^a + \gamma V(s') \right] \end{align} このコードでは方策行動に対する期待値（上の第一の和）のみを取っています。ですがこのグリッドワールドは決定論的であるため、上の第二の和は評価されていないことに注意です。すなわち、コード中の `ns` は次の状態を示す単一の整数です。したがって全確率量は単一の次の状態にあり、期待値は不要です。価値関数が再推定されると **方策更新 (policy update)** を実行して、各状態での推定値に対して方策を貪欲にすることができます。これは非常に簡単なプロセスです。以下のコードは少し拡張しています。これは、アクション間の結びつきを慎重に処理し、すべての勝利アクションに均等にポリシーの確率を配分しているからです。


updatePolicy: function() {
  // 学習した各関数について貪欲に方策を更新する 
  // すべての状態について繰り返し... 
  for(var s=0;s < this.ns;s++) {
    var poss = this.env.allowedActions(s);
    // 可能な行動をとったときの価値を計算 
    var vmax, nmax;
    var vs = [];
    for(var i=0,n=poss.length;i < n;i++) {
      var a = poss[i];
      // 行動 a をとったときの価値 を計算 
      var ns = this.env.nextStateDistribution(s,a);
      var rs = this.env.reward(s,a,ns);
      var v = rs + this.gamma * this.V[ns];
      // ブックキーピング: 最大値を保存 
      vs.push(v);
      if(i === 0 || v > vmax) { vmax = v; nmax = 1; }
      else if(v === vmax) { nmax += 1; }
    }
    // すべての行動に渡って方策を更新 
    for(var i=0,n=poss.length;i < n;i++) {
      var a = poss[i];
      this.P[a*this.ns+s] = (vs[i] === vmax) ? 1.0/nmax : 0.0;
    }
  }
},

ここでは、各状態 $Q(s,a)$ での行動価値関数を計算しています。 Q とは，ある行動 $a$ をとることで，どの程度期待報酬が得られるかを表す関数です。 Q 関数は以下のようになります: \begin{align} Q^\pi (s,a) &= E_\pi \left\{ r_t + \gamma V^\pi(s_{t+1}) \mid s_t = s, a_t = a \left\} \\ &= \sum_{s'} \mathcal{P}_{ss'}^a \left[\mathcal{R}_{ss'}^a + \gamma V^\pi(s') \right] \end{align} グリッドワールドではすべての状態をループして最大 4 つの行為のそれぞれについて Q関数を評価します。各状態で最大値を与える行動を実行するように方策を更新します。以下のようになります: $$ \pi'(s) = \arg\max_a Q(s,a) $$ このような更新を何度も何度も行うことで、最適な政策に収束することが保証されています。（リチャード・サットンの本を参照）。このグリッドワールドの例では、エージェントが報酬+1 を得る終末状態へと完璧に導く矢印に対応しています。 ### REINFORCE js API の動的プログラミングの使用マルコフ決定過程 MDP に REINFORCEjs ダイナミックプログラミングを使いたい場合 DP エージェントが必要とするいくつかのメソッドを持つ環境オブジェクト `env` を定義しなければなりません。 - 環境オブジェクト `env.getNumStates()` は状態の総数を整数で返します。 - `env.getMaxNumActions()` は、任意の状態におけるアクションの最大数を表す整数を返します。 - これは 0 から `maxNumActions` までの整数でなければなりません。 - これは誤記です。今のところライブラリは決定論的な MDP を想定しているので (状態、アクションの)ペアごとに一意の新しい状態を持つことになっています。したがってこの関数は世界の次の状態を識別する単一の整数を返すべきです。 - これはエージェントが `s`, `a`, `ns` の遷移に対して達成した報酬を浮動小数点 float で返します．最も単純な場合では，報酬は通常，状態 `s` のみに基づいています．このデモのソースコードの `GridWorld` 環境を参照してください。エージェントの作成と訓練の例は次のようになります。


// 環境の生成 
env = new Gridworld(); 
// エージェントの生成，割引率は 0.9 
agent = new RL.DPAgent(env, {'gamma':0.9}); 

// 収束するまで，この関数を呼び出す 
agent.learn();

// 一度実行した場合のエージェントの行動 
var action = agent.act(); // 選択された行動のインデックスを返す

### 長所と短所 (Pros and Cons) 実際には，強化学習の問題を解決するために動的プログラミングを使用している人をほとんど見かけません。理由はいくつも挙げられます。おそらく以下の 2 理由が大きいと思われます。 - どうすれば，連続的な行動(動作) や状態に拡張できるのかが不明である - 動的計画法による更新を計算するためには、環境モデルへのアクセスが必要です。ですが実際にはほとんど利用できません。通常期待できる最善の方法としてはエージェントが環境と相互作用し，経験を重ねることで，この分布からサンプルを得ることである。このことの詳細は TD 法で! 長所は次のとおり: - 数学的に正確，表現可能，分析可能である - 問題が比較的小さい場合（数千の状態と数十/数百の行動くらい）動的プログラミング法は最も安定しています。また，最も安全でもあり，最も単純な収束保証もあります。このような場合には動的プログラミング法は最良の解決策かも知れません。

REINFORCE js

グリッドワールド: 動的プログラミング法 デモ

グリッドワールド: 動的プログラミング法デモ