
Hence, \(\Sigma _{t}\)  is a martingale with a bounded difference (by boundedness of \(\Theta , \mathcal {A}_t\) ). By Azuma–Hoeffding inequality [1]}, we have that \(|\Sigma _T|\le c\sqrt{T\log 1/\delta }\)  with probability at least \(1-\frac{1}{2\delta }\) . For completeness, we state a special case of the Azuma-Hoeffding inequality at the end of our proof. The summation \(\Sigma ^{\prime }_T=\sum _{t=1}^T {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle } - \mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle }]\)  can be bounded similarly. Hence, by (REF ), we have that with probability at least \(1-\delta \)
\(|R_T^\mathcal {M}(I)-R_T^\Lambda (L)|\le c \sqrt{T\log 1/\delta }.\) 
