論文の概要: A Perturbation Approach to Unconstrained Linear Bandits

• arxiv url: http://arxiv.org/abs/2603.28201v1
• Date: Mon, 30 Mar 2026 09:17:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-31 23:18:45.318391
• Title: A Perturbation Approach to Unconstrained Linear Bandits
• Title（参考訳）: 制約のない線形帯域に対する摂動的アプローチ
• Abstract要約: 我々は、制約のない帯域線形最適化(uBLO)の文脈で、Abernethy et al. (2008) の標準摂動に基づくアプローチを再考する。 制約のない環境では、バンド線形最適化(BLO)を標準オンライン線形最適化(OLO)問題に効果的に還元することを示す。
• 参考スコア（独自算出の注目度）: 48.45987210959519
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO). We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem. Our framework improves on prior work in several ways. First, we derive expected-regret guarantees when our perturbation scheme is combined with comparator-adaptive OLO algorithms, leading to new insights about the impact of different adversarial models on the resulting comparator-adaptive rates. We also extend our analysis to dynamic regret, obtaining the optimal $\sqrt{P_T}$ path-length dependencies without prior knowledge of $P_T$. We then develop the first high-probability guarantees for both static and dynamic regret in uBLO. Finally, we discuss lower bounds on the static regret, and prove the folklore $Ω(\sqrt{dT})$ rate for adversarial linear bandits on the unit Euclidean ball, which is of independent interest.
• Abstract（参考訳）: 我々は、制約のない帯域線形最適化(uBLO)の文脈で、Abernethy et al (2008) の標準摂動に基づくアプローチを再検討する。 制約のない環境では、バンド線形最適化(BLO)を標準オンライン線形最適化(OLO)問題に効果的に還元することを示す。 私たちのフレームワークは、いくつかの方法で先行作業を改善します。 まず、摂動スキームとコンパレータ適応型OLOアルゴリズムを組み合わせることで、異なる逆モデルが結果のコンパレータ適応率に与える影響について新たな知見を得る。 また、解析を動的後悔にまで拡張し、$P_T$の事前知識なしで最適な$\sqrt{P_T}$パス長の依存関係を得る。 次に、uBLOにおける静的および動的後悔の両方に対する最初の高確率保証を開発する。 最後に、静的な後悔の下位境界について論じ、独立な興味を持つユークリッド球面上の逆線型包帯に対して、フォークロア$Ω(\sqrt{dT})$レートを証明した。

関連論文リスト

• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 本稿では,ウィンドウ/リスタートベースアルゴリズムと同様に,より単純な重みに基づくアルゴリズムを提案する。 我々のフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2026-01-03T04:50:21Z)
• Towards a Unified Analysis of Neural Networks in Nonparametric Instrumental Variable Regression: Optimization and Generalization [66.08522228989634]
  非パラメトリックインスツルメンタル変数回帰(NPIV)における2段階最小二乗法(2SLS)アプローチのためのニューラルネットワークの最初の大域収束結果を確立する。 これは平均場ランゲヴィンダイナミクス(MFLD)を通して持ち上げられた視点を採用することで達成される。
  論文  参考訳（メタデータ） (2025-11-18T17:51:17Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Experimental Design for Semiparametric Bandits [11.156009461711639]
  両腕の報酬が線形成分と未知の、潜在的に敵対的なシフトを組み合わせた有限腕半パラメトリックバンドについて検討する。 我々は,シャープな後悔境界,PAC境界,ベストアーム識別保証を同時に提供する最初の実験設計手法を提案する。
  論文  参考訳（メタデータ） (2025-06-16T11:53:00Z)
• Constrained Linear Thompson Sampling [39.724313550777715]
  Constrained Linear Thompson Sampling (COLTS)は、摂動線形プログラムを解くことでアクションを選択するサンプリングベースのフレームワークである。 S-COLTSはゼロリスクと$widetildeO(sqrtd3 T)を許容するが、R-COLTSは$widetildeO(sqrtd3 T)を許容する。
  論文  参考訳（メタデータ） (2025-03-03T20:44:58Z)
• Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints [31.526232903811533]
  我々はOCO(Optimistically Safe OCO)と呼ぶアルゴリズムを導入し、そのアルゴリズムが$tildeO(sqrtT)$ regretと制約違反がないことを示す。 静的線形制約の場合、これは同じ仮定の下で、以前の最もよく知られた $tildeO(T2/3)$ regret よりも改善される。 時間的制約の場合、当社の作業は、$O(sqrtT)$ regretと$O(sqrtT)$ cumulative violationを示す既存の結果を補完します。
  論文  参考訳（メタデータ） (2024-03-09T04:01:39Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。 我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
  論文  参考訳（メタデータ） (2021-11-22T21:52:47Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)

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

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