論文の概要: Tail Distribution of Regret in Optimistic Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2511.18247v1
• Date: Sun, 23 Nov 2025 02:23:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:24.718663
• Title: Tail Distribution of Regret in Optimistic Reinforcement Learning
• Title（参考訳）: 最適強化学習におけるレグレトの姿勢分布
• Authors: Sajad Khodadadian, Mehrdad Moharrami,
• Abstract要約: 累積的後悔$R_K$ over $K$ エピソードのテール分布を,期待値や単一高確率量子化ではなく,特徴付ける。 提案したアルゴリズムは、期待される後悔と、その後悔がガウス以下の尾を示す範囲のバランスをとるチューニングパラメータ$$に依存する。
• 参考スコア（独自算出の注目度）: 3.9962751777898955
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We derive instance-dependent tail bounds for the regret of optimism-based reinforcement learning in finite-horizon tabular Markov decision processes with unknown transition dynamics. Focusing on a UCBVI-type algorithm, we characterize the tail distribution of the cumulative regret $R_K$ over $K$ episodes, rather than only its expectation or a single high-probability quantile. We analyze two natural exploration-bonus schedules: (i) a $K$-dependent scheme that explicitly incorporates the total number of episodes $K$, and (ii) a $K$-independent scheme that depends only on the current episode index. For both settings, we obtain an upper bound on $\Pr(R_K \ge x)$ that exhibits a distinctive two-regime structure: a sub-Gaussian tail starting from an instance-dependent scale $m_K$ up to a transition threshold, followed by a sub-Weibull tail beyond that point. We further derive corresponding instance-dependent bounds on the expected regret $\mathbb{E}[R_K]$. The proposed algorithm depends on a tuning parameter $α$, which balances the expected regret and the range over which the regret exhibits a sub-Gaussian tail. To the best of our knowledge, our results provide one of the first comprehensive tail-regret guarantees for a standard optimistic algorithm in episodic reinforcement learning.
• Abstract（参考訳）: 我々は、有限水平タブ状マルコフ決定過程における楽観主義に基づく強化学習の後悔のために、インスタンス依存尾辺を導出する。 UCBVI型アルゴリズムに着目して,期待値や1つの高確率量子化ではなく,累積的後悔$R_K$以上のエピソードのテール分布を特徴付ける。 我々は2つの自然探査のスケジュールを分析した。 (i)$K$及び$K$の合計数を明示的に組み込んだ$K$依存方式 (ii)現在のエピソードインデックスのみに依存する$K$非依存スキーム。 どちらの設定に対しても、$\Pr(R_K \ge x)$ 上の上界は、インスタンス依存のスケール $m_K$ から遷移しきい値まで、そしてそれを超えるサブWeibull テールという、特徴的な2つの登録構造を示す。 さらに、期待される後悔の$\mathbb{E}[R_K]$に対して対応するインスタンス依存境界を導出する。 提案アルゴリズムは期待される後悔と、その後悔がガウス以下の尾を示す範囲のバランスをとるチューニングパラメータである$α$に依存する。 我々の知識を最大限に活用するために、我々の結果は、エピソード強化学習における標準的な楽観的アルゴリズムに対して、最初の包括的なテール-レグレット保証を提供する。

関連論文リスト

• Achieving Constant Regret in Linear Markov Decision Processes [57.34287648914407]
  我々は不特定線形マルコフ決定過程(MDP)に対するアルゴリズムCert-LSVI-UCBを導入する。 Cert-LSVI-UCB は $tildemathcalO(d3H5/Delta)$ の累積後悔を高い確率で示し、不特定度 $zeta$ が $tildemathcalO(Delta / (sqrtdH2))$ 以下であることを示す。
  論文  参考訳（メタデータ） (2024-04-16T17:23:19Z)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。 AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-04T17:11:15Z)
• Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk [26.397343668067382]
  我々は,多武装バンディットモデルにおける後悔分布の予測とテールリスクの最適トレードオフについて検討した。 任意の後悔しきい値に対する最適な後悔の尾の確率を特徴付けるために、新しいポリシーが提案されている。
  論文  参考訳（メタデータ） (2023-04-10T01:00:18Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Nonstationary Reinforcement Learning with Linear Function Approximation [19.521419943509784]
  ドリフト環境下での線形関数近似によるマルコフ決定過程(MDP)における強化学習について考察する。 まず、周期的再起動を伴う最小二乗値の楽観的な修正を開発し、変動予算が分かっている場合にその動的後悔を束縛する。 非定常線型 MDP に対する最初の minimax dynamic regret lower bound を導出し、副生成物として Jin らによって未解決の線型 MDP に対する minimax regret lower bound を定めている。
  論文  参考訳（メタデータ） (2020-10-08T20:07:44Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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