論文の概要: Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints

• arxiv url: http://arxiv.org/abs/2311.03376v1
• Date: Tue, 31 Oct 2023 11:04:21 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-12 19:32:15.635834
• Title: Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints
• Title（参考訳）: ブロッキング・コラボレーティブ・バンディット:オンライン・コラボレーティブ・フィルタリング
• Authors: Soumyabrata Pal, Arun Sai Suggala, Karthikeyan Shanmugam, Prateek Jain
• Abstract要約: 本稿では,複数のユーザを抱えるエンブロック型協調バンドイットの問題点について考察する。 私たちのゴールは、時間とともにすべてのユーザーが獲得した累積報酬を最大化するアルゴリズムを設計することです。 textttB-LATTICEは、予算制約の下で、ユーザ毎に$widetildeO(sqrtmathsfT(sqrtmathsfM-1)$を後悔する。
• 参考スコア（独自算出の注目度）: 46.65419724935037
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of \emph{blocked} collaborative bandits where there are multiple users, each with an associated multi-armed bandit problem. These users are grouped into \emph{latent} clusters such that the mean reward vectors of users within the same cluster are identical. Our goal is to design algorithms that maximize the cumulative reward accrued by all the users over time, under the \emph{constraint} that no arm of a user is pulled more than $\mathsf{B}$ times. This problem has been originally considered by \cite{Bresler:2014}, and designing regret-optimal algorithms for it has since remained an open problem. In this work, we propose an algorithm called \texttt{B-LATTICE} (Blocked Latent bAndiTs via maTrIx ComplEtion) that collaborates across users, while simultaneously satisfying the budget constraints, to maximize their cumulative rewards. Theoretically, under certain reasonable assumptions on the latent structure, with $\mathsf{M}$ users, $\mathsf{N}$ arms, $\mathsf{T}$ rounds per user, and $\mathsf{C}=O(1)$ latent clusters, \texttt{B-LATTICE} achieves a per-user regret of $\widetilde{O}(\sqrt{\mathsf{T}(1 + \mathsf{N}\mathsf{M}^{-1})}$ under a budget constraint of $\mathsf{B}=\Theta(\log \mathsf{T})$. These are the first sub-linear regret bounds for this problem, and match the minimax regret bounds when $\mathsf{B}=\mathsf{T}$. Empirically, we demonstrate that our algorithm has superior performance over baselines even when $\mathsf{B}=1$. \texttt{B-LATTICE} runs in phases where in each phase it clusters users into groups and collaborates across users within a group to quickly learn their reward models.
• Abstract（参考訳）: 複数のユーザがいて,それぞれが関連するマルチアームのバンディット問題を持つ,<emph{blocked>コラボレーティブなバンディットの問題を考える。 これらのユーザは,同一クラスタ内のユーザの平均報酬ベクトルが同一になるように,\emph{latent}クラスタにグループ化される。 当社の目標は、ユーザの腕が$\mathsf{b}$ times以上引き出されないという \emph{constraint} の下で、全ユーザの累積報酬を最大化するアルゴリズムを設計することです。 この問題は、元々は \cite{bresler:2014} によって検討され、それに対する後悔最適化アルゴリズムの設計は未解決の問題のままである。 本研究では,ユーザ間で協調し,同時に予算制約を満たすアルゴリズムである「texttt{B-LATTICE} (Blocked Latent bAndiTs via maTrIx ComplEtion)」を提案し,累積報酬を最大化する。 理論的には、潜在構造上の一定の合理的な仮定の下では、$\mathsf{m}$ users, $\mathsf{n}$ arms, $\mathsf{t}$ rounds per user, $\mathsf{c}=o(1)$ latent clusters, \textt{b-lattice} は$\widetilde{o}(\sqrt{\mathsf{t}(1 + \mathsf{n}\mathsf{m}^{-1})}$ という予算制約の下で$\mathsf{b}=\theta(\log \mathsf{t})$ のユーザ一人当たりの後悔を達成する。 これらはこの問題に対する最初のsub-linear regret boundsであり、$\mathsf{b}=\mathsf{t}$ のときのminimax regret boundsと一致する。 経験的に、このアルゴリズムは$\mathsf{b}=1$でもベースラインよりも優れた性能を示す。 \texttt{B-LATTICE}は、各フェーズでユーザをグループに集約し、グループ内のユーザ間でコラボレーションして、報酬モデルを簡単に学習するフェーズで動作する。

関連論文リスト

• Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
  本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。 ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-11-11T03:43:52Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
  本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。 本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
  論文  参考訳（メタデータ） (2023-01-17T17:49:04Z)
• Online Low Rank Matrix Completion [28.316718791239303]
  我々は,textitonline Low-rank matrix completion with $mathsfM$ users, $mathsfN$ items and $mathsfT roundsについて検討した。 それぞれ、低線形ユーザ-イテム報酬行列からサンプリングされた(自明な)報酬を得る。 提案アルゴリズムは,ユーザをクラスタリングし,アイテムを協調的かつ反復的に除去する新しい手法を用いて,$mathsfT$で最小値に近い最適なレートを得ることができる。
  論文  参考訳（メタデータ） (2022-09-08T18:49:10Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• 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)
• Optimal Strategies for Graph-Structured Bandits [0.0]
  Bernoulli $!=!(nu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a
  論文  参考訳（メタデータ） (2020-07-07T06:27:51Z)

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

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