強化学習① - Markov決定過程
こんにちは～。
最近巷でホットな(深層)強化学習ですが、かくいう自分も1、2年前ぐらいにAlphaGoの熱に当てられて強化学習にハマりまして、そのときにちょっとした自分用のノートをつくりました。
その結果、ブラウザ上で深層強化学習をするAPIとかが生えたり生えなかったりした(これはまたいずれ別の機会にでも)のですが、ともかく折角書いたノートをこのまま腐らせておくのも勿体ないので、一連のノートを「週刊連載」で公開していきたいと思います(5回分ぐらいあります)。
今回はその一回目になります。
専門家でも何でもないですが、強化学習やってみたいけどよーわから～んっていう方々のお役に立てれば幸いです。
以下、本編です。
「意思決定」の「自動化」
わたしたちは与えられた環境(Environment)のなかで、多かれ少なかれ意思決定を繰り返しながら行動しています。
その中でも、様々な状況で「最適(optimal)な」意思決定を下したいという場面に遭遇します。しかし、何が「最適」なのかを限られた能力や状況で把握し、それに基づいて最善の意思決定を下すことは多くの場合困難です。
そこで与えられた環境の中で、ある主体が「最適な」意思決定を行っていくためにはどうすればいいのかというのが興味のある問題になります。
一般に環境の中には多くの意思決定主体が存在し、環境のとりうる状態は一つの意思決定主体では定まりません。ある意思決定主体の最適な行動を決定しようと思っても、この行動の結果として得られる系の新しい状態は常に外界による干渉を受けてしまうのです。
これを数学的に扱うための1つのモデルがMarkov決定過程(Markov Decision Process, MDP)と呼ばれる数理モデルです。
MDPでは、環境の状態は意思決定主体の行動に沿って確率的に変化していくと仮定します。確率的な記述を用いることで他者の干渉による系の状態変化を比較的簡単に扱うことができるようになるわけです。
確率解析とかの文脈でよくMarkov過程という概念が出てきますが、もし系の状態遷移が自分の行動に依らないのであれば、MDPはMarkov過程に一致します。その意味で、Markov過程を一般化したものがMDPだと言えます。
モデリング
さて、ここまでは問題設定を行ってきたわけですが、次はこれを数理モデルとして扱うために、必要な数学的な定義を行います:
- 状態集合 $S$
- 行動集合 $A$
- 遷移確率,モデル $P^{ss'}_{a} = \mathrm{Prob}[s_{t+1}=s'| a_t = a, s_t = s]$
- 即時報酬(immediate reward) $R^{ss'}_{a} \in \mathbb{R}$
- 割引因子(discount factor) $\gamma \in [0,1]$
状態集合$S$は文字通り、環境の取りうる可能な状態(state)の集合です。
行動集合$A$も、意思決定主体が採ることが可能な行動(action)の集合です。特に、採ることのできる行動は意思決定主体の置かれている状況$s \in S$に依存すると考えられるので、行動集合$A$は次のような直和分解が許されると仮定しましょう。ここで$A_s$は状態$s \in S$の下に置かれている意思決定主体に許される行動集合です:
$$A = \bigoplus_{s \in S} A_s$$
状態集合$S$や行動集合$A$は任意ですが、殆どの場合計算機を用いてこの問題を解くことを考えます。したがってこのような状況では、適当に離散化を行ったうえで$S$や$A$を有限集合とみなすことになります。そこで、これ以降も$S$や$A$は有限集合とみなします。
そして、ある状態$s \in S$の下である行動$a \in A$を採ったときに、系の状態が$s' \in S$に遷移する確率が遷移確率$P^{ss'}_{a}$です。後述する理由から、系のモデルとも呼ばれます。一般に$(a,s)$の組に対し、$s'$が確率的に定まるので、$\sum_{s' \in S}P^{ss'}_{a}=1$を満たします。
このとき、同時に意思決定主体には即時報酬(immediate reward)$R^{ss'}_{a}$が与えられます。この報酬は$(a,s) \rightarrow s'$という確率過程に伴う確率変数なので、状態$s$の下で行動$a$をとったときに得られる報酬の期待値$\mathsf{R}_{a}(s)$は
$$ \mathsf{R}_{a}(s) = \sum_{s' \in S} P^{ss'}_{a} R^{ss'}_{a} $$
と表現することができます。
これらの定義によると、もはや以前の「最適」という未定義語は「報酬を最大化する」という具体的文言に換言されたことに注目します。つまり通常の意味での最適化問題に帰着したのです。
なぜ確率なのか？
初めに、確率的な記述を用いることで他者の干渉による系の状態変化を記述するといいました。すなわち、状態変化が確率的に起きると仮定し、実際にその仮定に従って遷移確率というものを定義したのでした。しかし、これは本当に妥当な仮定なのでしょうか？
われわれが普段考える、サイコロを振ったときに5の目が出るのはどれぐらいの確率なのか、というような素朴な確率の概念からすると、これは少し奇妙に思えてきます。
なぜなら、環境というのは固定された背景事象ではなくて、意思決定主体各々の行動によって変化しこれらが再び各々の意思決定に影響を及ぼすような極めて複雑な存在だからです。われわれが巨大な環境を相手にして意思決定を行っているとき、他の一人一人もまた同じような立場に立たされているわけです。
強化学習においてMDPを採用するときには、この複雑な世界を「自分」と「自分以外」の2つに分割して、これらの間のdynamicalな応答を制御しようという意識が根底にあります。
したがって、この応答を頻度論的な静的確率で扱うことは不適当に思われます。
実際、このモデルを現実の問題へ適用した際の状態間の遷移確率というのは、問題を解決する試みを通じてアポステリオリに与えられることが殆どです。
つまり、多くの問題では、われわれは与えられた確率を基に最適な意思決定を探索すると同時に、確率分布そのものを探索していかなければならないというわけです。
したがって、ここで現れる「確率」というのは、「頻度論的な確率」というよりは、むしろ個人の知識を反映した「ベイズ主義的な確率」と解釈するのが好都合です。この意味で、このモデルで扱っている「確率」というのは、意思決定主体の持っている「知識」そのものだと言えます。われわれは、環境にプローブを挿し込んだときの応答を通して、環境についての「知識」を蓄えながら、問題に取り組んでいくのです。
このモデルはあくまで「前提知識」が備わっているという状況における設定であり、この「知識」をどのように環境から構築していくかという問題は、(強化学習において非常に重要な課題ではありますが)また別の話です。
もちろん強化学習において、個人の持っている「知識」を全て確率的記述に繰り込んでしまうのがそもそも正しい処方箋なのかという点については、非常に微妙なところだと思います。しかし、確率的な記述を導入することで「知識」の探索に関する問題をモデルから完全に分離できたという点、そして何よりもこのような処方箋によって強化学習の数理的な解析が可能になったという点をひとまずは評価しましょう👏
これらの点で言えば、MDPというのは強化学習における一つの簡潔なアプローチであり、巧妙なモデリングになっていることがわかってもらえるかと思います。
実際、MDPは最適制御理論と呼ばれる文脈の中で研究されていて、そこにはしっかりとした数理構造が存在することが既に知られているのです。
