論文の概要: Tracking Most Significant Shifts in Infinite-Armed Bandits

• arxiv url: http://arxiv.org/abs/2502.00108v1
• Date: Fri, 31 Jan 2025 19:00:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 15:04:15.506183
• Title: Tracking Most Significant Shifts in Infinite-Armed Bandits
• Title（参考訳）: 無限整列バンドにおける最も重要なシフトの追跡
• Authors: Joe Suk, Jung-hun Kim,
• Abstract要約: 本研究では,貯水池分布からアクションの平均報酬をサンプリングする無限武装バンディット問題について検討する。 貯水池の正則性の全規則に対して, パラメータフリーな最適後悔境界を示す。 そこで我々は,無作為な除去の変種を用いることで,大きな変化の点におけるより厳密な後悔境界を適応的に達成できることを示した。
• 参考スコア（独自算出の注目度）: 3.591122855617648
• License:
• Abstract: We study an infinite-armed bandit problem where actions' mean rewards are initially sampled from a reservoir distribution. Most prior works in this setting focused on stationary rewards (Berry et al., 1997; Wang et al., 2008; Bonald and Proutiere, 2013; Carpentier and Valko, 2015) with the more challenging adversarial/non-stationary variant only recently studied in the context of rotting/decreasing rewards (Kim et al., 2022; 2024). Furthermore, optimal regret upper bounds were only achieved using parameter knowledge of non-stationarity and only known for certain regimes of regularity of the reservoir. This work shows the first parameter-free optimal regret bounds for all regimes while also relaxing distributional assumptions on the reservoir. We first introduce a blackbox scheme to convert a finite-armed MAB algorithm designed for near-stationary environments into a parameter-free algorithm for the infinite-armed non-stationary problem with optimal regret guarantees. We next study a natural notion of significant shift for this problem inspired by recent developments in finite-armed MAB (Suk & Kpotufe, 2022). We show that tighter regret bounds in terms of significant shifts can be adaptively attained by employing a randomized variant of elimination within our blackbox scheme. Our enhanced rates only depend on the rotting non-stationarity and thus exhibit an interesting phenomenon for this problem where rising rewards do not factor into the difficulty of non-stationarity.
• Abstract（参考訳）: 本研究では,貯水池分布からアクションの平均報酬をサンプリングする無限武装バンディット問題について検討する。 この設定における多くの先行研究は、固定報酬(Berry et al , 1997; Wang et al , 2008; Bonald and Proutiere, 2013; Carpentier and Valko, 2015)に焦点を絞ったものであり、より困難な対外的/非定常的変種は、最近になってローッティング/減少の文脈でのみ研究された(Kim et al , 2022; 2024)。 さらに, 最適後悔上限は, 非定常性のパラメータ知識を用いてのみ達成され, 貯水池の一定の規則性についてのみ知られている。 この研究は、全てのレジームに対して最初のパラメータフリー最適後悔境界を示し、また貯水池上の分布仮定を緩和する。 まず,有限武装MABアルゴリズムをパラメータフリーなアルゴリズムに変換するブラックボックス方式を提案する。 次に、有限武装MAB(Suk & Kpotufe, 2022)の最近の発展に触発された、この問題に対する重要なシフトの自然な概念について研究する。 我々は,ブラックボックス方式でランダムに除去した変種を用いることで,大きな変化の点におけるより厳密な後悔境界を適応的に達成できることを示す。 我々の上昇率は、回転する非定常性にのみ依存しており、この問題に対して、上昇する報酬が非定常性の難しさに影響を及ぼさない興味深い現象を示す。

関連論文リスト

• An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints [29.596684377841182]
  本研究では、休息状態において、アームの平均報酬が各プルで減少する可能性があるが、そうでなければ変化しない、無限に多くの武器を持つバンディット問題を考察する。 本稿では,ゆがみ報酬に起因するバイアスや分散トレードオフを管理するために,適応的なスライディングウィンドウを備えたUTBを利用するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-22T14:11:54Z)
• 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)
• 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)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• On Slowly-varying Non-stationary Bandits [25.305949034527202]
  我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。 我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。 我々のアルゴリズムは基本的にミニマックス最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-25T12:56:19Z)
• Break your Bandit Routine with LSD Rewards: a Last Switch Dependent Analysis of Satiation and Seasonality [6.146046338698175]
  そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。 我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。 我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
  論文  参考訳（メタデータ） (2021-10-22T14:53:13Z)
• On Limited-Memory Subsampling Strategies for Bandits [0.0]
  本稿では,Budry et al. (2020) の最近の研究で提案されている単純な決定論的部分サンプリング則が,一次元指数関数族において最適であることを示す。 また、これらの保証は、アルゴリズムメモリを時間軸の多対数関数に制限する場合にも有効であることを示す。 本稿では,近年の観測結果のみをサブサンプリングに用い,既知の急激な変化を前提とした最適後悔保証を実現するアルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2021-06-21T09:11:22Z)
• Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
  Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。 最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
  論文  参考訳（メタデータ） (2020-02-13T08:53:43Z)

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

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