論文の概要: Smooth Non-Stationary Bandits
- arxiv url: http://arxiv.org/abs/2301.12366v2
- Date: Wed, 7 Jun 2023 17:32:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-08 19:34:34.270053
- Title: Smooth Non-Stationary Bandits
- Title(参考訳): 平滑な非定常バンド
- Authors: Su Jia, Qian Xie, Nathan Kallus, Peter I. Frazier
- Abstract要約: 本研究では、腕の平均報酬が正規化時間(正規化時間)で$beta$-H'older関数となる非定常二本腕バンディット問題について検討する。
滑らかな状態と非滑らかな状態の分離を最初に示すのは、$tilde O(T3/5)$ regret for $beta=2$である。
- 参考スコア(独自算出の注目度): 54.40609666958948
- License: http://creativecommons.org/licenses/by/4.0/
- 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, where
they guarantee $\tilde \Theta(T^{2/3})$ regret. However, in practice
environments are often changing {\bf smoothly}, so such algorithms may incur
higher-than-necessary regret in these settings and do not leverage information
on the rate of change. We study a non-stationary two-armed bandits problem
where we assume that an arm's mean reward is a $\beta$-H\"older function over
(normalized) time, meaning it is $(\beta-1)$-times Lipschitz-continuously
differentiable. We show the first separation between the smooth and non-smooth
regimes by presenting a policy with $\tilde O(T^{3/5})$ regret for $\beta=2$.
We complement this result by an $\Omg(T^{(\beta+1)/(2\beta+1)})$ lower bound
for any integer $\beta\ge 1$, which matches our upper bound for $\beta=2$.
- Abstract(参考訳): オンライン意思決定の多くの応用において、環境は非定常的であり、変化を処理するバンディットアルゴリズムを使用することが重要である。
既存のほとんどのアプローチは、全変動やリプシッツ性によって制限された非滑らかな変更から保護するために設計されており、ここでは $\tilde \Theta(T^{2/3})$ regret が保証されている。
しかし、実際には環境がスムーズに変化していることが多いため、このようなアルゴリズムはこれらの設定において必要以上に後悔を招き、変化率に関する情報を活用できない。
我々は、アームの平均報酬が(正規化された)時間上の$\beta$-h\"older関数であると仮定し、これは$(\beta-1)$-times lipschitz-continuously differentiableである。
我々は,スムースレジームと非スムースレジームの間の最初の分離を,$\tilde o(t^{3/5})$ regret for $\beta=2$ というポリシーで示す。
この結果を、任意の整数$\beta\ge 1$に対して$\omg(t^{(\beta+1)/(2\beta+1)})$下限で補う。
関連論文リスト
- 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) - Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed
Payoffs [35.988644745703645]
我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。
本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-04-28T13:01:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。