Gymで強化学習③状態とマルコフ性

今回は強化学習における状態とマルコフ性（Markov Property）について解説します。また、深層強化学習の定義についても触れます。

マルコフ性についての解説はよく見受けられますが、頭ごなしに「マルコフ性はこう言うものです」的な説明が多いように思われます。なぜマルコフ性が強化学習の前提として必要であり、また成立するのかよくわからないという壁があります。

マルコフ性の理解のためには観測値と状態を区別して理解する必要があります。

まず、前回の記事を思い起こして下さい。強化学習における基本的な枠組み（Framework）を解説しました。そこではエージェントが選んだ行動（Action）が環境（Environment）に影響を及ぼした結果として観測値（Observation）が更新され報酬（Reward）が与えられるという流れを話しました。

ただし、そこではエージェントが何を持って行動を決めるのかは詳しく触れませんでした。結論から言うと、エージェントは現在の状態（State）をもとに行動を決定します。しかし、状態は観測値と必ずしも一致しません。

さらに状態に対してマルコフ性を求めるのですが、ちょっと話が先走りました。まずは状態が観測値とどう異なるのかを解説します。

ただし、状態の定義をするにはヒストリーが必要です。

ヒストリーとは

状態とは行動を決めるのに必要な入力値です。ならば観測値と同じでも良さそうですが、同じとも限りません。具体例を見ていきましょう。

以下は、何度も登場した強化学習の枠組みです。この巡回的なフィードバック構造を展開して時間軸で見てみましょう。

まず、エージェントは、初期化された環境からの観測値を受けとります。ここからエージェントの最初のステップが始まります。

次にエージェントが行動を決めて環境に作用します。

環境は内部の状態を更新して、新たな観測値を報酬と共にエージェントに渡します。そしてエージェントのステップ２がはじまります。

この過程をステップ$${t}$$まで続けたのが以下の図です。

こうして見るとエージェントも環境も相互に影響し合いながら次に出力する値を決めているのがわかります。

このような観測値（$${o}$$）、行動（$${a}$$）、報酬（$${r}$$）の並びをヒストリー（歴史、History）と呼びます。エージェントから見たヒストリーを横並びのリストとして数式で書くと以下になります。

$$
H_t = o_0, \ a_1, o_1, r_1, \ a_2, o_2, r_2, \dots \ , a_{t-1}, o_{t-1}, r_{t-1}, \ a_t, o_t, r_t
$$

エージェントは、ヒストリーによって次に何が起こるのかを決めています。

しかし、次に何が起こるのかを決めるために、いちいちヒストリーをすべてチェックするのは不便です。ヒストリーが長くなるほど時間もかかるし複雑になります。

そこで状態（State）の概念が登場します。

観測値と状態の違い

エージェントの状態とはヒストリーからのデータをまとめたもので、次の行動を決めるために必要な情報です。また、環境の状態を考えることもできます。環境は自らの状態を参考にして、次に返す観測値と報酬を決めます。

つまり、エージェントにはエージェント内の状態があり、環境には環境内の状態があることになります。

しかし、環境の状態はエージェントからは直接にはわかりません。与えられるのは観測値と報酬のみです。よって、環境の状態がどのように維持されているのかは未知です。もしかしたら環境はヒストリーをそのまますべてどこかに格納しているかもしれないし、ヒストリーの一部を残しているだけかもしれません。あるいはヒストリーから計算した値だけを記憶している可能性もあります。

このような環境の状態から生成される観測値ですが、さらにノイズが追加されていることもあります。実際、現実の世界で画像やセンサーのデータを扱う場合には自然のノイズは多少なりとも存在します。よって強化学習環境でもノイズを導入することでエージェントをよりロバスト（頑健、Robust）にする効果が期待できます。

なお、完全に観測可能（Fully observable）な環境であってもエージェントは環境の状態を直接に与えられません。見えるのは観測値と報酬のみです。エージェントは自分が受け取ったヒストリーを駆使して自分が置かれている状態を計算し次の行動を決めます。

また、部分的に観測可能（Partially observable）ならば、状態を計算するのはさらに困難になります。

例えば、ババ抜きを想像してください。ババ抜きの目的はなるべく早く自分のカードをすべて捨てることになります。報酬として考えられるのは、「ペアになったカードを捨てる」や「ジョーカーを持っていたらそれを相手に取らせる」などになります。また、ペナルティとしては「ジョーカーを引いてしまう」や「ジョーカーを持っているけど相手に異なるカードを引かれる」などが考えられます。ただし、ここでは状態について話したいので報酬は本質ではありません。

