論文の概要: Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints

• arxiv url: http://arxiv.org/abs/2610.12153v1
• Date: Thu, 08 Oct 2026 15:36:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:54.121325
• Title: Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints
• Title（参考訳）: 確率的硬度制約を伴う対立型MDPの最適回帰に向けて
• Abstract要約: 本研究では,厳しい制約下での対向的損失を伴うエピソード的制約付きマルコフ決定過程について検討する。 我々は,Slaterマージンの楽観的な探索と選択したポリシーの悲観的な評価を組み合わせたMA-OPSを提案する。
• 参考スコア（独自算出の注目度）: 3.924657343062478
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study episodic constrained Markov decision processes with adversarial losses under stochastic hard constraints. Specifically, starting from a known strictly feasible policy with margin $d$, we seek to obtain optimal regret while satisfying the expected cost constraints in every episode. In this setting, Stradi et al. (2025) show that a carefully designed mixing rule attains regret of order $\widetilde{\mathcal{O}}(\sqrt{T}/\min\{d,d^2\})$. Interestingly, they also provide a lower bound of order $Ω(\sqrt{T}/ρ)$ for the same setting, where $ρ$ is the Slater margin of the offline problem and can be much larger than $d$. In this work, we build on their approach to obtain optimal regret dependence on these margins. Specifically, we propose MA-OPS, an algorithm that combines an optimistic search for the Slater margin with a pessimistic evaluation of the selected policies to safely learn a policy with a large feasibility margin. This policy is then used to minimize regret while satisfying the constraints at every episode. In particular, we show that MA-OPS attains regret $\widetilde{\mathcal{O}}(\sqrt{T}/ρ+ 1/(dρ))$. Finally, we provide a matching lower bound, showing that the dependence on $T$, $d$, $ρ$ in the regret bound is optimal up to logarithmic factors.
• Abstract（参考訳）: 本稿では,確率的制約下での対向的損失を伴うエピソード的制約付きマルコフ決定過程について検討する。 具体的には、マージン$d$の厳密な実行可能なポリシから始まり、各エピソードの期待されるコスト制約を満たしつつ、最適な後悔を得ようとしています。 この設定において、Stradi et al (2025) は、慎重に設計された混合規則は順序 $\widetilde{\mathcal{O}}(\sqrt{T}/\min\{d,d^2\})$ の後悔を達成することを示した。 興味深いことに、それらは同じ設定に対して$Ω(\sqrt{T}/ρ)$の下位境界を提供し、$ρ$はオフライン問題のスレーターマージンであり、$d$よりもはるかに大きい。 本研究は,これらの限界に対する最適な後悔の度合いを得るためのアプローチを構築した。 具体的には、スレーターマージンを楽観的に探索するアルゴリズムMA-OPSと、選択したポリシーの悲観的な評価を組み合わせて、大きな可能性マージンを持つポリシーを安全に学習するアルゴリズムを提案する。 このポリシーは、各エピソードの制約を満たしながら後悔を最小限にするために使用される。 特に、MA-OPS は $\widetilde{\mathcal{O}}(\sqrt{T}/ρ+ 1/(dρ))$ となる。 最後に、一致した下界を提供し、後悔境界における$T$, $d$, $ρ$への依存が対数的因子に最適であることを示す。

関連論文リスト

• Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
  我々は、学習者が$m$の腕から$m$の腕を正確に選択する、$m$セット半帯域問題の一般的な場合を考える。 また, Fr'echet 摂動を持つFTPL は, 対向的な設定で, $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ をほぼ最適に再現できることを示す。
  論文  参考訳（メタデータ） (2025-04-09T22:07:01Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  逆制約を伴うオンライン凸最適化(OCO)について検討する。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
  論文  参考訳（メタデータ） (2024-12-11T03:06:42Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Minimax Regret for Stochastic Shortest Path [63.45407095296692]
  我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。 この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。 本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
  論文  参考訳（メタデータ） (2021-03-24T10:11:49Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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