論文の概要: Rotting Infinitely Many-armed Bandits beyond the Worst-case Rotting: An Adaptive Approach

• arxiv url: http://arxiv.org/abs/2404.14202v1
• Date: Mon, 22 Apr 2024 14:11:54 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-23 13:47:08.921074
• Title: Rotting Infinitely Many-armed Bandits beyond the Worst-case Rotting: An Adaptive Approach
• Title（参考訳）: 最悪のローティングを超えて無限に多腕のバンドを回転させる:適応的アプローチ
• Authors: Jung-hun Kim, Milan Vojnovic, Se-Young Yun,
• Abstract要約: 本研究では、ロッティング環境における無数の武装バンディット問題について検討し、各プルで腕の平均報酬が減少するが、それ以外は変化しない。 本稿では,ゆがみ報酬に起因するバイアスや分散トレードオフを管理するために,適応的なスライディングウィンドウを備えたUTBを利用するアルゴリズムを提案する。 提案アルゴリズムは, 遅い, 突然のローティングシナリオの双方に対して, 厳密な後悔境界を達成できる。
• 参考スコア（独自算出の注目度）: 29.596684377841182
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this study, we consider the infinitely many armed bandit problems in rotting environments, where the mean reward of an arm may decrease with each pull, while otherwise, it remains unchanged. We explore two scenarios capturing problem-dependent characteristics regarding the decay of rewards: one in which the cumulative amount of rotting is bounded by $V_T$, referred to as the slow-rotting scenario, and the other in which the number of rotting instances is bounded by $S_T$, referred to as the abrupt-rotting scenario. To address the challenge posed by rotting rewards, we introduce an algorithm that utilizes UCB with an adaptive sliding window, designed to manage the bias and variance trade-off arising due to rotting rewards. Our proposed algorithm achieves tight regret bounds for both slow and abrupt rotting scenarios. Lastly, we demonstrate the performance of our algorithms using synthetic datasets.
• Abstract（参考訳）: 本研究では、ロッティング環境における無数の武装バンディット問題について検討し、各プルで腕の平均報酬が減少するが、それ以外は変化しない。 報奨の減衰に関する問題依存的な特徴をとらえるシナリオを2つ検討する。1つは、累積ローッティング量が、スローローッティングシナリオと呼ばれる$V_T$で、もう1つは、突然ローッティングシナリオと呼ばれる$S_T$で、またもう1つは、ローッティングインスタンスの数が、突発ローッティングシナリオと呼ばれる$S_T$で有界である。 ローティング報酬による課題に対処するため,ローッティング報酬によるバイアスと分散トレードオフを管理するために,適応的なスライディングウインドウを備えたUPBを利用するアルゴリズムを導入する。 提案アルゴリズムは, 遅い, 突然のローティングシナリオの双方に対して, 厳密な後悔境界を達成できる。 最後に,合成データセットを用いたアルゴリズムの性能を示す。

関連論文リスト

• 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)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Contextual bandits with concave rewards, and an application to fair ranking [108.48223948875685]
  CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。 我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。 推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
  論文  参考訳（メタデータ） (2022-10-18T16:11:55Z)
• The price of unfairness in linear bandits with biased feedback [62.25313751895011]
  線形帯域フィードバックによる逐次意思決定の問題点について検討する。 その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。 興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
  論文  参考訳（メタデータ） (2022-03-18T08:03:20Z)
• Risk-Aware Algorithms for Combinatorial Semi-Bandits [7.716156977428555]
  半帯域フィードバック下でのマルチアームバンディット問題について検討する。 本稿では,最悪の場合の報酬のみを考慮したリスク尺度であるCVaR(Conditional Value-at-Risk)の最大化の問題を検討する。 本稿では,バンディットのスーパーアームから得られる報酬のCVaRを最大化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-02T11:29:43Z)
• On Slowly-varying Non-stationary Bandits [25.305949034527202]
  我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。 我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。 我々のアルゴリズムは基本的にミニマックス最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-25T12:56:19Z)
• Multi-armed Bandit Algorithm against Strategic Replication [5.235979896921492]
  我々は,各エージェントが一組のアームを登録する多腕バンディット問題を考慮し,各エージェントがそのアームを選択すると報酬を受け取る。 エージェントは、より多くの武器を複製で戦略的に送信し、バンディットアルゴリズムの探索と探索のバランスを悪用することで、より多くの報酬をもたらす可能性がある。 本稿では,複製の復号化と,最小限の累積後悔を実現するバンディットアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-23T07:38:44Z)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。 本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-13T12:25:41Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)

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

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