論文の概要: The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin

• arxiv url: http://arxiv.org/abs/2511.03708v1
• Date: Wed, 05 Nov 2025 18:42:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-06 18:19:32.521716
• Title: The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin
• Title（参考訳）: バッチ非パラメトリック帯域における適応障壁:未知マージンの価格のシャープ特性
• Authors: Rong Jiang, Cong Ma,
• Abstract要約: 本研究は,$alpha$が不明な辺境条件下で,バッチ処理した非パラメトリックバンディットについて検討した。 我々は、後悔と$alpha$を知っている託宣の比率として定義される後悔のインフレーション基準を導入する。 最適後悔インフレーション問題は、指数指数の値によって正確に与えられる水平線$T$で増大することを示す。
• 参考スコア（独自算出の注目度）: 6.1384839775448325
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study batched nonparametric contextual bandits under a margin condition when the margin parameter $\alpha$ is unknown. To capture the statistical price of this ignorance, we introduce the regret inflation criterion, defined as the ratio between the regret of an adaptive algorithm and that of an oracle knowing $\alpha$. We show that the optimal regret inflation grows polynomial with the horizon $T$, with exponent precisely given by the value of a convex optimization problem involving the dimension, smoothness, and batch budget. Moreover, the minimizers of this optimization problem directly prescribe the batch allocation and exploration strategy of a rate-optimal algorithm. Building on this principle, we develop RoBIN (RObust batched algorithm with adaptive BINning), which achieves the optimal regret inflation up to logarithmic factors. These results reveal a new adaptivity barrier: under batching, adaptation to an unknown margin parameter inevitably incurs a polynomial penalty, sharply characterized by a variational problem. Remarkably, this barrier vanishes when the number of batches exceeds $\log \log T$; with only a doubly logarithmic number of updates, one can recover the oracle regret rate up to polylogarithmic factors.
• Abstract（参考訳）: マージンパラメータ$\alpha$が不明な場合、マージン条件下でバッチした非パラメトリックなコンテキスト帯域について検討する。 この無知の統計的価格を捉えるために、適応アルゴリズムの後悔と$\alpha$を知っているオラクルの後悔の比率として定義される後悔のインフレーション基準を導入する。 最適後悔インフレーションは, 次元, 滑らかさ, バッチ予算を含む凸最適化問題の値から, 偏差$T$で多項式を増大させることを示した。 さらに、この最適化問題の最小化者は、レート最適化アルゴリズムのバッチ割り当てと探索戦略を直接規定する。 この原理に基づいて,ロバストバッチアルゴリズムと適応的BINニングを併用したRoBIN (Robust batched algorithm with Adaptive BINning) を開発した。 これらの結果から, バッチ化において未知のマージンパラメータへの適応は必然的に多項式ペナルティを生じさせるが, 変動問題によって著しく特徴づけられる。 この障壁は、バッチ数が$\log \log T$を超えると消滅し、二重対数的な更新数だけで、オラクルの後悔率をポリ対数的要素まで回復することができる。

関連論文リスト

• Non-stationary Bandit Convex Optimization: A Comprehensive Study [28.086802754034828]
  Bandit Convex Optimizationは、シーケンシャルな意思決定問題のクラスである。 非定常環境でこの問題を研究する。 非定常性の標準的な3つの基準の下で、後悔を最小限に抑えることを目指しています。
  論文  参考訳（メタデータ） (2025-06-03T15:18:41Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Minimax Rate-Optimal Algorithms for High-Dimensional Stochastic Linear Bandits [1.2010968598596632]
  我々は、T$のラウンドで複数のアームで線形バンディット問題を研究した。 ラッソ推定器はシーケンシャルセッティングにおいて確実に準最適であることを示す。 しきい値付きラッソを主推定法として用いた3段アーム選択アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-05-23T02:20:00Z)
• Minimax Optimality in Contextual Dynamic Pricing with General Valuation Models [8.981637739384674]
  意思決定者は、観測可能なコンテキストに基づいてパーソナライズされた価格を投稿する。 それぞれのバリュエーションはコンテキストの未知の潜在関数としてモデル化され、独立性と同一に分散された市場ノイズによって破損する。
  論文  参考訳（メタデータ） (2024-06-24T23:43:56Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Autoregressive Bandits [58.46584210388307]
  本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。 報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。 次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
  論文  参考訳（メタデータ） (2022-12-12T21:37:36Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
  論文  参考訳（メタデータ） (2022-01-18T17:24:20Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards [24.983866845065926]
  我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。 本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。 提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
  論文  参考訳（メタデータ） (2020-10-24T10:44:02Z)
• Nonstationary Reinforcement Learning with Linear Function Approximation [19.521419943509784]
  ドリフト環境下での線形関数近似によるマルコフ決定過程(MDP)における強化学習について考察する。 まず、周期的再起動を伴う最小二乗値の楽観的な修正を開発し、変動予算が分かっている場合にその動的後悔を束縛する。 非定常線型 MDP に対する最初の minimax dynamic regret lower bound を導出し、副生成物として Jin らによって未解決の線型 MDP に対する minimax regret lower bound を定めている。
  論文  参考訳（メタデータ） (2020-10-08T20:07:44Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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