論文の概要: Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
- arxiv url: http://arxiv.org/abs/2102.07800v1
- Date: Mon, 15 Feb 2021 19:10:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-18 05:51:42.797056
- Title: Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
- Title（参考訳）: Top-k$ eXtreme Contextual Bandits with Arm Hierarchy
- Authors: Rajat Sen, Alexander Rakhlin, Lexing Ying, Rahul Kidambi, Dean Foster,
Daniel Hill, Inderjit Dhillon
- Abstract要約: 我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
- 参考スコア（独自算出の注目度）: 71.17938026619068
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by modern applications, such as online advertisement and
recommender systems, we study the top-$k$ extreme contextual bandits problem,
where the total number of arms can be enormous, and the learner is allowed to
select $k$ arms and observe all or some of the rewards for the chosen arms. We
first propose an algorithm for the non-extreme realizable setting, utilizing
the Inverse Gap Weighting strategy for selecting multiple arms. We show that
our algorithm has a regret guarantee of $O(k\sqrt{(A-k+1)T \log
(|\mathcal{F}|T)})$, where $A$ is the total number of arms and $\mathcal{F}$ is
the class containing the regression function, while only requiring
$\tilde{O}(A)$ computation per time step. In the extreme setting, where the
total number of arms can be in the millions, we propose a practically-motivated
arm hierarchy model that induces a certain structure in mean rewards to ensure
statistical and computational efficiency. The hierarchical structure allows for
an exponential reduction in the number of relevant arms for each context, thus
resulting in a regret guarantee of $O(k\sqrt{(\log A-k+1)T \log
(|\mathcal{F}|T)})$. Finally, we implement our algorithm using a hierarchical
linear function class and show superior performance with respect to well-known
benchmarks on simulated bandit feedback experiments using extreme multi-label
classification datasets. On a dataset with three million arms, our reduction
scheme has an average inference time of only 7.9 milliseconds, which is a 100x
improvement.
- Abstract（参考訳）: オンライン広告やレコメンデーションシステムなどの近代的な応用に動機づけられた我々は、腕の総数が膨大になり得る極端文脈的包帯問題について研究し、学習者は、腕を選択して、選択した腕に対する報酬の全てまたは一部を観察することができる。
本稿ではまず,逆ギャップ重み付け方式を用いて,非極端実現可能設定のためのアルゴリズムを提案する。
我々のアルゴリズムは、$O(k\sqrt{(A-k+1)T \log (|\mathcal{F}|T)})$で、$A$はアームの総数であり、$\mathcal{F}$は回帰関数を含むクラスであるが、$\tilde{O}(A)$計算は時間ステップごとに必要である。
腕の総数が数百万にもなる極端な環境下では、統計的および計算的効率を確保するために、特定の構造を平均報酬で誘導する実用的な動機付け腕階層モデルを提案します。
階層構造は各文脈の関連アーム数を指数関数的に減らすことを可能にし、その結果 $O(k\sqrt{(\log A-k+1)T \log (|\mathcal{F}|T)})$ の後悔保証となる。
最後に,階層型線形関数クラスを用いてアルゴリズムを実装し,極限マルチラベル分類データセットを用いたシミュレーションバンディットフィードバック実験において,よく知られたベンチマークに対して優れた性能を示す。
300万の腕を持つデータセットでは、平均推定時間はわずか7.9ミリ秒であり、これは100倍の改善である。
関連論文リスト
- A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem [10.994427113326996]
この問題の例としては、$k$のアームがあり、それぞれの報酬関数は凹凸であり、腕が引き抜かれた回数の関数が増加する。
任意のランダム化オンラインアルゴリズムに対して、最適報酬に対して少なくとも$Omega(sqrtk)$近似係数を負わなければならない事例が存在することを示す。
次に、この仮定を余分な$O(sqrtk log k)$近似係数のコストで除去する方法を示し、全体的な$O(sqrtk)を達成する。
論文 参考訳（メタデータ） (2024-04-01T15:55:45Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。
C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
論文 参考訳（メタデータ） (2021-09-10T15:41:07Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - 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) - Blocking Bandits [33.14975454724348]
我々は、腕を弾くことで固定時間帯で使用できなくなる、新しいマルチアームバンディット・セッティングについて考察する。
全ての武器の報酬と遅延の事前知識により、累積報酬を最適化する問題は擬似多項式時間アルゴリズムを含まないことを示した。
我々は,このアルゴリズムに対して,$c log T + o(log T)$ cumulative regret を持つ UCB ベースのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2019-07-27T20:42:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。