強化学習② - 方策と価値関数
強化学習の基礎についてまとめたノートの第二回です。
解となる「方策」
ある状態$s$の下で最適化するべき関数は、短期的な報酬ではなくゴールと呼ばれる一連の行動で得られる合計報酬です。これは状態遷移の列$s \xrightarrow{a_t} s_{t+1} \xrightarrow{a_{t+1}} s_{t+2} \xrightarrow{a_{t+2}} \cdots$から定まる次のような形式的冪級数$V(s)$によって表現することができます:
$$ \begin{array}{lll} V(s) &\displaystyle= R^{s_{}~s_{t+1}}_{a_t} + \gamma R^{s_{t+1}~s_{t+2}}_{a_{t+1}} + \gamma^2 R^{s_{t+2}~s_{t+3}}_{a_{t+2}} + \cdots &\displaystyle\ &\displaystyle= \left.\sum_{k=0}^\infty \gamma^k R^{s_{t+k}~s_{t+k+1}}_{a_{t+k}} \right|_{s_t=s}\ \end{array} $$
ここで、冪をとる$\gamma$のことを割引因子や時間選好率と呼び、これが小さければ小さいほど将来の報酬はより速やかに減少するようになります。すなわち、小さい$\gamma$の値は長期的に得られる価値を軽視し、短期的に得られる価値を相対的に優先することを意味します。この問題で目指すのは、あくまで(可能な限り短い)有限時間で適当な報酬を最大化することなので、少なくとも無限遠方の価値をより重視することは有り得ません。したがって、$\gamma$は少なくとも$0$から$1$の範囲の値をとる必要があります。
$V(s)$を計算する上で問題なのは、各状態$s_{t+k}$で採るべき行動$a_{t+k}$が決まっておらず、その結果合計報酬の期待値を計算できないということです。
そこで、ある状態$s$の下で採用するべき行動$a$の確率分布
$$\pi_a(s) = \mathrm{Prob}[a|s_t = s]$$
を定義します。このような確率分布$\pi_a(s)$を方策(policy)と言います。この方策を用いることで、各々の状況でどのような行動をとるべきかという指針がもたらされます。方策が確率分布で与えられるという点が問題ですが、次の回で分かる通り、実は系のモデルが既知ならば、最適な方策が必ず存在します。つまり系のモデルを完全に知っていれば確率分布を使う必要はないのです。
しかし、前回述べたように、実際の問題で系のモデルがアプリオリに与えられていることはほとんどありません。この場合、不確実な「知識」に基づいて意思決定を行う必要があり、この場合もはや確率的に行動を決定するほかないのです。
この方策と遷移確率を組み合わせることで、方策$\pi$に基づく状態$s$から状態$s'$への直接の遷移確率$P^{ss'}_{\pi}$が求められます:
$$ P^{ss'}_{\pi} = \sum_{a \in A_s}\pi_a(s)P^{ss'}_{a} $$
さらに、方策$\pi$に基づいた状態$s$の下で得られる即時報酬の期待値も求められます:
$$ \mathsf{R}_\pi(s) = \sum_{a \in A_s}\pi_a(s)\mathsf{R}_a(s) $$
方策$\pi$のおかげで、いまや状態遷移は確率分布$P^{ss'}_{\pi}$に従う確率過程に帰着したので、これを用いれば、現在の状態$s$にのみ依った合計報酬の期待値$\mathsf{V}_\pi(s)$を得ることができます。
$$ \begin{split} \mathsf{V}_\pi(s) &\displaystyle \equiv \mathbb{E}_\pi\left[ V(s)\right]\\ &\displaystyle= \mathbb{E}_\pi\left[\left. \sum_{k=0}^\infty \gamma^k R^{s_{t+k}~s_{t+k+1}}_{a_{t+k}} \right| _{s_t = s} \right]\\ &\displaystyle= \mathbb{E}_\pi\left[ R^{s~s_{t+1}}_{a_t} + \gamma V(s_{t+1})\right]\\ &\displaystyle= \sum_{a \in A_s}\pi_a(s) \sum_{s' \in S} P^{ss'}_{a}\left[R^{ss'}_{a} + \gamma \mathbb{E}_\pi\left[ V(s')\right]\right]\\ &\displaystyle= \sum_{a \in A_s} \pi_a(s) \left[\mathsf{R}_a(s) + \gamma \sum_{s' \in S} P^{ss'}_a\mathsf{V}_\pi(s')\right]\\ &\displaystyle= \mathsf{R}_\pi(s) + \gamma \sum_{s' \in S} P^{ss'}_\pi\mathsf{V}_\pi(s') \end{split} $$
ここで、確率分布$(p_i)$に従う確率変数$X$を引数にとる任意の関数$f(X)$の期待値が
$$ \mathbb{E}\left[ f(X)\right] = \sum_i p_i f(x_i) $$
で表されることを用いました。
わたしたちは$\mathsf{V}_\pi(s)$を用いて現在の状態を評価し、行動の最適化を行うので、この$\mathsf{V}_\pi(s)$を状態価値関数(state-value function)とよびます。
さて、状態価値関数に関する再帰方程式
$$ \mathsf{V}_\pi(s) = \mathsf{R}_\pi(s) + \gamma \sum_{s' \in S} P^{ss'}_\pi\mathsf{V}_\pi(s') $$
の意味は次のように説明できます。
まず、方策$\pi$が定まっていれば、状態$s$の下にいる時点で即時報酬の期待値は決まってしまいます。これが$\mathsf{R}_\pi(s)$の項です。
そして、何らかの行動を採った後遷移した状態$s'$の下で期待される合計報酬は$\gamma \mathsf{V}_\pi(s')$で与えられるので、これを方策$\pi$に従ったときの状態遷移確率$P^{ss'}_\pi$に関して期待値をとったものが第2項に相当します。
つまり、これを使えば確かに再帰的に合計報酬の期待値が求められることがわかります。
ナイーブなMDPの解法
定義からもわかるように、一般に方策$\pi$のとり方は任意です。ところが、わたしたちがいまここで中心的な問題としているのは、状態$s$の下で状態価値関数を最大にするような方策$\pi$なのです。このような指針に沿ってなされる意思決定は、最大の報酬をもたらす最善の意思決定になると期待されます。
実は状態価値関数の表式が再帰的な線形方程式であることに注目すると、ある方策$\pi$に対する状態価値関数$\mathsf{V}_\pi$は、状態$s$を添字とする連立方程式として
$$ \mathsf{V}_\pi = \mathsf{R}_\pi + \gamma P_\pi\mathsf{V}_\pi $$
と書けて、結局
$$ \mathsf{V}_\pi = (1 - \gamma P_\pi)^{-1}\mathsf{R}_\pi $$
と陽に解くことができることがわかります。
こうして得られた状態価値関数を用いれば、最適な意思決定をもたらす方策を、次のように定義される半順序
$$ \pi \geq \pi' \Leftrightarrow \forall s \in S ,~ \mathsf{V}_{\pi}(s) \geq \mathsf{V}_{\pi'}(s) $$
に対して極大となる$\pi^*$として定義することができます。これを最適な方策と呼びます。
さらに、最適な方策$\pi^*$を採用したときの状態価値関数$\mathsf{V}_{\pi^*}$を、最適な状態価値関数と呼び、そしてこれは次のような半順序に対する極大元になっています。
$$ \mathsf{V}_{\pi} \geq \mathsf{V}_{\pi'} \Leftrightarrow \forall s \in S ,~ \mathsf{V}_{\pi}(s) \geq \mathsf{V}_{\pi'}(s) $$
ここで導入された順序は半順序なので、ここまでの議論の範囲では最適な状態価値関数というのは一般に複数存在しうるわけですが、
次の回では、これらがすべて同じBellman方程式の解になることを明らかにします。
その結果、最適な状態価値関数は実際のところユニークに定まってしまい、他の全ての状態価値関数と比較可能であることがわかります。
その意味で、最適な状態価値関数$\mathsf{V}_{\pi^*}$を($\pi$が必ずしも一意ではないにもかかわらず)次のようにして定義してしまっている文献もあります。
$$ \mathsf{V}_{\pi^*} := \max_\pi \mathsf{V}_{\pi} $$
