論文の概要: 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倍の改善である。

関連論文リスト

• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• 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)
• Sleeping Combinatorial Bandits [15.004764451770441]
  睡眠帯域設定においてよく知られたCUCBアルゴリズムを適用し,それをCSUCBと呼ぶ。 穏やかな条件下では、CSUCBアルゴリズムが$O(sqrtT log (T)$ instance-dependent regret guaranteeを達成することを証明します。 我々の結果は極めて一般的なものであり、非付加的な報酬関数、揮発性アームの可用性、引くべきベースアームの変動数など、実用的な応用によって生じる一般的な環境下で維持されます。
  論文  参考訳（メタデータ） (2021-06-03T06:49:44Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• 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)
• Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
  最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。 我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。 鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
  論文  参考訳（メタデータ） (2021-01-30T21:51:47Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。