Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback

arXiv:2112.02856v4 Announce Type: replace
Abstract: We consider online no-regret learning in unknown games with bandit feedback, where each player can only observe its reward at each time -- determined by all players' current joint action -- rather than its gradient. We focus on the class of \textit{smooth and strongly monotone} games and study optimal no-regret learning therein. Leveraging self-concordant barrier functions, we first construct a new bandit learning algorithm and show that it achieves the single-agent optimal regret of $\tilde{\Theta}(n\sqrt{T})$ …

abstract arxiv class cs.gt cs.lg current feedback focus games gradient math.oc observe online learning type