論文の概要: Logarithmic Bayes Regret Bounds

• arxiv url: http://arxiv.org/abs/2306.09136v1
• Date: Thu, 15 Jun 2023 13:49:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-16 14:37:53.709383
• Title: Logarithmic Bayes Regret Bounds
• Title（参考訳）: 対数ベイズレッグ境界
• Authors: Alexia Atsidakou, Branislav Kveton, Sumeet Katariya, Constantine Caramanis, Sujay Sanghavi
• Abstract要約: ガウスの包帯に対して、$O(c_h log2 n)$bound, ここで$c_h$は事前依存定数である。 我々の証明は、先行研究から技術的に逸脱したものであり、単純で一般的なものである。 彼らは $tildeO(sqrtn)$ 境界を大幅に改善し、既存の下限にもかかわらず、文学において標準となっている。
• 参考スコア（独自算出の注目度）: 35.30144272346553
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We derive the first finite-time logarithmic regret bounds for Bayesian bandits. For Gaussian bandits, we obtain a $O(c_h \log^2 n)$ bound, where $c_h$ is a prior-dependent constant. This matches the asymptotic lower bound of Lai (1987). Our proofs mark a technical departure from prior works, and are simple and general. To show generality, we apply our technique to linear bandits. Our bounds shed light on the value of the prior in the Bayesian setting, both in the objective and as a side information given to the learner. They significantly improve the $\tilde{O}(\sqrt{n})$ bounds, that despite the existing lower bounds, have become standard in the literature.
• Abstract（参考訳）: ベイズバンドに対する最初の有限時間対数後悔境界を導出する。 ガウスの包帯に対して、$O(c_h \log^2 n)$bound, ここで$c_h$は事前依存定数である。 これは 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)

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

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