論文の概要: Learning to Identify Top Elo Ratings: A Dueling Bandits Approach
- arxiv url: http://arxiv.org/abs/2201.04480v1
- Date: Wed, 12 Jan 2022 13:57:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-13 17:15:02.975685
- Title: Learning to Identify Top Elo Ratings: A Dueling Bandits Approach
- Title(参考訳): トップエロ評価を識別する学習--デュエルバンドのアプローチ
- Authors: Xue Yan, Yali Du, Binxin Ru, Jun Wang, Haifeng Zhang, Xu Chen
- Abstract要約: 我々は,Elo評価(トッププレイヤー)のサンプル効率を改善するために,効率的なオンラインマッチングスケジューリングアルゴリズムを提案する。
具体的には、上位プレイヤーをデュエルバンドフレームワークで識別し、Eloの勾配ベースの更新に合わせてバンディットアルゴリズムを調整する。
我々のアルゴリズムは、競合ラウンドの数で$tildeO(sqrtT)$, sublinearを保証しており、多次元エロ評価にまで拡張されている。
- 参考スコア(独自算出の注目度): 27.495132915328025
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Elo rating system is widely adopted to evaluate the skills of (chess)
game and sports players. Recently it has been also integrated into machine
learning algorithms in evaluating the performance of computerised AI agents.
However, an accurate estimation of the Elo rating (for the top players) often
requires many rounds of competitions, which can be expensive to carry out. In
this paper, to improve the sample efficiency of the Elo evaluation (for top
players), we propose an efficient online match scheduling algorithm.
Specifically, we identify and match the top players through a dueling bandits
framework and tailor the bandit algorithm to the gradient-based update of Elo.
We show that it reduces the per-step memory and time complexity to constant,
compared to the traditional likelihood maximization approaches requiring $O(t)$
time. Our algorithm has a regret guarantee of $\tilde{O}(\sqrt{T})$, sublinear
in the number of competition rounds and has been extended to the
multidimensional Elo ratings for handling intransitive games. We empirically
demonstrate that our method achieves superior convergence speed and time
efficiency on a variety of gaming tasks.
- Abstract(参考訳): elo評価システムは、(チェス)ゲームやスポーツ選手のスキルを評価するために広く採用されている。
近年,コンピュータ化されたAIエージェントの性能評価において,機械学習アルゴリズムにも組み込まれている。
しかしながら、(トッププレイヤーの)エロ格付けの正確な評価は、しばしば多くの競技会を必要とするが、実行にはコストがかかる。
本稿では,トッププレイヤーを対象としたElo評価のサンプル効率を改善するために,効率的なオンラインマッチングスケジューリングアルゴリズムを提案する。
具体的には、上位プレイヤーをデュエル・バンディット・フレームワークを通じて識別・マッチングし、そのバンディット・アルゴリズムを勾配に基づくeloのアップデートに合わせる。
ステップ毎のメモリ容量と時間複雑性を一定に削減できることを,従来の最大化アプローチである$o(t)$ timeと比較した。
我々のアルゴリズムは、競合ラウンドの数で$\tilde{O}(\sqrt{T})$, sublinearという後悔の保証を持ち、非推移ゲームを扱うための多次元エロ評価にまで拡張されている。
本手法は,様々なゲーミングタスクにおいて,コンバージェンス速度と時間効率に優れることを示す。
関連論文リスト
- Policy Optimization for Markov Games: Unified Framework and Faster
Convergence [81.3266426402464]
このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。
このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
論文 参考訳(メタデータ) (2022-06-06T14:23:13Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳(メタデータ) (2022-01-30T06:10:04Z) - Evaluating Team Skill Aggregation in Online Competitive Games [4.168733556014873]
本稿では,2つの新しい集計手法が評価システムの予測性能に与える影響について分析する。
以上の結果から,テストケースの大部分において,MAX法が他の2手法よりも優れていることが示された。
本研究の結果は,チームのパフォーマンスを計算するために,より精巧な手法を考案する必要性を浮き彫りにした。
論文 参考訳(メタデータ) (2021-06-21T20:17:36Z) - Simplified Kalman filter for online rating: one-fits-all approach [4.010371060637208]
私たちは、選手/チームのスキルがゲームの観察された結果から推測されるスポーツのレーティングの問題に対処します。
本研究は,ゲーム結果とスキルの関係の確率的モデルを利用して,新たなゲーム後のスキルを推定するオンライン評価アルゴリズムに着目した。
論文 参考訳(メタデータ) (2021-04-28T20:44:10Z) - Elo Ratings for Large Tournaments of Software Agents in Asymmetric Games [0.0]
alphago zeroによる5185のレーティングのような、人間と同じeloスケールの人工知能エージェントを評価するのは自然である。
人間とAIの間には、システムの変更を提案する基本的な違いがいくつかある。
本稿では,これらの違いを反映したリフレッシュレーティングシステムとトーナメントのガイドラインを提案する。
論文 参考訳(メタデータ) (2021-04-23T21:49:20Z) - ELO System for Skat and Other Games of Chance [1.3706331473063877]
ELOランキングシステムは、ゼロサムゲームにおけるプレイヤーの相対スキルレベルを計算する信頼できる方法であることが証明されています。
しかし、skatやbridgeのようなトリックテイクカードゲームにおけるプレイヤーの強さの評価は明らかではない。
これらの弱点を克服するための新しいELOシステムを提案します。
論文 参考訳(メタデータ) (2021-04-07T08:30:01Z) - An Elo-like System for Massive Multiplayer Competitions [1.8782750537161612]
参加者数の多いコンテストを対象とした新しいベイズ評価システムを提案する。
それは離散的なランク付けされたマッチの競争のフォーマットに広く適当です。
システムにはインセンティブが整い、すなわち、格付けを最大化しようとするプレイヤーは、決してパフォーマンスを損なうことはない。
論文 参考訳(メタデータ) (2021-01-02T08:14:31Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。
この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。
各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-09-21T17:51:57Z) - Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。
対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。
我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
論文 参考訳(メタデータ) (2020-07-10T09:33:05Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳(メタデータ) (2020-02-17T17:04:16Z) - Provable Self-Play Algorithms for Competitive Reinforcement Learning [48.12602400021397]
我々はマルコフゲームの設定の下で、競争力強化学習における自己プレイについて研究する。
自己再生アルゴリズムは、ゲームのT$ステップをプレイした後、後悔の$tildemathcalO(sqrtT)$を達成する。
また, 最悪の場合においても, 時間内に実行可能であることを保証し, 若干悪い後悔を招き, エクスプロイトスタイルのアルゴリズムも導入する。
論文 参考訳(メタデータ) (2020-02-10T18:44:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。