上下文可归块的赌博机不再先恢复分块：在线遗憾降到与下界只差对数因子

上下文可归块赌博机的在线期望遗憾被压到与已知下界只差对数因子，且对任意块分布与上下文分布都成立。 此前 Lee 等人 2023 年给出的在线上界多出一个因子，其算法在细化上下文划分时还要保证不切开真实块，这一额外要求带来了该因子。 该速率与 Lee 等人 2023 年的下界在对数因子内一致，并去掉了那个额外因子；已知时间跨度时由 Algorithm 4 达到，未知时间跨度时用标准倍增重启得到同阶结果。

算法不先恢复未知的上下文分块，而是构造一个共享候选臂集合，其中每个块都含有一个足够好的臂，再在每个上下文上从该集合里单独挑选。 此前要共享观测就得先找出块划分，而划分细化不能切开真实块会带来额外代价。 该保证不要求不同块的奖励向量之间存在任何正间隔，块分布也不受限制。

探索按二进精度层级分阶段进行，先用基线策略估计各上下文的参考值，再按置信度提前停止采样。 若对每个上下文各跑一个赌博机，遗憾会随上下文数线性增长，而跨上下文探索本身也会付出代价。 在联合集中事件上，被提前停止的臂比前一策略差一个常数倍的精度，而跑满预算的臂得到该精度的估计。

跨上下文消除利用同一块内均值奖励相同这一事实：选中一个臂就删掉该块所有存活记录，因此每层最多需要若干次选择。 块划分始终不被识别，消除步骤却仍能整块清空记录。 多尺度探索给频繁块更细的精度、给稀有块更粗的精度，使每个块都得到近最优臂，同时把加权策略误差压小。

报道覆盖的是上下文可归块随机赌博机的在线期望遗憾结果：上下文被分成未知的块，同一块内每个臂的均值奖励相同，学习器看得到上下文身份但看不到块归属。结论面向研究赌博机、在线学习与低秩结构的读者，适用于任意块分布与任意上下文分布，且不要求不同块的奖励向量之间存在正间隔。作者提出的后续方向是把该思路推广到一般可归块马尔可夫决策过程，其中状态转移可以依赖状态与动作。

保证以期望遗憾的形式给出，并隐藏了关于上下文数、臂数、块数与时间跨度的多重对数因子。已知时间跨度时由 Algorithm 4 达到该速率，未知时间跨度时依靠标准倍增重启得到同阶结果。任意上下文分布的情形先按估计到达概率对上下文分组，再在每组内单独运行，并以至少给定概率保证每组条件分布满足近似均匀的假设，剩余低频上下文的总概率至多为一给定小量。