論文の概要: 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問題を純粋に探索するための議論とアルゴリズムについて述べる。

関連論文リスト

• 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)
• An $\alpha$-No-Regret Algorithm For Graphical Bilinear Bandits [15.29268368415036]
  本稿では,グラフィカルビリニア帯域問題に対する最初の後悔に基づくアプローチを提案する。 本稿では,不確実性に直面した楽観主義の原理を用いて,バイリニアバンディットに対する最初の後悔に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T12:55:17Z)
• Instance-Dependent Regret Analysis of Kernelized Bandits [19.252319300590653]
  雑音の多いゼロオーダーオーラを問合せするための適応戦略を設計することを含む、カーネル化された帯域幅問題について検討する。 正規化された累積後悔を解消する(関数クラス上)アルゴリズムに対して、不一致依存的後悔の下限を導出する。
  論文  参考訳（メタデータ） (2022-03-12T00:53:59Z)
• 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)

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

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