論文の概要: Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise

• arxiv url: http://arxiv.org/abs/2609.17595v1
• Date: Sat, 12 Sep 2026 11:38:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.450274
• Title: Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise
• Title（参考訳）: 帯域改善のための事前自由競争率:スケール、曲率、水平は自由だが、騒音下では結合しない
• Abstract要約: 1ページのemphprobe-and-commitアルゴリズムが競合比4sqrt3,sqrt k$ for $Tge2lfloorsqrt krfloor$を達成することを証明した。 各地平線に対する最適比は、未知地平線に対しても$(sqrt k+k/T)$である。
• 参考スコア（独自算出の注目度）: 6.657272312990604
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the improving multi-armed bandits problem, each of $k$ arms has an unknown nondecreasing, discretely concave reward curve $f_i$, and pulling arm $i$ for the $t$-th time yields $f_i(t)$. For sufficiently long horizons, Blum and Ravichandran (ALT 2025) proved that randomized algorithms achieve an $O(\sqrt k)$ approximation to the best single arm when the scale $m=f^*(T)$ of the optimal arm is known ($T\ge2k$), and $O(\sqrt k\log k)$ when it is not ($T>4k$), against an $Ω(\sqrt k)$ lower bound. The logarithmic factor is unnecessary: a one-page \emph{probe-and-commit} algorithm achieves competitive ratio $4\sqrt3\,\sqrt k$ for $T\ge2\lfloor\sqrt k\rfloor$, without any knowledge of the scale, and we determine the optimal ratio for every horizon, $Θ(\sqrt k+k/T)$, also for unknown horizons. Without noise, \emph{no prior is needed at all}: a random-marginal probing algorithm reading neither the scale $m$, nor the concavity-envelope exponent $β$ of Blum, Garicano, Ravichandran and Sharma (UAI 2026), nor the horizon $T$, achieves the optimal $Θ(k^{β/(1+β)}+k/T)$ simultaneously for every $β$ and every horizon. Under the multiplicative noise model of Blum and Ravichandran, probe-and-commit keeps the same all-horizon order $Θ(\sqrt k+k/T)$ without knowing the noise level (and $Θ(\sqrt k)$ on the same range), but the price of priors jumps: for any fixed noise level $\varepsilon\in(0,1/2]$, the uniform price of adaptation $φ_\varepsilon(k)$ --- the worst case over horizons $T\ge16k$ of the loss relative to $k^{β/(1+β)}$ for algorithms knowing neither $m$ nor $β$ --- is $Θ_\varepsilon(\sqrt{\log k/\log\log k})$, the lower bound asymptotic in $k$ at fixed positive $\varepsilon$ and matched by a nested random-permutation probing algorithm, whereas knowing either $m$ or $β$ alone restores a constant price.
• Abstract（参考訳）: 改良されたマルチアームバンディット問題において、$k$の各アームは未知の非減少性を持ち、離散的に報酬曲線が$f_i$であり、$t$-thのプルアーム$i$は$f_i(t)$である。 十分に長い地平線に対して、Blum と Ravichandran (ALT 2025) は、最適腕のスケール $m=f^*(T)$が知られている(T\ge2k$)と$O(\sqrt k\log k)$が知られていない(T>4k$)と、$Ω(\sqrt k)$下界に対してランダム化されたアルゴリズムが最高の単腕に$O(\sqrt k)$近似することを示した。 対数係数は不要である: 1ページ {\displaystyle \emph{probe-and-commit} アルゴリズムは、4\sqrt3\,\sqrt k$ for $T\ge2\lfloor\sqrt k\rfloor$に対して、スケールの知識のない競合比を達成し、すべての地平線に対する最適比を$(\sqrt k+k/T)$、未知の地平線に対しても決定する。 スケール$m$も共共振器付き指数$β$ of Blum, Garicano, Ravichandran, Sharma (UAI 2026)も、地平線$T$も、すべてのβ$とすべての地平線に対して同時に最適な$(k^{β/(1+β)}+k/T)$を達成する。 Blum と Ravichandran の乗法的ノイズモデルの下では、プローブ・アンド・コミットは、ノイズレベルを知らずに、同じ全水平順序を$(\sqrt k+k/T)$で保持するが(同じ範囲で)、先行値の価格が上昇する:任意の固定ノイズレベル $\varepsilon\in(0,1/2]$の場合、適応の均一価格 $φ_\varepsilon(k)$ --- 水平線上の最悪の場合 $T\ge16k$$$$k^{β/(1+β)}$-- は、$m$も$β$も知らないアルゴリズムに対して$--- は$\varepsilon(\sqrt k\log/k\log)$---- と$- は、固定ノイズレベル $\varepsilon\in(0,1/2)$--- と$-- と$- と$- と$- と$- と$- と$- と$- は一致しない。

関連論文リスト

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Algorithms for Sparse LPN and LSPN Against Low-noise [1.2143710013809321]
  ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。 我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースCSP(SparseCSP)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいフレームワークである。
  論文  参考訳（メタデータ） (2024-07-27T08:57:04Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)

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

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