Linear Bandit Algorithms with Sublinear Time Complexity
원문 초록
We propose two linear bandits algorithms with per-step complexity sublinear in the number of arms $K$. The algorithms are designed for applications where the arm set is extremely large and slowly changing. Our key realization is that choosing an arm reduces to a maximum inner product search (MIPS) problem, which can be solved approximately without breaking regret guarantees. Existing approximate MIPS solvers run in sublinear time. We extend those solvers and present theoretical guarantees for online learning problems, where adaptivity (i.e., a later step depends on the feedback in previous steps) becomes a unique challenge. We then explicitly characterize the tradeoff between the per-step complexity and regret. For sufficiently large $K$, our algorithms have sublinear per-step complexity and $\tilde O(\sqrt{T})$ regret. Empirically, we evaluate our proposed algorithms in a synthetic environment and a real-world online movie recommendation problem. Our proposed algorithms can deliver a more than 72 times speedup compared to the linear time baselines while retaining similar regret.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Ducho meets Elliot: Large-scale Benchmarks for Multimodal Recommendation
Harm Mitigation in Recommender Systems under User Preference Dynamics
Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
LFG: A Generative Network for Real-Time Recommendation
LlamaRec: Two-Stage Recommendation using Large Language Models for Ranking
On Generative Agents in Recommendation
토론
이 논문과 연결된 포럼 글이 아직 없습니다.