🤖 machine learning

Finding the Time to Think: Learning Planning Budgets in Real-Time RL

本論文は、エージェントが環境の進行に伴い熟考時間を選択しなければならない可変遅延リアルタイム強化学習を導入し、状態依存的なプランニング予算を動的に選択するための軽量なゲーティング・ポリシーの学習を提案しており、複数のリアルタイムゲームにおいて固定およびヒューリスティックなベースラインを上回る性能を示している。

原著者： Aneesh Muppidi, Firas Darwish, Dylan Cope, João F. Henriques, Jakob Nicolaus Foerster

公開日 2026-06-26

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Aneesh Muppidi, Firas Darwish, Dylan Cope, João F. Henriques, Jakob Nicolaus Foerster

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

パックマンやテトリスのような、テンポの速いビデオゲームをプレイしているところを想像してみてください。通常のゲームでは、あなたが「うーん、左に行くべきか、右に行くべきか？」と考えている間、世界は一時停止します。あなたは完璧な一手を選ぶために、好きなだけ時間をかけることができます。

しかし、リアルタイムの世界では、世界は待ってくれません。あなたが画面を見つめて考えている間も、ゴーストは動き続け、ブロックは落ち続け、時計の針は進み続けます。もし熟考しすぎてしまうと、完璧な瞬間を逃してしまうかもしれません。そして、素早く行われた「そこそこ良い」動きは、遅すぎた「完璧な」動きよりも優れたものになることがよくあります。

この論文では、特定の課題に取り組んでいます。それは、「いつ深く考え、いつ反射的に動くべきか？」をどうやって決めるのか？ という問題です。

核となるアイデア：「思考予算（Thinking Budget）」

著者らは、AIエージェントが決定ごとに自分自身の「思考予算」を選択できるシステムを導入しました。

選択肢A： 即座に反応する（思考時間を0秒とする）。
選択肢B： 少し時間をかけて考える（例えば1秒間）。
選択肢C： たっぷり時間をかけて考える（例えば4秒間）。

ここでの落とし穴は、AIが「考えている」間（選択肢BまたはC）、ゲームの世界は進行し続けているという点です。もしAIが4秒間考えてしまったら、ゲームは4ステップ分進んでしまいます。その4秒間のうちに、AIは決定的な好機を逃してしまっているかもしれません。

解決策：「ゲートキーパー（門番）」

研究者たちは、2つのパートからなるチームを作り上げました。

プランナー（脳）： 十分な時間が与えられれば最善手を計算できる、強力で思考の遅いAI（AlphaZeroベース）です。これは、まるでグランドマスターのチェスプレイヤーのようです。
ゲートキーパー（マネージャー）： 現在の状況を観察し、「グランドマスターに4秒間考えさせる必要があるのか、それとも素早い反射だけで十分なのか？」を判断する、極めて小さく超高速なAIです。

ゲートキーパーは、交通管制官のように機能します。ゲートキーパー自体はゲームをプレイするのではなく、プランナーに対して、「おい、この状況は危険だ、4秒間考えてくれ！」あるいは「この状況は退屈だ、指を鳴らすように素早く動け！」と指示を出すのです。

比喩：時計を持つチェスプレイヤー

スピードチェスのプレイヤーを想像してみてください。彼らには、ゲーム全体を通して使える限られた持ち時間があります。

ボードが単純な場合、彼らは2秒で手を打ちます。
ボードが複雑な罠に陥っている場合、彼らは分析のために2分間を費やすかもしれません。

この論文のAIも同じことをしますが、このスキルを自動的に学習します。AIは以下のように学習していきます。

パックマンでは、ゴーストが遠くにいれば、長く考えることが安全です。しかし、ゴーストがすぐ後ろに迫っていたら、即座に反応しなければなりません。
テトリスでは、ボードが空の状態なら、考える必要はありません。しかし、ボードがブロックの混沌とした状態であれば、最適なフィット具合を計算するために追加の時間が必要です。

検証方法

彼らはこの「ゲートキーパー」を5つの異なるゲームでテストしました。

パックマン、テトリス、およびスネーク： これらは「コミットされたアクション（決定的な行動）」を伴うゲームです。AIが考えている間も、「反射」バージョンのAIがゲームを動かし続けるため、世界が停止することはありません。
スピード・ヘックス（Speed Hex）およびスピード・ゴ（Speed Go）： これらは「クロック」ゲームです。ボードは動きませんが、AI自身の時計は、考える時間が長くなるにつれて減っていきます。

結果：
ゲートキーパーを備えたAIは、他のあらゆるバージョンの自分自身に勝利しました。

