論文の概要: Parameter-Free Dynamic Regret for Unconstrained Linear Bandits
- arxiv url: http://arxiv.org/abs/2603.25916v1
- Date: Thu, 26 Mar 2026 21:16:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-30 21:49:48.280381
- Title: Parameter-Free Dynamic Regret for Unconstrained Linear Bandits
- Title（参考訳）: 制約のない線形帯域に対するパラメータフリー動的レグレット
- Authors: Alberto Rumi, Andrew Jacobsen, Nicolò Cesa-Bianchi, Fabio Vitale,
- Abstract要約: 直交線形帯域問題における動的後悔について検討した。
順序の最適後悔保証を達成するために,線形帯域幅に対する最初のアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 21.35587581980097
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study dynamic regret minimization in unconstrained adversarial linear bandit problems. In this setting, a learner must minimize the cumulative loss relative to an arbitrary sequence of comparators $\boldsymbol{u}_1,\ldots,\boldsymbol{u}_T$ in $\mathbb{R}^d$, but receives only point-evaluation feedback on each round. We provide a simple approach to combining the guarantees of several bandit algorithms, allowing us to optimally adapt to the number of switches $S_T = \sum_t\mathbb{I}\{\boldsymbol{u}_t \neq \boldsymbol{u}_{t-1}\}$ of an arbitrary comparator sequence. In particular, we provide the first algorithm for linear bandits achieving the optimal regret guarantee of order $\mathcal{O}\big(\sqrt{d(1+S_T) T}\big)$ up to poly-logarithmic terms without prior knowledge of $S_T$, thus resolving a long-standing open problem.
- Abstract（参考訳）: 直交線形帯域問題における動的後悔の最小化について検討する。
この設定では、学習者は任意のコンパレータの列である $\boldsymbol{u}_1,\ldots,\boldsymbol{u}_T$ in $\mathbb{R}^d$ に対して累積損失を最小化しなければならないが、各ラウンドでのポイント評価フィードバックしか受け取らない。
いくつかのバンディットアルゴリズムの保証を組み合わせるための簡単なアプローチを提供し、任意のコンパレータ列のスイッチ数に最適化できる$S_T = \sum_t\mathbb{I}\{\boldsymbol{u}_t \neq \boldsymbol{u}_{t-1}\}$を提供する。
特に、次数 $\mathcal{O}\big(\sqrt{d(1+S_T) T}\big)$ を、S_T$ の事前の知識を伴わずに、多対数項までの最適後悔保証を達成するための最初のアルゴリズムを提供する。
関連論文リスト
- Efficient Simple Regret Algorithms for Stochastic Contextual Bandits [32.5817931126341]
簡単な後悔の目的の下で,文脈的ロジスティックな包帯について検討する。
本稿では, 簡単な後悔を解くアルゴリズムを初めて提案する。
我々はまた、単純回帰設定に合わせた新しいトンプソンサンプリングの変種も導入する。
論文 参考訳（メタデータ） (2026-01-29T02:09:13Z) - Dynamic Regret Reduces to Kernelized Static Regret [63.36965242404415]
本研究では,オンライン凸最適化において,任意のベンチマークシーケンスに対して低累積損失を達成することを目的とした動的後悔について検討する。
再生ケルネルヒルベルト空間 (RKHS) の形で適切な関数空間を構築することにより、最適$R_T(u_1,ldots,u_T) = MathcalO(sqrtsum_t|u_t-u_t-1|T)$ dynamic regret guarantee。
論文 参考訳（メタデータ） (2025-07-07T21:09:33Z) - An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。
R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-06-03T17:54:58Z) - Restless Linear Bandits [5.00389879175348]
未知の$mathbbRd$-valued stationary $varphi$-mixing sequence of parameters $(theta_t,t in mathbbN)$ が存在すると仮定される。
指数混合率が$theta_t$の場合、LinMix-UCBと呼ばれる楽観的なアルゴリズムが提案される。
論文 参考訳（メタデータ） (2024-05-17T14:37:39Z) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - 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) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。