ババ抜きでの環境は他のプレイヤー達です。自分が持っているカード、他のプレイヤーが捨てたカード、プレイヤーたちの顔の表情などは観測できます。しかし、たのプレイヤーたちが手の内に持っているカードは見えません。つまり、部分的に観測可能な環境です。

この環境で自分ができる限りのことを観測して次の行動を決めます。もっとも知りたいのは「ジョーカーを誰が持っているか」です。「妙にカードをシャッフルしているプレイヤー」とか「ジョーカーが引かれて嬉しそうな顔をした人」などをよく観察していると。だいたいどこにジョーカーがあるのか察しがつきます。

ジョーカーの位置がわかるといろいろと有利になりますし、それによって自分の行動も変化します。つまり、ジョーカーの位置が環境における重要な情報であり、自分の行動を決めるための状態の一部になります。

ちなみにジョーカーを持つと思われる相手からカードを引く際は相手の目線に注意すると良いそうです。なぜならジョーカーのある場所に視線が行きやすいからです。しかし、そのような行動は相手がジョーカーを持っていないと確信がある場合は不要になります。

また、カードを引く際にはその相手が直前に引いたカードをそのまま引くと自分のカードとペアになりやすいくなると言われています。これはそのカードが前の人のカードだけでなく、そのさらに前の人のカードともペアにならなかったからです。もちろん、そのカードがジョーカーでないと見極める必要があります。

なお、自分がジョーカーを持つ場合は、相手の利き手が取りやすい位置にジョーカーを置くことで、相手がジョーカーを引いてくれる確率が上がるそうです。

ちょっとウンチクが長くなりましたが、要するに重要な情報としてジョーカーの位置があげられます。よってジョーカーの位置の確率をヒストリーから予測して状態に含め、その状態から次の行動を決めるということを上手なプレイヤーは行っていると考えられます。

このように、状態（ジョーカーの位置）は観測値（捨て札など）から直接に得られる情報ではありません。よって、観測値と状態は必ずしも同じではありません。

ヒストリーと状態の関係

観測値と状態の違いとして、もう一つ例をあげます。何度か取り上げていますが、2013年にDeepMindの強化学習エージェントがアタリ（Atari）のゲームを人間並にプレイできることが論文によって発表されました。

これらのゲームは完全に観測可能な環境です。エージェントは観測値としてゲーム画面の画像データを受け取ります。しかし、一つ一つのゲーム画像は静止画であり、そこからはプレイヤーや敵の動きの情報は分かりません。よって、DeepMindの研究者たちは直近4つの画像をまとめたものをエージェントが行動を決めるための入力としました。つまり、ヒストリーの一部を状態の計算に利用しています。

以下の画像は、Atariのゲームからではありませんが、4つの画像が一つ一つの静止画以上の情報を与えることができる例です。

これによってどの物体がどんな速さで移動しているのかなど一つの観測値だけでは得られない情報が計算できます。このように直近のヒストリーを使って状態を計算するので、状態は観測値そのものとは異なっています。

よって、エージェントは次の行動を決めるためにヒストリーから現在の状態を計算するのですが、これを数式で表すと、エージェントにはある関数$${f}$$があって、ヒストリーから現在の状態を計算していることになります。

$$
s_t = f(H_t)
$$

もし、この関数が最後の観測値を返すだけであれば、観測値と状態は同じになります。しかし、一般には観測値と状態は異なる概念と取られるべきです。

まとめると、状態は現在の観測値ではなくヒストリーから計算されます。

深層強化学習とは

ヒストリーから計算される状態は様々な情報を含むので、報酬の値とは違い一つの値ではなく、ベクトルなどで表現される複数の値を持つのが一般的です。

ヒストリーから計算した状態は、ニューラルネットワークのモデルが受け取る入力データとネットワーク内の層が計算する隠れ状態（特徴量）との関係にもよく似ています。

とくに、深層強化学習（Deep Reinforcement Learning）では深層学習（ディープラーニング）のモデルを関数として使います。状態の計算や行動の選択などに利用されます。

 DeepMindのDQN（Deep Q-Network）のエージェントはゲーム画面の画像処理に畳み込み層を利用したことで成功を収めました。しかし、根底の理論としてはQ学習（Q-Learning）と呼ばれる従来の強化学習が用いられているわけです。そこではディープラーニングは複雑な関数をデータから学ぶ手段として使用されているのですが、強化学習の理論の本質ではありません。

