  This paper investigates the convergence time of log-linear learning to an
$\epsilon$-efficient Nash equilibrium (NE) in potential games. In such games,
an efficient NE is defined as the maximizer of the potential function. Existing
results are limited to potential games with stringent structural assumptions
and entail exponential convergence times in $1/\epsilon$. Unaddressed so far,
we tackle general potential games and prove the first finite-time convergence
to an $\epsilon$-efficient NE. In particular, by using a problem-dependent
analysis, our bound depends polynomially on $1/\epsilon$. Furthermore, we
provide two extensions of our convergence result: first, we show that a variant
of log-linear learning that requires a factor $A$ less feedback on the utility
per round enjoys a similar convergence time; second, we demonstrate the
robustness of our convergence guarantee if log-linear learning is subject to
small perturbations such as alterations in the learning rule or noise-corrupted
utilities.
