論文の概要: Combinatorial Causal Bandits without Graph Skeleton

• arxiv url: http://arxiv.org/abs/2301.13392v3
• Date: Sat, 16 Sep 2023 13:55:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2023-09-20 00:49:06.910612
• Title: Combinatorial Causal Bandits without Graph Skeleton
• Title（参考訳）: グラフ骨格のない組合せ因果帯域
• Authors: Shi Feng, Nuoya Xiong, Wei Chen
• Abstract要約: 因果的包帯(CCB)では、学習エージェントが各ラウンドの変数のサブセットを選択して介入し、観測された変数からフィードバックを収集し、期待される後悔やサンプルの複雑さを最小限に抑える。 従来の研究は、一般因果モデルと二元一般化線形モデル(BGLM)の両方でこの問題を研究する。 本稿では,二元一般因果モデルとBGLMのグラフ構造を持たないCCB問題を考察する。
• 参考スコア（独自算出の注目度）: 14.178659419111897
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In combinatorial causal bandits (CCB), the learning agent chooses a subset of variables in each round to intervene and collects feedback from the observed variables to minimize expected regret or sample complexity. Previous works study this problem in both general causal models and binary generalized linear models (BGLMs). However, all of them require prior knowledge of causal graph structure. This paper studies the CCB problem without the graph structure on binary general causal models and BGLMs. We first provide an exponential lower bound of cumulative regrets for the CCB problem on general causal models. To overcome the exponentially large space of parameters, we then consider the CCB problem on BGLMs. We design a regret minimization algorithm for BGLMs even without the graph skeleton and show that it still achieves $O(\sqrt{T}\ln T)$ expected regret. This asymptotic regret is the same as the state-of-art algorithms relying on the graph structure. Moreover, we sacrifice the regret to $O(T^{\frac{2}{3}}\ln T)$ to remove the weight gap covered by the asymptotic notation. At last, we give some discussions and algorithms for pure exploration of the CCB problem without the graph structure.
• Abstract（参考訳）: 組み合わせ因果帯域(CCB)において、学習エージェントは各ラウンドの変数のサブセットを選択して介入し、観測された変数からフィードバックを収集し、期待される後悔やサンプルの複雑さを最小限に抑える。 従来の研究は、一般因果モデルとバイナリ一般化線形モデル(BGLM)の両方でこの問題を研究する。 しかし、それら全ては因果グラフ構造の事前知識を必要とする。 本稿では,二元一般因果モデルとBGLMのグラフ構造を持たないCCB問題を考察する。 まず、一般的な因果モデルにおけるCCB問題に対する累積的後悔の指数的下限を提供する。 指数関数的に大きなパラメータ空間を克服するために、BGLM 上の CCB 問題を考える。 グラフスケルトンがなくても,BGLMに対する後悔最小化アルゴリズムを設計し,O(\sqrt{T}\ln T)$期待の後悔を実現することを示す。 この漸近的後悔は、グラフ構造に依存する最先端のアルゴリズムと同じである。 さらに、漸近的表記法でカバーされる重量ギャップを取り除くために、$O(T^{\frac{2}{3}}\ln T)$に対する後悔を犠牲にする。 最後に,グラフ構造を使わずにCCB問題を純粋に探索するための議論とアルゴリズムについて述べる。

関連論文リスト

• Linear Causal Bandits: Unknown Graph and Soft Interventions [18.412177974475526]
  因果バンディットのアルゴリズムを 設計するのは 2つの前提に依る その一般的な形式、すなわち未知グラフと未知の介入モデルにおける問題は、まだ未解決のままである。 本稿は、この問題に対処し、N$ノードを持つグラフにおいて、最大$d$と最大$L$の因果経路長を持つグラフにおいて、$T$相互作用が後悔の上限スケールをラウンド化することを示す。
  論文  参考訳（メタデータ） (2024-11-04T18:50:39Z)
• Improved Bound for Robust Causal Bandits with Linear Models [16.60875994745622]
  本稿では,時間的モデル変動に直面した因果包帯のロバスト性について検討する。 提案アルゴリズムは,$C$が$o(sqrtT)$の場合に,ほぼ最適な$tildemathcalO(sqrtT)$後悔を達成する。
  論文  参考訳（メタデータ） (2024-05-13T14:41:28Z)
• Robust Causal Bandits for Linear Models [20.028245872662843]
  因果系における報酬関数を最適化するための実験の逐次設計は、因果包帯における介入の逐次設計(CB)により効果的にモデル化できる。 本稿では,このようなモデルゆらぎに対するCBの頑健性について述べる。 累積後悔は設計基準として採用され、その目的は、因果モデル全体とその変動を意識したオラクルに対して最小の累積後悔を引き起こす一連の介入を設計することである。
  論文  参考訳（メタデータ） (2023-10-30T17:58:01Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Combinatorial Causal Bandits [25.012065471684025]
  因果的包帯において、学習エージェントは、各ラウンドで最大$K$変数を選択して介入し、ターゲット変数$Y$に対する期待される後悔を最小限にすることを目的としている。 因果モデルの簡潔なパラメトリック表現を用いた二元一般化線形モデル(BGLM)の文脈下で検討する。 マルコフ BGLM に対するアルゴリズム BGLM-OFU を最大推定法に基づいて提案し,O(sqrtTlog T)$ regret, ここでは$T$ が時間地平線となることを示す。
  論文  参考訳（メタデータ） (2022-06-04T14:14:58Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• The Performance of the MLE in the Bradley-Terry-Luce Model in $\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
  我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。 導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
  論文  参考訳（メタデータ） (2021-10-20T23:46:35Z)
• Causal Bandits on General Graphs [1.4502611532302039]
  本稿では、因果グラフのみによって指定された因果ベイズネットワーク(CBN)における最良の介入を決定する問題について検討する。 本稿では,原子間干渉や観測不可能な変数を含む半マルコフ因果グラフを入力として用いた,簡単な後悔最小化アルゴリズムを提案する。 この結果から,提案アルゴリズムの単純後悔保証は,因果グラフのより微妙な構造的制約を考慮すれば改善できることがわかった。
  論文  参考訳（メタデータ） (2021-07-06T17:29:45Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。 学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。 コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
  論文  参考訳（メタデータ） (2021-06-18T15:01:01Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)

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

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