｢｣ \stackrel{\triangle}{=}
\stackrel{\triangle}{=}
強化学習（著：森村哲郎）
- マルコフ性（Markov property）: サイコロの目のようなi.i.d. （独立同一分布）よりも弱く、平均値のようなこれまでの全ての値に依存するよりは強い条件で、現在の状態からのみ確率が求まるもの
- マルコフ過程（Markov process）: マルコフ性を持つ確率過程
- マルコフ連鎖（Markov chain）: 状態変数の値が離散的なマルコフ過程
- マルコフ決定過程（Markov decision process | MDP）: マルコフ連鎖に行動（action）と報酬（reward）を組み入れたもの。式にすると、state, action, 初期状態、状態遷移、報酬関数の5つで $$ M \stackrel{\triangle}{=} \{\mathcal{S}, \mathcal{A}, p_{s_{0}}, p_{T}, g\} $$
- 決定的方策（deterministic policy）: 判断する関数が常に一定のもの $\Pi^{d} \stackrel{\triangle}{=} \{\pi^{d}:\mathcal{S}\to\mathcal{A}\}$
- 定常なマルコフ方策（stationary Markov policy）: 過去の経験とは独立で、時間とともに方策関数が変化しないもの。決定的方策もこれに含む $\pi^{s}$
- 定常かつ決定的なものは $\pi^{sd}$ のように記述
- 履歴依存の方策（history-dependent policy）: 過去の経験に基づいて行動選択確率を決めるもの、マルコフ方策の逆 $\pi^{h}$
- 履歴依存の方策は、超指数関数的に組み合わせ爆発が起こってしまうので、取り扱い困難。実は大体のケースでマルコフ方策を考えるだけで十分
- 分位点（quantile）: 中央値（median）の一般化で、中央値は真ん中の値を取り出すが、分位点は真ん中以外の取り出すポイントを任意に定めたもの、0.05分位点など
- マルコフ決定過程には、ゴール状態があるもの、時間切れで停止するもの、無限に終わらないもの、の3種類あるが、ゴール後も時間切れ後も確率1で同じ状態にとどまり続けるものとすることで、3つ目のケースに単一化して考えることができる
- エルゴード性（ergodic property）: マルコフ連鎖のうち、既約的（irreducible, すべての状態が行き来可能）かつ非周期的（apriodic, ぐるぐる回るだけの形でないこと）であるもの。ただし、エルゴード定理（空間平均と時間平均が一致する）は既約でさえあれば成り立つので、エルゴード性の要件を既約性のみにしている本も多い。非周期性は極限分布の収束を保証するために必要。
- 期待リターンの時間平均 $$ f_{\infty}(\pi)\stackrel{\triangle}{=}\lim_{T\to\infty}\mathbb{E}^{\pi}\left[{1\over T}\sum_{t=0}^{T-1}C_{t}\right]=\lim_{T\to\infty}\mathbb{E}^{\pi}\left[{1\over T}\sum_{t=0}^{T-1}V^{\pi}(S_{t})\right] $$
- 定常分布（stationary distribution）$p^{\pi}_{\infty}:\mathcal{S}\to[0,1]$ $$ p^{\pi}_{\infty}(s')=\sum_{s\in\mathcal{S}}p^{\pi}_{MC}(s'|s)p^{\pi}_{\infty}(s), \forall s' \in \mathcal{S} $$
- 空間平均と時間平均の一致 $$ \sum_{s\in\mathcal{S}}p^{\pi}_{\infty}(s)v(s)=\lim_{T\to\infty}\mathbb{E}^{\pi}\left[{1\over T}\sum_{t=0}^{T-1}v(S_{t})\right] $$
- ベルマン期待方程式（Bellman expectation equation） $$ V^{\pi}(s)=\sum_{a\in\mathcal{A}}\pi(a|s)\left(g(s,a)+\gamma\sum_{s'\in\mathcal{S}}p_{T}(s'|s,a)V^{\pi}(s')\right), \forall s \in \mathcal{S} $$
- ↑までを使って期待リターンの時間平均を書き直すと、 $$ f_{\infty}(\pi)={1\over 1-\gamma}\lim_{T\to\infty}\mathbb{E}^{\pi}\left[{1\over T}\sum_{t=0}^{T-1}R_{t}\right], \forall \pi \in \Pi $$ となるので、逐次的意思決定問題は平均報酬の最大化問題と同じになり、割引率に依存しない
- （↑でRtはどこから来た?）
- ベルマンの最適方程式（Bellman optimality equation） $$ V^{*}(s)=\max_{a\in\mathcal{A}}\left\{g(s,a)+\gamma\sum_{s'\in\mathcal{S}}p_{T}(s'|s,a)V^{*}(s')\right\},\forall s\in\mathcal{S} $$
- ベルマン期待作用素（Bellman expectation operator） $$ (\textsf{B}_{\pi}(v))(s)\stackrel{\triangle}{=}\sum_{a\in\mathcal{A}}\pi(s|a)\left(g(s,a)+\gamma\sum_{s'\in\mathcal{S}}p_{T}(s'|s,a)v(s')\right), \forall s \in \mathcal{S} $$
- ベルマン最適作用素（Bellman optimality operator） $$ (\textsf{B}_{*}(v))(s)\stackrel{\triangle}{=}\max_{a\in\mathcal{A}}\left\{g(s,a)+\gamma\sum_{s'\in\mathcal{S}}p_{T}(s'|s,a)v(s')\right\}, \forall s \in \mathcal{S} $$
- 動的計画法による解法
- 価値反復法（value iteration algorithm）: 価値関数の更新と収束判定を繰り返す、つまり $$ v'(s):=\max_{a\in\mathcal{A}} \left\{g(s,a)+\gamma \sum_{s'\in\mathcal{S}}p_{T}(s'|s,a)v(s')\right\}, \forall s \in \mathcal{S} $$ とし、$\max_{s\in\mathcal{S}}|v(s)-v'(s)|<\epsilon$なら $$ \pi_{v'}^{d}:=\text{argmax}_{a\in\mathcal{A}} \left\{g(s,a)+\gamma \sum_{s'\in\mathcal{S}}p_{T}(s'|s,a)v'(s')\right\}, \forall s \in \mathcal{S} $$ を求めて終了
- 方策反復法（policy iteration algorithm）: ベルマン方程式を解いて価値関数を求め、それを使って方策を改善する。方策が変化しなくなったら終了、つまり $$ V^{\pi^{d}}(s)=(\textsf{B}_{\pi^{d}}V^{\pi^{d}})(s), \forall s \in\mathcal{S} $$ を求めて $$ \pi^{d'}(s):=\text{argmax}_{s\in\mathcal{S}}\left\{g(s,a)+\gamma\sum_{s\in\mathcal{S}}p_{T}(s'|s,a)V^{\pi^{d}}(s')\right\},\forall s \in\mathcal{S} $$ とし、$\pi^{d}(s)=\pi^{d'}(s)$となるまで繰り返す
- 線形計画法による解法
$$
\begin{cases}
\text{Minimize} &\displaystyle \sum_{s\in\mathcal{S}}w(s)v(s) \\
\text{subject to} &v(s)\geq g(s,a)+\gamma\sum_{s'\in\mathcal{S}}p_{T}(s'|s,a)+v(s'), \forall (s,a)\in\mathcal{S}\times\mathcal{A} \end{cases} $$ - ↑を双対化すると
$$
\begin{cases}
\text{Minimize} &\displaystyle \sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}x(s,a)g(s,a) \\
\text{subject to} &\displaystyle \sum_{a'\in\mathcal{A}} x(s',a')+\gamma\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}} p_{T}(s'|s,a)+x(s,a)=w(s'), \forall s'\in\mathcal{S} \\
& x(s,a)\geq 0, \forall (s,a)\in\mathcal{S}\times\mathcal{A} \end{cases} $$ - 経験度数関数（experience frequency function）$\Phi_{w}^{\pi}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ : 期待累積経験度数を出力する関数
$$\displaylines{
\begin{align}
\Phi_{w}^{\pi}(s,a)&\stackrel{\triangle}{=}\sum_{s_{0}\in\mathcal{S}}w(s_{0})\mathbb{E}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\mathbb{I}_{\{S_{t}=s\}}\mathbb{I}_{\{A_{t}=a\}}\mid S_{0}=s_{0}\right] \\
&= \sum_{s_{0}\in\mathcal{S}}w(s_{0}) \sum_{t=0}^{\infty}\gamma^{t}\text{Pr}(S_{t}=s,A_{t}=a\mid S_{0}=s_{0},M(\pi)) \\
&= \pi(a|s)\sum_{s_{0}\in\mathcal{S}}w(s_{0}) \sum_{t=0}^{\infty}\gamma^{t}\text{Pr}(S_{t}=s\mid S_{0}=s_{0},M(\pi)) \end{align} }$$ - 経験度数関数は双対問題の実行可能解。また、実行可能解xは確率的方策πに変換可能で、その方策の経験度関数は元の実行可能解と一致する、つまり $$ \pi_{x}(a|s)\stackrel{\triangle}{=}{x(s,a)\over\sum_{a\in\mathcal{A}}x(s,a)}, a\in\mathcal{A},s\in\mathcal{S} $$
- 結局、双対問題はvalue functionのweighted sumのmaximize問題である
- 双対問題の最適解から導かれる方策が最適方策と一致する
ch3 探索と活用のトレードオフ
- リグレット（regret）: 報酬の期待値と実際の報酬の差、つまり $$ L(\mathfrak{A},t;\mathrm{M},s_{0})\stackrel{\triangle}{=}t\max_{\pi\in\Pi}\lim_{T\to\infty}{1\over T}\mathbb{E}[C(\pi,t,\mathrm{M},s_{0})]-C(\mathfrak{A},t,\mathrm{M},s_{0}) $$ ただし、Cは確率変数で、 $$ C(\cdot,t,M,s_{0})\stackrel{\triangle}{=}\sum_{k=0}^{t-1}R_{k}|M,S_{0}=s_{0},\cdot $$
- リグレットが適用できるのは、時間割引の概念のない問題に限られる点に注意
- ε最適（ε-optimal）: 最適方策との誤差がε以内であること、つまり $$ v_{\mathrm{M}}(s;\pi^{*})-v_{\mathrm{M}}(s;\pi)\leq\varepsilon $$
- サンプル複雑度（sample complexity）$C(\mathfrak{A}; \varepsilon, \mathrm{M})$ : ε最適ではないステップtの総数、つまり $$ C(\mathfrak{A}; \varepsilon, \mathrm{M}) \stackrel{\triangle}{=} \lim_{T\to\infty}\sum_{t=0}^{T}\mathbb{I}_{\{v_{\mathrm{M}}(s_{t};\pi^{*})-v_{\mathrm{M}}(s;\pi_{t})>\varepsilon\}} $$
- PAC-MDP(probably approximately correct in markov decision process / マルコフ決定過程で確率的近似的に正しい) : サンプル複雑度が何らかの多項式で抑えられること（？）
- 方策のモデル化として、数理モデルで直接定義する方法と、効用関数で間接的に定義する方法がある
- 行動価値関数（action value function）、またはQ関数 : stateとactionの条件付き期待値、つまり $$ Q^{\pi}(s,a)\stackrel{\triangle}{=}\mathbb{E}^{\pi}[C_{0}\mid S_{0}=a,A_{0}=a] $$
- 貪欲方策：行動価値関数が最大のものを選び続ける方策。ただし局所最適に陥りやすい
- ε貪欲方策：ある確率でランダムに行動を選び、それ以外では行動価値関数が最大のものを選ぶ方策。ただし確率は一定でなくてもよく、1から始めて徐々に下げることで探索と活用のバランスをとることもある
- ソフトマックス方策（softmax policy）: 逆温度βを使って貪欲方策に確率的要素を入れたもの $$ \pi_{s}(a|s;q,\beta)={\exp{\beta q(s,a)}\over\displaystyle\sum_{b\in\mathcal{A}}\exp{\beta q(s,b)}} $$ ここで、βを無限大に飛ばすと貪欲方策と同じになる
- ソフトマックス方策は偏微分を計算できるため、更新に使いやすい
ch4 モデルフリー型の強化学習
- 事前データがそろっている場合バッチ学習、データを収集しながら学習することをオンライン学習という
- 価値関数=期待リターン
- 推定器（estimator）には^ハットをつけて表す
- モンテカルロ推定 $$ \hat{V}(s):={\displaystyle\sum_{t=0}^{T'}\mathbb{I}_{\{s=s_{t}\}}c_{t}\over \displaystyle\sum_{t=0}^{T'}\mathbb{I}_{\{s=s_{t}\}}},\quad \forall s \in \left\{s\in \mathcal{S}:\displaystyle\sum_{t=0}^{T'}\mathbb{I}_{\{s=s_{t}\}}>0 \right\} $$ ただし、 $c_{t}\stackrel{\triangle}{=}\sum_{k=t}^{T}\gamma^{k-t}r_{k}$
- 環境が未知の場合、ベルマン期待作用素を履歴データから標本近似する必要がある
- 近似ベルマン期待作用素（approximated Bellman expectation operator）
$$
\hat{\textsf{B}}(v;h_{t}^{\pi})(s)\stackrel{\triangle}{=}
\begin{cases}
{\displaystyle 1\over\displaystyle\sum_{t=0}^{T-1}\mathbb{I}_{\{s_{t}=s\}}}\displaystyle\sum_{t=0}^{T-1}\mathbb{I}_{\{s_{t}=s\}}(r_{t}+\gamma v(s_{t+1}))&(\textrm{if}\quad\displaystyle\sum_{t=0}^{T-1}\mathbb{I}_{\{s_{t}=s\}}>0) \\
v(s)&\text{(otherwise)} \end{cases} $$ - なお↑は、モデルベース型のベルマン作用素と同一
- ロビンス・モンローの条件（Robbins-Monro condition）: 収束性を保証するための条件。微小更新戦略 $$ \hat{V}(s_{t}):=(1-\alpha_{t})\hat{V}(s_{t})+\alpha_{t}\hat{\textsf{B}}(\hat{V};\{s_{t},r_{t},s_{t+1}\})(s_{t}) $$ において、 $$ \alpha_{t}\geq 0\quad (\forall t\in\mathbb{N}_{0}),\quad\sum_{t=0}^{\infty}\alpha_{t}=\infty,\quad\sum_{t=0}^{\infty}\alpha_{t}^{2}<\infty $$ のすべてを満たすこと。
- ただし実際には、現実的に学習が終わらないことが多く、収束性の保証を捨てて定数で学習することも多い
- ロビンス・モンローのアルゴリズム（Robbins-Monro algorithm）: 上記の微小更新戦略を、そこにおける確率変数と、ベルマン期待作用素との誤差 $$ X_{t}\stackrel{\triangle}{=} \hat{\textsf{B}}(\hat{V};\{s_{t},R_{t},S_{t+1}\})(s_{t}) -\textsf{B}_{\pi}\hat{V}(s_{t}) $$ を使って書き直したもの $$ \hat{V}(s_{t}):=(1-\alpha_{t})\hat{V}(s_{t})+\alpha_{t}(\textsf{B}_{\pi}\hat{V}(s_{t})+X_{t}) $$
- ↑から、微小更新戦略は動的計画法の確率的近似に対応することが分かる
- Temporal Difference error or TD error: 現時点での予測価値と次のステップでの予測価値の差
- TD法（TD method）: $\hat{V}(s_{t}):=\hat{V}(s_{t})+\alpha_{t}\delta_{t}$ によってTD誤差を使って学習すること
- nステップ切断リターン（n-steps truncated return）: ↑で、1ステップではなく一般のnステップでのリターンの予測価値のこと
- 前方観測的なTD(λ)誤差（TDλ error of forward view）: 特定のnステップの予測価値のかわりに、nステップまでのリターンの平均値を考え、それのTD誤差で、
$$
\delta_{t,\lambda}\stackrel{\triangle}{=}c_{t,\lambda}-\hat{V}(s_{t})
$$
ただし、
$$
c_{t,\lambda}\stackrel{\triangle}{=}
\begin{cases}
\sum_{n=1}^{\infty}\lambda^{n-1}c_{t}^{(n)}&\quad(\lambda\in[0,1)) \\
c_{t}^{(\infty)}&\quad(\lambda=1) \end{cases} $$ かつ、λは、どれくらい奥のステップに重みを付けるかのパラメータ、1に近いほど奥のステップを重視する - ↑のラムダは1の場合はモンテカルロ推定と同じで、分散が大きく、0に近いと学習が進みにくいので、実験的に0.4-0.8くらいがよいとされている
- 前方観測的なTDλアプローチはオンライン学習には向かない。そのため、後方観測的なTDλアプローチが考えられる
- まず、TD誤差の和を過去分と未来分に分ければ、過去分は計算可能で、
$$
\displaylines{
\begin{align}
\Delta_{T}^{\text{past}}(s)&=\sum_{t=0}^{T}\delta_{t}\sum_{τ=0}^{t}\mathbb{I}_{\{(t-τ)\subset \mathcal{T}_{s}\}}(\lambda\gamma)^{τ} \\
&=\sum_{t=0}^{T}\delta_{t}\sum_{τ=0}^{t}\mathbb{I}_{\{s_{t-τ}=s\}}(\lambda\gamma)^{τ}, \quad\forall s \in \mathcal{S} \end{align} } $$ と書けるので、以下のように書き換え可能 $$ \displaylines{ \Delta_{T}^{\text{past}}(s)=\sum_{t=0}^{T}\delta_{t,\lambda}^{\text{back}}(s), \quad\forall s \in \mathcal{S} \\
\delta_{t,\lambda}^{\text{back}}(s) \stackrel{\triangle}{=} \delta_{t}z_{t,\lambda}(s) , \quad\forall s \in \mathcal{S} \\
z_{t,\lambda}(s) \stackrel{\triangle}{=} \sum_{τ=0}^{t}\mathbb{I}_{\{s_{τ}=s\}}(\lambda\gamma)^{t-τ} , \quad\forall s \in \mathcal{S} } $$ ここで、$z_{t,\lambda}(s)$ はエリジビリティ・トレース（eligibility trace）という名がついている
- まず、TD誤差の和を過去分と未来分に分ければ、過去分は計算可能で、
$$
\displaylines{
\begin{align}
\Delta_{T}^{\text{past}}(s)&=\sum_{t=0}^{T}\delta_{t}\sum_{τ=0}^{t}\mathbb{I}_{\{(t-τ)\subset \mathcal{T}_{s}\}}(\lambda\gamma)^{τ} \\
- エリジビリティ・トレースは、同じstateに直近で何回訪れたか、γは減衰率。
- 前方観測と後方観測では同じ値に収束する
- 後方観測では、前方観測と違って状態がsに来たとき以外でもすべてのステップでVを更新でき、時間遅れも発生しないのでオンライン学習では好まれる
- TD(λ)法は、エリジビリティ・トレースあり、TD法はエリジビリティ・トレースなし。TD法がTD(0)法とも言われるのは、減衰倍率であるλを0にした場合と一致するから。
- 発展系として、true online TD(λ)法もあるらしい
- ベルマン行動最適作用素（Bellman optimality mapping for action values）: state-action pairについての更新式で、 $$ \Upsilon_{*}q(s,a)\stackrel{\triangle}{=} \mathbb{E}\left\{g(s,a)+\gamma\max_{a'\in\mathcal{A}}q(S_{t+1},a')\mid S_{t}=s,A_{t}=a\right\},\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A} $$
- 近似ベルマン行動最適作用素: ↑は未知の情報が含まれて現実的に計算できないので、近似したもの
$$
\hat{\Upsilon}_{*}(q;h_{T})(s,a)\stackrel{\triangle}{=}
\begin{cases}
{\displaystyle\sum_{t=0}^{T-1}\mathbb{I}_{\{s_{t}=s\}}\mathbb{I}_{\{a_{t}=a\}}\left(r_{t}+\gamma\max_{a'\in\mathcal{A}}q(s_{t+1},a')\right)\over\displaystyle\sum_{t=0}^{T-1}\mathbb{I}_{\{s_{t}=s\}}\mathbb{I}_{\{a_{t}=a\}}}&\quad(\text{if}\displaystyle\sum_{t=0}^{T-1}\mathbb{I}_{\{s_{t}=s\}}\mathbb{I}_{\{a_{t}=a\}}>0) \\
q(s,a)&\quad(\text{otherwise}) \end{cases} $$ - 行動方策（behaviour policy）: データ収集のための方策
- 目的方策（target pocily）: データを元に最終的に計算される方策
- 方策オン型の学習（on-pocily learning）: 行動方策と目的方策が一致する学習法。SARSA法、TD(λ)法など。
- 方策オフ型の学習（off-pocily learning）: 行動方策と目的方策が一致しない学習法。Q学習法など。
Q学習法（Q learning method）: バッチ学習をオンライン学習に拡張したもので、 $$ \hat{Q}(s_{t},a_{t}):=(1-\alpha_{t})\hat{Q}(s_{t},a_{t})+\alpha_{t}\Upsilon_{*}(\hat{Q};\{s_{t},a_{t},r_{t},s_{t+1}\})(s_{t},a_{t}) $$
楽観的な初期化（optimistic initilization）: Qを最大値に初期化して探索を促進すること
- SARSA法: Q学習法のTD誤差に次ステップの行動価値を用いたもの、つまり $$ \hat{Q}(s_{t},a_{t}):=(1-\alpha_{t})\hat{Q}(s_{t},a_{t})+\alpha_{t}\hat{\Upsilon}(\hat{Q};\{s_{t},a_{t},r_{t},s_{t+1},a_{t+1}\})(s_{t},a_{t}) $$
- SARSA(λ)法: SARSA法にエリジビリティ・トレースを適用したもの
- GLIE方策: Greedy in the Limit with Infinite Exploration, 無限に探索した極限では貪欲方策と一致する方策
- アクター・クリティック法/AC法（actor critic method）: 方策(actor)と方策評価(critic)からなるエージェントが行動を決定する仕組み全般のこと。SARSA法はactorとcriticが同一であるような、AC法の特殊例ともいえる
- ↑の例：actorはソフトマックス方策、criticはTD誤差
- AC法の弱点として、モジュールが2つある事による複雑さ・調整の難しさ。特に、actorの学習がcriticよりも速くなってしまうと、適切なcriticの働きが期待できなくなってしまうので注意が必要
- AC法の長所としては、モジュールが2つなので方策の自由度が高いこと、特に行動空間が連続的な場合（ロボット制御など）に有用
ch5 モデルベース型の強化学習
- 幅優先探索（breath-first search）: 状態行動空間の探索を優先するプランニング。動的計画法やスパースサンプリング法など
- 深さ優先探索（depth-first seach）: 時間ステップ方向を優先して探索するプランニング。UCT法やモンテカルロ木探索など
- スパースサンプリング法：状態を根ノードにしてほぼ最適な行動（near optimal action）を探索する方法。計算量が状態数に依存しないため、非常に大きいor連続な空間で有効
- ↑は状態数には依存しないが、パラメータ設定としてN（幅）とT（深さ）に強く依存するので、これの設定が重要。以下のように設定すると良いことが知られている
$$\displaylines{
T=\left\lceil {\log τ_{\varepsilon,\gamma}\over \log(1/\gamma)}\right\rceil \\
N=\left\lceil {τ^{2}_{\bar{\varepsilon},\gamma}(2T\log(|\mathcal{A}|Tτ^{2}_{\varepsilon,\gamma})+\log( (1-\gamma)τ_{\varepsilon,\gamma})}\right\rceil \\
τ_{\varepsilon,\gamma}\stackrel{\triangle}{=} {4R_{\text{max}}\over \varepsilon(1-\gamma)^{3}} } $$ - スパースサンプリング法は状態が変わるたびに計算し直しが必要
- UCT法(UCB applied to Trees): 信頼区間の上限（Upper Confidence Bound）を木探索に応用したもの
- スパースサンプリング法は全ての状態で探索するが、UCTはよさげな状態を優先して探索する
- UCTの行動選択はUCB1法にもとづき、以下のように決定する $$ a_{t}:=\text{argmax}_{a\in\mathcal{A}} \left\{q_{t}(s_{t},a)+\rho\sqrt{\log{(\sum_{a\in\mathcal{A}} m_{t}(s_{t},a) )} \over m_{t}(s_{t},a)}\right\} $$
- ここでρは探索強度のハイパーパラメータで、たとえば $\rho:=R_{\text{max}}/(\sqrt{2}(1-\gamma) )$
- UCT法は有用だが、場合によっては効率が悪く、対策として同じ状態が何度も登場する場合にmやqを共有するUCT1法が提案されている
- モンテカルロ木探索(Monte Carlo tree search: MCTS)：新しいノードごとに木を作らず、木を少しずつ成長させ、根ノードのみを保持するやり方。囲碁・将棋などのゲームAIの基礎的探索法。
- ロールアウト（rollout）: 意思決定シミュレーション
- 既定方策（default policy）: ロールアウトにつかう方策。単にランダム方策であることが多い
- R-max法：未知のstate-action pairを優先して探索する方法。環境をリセットできない場合に有効
- マルコフ決定過程の直径Dとは、以下のこと $$ D\stackrel{\triangle}{=} \max_{s\neq s'\in\mathcal{S}}\min_{\pi\in\Pi}\mathbb{E}[H(s,s';M(\pi) )] $$
ch6 関数近似を用いた強化学習
- 状態数が非常に多い場合や連続の場合、正確に表現するのは困難なので近似することを考える。つまり $$ V^{\pi}(s)\simeq\hat{V}(s;\bf{\omega}^{*}) $$ となるパラメータ $\bf{\omega}^{*}$ を学習したい
- 線形関数近似器（linear function approximator）: $\hat{V}_{\omega}(s)\stackrel{\triangle}{=}\omega^{\top}\phi(s)$
- ↑においてφは、基底関数（basis function） or 特徴ベクトル（feature vector）といい、状態の特徴を表現する
- 関数近似器族（family of function approximator）: $\mathcal{V}\stackrel{\triangle}{=}\{\hat{V}_{\bf\omega};{\bf\omega\in\mathbb{R}^{d}}\}$
- これまでに登場した方法を、関数近似の考えに拡張することを考えたい
- ただし、更新則をそのまま適用すると、関数近似器族の外に出てしまう可能性があるので（？）関数近似誤差を最小化することを考える、つまり $$ \omega:=\text{argmin}_{\omega\in\mathbb{R}^{d}}\sum_{s\in\mathcal{S}}(V^{\text{target}}(s)-\hat{V}_{\omega}(s) )^{2} $$ 書き換えると $$ \min_{\omega\in\mathbb{R}^{d}}(v^{\text{target}}-\Phi\omega)^{\top}(v^{\text{target}}-\Phi\omega) $$ で、これをωについて微分してゼロになる解 $$ \omega:=(\Phi^{\top}\Phi)^{-1}\Phi^{\top}\omega^{\text{target}} $$ として求めることができる。ただし、 $$ v^{\text{target}}\stackrel{\triangle}{=}[v^{\text{target}}(1),\dots,v^{\text{target}}(|\mathcal{S}|)]^{\top} $$
- ベルマン残差最小化（Bellman residual minimization）: ↑は目的変数を固定しているのに対し、目的変数を固定せずパラメータに依存させる最適化問題 $$ \min_{\omega\in\mathbb{R}^{d}} \sum_{s\in\mathcal{S}} (\mathsf{B}\hat{V}_{\omega}(s)-\hat{V}_{\omega}(s))^{2} $$
- ただし、↑は理論上の性質は良いものの、環境が未知だと扱いが難しく、実用例は少ない
- 適合価値反復法（fitted value iteration）: これまでは、状態の数に依存した計算量の学習だったが、状態数が多い場合はこれだと都合が悪い。そこで、状態ではなく経験(s,a,r,s')の組からなる履歴データ
$$
\mathcal{D} \stackrel{\triangle}{=} \{ (s_{(1)},a_{(1)},r_{(1)},s'_{(1)}), \dots, (s_{(N)},a_{(N)},r_{(N)},s'_{(N)}) \}
$$
を使って学習する
- 手順としては、各経験の目的変数を算出し、 $$ V_{(n)}^{\text{target}}:=\hat{\textsf{B}}(\hat{V}_{\omega};\{s_{(n)},r_{(n)},s'_{(n)}\})(s_{(n)}) $$ パラメータωを更新 $$ \omega:= \text{argmin}_{\omega\in\mathbb{R}^{d}} {1\over N} \sum_{n=1}^{N} (V^{\text{target}}_{(n)} - \hat{V}_{\omega}(s_{(n)}) )^{2} $$ を繰り返す（最後の式は経験近似誤差）
- 適合Q反復（fitted Q iteration）:適合価値反復と同じ事をQに対して行う
- 手順としては、各経験の目的変数を算出し、
$$\displaylines{
\begin{align}
Q_{(n)}^{\text{target}}:&=\hat{\Upsilon}_{*}(\hat{Q}_{\omega};\{s_{(n)},a_{(n)},r_{(n)},s'_{(n)}\})(s_{(n)},a_{(n)}) \\
&=r_{(n)}+\gamma\max_{a\in\mathcal{A}}\hat{Q}_{\omega}(s'_{(n)},a) \end{align} } $$ パラメータωを更新 $$ \omega:= \text{argmin}_{\omega\in\mathbb{R}^{d}} {1\over N} \sum_{n=1}^{N} (Q^{\text{target}}_{(n)} - \hat{Q}_{\omega}(s_{(n)},a_{(n)}) )^{2} $$ を繰り返す
- 手順としては、各経験の目的変数を算出し、
$$\displaylines{
\begin{align}
Q_{(n)}^{\text{target}}:&=\hat{\Upsilon}_{*}(\hat{Q}_{\omega};\{s_{(n)},a_{(n)},r_{(n)},s'_{(n)}\})(s_{(n)},a_{(n)}) \\
- ただし、関数近似の場合は収束性が保証されていないことに注意。そのため、モデル族Vの表現力の評価基準として、真の価値関数を含むかどうかのみならず、以下の最悪ケースの関数近似誤差も評価対象とすることが多い $$ \epsilon^{*}(\mathcal{V};\textsf{B}) \stackrel{\triangle}{=} \sup_{v\in\mathcal{V}}\inf_{v'\in\mathcal{V}}{1\over|\mathcal{S}|}\sum_{s\in\mathcal{S}} (\textsf{B}v(s)-v'(s) )^{2} $$
- モデルの自由度が高ければ収束しやすいが、そのためにはデータの量が必要
- ニューラル適合Q反復（neural fitted Q iteration, NFQ）: 適合Q反復にニューラルネットワークの考え方を適用したもの
- 深層Qネットワーク（Deep Q Network, DQN）: NFQでディープニューラルネットワークモデルを適用したもの。AlphaGoなどはこれ
- 近似TD法（approximate TD method）: TD法を近似で求めたもので、以下のもの
$$
\mathbf{\omega}_{t+1}:=\mathbf{\omega}_{t}+\alpha\delta_{t}\nabla_{\mathbf{\omega}}\hat{V}_{\mathbf{\omega_{t}}}(s_{t})
$$
ただし、
$$\displaylines{
\delta_{t} \stackrel{\triangle}{=} r_{t}+\gamma\hat{V}_{\omega_{t}}(s_{t+1})-\hat{V}_{\omega_{t}}(s_{t}) \\
\nabla_{\mathbf{\omega}}\hat{V}_{\mathbf{\omega_{t}}}(s_{t}) \stackrel{\triangle}{=} \left[ \left.{\partial\hat{V}_{\omega}(s)\over\partial\omega_{1}}\right|_{\omega=\omega_{t}} ,\dots, \left.{\partial\hat{V}_{\omega}(s)\over\partial\omega_{d}}\right|_{\omega=\omega_{t}} \right]^{\top},\quad\forall s\in\mathcal{S} }$$ - このとき、ωを微小変化させたときの推定価値は $$ \hat{V}_{\omega_{t}+\Delta\omega}(s)=\hat{V}_{\omega_{t}}(s)+\Delta\omega^{\top}\nabla_{\omega}\hat{V}_{\omega_{t}}(s)+\mathcal{O}(||\Delta\omega||_{2}^{2}) $$ で、微小量に上の式を代入し、αが十分に小さければ $||\Delta\omega||_{2}^{2}\simeq 0$ なので、 $$ \hat{V}_{\omega_{t+1}}(s_{t})\simeq \hat{V}_{\omega_{t}}(s_{t})+\alpha\delta_{t}c $$ となり、従来のTD法の更新式と一致する
- 注意点として、TD法は異なる状態は更新されないが、近似TD法の場合は $$ \hat{V}_{\omega_{t+1}} ( \tilde{s} ) \simeq \hat{V}_{\omega_{t}}(\tilde{s} ) +\alpha\delta_{t}(\nabla_{\omega}\hat{V}_{\omega_{t}}(s_{t})^{\top}\nabla_{\omega}\hat{V}_{\omega_{t}}(\tilde{s}) ) $$ となり、右辺第２項が０でない限り更新されてしまう。対策として、この値と状態の類似度が近くなるようにすることで精度を向上させることができる
- 近似TD法は学習率がロビンス・モンローの条件を満たしていれば収束するが、非線形のapproximatorを使うと発散する場合がある
- 近似SARSA法の場合はapproximatorが線形の場合であっても発散する場合があり、その収束性を保証するには、方策モデルがωに対してリプシッツ連続、かつεソフト（すべての状態であらゆる行動の選択確率がε以上）であることの2つの条件を満たす必要がある
- ただし↑の場合、GLIE方策を用いるとεソフトの条件が満たせないことに注意
- 近似Q学習法の場合、以下の条件を満たせば収束性が保証される
$$
\sum_{a\in\mathcal{A}}\pi^{b}(s,a)\phi(s,a)\simeq\phi(s,\text{argmax}_{a\in\mathcal{A}}\hat{Q}_{\omega}(s,a)),\quad\forall\omega\in\mathbb{R}^{d}
$$
- 実は、$\gamma\ll 1$ であればこの条件は不要だが、強化学習タスクは多くの場合γを1に近くして学習するため、結局この条件が必要になる
- しかし、この条件を満たそうとするとQ学習法の特徴である方策オフ探索の実施が難しくなるため、事実上満たすのが不可能な条件になっている
- ベルマン残差（Bellman residual）: $$ L_{BR}(\omega)\stackrel{\triangle}{=} \sum_{s\in\mathcal{S}}\mu(s)(\hat{V}_{\omega}(s)-\textsf{B}\hat{V}_{\omega}(s) )^{2} $$
- 射影ベルマン残差（projected Bellman residual）: ベルマン残差に、射影直行作用素を適用したもの $$ L_{PBR}(\omega)\stackrel{\triangle}{=} \sum_{s\in\mathcal{S}}\mu(s)(\hat{V}_{\omega}(s)-\Gamma(\textsf{B}\hat{V}_{\omega})(s) )^{2} $$
- ↑のどちらのほうがよいかはまだ確定していないが、状態数が多い場合ベルマン残差の計算が困難なため、近似のオンライン学習では射影ベルマン残差最小化が多い
- $\underset{a\in\mathcal{A}}{\text{argmax}}$
- 射影ベルマン残差最小化は、計算量が2乗オーダーになるため、線形オーダーにするために確率的勾配法の考えを用いることがある
$$\displaylines{
\omega:=\omega-\alpha_{t}G_{t} \\
\lim_{t\to\infty}\mathbb{E}^{\pi}\left[{1\over T}\sum_{t=0}^{T}G_{t}\right]={\partial L_{\text{PBR}}(\omega)\over\partial\omega} }$$ - GTD2法：↑はそのままでは確率勾配の計算が難しい。そこで、分解して考えたもの
$$\displaylines{
\begin{cases}
\theta:=\theta+\alpha_{t}^{\theta}\{r_{t}+\gamma\phi(s_{t+1})^{\top}\omega-\phi(s_{t})^{\top}\omega-\phi(s_{t})^{\top}\theta\}\phi(s_{t}) \\
\omega:=\omega+\alpha_{t}^{\omega}\{\phi(s_{t})+\gamma\phi(s_{t+1})\}\phi(s_{t})^{\top}\theta \end{cases} }$$ - 正則化（regularization）: 近似次元数が小さすぎると偏り、大きすぎると分散するので、近似誤差の損失関数Lに、複雑化寄与度を表す $\iota:\mathbb{R}^{d}\to\mathbb{R}$ を追加したもの $$ L(\omega)+\iota(\omega) $$
- 一般に、イオタにはL2ノルムの2乗 $\iota(\omega):=\lambda\sum_{i=1}^{d}\omega_{i}^{2}$ が使われる
- ロボット制御のトルク制御など、状態が連続の場合、argmaxのような演算は困難なため避けたい。そのため、確率密度関数による方策モデルが使われる $$ \pi_{\text{normal}}(a|s;\theta)\stackrel{\triangle}{=} {1\over \sqrt{2\pi} σ(s;\theta)} \exp{\left(-{(a-\mu(s;\theta) )^{2}\over 2σ(s;\theta)^{2}}\right)} $$
- 方策勾配法：方策自体を学習対象にしたもの（ハイパーパラメータ自体も学習対象）
- 期待割引累積訪問数（expected discounted cumulative visiting number）: 状態sへの訪問回数の期待値 $$ d^{\pi}(s)\stackrel{\triangle}{=} \sum_{t=0}^{\infty}\gamma^{t} \text{Pr}(S_{t}=s\mid M(\pi) ),\quad\forall s\in\mathcal{S} $$
（※この先もch6は数ページあるが、リーマン多様体やリーマン計量などが注釈なしの前提知識として使われていて理解が追い付かないため、一旦保留）
ch7 部分観測マルコフ決定過程
- 部分観測マルコフ決定過程（partially observable Markov decision process, POMDP）: 状態を部分的にしか観測できないMDP、この本では以下の定義
$$
P\stackrel{\triangle}{=} \{\mathcal{S}, \mathcal{A}, s_{p_{0}}, p_{\text{T}}, g, \mathcal{O}, p_{o}\}
$$
- ただし、 $\mathcal{O}$ は有限観測集合で $\mathcal{O}\stackrel{\triangle}{=}\{o^{1},\dots o^{|\mathcal{O}|}\}\ni o$
- $p_{o}:\mathcal{O}\times\mathcal{A}\times\mathcal{S}\to[0,1]$ は観測確率関数で $$ p_{o}(o|\grave{a},s)\stackrel{\triangle}{=} \text{Pr}(O_{t}=o\mid A_{t-1}=\grave{a}, S_{t}=s),\quad\forall t\in\mathbb{N} $$
- 潜在変数（latent variable）: エージェントが観測できない変数。POMDPの状態sも該当。
- POMDPの条件付き独立
$$
\text{Pr}(\check{H}_{t},A_{t},R_{t},O_{t+1}\mid S_{t}, P)=\text{Pr}(\check{H}_{t}\mid S_{t}, P)\text{Pr}(A_{t},R_{t},O_{t+1}\mid S_{t}, P)
$$
を、dawidの記号(Unicode 2AEB, double tack up)で
$$
\check{H}_{t} \perp\!\!\!\perp A_{t},R_{t},O_{t+1}\mid S_{t}
$$
と書け、同様に
$$\displaylines{
\check{H}_{t} \perp\!\!\!\perp A_{t},R_{t},S_{t+1},O_{t+1}\mid S_{t} \\
R_{t} \perp\!\!\!\perp S_{t+1},O_{t+1}\mid S_{t}, A_{t} }$$ - 信念状態（belief state）$b_{t}:\mathcal{S}\times\check{H}_{t}\to[0,1]$: 状態sが直接観測できない中でも、「多分この状態じゃないかなあ」というのを確信度としての確率として表現したもの、数式で言うと $$ b_{t}(s;\check{h}_{t})\stackrel{\triangle}{=}\text{Pr}(S_{t}=s\mid\check{H}_{t}=\check{h}),\quad\forall s\in\mathcal{S} $$
- 信念空間（belief space）: 信念状態の集合 $$ \mathcal{B}\stackrel{\triangle}{=}\left\{b:\mathcal{S}\to[0,1]:\sum_{s\in\mathcal{S}}b(s)=1\right\} $$
- 信念状態もマルコフ性を持つととらえられる
- ベルマン作用素と同様に、信念状態作用素 $\Psi$ を導入すれば、以下のように書ける $$ b_{t+1}=\Psi(b_{t},a_{t},r_{t},o_{t+1}) $$ $$ (\Psi(b,a,r,o'))(s')\stackrel{\triangle}{=} {p_{o}(o'|a,s')\sum_{s\in\mathcal{S}}p_{\text{T}}(s'|s,a)\mathbb{I}_{\{g(s|a)=r\}}b(s)\over\sum_{s'\in\mathcal{S}}p_{o}(o'|a,s')\sum_{s\in\mathcal{S}}p_{\text{T}}(s'|s,a)\mathbb{I}_{\{g(s|a)=r\}}b(s)} $$
- POMDPは状態を観測できないので、以下のように方策の再定義が必要 $$ \check{\Pi}_{t}^{h}\stackrel{\triangle}{=}\left\{\check{\pi}_{t}^{h}:\mathcal{A}\times\check{\mathcal{H}}_{t}\to[0,1]: \sum_{a\in\mathcal{A}}\check{\pi}_{t}^{h}(a\mid\check{h}_{t})=1, \quad\forall\check{h}_{t}\in\check{\mathcal{H}}_{t} \right\} $$
- POMDPでも、履歴依存方策まで考える必要はなく、マルコフ方策で十分
- 信念MDP(belief Markov decision process): MDPに信念の概念を導入したもの。基本的にMDPと同様の性質を持つが、状態数が発散しうるので近似的アプローチが必須など、細部でいくつか異なる
- 信念MDPにおける価値関数 $V_{\text{b}}^{\check{\pi}}:\mathcal{B}\to\mathbb{R}$ $$ V_{\text{b}}^{\check{\pi}} \stackrel{\triangle}{=} \mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}g_{\text{b}}(B_{t},A_{t})\mid B_{0}=b,M_{\text{b}}(\check{\pi})\right] , \quad\forall b\in\mathcal{B} $$
- ↑の価値関数の最適探索をすればよい
- 信念MDPにおけるベルマン最適作用素 $\textsf{B}_{\text{b}}^{*}v(b):\mathbb{R}^{\mathcal{B}\to\mathbb{R}^{\mathcal{B}$ $$ \textsf{B}_{\text{b}}^{*}v(b) \stackrel{\triangle}{=} \max_{a\in\mathcal{A}}\left\{g_{\text{b}}(b,a)+\gamma\sum_{z\in\tilde{\mathcal{Z}}} p_{z}^{\text{ba}}(z|ba)v(\Psi(b,a,z))\right\} ,\quad\forall b\in\mathcal{B} $$
- ただし、信念空間Bは連続空間で無限の自由度を持つため、↑をそのまま計算することはできない。近似することを考える。
$$\displaylines{
\begin{align}
V_{\text{b}}^{\check{\pi}^{h}}(b)&=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}\mid p_{s_{0}}=b,P(\check{\pi}^{h})\right] \\
&=\sum_{s\in\mathcal{S}} b(s)V_{\text{b}}^{\check{\pi}^{h}}(b),\quad\forall b\in\mathcal{B} \end{align} }$$ - アルファベクトル（alpha vector）: ↑の結果が重要で、2つの関数の内積で求められることを強調し、アルファに置き換えたもの $$ V_{\text{b}}^{\check{\pi}^{h}}(b) = \sum_{s\in\mathcal{S}} b(s)\alpha(b),\quad\forall b\in\mathcal{B} $$ （※以降は難易度が高い。トピックとしてはbackup, enum, prune, point-based value iteration, point-based error minimization algorithm, sarsop法, POMCP, など）
ch8 最近の話題（2018年）
- リスク考慮型強化学習：金融ポートフォリオなど、確率はわずかだが極大のリスクが存在する場合、期待値でまぜこぜにしてこれまで登場した方法で学習すると上手く考慮できない。それの対策。
- 分布強化学習（distributed reinforcement learning）: リターン分布を推定する強化学習
- $\hat{Q}$ 学習法：最悪ケース評価
- 効用関数をexpの形にすることで端っこを持ち上げる
- 深層強化学習（deep reinforcement learning）: 深層モデルを使う強化学習
- DQN（Deep Q Network）: 行動価値関数の近似に深層モデルQを使うQ反復法
- Rainbow DQN: double DQN, prioritized experience replay, conflict q network, category DQN, noise network, N-step 切断リターンの7つの技術を組み合わせた強化学習
