論文の概要: Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms

• arxiv url: http://arxiv.org/abs/2505.24692v1
• Date: Fri, 30 May 2025 15:15:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-02 19:47:53.028016
• Title: Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms
• Title（参考訳）: クイックドローバンド:非常に多くのアームを持つ非定常環境でのクイックオプティマイズ
• Authors: Derek Everett, Fred Lu, Edward Raff, Fernando Camacho, James Holt,
• Abstract要約: 本稿では,ガウス的手法を用いて連続空間上の報酬環境を学習するための新しいポリシーを提案する。 提案手法は,$mathcalO*(sqrtT)$ cumulative regret を用いて連続リプシッツ報酬関数を効率よく学習することを示す。
• 参考スコア（独自算出の注目度）: 80.05851139852311
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Canonical algorithms for multi-armed bandits typically assume a stationary reward environment where the size of the action space (number of arms) is small. More recently developed methods typically relax only one of these assumptions: existing non-stationary bandit policies are designed for a small number of arms, while Lipschitz, linear, and Gaussian process bandit policies are designed to handle a large (or infinite) number of arms in stationary reward environments under constraints on the reward function. In this manuscript, we propose a novel policy to learn reward environments over a continuous space using Gaussian interpolation. We show that our method efficiently learns continuous Lipschitz reward functions with $\mathcal{O}^*(\sqrt{T})$ cumulative regret. Furthermore, our method naturally extends to non-stationary problems with a simple modification. We finally demonstrate that our method is computationally favorable (100-10000x faster) and experimentally outperforms sliding Gaussian process policies on datasets with non-stationarity and an extremely large number of arms.
• Abstract（参考訳）: マルチアームバンディットのための標準的なアルゴリズムは、通常、アクション空間(腕の数)が小さい静止的な報酬環境を仮定する。 既存の非定常的バンディットポリシーは少数のアームのために設計され、一方リプシッツ、線形およびガウス的プロセスバンディットポリシーは、報酬関数の制約の下で静止的な報酬環境において、大きな(または無限の)アームを扱うように設計されている。 本稿では,ガウス補間法を用いて連続空間上の報酬環境を学習するための新しいポリシーを提案する。 本手法は, 連続リプシッツ報酬関数を$\mathcal{O}^*(\sqrt{T})$ cumulative regret で効率的に学習することを示す。 さらに本手法は, 簡単な修正を加えて, 非定常問題にまで自然に拡張する。 我々は最終的に,本手法が計算上有利であることを示した(100-10000倍高速)。

関連論文リスト

• Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits [31.212504858546232]
  ヘビーテールの片側定常バンディット問題に対処する。 重み付き分布に適した新しいカタニスタイル変化点検出戦略を提案する。 本稿では,この変化点検出戦略と楽観的アルゴリズムを組み合わせたロバストCPD-UCBを提案する。
  論文  参考訳（メタデータ） (2025-05-26T14:40:47Z)
• 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)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization [29.579719765255927]
  本稿では,文脈的帯域幅設定のための効率的な帯域幅アルゴリズムのファミリーを提案する。 我々のアルゴリズムは任意の関数クラスで動作し、不特定性をモデル化するのに堅牢で、連続したアーム設定で使用できます。
  論文  参考訳（メタデータ） (2023-07-05T08:34:54Z)
• PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits [29.097522376094624]
  そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。 我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
  論文  参考訳（メタデータ） (2022-10-25T19:13:20Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。 我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
  論文  参考訳（メタデータ） (2020-03-05T21:29:27Z)

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

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