論文の概要: Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2602.01295v2
• Date: Tue, 03 Feb 2026 07:17:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-04 13:28:03.719591
• Title: Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes
• Title（参考訳）: 重機型マルコフ決定過程のベスト・オブ・ボトム・ワールド
• Authors: Yu Chen, Yuhao Liu, Jiatai Huang, Yihan Du, Longbo Huang,
• Abstract要約: 重み付きフィードバック(HTMDP)を用いたマルコフ決定過程の検討 HTMDPの既存のアプローチは、環境において保守的であり、敵国体制では適応性が欠如している。 対戦環境におけるインスタンス依存の後悔と自己拘束環境における対数的インスタンス依存の後悔を保証するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 40.463324424591775
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We investigate episodic Markov Decision Processes with heavy-tailed feedback (HTMDPs). Existing approaches for HTMDPs are conservative in stochastic environments and lack adaptivity in adversarial regimes. In this work, we propose algorithms HT-FTRL-OM and HT-FTRL-UOB for HTMDPs that achieve Best-of-Both-Worlds (BoBW) guarantees: instance-independent regret in adversarial environments and logarithmic instance-dependent regret in self-bounding (including the stochastic case) environments. For the known transition setting, HT-FTRL-OM applies the Follow-The-Regularized-Leader (FTRL) framework over occupancy measures with novel skipping loss estimators, achieving a $\widetilde{O}(T^{1/α})$ regret bound in adversarial regimes and a $O(\log T)$ regret in stochastic regimes. Building upon this framework, we develop a novel algorithm HT-FTRL-UOB to tackle the more challenging unknown-transition setting. This algorithm employs a pessimistic skipping loss estimator and achieves a $\widetilde{O}(T^{1/α} + \sqrt{T})$ regret in adversarial regimes and a $O(\log^2(T))$ regret in stochastic regimes. Our analysis overcomes key barriers through several technical insights, including a local control mechanism for heavy-tailed shifted losses, a new suboptimal-mass propagation principle, and a novel regret decomposition that isolates transition uncertainty from heavy-tailed estimation errors and skipping bias.
• Abstract（参考訳）: 重み付きフィードバック(HTMDP)を用いたマルコフ決定過程について検討した。 HTMDPの既存のアプローチは、確率的環境においては保守的であり、敵国体制では適応性が欠如している。 本研究では,HTMDP に対する HT-FTRL-OM と HT-FTRL-UOB を用いて,Best-of-Both-Worlds (BoBW) の保証を実現するアルゴリズムを提案する。 既知の遷移設定について、HT-FTRL-OMは、新規スキッピング損失推定器による占有度測定にFollow-The-Regularized-Leader (FTRL) フレームワークを適用し、敵の政権における後悔の束縛を$\widetilde{O}(T^{1/α})と$O(\log T)$後悔の束縛を達成した。 この枠組みに基づいて,未知の遷移条件に対処する新しいアルゴリズムHT-FTRL-UOBを開発した。 このアルゴリズムは悲観的なスキップ損失推定器を使用し、対数的レジームでは$\widetilde{O}(T^{1/α} + \sqrt{T})$後悔、確率的レジームでは$O(\log^2(T))$後悔を達成する。 我々の分析は、重み付きシフト損失の局所制御機構、新しい準最適質量伝播原理、重み付き推定誤差とスキップバイアスから遷移不確かさを分離する新たな後悔分解など、いくつかの技術的洞察を通じて重要な障壁を克服する。

関連論文リスト

• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 本稿では,ウィンドウ/リスタートベースアルゴリズムと同様に,より単純な重みに基づくアルゴリズムを提案する。 我々のフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2026-01-03T04:50:21Z)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
  論文  参考訳（メタデータ） (2025-10-20T02:28:08Z)
• On the Power of Perturbation under Sampling in Solving Extensive-Form Games [56.013335390600524]
  本研究では, サンプリング対象の広義ゲームにおいて, 摂動がいかにしてFTRL(Follow-the-Regularized-Leader)アルゴリズムを改良するかを検討する。 我々は、textitPerturbed FTRLアルゴリズムの統一フレームワークを提案し、PFTRL-KLとPFTRL-RKLの2つの変種について検討する。
  論文  参考訳（メタデータ） (2025-01-28T00:29:38Z)
• uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs [33.262918224598614]
  本稿では,HTMAB(Heavy-Tailed Multi-Armed Bandits)問題に対する新しいアルゴリズムを提案する。 我々の新しいアルゴリズムユニは、Best-of-Both-Worlds(BoBW)特性を楽しみ、両環境とも最適に機能する。 我々の知る限り、UniINFは重み付きMAB問題に対するBoBW特性を達成する最初のパラメータフリーアルゴリズムである。
  論文  参考訳（メタデータ） (2024-10-04T09:55:44Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

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

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