Offline Reinforcement Learning特集！第二弾

強化学習 2020年09月25日

3つの要点
✔️ Imporatance SamplingによるOffline Evaluation
✔️ Dynamic Programmingを用いたOffline RL
✔️ Policy constraint、Uncertainty estimationによるDistributional shiftの緩和

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
written by Sergey Levine, Aviral Kumar, George Tucker, Justin Fu
(Submitted on 4 May 2020)
Comments: Published by arXiv
Subjects: Machine Learning (cs.LG), Artificial Intelligence (cs.AI), Machine Learning (stat.ML)

はじめに

Offline RL特集第一弾では、Offline RLの全体像、応用例、そして問題点を紹介しました。本記事は前回の記事の続きの第二弾で、Offline RLの手法、その中でも特にoff-policy RLに関するものについて細かく説明をしていきます。第一弾をまだお読みではない方は、是非先に第一弾に目を通していただけると流れがよりわかりやすくなると思いますので、是非ご覧ください。

本記事で主に紹介する手法として、importance samplingを用いたpolicy(方策)のリターンやpolicy gradientを推定する手法と、dynamic programmingを用いた手法の二種類を紹介します。

Importance SamplingによるOffline EvaluationとRL

まずはじめに、policyのリターン等を直接推定する手法をベースとしたoffline RLについて調査をしていきます。本章で説明していく手法は、Impace Sampling (重点サンプリング法)を用いて、与えられたpolicyにおけるリターンを評価、もしくはリターンに関するpolicy gradientの推定などを行い学習します。最も直接的な方法としては、$\pi_{\beta}$から得られた軌跡において、importance samplingによる$J(\pi)$(目標関数)の推定で、これをoff-policy evaluationと言います。では、このoff-policy evaluationがどのような式で表され、またどのようにしてoffline RLに利用されるかを紹介していきます。

Importance SamplingによるOff-policy Evaluation

Importance samplingを使うことでoff-policyの軌跡における$J(\pi)$のunbiased estimator(不偏推定量)を求めることが出来ます。

