論文の概要: Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability

• arxiv url: http://arxiv.org/abs/2410.05117v2
• Date: Fri, 06 Dec 2024 19:53:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-10 14:50:02.028694
• Title: Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
• Title（参考訳）: Assouad, Fano, Le Cam with Interaction: An Unification Lower Bound Framework and Characterization for Bandit Learnability (特集:ヒューマンコミュニケーション)
• Authors: Fan Chen, Dylan J. Foster, Yanjun Han, Jian Qian, Alexander Rakhlin, Yunbei Xu,
• Abstract要約: 我々は,統計的推定と対話的意思決定において,情報理論の下限を統一する枠組みを開発する。 Emphinteractive Fano methodinteractive と呼ばれる新しい下界アプローチを提案する。
• 参考スコア（独自算出の注目度）: 71.82666334363174
• License:
• Abstract: We develop a unifying framework for information-theoretic lower bound in statistical estimation and interactive decision making. Classical lower bound techniques -- such as Fano's method, Le Cam's method, and Assouad's lemma -- are central to the study of minimax risk in statistical estimation, yet are insufficient to provide tight lower bounds for \emph{interactive decision making} algorithms that collect data interactively (e.g., algorithms for bandits and reinforcement learning). Recent work of Foster et al. (2021, 2023) provides minimax lower bounds for interactive decision making using seemingly different analysis techniques from the classical methods. These results -- which are proven using a complexity measure known as the \emph{Decision-Estimation Coefficient} (DEC) -- capture difficulties unique to interactive learning, yet do not recover the tightest known lower bounds for passive estimation. We propose a unified view of these distinct methodologies through a new lower bound approach called \emph{interactive Fano method}. As an application, we introduce a novel complexity measure, the \emph{Fractional Covering Number}, which facilitates the new lower bounds for interactive decision making that extend the DEC methodology by incorporating the complexity of estimation. Using the fractional covering number, we (i) provide a unified characterization of learnability for \emph{any} stochastic bandit problem, (ii) close the remaining gap between the upper and lower bounds in Foster et al. (2021, 2023) (up to polynomial factors) for any interactive decision making problem in which the underlying model class is convex.
• Abstract（参考訳）: 我々は,統計的推定と対話的意思決定において,情報理論の下限を統一する枠組みを開発する。 ファノの法、ル・カムの法、アスーアの補題のような古典的な下界法は、統計的推定におけるミニマックスリスクの研究の中心であるが、データをインタラクティブに収集するemph{interactive decision making}アルゴリズム(例えば、バンディットと強化学習のためのアルゴリズム)に対して厳密な下界を与えるには不十分である。 Foster et al (2021, 2023) の最近の研究は、古典的手法とは明らかに異なる分析手法を用いて、対話的な意思決定のために最小限の下位境界を提供する。 これらの結果は、"emph{Decision-Estimation Coefficient} (DEC)"と呼ばれる複雑性尺度を用いて証明されている。 本稿では,これらの異なる手法の統一的なビューを,新しい下界アプローチである 'emph{interactive Fano method} を通じて提案する。 応用として,DEC手法を拡張した対話型意思決定において,計算の複雑さを取り入れて,新たな下位境界を導出する,新しい複雑性尺度である「emph{Fractional Covering Number}」を導入する。 分数被覆数を用いて i) {\displaystyle \emph{any} 確率的バンディット問題に対する学習可能性の統一的評価を提供する。 2) 基礎となるモデルクラスが凸である任意の対話的決定問題に対して、Foster et al (2021, 2023) における上界と下界の間の残りのギャップを閉じる。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。 我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。 この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
  論文  参考訳（メタデータ） (2023-01-19T18:24:08Z)
• Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization [48.12845778927164]
  凸最適化の設定において,勾配勾配降下の最小値設定の見通しを考察する。 勾配法の研究においてよく用いられる手法として、最終回はガウス雑音によって劣化し、ノイズの多い「代理」アルゴリズムが生成される。 以上の結果から,情報理論を用いた勾配降下解析には新たな考え方が必要であることが示唆された。
  論文  参考訳（メタデータ） (2022-12-27T17:16:48Z)
• 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)
• Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
  プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。 我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
  論文  参考訳（メタデータ） (2021-05-13T18:24:30Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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