一比特反馈也能追平下界：迹平方根势让上下文搜索与双边贸易同时达到紧遗憾

上下文搜索和上下文双边贸易在只看到一比特反馈时，现在都能做到与已知下界只差常数因子的遗憾，且界不随轮数增长。 此前这两种问题的上界与下界之间缺口明显，双边贸易的缺口尤其大，只存在一个一比特反馈模型的上界。 两种问题都在隐藏向量取自欧氏单位球、由对手选择的设定下给出期望损失界，与已有下界相差常数因子。

算法不再维护显式的可行域，而是用均值代理和平方根协方差代理来刻画对未知量的不确定度，并按上下文方向上的标准差来定价。 以往方法靠切割平面维护可行多面体，需要计算高维凸体的内在体积或重心这类几何量。 上下文搜索的对抗算法每轮只做少量算术运算、占用平方量级的存储，双边贸易则用一次极小极大论证保证存在一个对任意隐藏买卖双方都成立的有限价格彩票。

贝叶斯版本给出只依赖先验协方差矩阵的界，并且对任意轮数都成立。 这一视角偏离既有文献，但给出了更简单的算法，也提供了对抗分析所用的第一个势函数。 界分别由目标先验的协方差矩阵，以及卖方与买方估值的两个协方差矩阵决定，允许无界支撑或偏斜协方差。

讨论范围限于隐藏目标或买卖双方估值取自欧氏单位球、由对手选择的对抗设定，以及先验二阶矩有限的贝叶斯设定；两种保证都对任意轮数成立。

双边贸易的对抗算法只证明存在满足单轮界的有限价格彩票，材料明确不声称第 2 步中的优化有高效实现；贝叶斯界依赖已知先验，允许无界支撑或偏斜协方差。