論文の概要: Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals
- arxiv url: http://arxiv.org/abs/2407.00950v1
- Date: Mon, 1 Jul 2024 04:12:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-04 00:46:07.636471
- Title: Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals
- Title（参考訳）: 因果帯域:適応性のパレート最適フロンティア、線形帯域削減、未知のマルジナル周辺の制限
- Authors: Ziyi Liu, Idan Attias, Daniel M. Roy,
- Abstract要約: 条件付き良性環境と任意の環境下での学習性能におけるトレードオフの可能性について,上界と下界の整合性を証明した。
この問題を線形バンディット設定に還元することで、最初に因果バンディットのインスタンス依存境界を求める。
- 参考スコア（独自算出の注目度）: 28.94461817548213
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we investigate the problem of adapting to the presence or absence of causal structure in multi-armed bandit problems. In addition to the usual reward signal, we assume the learner has access to additional variables, observed in each round after acting. When these variables $d$-separate the action from the reward, existing work in causal bandits demonstrates that one can achieve strictly better (minimax) rates of regret (Lu et al., 2020). Our goal is to adapt to this favorable "conditionally benign" structure, if it is present in the environment, while simultaneously recovering worst-case minimax regret, if it is not. Notably, the learner has no prior knowledge of whether the favorable structure holds. In this paper, we establish the Pareto optimal frontier of adaptive rates. We prove upper and matching lower bounds on the possible trade-offs in the performance of learning in conditionally benign and arbitrary environments, resolving an open question raised by Bilodeau et al. (2022). Furthermore, we are the first to obtain instance-dependent bounds for causal bandits, by reducing the problem to the linear bandit setting. Finally, we examine the common assumption that the marginal distributions of the post-action contexts are known and show that a nontrivial estimate is necessary for better-than-worst-case minimax rates.
- Abstract（参考訳）: 本研究では,多腕バンディット問題における因果構造の有無に適応する問題について検討する。
通常の報奨信号に加えて、学習者は行動後に各ラウンドで観察される追加変数にアクセスできると仮定する。
これらの変数$d$-が報酬からアクションを分離する場合、因果的盗賊の既存の研究は、後悔の程度(Lu et al , 2020)を厳密に改善できることを示した。
我々のゴールは、環境に存在している場合、この好ましい「条件付良性」構造に適応し、そうでなければ最悪のミニマックスの後悔を同時に回復することである。
特に、学習者は、好意的な構造が持つかどうかについての事前の知識を持たない。
本稿では,適応率のパレート最適フロンティアを確立する。
条件付良性および任意環境における学習性能のトレードオフについて,ビロドーら (2022) が提起したオープンな疑問を解き, 上界と下界との整合性を証明した。
さらに,この問題を線形帯域設定に還元することにより,最初に因果帯域のインスタンス依存境界を求める。
最後に, 反応後の文脈の限界分布が知られているという一般的な仮定を考察し, 非自明な推定値が必要であることを示す。
関連論文リスト
- Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits [7.064432289838905]
現在の研究はしばしば因果グラフが知られていると仮定するが、これは必ずしも先入観として利用できるとは限らない。
我々は、根底にある因果グラフが不明で、潜伏する共同設立者を含むシナリオにおける因果帯域の問題に焦点を当てる。
われわれは、必要で十分な潜在的共同創設者の集合を公式に特徴付け、可能な限り最適な武器が正しく特定されるように検出または学習する必要がある。
論文 参考訳（メタデータ） (2024-11-06T16:59:11Z) - Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - Non-stationary Bandits with Knapsacks [6.2006721306998065]
非定常環境におけるクナプサック(BwK)による包帯問題について検討する。
我々は、この問題の上下境界を導出するために、非定常対策を両方採用する。
論文 参考訳（メタデータ） (2022-05-25T01:22:36Z) - Versatile Dueling Bandits: Best-of-both-World Analyses for Online
Learning from Preferences [28.79598714109439]
両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。
まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。
提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
論文 参考訳（メタデータ） (2022-02-14T13:37:23Z) - On Slowly-varying Non-stationary Bandits [25.305949034527202]
我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。
我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。
我々のアルゴリズムは基本的にミニマックス最適であることを示す。
論文 参考訳（メタデータ） (2021-10-25T12:56:19Z) - Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。
情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。
これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
論文 参考訳（メタデータ） (2021-05-25T10:08:41Z) - Effects of Model Misspecification on Bayesian Bandits: Case Studies in
UX Optimization [8.704145252476705]
我々は、新しい定式化を、保存されていない共同創設者とオプションの停止を伴う、安静な睡眠バンディットとして提示する。
ケーススタディは、一般的な不特定が最適以下の報酬につながることを示している。
また、レスレスバンディットにおける結合を利用した最初のモデルを示し、有限の後悔と高速で一貫した停止が可能であることを示した。
論文 参考訳（メタデータ） (2020-10-07T14:34:28Z) - Instance-Dependent Complexity of Contextual Bandits and Reinforcement
Learning: A Disagreement-Based Perspective [104.67295710363679]
古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。
我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。
次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
論文 参考訳（メタデータ） (2020-10-07T01:33:06Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z) - Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。
ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。
逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
論文 参考訳（メタデータ） (2020-06-22T16:06:25Z) - Bias no more: high-probability data-dependent regret bounds for
adversarial bandits and MDPs [48.44657553192801]
我々は,適応的相手に対する盗聴フィードバックを用いたオンライン学習において,高い確率的後悔境界を得るための新しいアプローチを開発した。
我々のアプローチは、対数的に均質な自己協和障壁と強化されたフリードマンの不平等の助けを借りて、単純な学習率のスケジュールの増大に依存している。
論文 参考訳（メタデータ） (2020-06-14T22:09:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。