arXiv:2409.16197v2 宣告类型: replace-cross 摘要: 许多研究工作已经为功能近似条件 bandits 开发了无遗憾算法，在这种算法中，上下文-动作对的平均奖励函数属于一个函数类。尽管有许多解决此问题的方法，其中一种越来越重要的方法是基于乐观原则的算法，如乐观最小二乘法。可以证明，这种算法的遗憾可以扩展为函数类的 eluder 维度（该统计量衡量函数类的复杂性）的平方根、函数类大小的对数和时间范围的乘积。不幸的是，即使每个时间点的奖励测量噪声方差发生变化且非常小，乐观最小二乘法算法的遗憾仍然与时间范围的平方根成比例。在这项工作中，我们在条件 bandits 中首次开发了算法，这些算法在功能近似的情况下能够满足遗憾边界，当方差未知时，它们的遗憾边界不仅与时间范围的平方根成比例，还与测量方差之和的平方根成比例。这些边界推广了在条件线性问题中推导二阶边界的技术。