提出新算法，高效应对奖励函数随时间突变的无限动作问题。
Non-Stationary Lipschitz Bandits
- 通过分层离散化动作空间，自适应追踪奖励变化的关键点。
- 在无先验知识下实现最优动态遗憾界 $\tilde{O}(\tilde{L}^{1/3}T^{2/3})$。
- 适合研究动态环境下的强化学习与在线优化问题。
我们研究非平稳的Lipschitz老虎机问题，其中动作数量为无穷，且满足Lipschitz条件的奖励函数可随时间任意变化。我们设计了一种自适应跟踪近期引入的显著变化（由累积奖励函数的大偏差定义）的算法。为检测此类奖励变化，算法利用动作空间的分层离散化。无需任何关于非平稳性的先验知识，该算法实现了最小最大最优的动态遗憾界 $\tilde{O}(\tilde{L}^{1/3}T^{2/3})$，其中 $\tilde{L}$ 为显著变化次数，$T$ 为时间跨度。这是该设置下的首个最优保证。
原文摘要 · Abstract (English)
We study the problem of non-stationary Lipschitz bandits, where the number of actions is infinite and the reward function, satisfying a Lipschitz assumption, can change arbitrarily over time. We design an algorithm that adaptively tracks the recently introduced notion of significant shifts, defined by large deviations of the cumulative reward function. To detect such reward changes, our algorithm leverages a hierarchical discretization of the action space. Without requiring any prior knowledge of the non-stationarity, our algorithm achieves a minimax-optimal dynamic regret bound of $\mathcal{\widetilde{O}}(\tilde{L}^{1/3}T^{2/3})$, where $\tilde{L}$ is the number of significant shifts and $T$ the horizon. This result provides the first optimal guarantee in this setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。