論文の概要: The Minimal Search Space for Conditional Causal Bandits

• arxiv url: http://arxiv.org/abs/2502.06577v1
• Date: Mon, 10 Feb 2025 15:45:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 14:36:16.790507
• Title: The Minimal Search Space for Conditional Causal Bandits
• Title（参考訳）: 条件付き因果帯域の最小探索空間
• Authors: Francisco N. F. Q. Simoes, Itai Feigenbaum, Mehdi Dastani, Thijs van Ommen,
• Abstract要約: 因果知識は意思決定問題を支援するのに使える。 本稿では、最適条件介入を含むことが保証される最小限のノードのグラフィカルな特徴について述べる。 次に、この最小のノード群を特定するために、O(|V| + |E|)$の時間複雑性を持つ効率的なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.18124328823188351
• License:
• Abstract: Causal knowledge can be used to support decision-making problems. This has been recognized in the causal bandits literature, where a causal (multi-armed) bandit is characterized by a causal graphical model and a target variable. The arms are then interventions on the causal model, and rewards are samples of the target variable. Causal bandits were originally studied with a focus on hard interventions. We focus instead on cases where the arms are conditional interventions, which more accurately model many real-world decision-making problems by allowing the value of the intervened variable to be chosen based on the observed values of other variables. This paper presents a graphical characterization of the minimal set of nodes guaranteed to contain the optimal conditional intervention, which maximizes the expected reward. We then propose an efficient algorithm with a time complexity of $O(|V| + |E|)$ to identify this minimal set of nodes. We prove that the graphical characterization and the proposed algorithm are correct. Finally, we empirically demonstrate that our algorithm significantly prunes the search space and substantially accelerates convergence rates when integrated into standard multi-armed bandit algorithms.
• Abstract（参考訳）: 因果知識は意思決定問題を支援するのに使える。 これは、因果的図形モデルと対象変数によって特徴付けられる因果的(多腕的)包帯の文献で認識されている。 腕は因果モデルへの介入であり、報酬は対象変数のサンプルである。 ケーサル・バンディットはもともと、ハード・介入に焦点をあてて研究された。 代わりに、アームが条件付き介入である場合に焦点を当て、他の変数の観測値に基づいて、介入変数の値を選択できるようにすることにより、多くの実世界の意思決定問題をより正確にモデル化する。 本稿では、最適条件付き介入を含むことが保証される最小限のノードのグラフィカルな特徴付けを行い、期待される報酬を最大化する。 次に、この最小のノード群を特定するために、O(|V| + |E|)$の時間複雑性を持つ効率的なアルゴリズムを提案する。 グラフィカルな特徴付けと提案アルゴリズムが正しいことを証明する。 最後に,本アルゴリズムは探索空間を著しく向上させ,標準のマルチアームバンディットアルゴリズムに統合した場合の収束率を大幅に向上させることを示す。

関連論文リスト

• Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits [7.064432289838905]
  現在の研究はしばしば因果グラフが知られていると仮定するが、これは必ずしも先入観として利用できるとは限らない。 我々は、根底にある因果グラフが不明で、潜伏する共同設立者を含むシナリオにおける因果帯域の問題に焦点を当てる。 われわれは、必要で十分な潜在的共同創設者の集合を公式に特徴付け、可能な限り最適な武器が正しく特定されるように検出または学習する必要がある。
  論文  参考訳（メタデータ） (2024-11-06T16:59:11Z)
• Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
  Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。 本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
  論文  参考訳（メタデータ） (2024-09-09T18:23:07Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Pure Exploration of Causal Bandits [9.77519365079468]
  因果バンディット問題は多腕バンディットと因果推論を統合する。 オンライン学習課題:未知の因果推論分布を持つ因果グラフを与えられた場合、1つの変数に介入するか、介入しないかを選択できる。 3種類の因果モデルに対して、第一のギャップ依存完全適応純粋探索アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-06-16T02:19:37Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
  静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。 我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。 最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
  論文  参考訳（メタデータ） (2020-12-07T08:23:08Z)
• Causal Bandits without prior knowledge using separating sets [3.1000291317725]
  カウサル・バンディット(Causal Bandit)は、エージェントがシーケンシャルな意思決定プロセスにおいて最良のアクションを識別しなければならない古典的なバンディット問題の変種である。 これまでの文献で提案されている手法は、完全な因果グラフの正確な事前知識に依存している。 我々は、必ずしも因果知識に依存しない新たな因果バンディットアルゴリズムを定式化する。
  論文  参考訳（メタデータ） (2020-09-16T20:08:03Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。 ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。 このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
  論文  参考訳（メタデータ） (2020-06-11T20:23:43Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。 我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
  論文  参考訳（メタデータ） (2020-03-05T21:29:27Z)
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity [83.81297078039836]
  インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。 我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
  論文  参考訳（メタデータ） (2020-02-03T04:58:51Z)

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

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