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

• arxiv url: http://arxiv.org/abs/2405.17061v2
• Date: Tue, 05 Nov 2024 02:29:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-06 14:56:09.110106
• 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の新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。 非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。 我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 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 benefits, introducing the non-linear function raises significant challenges in both computational and statistical efficiency. The best-known result of Hwang and Oh [2023] has achieved an $\widetilde{\mathcal{O}}(\kappa^{-1}dH^2\sqrt{K})$ regret, where $\kappa$ is a problem-dependent quantity, $d$ is the feature dimension, $H$ is the episode length, and $K$ is the number of episodes. While this result attains the same rate in $K$ as linear cases, the method requires storing all historical data and suffers from an $\mathcal{O}(K)$ computation cost per episode. Moreover, the quantity $\kappa$ can be exponentially small in the worst case, leading to a significant gap for the regret compared to linear function approximation. In this work, we first address the computational and storage issue by proposing an algorithm that achieves the same regret with only $\mathcal{O}(1)$ cost. Then, we design an enhanced algorithm that leverages local information to enhance statistical efficiency. It not only maintains an $\mathcal{O}(1)$ computation and storage cost per episode but also achieves an improved regret of $\widetilde{O}(dH^2\sqrt{K} + d^2H^2\kappa^{-1})$, nearly closing the gap with linear function approximation. Finally, we establish the first lower bound for MNL function approximation, 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, where $\kappa$ is a problem-dependent amount, $d$ is the feature dimension, $H$ is the episode length, $K$ is the number of episodesである。 この結果は線形の場合と同様に$K$で達成されるが、この方法はすべての履歴データを保存し、エピソード毎に$\mathcal{O}(K)$の計算コストに悩まされる。 さらに、最悪の場合、$\kappa$は指数関数的に小さくなり、線形関数近似と比較して、後悔に対する大きなギャップが生じる。 本研究では,計算と記憶の問題を,$\mathcal{O}(1)$コストで同じ後悔を解くアルゴリズムを提案することで,まず計算と記憶の問題に対処する。 そこで我々は,局所的な情報を利用して統計的効率を向上させるアルゴリズムを設計する。 これは、$\mathcal{O}(1)$計算と1回あたりのストレージコストを維持できるだけでなく、$\widetilde{O}(dH^2\sqrt{K} + d^2H^2\kappa^{-1})$の改善された後悔も達成している。 最後に、MNL関数近似の最初の下界を確立し、結果の最適性を$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)

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

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