Reproduce “Efficient Kernel UCB for Contextual Bandits” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Houssam Zenati, Alberto Bietti, Eustache Diemert, Julien Mairal, Matthieu Martin, Pierre Gaillard
EK-UCB reduces the computation of kernelized upper-confidence-bound contextual bandits by incrementally building a dictionary of informative context–action pairs and updating the model on that smaller set. Under the paper’s assumptions, its time complexity is O(CTm²), and a dictionary sized by effective dimension preserves the kernel-UCB regret guarantee up to logarithmic factors. Synthetic experiments show a computation–regret trade-off, not universal speedups.
Key insights
- Incremental Nyström approximations, particularly when managed by KORS with specific parameter choices, can effectively reduce the problem's effective dimensionality in online contextual bandits without compromising theoretical regret guarantees.
- By aligning the KORS parameter "mu" with the regularization parameter "lambda" ("mu" = "lambda"), EK-UCB can achieve the same optimal regret bounds as computationally intensive standard Kernel-UCB algorithms.
- Designing confidence sets that are not strictly restricted to the approximated subspace helps mitigate misspecification errors and enables strong theoretical performance in dynamic projection settings.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.