协助博弈的可证明最优学习算法

论文研究重复协助博弈：掌握潜在世界状态的人类与只能观察人类动作的助手，在共同奖励下交互学习。作者提出多项式时间的去中心化算法，实现近似为$(1-1/e)$、速率为~O(T^{3/4})的协助遗憾；借助共享随机串的伪去中心化设置，可将速率提升至~O(T^{1/2})，并证明更高近似因子在计算上不可行。