論文の概要: Adaptively Exploiting d-Separators with Causal Bandits

• arxiv url: http://arxiv.org/abs/2202.05100v1
• Date: Thu, 10 Feb 2022 15:39:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-11 15:21:29.461198
• Title: Adaptively Exploiting d-Separators with Causal Bandits
• Title（参考訳）: 因果バンディットを用いた適応型d-セパレータ
• Authors: Blair Bilodeau, Linbo Wang, Daniel M. Roy
• Abstract要約: 我々は、(a)d-セパレータが観測されたときの最適後悔を同時に達成し、(b)観測変数がd-セパレータでないときの後悔を著しく小さくするアルゴリズムを提案する。 我々のアルゴリズムは、d-セパレータが観測されるかどうかのオラクルの知識を必要としない。
• 参考スコア（独自算出の注目度）: 15.551812811058708
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-armed bandit problems provide a framework to identify the optimal intervention over a sequence of repeated experiments. Without additional assumptions, minimax optimal performance (measured by cumulative regret) is well-understood. With access to additional observed variables that d-separate the intervention from the outcome (i.e., they are a d-separator), recent causal bandit algorithms provably incur less regret. However, in practice it is desirable to be agnostic to whether observed variables are a d-separator. Ideally, an algorithm should be adaptive; that is, perform nearly as well as an algorithm with oracle knowledge of the presence or absence of a d-separator. In this work, we formalize and study this notion of adaptivity, and provide a novel algorithm that simultaneously achieves (a) optimal regret when a d-separator is observed, improving on classical minimax algorithms, and (b) significantly smaller regret than recent causal bandit algorithms when the observed variables are not a d-separator. Crucially, our algorithm does not require any oracle knowledge of whether a d-separator is observed. We also generalize this adaptivity to other conditions, such as the front-door criterion.
• Abstract（参考訳）: マルチアームバンディット問題(英語版)は、反復実験の連続に対する最適な介入を特定するための枠組みを提供する。 追加の仮定がなければ、最小限の最適性能(累積的後悔によって測定される)はよく理解される。 結果からの介入をd-分離する追加の観測変数(d-セパレータ)へのアクセスにより、最近の因果バンディットアルゴリズムは明らかに後悔を少なくする。 しかし、実際には観測変数が d-分離子であるかどうかによらないことが望ましい。 理想的には、アルゴリズムは適応的であり、つまり、d-分離子の有無に関するオラクルの知識を持つアルゴリズムとほぼ同等の性能を発揮するべきである。 本研究では、適応性の概念を形式化し、研究し、同時に達成する新しいアルゴリズムを提供する。 (a)d-セパレータが観測されたときの最適後悔、古典的ミニマックスアルゴリズムの改善、 (b) 観察変数がd-セパレータでない場合, 最近の因果バンディットアルゴリズムに比べ有意に少ない。 重要なことは、我々のアルゴリズムは、d-セパレータが観測されているかどうかについてのオラクルの知識を必要としない。 また,この適応性をフロントドア基準など他の条件にも一般化する。

関連論文リスト

• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Convergent plug-and-play with proximal denoiser and unconstrained regularization parameter [12.006511319607473]
  本稿では,Plug-Play(PGD)アルゴリズムの収束性について述べる。 最近の研究は、証明(DRS)による収束を探求している。 まず、新しい収束証明を提供する。 正規化にいかなる制限も課さないDSS。 第2に、画像復元の精度を高めるPGDの緩和版について検討する。
  論文  参考訳（メタデータ） (2023-11-02T13:18:39Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Accelerated and instance-optimal policy evaluation with linear function approximation [17.995515643150657]
  既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。 我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
  論文  参考訳（メタデータ） (2021-12-24T17:21:04Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits [27.09804256642197]
  我々はFrank-Wolfeアルゴリズムにインスパイアされたアルゴリズム群を紹介する。 我々は幅広い問題に対して新しい明示的アルゴリズムを構築した。 我々はこの現象を洞察に富んだおもちゃの問題で説明する。
  論文  参考訳（メタデータ） (2021-10-18T09:36:36Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Nonparametric adaptive active learning under local smoothness condition [0.76146285961466]
  本稿では,最小仮定の非パラメトリック環境における適応型アクティブラーニングの問題に対処する。 従来知られていたアルゴリズムよりも,より一般的な仮定の下で有効な新しいアルゴリズムを提案する。 我々のアルゴリズムは最小収束率を達成し、最もよく知られた非適応アルゴリズムと同等に機能する。
  論文  参考訳（メタデータ） (2021-02-22T14:47:21Z)
• Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence [29.189409618561964]
  我々は単調演算子を用いた変分不等式の新しい適応アルゴリズムを開発した。 我々のアルゴリズムは未知の問題パラメータに自動的に適応する。 我々のアルゴリズムは普遍的であり、同時に最適な収束率を達成することを示す。
  論文  参考訳（メタデータ） (2020-10-15T14:44:26Z)
• Comparator-adaptive Convex Bandits [77.43350984086119]
  我々は,コンパレータのノルムが小さい場合,残差が小さい凸バンディットアルゴリズムを開発した。 アイデアを拡張して、リプシッツや滑らかな損失関数で包帯を凸する。
  論文  参考訳（メタデータ） (2020-07-16T16:33:35Z)

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

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