Second Order Bounds for Contextual Bandits with Function Approximation
This work addresses the issue of inefficient regret scaling in contextual bandits for machine learning practitioners, offering a novel improvement over prior methods by adapting to noise variance, though it builds incrementally on existing linear techniques.
The paper tackles the problem of high regret scaling in contextual bandits with function approximation, where existing algorithms scale with the square root of the time horizon even under low noise. It introduces new algorithms that achieve regret bounds scaling with the square root of the sum of measurement variances, generalizing second-order bounds to this setting.
Many works have developed no-regret algorithms for contextual bandits with function approximation, where the mean reward function over context-action pairs belongs to a function class. Although there are many approaches to this problem, one that has gained in importance is the use of algorithms based on the optimism principle such as optimistic least squares. It can be shown the regret of this algorithm scales as square root of the product of the eluder dimension (a statistical measure of the complexity of the function class), the logarithm of the function class size and the time horizon. Unfortunately, even if the variance of the measurement noise of the rewards at each time is changing and is very small, the regret of the optimistic least squares algorithm scales with square root of the time horizon. In this work we are the first to develop algorithms that satisfy regret bounds of scaling not with the square root of the time horizon, but the square root of the sum of the measurement variances in the setting of contextual bandits with function approximation when the variances are unknown. These bounds generalize existing techniques for deriving second order bounds in contextual linear problems.