論文の概要: Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret

• arxiv url: http://arxiv.org/abs/2205.14790v1
• Date: Sun, 29 May 2022 23:55:36 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-31 18:49:49.653211
• Title: Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret
• Title（参考訳）: チャージペイオフ時の非定常帯域:サブリニアレグレットによる計画の改善
• Authors: Orestis Papadigenopoulos, Constantine Caramanis, Sanjay Shakkottai
• Abstract要約: マルチアームバンディット設定は、最近非定常状態において研究されている。 各アクションの平均的なペイオフは、前回のプレイ以来のラウンド数の増加しない機能である。 我々は,我々のアルゴリズムがサブ線形後悔を伴う帯域幅アルゴリズムにどのように変換されるかを示す。
• 参考スコア（独自算出の注目度）: 34.44347218903429
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The stochastic multi-armed bandit setting has been recently studied in the non-stationary regime, where the mean payoff of each action is a non-decreasing function of the number of rounds passed since it was last played. This model captures natural behavioral aspects of the users which crucially determine the performance of recommendation platforms, ad placement systems, and more. Even assuming prior knowledge of the mean payoff functions, computing an optimal planning in the above model is NP-hard, while the state-of-the-art is a $1/4$-approximation algorithm for the case where at most one arm can be played per round. We first focus on the setting where the mean payoff functions are known. In this setting, we significantly improve the best-known guarantees for the planning problem by developing a polynomial-time $(1-{1}/{e})$-approximation algorithm (asymptotically and in expectation), based on a novel combination of randomized LP rounding and a time-correlated (interleaved) scheduling method. Furthermore, our algorithm achieves improved guarantees -- compared to prior work -- for the case where more than one arm can be played at each round. Moving to the bandit setting, when the mean payoff functions are initially unknown, we show how our algorithm can be transformed into a bandit algorithm with sublinear regret.
• Abstract（参考訳）: 確率的多腕バンディットセッティングは、最近は非定常体制において研究されており、各アクションの平均ペイオフは、最後に演奏されてから経過したラウンド数の非減算関数である。 このモデルは、レコメンデーションプラットフォームや広告配置システムなどのパフォーマンスを決定的に決定するユーザの自然な行動的側面を捉えます。 平均ペイオフ関数の事前知識を仮定しても、上述のモデルにおける最適計画計算はNPハードであり、最先端のアルゴリズムは1ラウンド当たり1本以上の腕をプレイできる場合の1/4$近似アルゴリズムである。 まず、平均ペイオフ関数が知られている設定に焦点を合わせます。 この設定では、ランダム化LPラウンドリングと時間関連(インターリーブ)スケジューリングの新たな組み合わせに基づいて、多項式時間(1-{1}/{e})$-approximationアルゴリズム(漸近および期待)を開発することにより、計画問題の最もよく知られている保証を大幅に改善する。 さらに,本アルゴリズムは,各ラウンドで複数のアームをプレイできる場合に,先行作業と比較して,改良された保証を実現する。 バンディット設定に移行すると、平均ペイオフ関数が未知の場合、我々のアルゴリズムがサブ線形後悔を伴うバンディットアルゴリズムにどのように変換されるかを示す。

関連論文リスト

• Near-Optimal Algorithm for Non-Stationary Kernelized Bandits [6.379833644595456]
  時変ベイズ最適化(英語版)とも呼ばれる非定常カーネル化バンドイット問題(KB)について検討する。 我々は,2乗指数およびマタン核を持つ非定常KBに対して,アルゴリズムに依存しない最初のリフレッシュローバウンドを示す。 本稿では,ランダムな置換による位相除去を再開する手法を提案する。
  論文  参考訳（メタデータ） (2024-10-21T14:28:26Z)
• 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)
• Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
  この仕事の動機は、再現可能な機械学習の需要の増加にある。 特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
  論文  参考訳（メタデータ） (2024-02-12T03:31:34Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。 我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。 GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
  論文  参考訳（メタデータ） (2022-02-03T21:19:36Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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