論文の概要: Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition
- arxiv url: http://arxiv.org/abs/2606.29203v1
- Date: Sun, 28 Jun 2026 05:07:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-30 18:07:15.831941
- Title: Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition
- Title（参考訳）: 留意を伴うベイズ的ベストアーム同定:多項式-指数相転移
- Abstract要約: 本研究では,学習者が端末の推薦を控えることができるベイジアン固定予算のベストアーム識別問題について検討する。
本研究は,非検出誤りの確率を解析し,吸収を伴わない準最適腕を推奨するリスクについて考察する。
- 参考スコア（独自算出の注目度）: 51.253617466579335
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation. Subject to an abstention budget $α$, we analyze the probability of undetected error--the risk of recommending a suboptimal arm without abstaining. Our central finding is that abstention induces a phase transition: without abstention, the error probability decays polynomially in the sampling budget $T$; in contrast, introducing any small positive abstention budget shifts this to an exponential decay. For Gaussian priors and rewards, in the regime $T\to\infty$ followed by $α\downarrow0$, we establish exact matching information-theoretic lower bounds and algorithmic upper bounds on the optimal error exponent, which takes the form $\exp(-\frac{α^{2}T}{8κ_ν^{2}})$. The hardness parameter $κ_ν$ represents the prior density of the top-two gap at zero, highlighting that nearly tied instances drive the fundamental error. We introduce an adaptive algorithm, PGWS, that successfully achieves this optimal exponent by expending its abstention budget on statistically ambiguous instances. We further demonstrate that this polynomial-to-exponential improvement is exclusively a Bayesian phenomenon--in the frequentist setting, abstention only affects lower-order exponent terms. We also extend our results beyond the Gaussian model.
- Abstract（参考訳）: 本研究では,学習者が端末の推薦を控えることができるベイジアン固定予算のベストアーム識別問題について検討する。
棄権予算が$α$となると、未検出誤差の可能性を分析し、棄権せずに準最適腕を推奨するリスクを負う。
我々の中心的な発見は、棄却が相転移を誘導することである: 棄却がなければ、誤差確率はサンプリング予算の$T$で多項式的に減衰する; 対照的に、小さな正の棄却予算を導入すると、これを指数関数的崩壊に移行させる。
ガウスの先行と報酬に対して、$T\to\infty$ と $α\downarrow0$ は真に一致する情報理論の下界とアルゴリズム上の上界を最適誤差指数上で確立し、$\exp(-\frac{α^{2}T}{8κ_ν^{2}})$ という形式を取る。
ハードネスパラメータ $κ_ν$ は、ゼロの上位2つのギャップの以前の密度を表しており、ほぼ結びついたインスタンスが基本的なエラーを引き起こすことを強調している。
本稿では,統計的にあいまいなインスタンスに対して,アダプティブアルゴリズムPGWSを導入することで,この最適指数の達成に成功している。
さらに、この多項式対指数改善はベイズ現象のみであり、頻繁な設定では、棄却は下位指数項にのみ影響する。
また、ガウスモデルを超えて結果を拡張します。
関連論文リスト
- Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? [11.223878908981725]
1/2$-Tsallis-INFは、標準的なFTRLアルゴリズムである。
盗賊の対数的擬似回帰を達成しつつ、敵の盗賊の最小限の後悔を保ちながら達成する。
これは自然な疑問を提起する:同じアルゴリズムは、追加の探索なしに、最高の腕を確実に特定できるのか?
論文 参考訳（メタデータ） (2026-08-15T18:38:36Z) - Adaptive Confidence Intervals in Efron's Gaussian Two-Groups Model [28.636700996382558]
敵のノイズに満ちた性質により、Efronのガウス的二群分数モデルにおいて、ヌル位置パラメータ$$に対する信頼区間を研究する。
信頼区間の最小最適長を、未知の割合の汚染と全てのノイズに満ちた敵に対して、所定のカバレッジレベルで特徴付ける。
論文 参考訳（メタデータ） (2026-04-28T22:40:54Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳（メタデータ） (2025-02-19T06:37:37Z) - Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
論文 参考訳（メタデータ） (2025-02-11T19:54:11Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence
and Beyond [15.871535287520393]
本稿では,バンディットの腕識別のための新しいサンプリングルールであるEB-TC$varepsilon$を提案する。
EB-TC$varepsilon$に対して3種類の理論的保証を提供する。
EB-TC$varepsilon$が既存のアルゴリズムと比較して好適に動作することを示す。
論文 参考訳（メタデータ） (2023-05-25T13:19:11Z) - Suboptimal Performance of the Bayes Optimal Algorithm in Frequentist Best Arm Identification [5.176134438571082]
正規分布による報酬を伴う固定予算ベストアーム識別問題を考察する。
この問題では、予測者は、腕(または治療)が$K$、タイムステップが$T$である。
アルゴリズムの性能は、推定されたベストアームの品質を反映して、単純な後悔によって評価される。
論文 参考訳（メタデータ） (2022-02-10T17:50:26Z) - Optimal Regret Is Achievable with Bounded Approximate Inference Error:
An Enhanced Bayesian Upper Confidence Bound Framework [22.846260353176614]
本稿では,帯域幅問題に効率的に対応できる拡張ベイズアッパー信頼境界(EBUCB)フレームワークを提案する。
EBUCBは2つの異なる$alpha$-divergencesで測定された推論誤差が定数以下である場合、最適後悔順序$O(log T)$を達成可能であることを示す。
我々の研究は、定数近似推論誤差の設定において$o(T)$よりも良い最初の理論的後悔境界を提供する。
論文 参考訳（メタデータ） (2022-01-31T01:36:15Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。