論文の概要: Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs

• arxiv url: http://arxiv.org/abs/2505.06319v1
• Date: Thu, 08 May 2025 21:12:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-13 20:21:48.781446
• Title: Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs
• Title（参考訳）: グラフ上のゲーム理論資源配分のための強化学習
• Authors: Zijian An, Lifeng Zhou,
• Abstract要約: GRAG (Game-theoretic Resource allocation on graphs) は、マルチステップのColoner Blotto Game (MCBG) としてモデル化された問題である。 MCBGをマルコフ決定過程(MDP)として定式化し、強化学習(RL)法、特にDeep Q-Network(DQN)とPPOを適用した。 各種グラフ構造および初期資源分布におけるRL性能の評価を行い, ランダム, 欲求, 学習されたRLポリシーとの比較を行った。
• 参考スコア（独自算出の注目度）: 9.369330148791201
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Game-theoretic resource allocation on graphs (GRAG) involves two players competing over multiple steps to control nodes of interest on a graph, a problem modeled as a multi-step Colonel Blotto Game (MCBG). Finding optimal strategies is challenging due to the dynamic action space and structural constraints imposed by the graph. To address this, we formulate the MCBG as a Markov Decision Process (MDP) and apply Reinforcement Learning (RL) methods, specifically Deep Q-Network (DQN) and Proximal Policy Optimization (PPO). To enforce graph constraints, we introduce an action-displacement adjacency matrix that dynamically generates valid action sets at each step. We evaluate RL performance across a variety of graph structures and initial resource distributions, comparing against random, greedy, and learned RL policies. Experimental results show that both DQN and PPO consistently outperform baseline strategies and converge to a balanced $50\%$ win rate when competing against the learned RL policy. Particularly, on asymmetric graphs, RL agents successfully exploit structural advantages and adapt their allocation strategies, even under disadvantageous initial resource distributions.
• Abstract（参考訳）: グラフ上でのゲーム理論的リソース割り当て(GRAG)は、グラフ上の関心ノードを制御するために複数のステップで競合する2人のプレイヤーを巻き込み、これはマルチステップのBlotto Game(MCBG)としてモデル化される。 動的なアクション空間とグラフによって課される構造的制約のため、最適な戦略を見つけることは困難である。 そこで我々は,MCBGをMDP(Markov Decision Process)として定式化し,強化学習(Reinforcement Learning, RL)法,特にDeep Q-Network(DQN)法とPPO法を適用した。 グラフ制約を強制するために、各ステップで有効なアクションセットを動的に生成するアクション変位隣接行列を導入する。 各種グラフ構造および初期資源分布におけるRL性能の評価を行い, ランダム, 欲求, 学習されたRLポリシーとの比較を行った。 実験結果から,DQNとPPOはいずれもベースライン戦略を一貫して上回り,学習したRL政策に対抗してバランスのとれた50\%の勝利率に収束することがわかった。 特に非対称グラフ上では、RLエージェントは構造上の利点をうまく活用し、不利な初期資源分布の下でもそれらの割り当て戦略に適応する。

関連論文リスト

• GraphRAG-R1: Graph Retrieval-Augmented Generation with Process-Constrained Reinforcement Learning [33.57411612551111]
  プロセス制約付き結果ベース強化学習(RL)を用いたLLMの学習による適応型GraphRAGフレームワークGraphRAG-R1を提案する。 本手法は,複雑な問題を分解し,検索ツールを自律的に実行し,効果的な推論を行う。 我々のフレームワークは、様々な既存の検索手法と柔軟に統合でき、継続的に性能改善を提供することができる。
  論文  参考訳（メタデータ） (2025-07-31T14:11:16Z)
• Learning Efficient and Generalizable Graph Retriever for Knowledge-Graph Question Answering [75.12322966980003]
  大規模言語モデル(LLM)は、様々な領域にわたって強い帰納的推論能力を示している。 既存のRAGパイプラインのほとんどは非構造化テキストに依存しており、解釈可能性と構造化推論を制限する。 近年,知識グラフ解答のための知識グラフとLLMの統合について検討している。 KGQAにおける効率的なグラフ検索のための新しいフレームワークであるRAPLを提案する。
  論文  参考訳（メタデータ） (2025-06-11T12:03:52Z)
• HGFormer: A Hierarchical Graph Transformer Framework for Two-Stage Colonel Blotto Games via Reinforcement Learning [4.144893164317513]
  ブロット大佐の2段階のゲームは典型的な逆資源割り当て問題を表す。 本稿ではHGformerと呼ばれる階層型グラフトランスフォーマフレームワークを提案する。 本手法により,大規模環境における効率的な政策生成が可能となる。
  論文  参考訳（メタデータ） (2025-06-10T08:51:18Z)
• G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning [58.73279333365234]
  合成グラフ理論タスクにおける強化学習(RL)はグラフ推論能力を著しく拡張することができる。 RL on ErdosでG1はグラフ推論の大幅な改善を実現し、微調整された3BモデルはQwen2.5-72B-Instruct(24倍)よりも優れています。 我々の研究は、グラフ理論上のRLでLLMを微調整することで、強力なグラフ推論器を構築するための効率的でスケーラブルな経路を提供する。
  論文  参考訳（メタデータ） (2025-05-24T04:33:41Z)
