
Following the terminology in [1]}, we describe \(\bar{\mathcal {R}}\left( \mathbf {x}\left( t \right),T \right)\) , \(t\in \left[ T \right]\) , \(T\in \mathbb {Z}_+\)  as the pseudo-regretNote that there is a slight difference between the quantity (REF ) and the commonly used expected regret, i.e., \(\tilde{\mathcal {R}}\left( \mathbf {x}\left( t \right) ,T \right) \triangleq \mathbb {E}[ \sum \nolimits _{t=1}^T{f_t\left( \mathbf {x}\left( t \right) \right)} ] -\mathbb {E}[ \sum \nolimits _{t=1}^T{f_t\left( \mathbf {x}^{\ast } \right)} ]\)  with \(\mathbf {x}^{\ast }=\text{arg}\min _{\mathbf {x}\in \chi ^n}\sum \nolimits _{t=1}^T{f_t\left( \mathbf {x} \right)}\) , the difference being that the infimum on \(\mathbf {v}\in \chi ^n\)  is within the expectation. Applying Jensen's inequality, it can be deduced that \(\bar{\mathcal {R}}\left( \mathbf {x}\left( t \right) ,T \right) \le \tilde{\mathcal {R}}\left( \mathbf {x}\left( t \right) ,T \right)\) . about decision \(\mathbf {x}\left( t \right)\)  at time horizon \(T\) . Clearly, the pseudo-regret \(\bar{\mathcal {R}}\left( \mathbf {x}\left( t \right),T \right)\)  is the difference between the expectation of the total cost generated by the algorithm at time \(T\)  and the expected total cost generated by the best single decision in \(\chi ^n\)  in hindsight.