ただし、ディープラーニングの導入によって人間の頭だけでは考えられなかったような関数をデータから学ぶことが出来たわけで、ディープラーニングの登場が重要であることは間違いありません。

DeepMindのDQNが登場したのは2013年ですが、使用している深層学習モデルは2012年にImageNetにおける画像分類のコンペで優勝したAlexNet（アレックス・ネット）を使用しています。つまり、ディープラーニングの進歩が強化学習の進化に直接的に寄与していることになります。

さて、強化学習の本質の理論へと話を戻しましょう。

エージェントは次の行動を決めるために状態を使います。そして状態とはヒストリーから必要な情報を集約したものです。よって、状態の計算が終われば、観測値やヒストリー自体は行動の選択には関わりがなくなります。要するに、次の行動を決めるためには現在の状態だけがあれば良いことになります。

このように状態は便利ですが、状態自体はヒストリーから計算するので、ヒストリーがどんどん長くなったら状態の計算がどんどん大変にならないでしょうか。

この問題を解決するのがマルコフ性です。

マルコフ性

エージェントの行動によって環境から次の観測値と報酬が返されるとヒストリーは$${H_t}$$から$${H_{t+1}}$$になります。

$$
\begin{align*}
H_{t   }  &= o_0, \ a_1, o_1, r_1, \dots \ , a_t, o_t, r_t \\
H_{t+1} &= o_0, \ a_1, o_1, r_1,\dots \ , a_t, o_t, r_t, \ a_{t+1}, o_{t+1}, r_{t+1}
\end{align*}
$$

ヒストリーが$${H_t}$$から$${H_{t+1}}$$に変わるので、状態も$${s_t}$$から$${s_{t+1}}$$へと遷移します。よってヒストリーの更新は状態の変化として表現できます。

$$
\begin{align*}
s_0 &\leftarrow H_0 \\
s_1 &\leftarrow H_1 \\
&\dots \\
s_t &\leftarrow H_t \\
s_{t+1} &\leftarrow H_{t+1} \\
\end{align*}
$$

状態一つ一つにその時点でのヒストリーからの情報が凝縮していると捉えるとイメージが湧きやすいと思います。よって、ある時点での状態$${s_t}$$にはその時点でのヒストリー$${H_t}$$が必要となります。

$$
\begin{align*}
s_t \leftarrow& \ H_t \\
=& \ o_0, \ a_1, o_1, r_1, \\
& \ \dots \ ,\\
& \ a_{t-1}, o_{t-1}, r_{t-1}, \\
& \ a_t, o_t, r_t
\end{align*}
$$

更新されたヒストリーから状態が計算されることを以下のように表現できます。

$$
\begin{align*}
s_{t+1} \leftarrow& \ H_{t+1} \\
=& \ o_0, \ a_1, o_1, r_1, \\
& \ \dots \ ,\\
& \ a_{t-1}, o_{t-1}, r_{t-1}, \\
& \ a_t, o_t, r_t, \\
& \ a_{t+1}, o_{t+1}, r_{t+1}
\end{align*}
$$

さらに更新されたヒストリーでは状態の計算がもっと長くなります。

$$
\begin{align*}
s_{t+2} \leftarrow& \ H_{t+2} \\
=& \ o_0, \ a_1, o_1, r_1, \\
& \ \dots \ , \\
& \ a_{t-1}, o_{t-1}, r_{t-1}, \\
& \ a_t, o_t, r_t, \\
& \ a_{t+1}, o_{t+1}, r_{t+1}, \\
& \ a_{t+2}, o_{t+2}, r_{t+2}
\end{align*}
$$

これではヒストリーがどんどん増えてキリがありません。

しかし、状態$${s_t}$$には、ヒストリー$${H_t}$$から情報が凝縮されているのであり、次の状態$${s_{t+1}}$$を計算するのに必要な情報がヒストリーからすべて含まれているとしたらどうでしょうか。

この場合、状態$${s_{t+1}}$$の計算はヒストリー全体を必要とせず、一歩手前の状態$${s_t}$$と新しい情報である行動$${a_{t+1}}$$、観測値$${o_{t+1}}$$、報酬$${r_{t+1}}$$をあわせて計算できることになります。

$$
s_{t+1} \leftarrow s_{t}, \ a_{t+1}, o_{t+1}, r_{t+1}
$$

$${s_{t+2}}$$は次のようになります。

$$
s_{t+2} \leftarrow s_{t+1}, \ a_{t+2}, o_{t+2}, r_{t+2}
$$

$${s_{t+3}}$$は次のようになります。

