No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting

M${}^{\natural}$-凹函数，也被称为总代替估值函数，在离散数学和经济学等许多领域中起着基础性的作用。在实践中，我们通常无法事先完全了解M${}^{\natural}$-凹函数，只能根据一些反馈进行交互式优化。在这种情况下，我们研究在线M${}^{\natural}$-凹函数最大化问题，这是Murota和Shioura（1999）所研究问题的交互式版本。对于随机赌博机设置，我们提出了在$T$次访问M${}^{\natural}$-凹函数的无偏噪声值预言家的情况下，$O(T^{-1/2})$-简单遗憾和$O(T^{2/3})$-遗憾算法。证明这些结果的关键是贪心算法在M${}^{\natural}$-凹函数最大化的局部误差中的鲁棒性，这是我们的主要技术结果之一。虽然我们获得了这些随机设置的正面结果，但我们的另一个主要结果是在对抗性设置中的不可能性。我们证明，即使拥有完全信息反馈，也没有每轮运行多项式时间的算法能够在任何常数$c>0$的情况下实现$O(T^{1-c})$的遗憾，除非$\mathsf{P}=\mathsf{NP}$。我们的证明基于三个拟阵交集问题的约简，这在在线学习的背景下是一个新颖的想法。

本篇论文研究了在线M${}^{ atural}$-concave函数最大化问题，特别是在随机赌博机设置下的简单后悔和后悔算法，并证明了在对抗性设置下不可能实现多项式时间的$O(T^{1-c})$后悔。

本文的主要思路是研究贪心算法在M${}^{ atural}$-concave函数最大化中的鲁棒性，并将其应用于随机赌博机设置下的简单后悔和后悔算法，从而实现$O(T^{-1/2})$和$O(T^{2/3})$的后悔。同时，作者证明了在对抗性设置下，即使有完全信息反馈，也无法实现多项式时间的$O(T^{1-c})$后悔。

本文的实验结果表明了算法的有效性，并且作者提供了开源代码。此外，作者的证明使用了matroid intersection问题的约简，这在在线学习领域中是一个新的想法。

最近在这个领域中，也有一些相关的研究，例如Murota和Shioura(1999)的研究，以及关于在线最大化问题的其他研究，例如在线凸优化和在线子模函数最大化。