【MIT博士论文】序列博弈中的近似最优学习, 338页pdf

决策制定无处不在，一些问题由于其序列性质变得特别具有挑战性，即后续决策取决于早期决策。虽然人类一直在努力解决顺序决策问题，但现代计算和机器学习技术是需要找到最优决策规则。一种流行的方法是强化学习（RL）视角，其中，代理通过基于其行动接收奖励来学习最优决策规则。在存在多个学习代理的情况下，顺序决策制定问题变成顺序博弈。在这种设置下，学习目标从找到最优决策规则转变为找到纳什均衡，即没有代理可以通过单方面切换到另一决策规则来增加他们的奖励。为了处理问题的顺序性质和其他学习代理的存在，多代理RL任务需要的数据比监督学习和单一代理RL任务更多。因此，样本效率对多代理RL的成功至关重要。

在这篇论文中，我研究了序列博弈中学习的最基本问题：1.（下界）在序列博弈中找到纳什均衡需要多少样本，无论使用什么学习算法？2.（上界）如何设计具有严格样本复杂性保证的（计算上）高效学习算法？当上界和下界相互匹配时，实现了（极小极大）最优学习。结果显示，利用序列博弈的结构是实现最优学习的关键。在这篇论文中，我们研究了两种类型的序列博弈的近乎最优学习：1.（马尔科夫博弈）所有代理可以观察到潜在的状态（第2章），2.（广泛形式博弈）不同的代理可以在给定相同状态的情况下具有不同的观察结果（第5章）。为了实现近乎最优学习，将引入一系列新颖的算法思想和分析工具，例如1.（自适应不确定性量化）对值函数估计进行尖锐的不确定性量化，以设计近乎最优的探索奖励（第3章），2.（认证策略）对历史策略进行非均匀和分阶段的重新加权，以产生近似纳什均衡策略（第4章），3.（平衡探索）根据子树的大小实现博弈树的最优探索（第6章），4.（对数分区函数重表述）将经典算法重新解释为计算对数分区函数的梯度（第7章），这可能具有独立的兴趣。