論文の概要: 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)})$下限で補う。

関連論文リスト

• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
  本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。 提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
  論文  参考訳（メタデータ） (2024-03-05T18:59:47Z)
• On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
  強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。 改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
  論文  参考訳（メタデータ） (2023-05-24T17:40:57Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15: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)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Smooth Bandit Optimization: Generalization to H\"older Space [37.15553727896912]
  我々は、目標が累積後悔である滑らかな報酬関数のバンディット最適化を考える。 私たちの主な結果は、指数 $alpha>1$ を持つ H"older space への報酬関数の一般化です。 私たちは、$alphaleq 1$サブセット内で、既存の下限に適合する後悔率を達成することを示します。
  論文  参考訳（メタデータ） (2020-12-11T01:43:25Z)

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

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