Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

技術要約：非単調包含による非凸スパース強化学習

問題提起
強化学習（RL）は、高次元の状態空間においてQ関数を近似する際、「次元の呪い」に直面することが多い。線形関数近似は標準的な解決策であるが、近似精度と計算複雑性の間のトレードオフが生じる。特徴量選択のためのスパースモデリングによる特徴量選択は、計算量を軽減するための一般的な戦略であるが、従来の$\ell_1$ノルム正則化（例：LARS-TD、$\ell_1$を用いたLSTD）に基づく手法は、推定バイアスを伴い、振幅の大きい成分を系統的に過小評価してしまう。さらに、データが固定されておりノイズが含まれる可能性があるバッチRLの設定では、無関係な特徴量や外れ値に対するロバスト性が極めて重要である。スパース回帰においてバイアスを軽減するためにMinimax Concave（MC）ペナルティのような非凸ペナルティが提案されているが、その適用は、最適化問題の非凸性が標準的な演算子分割法の収束保証に必要な単調性の仮定を崩してしまうため、強化学習への適用については未開拓のままである。

手法
本論文は、Projective Minimax Concave（PMC）ペナルティをLSTDの定式化に統合した、強化学習のための新しいバッチ特徴量選択アルゴリズムを提案する。

1. 問題の再定式化： 著者らは、最小二乗時間差誤差をPMCペナルティで正則化した最小二乗時間差誤差を最小化する不動点探索問題として、方策評価問題を定式化する。標準的なLSTDとは異なり、この目的関数は非凸である。
2. 演算子分割： PMCペナルティの弱凸性を利用することで、この不動点問題を、単調リプシッツ演算子とハイポモノトーン（hypomonotone）演算子の和の零点を求める問題へと再定式化する。これにより、問題は非単調包含のクラスに位置付けられる。
3. アルゴリズムによる解法： 著者らは、この包含問題を解くためにForward-Reflected-Backward Splitting（FRBS）法を採用している。主要な技術的貢献は、ハイポモノトーン部分のレゾルベント（resolvent）に関する閉形式の表現（ソフト収縮演算子を含む）を導出したことであり、これにより補助変数を用いることなくアルゴリズムを扱いやすくしている。
4. ハイパーパラメータ・チューニング： 本手法は、PMCペナルティによるデバイアス効果が限定される部分空間$M$を制御する調整可能なハイパーパラメータ$q$を導入している。これは、元のPMCの定義を一般化したものであり、入力グラム行列の正の固有値が非常に小さい場合でも、ペナルティの性能を最適化することを可能にする。

主な貢献
本論文には主に4つの貢献がある。

• RLアルゴリズム： 非凸のPMCペナルティをLSTDに組み込んだ、効率的なバッチ特徴量選択手法を導入している。これは、$\ell_1$正則化手法に内在する推定バイアスに対処するものである。
• 理論的拡張： FRBS法の収束解析を、より広範な非単調包含問題へと拡張した。具体的には、以下を確立している：
  • リアプノフ安定性： 緩やかな条件下で、反復列は準Fejér単調であることが示され、極限点の存在と安定性が保証される。
  • 厳密な収束： 弱Minty変分不等式（MVI）の仮定の下で、系列が解に厳密に収束することが証明されている。
• 一般化されたPMCペナルティ： 部分空間$M$を、零空間の直交補空間に固定するのではなく、調整可能なパラメータ$q$によって制御できるようにすることで、PMCペナルティを一般化した。これにより、不良設定（ill-conditioned）の設定における性能低下を防いでいる。
• 誤差境界： 提案された近似方策反復（API）スキームによって生成される方策の誤差境界が提供されており、近似誤差とQ関数の推定誤差との関連性が示されている。

結果
数値テストは、50状態のチェインウォーク、マウンテンカー、およびアクロバットの3つのベンチマークRLタスクを用いて実施された。提案手法は、LSTD、LARS-TD、およびBasis Pursuit Denoising（BPDN）を含む最先端のバッチ特徴量選択手法と比較された。

• 性能： 提案手法は、特に多数のノイズを含む、あるいは無関係な特徴量が存在するシナリオにおいて、競合手法を大幅に上回る性能を示した。マウンテンカーとアクロバットのタスクにおいて、最も高い成功率と、目標到達までの平均ステップ数の少なさを達成した。
• バイアス軽減： 結果は、提案手法が$\ell_1$ノルム正則化に伴う推定バイアスを効果的に軽減し、より正確なQ関数推定を実現していることを示した。
• ハイパーパラメータの感度： 50状態のチェインウォークの実験により、ハイパーパラメータ$q$が性能に大きく影響することが示された。適度な範囲の$q$において最小の正規化平均二乗誤差（NMSE）が得られた一方で、極端な値では、デバイアスが不十分になるか、あるいはペナルティがバイアスのある$\ell_1$ノルムを近似するように強制されることにより、性能が低下した。

意義
本論文は、収束性の懸念から非凸ペナルティの適用が避けられてきた領域において、非凸ペナルティを強化学習に適用するための厳密な理論的基礎を提供すると主張している。FRBSの非単調設定における収束保証を確立することで、本研究は非凸スパースモデリング理論と実用的な強化学習への応用との間の溝を埋めるものである。著者らは、提案手法が凸正則化に代わる堅牢な選択肢を提供し、理論的な収束保証を損なうことなく、高次元かつノイズの多い環境において優れた特徴量選択と方策性能を実現すると断言している。本研究は、弱MVI仮定の下での完全な収束証明と広範な数値検証を提供することで、予備的な会議論文の内容を拡張したものである。