論文の概要: A/B Testing and Best-arm Identification for Linear Bandits with
Robustness to Non-stationarity
- arxiv url: http://arxiv.org/abs/2307.15154v2
- Date: Thu, 15 Feb 2024 07:52:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-16 18:52:34.297163
- Title: A/B Testing and Best-arm Identification for Linear Bandits with
Robustness to Non-stationarity
- Title（参考訳）: 非定常性に対するロバスト性を有する線形帯域のA/B試験とベストアーム同定
- Authors: Zhihan Xiong, Romain Camilleri, Maryam Fazel, Lalit Jain, Kevin
Jamieson
- Abstract要約: 非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。
アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
- 参考スコア（独自算出の注目度）: 28.068960555415014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the fixed-budget best-arm identification (BAI) problem for
linear bandits in a potentially non-stationary environment. Given a finite arm
set $\mathcal{X}\subset\mathbb{R}^d$, a fixed budget $T$, and an unpredictable
sequence of parameters $\left\lbrace\theta_t\right\rbrace_{t=1}^{T}$, an
algorithm will aim to correctly identify the best arm $x^* :=
\arg\max_{x\in\mathcal{X}}x^\top\sum_{t=1}^{T}\theta_t$ with probability as
high as possible. Prior work has addressed the stationary setting where
$\theta_t = \theta_1$ for all $t$ and demonstrated that the error probability
decreases as $\exp(-T /\rho^*)$ for a problem-dependent constant $\rho^*$. But
in many real-world $A/B/n$ multivariate testing scenarios that motivate our
work, the environment is non-stationary and an algorithm expecting a stationary
setting can easily fail. For robust identification, it is well-known that if
arms are chosen randomly and non-adaptively from a G-optimal design over
$\mathcal{X}$ at each time then the error probability decreases as
$\exp(-T\Delta^2_{(1)}/d)$, where $\Delta_{(1)} = \min_{x \neq x^*} (x^* -
x)^\top \frac{1}{T}\sum_{t=1}^T \theta_t$. As there exist environments where
$\Delta_{(1)}^2/ d \ll 1/ \rho^*$, we are motivated to propose a novel
algorithm $\mathsf{P1}$-$\mathsf{RAGE}$ that aims to obtain the best of both
worlds: robustness to non-stationarity and fast rates of identification in
benign settings. We characterize the error probability of
$\mathsf{P1}$-$\mathsf{RAGE}$ and demonstrate empirically that the algorithm
indeed never performs worse than G-optimal design but compares favorably to the
best algorithms in the stationary setting.
- Abstract（参考訳）: 非定常環境下での線形包帯に対する固定予算ベストアーム識別(BAI)問題について検討する。
有限腕集合 $\mathcal{X}\subset\mathbb{R}^d$ と固定予算 $T$ とパラメータの予測不可能な列 $\left\lbrace\theta_t\right\rbrace_{t=1}^{T}$ が与えられたとき、アルゴリズムは可能な限り高い確率で最良のアーム $x^* := \arg\max_{x\in\mathcal{X}}x^\top\sum_{t=1}^{T}\theta_t$ を正しく識別する。
以前の研究では、すべての$t$に対して$\theta_t = \theta_1$ という定常設定に対処し、問題依存定数 $\rho^*$ に対して$\exp(-t /\rho^*)$ でエラー確率が減少することを示した。
しかし、私たちの仕事の動機となる多くの現実世界の$a/b/n$多変量テストシナリオでは、環境は不安定であり、定常設定を期待するアルゴリズムは簡単に失敗する可能性がある。
堅牢な識別のために、もし腕を$\mathcal{X}$よりもG最適設計からランダムに非適応に選択すると、誤差確率は$\exp(-T\Delta^2_{(1)}/d)$と減少し、$\Delta_{(1)} = \min_{x \neq x^*} (x^*x)^\top \frac{1}{T}\sum_{t=1}^T \theta_t$となることが知られている。
例えば、$\Delta_{(1)}^2/ d \ll 1/ \rho^*$ という環境が存在するため、我々は、良性設定における非定常性に対する堅牢性と識別の速さという両方の世界の長所を得るための新しいアルゴリズム $\mathsf{P1}$-$\mathsf{RAGE}$ を提案する動機付けがある。
我々は、$\mathsf{p1}$-$\mathsf{rage}$の誤差確率を特徴付け、このアルゴリズムがg-optimal設計よりも決して悪くなることはないが、定常設定の最良のアルゴリズムと比較すると実証的に証明する。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - 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) - Variance-Dependent Best Arm Identification [12.058652922228918]
マルチアームバンディットゲームにおける最適な腕を特定する問題について検討する。
武器の報酬のギャップと分散を探索する適応アルゴリズムを提案する。
このアルゴリズムは2つの対数項に最適であることを示す。
論文 参考訳（メタデータ） (2021-06-19T04:13:54Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners [17.224805430291177]
線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。
そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-13T05:00:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。