論文の概要: Playing against no-regret players

• arxiv url: http://arxiv.org/abs/2202.09364v1
• Date: Wed, 16 Feb 2022 10:12:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-27 17:41:36.558326
• Title: Playing against no-regret players
• Title（参考訳）: レスリートプレーヤーと対戦する
• Authors: Maurizio D 'Andrea (ANITI, TSE)
• Abstract要約: n-プレイヤゲームにおけるスタックルバーグ均衡の概念を考える。 最初の結果から,ゲームが複数のプレイヤーと向き合わなければならない場合,この結果がもはや真実ではないことを示す。 我々は,少なくとも1ラウンドあたりのStackelberg値の相関を保証できることを証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In increasingly different contexts, it happens that a human player has to interact with artificial players who make decisions following decision-making algorithms. How should the human player play against these algorithms to maximize his utility? Does anything change if he faces one or more artificial players? The main goal of the paper is to answer these two questions. Consider n-player games in normal form repeated over time, where we call the human player optimizer, and the (n -- 1) artificial players, learners. We assume that learners play no-regret algorithms, a class of algorithms widely used in online learning and decision-making. In these games, we consider the concept of Stackelberg equilibrium. In a recent paper, Deng, Schneider, and Sivan have shown that in a 2-player game the optimizer can always guarantee an expected cumulative utility of at least the Stackelberg value per round. In our first result, we show, with counterexamples, that this result is no longer true if the optimizer has to face more than one player. Therefore, we generalize the definition of Stackelberg equilibrium introducing the concept of correlated Stackelberg equilibrium. Finally, in the main result, we prove that the optimizer can guarantee at least the correlated Stackelberg value per round. Moreover, using a version of the strong law of large numbers, we show that our result is also true almost surely for the optimizer utility instead of the optimizer's expected utility.
• Abstract（参考訳）: 異なる状況下では、人間プレイヤーは意思決定アルゴリズムに従って意思決定を行う人工プレイヤーと対話しなければならない。 人間のプレイヤーは、このアルゴリズムを最大限に活用するにはどうすればよいのか? 1人以上の人工プレイヤーと向き合えば、何か変わりますか? 論文の主な目的は、この2つの質問に答えることである。 人間のプレイヤーオプティマイザ (human player optimizer) と (n -- 1) 人工プレイヤー (artificial players)、学習者 (learningers) と呼ぶ、通常の形式のnプレイヤーゲームが繰り返し繰り返される。 学習者は、オンライン学習や意思決定で広く使われているアルゴリズムのクラスであるノンレグレットアルゴリズムをプレイすると仮定する。 これらのゲームでは、スタックルバーグ均衡の概念を考える。 最近の論文で、deng、schneider、sivanは、2人のプレイヤーゲームにおいて、オプティマイザは、少なくとも1ラウンド当たりのstackelberg値の期待累積効能を常に保証できることを示した。 最初の結果から,オプティマイザが複数のプレイヤーと向き合わなければならない場合,この結果はもはや真実ではないことを示す。 したがって、相関したスタックルバーグ均衡の概念を導入したスタックルバーグ均衡の定義を一般化する。 最後に,主結果として,オプティマイザが少なくとも1ラウンド当たりの相関付きstackelberg値を保証することを証明した。 さらに,大数の強法則のバージョンを用いて,オプティマイザの期待するユーティリティではなく,オプティマイザユーティリティについてもほぼ確実に結果が成り立つことを示す。

関連論文リスト

• Is Learning in Games Good for the Learners? [14.781100349601587]
  2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。 このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
  論文  参考訳（メタデータ） (2023-05-31T02:10:27Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。 一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
  論文  参考訳（メタデータ） (2022-05-17T18:10:25Z)
• Robust No-Regret Learning in Min-Max Stackelberg Games [1.6500749121196987]
  本研究は,Min-maxゲームにおける非regret学習の挙動について考察する。 非回帰力学がスタックルバーグ平衡に収束することを示す。 OMD のダイナミクスは,オンライン min-max Stackelberg ゲームの大規模なクラスでは堅牢であることを示す。
  論文  参考訳（メタデータ） (2022-03-26T18:12:40Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  対戦チームゲームは、プレイ中にチームメンバーが利用可能な非対称情報の中にあります。 本アルゴリズムは,対戦相手を持つ逐次チームゲームから古典的な2プレイヤーゼロサムゲームに変換する。 この問題のNPハード性のため、結果のパブリックチームゲームは元のゲームよりも指数関数的に大きいかもしれない。
  論文  参考訳（メタデータ） (2022-01-25T15:07:12Z)
• Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers? [156.5760265539888]
  我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーに指名されたプレイヤーとフォロワーに指名されたプレイヤーの1人を用いて研究した。 そのようなゲームに対して、我々のゴールは、政策対 $(pi*, nu*)$ であるスタックルバーグ・ナッシュ均衡 (SNE) を見つけることである。 オンラインとオフラインの両方でSNEを解くために,サンプル効率強化学習(RL)アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-27T05:41:14Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)
• 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)

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

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