論文の概要: Reinforcement Learning from Adversarial Preferences in Tabular MDPs

• arxiv url: http://arxiv.org/abs/2507.11706v1
• Date: Tue, 15 Jul 2025 20:19:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-17 19:00:11.13834
• Title: Reinforcement Learning from Adversarial Preferences in Tabular MDPs
• Title（参考訳）: タブラルMDPにおける対立選好からの強化学習
• Authors: Taira Tsuchiya, Shinji Ito, Haipeng Luo,
• Abstract要約: 我々は,敵対的嗜好を持つエピソードマルコフ決定プロセス(MDP)の新たな枠組みを導入する。 PbMDP では、標準的なエピソード MDP とは異なり、学習者は2つの候補アーム間の好みを観察する。 我々は、既知遷移の下で、T2/3$という残差境界を達成するアルゴリズムを開発する。
• 参考スコア（独自算出の注目度）: 62.73758165845971
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a new framework of episodic tabular Markov decision processes (MDPs) with adversarial preferences, which we refer to as preference-based MDPs (PbMDPs). Unlike standard episodic MDPs with adversarial losses, where the numerical value of the loss is directly observed, in PbMDPs the learner instead observes preferences between two candidate arms, which represent the choices being compared. In this work, we focus specifically on the setting where the reward functions are determined by Borda scores. We begin by establishing a regret lower bound for PbMDPs with Borda scores. As a preliminary step, we present a simple instance to prove a lower bound of $\Omega(\sqrt{HSAT})$ for episodic MDPs with adversarial losses, where $H$ is the number of steps per episode, $S$ is the number of states, $A$ is the number of actions, and $T$ is the number of episodes. Leveraging this construction, we then derive a regret lower bound of $\Omega( (H^2 S K)^{1/3} T^{2/3} )$ for PbMDPs with Borda scores, where $K$ is the number of arms. Next, we develop algorithms that achieve a regret bound of order $T^{2/3}$. We first propose a global optimization approach based on online linear optimization over the set of all occupancy measures, achieving a regret bound of $\tilde{O}((H^2 S^2 K)^{1/3} T^{2/3} )$ under known transitions. However, this approach suffers from suboptimal dependence on the potentially large number of states $S$ and computational inefficiency. To address this, we propose a policy optimization algorithm whose regret is roughly bounded by $\tilde{O}( (H^6 S K^5)^{1/3} T^{2/3} )$ under known transitions, and further extend the result to the unknown-transition setting.
• Abstract（参考訳）: 本稿では,表在性表在性マルコフ決定過程 (MDPs) の新たな枠組みを導入し,これを優先型MDP (PbMDPs) と呼ぶ。 PbMDPでは、損失の数値が直接観測される標準的なエピソードMDPとは異なり、学習者は、比較される選択を表す2つの候補アーム間の好みを観察する。 本稿では,報奨関数がボルダのスコアによって決定される設定に着目する。 我々はまず、ボルダスコアによるPbMDPに対する後悔の低い境界を確立することから始める。 予備的なステップとして, エピソード当たりのステップ数である$H$, 状態数である$S$, アクション数である$A$, エピソード数である$T$に対する$Omega(\sqrt{HSAT})$の低い境界を証明するための簡単な例を示す。 この構成を活用すると、Bordaスコアを持つPbMDPsに対して$\Omega( (H^2 S K)^{1/3} T^{2/3} )$の後悔の低い境界を導出する。 次に、次数$T^{2/3}$の後悔境界を達成するアルゴリズムを開発する。 まず、すべての占有度に対するオンライン線形最適化に基づく大域的最適化手法を提案し、既知遷移の下では、$\tilde{O}((H^2 S^2 K)^{1/3} T^{2/3} )$の後悔境界を達成する。 しかし、このアプローチは、潜在的に多くの状態に対する最適以下の依存と、計算の非効率さに悩まされる。 この問題に対処するために、約$\tilde{O}( (H^6 S K^5)^{1/3} T^{2/3} )$ で制限されたポリシー最適化アルゴリズムを提案し、その結果を未知の遷移条件に拡張する。

関連論文リスト

• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。 この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。 この設定のための最初のポリシー最適化アルゴリズムを紹介します。
  論文  参考訳（メタデータ） (2025-02-06T12:03:24Z)
• Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
  対人的マルコフ決定過程における学習の問題を考える。 本稿では,APO-MVPと呼ばれるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-08T08:06:45Z)
• Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation [3.2703356989962518]
  非線型関数近似を用いたモデルに基づく強化学習について検討する。 本研究では,無限水平平均逆法と割引逆法の両方に有効である確率効率のよい値反復型アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-06-19T15:29:14Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space [0.0]
  我々は、出生・死亡構造を有するMDPにおける未報告の強化学習の後悔を再考する。 本研究の結果から,従来の学習アルゴリズム sc Ucrl2 のやや遅れたバージョンに対する後悔は,実際には $tildemathcalO(sqrtEAT)$ で表される。
  論文  参考訳（メタデータ） (2023-02-21T13:28:37Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
  本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。 また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
  論文  参考訳（メタデータ） (2021-02-09T07:46:34Z)

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

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