固定された一定の時間で常に考えるバージョン（遅すぎる、あるいは早すぎるもの）に勝利しました。
人間が設計したルール（「ゲームの中盤では長く考える」など）を使用するバージョンに勝利しました。
さらに、彼らが「思考」の部分を一つのコンピュータに、「ゲーム」の部分を全く別のコンピュータに配置した場合でも機能しました。これは、現実世界の複雑なハードウェア構成においても動作することを証明しています。

なぜこれが重要なのか

この論文は、「いつ考えるべきかを知ること」は、「どのように考えるかを知ること」と同じくらい重要であるということを示しています。

小さな「マネージャー」を訓練して、各手に対してどれだけの時間を費やすかを決定させることで、AIは非常に効率的になります。AIは簡単な決断に時間を浪費することをやめ、本当に重要な瞬間のために重厚な思考を温存します。これにより、AIが考えすぎて「麻痺」してしまうのを防ぎ、決して止まることのない世界の中で生き残るためのスピードを維持できるのです。

技術要約：考える時間を見つける：リアルタイムRLにおける学習計画予算

問題定義：可変遅延リアルタイムRL

標準的な強化学習（RL）およびマルコフ決定過程（MDP）は、エージェントが行動を計算する間、環境が無期限に待機するという仮定の下で動作している。したがって、熟考（deliberation）にはコストがかからない。しかし、リアルタイムの設定ではこの仮定は成立しない。エージェントの計算時間に関わらず、環境は連続的に進行する。完璧な行動であっても、実行が遅すぎれば、適時実行された不完全な行動よりも劣ることが多い。

先行研究（Ramsted & Pal, 2019）は、固定遅延（例：計算のために正確に1タイムステップを要する）を持つリアルタイムRLを定式化した。これに対し、本論文は可変遅延リアルタイムRLを導入する。このフレームワークにおいて、エージェントは静的な関数ではなく、時間の中で動作する「手続き（procedure）」である。エージェントは、各意思決定ポイントにおいて「どのくらいの長さ」熟考すべきかを決定しなければならない。熟考のコストは、エージェントが計算を行っている間の環境の進行（またはボードゲームにおける時計の減少）として「支払われる」。これはメタ推論の課題を生み出す。すなわち、エージェントは、計画される行動の質と、計画に費やした時間によって引き起こされる状態の劣化とのバランスを取らなければならない。いかに計画するかを計画することは、メタ決定自体が、最適化しようとしている計画と同じリアルタイム・コストを発生させるというパラドックスに陥るリスクがある。

手法

著者らは、**予算化されたオプション（budgeted options）に基づくセミマルコフ決定過程（SMDP）**を用いた解決策を提案しており、これによりプランニング・アルゴリズムと「どの程度」計画するかという決定を分離している。

アーキテクチャ構成要素:
- 反射方策 ( $\pi_{reflex}$ ): 高速かつ軽量な方策（例：MCTSを除いたAlphaZeroモデルのポリシー・ヘッド）。これは1フレーム未満で動作する。プランナーがバックグラウンドで動作している間、即時的な行動を提供する。
- 逐次的な行動精緻化計算 ( $\{c_k\}$ ): 離散的な期間 $k$ によってインデックス付けされた有限の計算セット。本研究では、これらは $k$ フレーム分のモンテカルロ木探索（MCTS）の実行として具体化される。実行時間が長いほど（ $c_k$ ）、より高品質な行動が生成されるが、より多くの時間を要する。
- 予算化されたオプション ( $o_k$ ): 各オプション $o_k$ は計算 $c_k$ をラップしている。開始時、エージェントは $c_k$ が実行されている間、 $\pi_{reflex}$ から生成される $k-1$ 回の行動を実行することをコミットする。 $k$ フレーム目に、 $c_k$ から精緻化された行動が実行される。
- ゲーティング方策 ( $\pi_{gate}$ ): 近似方策最適化（PPO）を通じて訓練された軽量なニューラルネットワークであり、メタ方策として機能する。現在の状態（ゲームの観測、プランナーの特徴量、および価値推定値）を観察し、次のメタステップのための予算 $k$ （オプションの期間）を選択する。
訓練プロトコル:
- 二段階訓練: まず、特定の環境に対してベースとなるAlphaZeroスタイルのプランナーを訓練する。その後、これらのプランナーは**凍結（frozen）**される。次に、凍結されたプランナーの上でゲーティング方策を訓練する。
- メタMDP定式化: ゲーティング方策は、アクションが予算化されたオプションの選択となる離散制御問題を解く。報酬は、 $k$ フレームにわたる累積リターンであり、 $\gamma^k$ で割引かれる。
- 適応型GAE: メタステップの期間が可変（ $k$ ）であるため、著者らは、アドバンテージ計算を通じて、ステップごとの割引 $\gamma^k$ を伝播させるように一般化アドバンテージ推定（GAE）を適応させている。
環境の実装:
- コミット済み行動環境（パックマン、リアルタイム・テトリス、スネーク）: 環境は連続的に進行する。エージェントは計画中に $k-1$ 回の反射行動を実行する。計画のコストは、計算中に世界の状態が変化することである。
- クロック環境（スピード・ヘックス、スピード・ゴー）: ボードは静止しているが、共有の時計が思考時間とともに減少していく。反射方策は、計画ウィンドウ中に「ノーオップ（何もしない）」を出力する。コストは、残りの時間予算の減少である。

