論文の概要: Smooth Non-Stationary Bandits

• arxiv url: http://arxiv.org/abs/2301.12366v3
• Date: Sun, 17 Nov 2024 18:03:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-19 14:29:59.246418
• Title: Smooth Non-Stationary Bandits
• Title（参考訳）: 平滑な非定常バンド
• Authors: Su Jia, Qian Xie, Nathan Kallus, Peter I. Frazier,
• Abstract要約: 本研究では、各アームの平均報酬シーケンスを$beta$-H"older関数に埋め込むことができる非定常包帯問題について検討する。 スムース(つまり$betage 2$)と非スムース(つまり$beta=1$)との最初の分離は、$tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2-H"older instanceでポリシーを提示することで示します。
• 参考スコア（独自算出の注目度）: 49.19728527803684
• License:
• Abstract: In many applications of online decision making, the environment is non-stationary and it is therefore crucial to use bandit algorithms that handle changes. Most existing approaches are designed to protect against non-smooth changes, constrained only by total variation or Lipschitzness over time. However, in practice, environments often change {\em smoothly}, so such algorithms may incur higher-than-necessary regret. We study a non-stationary bandits problem where each arm's mean reward sequence can be embedded into a $\beta$-H\"older function, i.e., a function that is $(\beta-1)$-times Lipschitz-continuously differentiable. The non-stationarity becomes more smooth as $\beta$ increases. When $\beta=1$, this corresponds to the non-smooth regime, where \cite{besbes2014stochastic} established a minimax regret of $\tilde \Theta(T^{2/3})$. We show the first separation between the smooth (i.e., $\beta\ge 2$) and non-smooth (i.e., $\beta=1$) regimes by presenting a policy with $\tilde O(k^{4/5} T^{3/5})$ regret on any $k$-armed, $2$-H\"older instance. We complement this result by showing that the minimax regret on the $\beta$-H\"older family of instances is $\Omega(T^{(\beta+1)/(2\beta+1)})$ for any integer $\beta\ge 1$. This matches our upper bound for $\beta=2$ up to logarithmic factors. Furthermore, we validated the effectiveness of our policy through a comprehensive numerical study using real-world click-through rate data.
• Abstract（参考訳）: オンライン意思決定の多くの応用において、環境は非定常的であり、変化を処理するバンディットアルゴリズムを使用することが重要である。 既存のアプローチのほとんどは、時間とともに全体の変動やリプシッツネスによってのみ制約される、非滑らかな変更から保護するために設計されている。 しかし、実際には環境がスムーズに変化することが多いため、そのようなアルゴリズムは必要以上に後悔を招きかねない。 我々は、各アームの平均報酬列を$\beta$-H\"older関数、すなわち$(\beta-1)$-times Lipschitz-continuously differentiable(英語版))に埋め込むことができる非定常包帯問題を研究する。 非定常性は$\beta$が増加するにつれてより滑らかになる。 ここで \cite{besbes2014stochastic} は $\tilde \Theta(T^{2/3})$ のミニマックス後悔を確立した。 滑らかな(つまり$\beta\ge 2$)と非滑らかな(つまり$\beta=1$)レギュレーションの間の最初の分離を示す。 任意の整数 $\beta\ge 1$ に対して $\Omega(T^{(\beta+1)/(2\beta+1)})$ である。 これは、対数係数まで$\beta=2$の上限と一致する。 さらに,実世界のクリックスルー率データを用いた包括的数値研究により,政策の有効性を検証した。

関連論文リスト

• Generalized Linear Bandits with Limited Adaptivity [12.112051468737596]
  限定適応性の制約内における一般化線形文脈帯域問題について検討する。 我々は2つのアルゴリズム, $textttB-GLinCB$ と $textttRS-GLinCB$ を提示した。
  論文  参考訳（メタデータ） (2024-04-10T08:47:57Z)
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
  我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
  論文  参考訳（メタデータ） (2023-05-01T14:00:15Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• 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)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
  そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。 私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
  論文  参考訳（メタデータ） (2021-02-19T11:03:51Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Smooth Bandit Optimization: Generalization to H\"older Space [37.15553727896912]
  我々は、目標が累積後悔である滑らかな報酬関数のバンディット最適化を考える。 私たちの主な結果は、指数 $alpha>1$ を持つ H"older space への報酬関数の一般化です。 私たちは、$alphaleq 1$サブセット内で、既存の下限に適合する後悔率を達成することを示します。
  論文  参考訳（メタデータ） (2020-12-11T01:43:25Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)

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

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