論文の概要: Batched Stochastic Matching Bandits

• arxiv url: http://arxiv.org/abs/2509.04194v1
• Date: Thu, 04 Sep 2025 13:16:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-05 20:21:10.170094
• Title: Batched Stochastic Matching Bandits
• Title（参考訳）: バッチ確率マッチングバンド
• Authors: Jung-hun Kim, Min-hwan Oh,
• Abstract要約: 本稿では,MNL選択モデルに基づくマッチングのための新しい帯域幅フレームワークを提案する。 私たちの設定では、一方の$N$エージェントは他方の$K$アームに割り当てられます。 目的は、すべてのエージェントで成功した試合から累積収入を最大化することで、後悔を最小限に抑えることである。
• 参考スコア（独自算出の注目度）: 43.651070266360954
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this study, we introduce a novel bandit framework for stochastic matching based on the Multi-nomial Logit (MNL) choice model. In our setting, $N$ agents on one side are assigned to $K$ arms on the other side, where each arm stochastically selects an agent from its assigned pool according to an unknown preference and yields a corresponding reward. The objective is to minimize regret by maximizing the cumulative revenue from successful matches across all agents. This task requires solving a combinatorial optimization problem based on estimated preferences, which is NP-hard and leads a naive approach to incur a computational cost of $O(K^N)$ per round. To address this challenge, we propose batched algorithms that limit the frequency of matching updates, thereby reducing the amortized computational cost (i.e., the average cost per round) to $O(1)$ while still achieving a regret bound of $\tilde{O}(\sqrt{T})$.
• Abstract（参考訳）: 本研究では,MNL選択モデルに基づく確率マッチングのための新しい帯域幅フレームワークを提案する。 我々の設定では、一方の$N$エージェントは他方の$K$アームに割り当てられ、各アームは未知の好みに応じて割り当てられたプールからエージェントを確率的に選択し、対応する報酬を得る。 目的は、すべてのエージェントで成功した試合から累積収入を最大化することで、後悔を最小限に抑えることである。 このタスクは、NPハードであり、1ラウンドあたりの計算コストが$O(K^N)$であるような単純なアプローチを導く、推定された選好に基づいて組合せ最適化問題を解決する必要がある。 この課題に対処するために、我々はバッチアルゴリズムを提案し、一致頻度を制限することにより、償却計算コスト(すなわち、ラウンド当たりの平均コスト)を$O(1)$に削減し、なおも$\tilde{O}(\sqrt{T})$の償却バウンダリを達成している。

関連論文リスト

• Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
  我々は、学習者が$m$の腕から$m$の腕を正確に選択する、$m$セット半帯域問題の一般的な場合を考える。 また, Fr'echet 摂動を持つFTPL は, 対向的な設定で, $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ をほぼ最適に再現できることを示す。
  論文  参考訳（メタデータ） (2025-04-09T22:07:01Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
  本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。 提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
  論文  参考訳（メタデータ） (2023-01-31T03:49:00Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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