論文の概要: Robust Causal Bandits for Linear Models
- arxiv url: http://arxiv.org/abs/2310.19794v2
- Date: Mon, 4 Mar 2024 22:32:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 01:48:41.545139
- Title: Robust Causal Bandits for Linear Models
- Title（参考訳）: 線形モデルのためのロバスト因果バンディット
- Authors: Zirui Yan, Arpan Mukherjee, Burak Var{\i}c{\i}, Ali Tajer
- Abstract要約: 因果系における報酬関数を最適化するための実験の逐次設計は、因果包帯における介入の逐次設計(CB)により効果的にモデル化できる。
本稿では,このようなモデルゆらぎに対するCBの頑健性について述べる。
累積後悔は設計基準として採用され、その目的は、因果モデル全体とその変動を意識したオラクルに対して最小の累積後悔を引き起こす一連の介入を設計することである。
- 参考スコア（独自算出の注目度）: 20.028245872662843
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sequential design of experiments for optimizing a reward function in causal
systems can be effectively modeled by the sequential design of interventions in
causal bandits (CBs). In the existing literature on CBs, a critical assumption
is that the causal models remain constant over time. However, this assumption
does not necessarily hold in complex systems, which constantly undergo temporal
model fluctuations. This paper addresses the robustness of CBs to such model
fluctuations. The focus is on causal systems with linear structural equation
models (SEMs). The SEMs and the time-varying pre- and post-interventional
statistical models are all unknown. Cumulative regret is adopted as the design
criteria, based on which the objective is to design a sequence of interventions
that incur the smallest cumulative regret with respect to an oracle aware of
the entire causal model and its fluctuations. First, it is established that the
existing approaches fail to maintain regret sub-linearity with even a few
instances of model deviation. Specifically, when the number of instances with
model deviation is as few as $T^\frac{1}{2L}$, where $T$ is the time horizon
and $L$ is the longest causal path in the graph, the existing algorithms will
have linear regret in $T$. Next, a robust CB algorithm is designed, and its
regret is analyzed, where upper and information-theoretic lower bounds on the
regret are established. Specifically, in a graph with $N$ nodes and maximum
degree $d$, under a general measure of model deviation $C$, the cumulative
regret is upper bounded by $\tilde{\mathcal{O}}(d^{L-\frac{1}{2}}(\sqrt{NT} +
NC))$ and lower bounded by $\Omega(d^{\frac{L}{2}-2}\max\{\sqrt{T},d^2C\})$.
Comparing these bounds establishes that the proposed algorithm achieves nearly
optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret when $C$ is $o(\sqrt{T})$ and
maintains sub-linear regret for a broader range of $C$.
- Abstract（参考訳）: 因果系における報酬関数を最適化するための実験の逐次設計は、因果包帯(CB)における介入のシーケンシャル設計によって効果的にモデル化することができる。
CBに関する既存の文献では、因果モデルが時間とともに一定であることが重要な仮定である。
しかし、この仮定は、常に時間モデルゆらぎを経る複雑なシステムでは必ずしも成り立たない。
本稿では,このようなモデル変動に対するCBの堅牢性について述べる。
焦点は線形構造方程式モデル(SEM)による因果系である。
SEMと時間変化の前・後統計モデルは、すべて不明である。
累積的後悔(cumulative regret)は設計基準として採用され、その目的は、因果モデル全体とそのゆらぎを認識したオラクルに対して、最小の累積後悔を引き起こす一連の介入を設計することである。
第一に, 既存手法ではモデル偏差の例さえあれば, 後悔する部分線形性が維持できないことが判明した。
特に、モデルの偏差を持つインスタンス数が$t^\frac{1}{2l}$で、$t$が時間軸であり、$l$がグラフの最長因果経路である場合、既存のアルゴリズムは、$t$で線形後悔する。
次に、ロバストなcbアルゴリズムを設計し、その後悔を解析し、後悔の上位及び情報理論的下限を設定する。
具体的には、$N$ノードと最大次数$d$のグラフにおいて、モデル偏差$C$の一般的な測度の下で、累積後悔は$\tilde{\mathcal{O}}(d^{L-\frac{1}{2}}(\sqrt{NT} + NC))$で上界、下界$\Omega(d^{\frac{L}{2}-2}\max\{\sqrt{T},d^2C\})$で下界となる。
これらの境界を比較すると、提案アルゴリズムは$C$が$o(\sqrt{T})$であるときにほぼ最適な$\tilde{\mathcal{O}}(\sqrt{T})$後悔を達成し、より広い範囲の$C$に対してサブ線形後悔を維持する。
関連論文リスト
- Linear Causal Bandits: Unknown Graph and Soft Interventions [18.412177974475526]
因果バンディットのアルゴリズムを 設計するのは 2つの前提に依る
その一般的な形式、すなわち未知グラフと未知の介入モデルにおける問題は、まだ未解決のままである。
本稿は、この問題に対処し、N$ノードを持つグラフにおいて、最大$d$と最大$L$の因果経路長を持つグラフにおいて、$T$相互作用が後悔の上限スケールをラウンド化することを示す。
論文 参考訳（メタデータ） (2024-11-04T18:50:39Z) - Beyond Closure Models: Learning Chaotic-Systems via Physics-Informed Neural Operators [78.64101336150419]
カオスシステムの長期的挙動を予測することは、気候モデリングなどの様々な応用に不可欠である。
このような完全解法シミュレーションに対する別のアプローチは、粗いグリッドを使用して、時間テキストモデルによってエラーを修正することである。
この制限を克服する物理インフォームド・ニューラル演算子(PINO)を用いたエンド・ツー・エンドの学習手法を提案する。
論文 参考訳（メタデータ） (2024-08-09T17:05:45Z) - Improved Bound for Robust Causal Bandits with Linear Models [16.60875994745622]
本稿では,時間的モデル変動に直面した因果包帯のロバスト性について検討する。
提案アルゴリズムは,$C$が$o(sqrtT)$の場合に,ほぼ最適な$tildemathcalO(sqrtT)$後悔を達成する。
論文 参考訳（メタデータ） (2024-05-13T14:41:28Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Provably Efficient Model-Free Constrained RL with Linear Function
Approximation [4.060731229044571]
我々は,大規模システムにおいても,サブリニア後悔とサブリニア制約違反を実現するための,最初のモデルフリーシミュレータフリーアルゴリズムを開発した。
本結果は,標準LSVI-UCBアルゴリズムの新たな適応により達成される。
論文 参考訳（メタデータ） (2022-06-23T17:54:31Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Model-Based Reinforcement Learning with Value-Targeted Regression [48.92439657407732]
我々は、遷移モデル $P$ が既知のモデルの族 $mathcalP$ に属する有限水平エピソード RL に焦点を当てる。
線形混合の特別な場合において、後悔束は $tildemathcalO(dsqrtH3T)$ という形を取る。
論文 参考訳（メタデータ） (2020-06-01T17:47:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。