$$
s_{t+3} \leftarrow s_{t+2}, \ a_{t+3}, o_{t+3}, r_{t+3}
$$

よってヒストリーがいくら増えても計算量は変わりません。一歩手前の状態がわかっていればヒストリーは捨てても構いません。なぜなら、次の状態を計算するのに必要ないからです。

つまり、次の状態が現在の状態に依存することはあっても、それ以前の過去のいかなる状態にも依存しないことになります。これをマルコフ性（Markov Property）と呼びます。マルコフはロシア人数学者のアンドレイ・マルコフ（Andrey Markov）です。

例えば、DeepMindのDQNが直近4つのゲーム画面を状態として利用したのが良い例です。直近4つのゲーム画面があれば新しい状態の計算ができるのでヒストリー全体は必要としません。直前の状態から3つの画像を取り出して新しい観測値の画像を組み合わせれば新しい状態が計算できます。

また、株価の移動平均を状態として使うのも似た例です。現在の移動平均の計算に必要なデータと新しい株価があれば新しい移動平均が計算できます。

最も単純な例は観測値をそのまま状態として使う場合です。ヒストリーをまったく必要とせず、マルコフ性があります。

このようにマルコフ性のある状態を作り出すことは難しくはありません。そしてマルコフ性があることを前提とすることで強化学習の理論が構築しやすくなります。なぜならヒストリー全体を考慮する必要がなくなるからです。

ただし、マルコフ性について「強化学習における状態にはマルコフ性があります」的な説明になると、「なんで？」となってしまいます。しかし、ここまで読まれた方ならマルコフ性は不思議でもなんでもないはずです。

つまり、強化学習でマルコフ性が成り立つのは、そのように状態を設定するからです。そして強化学習がマルコフ性を前提とするのは理論が単純になり問題を解く際の計算量が減るからです。

マルコフ性が成り立つように設定した状態の計算方法はいろいろ考えられます。直近４画像にするのか10画像にするのか、最終的には強化学習がうまくいくことを実験的に証明することが必須となります。また、ニューラルネットワークを利用したりと工夫の余地が多々あります。

なお、Q学習など既存の強化学習の手法を利用したい場合には、状態として用いる値は必ずマルコフ性があるように設定する必要があります。これは自分で強化学習エージェントを構築する際に注意する点になります。

確率表記の意味

最後に確率を使ったマルコフ性の表現について触れます。と言うのも強化学習の記事や論文を読むと必ず出てくるので知っておいた方がいいからです。

まず、マルコフ性は以下のように確率を使って表現できます。

$$
P[s_{t+1}|s_t] = P[s_{t+1}|s_t, s_{t-1}, \dots, s_1, s_0]
$$

左辺の$${P[s_{t+1}|s_t]}$$は状態$${s_t}$$が与えられている時に次の状態が$${s_{t+1}}$$である確率という意味です。縦棒｜の後にくるのが確率を計算する際に与えられる条件となっています。

ここで$${s_{t+1}}$$は行動$${a_{t+1}}$$、観測値$${o_{t+1}}$$、報酬$${r_{t+1}}$$などによって変化します。ノイズなども考慮すると100％の確信を持って次の状態が一意の値になるとは言えないので確率の表現を使います。つまり、予測される状態にはなんらかの分布があるということです。

なお、状態の値が一意に決まるとしても確率分布を使った表現と矛盾することはありません。一点だけに値が存在する確率分布を使えば良いだけです。

また、右辺の$${P[s_{t+1}|s_t, s_{t-1}, \dots, s_1, s_0]}$$は、次の状態$${s_{t+1}}$$を計算するのにそれまでのすべての状態を与えられていることを意味します。

よって、$${P[s_{t+1}|s_t] = P[s_{t+1}|s_t, s_{t-1}, \dots, s_1, s_0]}$$とは次の状態$${s_{t+1}}$$の確率分布を計算するのには現在の状態$${s_t}$$だけあれば良いということを数学的に表現しています。なぜなら、$${s_{t-1}, \dots, s_1, s_0}$$は条件として与えられても使われないことになるので必要ないからです。

こういった数式はマルコフ性などを簡潔にまた明確に表現するのに便利ではありますが、実際にエージェントを実装するときに登場することはまずありません。また、上記のような確率分布を実際に計算することもありません。

なので重要なのは数式ではなく、マルコフ性がなぜ成立するのか、なぜ必要なのかを理解することになります。なぜなら強化学習の理論はマルコフ性をもとに成り立っているからです。

次回からはマルコフ性を土台として強化学習の理論をさらに構築してしていきます。

（続く）