
Gymで強化学習⑦グリッド・ワールド
前回の記事で強化学習の目的を「環境における最適なポリシー」を見つけること定義しました。ただし、数式が多く登場したので話が抽象的になりました。そこで今回は単純なグリッド・ワールドを使って具体例と共に数式を見て行きます。
グリッド・ワールドを使う最大の利点はその分かり易さにあります。すべて状態が観測可能であり個別な(連続ではない)値なので状態遷移などを例を使って考えやすくなります。
もし前回の記事でイメージが湧きにくいと感じた方は今回の記事を読まれるとより数式の意味が伝わるはずです。また、最後には最適なポリシーを探す一般的な考え方について解説します。
では、さっそく始めましょう。
グリッド・ワールド
グリッドとセル
グリッド(Grid)というと将棋やチェスの盤面のように直交する行と列をイメージします。つまり、2次元に配列されたセル(正方形のマス)です。

将棋やチェスの盤面上に駒を配置したものを状態とすると、その数は有限ですが駒の並びの組み合わせが膨大なので最適ポリシーを見つけるのが非常に困難なゲームになっています。よって例として扱うには向いていません。
もっと小さなグリッド・ワールドで単純なゲームを想定しても良いのですが、ここではさらに単純な1次元のグリッド・ワールドを考えます。そうすることで数式との対比が簡単になるからです。
状態
下のように、5つのセルそれぞれに番号がついており、これを状態の値として使います。よって初期状態は2です。ゴールは状態4に到達することですが、エージェントはゴールの場所を知りません。

つまり、エージェントはあちこち動き回って報酬(あるいはペナルティ)を得ながら生涯報酬を最大化する行動パターン、つまりこの環境における最適なポリシーを見つける必要があります。
なお、一般に状態は複数の値を含みベクトルになりますが、この環境では状態は一つの値しかないのでスカラー(一つの数値)として表現しています。
行動
行動としては3つあります。以下のどれかを選ぶことができます。
「左」左のセルに移動
「止」停止(同じセルに居続ける)
「右」右のセルに移動

行動を決めると必ずそのように動きます。つまり、確率的な要素はありません。例えば、「左」を選ぶと必ず左へ動きます。もちろんグリッドの外には移動できませんが、以下に述べる終了の条件によりそれを考える必要もありません。
報酬
各状態には報酬が一意に決められているとします。つまり、確率的ではないので状態によって報酬の値が確定します。

なお、報酬の合計が-2になると負けとなりゲーム終了です。このためエピソードは常に有限のステップ数で終わります。そのため報酬の割引率は考えなくとも報酬の合計が無限に膨らむことはありません。割引率が1であると考えても同じです。つまり、現在得る報酬と将来得る報酬の価値に差がないとみなしています。
最適なポリシー
以上をまとめると、この環境は以下のようになっています。

これを見ると右に2回移動するのが最適ポリシーだとわかります。しかし、エージェントはこのようにゴールと報酬が決まっているとは知りません。
では、最適なポリシーを発見するにはどうすれば良いのでしょうか。
ここからは、この環境において幾つかのポリシーを使って考察していきます。
何もしないエージェント
ポリシーの定義
ポリシーは現在の状態から次の行動を決めるもので、ポリシーはと表記しました。ある状態における行動の確率を返します。
ここでは、まず何もしないで停止したままのエージェントのポリシーを評価します。
この何もしないポリシーをと呼びましょう。このポリシーに従うエージェントが初期状態2でエピソードを開始します。もちろん、行動は常に「止」なので状態は変わりません。

よって、何もしないポリシーを次のように確率で表現できます。
このポリシーの数式は上図と同じことを確率で表現しただけです。つまり、状態2において「止」を選ぶ確率は100%で、「左」か「右」を選ぶ確率は0%です。
状態遷移
次に何もしないポリシーの状態遷移を考えます。ポリシーに従うエージェントの状態遷移は現在の状態からある状態へ遷移する確率を返します。
ここでは可能な行動の集合です。
また、はポリシーに依存しない状態遷移の確率で、エージェントが状態において行動を選択したという条件でへ遷移する確率を表します。
ポリシーに依存しない状態遷移の確率とポリシーが行動を選ぶ確率と掛け合わせたのがであり、状態においてポリシーがある行動を選んで状態に遷移する確率が計算できます。
このをすべての可能な行動に対して計算して足し合わせれば、ポリシーに従うエージェントが状態から状態へ遷移する確率が計算できます。
前置きが長くなりましたが、何もしないポリシーでは行動として「止」のみを選ぶので、状態遷移の確率は次のように単純化されます。
なお、この環境ではエージェントがある行動を決めると必ずそのように動くとしています。よって、何もしないポリシーによって初期状態2から次の状態へ遷移する確率は次のように確定します。
これを図にすると以下になります。