主な貢献

可変遅延リアルタイムRLフレームワーク: 遅延の選択をシステムに課された制約ではなく、学習可能な問題として扱うことで、固定遅延フレームワークを一般化したもの。
計画のトレードオフの経験的特性付け: 著者らは、計画の質と推論レイテンシがMCTSのシミュレーション回数と共にスケールすることを立証した。この共同スケーリングが、固定予算ではなく適応的な割り当ての必要性を動機付けている。
凍結されたプランナー上での適応型ゲーティング: 凍結されたAlphaZeroプランナー上で訓練された軽量なゲーティング方策を用いて、状態依存的な計画予算を学習する方法。これにより、「計画についての計画」というパラドックスを回避できる。なぜなら、単一のゲートのフォワードパスは、MCTSのロールアウトよりも数桁高速だからである。
実世界のハードウェア検証: 本手法は、真の非同期、2-GPUデプロイメント（環境/反射用とMCTS用のGPUを分ける）において検証されており、アーキテクチャの変更や再訓練なしで、シミュレーションで訓練されたポリシーがハードウェア分離された実行に効果的に転移することを実証している。

結果

ゲーティング方策は、パックマン、リアルタイム・テトリス、スネーク、スピード・ヘックス、スピード・ゴーの5つの環境で評価された。

ベースラインとの比較: 適応型ゲーティング方策は、以下を一貫して上回った：
- 固定予算方策: 単一の $k$ に制約されたエージェント（例：常に1, 2, 3, または4フレーム分を計画する）。
- ヒューリスティック・ベースライン: 「Greedy」（常に最大シミュレーション）や、ゲームエンジンで一般的な「Midpeak」（ベルカーブ型の割り当て）を含む。
- ランダム・ベースライン: ランダムに予算を選択するとパフォーマンスが著しく低下し、いつ計算資源を割り当てるかが、どの程度の量を割り当てるかと同じくらい重要であることを裏付けた。
具体的な利得:
- パックマン: 最良の固定予算に対して+10.3%の改善。
- リアルタイム・テトリス: 最良の固定予算に対して+65%の改善。
- スネーク: +10.9%の改善。
- スピード・ヘックス/ゴー: ゲーティング方策は、変動するクロック制約の下で、固定予算およびヒューリスティックの両方を上回る期待スコアを達成した。
行動分析: ゲーティング方策は、高リスクまたは制約の多い状態（例：パックマンにおけるゴーストの接近、テトリスの密集したボード、スネークにおける到達可能性の低下）において、より深い計画（高い $k$ ）を割り当てることを学習し、安全または開けた状態では素早く反応（低い $k$ ）することを学習した。また、スピード・ヘックス/ゴーにおいて、再訓練なしで異なるクロック予算に汎化することも示した。
ハードウェア転移: 2-GPU非同期セットアップ（H100, A100, A40）において、ポリシーはシミュレーションから実ハードウェアへクリーンに転移した。レイテンシはH100およびA100において予算内に収まり、リターンはシミュレーションの対応物と密接に一致した。

意義と主張

本論文は、標準的なRLとリアルタイムな相互作用との間の根本的な不一致に対し、熟考時間を動的に管理すべきリソースとして定式化することで対処していると主張している。その意義は以下の点にある：

メタ推論パラドックスの回避: 凍結されたプランナー上に軽量なゲートを使用することで、計画の計画を行うための計算オーバーヘッドを回避しており、このアプローチをリアルタイム展開において実用的なものにしている。
状態依存的なリソース割り当て: 結果は、単一の固定計画予算は最適ではないことを示しており、計算の価値は状態に強く依存することを示している。
非同期ハードウェアへのスケーラビリティ: 「コミット済み行動」訓練プロトコルは、非同期実行のダイナミクスを成功裏にモデルしており、シミュレーションで訓練されたポリシーを、修正なしに環境とプランナーを分離した別々のハードウェアにデプロイすることを可能にしている。

認められた限界事項:

本フレームワークは、コミットされたステップに対して完全な環境シミュレータが存在することを前提としている（MCTSは $k-1$ 回の反射行動を正確に予測しなければならない）。
ゲーティング方策は凍結されたプランナーに対して訓練されている。プランナーとゲートの共同最適化は今後の課題である。
予算セット $\mathcal{K}$ は手動で較正された離散的なものであり、連続的またはより豊かな計算語彙（computational vocabularies）への拡張が将来の拡張として示唆されている。