Provable Sample Complexity Guarantees for Learning of Continuous-Action Graphical Games with Nonparametric Utilities
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Provable Computational and Statistical Guarantees for Efficient Learning of Continuous-Action Graphical Games
In this paper, we study the problem of learning the set of pure strategy Nash equilibria and the exact structure of a continuous-action graphical game with quadratic payoffs by observing a small set of perturbed equilibr…
Constrained Meta Reinforcement Learning with Provable Test-Time Safety
Meta reinforcement learning (RL) allows agents to leverage experience across a distribution of tasks on which the agent can train at will, enabling faster learning of optimal policies on new test tasks. Despite its succe…
Reinforcement LearningFormal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees
*Automated circuit discovery* is a central tool in mechanistic interpretability for identifying the internal components of neural networks responsible for specific behaviors. While prior methods have made significant pro…
Active Algorithms For Preference Learning Problems with Multiple Populations
In this paper we model the problem of learning preferences of a population as an active learning problem. We propose an algorithm can adaptively choose pairs of items to show to users coming from a heterogeneous populati…
Active LearningAgnostic Interactive Imitation Learning: New Theory and Practical Algorithms
We study interactive imitation learning, where a learner interactively queries a demonstrating expert for action annotations, aiming to learn a policy that has performance competitive with the expert, using as few annota…
continuous-controlContinuous ControlImitation Learning