論文の概要: Short-lived High-volume Multi-A(rmed)/B(andits) Testing
- arxiv url: http://arxiv.org/abs/2312.15356v1
- Date: Sat, 23 Dec 2023 21:38:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-27 18:27:56.622912
- Title: Short-lived High-volume Multi-A(rmed)/B(andits) Testing
- Title（参考訳）: 短時間大容量マルチa(rmed)/b(andits)試験
- Authors: Su Jia, Andrew Li, R. Ravi, Nishant Oli, Paul Duff, Ian Anderson
- Abstract要約: 短命の腕を多量に持つベイズ的マルチプレイバンディット問題について検討した。
我々は、ある定数$rho>0$に対して$k = O(nrho)$が与えられたとき、我々の提案したポリシーは、事前分布の十分大きなクラスに対して$tilde O(n-min rho, frac 12 (1+frac 1w)-1)$損失を持つことを示した。
- 参考スコア（独自算出の注目度）: 6.707544598445059
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Modern platforms leverage randomized experiments to make informed decisions
from a given set of items (``treatments''). As a particularly challenging
scenario, these items may (i) arrive in high volume, with thousands of new
items being released per hour, and (ii) have short lifetime, say, due to the
item's transient nature or underlying non-stationarity that impels the platform
to perceive the same item as distinct copies over time. Thus motivated, we
study a Bayesian multiple-play bandit problem that encapsulates the key
features of the multivariate testing (or ``multi-A/B testing'') problem with a
high volume of short-lived arms. In each round, a set of $k$ arms arrive, each
available for $w$ rounds. Without knowing the mean reward for each arm, the
learner selects a multiset of $n$ arms and immediately observes their realized
rewards. We aim to minimize the loss due to not knowing the mean rewards,
averaged over instances generated from a given prior distribution. We show that
when $k = O(n^\rho)$ for some constant $\rho>0$, our proposed policy has
$\tilde O(n^{-\min \{\rho, \frac 12 (1+\frac 1w)^{-1}\}})$ loss on a
sufficiently large class of prior distributions. We complement this result by
showing that every policy suffers $\Omega (n^{-\min \{\rho, \frac 12\}})$ loss
on the same class of distributions. We further validate the effectiveness of
our policy through a large-scale field experiment on {\em Glance}, a
content-card-serving platform that faces exactly the above challenge. A simple
variant of our policy outperforms the platform's current recommender by 4.32\%
in total duration and 7.48\% in total number of click-throughs.
- Abstract（参考訳）: 現代のプラットフォームはランダム化実験を利用して、与えられた項目のセット(`treatments'')から情報的決定を行う。
特に難しいシナリオとして、これらのアイテムは
(i)大量に登場し、1時間に何千もの新品が発売され、
(ii)項目の過渡的性質や、プラットフォームが時間とともに異なるコピーと同一の項目を知覚することを妨げる非定常性などにより、寿命が短いこと。
そこで本研究では,多変量検定(または'multi-A/B test'')問題の主要特徴をカプセル化したベイズ多目的包帯問題について,短命な腕数で検討する。
各ラウンドには1組の$k$ armsが到着し、それぞれ$w$のラウンドが利用できる。
各腕の平均報酬を知らずに、学習者は複数セットのn$ armsを選択し、すぐにその報酬を観察する。
我々は、与えられた事前分布から生成されるインスタンスよりも平均される平均報酬を知らずに損失を最小限に抑えることを目指している。
ある定数 $\rho>0$ に対して $k = o(n^\rho)$ の場合、提案するポリシーは、十分に大きな事前分布のクラスで$\tilde o(n^{-\min \{\rho, \frac 12 (1+\frac 1w)^{-1}\}}) となる。
この結果は、すべてのポリシーが同じ分布のクラスにおいて$\Omega (n^{-\min \{\rho, \frac 12\}})$損失を負うことを示すことによって補完する。
以上の課題に直面したコンテンツカード提供プラットフォームである {\em Glance} の大規模フィールド実験を通じて,我々の政策の有効性をさらに検証する。
私たちのポリシーの単純な変種は、プラットフォームの現在の推奨期間を4.32\%、クリックスルー総数を7.48\%上回っています。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Multi-Armed Bandits with Interference [39.578572123342944]
スイッチバックポリシは,最高の固定アームポリシに対して,最適に期待された後悔のO(sqrt T)$を達成できることが示される。
提案するクラスタランダム化ポリシは,期待値に最適である。
論文 参考訳（メタデータ） (2024-02-02T19:02:47Z) - Allocating Divisible Resources on Arms with Unknown and Random Rewards [25.93048671326331]
我々は、各期間に複数の武器で再生可能資源の1単位を割り当てる意思決定者について検討する。
アームは未知でランダムな報酬であり、その手段は割り当てられたリソースに比例し、分散は割り当てられたリソースのオーダー$b$に比例する。
論文 参考訳（メタデータ） (2023-06-28T21:59:11Z) - Piecewise-Stationary Multi-Objective Multi-Armed Bandit with Application
to Joint Communications and Sensing [7.0997346625024]
本稿では,この問題を解決するために,変化検出を用いた汎用上信頼境界(UCB)に基づくアルゴリズムを提案する。
また,統合通信・センシングシステムにおけるエネルギー効率のよい波形設計問題を玩具の例として定式化する。
論文 参考訳（メタデータ） (2023-02-10T14:10:14Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - Smooth Non-Stationary Bandits [49.19728527803684]
本研究では、各アームの平均報酬シーケンスを$beta$-H"older関数に埋め込むことができる非定常包帯問題について検討する。
スムース(つまり$betage 2$)と非スムース(つまり$beta=1$)との最初の分離は、$tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2-H"older instanceでポリシーを提示することで示します。
論文 参考訳（メタデータ） (2023-01-29T06:03:20Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Risk-averse Contextual Multi-armed Bandit Problem with Linear Payoffs [7.125769932993104]
リスク・逆条件下での線形ペイオフに対するコンテキスト多重武装バンディット問題について考察する。
各ラウンドにおいて、各アームのコンテキストが明らかにされ、意思決定者は1つのアームを選択して、対応する報酬を受け取ります。
解離モデルに対してトンプソンサンプリングアルゴリズムを適用し,提案アルゴリズムの変種に対する包括的後悔解析を行う。
論文 参考訳（メタデータ） (2022-06-24T18:48:35Z) - Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
論文 参考訳（メタデータ） (2021-12-13T09:48:54Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。