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

• arxiv url: http://arxiv.org/abs/2410.05117v1
• Date: Mon, 7 Oct 2024 15:14:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 00:08:45.330498
• 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要約: 我々は,統計的推定と対話的意思決定において,下位境界法のための統一的なフレームワークを開発する。 対話型意思決定のための新しい下位境界の複雑さを促進する新しい尺度である決定次元を導入する。
• 参考スコア（独自算出の注目度）: 71.82666334363174
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we develop a unified framework for lower bound methods in statistical estimation and interactive decision making. Classical lower bound techniques -- such as Fano's inequality, Le Cam's method, and Assouad's lemma -- have been central to the study of minimax risk in statistical estimation, yet they are insufficient for the analysis of methods that collect data in an interactive manner. The recent minimax lower bounds for interactive decision making via the Decision-Estimation Coefficient (DEC) appear to be genuinely different from the classical methods. We propose a unified view of these distinct methodologies through a general algorithmic lower bound method. We further introduce a novel complexity measure, decision dimension, which facilitates the derivation of new lower bounds for interactive decision making. In particular, decision dimension provides a characterization of bandit learnability for any structured bandit model class. Further, we characterize the sample complexity of learning convex model class up to a polynomial gap with the decision dimension, addressing the remaining gap between upper and lower bounds in Foster et al. (2021, 2023).
• Abstract（参考訳）: 本稿では,統計的推定と対話的意思決定における下界手法の統一的枠組みを開発する。 ファノの不等式、ル・カムの方法、アスーアの補題のような古典的な下界の手法は、統計的推定におけるミニマックスリスクの研究の中心であるが、データを対話的に収集する手法の分析には不十分である。 最近のDEC(Decision-Estimation Coefficient)による対話的意思決定の最小限境界は、古典的手法と真に異なるようである。 一般的なアルゴリズム的下界法を用いて,これらの異なる手法の統一的なビューを提案する。 さらに、インタラクティブな意思決定のための新しい下位境界の導出を容易にする、新しい複雑性尺度、決定次元を導入する。 特に、決定次元は任意の構造化バンディットモデルクラスに対するバンディット学習可能性の特徴を与える。 さらに,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)

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

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