論文の概要: Closing the Gap on the Sample Complexity of 1-Identification
- arxiv url: http://arxiv.org/abs/2601.15620v1
- Date: Thu, 22 Jan 2026 03:50:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-23 21:37:20.48269
- Title: Closing the Gap on the Sample Complexity of 1-Identification
- Title（参考訳）: 1-Identification のサンプル複雑度におけるギャップの閉包
- Authors: Zitian Li, Wang Chi Cheung,
- Abstract要約: 1-恒等化(1-identification)は、純粋探索における基本的な多重武装バンドイットの定式化である。
我々は、少なくとも1つの有資格腕が存在する場合、$mathbbE$の新たな下限を導出する。
我々の結果は、複数の資格を持つ腕がある場合の$mathbbE$の分析を補完する。
- 参考スコア（独自算出の注目度）: 8.450904497835262
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 1-identification is a fundamental multi-armed bandit formulation on pure exploration. An agent aims to determine whether there exists a qualified arm whose mean reward is not less than a known threshold $μ_0$, or to output \textsf{None} if it believes such an arm does not exist. The agent needs to guarantee its output is correct with probability at least $1-δ$, while making expected total pulling times $\mathbb{E}τ$ as small as possible. We work on 1-identification with two main contributions. (1) We utilize an optimization formulation to derive a new lower bound of $\mathbb{E}τ$, when there is at least one qualified arm. (2) We design a new algorithm, deriving tight upper bounds whose gap to lower bounds are up to a polynomial of logarithm factor across all problem instance. Our result complements the analysis of $\mathbb{E}τ$ when there are multiple qualified arms, which is an open problem left by history literature.
- Abstract（参考訳）: 1-恒等化(1-identification)は、純粋探索における基本的な多重武装バンドイットの定式化である。
エージェントは、平均報酬が既知のしきい値$μ_0$以下である有資格腕が存在するかどうかを判断すること、またはそのような腕が存在しないと信じている場合は \textsf{None} を出力することを目的としている。
エージェントは、その出力が少なくとも1-δ$の確率で正しいことを保証し、期待される総プルタイム$\mathbb{E}τ$をできるだけ小さくする。
私たちは2つの主要な貢献で1つのアイデンティティに取り組んでいます。
1)少なくとも1つの有資格腕が存在する場合、最適化定式化を利用して、$\mathbb{E}τ$の新しい下限を導出する。
本研究では,全ての問題インスタンスにまたがる対数係数の多項式に対して,下界とのギャップが最大となる厳密な上界を導出するアルゴリズムを設計する。
この結果は、複数の有資格腕が存在する場合の$\mathbb{E}τ$の分析を補完する。
関連論文リスト
- Near Optimal Non-asymptotic Sample Complexity of 1-Identification [5.279257531335345]
純粋探索における基本的多武装バンディット定式化である1同定問題について検討する。
目標は、平均報酬が少なくとも既知の閾値$mu_0$である腕が存在するかどうかを判断すること、またはそのような腕が存在しないと信じている場合、Noneを出力することである。
我々は,新しいアルゴリズムを設計し,非漸近的観点から理論的解析を行う。
論文 参考訳（メタデータ） (2025-06-08T03:23:45Z) - Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。
善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。
我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
論文 参考訳（メタデータ） (2025-05-28T09:48:16Z) - Multi-thresholding Good Arm Identification with Bandit Feedback [1.079960007119637]
我々は,多目的のバンドイット設定において,良好な腕識別問題を考える。
サンプル複雑性境界を持つマルチスレッド UCB (MultiTUCB) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-03-13T14:04:04Z) - Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳（メタデータ） (2025-01-23T12:28:09Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。
提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
論文 参考訳（メタデータ） (2024-03-14T06:14:07Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳（メタデータ） (2023-04-04T04:32:29Z) - Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。
C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
論文 参考訳（メタデータ） (2021-09-10T15:41:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。