偏好反馈的赌徒问题：斯塔凯尔伯格博弈视角
内容提要
本文研究了在线线性优化问题，提出了多种算法以最小化后悔量，包括基于Bregman投影的梯度下降策略和Maximin-LUCB策略。同时探讨了模仿学习中的偏好反馈优势，并提出了基于上置信界的算法，实验证明其优于传统方法。
延伸解读
从在线优化到偏好反馈：研究脉络
文章梳理了在线线性优化、纯探索、上下文模仿学习等多个方向，时间跨度从2011年到2023年。这些工作围绕反馈结构（半强盗、强盗、完全反馈）和后悔最小化展开，逐步引入偏好反馈和专家查询。读者可借此了解在线学习领域如何从传统奖励反馈扩展到更复杂的交互设定。
偏好反馈在模仿学习中的优势与代价
在模仿学习中，学习者通过查询专家获得偏好反馈，算法对专家的查询次数仅为O(min{T,d²/Δ²})，且后悔界限与标准上下文强化学习相当。值得注意的是，当专家表现不佳时，算法甚至能超越专家，这凸显了基于偏好反馈的模仿学习在实践中的潜在优势，但查询次数仍受时间步和问题复杂度约束。
赌徒问题变体：从随机线性到背包约束
文章介绍了在线随机线性优化的赌徒环境，其中每轮仅揭示一位信息，并假设二元反馈来自对数模型。此外，带背包的赌徒问题结合了随机整数规划和在线学习，提出的算法报酬接近信息论最优，但问题本身比传统赌徒问题更具挑战性。这些变体反映了在线学习在资源约束下的扩展。
斯塔克尔伯格博弈与稳定匹配的扩展
文章还涉及 follower 效用未知的 Stackelberg 博弈中 leader 最优策略的求解，通过揭示意向方法在利润最大化等问题上表现良好。同时，双边市场中的稳定匹配问题扩展了多臂赌博机框架，研究了集中式和分散式方法，发现了与单人多臂赌博机不同的探索-利用权衡。这些工作展示了在线学习在博弈和市场设计中的应用。
Q&A
什么是偏好反馈的赌徒问题？
偏好反馈的赌徒问题是一个在线学习模型，研究如何在缺乏直接奖励知识的情况下，通过查询专家获得偏好反馈，以最小化后悔量。
文章中提到的Maximin-LUCB策略有什么特点？
Maximin-LUCB策略用于寻找最佳动作，能够在模仿学习中有效利用偏好反馈，提升学习效率。
如何通过Bregman投影技术优化在线线性问题？
使用Bregman投影技术的梯度下降策略可以有效地解决在线线性优化问题，最小化后悔量。
模仿学习中如何利用偏好反馈？
模仿学习中可以通过主动查询专家，比较动作并获取偏好反馈，从而在未知环境中达到最小后悔和查询复杂度的目标。
带背包的赌徒问题与传统赌徒问题有什么不同？
带背包的赌徒问题结合了随机整数规划和在线学习，具有更高的复杂性和挑战性，相比传统赌徒问题更难以解决。
文章中提到的遗憾上界是如何证明的？
文章通过引入基于上置信界的算法，结合离线情境对决贝叶斯臂设置，证明了遗憾上界的存在。
