論文の概要: An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs

• arxiv url: http://arxiv.org/abs/2510.08882v1
• Date: Fri, 10 Oct 2025 00:25:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 00:38:47.904117
• Title: An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
• Title（参考訳）: 対向型MDPを用いたモデル自由度推定係数の改善
• Authors: Haolin Liu, Chen-Yu Wei, Julian Zimmert,
• Abstract要約: 構造観察による意思決定(DMSO)について検討する。 我々はDig-DECを紹介した。Dig-DECはモデルのないDECで、楽観性を排除し、情報ゲインによって純粋に探索を駆動する。
• 参考スコア（独自算出の注目度）: 41.17780671950473
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study decision making with structured observation (DMSO). Previous work (Foster et al., 2021b, 2023a) has characterized the complexity of DMSO via the decision-estimation coefficient (DEC), but left a gap between the regret upper and lower bounds that scales with the size of the model class. To tighten this gap, Foster et al. (2023b) introduced optimistic DEC, achieving a bound that scales only with the size of the value-function class. However, their optimism-based exploration is only known to handle the stochastic setting, and it remains unclear whether it extends to the adversarial setting. We introduce Dig-DEC, a model-free DEC that removes optimism and drives exploration purely by information gain. Dig-DEC is always no larger than optimistic DEC and can be much smaller in special cases. Importantly, the removal of optimism allows it to handle adversarial environments without explicit reward estimators. By applying Dig-DEC to hybrid MDPs with stochastic transitions and adversarial rewards, we obtain the first model-free regret bounds for hybrid MDPs with bandit feedback under several general transition structures, resolving the main open problem left by Liu et al. (2025). We also improve the online function-estimation procedure in model-free learning: For average estimation error minimization, we refine the estimator in Foster et al. (2023b) to achieve sharper concentration, improving their regret bounds from $T^{3/4}$ to $T^{2/3}$ (on-policy) and from $T^{5/6}$ to $T^{7/9}$ (off-policy). For squared error minimization in Bellman-complete MDPs, we redesign their two-timescale procedure, improving the regret bound from $T^{2/3}$ to $\sqrt{T}$. This is the first time a DEC-based method achieves performance matching that of optimism-based approaches (Jin et al., 2021; Xie et al., 2023) in Bellman-complete MDPs.
• Abstract（参考訳）: 構造観察(DMSO)による意思決定について検討した。 従来の研究 (Foster et al , 2021b, 2023a) は、決定推定係数 (DEC) によるDMSOの複雑さを特徴付けてきたが、モデルクラスのサイズに応じてスケールする後悔の上境界と下限の間のギャップを残した。 このギャップを狭めるため、Foster et al (2023b) は楽観的な DEC を導入し、値関数クラスのサイズでしかスケールしない境界を達成した。 しかし、彼らの楽観主義に基づく探索は確率的な設定を扱うことでのみ知られており、それが対向的な設定に拡張されるかどうかは不明である。 我々はDig-DECを紹介した。Dig-DECはモデルのないDECで、楽観性を排除し、情報ゲインによって純粋に探索を駆動する。 Dig-DECは常に楽観的なDECよりも大きくなく、特別な場合にはずっと小さくなる。 重要なことは、楽観主義の除去は、明示的な報酬推定者なしで敵の環境を扱えることである。 そこで,Dig-DEC を確率遷移と逆の報酬を持つハイブリッド MDP に適用することにより,複数の一般的な遷移構造の下でのバンドバンドフィードバックを持つハイブリッド MDP に対する最初のモデルフリー後悔境界を求め,Liu et al (2025) が残した主要な開問題を解決する。 また, モデルフリー学習におけるオンライン関数推定手法の改善も行った: 平均推定誤差最小化のために, Foster et al (2023b) における推定器を改良し, よりシャープな集中度を実現し, 後悔境界を$T^{3/4}$から$T^{2/3}$(on-policy)、$T^{5/6}$から$T^{7/9}$(off-policy)に改善する。 ベルマン完全 MDP における二乗誤差最小化のために、我々は2段階の手順を再設計し、後悔の限界を$T^{2/3}$から$\sqrt{T}$に改善する。 ベルマン完全 MDP における楽観主義的アプローチ (Jin et al , 2021; Xie et al , 2023) と性能整合性を実現するのはこれが初めてである。

関連論文リスト

• Large Language Models Imitate Logical Reasoning, but at what Cost? [0.42970700836450487]
  本稿では,18カ月間のフロンティア大言語モデルの推論能力を評価する。 我々は,2023年12月,2024年9月,2025年6月の3つの主要モデルの精度を,真偽の質問に対して測定した。 2023年から2024年までのパフォーマンス向上は、シークレットの隠された連鎖によるものである。
  論文  参考訳（メタデータ） (2025-09-16T04:03:42Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Regret Minimization via Saddle Point Optimization [29.78262192683203]
  決定推定係数 (DEC) は, 構造的バンディットと強化学習における最悪の既往歴に対して, ほぼ下限および上限の値を与えることを示した。 推定・判定アルゴリズム(E2D)の任意の変種を導出する。 我々の定式化は有限モデルクラスと線形フィードバックモデルのための実用的なアルゴリズムにつながる。
  論文  参考訳（メタデータ） (2024-03-15T15:09:13Z)
• The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization [30.26365073195728]
  基本凸最適化設定における勾配法の一般化性能について検討する。 同様の構成手法を適用すると、SGDのサンプル複雑性に対して同様の$Omega(sqrtd)$ローバウンドが得られ、非自明な経験的誤差に達することが示される。
  論文  参考訳（メタデータ） (2024-01-22T15:50:32Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。 我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。 この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
  論文  参考訳（メタデータ） (2023-01-19T18:24:08Z)
• 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)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

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

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