論文の概要: Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime

• arxiv url: http://arxiv.org/abs/2610.06213v1
• Date: Mon, 05 Oct 2026 12:23:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-09 17:51:15.399339
• Title: Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime
• Title（参考訳）: LinUCBのサンプリングアロケーション:小ギャップレジームにおける最適設計限界
• Abstract要約: 我々は,LinUCB の小ギャップ系におけるサンプリング割り当てについて検討し,報酬ギャップは決定地平線上で最大$n-1/2$である。 このスケーリングは、LinUCBが$n$の対数係数にほぼ最適であることが知られている、最悪の後悔の低いバウンダリの根底にあるハードインスタンスをキャプチャする。
• 参考スコア（独自算出の注目度）: 52.72674885287868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the sampling allocation of LinUCB in the small-gap regime, where the reward gaps are of order at most $n^{-1/2}$ over the decision horizon $n$. This scaling captures the hard instances underlying worst-case regret lower bounds, for which LinUCB is known to be near optimal up to logarithmic factors in $n$. Using a mean-field perspective, we characterize this allocation through the empirical sampling distribution, a macroscopic object that averages the effect of adaptive decisions over the horizon, and identify its limit as $n\to\infty$. We establish that in this regime, the empirical sampling distribution induced by LinUCB converges to the set of D-optimal designs. This central result reveals that, in the small-gap regime, LinUCB not only achieves near optimal minimax regret but also allocates samples in a way that is asymptotically efficient for learning the reward parameter, thereby connecting regret-driven online learning with information-efficient experimental design. Building on the optimal design limit, we obtain two useful consequences. First, we refine the asymptotic regret analysis of LinUCB in the small-gap regime by characterizing its leading-order constant in the limit. Second, we show that, despite LinUCB's adaptive sampling strategy, the regularized least-squares estimator satisfies a central-limit-type theorem in the small-gap regime, thereby enabling valid statistical inference for the reward parameter.
• Abstract（参考訳）: 我々は,LinUCB の小ギャップ系におけるサンプリング割り当てについて検討し,報酬ギャップは最大$n^{-1/2}$で決定的地平線上では$n^{-1/2}$である。 このスケーリングは、LinUCBが$n$の対数係数にほぼ最適であることが知られている、最悪の後悔の低いバウンダリの根底にあるハードインスタンスをキャプチャする。 平均場パースペクティブを用いて、地平線上の適応的決定の効果を平均化するマクロオブジェクトである経験的サンプリング分布を通して、この割り当てを特徴付け、その極限を$n\to\infty$と同定する。 この状態において、LinUCBによって誘導される経験的サンプリング分布は、D-最適設計の集合に収束する。 この中心的な結果から,LinUCBは最小限の最小限の後悔に近づいただけでなく,報酬パラメータを学習するのに漸近的に効率的な方法でサンプルを割り当てることで,後悔駆動型オンライン学習と情報効率のよい実験設計を結びつけることが示唆された。 最適設計限界に基づいて、2つの有用な結果が得られる。 まず,LinUCBの低ギャップ状態における漸近的後悔解析を,その限界における先行次定数を特徴付けることによって洗練する。 第2に、LinUCBの適応サンプリング戦略にもかかわらず、正規化最小二乗推定器は小ギャップ法における中心極限型定理を満たすことを示し、報酬パラメータの統計的推測を可能にする。

関連論文リスト

• Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments [1.8224668251608893]
  層状サンプリングは古典的な分散低減手法であるが、その有効性は層がどのように構築されるかに大きく依存する。 最適マルチウェイ決定木を用いた階層化サンプリングのための最適化に基づく階層化フレームワークを提案する。 実世界のデータセットとシミュレーションデータセットの両方の実験は、OMSTが既存の手法に匹敵する、あるいは優れた分散還元を達成することを示した。
  論文  参考訳（メタデータ） (2026-09-20T02:52:03Z)
• Zero-Order Optimization for LLM Fine-Tuning via Learnable Direction Sampling [40.94400211806987]
  摂動方向のサンプリング分布を学習可能なポリシとして扱う政策駆動型ZOフレームワークを提案する。 学習したサンプリングは、品質勾配情報を改善し、$d$の収束境界への明示的な依存を緩和することを示す。 以上の結果から,適応方向サンプリングはZOの微調整を大規模に実現する上で有望な方法であることが示唆された。
  論文  参考訳（メタデータ） (2026-02-14T08:01:41Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack [74.5144793386864]
  LSDATは、入力サンプルのスパース成分と対向サンプルのスパース成分によって形成される低次元部分空間における摂動を加工する。 LSDは画像ピクセル領域で直接動作し、スパース性などの非$ell$制約が満たされることを保証します。
  論文  参考訳（メタデータ） (2021-03-19T13:10:47Z)

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

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