Reproduce “Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions” on OpenResearch

About this paper

Yue Kang, Mingshuo Liu, Bongsoo Yi, Jing Lyu, Zhi Zhang, Doudou Zhou, Yao Li

This work introduces Single Index Bandits (SIBs), extending Generalized Linear Bandits (GLBs) to scenarios where the reward function is unknown, and develops algorithms that achieve nearly-optimal O(sqrt(T)) regret for monotonic reward functions. The proposed methods demonstrate robustness against model misspecification and exhibit computational speeds hundreds to thousands of times faster than existing GLB approaches on various datasets.

Key insights

• Stein's method can be successfully leveraged to construct a robust and minimax optimal estimator for the linear predictor in bandit settings, even without explicit knowledge of the reward function.
• Despite the increased complexity of an unknown, monotonic reward function, an epoch-based algorithm (ESTOR) can achieve nearly-optimal O(sqrt(T)) regret, matching the best known rates for GLBs.
• The framework can be extended to sparse high-dimensional settings and even to arbitrary, non-monotonic reward functions (under certain distributional assumptions), showcasing the versatility of the Stein's method-based estimation.

Summary by alphaXiv.