論文の概要: Decentralized Competing Bandits in Non-Stationary Matching Markets
- arxiv url: http://arxiv.org/abs/2206.00120v1
- Date: Tue, 31 May 2022 21:05:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-02 16:43:55.869487
- Title: Decentralized Competing Bandits in Non-Stationary Matching Markets
- Title（参考訳）: 非定常マッチング市場における分散競合バンディット
- Authors: Avishek Ghosh, Abishek Sankararaman, Kannan Ramchandran, Tara Javidi
and Arya Mazumdar
- Abstract要約: 非定常(動的)環境下での分散化二面マッチング市場の枠組みを紹介する。
分散非定常競合帯域(textttDNCB)を用いた分散非同期学習アルゴリズムの提案と解析を行う。
我々はこの強調探索を特徴付け、texttDNCBのサブ線形(対数的)後悔を得る。
- 参考スコア（独自算出の注目度）: 46.13741000158631
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Understanding complex dynamics of two-sided online matching markets, where
the demand-side agents compete to match with the supply-side (arms), has
recently received substantial interest. To that end, in this paper, we
introduce the framework of decentralized two-sided matching market under non
stationary (dynamic) environments. We adhere to the serial dictatorship
setting, where the demand-side agents have unknown and different preferences
over the supply-side (arms), but the arms have fixed and known preference over
the agents. We propose and analyze a decentralized and asynchronous learning
algorithm, namely Decentralized Non-stationary Competing Bandits
(\texttt{DNCB}), where the agents play (restrictive) successive elimination
type learning algorithms to learn their preference over the arms. The
complexity in understanding such a system stems from the fact that the
competing bandits choose their actions in an asynchronous fashion, and the
lower ranked agents only get to learn from a set of arms, not \emph{dominated}
by the higher ranked agents, which leads to \emph{forced exploration}. With
carefully defined complexity parameters, we characterize this \emph{forced
exploration} and obtain sub-linear (logarithmic) regret of \texttt{DNCB}.
Furthermore, we validate our theoretical findings via experiments.
- Abstract（参考訳）: 需要側のエージェントが供給側(arms)と競争するオンラインマッチング市場の複雑なダイナミクスを理解することが最近大きな関心を集めている。
そこで本稿では,非定常(動的)環境下での分散化二面マッチング市場の枠組みを紹介する。
我々は、需要側エージェントが供給側(武器)に対して未知で異なる嗜好を持つシリアルな独裁体制に固執するが、武器はエージェントに対して固定され、既知の嗜好を持つ。
本稿では,分散非定常競合帯域(Decentralized Non-stationary Competing Bandits (\texttt{DNCB})と呼ばれる分散型非同期学習アルゴリズムを提案する。
このようなシステムの理解の複雑さは、競合するバンドイットが非同期に行動を選択し、下位のエージェントは上位のエージェントによって「emph{dominated}」ではなく「emph{forced Explor}」と呼ばれる一連のアームからしか学ばないという事実に起因している。
慎重に定義された複雑性パラメータを用いて、この \emph{forced exploration} を特徴付け、textt{dncb} の部分線形(対数)後悔を得る。
さらに,実験により理論的知見を検証した。
関連論文リスト
- Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳（メタデータ） (2023-08-29T18:18:21Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳（メタデータ） (2023-05-01T06:46:22Z) - Decentralized, Communication- and Coordination-free Learning in
Structured Matching Markets [2.9833943723592764]
両面マッチング市場における競争環境におけるオンライン学習の問題について検討する。
本稿では、エージェントが安定したマッチングに到達できるように、分散化、通信、調整不要なアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2022-06-06T04:08:04Z) - Private and Byzantine-Proof Cooperative Decision-Making [15.609414012418043]
協調バンディット問題は、多腕バンディットと同時に相互作用するエージェントのグループを含むマルチエージェント決定問題である。
本稿では、エージェントがアクションシーケンスに関して通信をプライベートにしたい場合と、エージェントがビザンチンになり得る場合の2つの設定の下で、バンドイット問題を調査する。
我々は,(a)微分プライベートかつ(b)プライベートでありながら,最適な後悔を得る高信頼有界アルゴリズムを提供する。
我々の分散アルゴリズムはエージェント間の接続のネットワークに関する情報を必要とせず、大規模な動的システムにスケーラブルにします。
論文 参考訳（メタデータ） (2022-05-27T18:03:54Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z) - Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。
このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。
アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文 参考訳（メタデータ） (2020-12-14T08:58:07Z) - Learning Strategies in Decentralized Matching Markets under Uncertain
Preferences [91.3755431537592]
エージェントの選好が不明な場合,共有資源の不足の設定における意思決定の問題について検討する。
我々のアプローチは、再生されたカーネルヒルベルト空間における好みの表現に基づいている。
エージェントの期待した利益を最大化する最適な戦略を導出する。
論文 参考訳（メタデータ） (2020-10-29T03:08:22Z) - Dominate or Delete: Decentralized Competing Bandits in Serial
Dictatorship [16.883188358641398]
我々は、需要側エージェントが供給側(武器)に対して未知かつ不均一な評価を有する二面マッチング市場について検討する。
エージェントのための分散ドミナントアーム削除 (UCB-D3) を用いた最初の分散アルゴリズムを設計する。
本稿では, 分散化直列独裁モデルに対する新たな後悔の低減と, UCB-D3 が最適であることを示す。
論文 参考訳（メタデータ） (2020-06-26T18:44:06Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。