論文の概要: On the Hardness of Bandit Learning

• arxiv url: http://arxiv.org/abs/2506.14746v1
• Date: Tue, 17 Jun 2025 17:35:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-18 17:34:59.594914
• Title: On the Hardness of Bandit Learning
• Title（参考訳）: バンド学習の難しさについて
• Authors: Nataly Brukhim, Aldo Pacchiano, Miroslav Dudik, Robert Schapire,
• Abstract要約: ベストアーム識別としても知られるバンディット学習の課題について検討する。 我々は、分類のためのPACフレームワークと同様に、包帯学習可能性の一般的な理論を模索する。
• 参考スコア（独自算出の注目度）: 21.32087711586654
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the task of bandit learning, also known as best-arm identification, under the assumption that the true reward function f belongs to a known, but arbitrary, function class F. We seek a general theory of bandit learnability, akin to the PAC framework for classification. Our investigation is guided by the following two questions: (1) which classes F are learnable, and (2) how they are learnable. For example, in the case of binary PAC classification, learnability is fully determined by a combinatorial dimension - the VC dimension- and can be attained via a simple algorithmic principle, namely, empirical risk minimization (ERM). In contrast to classical learning-theoretic results, our findings reveal limitations of learning in structured bandits, offering insights into the boundaries of bandit learnability. First, for the question of "which", we show that the paradigm of identifying the learnable classes via a dimension-like quantity fails for bandit learning. We give a simple proof demonstrating that no combinatorial dimension can characterize bandit learnability, even in finite classes, following a standard definition of dimension introduced by Ben-David et al. (2019). For the question of "how", we prove a computational hardness result: we construct a reward function class for which at most two queries are needed to find the optimal action, yet no algorithm can do so in polynomial time unless RP=NP. We also prove that this class admits efficient algorithms for standard algorithmic operations often considered in learning theory, such as an ERM. This implies that computational hardness is in this case inherent to the task of bandit learning. Beyond these results, we investigate additional themes such as learning under noise, trade-offs between noise models, and the relationship between query complexity and regret minimization.
• Abstract（参考訳）: 我々は、真報酬関数 f が既知のが任意の関数クラス F に属するという仮定の下で、ベストアーム識別(英語版)としても知られるバンディット学習(英語版)の課題を研究する。 本研究は,(1)どのクラスFが学習可能か,(2)どのクラスFが学習可能か,という2つの質問に導かれる。 例えば、バイナリPAC分類の場合、学習可能性は組合せ次元(VC次元)によって完全に決定され、単純なアルゴリズム原理、すなわち経験的リスク最小化(ERM)によって達成できる。 古典的な学習理論とは対照的に,本稿では,構造化された帯域での学習の限界を明らかにし,帯域学習可能性の境界について考察した。 まず,「どれ」という問題に対して,学習可能なクラスを次元的な量で識別するパラダイムが,包帯学習に失敗することを示す。 我々は,Ben-David et al (2019) が導入した次元の標準定義に従って,有限クラスにおいても,任意の組合せ次元が帯域学習可能性を特徴づけることを示す簡単な証明を与える。 最適動作を見つけるのに少なくとも2つのクエリが必要な報酬関数クラスを構築するが、RP=NPを除いた多項式時間ではアルゴリズムが実行できない。 また、このクラスは、ERMのような学習理論においてよく考慮される標準的なアルゴリズム演算に対する効率的なアルゴリズムを許容していることを示す。 これは、計算硬度がこの場合、帯域学習のタスクに固有のものであることを意味する。 これらの結果に加えて,ノイズ下での学習,ノイズモデル間のトレードオフ,クエリ複雑性と後悔の最小化の関係などの追加テーマについても検討する。

関連論文リスト

• STARC: A General Framework For Quantifying Differences Between Reward Functions [52.69620361363209]
  我々は、STARCメトリックと呼ばれるすべての報酬関数の空間上の擬計量のクラスを提供する。 以上の結果から,STARCは最悪の後悔に対して上界と下界の両方を誘導することがわかった。 また、以前の研究によって提案された報酬指標に関するいくつかの問題も特定します。
  論文  参考訳（メタデータ） (2023-09-26T20:31:19Z)
• Adversarially Robust PAC Learnability of Real-Valued Functions [19.54399554114989]
  脂肪散乱次元のクラスは $ell_p$ 摂動条件で学習可能であることを示す。 そこで本研究では,実関数に対する非依存的な新しいサンプルスキームを提案する。
  論文  参考訳（メタデータ） (2022-06-26T21:27:23Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。 ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。 本稿では,FTRLに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-28T08:25:26Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
  古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
  論文  参考訳（メタデータ） (2020-10-07T01:33:06Z)
• When Hardness of Approximation Meets Hardness of Learning [35.39956227364153]
  線形クラスと浅層ネットワークを用いた近似の硬さと,相関クエリと勾配差を用いた学習の硬さを両立させる単一の硬さ特性を示す。 これにより、パリティ関数、DNF式および$AC0$回路の近似の硬さと学習性に関する新たな結果が得られる。
  論文  参考訳（メタデータ） (2020-08-18T17:41:28Z)
• Pairwise Supervision Can Provably Elicit a Decision Boundary [84.58020117487898]
  類似性学習は、パターンのペア間の関係を予測することによって有用な表現を引き出す問題である。 類似性学習は、決定境界を直接引き出すことによって二項分類を解くことができることを示す。
  論文  参考訳（メタデータ） (2020-06-11T05:35:16Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。 我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
  論文  参考訳（メタデータ） (2020-05-18T08:41:39Z)
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
  強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。 本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-15T19:23:59Z)

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

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