MLエンジニアへの道 #42

この記事では、強化学習における関数近似について紹介します。

これまでの強化学習シリーズでは、独自の更新規則を持つテーブル、Qテーブルで状態行動価値を更新する手法を扱ってきました。しかし、現実的な強化学習の問題は非常に複雑で、テーブルが極めて大きくなり、メモリに収まりきらなくなります。この問題に対処するため、テーブルの項目を関数で近似することで、テーブルへの依存から脱却することができます。

関数近似

ここでの課題は、任意の関数 $\hat{q}(s, a, w)$ を、状態行動ペアと最適なポリシーに対応する状態行動価値 $q_{\pi}(s, a)$ をマッピングするテーブルに適合させることです。（あるいは、計算を容易にするために、状態を各行動のQ値（Qテーブルの行）にマッピングすることもできます。）この関数は、線形、多項式、三角関数基底を持つ線形関数でも、深層ニューラルネットワークのような非線形関数でも良いです。いずれの場合も、以下のように最小二乗誤差を用いた確率的勾配降下法（SGD）を含む様々な最適化手法を使用して関数を適合させることができます。

w_{t+1} = w_t - \frac{1}{2}\alpha \frac{\partial}{\partial w} (q_{\pi}(S_t, A_t) - \hat{q}(S_t, A_t, w_t))^2

$q_{\pi}(S_t, A_t)$ の推定値は、 $G_t$ を使用するモンテカルロ法や $R_t + \gamma \hat{q}(S_t+1, A_t+1; w)$ を使用するTD(0)など、これまで説明してきた様々な手法を用いて得ることができます。この関数近似アプローチは、特に深層ニューラルネットワークに対して有望に見えます。(深層Q学習) なぜなら、深層ニューラルネットワークは理論的には十分な重みがあれば事実上あらゆる非線形関数にマッピングできるからです。しかし、現実はそう甘くありません。

関数近似の課題

状態行動ペアに基づいてQ値を予測するような深層ニューラルネットワークを実装すると、最適ポリシーへの収束に苦労することがわかるでしょう。これは、DNNとMDPの前提と仮定の間の矛盾によるものです。第一に、最適なポリシーに対応する状態行動価値の推定値は非定常であり、新しい報酬が探索されるにつれて動的に変化します。これはDNNのデータは定常であるという仮定と矛盾します。第二に、MDPからのデータは高度に相関しており、 DNNが仮定する独立同一分布（i.i.d.）ではありません。

そのため、実践では、DNNは通常、近最適な価値関数の周りで'チャタリング'(探索によって時折損失が突然発散)したりします。毎回の反復でポリシーが改善されることが保証されないため、これまで説明してきた手法とは異なり、非線形関数近似では理論的な収束保証が失われます。

優先順位付き経験再生

データの高い相関を引き起こすTDのような逐次的アプローチの代わりに、多くの経験をバッファ（再生バッファと呼ばれる）に保存し、学習のためにバッファから経験（状態、行動、報酬、終了）のセットをサンプリングすることができます。経験再生と呼ばれるこの手法により、技術的には同じ分布からサンプリングしていると言えるため、学習がより安定します。しかし、FrozenLakeEnvironmentのように報酬がほとんどゼロの場合、学習が困難になることが観察されます。より多くの学習機会を提供できる状態行動ペアをより多くサンプリングするために、 TD誤差に基づいてペアに優先順位を割り当て、以下のように優先順位を使用してペアをサンプリングすることができます。

p = [r + \gamma Q(s', a') - Q(s, a)] + \epsilon \\ P(i) = \frac{p_i^{\alpha}}{\sum_k p_k^{\alpha}}

ここで、 $\epsilon$ は小さなTD誤差を持つデータにもサンプリングされる機会を確保するための小さな値、 $P(i)$ は $i$ 番目の経験が選択される確率、 $\alpha$ は分布の鋭さを決定するハイパーパラメータです（ $\alpha=0$ は一様サンプリングとなります）。このサンプリングに優先順位を使用する手法は 優先順位付き経験再生（PER） と呼ばれます。しかし、高いTD誤差を持つ経験のみを選択すると、モデルにバイアスがかかり過学習が起きやすくなります。そのため、以下のように重要度サンプリングの重みを勾配に掛けることで、学習のバイアスを調整する必要があります。

