論文の概要: Dueling Bandits with Team Comparisons
- arxiv url: http://arxiv.org/abs/2107.02738v1
- Date: Tue, 6 Jul 2021 17:12:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-07 13:53:26.275436
- Title: Dueling Bandits with Team Comparisons
- Title（参考訳）: チーム比較によるダイアリングバンド
- Authors: Lee Cohen, Ulrike Schmidt-Kraepelin, Yishay Mansour
- Abstract要約: そこで本研究では,学習者が400ドル規模のチーム同士の相容れない比較を,nドルのプレーヤーの宇宙から観察する,新たなオンライン学習環境であるデュエルチーム問題を紹介する。
学習者の目標は、高い確率で、コンドルセットの勝利チームを特定するのに必要なデュエルの数を最小限にすることである。
本稿では,$mathcalO(n + k log (k)) fracmax(loglog n, log k)Delta2内のコンドルチェット優勝チームを特定するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 42.72668864241492
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the dueling teams problem, a new online-learning setting in
which the learner observes noisy comparisons of disjoint pairs of $k$-sized
teams from a universe of $n$ players. The goal of the learner is to minimize
the number of duels required to identify, with high probability, a Condorcet
winning team, i.e., a team which wins against any other disjoint team (with
probability at least $1/2$). Noisy comparisons are linked to a total order on
the teams. We formalize our model by building upon the dueling bandits setting
(Yue et al.2012) and provide several algorithms, both for stochastic and
deterministic settings. For the stochastic setting, we provide a reduction to
the classical dueling bandits setting, yielding an algorithm that identifies a
Condorcet winning team within $\mathcal{O}((n + k \log (k)) \frac{\max(\log\log
n, \log k)}{\Delta^2})$ duels, where $\Delta$ is a gap parameter. For
deterministic feedback, we additionally present a gap-independent algorithm
that identifies a Condorcet winning team within $\mathcal{O}(nk\log(k)+k^5)$
duels.
- Abstract（参考訳）: これは、学習者がn$プレーヤーの宇宙から、k$サイズのチーム同士の無関係なペアのノイズの多い比較を観察する、新しいオンライン学習環境です。
学習者のゴールは、高い確率でコンドルセトの勝利チーム、すなわち他のどのチームにも勝利するチーム、すなわち少なくとも1/2$の確率で)を特定するために必要なデュエルの数を最小化することである。
ノイズの多い比較は、チームの総順序と関連付けられます。
我々は,デュエルバンド設定(Yue et al.2012)に基づいてモデルを定式化し,確率的および決定論的両方の設定にいくつかのアルゴリズムを提供する。
確率的な設定では、古典的なデュエルバンドの設定を減らし、$\mathcal{O}((n + k \log (k)) \frac{\max(\log\log n, \log k)}{\Delta^2})$ duels($\Delta$はギャップパラメータ)内のコンドルチェット勝利チームを特定するアルゴリズムを与える。
決定論的フィードバックに対しては,$\mathcal{O}(nk\log(k)+k^5)$ duels内でのコンドルチェット勝利チームを識別するギャップ独立アルゴリズムを提案する。
関連論文リスト
- Adversarial Multi-dueling Bandits [0.4467766778351321]
対戦型多段バンディットにおける後悔の問題について紹介する。
このような嗜好フィードバックから学習するための新しいアルゴリズム MiDEX (Multi Dueling EXP3) を導入する。
論文 参考訳（メタデータ） (2024-06-18T10:28:12Z) - Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Competing Bandits in Time Varying Matching Markets [1.1470070927586014]
両面の非定常マッチング市場におけるオンライン学習の課題について検討し,安定したマッチングに収束することが目的である。
非定常性を扱うための単純な再起動戦略を組み合わせたRCB(Restart Competing Bandits)アルゴリズムを提案する。
提案アルゴリズムにより,各プレイヤーは,エージェントの嗜好の変動数に対して,$widetildemathcalO(L1/2_TT1/2)$の均一なサブ線形後悔を受けることを示す。
論文 参考訳（メタデータ） (2022-10-21T02:36:57Z) - An Asymptotically Optimal Batched Algorithm for the Dueling Bandit
Problem [13.69077222007053]
従来のマルチアームバンディット問題(英語版)のバリエーションである$K$のデュエルリングバンディット問題(英語版)について検討し、フィードバックをペア比較の形で得られる。
我々は、$O(K2log(K)) + O(Klog(T))$ in $O(log(T))$ rounds を後悔する。
実世界の様々なデータセットに対する計算実験において、$O(log(T))$ラウンドを用いたアルゴリズムが完全に同じ性能を達成することが観察された。
論文 参考訳（メタデータ） (2022-09-25T00:23:55Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Almost Optimal Algorithms for Two-player Markov Games with Linear
Function Approximation [92.99933928528797]
同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。
我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。
我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
論文 参考訳（メタデータ） (2021-02-15T09:09:16Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。