論文の概要: 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$で正当化する。

関連論文リスト

• Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation [8.274693573069442]
  多項ロジスティック(MNL)関数近似を用いた強化学習について検討した。 頻繁な後悔の保証を有するランダムな探索を伴う確率的効率のアルゴリズムを提案する。 数値実験により提案アルゴリズムの優れた性能を示す。
  論文  参考訳（メタデータ） (2024-05-30T15:39:19Z)
• 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)
• Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation [25.60689712525918]
  本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。 本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
  論文  参考訳（メタデータ） (2022-06-23T06:04:21Z)
• Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP [31.62899359543925]
  線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。 我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。 第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
  論文  参考訳（メタデータ） (2021-12-18T06:47:31Z)
• 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)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Convergence of Sparse Variational Inference in Gaussian Processes Regression [29.636483122130027]
  計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
  論文  参考訳（メタデータ） (2020-08-01T19:23:34Z)

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

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