論文の概要: Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

• arxiv url: http://arxiv.org/abs/2603.23926v1
• Date: Wed, 25 Mar 2026 04:34:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-26 21:06:11.129292
• Title: Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
• Title（参考訳）: Infinite-Horizon MDPに対する最適分散依存性レギュレット境界
• Authors: Guy Zamir, Matthew Zurek, Yudong Chen,
• Abstract要約: 無限水平マルコフ決定過程(MDP)におけるオンライン強化学習は、そのエピソード的学習よりも理論上、アルゴリズム上は発展していない。 本研究では、古典的平均逆後悔と$$-regretという2つの無限水平目的に対する欠点に対処する。 両設定に適用可能な単一トラクタブルなUPBスタイルのアルゴリズムを開発し、このアルゴリズムは、最初の最適分散依存後悔保証を実現する。
• 参考スコア（独自算出の注目度）: 8.923988278588768
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many algorithms suffering from high ``burn-in'' costs and failing to adapt to benign instance-specific complexity. In this work, we address these shortcomings for two infinite-horizon objectives: the classical average-reward regret and the $γ$-regret. We develop a single tractable UCB-style algorithm applicable to both settings, which achieves the first optimal variance-dependent regret guarantees. Our regret bounds in both settings take the form $\tilde{O}( \sqrt{SA\,\text{Var}} + \text{lower-order terms})$, where $S,A$ are the state and action space sizes, and $\text{Var}$ captures cumulative transition variance. This implies minimax-optimal average-reward and $γ$-regret bounds in the worst case but also adapts to easier problem instances, for example yielding nearly constant regret in deterministic MDPs. Furthermore, our algorithm enjoys significantly improved lower-order terms for the average-reward setting. With prior knowledge of the optimal bias span $\Vert h^\star\Vert_\text{sp}$, our algorithm obtains lower-order terms scaling as $\Vert h^\star\Vert_\text{sp} S^2 A$, which we prove is optimal in both $\Vert h^\star\Vert_\text{sp}$ and $A$. Without prior knowledge, we prove that no algorithm can have lower-order terms smaller than $\Vert h^\star \Vert_\text{sp}^2 S A$, and we provide a prior-free algorithm whose lower-order terms scale as $\Vert h^\star\Vert_\text{sp}^2 S^3 A$, nearly matching this lower bound. Taken together, these results completely characterize the optimal dependence on $\Vert h^\star\Vert_\text{sp}$ in both leading and lower-order terms, and reveal a fundamental gap in what is achievable with and without prior knowledge.
• Abstract（参考訳）: 無限水平マルコフ決定過程(MDP)におけるオンライン強化学習は、そのエピソジックな手法よりも理論的・アルゴリズム的に発展し続けており、多くのアルゴリズムは高い『バーンイン』コストに悩まされ、良心的なインスタンス固有の複雑さに適応できなかった。 本研究では、古典的平均逆後悔と$γ$-regretという2つの無限水平目的に対するこれらの欠点に対処する。 両設定に適用可能な単一トラクタブルなUPBスタイルのアルゴリズムを開発し、このアルゴリズムは、最初の最適分散依存後悔保証を実現する。 ここで$S,A$は状態とアクション空間のサイズであり、$\text{Var}$は累積遷移分散をキャプチャする。 これは、最悪の場合、最小値の最適平均リワードと$γ$-regret境界を示すが、例えば決定論的 MDP においてほぼ一定の後悔をもたらすような、より簡単な問題インスタンスにも適応することを意味する。 さらに,提案アルゴリズムは,平均回帰設定における下位項の大幅な改善を享受する。 最適バイアスの事前の知識は、$\Vert h^\star\Vert_\text{sp}$であり、このアルゴリズムは、$\Vert h^\star\Vert_\text{sp} S^2 A$と、$\Vert h^\star\Vert_\text{sp}$と$A$の両方で最適であることを示す。 事前知識がなければ、アルゴリズムは$\Vert h^\star \Vert_\text{sp}^2 S A$より小さい下位項を持つことができないことを証明し、この下位境界にほぼ一致する、$\Vert h^\star\Vert_\text{sp}^2 S^3 A$という下位項のスケールを持つ事前自由なアルゴリズムを提供する。 これらの結果は、先行項と下階項の両方において$\Vert h^\star\Vert_\text{sp}$に対する最適依存を完全に特徴付け、事前の知識がなければ達成できることの根本的なギャップを明らかにする。

関連論文リスト

• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes [21.77276136591518]
  我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。 シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
  論文  参考訳（メタデータ） (2023-06-28T17:43:19Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• 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)
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit [10.604939762790517]
  我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。 第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T19:35:38Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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