Abstract:This paper addresses the problem of learning to sparsify stochastic linear bandits, where a decision-maker sequentially selects actions from a high-dimensional space subject to a sparsity constraint on the number of nonzero elements in the action vector. The key challenge lies in minimizing cumulative regret while tackling the potential NP-hardness of finding optimal sparse actions due to the inherent combinatorial structure of the problem. We propose an adaptively phased exploration and exploitation algorithmic framework, utilizing ordinary least squares for parameter learning and specialized subroutines for sparse action selection. When the action set is a Euclidean ball, optimal sparse actions can be efficiently computed, enabling us to establish a $\tilde{\mathcal{O}}(d\sqrt{T})$ regret, where $d$ is the dimension of the action vector and $T$ is the time horizon length. For general convex and compact action sets where finding optimal sparse actions is intractable, we employ a greedy subroutine. For general strongly convex action sets, we derive a $\tilde{\mathcal{O}}(d \sqrt{T})$ $\alpha$-regret; for general compact sets lacking strong convexity, we establish a $\tilde{\mathcal{O}}(d T^{2/3})$ $\alpha$-regret, where $\alpha$ pertains to the approximation ratio of the greedy algorithm. Finally, we validate the performance of our algorithms using extensive experiments including an application to recommendation system.
| Comments: | Include all the omitted details and proofs from the conference paper accepted to IJCAI 2026 |
| Subjects: | Machine Learning (cs.LG); Systems and Control (eess.SY); Optimization and Control (math.OC) |
| Cite as: | arXiv:2605.10151 [cs.LG] |
| (or arXiv:2605.10151v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.10151 arXiv-issued DOI via DataCite (pending registration) |
From: Zhengmiao Wang [view email]
[v1]
Mon, 11 May 2026 07:57:37 UTC (1,622 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。