Transitive RL: 分割統治によるオフポリシーRLのスケーリング

BAIRは、**Transitive RL (TRL)**と呼ばれる新しい強化学習アルゴリズムを導入しました。これは、従来の時間的差分（TD）学習を「分割統治」パラダイムに置き換えるものです。このアプローチは、ベルマン再帰の数を線形ではなく対数的に削減することにより、オフポリシーRLを複雑で長時間範囲のタスクにスケーリングし、nステップハイパーパラメータのチューニングの必要性をなくします。

オフポリシーRLのスケーラビリティの課題

オフポリシーRLは、データ収集が高コストになるロボット工学、医療、対話システムなどのドメインにおいて重要です。これは、古い経験や人間のデモンストレーションを含むあらゆるデータを使用できるからです。ただし、現在の価値学習パラダイムの制約により、長時間範囲のタスクへのオフポリシーRLのスケーリングは依然として困難です。

  • 時間的差分（TD）学習: 従来のQ学習はブートストラッピングに依存しており、次の値 $Q(s', a')$ の誤差が現在の値 $Q(s, a)$ に伝播します。これらの誤差はホライズン全体にわたって蓄積され、スケーラビリティを妨げます。
  • モンテカルロ（MC）リターン: nステップTD学習（TD-n）は定数因子 $n$ でベルマン再帰の数を減らしますが、誤差の蓄積を根本的に解決するわけではありません。バイアスを減らすために $n$ を増やすと、しばしば高い分散と最適性の低下を引き起こし、タスクごとの慎重なチューニングが必要になります。

分割統治パラダイム

Transitive RLは、軌跡を二つの等長セグメントに分割し、それらの値を組み合わせて完全な軌跡の値を更新する第三のパラダイムを導入します。この方法は、ベルマン再帰の数を対数的に削減し、純粋なモンテカルロ法の高い分散とnステップTDのチューニング要件を回避します。

ゴール条件付きRLへの応用

TRLは、ゴール条件付きRLに特化して実装されており、ここでの目的は任意の状態から任意の他の状態に到達できるポリシーを学ぶことです。この設定は、最短経路距離 $d^*(s, g)$ の三角不等式に基づく自然な構造を提供します：

$$d^(s, g) \le d^(s, w) + d^*(w, g)$$

スパース報酬に対する価値関数 $V$ の観点では、これは「推移的」ベルマン更新規則に変換されます：

$$V(s, g) \leftarrow \begin{cases} \gamma^0 & \text{if } s=g \ \gamma^1 & \text{if } (s, g) \in E \ \max_{w \in S} V(s, w)V(w, g) & \text{otherwise} \end{cases}$$

この規則により、$V(s, g)$ の値は、最適な中点またはサブゴールである $w$ を用いて、二つの小さな値 $V(s, w)$ と $V(w, g)$ を使って更新することができます。

TRLの実践的実装

連続的で状態空間が大きい環境において分割統治型の価値学習を実用的にするため、TRLは最適なサブゴール $w$ を見つける問題に対して二つの重要な技術的解決策を採用します：

  1. 制約された探索空間: 状態空間全体を探索する代わりに、TRLは $s$ と $g$ の間のデータセットの軌跡に現れる状態に $w$ の探索を制限します。
  2. 期待値回帰: $\max$ 演算子によって典型的に引き起こされる価値の過大評価を防ぐため、TRLは期待値回帰による「ソフト」なargmaxを使用します。アルゴリズムは以下の損失を最小化します：

$$ \mathbb{E}[\ell_{2\kappa}(V(s_i, s_j) - \bar{V}(s_i, s_k)\bar{V}(s_k, s_j))] $$

ここで、$\bar{V}$ はターゲット価値ネットワークであり、$\ell_{2\kappa}$ は期待値 $\kappa$ の期待値損失であり、サンプリングされた軌跡におけるすべてのタプル $(s_i, s_k, s_j)$ （ただし $i \le k \le j$）に対して計算されます。

パフォーマンスとベンチマーク

TRLは、OGBenchベンチマークにおけるオフラインゴール条件付きRLで評価され、特に1Bサイズのデータセットと最大3,000環境ステップのホライズンを持つhumanoidmazeとpuzzleタスクの最も難しいバージョンに焦点を当てました。

  • ベースラインを上回る性能: TRLはほとんどのタスクにおいて、TD、MC、および準メトリック学習カテゴリの強力なベースラインを上回りました。
  • ハイパーパラメータチューニングの不要化: TRLは、ユーザーが $n$ の値を指定することなく、すべてのタスクにおいて個別にチューンされた最高のnステップTD学習（TD-n）の性能に匹敵しました。

今後の方向性

TRLは現在決定論的ダイナミクスを仮定していますが、BAIRは今後の開発のためのいくつかの道筋を特定しています：

  • 一般化: ゴール条件付き設定を超えた通常の報酬ベースのRLタスクへのTRLの拡張。
  • 確率性: 確率的環境と部分観測性を扱うためにアルゴリズムを適応させ、潜在的に「確率的」三角不等式を使用する。
  • 最適化: 同じ軌跡を超えたサブゴール候補選択の改善と、さらなるトレーニングの安定化。

Sources