本文研究了辅助游戏框架的在线变体，其中一个知情代理和一个不知情代理在 $T$ 个时间步中反复互动，以优化共同的奖励函数。知情代理（人类）观察到世界的潜在状态，而不知情代理（助手）仅观察人类的行为。我们提供了第一个在重复辅助游戏中具有证明效率的学习算法。
我们引入了辅助遗憾的概念：互动的累积效用与事后最优联合策略（将潜在状态映射到动作对）的差距。我们为人类和助手提出了去中心化算法，达到 $(1-1/e)$ 近似的辅助遗憾率 $\tilde{O}(T^{3/4})$，其运行时间在动作和状态空间的大小上是多项式的。这些算法是通用的；特别是，它们适用于任何无遗憾算法的助手。
我们证明了实现比 $(1-1/e)$ 更好的遗憾近似因子在计算上是不可行的。此外，我们展示了如何将这些通用的无遗憾算法调整为伪去中心化环境——使用共享随机字符串——以实现 $\tilde{O}(T^{1/2})$ 的速率，最优到对数因子。
博主点评： 本文深入探讨了辅助游戏中的学习算法，提出了新的遗憾概念及其优化算法，具有重要的理论意义与实际应用潜力，尤其是在人机协作领域。