by , , ,
We consider the problem of learning to play a repeated multi-agent game with an unknown reward function. Single player online learning algorithms attain strong regret bounds when provided with full information feedback, which unfortunately is unavailable in many real-world scenarios. Bandit feedback alone, i.e., observing outcomes only for the selected action, yields substantially worse performance. In this paper, we consider a natural model where, besides a noisy measurement of the obtained reward, the player can also observe the opponents' actions. This feedback model, together with a regularity assumption on the reward function, allows us to exploit the correlations among different game outcomes by means of Gaussian processes (GPs). We propose a novel confidence-bound based bandit algorithm GP-MW, which utilizes the GP model for the reward function and runs a multiplicative weight (MW) method. We obtain novel kernel-dependent regret bounds that are comparable to the known bounds in the full information setting, while substantially improving upon the existing bandit results. We experimentally demonstrate the effectiveness of GP-MW in random matrix games, as well as real- world problems of traffic routing and movie recommendation. In our experiments, GP-MW consistently outperforms several baselines, while its performance is often comparable to methods that have access to full information feedback.
Efficiently Learning Fourier Sparse Set Functions A. Amrollahi, A. Zandieh, M. Kapralov, A. KrauseIn Proc. Neural Information Processing Systems (NeurIPS), 2019Spotlight presentation
Bibtex Entry:
	Author = {Andisheh Amrollahi and Amir Zandieh and Michael Kapralov and Andreas Krause},
	Booktitle = {Proc. Neural Information Processing Systems (NeurIPS)},
	Month = {December},
	Title = {Efficiently Learning Fourier Sparse Set Functions},
	Year = {2019}}