論文の概要: Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation

• arxiv url: http://arxiv.org/abs/2405.20165v2
• Date: Thu, 31 Oct 2024 05:14:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 16:59:10.493362
• Title: Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation
• Title（参考訳）: 多項ロジスティック関数近似を用いた強化学習のためのランダム化探索
• Authors: Wooseong Cho, Taehyun Hwang, Joongkyu Lee, Min-hwan Oh,
• Abstract要約: 多項ロジスティック(MNL)関数近似を用いた強化学習について検討した。 頻繁な後悔の保証を有するランダムな探索を伴う確率的効率のアルゴリズムを提案する。 数値実験により提案アルゴリズムの優れた性能を示す。
• 参考スコア（独自算出の注目度）: 8.274693573069442
• License:
• Abstract: We study reinforcement learning with multinomial logistic (MNL) function approximation where the underlying transition probability kernel of the Markov decision processes (MDPs) is parametrized by an unknown transition core with features of state and action. For the finite horizon episodic setting with inhomogeneous state transitions, we propose provably efficient algorithms with randomized exploration having frequentist regret guarantees. For our first algorithm, $\texttt{RRL-MNL}$, we adapt optimistic sampling to ensure the optimism of the estimated value function with sufficient frequency. We establish that $\texttt{RRL-MNL}$ achieves a $\tilde{O}(\kappa^{-1} d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T})$ frequentist regret bound with constant-time computational cost per episode. Here, $d$ is the dimension of the transition core, $H$ is the horizon length, $T$ is the total number of steps, and $\kappa$ is a problem-dependent constant. Despite the simplicity and practicality of $\texttt{RRL-MNL}$, its regret bound scales with $\kappa^{-1}$, which is potentially large in the worst case. To improve the dependence on $\kappa^{-1}$, we propose $\texttt{ORRL-MNL}$, which estimates the value function using the local gradient information of the MNL transition model. We show that its frequentist regret bound is $\tilde{O}(d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T} + \kappa^{-1} d^2 H^2)$. To the best of our knowledge, these are the first randomized RL algorithms for the MNL transition model that achieve statistical guarantees with constant-time computational cost per episode. Numerical experiments demonstrate the superior performance of the proposed algorithms.
• Abstract（参考訳）: 我々は,マルコフ決定過程(MDP)の基底となる遷移確率核が,状態と動作の特徴を持つ未知の遷移コアによってパラメータ化されるような,MNL関数近似を用いた強化学習について検討した。 不均質な状態遷移を伴う有限地平線エピソディクス設定に対しては、頻繁な後悔の保証を有するランダムな探索を伴う確率的に効率的なアルゴリズムを提案する。 最初のアルゴリズムである$\texttt{RRL-MNL}$に対して、十分な周波数で推定値関数の楽観性を確保するために楽観的なサンプリングを適用する。 我々は、$\texttt{RRL-MNL}$が$\tilde{O}(\kappa^{-1} d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T})$ oftenist regret bound with constant-time compute cost per episodeを達成できることを確立する。 ここで、$d$は遷移コアの次元、$H$は地平線の長さ、$T$はステップの総数、$\kappa$は問題依存定数である。 $\texttt{RRL-MNL}$の単純さと実用性にもかかわらず、その後悔は$\kappa^{-1}$とスケールする。 MNL遷移モデルの局所勾配情報を用いて値関数を推定する$\texttt{ORRL-MNL}$を提案する。 頻繁な後悔境界は$\tilde{O}(d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T} + \kappa^{-1} d^2 H^2)$であることを示す。 我々の知る限り、これらはMNLトランジションモデルのための最初のランダム化RLアルゴリズムであり、1エピソード当たりの計算コストを一定に抑える統計的保証を実現する。 数値実験により提案アルゴリズムの優れた性能を示す。

関連論文リスト

• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。 非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。 我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T11:31:54Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• 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)
• Randomized Exploration is Near-Optimal for Tabular MDP [45.16374124699648]
  強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。 1)1つのランダムシードを各エピソードで使用し、2)ベルンシュタイン型のノイズの大きさを算出すると、最悪の$widetildeOleft(HsqrtSATright)$リコールがエピソード時間非均質決定プロセスにバインドされることを示します。
  論文  参考訳（メタデータ） (2021-02-19T01:42:50Z)
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration [94.47472987987805]
  有限水平強化学習(RL)における探索・探索ジレンマの検討 本稿では,ランダム化最小二乗値 (RLSVI) の楽観的な変種を紹介する。 マルコフ決定過程が低ランク遷移ダイナミクスを持つという仮定の下で、RSVIの頻繁な後悔は、$widetilde O(d2 H2 sqrtT)$$ d $ が特徴次元であり、$ H $ が地平線であり、$ T $ が総数であることを示す。
  論文  参考訳（メタデータ） (2019-11-01T19:48:57Z)

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

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