論文の概要: 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$に対してサブ線形後悔を維持する。

関連論文リスト

• Improved Bound for Robust Causal Bandits with Linear Models [16.60875994745622]
  本稿では,時間的モデル変動に直面した因果包帯のロバスト性について検討する。 提案アルゴリズムは,$C$が$o(sqrtT)$の場合に,ほぼ最適な$tildemathcalO(sqrtT)$後悔を達成する。
  論文  参考訳（メタデータ） (2024-05-13T14:41:28Z)
• Linear bandits with polylogarithmic minimax regret [8.97780713904412]
  本研究では,未知ベクトルに近づいた単位球上での動作を選択すると,サブガウス雑音パラメータが線形に消滅する線形帯域の雑音モデルについて検討する。 我々は,この問題に対するアルゴリズムを導入し,この最小限の後悔のスケーリングを,時間軸で$log3(T)$,時間軸で$T$として示す。
  論文  参考訳（メタデータ） (2024-02-19T10:56:47Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• 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)

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

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