論文の概要: Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits

• arxiv url: http://arxiv.org/abs/2406.14071v2
• Date: Sun, 27 Oct 2024 23:43:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 12:18:01.209919
• Title: Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits
• Title（参考訳）: 確率線形帯域における近似推論を用いたベイズ帯域アルゴリズム
• Authors: Ziyi Huang, Henry Lam, Haofeng Zhang,
• Abstract要約: 我々は,線形トンプソンサンプリング (LinTS) とベイズ的上部信頼境界の拡張 (LinBUCB) が,元の後悔の上界の速度を保てることを示す。 また、LinBUCBはLinTSの後悔率を$tildeO(d3/2sqrtT)$から$tildeO(dsqrtT)$に短縮することを示した。
• 参考スコア（独自算出の注目度）: 21.09844002135398
• License:
• Abstract: Bayesian bandit algorithms with approximate Bayesian inference have been widely used in real-world applications. Despite the superior practical performance, their theoretical justification is less investigated in the literature, especially for contextual bandit problems. To fill this gap, we propose a theoretical framework to analyze the impact of approximate inference in stochastic linear bandits and conduct regret analysis on two Bayesian bandit algorithms, Linear Thompson sampling (LinTS) and the extension of Bayesian Upper Confidence Bound, namely Linear Bayesian Upper Confidence Bound (LinBUCB). We demonstrate that when applied in the presence of approximate inference, LinTS and LinBUCB can preserve their original rates of regret upper bound but with a sacrifice of larger constant terms. These results hold for general Bayesian inference approaches, assuming the inference error measured by two different $\alpha$-divergences is bounded. Additionally, by introducing a new definition of well-behaved distributions, we show that LinBUCB expedites the regret rate of LinTS from $\tilde{O}(d^{3/2}\sqrt{T})$ to $\tilde{O}(d\sqrt{T})$, matching the minimax optimal rate. To our knowledge, this work provides the first regret bounds in the setting of stochastic linear bandits with bounded approximate inference errors.
• Abstract（参考訳）: ベイズ推定を近似したベイズ帯域幅アルゴリズムは、現実世界の応用に広く用いられている。 優れた実用性能にもかかわらず、その理論的正当性は文学、特に文脈的盗賊問題では研究されていない。 このギャップを埋めるために、確率線形包帯における近似推論の影響を解析し、2つのベイズ的包帯アルゴリズム、LinTS(Linar Thompson sample)とLinBUCB(Linar Bayesian upper Confidence Bound)の拡張に対する後悔の解析を行う理論的枠組みを提案する。 近似推論で適用した場合、LinTSとLinBUCBは、元の後悔の上限を保ちながら、より大きい一定の項を犠牲にすることができることを示した。 これらの結果は、二つの異なる$\alpha$-divergences によって測定された推論誤差が有界であると仮定して、一般ベイズ推論のアプローチを裏付ける。 さらに、LinBUCB は分布の定義を新たに導入することにより、LinTS の後悔率を $\tilde{O}(d^{3/2}\sqrt{T})$ から $\tilde{O}(d\sqrt{T})$ に短縮し、最小値の最適レートと一致することを示す。 我々の知る限り、この研究は、有界近似推論誤差を持つ確率線型帯域の設定における最初の後悔の限界を提供する。

関連論文リスト

• Regret Minimization and Statistical Inference in Online Decision Making with High-dimensional Covariates [7.21848268647674]
  我々は、決定のための$varepsilon$-greedybanditアルゴリズムと、疎帯域パラメータを推定するためのハードしきい値アルゴリズムを統合する。 マージン条件下では、我々の手法は、$O(T1/2)$ regret あるいは古典的な$O(T1/2)$-consistent推論のいずれかを達成する。
  論文  参考訳（メタデータ） (2024-11-10T01:47:11Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• 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)
• Optimal Regret Is Achievable with Bounded Approximate Inference Error: An Enhanced Bayesian Upper Confidence Bound Framework [22.846260353176614]
  本稿では,帯域幅問題に効率的に対応できる拡張ベイズアッパー信頼境界(EBUCB)フレームワークを提案する。 EBUCBは2つの異なる$alpha$-divergencesで測定された推論誤差が定数以下である場合、最適後悔順序$O(log T)$を達成可能であることを示す。 我々の研究は、定数近似推論誤差の設定において$o(T)$よりも良い最初の理論的後悔境界を提供する。
  論文  参考訳（メタデータ） (2022-01-31T01:36:15Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。 性能は不特定な事前条件で優雅に低下することを示す。
  論文  参考訳（メタデータ） (2021-07-03T23:17:26Z)
• Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
  ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。 情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。 これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2021-05-25T10:08:41Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Differentiable Linear Bandit Algorithm [6.849358422233866]
  アッパー信頼境界は、線形多腕バンディット問題の最も一般的な方法である。 勾配上昇による信頼度を学習できる勾配推定器を導入する。 提案アルゴリズムは,腕の特徴の次元を$d$で,信頼度を$hatbeta$で学習したサイズを$tildemathcalO(hatbetasqrtdT)$上限とする。
  論文  参考訳（メタデータ） (2020-06-04T16:43:55Z)
• Thompson Sampling for Linearly Constrained Bandits [18.477962150017095]
  我々はLinConTSについて述べる。LinConTSは、各ラウンドで報酬を得る確率に線形制約を課すバンディットのアルゴリズムである。 また,LinConTSでは,過度な制約違反と累積的制約違反はO(log T)で上限づけられていることを示す。
  論文  参考訳（メタデータ） (2020-04-20T13:06:35Z)

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

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