論文の概要: On Characterizing Learnability for Adversarial Noisy Bandits
- arxiv url: http://arxiv.org/abs/2605.09200v1
- Date: Sat, 09 May 2026 22:40:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-12 23:28:50.110236
- Title: On Characterizing Learnability for Adversarial Noisy Bandits
- Title（参考訳）: 逆雑音帯域の学習性評価について
- Abstract要約: 我々は、既知の関数クラス $mathcalF$ を与えられた逆雑音帯について研究する。
ゴールは、学習者のパフォーマンスと後ろ向きの最高の固定アームとの差として定義される累積的後悔$R(T)$を最小化することである。
関数クラス $mathcalF$ は、サブ線形後悔を達成するアルゴリズムが存在する場合、学習可能であると言う。
- 参考スコア（独自算出の注目度）: 32.68446505032741
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study adversarial noisy bandits given a known function class $\mathcal{F}$. In each round, the adversary selects a function $f \in \mathcal{F}$, the learner chooses an arm, and then observes a noisy reward determined by the chosen arm and the function $f$. The goal is to minimize the cumulative regret $R(T)$, defined as the difference between the learner's performance and that of the best fixed arm in hindsight over $T$ rounds. We say that a function class $\mathcal{F}$ is learnable if there exists an algorithm achieving sublinear regret. Our main results concern characterizing learnability. The main quantity appearing in our characterization is a convexified variant of the generalized maximin volume introduced by Hanneke and Wang (2025). For oblivious adversaries, we characterize learnability in terms of this convexified generalized maximin volume. For adaptive adversaries, we show that the same quantity characterizes learnability when the arm space is countable. Our analysis builds on a connection between convexified generalized maximin volume and the existence of simple hitting sets. We further conjecture that the same quantity also characterizes learnability when the arm space is uncountable, via its relation to a new complexity measure, which we call the distribution covering number. This notion can be viewed as a strengthened form of the hitting set that still admits efficient learning via the multiplicative weights algorithm. We also pose a number of relevant open questions regarding this problem.
- Abstract（参考訳）: 既知関数クラス $\mathcal{F}$ を与えられた逆雑音帯域について検討する。
各ラウンドで、相手は関数 $f \in \mathcal{F}$ を選択し、学習者は腕を選択し、選択した腕と関数 $f$ によって決定されるノイズの多い報酬を観察する。
目標は、学習者のパフォーマンスと、後見で最高の固定アームとの違いとして定義される累積的後悔$R(T)$を、$T$のラウンドで最小化することである。
関数クラス $\mathcal{F}$ は、サブ線形後悔を達成するアルゴリズムが存在する場合、学習可能である。
私たちの主な成果は、学習性の特徴付けに関するものです。
我々の特徴づけに現れる主な量は、Hanneke and Wang (2025) によって導入された一般化された最大体積の凸化された変種である。
難解な敵に対しては、この凸化された一般化最大体積の点から学習性を特徴づける。
適応的逆数に対して、同じ量が、腕の空間が可算であるときに学習可能であることを示す。
我々の解析は、凸化された一般化最大体積と単純な打撃集合の存在の間の接続の上に成り立っている。
さらに、同じ量が、アーム空間が可算でないときにも、その分布被覆数と呼ばれる新しい複雑性尺度との関係を通して、学習可能性も特徴付けると推測する。
この概念は、乗法重みアルゴリズムによる効率的な学習を継続するヒットセットの強化形式と見なすことができる。
私たちはまた、この問題に関していくつかの関連するオープンな質問を投げかけます。
関連論文リスト
- Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
本稿では,学習過程を通じて動作セットをプレフィックスするヘテロセシダスティックノイズによる線形帯域問題を再検討する。
本稿では,情報ゲインを最大化するアクションを積極的に探求する,大規模アクション集合のための分散適応アルゴリズムのtexttVAEEを提案する。
音素平均依存率が避けられないことを示す固定作用集合に対して、ほぼ一致する下界を確立する。
論文 参考訳（メタデータ） (2026-07-26T14:24:34Z) - High-dimensional Nonparametric Contextual Bandit Problem [12.828728138651266]
カーネル化された文脈帯域幅は、線形文脈帯域幅問題を一般化する。
サンプル数まで次元が増大しても,非回帰学習は達成可能であることを示す。
Delta$の観点で、寛大な後悔の率を導き出す。
論文 参考訳（メタデータ） (2025-05-20T09:10:39Z) - A Complete Characterization of Learnability for Stochastic Noisy Bandits [19.35221816408955]
未知の報酬関数 $f*$ を既知の関数クラス $mathcalF$ で検討する。
任意の雑音を持つモデルクラスに対して、学習可能性の完全な評価を与える。
また、最適なクエリ複雑性を達成するためには適応性が必要であることも証明します。
論文 参考訳（メタデータ） (2024-10-12T17:23:34Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs [32.29254118429081]
我々は,帯域幅フィードバックの下での最適誤りが,全情報ケースの最適誤りよりも少なくとも$O(k)$倍高いことを示す。
また、ランダム化学習者と決定論的学習者の間のギャップに対して、$tildeTheta(k)$のほぼ最適な境界を示す。
論文 参考訳（メタデータ） (2024-02-12T07:20:05Z) - Adversarially Robust Learning: A Generic Minimax Optimal Learner and
Characterization [39.51923275855131]
本研究では,テスト時間における逆例に頑健な予測器の学習問題に対して,最小限の最適学習器を提案する。
特に、強い否定的な意味で、モンタッサー、ハネケ、スレブロによって提案された頑健な学習者の亜最適性を示す。
論文 参考訳（メタデータ） (2022-09-15T15:32:42Z) - There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning
for Mazes [64.05903267230467]
相互理解性は,強化学習システムにおける信頼性に不可欠なビルディングブロックである。
場合によっては、最適性を保ちつつ、政策の解釈可能性を達成することができることを示す。
論文 参考訳（メタデータ） (2022-06-09T04:23:26Z) - A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits [11.918230810566945]
本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。
我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
論文 参考訳（メタデータ） (2022-01-17T17:23:56Z) - Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
論文 参考訳（メタデータ） (2021-12-13T09:48:54Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。