論文の概要: Causal Bandits for Linear Structural Equation Models
- arxiv url: http://arxiv.org/abs/2208.12764v1
- Date: Fri, 26 Aug 2022 16:21:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-29 12:36:47.647018
- Title: Causal Bandits for Linear Structural Equation Models
- Title（参考訳）: 線形構造方程式モデルのための因果帯域
- Authors: Burak Varici, Karthikeyan Shanmugam, Prasanna Sattigeri, and Ali Tajer
- Abstract要約: 本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 58.2875460517691
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the problem of designing an optimal sequence of
interventions in a causal graphical model to minimize the cumulative regret
with respect to the best intervention in hindsight. This is, naturally, posed
as a causal bandit problem. The focus is on causal bandits for linear
structural equation models (SEMs) and soft interventions. It is assumed that
the graph's structure is known, and it has $N$ nodes. Two linear mechanisms,
one soft intervention and one observational, are assumed for each node, giving
rise to $2^N$ possible interventions. The existing causal bandit algorithms
assume that at least the interventional distributions of the reward node's
parents are fully specified. However, there are $2^N$ such distributions (one
corresponding to each intervention), acquiring which becomes prohibitive even
in moderate-sized graphs. This paper dispenses with the assumption of knowing
these distributions. Two algorithms are proposed for the frequentist
(UCB-based) and Bayesian (Thompson Sampling-based) settings. The key idea of
these algorithms is to avoid directly estimating the $2^N$ reward distributions
and instead estimate the parameters that fully specify the SEMs (linear in $N$)
and use them to compute the rewards. In both algorithms, under boundedness
assumptions on noise and the parameter space, the cumulative regrets scale as
$\tilde{\cal O} ((2d)^L L \sqrt{T})$, where $d$ is the graph's maximum degree,
and $L$ is the length of its longest causal path.
- Abstract（参考訳）: 本稿では,過去最良介入に対する累積後悔を最小限に抑えるために,因果グラフモデルにおける最適な介入系列を設計する問題を考察する。
これは当然、因果的盗賊問題として提起される。
焦点は線形構造方程式モデル(SEM)とソフト介入のための因果包帯である。
グラフの構造は知られており、ノードは$N$である。
2つの線形機構、1つのソフト介入と1つの観察機構が各ノードに対して仮定され、2^n$の介入が可能となる。
既存の因果バンディットアルゴリズムは、少なくとも報酬ノードの両親の介入分布が完全に特定されていると仮定する。
しかし、そのような分布(各介入に対応するもの)は2^N$であり、中程度のグラフでも禁止となる。
本稿では,これらの分布を知るという仮定を省略する。
頻繁性(UCBベース)とベイズ性(トンプソンサンプリングベース)の2つのアルゴリズムを提案する。
これらのアルゴリズムの鍵となる考え方は、$2^N$の報酬分布を直接見積もることを避け、代わりにSEMを完全に指定したパラメータ($N$の線形)を推定し、報酬を計算することである。
どちらのアルゴリズムにおいても、雑音とパラメータ空間の有界性仮定の下では、累積的後悔は$\tilde{\cal o} ((2d)^l l \sqrt{t})$であり、ここで$d$はグラフの最大次数、$l$は最長因果経路の長さである。
関連論文リスト
- Linear Causal Bandits: Unknown Graph and Soft Interventions [18.412177974475526]
因果バンディットのアルゴリズムを 設計するのは 2つの前提に依る
その一般的な形式、すなわち未知グラフと未知の介入モデルにおける問題は、まだ未解決のままである。
本稿は、この問題に対処し、N$ノードを持つグラフにおいて、最大$d$と最大$L$の因果経路長を持つグラフにおいて、$T$相互作用が後悔の上限スケールをラウンド化することを示す。
論文 参考訳（メタデータ） (2024-11-04T18:50:39Z) - Improved Bound for Robust Causal Bandits with Linear Models [16.60875994745622]
本稿では,時間的モデル変動に直面した因果包帯のロバスト性について検討する。
提案アルゴリズムは,$C$が$o(sqrtT)$の場合に,ほぼ最適な$tildemathcalO(sqrtT)$後悔を達成する。
論文 参考訳（メタデータ） (2024-05-13T14:41:28Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Robust Causal Bandits for Linear Models [20.028245872662843]
因果系における報酬関数を最適化するための実験の逐次設計は、因果包帯における介入の逐次設計(CB)により効果的にモデル化できる。
本稿では,このようなモデルゆらぎに対するCBの頑健性について述べる。
累積後悔は設計基準として採用され、その目的は、因果モデル全体とその変動を意識したオラクルに対して最小の累積後悔を引き起こす一連の介入を設計することである。
論文 参考訳（メタデータ） (2023-10-30T17:58:01Z) - Learning Good Interventions in Causal Graphs via Covering [12.512036656559685]
A$の最適介入は、グラフ内の指定された報酬変数の期待値を最大化するものである。
簡単な後悔のために、$widetildeO(sqrtN/T)$の単純な後悔保証を確立する。
また、事前の作業を超えて、観測されていない変数を持つ因果グラフに対する単純な後悔の保証も達成します。
論文 参考訳（メタデータ） (2023-05-08T11:35:22Z) - Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳（メタデータ） (2023-04-25T09:31:20Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Causal Bandits on General Graphs [1.4502611532302039]
本稿では、因果グラフのみによって指定された因果ベイズネットワーク(CBN)における最良の介入を決定する問題について検討する。
本稿では,原子間干渉や観測不可能な変数を含む半マルコフ因果グラフを入力として用いた,簡単な後悔最小化アルゴリズムを提案する。
この結果から,提案アルゴリズムの単純後悔保証は,因果グラフのより微妙な構造的制約を考慮すれば改善できることがわかった。
論文 参考訳（メタデータ） (2021-07-06T17:29:45Z) - Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。
我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
論文 参考訳（メタデータ） (2020-02-29T02:02:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。