論文の概要: Closing the Log Gap: Minimax-Optimal Regret for Episodic RL

• arxiv url: http://arxiv.org/abs/2610.40165v1
• Date: Thu, 29 Oct 2026 14:38:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.51902
• Title: Closing the Log Gap: Minimax-Optimal Regret for Episodic RL
• Title（参考訳）: ログギャップの閉鎖: エピソードRLのための最小限のレグレット
• Abstract要約: 我々は,$big(H3 SAlog(frac1)varepsilon-2big)$ minimax lower のアルゴリズムを開発した。 また、$varepsilon, )$-PACベスト政治識別アルゴリズムも開発しており、これは最初に$big(H3 SAlog(frac1)varepsilon-2big)$ minimax lower bound up to constants in some regimesと一致する。
• 参考スコア（独自算出の注目度）: 13.138763447728417
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the regret minimization problem in episodic tabular MDPs. Our algorithm achieves the first expected regret bound scaling as $\sqrt{H^3 S A K}$ for sufficiently large $K$, where $H$ is the episode length, $K$ is the number of episodes, and $S$ and $A$ are the numbers of states and actions, respectively. Our method is the first to match the minimax lower bound \emph{without extra polylog factors}. We introduce a variant of UCBVI which does not maintain strictly optimistic estimates, and uses MOSS-style exploration bonuses whose logarithmic terms adapt to both visit counts and estimated variances. A key challenge is controlling the propagation of errors caused by under-optimism, which we accomplish in an occupancy-weighted way, avoiding logarithmic overhead that would be incurred by uniform-over-rows concentration. Our analysis develops time-uniform and variance-aware concentration bounds that may be of independent interest. As a corollary we also develop an algorithm for $(\varepsilon, δ)$-PAC best-policy identification, which is the first to match the $Ω\big(H^3 SA\log(\frac{1}δ)\varepsilon^{-2}\big)$ minimax lower bound up to constants in some regimes.
• Abstract（参考訳）: 本稿では,表在性表在性MDPにおける後悔の最小化問題について検討する。 我々のアルゴリズムは,十分に大きな$K$に対して$\sqrt{H^3 S A K}$,$H$がエピソード数,$K$がエピソード数,$S$が状態数,$A$がアクション数として,最初に期待されるリフレッシュバウンドスケーリングを実現する。 我々の手法は、最小値下界 \emph{without extra polylog factor} に初めて一致する。 我々は、厳密な楽観的な推定を保たない UCBVI の変種を導入し、訪問数と推定分散の両方に対数項が適合する MOSS スタイルの探索ボーナスを使用する。 重要な課題は、過度な最適化によって引き起こされるエラーの伝播を制御することであり、これは占有重み付けされた方法で達成し、均一なオーバ・ローズの集中によって引き起こされる対数的オーバーヘッドを避けることである。 本分析では, 時間的一様および分散を考慮した濃度境界が発達し, 利害関係にある可能性がある。 このアルゴリズムは最初に$Ω\big(H^3 SA\log(\frac{1}δ)\varepsilon^{-2}\big)$ minimax と一致する。

関連論文リスト

• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)

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

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