論文の概要: Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback

• arxiv url: http://arxiv.org/abs/2411.06739v1
• Date: Mon, 11 Nov 2024 06:19:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-12 14:08:29.856614
• Title: Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback
• Title（参考訳）: 未知遷移と帯域フィードバックを持つ逆向き低ランクMPPのビーティング
• Authors: Haolin Liu, Zakaria Mhammedi, Chen-Yu Wei, Julian Zimmert,
• Abstract要約: 低位のMDPが一定の移行と敵対的な損失を被ったことを後悔している。 モデルベースとモデルフリーなアルゴリズムの両方を提案し、$poly(d, A, H)T2/3$ regretとする。 また、$poly(d, A, H)T4/5$ regret を用いたオラクル効率の良いモデルフリーアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 31.75924056431108
• License:
• Abstract: We consider regret minimization in low-rank MDPs with fixed transition and adversarial losses. Previous work has investigated this problem under either full-information loss feedback with unknown transitions (Zhao et al., 2024), or bandit loss feedback with known transition (Foster et al., 2022). First, we improve the $poly(d, A, H)T^{5/6}$ regret bound of Zhao et al. (2024) to $poly(d, A, H)T^{2/3}$ for the full-information unknown transition setting, where d is the rank of the transitions, A is the number of actions, H is the horizon length, and T is the number of episodes. Next, we initiate the study on the setting with bandit loss feedback and unknown transitions. Assuming that the loss has a linear structure, we propose both model based and model free algorithms achieving $poly(d, A, H)T^{2/3}$ regret, though they are computationally inefficient. We also propose oracle-efficient model-free algorithms with $poly(d, A, H)T^{4/5}$ regret. We show that the linear structure is necessary for the bandit case without structure on the reward function, the regret has to scale polynomially with the number of states. This is contrary to the full-information case (Zhao et al., 2024), where the regret can be independent of the number of states even for unstructured reward function.
• Abstract（参考訳）: 低位のMDPでは, 変化が一定であり, 敵の損失も少なく, 後悔の最小化を考慮に入れている。 これまでの研究では、未知の遷移を持つ全情報損失フィードバック(Zhao et al , 2024)や、既知の遷移を持つ帯域損失フィードバック(Foster et al , 2022)の下でこの問題を調査してきた。 まず、Zhao et al (2024) の $poly(d, A, H)T^{5/6}$ regret bound of Zhao et al (2024) を $poly(d, A, H)T^{2/3}$ に改良する。 次に,帯域損失フィードバックと未知遷移を用いた設定に関する研究を開始する。 損失が線形構造であることを仮定すると、計算的に非効率であるにもかかわらず、$poly(d, A, H)T^{2/3}$ regretを達成するモデルベースとモデルフリーアルゴリズムの両方を提案する。 また、$poly(d, A, H)T^{4/5}$ regret を用いたオラクル効率のよいモデルフリーアルゴリズムを提案する。 報奨関数の構造を持たないバンディットの場合、線形構造は必要であり、後悔は状態の数と多項式的にスケールしなければならないことを示す。 これは全情報の場合(Zhao et al , 2024)とは反対であり、未構造化の報酬関数であっても、後悔は状態の数から独立することができる。

関連論文リスト

• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback [30.23951525723659]
  本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。 政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
  論文  参考訳（メタデータ） (2023-11-14T03:12:43Z)
• No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions [39.864174754882754]
  対戦型マルコフ決定プロセスのための既存のオンライン学習アルゴリズムは、T$ラウンドのインタラクションの後、後悔して$O(sqrtT)を達成します。 これは、対向遷移関数が非回帰学習を不可能にすることが示されているためである。 我々は、$widetildeO(sqrtT + CtextsfP)$ regretというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-27T06:10:17Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition [49.78053380710322]
  我々は,エピソードT$でマルコフ決定過程を学習する上で,両世界の最良の問題を考える。 最近の[Jin and Luo, 2020]による研究は、固定遷移が分かっているときにこの目標を達成する。 本研究では,同じFollow-the-Regularized-Leader(textFTRL$)フレームワークを新しいテクニックのセットと組み合わせることで,この問題を解決する。
  論文  参考訳（メタデータ） (2021-06-08T05:46:35Z)
• 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)
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case [29.99619764839178]
  敵の費用と未知の遷移を伴う最短経路問題に対して,大きな進展をみせている。 具体的には、全情報設定を後悔する$widetildeO(sqrtS3A2DT_star K)を実現するアルゴリズムを開発する。 私たちはまた、最も難しい組み合わせとして、敵のコストによる盗聴フィードバックと未知の移行を最初に検討しています。
  論文  参考訳（メタデータ） (2021-02-10T06:33:04Z)

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

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