w_i = \bigg(\frac{1}{NP(i)}\bigg)^{\beta}

ここで、 $N$ は再生バッファのサイズ、 $\beta$ はバイアス補正の程度を決定するハイパーパラメータです。最初は高いTD誤差を持つ経験からの学習を優先するためにバイアス補正を少なくし、安定した学習の後にバイアスを補正するために徐々にバイアス補正のレベルを上げていきます（ $\beta$ を0.4から1にアニーリング）。リンクはPERの実装例です。この実装では、最も早くプッシュされた経験の優先順位は最初は最大値に設定され、TD損失の計算時に更新されます。また、優先順位はTD誤差の代わりに重み付きTD損失を使用して計算され、優先順位の $\epsilon$ は $10^{-5}$ であり、深層Q学習のための $\epsilon$ -貪欲行動ポリシーにおける減衰するepsilonとは異なることに注意が必要です。

二重Q学習

PERは学習の安定性を大きく向上させますが、上記のリンクされたコードの実装では、二重Q学習と呼ばれる別の戦略が学習をさらに安定させるために利用されていることが分かります。標準的な深層Q学習では、 $\epsilon$ -貪欲行動ポリシーと貪欲目標ポリシー、または行動の選択と評価に同じネットワークや重みを使用します。これは現在の状態行動ペアの価値を過大評価するバイアスを引き起こす可能性があります（行動ポリシーは目標ポリシーも使用する基準に基づいて最良の行動を選択するため、目標ポリシーは行動ポリシーに同意し、その行動を最良と評価するか、価値を高く設定する傾向があります）。二重Q学習は、行動の選択と評価に2つの別々のネットワークを持つことでこの問題に対処し、より公平な評価と安定した学習を提供します。

\delta = r + \gamma Q_{\text{target}}(s', \argmax_{a'} Q_{\text{behavior}}(s', a')) - Q_{\text{behavior}}(s, a)

実践では、同じ形状の2つのネットワークを使用し、目標ネットワークは凍結され、その重みは定期的に行動ネットワークの重みに一致するように更新されます。この実装では、PyTorchのload_state_dictをupdate_target内で使用し、1000反復ごとに関数を実行することでこれを行っています。 MDPに対する真のQテーブルの存在を仮定しながらの異なるネットワークの使用は、Q値の過大評価を減らし学習を安定させるためだけであるため、このアプローチを取ることは理にかなっています。

デュエリングQ学習

デュエリングQ学習は、いくつかの状態における行動の選択が報酬にあまり影響を与えないシナリオに対処します。例えば、すべての行動が追加の報酬なしでほぼ同じ状態に導く場合や、行動の選択が報酬に影響を与えない場合です。このようなシナリオでも、標準的なQ学習はすべての状態におけるすべての行動のQ値を近似するため、冗長な計算を行ってしまいます。デュエリングQ学習は、以下のようにQ値を状態価値と優位性に分解することでこれに対処します。

Q(s, a) = V(s) + A(s, a)

優位性関数 $A(s, a)$ は、状態 $s$ における平均的な行動と比べて行動 $a$ がどれだけ優れているかを測定します。価値と優位性を近似する別々のネットワークを持つことで、安定した状態価値をより効率的に学習し、一般的により安定的かつ速く学習することができます。さらに学習を安定させるために、任意の値を持つ優位性から優位性の平均を引くことができます。標準的な経験再生を用いたデュエリングQ学習の実装は、ここのリンクからアクセスできます。

結論

この記事では、強化学習における関数近似のアイデア、そのアプローチの課題、そしてこれらの課題に取り組むためのいくつかのテクニックについて説明しました。これらのテクニックは組み合わせることで、様々なシナリオに対して可能な限り安定的で効率的な学習プロセスを実現することができます。また、この記事では触れていない学習プロセスを少し容易にできる他の多くのテクニックがあるため、それらについても以下のリソースから確認することをお勧めします。

リソース

cwkx. 2022. Reinforcement Learning 7: Function approximation. YouTube.
higgsfield. 2018. DQN Adventure: from Zero to State of the Art. GitHub.
Sutton, S. R. & Barto, G. A. 2015. Reinforcement Learning: An Introduction. Carnegie Mellon University.