論文の概要: Best Arm Identification for Bandits with Shifting Means

• arxiv url: http://arxiv.org/abs/2610.10488v1
• Date: Wed, 07 Oct 2026 17:44:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:23.089984
• Title: Best Arm Identification for Bandits with Shifting Means
• Title（参考訳）: シフト平均をもつバンドのベストアーム識別
• Abstract要約: 本研究では, 対角的摂動の新たな形態を用いて, 対角的環境における最適な腕識別問題について検討する。 本稿では, 一般的なトラック・アンド・ストップを含むGLRT (Generalized Likelihood Ratio Test) の停止規則を用いたアルゴリズムは, 時間変化によって失敗することを示す。 ここでは、$mathsfISM$ を$$-correct とし、次数 $K (2 + U2) _min-2 ln frac1$ の複雑さのサンプルを楽しむ。
• 参考スコア（独自算出の注目度）: 11.82340939131766
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the $K$ arms are stable in time, in Shifting Means only the gaps $\boldsymbolΔ$ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means ($\mathsf{ISM}$). Assuming means bounded by $U$ and $σ^2$-sub-Gaussian rewards, we show $\mathsf{ISM}$ to be $δ$-correct and to enjoy a sample complexity bound of order $K (σ^2 + U^2) Δ_{\min}^{-2} \ln \frac{1}δ$. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.
• Abstract（参考訳）: 確率的環境下での最適な腕の識別問題について,新しい形態の対角摂動を用いて検討し,シフト平均を定式化した。 古典的には、$K$アームの平均報酬は時間的に安定であるが、Shifting Meansでは、平均報酬間のギャップ$\boldsymbolΔ$のみが安定であり、それぞれのラウンドで共通のシフトが逆向きに決定される。 学習者の目的は、標本の複雑さを最小化しつつ、高い確率で最適な腕を識別することである。 シフトの処理には新しいツールが必要である。我々は、一般的なGLRT(Universalized Likelihood Ratio Test)の停止ルールを用いるアルゴリズムが、時変シフトで失敗することを示す。 代わりに、シフト平均(\mathsf{ISM}$)に対するImportance Weightsを提案する。 U$ と $σ^2$-sub-Gaussian rewards で有界な平均を仮定すると、$\mathsf{ISM}$ は $δ$-正則であることを示し、次数 $K (σ^2 + U^2) Δ_{\min}^{-2} \ln \frac{1}δ$ の有界なサンプル複雑性を楽しむ。 また、一致した(定数要素まで)最悪の場合のバウンドを低くし、その結果を経験的に評価する。

関連論文リスト

• Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? [11.223878908981725]
  1/2$-Tsallis-INFは、標準的なFTRLアルゴリズムである。 盗賊の対数的擬似回帰を達成しつつ、敵の盗賊の最小限の後悔を保ちながら達成する。 これは自然な疑問を提起する:同じアルゴリズムは、追加の探索なしに、最高の腕を確実に特定できるのか?
  論文  参考訳（メタデータ） (2026-08-15T18:38:36Z)
• Price of Fairness in Bandits: A Tight Minimax Characterization [9.360852329235477]
  盗賊問題では、標準的な後悔を最小化するアルゴリズムが探索を償却コストとして扱い、初期の参加者は不公平な前衛の損失に晒される。 最近の研究は、一般化された$p$-meanを通じて、ラウンドごとの期待される報酬のシーケンスを評価することで、この問題に対処している。 アルゴリズムに依存しない下界$(sqrtkmax(1,q)/T)$; for $q>1$, this shows that $kq/2$ is a information-theoretically unavoidable。
  論文  参考訳（メタデータ） (2026-07-15T02:58:57Z)
• A Complexity Measure for Active Learning in Multi-group Mean Estimation [8.550300650352732]
  マルチグループ平均バンドレート$d$-armed banditsにおけるemphmax-riskによるアクティブラーニングの目的について検討した。 学習者は、最悪の不確実性指数を最小限に抑えるために、$d$グループ全体で$T$サンプルの予算を適応的に割り当てる。 滑らかなクラスに対しては、$mathrmVLC$ は分散-フィッシャー情報の再パラメータ化であり、共通族に対する閉形式値を持つ。
  論文  参考訳（メタデータ） (2026-06-12T17:54:26Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)

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

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