強化学習の手法の分類

はじめに

MLPシリーズの強化学習を読んだのですが、各ページを追うのに必死で全体像を理解できていなかったので、復習がてら内容をまとめてみました。ただし、各章の要約をしてもつまらないので、強化学習の手法の分類方法という観点で考えています。忘れている内容があれば、適宜森村に戻って参照してください。

各手法の詳しいことに詳しく触れる訳ではありませんし、私は強化学習の門外漢なので、間違っている内容があればご指摘ください。

ざっくり分類

Notation

• S: 状態, A: 行動, R: 報酬, $\pi(a\|s)$: (確率的)方策
• 価値関数
  • (初期)状態が$s$のときに、ある方策$\pi$に従った行動をとることで得られる累積報酬の期待値

$$V^{\pi}(s) = E^{M(\pi)}[\sum_{t} \gamma^{t} R_t |S_0=s] = E^{M(\pi)}[R_0\|S_0=s] + \gamma V^{\pi}(s)$$

• 行動価値関数
  • 状態が$s$のときに、ある行動$a$をとることで得られる累積報酬の期待値

$$Q^{\pi}(s) = E^{M(\pi)}[\sum_{t} \gamma^{t} R_t |S_0=s, A_0=a]$$

方策評価と方策学習 / プランニング

まず、方策評価（Policy Evaluation）と方策学習 / プランニング（Policy Learning / Planning）に大別される。

方策評価はある方策$\pi$の価値関数$V^{\pi}(s)$を推定する。一方で、方策学習プランニングは$E[V^{\pi}(S_0)]$を最大化するような方策$\pi$を探す。

往々にして我々は最適な方策$\pi$を知りたいので、方策学習 / プランニングが重要になってくる訳だが、適切に方策学習 / プランニングを行うために方策評価も重要となる。

モデルベースとモデルフリー

環境モデルが

• 何かしらの意味で既知であることを前提とした手法をモデルベース
• 未知であることを前提とした手法をモデルフリー

な手法と呼ぶ。

方策評価にしても、方策学習 / プランニングにしても、環境モデルが既知か否かでその手法が大きく変わってくるので、このような分け方がされている。

モデルベース : 分布モデルとサンプルモデル

ところで、上のモデルベースの説明で、「何かしらの意味で」モデルが既知と書いたが、ここでのモデルは二種類に分けられる（c.f.Sutton 8章, 森村 5章）。

• 分布モデル：環境モデルの分布こと。$P[S_{t+1}|S_t, A_t], P[R_t|S_t, A_t]$が既知であるということ。

  • なお、経験分布を用いて$P[S_{t+1}|S_t, A_t], P[R_t|S_t, A_t]$を陽に推定する場合もここに入るらしい。解せないが。

• サンプルモデル：シミュレーター（ブラックボックスモデル）のこと。分布は未知だが、シミュレーションは出来る。例えば、サイコロで各目が出る確率は分からないが、サイコロは手元にある場合などを指す。

当然、分布モデルが既知ならばサンプルモデルも既知なので、前者の方が強い。

方策学習とプランニング

最初の章で方策学習 /プランニングという表記をしたが、方策学習とプランニングは用語として使い分けられているらしい（c.f.森村1.4）。

• 環境モデルから最適方策を求めることをプランニング（プランニング問題）

• 環境モデルが未知であり、データから最適方策を求めることを学習（強化学習問題）

と呼ぶ。基本的には、前者がモデルベース、後者がモデルフリーに対応していると考えて問題ないだろう（とはいえ、経験分布を使ったものモデルベース手法は強化学習問題と捉えた方がしっくりくるが）。

厳密手法か近似手法か

基本的には$V_{\pi} \in \mathbb{R}^{|\mathcal{S}|}, Q \in \mathbb{R}^{|\mathcal{S}| \times |\mathcal{A}|}$であり、状態や行動が連続ないしは非常に多いときは適切に推定できない。そこで、$V, Q$がとりうる関数族を事前に決めてしまうのが近似手法。

通常の機械学習でイメージすると（特徴量が連続値なので例としてちょっと微妙だが）、例えばニューラルネットはあらゆる関数を表現できるという点で厳密手法っぽいが、線形回帰は近似手法になっているイメージ。

バッチ学習とオンライン強化学習

• バッチ学習

  • データ（＝過去の履歴$\{s_t, a_t, r_t\}$）が既に手元にあって、そこから方策を学習していく

• オンライン学習

  • データを収集しながら、逐次的に学習していく手法のこと。

  • 最適化とかの文脈だと、データが既に手元にある場合でも、データをランダムに選んでモデルを改善していく手法のことをオンライン学習（広義にはミニバッチ学習）と呼ぶ。基本的には意味合いは一緒。

（私見）強化学習の文脈のオンライン学習だと、最適化の文脈と異なり、全てのデータ数（時間数）Tが無限にあるということも追加で仮定されている気がする。

方策オン型と方策オフ型

方策オン型と方策オフ型という分類もあった。正直、ここの理解が一番曖昧。

• 方策オン型

  • 意思決定に使っていた手法を評価し、改善していく手法

  • 私の理解では、データ$(s_t, a_t, r_t, s_{t+1})$が$M(\pi)$に従がって生成されている。ただし、$\pi$は固定されたもの。$Q^{\pi}(s, a)$とかはモンテカルロ推定で容易に計算できる。

  • 方策オン型ではエリジビリティ・トレースを用いたTD(λ)方が使えるのが大きなメリット。

• 方策オフ型

  • データを生成するのに使うものとは異なる方策を評価、改善していく手法
  • データが$M(\pi)$に従っているというよりも、$(s_t, r_t, s_{t+1})$が$M(\pi) | a_t$に従って生成されているというお気持ち。記法がおかしいのは百も承知ですが、お気持ち。要は$a_t$は何かしらの分布に従って生成されたのではなく、外生的に与えられた値であるというお気持ち。

方策学習: 行動価値手法と方策勾配法

方策学習は最適な$\pi$を選ぶものだが、そのアプローチが3つある

• 行動価値手法

  • $Q(s, a)$を推定して、そこから以下の方策モデル（c.f. 森村3章）に従って最適なactionを選ぶ。いずれにせよ、$Q(s, a)$の推定が本質的に重要。

    • greedyな手法：$\pi(a|s) = \arg \max_{a} Q(s, a)$

    • ε-greedyな手法：greedyな手法にちょっとランダムネスを足す

• 方策勾配法

  • 方策$\pi$をパラメータ$\theta$で定義し、$\theta$を更新していく。（狭義の意味での方策勾配法は）$Q(s, a), V(s)$の推定は行わない。

• アクタークリティック：方策勾配法のように、$\pi_{\theta}(a|s)$の$\theta$を更新していく。ただし、その更新に$Q(s, a)$の推定値や$V(s)$の推定値を用いる。$\theta$を更新するモジュールをアクター、$Q(s, a)$や$V(s)$の推定（更新）を行うモジュールをクリティックと呼ぶ。

行動価値手法では、$\pi(a|s) = \arg \max_{a} Q(s, a)$がベースなので、行動空間$\mathcal{A}$が離散であることが念頭にある。一方で、方策勾配法やアクタークリティックはそのような$a$の選択がないため、行動空間が連続でも対応できる。

なお、アクタークリティックと方策勾配法は必ずしも使い分けられていない印象はある。

参考

今井翔太さんが強化学習の手法をまとめたもの。https://twitter.com/ImAI_Eruel/status/1303677795806056451/photo/1