論文の概要: On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits

• arxiv url: http://arxiv.org/abs/2603.10346v1
• Date: Wed, 11 Mar 2026 02:34:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-12 16:22:32.753332
• Title: On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits
• Title（参考訳）: 非定常線形帯域におけるBest-Arm識別の複雑さについて
• Authors: Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson, Maryam Fazel,
• Abstract要約: 非定常線形包帯における固定予算ベストアーム識別問題について検討する。 学習者は、最大累積報酬$x_* = argmax_xを高い確率でxtopsum_t=1T _t$で識別することを目的とする。
• 参考スコア（独自算出の注目度）: 15.93884263655552
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the fixed-budget best-arm identification (BAI) problem in non-stationary linear bandits. Concretely, given a fixed time budget $T\in \mathbb{N}$, finite arm set $\mathcal{X} \subset \mathbb{R}^d$, and a potentially adversarial sequence of unknown parameters $\lbrace θ_t\rbrace_{t=1}^{T}$ (hence non-stationary), a learner aims to identify the arm with the largest cumulative reward $x_* = \arg\max_{x \in \mathcal{X}} x^\top\sum_{t=1}^T θ_t$ with high probability. In this setting, it is well-known that uniformly sampling arms from the G-optimal design yields a minimax-optimal error probability of $\exp\left(-Θ\left(T / H_{G}\right)\right)$, where $H_{G}$ scales proportionally with the dimension $d$. However, this notion of complexity is overly pessimistic, as it is derived from a lower bound in which the arm set consists only of the standard basis vectors, thus masking any potential advantages arising from arm sets with richer geometric structure. To address this, we establish an arm-set-dependent lower bound that, in contrast, holds for any arm set. Motivated by the ideas underlying our lower bound, we propose the Adjacent-optimal design, a specialization of the well-known $\mathcal{X}\mathcal{Y}$-optimal design, and develop the $\textsf{Adjacent-BAI}$ algorithm. We prove that the error probability of $\textsf{Adjacent-BAI}$ matches our lower bound up to constants, verifying the tightness of our lower bound, and establishing the arm-set-dependent complexity of this setting.
• Abstract（参考訳）: 非定常線形帯域における固定予算ベストアーム識別(BAI)問題について検討する。 具体的には、固定時間予算$T\in \mathbb{N}$、有限アームセット$\mathcal{X} \subset \mathbb{R}^d$、および未知パラメータの潜在的逆列$\lbrace θ_t\rbrace_{t=1}^{T}$(hence non-stationary)を与えられた場合、学習者は、最大累積報酬$x_* = \arg\max_{x \in \mathcal{X}} x^\top\sum_{t=1}^T θ_t$を高い確率で特定することを目指す。 この設定では、G-最適設計からアームを均一にサンプリングすると、$\exp\left(T / H_{G}\right)\right)$のミニマックス最適誤差確率が得られ、$H_{G}$は次元$d$と比例してスケールする。 しかし、この複雑性の概念は過度に悲観的であり、これはアーム集合が標準基底ベクトルのみからなる下界から派生しており、したがってよりリッチな幾何学構造を持つアーム集合から生じる潜在的な利点を隠蔽しているからである。 これを解決するために、アームセットに依存した下界を確立し、それとは対照的に、どのアームセットに対しても保持する。 下界の根底にあるアイデアに触発され、よく知られた$\mathcal{X}\mathcal{Y}$-Optimalデザインの特殊化であるAdjacent-Optimalデザインを提案し、$\textsf{Adjacent-BAI}$アルゴリズムを開発した。 我々は、$\textsf{Adjacent-BAI}$の誤差確率が、我々の下限を定数に一致させ、下限の厳密性を検証し、この設定のアームセット依存の複雑さを確立することを証明した。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。 我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity [28.068960555415014]
  非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。 アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
  論文  参考訳（メタデータ） (2023-07-27T19:03:36Z)
• Revisiting Simple Regret Minimization in Multi-Armed Bandits [33.88679679593314]
  単純な後悔は、最高の腕や$epsilon$-good腕を欠く確率よりもあまり一般的ではない。 本稿では,データ豊かさ (Tge n$) とデータ貧弱さ (T le n$) の両面において,単純な後悔の上限を改良した。 より困難なデータ・ポーア・レシエーションのために、少なくとも1回は各腕をサンプリングすることなく、同じ改善を享受できるブラッケティングSH(BSH)を提案する。
  論文  参考訳（メタデータ） (2022-10-30T18:31:03Z)
• Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
  本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。 C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
  論文  参考訳（メタデータ） (2021-09-10T15:41:07Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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