版像 NJUAT 南京大学 人工智能学院 SCHODL OF ARTIFICIAL INTELUGENCE,NANJING UNIVERSITY Lecture 11.Adversarial Bandits Advanced Optimization(Fall 2023) Peng Zhao zhaop@lamda.nju.edu.cn Nanjing University
Lecture 11. Adversarial Bandits Peng Zhao zhaop@lamda.nju.edu.cn Nanjing University Advanced Optimization (Fall 2023)
Outline 。Problem Setup ·Multi-Armed Bandits Bandit Convex Optimization ·Advanced Topics Advanced Optimization(Fall 2023) Lecture 11.Adversarial Bandits 2
Advanced Optimization (Fall 2023) Lecture 11. Adversarial Bandits 2 Outline • Problem Setup • Multi-Armed Bandits • Bandit Convex Optimization • Advanced Topics
Online Convex Optimization At each round t=1,2,... (1)the player first picks a model xt from aconvex set cRd (2)and environments pick an online convex functionf:->R; (3)the player suffers loss fi(xt),observes some information about fi and updates the model. Problem Domain Online Functions General OCO convex set t'cRd convex function fi() OCO with Strongly Convex Functions convex set tc Rd V2fi(x)=aI OCO with Exp-concave Functions convex set t'C Rd V2f(x)≥BVf(x)Vf(x)T Prediction with Experts'Advice △4={x∈R+∑1，=1 f(x)=(,x) Advanced Optimization(Fall 2023) Lecture 11.Adversarial Bandits 3
Advanced Optimization (Fall 2023) Lecture 11. Adversarial Bandits 3 Online Convex Optimization
OCO Algorithms learned so far Given first-order information oracle:worst-case bound Online Mirror Descent =arg minxex if()() where D(x,y)=(x)-(y)-(Vu(y),x-y)is the Bregman divergence. T ∑(x)-∑f画 t=1 t=1 +(m-nux)-a T t=1 Advanced Optimization(Fall 2023) Lecture 11.Adversarial Bandits 4
Advanced Optimization (Fall 2023) Lecture 11. Adversarial Bandits 4 Online Mirror Descent OCO Algorithms learned so far • Given first-order information oracle: worst-case bound
OCO Algorithms learned so far Given first-order information oracle:worst-case bound Algo. OMD/proximal form () nt RegretT OGD for x+=arg min ne(x,Vfe(x)) llxll O(VT) convex XEX OGD for strongly c. X1=argin,7fx》+Ix-x Ilxll 品 O(logT) x∈X ONS for exp-concave +1=arg min m(x Vf() Ixl O(4logT) Hedge for N In N PEA x:+1=arg min m (x,Vfi(x))+KL(xx) cilog xi m O(VTlog N) xE△N =1 Advanced Optimization(Fall 2023) Lecture 11.Adversarial Bandits 5
Advanced Optimization (Fall 2023) Lecture 11. Adversarial Bandits 5 OCO Algorithms learned so far • Given first-order information oracle: worst-case bound OGD for convex OGD for strongly c. ONS for exp-concave Hedge for PEA Algo. OMD/proximal form