Fugu-MT 論文翻訳(概要): Adaptive Smooth Non-Stationary Bandits

論文の概要: Adaptive Smooth Non-Stationary Bandits

arxiv url: http://arxiv.org/abs/2407.08654v1
Date: Thu, 11 Jul 2024 16:37:15 GMT
ステータス: 処理完了
システム内更新日: 2024-07-12 16:40:31.927259
Title: Adaptive Smooth Non-Stationary Bandits
Title（参考訳）: 適応スムース非定常バンド
Authors: Joe Suk,
Abstract要約: 我々は、報酬がスムーズに変化する、$Kの非定常バンディットモデルについて研究する。一般に、すべての$K,beta,lambda$に対してminimax動的後悔率を確立します。また,非定常帯域におけるギャップ依存的後悔率の高速化についても検討した。
参考スコア（独自算出の注目度）: 0.8158530638728501
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study a $K$-armed non-stationary bandit model where rewards change smoothly, as captured by H\"{o}lder class assumptions on rewards as functions of time. Such smooth changes are parametrized by a H\"{o}lder exponent $\beta$ and coefficient $\lambda$. While various sub-cases of this general model have been studied in isolation, we first establish the minimax dynamic regret rate generally for all $K,\beta,\lambda$. Next, we show this optimal dynamic regret can be attained adaptively, without knowledge of $\beta,\lambda$. To contrast, even with parameter knowledge, upper bounds were only previously known for limited regimes $\beta\leq 1$ and $\beta=2$ (Slivkins, 2014; Krishnamurthy and Gopalan, 2021; Manegueu et al., 2021; Jia et al.,2023). Thus, our work resolves open questions raised by these disparate threads of the literature. We also study the problem of attaining faster gap-dependent regret rates in non-stationary bandits. While such rates are long known to be impossible in general (Garivier and Moulines, 2011), we show that environments admitting a safe arm (Suk and Kpotufe, 2022) allow for much faster rates than the worst-case scaling with $\sqrt{T}$. While previous works in this direction focused on attaining the usual logarithmic regret bounds, as summed over stationary periods, our new gap-dependent rates reveal new optimistic regimes of non-stationarity where even the logarithmic bounds are pessimistic. We show our new gap-dependent rate is tight and that its achievability (i.e., as made possible by a safe arm) has a surprisingly simple and clean characterization within the smooth H\"{o}lder class model.
Abstract（参考訳）: 我々は、時間関数としての報酬に関するH\"{o}lderクラス仮定によって得られるように、報酬がスムーズに変化する、$K$の非定常バンディットモデルについて検討する。このような滑らかな変化は、H\"{o}lder exponent $\beta$ と係数 $\lambda$ によってパラメタ化される。この一般モデルの様々な部分ケースは独立に研究されているが、まずはすべての$K,\beta,\lambda$に対してミニマックス動的後悔率を確立する。次に、この最適な動的後悔は、$\beta,\lambda$を知らずに適応的に達成できることを示す。対照的に、パラメータの知識がある場合でも、上界は以前は限定的な制度でのみ知られていた: $\beta\leq 1$ と $\beta=2$ (Slivkins, 2014; Krishnamurthy and Gopalan, 2021; Manegueu et al , 2021; Jia et al , 2023)。このように、本研究は、これらの異なるスレッドによって提起されたオープンな疑問を解決している。また,非定常帯域におけるギャップ依存的後悔率の高速化についても検討した。そのようなレートは、一般的には不可能であることが長く知られている(Garivier and Moulines, 2011)が、安全なアームを持つ環境(Suk and Kpotufe, 2022)は、$\sqrt{T}$の最悪のスケールよりもはるかに高速であることを示す。この方向の以前の研究は、定常期間にまとめられた通常の対数的後悔境界を達成することに重点を置いていたが、我々の新たなギャップ依存率は、対数的後悔境界でさえ悲観的である新しい楽観的な非定常状態を示す。新たなギャップ依存速度は厳密であり、その達成可能性(つまり安全なアームでできるような)が、スムーズなH\"{o}lderクラスモデルの中で驚くほど単純でクリーンな特徴づけを持つことを示す。

関連論文リスト

Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文参考訳（メタデータ） (2024-03-15T23:36:55Z)
Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-02-21T00:17:24Z)
Smooth Non-Stationary Bandits [49.19728527803684]
本研究では、各アームの平均報酬シーケンスを$beta$-H"older関数に埋め込むことができる非定常包帯問題について検討する。スムース(つまり$betage 2$)と非スムース(つまり$beta=1$)との最初の分離は、$tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2-H"older instanceでポリシーを提示することで示します。
論文参考訳（メタデータ） (2023-01-29T06:03:20Z)
High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文参考訳（メタデータ） (2022-04-06T13:50:33Z)
The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。一般関数クラスと一般モデルクラスで学ぶことに集中する。対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文参考訳（メタデータ） (2022-03-03T02:55:55Z)
A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits [11.918230810566945]
本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
論文参考訳（メタデータ） (2022-01-17T17:23:56Z)
On Slowly-varying Non-stationary Bandits [25.305949034527202]
我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。我々のアルゴリズムは基本的にミニマックス最適であることを示す。
論文参考訳（メタデータ） (2021-10-25T12:56:19Z)
Non-stationary Linear Bandits Revisited [26.082923174615495]
非定常線形帯域は、時間変化の根底にある回帰パラメータを持つ線形帯域の変種である。これらのアルゴリズムに対して,$widetildeO(T3/4(1+P_T)1/4)$ dynamic regretを証明した。
論文参考訳（メタデータ） (2021-03-09T10:07:17Z)
Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits [9.833844886421694]
ロジスティック・バンディットは、パラメタライズド・バンディットにおける非線形性の影響を理解するための、散らかったが挑戦的な枠組みを提供することによって、かなりの注目を集めている。非線型性の効果を精密に解析する新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-10-23T20:07:31Z)
Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文参考訳（メタデータ） (2020-09-04T04:10:39Z)

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

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