We Are Legion: High Probability Regret Bound in Adversarial Multiagent Online Learning
Sri Jaladi, Ilai Bistritz · IEEE Control Systems Letters · 2024
We study a large-scale multiagent online learning problem where the number of agents N is significantly larger than the number of arms K. The agents face the same adversarial online learning problem with K arms over T rounds, where the adversary chooses the cost vectors$\boldsymbol {l}(1), \ldots ,\boldsymbol {l}(T)$before the game begins. Each round t, each agent n picks an arm$a_{n}$(t) and incurs a cost of$l_{a_{n}(t)}$(t). Then, at the end of the round, all agents observe the costs of all arms$l_{1}(t), \ldots ,l_{K}(t)$. The exponential weights algorithm achieves an order-wise optimal expected regret of$O(\sqrt {T})$for each agent. However, the variance of the sum of regrets scales linearly with the number of agents, which is unacceptable for a large-scale multi-agent system. To mitigate this, we propose a simple fully distributed algorithm that achieves the same optimal expected sum of regrets but reduces the variance of the sum of regrets from O(N) to$O(\min (N,K))$with no communication required between the agents.