論文の概要: Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing

• arxiv url: http://arxiv.org/abs/2512.21626v1
• Date: Thu, 25 Dec 2025 11:19:09 GMT
• ステータス: 情報取得中
• システム内更新日: 2025-12-29 12:06:59.2175
• Title: Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing
• Title（参考訳）: 優先順位付きアーム容量共有を用いたマルチプレイ確率帯域分割
• Authors: Hong Xie, Haoran Gu, Yanying Huang, Tao Tan, Defu Lian,
• Abstract要約: このモデルは、$M$armと$K$playで構成されている。 各アームには複数の能力があり、各ユニットの能力は報酬関数に関連付けられている。 複数のプレーがアームキャパシティを競う場合、アームキャパシティは第1の優先重みで割り当てられる。
• 参考スコア（独自算出の注目度）: 52.124267908936396
• License:
• Abstract: This paper proposes a variant of multiple-play stochastic bandits tailored to resource allocation problems arising from LLM applications, edge intelligence, etc. The model is composed of $M$ arms and $K$ plays. Each arm has a stochastic number of capacities, and each unit of capacity is associated with a reward function. Each play is associated with a priority weight. When multiple plays compete for the arm capacity, the arm capacity is allocated in a larger priority weight first manner. Instance independent and instance dependent regret lower bounds of $Ω( α_1 σ\sqrt{KM T} )$ and $Ω(α_1 σ^2 \frac{M}Δ \ln T)$ are proved, where $α_1$ is the largest priority weight and $σ$ characterizes the reward tail. When model parameters are given, we design an algorithm named \texttt{MSB-PRS-OffOpt} to locate the optimal play allocation policy with a computational complexity of $O(MK^3)$. Utilizing \texttt{MSB-PRS-OffOpt} as a subroutine, an approximate upper confidence bound (UCB) based algorithm is designed, which has instance independent and instance dependent regret upper bounds matching the corresponding lower bound up to factors of $ \sqrt{K \ln KT }$ and $α_1 K^2$ respectively. To this end, we address nontrivial technical challenges arising from optimizing and learning under a special nonlinear combinatorial utility function induced by the prioritized resource sharing mechanism.
• Abstract（参考訳）: 本稿では,LLMアプリケーションやエッジインテリジェンスなどによる資源配分問題に適したマルチプレイ確率的バンディットを提案する。 このモデルは、$M$armと$K$playで構成されている。 各アームには確率的な容量があり、各ユニットの能力は報酬関数に関連付けられている。 各プレイは優先順位の重みに関連付けられている。 複数のプレーがアームキャパシティを競う場合、アームキャパシティは第1の優先重みで割り当てられる。 インスタンス独立かつインスタンス依存的後悔 Ω(α_1 σ\sqrt{KM T} )$ と $Ω(α_1 σ^2 \frac{M}Δ \ln T)$ の下位境界が証明され、ここでは$α_1$が最優先重みであり、$σ$が報酬尾を特徴づける。 モデルパラメータが与えられた場合、最適プレイアロケーションポリシーを計算複雑性$O(MK^3)$で探索するアルゴリズムを設計する。 サブルーチンとして \texttt{MSB-PRS-OffOpt} を用いると、それぞれ$ \sqrt{K \ln KT }$ と $α_1 K^2$ の係数に一致するインスタンス独立およびインスタンス依存の後悔の上界を持つ近似上信頼境界(UCB)ベースのアルゴリズムが設計される。 この目的のために、優先順位付けされたリソース共有機構によって誘導される特別な非線形組合せユーティリティ関数の下で、最適化と学習から生じる非自明な技術的課題に対処する。

関連論文リスト

• Batched Stochastic Matching Bandits [43.651070266360954]
  本稿では,MNL選択モデルに基づくマッチングのための新しい帯域幅フレームワークを提案する。 私たちの設定では、一方の$N$エージェントは他方の$K$アームに割り当てられます。 目的は、すべてのエージェントで成功した試合から累積収入を最大化することで、後悔を最小限に抑えることである。
  論文  参考訳（メタデータ） (2025-09-04T13:16:32Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。 本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。 我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
  論文  参考訳（メタデータ） (2024-08-27T18:28:31Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
  遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。 我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。 問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
  論文  参考訳（メタデータ） (2023-01-18T00:53:46Z)
• Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes [8.919345630832366]
  本稿では,アクションセットと時間変化によるベースアームの可利用性に関するコンテキスト的帯域幅問題について考察する。 我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。 アルゴリズムを劇的に高速化するために,スパースGPを用いたO'CLOK-UCBの変種を提案する。
  論文  参考訳（メタデータ） (2021-10-05T18:02:10Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• 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)

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

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