論文の概要: Optimal No-Regret Learning in Strongly Monotone Games with Bandit
Feedback
- arxiv url: http://arxiv.org/abs/2112.02856v2
- Date: Wed, 8 Dec 2021 02:06:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-09 10:21:25.071410
- Title: Optimal No-Regret Learning in Strongly Monotone Games with Bandit
Feedback
- Title(参考訳): バンドフィードバックを持つ強いモノトーンゲームにおける最適非線形学習
- Authors: Tianyi Lin, Zhengyuan Zhou, Wenjia Ba, Jiawei Zhang
- Abstract要約: 我々は,各エージェントが各エージェントの報酬を観察する,未知のゲームにおけるオンライン学習について検討する。
まず,オンラインバンディット凸最適化アルゴリズムを構築し,$tildeTheta(sqrtT)$に対する単一エージェントの最適後悔を実現することを示す。
すると、各エージェントがこの非回帰学習アルゴリズムを強い単調ゲームに適用すると、ジョイントアクションはテクストラストにおいて、$tildeTheta(sqrt)の速度でユニークなナッシュ平衡に収束することを示す。
- 参考スコア(独自算出の注目度): 33.58816254556432
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider online no-regret learning in unknown games with bandit feedback,
where each agent only observes its reward at each time -- determined by all
players' current joint action -- rather than its gradient. We focus on the
class of smooth and strongly monotone games and study optimal no-regret
learning therein. Leveraging self-concordant barrier functions, we first
construct an online bandit convex optimization algorithm and show that it
achieves the single-agent optimal regret of $\tilde{\Theta}(\sqrt{T})$ under
smooth and strongly-concave payoff functions. We then show that if each agent
applies this no-regret learning algorithm in strongly monotone games, the joint
action converges in \textit{last iterate} to the unique Nash equilibrium at a
rate of $\tilde{\Theta}(1/\sqrt{T})$. Prior to our work, the best-know
convergence rate in the same class of games is $O(1/T^{1/3})$ (achieved by a
different algorithm), thus leaving open the problem of optimal no-regret
learning algorithms (since the known lower bound is $\Omega(1/\sqrt{T})$). Our
results thus settle this open problem and contribute to the broad landscape of
bandit game-theoretical learning by identifying the first doubly optimal bandit
learning algorithm, in that it achieves (up to log factors) both optimal regret
in the single-agent learning and optimal last-iterate convergence rate in the
multi-agent learning. We also present results on several simulation studies --
Cournot competition, Kelly auctions, and distributed regularized logistic
regression -- to demonstrate the efficacy of our algorithm.
- Abstract(参考訳): 各エージェントは、その勾配ではなく、すべてのプレイヤーの現在の共同アクションによって決定される、各時点における報酬のみを観察する。
我々は,滑らかで強いモノトーンゲームのクラスに注目し,そこでの最適ノンリグレット学習を考察する。
自己一致バリア関数を活用することで,オンラインバンディット凸最適化アルゴリズムをまず構築し,平滑かつ強コンケーブなペイオフ関数の下で$\tilde{\theta}(\sqrt{t})$の単一エージェント最適後悔を達成することを示す。
すると、各エージェントがこの非回帰学習アルゴリズムを強い単調ゲームに適用すると、結合作用は、$\tilde{\Theta}(1/\sqrt{T})$の速度で、一意なナッシュ平衡に収束する。
我々の研究に先立ち、同じゲームのクラスにおける最良の知識収束率は$O(1/T^{1/3})$(異なるアルゴリズムによって達成される)であり、したがって最適な非回帰学習アルゴリズムの問題を解き放つ(既知の下界は$\Omega(1/\sqrt{T})$)。
そこで本研究では,この開放的課題を解決し,第1次バンディット最適学習アルゴリズムを同定することで,バンディットゲーム理論的学習の広い景観に寄与し,単一エージェント学習における最適後悔とマルチエージェント学習における最適ラストイテレート収束率の両方を(ログファクターまで)達成する。
また,提案アルゴリズムの有効性を実証するため,いくつかのシミュレーション研究 (Cournot competition, Kelly auctions, distributed regularized logistic regression) の結果も提示した。
関連論文リスト
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in
Games [72.43065138581589]
RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。
本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。
そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
論文 参考訳(メタデータ) (2023-11-01T17:34:58Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and
Exp-Concave Games with Gradient Feedback [84.61895643083226]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳(メタデータ) (2023-10-21T18:38:13Z) - Doubly Optimal No-Regret Learning in Monotone Games [10.760195409078591]
本研究では,スムーズなモノトーンゲームのための2倍最適非線形学習アルゴリズムを提案する。
このアルゴリズムは, 滑らかかつ凸な損失関数の下での対角的条件下での最適$O(sqrtT)$後悔と, (ii) 最適$O(frac1T)$最後の収束率をナッシュ平衡に達成する。
論文 参考訳(メタデータ) (2023-01-30T17:55:53Z) - No-regret learning for repeated non-cooperative games with lossy bandits [5.437709019435926]
本研究では,長期的後悔の損失を最小限に抑えるために,プレイヤーの非同期オンライン学習戦略について検討する。
この論文は、損失帯域付きオンライングラディエントDescent(OGD-lb)と呼ばれる、新しい非回帰学習アルゴリズムを提供する。
論文 参考訳(メタデータ) (2022-05-14T05:02:56Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳(メタデータ) (2022-01-30T06:10:04Z) - 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) - Tight last-iterate convergence rates for no-regret learning in
multi-player games [31.604950465209335]
定常的なステップサイズを持つ楽観的勾配(OG)アルゴリズムは,スムーズな単調ゲームにおいて最終定位レートが$O(1/sqrtT)であることを示す。
また、$O (1/sqrtT)$レートは、特別なケースとしてOGを含む全ての$p$-SCLIアルゴリズムに対して厳密であることを示す。
論文 参考訳(メタデータ) (2020-10-26T17:06:19Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-22T05:00:13Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-20T06:36:19Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳(メタデータ) (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。