論文の概要: Improved Bound for Robust Causal Bandits with Linear Models

• arxiv url: http://arxiv.org/abs/2405.07795v1
• Date: Mon, 13 May 2024 14:41:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-14 13:25:43.137542
• Title: Improved Bound for Robust Causal Bandits with Linear Models
• Title（参考訳）: 線形モデルを用いたロバストカウンサルバンドのバウンド改善
• Authors: Zirui Yan, Arpan Mukherjee, Burak Varıcı, Ali Tajer,
• Abstract要約: 本稿では,時間的モデル変動に直面した因果包帯のロバスト性について検討する。 提案アルゴリズムは,$C$が$o(sqrtT)$の場合に,ほぼ最適な$tildemathcalO(sqrtT)$後悔を達成する。
• 参考スコア（独自算出の注目度）: 16.60875994745622
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the robustness of causal bandits (CBs) in the face of temporal model fluctuations. This setting deviates from the existing literature's widely-adopted assumption of constant causal models. 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 and subject to variations over time. The goal is to design a sequence of interventions that incur the smallest cumulative regret compared to an oracle aware of the entire causal model and its fluctuations. A robust CB algorithm is proposed, and its cumulative regret is analyzed by establishing both upper and lower bounds on the regret. It is shown that in a graph with maximum in-degree $d$, length of the largest causal path $L$, and an aggregate model deviation $C$, the regret is upper bounded by $\tilde{\mathcal{O}}(d^{L-\frac{1}{2}}(\sqrt{T} + C))$ and lower bounded by $\Omega(d^{\frac{L}{2}-2}\max\{\sqrt{T}\; ,\; d^2C\})$. The proposed algorithm achieves nearly optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret when $C$ is $o(\sqrt{T})$, maintaining sub-linear regret for a broad range of $C$.
• Abstract（参考訳）: 本稿では,時間的モデルゆらぎに直面した原因帯域(CB)のロバスト性について検討する。 この設定は、既存の文献の定数因果モデルに対する広く受け入れられた仮定から逸脱している。 焦点は線形構造方程式モデル(SEM)による因果系である。 SEMと時間変化の前・後統計モデルは、すべて未知であり、時間とともに変動する。 目的は、因果モデル全体とそのゆらぎを認識したオラクルと比較して最小の累積後悔を引き起こす一連の介入を設計することである。 頑健なCBアルゴリズムを提案し、その累積的後悔を、その後悔の上下の境界を定め、解析する。 最大 in-degree $d$ のグラフでは、最大の因果経路 $L$ の長さと集合モデルの偏差 $C$ で、後悔は $\tilde{\mathcal{O}}(d^{L-\frac{1}{2}}(\sqrt{T} + C))$ で上界、下界 $\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)
• Linear bandits with polylogarithmic minimax regret [8.97780713904412]
  本研究では,未知ベクトルに近づいた単位球上での動作を選択すると,サブガウス雑音パラメータが線形に消滅する線形帯域の雑音モデルについて検討する。 我々は,この問題に対するアルゴリズムを導入し,この最小限の後悔のスケーリングを,時間軸で$log3(T)$,時間軸で$T$として示す。
  論文  参考訳（メタデータ） (2024-02-19T10:56:47Z)
• Robust Causal Bandits for Linear Models [20.028245872662843]
  因果系における報酬関数を最適化するための実験の逐次設計は、因果包帯における介入の逐次設計(CB)により効果的にモデル化できる。 本稿では,このようなモデルゆらぎに対するCBの頑健性について述べる。 累積後悔は設計基準として採用され、その目的は、因果モデル全体とその変動を意識したオラクルに対して最小の累積後悔を引き起こす一連の介入を設計することである。
  論文  参考訳（メタデータ） (2023-10-30T17:58:01Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• 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)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Model-Based Reinforcement Learning with Value-Targeted Regression [48.92439657407732]
  我々は、遷移モデル $P$ が既知のモデルの族 $mathcalP$ に属する有限水平エピソード RL に焦点を当てる。 線形混合の特別な場合において、後悔束は $tildemathcalO(dsqrtH3T)$ という形を取る。
  論文  参考訳（メタデータ） (2020-06-01T17:47:53Z)

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

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