論文の概要: Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence

• arxiv url: http://arxiv.org/abs/2607.19854v1
• Date: Wed, 22 Jul 2026 07:42:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-23 18:51:38.017329
• Title: Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
• Title（参考訳）: 水平依存を伴わない強化学習のための漸近的最適レグレット
• Abstract要約: 有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
• 参考スコア（独自算出の注目度）: 54.59847568544922
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study horizon-free regret minimization for finite-horizon time-homogeneous tabular Markov decision processes with $S$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$. We propose a new algorithm and prove a regret upper bound \[\tilde O(\sqrt{SAK}+S^8A^3)\] with failure probability $δ$, where $K$ is the number of episodes and $\tilde O(\cdot)$ hides $\mathsf{poly}\log(S,A,K,1/δ)$. Thus, the regret is $H$-free and asymptotically optimal, matching the contextual-bandit lower bound $Ω(\sqrt{SAK})$ up to logarithmic factors. This completely removes the $\log H$ dependence from the previous $\tilde O(\sqrt{SAK\log H}+S^2A\log H)$ guarantee of Zhang et al. (2021), and drastically improves the prior best horizon-free regret $\tilde O(\sqrt{S^9A^3K})$ of Zhang et al. (2022) asymptotically. The main technical difficulty is that the optimal value functions $\{V_h^*\}_{h=1}^H$ are time-inhomogeneous even though the transition kernel is time-homogeneous. A direct union bound over all value functions typically incurs an additional $\min\{\log H,S\}$ factor. We avoid this factor by (i) exploiting the monotonicity of $V_h^*$ in $h$ and (ii) non-trivially projecting the value functions onto an $S$-dimensional grid. Our analysis relies on three additional ingredients. First, we introduce a horizon-truncation argument that enables reward-based exploration and removes the cost of a separate reward-free exploration phase. Second, we design a cutting bonus that preserves both optimism and the monotonicity needed for planning. Third, we prove a new bound on total deviation for time-homogeneous MDPs, which controls the clipped variance terms in the cutting bonus with adjustable polynomial dependence on $S$ and without any dependence on $H$. Together, these tools yield an asymptotically optimal horizon-free regret guarantee.
• Abstract（参考訳）: 有限水平時間均質なテーブル状マルコフ決定過程をS$状態,$A$アクション,hoighty $H$,およびトラジェクトリごとの合計報酬を1$で有界化するための地平自由後悔最小化について検討する。 我々は,新たなアルゴリズムを提案し,失敗確率が$δ$で,$K$はエピソード数であり,$\tilde O(\cdot)$ hides $\mathsf{poly}\log(S,A,K,1/δ)$であることを示す。 したがって、後悔は$H$フリーで漸近的に最適であり、文脈帯域下界の$Ω(\sqrt{SAK})$と対数因子に一致する。 これにより、以前の$\tilde O(\sqrt{SAK\log H}+S^2A\log H)$ Zhang et al (2021) からの $\log H$ 依存は完全に取り除かれ、Zhang et al (2022) 漸近的に Zhang et al (2022) の $\tilde O(\sqrt{S^9A^3K})$ の最高の地平線のない後悔を劇的に改善する。 主な技術的困難は、最適値関数 $\{V_h^*\}_{h=1}^H$ が時間不均一であることである。 すべての値関数に有界な直和は、通常、追加の$\min\{\log H,S\}$ factorを生じる。 私たちはこの要因を避ける (i)$V_h^*$ in $h$ の単調性を利用する (ii) 値関数を$S$次元グリッドに非自明に投影する。 我々の分析は3つの追加材料に依存している。 まず、報酬に基づく探索が可能で、報酬のない探索フェーズのコストを削減できる地平線トラクションの議論を導入する。 第二に、最適化と計画に必要な単調性の両方を保ったカットボーナスを設計する。 第3に、時間同質なMDPの総偏差に新たな限界があることを証明し、カットボーナスにおけるクリッピング分散項を$S$に調整可能な多項式依存で制御し、$H$に依存しない。 これらのツールを組み合わせることで、漸近的に最適な地平線のない後悔の保証が得られる。

関連論文リスト

• Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning [17.131069269126776]
  固定報酬と遷移関数を用いて,エピソード依存の許容アクションセットを用いて,エピソード強化学習について検討した。 エピソードごとの最適値に対して累積後悔(sum_k=1K[V*,Mk - Vk,Mk]$)で評価する。 MVPアルゴリズムが自然にこのフレームワークに拡張され、強力な理論的保証を享受していることを示す。
  論文  参考訳（メタデータ） (2026-05-15T07:28:42Z)
• Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank [14.919427330415608]
  FISTAは1/$ローカリティスケーリングを保ちながら$$への依存を改善することができることを示す。 我々はFISTAをわずかに過正規化された目的に基づいて解析し、チェック可能な閉じ込め条件下では、全ての刺激活性化が境界集合内に存在することを示す。 これにより、加速された$(sqrt)-1log(/varepsilon)$項と境界オーバーヘッド$sqrtvol(mathcalB)/(3/2)$からなるバウンダリが得られる。
  論文  参考訳（メタデータ） (2026-02-24T17:35:46Z)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。 この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。 この設定のための最初のポリシー最適化アルゴリズムを紹介します。
  論文  参考訳（メタデータ） (2025-02-06T12:03:24Z)
• Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound [25.50155563108198]
  ラウンド単位の複雑さが$T$に依存しない最初の対数-回帰法を提案する。 我々の方法は極めて単純であり、オンラインニュートンステップ(ONS)を適切なexp-concave損失関数に適用する。 また、$Omega(n)$ の下限を示し、$O(nln T)$ 境界が $O(ln T)$ 係数まで固であることを示す。
  論文  参考訳（メタデータ） (2025-01-24T09:19:15Z)
• 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)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
  我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。 この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
  論文  参考訳（メタデータ） (2022-03-24T08:14:12Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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