この記事は強化学習苦手の会 Advent Calendar 2020の5日目の記事です。サクサク行きましょう。
追記 2020.12.16
Actor-Criticの式が思った通りに伝わらなさそうなので、以下のように書き直しました。
（修正前）$\nabla_{\theta} \mathcal{L}_{\theta}= - \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T} { \nabla_{\theta} \log \pi_{\theta}\left(\hat{y}_{t+1} \mid \hat{y}_{t}, S_{t} \right) \left( r(\hat{Y}) - V_{\Psi}\left( S_{t} \right) \right)}$
（修正後）$\nabla_{\theta} \mathcal{L}_{\theta}= - \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T} { \nabla_{\theta} \log \pi_{\theta}\left(\hat{y}_{t+1} \mid \hat{y}_{t}, S_{t} \right) \left( Q(S_{t}, y) - V_{\Psi}\left( S_{t} \right) \right)}$
ここではひとまず、$V_{\Psi}$をCriticのモデルにしてQ値を求めている文献[167] Learning to Decode for Future Success (ArXiv)に沿って定式化しました。
しかし、Actor-Criticは色々な設定があるようでして、$V_{\Psi}$でなくて$Q_{\Psi}(s,a)$で定式化していたり、ひとつのモデルでVとQを両方予測別々に予測してたり、個別に別の構造・パラメータでモデル化してたりしているようです。
例えば、 文献[39] An Actor-Critic Algorithm for Sequence Prediction (ICLR2017) はDQNのように、各行動に対するQ値を出力するCriticです。アドバンテージ関数$A(s,a)$の最大化の問題ではなくQ値の最大化の問題として定式化しているため、状態価値関数$V$は出てきません。
ちなみに、上の（修正前）の方は、CriticをREINFORCEのbaselineとして使っているということで、文献[39]では”REINFORCE-Critic”と呼ばれていました。論文の報告によると、機械翻訳タスクでのBLEUはActor-Criticと遜色ないとのことでした。（収束はActor-Criticが数倍早い模様です）
追記 2020.12.16
「Memory bufferによるoff-policy化」を「Memory bufferによるCriticの学習の工夫」と変更しました。off-policy化という話はサーベイ論文で言われている内容をまとめたものでしたが、Criticのみのoff-policy化ということもあり、on-policy, off-policyの境界は私には闇が深そうなので触れるのをやめました・・・伝えたいのはMemory bufferに突っ込んで時系列情報の相関を無くすことが言えれば十分なので。
（追記分おわり）
目次
免責事項：載せている式は論文からの引用ではなく、自分の理解で書いたものが含まれますので、サーベイ論文の紹介と言っても論文の内容をそのまま写しているわけではありません。気になるところがあれば原論文をご確認することを勧めます。
言語生成の強化学習 弐ノ型 「Actor-Critic」
さて、前回の記事でREINFORCEによる言語生成を紹介しました。REINFORCEの問題点は、サンプリングを行うことにより近似する行動価値の分散が大きくなりがちで、学習に悪影響を及ぼすことです。REINFORCEの派生手法であるSelf-Criticは、生成系列にgreedy searchを用いてベースラインとすることでサンプルの分散の影響を減らそうとしていました。
Actor-Criticでは、新たにCriticと呼ばれるモデルを導入として、ベースライン（現在の状態における平均的な価値、つまり状態価値）を直接推定します。
方策$\pi$におけるAdvantarge関数（行動価値関数から状態価値関数を引いたもの）を以下のように定めると、
$A\left(s_{t}, a_{t}\right)=Q \left(s_{t}, a_{t}\right)-V\left(s_{t}\right)= \ r_{t}+\gamma \mathbb{E}_{s_{t^{\prime}} \sim \pi\left(s_{t^{\prime}} \mid s_{t}\right)}\left[V\left(s_{t^{\prime}}\right)\right]-V\left(s_{t}\right)$
と書けます。$V\left(s_{t}\right)$がこのときの新しいベースラインになるCriticで、学習パラメータを$\Psi$として$V_{\Psi}\left(s_{t}\right)$と書くと、言語生成の強化学習におけるActor-Criticの式は、前回のREINFORCEと形式を合わせて以下のようになります。
REINFORCE
$\nabla_{\theta} \mathcal{L}_{\theta}= - \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T} { \nabla_{\theta} \log \pi_{\theta}\left(\hat{y}_{t+1} \mid \hat{y}_{t}, S_{t} \right) \left( r(\hat{Y}) - r_b \right)}$
Actor-Critic
$\nabla_{\theta} \mathcal{L}_{\theta}= - \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T} { \nabla_{\theta} \log \pi_{\theta}\left(\hat{y}_{t+1} \mid \hat{y}_{t}, S_{t} \right) \left( Q(S_{t}, y) - V_{\Psi}\left( S_{t} \right) \right)}$
（ただし、$S_{t}=(s_{t+1}, c_{t})$とした）
（ちなみに）論文中ではこのように載ってます。
ここでいくつか疑問があります。
$c_{t-1}$は文脈ベクトルで、状態の中に入ると思います（でも論文だと入ってなくて$A_{\Psi}\left(s_{t}, y_{t}\right)$になってるのが謎）
推論時に$A_{\Psi}$を使っているが、行動価値関数に対応する情報は保持してないからこれできなくない？
以上です。これについては後日確認して追記します。（力が尽きてる・・・）
さて、Criticは新しく追加されたモデルなので、学習する必要があります。これには状態$S^{(i)}$と、その状態$S^{(i)}$からエピソード終了までの累積報酬$v^{(i)}$の組$\left(S^{(i)}, v^{(i)} \right)$による教師あり学習(TD学習)で学習することができます。（$i$は組のサンプル番号）
$\mathcal{L}(\Psi)=\frac{1}{2} \sum_{i} \left|V_{\Psi}\left(S^{(i)} \right)-v^{(i)}\right|^{2}$
言語生成の強化学習では、（おそらく）即時報酬が無い、かつ時間による価値の割引も無い設定です。よって、エピソードの状態系列が$S_1, S_2, \ldots, S_T$、その時の報酬が$r(\hat{Y})$だとすると、以下のような感じになりそうです。
$(S^{(1)}, v^{(1)}) = (S_1, r(\hat{Y}))$,
$(S^{(2)}, v^{(2)}) = (S_2, r(\hat{Y}))$,
$\ldots$,
$(S^{(T)}, v^{(T)}) = (S_T, r(\hat{Y}))$
Memory bufferによるCriticの学習の工夫
上のように作成されるサンプル$\left(S^{(i)}, v^{(i)} \right)$は、方策（Actor model）に従い時々刻々と生成された系列です。
時々刻々と生成された系列を利用して得られたサンプル同士は相関を持っていてCriticの学習に悪影響を与える問題があります。
この相関を消すために、memory bufferを用意して、得られたサンプルをこのbufferに突っ込んでいき、学習時はbufferからランダムに抽出したサンプルを利用するという工夫がよく行われるようです。
Experience replayの名前でよく知られた手法かなと思います。
Actor-Criticの強み
REINFORCEと比べると、ベースラインを推定することで系列のサンプリングにより近似的に求める行動価値の分散を小さくできる点が優れているのかと思います。この点のモチベーションはSelf-Criticと同じですが、差がどのようになるかは気になるところです。
他にもMLP強化学習（青本）だと、次のような利点が紹介されています。
クリティックとアクターが分かれていることで、さまざまな関数近似器を方策モデルに用いることができる
確率的方策をそのランダム性も含めて学習できる
今週は学会でかなり消耗したので、これくらいでギブアップです。
次回はActor-Criticを用いたDeep Q-learningを使う話を書こうかと思います。
実はサーベイ論文の後ろの方にももう少しActor-Criticの話があったので、後日追記するかもしれません（ということで、タイトルに①をつけておきました）
