論文の概要: Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback

• arxiv url: http://arxiv.org/abs/2510.17103v2
• Date: Mon, 27 Oct 2025 06:46:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 13:14:10.576316
• Title: Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
• Title（参考訳）: Aggregate Bandit Feedback を伴う表在性MDPにおける確率的・対向的損失への適応
• Authors: Shinji Ito, Kevin Jamieson, Haipeng Luo, Arnab Maiti, Taira Tsuchiya,
• Abstract要約: 本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
• 参考スコア（独自算出の注目度）: 61.49239204705301
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model, where the learner observes only the cumulative loss incurred in each episode, rather than individual losses at each state-action pair. While prior work in this setting has focused exclusively on worst-case analysis, we initiate the study of best-of-both-worlds (BOBW) algorithms that achieve low regret in both stochastic and adversarial environments. We propose the first BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback. In the case of known transitions, our algorithms achieve $O(\log T)$ regret in stochastic settings and ${O}(\sqrt{T})$ regret in adversarial ones. Importantly, we also establish matching lower bounds, showing the optimality of our algorithms in this setting. We further extend our approach to unknown-transition settings by incorporating confidence-based techniques. Our results rely on a combination of FTRL over occupancy measures, self-bounding techniques, and new loss estimators inspired by recent advances in online shortest path problems. Along the way, we also provide the first individual-gap-dependent lower bounds and demonstrate near-optimal BOBW algorithms for shortest path problems with bandit feedback.
• Abstract（参考訳）: 学習者は各エピソードにおいて発生した累積損失のみを、各状態対における個人的損失ではなく、観察する。 この環境での以前の研究は、最悪のケース分析にのみ焦点を合わせてきたが、確率的環境と敵対的環境の両方において、後悔の少ないBOBW(Best-of-both-worlds)アルゴリズムの研究を開始する。 本稿では,集合帯域フィードバックを用いた表層表状MDPのための最初のBOBWアルゴリズムを提案する。 既知の遷移の場合、我々のアルゴリズムは確率的に$O(\log T)$後悔し、${O}(\sqrt{T})$後悔する。 重要なことは、この設定におけるアルゴリズムの最適性を示すために、一致した下位境界を確立することである。 我々は、信頼に基づく手法を取り入れることで、未知の遷移設定へのアプローチをさらに拡張する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。 また,帯域幅フィードバックによる最短経路問題に対する最適BOBWアルゴリズムの検証を行った。

関連論文リスト

• Best-of-Both Worlds for linear contextual bandits with paid observations [16.13456643813766]
  本稿では,この問題に対する計算効率の良いBest-of-Both-Worldsアルゴリズムを提案する。 また, 逆数設定では$Theta(T2/3)$のミニマックス最適後悔を達成し, 複数対数的後悔を(破損した)レジームで保証することを示した。
  論文  参考訳（メタデータ） (2025-10-08T18:23:37Z)
• 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)
• Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
  我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。 我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
  論文  参考訳（メタデータ） (2023-07-05T13:52:10Z)
• Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback [35.687473978249535]
  本稿では, 損失関数が時間とともに変化し, 逆選択されるAMDP(Adversarial Markov Decision Processs)に対する後悔について考察する。 Online-Mirror-Descent(OMD)法によるこの問題の研究が急増しているが、Follow-the-Perturbed-Leader(FTPL)法についてはほとんど知られていない。 我々は,帯域幅のフィードバックと遷移を伴う無限水平環境において,AMDPを学習するための最初のノンレグレットアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:50Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。 我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
  論文  参考訳（メタデータ） (2020-02-19T15:41:18Z)

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

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