論文の概要: Faster Fixed-Point Methods for Multichain MDPs

• arxiv url: http://arxiv.org/abs/2506.20910v1
• Date: Thu, 26 Jun 2025 00:31:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-27 19:53:09.922995
• Title: Faster Fixed-Point Methods for Multichain MDPs
• Title（参考訳）: マルチチェーンMDPの高速固定点法
• Authors: Matthew Zurek, Yudong Chen,
• Abstract要約: 平均回帰基準の下で,一般(多鎖)マルコフ決定過程(MDP)を解くための値イテレーション(VI)アルゴリズムについて検討する。
• 参考スコア（独自算出の注目度）: 6.996002801232415
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study value-iteration (VI) algorithms for solving general (a.k.a. multichain) Markov decision processes (MDPs) under the average-reward criterion, a fundamental but theoretically challenging setting. Beyond the difficulties inherent to all average-reward problems posed by the lack of contractivity and non-uniqueness of solutions to the Bellman operator, in the multichain setting an optimal policy must solve the navigation subproblem of steering towards the best connected component, in addition to optimizing long-run performance within each component. We develop algorithms which better solve this navigational subproblem in order to achieve faster convergence for multichain MDPs, obtaining improved rates of convergence and sharper measures of complexity relative to prior work. Many key components of our results are of potential independent interest, including novel connections between average-reward and discounted problems, optimal fixed-point methods for discounted VI which extend to general Banach spaces, new sublinear convergence rates for the discounted value error, and refined suboptimality decompositions for multichain MDPs. Overall our results yield faster convergence rates for discounted and average-reward problems and expand the theoretical foundations of VI approaches.
• Abstract（参考訳）: 本研究では, 一般(多鎖)マルコフ決定過程 (MDP) を, 基本的かつ理論的に困難な条件下で解くための値イテレーション (VI) アルゴリズムについて検討する。 ベルマン作用素に対する解の縮約性や非特異性の欠如によって生じる全ての平均逆問題に固有の困難に加えて、最適ポリシでは、各コンポーネント内での長期性能の最適化に加えて、最良の連結コンポーネントへの操舵のナビゲーションサブプロブレムを解決しなければならない。 我々は,マルチチェーンMDPの高速収束を実現するために,このナビゲーションサブプロブレムをよりよく解くアルゴリズムを開発した。 この結果の重要な要素は, 平均再帰問題と割引問題との新たな接続, 一般的なバナッハ空間に拡張したディスカウントVIの最適固定点法, 割引値誤差に対する新しいサブ線形収束率, マルチチェーンMDPに対する改良された準最適分解など, 潜在的な独立性である。 総じて, 縮退問題と平均回帰問題に対する収束速度を高速化し, VIアプローチの理論的基礎を拡大した。

関連論文リスト

• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。 大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。 統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
  論文  参考訳（メタデータ） (2025-05-13T16:47:00Z)
• Deep Distributed Optimization for Large-Scale Quadratic Programming [15.773581194857085]
  本稿では,大規模擬似プログラミング(QP)問題に対処するために設計された,ディープラーニング支援型分散最適化アーキテクチャを提案する。 DeepDistributedQPは、小さな問題をトレーニングし、同じポリシーを使用してもっと大きな問題(最大50K変数と150K制約)をスケールすることで、強力な一般化を示す。
  論文  参考訳（メタデータ） (2024-12-11T09:45:00Z)
• On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes [11.868402302316131]
  本稿では,マルコフ決定過程(MDP)の強化学習(RL)アルゴリズムを,平均回帰基準の下で解析する。 本稿では,MDPを弱通信する反復RVI法のモデル自由集合であるRVI(Rexent Value)に基づくQ-learningアルゴリズムに着目した。
  論文  参考訳（メタデータ） (2024-08-29T04:57:44Z)
• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。 ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。 提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
  論文  参考訳（メタデータ） (2023-10-10T00:21:10Z)
• Optimization and Optimizers for Adversarial Robustness [10.279287131070157]
  本稿では,汎用的制約最適化解法と制約Foldingを融合した新しいフレームワークを提案する。 信頼性に関して、PWCFは、ソリューションの品質を評価するための定常度測定と実現可能性テストのソリューションを提供する。 さらに、損失、摂動モデル、最適化アルゴリズムの様々な組み合わせを用いて、これらの問題を解決するための解の異なるパターンについて検討する。
  論文  参考訳（メタデータ） (2023-03-23T16:22:59Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
  論文  参考訳（メタデータ） (2022-10-03T16:05:43Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• 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)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  複数変数の非プロブレムに挑戦する新しい解を提案する。 提案手法では,他の手法が一般的に失敗するケースに対して,効果的なイテレーションを実現することができる。
  論文  参考訳（メタデータ） (2020-09-09T10:45:00Z)

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

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