论文标题
可证明的样本复杂性保证与非参数实用程序学习连续行动图形游戏
Provable Sample Complexity Guarantees for Learning of Continuous-Action Graphical Games with Nonparametric Utilities
论文作者
论文摘要
在本文中，我们研究了通过非参数效用功能学习连续行动游戏的确切结构的问题。我们提出了一种$ \ ell_1 $正则化方法，该方法鼓励回收实用程序的傅立叶变换的系数稀疏。我们的方法通过访问很少的Nash Equilibria及其嘈杂的实用程序来起作用。在某些技术条件下，我们的方法还恢复了这些实用程序功能的确切结构，从而恢复了游戏的确切结构。此外，我们的方法只需要在多项式时间内的玩家数量和运行方式来对数数量的样本数。我们遵循原始的双重见证框架，提供可证明的理论保证。
In this paper, we study the problem of learning the exact structure of continuous-action games with non-parametric utility functions. We propose an $\ell_1$ regularized method which encourages sparsity of the coefficients of the Fourier transform of the recovered utilities. Our method works by accessing very few Nash equilibria and their noisy utilities. Under certain technical conditions, our method also recovers the exact structure of these utility functions, and thus, the exact structure of the game. Furthermore, our method only needs a logarithmic number of samples in terms of the number of players and runs in polynomial time. We follow the primal-dual witness framework to provide provable theoretical guarantees.
