論文の概要: Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a
Differentially Private Scheme
- arxiv url: http://arxiv.org/abs/2006.06792v3
- Date: Sun, 23 May 2021 23:08:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 12:38:14.547094
- Title: Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a
Differentially Private Scheme
- Title（参考訳）: 四角形多腕バンディット:最適最良腕識別と微分プライベートスキーム
- Authors: Kontantinos E. Nikolakakis, Dionysios S. Kalogerias, Or Sheffet and
Anand D. Sarwate
- Abstract要約: 我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。
ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。
このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
- 参考スコア（独自算出の注目度）: 16.1694012177079
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the best-arm identification problem in multi-armed bandits with
stochastic, potentially private rewards, when the goal is to identify the arm
with the highest quantile at a fixed, prescribed level. First, we propose a
(non-private) successive elimination algorithm for strictly optimal best-arm
identification, we show that our algorithm is $\delta$-PAC and we characterize
its sample complexity. Further, we provide a lower bound on the expected number
of pulls, showing that the proposed algorithm is essentially optimal up to
logarithmic factors. Both upper and lower complexity bounds depend on a special
definition of the associated suboptimality gap, designed in particular for the
quantile bandit problem, as we show when the gap approaches zero, best-arm
identification is impossible. Second, motivated by applications where the
rewards are private, we provide a differentially private successive elimination
algorithm whose sample complexity is finite even for distributions with
infinite support-size, and we characterize its sample complexity. Our
algorithms do not require prior knowledge of either the suboptimality gap or
other statistical information related to the bandit problem at hand.
- Abstract（参考訳）: 確率的,潜在的に私的な報奨を有する多腕包帯において,最も高い定量値を持つ腕を一定かつ所定のレベルで同定することを目的としたベストアーム識別問題について検討する。
まず,厳密な最適最良アーム識別のための(非プライベート)逐次除去アルゴリズムを提案し,本アルゴリズムが$\delta$-pacであることを示し,そのサンプル複雑性を特徴付ける。
さらに,提案アルゴリズムは対数的因子に対して本質的に最適であることを示す。
上側と下側の両方の複雑性境界は、関連する部分最適化ギャップの特別な定義に依存しており、特に分位性バンディット問題のために設計されており、ギャップがゼロに近づくと最良のアーム識別は不可能である。
第二に,報奨がプライベートなアプリケーションによって動機づけられた,無限の支持サイズを持つ分布に対してもサンプル複雑性が有限である微分プライベートな逐次除去アルゴリズムを提供し,そのサンプル複雑性を特徴付ける。
我々のアルゴリズムは、最適以下のギャップや、手前のバンディット問題に関連する統計情報の事前知識を必要としない。
関連論文リスト
- Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。
マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。
この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文 参考訳（メタデータ） (2024-06-05T08:02:40Z) - Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
この仕事の動機は、再現可能な機械学習の需要の増加にある。
特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
論文 参考訳（メタデータ） (2024-02-12T03:31:34Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - On the Existence of a Complexity in Fixed Budget Bandit Identification [0.0]
固定予算帯域識別では、アルゴリズムは複数の分布から与えられた最終時点までのサンプルを逐次観察する。
我々は,ベルヌーイの腕を2つの腕で識別するなど,いくつかの固定予算識別タスクにおいて,そのような複雑さは存在しないことを示した。
論文 参考訳（メタデータ） (2023-03-16T16:39:00Z) - Choosing Answers in $\varepsilon$-Best-Answer Identification for Linear
Bandits [0.8122270502556374]
純粋探索問題では、情報を逐次収集して環境問題に答える。
平均値の高い解を選択すると、期待されるサンプルの複雑さの観点からアルゴリズムが最適に到達できないことを示す。
導出線形帯域における$varepsilon$-best-answer識別にベストアーム識別アルゴリズムを適用するための簡単な手法を開発した。
論文 参考訳（メタデータ） (2022-06-09T12:27:51Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳（メタデータ） (2020-06-29T14:25:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。