論文の概要: Optimal Best-arm Identification in Linear Bandits
- arxiv url: http://arxiv.org/abs/2006.16073v1
- Date: Mon, 29 Jun 2020 14:25:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 13:45:11.924139
- Title: Optimal Best-arm Identification in Linear Bandits
- Title（参考訳）: リニアバンディットにおける最適最適腕識別
- Authors: Yassir Jedra, Alexandre Proutiere
- Abstract要約: サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
- 参考スコア（独自算出の注目度）: 79.3239137440876
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of best-arm identification with fixed confidence in
stochastic linear bandits. The objective is to identify the best arm with a
given level of certainty while minimizing the sampling budget. We devise a
simple algorithm whose sampling complexity matches known instance-specific
lower bounds, asymptotically almost surely and in expectation. The algorithm
relies on an arm sampling rule that tracks an optimal proportion of arm draws,
and that remarkably can be updated as rarely as we wish, without compromising
its theoretical guarantees. Moreover, unlike existing best-arm identification
strategies, our algorithm uses a stopping rule that does not depend on the
number of arms. Experimental results suggest that our algorithm significantly
outperforms existing algorithms. The paper further provides a first analysis of
the best-arm identification problem in linear bandits with a continuous set of
arms.
- Abstract（参考訳）: 確率線形包帯の信頼度を一定としたベストアーム識別問題について検討する。
目的は、サンプリング予算を最小化しながら、所定の確信度で最適な腕を特定することである。
サンプリングの複雑さが既知のインスタンス固有の下限にほぼ確実に一致する単純なアルゴリズムを考案する。
このアルゴリズムは、アームドローの最適な比率を追跡するアームサンプリングルールに依存しており、理論的な保証を損なうことなく、非常に稀に更新することができる。
さらに,既存のベストアーム識別戦略とは異なり,本アルゴリズムは武器数に依存しない停止規則を用いる。
実験結果から,本アルゴリズムは既存のアルゴリズムを大きく上回っていることが示唆された。
さらに本論文は,連続的なアームセットを持つ線形バンディットにおける最良アーム識別問題の第一解析を提供する。
関連論文リスト
- Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。
マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。
この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文 参考訳（メタデータ） (2024-06-05T08:02:40Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Gamification of Pure Exploration for Linear Bandits [34.16123941778227]
線形バンディットの文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。
標準的なマルチアームバンディットには最適アルゴリズムが存在するが、リニアバンディットにおけるベストアーム識別のためのアルゴリズムの存在は明白である。
線形帯域における固定信頼純粋探索のための第一の洞察的最適アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-07-02T08:20:35Z) - Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a
Differentially Private Scheme [16.1694012177079]
我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。
ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。
このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
論文 参考訳（メタデータ） (2020-06-11T20:23:43Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-23T19:52:44Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳（メタデータ） (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。