論文の概要: Tracking Most Significant Shifts in Nonparametric Contextual Bandits

• arxiv url: http://arxiv.org/abs/2307.05341v2
• Date: Sun, 19 Nov 2023 00:49:21 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-22 18:48:05.856992
• Title: Tracking Most Significant Shifts in Nonparametric Contextual Bandits
• Title（参考訳）: 非パラメトリックな帯域における最も重要なシフトの追跡
• Authors: Joe Suk and Samory Kpotufe
• Abstract要約: リプシッツは報酬関数が時間とともに変化する可能性のある非パラメトリックな文脈的包帯について検討する。 私たちはまず、このあまり理解されていない環境で、ミニマックスのダイナミックな後悔率を確立します。 そして、この設定では最先端の手続きが準最適であると論じる。
• 参考スコア（独自算出の注目度）: 4.985768723667416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study nonparametric contextual bandits where Lipschitz mean reward functions may change over time. We first establish the minimax dynamic regret rate in this less understood setting in terms of number of changes $L$ and total-variation $V$, both capturing all changes in distribution over context space, and argue that state-of-the-art procedures are suboptimal in this setting. Next, we tend to the question of an adaptivity for this setting, i.e. achieving the minimax rate without knowledge of $L$ or $V$. Quite importantly, we posit that the bandit problem, viewed locally at a given context $X_t$, should not be affected by reward changes in other parts of context space $\cal X$. We therefore propose a notion of change, which we term experienced significant shifts, that better accounts for locality, and thus counts considerably less changes than $L$ and $V$. Furthermore, similar to recent work on non-stationary MAB (Suk & Kpotufe, 2022), experienced significant shifts only count the most significant changes in mean rewards, e.g., severe best-arm changes relevant to observed contexts. Our main result is to show that this more tolerant notion of change can in fact be adapted to.
• Abstract（参考訳）: リプシッツが報酬関数を意味する非パラメトリックな文脈帯域について、時間とともに変化する可能性がある。 まず、この最小限のダイナミックな後悔率を、変更数で$L$と総変量$V$で理解されていない設定で確立し、どちらも文脈空間上の分布のすべての変化を捉え、この設定では最先端の手続きが最適でないと主張する。 次に、私たちはこの設定に対する適応性の問題、すなわち$l$ や $v$ を知らずにminimaxレートを達成する傾向がある。 極めて重要なことは、与えられたコンテキストで局所的に見られるbandit問題は、他のコンテキスト空間の報酬変更である$\cal x$の影響を受けるべきではない、ということです。 したがって、我々は変化の概念を提案し、これは大きな変化を経験し、局所性をうまく考慮し、したがって$L$や$V$よりもかなり少ない変化を数えている。 さらに、非定常MAB(Suk & Kpotufe, 2022)に関する最近の研究と同様に、大きな変化は平均報酬の最も重要な変化(例えば、観測された文脈に関連する深刻なベストアームの変化)を数えることしかなかった。 私たちの主な成果は、このより寛容な変化の概念が実際に適応可能であることを示すことです。

関連論文リスト

• Adaptive Smooth Non-Stationary Bandits [0.8158530638728501]
  我々は、報酬がスムーズに変化する、$Kの非定常バンディットモデルについて研究する。 一般に、すべての$K,beta,lambda$に対してminimax動的後悔率を確立します。 また,非定常帯域におけるギャップ依存的後悔率の高速化についても検討した。
  論文  参考訳（メタデータ） (2024-07-11T16:37:15Z)
• 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)
• 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)
• Autoregressive Bandits [58.46584210388307]
  本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。 報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。 次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
  論文  参考訳（メタデータ） (2022-12-12T21:37:36Z)
• 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)
• Tracking Most Severe Arm Changes in Bandits [12.29762518277676]
  我々は、$tildeO(sqrtT)ll tildeO(sqrtLT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll
  論文  参考訳（メタデータ） (2021-12-27T18:59:05Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。 局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。 他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
  論文  参考訳（メタデータ） (2021-06-28T00:38:54Z)
• Self-Tuning Bandits over Unknown Covariate-Shifts [7.982668978293684]
  非パラメトリックな文脈的包帯は、シフトの時間やシフトの量を知ることなく適応的に達成できることを示す。 我々は,文脈分布の変化の連続性を強く捉えた新たな後悔境界を導出する。 これらのレートは、シフトの時間やシフトの量を知ることなく適応的に達成できることを示す。
  論文  参考訳（メタデータ） (2020-07-16T19:40:16Z)
• Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)

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

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