論文の概要: SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2510.19241v1
• Date: Wed, 22 Oct 2025 04:57:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:15.1264
• Title: SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes
• Title（参考訳）: SPOT: マルコフ決定プロセスのためのツリーによるスケーラブルなポリシー最適化
• Authors: Xuyuan Xiong, Pedro Chumpitaz-Flores, Kaixun Hua, Cheng Hua,
• Abstract要約: 高い意思決定には、解釈可能な強化学習政策が不可欠である。 本研究では,決定木ポリシーを計算するための新しい手法であるSPOTを提案する。 我々は,木構造制約からMDPダイナミクスを分離する空間的分岐結合アプローチを採用する。
• 参考スコア（独自算出の注目度）: 3.1382171194541306
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Interpretable reinforcement learning policies are essential for high-stakes decision-making, yet optimizing decision tree policies in Markov Decision Processes (MDPs) remains challenging. We propose SPOT, a novel method for computing decision tree policies, which formulates the optimization problem as a mixed-integer linear program (MILP). To enhance efficiency, we employ a reduced-space branch-and-bound approach that decouples the MDP dynamics from tree-structure constraints, enabling efficient parallel search. This significantly improves runtime and scalability compared to previous methods. Our approach ensures that each iteration yields the optimal decision tree. Experimental results on standard benchmarks demonstrate that SPOT achieves substantial speedup and scales to larger MDPs with a significantly higher number of states. The resulting decision tree policies are interpretable and compact, maintaining transparency without compromising performance. These results demonstrate that our approach simultaneously achieves interpretability and scalability, delivering high-quality policies an order of magnitude faster than existing approaches.
• Abstract（参考訳）: 解釈可能な強化学習政策は高い意思決定に不可欠であるが,マルコフ決定プロセス(MDP)における決定木政策の最適化は依然として困難である。 混合整数線形プログラム(MILP)として最適化問題を定式化する決定木ポリシーの新しい手法であるSPOTを提案する。 効率を向上させるために,木構造制約からMDPダイナミクスを分離し,効率的な並列探索を可能にする,空間分割バウンド法を用いる。 これにより、以前の方法に比べてランタイムとスケーラビリティが大幅に向上する。 このアプローチは、各イテレーションが最適な決定木を生成することを保証します。 標準ベンチマークによる実験結果から,SPOTは相当なスピードアップを実現し,より多くの状態を持つ大規模MDPにスケールすることを示した。 結果として得られる決定ツリーポリシーは解釈可能でコンパクトであり、パフォーマンスを損なうことなく透明性を維持します。 これらの結果から,本手法は解釈可能性とスケーラビリティを同時に達成し,既存の手法よりも一桁早く高品質なポリシーを提供することを示す。

関連論文リスト

• Breiman meets Bellman: Non-Greedy Decision Trees with MDPs [8.530182510074983]
  我々は、欲求と最適なアプローチのギャップを埋めるフレームワークDPDT(Dynamic Programming Decision Trees)を提案する。 DPDTはマルコフ決定プロセスの定式化と分割生成を組み合わせ、ほぼ最適決定木を構築する。 実験の結果,DPDTは既存の最適解法よりも桁違いに少ない演算でほぼ最適損失を達成できた。
  論文  参考訳（メタデータ） (2023-09-22T08:18:08Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Optimal Decision Tree Policies for Markov Decision Processes [7.995360025953931]
  マルコフ決定過程(MPD)におけるサイズ制限決定木の最適化について検討する。 これは、模倣学習の固有の欠点、すなわち、複雑なポリシーが、サイズ制限木を使って表現できないことによるものである。 一般的に、機械学習モデルの性能と解釈可能性の間にはトレードオフがあるが、OMDTは3の深さに制限され、しばしば最適限に近い性能を示す。
  論文  参考訳（メタデータ） (2023-01-30T18:51:02Z)
• First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
  我々はロバストマルコフ決定過程(MDP)の解法を考える。 MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。 $(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
  論文  参考訳（メタデータ） (2022-09-21T18:10:28Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [113.8752163061151]
  非定常線形カーネルマルコフ決定過程(MDP)におけるエピソード強化学習(RL)の研究 線形最適化アンダーライン最適化アルゴリズム(PROPO)を提案する。 PROPOはスライディングウィンドウベースのポリシー評価と周期的リスタートベースのポリシー改善の2つのメカニズムを特徴としている。
  論文  参考訳（メタデータ） (2021-10-18T02:33:20Z)
• Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learning [52.74071439183113]
  我々は、強化学習を通して解決された逐次決定問題(MDP)の文脈における予測列最適化フレームワークについて検討した。 2つの重要な計算課題は、意思決定中心の学習をMDPに適用することである。
  論文  参考訳（メタデータ） (2021-06-06T23:53:31Z)
• Logistic Q-Learning [87.00813469969167]
  MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。 提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
  論文  参考訳（メタデータ） (2020-10-21T17:14:31Z)
• Partial Policy Iteration for L1-Robust Markov Decision Processes [13.555107578858307]
  本稿では、ロバストなMDPの共通クラスを解くための新しい効率的なアルゴリズムについて述べる。 我々は、ロバストなMDPのための部分ポリシーイテレーション、新しい、効率的で柔軟な、一般的なポリシーイテレーションスキームを提案する。 実験結果から,提案手法は最先端手法よりも桁違いに高速であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-16T19:50:14Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)

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

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