> I read a paper a while back which introduced a different algorithm with tighter bounds on regret

Got a link or cite for that paper? It sounds interesting.