在线多类别分类的强化学习反馈算法：变体和权衡
内容提要
该文综述在线学习中的反馈与遗憾问题，涵盖部分信息模型、延迟模糊强化学习、函数族组合学习、犹豫学习、多类分类及组合多臂老虎机等场景，提出多种算法，刻画反馈图结构与学习难度的关系，并给出紧密遗憾边界及最优保证。
延伸解读
反馈结构如何决定学习难度
文章指出，反馈图的结构直接控制在线学习问题的难度，并给出了三类反馈图的理论极限表现。这意味着在实际应用中，设计学习算法前需先分析反馈信息的获取方式，因为不同的反馈结构可能导致完全不同的遗憾边界，从而影响算法选择与性能预期。
多类分类中反馈价格问题的解决
文章解决了多类学习中反馈价格问题，扩展了先前关于强化学习小石维度的结果，证明在标签空间无限时，小石维度的有限性是在线多类别可学习性的必要充分条件。这一结论补充了全信息设置下的对应工作，为多类分类的在线学习提供了理论判据。
延迟模糊强化学习的边界改进
文章改进了延迟模糊强化学习的最坏情况边界，并解决了多输入延迟模糊强化学习的边界问题。这表明在反馈延迟且模糊的场景下，原有理论保证可能不够紧，新结果提升了边界质量，为相关应用提供了更可靠的理论基础。
组合多臂老虎机的离线到在线转化
针对随机组合式多臂老虎机，文章提出将离线算法转化为基于有限老虎机反馈的子线性α遗憾策略的框架，并应用于基数问题和背包约束问题。这为利用离线优化工具解决在线组合决策提供了通用途径，但需注意其依赖随机模型和有限反馈的假设。
Q&A
在线多类别分类中，强化学习反馈下的可学习性条件是什么？
在标签空间无限的情况下，强化学习小石维度的有限性是在线多类别可学习性的必要和充分条件。
反馈图的结构如何影响在线学习的难度？
反馈图的结构控制引起的学习难度，文章给出了三个类别的反馈图的理论极限表现和影响。
在部分信息在线学习模型中，如何获得紧密的遗憾界限？
通过信息反馈结构的组合特性，提出了多种算法，给出了紧密的遗憾界限。
延迟模糊强化学习中的最坏情况边界有哪些改进？
改进了延迟模糊强化学习的最坏情况边界，并解决了多输入延迟模糊强化学习的边界问题。
在bandit学习中，不同反馈类型下的minimax遗憾如何被表征？
充分表征了不同反馈类型下的minimax遗憾，并设计了算法框架以实现匹配上限。
如何将离线算法转化为组合多臂老虎机中的子线性α遗憾策略？
提出了一种将离线算法转化为基于有限老虎机反馈的子线性α遗憾策略的框架，并应用于离散优化问题中的基数问题和背包约束问题。
