論文の概要: Offline congestion games: How feedback type affects data coverage requirement

• arxiv url: http://arxiv.org/abs/2210.13396v1
• Date: Mon, 24 Oct 2022 16:49:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-25 22:18:24.534457
• Title: Offline congestion games: How feedback type affects data coverage requirement
• Title（参考訳）: オフライン混雑ゲーム:フィードバックタイプがデータカバレッジ要求に与える影響
• Authors: Haozhe Jiang, Qiwen Cui, Zhihan Xiong, Maryam Fazel, Simon S. Du
• Abstract要約: 情報開示を減らした3種類のフィードバックについて検討する。 ゲームレベルのフィードバック設定ではエージェントレベルのフィードバック設定のカバレッジ仮定が不十分であることを示す。 最後に,新たなタイプのフィードバック,ゲームレベルのフィードバックについて考察する。
• 参考スコア（独自算出の注目度）: 41.608459163192684
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper investigates when one can efficiently recover an approximate Nash Equilibrium (NE) in offline congestion games.The existing dataset coverage assumption in offline general-sum games inevitably incurs a dependency on the number of actions, which can be exponentially large in congestion games. We consider three different types of feedback with decreasing revealed information. Starting from the facility-level (a.k.a., semi-bandit) feedback, we propose a novel one-unit deviation coverage condition and give a pessimism-type algorithm that can recover an approximate NE. For the agent-level (a.k.a., bandit) feedback setting, interestingly, we show the one-unit deviation coverage condition is not sufficient. On the other hand, we convert the game to multi-agent linear bandits and show that with a generalized data coverage assumption in offline linear bandits, we can efficiently recover the approximate NE. Lastly, we consider a novel type of feedback, the game-level feedback where only the total reward from all agents is revealed. Again, we show the coverage assumption for the agent-level feedback setting is insufficient in the game-level feedback setting, and with a stronger version of the data coverage assumption for linear bandits, we can recover an approximate NE. Together, our results constitute the first study of offline congestion games and imply formal separations between different types of feedback.
• Abstract（参考訳）: 本稿では,オフラインの混雑ゲームにおけるナッシュ均衡(ne)を効率的に回復できる場合について検討する。オフラインの汎用ゲームにおける既存のデータセットカバレッジの仮定は,混雑ゲームにおいて指数関数的に大きいアクション数に必然的に依存する。 情報量を減らすことで,3種類のフィードバックを考察する。 施設レベルのフィードバック(すなわち半帯域)から始めて、新しい一単位偏差被覆条件を提案し、近似neを回復できる悲観的型アルゴリズムを与える。 エージェントレベル(つまりbandit)のフィードバック設定では、興味深いことに、1単位の偏差カバレッジ条件が不十分である。 一方,ゲームをマルチエージェントリニアバンディットに変換し,オフラインリニアバンディットにおける一般的なデータカバレッジ仮定により,近似neを効率的に回収できることを示す。 最後に、新たなタイプのフィードバック、すなわち、すべてのエージェントからの全報酬のみを開示するゲームレベルのフィードバックについて検討する。 また,ゲームレベルのフィードバック設定ではエージェントレベルのフィードバック設定のカバレッジ設定が不十分であることを示すとともに,線形帯域に対するデータカバレッジ設定のより強力なバージョンにより,近似NEを復元できることを示す。 共に,オフラインの混雑ゲームに関する最初の研究であり,フィードバックの形式的分離を示唆する。

関連論文リスト

• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• Auto-Encoding Bayesian Inverse Games [36.06617326128679]
  ゲームの性質が不明な逆ゲーム問題を考える。 既存の最大推定手法は、未知のパラメータの点推定のみを提供する。 ベイズ的視点を採り、ゲームパラメータの後方分布を構成する。 この構造化されたVAEは、観測された相互作用のラベルのないデータセットから訓練することができる。
  論文  参考訳（メタデータ） (2024-02-14T02:17:37Z)
• Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach [18.13887411913371]
  本稿では,エージェントが各アームの報酬分布の推定を改善するために使用可能なオフラインデータにアクセス可能な帯域幅問題について検討する。 我々はバイアスを、それらが示唆する因果構造に基づいて、矛盾するバイアスと選択バイアスに分類する。 我々は、偏りのある観測データから、複合バイアスに対して頑健な各腕の因果関係を抽出する。
  論文  参考訳（メタデータ） (2023-12-20T03:03:06Z)
• Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptive Residual Module [65.81781176362848]
  グラフニューラルネットワーク(GNN)は、近隣情報収集を通じてグラフ構造化データから学習することができる。 レイヤーの数が増えるにつれて、ノード表現は区別不能になり、オーバー・スムーシング(over-smoothing)と呼ばれる。 我々は,textbfPosterior-Sampling-based, Node-distinguish Residual Module (PSNR)を提案する。
  論文  参考訳（メタデータ） (2023-05-09T12:03:42Z)
• Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
  マルコフゲームにおけるオフラインマルチエージェント強化学習(RL)について検討する。 マルコフゲームにおけるサンプル効率のよいオフライン学習のための最初のフレームワークを提供する。
  論文  参考訳（メタデータ） (2023-02-06T05:22:27Z)
• Reward Imputation with Sketching for Contextual Batched Bandits [48.80803376405073]
  コンテキストバッチバンドイット(Contextual batched bandit、CBB)は、各エピソードの最後に環境から報酬のバッチを観測する設定である。 CBBの既存のアプローチは、実行されていないアクションの報酬を無視し、フィードバック情報の未利用につながることが多い。 本研究では,未観測の報酬をスケッチを用いて完遂するSketched Policy Updating with Imputed Rewards (SPUIR)を提案する。
  論文  参考訳（メタデータ） (2022-10-13T04:26:06Z)
• Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts [53.579515853222986]
  時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。 この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。 本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T15:56:59Z)
• No-regret learning for repeated non-cooperative games with lossy bandits [5.437709019435926]
  本研究では,長期的後悔の損失を最小限に抑えるために,プレイヤーの非同期オンライン学習戦略について検討する。 この論文は、損失帯域付きオンライングラディエントDescent(OGD-lb)と呼ばれる、新しい非回帰学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-14T05:02:56Z)
• Experts with Lower-Bounded Loss Feedback: A Unifying Framework [8.947188600472256]
  我々はexp3の修正版に対する最適な後悔の限界を証明し、アルゴリズムと境界をバンディットと全情報設定の両方に一般化する。 この結果から,各ラウンドにおける専門家の任意のサブセットからのフィードバックを,グラフ構造化されたフィードバックで受けられるようにした。 また,各損失に対する非自明な下限を許容することにより,一貫したレベルの部分的フィードバックを許容する。
  論文  参考訳（メタデータ） (2020-12-17T12:18:52Z)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。 また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
  論文  参考訳（メタデータ） (2020-02-19T21:36:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。