論文の概要: Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling

• arxiv url: http://arxiv.org/abs/2303.09033v2
• Date: Thu, 12 Oct 2023 10:34:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-16 04:02:46.695328
• Title: Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling
• Title（参考訳）: 不確実性のみを支払う - 分散適応型トンプソンサンプリング
• Authors: Aadirupa Saha and Branislav Kveton
• Abstract要約: ほとんどのバンディットアルゴリズムは、報酬のばらつきまたはその上限が知られており、全ての腕について同じであると仮定する。 この動機付けは、強いインスタンス依存の後悔境界を持つ分散適応型頻繁性アルゴリズムに関する先行研究である。 我々は、過去の知識を取り入れたベイズ的設定の基礎を築いた。
• 参考スコア（独自算出の注目度）: 44.921905700729766
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most bandit algorithms assume that the reward variances or their upper bounds are known, and that they are the same for all arms. This naturally leads to suboptimal performance and higher regret due to variance overestimation. On the other hand, underestimated reward variances may lead to linear regret due to committing early to a suboptimal arm. This motivated prior works on variance-adaptive frequentist algorithms, which have strong instance-dependent regret bounds but cannot incorporate prior knowledge on reward variances. We lay foundations for the Bayesian setting, which incorporates prior knowledge. This results in lower regret in practice, due to using the prior in the algorithm design, and also improved regret guarantees. Specifically, we study Gaussian bandits with {unknown heterogeneous reward variances}, and develop a Thompson sampling algorithm with prior-dependent Bayes regret bounds. We achieve lower regret with lower reward variances and more informative priors on them, which is precisely why we pay only for what is uncertain. This is the first result of its kind. Finally, we corroborate our theory with extensive experiments, which show the superiority of our variance-adaptive Bayesian algorithm over prior frequentist approaches. We also show that our approach is robust to model misspecification and can be applied with estimated priors.
• Abstract（参考訳）: ほとんどのバンディットアルゴリズムは、報酬のばらつきまたはその上限が知られており、全ての腕に同じものであると仮定する。 これは自然に最適以下のパフォーマンスと、分散過大評価による後悔につながる。 一方、過小評価された報酬分散は、最適下腕に早期にコミットするため、線形後悔を引き起こす可能性がある。 これは、強いインスタンス依存の後悔境界を持つが、報酬分散に関する事前知識を組み込むことができない分散適応型頻繁性アルゴリズムに関する先行研究である。 我々は、事前知識を組み込んだベイズ設定の基礎を築いた。 この結果,アルゴリズム設計における事前使用による後悔度が低下し,後悔の保証も改善した。 具体的には,不均質な報酬分散を用いたガウス的バンディットの研究を行い,事前依存ベイズ後悔境界を持つトンプソンサンプリングアルゴリズムを開発した。 報酬のばらつきを低くし、より情報的な優先事項で後悔を減らし、不確実なものに対してのみ支払いを行うのはまさにそのためです。 これがその種の最初の結果である。 最後に,従来の頻繁なアプローチよりも分散適応ベイズアルゴリズムの方が優れていることを示す広範な実験で,我々の理論を裏付ける。 また,提案手法は誤特定をモデル化し,事前推定に適用可能であることを示す。

関連論文リスト

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization [15.275864909088577]
  事前の未知のノイズレベルに適応することは、シーケンシャルな意思決定において非常に重要であるが難しい問題である。 未知のガウスパラメータ $sigma_*2$ に半適応的な新しい信頼集合を提案する。 有界報酬に対しては,先行技術により数値性能が大幅に向上した新しい分散適応信頼セットを提案する。
  論文  参考訳（メタデータ） (2024-02-12T00:19:09Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variances [12.00630538470713]
  不均一な報酬分散を伴う固定予算設定におけるベストアーム識別(BAI)の問題について検討する。 本稿では, 既知報酬分散に対するSHVarと未知報酬分散に対するSHAdaVarの2つの分散適応型BAIアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-13T05:41:38Z)
• Suboptimal Performance of the Bayes Optimal Algorithm in Frequentist Best Arm Identification [5.176134438571082]
  正規分布による報酬を伴う固定予算ベストアーム識別問題を考察する。 この問題では、予測者は、腕(または治療)が$K$、タイムステップが$T$である。 アルゴリズムの性能は、推定されたベストアームの品質を反映して、単純な後悔によって評価される。
  論文  参考訳（メタデータ） (2022-02-10T17:50:26Z)
• On Slowly-varying Non-stationary Bandits [25.305949034527202]
  我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。 我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。 我々のアルゴリズムは基本的にミニマックス最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-25T12:56:19Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。 性能は不特定な事前条件で優雅に低下することを示す。
  論文  参考訳（メタデータ） (2021-07-03T23:17:26Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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