論文の概要: Competition is the key: A Game Theoretic Causal Discovery Approach

• arxiv url: http://arxiv.org/abs/2510.20106v1
• Date: Thu, 23 Oct 2025 01:19:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:17.116833
• Title: Competition is the key: A Game Theoretic Causal Discovery Approach
• Title（参考訳）: 競争が鍵:ゲーム理論の因果発見アプローチ
• Authors: Amartya Roy, Souvik Chakraborty,
• Abstract要約: 因果発見のためのゲーム理論強化学習フレームワークを提案する。 DDQNエージェントは、強いベースライン(GESまたはGraN-DAG)と直接競合し、常に相手の解からウォームスタートする。 この設計は、3つの証明可能な保証を与える: 学習されたグラフは相手よりも決して悪くない、ウォームスタートは厳密に収束を加速する、そして最も重要なことはアルゴリズムが真のベスト候補グラフを選択する確率が高いことである。
• 参考スコア（独自算出の注目度）: 2.248800010440909
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Causal discovery remains a central challenge in machine learning, yet existing methods face a fundamental gap: algorithms like GES and GraN-DAG achieve strong empirical performance but lack finite-sample guarantees, while theoretically principled approaches fail to scale. We close this gap by introducing a game-theoretic reinforcement learning framework for causal discovery, where a DDQN agent directly competes against a strong baseline (GES or GraN-DAG), always warm-starting from the opponent's solution. This design yields three provable guarantees: the learned graph is never worse than the opponent, warm-starting strictly accelerates convergence, and most importantly, with high probability the algorithm selects the true best candidate graph. To the best of our knowledge, our result makes a first-of-its-kind progress in explaining such finite-sample guarantees in causal discovery: on synthetic SEMs (30 nodes), the observed error probability decays with n, tightly matching theory. On real-world benchmarks including Sachs, Asia, Alarm, Child, Hepar2, Dream, and Andes, our method consistently improves upon GES and GraN-DAG while remaining theoretically safe. Remarkably, it scales to large graphs such as Hepar2 (70 nodes), Dream (100 nodes), and Andes (220 nodes). Together, these results establish a new class of RL-based causal discovery algorithms that are simultaneously provably consistent, sample-efficient, and practically scalable, marking a decisive step toward unifying empirical performance with rigorous finite-sample theory.
• Abstract（参考訳）: GESやGraN-DAGのようなアルゴリズムは強力な経験的性能を達成しているが、有限サンプル保証は欠如している。 DDQNエージェントが強いベースライン(GESまたはGraN-DAG)と直接競合し、常に相手の解からウォームスタートする因果発見のためのゲーム理論強化学習フレームワークを導入することで、このギャップを埋める。 この設計は、3つの証明可能な保証を与える: 学習されたグラフは相手よりも決して悪くない、ウォームスタートは厳密に収束を加速する、そして最も重要なことはアルゴリズムが真のベスト候補グラフを選択する確率が高いことである。 我々の知識を最大限に活用するために、我々の結果は、因果発見におけるそのような有限サンプル保証を説明するための第一段階の進歩である:合成SEM(30ノード)において、観測された誤差確率は、n, tightly matching theoryで崩壊する。 Sachs、Asia、Alarm、Child、Hepar2、Dream、Andesといった実世界のベンチマークでは、理論上は安全でありながら、GESとGraN-DAGを継続的に改善しています。 注目すべきは、Hepar2 (70ノード)、Dream (100ノード)、Andes (220ノード)のような大きなグラフにスケールすることです。 これらの結果とともに、RLに基づく因果探索アルゴリズムの新たなクラスが確立され、証明可能な一貫性、サンプル効率、実用的スケーラビリティが確立され、厳密な有限サンプル理論による経験的性能の統一に向けた決定的な一歩となった。

関連論文リスト

• Retrieving Classes of Causal Orders with Inconsistent Knowledge Bases [0.8192907805418583]
  大規模言語モデル(LLM)は、テキストベースのメタデータから因果的知識を抽出するための有望な代替手段として登場した。 LLMは信頼できない傾向があり、幻覚を起こす傾向があり、その限界を考慮に入れた戦略を必要とする。 本稿では,非循環型トーナメントのクラスを導出する新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-12-18T16:37:51Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Valid Inference After Causal Discovery [73.87055989355737]
  我々は、因果関係発見後の推論に有効なツールを開発する。 因果発見とその後の推論アルゴリズムの組み合わせは,高度に膨らんだ誤発見率をもたらすことを示す。
  論文  参考訳（メタデータ） (2022-08-11T17:40:45Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More [85.52940587312256]
  本稿では,初期作業を想定したランダム化平滑化フレームワークに基づくモデル非依存の証明書を提案する。 このアプローチがさまざまなモデル、データセット、タスクに対して有効であることを示します。
  論文  参考訳（メタデータ） (2020-08-29T10:09:02Z)
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks [96.93500886136532]
  グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。 GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。 我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-25T15:17:58Z)

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

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