論文の概要: Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation

• arxiv url: http://arxiv.org/abs/2405.17061v3
• Date: Thu, 16 Jan 2025 14:45:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-17 18:31:25.116014
• Title: Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation
• Title（参考訳）: 多項ロジット関数近似を用いた高能率強化学習
• Authors: Long-Fei Li, Yu-Jie Zhang, Peng Zhao, Zhi-Hua Zhou,
• Abstract要約: 本稿では,MNL関数近似を用いたMDPの新たなクラスについて検討し,状態空間上の確率分布の正当性を保証する。 その大きな利点にもかかわらず、非線形関数を組み込むことは、統計的および計算効率の両方において重大な課題を提起する。 我々は,$widetildemathcalO(dH2sqrtK + kappa-1d2H2)$を後悔するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 67.8414514524356
• License:
• Abstract: We study a new class of MDPs that employs multinomial logit (MNL) function approximation to ensure valid probability distributions over the state space. Despite its significant benefits, incorporating the non-linear function raises substantial challenges in both statistical and computational efficiency. The best-known result of Hwang and Oh [2023] has achieved an $\widetilde{\mathcal{O}}(\kappa^{-1}dH^2\sqrt{K})$ regret upper bound, where $\kappa$ is a problem-dependent quantity, $d$ is the feature dimension, $H$ is the episode length, and $K$ is the number of episodes. However, we observe that $\kappa^{-1}$ exhibits polynomial dependence on the number of reachable states, which can be as large as the state space size in the worst case and thus undermines the motivation for function approximation. Additionally, their method requires storing all historical data and the time complexity scales linearly with the episode count, which is computationally expensive. In this work, we propose a statistically efficient algorithm that achieves a regret of $\widetilde{\mathcal{O}}(dH^2\sqrt{K} + \kappa^{-1}d^2H^2)$, eliminating the dependence on $\kappa^{-1}$ in the dominant term for the first time. We then address the computational challenges by introducing an enhanced algorithm that achieves the same regret guarantee but with only constant cost. Finally, we establish the first lower bound for this problem, justifying the optimality of our results in $d$ and $K$.
• Abstract（参考訳）: 本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。 その大きな利点にもかかわらず、非線形関数を組み込むことは、統計的および計算効率の両方において重大な課題を提起する。 Hwang と Oh [2023] の最もよく知られている結果は、$\widetilde{\mathcal{O}}(\kappa^{-1}dH^2\sqrt{K})$ regret upper bound, where $\kappa$ is a problem-dependent amount, $d$ is the feature dimension, $H$ is the episode length, $K$ is the number of episodes。 しかし、$\kappa^{-1}$は到達可能な状態の数に多項式依存を示し、これは最悪の場合の状態空間サイズと同じくらいの大きさであり、したがって関数近似の動機を損なう。 さらに、その手法では、すべての履歴データを保存し、計算コストのかかるエピソード数とともに、時間複雑性を線形にスケールする必要がある。 本研究では,$\widetilde{\mathcal{O}}(dH^2\sqrt{K} + \kappa^{-1}d^2H^2)$を後悔し,初めて支配的項における$\kappa^{-1}$への依存を排除した統計的に効率的なアルゴリズムを提案する。 次に、同じ後悔の保証を一定コストで達成する拡張アルゴリズムを導入することで、計算上の課題に対処する。 最後に、この問題に対する最初の下限を確立し、結果の最適性を$d$と$K$で正当化する。

関連論文リスト

• Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism [1.4999444543328293]
  本稿では,新しいコストと報酬関数推定器に基づくモデルベースアルゴリズムを提案する。 我々のアルゴリズムは、$widetildemathcalO((bar C - bar C_b)-1H2.5 SsqrtAK)$の残念な上限を達成する。
  論文  参考訳（メタデータ） (2024-10-14T04:51:06Z)
• Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation [8.274693573069442]
  多項ロジスティック(MNL)関数近似を用いた強化学習について検討した。 頻繁な後悔の保証を有するランダムな探索を伴う確率的効率のアルゴリズムを提案する。 数値実験により提案アルゴリズムの優れた性能を示す。
  論文  参考訳（メタデータ） (2024-05-30T15:39:19Z)
• Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds [26.277745106128197]
  本研究では,線形関数近似を用いた強化学習におけるそのような報奨の課題に対処する。 我々はまず,重み付き線形包帯に対するtextscHeavy-OFUL というアルゴリズムを設計し,インセンス依存の$T$-round regret of $tildeObig を実現した。 我々の結果は、オンライン回帰問題全般において、重くノイズを扱うことに独立した関心を持つような、新しい自己正規化集中不等式によって達成される。
  論文  参考訳（メタデータ） (2023-06-12T02:56:09Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• 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)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。 我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。 また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
  論文  参考訳（メタデータ） (2021-02-17T18:54:08Z)

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

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