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

• arxiv url: http://arxiv.org/abs/2210.13396v2
• Date: Fri, 04 Oct 2024 07:27:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-07 15:06:12.352774
• 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種類のフィードバックについて検討する。 ゲームレベルのフィードバック設定ではエージェントレベルのフィードバック設定のカバレッジ仮定が不十分であることを示す。 本研究は,オフラインの混雑ゲームに関する最初の研究である。
• 参考スコア（独自算出の注目度）: 53.83345471268163
• License:
• 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（参考訳）: 本稿では,オフラインの混雑ゲームにおいて,Nash Equilibrium (NE) を効率よく回収する方法について検討する。 オフラインの汎用ゲームにおける既存のデータセットカバレッジの仮定は、必然的に、混雑ゲームにおいて指数関数的に大きいアクションの数に依存する。 情報開示を減らした3種類のフィードバックについて検討する。 施設レベルのフィードバック(半帯域)から始まり、新しい一単位偏差カバレッジ条件を提案し、近似NEを復元できる悲観型アルゴリズムを提案する。 エージェントレベル(つまりバンドイット)のフィードバック設定については、興味深いことに、単ユニット偏差カバレッジ条件が不十分であることを示す。 一方、ゲームはマルチエージェント線形帯域に変換され、オフライン線形帯域における一般化されたデータカバレッジ仮定により、近似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)

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

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