論文の概要: Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs

• arxiv url: http://arxiv.org/abs/2609.38132v1
• Date: Tue, 29 Sep 2026 17:53:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-30 21:28:47.81459
• Title: Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs
• Title（参考訳）: 平均逆弱結合MDPにおけるO(1/N)$Optimality Gapの達成
• Abstract要約: We study average-reward weak-upupled Markov decision process (WCMDPs)。 アームが同一のモデルパラメータ、複数のアクション、状態依存と行動依存のコストを持つような設定について検討する。
• 参考スコア（独自算出の注目度）: 20.60194121026095
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study average-reward weakly-coupled Markov decision processes (WCMDPs), where a WCMDP consists of $N$ smaller MDPs, called arms, that share multiple per-step budget constraints. We consider the setting where the arms have identical model parameters, multiple actions, and state- and action-dependent costs. For restless bandits (RBs), a well-studied special case of WCMDPs, prior work has developed policies that achieve an $O(1/\sqrt{N})$ optimality gap under general conditions, and has further identified conditions under which policies can achieve a better-than-$1/\sqrt{N}$ optimality gap. However, for general WCMDPs, no prior result achieves an optimality gap better than $1/\sqrt{N}$. In this paper, we identify conditions analogous to those for RBs under which a better-than-$1/\sqrt{N}$ optimality gap is achievable, and design a policy that attains an $O(1/N)$ optimality gap. Notably, unlike prior approaches based on generalizing priority orderings, our policy is not priority-based but rather is designed to induce locally linear mean-field dynamics.
• Abstract（参考訳）: 我々は、WCMDPが、複数のステップ毎の予算制約を共有するアームと呼ばれる、より小さなMDPからなる平均再帰弱結合マルコフ決定プロセス(WCMDP)について検討する。 アームが同一のモデルパラメータ、複数のアクション、状態依存と行動依存のコストを持つような設定について検討する。 WCMDPのよく研究された特殊なケースであるレスレス・バンディット(RBs)について、先行研究は一般的な条件下でO(1/\sqrt{N})$最適性ギャップを達成するためのポリシーを開発し、ポリシーが1/\sqrt{N}$最適性ギャップを達成できる条件をさらに特定した。 しかし、一般の WCMDP に対して、1/\sqrt{N}$ よりも良い最適性ギャップを得られるような事前の結果は得られない。 本稿では,1/\sqrt{N}$の最適性ギャップが達成可能なRBと類似した条件を特定し,O(1/N)$の最適性ギャップを達成するポリシーを設計する。 特に、優先順位付けの一般化に基づく従来のアプローチとは異なり、我々のポリシーは優先順位に基づくものではなく、局所線形平均場力学を誘導するように設計されている。

関連論文リスト

• Ratio-Variance Regularized Policy Optimization [64.95520246570446]
  ポリシ比の分散を明示的に制約することは、信頼領域の制約に対する原則的な局所近似をもたらすことを示す。 本稿では,この制約を実装したR2bf VPO$(Ratio-Variance Regularized Policy Optimization)を紹介する。
  論文  参考訳（メタデータ） (2026-05-26T09:53:42Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Best-Effort Policies for Robust Markov Decision Processes [69.60742680559788]
  我々は、ロバスト MDP (RMDPs) として知られる遷移確率の組によるマルコフ決定過程(MDPs)の共通一般化について研究する。 このような政策を最適な堅牢なベストプラクティス(ORBE)政策と呼ぶ。 我々はORBEポリシーが常に存在することを証明し、その構造を特徴付け、標準的なロバストな値反復よりも小さなオーバヘッドで計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-08-11T09:18:34Z)
• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。 私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。 オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
  論文  参考訳（メタデータ） (2023-09-27T04:33:09Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
  最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。 次に,政策最適化におけるコミット率の概念を紹介する。 第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
  論文  参考訳（メタデータ） (2021-10-29T06:35:44Z)

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

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