論文の概要: ID policy (with reassignment) is asymptotically optimal for heterogeneous weakly-coupled MDPs

• arxiv url: http://arxiv.org/abs/2502.06072v2
• Date: Thu, 20 Feb 2025 04:25:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-21 14:24:24.002374
• Title: ID policy (with reassignment) is asymptotically optimal for heterogeneous weakly-coupled MDPs
• Title（参考訳）: IDポリシー(再割り当てを伴う)は異種弱結合型MDPに対して漸近的に最適である
• Authors: Xiangcheng Zhang, Yige Hong, Weina Wang,
• Abstract要約: 弱結合マルコフ決定過程(WCMDP)の完全不均一な設定について検討する。 軽微な仮定では、IDポリシーの自然な適応は、元々はWCMDPの同質な特殊ケースとして提案されていたが、N$が大きくなるにつれて、腕ごとの平均報酬が1/sqrtNで$O (1/sqrtN)$の最適性ギャップを達成できることが示される。
• 参考スコア（独自算出の注目度）: 3.850666668546735
• License:
• Abstract: Heterogeneity poses a fundamental challenge for many real-world large-scale decision-making problems but remains largely understudied. In this paper, we study the fully heterogeneous setting of a prominent class of such problems, known as weakly-coupled Markov decision processes (WCMDPs). Each WCMDP consists of $N$ arms (or subproblems), which have distinct model parameters in the fully heterogeneous setting, leading to the curse of dimensionality when $N$ is large. We show that, under mild assumptions, a natural adaptation of the ID policy, although originally proposed for a homogeneous special case of WCMDPs, in fact achieves an $O(1/\sqrt{N})$ optimality gap in long-run average reward per arm for fully heterogeneous WCMDPs as $N$ becomes large. This is the first asymptotic optimality result for fully heterogeneous average-reward WCMDPs. Our techniques highlight the construction of a novel projection-based Lyapunov function, which witnesses the convergence of rewards and costs to an optimal region in the presence of heterogeneity.
• Abstract（参考訳）: 異質性は多くの現実世界の大規模意思決定問題に対して根本的な課題を提起するが、いまだほとんど検討されていない。 本稿では,弱い結合型マルコフ決定過程 (WCMDP) として知られる,そのような問題の一級の完全均一な設定について検討する。 各WCMDPは$N$アーム(またはサブプロブレム)で構成されており、完全に不均一な設定で異なるモデルパラメータを持ち、$N$が大きければ次元性の呪いにつながる。 軽微な仮定の下では、IDポリシーの自然な適応は、元々はWCMDPの同種特殊ケースに対して提案されていたが、実際には$O(1/\sqrt{N})$Optimity gap in long-run average reward per arm for fully heterogeneous WCMDPs as $N$ is largeであることを示す。 これは完全不均一平均逆WCMDPに対する最初の漸近最適結果である。 この手法は、射影に基づく新しいリアプノフ関数の構築を強調し、不均一性の存在下での最適領域への報酬とコストの収束を目撃する。

関連論文リスト

• Mechanism design with multi-armed bandit [8.013444110633223]
  自動メカニズム設計の一般的なアプローチは、ソリューションが望ましい特性を持つメカニズムを提供する線形プログラム(LP)を定式化することである。 我々は、効率、インセンティブ整合性、強い予算収支(SBB)、個人合理性(IR)の標準的な特性を達成するメカニズムを提供する、そのようなLPのための最適解のクラスを解析的に導出した。
  論文  参考訳（メタデータ） (2024-11-30T03:59:36Z)
• Achieving O(1/N) Optimality Gap in Restless Bandits through Diffusion Approximation [21.34216861973257]
  有限地平線レスレスト・マルチアーマッド・バンドイット(RMAB)問題を$N$等質アームで検討する。 我々の新しい拡散解法は、LP上界よりも真の最適値に対して$O (1/sqrtN)$の最適性ギャップを達成する。 これらの洞察は、縮退の有無にかかわらず、RMABに対して$O (1/sqrtN)$Optimity gapを超えるポリシーを構築するための道を開く。
  論文  参考訳（メタデータ） (2024-10-19T06:29:18Z)
• Sample-Efficient Constrained Reinforcement Learning with General Parameterization [35.22742439337603]
  エージェントの目標は、無限の地平線上で期待される割引報酬の和を最大化することである。 我々は,世界最適性ギャップを$epsilon$で保証し,制約違反を$epsilon$で保証するPrimal-Dual Accelerated Natural Policy Gradient (PD-ANPG)アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-17T08:39:05Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
  我々はロバストマルコフ決定過程(MDP)の解法を考える。 MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。 $(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
  論文  参考訳（メタデータ） (2022-09-21T18:10:28Z)
• DeepHAM: A Global Solution Method for Heterogeneous Agent Models with Aggregate Shocks [9.088303226909277]
  ヘテロジニアスエージェントモデル(DeepHAM$)のための,効率よく,信頼性が高く,解釈可能なグローバルソリューション法である$textitDeep学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-29T03:09:19Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  本稿では,平均場近似ポリシ最適化(MF-PPO)アルゴリズムを提案する。 我々は,MF-PPOが収束のサブ線形速度で世界的最適政策を達成することを証明した。 特に、置換不変ニューラルアーキテクチャによって引き起こされる誘導バイアスは、MF-PPOが既存の競合より優れていることを示す。
  論文  参考訳（メタデータ） (2021-05-18T04:35:41Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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