論文の概要: Optimal Decision Tree Policies for Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2301.13185v2
- Date: Wed, 14 Feb 2024 01:00:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-15 20:24:59.602430
- Title: Optimal Decision Tree Policies for Markov Decision Processes
- Title（参考訳）: マルコフ決定過程のための最適決定木政策
- Authors: Dani\"el Vos and Sicco Verwer
- Abstract要約: マルコフ決定過程(MPD)におけるサイズ制限決定木の最適化について検討する。
これは、模倣学習の固有の欠点、すなわち、複雑なポリシーが、サイズ制限木を使って表現できないことによるものである。
一般的に、機械学習モデルの性能と解釈可能性の間にはトレードオフがあるが、OMDTは3の深さに制限され、しばしば最適限に近い性能を示す。
- 参考スコア（独自算出の注目度）: 7.995360025953931
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Interpretability of reinforcement learning policies is essential for many
real-world tasks but learning such interpretable policies is a hard problem.
Particularly rule-based policies such as decision trees and rules lists are
difficult to optimize due to their non-differentiability. While existing
techniques can learn verifiable decision tree policies there is no guarantee
that the learners generate a decision that performs optimally. In this work, we
study the optimization of size-limited decision trees for Markov Decision
Processes (MPDs) and propose OMDTs: Optimal MDP Decision Trees. Given a
user-defined size limit and MDP formulation OMDT directly maximizes the
expected discounted return for the decision tree using Mixed-Integer Linear
Programming. By training optimal decision tree policies for different MDPs we
empirically study the optimality gap for existing imitation learning techniques
and find that they perform sub-optimally. We show that this is due to an
inherent shortcoming of imitation learning, namely that complex policies cannot
be represented using size-limited trees. In such cases, it is better to
directly optimize the tree for expected return. While there is generally a
trade-off between the performance and interpretability of machine learning
models, we find that OMDTs limited to a depth of 3 often perform close to the
optimal limit.
- Abstract（参考訳）: 強化学習政策の解釈可能性は多くの実世界の課題に不可欠であるが、そのような解釈可能な政策の学習は難しい問題である。
特に、決定木やルールリストのようなルールベースのポリシーは、その非微分性のために最適化が難しい。
既存の手法では検証可能な決定木ポリシーを学習できるが、学習者が最適な決定木を生成する保証はない。
本研究では,マルコフ決定過程(MPD)のサイズ制限決定木の最適化について検討し,最適MDP決定木を提案する。
ユーザ定義サイズ制限とMDP定式化 OMDT が与えられた場合、Mixed-Integer Linear Programming を用いて、決定木に対する期待値の値引きを直接最大化する。
異なるMDPに対する最適決定木ポリシーを訓練することにより、既存の模倣学習手法の最適性ギャップを経験的に研究し、それらが準最適に実行されることを確認する。
これは模倣学習が本質的に欠如していること、すなわち、複雑なポリシーはサイズ制限木を使って表現できないことによるものである。
そのような場合、期待した戻りのためにツリーを直接最適化する方がよい。
一般的に、機械学習モデルの性能と解釈可能性の間にはトレードオフがあるが、3の深さに制限されたOMDTは、しばしば最適限に近い性能を示す。
関連論文リスト
- Optimizing Interpretable Decision Tree Policies for Reinforcement Learning [10.68128849363198]
決定木は、その固有の解釈可能性について教師あり学習において注目を集めている。
本稿では、強化学習環境におけるニューラルネットワークを置き換えるために、解釈可能な決定木ポリシーを最適化する問題を考察する。
論文 参考訳（メタデータ） (2024-08-21T14:04:00Z) - Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。
我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
論文 参考訳（メタデータ） (2024-02-06T07:40:53Z) - Reinforcement Learning with Human Feedback: Learning Dynamic Choices via
Pessimism [91.52263068880484]
人間のフィードバックを用いたオフライン強化学習(RLHF)について検討する。
我々は、人間の選択によって引き起こされる一連の軌道から、人間の根底にある報酬とMDPの最適政策を学習することを目指している。
RLHFは、大きな状態空間だが人間のフィードバックが限られていること、人間の決定の有界な合理性、政治外の分散シフトなど、さまざまな理由から挑戦されている。
論文 参考訳（メタデータ） (2023-05-29T01:18:39Z) - Policy learning for many outcomes of interest: Combining optimal policy
trees with multi-objective Bayesian optimisation [0.0]
多目的政策学習は、ポリシー学習のための最適な決定木と、多目的ベイズ最適化アプローチを組み合わせる。
本手法はケニアにおける抗マラリア薬の非価格設定の現実世界のケーススタディに適用される。
論文 参考訳（メタデータ） (2022-12-13T01:39:14Z) - bsnsing: A decision tree induction method based on recursive optimal
boolean rule composition [2.28438857884398]
本稿では,決定木帰納過程における分割規則選択を最適化するMIP(Mixed-integer Programming)の定式化を提案する。
商用の解法よりも高速に実例を解くことができる効率的な探索解法を開発した。
論文 参考訳（メタデータ） (2022-05-30T17:13:57Z) - Efficient Policy Iteration for Robust Markov Decision Processes via
Regularization [49.05403412954533]
ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。
最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。
本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
論文 参考訳（メタデータ） (2022-05-28T04:05:20Z) - Robust Optimal Classification Trees Against Adversarial Examples [5.254093731341154]
本稿では,ユーザが特定した攻撃モデルに対して最適に堅牢な決定木を訓練する手法の集合を提案する。
逆学習において生じるmin-max最適化問題は、単一最小化定式化を用いて解くことができることを示す。
また,両部マッチングを用いた任意のモデルに対して,上界の対角精度を決定する手法を提案する。
論文 参考訳（メタデータ） (2021-09-08T18:10:49Z) - Learning MDPs from Features: Predict-Then-Optimize for Sequential
Decision Problems by Reinforcement Learning [52.74071439183113]
我々は、強化学習を通して解決された逐次決定問題(MDP)の文脈における予測列最適化フレームワークについて検討した。
2つの重要な計算課題は、意思決定中心の学習をMDPに適用することである。
論文 参考訳（メタデータ） (2021-06-06T23:53:31Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳（メタデータ） (2020-07-24T17:06:55Z) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
様々な目的に対して最適な決定木を生成する手法を提案する。
また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
論文 参考訳（メタデータ） (2020-06-15T19:00:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。