Search papers, labs, and topics across Lattice.
This paper introduces ECHO-OFTRL, an innovative algorithm that achieves constant individual regret in finite $N$-player normal-form games under full-information feedback, eliminating the polylogarithmic dependence on the horizon. By employing optimistic follow-the-regularized-leader dynamics with an exponential moving average cascade, the algorithm ensures that each player's regret is bounded by a polynomial function of the number of players and the logarithm of the maximum action set size. This advancement is significant as it provides a fully uncoupled and deterministic approach to achieving equilibrium in decentralized settings, enhancing the robustness of no-regret learning in game theory.
ECHO-OFTRL guarantees constant individual regret for all players in finite games, breaking the polylogarithmic barrier that has constrained decentralized learning dynamics.
Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependence on the horizon. We remove this dependence for every finite $N$-player normal-form game under full-information feedback. We introduce \emph{ECHO-OFTRL}: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled. If $m_{\max}$ denotes the largest action-set size, then, simultaneously for every horizon $T\geq1$, it guarantees that each of the $N$ players in the game incurs regret upper bounded by $O(\textrm{poly}(N, \log m_{\max}))$. Our algorithm leverages a new form of optimism inspired by modern filter design.
