論文の概要: Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback

• arxiv url: http://arxiv.org/abs/2610.02771v1
• Date: Fri, 02 Oct 2026 03:56:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.202139
• Title: Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
• Title（参考訳）: 1ビットフィードバックを用いた最適信頼度ベストアーム同定
• Abstract要約: ランダム化しきい値クエリとクリップ付きテール積分IDに基づく時間均一な1ビット平均推定プリミティブを提案する。 固定クリッピングアルゴリズムは、簡単ないつでも$(,)$-PACを保証する一方、位相適応クリッピングアルゴリズムは、クリッピングレベルと現在の解像度とを一致させ、ギャップ適応的なサンプル複雑性をもたらす。
• 参考スコア（独自算出の注目度）: 0.6524460254566904
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study fixed-confidence best-arm identification under strict 1-bit feedback constraints. At each round, the learner selects an arm and a query set, and receives only a single bit indicating whether the sampled reward belongs to that set. We consider a distribution-free finite-variance setting with arm-wise localization, where direct empirical mean estimation is no longer available and clipping becomes unavoidable. We first formulate a time-uniform 1-bit mean-estimation primitive based on randomized threshold queries and a clipped tail-integral identity. We then embed this primitive into candidate-challenger best-arm identification algorithms. A fixed-clipping algorithm gives a simple anytime $(ε,δ)$-PAC guarantee, while a phased adaptive-clipping algorithm matches the clipping level to the current resolution and yields a gap-adaptive sample complexity. We also prove a $K$-arm worst-case information-theoretic lower bound showing that the logarithmic penalty caused by finite-variance 1-bit feedback is intrinsic. This bound matches the leading dependence of the phased algorithm up to lower-order $\log\log$ factors.
• Abstract（参考訳）: 厳密な1ビットフィードバック制約の下で、固定信頼度ベストアーム識別について検討する。 各ラウンドで、学習者は、アームとクエリセットを選択し、サンプルされた報酬がそのセットに属するかどうかを示す1ビットのみを受け取る。 そこでは, 直接的経験的平均推定が不可能となり, クリッピングが避けられないような, アームワイドな分布自由有限分散設定について検討する。 まず、ランダム化しきい値クエリとクリップされたテール積分IDに基づいて、時間一様1ビット平均推定プリミティブを定式化する。 次に、このプリミティブを候補型ベストアーム識別アルゴリズムに組み込む。 固定クリッピングアルゴリズムは単純ないつでも$(ε,δ)$-PACを保証する一方、位相適応クリッピングアルゴリズムはクリッピングレベルと現在の解像度とを一致させ、ギャップ適応的なサンプル複雑性をもたらす。 また,有限分散1ビットフィードバックによる対数ペナルティが本質的であることを示す,$K$-arm最悪の情報理論の下限を証明した。 このバウンダリは、位相付きアルゴリズムの先行的依存度を、下位の$\log\log$因子に一致させる。

関連論文リスト

• Fundamental Limitations of Fixed-Budget Best-Arm Identification [0.0]
  固定予算のベストアーム識別では、ランキングとセレクションとしても知られ、アルゴリズムはK$アームに分散するサンプリング予算を持つ。 任意のアルゴリズムに対して、誤差崩壊率が静的オラクルの少なくとも$left(+ fraclog(K)8right)-1$である少なくとも1つの例が存在することを示す。
  論文  参考訳（メタデータ） (2026-07-13T14:50:32Z)
• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  本研究では,学習者が端末の推薦を控えることができるベイジアン固定予算のベストアーム識別問題について検討する。 本研究は,非検出誤りの確率を解析し,吸収を伴わない準最適腕を推奨するリスクについて考察する。
  論文  参考訳（メタデータ） (2026-06-28T05:07:27Z)
• EVaR-Optimal Arm Identification in Bandits [7.340828059560291]
  The fixed-confidence best arm identification problem in the multiarmed bandit (MAB) framework under the Entropic Value-at-Risk criterion。
  論文  参考訳（メタデータ） (2025-10-06T11:49:56Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Robust Outlier Arm Identification [16.21284542559277]
  ロバスト・アウトリー・アーム識別(ROAI)の問題点について検討する。 目標は、期待される報酬が多数派から大きく逸脱した武器を特定することである。 我々は、期待される報酬の中央値と中央値の絶対偏差を用いて、外れ値のしきい値を算出する。
  論文  参考訳（メタデータ） (2020-09-21T16:13:01Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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