論文の概要: Achieving Better Regret against Strategic Adversaries
- arxiv url: http://arxiv.org/abs/2302.06652v1
- Date: Mon, 13 Feb 2023 19:34:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-15 17:24:51.627667
- Title: Achieving Better Regret against Strategic Adversaries
- Title(参考訳): 戦略的敵に対するより良いレグレットを達成する
- Authors: Le Cong Dinh, Tri-Dung Nguyen, Alain Zemkoho and Long Tran-Thanh
- Abstract要約: 本研究では,学習者が相手の行動について余分な知識を持つオンライン学習問題について検討する。
我々は,正規化リーダ(AFTRL)とProd-Best Response(Prod-BR)の2つの新しいオンライン学習アルゴリズムを提案する。
AFTRLは、外部の後悔に対して$O(1)$、または$O(1)$、遠回りの後悔に対して$O(1)$を達成する。
- 参考スコア(独自算出の注目度): 15.51709428653595
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study online learning problems in which the learner has extra knowledge
about the adversary's behaviour, i.e., in game-theoretic settings where
opponents typically follow some no-external regret learning algorithms. Under
this assumption, we propose two new online learning algorithms, Accurate Follow
the Regularized Leader (AFTRL) and Prod-Best Response (Prod-BR), that
intensively exploit this extra knowledge while maintaining the no-regret
property in the worst-case scenario of having inaccurate extra information.
Specifically, AFTRL achieves $O(1)$ external regret or $O(1)$ \emph{forward
regret} against no-external regret adversary in comparison with $O(\sqrt{T})$
\emph{dynamic regret} of Prod-BR. To the best of our knowledge, our algorithm
is the first to consider forward regret that achieves $O(1)$ regret against
strategic adversaries. When playing zero-sum games with Accurate Multiplicative
Weights Update (AMWU), a special case of AFTRL, we achieve \emph{last round
convergence} to the Nash Equilibrium. We also provide numerical experiments to
further support our theoretical results. In particular, we demonstrate that our
methods achieve significantly better regret bounds and rate of last round
convergence, compared to the state of the art (e.g., Multiplicative Weights
Update (MWU) and its optimistic counterpart, OMWU).
- Abstract(参考訳): 我々は,学習者が相手の行動について余分な知識を持つオンライン学習問題,すなわち,対戦相手が通常,外部の後悔しない学習アルゴリズムに従うゲーム理論的な環境で研究する。
そこで,本研究では,不正確な情報を持つという最悪のシナリオにおいて,この知識を積極的に活用しつつ,不適切な特性を維持しながら,その知識を積極的に活用する,正則化リーダ(aftrl)とprod-br(prod-br)の2つのオンライン学習アルゴリズムを提案する。
特に aftrl は、prod-br の $o(\sqrt{t})$ \emph{dynamic regret} と比較して、外部の後悔のない敵に対して $o(1)$ または $o(1)$ \emph{forward regret} を達成する。
我々の知る限りでは、我々のアルゴリズムは、戦略的敵に対して$o(1)$ regretを達成する前進的後悔を最初に検討する。
AFTRL の特別な場合である精度乗算重み更新 (AMWU) でゼロサムゲームをするとき、ナッシュ平衡に \emph{last round convergence} を達成する。
また、理論的結果をさらに支援するための数値実験も実施する。
特に,本手法は,最先端技術(MWUやその楽観的手法であるOMWUなど)と比較して,残差や最終ラウンド収束率を著しく向上させることを示した。
関連論文リスト
- Is Learning in Games Good for the Learners? [14.781100349601587]
2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。
このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。
また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
論文 参考訳(メタデータ) (2023-05-31T02:10:27Z) - Best of Both Worlds Policy Optimization [33.13041034490332]
本稿では,正則化器,探索ボーナス,学習率を適切に設計することにより,損失が相反する場合には,より好意的なポリログ$(T)=後悔が得られることを示す。
政策最適化のために、ギャップ依存のポリログ$(T)$後悔境界が示されるのはこれが初めてである。
論文 参考訳(メタデータ) (2023-02-18T19:46:11Z) - Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
我々は、効率よく非結合な学習力学を確立し、各プレイヤーのトリガー後悔は、プレイの繰り返しの後に$O(log T)$として成長する。
これにより、これまでよく知られていた$O(T1/4)$よりも指数関数的に改善される。
論文 参考訳(メタデータ) (2022-08-20T20:48:58Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳(メタデータ) (2022-03-03T02:55:55Z) - Near-Optimal No-Regret Learning for Correlated Equilibria in
Multi-Player General-Sum Games [104.74734408204749]
マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。
外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
論文 参考訳(メタデータ) (2021-11-11T01:19:53Z) - Evolutionary Dynamics and $\Phi$-Regret Minimization in Games [38.00008966802513]
Regretはオンライン学習の基礎概念として確立されており、ゲームにおける学習力学の分析にも重要な応用がある。
本稿では,全エンフミックス戦略空間の分割に対する偏差の観点から,後悔に対する理解を再考する。
ここでは、複製子力学(RD)のよく研究された進化的学習アルゴリズムが、一般的な2倍の2ドルゲームにおいて、最強の$Phi$-regretの形式をシームレスに最小化することを証明している。
論文 参考訳(メタデータ) (2021-06-28T12:48:15Z) - 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 Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳(メタデータ) (2021-01-31T16:49:07Z) - Provable Self-Play Algorithms for Competitive Reinforcement Learning [48.12602400021397]
我々はマルコフゲームの設定の下で、競争力強化学習における自己プレイについて研究する。
自己再生アルゴリズムは、ゲームのT$ステップをプレイした後、後悔の$tildemathcalO(sqrtT)$を達成する。
また, 最悪の場合においても, 時間内に実行可能であることを保証し, 若干悪い後悔を招き, エクスプロイトスタイルのアルゴリズムも導入する。
論文 参考訳(メタデータ) (2020-02-10T18:44:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。