Reproduce “High-Dimensional Experimental Design and Kernel Bandits” on OpenResearch

About this paper

Romain Camilleri, Julian Katz-Samuels, Kevin Jamieson

Researchers at the University of Washington and University of Wisconsin introduced the Robust Inverse Propensity Score (RIPS) estimator, which enables efficient experimental design by decoupling the number of measurements from data dimensionality. This estimator was then applied to kernel bandit algorithms, achieving state-of-the-art regret bounds in well-specified scenarios and establishing the first linear regret bounds for misspecified settings.

Key insights

• Effective experimental design can be achieved with a number of measurements independent of the underlying feature dimension by using robust estimation techniques that focus on individual linear forms of the parameter.
• Regularization in RKHS combined with robust mean estimation provides a powerful mechanism to handle both high-dimensional feature spaces and practical challenges like model misspecification and heavy-tailed noise distributions.
• Applying robust experimental design principles through the RIPS estimator allows for the development of kernel bandit algorithms that offer strong theoretical guarantees for regret minimization and best-arm identification even under non-ideal conditions.

Summary by alphaXiv.