論文の概要: Learning Good Interventions in Causal Graphs via Covering
- arxiv url: http://arxiv.org/abs/2305.04638v1
- Date: Mon, 8 May 2023 11:35:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-09 14:40:18.199489
- Title: Learning Good Interventions in Causal Graphs via Covering
- Title(参考訳): 被覆による因果グラフのよい介入の学習
- Authors: Ayush Sawarni, Rahul Madhavan, Gaurav Sinha, and Siddharth Barman
- Abstract要約: A$の最適介入は、グラフ内の指定された報酬変数の期待値を最大化するものである。
簡単な後悔のために、$widetildeO(sqrtN/T)$の単純な後悔保証を確立する。
また、事前の作業を超えて、観測されていない変数を持つ因果グラフに対する単純な後悔の保証も達成します。
- 参考スコア(独自算出の注目度): 12.512036656559685
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the causal bandit problem that entails identifying a near-optimal
intervention from a specified set $A$ of (possibly non-atomic) interventions
over a given causal graph. Here, an optimal intervention in ${A}$ is one that
maximizes the expected value for a designated reward variable in the graph, and
we use the standard notion of simple regret to quantify near optimality.
Considering Bernoulli random variables and for causal graphs on $N$ vertices
with constant in-degree, prior work has achieved a worst case guarantee of
$\widetilde{O} (N/\sqrt{T})$ for simple regret. The current work utilizes the
idea of covering interventions (which are not necessarily contained within
${A}$) and establishes a simple regret guarantee of
$\widetilde{O}(\sqrt{N/T})$. Notably, and in contrast to prior work, our simple
regret bound depends only on explicit parameters of the problem instance. We
also go beyond prior work and achieve a simple regret guarantee for causal
graphs with unobserved variables. Further, we perform experiments to show
improvements over baselines in this setting.
- Abstract(参考訳): 本研究では,ある因果グラフ上のA$の(おそらく非原子的な)介入から,最適に近い介入を特定するための因果バンディット問題を考察する。
ここで、${a}$ の最適介入は、グラフ内の指定された報奨変数の期待値を最大化するものであり、我々は、至近の最適性を定量化するために、simple regret の標準的な概念を用いる。
ベルヌーイ確率変数とn$頂点の因果グラフを考えると、先行研究は単純な後悔に対して$\widetilde{o} (n/\sqrt{t})$という最悪のケース保証を達成した。
現在の研究は、介入をカバーするというアイデア(必ずしも${A}$に含まれない)を利用し、$\widetilde{O}(\sqrt{N/T})$の単純な後悔の保証を確立する。
特に、以前の作業とは対照的に、単純な後悔は問題インスタンスの明示的なパラメータにのみ依存します。
また、事前の作業を超えて、観測されていない変数を持つ因果グラフに対する単純な後悔の保証も達成します。
さらに,この設定におけるベースラインの改善を示す実験を行った。
関連論文リスト
- Linear Causal Bandits: Unknown Graph and Soft Interventions [18.412177974475526]
因果バンディットのアルゴリズムを 設計するのは 2つの前提に依る
その一般的な形式、すなわち未知グラフと未知の介入モデルにおける問題は、まだ未解決のままである。
本稿は、この問題に対処し、N$ノードを持つグラフにおいて、最大$d$と最大$L$の因果経路長を持つグラフにおいて、$T$相互作用が後悔の上限スケールをラウンド化することを示す。
論文 参考訳(メタデータ) (2024-11-04T18:50:39Z) - Confounded Budgeted Causal Bandits [28.199741662190203]
基礎となる因果グラフをモデルとした環境における「良い」介入の学習問題について検討する。
良い介入は報酬を最大化する介入を指す。
一般因果グラフにおける累積後悔を最小限に抑えるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-01-15T10:26:13Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳(メタデータ) (2023-06-05T15:35:00Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-19T01:09:24Z) - 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) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳(メタデータ) (2022-03-03T02:55:55Z) - Causal Bandits on General Graphs [1.4502611532302039]
本稿では、因果グラフのみによって指定された因果ベイズネットワーク(CBN)における最良の介入を決定する問題について検討する。
本稿では,原子間干渉や観測不可能な変数を含む半マルコフ因果グラフを入力として用いた,簡単な後悔最小化アルゴリズムを提案する。
この結果から,提案アルゴリズムの単純後悔保証は,因果グラフのより微妙な構造的制約を考慮すれば改善できることがわかった。
論文 参考訳(メタデータ) (2021-07-06T17:29:45Z) - Intervention Efficient Algorithms for Approximate Learning of Causal
Graphs [22.401163479802094]
我々は、潜時の存在下で観察された変数の集合間の因果関係を学習する問題を研究する。
我々の目標は、介入の最小限の費用で、すべての因果関係や祖先関係の方向性を$G$で回収することです。
我々のアルゴリズムは効率的な介入設計と低コストな分離集合系の設計を組み合わせる。
論文 参考訳(メタデータ) (2020-12-27T17:08:46Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳(メタデータ) (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。