論文の概要: Exploiting No-Regret Algorithms in System Design
- arxiv url: http://arxiv.org/abs/2007.11172v2
- Date: Fri, 24 Jul 2020 10:05:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-07 23:15:54.920239
- Title: Exploiting No-Regret Algorithms in System Design
- Title（参考訳）: システム設計におけるNo-Regretアルゴリズムの展開
- Authors: Le Cong Dinh and Nick Bishop and Long Tran-Thanh
- Abstract要約: カラムプレーヤがシステムのデザイナでもある2人プレイヤゼロサムゲーム設定について検討する。
カラムプレーヤの目標は、システムデザイナが好む混合戦略を選択するように、相手を誘導することである。
本稿では,システムデザイナのための新しいゲームプレイアルゴリズムを提案し,行プレーヤがミニマックスソリューションに収束するように誘導できることを証明する。
- 参考スコア（独自算出の注目度）: 20.189783788006263
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate a repeated two-player zero-sum game setting where the column
player is also a designer of the system, and has full control on the design of
the payoff matrix. In addition, the row player uses a no-regret algorithm to
efficiently learn how to adapt their strategy to the column player's behaviour
over time in order to achieve good total payoff. The goal of the column player
is to guide her opponent to pick a mixed strategy which is favourable for the
system designer. Therefore, she needs to: (i) design an appropriate payoff
matrix $A$ whose unique minimax solution contains the desired mixed strategy of
the row player; and (ii) strategically interact with the row player during a
sequence of plays in order to guide her opponent to converge to that desired
behaviour. To design such a payoff matrix, we propose a novel solution that
provably has a unique minimax solution with the desired behaviour. We also
investigate a relaxation of this problem where uniqueness is not required, but
all the minimax solutions have the same mixed strategy for the row player.
Finally, we propose a new game playing algorithm for the system designer and
prove that it can guide the row player, who may play a \emph{stable} no-regret
algorithm, to converge to a minimax solution.
- Abstract（参考訳）: 本研究では,コラムプレーヤがシステムの設計者でもある2人プレイのゼロサムゲームの設定を繰り返し検討し,ペイオフ行列の設計を完全に制御する。
さらに、row playerはno-regretアルゴリズムを使用して、その戦略をコラムプレイヤーの振る舞いに効率的に適応する方法を学習し、十分な総報酬を得る。
コラムプレイヤーの目標は、システムデザイナーに好まれる混合戦略を選択するために対戦相手を導くことである。
したがって、彼女はこうする必要がある。
i) 行プレーヤの所望の混合戦略を含む独自のミニマックスソリューションを含む適切なペイオフ行列$A$を設計すること。
(ii) プレイの連続中に行プレーヤと戦略的に相互作用し、相手にその望ましい行動に収束させるよう誘導する。
このようなペイオフ行列を設計するために,所望の振る舞いを持つ一意のミニマックス解を確実に持つ新しい解を提案する。
また、一意性が不要な問題の緩和についても検討するが、すべてのminimaxソリューションは行プレーヤに対して同じ混合戦略を持つ。
最後に,システム設計者のための新たなゲームプレイアルゴリズムを提案し, \emph{stable} no-regretアルゴリズムをプレイ可能な行プレーヤをミニマックス解に収束させることを証明した。
関連論文リスト
- Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret [10.700891331004799]
本稿では,非損失関数を用いた分散オンライン帯域最適化問題について検討する。
プレイヤーは敵を選択し、そのプレイヤーに任意の非線形損失関数を割り当てる。
予想されるアルゴリズムの後悔は、2点偏差を用いた既存のアルゴリズムに匹敵する。
論文 参考訳（メタデータ） (2024-09-24T02:37:33Z) - Learning to Control Unknown Strongly Monotone Games [16.327788209492805]
制御された係数をオンラインで調整し,線形制約を満たすためにゲームのNEをシフトする簡単なアルゴリズムを提案する。
我々は,2つの時間スケール近似に基づくアルゴリズムが,目的とする線形制約を満たすNEの集合に対する確率1との収束を保証することを証明した。
本稿では,NEにおけるグローバル2次コストの最適化と資源配分ゲームにおけるロードバランシングに,我々の手法を適用する方法を示す。
論文 参考訳（メタデータ） (2024-06-30T03:33:42Z) - Logarithmic Regret for Matrix Games against an Adversary with Noisy
Bandit Feedback [23.97611639885236]
本稿では,行プレーヤが行$i$を選択し,列プレーヤが列$j$を選択し,行プレーヤが平均$A_i,j$でノイズの多い報酬を受け取るゼロサム行列ゲームの変形について考察する。
行プレーヤの目的は、敵列プレーヤに対してもできるだけ多くの報酬を蓄積することである。
もし行プレーヤが、任意の報酬列に対して$sqrtT$ regretを得るアルゴリズムであるEXP3戦略を使用するなら、行プレーヤも$sqrtTを達成できるのは即時である。
論文 参考訳（メタデータ） (2023-06-22T22:45:48Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳（メタデータ） (2022-01-30T06:10:04Z) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳（メタデータ） (2021-07-30T15:25:13Z) - Almost Optimal Algorithms for Two-player Markov Games with Linear
Function Approximation [92.99933928528797]
同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。
我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。
我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
論文 参考訳（メタデータ） (2021-02-15T09:09:16Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。