論文の概要: Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2604.02196v1
• Date: Thu, 02 Apr 2026 15:51:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:10.900425
• Title: Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes
• Title（参考訳）: 平均コスト多目的マルコフ決定過程におけるパレートフロントの厳密な計算
• Authors: Jiping Luo, Nikolaos Pappas,
• Abstract要約: 多くの通信・制御問題は多目的意思決定プロセス(MOMDP)として採用されている。 前方は凸ポリトープの境界面上の連続的、片方向の直線面であることが示される。
• 参考スコア（独自算出の注目度）: 6.760219793153785
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many communication and control problems are cast as multi-objective Markov decision processes (MOMDPs). The complete solution to an MOMDP is the Pareto front. Much of the literature approximates this front via scalarization into single-objective MDPs. Recent work has begun to characterize the full front in discounted or simple bi-objective settings by exploiting its geometry. In this work, we characterize the exact front in average-cost MOMDPs. We show that the front is a continuous, piecewise-linear surface lying on the boundary of a convex polytope. Each vertex corresponds to a deterministic policy, and adjacent vertices differ in exactly one state. Each edge is realized as a convex combination of the policies at its endpoints, with the mixing coefficient given in closed form. We apply these results to a remote state estimation problem, where each vertex on the front corresponds to a threshold policy. The exact Pareto front and solutions to certain non-convex MDPs can be obtained without explicitly solving any MDP.
• Abstract（参考訳）: 多くの通信および制御問題は多目的マルコフ決定プロセス(MOMDP)として実装されている。 MOMDPの完全な解決策はParetoフロントである。 文献の多くは、単一目的のMDPにスキャラライズすることで、この領域を近似している。 最近の研究は、その幾何学を活かして、ディスカウントされた、あるいは単純な二重目的の設定の全体像を特徴付け始めている。 本研究では,平均コストMOMDPの正確なフロントを特徴付ける。 前方は凸多面体の境界に面した連続した直線面であることを示す。 各頂点は決定論的ポリシーに対応し、隣接する頂点は正確に1つの状態で異なる。 各エッジは、そのエンドポイントにおけるポリシーと、閉じた形で与えられる混合係数の凸結合として実現される。 これらの結果を,各頂点がしきい値ポリシーに対応する遠隔状態推定問題に適用する。 正確なパレートフロントとある種の非凸 MDP に対する解は、明示的に MDP を解くことなく得ることができる。

関連論文リスト

• Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing [51.30643063554434]
  上界の先導手法である三点法は、大高精度半確定プログラム(SDP)の解法に問題を還元する。 我々は、SDP構成を、ポリシーが一連の許容成分からSDP定式化を組み立てる逐次決定過程、SDPゲームとして定式化する。 従来からある幾何学的問題において,モデルに基づく探索が計算の進歩を推し進めることができることを示す。
  論文  参考訳（メタデータ） (2025-12-04T14:11:52Z)
• Scalable Policy-Based RL Algorithms for POMDPs [6.2229686397601585]
  我々は、POMDPモデルを有限状態マルコフ決定プロセス(MDP)に近似することにより、部分観測可能強化学習(PORL)問題を解決するアプローチを検討する。 近似誤差はこの履歴の長さとともに指数関数的に減少することを示す。 我々の知識を最大限に活用するために、我々の有限時間境界は、真の力学がマルコフ的でない設定に標準的TD学習を適用する際に導入された誤差を明示的に定量化する最初のものである。
  論文  参考訳（メタデータ） (2025-10-08T00:33:38Z)
• How to Find the Exact Pareto Front for Multi-Objective MDPs? [28.70863169250383]
  多目的マルコフ決定プロセス (MO-MDPs) は, 現実の意思決定問題は, 単一目的のMDPでは対応できない相反する目的を伴うことが多いため, 注目を集めている。 本研究では,パレートフロントの効率的な発見という課題に対処する。 MO-MDPにおけるパレートフロントの幾何学的構造を調べた結果,鍵となる性質が明らかになった。 この洞察は、すべての政策間でのグローバルな比較を、一つの状態-作用ペアによって異なる決定論的ポリシー間の局所的な探索に変換する。
  論文  参考訳（メタデータ） (2024-10-21T01:03:54Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
  マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。 重みベクトル w でパラメトリした線型効用関数の場合に焦点を当てる。 学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
  論文  参考訳（メタデータ） (2024-05-01T09:34:42Z)
• On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
  我々は、平均報酬マルコフ決定過程(MDP)の文脈における政策勾配の最初の有限時間大域収束解析を示す。 我々の分析によると、ポリシー勾配は、$Oleft(frac1Tright)$のサブリニアレートで最適ポリシーに収束し、$Oleft(log(T)right)$ regretに変換され、$T$は反復数を表す。
  論文  参考訳（メタデータ） (2024-03-11T15:25:03Z)
• First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
  我々はロバストマルコフ決定過程(MDP)の解法を考える。 MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。 $(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
  論文  参考訳（メタデータ） (2022-09-21T18:10:28Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Reward is enough for convex MDPs [30.478950691312715]
  静止分布の凸関数として目標が表現される凸MDPについて検討する。 本稿では,この問題を解決するメタアルゴリズムを提案し,文献における既存のアルゴリズムを統一することを示す。
  論文  参考訳（メタデータ） (2021-06-01T17:46:25Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)

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

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