提出首个基于函数逼近的上下文老虎机第二阶上界算法
Second Order Bounds for Contextual Bandits with Function Approximation
- 基于乐观原则设计新算法，用测量方差和替代时间跨度
- 首次实现不随时间平方根增长的后悔上界
- 适合奖励噪声方差未知且变化的强化学习场景
许多工作已为具有函数逼近的上下文老虎机问题开发了无遗憾算法，其中期望奖励函数属于某个函数类。尽管已有多种方法，基于乐观原则（如乐观最小二乘）的算法日益重要。此类算法的后悔上界通常与弹道维数（eluder dimension）、函数类大小的对数及时间跨度的乘积平方根成正比。然而，即使奖励测量噪声的方差随时间变化且极小，乐观最小二乘算法的后悔仍随时间跨度的平方根增长。本文首次提出在函数逼近设定下，后悔上界不依赖于时间跨度平方根，而是依赖于测量方差之和平方根的算法。该结果推广了在线性上下文老虎机中第二阶上界的现有技术。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。