論文の概要: Beyond $\log^2(T)$ Regret for Decentralized Bandits in Matching Markets

• arxiv url: http://arxiv.org/abs/2103.07501v1
• Date: Fri, 12 Mar 2021 19:46:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-16 14:27:09.187547
• Title: Beyond $\log^2(T)$ Regret for Decentralized Bandits in Matching Markets
• Title（参考訳）: 一致する市場での分散バンディットに対する$\log^2(t)$の後悔
• Authors: Soumya Basu, Karthik Abinav Sankararaman, Abishek Sankararaman
• Abstract要約: 片面のバンディットフィードバックにより、両面マッチング市場における後悔のための分散アルゴリズムを設計します。 まず、一般的な市場では、任意の$varepsilon > 0$に対して、エージェント-最適安定マッチングに後悔する$O(log1+varepsilon(T))のアルゴリズムを設計する。 第二に、一意性の整合性を満たす市場に対して最適な$Theta(log(T))$エージェント最適後悔を提供する。
• 参考スコア（独自算出の注目度）: 11.219649988397222
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We design decentralized algorithms for regret minimization in the two-sided matching market with one-sided bandit feedback that significantly improves upon the prior works (Liu et al. 2020a, 2020b, Sankararaman et al. 2020). First, for general markets, for any $\varepsilon > 0$, we design an algorithm that achieves a $O(\log^{1+\varepsilon}(T))$ regret to the agent-optimal stable matching, with unknown time horizon $T$, improving upon the $O(\log^{2}(T))$ regret achieved in (Liu et al. 2020b). Second, we provide the optimal $\Theta(\log(T))$ agent-optimal regret for markets satisfying uniqueness consistency -- markets where leaving participants don't alter the original stable matching. Previously, $\Theta(\log(T))$ regret was achievable (Sankararaman et al. 2020, Liu et al. 2020b) in the much restricted serial dictatorship setting, when all arms have the same preference over the agents. We propose a phase-based algorithm, wherein each phase, besides deleting the globally communicated dominated arms the agents locally delete arms with which they collide often. This local deletion is pivotal in breaking deadlocks arising from rank heterogeneity of agents across arms. We further demonstrate the superiority of our algorithm over existing works through simulations.
• Abstract（参考訳）: 両サイドマッチング市場における後悔の最小化のための分散アルゴリズムを,前作(Liu et al.)において有意に改善した片側バンディットフィードバックを用いて設計した。 2020a, 2020b, Sankararaman et al。 2020). まず、一般市場では、任意の $\varepsilon > 0$ に対して、$O(\log^{1+\varepsilon}(T))$ をエージェント最適安定マッチングに後悔するアルゴリズムを設計し、未知の時空 $T$ で、$O(\log^{2}(T))$ で達成された後悔(Liu et al)に改善します。 2020年)。 第二に、参加者が元の安定したマッチングを変更しない市場 - ユニークさの一貫性を満たす市場のために最適な$\Theta(\log(T))$エージェント最適の後悔を提供します。 以前は$\Theta(\log(T))$ regretは達成できた(Sankararaman et al)。 2020年、Luら。 2020b) はるかに制限された連続独裁設定において、すべての武器がエージェントに対して同じ好みを有する場合。 我々は,各フェーズにおいて,エージェントが頻繁に衝突する腕を局所的に除去する,グローバルに通信される支配的武器を除去するフェーズベースのアルゴリズムを提案する。 この局所的な削除は、腕間のエージェントのランクの不均一性から生じるデッドロックを壊す上で重要である。 さらにシミュレーションにより,既存の手法よりもアルゴリズムが優れていることを示す。

関連論文リスト

• Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets [7.512199306943756]
  我々は、需要側(プレイヤー)が供給側(アーム)と競合する分散化された二面マッチング市場を研究する。 この問題に対して,エポック型CA-ETC (Collision avoidance explore then commit) (textttCA-ETC,略してtextttCA-ETC) という多相探索型アルゴリズムを提案する。 初期エポック長が$T_circ$で、その後のエポック長が$2l/gamma T_circ$の場合、textttCA-ETC がプレイヤーとなることを示す。
  論文  参考訳（メタデータ） (2024-08-16T12:06:09Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。 我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
  論文  参考訳（メタデータ） (2023-03-05T18:08:54Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。 分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
  論文  参考訳（メタデータ） (2021-07-30T15:25:13Z)
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition [49.78053380710322]
  我々は,エピソードT$でマルコフ決定過程を学習する上で,両世界の最良の問題を考える。 最近の[Jin and Luo, 2020]による研究は、固定遷移が分かっているときにこの目標を達成する。 本研究では,同じFollow-the-Regularized-Leader(textFTRL$)フレームワークを新しいテクニックのセットと組み合わせることで,この問題を解決する。
  論文  参考訳（メタデータ） (2021-06-08T05:46:35Z)
• Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits [12.462608802359936]
  Zimmert and Seldin (2021) の Tsallis-INF アルゴリズムに対する後悔の境界を改善した。 特に、$C = Thetaleft(fracTlog Tlog T$)$の場合、$T$が時空である場合、乗算因子による改善を達成します。 また, time horizon 上の後悔の依存性を $log t$ から $log frac(k-1)t(sum_ineq i*frac1delta_ に改善する。
  論文  参考訳（メタデータ） (2021-03-23T12:26:39Z)
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
  そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。 私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
  論文  参考訳（メタデータ） (2021-02-19T11:03:51Z)
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost [53.968049198926444]
  スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。 このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
  論文  参考訳（メタデータ） (2021-01-02T18:41:27Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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