上の式において、$w_{t}^{i}=\frac{1}{n} \prod_{t^{\prime}=0}^{t} \frac{\pi_{\theta}\left(\mathbf{a}_{t^{\prime}}^{i} \mid \mathbf{s}_{t^{\prime}}^{\mathrm{i}}\right)}{\pi_{\beta}\left(\mathbf{a}_{t^{\prime}}^{i} \mid \mathbf{s}_{t^{\prime}}^{i}\right)}$、そして$\left\{\left(\mathbf{s}_{0}^{i}, \mathbf{a}_{0}^{i}, r_{0}^{i}, \mathbf{s}_{1}^{i}, \ldots\right)\right\}_{i=1}^{n}$はn個の$\pi_{\beta}$からサンプルされた軌跡を示しています。しかし、このestimatorはimportance weight $w$をhorizon $H$にかけていくために分散が大きくなる問題があります。これを解決するために、$r_{t}$が未来の時間$t'$において$s_{t'}$と$a_{t'}$に依存しないことを利用し、未来のimportance weightを消すことができ、以下の式のように表すことが出来ます。

これにより未来のimportance weightsをかける必要がなくなるため、元の式よりも分散が低くなります。しかし、このような工夫を施しても、一般的にまだ分散が大きいとされています。ただ一つの目的として、policyのパフォーマンスに関して高い確率の保証を求めることが重要になることがあり、このimportance samplingを用いて、信頼度区間を求める研究などがなされています。特に、Offline RLの安全性が重要なアプリケーションに対しては、求めているpolicyのパフォーマンスがある一定よりも低くならないという保証（例えば事故を起こさないなど）をもった上で、行動policy $\pi_{\beta}$に対して改善していく必要があります。この安全制約が満たされていることが保証されるように、importance sampling estimatorのより低い信頼度の境界を用いてポリシーを探索する研究がなされています。

Off-Policy Policy Gradient

本章のはじめに説明したように、importance samplingを用いてpolicy gradientを直接推定することが可能で、$J(\pi)$を最適化するために、求めるpolicyのパラメーターに対するgradientを推定する方法です。このgradientはMonte Carloサンプルを用いることで推定することが出来ますが、これはon-policyの軌跡 ($\tau \sim \pi_{\theta}$)が必要になります。では、どのようにしてoffline RLに拡張することができるのでしょうか。

今までの研究では、offlineではなく、off-policyの設定、つまりbehavior policy $\pi_{\beta}(a|s)$と$\pi(a|s)$は異なるが、offlineとは違いoff-policy policy gradientでは過去に集めたデータを再利用するとともに、学習と同時に新しいサンプルをbehavior policyから得ます。本節では、off-policy gradientを紹介し、そして後にこれをofflineに拡張するためにどのような問題点、挑戦があるかを紹介します。

Policy gradientは以下のように表され、

これをimportance samplingを利用して推定すると

のように表すことができます。policy gradientを推定する場合も、前節で紹介したリターンを推定する場合と同様に未来のimportance weightを除くことが出来ます。

Approximate Off-Policy Policy Gradient

前節で説明したimportance-weighted policy objectiveにおいても、importance weightを掛け合わさないといけないため、分散が大きくなってしまいます。そこで、現在の学習しているpolicy $\pi$におけるstate分布$d^{\pi}$の代わりに$\pi_{\beta}$のstate分布を用いて$\pi$のapproximate policy gradientを求めることができます。このapproximate policy gradientも、state分布$d^{pi}$と$d^{\pi_{\beta}}$のミスマッチによりbiasがかかりますが、実際にはうまくいくことが多いことが研究でわかっています。この新しい目的関数は以下のように表されます。

$$J_{\beta}\left(\pi_{\theta}\right)=\mathbb{E}_{\mathbf{s} \sim d^{\pi} \beta(\mathbf{s})}\left[V^{\pi}(\mathbf{s})\right]$$

この$J_{\beta}(\pi_{\theta})$と$J(\pi_{\theta})$は異なるstate分布下によるものであり、$J_{\beta}(\pi_{\theta})$は$J(\pi_{\theta})$の biased estimatorとされています。biased estimatorのため、suboptimalな解が求められることがありますが、$d^{\pi_{\beta}}$における目的関数の場合は、importance samplingを利用する必要がないので、offlineにおけるデータセットからデータをサンプリングして簡単に計算することができるという利点があります。

今後のチャレンジ

本章では、importance samplingを使って、現在のpolicy $\pi_{\theta}$に関する最終的なリターン、もしくはリターンの勾配を推定する手法を紹介しました。ただし上で紹介したpolicy improvementは基本的にoff-policy learningのためのもの、つまり過去に集められたサンプルと、更に学習と同時に新たに集めたサンプルの両方を使って学習するためのものです。そのためoffline RLの場合は、基本的にあまり利用することが出来ないのが現状です。ではoffline RLに利用するためには、どのような問題を解決していかなければならないのでしょうか。まずひとつに、importance sampling自体が分散の大きいために、offlineデータを集めるのに利用されたbehavior policy $\pi_{\beta}$が現在のpolicy $\pi_{\theta}$から離れすぎていると、importance samplingによる推定が悪くなり、特に高次元のstateやactionの空間もしくは、long-horizonな問題において分散が大きくなりすぎるという問題があります。よって、$\pi_{\theta}$は$\pi_{\beta}$に対して離れすぎないという条件が必須です。よってimportance samplingを利用した手法だと現状、suboptimalな$\pi_{\beta}$を利用する、低次元のstate/action空間、また比較的短いhorizonのタスクに限られています。

Dynamic ProgrammingによるOffline RL

Q-learnngのようなDynamic Programmingを利用したアルゴリズムの方が、基本的にpolicy gradientを利用したものよりも、Offline RLにとってより良いとされております。Dynamic programmingによるアルゴリズムはstate value functionもしくはstate-action value functionを学習し、optimal policyを導出するもので、actor-criticの場合はvalue functionを利用してpolicy gradientを推定します。Dynamic programmingを利用したoffline RLに関する研究は今までにいくつかあり、代表的なものとしては、500,000のgraspingに関するofflineデータを元にQ-learningで学習する手法QT-Optが挙げられます。しかし、この手法も新たに学習と同時に追加のデータを利用したほうが精度が向上することが分かっています。だだし、データセットによってはoffline RLでも良い結果を出すことを示した研究などもされています。

しかし、online data collectionが行われない場合、offline RL特集第一弾でも紹介したようにdistribution shiftによって良い結果が出ないことが分かっています。これを解決する方法としては大きく２つあり、一つはpolicy constrantと呼ばれるもので、学習されるpolicy $\pi$をデータを集めるのに利用されたpolicy$\pi_{\beta}$に近づけるというものです。もう一つは、uncertainty-based methodと呼ばれるもので、Q-valueの不確かさを推定し、それを利用することでdistribution shiftを発見するという手法です。本節では、はじめにdistribution shiftについて詳しく説明するとともに、この２つの手法について紹介し、最終的にどのような問題を解決していかなければならないのかを説明します。

Distribution Shift

Offline RLで問題となるdistribution shiftは二種類あり、一つはstateに関するdistribution shift (visitation frequency)、そしてactionに関するdistribution shiftです。Stateのdistribution shiftは、offline RLで学習されたpolicy $\pi$がテスト時に評価される際、学習されたpolicyに関するstate visitation frequency $d^{\pi}(s)$とbehavior policy $\pi_{\beta}$のstate visitation frequency $d^{\pi_{\beta}}(s)$が異なった場合、未知のstateにおいてactor-criticによって学習されたpolicyが予期せぬactionを出力してしまうことがあります。このstateに関するdistribution shiftはテスト時において問題となるものですが、逆にactionに関するdistribution shiftは学習時に問題となります。これは、以下のtarget Q-valueを計算するためには$Q(s_{t+1}, a_{t+1})$を計算する必要があり、これは$a_{t+1} \sim \pi(a_{t+1}|s_{t+1})$に依存しているため、仮に$\pi(a|s)$が$\pi_{\beta}$から大きく離れてしまっている場合、誤差が大きいtarget Q-valueが出力されます。

そして、例えばpolicyがQ-functionが誤差によりとても大きい値を出力してしまうようなもとで、未知のactionを出力することができるならば、policyはそのactionを実行するように学習してしまいます。本来online RLではこのような自体に陥っても新しいデータを取得することでQ-functionを正していくことが出来ますが、offline RLではそれが不可能なので、問題となっています。

ただデータを増やすだけで良いのかというとそのような問題でもありません。下図は、横軸がgradient update、縦軸が左が最終的な平均リターン、右がlogスケールのQ-valueを表しています。下図の左の緑のラインを見る限り、一度パフォーマンスが上がり、そして学習を続けていくことで下がっていくことからoverfittingのように見えますが、これはオレンジのデータがより少ないのと比べてたとき、データを増やしたからと言ってoverfittingが解決されたわけではないので、より問題を複雑にしています。またQ-valueに関しても学習が進むごとに、target Q-valueのエラーが大きくなっていきQ-function全体が悪くなっていきます。このようにactionに関するdistribution errorがoffliine RLを用いて効果的にagentを学習するには重要だということが言えます。では、次にその解決方法の一つであるpolicy constraintについて紹介します。

Policy Constraints

Actionに関するdistribution shiftを防ぐために、policy constraintによって$\pi(a|s)$と$\pi_{\beta}(a|s)$を近づけ、未知のactionを実行しないようにすることが一つの有効な方法です。未知のactionが実行された場合、一度予期せぬactionを実行することによるその後もエラーが続くことになり、エラーの積み重ねが起きてしまいますが、未知のactionが実行されない場合はエラーの積み重ねを防ぐことができます。ではどのようにpolicy constrantを行うのでしょうか。本記事では、explicit f-divergene constraints、implicit f-divergence constraints (主にKL-divergence)、そしてintegral probability metric (IPM)と呼ばれる手法について紹介していきます。また、constraintは基本的にactorの更新に対して直接制約をかけるpolicy constraintsと、報酬関数やtarget Q-valueに制約をかけるpolicy penaltyの二種類があります。

まずはじめに、policy constraintsについで紹介します。policy constraints付きのpolicy interation methodは以下の目的の反復最適化を含んだfixed point iteration (不動点反復)として表すことが出来ます。

$$\pi_{k+1} \leftarrow \arg \max _{\pi} \mathbb{E}_{\mathbf{s} \sim \mathcal{D}}\left[\mathbb{E}_{\mathbf{a} \sim \pi(\mathbf{a} \mid \mathbf{s})}\left[\hat{Q}_{k+1}^{\pi}(\mathbf{s}, \mathbf{a})\right]\right]$ s.t. $D\left(\pi, \pi_{\beta}\right) \leq \epsilon$$

これは基本的に一般的なactor-criticの手法に対してconstraint $D\left(\pi, \pi_{\beta}\right) \leq \epsilon$を追加したものです。この$D$に関しては過去にいくつかの研究で異なるものを選んだ上での実験などが行われています。このようにactorのupdateに関して制約を加えたものをpolicy constraintといいます。

では、次にpolicy penaltyについて紹介します。Actor-criticにおいて、constraintはQ-valueに対して加えられ、policy $\pi$が$\pi_{\beta}$から離れすぎずかつ、未来に$\pi_{\beta}$から離れるようなactionを選ぶことを防ぐようにします。これは、報酬関数に対してpenalty $\alpha \mathcal{D}(\pi(\cdot|s), \pi_{\beta}(\cdot|s))$を追加する、つまり$\bar{r}(\mathbf{s}, \mathbf{a})=r(\mathbf{s}, \mathbf{a})-\alpha D\left(\pi(\cdot \mid \mathbf{s}), \pi_{\beta}(\cdot \mid \mathbf{s})\right)$とすることで可能となります。また、その他にもconstraint$\alpha D\left(\pi(\cdot \mid \mathbf{s}), \pi_{\beta}(\cdot \mid \mathbf{s})\right)$をtarget Q-valueに直接追加する手法も提案され、以下の式で表すことが出来ます。

では次に、constraintの種類について紹介します。まずはじめにexplicit f-divergence constraintsに関してです。全ての凸関数$f$において$f$-divergenceは以下のように定義されます。

KL-divergence, $\chi^{2}$ -divergence, total-variance distanceなどがよく使われる$f$-divergenceの一種です。では次にimplicit $f$-divergence constraintsを紹介します。

Implicit $f$-divergence constraintsはAWRやABMなどモデルに使われており、以下の手順でpolicyを学習させていきます。

上の最初の式は、importance sampling weight $\exp \left(\frac{1}{\alpha} Q_{k}^{\pi}(\mathbf{s}, \mathbf{a})\right)$を用いて$\pi_{\beta}(a|s)$に関するサンプルに対して重み付けし、KL-divergenceを用いたregressionの問題を解くことにより、次のpolicyを決定します。ここで$\alpha$はラグランジュ乗数を表します。この手法に関する導出に関してはこちらから確認することが出来ます。

では最後にIntegral probability metrics (IPMs)を紹介します。これは、divergenceを測定する事ができる以下の式で表されるようなもので、$D_{\Phi}$は関数クラス $\Phi$に依存します。

例えば、関数クラス$\Phi$が、reproducing kernel Hilbert space (RKHS)である場合、$D_{\Phi}$はmaximum mean discrepancy (MMD)を表します。このMMDを利用した手法はBEARと呼ばれる手法で利用されています。

ではどのようにconstraintを選べばよいのでしょうか。基本的にKL-divergenceやその他$f$-divergenceはoffline RLにあまり適していないとされています。例えば、behavior policyが一様にランダムな場合、KL-divergenceによりpolicyがbehavior policyに近づくようにするため、とてもstochasticなsuboptimal policyになってしまいます。それに対し、policy $\pi(a|s)$のsupport (台)をbehavior policyの台に対して制限することによってoffline RLにとってより効果的であるという研究があります。下図の1-D Lineworld Environmentの例を見てみましょう。この例ではStart $S$から出発してGoal $G$に向かうというもので、Behavior policyは(b)のように左への遷移の確率が高い場合を想定しています。この場合distribution-matchingを行う(KL-divergence等)場合、左への遷移の確率が高いbehavior policyとのmatchingを行うことから、最適なpolicyを見つけることが出来ません。それに対して、support-constraintを利用することで、最適なpolicyを見つけることができるとされています。このsupport constraintは、上で紹介したMaximum Mean Discrepancyを使ったconstraintにより可能となり、distributionに関する制約だけではなく、supportに関する制約と似たような働きが行われることが過去の研究で実験的に示しています。

Uncertainty Estimation

では、次にpolicy constraintとは別の方法でdistribution shiftに対応するuncertainty estimationに関する手法を紹介します。これは、仮にQ-functionの不確かさを推定できる場合、未知のactionに関する不確かさが大きくなることから、その不確かさを利用してconservative (保守的)なtarget Q-valueを出力するというのが主な概要です。この手法は、$\mathcal{P}_{\mathcal{D}}\left(Q^{\pi}\right)$で表されるQ-functionにおける不確かさの集合もしくは分布を学習しなければなりません。そしてもし、この不確かさの集合を学習することが出来た場合、conservativeなQ-functionの推定を行うことで、policyを改善することが出来ます。この式は以下のように表され、$Unc$はuncertaintyを表しており、これを実際のQ-valueの推定値から引きます。

この$Unc$を計算する方法として主なものは、Q-functionのアンサンブルを行う方法、もしくはworst-caseのQ-valueの最大化を行ったものなどがあります。

今後のチャレンジ

本章で説明したように、approximate dynamic programming algorithmはoffline settingでは、主にactionに関するdistributional shiftによりパフォーマンスが低い結果となっており、policy constraintとuncertainty estimationの二種類の解決策を紹介しました。しかし、現状uncertainty estimationを利用した手法はpolicy constraintを利用した方法よりも良いパォーマンスを出していませんが、offline RLにおいて特に保守的にactionを実行するような必要がある場合 (事故を防ぐ等など)、このuncertainty estimationを利用したものが特に重要になってくるため、今後も改善が必要となっています。それに対し、policy constraintは、ある程度良いパフォーマンスを見せていますが、policy constraintを利用したアルゴリズムのパフォーマンスは、behavior policyの分布に学習しているpolicyの分布を近づけることから、behavior policyの推定の精度に依存します。つまり、仮にbehavior policyがマルチモーダルな動きを見せた場合、behavior policyを正確に推定することは困難であり、現実世界の問題に対して応用することは現状難しいとされています。また、仮にbehavior policyを完璧に推定することが出来たとしても、function approximationによる影響によって、学習が進まないこともあります。例えば、データセットが小さい場合は、小さいデータセットに対してoverfittingする可能性があり、また仮にaction-state分布がとても狭い場合、学習されたpolicyは汎用性の引くpolicyになってしまいます。そして何よりも、online RLではoverestimationによるエラーは新しいデータを集めることで解決されますが、　offline RLでは、そのエラーが積み上がってしまう問題があります。そしてその他の問題としては、学習しているpolicyが一度behavior policyから離れてしまうと、それに伴って学習が進むごとにより離れていってしまい、未知のstateに学習されたpolicyが訪れることが多くなるのでそれによるパフォーマンス位の悪化が起こります。そのためpolicy constraintを強く掛ける必要がありますが、そのようにするとpolicy improvementが制限されてしまします。よって今後考えていく必要があるのは、エラーが積み重なる問題点とsuboptimalなpolicyが学習されてしまう問題の間で効果的にトレードオフを行うようなconstraintを探すことが一つ挙げられます。

まとめ

本記事では、Model-free RLにおけるOffline RLの手法、問題点などを紹介しました。様々な手法が提案されているため、全ては紹介することは出来ませんが、全体像をこの記事にて掴んで頂くことにより、今後論文を読むにあたって役立てば幸いと思っています。現状、offline RLには様々な問題があり、パフォーマンス自体も良くないので今後の動向に注視したいとともに、action distribution shiftの問題などが果たしてofflineのデータセットのみから本当に解決可能なのかはとても気になってくるところです。