• Delving into RL for Image Generation with CoT: A Study on DPO vs. GRPO [68.44918104224818]
  自己回帰画像生成は、Chain-of-Thought(CoT)推論とは異なる固有の課題を示す。 本研究は,自己回帰画像生成におけるGRPOアルゴリズムとDPOアルゴリズムの総合的研究である。 以上の結果から,GRPOとDPOは異なる優位性を示し,本質的な一般化能力を有する報酬モデルが適用されたRLアルゴリズムの一般化可能性を高める可能性が示唆された。
  論文  参考訳（メタデータ） (2025-05-22T17:59:49Z)
• Compile Scene Graphs with Reinforcement Learning [69.36723767339001]
  次世代予測は大規模言語モデル(LLM)の訓練の基本原理である 本稿では,マルチモーダルLLM(M-LLM)であるR1-SGGを紹介する。 私たちは、Hard Recall、Hard Recall+Relax、Soft Recallの3つのリコールベースのバリエーションを含む、グラフ中心の報酬セットを設計します。
  論文  参考訳（メタデータ） (2025-04-18T10:46:22Z)
• Paths to Equilibrium in Games [6.812247730094933]
  我々は、強化学習におけるポリシー更新に触発されたペアワイズ制約を満たす戦略の列について研究する。 我々の分析は、戦略的な更新を劣化させる報酬が、満足のいく道に沿って均衡に進むための鍵である、という直感的な洞察を明らかにした。
  論文  参考訳（メタデータ） (2024-03-26T19:58:39Z)
• Optimal coordination of resources: A solution from reinforcement learning [6.0413802011767705]
  マイノリティゲーム(MG)はおそらくこの問題に対処する最もシンプルなおもちゃモデルだろう。 我々はMGに強化学習パラダイムを導入し、蓄積された経験に基づいて個人が意思決定を調整する。 このRLフレームワークは、個人がランダム探索による経験の活用のバランスをとると、最適な資源調整を実現する。
  論文  参考訳（メタデータ） (2023-12-20T00:47:45Z)
• Decoupled Prioritized Resampling for Offline RL [114.73666323173204]
  オフライン強化学習のためのオフライン優先体験再生(OPER)を提案する。 OPERは、高度に反転する遷移を優先するように設計された優先順位関数のクラスを備えており、トレーニング中により頻繁に訪問することができる。 優先順位関数のクラスは行動ポリシーの改善を誘導し、この改善されたポリシーに制約された場合、ポリシー制約付きオフラインRLアルゴリズムによりより良い解が得られる可能性が示唆された。
  論文  参考訳（メタデータ） (2023-06-08T17:56:46Z)
• Mastering the Unsupervised Reinforcement Learning Benchmark from Pixels [112.63440666617494]
  強化学習アルゴリズムは成功するが、エージェントと環境の間の大量の相互作用を必要とする。 本稿では,教師なしモデルベースRLを用いてエージェントを事前学習する手法を提案する。 我々はReal-Word RLベンチマークにおいて、適応中の環境摂動に対する抵抗性を示唆し、堅牢な性能を示す。
  論文  参考訳（メタデータ） (2022-09-24T14:22:29Z)
• Scalable Deep Reinforcement Learning Algorithms for Mean Field Games [60.550128966505625]
  平均フィールドゲーム (MFGs) は、非常に多くの戦略エージェントを持つゲームを効率的に近似するために導入された。 近年,モデルフリー強化学習(RL)手法を用いて,MFGの学習均衡の課題が活発化している。 MFGを解くための既存のアルゴリズムは戦略や$q$-valuesのような近似量の混合を必要とする。 本稿では,この欠点に対処する2つの手法を提案する。まず,歴史データの蒸留からニューラルネットワークへの混合戦略を学習し,Factitious Playアルゴリズムに適用する。 2つ目はオンライン混合方式である。
  論文  参考訳（メタデータ） (2022-03-22T18:10:32Z)
• Designing Heterogeneous GNNs with Desired Permutation Properties for Wireless Resource Allocation [11.66835230109271]
  グラフニューラルネットワーク(GNN)は、さまざまな無線ポリシを学ぶために設計されている。 本稿では,所望の置換特性を満たすための設計手法を提案する。
  論文  参考訳（メタデータ） (2022-03-08T08:02:54Z)
• Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions [7.6860514640178]
  協調型マルチエージェント強化学習(MARL)のための計算効率の良い分散フレームワークを提案する。 MARLにおける3種類のエージェント間カップリングを記述した3つのカップリンググラフを導入する。 結合グラフから導出した局所値関数に基づく2つの分散RL手法を提案する。
  論文  参考訳（メタデータ） (2022-02-26T03:01:51Z)
• Learning Two-Step Hybrid Policy for Graph-Based Interpretable Reinforcement Learning [7.656272344163665]
  本稿では,グラフベース入力を用いたRL問題に対して,解釈可能かつ堅牢な階層型ポリシを生成するための2段階のハイブリッド強化学習(RL)ポリシーを提案する。 この2段階のハイブリッドポリシは、人間フレンドリーな解釈を示し、一般化と堅牢性の観点から、より良いパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2022-01-21T03:06:24Z)

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

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