ものすごく当たり前のことを周りくどく言っているようですが、一般的な数式に具体例を当てはめると上の図と同じことが確率として表現できるということに注目してください。確率は最適化に必要なのでここを理解することが大切です。
まとめると何もしないポリシーによる状態遷移では状態2から状態2への遷移が100%になります。
報酬の期待値
次に報酬を考えます。報酬は次のように定義しました。
これはある状態における報酬の期待値を意味します。
何もしないエージェントは状態2に居続けて報酬-1を受けるだけです。
報酬は状態によって一意に決まるとしているので期待値と実際に受け取る報酬の値が同じになっています。
マルコフ決定過程
以上を踏まえて実際に何が起こるのかを示したのが下図です。

状態遷移も報酬もすべて決定的であり、マルコフ決定過程も上記の以外の可能性はありません。
報酬の総和
強化学習では報酬の総和を割引率(ガンマ)を使って次のように表現します。
この環境では割引率(、ガンマ)は1を想定しました。また、ステップ2より後のステップは存在しません(エピソードが終了してしまうから)。
よって、何もしないポリシーによるステップ1()から将来にわたって得られる報酬は次のようになります。
一つのマフコフ決定過程しかないので、上記以外の報酬を受け取る可能性はありません。
状態価値関数
状態価値はあるポリシーによるある状態からの生涯報酬の期待値です。次のように定義しました。
何もしないポリシーを使うと初期状態での状態価値は次のように表現できます。
何もしないポリシーに従うエージェントのマルコフ決定過程には一つのパターンしかありません。よってもの可能性しかありません。つまり、期待値である価値関数の値と実際に起こりえる報酬の総和とが一致しています。
つまりこのポリシーに従うと絶対に成功しないわけです。
ランダムに行動するエージェント
ポリシーの定義
同様の思考実験をランダムに行動するエージェントで試しましょう。
このエージェントのポリシーは常に行動をランダムに選択するので、と呼びましょう。初期状態2での行動は次の確率で決まります。
つまり、「左」、「止」、「右」とすべて同じ確率で選択されます。

また、初期状態からの状態遷移の確率も同様に決まります。
次からは初期状態2における行動の選択による価値、つまり行動価値の変化を見ていきます。
左へ移動
仮に「左」が選ばれたとすると、状態は1に遷移します。ここで受け取る報酬は-1となります。

さらに、状態1での行動の確率は以下になります。
再び同確率で次の行動が3つのうちの一つに決まります。また、状態遷移の確率も同様に決まります。
よって、状態として可能なのは0、1、2のどれかです。つまり、次の状態が何であれ受け取る報酬は-1しかありません。そして報酬の合計が-2となりエピソードが終了します。
これまでの状況を図にまとめると以下になります。

左の行動価値
「左」を選んだことによる行動価値を計算しましょう。
あるポリシーに従うエージェントが状態において行動を取ることで期待される価値は以下になります。
行動価値関数の意味は、状態で行動を選択することで得られるその時点からの生涯報酬の期待値です。
では、ランダムに行動するポリシーが初期状態2で「左」を選択した時の行動価値を計算します。この場合、ステップ1からの生涯報酬はステップ2での行動に関わらずしかあり得ないので期待値も同様になります。
まとめると、初期状態2から左へ移動すると生涯報酬の期待値が-2となります。また、実際に起こり得るマルコフ行動過程はどれも生涯報酬が-2です。
よって、初期状態2から左へ移動すると絶対に成功しません。
移動しない
では初期状態2から「止」が選ばれたとします。

状態は初期状態と変わらず2ですが、報酬として-1を受け取ります。
また、状態遷移の確率も変わらないので、次の状態として可能なのは1、2、3のどれかです。よって次の状態から受け取る報酬は-1です。そして報酬の合計が-2となりエピソードが終了します。

