本文研究了两人零和博弈中强化学习的最优算法设计问题。我们专注于自演算法，该算法通过在没有任何直接监督的情况下自演来学习最优策略。在具有S状态、a最大游戏者动作和B最小游戏者行为的表式情节马尔可夫博弈中，寻找近似纳什均衡的最佳现有算法需要O（S 2AB）个博弈步骤，同时仅强调对（S，a，B）的依赖性。相比之下，现有的最佳下限为Ω（S（A+B）），并且与上限有显著的间隙。本文首次填补了这一空白：我们提出了样本复杂度为O（SAB）的纳什Q学习算法的乐观变体，以及样本复杂度O（S（a+B））的新纳什V学习算法。后一个结果与所有问题相关参数的信息理论下限相匹配，除了每集长度的多项式因子。此外，我们给出了一个计算困难的结果，用于学习马尔可夫博弈中针对固定对手的最佳反应——这是一个不同于寻找纳什均衡的学习目标。
现代人工智能面临的一系列挑战可以归结为多智能体强化学习（multi-agent relation learning，多智能体RL）问题，其中不止一个智能体在交互环境中执行顺序决策。多智能体RL最近在传统挑战性任务上取得了重大成功，例如在围棋游戏[30,31]、扑克游戏[6]、实时策略游戏[33,22]、分散控制或多智能体机器人系统[5]、自主驾驶[27]以及复杂的社会场景（如捉迷藏[3]）。在许多情况下，学习代理甚至比最好的人类专家表现更好。尽管取得了巨大的经验成功，但许多现有RL算法的一个主要瓶颈是它们需要大量的样本。例如，最大的AlphaGo Zero模型是在数千万个游戏上训练的，需要一个多月的训练[31]。虽然在GO等可模拟环境中需要如此数量的样本可能是可以接受的，但在机器人和自动驾驶等其他采样昂贵的真实世界环境中则不然。因此，我们必须了解RL中的样本复杂性，我们如何设计能够用少量样本找到接近最优策略的算法，以及基本极限是什么，即任何算法找到好策略所需的最小样本数。
