研究滑动窗口下在线学习的高效算法，解决记忆有限时如何快速选最优选项。
Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
- 基于最近W个选项的滑动窗口设计新算法，只存部分数据提升效率
- 证明在亚线性内存下精确找最优难，近似解可高效完成
- 首次给出内存与后悔值的精确权衡，适合资源受限的实时决策场景
受在线学习中近期效应启发，本文研究单遍流式滑动窗口多臂老虎机（MAB）的算法。给定n个臂，其回报服从未知子高斯分布，以及参数W，臂以单遍流形式到达，仅最近W个臂被视为有效。算法需在有限存储（即存储臂的数量）条件下完成纯探索与最小化遗憾。该模型是近年被广泛研究的流式多臂老虎机的自然扩展。本文对纯探索与遗憾最小化问题进行了全面分析：对于纯探索，证明在亚线性内存下精确找到最优臂困难，但近似解存在高效算法；对于遗憾最小化，引入新遗憾定义，并为任意单遍算法给出了紧致的内存-遗憾权衡。实验验证了样本、遗憾与内存间的权衡关系。
原文摘要 · Abstract (English)
Motivated by the recency effect in online learning, we study algorithms for single-pass *sliding-window streaming multi-armed bandits (MABs)* in this paper. In this setting, we are given $n$ arms with unknown sub-Gaussian reward distributions and a parameter $W$. The arms arrive in a single-pass stream, and only the most recent $W$ arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。