提出快速适应非平稳环境的超多臂强化学习方法
Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms
- 用高斯插值处理连续空间奖励函数，支持海量动作选择
- 理论证明累积损失仅随√T增长，且在非平稳场景下表现更优
- 计算速度比现有方法快100-10000倍，适合大规模动态场景
传统多臂老虎机算法通常假设奖励环境是静态的，且动作空间较小。近年方法虽放宽了部分假设，但或仅适用于少量动作，或仅在静态环境中处理大量（或无限）动作。本文提出一种新策略，利用高斯插值学习连续空间中的奖励函数。理论表明，该方法可高效学习满足利普希茨条件的连续奖励函数，累积遗憾为 𝒪*(√T)。此外，通过简单改进，该方法自然拓展至非平稳问题。实验显示，该方法在非平稳、超多动作的数据集上，计算效率比滑动窗口高斯过程方法提升100至10000倍，并取得更优性能。
原文摘要 · Abstract (English)
Canonical algorithms for multi-armed bandits typically assume a stationary reward environment where the size of the action space (number of arms) is small. More recently developed methods typically relax only one of these assumptions: existing non-stationary bandit policies are designed for a small number of arms, while Lipschitz, linear, and Gaussian process bandit policies are designed to handle a large (or infinite) number of arms in stationary reward environments under constraints on the reward function. In this manuscript, we propose a novel policy to learn reward environments over a continuous space using Gaussian interpolation. We show that our method efficiently learns continuous Lipschitz reward functions with $\mathcal{O}^*(\sqrt{T})$ cumulative regret. Furthermore, our method naturally extends to non-stationary problems with a simple modification. We finally demonstrate that our method is computationally favorable (100-10000x faster) and experimentally outperforms sliding Gaussian process policies on datasets with non-stationarity and an extremely large number of arms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。