Many works have developed algorithms no-regret algorithms for contextual bandits with function approximation, where the mean rewards 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.

本研究解决了具有函数逼近的上下文赌博机中，乐观最小二乘法算法在奖励测量噪声变化情况下的后悔界限问题。我们首次提出了不再依赖时间范围平方根而是依赖测量方差总和的算法，显著提升了算法的适用性与效率。研究结果为上下文线性问题中导出二阶界限的方法提供了新的思路。

具有函数逼近的上下文赌博机的二阶界限