論文の概要: On the optimal regret of collaborative personalized linear bandits

• arxiv url: http://arxiv.org/abs/2506.15943v1
• Date: Thu, 19 Jun 2025 00:56:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-23 19:00:04.902272
• Title: On the optimal regret of collaborative personalized linear bandits
• Title（参考訳）: 協調的パーソナライズされた線形包帯の最適後悔について
• Authors: Bruce Huang, Ruida Zhou, Lin F. Yang, Suhas Diggavi,
• Abstract要約: 本稿では,協調的パーソナライズされたリニアバンディットにおける最適後悔について検討する。 我々は,エージェント数,相互作用ラウンド,不均一性の程度が共に後悔にどう影響するかを特徴付ける情報理論の下限を提供する。 私たちの結果は、いつ、いつ、コラボレーションが最適な後悔の束縛でどのように役立つか、完全な特徴を与えます。
• 参考スコア（独自算出の注目度）: 15.661920010658626
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic linear bandits are a fundamental model for sequential decision making, where an agent selects a vector-valued action and receives a noisy reward with expected value given by an unknown linear function. Although well studied in the single-agent setting, many real-world scenarios involve multiple agents solving heterogeneous bandit problems, each with a different unknown parameter. Applying single agent algorithms independently ignores cross-agent similarity and learning opportunities. This paper investigates the optimal regret achievable in collaborative personalized linear bandits. We provide an information-theoretic lower bound that characterizes how the number of agents, the interaction rounds, and the degree of heterogeneity jointly affect regret. We then propose a new two-stage collaborative algorithm that achieves the optimal regret. Our analysis models heterogeneity via a hierarchical Bayesian framework and introduces a novel information-theoretic technique for bounding regret. Our results offer a complete characterization of when and how collaboration helps with a optimal regret bound $\tilde{O}(d\sqrt{mn})$, $\tilde{O}(dm^{1-\gamma}\sqrt{n})$, $\tilde{O}(dm\sqrt{n})$ for the number of rounds $n$ in the range of $(0, \frac{d}{m \sigma^2})$, $[\frac{d}{m^{2\gamma} \sigma^2}, \frac{d}{\sigma^2}]$ and $(\frac{d}{\sigma^2}, \infty)$ respectively, where $\sigma$ measures the level of heterogeneity, $m$ is the number of agents, and $\gamma\in[0, 1/2]$ is an absolute constant. In contrast, agents without collaboration achieve a regret bound $O(dm\sqrt{n})$ at best.
• Abstract（参考訳）: 確率線形帯域は逐次決定のための基本モデルであり、エージェントがベクトル値のアクションを選択し、未知の線形関数によって与えられる期待値のノイズ報酬を受け取る。 単一エージェント環境ではよく研究されているが、多くの実世界のシナリオでは、それぞれ異なる未知のパラメータを持つ異種バンディット問題を解く複数のエージェントが関与している。 単一エージェントアルゴリズムを独立して適用することは、エージェント間の類似性と学習機会を無視する。 本稿では,協調的パーソナライズされたリニアバンディットにおける最適後悔について検討する。 我々は,エージェント数,相互作用ラウンド,不均一性の程度が共に後悔にどう影響するかを特徴付ける情報理論の下限を提供する。 次に,最適後悔を実現する2段階協調アルゴリズムを提案する。 本稿では,階層的ベイズ的枠組みによる不均一性をモデル化し,新たな情報理論を導入し,後悔を和らげる手法を提案する。 我々の結果は、いつ、どのようにコラボレートが最適後悔境界付き$\tilde{O}(d\sqrt{mn})$, $\tilde{O}(dm^{1-\gamma}\sqrt{n})$, $\tilde{O}(dm\sqrt{n})$ for the number of rounds $n$ in the range of $(0, \frac{d}{m \sigma^2})$, $[\frac{d}{m^{2\gamma} \sigma^2}, \frac{d}{\sigma^2}]$, $(\frac{d}{\sigma^2}, \infty)$, $(\frac{d}{\sigma^2})$, $[0, \gamma 1/2]$に対して、それぞれ$\tilde{O}(dm\sqrt{n})$, $[\tilde{O}(dm\sqrt{n})$, $[0, $[0, $[0,\gamma]$, $[0, $\gamma の値の値が絶対値となるかの完全な特徴を与える。 これとは対照的に、コラボレーションのないエージェントは、せいぜい$O(dm\sqrt{n})$の償却を達成する。

関連論文リスト

• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。 我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。 我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
  論文  参考訳（メタデータ） (2024-10-22T19:34:53Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである 本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。 マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-02-11T01:51:15Z)
• Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  本稿では,マルチアームバンディット(R-CPE-MAB)問題の実測値について検討する。 一般トンプソンサンプリング探索法(GenTS-Explore)と呼ばれるアルゴリズムを導入する。これは,アクションセットのサイズが指数関数的に$d$で大きい場合でも動作可能な,最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-08-20T11:56:02Z)
• Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
  本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。 疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。 後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
  論文  参考訳（メタデータ） (2023-05-30T16:05:44Z)
• Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds [31.5504566292927]
  我々は, 後悔を最小限に抑えるために, 中央サーバを介して協調できる$M$エージェントを含む線形帯域幅問題を考える。 これらのエージェントのわずか$alpha$は敵対的であり、任意に作用し、次の緊張に繋がる。 我々は、厳密な信頼区間を慎重に構築し、探索と探索のトレードオフをバランスさせる新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-06-06T18:16:34Z)
• Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
  我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。 すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
  論文  参考訳（メタデータ） (2022-05-12T19:46:35Z)
• Distributed Bandits with Heterogeneous Agents [38.90376765616447]
  本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。 本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。 Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
  論文  参考訳（メタデータ） (2022-01-23T20:04:15Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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