論文の概要: 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) はるかに制限された連続独裁設定において、すべての武器がエージェントに対して同じ好みを有する場合。
我々は,各フェーズにおいて,エージェントが頻繁に衝突する腕を局所的に除去する,グローバルに通信される支配的武器を除去するフェーズベースのアルゴリズムを提案する。
この局所的な削除は、腕間のエージェントのランクの不均一性から生じるデッドロックを壊す上で重要である。
さらにシミュレーションにより,既存の手法よりもアルゴリズムが優れていることを示す。
関連論文リスト
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
論文 参考訳（メタデータ） (2025-02-06T12:03:24Z) - p-Mean Regret for Stochastic Bandits [52.828710025519996]
単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。
我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
論文 参考訳（メタデータ） (2024-12-14T08:38:26Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。