論文の概要: Towards Minimax Optimal Best Arm Identification in Linear Bandits
- arxiv url: http://arxiv.org/abs/2105.13017v1
- Date: Thu, 27 May 2021 09:19:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-29 04:17:48.634024
- Title: Towards Minimax Optimal Best Arm Identification in Linear Bandits
- Title(参考訳): 線形バンディットにおけるミニマックス最適腕同定に向けて
- Authors: Junwen Yang, Vincent Y. F. Tan
- Abstract要約: 固定予算設定における線形包帯における最適な腕識別の問題について検討する。
G-最適設計の特性を活用し、アーム割り当て規則に組み込むことにより、パラメータフリーなアルゴリズムを設計する。
OD-LinBAIの故障確率に関する理論的解析を行った。
- 参考スコア(独自算出の注目度): 95.22854522340938
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of best arm identification in linear bandits in the
fixed-budget setting. By leveraging properties of the G-optimal design and
incorporating it into the arm allocation rule, we design a parameter-free
algorithm, Optimal Design-based Linear Best Arm Identification (OD-LinBAI). We
provide a theoretical analysis of the failure probability of OD-LinBAI. While
the performances of existing methods (e.g., BayesGap) depend on all the
optimality gaps, OD-LinBAI depends on the gaps of the top $d$ arms, where $d$
is the effective dimension of the linear bandit instance. Furthermore, we
present a minimax lower bound for this problem. The upper and lower bounds show
that OD-LinBAI is minimax optimal up to multiplicative factors in the exponent.
Finally, numerical experiments corroborate our theoretical findings.
- Abstract(参考訳): 固定予算設定における線形包帯における最適な腕識別の問題について検討する。
g-optimal designの特性を活用し、アーム割り当てルールに組み込むことにより、パラメータフリーな最適設計に基づく線形最良アーム識別(od-linbai)を設計する。
OD-LinBAIの故障確率に関する理論的解析を行った。
既存の方法(例えばベイズガップ)のパフォーマンスはすべての最適性ギャップに依存するが、od-linbai は最上位の$d$ arms のギャップに依存しており、ここで $d$ はリニア・バンディット・インスタンスの有効次元である。
さらに,この問題に対してミニマックス下限を提案する。
上と下の境界は、OD-LinBAI が指数の乗算因子まで極小であることを示している。
最後に,数値実験によって理論的知見が一致した。
関連論文リスト
- Cost Aware Best Arm Identification [15.038210624870656]
emphCost Aware Best Arm Identification (CABAI)と呼ぶ。
そこで我々は,2本腕の単純化モデルにおいて最適であることが証明され,数値実験で驚くほどよく一般化されるCOという低複素性アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-26T16:27:08Z) - Fixed-Budget Best-Arm Identification in Sparse Linear Bandits [69.6194614504832]
固定予算設定下での疎線形包帯のベストアーム識別問題について検討した。
我々は2相アルゴリズムであるLassoとOptimal-Design-(Lasso-OD)をベースとした線形ベストアーム識別を設計する。
我々はラッソODが指数においてほぼ極小であることを示す。
論文 参考訳(メタデータ) (2023-11-01T12:32:17Z) - PopArt: Efficient Sparse Regression and Experimental Design for Optimal
Sparse Linear Bandits [29.097522376094624]
そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。
我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
論文 参考訳(メタデータ) (2022-10-25T19:13:20Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Fixed-Budget Best-Arm Identification in Structured Bandits [33.27743152847947]
固定予算設定におけるベストアーム識別(BAI)は、学習エージェントが一定の回数の観測後に最適な(ベスト)腕を特定する確率を最大化する盗賊問題である。
結合一般化モデルから平均報酬推定値に基づいて最適アームを除去し,構造を組み込んだ一般トラクタブルアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-09T01:32:43Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-21T00:56:33Z) - Locally Differentially Private (Contextual) Bandits Learning [55.63825598391525]
本論文では,局所的差分性(LDP)バンディット学習について検討する。
我々は,DP保証を用いて,文脈自由な帯域幅学習問題を解くことのできる,シンプルなブラックボックス削減フレームワークを提案する。
論文 参考訳(メタデータ) (2020-06-01T04:02:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。