論文の概要: Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs
- arxiv url: http://arxiv.org/abs/2611.17469v1
- Date: Thu, 12 Nov 2026 19:52:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-16 18:43:16.252169
- Title: Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs
- Title(参考訳): 適応型MDPにおける変数認識ポリシー最適化によるレグレットの改善
- Abstract要約: 本研究は,未知のダイナミックスとフルインフォメーションをともなう表在性対立性MDPについて検討した。
我々は、ポリシー最適化(PO)アルゴリズムVOPOを用いて、削減をインスタンス化する。
また、既知のダイナミクスとトラジェクトリ・バンディットフィードバックにより、VOPOは$widetilde O(sqrtH2SAK)$ regretを達成できることを示す。
- 参考スコア(独自算出の注目度): 42.02979910641523
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study episodic adversarial MDPs with unknown dynamics and full-information rewards and achieve regret with leading term $\widetilde O(\sqrt{H^3SAK})$. Here $H$ is the horizon, $S$ the total number of states across decision layers, $A$ the number of actions, and $K$ the number of episodes. This improves the two incomparable prior leading terms by factors $\sqrt{S/H}$ and $\sqrt{H^3}$, leaving a factor $\sqrt H$ to the lower-bound scale. We give a reduction from unknown to known dynamics for \emph{downstream-dependent} algorithms, whose policy at step $h$ is computed only from information at steps $h+1$ and onward. This reduces the remaining leading-order gap to finding a downstream-dependent known-dynamics algorithm with $\widetilde O(H\sqrt K)$ regret, which would yield the tight $\widetilde O(H\sqrt{SAK})$ leading term for unknown dynamics. We instantiate the reduction with VOPO, a policy optimization (PO) algorithm. Its improved guarantees follow from a variance-aware analysis enabled by a novel bonus, which we call the Stability-Matching Bonus (SMB). VOPO achieves $\widetilde O(\sqrt{H^3K})$ regret under known dynamics with full information; its $\sqrt H$ gap to the target $H\sqrt K$ rate is inherited by our unknown-dynamics guarantee. We also show that with known dynamics and trajectory bandit feedback, VOPO achieves $\widetilde O(\sqrt{H^2SAK})$ regret. Both known-dynamics guarantees improve the corresponding state-of-the-art PO bounds by a factor $\sqrt H$. A matching lower bound establishes that the full-information rate is tight in one parameter regime.
- Abstract(参考訳): 我々は,未知のダイナミックスとフルインフォメーションをともなう表在的敵対的MDPについて検討し,先行項である$\widetilde O(\sqrt{H^3SAK})$で後悔する。
ここで$H$は地平線、$S$は意思決定層全体の状態の総数、$A$はアクションの数、$K$はエピソードの数である。
これにより、因数$\sqrt{S/H}$と$\sqrt{H^3}$の2つの相反する先行項が改善され、因子$\sqrt H$は下界スケールに残される。
ステップ$h$のポリシーは、ステップ$h+1$以降の情報のみから計算される。
これにより、ダウンストリーム依存の既知の力学アルゴリズムを$\widetilde O(H\sqrt K)$ regret とすることで、残りの事前順序ギャップを減らし、未知の力学のリード項である$\widetilde O(H\sqrt{SAK})$が強くなる。
我々は、ポリシー最適化(PO)アルゴリズムVOPOを用いて、削減をインスタンス化する。
改良された保証は、新しいボーナスによって実現された分散認識分析(stable-Matching Bonus, SMB)から従う。
VOPOは、フル情報を持つ既知のダイナミクスの下で、$\widetilde O(\sqrt{H^3K})$ regretを達成し、その$\sqrt H$ ターゲットへのギャップ$H\sqrt K$ は、未知の力学保証によって継承される。
また、既知のダイナミックスとトラジェクトリ・バンディットフィードバックにより、VOPO は $\widetilde O(\sqrt{H^2SAK})$ regret を達成することを示す。
両方の既知の力学は、対応する最先端のPO境界を$\sqrt H$で改善することを保証している。
一致した下界は、全情報レートが1つのパラメータ状態において厳密であることを示す。
関連論文リスト
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
論文 参考訳(メタデータ) (2025-02-06T12:03:24Z) - Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning [6.236688509180343]
政策訓練と展開環境が異なるオフダイナミックス強化学習(RL)について検討する。
We-DRIVE-Uは,平均的最適値$widetildemathcalObig(d H cdot min 1/rho, H/sqrtK big)$を満足するアルゴリズムを提案する。
また、新しいハードインスタンスを構築し、この設定で最初の情報理論の下界を導出する。
論文 参考訳(メタデータ) (2024-09-30T17:21:15Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳(メタデータ) (2023-02-07T02:22:31Z) - Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文 参考訳(メタデータ) (2021-12-21T01:54:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。