論文の概要: Matrix games with bandit feedback
- arxiv url: http://arxiv.org/abs/2006.05145v2
- Date: Sat, 12 Jun 2021 10:23:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-23 14:26:29.455404
- Title: Matrix games with bandit feedback
- Title（参考訳）: バンドフィードバックによるマトリックスゲーム
- Authors: Brendan O'Donoghue, Tor Lattimore, Ian Osband
- Abstract要約: 本研究では,古典的ゼロサム行列ゲームのバージョンを,未知のペイオフ行列と帯域幅フィードバックを用いて検討する。
我々は、トンプソンがこの設定で破滅的に失敗し、既存のアルゴリズムと経験的な比較を行うことを示した。
- 参考スコア（独自算出の注目度）: 33.637621576707076
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a version of the classical zero-sum matrix game with unknown payoff
matrix and bandit feedback, where the players only observe each others actions
and a noisy payoff. This generalizes the usual matrix game, where the payoff
matrix is known to the players. Despite numerous applications, this problem has
received relatively little attention. Although adversarial bandit algorithms
achieve low regret, they do not exploit the matrix structure and perform poorly
relative to the new algorithms. The main contributions are regret analyses of
variants of UCB and K-learning that hold for any opponent, e.g., even when the
opponent adversarially plays the best-response to the learner's mixed strategy.
Along the way, we show that Thompson fails catastrophically in this setting and
provide empirical comparison to existing algorithms.
- Abstract（参考訳）: 本研究では,従来のゼロサム行列ゲームのバージョンを未知のペイオフ行列と帯域フィードバックを用いて検討し,各プレイヤーが互いに行動を観察し,ノイズの多いペイオフを行う。
これは通常のマトリクスゲームを一般化し、そこではプレイヤーにペイオフマトリクスが知られている。
多くの応用にもかかわらず、この問題はあまり注目されていない。
反逆バンディットアルゴリズムは, 後悔度は低いが, 行列構造を活用せず, 新たなアルゴリズムとの相関性も低い。
主な貢献は、対戦相手が学習者の混合戦略に逆らって最善の反応をする場合でも、任意の対戦相手のために保持されるucbとk学習の変種について、後悔的な分析である。
その過程で、トンプソンはこの設定で壊滅的に失敗し、既存のアルゴリズムと実証的な比較を行う。
関連論文リスト
- Finite-Sample Guarantees for Best-Response Learning Dynamics in Zero-Sum Matrix Games [22.380293155135096]
2人のプレイヤーゼロサム行列ゲームに対する最適応答型学習ダイナミクスについて検討する。
我々は,各プレイヤーがゲームと相手の戦略について持っている情報の種類によって区別される2つの設定について検討する。
論文 参考訳（メタデータ） (2024-07-29T15:56:49Z) - No Algorithmic Collusion in Two-Player Blindfolded Game with Thompson Sampling [10.376707874029561]
プレイヤーがトンプソンサンプリングを使用すると、ゲームダイナミクスはペイオフ行列の軽度な仮定の下でナッシュ平衡に収束することを示す。
アルゴリズムによる共謀は 発生しない プレイヤーが意図的に 競争戦略を展開していないにもかかわらず
論文 参考訳（メタデータ） (2024-05-23T08:21:48Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳（メタデータ） (2022-01-30T06:10:04Z) - Balancing Adaptability and Non-exploitability in Repeated Games [29.04618208068207]
複数のクラスのうちの1つで、未知のメンバシップを持つ対戦相手に対して、繰り返しのゲームにおいて、低後悔を保証する問題について検討する。
我々は,我々のアルゴリズムが探索不可能であるという制約を加味し,対戦相手が「公正」な値を超える報酬を達成できないアルゴリズムを使用する動機を欠いていることを付け加える。
我々の解法は,各クラスに最適である一連のサブアルゴリズム内を探索し,相手による搾取の証拠を検出するための罰則を用いる専門家アルゴリズム (LAFF) である。
論文 参考訳（メタデータ） (2021-12-20T03:09:30Z) - Online Learning in Unknown Markov Games [55.07327246187741]
未知のマルコフゲームでオンライン学習を学ぶ。
後方視における最良の反応に対するサブ線形後悔の達成は統計的に困難であることを示す。
サブ線形$tildemathcalO(K2/3)$ regretを$K$のエピソード後に達成するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-28T14:52:15Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。