論文の概要: Balancing Adaptability and Non-exploitability in Repeated Games
- arxiv url: http://arxiv.org/abs/2112.10314v1
- Date: Mon, 20 Dec 2021 03:09:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-21 17:30:16.470991
- Title: Balancing Adaptability and Non-exploitability in Repeated Games
- Title(参考訳): 繰り返しゲームにおける適応性と非探索性
- Authors: Anthony DiGiovanni and Ambuj Tewari
- Abstract要約: 複数のクラスのうちの1つで、未知のメンバシップを持つ対戦相手に対して、繰り返しのゲームにおいて、低後悔を保証する問題について検討する。
我々は,我々のアルゴリズムが探索不可能であるという制約を加味し,対戦相手が「公正」な値を超える報酬を達成できないアルゴリズムを使用する動機を欠いていることを付け加える。
我々の解法は,各クラスに最適である一連のサブアルゴリズム内を探索し,相手による搾取の証拠を検出するための罰則を用いる専門家アルゴリズム (LAFF) である。
- 参考スコア(独自算出の注目度): 29.04618208068207
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the problem of guaranteeing low regret in repeated games against an
opponent with unknown membership in one of several classes. We add the
constraint that our algorithm is non-exploitable, in that the opponent lacks an
incentive to use an algorithm against which we cannot achieve rewards exceeding
some "fair" value. Our solution is an expert algorithm (LAFF) that searches
within a set of sub-algorithms that are optimal for each opponent class and
uses a punishment policy upon detecting evidence of exploitation by the
opponent. With benchmarks that depend on the opponent class, we show that LAFF
has sublinear regret uniformly over the possible opponents, except exploitative
ones, for which we guarantee that the opponent has linear regret. To our
knowledge, this work is the first to provide guarantees for both regret and
non-exploitability in multi-agent learning.
- Abstract(参考訳): 複数のクラスのうちの1つで、未知のメンバシップを持つ対戦相手に対して、繰り返しゲームにおける低後悔を保証する問題について検討する。
我々は,我々のアルゴリズムが探索不可能であるという制約を加味し,対戦相手が「公正」な値を超える報酬を達成できないアルゴリズムを使用する動機を欠いている。
我々の解法は,各クラスに最適である一連のサブアルゴリズム内を探索し,相手による搾取の証拠を検出するために罰則を用いる専門家アルゴリズム (LAFF) である。
対立するクラスに依存したベンチマークでは、LAFFは、攻撃的クラスを除いて、可能な相手に対して一様にサブリニア後悔をしており、敵が線形後悔を保証していることを示す。
私たちの知る限り、この研究は、マルチエージェント学習における後悔と非発見性の両方の保証を提供する最初のものである。
関連論文リスト
- Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳(メタデータ) (2024-04-16T17:59:55Z) - Is Learning in Games Good for the Learners? [14.781100349601587]
2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。
このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。
また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
論文 参考訳(メタデータ) (2023-05-31T02:10:27Z) - Strategizing against Learners in Bayesian Games [74.46970859427907]
プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。
一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
論文 参考訳(メタデータ) (2022-05-17T18:10:25Z) - Learning Markov Games with Adversarial Opponents: Efficient Algorithms
and Fundamental Limits [37.573273877814906]
ゼロサムゲームにおける理想的な戦略は、プレイヤーにナッシュ均衡の値に劣らず平均的な報酬を与えるだけでなく、最適でないとき(適応的な)相手を利用することである。
本研究は, マルコフゲームにおいて, 対戦相手が後見の最良の固定政策と競合する際の非回帰学習について研究する。
論文 参考訳(メタデータ) (2022-03-14T01:23:56Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳(メタデータ) (2022-01-30T06:10:04Z) - L2E: Learning to Exploit Your Opponent [66.66334543946672]
本稿では,暗黙的対向モデリングのための新しい学習フレームワークを提案する。
L2Eは、トレーニング中に異なる相手との対話によって、相手を悪用する能力を取得する。
本稿では, 対戦相手を自動的に生成する新しい対戦相手戦略生成アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-18T14:27:59Z) - Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。
対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。
我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
論文 参考訳(メタデータ) (2020-07-10T09:33:05Z) - Matrix games with bandit feedback [33.637621576707076]
本研究では,古典的ゼロサム行列ゲームのバージョンを,未知のペイオフ行列と帯域幅フィードバックを用いて検討する。
我々は、トンプソンがこの設定で破滅的に失敗し、既存のアルゴリズムと経験的な比較を行うことを示した。
論文 参考訳(メタデータ) (2020-06-09T09:36:21Z) - Provable Self-Play Algorithms for Competitive Reinforcement Learning [48.12602400021397]
我々はマルコフゲームの設定の下で、競争力強化学習における自己プレイについて研究する。
自己再生アルゴリズムは、ゲームのT$ステップをプレイした後、後悔の$tildemathcalO(sqrtT)$を達成する。
また, 最悪の場合においても, 時間内に実行可能であることを保証し, 若干悪い後悔を招き, エクスプロイトスタイルのアルゴリズムも導入する。
論文 参考訳(メタデータ) (2020-02-10T18:44:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。