論文の概要: Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

• arxiv url: http://arxiv.org/abs/2606.31769v1
• Date: Tue, 30 Jun 2026 14:54:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-01 18:27:19.276397
• Title: Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions
• Title（参考訳）: 未知遷移を伴うMDPにおけるデータ依存レグレクト境界の政策最適化
• Abstract要約: ポリシー最適化は、一階、二階、パス長境界において、逆数と損失の両方に適応することができる。 我々は,これらの保証を未知の遷移の下で達成する,楽観的な追従型リーダに基づく新しいアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 15.092125124258592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study policy optimization for online episodic tabular Markov decision processes with unknown transition kernels, aiming for best-of-both-worlds guarantees together with data-dependent regret bounds. Recent work (Dann et al., 2023; Li et al., 2026) has shown that policy optimization can adapt to both adversarial and stochastic losses with first-order, second-order, and path-length bounds, but only under known transitions, leaving open whether such data-dependent guarantees are achievable by policy optimization when the transition kernel is unknown. We resolve this by developing a new algorithm based on optimistic follow-the-regularized-leader that attains these guarantees under unknown transitions. The key ingredient is a new design of optimistic $Q$-function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. Our analysis further identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel. As a result, we obtain first-order, second-order, and path-length bounds with the transition-dependent complexity term while simultaneously achieving gap-dependent $\mathrm{polylog}(T)$ regret in the stochastic regime.
• Abstract（参考訳）: 本研究は,オンライン表層表層マルコフ決定過程を未知のトランジションカーネルを用いて最適化し,データ依存的後悔境界とともに最良世界を保証することを目的とする。 最近の研究 (Dann et al , 2023; Li et al , 2026) では、政策最適化は1次、2次、2次、パス長境界で逆・確率的な損失に適応できるが、既知の遷移の下でのみ適用可能であることが示されている。 我々は、これらの保証を未知の遷移の下で達成する楽観的な追従型リーダに基づく新しいアルゴリズムを開発することで、これを解決する。 鍵となる要素は、楽観的な$Q$関数推定器の新しい設計と、損失予測誤差を通じて推定器バイアスを制御するデータ依存遷移ボーナスである。 我々の分析では、遷移カーネルを推定する本質的なコストを捉える、避けられない遷移依存の複雑性項をさらに特定する。 その結果、遷移依存的な複雑性項と一階、二階、経路長の境界を同時に達成し、確率的体制においてギャップ依存の$\mathrm{polylog}(T)$後悔を達成する。

関連論文リスト

• Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses [0.8984888893275712]
  我々は、LogSumExpソフトマックスポリシーと呼ばれる新しいクラスのポリシーを導入し、実行します。 周期的ポリシーミキシングと正規化された二重更新という2つの新しいアルゴリズムコンポーネントは、被覆数と二重変数の両方を効果的に制御できる。
  論文  参考訳（メタデータ） (2026-05-12T05:02:02Z)
• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  有限-水平線形混合制約マルコフ決定過程における安全強化学習について検討する。 本稿では, 後悔と制約違反境界を実現するプリミティブ・デュアルポリシー最適化アルゴリズムを提案する。 これは、線形混合CMDPと逆効果を持つ最初の証明可能な効率のよいアルゴリズムである。
  論文  参考訳（メタデータ） (2026-03-29T21:51:33Z)
• Data- and Variance-dependent Regret Bounds for Online Tabular MDPs [15.092125124258592]
  両世界の最良なアルゴリズムは, 逆境系における洗練されたデータ依存的後悔境界と, 逆境系における分散依存的後悔境界を実現する。 政策最適化のために、我々のアルゴリズムは同じデータと分散に依存した適応性を、エピソード水平線の要素まで達成する。
  論文  参考訳（メタデータ） (2026-02-02T10:09:29Z)
• SGD with Dependent Data: Optimal Estimation, Regret, and Inference [3.038061705362137]
  勾配降下 (SGD) は, 広範囲の段階的スケジュールと探索率スキームの下で, 独立情報と依存情報の両方に対応できることが示されている。 SGDは統計的に最適な推定誤差と後悔を同時に達成し,既存の結果を拡張し,改善することを示す。 オンラインのスパースレグレッションのために、我々はSGDベースの新しいアルゴリズムを開発し、ストレージの$d$のみを使用し、1イテレーションあたり$O(d)$フロップを必要とする。
  論文  参考訳（メタデータ） (2026-01-04T04:52:11Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization [11.739526562075339]
  ロバスト正規化マルコフ決定過程 (RRMDP) は、値関数の遷移力学に正規化を加えることで、ダイナミクスシフトに頑健なポリシーを学ぶために提案される。 本稿では,リニア関数近似を用いたロバスト正規化ペシミスティック値反復法 (R2PVI) アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-11-27T18:57:03Z)
• Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
  本研究は,完全情報フィードバックの下で,相変わらずの相変わらずの線形混合MDPについて検討した。 本稿では,占領率に基づく手法と政策に基づく手法の利点を組み合わせた新しいアルゴリズムを提案する。 我々のアルゴリズムは$widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, ここで$d$は特徴次元である。
  論文  参考訳（メタデータ） (2024-11-05T13:55:52Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Best of Both Worlds Policy Optimization [33.13041034490332]
  本稿では,正則化器,探索ボーナス,学習率を適切に設計することにより,損失が相反する場合には,より好意的なポリログ$(T)=後悔が得られることを示す。 政策最適化のために、ギャップ依存のポリログ$(T)$後悔境界が示されるのはこれが初めてである。
  論文  参考訳（メタデータ） (2023-02-18T19:46:11Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。 2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。 GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
  論文  参考訳（メタデータ） (2022-09-12T06:53:24Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。 我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
  論文  参考訳（メタデータ） (2020-02-19T15:41:18Z)

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

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