論文の概要: Causal Bandits without Graph Learning

• arxiv url: http://arxiv.org/abs/2301.11401v1
• Date: Thu, 26 Jan 2023 20:27:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-30 17:16:25.246547
• Title: Causal Bandits without Graph Learning
• Title（参考訳）: グラフ学習のない因果帯域
• Authors: Mikhail Konobeev, Jalal Etesami, Negar Kiyavash
• Abstract要約: 我々は,原子間干渉を用いた報酬ノードの親ノード探索のための効率的なアルゴリズムを開発した。 報奨ノードが複数の親を持つ場合にアルゴリズムを拡張します。
• 参考スコア（独自算出の注目度）: 28.021500949026766
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the causal bandit problem when the causal graph is unknown and develop an efficient algorithm for finding the parent node of the reward node using atomic interventions. We derive the exact equation for the expected number of interventions performed by the algorithm and show that under certain graphical conditions it could perform either logarithmically fast or, under more general assumptions, slower but still sublinearly in the number of variables. We formally show that our algorithm is optimal as it meets the universal lower bound we establish for any algorithm that performs atomic interventions. Finally, we extend our algorithm to the case when the reward node has multiple parents. Using this algorithm together with a standard algorithm from bandit literature leads to improved regret bounds.
• Abstract（参考訳）: 因果グラフが未知な場合の因果バンディット問題を調べ,原子間介入を用いて報奨ノードの親ノードを探索する効率的なアルゴリズムを開発した。 アルゴリズムが実施する介入回数の正確な式を導出し、あるグラフィカルな条件下では対数的に速く、あるいはより一般的な仮定の下では、変数数では遅いが、いまだサブ線形に実行可能であることを示す。 我々は、原子間干渉を行うアルゴリズムに対して確立した普遍的な下限を満たすように、我々のアルゴリズムが最適であることを示す。 最後に、報酬ノードが複数の親を持つ場合にアルゴリズムを拡張します。 このアルゴリズムとバンディット文学の標準的なアルゴリズムを併用すると、後悔の限界が改善される。

関連論文リスト

• Nearest Neighbour with Bandit Feedback [4.9094025705644695]
  我々のアルゴリズムは、データ生成プロセスに関する仮定が全くなされていない完全に逆向きな設定を処理します。 ユークリッド空間におけるバンドイト問題に適用した場合,アルゴリズムに対する一般的な後悔と解析を行う。
  論文  参考訳（メタデータ） (2023-06-23T20:09:01Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Causal Bandits with Unknown Graph Structure [24.58691421788476]
  因果グラフを知らずに新たな因果バンディットアルゴリズムを開発する。 我々のアルゴリズムは、因果樹、因果樹、および一般的な因果グラフに対してうまく機能する。
  論文  参考訳（メタデータ） (2021-06-05T23:41:38Z)
• Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
  有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。 We show that our method with depth $w$ run in $O(pw+3) $ time。 また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
  論文  参考訳（メタデータ） (2020-11-06T21:56:41Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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