models additive noise to the elimination signal. When there is no noise in the elimination signal, then $R=0$. Otherwise, as the elimination signal is bounded in $[0,1]$, it holds that $R\le1$. We’ll also relax our previous assumptions and allow the elimination signal to have values $0\le\mathbb{E}\brs*{e_t(s_t,a)}\le \ell$ for any valid action and $u\le\mathbb{E}\brs*{e_t(s_t,a)}\le 1$ for any invalid action, with $\ell<u$. Next, we denote by $X_{t,a}$ ($E_{t,a}$) the matrix (vector) whose rows (elements) are the observed state representation vectors (elimination signals) in which action $a$ was chosen, up to time $t$. For example, the $i^{th}$ row in $X_{t,a}$ is the representation vector of the $i^{th}$ state on which the action $a$ was chosen. Denote the solution to the regularized linear regression $\norm*{X_{t,a} \theta _{t,a}-E_{t,a}}_2^2+\lambda\norm*{\theta _{t,a}}_2^2$ (for some $\lambda>0$) by $\hat{\theta}_{t,a}=\bar{V}_{t,a}^{-1}X_{t,a}^T E_{t,a}$ where $\bar{V}_{t,a}=\lambda I+ X_{t,a}^TX_{t,a}.$

Similarly to Theorem 2 in [@abbasi2011improved][^2], for any state history and with probability of at least $1-\delta$, it holds for all $t>0$ that $\abs*{{\hat{\theta}_{t-1,a}}^T x(s_t)-{\theta ^*_a}^Tx(s_t)}\le \sqrt{\beta_{t-1}(\delta)x(s_t)^T\bar{V}_{t-1,a}^{-1}x(s_t)},
$ where $\sqrt{\beta_t(\delta)}=R\sqrt{2\log(\mbox{det}(\bar{V}_{t,a})^{1/2}\mbox{det}(\lambda I)^{-1/2}/\delta)}+\lambda^{1/2}S.$ If $\forall s, \norm*{x(s)}_2\le L$, then $\beta_t$ can be bounded by $\sqrt{\beta_t(\delta)}\le R\sqrt{d\log\left(\frac{1+tL^2/\lambda}{\delta}\right)}+\lambda^{1/2}S$. Next, we define $\tilde{\delta} = \delta/k$ and bound this probability for all the actions, i.e., $\forall a, t>0$ $$\centering
\label{eq:contextual}
\mbox{Pr}  \left\{ 