論文の概要: Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees

• arxiv url: http://arxiv.org/abs/2610.15461v1
• Date: Sun, 11 Oct 2026 09:01:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.215025
• Title: Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees
• Title（参考訳）: 任意の決定論的最適性保証を備えたスケーラブルロバストMCTS
• Abstract要約: 我々は、我々の知る限り、オンラインMDPプランニングを堅牢にするための最初の決定論的時限保証について紹介する。 任意の固定されたポリシーに対して、矩形および非矩形不確実集合の下で、投影された値と真のロバストな値の間のギャップの上下境界を導出する。 CAR-MCTSは境界誘導型MCTSプランナーで、これらの決定論的境界を用いて探索をガイドし、証明可能な最適枝を探索し、最適根アクションが認証されると終了する。
• 参考スコア（独自算出の注目度）: 9.269394037577177
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: MDP planners often rely on nominal transition models that may differ from the true dynamics. Robust MDP planning accounts for this uncertainty through a set of admissible models, but doing so with limited online computation is challenging: the search tree grows exponentially with the horizon and each robust backup requires an additional optimization. Existing online robust methods remain limited in scale and offer at most probabilistic guarantees. We introduce, to the best of our knowledge, the first deterministic anytime guarantees for robust online MDP planning. We restrict computation to the sampled search tree while deterministically bounding the contribution of unsampled trajectories. For any fixed policy, we derive lower and upper bounds on the gap between its projected and true robust values under rectangular and non-rectangular uncertainty sets. Under rectangular uncertainty, we propagate these bounds through the robust Bellman operator to bound the optimal robust value. These bounds are computable from the current sampled tree, hold at every node, tighten as the sampled support expands, and converge to the robust values as full support is recovered. We develop CAR-MCTS, a bound-guided MCTS planner that uses these deterministic bounds to guide exploration, prune provably suboptimal branches, and terminate once the optimal root action is certified. The fixed-policy bounds also yield an anytime policy-evaluation mechanism that certifies the robust value of any policy, independent of how it was obtained. Experiments verify the deterministic bounds, their tightening under support expansion, substantial branch pruning, root-action certification, and convergence to the optimal robust policy. To our knowledge, this is the first scalable robust MCTS framework with anytime deterministic guarantees for both online planning and policy evaluation, without enumerating the full state space.
• Abstract（参考訳）: MDPプランナーはしばしば、真の力学と異なるかもしれない名目遷移モデルに依存している。 頑健なMDP計画では、許容可能なモデルの集合を通してこの不確実性を説明できるが、限られたオンライン計算で行うことは困難である。 既存のオンラインロバストメソッドの規模は限定的であり、ほとんどの確率的保証を提供する。 我々は、我々の知る限り、オンラインMDPプランニングを堅牢にするための最初の決定論的時限保証について紹介する。 標本探索木に限定し,無サンプル軌道の寄与を決定的に制限する。 任意の固定されたポリシーに対して、矩形および非矩形不確実集合の下で、投影された値と真のロバストな値の間のギャップの上下境界を導出する。 正則不確実性の下では、これらの境界をベルマン作用素を通して伝播させ、最適なロバスト値を有界とする。 これらのバウンダリは、現在のサンプルツリーから計算可能で、すべてのノードに保持され、サンプルサポートが拡大するにつれて固まり、完全なサポートが回復するにつれてロバストな値に収束する。 CAR-MCTSは境界誘導型MCTSプランナーで、これらの決定論的境界を用いて探索をガイドし、証明可能な最適枝を探索し、最適根アクションが認証されると終了する。 固定政治境界はまた、どのような政策のロバストな価値も証明し、その取得方法とは無関係に、いつでも政策評価のメカニズムをもたらす。 実験では、決定論的境界、サポート拡張下での強化、実質的な分岐プルーニング、ルートアクション認証、そして最適なロバストポリシーへの収束を検証する。 私たちの知る限り、これは、完全な状態空間を列挙することなく、オンライン計画とポリシー評価の両方に対して決定論的保証を持つ、初めてのスケーラブルな堅牢なMCTSフレームワークです。

関連論文リスト

• BandPO: Bridging Trust Regions and Ratio Clipping via Probability-Aware Bounds for LLM Reinforcement Learning [49.25750348525603]
  BandPOは、信頼領域を動的で確率対応のクリッピング間隔に投影する統一理論演算子であるBandに取って代わる。 BandPOはカノニカルクリッピングやClip-Higherより一貫して優れ,エントロピー崩壊の軽減が図られている。
  論文  参考訳（メタデータ） (2026-03-05T08:03:05Z)
• Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values [11.174902793218834]
  非矩形ロバストマルコフ決定過程を平均逆基準下で研究する。 あいまいさの集合に対して一様に、サブリニアな後悔を達成できる歴史に依存した政策が、頑健な最適化であることを示す。
  論文  参考訳（メタデータ） (2026-03-01T06:29:34Z)
• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality [53.525547349715595]
  我々はRectified Robust Policy Optimization (RRPO) と呼ばれる新しいプライマリのみのアルゴリズムを提案する。 RRPOは双対の定式化に頼ることなく、主問題に直接作用する。 我々は、最もよく知られた下界と一致する複雑性を持つ、ほぼ最適な実現可能なポリシーに収束することを示す。
  論文  参考訳（メタデータ） (2025-08-24T16:59:38Z)
• Best-Effort Policies for Robust Markov Decision Processes [69.60742680559788]
  我々は、ロバスト MDP (RMDPs) として知られる遷移確率の組によるマルコフ決定過程(MDPs)の共通一般化について研究する。 このような政策を最適な堅牢なベストプラクティス(ORBE)政策と呼ぶ。 我々はORBEポリシーが常に存在することを証明し、その構造を特徴付け、標準的なロバストな値反復よりも小さなオーバヘッドで計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-08-11T09:18:34Z)
• MIBP-Cert: Certified Training against Data Perturbations with Mixed-Integer Bilinear Programs [50.41998220099097]
  トレーニング中のデータエラー、汚職、中毒攻撃は、現代のAIシステムの信頼性に大きな脅威をもたらす。 混合整数双線形プログラミング(MIBP)に基づく新しい認証手法MIBP-Certを紹介する。 摂動データや操作データを通じて到達可能なパラメータの集合を計算することで、可能なすべての結果を予測することができ、堅牢性を保証することができる。
  論文  参考訳（メタデータ） (2024-12-13T14:56:39Z)
• Online POMDP Planning with Anytime Deterministic Optimality Guarantees [13.824288326240927]
  近似解と最適解の間の離散POMDPに対する決定論的関係を導出する。 我々の導出は、新しいアルゴリズムセットの道を提供し、既存のアルゴリズムにアタッチできることを示します。
  論文  参考訳（メタデータ） (2023-10-03T04:40:38Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。