論文の概要: Optimal Regret Is Achievable with Bounded Approximate Inference Error:
An Enhanced Bayesian Upper Confidence Bound Framework
- arxiv url: http://arxiv.org/abs/2201.12955v4
- Date: Fri, 10 Nov 2023 03:01:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-13 18:53:14.803708
- Title: Optimal Regret Is Achievable with Bounded Approximate Inference Error:
An Enhanced Bayesian Upper Confidence Bound Framework
- Title（参考訳）: 最適後悔は有界近似推論誤差で達成可能である:拡張ベイズ高信頼境界フレームワーク
- Authors: Ziyi Huang, Henry Lam, Amirhossein Meisami, Haofeng Zhang
- Abstract要約: 本稿では,帯域幅問題に効率的に対応できる拡張ベイズアッパー信頼境界(EBUCB)フレームワークを提案する。
EBUCBは2つの異なる$alpha$-divergencesで測定された推論誤差が定数以下である場合、最適後悔順序$O(log T)$を達成可能であることを示す。
我々の研究は、定数近似推論誤差の設定において$o(T)$よりも良い最初の理論的後悔境界を提供する。
- 参考スコア（独自算出の注目度）: 22.846260353176614
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bayesian bandit algorithms with approximate Bayesian inference have been
widely used in real-world applications. However, there is a large discrepancy
between the superior practical performance of these approaches and their
theoretical justification. Previous research only indicates a negative
theoretical result: Thompson sampling could have a worst-case linear regret
$\Omega(T)$ with a constant threshold on the inference error measured by one
$\alpha$-divergence. To bridge this gap, we propose an Enhanced Bayesian Upper
Confidence Bound (EBUCB) framework that can efficiently accommodate bandit
problems in the presence of approximate inference. Our theoretical analysis
demonstrates that for Bernoulli multi-armed bandits, EBUCB can achieve the
optimal regret order $O(\log T)$ if the inference error measured by two
different $\alpha$-divergences is less than a constant, regardless of how large
this constant is. To our best knowledge, our study provides the first
theoretical regret bound that is better than $o(T)$ in the setting of constant
approximate inference error. Furthermore, in concordance with the negative
results in previous studies, we show that only one bounded $\alpha$-divergence
is insufficient to guarantee a sub-linear regret.
- Abstract（参考訳）: ベイズ推定を近似したベイズ帯域幅アルゴリズムは現実世界の応用に広く用いられている。
しかし、これらのアプローチの優れた実用的性能と理論的正当化との間には大きな相違がある。
トンプソンサンプリングは、最低ケースの線形後悔$\Omega(T)$で、1$\alpha$-divergenceで測定された推論誤差に一定の閾値を持つ可能性がある。
このギャップを埋めるために,近似推論の存在下でバンドイット問題を効率的に対応できる拡張ベイズ高信頼境界(ebucb)フレームワークを提案する。
我々の理論的分析は、ベルヌーイの多重武装バンディットに対して、2つの異なる$\alpha$-divergencesで測定された推論誤差が定数以下である場合、EBUCBが最適後悔順序$O(\log T)$を達成できることを証明している。
我々の知る限り、我々の研究は、定数近似推論誤差の設定において$o(T)$よりも良い最初の理論的後悔境界を提供する。
さらに, 前回の研究では否定的な結果と一致して, 1つの有界$\alpha$-divergenceのみが, サブ線形後悔を保証するには不十分であることを示す。
関連論文リスト
- 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) - Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits [21.09844002135398]
我々は,線形トンプソンサンプリング (LinTS) とベイズ的上部信頼境界の拡張 (LinBUCB) が,元の後悔の上界の速度を保てることを示す。
また、LinBUCBはLinTSの後悔率を$tildeO(d3/2sqrtT)$から$tildeO(dsqrtT)$に短縮することを示した。
論文 参考訳（メタデータ） (2024-06-20T07:45:38Z) - 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) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - First-Order Regret in Reinforcement Learning with Linear Function
Approximation: A Robust Estimation Approach [57.570201404222935]
我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。
この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
論文 参考訳（メタデータ） (2021-12-07T00:29:57Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Sharp regret bounds for empirical Bayes and compound decision problems [42.397889421982555]
ベイズ設定では、最適推定器は事前依存条件平均によって与えられる。
コンパクトにサポートされた部分指数前のPoissonモデルに対して、最適の後悔スケールは $Theta(fraclog nloglog n)2)$ と $Theta(log3 n)$ である。
論文 参考訳（メタデータ） (2021-09-08T21:34:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。