論文の概要: Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient

• arxiv url: http://arxiv.org/abs/2301.08215v1
• Date: Thu, 19 Jan 2023 18:24:08 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-20 14:24:07.140974
• Title: Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient
• Title（参考訳）: 意思決定係数を用いた対話的意思決定に対する厳密な保証
• Authors: Dylan J. Foster, Noah Golowich, Yanjun Han
• Abstract要約: 我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。 我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。 この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
• 参考スコア（独自算出の注目度）: 51.37720227675476
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A foundational problem in reinforcement learning and interactive decision making is to understand what modeling assumptions lead to sample-efficient learning guarantees, and what algorithm design principles achieve optimal sample complexity. Recently, Foster et al. (2021) introduced the Decision-Estimation Coefficient (DEC), a measure of statistical complexity which leads to upper and lower bounds on the optimal sample complexity for a general class of problems encompassing bandits and reinforcement learning with function approximation. In this paper, we introduce a new variant of the DEC, the Constrained Decision-Estimation Coefficient, and use it to derive new lower bounds that improve upon prior work on three fronts: - They hold in expectation, with no restrictions on the class of algorithms under consideration. - They hold globally, and do not rely on the notion of localization used by Foster et al. (2021). - Most interestingly, they allow the reference model with respect to which the DEC is defined to be improper, establishing that improper reference models play a fundamental role. We provide upper bounds on regret that scale with the same quantity, thereby closing all but one of the gaps between upper and lower bounds in Foster et al. (2021). Our results apply to both the regret framework and PAC framework, and make use of several new analysis and algorithm design techniques that we anticipate will find broader use.
• Abstract（参考訳）: 強化学習と対話的意思決定における基本的な問題は、モデリング仮定がサンプル効率の学習保証につながるもの、そしてアルゴリズム設計原則が最適なサンプル複雑性を達成するものを理解することである。 フォスターらは最近、バンドイットと関数近似による強化学習を包含する一般的な問題の最適標本複雑性の上限を上下に設定する統計複雑性の尺度である決定推定係数(dec)を導入した(2021年)。 本稿では,DECの新たな変種であるConstrained Decision-Estimation Coefficientを導入し,それを用いて,従来の3つの面での作業を改善する新しい下限を導出する。 -グローバルに存在し、フォスターら(2021年)のローカライズの概念には依存しない。 もっとも興味深いのは、DECが不適切なものと定義されているリファレンスモデルを許容し、不適切な参照モデルが基本的な役割を果たすことを保証することです。 我々は同じ量でスケールした後悔の上限について上界を提供し、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる(2021年)。 本研究は,pealtフレームワークとpacフレームワークの両方に適用し,より広範な利用を期待する新たな分析手法とアルゴリズム設計手法を生かした。

関連論文リスト

• Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability [71.82666334363174]
  我々は,統計的推定と対話的意思決定において,下位境界法のための統一的なフレームワークを開発する。 対話型意思決定のための新しい下位境界の複雑さを促進する新しい尺度である決定次元を導入する。
  論文  参考訳（メタデータ） (2024-10-07T15:14:58Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Efficient Alternating Minimization Solvers for Wyner Multi-View Unsupervised Learning [0.0]
  本稿では,計算効率のよい解法の開発を可能にする2つの新しい定式化法を提案する。 提案した解法は, 計算効率, 理論的収束保証, ビュー数による局所最小値複雑性, 最先端技術と比較して, 例外的な精度を提供する。
  論文  参考訳（メタデータ） (2023-03-28T10:17:51Z)
• Model-Free Reinforcement Learning with the Decision-Estimation Coefficient [79.30248422988409]
  本稿では,汎用関数近似による構造化帯域と強化学習を包含する対話型意思決定の課題について考察する。 提案手法は,値関数近似を用いたモデル自由強化学習における残差を導出し,より一般的には有効かつ不可能な構造的結果を与える。
  論文  参考訳（メタデータ） (2022-11-25T17:29:40Z)
• On the Complexity of Adversarial Decision Making [101.14158787665252]
  決定推定係数は, 相手の意思決定に対する後悔度を低く抑えるのに必要であり, 十分であることを示す。 我々は、決定推定係数を他のよく知られた複雑性尺度の変種に結びつける新しい構造結果を提供する。
  論文  参考訳（メタデータ） (2022-06-27T06:20:37Z)
• The Statistical Complexity of Interactive Decision Making [126.04974881555094]
  複雑度尺度であるDecision-Estimation Coefficientは,サンプル効率のインタラクティブ学習に必要かつ十分であることが証明された。 統合アルゴリズム設計原則であるE2Dは、教師付き推定のための任意のアルゴリズムを、意思決定のためのオンラインアルゴリズムに変換する。
  論文  参考訳（メタデータ） (2021-12-27T02:53:44Z)

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

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