論文の概要: Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits

• arxiv url: http://arxiv.org/abs/2209.06983v1
• Date: Thu, 15 Sep 2022 00:20:38 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-16 12:12:47.664805
• Title: Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits
• Title（参考訳）: 一般化線形帯域に対する二重二重ロバストトンプソンサンプリング
• Authors: Wonyoung Kim, Kyungbok Lee, Myunghee Cho Paik
• Abstract要約: 一般化線形報酬に$tildeO(sqrtkappa-1 phi T)$ regret over $T$ roundsを提案する。 また、確率的マージン条件下では、$O(kappa-1 phi log (NT) log T)$ regret bound for $N$ arms も提供する。
• 参考スコア（独自算出の注目度）: 8.508198765617198
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a novel contextual bandit algorithm for generalized linear rewards with an $\tilde{O}(\sqrt{\kappa^{-1} \phi T})$ regret over $T$ rounds where $\phi$ is the minimum eigenvalue of the covariance of contexts and $\kappa$ is a lower bound of the variance of rewards. In several practical cases where $\phi=O(d)$, our result is the first regret bound for generalized linear model (GLM) bandits with the order $\sqrt{d}$ without relying on the approach of Auer [2002]. We achieve this bound using a novel estimator called double doubly-robust (DDR) estimator, a subclass of doubly-robust (DR) estimator but with a tighter error bound. The approach of Auer [2002] achieves independence by discarding the observed rewards, whereas our algorithm achieves independence considering all contexts using our DDR estimator. We also provide an $O(\kappa^{-1} \phi \log (NT) \log T)$ regret bound for $N$ arms under a probabilistic margin condition. Regret bounds under the margin condition are given by Bastani and Bayati [2020] and Bastani et al. [2021] under the setting that contexts are common to all arms but coefficients are arm-specific. When contexts are different for all arms but coefficients are common, ours is the first regret bound under the margin condition for linear models or GLMs. We conduct empirical studies using synthetic data and real examples, demonstrating the effectiveness of our algorithm.
• Abstract（参考訳）: 本稿では,一般化線形報酬に対する新しい文脈的バンディットアルゴリズムを提案する。$\tilde{o}(\sqrt{\kappa^{-1} \phi t})$ regret over $t$ rounds ここで$\phi$は文脈の共分散の最小固有値,$\kappa$は報酬の分散の下限である。 $\phi=O(d)$ のいくつかの実例では、Auer [2002] のアプローチに頼らずに$\sqrt{d}$ の順序を持つ一般化線形モデル (GLM) バンディットに対する最初の後悔境界となる。 二重二重ロバスト(ddr)推定子(double doubly-robust)推定子(double doubly-robust (ddr) estimator)は二重ロバスト(dr)推定子(doubly-robust)のサブクラスである。 Auer [2002] のアプローチは、観測された報酬を捨てて独立性を達成する一方、我々のアルゴリズムは、我々のDDR推定器を用いて、すべての文脈を考慮した独立性を達成する。 また、確率的マージン条件の下では、$O(\kappa^{-1} \phi \log (NT) \log T)$ regret bound for $N$ arms も提供する。 境界条件下でのレグレト境界は、Bastani と Bayati [2020] と Bastani et al によって与えられる。 2021] 文脈はすべての腕に共通であるが, 係数はアーム固有である。 全てのアームでコンテキストが異なるが係数が一般的である場合、線形モデル(GLM)のマージン条件の下で最初の後悔となる。 我々は,合成データと実例を用いて経験的研究を行い,アルゴリズムの有効性を実証する。

関連論文リスト

• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Best-of-Both-Worlds Linear Contextual Bandits [45.378265414553226]
  本研究は, 対向汚職下での多武装盗賊問題の事例である$K$腕線形文脈盗賊の問題を考察する。 我々は,理論的保証のもと,双方の敵環境に有効な戦略を開発する。 両体制の理論的保証から,我々の戦略をBest-of-Both-Worlds (BoBW) RealFTRLと呼んでいる。
  論文  参考訳（メタデータ） (2023-12-27T09:32:18Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Risk-averse Contextual Multi-armed Bandit Problem with Linear Payoffs [7.125769932993104]
  リスク・逆条件下での線形ペイオフに対するコンテキスト多重武装バンディット問題について考察する。 各ラウンドにおいて、各アームのコンテキストが明らかにされ、意思決定者は1つのアームを選択して、対応する報酬を受け取ります。 解離モデルに対してトンプソンサンプリングアルゴリズムを適用し,提案アルゴリズムの変種に対する包括的後悔解析を行う。
  論文  参考訳（メタデータ） (2022-06-24T18:48:35Z)
• Doubly robust Thompson sampling for linear payoffs [12.375561840897742]
  本稿では,Douubly Robust (DR) Thompson Sampling と呼ばれる新しいマルチアームコンテキスト帯域幅アルゴリズムを提案する。 提案アルゴリズムは, 新たな補遺分解を許容し, $tildeO(phi-2sqrtT)$の順序で補遺を改良する。
  論文  参考訳（メタデータ） (2021-02-01T23:31:10Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。 結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
  論文  参考訳（メタデータ） (2020-06-29T21:06:52Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Budget-Constrained Bandits over General Cost and Reward Distributions [32.63624728528415]
  我々は,各アームがランダムなコストを発生させ,その見返りにランダムな報酬を与える,予算制約付きバンディット問題を考える。 ある$gamma > 0$ に対して位数 $(2+gamma)$ のモーメントが存在するならば、$O(log B)$ regret は予算 $B>0$ に対して達成可能である。
  論文  参考訳（メタデータ） (2020-02-29T23:50:08Z)

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

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