論文の概要: Competing Bandits in Decentralized Large Contextual Matching Markets

• arxiv url: http://arxiv.org/abs/2411.11794v1
• Date: Mon, 18 Nov 2024 18:08:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-19 14:35:31.810656
• Title: Competing Bandits in Decentralized Large Contextual Matching Markets
• Title（参考訳）: 分散型大規模コンテキストマッチング市場における帯域競争
• Authors: Satush Parikh, Soumya Basu, Avishek Ghosh, Abishek Sankararaman,
• Abstract要約: 我々は、需要側(プレイヤーまたはエージェント)が大きな供給側(腕)と競合する二面的マッチング市場における分散学習を研究する。 提案アルゴリズムは,腕の数によらず,インスタンス依存の対数的後悔を実現する。
• 参考スコア（独自算出の注目度）: 13.313881962771777
• License:
• Abstract: Sequential learning in a multi-agent resource constrained matching market has received significant interest in the past few years. We study decentralized learning in two-sided matching markets where the demand side (aka players or agents) competes for a `large' supply side (aka arms) with potentially time-varying preferences, to obtain a stable match. Despite a long line of work in the recent past, existing learning algorithms such as Explore-Then-Commit or Upper-Confidence-Bound remain inefficient for this problem. In particular, the per-agent regret achieved by these algorithms scales linearly with the number of arms, $K$. Motivated by the linear contextual bandit framework, we assume that for each agent an arm-mean can be represented by a linear function of a known feature vector and an unknown (agent-specific) parameter. Moreover, our setup captures the essence of a dynamic (non-stationary) matching market where the preferences over arms change over time. Our proposed algorithms achieve instance-dependent logarithmic regret, scaling independently of the number of arms, $K$.
• Abstract（参考訳）: マルチエージェントリソース制約型市場におけるシーケンシャルラーニングは,ここ数年で大きな関心を集めている。 需要側(プレイヤーやエージェント)が「大きな」供給側(いわゆるアーム)と、潜在的に時間によって異なる好みで競合する二面的なマッチング市場において、分散学習を学習し、安定したマッチングを得る。 近年の長い作業にもかかわらず、Explore-Then-CommitやUpper-Confidence-Boundといった既存の学習アルゴリズムは、この問題に対して非効率なままである。 特に、これらのアルゴリズムによって達成された一人当たりの後悔は、腕の数と線形にスケールし、$K$である。 ここでは,各エージェントに対して既知の特徴ベクトルの線形関数と未知の(エージェント固有の)パラメータを表現できることを仮定する。 さらに、我々の設定は、時間とともに武器よりも好みが変わる動的な(静止しない)市場の本質を捉えている。 提案アルゴリズムは,腕の数によらず,インスタンス依存の対数的後悔を実現する。

関連論文リスト

• Pure Exploration under Mediators' Feedback [63.56002444692792]
  マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。 本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。 本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
  論文  参考訳（メタデータ） (2023-08-29T18:18:21Z)
• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation [56.715186432566576]
  そこで本稿では,大規模状態空間と多数のエージェントを用いた強化学習のための新しいモデルである独立線形マルコフゲームを提案する。 我々は,各エージェントの関数クラスの複雑性にのみ対応して,サンプル境界複雑性を持つ相関平衡 (CCE) とマルコフ相関平衡 (CE) を学習するための新しいアルゴリズムを設計する。 提案アルゴリズムは,1)複数のエージェントによる非定常性に対処するためのポリシーリプレイと,機能近似の利用,2)マルコフ均衡の学習とマルコフゲームにおける探索の分離という,2つの重要な技術革新に依存している。
  論文  参考訳（メタデータ） (2023-02-07T18:47:48Z)
• Decentralized Competing Bandits in Non-Stationary Matching Markets [46.13741000158631]
  非定常(動的)環境下での分散化二面マッチング市場の枠組みを紹介する。 分散非定常競合帯域(textttDNCB)を用いた分散非同期学習アルゴリズムの提案と解析を行う。 我々はこの強調探索を特徴付け、texttDNCBのサブ線形(対数的)後悔を得る。
  論文  参考訳（メタデータ） (2022-05-31T21:05:30Z)
• Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets [151.03738099494765]
  我々は、市場の両側でプランナーと戦略エージェントのセットを含むマルコフマッチング市場について検討する。 本稿では,楽観的な値反復と最大重みマッチングを組み合わせた強化学習フレームワークを提案する。 我々は,アルゴリズムがサブ線形後悔を実現することを証明した。
  論文  参考訳（メタデータ） (2022-03-07T19:51:25Z)
• Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demand [11.935419090901524]
  本稿では,非定常要求の繰り返しCournotゲームについてモデル化する。 エージェントが選択できる武器/アクションのセットは、個別の生産量を表す。 本稿では,よく知られた$epsilon$-greedyアプローチに基づく,新しいアルゴリズム"Adaptive with Weighted Exploration (AWE) $epsilon$-greedy"を提案する。
  論文  参考訳（メタデータ） (2022-01-03T05:51:47Z)
• Modelling Cournot Games as Multi-agent Multi-armed Bandits [4.751331778201811]
  繰り返しCournot oligopolyゲームにおけるマルチエージェントマルチアーム・バンディット(MA-MAB)の設定について検討した。 私たちは、$epsilon$-greedyアプローチが、従来のMABアプローチよりもより実行可能な学習メカニズムを提供することに気付きました。 順序付けられたアクション空間を利用する新しいアプローチとして、$epsilon$-greedy+HLと$epsilon$-greedy+ELを提案する。
  論文  参考訳（メタデータ） (2022-01-01T22:02:47Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。 私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
  論文  参考訳（メタデータ） (2021-08-19T17:59:28Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Contextual Blocking Bandits [35.235375147227124]
  我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。 アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。 我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2020-03-06T20:34:42Z)

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

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