Thanks for adding the reference. Are you sure McDiarmid's inequality applies in the online learning case, though? The inequality you wrote down looks like a uniform convergence result, which as far as I'm aware still required an i.i.d. assumption somewhere (although uniform convergence results are also super-awesome; I was even considering including them in my post but removed them due to length reasons).