論文の概要: Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners
- arxiv url: http://arxiv.org/abs/2006.07562v1
- Date: Sat, 13 Jun 2020 05:00:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 20:43:49.542470
- Title: Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners
- Title（参考訳）: 非線形学習者を用いたリニアバンドの腕の特定
- Authors: Mohammadi Zaki, Avi Mohan, Aditya Gopalan
- Abstract要約: 線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。
そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 17.224805430291177
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of best arm identification in linearly parameterised
multi-armed bandits. Given a set of feature vectors
$\mathcal{X}\subset\mathbb{R}^d,$ a confidence parameter $\delta$ and an
unknown vector $\theta^*,$ the goal is to identify
$\arg\max_{x\in\mathcal{X}}x^T\theta^*$, with probability at least $1-\delta,$
using noisy measurements of the form $x^T\theta^*.$ For this fixed confidence
($\delta$-PAC) setting, we propose an explicitly implementable and provably
order-optimal sample-complexity algorithm to solve this problem. Previous
approaches rely on access to minimax optimization oracles. The algorithm, which
we call the \textit{Phased Elimination Linear Exploration Game} (PELEG),
maintains a high-probability confidence ellipsoid containing $\theta^*$ in each
round and uses it to eliminate suboptimal arms in phases. PELEG achieves fast
shrinkage of this confidence ellipsoid along the most confusing (i.e., close
to, but not optimal) directions by interpreting the problem as a two player
zero-sum game, and sequentially converging to its saddle point using low-regret
learners to compute players' strategies in each round. We analyze the sample
complexity of PELEG and show that it matches, up to order, an
instance-dependent lower bound on sample complexity in the linear bandit
setting. We also provide numerical results for the proposed algorithm
consistent with its theoretical guarantees.
- Abstract（参考訳）: 線形パラメータ化マルチアームバンディットにおける最良腕識別の問題点について検討した。
特徴ベクトルの集合 $\mathcal{x}\subset\mathbb{r}^d,$ 信頼度パラメータ $\delta$ と未知ベクトル $\theta^*,$ が与えられたとき、目標は$\arg\max_{x\in\mathcal{x}}x^t\theta^*$ を識別することである。
この固定信頼(\delta$-PAC)設定のために、この問題を解決するために、明示的に実装可能で、証明可能なオーダー最適化サンプル-複雑度アルゴリズムを提案する。
以前のアプローチは、minimax最適化オラクルへのアクセスに依存している。
このアルゴリズムは \textit{phased elimination linear exploration game} (peleg) と呼ばれ、各ラウンドに$\theta^*$を含む高確率信頼楕円体を維持し、フェーズで準最適アームを排除するために使用する。
PELEGは、2つのプレイヤーゼロサムゲームとして問題を解釈し、低レベルの学習者を用いて、各ラウンドにおけるプレイヤーの戦略を計算することによって、最も紛らわしい(すなわち、最適ではない)方向に沿って、この信頼楕円体の高速な縮小を実現する。
我々は, PELEGのサンプル複雑性を解析し, 線形バンディット設定におけるサンプル複雑性に対するインスタンス依存の低い値に一致したことを示す。
また,提案アルゴリズムの理論的保証に整合した数値結果も提供する。
関連論文リスト
- Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。
また、最適な$(lambda, beta)$-sparsity条件に適応する適応アルゴリズムを示す。
論文 参考訳（メタデータ） (2024-10-01T13:45:55Z) - Thompson Sampling for Real-Valued Combinatorial Pure Exploration of
Multi-Armed Bandit [65.268245109828]
本稿では,マルチアームバンディット(R-CPE-MAB)問題の実測値について検討する。
一般トンプソンサンプリング探索法(GenTS-Explore)と呼ばれるアルゴリズムを導入する。これは,アクションセットのサイズが指数関数的に$d$で大きい場合でも動作可能な,最初のアルゴリズムである。
論文 参考訳（メタデータ） (2023-08-20T11:56:02Z) - A/B Testing and Best-arm Identification for Linear Bandits with
Robustness to Non-stationarity [28.068960555415014]
非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。
アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
論文 参考訳（メタデータ） (2023-07-27T19:03:36Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。
我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-13T10:54:52Z) - Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual
Linear Bandit [10.604939762790517]
我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。
第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T19:35:38Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Problem-Complexity Adaptive Model Selection for Stochastic Linear
Bandits [20.207989166682832]
2つの一般的な線形バンディット設定におけるモデル選択の問題について考察する。
まず、[K]$におけるarm $iの平均的な報酬は、$mu_i+ langle alpha_i,t,theta*|$である。
我々は、ALBが$O(|theta*|sqrtT)$の後悔のスケーリングを達成することを示す。
論文 参考訳（メタデータ） (2020-06-04T02:19:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。