論文の概要: Data- and Variance-dependent Regret Bounds for Online Tabular MDPs

• arxiv url: http://arxiv.org/abs/2602.01903v1
• Date: Mon, 02 Feb 2026 10:09:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:34.065236
• Title: Data- and Variance-dependent Regret Bounds for Online Tabular MDPs
• Title（参考訳）: オンラインタブラルMDPのためのデータおよび変数依存レギュレット境界
• Authors: Mingyi Li, Taira Tsuchiya, Kenji Yamanishi,
• Abstract要約: 両世界の最良なアルゴリズムは, 逆境系における洗練されたデータ依存的後悔境界と, 逆境系における分散依存的後悔境界を実現する。 政策最適化のために、我々のアルゴリズムは同じデータと分散に依存した適応性を、エピソード水平線の要素まで達成する。
• 参考スコア（独自算出の注目度）: 15.092125124258592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work studies online episodic tabular Markov decision processes (MDPs) with known transitions and develops best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the stochastic regime. We quantify MDP complexity using a first-order quantity and several new data-dependent measures for the adversarial regime, including a second-order quantity and a path-length measure, as well as variance-based measures for the stochastic regime. To adapt to these measures, we develop algorithms based on global optimization and policy optimization, both built on optimistic follow-the-regularized-leader with log-barrier regularization. For global optimization, our algorithms achieve first-order, second-order, and path-length regret bounds in the adversarial regime, and in the stochastic regime, they achieve a variance-aware gap-independent bound and a variance-aware gap-dependent bound that is polylogarithmic in the number of episodes. For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon, by exploiting a new optimistic $Q$-function estimator. Finally, we establish regret lower bounds in terms of data-dependent complexity measures for the adversarial regime and a variance measure for the stochastic regime, implying that the regret upper bounds achieved by the global-optimization approach are nearly optimal.
• Abstract（参考訳）: この研究は、オンライン表層表層マルコフ決定過程(MDPs)を既知の遷移とともに研究し、確率的状態におけるデータ依存的後悔境界と分散依存的後悔境界を達成するベスト・オブ・ボス・ワールドズ・アルゴリズムを開発した。 本研究では,一階数量と,二階数量と経路長の測度を含む新たなデータ依存的測度と,確率的測度に対する分散に基づく測度を用いて,MDPの複雑性を定量化する。 これらの対策に適応するために,ログバリア正規化を用いた楽観的なフォローザレギュラー化リーダに基づく,グローバル最適化とポリシ最適化に基づくアルゴリズムを開発した。 大域的最適化のために,我々のアルゴリズムは,逆数系において一階,二階,経路長の後悔境界を達成し,確率的条件下では,差分認識のギャップ非依存境界と差分認識のギャップ非依存境界を達成し,エピソード数で多対数となるような差分認識のギャップ依存境界を達成している。 政策最適化のために,我々のアルゴリズムは,新たな楽観的な$Q$関数推定器を利用することで,各エピソードの水平方向の要素まで,データと分散に依存した適応性を実現する。 最後に,敵対的体制に対するデータ依存的複雑性尺度と確率的体制に対する分散尺度の点で,後悔の少ない境界を定め,グローバル最適化アプローチによって達成された後悔の上限がほぼ最適であることを示す。

関連論文リスト

• Discretization-free Multicalibration through Loss Minimization over Tree Ensembles [22.276913140687725]
  深度2の決定木をアンサンブルする離散化のない多重校正法を提案する。 本アルゴリズムは,データ分布が損失飽和と呼ばれる技術的条件を満たすことを前提として,マルチキャリブレーションを確実に達成する。
  論文  参考訳（メタデータ） (2025-05-23T03:29:58Z)
• Efficiently Training Deep-Learning Parametric Policies using Lagrangian Duality [55.06411438416805]
  制約付きマルコフ決定プロセス(CMDP)は、多くの高度な応用において重要である。 本稿では,パラメトリックアクターポリシーを効率的に訓練するための2段階深度決定規則(TS-DDR)を提案する。 現状の手法と比較して, 解の質を高め, 数桁の計算時間を削減できることが示されている。
  論文  参考訳（メタデータ） (2024-05-23T18:19:47Z)
• Ensemble Kalman Filtering Meets Gaussian Process SSM for Non-Mean-Field and Online Inference [47.460898983429374]
  我々は,非平均場(NMF)変動推定フレームワークにアンサンブルカルマンフィルタ(EnKF)を導入し,潜在状態の後方分布を近似する。 EnKFとGPSSMのこの新しい結婚は、変分分布の学習における広範なパラメータ化の必要性をなくすだけでなく、エビデンスの下限(ELBO)の解釈可能でクローズドな近似を可能にする。 得られたEnKF支援オンラインアルゴリズムは、データ適合精度を確保しつつ、モデル正規化を組み込んで過度適合を緩和し、目的関数を具現化する。
  論文  参考訳（メタデータ） (2023-12-10T15:22:30Z)
• Multistage Stochastic Optimization via Kernels [3.7565501074323224]
  我々は,多段階最適化問題に対する非パラメトリック,データ駆動,トラクタブルアプローチを開発した。 本稿では,提案手法が最適に近い平均性能で決定ルールを生成することを示す。
  論文  参考訳（メタデータ） (2023-03-11T23:19:32Z)
• Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments [48.96971760679639]
  マルコフ決定過程(MDP)の分散依存的後悔境界について検討する。 環境の微細な分散特性を特徴付けるための2つの新しい環境規範を提案する。 モデルに基づく手法では、MVPアルゴリズムの変種を設計する。 特に、この境界は極小かつ決定論的 MDP に対して同時に最適である。
  論文  参考訳（メタデータ） (2023-01-31T06:54:06Z)
• Offline Policy Optimization in RL with Variance Regularizaton [142.87345258222942]
  定常分布補正を用いたオフラインRLアルゴリズムの分散正則化を提案する。 Fenchel双対性を用いることで、分散正規化器の勾配を計算するための二重サンプリング問題を回避することができることを示す。 オフライン分散正規化アルゴリズム(OVAR)は,既存のオフラインポリシー最適化アルゴリズムを拡張できる。
  論文  参考訳（メタデータ） (2022-12-29T18:25:01Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
  論文  参考訳（メタデータ） (2022-10-03T16:05:43Z)
• First-order Policy Optimization for Robust Markov Decision Process [40.2022466644885]
  我々はロバストマルコフ決定過程(MDP)の解法を考える。 MDPは、不確実な遷移カーネルを持つ割引状態、有限状態、有限作用空間 MDP の集合を含む。 $(mathbfs,mathbfa)$-矩形不確かさ集合に対して、ロバストな目的に関するいくつかの構造的な観察を確立する。
  論文  参考訳（メタデータ） (2022-09-21T18:10:28Z)
• Risk-Sensitive Markov Decision Processes with Combined Metrics of Mean and Variance [3.062772835338966]
  本稿では,長期平均値を持つ無限段階離散時間マルコフ決定過程(MDP)の最適化問題について検討する。 性能差式が導出され、任意の2つの異なるポリシーの下で、MPPの平均分散結合メトリクスの差を定量化することができる。 最適政策の必要条件と決定論的政策の最適性が導出される。
  論文  参考訳（メタデータ） (2020-08-09T10:35:35Z)

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

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