論文の概要: Learning Markov Decision Processes under Fully Bandit Feedback

• arxiv url: http://arxiv.org/abs/2602.02260v1
• Date: Mon, 02 Feb 2026 16:03:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:34.275044
• Title: Learning Markov Decision Processes under Fully Bandit Feedback
• Title（参考訳）: 完全帯域フィードバックによるマルコフ決定過程の学習
• Authors: Zhengjia Zhuo, Anupam Gupta, Viswanath Nagarajan,
• Abstract要約: 強化学習における標準的な前提は、エージェントが関連する決定プロセス(MDP)において、訪れた状態-行動ペアをすべて観察するということである。 我々は,$widetildeO(sqrtT)$ regretのエピソードMDPに対して,最初の効率的な帯域幅学習アルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 7.462282493793144
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A standard assumption in Reinforcement Learning is that the agent observes every visited state-action pair in the associated Markov Decision Process (MDP), along with the per-step rewards. Strong theoretical results are known in this setting, achieving nearly-tight $Θ(\sqrt{T})$-regret bounds. However, such detailed feedback can be unrealistic, and recent research has investigated more restricted settings such as trajectory feedback, where the agent observes all the visited state-action pairs, but only a single \emph{aggregate} reward. In this paper, we consider a far more restrictive ``fully bandit'' feedback model for episodic MDPs, where the agent does not even observe the visited state-action pairs -- it only learns the aggregate reward. We provide the first efficient bandit learning algorithm for episodic MDPs with $\widetilde{O}(\sqrt{T})$ regret. Our regret has an exponential dependence on the horizon length $\H$, which we show is necessary. We also obtain improved nearly-tight regret bounds for ``ordered'' MDPs; these can be used to model classical stochastic optimization problems such as $k$-item prophet inequality and sequential posted pricing. Finally, we evaluate the empirical performance of our algorithm for the setting of $k$-item prophet inequalities; despite the highly restricted feedback, our algorithm's performance is comparable to that of a state-of-art learning algorithm (UCB-VI) with detailed state-action feedback.
• Abstract（参考訳）: 強化学習における標準的な仮定は、エージェントが関連するマルコフ決定プロセス(MDP)で訪れた全ての状態-作用対を、ステップごとの報酬とともに観察するということである。 この設定では強い理論的な結果が知られており、ほぼ8つの$(\sqrt{T})$-regret境界を達成している。 しかし、そのような詳細なフィードバックは非現実的であり、最近の研究では、エージェントが訪れた全ての状態-行動ペアを観察するが、単一の 'emph{aggregate} 報酬のみを観察する、軌道フィードバックのようなより制限された設定を調査している。 本稿では, エージェントが訪れた状態と行動のペアを観察することさえせず, 合計報酬のみを学習する, エピソジックなMDPに対するより制限的な ‘fully bandit' フィードバックモデルについて考察する。 エピソードMDPに対して, $\widetilde{O}(\sqrt{T})$ regret を用いた最初の効率的な帯域幅学習アルゴリズムを提供する。 我々の後悔は地平線長$\H$に指数関数的に依存しており、これは必要であることを示している。 また, '`ordered'' の MDP に対する約28 個の後悔境界を改良し,$k$-item の預言不等式や逐次投稿価格などの古典的確率的最適化問題のモデル化に使用することができる。 最後に, 提案アルゴリズムは, 高度に制限されたフィードバックにもかかわらず, 詳細な状態フィードバックを持つ最先端学習アルゴリズム (UCB-VI) に匹敵する, 約$k$-itemの預言不等式の設定に対して, 経験的性能を評価する。

関連論文リスト

• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
  論文  参考訳（メタデータ） (2025-10-20T02:28:08Z)
• Reinforcement Learning with Segment Feedback [56.54271464134885]
  状態ごとの反応フィードバックと軌道フィードバックのギャップを埋める一般的なパラダイムを提供するRLというモデルを考える。 バイナリフィードバックの下では、$m$のセグメント数の増加は指数率で後悔を減少させるが、驚くべきことに、和フィードバックの下では、$m$の増加は後悔を著しく減少させるものではない。
  論文  参考訳（メタデータ） (2025-02-03T23:08:42Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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