論文の概要: Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2505.13562v1
• Date: Mon, 19 May 2025 10:05:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-21 14:49:52.443521
• Title: Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback
• Title（参考訳）: 帯域フィードバックを持つ行列ゲームに対する競合共進化によるランダム化された最適化
• Authors: Shishen Lin,
• Abstract要約: 本研究では,未知のペイオフ行列と帯域フィードバックを持つ2プレイヤーゼロサム行列ゲームについて検討する。 本稿では,進化的アルゴリズムをバンディットフレームワークに統合する新しいアルゴリズムであるコンペティティブ共進化帯域学習(coebl)を提案する。 決定論的楽観主義に基づく手法の性能と一致して,coeblがサブ線形後悔を実現することを証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning in games is a fundamental problem in machine learning and artificial intelligence, with numerous applications~\citep{silver2016mastering,schrittwieser2020mastering}. This work investigates two-player zero-sum matrix games with an unknown payoff matrix and bandit feedback, where each player observes their actions and the corresponding noisy payoff. Prior studies have proposed algorithms for this setting~\citep{o2021matrix,maiti2023query,cai2024uncoupled}, with \citet{o2021matrix} demonstrating the effectiveness of deterministic optimism (e.g., \ucb) in achieving sublinear regret. However, the potential of randomised optimism in matrix games remains theoretically unexplored. We propose Competitive Co-evolutionary Bandit Learning (\coebl), a novel algorithm that integrates evolutionary algorithms (EAs) into the bandit framework to implement randomised optimism through EA variation operators. We prove that \coebl achieves sublinear regret, matching the performance of deterministic optimism-based methods. To the best of our knowledge, this is the first theoretical regret analysis of an evolutionary bandit learning algorithm in matrix games. Empirical evaluations on diverse matrix game benchmarks demonstrate that \coebl not only achieves sublinear regret but also consistently outperforms classical bandit algorithms, including \exptr~\citep{auer2002nonstochastic}, the variant \exptrni~\citep{cai2024uncoupled}, and \ucb~\citep{o2021matrix}. These results highlight the potential of evolutionary bandit learning, particularly the efficacy of randomised optimism via evolutionary algorithms in game-theoretic settings.
• Abstract（参考訳）: ゲームにおける学習は、機械学習と人工知能の基本的な問題であり、多くの応用 --\citep{silver2016mastering,schrittwieser2020mastering} がある。 本研究では、未知のペイオフ行列と帯域フィードバックを持つ2つのプレイヤーゼロサム行列ゲームについて検討し、各プレイヤーがそれぞれの動作とそれに対応するノイズのペイオフを観測する。 以前の研究では、決定論的楽観主義(eg, \ucb)の有効性を実証するアルゴリズムが提案されている。 しかし、行列ゲームにおけるランダム化された楽観主義のポテンシャルは理論的には未解明のままである。 我々は,進化的アルゴリズム(EA)をバンディットフレームワークに統合し,EA変動演算子によるランダムな最適化を実現する新しいアルゴリズムであるCompetitive Co-evolutionary Bandit Learning (\coebl)を提案する。 我々は, 決定論的楽観主義に基づく手法の性能と一致して, サブ線形後悔を実現することを証明した。 我々の知る限りでは、これは行列ゲームにおける進化的バンディット学習アルゴリズムに関する最初の理論的後悔の分析である。 多様な行列ゲームベンチマークに関する実証的な評価は、'coebl'はサブ線形後悔を達成できるだけでなく、'exptr~\citep{auer2002nonstochastic}, variant \exptrni~\citep{cai2024uncoupled}, \ucb~\citep{o2021matrix} などの古典的バンディットアルゴリズムを一貫して上回ることを示した。 これらの結果は、進化的バンディット学習の可能性、特にゲーム理論における進化的アルゴリズムによるランダム化された楽観主義の有効性を浮き彫りにする。

関連論文リスト

• Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
  両プレイヤー間のペイオフベース、収束、合理的、対称な学習ダイナミクスを開発する。 行列ゲーム設定では、結果はナッシュ分布を見つけるために$O(epsilon-1)$の複雑さを意味する。 ゲーム設定では、結果はナッシュ平衡を求めるために$O(epsilon-8)$の複雑さをも意味している。
  論文  参考訳（メタデータ） (2024-09-02T20:07:25Z)
• Alternating Mirror Descent for Constrained Min-Max Games [44.46086335474311]
  制約付き戦略空間を持つ2プレイヤー双線形ゼロサムゲームについて検討する。 我々は,各プレイヤーが交互に行動する交互ミラー降下アルゴリズムを,制約付き最適化のためのミラー降下アルゴリズムに従って解析する。
  論文  参考訳（メタデータ） (2022-06-08T20:48:16Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  ゲームにおける学習の長期的挙動(連続的・有限的)を解析するためのフレキシブルな近似フレームワークを開発する。 提案する分析テンプレートには,勾配に基づく手法,有限ゲームでの学習のための指数的/乗算的重み付け,楽観的および帯域的変異など,幅広い一般的な学習アルゴリズムが組み込まれている。
  論文  参考訳（メタデータ） (2022-06-08T14:30:38Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  そこで我々は,適応的かつ音質の高い"核フロベニウスノルム"と呼ばれる新しい非スケーラブルな低ランク正規化器を提案する。 特異値の計算をバイパスし、アルゴリズムによる高速な最適化を可能にする。 既存の行列学習手法では最速でありながら、最先端の回復性能が得られる。
  論文  参考訳（メタデータ） (2020-08-14T18:47:58Z)
• Matrix games with bandit feedback [33.637621576707076]
  本研究では,古典的ゼロサム行列ゲームのバージョンを,未知のペイオフ行列と帯域幅フィードバックを用いて検討する。 我々は、トンプソンがこの設定で破滅的に失敗し、既存のアルゴリズムと経験的な比較を行うことを示した。
  論文  参考訳（メタデータ） (2020-06-09T09:36:21Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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