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

• arxiv url: http://arxiv.org/abs/2301.13392v4
• Date: Sun, 29 Sep 2024 02:13:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-01 22:00:54.132617
• Title: Combinatorial Causal Bandits without Graph Skeleton
• Title（参考訳）: グラフ骨格のない組合せ因果帯域
• Authors: Shi Feng, Nuoya Xiong, Wei Chen,
• Abstract要約: グラフ構造を持たないCCB問題を二元一般因果モデルとBGLM上で検討する。 グラフスケルトンがなくても,BGLMに対する後悔のアルゴリズムを設計し,期待された後悔の程度でO(sqrtTln T)を達成していることを示す。 我々は、重量ギャップの仮定を除去するために、$O(Tfrac23ln T)$ regret の別のアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 12.615590470530227
• License:
• 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 or unrealistic assumptions. 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, as long as the causal graph satisfies a weight gap assumption. This asymptotic regret is the same as the state-of-art algorithms relying on the graph structure. Moreover, we propose another algorithm with $O(T^{\frac{2}{3}}\ln T)$ regret to remove the weight gap assumption.
• Abstract（参考訳）: 組み合わせ因果バンドイット(CCB)では、学習エージェントが各ラウンドの変数のサブセットを選択して介入し、観測された変数からフィードバックを収集し、期待される後悔やサンプルの複雑さを最小限に抑える。 従来の研究は、一般因果モデルとバイナリ一般化線形モデル(BGLM)の両方でこの問題を研究する。 しかし、これらは全て因果グラフ構造や非現実的な仮定に関する事前の知識を必要とする。 本稿では,二元一般因果モデルとBGLMのグラフ構造を持たないCCB問題を考察する。 まず、一般的な因果モデル上でのCCB問題に対する累積的後悔の指数的下限を提供する。 指数関数的に大きなパラメータ空間を克服するために、BGLM 上の CCB 問題を考察する。 グラフスケルトンがなくても,BGLMに対する後悔最小化アルゴリズムを設計し,因果グラフがウェイトギャップの仮定を満たす限り,O(\sqrt{T}\ln T)$期待後悔を実現することを示す。 この漸近的後悔は、グラフ構造に依存する最先端のアルゴリズムと同じである。 さらに,ウェイトギャップの仮定を取り除くために,$O(T^{\frac{2}{3}}\ln T)$ regret という別のアルゴリズムを提案する。

関連論文リスト

• Improved Bound for Robust Causal Bandits with Linear Models [16.60875994745622]
  本稿では,時間的モデル変動に直面した因果包帯のロバスト性について検討する。 提案アルゴリズムは,$C$が$o(sqrtT)$の場合に,ほぼ最適な$tildemathcalO(sqrtT)$後悔を達成する。
  論文  参考訳（メタデータ） (2024-05-13T14:41:28Z)
• Online Clustering of Bandits with Misspecified User Models [42.56440072468658]
  コンテキスト線形バンディット(Contextual linear bandit)は、与えられた腕の特徴を学習エージェントが各ラウンドで選択し、長期の累積報酬を最大化するオンライン学習問題である。 バンディットのクラスタリング(CB)と呼ばれる一連の研究は、ユーザの好みに対する協調効果を利用しており、古典的な線形バンディットアルゴリズムよりも大幅に改善されている。 本稿では,不特定ユーザモデル (CBMUM) による盗賊のクラスタリングに関する重要な問題を初めて提示する。 モデル誤特定による不正確なユーザの選好推定と誤クラスタリングを両立できる頑健なCBアルゴリズムRCLUMBとRCLUMBを考案した。
  論文  参考訳（メタデータ） (2023-10-04T10:40:50Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• 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 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)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)

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

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