論文の概要: Finite-Time Logarithmic Bayes Regret Upper Bounds

• arxiv url: http://arxiv.org/abs/2306.09136v2
• Date: Fri, 3 Nov 2023 08:47:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-06 17:39:27.844373
• Title: Finite-Time Logarithmic Bayes Regret Upper Bounds
• Title（参考訳）: 有限時間対数ベイズ上界を後悔する
• Authors: Alexia Atsidakou, Branislav Kveton, Sumeet Katariya, Constantine Caramanis, and Sujay Sanghavi
• Abstract要約: ベイジアン・バンディットに対する最初の有限時間対数ベイズ後悔の上界を導出する。 この結果から,ベイジアン設定における事前情報の価値について,学習者に与える副次的情報と目的的情報の両方について考察した。 これらは既存の$tildeO(sqrtn)$boundsよりも大幅に改善され、既存の下位境界にもかかわらず文学において標準となっている。
• 参考スコア（独自算出の注目度）: 41.192035568937214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We derive the first finite-time logarithmic Bayes regret upper bounds for Bayesian bandits. In Gaussian bandits, we obtain $O(c_\Delta \log n)$ and $O(c_h \log^2 n)$ bounds for an upper confidence bound algorithm, where $c_h$ and $c_\Delta$ are constants depending on the prior distribution and the gaps of random bandit instances sampled from it, respectively. The latter bound asymptotically matches the lower bound of Lai (1987). Our proofs are a major technical departure from prior works, while being simple and general. To show the generality of our techniques, we apply them to linear bandits. Our results provide insights on the value of prior in the Bayesian setting, both in the objective and as a side information given to the learner. They significantly improve upon existing $\tilde{O}(\sqrt{n})$ bounds, which have become standard in the literature despite the existing lower bounds.
• Abstract（参考訳）: ベイジアン・バンディットに対する最初の有限時間対数ベイズ後悔の上界を導出する。 gaussian bandits では、c_h$ と $c_\delta$ はそれぞれ事前分布とそれからサンプリングされたランダムバンディットインスタンスのギャップに依存する定数である上信頼境界アルゴリズムに対して、$o(c_\delta \log n)$ と $o(c_h \log^2n)$ が与えられる。 後者の境界は Lai (1987) の下界と漸近的に一致する。 我々の証明は、単純で汎用的でありながら、先行研究から大きな技術的逸脱である。 本手法の一般性を示すため,線形包帯に適用する。 この結果は,目的と学習者に与えた副情報の両方において,ベイズ設定における事前値に関する洞察を与える。 これらは既存の$\tilde{o}(\sqrt{n})$境界によって著しく改善され、既存の下限にもかかわらず文献では標準となっている。

関連論文リスト

• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
  我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
  論文  参考訳（メタデータ） (2023-05-01T14:00:15Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。 時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。 また, 動的上界に依存した新しい行列不等式濃度を証明した。
  論文  参考訳（メタデータ） (2021-10-15T12:32:33Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• 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)
• A Tight Lower Bound for Uniformly Stable Algorithms [6.331019775653315]
  アルゴリズムの安定性を利用して鋭い一般化境界を導出することは、学習理論における古典的かつ強力なアプローチである。 順序 $omega(gamma+fraclsqrtn)$ の厳密な一般化を証明し、これは最もよく知られた上限値から対数因子に一致する。
  論文  参考訳（メタデータ） (2020-12-24T17:01:18Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)

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

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