論文の概要: A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

• arxiv url: http://arxiv.org/abs/2610.30801v1
• Date: Thu, 22 Oct 2026 06:26:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-24 02:08:44.236623
• Title: A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback
• Title（参考訳）: Aggregate(Aggregate)帯域フィードバックを用いた逆線形MDPの計算効率とレート最適アルゴリズム
• Abstract要約: 本研究では, 線形マルコフ決定過程について, 未知の遷移, 反対の損失, および帯域フィードバックを用いて検討した。 我々の研究はアルゴリズムタイムのアルゴリズムで最初の$sqrtK$の後悔を与える。
• 参考スコア（独自算出の注目度）: 26.28492097543273
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study episodic linear Markov decision processes with unknown transitions, adversarial losses, and bandit feedback. The state-of-the-art result for this setting (Liu et al., 2024) either achieves $\sqrt{K}$ regret with a computationally inefficient algorithm or achieves suboptimal $K^{3/4}$ regret, where $K$ is the number of episodes. Our work gives the first $\sqrt{K}$ regret with a polynomial-time algorithm. Our method reduces adversarial linear MDPs to adversarial linear bandits whose action set consists of policies' expected feature vectors. The central challenge is that this action set is unknown and can be estimated only through exploration. We address this challenge by constructing an approximate separation oracle for the action set that either generates executable policies from queried features, or refines an outer approximation of the action set. This approach draws inspiration from the reduction of van Erven et al. (2025) for linear contextual bandits and the oracle-efficient linear bandit algorithm of Ito et al. (2019), but additionally deals with the imprecision of the oracle. The resulting algorithm requires only aggregate loss feedback, and to our knowledge. This is the first polynomial-time algorithm for adversarial MDPs with aggregate feedback beyond the tabular case.
• Abstract（参考訳）: 本研究では, 線形マルコフ決定過程について, 未知の遷移, 反対の損失, および帯域フィードバックを用いて検討した。 この設定の最先端の結果(Liu et al , 2024)は、計算的に非効率なアルゴリズムで$\sqrt{K}$後悔を達成するか、あるいはサブ最適の$K^{3/4}$後悔を達成し、ここで$K$はエピソードの数である。 我々の研究は多項式時間アルゴリズムで最初の$\sqrt{K}$後悔を与える。 提案手法は,ポリシーが期待する特徴ベクトルから構成される逆線形帯域に対して,逆線形 MDP を減少させる。 中心的な課題は、このアクションセットが未知であり、探索によってのみ推定可能であることである。 この課題は、クエリされた特徴から実行可能なポリシーを生成するか、あるいはアクションセットの外部近似を洗練させるアクションセットに対して、近似的な分離オラクルを構築することで解決する。 このアプローチは、線形文脈的包帯に対するvan Erven et al (2025) の減少と、Ito et al (2019) のオラクル効率のよい線形包帯アルゴリズム(英語版)から着想を得ているが、さらにオラクルのインプレクションを扱う。 得られたアルゴリズムは、損失の総和フィードバックと知識のみを必要とする。 これは、表のケースを超えた集合フィードバックを持つ逆MDPに対する最初の多項式時間アルゴリズムである。

関連論文リスト

• An Efficient Near-Optimal Algorithm for Adversarial $m$-Set Bandits [13.063864592666777]
  各ラウンドで学習者が$d$アイテムから$m$を選択し、選択した項目の総損失のみを観察する。 結果として得られる作用集合は$K=binomdm$要素を含み、したがって指数関数的に大きい。 本稿では,この構造を利用した計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-08-12T16:28:06Z)
• Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
  対人的マルコフ決定過程における学習の問題を考える。 本稿では,APO-MVPと呼ばれるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-08T08:06:45Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• 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)
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [44.374427255708135]
  線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。 まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。 次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
  論文  参考訳（メタデータ） (2020-07-23T08:23:44Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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