論文の概要: Detection Is All You Need: A Feasible Optimal Prior-Free Black-Box Approach For Piecewise Stationary Bandits

• arxiv url: http://arxiv.org/abs/2501.19401v1
• Date: Fri, 31 Jan 2025 18:57:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-03 14:03:26.824405
• Title: Detection Is All You Need: A Feasible Optimal Prior-Free Black-Box Approach For Piecewise Stationary Bandits
• Title（参考訳）: 必要なものはすべて検出する: 適度に固定されたバンドに最適なプリ・フリーのブラックボックスアプローチ
• Authors: Argyrios Gerogiannis, Yu-Han Huang, Subhonmesh Bose, Venugopal V. Veeravalli,
• Abstract要約: 基礎となる非定常性に関する事前の知識を必要とせず, 断片的な定常的包帯の問題について検討する。 我々は、最も一般的なパラメトリックバンディット変種に適用可能な、最初の$textitfeasible$ black-boxアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 16.606885016888306
• License:
• Abstract: We study the problem of piecewise stationary bandits without prior knowledge of the underlying non-stationarity. We propose the first $\textit{feasible}$ black-box algorithm applicable to most common parametric bandit variants. Our procedure, termed Detection Augmented Bandit (DAB), is modular, accepting any stationary bandit algorithm as input and augmenting it with a change detector. DAB achieves optimal regret in the piecewise stationary setting under mild assumptions. Specifically, we prove that DAB attains the order-optimal regret bound of $\tilde{\mathcal{O}}(\sqrt{N_T T})$, where $N_T$ denotes the number of changes over the horizon $T$, if its input stationary bandit algorithm has order-optimal stationary regret guarantees. Applying DAB to different parametric bandit settings, we recover recent state-of-the-art results. Notably, for self-concordant bandits, DAB achieves optimal dynamic regret, while previous works obtain suboptimal bounds and require knowledge on the non-stationarity. In simulations on piecewise stationary environments, DAB outperforms existing approaches across varying number of changes. Interestingly, despite being theoretically designed for piecewise stationary environments, DAB is also effective in simulations in drifting environments, outperforming existing methods designed specifically for this scenario.
• Abstract（参考訳）: 基礎となる非定常性に関する事前の知識を必要とせず, 断片的な定常的包帯の問題について検討する。 我々は、最も一般的なパラメトリックバンディット変種に適用可能な最初の$\textit{feasible}$ black-boxアルゴリズムを提案する。 提案手法はDAB ( Detection Augmented Bandit) と呼ばれるモジュール式であり,任意の固定帯域アルゴリズムを入力として受け入れ,変更検出器で拡張する。 DABは、軽微な仮定の下で、断片的な定常状態において最適な後悔を達成する。 具体的には、DABが$\tilde{\mathcal{O}}(\sqrt{N_TT})$のオーダー最適後悔境界に達することを証明している。 DABを異なるパラメトリックバンディット設定に適用することにより、最近の最先端の結果を回復する。 特に、自己協和バンドにとって、DABは最適な動的後悔を達成する一方、以前の研究は最適下界を取得し、非定常性に関する知識を必要とする。 断片的な定常環境のシミュレーションでは、DABは様々な変化に対して既存のアプローチよりも優れています。 興味深いことに、DABは理論上は断片的な定常環境のために設計されているが、ドリフト環境のシミュレーションにも有効であり、このシナリオのために設計された既存の手法よりも優れている。

関連論文リスト

• 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)
• Adaptive Regret for Bandits Made Possible: Two Queries Suffice [26.769372199571002]
  我々は、強い適応的後悔という厳密な概念の下で、クエリと後悔の最適包帯アルゴリズムを与える。 驚いたことに、1ラウンドあたり2つのクエリで$tildeO(sqrtn|I|)$ Adaptive Bandit Learner(StABL)を達成できる。
  論文  参考訳（メタデータ） (2024-01-17T15:32:04Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)
• Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits [55.03293214439741]
  文脈的包帯では、エージェントは過去の経験に基づいた時間依存アクションセットから順次アクションを行う。 そこで本稿では,文脈的包帯のためのオンライン連続型ハイパーパラメータチューニングフレームワークを提案する。 理論上はサブ線形の後悔を達成でき、合成データと実データの両方において既存のすべての手法よりも一貫して優れた性能を発揮することを示す。
  論文  参考訳（メタデータ） (2023-02-18T23:31:20Z)
• Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret [34.44347218903429]
  マルチアームバンディット設定は、最近非定常状態において研究されている。 各アクションの平均的なペイオフは、前回のプレイ以来のラウンド数の増加しない機能である。 我々は,我々のアルゴリズムがサブ線形後悔を伴う帯域幅アルゴリズムにどのように変換されるかを示す。
  論文  参考訳（メタデータ） (2022-05-29T23:55:36Z)
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach [42.021871809877595]
  近静止環境における最適な後悔を伴う強化学習アルゴリズムを、非定常環境における最適な動的後悔を伴う別のアルゴリズムに変換するブラックボックス還元を提案する。 提案手法は, 線形包帯, エピソードMDP, 無限水平MDPの技量を有意に改善することを示す。
  論文  参考訳（メタデータ） (2021-02-10T12:43:31Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  GPバンディットアルゴリズムの残差境界と後部分布の複雑さのトレードオフを特徴付ける方法を示す。 大域的最適化に応用したGPバンディットアルゴリズムの精度と複雑性のトレードオフを観察する。
  論文  参考訳（メタデータ） (2020-03-23T21:05:15Z)

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

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