論文の概要: Non-Stationary Lipschitz Bandits

• arxiv url: http://arxiv.org/abs/2505.18871v1
• Date: Sat, 24 May 2025 21:23:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:42.711778
• Title: Non-Stationary Lipschitz Bandits
• Title（参考訳）: 非定常リプシッツバンド
• Authors: Nicolas Nguyen, Solenne Gaucher, Claire Vernade,
• Abstract要約: 動作数が無限であり、リプシッツの仮定を満たす報酬関数が時間とともに任意に変化するような非定常リプシッツ包帯問題について検討する。 累積報酬関数の大きな偏差によって定義される,最近導入された有意なシフトの概念を適応的に追跡するアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 10.073375215995611
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of non-stationary Lipschitz bandits, where the number of actions is infinite and the reward function, satisfying a Lipschitz assumption, can change arbitrarily over time. We design an algorithm that adaptively tracks the recently introduced notion of significant shifts, defined by large deviations of the cumulative reward function. To detect such reward changes, our algorithm leverages a hierarchical discretization of the action space. Without requiring any prior knowledge of the non-stationarity, our algorithm achieves a minimax-optimal dynamic regret bound of $\mathcal{\widetilde{O}}(\tilde{L}^{1/3}T^{2/3})$, where $\tilde{L}$ is the number of significant shifts and $T$ the horizon. This result provides the first optimal guarantee in this setting.
• Abstract（参考訳）: 動作数が無限であり、リプシッツの仮定を満たす報酬関数が時間とともに任意に変化するような非定常リプシッツ包帯問題について検討する。 累積報酬関数の大きな偏差によって定義される,最近導入された有意なシフトの概念を適応的に追跡するアルゴリズムを設計する。 このような報酬変化を検出するために,本アルゴリズムは行動空間の階層的離散化を利用する。 非定常性に関する事前の知識を必要とせずに、我々のアルゴリズムは、$\mathcal{\widetilde{O}}(\tilde{L}^{1/3}T^{2/3})$の最小最大最適動的後悔境界を達成し、$\tilde{L}$は重要なシフトの数であり、水平線は$T$である。 この結果は、この設定で最初の最適な保証を提供する。

関連論文リスト

• Quantum Lipschitz Bandits [6.167074802065416]
  リプシッツ・バンディットは、期待される報酬関数がリプシッツ条件を満たすバンディット問題の重要な変種である。 連続的な行動空間と非線形報酬関数の課題に対処するために、最初の量子リプシッツバンディットアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-04-03T03:39:04Z)
• Linear Bandits with Partially Observable Features [35.08645010112184]
  本稿では,部分的に観測可能な特徴を持つ線形帯域問題を導入し,部分的な報奨情報と突発的な推定を行う。 遅延部分に対する適切なアドレスがなければ、後悔は、報酬に対する影響が不明であるため、決定の地平線上で線形に増加する可能性がある。 本稿では,潜在特徴を扱うための新しい解析法と,サブ線形後悔を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-10T04:15:38Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization [0.0]
  We study the problem of global optimization, where we analyze the performance of the Piyavskii-Shubert algorithm and its variants。 その結果,提案アルゴリズムはクエリを効率よく決定し,最小限の(ログファクタまで)累積的後悔を実現する。
  論文  参考訳（メタデータ） (2021-08-24T17:36:33Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Smooth Bandit Optimization: Generalization to H\"older Space [37.15553727896912]
  我々は、目標が累積後悔である滑らかな報酬関数のバンディット最適化を考える。 私たちの主な結果は、指数 $alpha>1$ を持つ H"older space への報酬関数の一般化です。 私たちは、$alphaleq 1$サブセット内で、既存の下限に適合する後悔率を達成することを示します。
  論文  参考訳（メタデータ） (2020-12-11T01:43:25Z)

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

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