論文の概要: Competing Bandits in Time Varying Matching Markets
- arxiv url: http://arxiv.org/abs/2210.11692v1
- Date: Fri, 21 Oct 2022 02:36:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-24 16:21:43.390278
- Title: Competing Bandits in Time Varying Matching Markets
- Title（参考訳）: 一致する市場が異なる時間における競合するバンディット
- Authors: Deepan Muthirayan, Chinmay Maheshwari, Pramod P. Khargonekar, Shankar
Sastry
- Abstract要約: 両面の非定常マッチング市場におけるオンライン学習の課題について検討し,安定したマッチングに収束することが目的である。
非定常性を扱うための単純な再起動戦略を組み合わせたRCB(Restart Competing Bandits)アルゴリズムを提案する。
提案アルゴリズムにより,各プレイヤーは,エージェントの嗜好の変動数に対して,$widetildemathcalO(L1/2_TT1/2)$の均一なサブ線形後悔を受けることを示す。
- 参考スコア（独自算出の注目度）: 1.1470070927586014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of online learning in two-sided non-stationary matching
markets, where the objective is to converge to a stable match. In particular,
we consider the setting where one side of the market, the arms, has fixed known
set of preferences over the other side, the players. While this problem has
been studied when the players have fixed but unknown preferences, in this work
we study the problem of how to learn when the preferences of the players are
time varying. We propose the {\it Restart Competing Bandits (RCB)} algorithm,
which combines a simple {\it restart strategy} to handle the non-stationarity
with the {\it competing bandits} algorithm \citep{liu2020competing} designed
for the stationary case. We show that, with the proposed algorithm, each player
receives a uniform sub-linear regret of
{$\widetilde{\mathcal{O}}(L^{1/2}_TT^{1/2})$} up to the number of changes in
the underlying preference of agents, $L_T$. We also discuss extensions of this
algorithm to the case where the number of changes need not be known a priori.
- Abstract（参考訳）: 両面の非定常マッチング市場におけるオンライン学習の課題について検討し,安定したマッチングに収束することが目的である。
特に、市場の一方の側、腕が、もう一方の側、プレイヤーに対して既知の選好のセットを固定した設定を考える。
本研究は,プレイヤーの嗜好が一定だが未知の嗜好が与えられた場合に,プレイヤーの嗜好が変動する際の学習方法について議論するものである。
そこで本研究では,非定常性を扱うための単純な {\it restart competing bandits (rcb) アルゴリズムと,定常ケース用に設計された {\it competing bandits} アルゴリズム \citep{liu2020competing} を組み合わせる。
提案アルゴリズムにより,各プレイヤーは,エージェントの嗜好の変化量である$L_T$に対して,{$\widetilde{\mathcal{O}}(L^{1/2}_TT^{1/2})$} の均一なサブ線形後悔を受けることを示す。
また,このアルゴリズムの拡張について,変更回数を事前に知る必要のない場合に論じる。
関連論文リスト
- Competing Bandits in Decentralized Large Contextual Matching Markets [13.313881962771777]
我々は、需要側(プレイヤーまたはエージェント)が大きな供給側(腕)と競合する二面的マッチング市場における分散学習を研究する。
提案アルゴリズムは,腕の数によらず,インスタンス依存の対数的後悔を実現する。
論文 参考訳（メタデータ） (2024-11-18T18:08:05Z) - Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。
課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。
我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-08-20T13:57:00Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - Decentralized Competing Bandits in Non-Stationary Matching Markets [46.13741000158631]
非定常(動的)環境下での分散化二面マッチング市場の枠組みを紹介する。
分散非定常競合帯域(textttDNCB)を用いた分散非同期学習アルゴリズムの提案と解析を行う。
我々はこの強調探索を特徴付け、texttDNCBのサブ線形(対数的)後悔を得る。
論文 参考訳（メタデータ） (2022-05-31T21:05:30Z) - 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) - Multitask Bandit Learning Through Heterogeneous Feedback Aggregation [35.923544685900055]
我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。
我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
論文 参考訳（メタデータ） (2020-10-29T07:13:28Z) - 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) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。