はじめに
強化学習を真面目に勉強し始めたので、ここまで学んだ知見を記事としてまとめます。 線形代数の基本的な表記や確率統計で出てくる基本的な言葉を前提とし、理論的な証明などは割愛し結果だけを認める形で進めていきたいと思います。
環境とエージェント
まず最初に強化学習で現れる「環境とエージェントの相互作用」なるもの言葉について、実を言うと、目の前にある課題は環境とエージェントの相互作用というのは必ずしも必要がないかもしれません（そうであれば強化学習という手段を行使しないということ…）。
強化学習を学び始めるとどうしてもこの相互作用なるものが前提で話が進んでしまうため、若干の分かりにくさが生まれてしまうように思います。ここでは思い切って、「環境」と「エージェント」を完全に分離して説明し、問題によっては相互作用が必要になるという形式で話を展開しましょう。
環境
マルコフ過程
私達はある環境を外から観測しています。環境は状態 $s_t$ というものを有しており、これが時刻 $t$ の経過とともに刻一刻と変わっていっているという状況です。仮にこの環境の状態遷移が下記のように表されるとしましょう。
$$ s _ {t+1} = T(s_t) $$
ここで $T$ は何某かの関数です。すなわち時刻 $t$ の状態が関数 $T$ によって変換され $s _ {t+1}$ になっているという状況を想定しています。いやいやちょっと待った、
$$ s _ {t+1} = T(s_t, s _ {t - 1}) $$
みたいに複数の時刻の状態に依存して $s _ {t+1}$ は決まるのかもしれない！ということも想定できます。ところがそうなってくると問題がやけに複雑になってしまうので、我々の扱う環境は前後1時刻のみによって状態の変化が記述されていると仮定するのです。 このような性質をマルコフ性と呼びます。そしてそのような時間発展していく変数の列をマルコフ過程などと呼びます。
さて、仮に $T(s) = \frac{1}{2} s $ みたいな関数だったとしましょう。そうするとこのマルコフ過程は
$$ s _ {t+1} = \frac{1}{2}s_t $$
という漸化式で表現されることになります。このようなマルコフ過程は時間経過と共にどうなるのでしょうか？簡単なことです。 $s_0 = 7$ だと思って計算すれば、 $s_1 = \frac{7}{2}$ になりますし、 $s_2 = \frac{7}{4}$ となりますし、…（以下略）で
$$ s_{t} = \frac{7}{2 ^ t} $$
となります。 $t \rightarrow \infty$ で $s _ t \rightarrow 0$ というのは高校生でも分かります。さて、これではどうにもこうにも面白くないので、本当のマルコフ過程を見ていきましょう（今までのは嘘のマルコフ過程である！）。
本当のマルコフ過程
本当のマルコフ過程は関数 $T$ で決定論的に値が変換されるのではなく、確率的に値が変換されます。ここでは問題を簡単にするために各時刻について状態は
$$ \{s ^ {(0)}, s ^ {(1)}, s ^ {(2)}\} $$
という3つのうちいずれかの値を取るということにしましょう。すると
$$ s _ {t+1} = T(s_t) $$
と先程まで表されていたマルコフ過程を修正し、確率遷移関数 $T$ によって $s_t$ が $s _ {t+1}$ に確率的に変化するという様子を表したいということです。 そこで、 $T$ は具体的にどういうものになっているのかというと、 例えば $s ^ {(0)} \rightarrow s ^ {(1)}$ という状態遷移のしやすさ、あるいは$s ^ {(0)} \rightarrow s ^ {(2)}$ への状態遷移のしやすさ、を表したものになっていると良いでしょう。すべて列挙すれば
$$ \begin{align} s ^ {(0)} &\rightarrow s ^ {(0)} \\ s ^ {(0)} &\rightarrow s ^ {(1)} \\ s ^ {(0)} &\rightarrow s ^ {(2)} \\ s ^ {(1)} &\rightarrow s ^ {(0)} \\ s ^ {(1)} &\rightarrow s ^ {(1)} \\ s ^ {(1)} &\rightarrow s ^ {(2)} \\ s ^ {(2)} &\rightarrow s ^ {(0)} \\ s ^ {(2)} &\rightarrow s ^ {(1)} \\ s ^ {(2)} &\rightarrow s ^ {(2)} \\ \end{align} $$
という遷移の仕方全てについて確率を割り当てたものとなっていると良いということです。まとめてしまえば、時間が進むことで状態の遷移がどのように起こるのかを表していた $T$ なるものは
$$ T = {\rm Pr} (s _ {t+1} | s _ {t}) $$
という条件付き確率を表しているというわけです（正確には、離散の場合は$T _ {ij} = {\rm Pr } ( s _ {t+1} = s ^ { (j) }| s _ t = s ^ {(i)} )$ という行列）。
ここで例を見てみましょう。もしも $s _ t = s ^ {(0)}$ だとすれば
$$ \begin{align} s ^ {(0)} &\rightarrow s ^ {(0)} \\ s ^ {(0)} &\rightarrow s ^ {(1)} \\ s ^ {(0)} &\rightarrow s ^ {(2)} \end{align} $$
に対応する条件付き確率を参照すればよく、これが
$$ \begin{align} T(s ^ {(0)} | s ^ {(0)})& = \frac{1}{4} \\ T(s ^ {(1)} | s ^ {(0)})& = \frac{1}{2} \\ T(s ^ {(2)} | s ^ {(0)})& = \frac{1}{4} \end{align} $$
となっていれば「あ、次は $ s ^ {(1)}$ になりそうな気がするな…」と見積もれるというわけです。 要するにマルコフ過程は現在の状態次第で、次の状態がどれになりやすいかが決まるものであるということです。
マルコフ決定過程
仮に環境を眺めていたらマルコフ過程でした…！ということがわかったとすれば、現在の状態を観測することで次の状態がどうなるかを、確率遷移関数 $T$ を知ってさえいれば！！、見積もることが出来るという話になります。 このように時間変化で状態が変わっていくような環境の振る舞いを知ろうという試み（すなわち遷移関数を知ろうという試み）は、システム同定と言ったりします（若干不正確ですが…）。
もしも、データ $D = \{s _ 1, \cdots, s _ T \}$ が手元にあったとすれば、それぞれ各状態から各状態への移り変わりがどれくらいの頻度で起こっているのかを見積もることができるので、ある種のシステム同定を行うことができるでしょう。この概念は後にモデルベース強化学習（環境を同定した上でエージェントを学習させる）につながる重要な事柄です。
ここではマルコフ決定過程の話をするために、新たな変数 $a _ t$ を登場させてみましょう。こいつは
$$ \{ a ^ {(0)}, a ^ {(1)} \} $$
という2つの値のいずれかを取るものとします。さて環境の状態が $s ^ {(0)}$ のとき次の状態が
$$ \begin{align} T(s ^ {(0)} | s ^ {(0)})& = \frac{1}{4} \\ T(s ^ {(1)} | s ^ {(0)})& = \frac{1}{2} \\ T(s ^ {(2)} | s ^ {(0)})& = \frac{1}{4} \end{align} $$
で決まるということですが、ここで私達は、 次の状態は $s ^ {(2)}$ になってほしいと思っていたとします。しかし確率遷移関数を見るに、放っておけば思惑通りになるのは難しそうな状況です。
ここで環境の外から $ a _ t$ を与えてみると上記の確率遷移関数が変化すると考えます。具体的に $ a ^ {(0)}$ を与えてみたら
$$ \begin{align} T _ {a ^ {(0)}}(s ^ {(0)} | s ^ {(0)})& = \frac{1}{3} \\ T _ {a ^ {(0)}}(s ^ {(1)} | s ^ {(0)})& = \frac{1}{3} \\ T _ {a ^ {(0)}}(s ^ {(2)} | s ^ {(0)})& = \frac{1}{3} \end{align} $$
になり、$ a ^ {(1)}$ を与えてみたら
$$ \begin{align} T _ {a ^ {(1)}}(s ^ {(0)} | s ^ {(0)})& = \frac{1}{6} \\ T _ {a ^ {(1)}}(s ^ {(1)} | s ^ {(0)})& = \frac{1}{6} \\ T _ {a ^ {(1)}}(s ^ {(2)} | s ^ {(0)})& = \frac{2}{3} \end{align} $$
となるとわかっていたらどうしましょうか。当然、次は $s ^ {(2)}$ になってほしいのですから $ a ^ {(1)}$ を外から与えてやろうと思えるわけですね。このように、現在の状態 $s _ t$ と外から与える行動 $a _ t$ によって次の状態 $s _ {t + 1}$ が確率的に決まるような場合には、マルコフ過程を改め、マルコフ決定過程と呼ぶようにします。
そして、現在の状態 $s _ t$ と今回外から取った行動 $a _ t$ によって環境の次の状態 $s _ {t+1}$ が決まるというようなことを改めて記述するために、状態遷移関数は下記のような条件付き確率として記述され直すこととなります。
$$ T = p (s _ {t + 1} | s _ t, a _ t) $$
ところで、「マルコフ決定過程が、外部から影響を及ぼすことで遷移の仕方が変わるようなマルコフ過程である」と思えば、そんな環境を目の前にしたときに私達が考えたくなるのは、「環境の状態 $s$ を思い通りにコントロールしてやるにはどのように外部から行動 $a$ を与えてやればいいのだろうか？ 」ということにならないでしょうか。
そのようなことを学習させるのが強化学習の大きな目標なのです。
本当のマルコフ決定過程
また、嘘をついてしまいました。マルコフ決定過程を定式化するものは、上記だけではありません。 先程 $s ^ {(0)} \rightarrow s ^ {(2)}$ と移ることを良しと考え、その確率が高くなるような行動 $ a ^ {(1)} $ を選んでやろうという話がありました。
この、状態 $s _ t$ に対して取る行動 $a _ t$ を「良し」と考える度合いを数値で表現したものを報酬関数 $g(s _ t, a _ t)$ と呼びます。今回は $g (s ^ {(0)}, a ^ {(1)})$ の報酬はきっと高い値になっていることでしょう。マルコフ決定過程とはこれまでの説明の通り、状態、行動、確率遷移関数、報酬関数によって規定される何某かのものであるということです（あとは初期状態を規定するなにかも必要ですが…）。
まとめると、
$$ \begin{align} 行動集合&：\mathcal A = \{a ^ {(1)}, a ^ {(2)}, \cdots, \} \\ 状態集合&：\mathcal S = \{s ^ {(1)}, s ^ {(2)}, \cdots, \} \\ 遷移関数&：T _ {ijk} = {\rm Pr}(s _ {t+1} = s ^ {(j)} \mid s _ {t} = s ^ {(i)}, a _ {t} = a ^ {(k)}) \\ 報酬関数&：g(s , a )\\ 初期状態確率&：p _ 0 = {\rm Pr} (s _ 0) \end{align} $$
でマルコフ決定過程が規定されます。
強化学習の話をちょっとだけ
ところで状態の遷移はそのときは良いと思っても、後々になってみれば失敗だったということも起こりえます（飛車を捨てて銀と交換するのは一見悪いのだが、ゲーム終盤では大駒を切るという行動が良い場合もある。あるいは迷路の出口に近づくことが良い行動だと思いきや、ゴールへは遠回りをしないと絶対にたどり着けないなど）。
マルコフ決定過程において状態をコントロールしたい時に、そのコントロールに貢献する（報酬をもらえる）行動を貪欲にとってみても、その行動によって状態が変わり、次の状態ではもはや手の付けられない状態になっているということが起こるからです。つまり、この行動は今は良しとされているが、状態が変わったあとのことも考慮に入れて（将来もらえる報酬のことも考えて）行動を選択しなければならないということです。
もしも（報酬関数もまともであり）状態遷移確率も完全に把握できているのであれば、慎重に先の遷移の仕方も見積もりながら、各時刻に取るべき行動を計算することが出来ます（動的計画法など）。
ところが、実際は確率遷移関数はどういうものになっているのかわからない（どういう状態にどういう行動を与えれば、どんな遷移が起こりやすいのかを知らない）ケースが実用上ほとんどです。仕方がないので、すべての状態に対してすべての行動を取ってみることを永遠と繰り返してやれば、その遷移の様子を見積もることが出来ます（すべてのパターンを試してもあくまで確率的な遷移なので、統計的に見積もるのが限界であるが、ある種のシステム同定を実施するということである）。
遷移確率を把握して（それが正しいと信ずれば）、動的計画法などで解くことができるわけですから、そのような方針が「モデルベース強化学習」の基本的なスタンスです。実際にはガチガチにシステム同定をするとは限りません（なぜなら、すべての状態遷移のパターンをシラベまくらねばならないから）。なのでマルコフ決定過程に従っているであろう環境の振る舞いを何かしら関数や分布などで表し、その数理モデルに基づいて行動の仕方（方策）を決めようというやり方は全般的にモデルベースであると言われます。
一方で、もうマルコフ決定過程の中身は諦めてしまい、行動を取ったらなにかしらの状態が返ってきて報酬をくれる箱だと思い、報酬を高められるような行動のとり方（方策）をひたすら模索することも考えられます（モデルフリー）。
上記のように様々なマルコフ決定過程との向き合い方がある中で、状態や報酬を見ながらマルコフ決定過程のことを見積もりつつ、行動を決める何かをエージェントと呼びます。強化学習は賢いエージェントを作るというのが目的になるのです。
最後に
簡単のため価値関数うんぬんの話は省きましたが、概ね強化学習の基礎になるマルコフ決定過程を抑えておけば、あとは数学的にテクニカルな部分を追っていくことで話がわかるようになるでしょう。
たいてい多くの不慣れな人は、教師あり学習、教師なし学習、強化学習という言葉の枠組みで既によくわからん！となる場合が多い気がします。強化学習というのは上記のようなマルコフ決定過程で動いている環境に対して、その状態を思い通りにコントロールするような行動の取り方を学習させる方法であるということは強く意識して良いと思います（僕は、教師ありとか教師なしと肩を並べる形の説明、すなわちラベルの代わりに報酬を与えることで学習させる…という説明はなんとなく好まない。決定的に重要なのは、制御問題を解こうという、その問題設定の方だと思うからだ）。
