Repeated Play It is often that a game is repeatedly played for many times At each round t=1,2,...,T: (I)x-player picks a mixed strategy xt∈△m (2)simitaneously y-player picks a mixed strategy yEAn (3)x-player and y-player submit their strategies together (4)x-player receives loss x Ay and observes Ay;y-player receives loss-x,Ay:and observes-Axt The loss function that x-player receives is f().TAyt.assume a gradient feedback yt can depend on x1,...,x-1,meaning that x-player is facing an adptive adversary. Advanced Optimization(Fall 2023) Lecture 10.Online Learning in Games 11
Advanced Optimization (Fall 2023) Lecture 10. Online Learning in Games 11 Repeated Play • It is often that a game is repeatedly played for many times assume a gradient feedback
Repeated Play Assume x-player and y-player run online algorithms with regret Reg and Reg Our goal:prove minx maxy x Ay<maxy minx x Ay via repeated play. Key idea:use the quantityAy as a bridge between minx maxyTAy and maxy minx x Ay. Reg? min x Ayr+ Regt r≌∑y) x∈△m T Reg max min xTAy+ y∈△nx∈△m Advanced Optimization(Fall 2023) Lecture 10.Online Learning in Games 12
Advanced Optimization (Fall 2023) Lecture 10. Online Learning in Games 12 Repeated Play