論文の概要: Clustered Linear Contextual Bandits with Knapsacks
- arxiv url: http://arxiv.org/abs/2308.10722v1
- Date: Mon, 21 Aug 2023 13:47:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-22 13:19:56.791925
- Title: Clustered Linear Contextual Bandits with Knapsacks
- Title（参考訳）: クナップサックを用いたクラスタ化線形コンテキスト帯域
- Authors: Yichuan Deng, Michalis Mamakos, Zhao Song
- Abstract要約: 本研究では,クラスタ固有の線形モデルの帰結として,報酬と資源消費が帰結するクラスタ化されたコンテキスト帯について検討する。
一定期間に腕を引っ張ると、複数のリソースのそれぞれに対して報酬と消費が生じる。
ランダムに選択された腕の部分集合に1回だけクラスタリングを実行するだけで十分であることを示す。
- 参考スコア（独自算出の注目度）: 9.668078830796999
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this work, we study clustered contextual bandits where rewards and
resource consumption are the outcomes of cluster-specific linear models. The
arms are divided in clusters, with the cluster memberships being unknown to an
algorithm. Pulling an arm in a time period results in a reward and in
consumption for each one of multiple resources, and with the total consumption
of any resource exceeding a constraint implying the termination of the
algorithm. Thus, maximizing the total reward requires learning not only models
about the reward and the resource consumption, but also cluster memberships. We
provide an algorithm that achieves regret sublinear in the number of time
periods, without requiring access to all of the arms. In particular, we show
that it suffices to perform clustering only once to a randomly selected subset
of the arms. To achieve this result, we provide a sophisticated combination of
techniques from the literature of econometrics and of bandits with constraints.
- Abstract（参考訳）: 本研究では,クラスタ固有の線形モデルの結果が報酬とリソース消費であるクラスタ化されたコンテキストバンディットについて検討する。
腕はクラスターに分割され、クラスタのメンバーシップはアルゴリズムによって未知である。
時間内にアームをプルすると、複数のリソースのそれぞれに対して報酬と消費が得られ、アルゴリズムの終了を意味する制約を超えるリソースの総消費が発生する。
したがって、全報酬を最大化するには、報酬とリソース消費に関するモデルだけでなく、クラスタメンバシップも学習する必要がある。
全アームへのアクセスを必要とせず、一定期間内に後悔のサブリニアを実現するアルゴリズムを提供する。
特に、腕のランダムに選択されたサブセットに一度だけクラスタリングを実行することが十分であることを示す。
この結果を達成するために、計量学の文献と制約付きバンディットの技法の洗練された組み合わせを提供する。
関連論文リスト
- Large Scale Constrained Clustering With Reinforcement Learning [1.3597551064547502]
ネットワークが与えられた場合、各ノードではなく、クラスタレベルでリソースを割り当てることによって、リソースの割り当てと使用効率が向上する。
本稿では,この制約付きクラスタリング問題を強化学習を用いて解く手法を提案する。
結果の節では,大規模インスタンスにおいても,アルゴリズムが最適に近い解を見つけることを示す。
論文 参考訳（メタデータ） (2024-02-15T18:27:18Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Hard Regularization to Prevent Deep Online Clustering Collapse without
Data Augmentation [65.268245109828]
オンラインディープクラスタリング(オンラインディープクラスタリング)とは、機能抽出ネットワークとクラスタリングモデルを組み合わせて、クラスタラベルを処理された各新しいデータポイントまたはバッチに割り当てることである。
オフラインメソッドよりも高速で汎用性が高いが、オンラインクラスタリングは、エンコーダがすべての入力を同じポイントにマッピングし、すべてを単一のクラスタに配置する、崩壊したソリューションに容易に到達することができる。
本稿では,データ拡張を必要としない手法を提案する。
論文 参考訳（メタデータ） (2023-03-29T08:23:26Z) - Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。
本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
論文 参考訳（メタデータ） (2023-01-17T17:49:04Z) - Genie: A new, fast, and outlier-resistant hierarchical clustering
algorithm [3.7491936479803054]
我々はGenieと呼ばれる新しい階層的クラスタリングリンク基準を提案する。
我々のアルゴリズムは、2つのクラスタを、選択された経済不平等尺度が与えられたしきい値を超えないようにリンクする。
このアルゴリズムのリファレンス実装は、Rのためのオープンソースの'genie'パッケージに含まれている。
論文 参考訳（メタデータ） (2022-09-13T06:42:53Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
半教師付きMSSCのための分岐結合アルゴリズムを提案する。
背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。
提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
論文 参考訳（メタデータ） (2021-11-30T17:08:53Z) - Censored Semi-Bandits for Resource Allocation [12.450488894967773]
我々は、検閲された半バンド構成でリソースを順次割り当てる問題を考える。
損失は2つの隠れたパラメータに依存する。1つはarmに固有のが、リソース割り当てには依存せず、もう1つは割り当てられたリソースに依存する。
MP-MABおよびCombinial Semi-Banditsの既知のアルゴリズムを使用して、問題設定に最適なアルゴリズムを導き出します。
論文 参考訳（メタデータ） (2021-04-12T19:15:32Z) - Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous
Feedback [32.62857394584907]
複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。
本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-13T12:25:41Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。