初期状態2で「止」を選択するとステップ1からの生涯報酬の期待値は以下になります。
また、実際に起こり得るマルコフ行動過程はどれも生涯報酬が-2です
よって、初期状態2で「止」を選ぶと絶対に成功しません。
右へ移動
最後の希望は右への移動に託されました。
初期状態で「右」を選択すると、状態は3に遷移します。

状態3での行動の確率は以下になります。常にランダムですね。
状態遷移の確率は次になります。
状態3から「左」や「止」が選択されるとステップ1からの生涯報酬が-2となりゲーム終了です。しかし、状態3で「右」が選択されると状態4となりゴールします。

つまり、ランダムなポリシーが状態3にいると3分の1の確率でゴールします。そこでの報酬は100です。以上から、状態3での行動価値は次のようになります。
右の行動価値
上述の状態3からの行動価値はステップ2から期待される生涯報酬です。ステップ1からの行動価値を計算するにはベルマン方程式を利用して以下の式を使います。
ベルマン方程式は現在の状態から将来に渡って受ける報酬の総和を、現在受ける報酬と将来にわたって受ける報酬とに分けて計算できるのが特徴です。
これまでの情報ですべて必要な数値は出揃っているので、ポリシーが初期状態2で右を選択した行動価値を計算できます。
ステップ1で右へ移動し状態3になった報酬は
割引率は1
ステップ2での各行動に対する行動価値は上記の通り
以上を踏まえて初期状態2で「右」を選択した行動価値を計算します。
となり最初に右へ移動することの価値が他の選択よりも遥かに高いことがわかります。もちろんそうなるように報酬の構造を決めているのですが、それをエージェントが見つける手掛かりがランダムな行動によって手に入りました。
しかし、ランダムなポリシーでは常に成功するとは限りません。
ランダム・ポリシーの評価
実際、ランダム・ポリシーはどの程度見込みのあるポリシーなのでしょうか。ランダム・ポリシーの行動過程をすべて図にまとめると以下になります。

単純な1次元グリッドでもこうして見ると複雑に見え、どのようにポリシーを評価すると良いのか、難しそうです。
実はポリシーの評価は初期状態における状態価値を計算するとわかります。これはベルマン方程式で状態価値を計算する際にポリシーの影響を含めたものです。
また、状態における状態価値は、その状態におけるすべての行動価値の期待値を計算することで求められます。
数式ばかりだと抽象的なので、ランダムなポリシーに当てはめて状態価値を計算しましょう。つまり、初期状態2からランダムなポリシーを採用した場合における状態価値を計算します。
状態価値はすべての行動価値をもとに計算した期待値なので、すでに計算した以下の値を利用することができます。
ステップ1で行動「左」を選択した行動価値
ステップ1で行動「止」を選択した行動価値
ステップ1で行動「右」を選択した行動価値
上記の行動価値がそれぞれ3分の1で生じるので、ランダム・ポリシーによる初期状態2からの状態価値は以下になります。
これに対して、最適なポリシーは右に2回進むことで99ポイント獲得できます。よってランダム・ポリシーはあまり良いポリシーとは言えません。
最適なポリシーを目指して
今回は前回数式ばかりだったので1次元のグリッド・ワールドを通して状態価値や行動価値やマルコフ方程式などを復習しました。
何もしないポリシーのようにまったく探索(Exploration)をしないポリシーでは最適な行動を完全に見逃す可能性があることもわかりました。
ランダム・ポリシーのように探索をするとグリッド・ワールドのような状態が有限である場合はすべての状態を訪れることが出来ます。今回は状態遷移や報酬に関してはランダム性がないので簡単な思考実験が行えました。
もし、状態遷移や報酬にランダム性があると、右に行こうとしても失敗して同じ状態に留まったり、報酬の値も状態から一意に決まらなかったりするので、何度も実際の環境で探索を繰り返して状態価値や行動価値を実験からの値で計算する必要があります。
いずれにせよ、ランダムな行動が環境から学習する上で重要なことが見えてきました。今回の環境ではランダムな行動から得た行動価値関数に従って価値を最大にする行動を選べば最適なポリシーになります。つまり、探索から得た知識をもとに搾取(Exploitation)することができればそれが最適なポリシーになるわけです。
問題はどのようにして探索と搾取のバランスをとるのかということです。代表的な強化学習の手法としてSARSAとQ学習があります。両方とも(イプシロン)-greedy法を使って探索と搾取のバランスを管理します。
それについては次回に解説します。
(続く)