論文の概要: No-regret learning for repeated non-cooperative games with lossy bandits
- arxiv url: http://arxiv.org/abs/2205.06968v1
- Date: Sat, 14 May 2022 05:02:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-19 06:54:44.886899
- Title: No-regret learning for repeated non-cooperative games with lossy bandits
- Title（参考訳）: 繰り返し非協調ゲームにおける非回帰学習
- Authors: Wenting Liu, Jinlong Lei, Peng Yi, Yiguang Hong
- Abstract要約: 本研究では,長期的後悔の損失を最小限に抑えるために,プレイヤーの非同期オンライン学習戦略について検討する。
この論文は、損失帯域付きオンライングラディエントDescent(OGD-lb)と呼ばれる、新しい非回帰学習アルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 5.437709019435926
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper considers no-regret learning for repeated continuous-kernel games
with lossy bandit feedback. Since it is difficult to give the explicit model of
the utility functions in dynamic environments, the players' action can only be
learned with bandit feedback. Moreover, because of unreliable communication
channels or privacy protection, the bandit feedback may be lost or dropped at
random. Therefore, we study the asynchronous online learning strategy of the
players to adaptively adjust the next actions for minimizing the long-term
regret loss. The paper provides a novel no-regret learning algorithm, called
Online Gradient Descent with lossy bandits (OGD-lb). We first give the regret
analysis for concave games with differentiable and Lipschitz utilities. Then we
show that the action profile converges to a Nash equilibrium with probability 1
when the game is also strictly monotone. We further provide the mean square
convergence rate $\mathcal{O}\left(k^{-2\min\{\beta, 1/6\}}\right)$ when the
game is $\beta-$ strongly monotone. In addition, we extend the algorithm to the
case when the loss probability of the bandit feedback is unknown, and prove its
almost sure convergence to Nash equilibrium for strictly monotone games.
Finally, we take the resource management in fog computing as an application
example, and carry out numerical experiments to empirically demonstrate the
algorithm performance.
- Abstract（参考訳）: 本稿では,バンディットフィードバックの損失を伴う連続カーネルゲームにおけるノンリグレット学習について検討する。
動的環境における効用関数の明示的なモデルを与えるのは難しいため、プレイヤーの行動はバンディットフィードバックによってのみ学習できる。
さらに、信頼性の低い通信チャネルやプライバシ保護のため、盗聴のフィードバックは無作為に失われることがある。
そこで我々は,長期的後悔の損失を最小限に抑えるため,プレイヤーの非同期オンライン学習戦略について検討した。
この論文は、オンライン勾配降下と損失バンド(ogd-lb)と呼ばれる新しい非回帰学習アルゴリズムを提供する。
まず,微分可能およびリプシッツユーティリティを備えたconcaveゲームに対する後悔の分析を行う。
次に、ゲームが厳密に単調であるときに、アクションプロファイルが確率1とナッシュ平衡に収束することを示す。
さらに、ゲームが$\beta-$強単調であるときの平均平方収束率 $\mathcal{O}\left(k^{-2\min\{\beta, 1/6\right)$ を提供する。
さらに,バンディットフィードバックの損失確率が未知の場合にもアルゴリズムを拡張し,厳密な単調ゲームに対するナッシュ平衡へのほぼ確実な収束性を証明した。
最後に,フォグコンピューティングにおける資源管理を応用例として取り上げ,アルゴリズムの性能を実証的に示す数値実験を行った。
関連論文リスト
- No Algorithmic Collusion in Two-Player Blindfolded Game with Thompson Sampling [10.376707874029561]
プレイヤーがトンプソンサンプリングを使用すると、ゲームダイナミクスはペイオフ行列の軽度な仮定の下でナッシュ平衡に収束することを示す。
アルゴリズムによる共謀は 発生しない プレイヤーが意図的に 競争戦略を展開していないにもかかわらず
論文 参考訳（メタデータ） (2024-05-23T08:21:48Z) - Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games [27.52590585111178]
我々は、コストと帯域幅のフィードバックの下で、潜在的なゲームとマルコフ潜在的なゲームについて研究する。
我々のアルゴリズムは、潜在的なゲームに対して、ナッシュの後悔と、O(T4/5)の後悔の限界を同時に達成する。
論文 参考訳（メタデータ） (2024-04-04T01:02:03Z) - Is Learning in Games Good for the Learners? [14.781100349601587]
2人のエージェント間の繰り返しのゲームプレイにおいて、報酬と後悔の間のトレードオフを考慮する。
このような平衡は、任意の相手に対する後悔の保証を維持するアルゴリズムのペアによって到達可能であることを示す。
また,ゲーム開始時において,未学習エージェントとの繰り返しプレイを通じて報酬-最適戦略を学習する問題についても検討する。
論文 参考訳（メタデータ） (2023-05-31T02:10:27Z) - Regret Matching+: (In)Stability and Fast Convergence in Games [68.13214224119024]
RM+とその予測バージョンは不安定であり,他のプレイヤーが大きな後悔を味わう可能性がある。
これらの修正は、RM+による通常のゲームにおいて、個々の後悔に対して$O(T1/4)$$と$O(1)$の社会的後悔を得るのに十分であることを示す。
論文 参考訳（メタデータ） (2023-05-24T04:26:21Z) - Bandit Social Learning: Exploration under Myopic Behavior [58.75758600464338]
オンラインプラットフォーム上でのレビューによって動機付けられた社会学習のダイナミクスについて検討する。
エージェントはまとめて単純なマルチアームのバンディットプロトコルに従うが、各エージェントは探索を伴わずにミオプティカルに振る舞う。
このような振る舞いに対して,スターク学習の失敗を導出し,好意的な結果を提供する。
論文 参考訳（メタデータ） (2023-02-15T01:57:57Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Offline congestion games: How feedback type affects data coverage requirement [53.83345471268163]
情報開示を減らした3種類のフィードバックについて検討する。
ゲームレベルのフィードバック設定ではエージェントレベルのフィードバック設定のカバレッジ仮定が不十分であることを示す。
本研究は,オフラインの混雑ゲームに関する最初の研究である。
論文 参考訳（メタデータ） (2022-10-24T16:49:16Z) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳（メタデータ） (2022-04-24T03:10:27Z) - Nonstochastic Bandits with Composite Anonymous Feedback [41.38921728211769]
本研究では,アクションの損失が直ちにプレイヤーに請求されない非確率的バンディット設定について検討する。
各ラウンドの最後にプレイヤーが観測した瞬間的な損失は、これまでプレイされたアクションの多くの損失成分の合計である。
論文 参考訳（メタデータ） (2021-12-06T08:44:04Z) - Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。
我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。
そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
論文 参考訳（メタデータ） (2021-12-06T08:27:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。