RM Algorithm (full information) Main idea: Smoothed Greedy Best action – Highest weight Near-best action – High weight Inferior actions – low weight Non trivial analysis Many algorithms Polynomial Weights: Parameter u Maintain weights w i,t p i,t = w i,t /W t Initially w i,1 =1, W 1 =m At time step t: observed gains g i,t-1 : w i,t =w i,t-1 (1+u*g i,t-1 )
{}