論文の概要: UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity

• arxiv url: http://arxiv.org/abs/2511.22273v1
• Date: Thu, 27 Nov 2025 09:54:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-01 19:47:55.493621
• Title: UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity
• Title（参考訳）: UCB、大規模純正探査へ-準ガウシアン性を超えて
• Authors: Zaile Li, Weiwei Fan, L. Jeff Hong,
• Abstract要約: 本稿では,大規模純探索問題における高信頼度境界(UCB)アルゴリズムの性能について検討する。 本稿では,メタUCBアルゴリズムと広い範囲の UCB アルゴリズムが標本最適性を達成可能であることを示す。 その結果, 非ガウス分布を用いた大規模純粋探索問題に対する UCB アルゴリズムの適用性を示した。
• 参考スコア（独自算出の注目度）: 0.8283940114367679
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Selecting the best alternative from a finite set represents a broad class of pure exploration problems. Traditional approaches to pure exploration have predominantly relied on Gaussian or sub-Gaussian assumptions on the performance distributions of all alternatives, which limit their applicability to non-sub-Gaussian especially heavy-tailed problems. The need to move beyond sub-Gaussianity may become even more critical in large-scale problems, which tend to be especially sensitive to distributional specifications. In this paper, motivated by the widespread use of upper confidence bound (UCB) algorithms in pure exploration and beyond, we investigate their performance in the large-scale, non-sub-Gaussian settings. We consider the simplest category of UCB algorithms, where the UCB value for each alternative is defined as the sample mean plus an exploration bonus that depends only on its own sample size. We abstract this into a meta-UCB algorithm and propose letting it select the alternative with the largest sample size as the best upon stopping. For this meta-UCB algorithm, we first derive a distribution-free lower bound on the probability of correct selection. Building on this bound, we analyze two general non-sub-Gaussian scenarios: (1) all alternatives follow a common location-scale structure and have bounded variance; and (2) when such a structure does not hold, each alternative has a bounded absolute moment of order $q > 3$. In both settings, we show that the meta-UCB algorithm and therefore a broad class of UCB algorithms can achieve the sample optimality. These results demonstrate the applicability of UCB algorithms for solving large-scale pure exploration problems with non-sub-Gaussian distributions. Numerical experiments support our results and provide additional insights into the comparative behaviors of UCB algorithms within and beyond our meta-UCB framework.
• Abstract（参考訳）: 有限集合から最良の選択肢を選択することは、純粋探索問題の幅広いクラスを表す。 純粋探索への伝統的なアプローチは、ガウスあるいはガウス以下の仮定が全ての代替品のパフォーマンス分布に大きく依存しており、これは非ガウス的問題、特にヘビーテール問題への適用性を制限する。 亜ガウス性を超えて移動する必要性は、特に分布仕様に敏感な大規模問題においてさらに重要になる。 本稿では,高信頼度境界(UCB)アルゴリズムを純粋探索などに広く活用することによる,大規模で非ガウス的条件下での性能評価を行った。 UCBアルゴリズムの最も単純なカテゴリについて考察し, UCBの値が標本平均値として定義され, サンプルサイズにのみ依存する探索ボーナスが与えられる。 我々はこれをメタUCBアルゴリズムに抽象化し、最大のサンプルサイズを持つ代替品を停止時に最適に選択させることを提案する。 このメタUCBアルゴリズムでは、まず正しい選択の確率に基づいて分布自由な下界を導出する。 この境界に基づいて、我々は2つの一般非ガウス的シナリオを解析する: (1) すべての選択肢は共通の位置階構造に従い、有界分散を持つ; (2) そのような構造が保たないとき、それぞれの選択肢は位数$q > 3$の有界絶対モーメントを持つ。 いずれの設定においても,メタUCBアルゴリズムと広い範囲の UCB アルゴリズムが標本最適性を達成可能であることを示す。 これらの結果は,非ガウス分布を用いた大規模純粋探索問題に対する UCB アルゴリズムの適用性を示すものである。 数値実験は,本研究の結果を支持し,メタUCBフレームワーク内外における UCB アルゴリズムの比較行動に関するさらなる知見を提供する。

関連論文リスト

• Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient? [12.182108642150103]
  我々は,不正確なBOアルゴリズムがいまだにサブ線形累積後悔を達成可能であることを示す。 このような知見により,ランダムグリッド探索の理論的正当化と数値検証の両立を図った。
  論文  参考訳（メタデータ） (2025-06-13T14:35:39Z)
• Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling [24.487235945761913]
  本研究では, 1-パラメータ指数分布系に属する報酬分布を持つ帯域幅$K$の帯域幅の問題について検討する。 本稿では,Asymptotic Optimality, Minimax Optimality with a $sqrtln (K)$ factor, Sub-UCB, and variance-adaptive worst-case regret boundなど,複数の最適条件を同時に達成できるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-20T09:12:16Z)
• Generalized Naive Bayes [0.0]
  我々は、ネイブベイズ構造の拡張として、いわゆる一般化ネイブベイズ構造を導入する。 古典的ネーブベイズ(NB)によって決定される確率分布と同様に、この値が少なくともデータに適合することを証明する。
  論文  参考訳（メタデータ） (2024-08-28T16:36:18Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Generalized Schrödinger Bridge Matching [54.171931505066]
  一般化Schr"odinger Bridge (GSB) 問題設定は、機械学習の内外を問わず、多くの科学領域で一般的である。 我々は最近の進歩に触発された新しいマッチングアルゴリズムである一般化シュリンガーブリッジマッチング(GSBM)を提案する。 このような一般化は条件最適制御の解法として、変分近似を用いることができることを示す。
  論文  参考訳（メタデータ） (2023-10-03T17:42:11Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。 性能は不特定な事前条件で優雅に低下することを示す。
  論文  参考訳（メタデータ） (2021-07-03T23:17:26Z)
• A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms [8.099977107670918]
  アッパー信頼境界 (UCB) は楽観的なMABアルゴリズムである。 本稿では,UCBのアームサンプリング動作に関する新しい知見を提供する。 また、UPBの下でのMAB問題のプロセスレベルの特徴付けも提供する。
  論文  参考訳（メタデータ） (2021-06-03T20:52:26Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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