論文の概要: Causal Bandits on General Graphs

• arxiv url: http://arxiv.org/abs/2107.02772v1
• Date: Tue, 6 Jul 2021 17:29:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-07 13:59:33.726665
• Title: Causal Bandits on General Graphs
• Title（参考訳）: 一般グラフ上の因果的バンディット
• Authors: Aurghya Maiti, Vineet Nair, Gaurav Sinha
• Abstract要約: 本稿では、因果グラフのみによって指定された因果ベイズネットワーク(CBN)における最良の介入を決定する問題について検討する。 本稿では,原子間干渉や観測不可能な変数を含む半マルコフ因果グラフを入力として用いた,簡単な後悔最小化アルゴリズムを提案する。 この結果から,提案アルゴリズムの単純後悔保証は,因果グラフのより微妙な構造的制約を考慮すれば改善できることがわかった。
• 参考スコア（独自算出の注目度）: 1.4502611532302039
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the problem of determining the best intervention in a Causal Bayesian Network (CBN) specified only by its causal graph. We model this as a stochastic multi-armed bandit (MAB) problem with side-information, where the interventions correspond to the arms of the bandit instance. First, we propose a simple regret minimization algorithm that takes as input a semi-Markovian causal graph with atomic interventions and possibly unobservable variables, and achieves $\tilde{O}(\sqrt{M/T})$ expected simple regret, where $M$ is dependent on the input CBN and could be very small compared to the number of arms. We also show that this is almost optimal for CBNs described by causal graphs having an $n$-ary tree structure. Our simple regret minimization results, both upper and lower bound, subsume previous results in the literature, which assumed additional structural restrictions on the input causal graph. In particular, our results indicate that the simple regret guarantee of our proposed algorithm can only be improved by considering more nuanced structural restrictions on the causal graph. Next, we propose a cumulative regret minimization algorithm that takes as input a general causal graph with all observable nodes and atomic interventions and performs better than the optimal MAB algorithm that does not take causal side-information into account. We also experimentally compare both our algorithms with the best known algorithms in the literature. To the best of our knowledge, this work gives the first simple and cumulative regret minimization algorithms for CBNs with general causal graphs under atomic interventions and having unobserved confounders.
• Abstract（参考訳）: 因果グラフのみによって指定された因果ベイズネットワーク(cbn)における最善の介入を決定する問題について検討する。 我々は、これをサイド情報を伴う確率的多腕バンディット(mab)問題としてモデル化し、介入はバンディットインスタンスの腕に対応する。 まず,半マルコフ的因果グラフの入力として原子介入や観測不可能な変数を考慮し,入力されたCBNに依存する$M$が,アーム数に比べて非常に小さいような単純な後悔を$\tilde{O}(\sqrt{M/T})$で達成する,簡単な後悔最小化アルゴリズムを提案する。 また、これは、$n$-ary木構造を持つ因果グラフによって記述されるCBNに対してほぼ最適であることを示す。 我々の単純な後悔の最小化の結果は、上界と下界の両方で、入力因果グラフに付加的な構造的制約を仮定する文献に先行する。 特に,提案アルゴリズムの単純な後悔保証は,因果グラフに対するよりニュアンス的な構造制約を考慮することでのみ改善できることを示す。 次に,すべての可観測ノードとアトミック介入を持つ一般的な因果グラフを入力とし,因果関係情報を考慮していない最適なmabアルゴリズムよりも優れた処理を行う累積的後悔最小化アルゴリズムを提案する。 また,両アルゴリズムを文献上で最もよく知られたアルゴリズムと比較した。 私たちの知る限りでは、この研究は原子の介入の下で一般的な因果グラフを持つcbnに対する最初の単純で累積的な後悔の最小化アルゴリズムを提供する。

関連論文リスト

• Confounded Budgeted Causal Bandits [28.199741662190203]
  基礎となる因果グラフをモデルとした環境における「良い」介入の学習問題について検討する。 良い介入は報酬を最大化する介入を指す。 一般因果グラフにおける累積後悔を最小限に抑えるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-15T10:26:13Z)
• Combinatorial Causal Bandits without Graph Skeleton [12.615590470530227]
  グラフ構造を持たないCCB問題を二元一般因果モデルとBGLM上で検討する。 グラフスケルトンがなくても,BGLMに対する後悔のアルゴリズムを設計し,期待された後悔の程度でO(sqrtTln T)を達成していることを示す。 我々は、重量ギャップの仮定を除去するために、$O(Tfrac23ln T)$ regret の別のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T03:45:17Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Verification and search algorithms for causal DAGs [11.038866111306728]
  クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。 我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。 この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-30T15:52:30Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• The Performance of the MLE in the Bradley-Terry-Luce Model in $\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
  我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。 導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
  論文  参考訳（メタデータ） (2021-10-20T23:46:35Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Budgeted and Non-budgeted Causal Bandits [2.9005223064604078]
  因果グラフで良い介入を学ぶことは、サイド情報を持つマルチアームのバンディット問題としてモデル化することができる。 介入コストに基づいて観察と介入を最適にトレードオフする単純な後悔を最小限に抑えるアルゴリズムを提案する。 本研究は,現在の文献で最もよく知られた境界と比較し,実験的に検証した。
  論文  参考訳（メタデータ） (2020-12-13T13:31:14Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)

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

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