arXiv：cs.LG· Kushagra Chandak, Volodymyr Tkachuk, Xiaoqi Tan, Csaba Szepesv\'ari·· 13 小时前
部分覆盖离线数据下的线性 Bandit：从离线到在线的 Gaussian-Width 界
Gaussian-Width Bounds for Offline-to-Online Linear Bandits
AI 导读
针对部分覆盖离线数据（d 个特征方向中仅 k 个覆盖不足）的随机线性 bandit，研究者指出基于 phased elimination 和乐观主义的算法其 Õ(√(dkT)) 遗憾界源于对奖励预测误差的控制过松，改用高斯向量 Lipschitz 函数集中不等式后给出更紧的界，并据此提出遗憾为 Õ(k√T) 的 phased elimination 算法。
正文
Abstract:We study how offline data can help online learning in stochastic linear bandits. We focus on partially covered offline data, where only $k$ of the $d$ feature directions are poorly covered. Existing analyses of algorithms based on phased elimination and optimism give regret bounds of order $\widetilde O(\sqrt{dkT})$ in this regime. We show that this dependence arises from loose control of the reward prediction error, and obtain tighter bounds using concentration of Lipschitz functions of Gaussian vectors. Based on this analysis, we develop a phased elimination algorithm with regret $\widetilde O(k\sqrt T)$. For the unit Euclidean ball, we prove a matching regret lower bound under partial coverage, as well as matching upper and lower bounds under uniform offline coverage. We also study pure exploration with offline data, providing algorithms and matching upper and lower bounds on simple regret for fixed-design algorithms and also for adaptive algorithms under partial and uniform coverage of offline data.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.12990 [cs.LG] |
| (or arXiv:2610.12990v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.12990 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Kushagra Chandak [view email]
[v1]
Fri, 9 Oct 2026 04:45:56 UTC (58 KB)
来源：arXiv：cs.LG · arxiv.org