只用一个优质数据源，就能逼近最优的强化学习效果。
One Good Source is All You Need: Near-Optimal Regret for Bandits under Heterogeneous Noise
- 通过自适应筛选低方差数据源，快速排除噪声大的选项。
- 理论证明可达到近似最优的后悔率，且不依赖先验知识。
- 适合多源异质噪声环境下的高效决策问题研究者。
我们研究具有 M 个异质数据源的 K-臂强化学习问题，每个源具有未知且不同的噪声方差 {σ_j²}。学习者需在每轮中自适应选择查询哪个数据源，目标是最小化标准的累积后悔值。提出 SOAR 算法：利用紧致方差集中界快速剔除高方差源，并采用平衡最小最大下置信区间-上置信区间策略，同时识别最优动作与最低方差数据源。理论分析显示，SOAR 实现实例相关后悔上界为 Õ(σ*²∑_{i=2}^K log T / Δ_i + √(K ∑_{j=1}^M σ_j²))，其中 σ*² = min_j σ_j² 为最小源方差，Δ_i 为第 i 个臂的次优差距。该结果令人意外——尽管对最小方差源无先验信息，仍可达到单源最优后悔率（以 σ*² 为基准），仅增加一个较小的附加项 Õ(√(K ∑_{j=1}^M σ_j²))。相比均匀采样或探索后固定等基线方法，其性能显著更优，尤其在 σ_max >> σ* 时差距更大。在多个合成任务和真实世界 MovieLens 25M 数据集上的实验验证了 SOAR 的优越性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。