論文の概要: Confounded Budgeted Causal Bandits
- arxiv url: http://arxiv.org/abs/2401.07578v1
- Date: Mon, 15 Jan 2024 10:26:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-17 17:20:17.721827
- Title: Confounded Budgeted Causal Bandits
- Title(参考訳): 予算付カウンサルバンドの結成
- Authors: Fateme Jamshidi, Jalal Etesami, Negar Kiyavash
- Abstract要約: 基礎となる因果グラフをモデルとした環境における「良い」介入の学習問題について検討する。
良い介入は報酬を最大化する介入を指す。
一般因果グラフにおける累積後悔を最小限に抑えるアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 28.199741662190203
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of learning 'good' interventions in a stochastic
environment modeled by its underlying causal graph. Good interventions refer to
interventions that maximize rewards. Specifically, we consider the setting of a
pre-specified budget constraint, where interventions can have non-uniform
costs. We show that this problem can be formulated as maximizing the expected
reward for a stochastic multi-armed bandit with side information. We propose an
algorithm to minimize the cumulative regret in general causal graphs. This
algorithm trades off observations and interventions based on their costs to
achieve the optimal reward. This algorithm generalizes the state-of-the-art
methods by allowing non-uniform costs and hidden confounders in the causal
graph. Furthermore, we develop an algorithm to minimize the simple regret in
the budgeted setting with non-uniform costs and also general causal graphs. We
provide theoretical guarantees, including both upper and lower bounds, as well
as empirical evaluations of our algorithms. Our empirical results showcase that
our algorithms outperform the state of the art.
- Abstract(参考訳): 基礎となる因果グラフをモデルとした確率的環境における「良い」介入の学習問題について検討する。
良い介入は報酬を最大化する介入を指す。
具体的には、介入が一様でないコストを伴うような、予め規定された予算制約の設定を検討する。
この問題を,確率的多腕バンディットに対する期待報酬の最大化として定式化できることを示す。
一般因果グラフにおける累積後悔を最小限に抑えるアルゴリズムを提案する。
このアルゴリズムは、最適報酬を達成するための費用に基づいて、観察と介入をトレードオフする。
このアルゴリズムは、不均一なコストと隠れた共同創設者を因果グラフで許容することで、最先端の手法を一般化する。
さらに,非一様コストと汎用因果グラフを用いて,予算設定における単純な後悔を最小限に抑えるアルゴリズムを開発した。
我々は,上界と下界の両方を含む理論的保証と,アルゴリズムの実証的評価を提供する。
実験の結果、私たちのアルゴリズムは芸術の状態を上回ります。
関連論文リスト
- The Minimal Search Space for Conditional Causal Bandits [0.18124328823188351]
因果知識は意思決定問題を支援するのに使える。
本稿では、最適条件介入を含むことが保証される最小限のノードのグラフィカルな特徴について述べる。
次に、この最小のノード群を特定するために、O(|V| + |E|)$の時間複雑性を持つ効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2025-02-10T15:45:18Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。
我々は、ETCアルゴリズムの最適レートを$T$で導出し、探索とエクスプロイトのバランスをとることで、このレートを実現できることを示す。
本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-19T15:29:32Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T17:26:39Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-08-26T16:21:31Z) - Causal Bandits on General Graphs [1.4502611532302039]
本稿では、因果グラフのみによって指定された因果ベイズネットワーク(CBN)における最良の介入を決定する問題について検討する。
本稿では,原子間干渉や観測不可能な変数を含む半マルコフ因果グラフを入力として用いた,簡単な後悔最小化アルゴリズムを提案する。
この結果から,提案アルゴリズムの単純後悔保証は,因果グラフのより微妙な構造的制約を考慮すれば改善できることがわかった。
論文 参考訳(メタデータ) (2021-07-06T17:29:45Z) - Budgeted and Non-budgeted Causal Bandits [2.9005223064604078]
因果グラフで良い介入を学ぶことは、サイド情報を持つマルチアームのバンディット問題としてモデル化することができる。
介入コストに基づいて観察と介入を最適にトレードオフする単純な後悔を最小限に抑えるアルゴリズムを提案する。
本研究は,現在の文献で最もよく知られた境界と比較し,実験的に検証した。
論文 参考訳(メタデータ) (2020-12-13T13:31:14Z) - Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
分散分類におけるAUCのためのハードしきい値決定アルゴリズムを開発した。
提案アルゴリズムの有効性と有効性を示す実験を行った。
論文 参考訳(メタデータ) (2020-11-04T16:49:29Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Budget-Constrained Bandits over General Cost and Reward Distributions [32.63624728528415]
我々は,各アームがランダムなコストを発生させ,その見返りにランダムな報酬を与える,予算制約付きバンディット問題を考える。
ある$gamma > 0$ に対して位数 $(2+gamma)$ のモーメントが存在するならば、$O(log B)$ regret は予算 $B>0$ に対して達成可能である。
論文 参考訳(メタデータ) (2020-02-29T23:50:08Z) - Fair Correlation Clustering [92.15492066925977]
相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。
相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
論文 参考訳(メタデータ) (2020-02-06T14:28:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。