論文の概要: Is Learning in Games Good for the Learners?

• arxiv url: http://arxiv.org/abs/2305.19496v1
• Date: Wed, 31 May 2023 02:10:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-01 18:58:24.020126
• Title: Is Learning in Games Good for the Learners?
• Title（参考訳）: ゲームにおける学習は学習者に良いか?
• Authors: William Brown, Jon Schneider, Kiran Vodrahalli
• Abstract要約: 2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。 このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
• 参考スコア（独自算出の注目度）: 14.095924542242777
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a number of questions related to tradeoffs between reward and regret in repeated gameplay between two agents. To facilitate this, we introduce a notion of {\it generalized equilibrium} which allows for asymmetric regret constraints, and yields polytopes of feasible values for each agent and pair of regret constraints, where we show that any such equilibrium is reachable by a pair of algorithms which maintain their regret guarantees against arbitrary opponents. As a central example, we highlight the case one agent is no-swap and the other's regret is unconstrained. We show that this captures an extension of {\it Stackelberg} equilibria with a matching optimal value, and that there exists a wide class of games where a player can significantly increase their utility by deviating from a no-swap-regret algorithm against a no-swap learner (in fact, almost any game without pure Nash equilibria is of this form). Additionally, we make use of generalized equilibria to consider tradeoffs in terms of the opponent's algorithm choice. We give a tight characterization for the maximal reward obtainable against {\it some} no-regret learner, yet we also show a class of games in which this is bounded away from the value obtainable against the class of common ``mean-based'' no-regret algorithms. Finally, we consider the question of learning reward-optimal strategies via repeated play with a no-regret agent when the game is initially unknown. Again we show tradeoffs depending on the opponent's learning algorithm: the Stackelberg strategy is learnable in exponential time with any no-regret agent (and in polynomial time with any no-{\it adaptive}-regret agent) for any game where it is learnable via queries, and there are games where it is learnable in polynomial time against any no-swap-regret agent but requires exponential time against a mean-based no-regret agent.
• Abstract（参考訳）: 2つのエージェント間の繰り返しゲームプレイにおける報酬と後悔のトレードオフに関する多くの質問について考察した。 これを容易にするために、非対称な後悔の制約を許容し、各エージェントと一対の後悔の制約に対して実現可能な値のポリトープを出力する {\it Generalized equilibriumの概念を導入し、そのような平衡が任意の反対者に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。 中心となる例として、あるエージェントがno-swapであり、もう一方のエージェントの後悔が制約されていない場合を挙げる。 このことは,最適値が一致するような<it Stackelberg}平衡の拡張を捕捉し,非スワップ学習者に対して非スワップ回帰アルゴリズムから逸脱することで,プレイヤーが有効性を著しく向上できるゲームが広い範囲に存在することを示している(実際,純粋なナッシュ平衡のないゲームはこの形式である)。 さらに,対戦相手のアルゴリズム選択の観点からのトレードオフを考えるために,一般化された平衡を用いる。 我々は,学習者に対して得られる最大報酬を厳密に評価するが,これは共通な<mean-based''のno-regretアルゴリズムのクラスに対して得られる値から切り離されたゲームのクラスを示す。 最後に,ゲーム開始当初不明のエージェントによる繰り返しプレイによる報酬最適戦略の学習について考察する。 また、相手の学習アルゴリズムによるトレードオフを示す: stackelberg戦略は、クエリによって学習可能な任意のゲームに対して、任意の非regretエージェント(および任意の非{\it adaptive}-regretエージェントの多項式時間)で指数時間で学習でき、任意の非swap-regretエージェントに対して多項式時間で学習できるゲームがあるが、平均ベースのno-regretエージェントに対して指数時間を必要とする。

関連論文リスト

• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  非定常マルチエージェントシステムにおける平衡の学習について検討する。 単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
  論文  参考訳（メタデータ） (2023-06-12T23:48:24Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。 我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。 先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
  論文  参考訳（メタデータ） (2022-06-17T12:58:58Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。 一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
  論文  参考訳（メタデータ） (2022-05-17T18:10:25Z)
• Balancing Adaptability and Non-exploitability in Repeated Games [29.04618208068207]
  複数のクラスのうちの1つで、未知のメンバシップを持つ対戦相手に対して、繰り返しのゲームにおいて、低後悔を保証する問題について検討する。 我々は,我々のアルゴリズムが探索不可能であるという制約を加味し,対戦相手が「公正」な値を超える報酬を達成できないアルゴリズムを使用する動機を欠いていることを付け加える。 我々の解法は,各クラスに最適である一連のサブアルゴリズム内を探索し,相手による搾取の証拠を検出するための罰則を用いる専門家アルゴリズム (LAFF) である。
  論文  参考訳（メタデータ） (2021-12-20T03:09:30Z)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• Near-Optimal No-Regret Learning in General Games [31.293412884145066]
  マルチプレイヤー汎用ゲームにおいて,Optimistic Hedge が $rm poly(log T)$ regret を達成することを示す。 我々の境界の系は、最適化的ヘッジが一般ゲームにおいて$tildeOleft(frac 1Tright)$の速度で粗相関平衡に収束するということである。
  論文  参考訳（メタデータ） (2021-08-16T06:53:02Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• 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)

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

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