Fugu-MT 論文翻訳(概要): One Good Source is All You Need: Near-Optimal Regret for Bandits under Heterogeneous Noise

論文の概要: One Good Source is All You Need: Near-Optimal Regret for Bandits under Heterogeneous Noise

arxiv url: http://arxiv.org/abs/2602.14474v1
Date: Mon, 16 Feb 2026 05:25:06 GMT
ステータス: 翻訳完了
システム内更新日: 2026-02-17 16:22:50.160266
Title: One Good Source is All You Need: Near-Optimal Regret for Bandits under Heterogeneous Noise
Title（参考訳）: 不均質な騒音下でのバンドの最適レグレット
Authors: Aadirupa Saha, Amith Bhat, Haipeng Luo,
Abstract要約: Source-Optimistic Adaptive Regret Minimization (SOAR) は、シャープな分散集中境界を用いて高分散ソースを創出する新しいアルゴリズムである。我々は、標準の単一ソースMABのインスタンス依存の最適後悔を、分散$*2$で達成していることを示す。我々の理論的境界は、提案されたベースラインよりも大幅に改善されている。
参考スコア（独自算出の注目度）: 49.12618706309658
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study $K$-armed Multiarmed Bandit (MAB) problem with $M$ heterogeneous data sources, each exhibiting unknown and distinct noise variances $\{σ_j^2\}_{j=1}^M$. The learner's objective is standard MAB regret minimization, with the additional complexity of adaptively selecting which data source to query from at each round. We propose Source-Optimistic Adaptive Regret minimization (SOAR), a novel algorithm that quickly prunes high-variance sources using sharp variance-concentration bounds, followed by a `balanced min-max LCB-UCB approach' that seamlessly integrates the parallel tasks of identifying the best arm and the optimal (minimum-variance) data source. Our analysis shows SOAR achieves an instance-dependent regret bound of $\tilde{O}\left({σ^*}^2\sum_{i=2}^K \frac{\log T}{Δ_i} + \sqrt{K \sum_{j=1}^M σ_j^2}\right)$, up to preprocessing costs depending only on problem parameters, where ${σ^*}^2 := \min_j σ_j^2$ is the minimum source variance and $Δ_i$ denotes the suboptimality gap of the $i$-th arm. This result is both surprising as despite lacking prior knowledge of the minimum-variance source among $M$ alternatives, SOAR attains the optimal instance-dependent regret of standard single-source MAB with variance ${σ^*}^2$, while incurring only an small (and unavoidable) additive cost of $\tilde O(\sqrt{K \sum_{j=1}^M σ_j^2})$ towards the optimal (minimum variance) source identification. Our theoretical bounds represent a significant improvement over some proposed baselines, e.g. Uniform UCB or Explore-then-Commit UCB, which could potentially suffer regret scaling with $σ_{\max}^2$ in place of ${σ^*}^2$-a gap that can be arbitrarily large when $σ_{\max} \gg σ^*$. Experiments on multiple synthetic problem instances and the real-world MovieLens\;25M dataset, demonstrating the superior performance of SOAR over the baselines.
Abstract（参考訳）: 我々は、M$の不均質なデータソースを用いて、$K$武装マルチアームバンド(MAB)問題を研究し、それぞれが未知のノイズ分散を呈し、${σ_j^2\}_{j=1}^M$を示す。学習者の目的は、各ラウンドでどのデータソースをクエリするかを適応的に選択するという、標準的なMAB後悔の最小化である。本稿では,高速な分散集中バウンダリを用いて高速に高分散源を創出する新しいアルゴリズムであるソース・オプティミスティック・アダプティブ・レグレト最小化(SOAR)を提案し,次に最適なアームと最適な(最小分散)データソースを特定する並列タスクをシームレスに統合する'バランスド・min-max LCB-UCBアプローチ"を提案する。我々の分析によると、SOARはインスタンス依存のリセット境界を$\tilde{O}\left({σ^*}^2\sum_{i=2}^K \frac{\log T}{Δ_i} + \sqrt{K \sum_{j=1}^M σ_j^2}\right)$で達成している。この結果は、$M$の代替案の間で最小分散源についての事前の知識がないにもかかわらず、SOARは、${σ^*}^2$の分散を伴う標準単一ソースMABの最適インスタンス依存の後悔を達成し、また、$\tilde O(\sqrt{K \sum_{j=1}^M σ_j^2})$の小さな(かつ避けられない)付加コストのみを最適な(最小分散)ソース識別にもたらす。我々の理論的境界は、提案されたベースライン、例えば、Uniform UCB や Explore-then-Commit UCB よりも大幅に改善され、$σ_{\max}^2$ の代わりに${σ^*}^2$-a のスケーリングに後悔する可能性がある。複数の合成問題インスタンスと実世界のMovieLens\;25Mデータセットの実験は、ベースラインよりもSOARの方が優れたパフォーマンスを示している。

関連論文リスト

Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
このモデルは、$M$armと$K$playで構成されている。各アームには複数の能力があり、各ユニットの能力は報酬関数に関連付けられている。複数のプレーがアームキャパシティを競う場合、アームキャパシティは第1の優先重みで割り当てられる。
論文参考訳（メタデータ） (2025-12-25T11:19:09Z)
Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity [32.65125292684608]
1ビット通信制約を用いた分散平均推定問題について検討する。私たちの推定器は、有界平均$-lambda le mathbbE(X) le lambda $)と変数$mathrmVar(X) le sigma2$)を持つすべてのディストリビューションに対して$(epsilon, delta)$-PACです。
論文参考訳（メタデータ） (2025-09-26T06:22:57Z)
Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文参考訳（メタデータ） (2025-06-30T13:27:39Z)
Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
論文参考訳（メタデータ） (2024-01-16T03:14:24Z)
Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
論文参考訳（メタデータ） (2023-07-18T15:49:02Z)
Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文参考訳（メタデータ） (2023-03-30T02:51:00Z)
Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文参考訳（メタデータ） (2023-02-18T09:24:15Z)
Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文参考訳（メタデータ） (2022-10-20T21:32:01Z)
Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-06-14T12:58:46Z)
DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
論文参考訳（メタデータ） (2022-05-27T02:02:17Z)
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)

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

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