Q-learningはまだスケーラブルではない
(seohong.me)- RLはGo・ChessやLLMの事後学習で大きな成果を上げてきたが、その多くは新しいロールアウトを必要とするオンポリシーRLに依存しており、過去のデータを自由に再利用できるオフポリシーRLとは条件が異なる
- 代表的なオフポリシーRLであるQ-learningはサンプル効率が高いが、100以上の意味ある意思決定ステップを要する長期課題では、まだ十分にスケールしていない
- ボトルネックは、TD学習のバイアスのあるブートストラップターゲットがhorizonが長くなるほど累積する点にあり、これは次トークン予測・拡散モデル・対照学習とは異なる制約である
- OGBench実験では、flow BC、IQL、CRL、SAC+BCは、一般的なオフラインRLデータセットより1000倍大きい1Bデータセットでもすべての長期課題を解けず、性能は最適水準より低いところで頭打ちになった
- n-step returnsや階層型RLのようなhorizon reductionはスケーラビリティと最終性能を改善したが、現行手法は問題を定数倍だけ緩和するにとどまり、任意に複雑な長期課題を解くには不十分である
RLスケーラビリティの現在地
- 次トークン予測、denoising diffusion、対照学習は、大規模データと数十億パラメータのモデルにおいてスケーラブルな目的関数であることを示している
- RLもGo・Chessで超人的性能を達成し、LLMでは数学・コーディングのような複雑な推論課題を解いている
- ただし現在の実際の成功事例の大半はオンポリシーRLアルゴリズムに基づいている
- 代表例はREINFORCE、PPO、GRPOなど
- 現在の方策から新たにサンプリングしたロールアウトが常に必要
- 過去のデータを再利用できない
- PPO系の手法は限定的にデータを再利用できるが、OpenAI文書のような分類に従えばオンポリシーRLと見なされる
- ボードゲームやLLMのようにロールアウトを安価に大量生成できる環境では、この制約は大きな問題ではないかもしれない
- ロボティクスでは、RLで言語モデルを事後学習するときに使う水準のサンプルを現実世界で生成するには数か月以上かかり、学習中のロボットのリセットのために人が24時間付き添う必要がある
オフポリシーRLとQ-learning
- オフポリシーRLは原理的に、いつどのように収集されたデータでも利用できる
- 同じデータを何度も再利用できるため、一般にサンプル効率が高い
- 実環境で犬型ロボットを最初から20分で歩かせる訓練に成功した例もある
- 関連事例: walk in the park
- Q-learningは最も広く使われているオフポリシーRLアルゴリズムである
- 実用的なモデルフリーのオフポリシーRLアルゴリズムの大半はTD損失の変種に基づいている
- RLをより多くの実世界問題に適用するには、「Q-learning、すなわちTD learningはスケーラブルか」が中核的な問いになる
- もし可能なら、ロボティクスやコンピュータ使用エージェントのような、より多様で複雑な実世界課題を効率よく解ける
「スケーラブル」の意味: 幅ではなく深さ
- ここでいうスケーラビリティとは、十分なカバレッジを持つデータ、計算資源、時間をさらに投入したとき、より難しく、より長いhorizonの問題を解ける能力を指す
- これは単一モデルでより多くの数の課題を解く能力とは異なる
- 課題数が増えることが、必ずしもより難しい課題を解けることを意味するわけではない
- 多くの既存のscaling研究は、この「幅(width)」軸での可能性を示している
- より重要で難しい軸は**深さ(depth)**である
- より高度な意思決定能力が求められるためである
- 現在の形のQ-learningは深さの軸では高くスケールしない
- 複雑な長期問題へQ-learningとオフポリシーRLを拡張するには、アルゴリズム上のブレークスルーが必要である
大規模RL成功事例から抜け落ちているQ-learning
- 多くの実際のRL成功例は、TDベースのQ-learningではなく別の方法に基づいている
- AlphaGo、AlphaZero、MuZeroはモデルベースRLとMonte Carlo tree searchを使っており、ボードゲームではTD learningを使わない
- 参考: MuZero 論文15ページ
- OpenAI FiveはDota 2でPPOにより超人的性能を達成した
- 参考: OpenAI Five 論文脚注6
- LLM向けRLは現在、PPOやGRPOのようなオンポリシー方策勾配系が支配的である
- AlphaGoやLLMに近い規模で、オフポリシーRL、特に1-step TD learningが成功した実例は示されていない
- この評価はオフポリシーRLを否定するものというより、RLアルゴリズム研究がさらに必要だという問題意識に近い
長期課題でQ-learningが揺らぐ理由
- Q-learningのTD損失は、現在のQ値を報酬と次状態の最大Q値を足したターゲットに合わせるよう学習する
- このターゲットは、実際の最適Q値と一致しない可能性があるバイアスのあるブートストラップターゲットである
- Q-learningがスケーリングに苦しむ主因は、予測ターゲットのバイアスがhorizonに沿って累積することにある
- このバイアスの累積はTD learningの根本的な限界として働く
- 次トークン予測、denoising diffusion、対照学習のような目的関数には、このような予測ターゲットのバイアスはない
- BYOL、DINOは仮にバイアスがあっても、horizonに沿って累積はしない
- 問題が複雑になりhorizonが長くなるほど、ブートストラップターゲットのバイアスはより深刻に蓄積する
- より多くのデータやより大きなモデルだけでは、この問題を容易には緩和しにくい
- 実際、より大きい割引率である (\gamma > 0.999) がほとんど使われない主な理由もこれと関係している
- 方策勾配法はこの問題の影響を比較的受けにくい
- GAE のようなオンポリシー価値推定手法は、より高い分散を受け入れる代わりに長いhorizonを比較的扱いやすい
- 厳密な1-step再帰に縛られない
OGBenchベースのスケーラビリティ実験
- 最近の論文 Horizon Reduction Makes RL Scalable は、さまざまな制御されたscaling研究で上記の仮説を検証している
- 目的は、現在のオフポリシーRL手法がデータと計算資源を増やすだけで非常に難しい課題を解けるかを確認することにある
- 実験には OGBench の複雑で、これまで解かれていなかった課題を用いる
- 課題の要件は次のとおり
- エージェントは構造化されていないランダムなplay-styleデモから複雑なgoal-reaching行動を学習しなければならない
- テスト時には精密操作、組み合わせ的パズル解決、長期ナビゲーションを行う必要がある
- 課題は1,000 environment stepsにわたって進行する
- 実験は交絡要因を減らすよう設計されている
- 過学習が事実上不可能なほどのほぼ無限データを収集する
- 探索問題を排除するためオフラインRLに集中する
- データセットに十分なカバレッジがあり、与えられたデータセットで全課題が解けることを保証する
- 表現学習の負担を減らすため、ground-truth state observationを直接与える
- この統制環境でもQ-learningがスケールしないなら、限られたデータやノイジーな観測を伴う現実環境では可能性はさらに低い
標準的なオフラインRLアルゴリズムの結果
- 標準的で広く使われるオフラインRLアルゴリズムは、どれも全課題を解けなかった
- 対象アルゴリズムはflow BC、IQL、CRL、SAC+BCである
- 実験は1B規模データセットでも実施された
- これは一般的なオフラインRLデータセットより (1000 \times) 大きい
- さらに重要なのは、性能がしばしば最適性能より大幅に低い地点でplateauに達したことである
- より大きいモデル、より長い学習、別のハイパーパラメータなど、さまざまなablationや統制実験も効果がなかった
- 例外的に効果があった手法はhorizon reductionだった
Horizon reductionがもたらした改善
- 前述の仮説は、horizonとそれに伴うバイアス累積がオフポリシーRLスケーリングの主要な障害だというものだった
- これを検証するため、バイアスのあるTD backup回数を減らす複数のhorizon reduction手法を試した
- 例としてn-step returns、階層型RLなど
- 結果は肯定的だった
- n-step returnsのような単純な手法でも、スケーラビリティと最終性能を大きく改善した
- 単に学習を速くするtrickではなく、asymptotic performanceも改善した
- 完全な階層型手法はさらによく機能した
- 実験全体を通じて一貫して機能した唯一の手法がhorizon reductionだった
- データと計算資源を単純に増やすだけでは、horizonの呪いを解決するには不十分である
- この問題を直接狙う、より優れたアルゴリズムが必要である
スケーラブルなオフポリシーRL目的関数に向けた研究方向
- horizon reductionはQ-learningのスケーラビリティを切り開くが、現行手法は問題を根本的には解決しない
- n-step returnsや階層型RLのような現在の方法は、主として問題を定数倍だけ緩和する
- 任意に複雑な長期問題までスケールするオフポリシーRLアルゴリズムはまだ不足している
- 可能な研究方向は3つに整理できる
- 任意長のhorizonを扱うために、2段階階層を超える単純でスケーラブルな再帰的階層構造を見つける方法
- モデル学習は教師あり学習であり、オンポリシーRLもスケーラブルなので、まずモデルを学習し、そのモデル内でオンポリシーRLを実行するモデルベースRLアプローチ
- TD learningを完全に避ける方法
- 例として quasimetric RL はRLのLP formulationに基づく
- contrastive RL のようなMCベース手法も、TDベース手法よりよくスケールする可能性を検証できる
- 上記の実験設定は、こうしたアイデアを試す出発点になりうる
- 複雑なロボット課題とデータセットがすでに設計されている
- 課題が与えられたデータで解けることが検証済みである
- キューブをさらに追加する形で課題を任意に難しくし、アルゴリズムのスケーラビリティを統制された方法でストレステストできる
- コード公開: horizon-reduction
1件のコメント
Hacker Newsの意見
この記事は、Q学習がスケールしにくいより大きな理由を見落としているように思う
ホライズンが長くなるほど、可能な状態数は普通は指数関数的に増え、それらの状態を扱えるQを学習するにはデータも指数関数的に増やす必要がある
オンポリシー学習ではこの問題は軽くなる。重要なのは現在のポリシー近傍の状態だけで、実際にそうした状態だけをサンプリングするからだ
Q学習の
max演算によって時間ステップを経るにつれてノイズが増幅されるのが本質で、https://arxiv.org/abs/1509.06461 のようなバイアス緩和手法は強化学習エージェントの性能向上に成功している研究によると、ネットワークがあまり訪れていない状態でこの現象はより強く現れる
状態数が指数関数的に多いことが決定的に問題になるのは、それらの状態の間にパターンがない場合だけだ。学習可能な構造があるならうまく機能し得るし、これはディープラーニングの弱点ではなく強みだ
鍵は正しい学習目標を設定することで、記事はQ学習はその目標ではないと主張しているようなものだ
MuZeroのようなモデルベース強化学習が、筆者の懸念への解決策になるのかも気になる。MuZeroは過去の軌跡を再分析して学習効率を高められるし、モンテカルロ木探索（MCTS）はモデルを複数ステップ展開してホライズンを短くする原理的な方法だ
MCTSの
max演算も似た問題を生み得るが、探索が深くなっていく過程がそれを相殺できるかもしれない完全な非専門家の立場だが、ある課題は「深い」課題であっても十分に「一様」なので、悪いサンプルだけでも十分な場合があるのではないかと思う。そうした課題をエルゴード的課題と呼びたい
もちろん、そうでない課題も確かにあるはずだ
この論文は、読者がすでに強化学習をかなり理解していることを前提にしている
強化学習をきちんと掘り下げたいなら、David Silver（DeepMind）の入門講義が素晴らしい: https://youtu.be/2pWv7GOvuf0?si=CmFJHNnNqraL5i0s
完全に同意で、とても良い要約だと思う
ごく短く言えば、動く目標を追いかける問題で、その目標は自分がどう動くかによって変わる
価値ベース強化学習には、収束できる本当の正解がない。方程式の両辺に自分自身の近似値が入った差を最小化しているようなものだ
それでも絶望的だとは思わない。強化学習は動作するところに非常に近づいていると思っていて、これまで足りなかったのは信頼できる世界モデル／順方向ダイナミクス関数だったからだ
それがあれば探索せずに計画でき、今ではそのようなモデルができている
オフポリシー学習の利点は、初期探索から得られた非効率なデータが、後のより洗練されたポリシーを改善するうえでそれほど有用ではないという事実によって根本的に制限される
チェスのミス、けいれんのような動き、パズル解法の失敗を思い浮かべれば明らかだ
データがオフポリシーになるのは、そのデータが現在のポリシーなら行わないことを描写している場合だけだと気づくと、さらに明確になる
この問題の解法は、残念ながら、より良い汎化とサンプル効率が必要だという方向に関係していると思う
引用されている、オフポリシー学習で20分で歩けるようになった犬はどう説明できるのか？ それとも、もっと微妙な主張をしているのだろうか？
Decision TransformerやTrajectory Transformerが抜けているのは不思議だ
どちらもオフラインのアプローチで、注意機構のおかげで信用割当問題を回避し、長いホライズンの課題でかなりうまく機能する傾向がある
ほとんどの強化学習研究者は、こうしたアプローチを「本当の強化学習」とは見なさない。コンテキストウィンドウの外には信用を割り当てられず、無限ホライズンの課題を学習できないからだ
だが100万トークン以上のコンテキストウィンドウがあれば、実際にはそれほど問題ではないのでは？ 他の考えも聞きたい
DT: https://arxiv.org/abs/2106.01345
TT: https://arxiv.org/abs/2106.02039
単にTransformerを使うだけで信用割当問題を回避できるわけではない
Transformerは系列モデリング問題を解くためのアーキテクチャであり、強化学習で生じる信用割当問題もそうした問題の一例だ。この種のアーキテクチャは以前から数多く存在していた
信用割当問題が難しいというのは、データの希少性に関する主張だ。アーキテクチャの選択だけでそれを「回避」することはできない
人間は実際には両方をやっている
自分の行動の結果を探索しながらオンポリシーでも学び、専門家のデモンストレーションのようにオフポリシーでも学ぶ
違いは、人間は良い行動と悪い行動を区別でき、良いと判断した行動だけを選別して学べる点にある
ほとんどのオフポリシー強化学習では悪い行動も多く含まれ、それが学習セットに入ることで学習が遅くなる
だからこそ、専門家のデモンストレーションの中には魅力的なものがある。初心者レベルの「ベストプラクティス」から見ると完全に間違ったやり方なのに、より良い結果を出すのを見ることができる
もちろん、ときには、それほど上手ければそのような技法やミスも許容できるという意味にすぎない場合もある
人間が反復訓練で学ぶ長いホライズンの課題は、より短いホライズンの課題に分解したうえで、後から階層的に合成して学ぶという点は指摘に値する
モデルが最初から長いホライズンの課題を扱えないことはあり得るが、まず短いホライズンのスキルを学び、その小さなスキルの束を活用してより長いホライズンを学べる
私たち全員が行っているチャンキングと同じだ
誰も商業旅客機を大陸横断で操縦する方法を、手や腕の微細な動きのシーケンスとして学ぶことはない
幼い頃にボールをつかむのはそういう形で学ぶが、飛行やスポーツは学習済みのスキルと計画の階層で成り立っている
記事は気に入ったが、説明なしの略語の使用によって、より広い読者にとって有用になる機会を減らしていると思う
小さな指摘だが、略語と専門用語は説明してくれるとよい
新しいブラウザDiaでたった今試したが、うまく動いた。好みのモデルプロバイダーにコピー＆ペーストしてもよい
こうすれば記事を簡潔に保ちながら、AIツールに質問して明確にできる
Q-Learningのようなオフポリシー手法の魔法のような点は、最適ではない訓練データだけを見ても最適な結果に収束するところにある
たとえば、戦略なしに完全にランダムに動くエージェントたちのチェス対局データセットをQ-Learningの入力に使っても、高品質な入力がある場合より遅いだけで、最終的には最適ポリシーに収束する
用語を少しひねって使っているのかもしれないが、エルゴード的ではない課題も存在すると思う