論文の概要: How to Find the Exact Pareto Front for Multi-Objective MDPs?
- arxiv url: http://arxiv.org/abs/2410.15557v1
- Date: Mon, 21 Oct 2024 01:03:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-22 13:20:56.546952
- Title: How to Find the Exact Pareto Front for Multi-Objective MDPs?
- Title（参考訳）: 多目的MDPのための厳格なパレートフロントの探索法
- Authors: Yining Li, Peizhong Ju, Ness B. Shroff,
- Abstract要約: 多目的マルコフ決定プロセス (MDPs) は、現実の意思決定問題は、単一目的のMDPでは対応できない相反する目的を伴うことが多いため、注目を集めている。
Paretoのフロントは、支配できないポリシーの集合を特定し、様々な好みに効率的に適応できる最適なソリューションを見つけるための基盤を提供する。
- 参考スコア（独自算出の注目度）: 28.70863169250383
- License:
- Abstract: Multi-objective Markov Decision Processes (MDPs) are receiving increasing attention, as real-world decision-making problems often involve conflicting objectives that cannot be addressed by a single-objective MDP. The Pareto front identifies the set of policies that cannot be dominated, providing a foundation for finding optimal solutions that can efficiently adapt to various preferences. However, finding the Pareto front is a highly challenging problem. Most existing methods either (i) rely on traversing the continuous preference space, which is impractical and results in approximations that are difficult to evaluate against the true Pareto front, or (ii) focus solely on deterministic Pareto optimal policies, from which there are no known techniques to characterize the full Pareto front. Moreover, finding the structure of the Pareto front itself remains unclear even in the context of dynamic programming. This work addresses the challenge of efficiently discovering the Pareto front. By investigating the geometric structure of the Pareto front in MO-MDP, we uncover a key property: the Pareto front is on the boundary of a convex polytope whose vertices all correspond to deterministic policies, and neighboring vertices of the Pareto front differ by only one state-action pair of the deterministic policy, almost surely. This insight transforms the global comparison across all policies into a localized search among deterministic policies that differ by only one state-action pair, drastically reducing the complexity of searching for the exact Pareto front. We develop an efficient algorithm that identifies the vertices of the Pareto front by solving a single-objective MDP only once and then traversing the edges of the Pareto front, making it more efficient than existing methods. Our empirical studies demonstrate the effectiveness of our theoretical strategy in discovering the Pareto front.
- Abstract（参考訳）: 多目的マルコフ決定プロセス (MDPs) は、現実の意思決定問題は、単一目的のMDPでは対応できない相反する目的を伴うことが多いため、注目を集めている。
Paretoのフロントは、支配できないポリシーの集合を特定し、様々な好みに効率的に適応できる最適なソリューションを見つけるための基盤を提供する。
しかし、Paretoフロントを見つけることは非常に難しい問題である。
既存の方法がほとんどである。
一 真のパレート前面に対して評価し難い近似をもたらす連続的嗜好空間のトラバースに依拠する、又は
(II) 決定論的パレート最適政策にのみ焦点を合わせ、そこから全パレートフロントを特徴づける既知の手法が存在しない。
さらに、Paretoフロントの構造自体の発見は、動的プログラミングの文脈においても不明確である。
この研究は、パレートフロントの効率的な発見という課題に対処する。
MO-MDPにおけるパレートフロントの幾何学的構造を調べることで、パレートフロントはすべての頂点が決定論的ポリシーに対応する凸ポリトープの境界にあり、パレートフロントの隣接する頂点は、決定論的ポリシーの1つの状態-作用ペアによってほぼ確実に異なる。
この洞察は、全ての政策間でのグローバルな比較を、一つの状態-行動ペアによって異なる決定論的ポリシー間の局所的な検索に変換し、正確なパレートフロントの探索の複雑さを劇的に減少させる。
単目的のMDPを1回だけ解き、パレートフロントのエッジをトラバースすることで、パレートフロントの頂点を同定する効率的なアルゴリズムを開発し、既存の手法よりも効率的である。
実証実験により,パレート前線の発見における理論戦略の有効性が実証された。
関連論文リスト
- Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs [82.34567890576423]
我々は,非漸近収束を伴う最適決定主義政策を求めるための決定主義的政策勾配原始双対法を開発した。
D-PGPDの一次-双対反復は、最適正則化原始-双対にサブ線形速度で収束することが証明された。
我々の知る限り、これは連続空間制約型MDPに対する決定論的ポリシー探索法を提案する最初の研究であると思われる。
論文 参考訳（メタデータ） (2024-08-19T14:11:04Z) - Pareto Front Shape-Agnostic Pareto Set Learning in Multi-Objective Optimization [6.810571151954673]
既存の方法は、目的空間における選好ベクトルを決定空間における最適解にマッピングすることに依存する。
提案手法は, 事前知識を必要とせずに, パレート前面の任意の形状を処理し, パレート集合を学習することができる。
論文 参考訳（メタデータ） (2024-08-11T14:09:40Z) - Learning Pareto Set for Multi-Objective Continuous Robot Control [7.853788769559891]
本研究では,高次元ポリシーパラメータ空間におけるパレート集合の連続表現を学習する,単純かつ資源効率のMORLアルゴリズムを提案する。
実験結果から,本手法はトレーニングパラメータを最小にすることで,最高の総合的な性能を達成できることが示唆された。
論文 参考訳（メタデータ） (2024-06-27T06:31:51Z) - UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - UMOEA/D: A Multiobjective Evolutionary Algorithm for Uniform Pareto
Objectives based on Decomposition [19.13435817442015]
多目的最適化(MOO)は、多くのアプリケーションで広く使われている。
従来の手法では、PF全体を表すためにパレートの目的(PF上の粒子)の集合を利用するのが一般的であった。
本稿は,従来のMOO手法で見られる限られた多様性を緩和するため,PF上でのインフォニフォーム分散目的を構築することを提案する。
論文 参考訳（メタデータ） (2024-02-14T08:09:46Z) - Divide and Conquer: Provably Unveiling the Pareto Front with
Multi-Objective Reinforcement Learning [2.5115843173830252]
本稿では,Paretoフロントを単一目的問題列に分解するアルゴリズムIPROを紹介する。
実証的な評価は、IPROが追加のドメイン知識を必要とするメソッドにマッチするか、より優れていることを示している。
問題固有の単目的解法を利用することで、本手法は多目的強化学習を超える応用を約束する。
論文 参考訳（メタデータ） (2024-02-11T12:35:13Z) - Pareto Manifold Learning: Tackling multiple tasks via ensembles of
single-task models [50.33956216274694]
マルチタスク学習(MTL)では、タスクは、ソリューションへの最適化を導くのではなく、互いに達成したパフォーマンスを競い、制限することができる。
重み空間におけるアンサンブル手法であるTextitPareto Manifold Learningを提案する。
論文 参考訳（メタデータ） (2022-10-18T11:20:54Z) - Pareto Set Learning for Expensive Multi-Objective Optimization [5.419608513284392]
膨大な多目的最適化問題は、多くの現実世界のアプリケーションで見られる。
本稿では,MOBOのパレート集合全体を近似する学習に基づく新しい手法を提案する。
論文 参考訳（メタデータ） (2022-10-16T09:41:54Z) - Continuous MDP Homomorphisms and Homomorphic Policy Gradient [51.25171126424949]
MDP準同型の定義を拡張し、連続状態空間における連続的な作用を包含する。
本稿では,政策とMDP準同型写像を同時に学習できるアクター批判アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-15T15:26:49Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳（メタデータ） (2022-09-15T07:22:58Z) - Safe Exploration by Solving Early Terminated MDP [77.10563395197045]
我々は、Early TerminatedP(ET-MDP)の枠組みの下で、安全なRL問題に対処する新しいアプローチを導入する。
まず、ET-MDPを対応するCMDPと同じ最適値関数を持つ非制約アルゴリズムとして定義する。
そこで,文脈モデルに基づく非政治アルゴリズムを提案し,ET-MDPを解き,それに対応するCMDPをより良い性能で解き,学習効率を向上する。
論文 参考訳（メタデータ） (2021-07-09T04:24:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。