Alternation Makes the Adversary Weaker in Two-player Games

Stratis Skoulakis

Assistant Professor in the Department of Computer Science at Aarhus University

2025年2月20日 星期四

上午 10:00-11:00

Motivated by alternating game-play in two-player games, we present an altenating variant of the Online Linear Optimization (OLO). In alternating OLO,  a learner at each round t, selects a vector x^t and then an adversary selects a cost-vector c^t. The learner then experiences costinstead ofas in standard OLO. We establish that under this small twist, the Ω(√T) lower bound on the regret is no longer valid. More precisely, we present two online learning algorithms for alternating OLO that respectively admit O(T^{1/3}) regret for the simplex and O(ρ log T) regret for the ball of radius ρ>0. Our results imply that in alternating game-play, an agent can always guarantee O(T^{1/3}) regardless the strategies of the other agent while the regret bound improves to O(log T) in case the agent admits only two actions.