論文の概要: Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

• arxiv url: http://arxiv.org/abs/2610.12362v1
• Date: Thu, 08 Oct 2026 17:26:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:54.222316
• Title: Closing the Horizon Gap in Policy Optimization for Adversarial MDPs
• Title（参考訳）: 対立型MDPの政策最適化における水平ギャップの閉鎖
• Abstract要約: 正規化された$Q$関数を使用して、すべての状態-動作ペアに対して共同でローカル更新の安定性を制御する。 得られたアルゴリズムは、既知の遷移に対して$widetilde O(sqrtHS(H+A)T)$、未知遷移に対して$widetilde O(HSsqrtAT)$の高確率後悔境界を得る。 我々は,逆線形混合MDPにアルゴリズムを拡張し,地平面依存性を改良した。
• 参考スコア（独自算出の注目度）: 12.70261661948628
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider policy optimization for online episodic tabular Markov decision processes (MDPs) with adversarial losses and bandit feedback. Policy optimization updates the policy locally at each state and avoids optimization over the occupancy-measure polytope, but its existing regret bounds are larger by a factor of the horizon $H$ than those of occupancy-measure-based algorithms. We close this gap by using regularized $Q$-functions, which allow us to control the stability of the local updates jointly over all state-action pairs rather than separately at each state. The resulting algorithm attains high-probability regret bounds of $\widetilde O(\sqrt{HS(H+A)T})$ for known transitions and $\widetilde O(HS\sqrt{AT})$ for unknown transitions, where $S$ is the number of states, $A$ the number of actions, and $T$ the number of episodes. Both bounds improve the horizon dependence of existing policy optimization bounds, and the latter matches the best-known bound. We further extend the algorithm to adversarial linear-mixture MDPs and obtain the same improvement in the horizon dependence.
• Abstract（参考訳）: 本稿では,オンライン表層表層マルコフ決定プロセス(MDP)の政策最適化について考察する。 政策最適化は、各州でポリシーを更新し、占有度測定ポリトープに対する最適化を避けるが、既存の後悔境界は占有度測定に基づくアルゴリズムよりも地平線係数$H$より大きい。 このギャップを正規化された$Q$-functionsを使用することで、各状態で個別にではなく、すべての状態-動作ペアに対して、局所的な更新の安定性を共同で制御することが可能になります。 得られたアルゴリズムは、既知の遷移に対して$\widetilde O(\sqrt{HS(H+A)T})$と未知の遷移に対して$\widetilde O(HS\sqrt{AT})$の高確率後悔境界を得る。 どちらの境界も既存の政策最適化境界の地平線依存を改善し、後者は最もよく知られた境界と一致する。 さらに, 逆線形混合MDPにアルゴリズムを拡張し, 地平線依存性を同等に改善する。

関連論文リスト

• Best-Effort Policies for Robust Markov Decision Processes [69.60742680559788]
  我々は、ロバスト MDP (RMDPs) として知られる遷移確率の組によるマルコフ決定過程(MDPs)の共通一般化について研究する。 このような政策を最適な堅牢なベストプラクティス(ORBE)政策と呼ぶ。 我々はORBEポリシーが常に存在することを証明し、その構造を特徴付け、標準的なロバストな値反復よりも小さなオーバヘッドで計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-08-11T09:18:34Z)
• Mirror Descent Policy Optimisation for Robust Constrained Markov Decision Processes [12.666842349236788]
  本稿では,ロバストなマルコフ決定過程に対するミラー降下ポリシーの最適化について述べる。 政策勾配法を用いて、ラグランジアン上のポリシー(最大値)と遷移カーネル(最小値)の両方を最適化する。 実験は、制約付きおよび制約なし最適化におけるミラー降下ポリシー最適化の利点を確認する。
  論文  参考訳（メタデータ） (2025-06-29T09:55:52Z)
• Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
  対人的マルコフ決定過程における学習の問題を考える。 本稿では,APO-MVPと呼ばれるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-08T08:06:45Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• Fast Global Convergence of Policy Optimization for Constrained MDPs [17.825031573375725]
  勾配法は最適性ギャップと制約違反の両方に対して$mathcalO(log(T)/T)$大域収束率が得られることを示す。 スレーターの条件が満たされ、事前条件が知られているとき、十分大きなT$に対してゼロ制約違反がさらに保証される。
  論文  参考訳（メタデータ） (2021-10-31T17:46:26Z)
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [113.8752163061151]
  非定常線形カーネルマルコフ決定過程(MDP)におけるエピソード強化学習(RL)の研究 線形最適化アンダーライン最適化アルゴリズム(PROPO)を提案する。 PROPOはスライディングウィンドウベースのポリシー評価と周期的リスタートベースのポリシー改善の2つのメカニズムを特徴としている。
  論文  参考訳（メタデータ） (2021-10-18T02:33:20Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。 ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
  論文  参考訳（メタデータ） (2021-02-22T18:56:26Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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