論文の概要: Learning Equilibria in Matching Games with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2506.03802v1
• Date: Wed, 04 Jun 2025 10:15:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 21:20:14.2854
• Title: Learning Equilibria in Matching Games with Bandit Feedback
• Title（参考訳）: 帯域フィードバックを用いたマッチゲームにおける学習平衡
• Authors: Andreas Athanasopoulos, Christos Dimitrakakis,
• Abstract要約: 一般化された二面マッチング市場における均衡学習の問題について検討する。 エージェントが選好を作成し、ゲームペイオフの楽観的な推定に基づいて選択する UCB アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 2.5015086558362247
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the problem of learning an equilibrium in a generalized two-sided matching market, where agents can adaptively choose their actions based on their assigned matches. Specifically, we consider a setting in which matched agents engage in a zero-sum game with initially unknown payoff matrices, and we explore whether a centralized procedure can learn an equilibrium from bandit feedback. We adopt the solution concept of matching equilibrium, where a pair consisting of a matching $\mathfrak{m}$ and a set of agent strategies $X$ forms an equilibrium if no agent has the incentive to deviate from $(\mathfrak{m}, X)$. To measure the deviation of a given pair $(\mathfrak{m}, X)$ from the equilibrium pair $(\mathfrak{m}^\star, X^\star)$, we introduce matching instability that can serve as a regret measure for the corresponding learning problem. We then propose a UCB algorithm in which agents form preferences and select actions based on optimistic estimates of the game payoffs, and prove that it achieves sublinear, instance-independent regret over a time horizon $T$.
• Abstract（参考訳）: 本稿では、エージェントが割り当てられたマッチングに基づいて、適応的に行動を選択することができる一般化された二面マッチング市場における均衡学習の問題について検討する。 具体的には、一致したエージェントが当初未知のペイオフ行列を持つゼロサムゲームに従事している状況について考察し、集中的な手続きが帯域フィードバックから平衡を学習できるかどうかを検討する。 一致する$\mathfrak{m}$と一組のエージェント戦略からなる対が、もしエージェントが$(\mathfrak{m}, X)$から逸脱する動機を持たないなら、$X$は平衡を形成する。 与えられた対 $(\mathfrak{m}, X)$ の平衡対 $(\mathfrak{m}^\star, X^\star)$ の偏差を測定するために、対応する学習問題に対する後悔の尺度となるマッチング不安定性を導入する。 次に, エージェントがゲームペイオフの楽観的な推定値に基づいて選好を形成し, 選択行動を選択する UCB アルゴリズムを提案し, 時間軸$T$ でサブリニアなインスタンス非依存の後悔を実現することを証明した。

関連論文リスト

• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  非定常マルチエージェントシステムにおける平衡の学習について検討する。 単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
  論文  参考訳（メタデータ） (2023-06-12T23:48:24Z)
• Equilibrium Bandits: Learning Optimal Equilibria of Unknown Dynamics [23.722837647516357]
  未知のシステムを制御するために、$K$アクションのうちの1つを選ぶことができる意思決定者を考えてみましょう。 システムのダイナミクスは意思決定者にとって未知であり、各ターンの最後にノイズの多い報酬しか観測できない。 既存のバンディットアルゴリズムは、逆数でも、この問題に対して線形な(タウ)後悔を達成する。 均衡に達するまで待つ価値がなければ、素早くアクションを切り替えることを知っている新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-27T10:47:15Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Multi-Leader Congestion Games with an Adversary [0.5914780964919123]
  本研究では,複数のユーザ(リーダ)がリソースセットから1つのリソースを選択するマルチリーダシングルフォロワ・コングリゲーションゲームについて検討する。 純粋なナッシュ平衡は存在せず、従って近似平衡を考える。 与えられたインスタンスのすべての$alpha$-approximate equilibriaの中で、最小の$alpha$で、最適な近似平衡を効率的に計算する方法を示す。
  論文  参考訳（メタデータ） (2021-12-14T14:47:43Z)
• Learning equilibria with personalized incentives in a class of nonmonotone games [7.713240800142863]
  我々は、ポテンシャルであることが知られているエージェント間の対称相互作用を伴う二次的、非単調なナッシュ均衡問題を考察する。 提案手法では,コーディネータが騒音エージェントのフィードバックを反復的に統合し,エージェントの擬似階調を学習し,パーソナライズされたインセンティブを設計する。 我々は,コーディネータに標準学習ポリシーが与えられた場合,アルゴリズムが平衡を返すことを示す。
  論文  参考訳（メタデータ） (2021-11-06T11:18:59Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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