論文の概要: A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming
- arxiv url: http://arxiv.org/abs/2606.29221v1
- Date: Sun, 28 Jun 2026 06:13:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-30 18:07:15.836532
- Title: A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming
- Title（参考訳）: オンラインマルチHuman Multi-Robot Teamingにおける線形マッチングバンドバンドアプローチ
- Abstract要約: 我々は,未知の特徴の信頼区間を更新し,不確実性の下で楽観的なマッチングを行うオンライン学習アルゴリズムLinMatchを提案する。
提案アルゴリズムとバウンダリは,人間-ロボットマッチング以外の応用において,幅広いマッチング問題に適用できる。
- 参考スコア（独自算出の注目度）: 5.669894448797468
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We address the problem of online multi-human multi-robot teaming through the lens of a linear matching bandit framework, where a learner assigns robots with unknown features from a fixed pool to distinct sets of human agents over multiple rounds. To solve this problem, we propose LinMatch, an online learning algorithm that updates the confidence intervals of the unknown features and makes the optimistic matching under uncertainty. The contributions and novelty of this work are twofold. First, we recast the optimistic matching problem in each round as a linear program of maximum weighted matching, efficiently solvable by the celebrated Hungarian algorithm. Second, we provide novel bounds for matching with linear feature problems, showing an upper bound of $\tilde{O}(d\sqrt{MKT})$ and a minimax lower bound of $Ω(d\sqrt{MKT})$, establishing a tight optimal regret rate of $\tildeΘ(d\sqrt{MKT})$. This demonstrates that LinMatch achieves strictly optimal achievable regret with respect to the total number of rounds $T$, the feature dimension $d$, and the matching parameters $M$ and $K$. The proposed algorithm and bounds apply to a wide range of matching problems with applications beyond human-robot matching, such as housing allocation, recommendation systems, and more.
- Abstract（参考訳）: 学習者は、固定プールから未知の特徴を持つロボットを複数のラウンドで異なる人間のエージェント群に割り当てるという、線形マッチングバンディットフレームワークのレンズを通して、オンラインマルチヒューマン・マルチロボット・コラボレーションの課題に対処する。
この問題を解決するために,未知の特徴の信頼区間を更新し,不確実性の下で楽観的なマッチングを行うオンライン学習アルゴリズムLinMatchを提案する。
この作品の貢献と新規性は2つある。
まず,各ラウンドの楽観的マッチング問題を,ハンガリーの有名なアルゴリズムで効率的に解ける最大重み付きマッチングの線形プログラムとして再検討する。
第二に、線形特徴問題にマッチする新しい境界を提供し、上限が$\tilde{O}(d\sqrt{MKT})$とミニマックス下限が$Ω(d\sqrt{MKT})$であり、厳密な最適後悔率が$\tilde(d\sqrt{MKT})$であることを示す。
これは、LinMatchがラウンドの総数$T$、特徴次元$d$、マッチングパラメータ$M$と$K$に関して厳密に最適に達成可能な後悔を達成していることを示している。
提案したアルゴリズムとバウンダリは、住宅割当やレコメンデーションシステムなど、人間-ロボットマッチング以外の応用における幅広いマッチング問題に適用できる。
関連論文リスト
- Offline Local Search for Online Stochastic Bandits [3.029373177207996]
コンビニアル・マルチアーマード・バンディットは基本的なオンライン意思決定環境を提供する。
目的は、後ろ向きの最適な固定アクションに比べて損失として定義される後悔である。
オフラインの欲求と線形最適化アルゴリズム(正確にも近似的にも)は、オンラインにデプロイする際に有用な保証を提供することが示されている。
論文 参考訳（メタデータ） (2026-04-10T15:36:11Z) - Bandits with Single-Peaked Preferences and Limited Resources [6.205308371824035]
アルゴリズムがU$ユーザとK$アームとを逐次一致させるオンラインマッチング問題について検討する。
構造的仮定がなければ、最適マッチングの計算はNPハードであり、オンライン学習は計算不可能である。
我々はオフラインの予算マッチング問題に対する効率的なアルゴリズムを考案し、それを$tilde O(UKT2/3)$を後悔して効率的なオンラインアルゴリズムに活用する。
論文 参考訳（メタデータ） (2025-10-10T14:27:25Z) - Batched Stochastic Matching Bandits [43.651070266360954]
本稿では,MNL選択モデルに基づくマッチングのための新しい帯域幅フレームワークを提案する。
私たちの設定では、一方の$N$エージェントは他方の$K$アームに割り当てられます。
目的は、すべてのエージェントで成功した試合から累積収入を最大化することで、後悔を最小限に抑えることである。
論文 参考訳（メタデータ） (2025-09-04T13:16:32Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - 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) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。