\abs*{\hat{\theta}_{t-1,a}^Tx(s_t)-{\theta ^*_a}^Tx(s_t) } 
 \le \sqrt{\beta_{t-1}(\tilde{\delta})x(s_t)^T\bar{V}_{t-1,a}^{-1}x(s_t)} \right\} \ge 1-\delta$$ Recall that any valid action $a$ at state $s$ satisfies $\mathbb{E}\brs{e_t(s,a)}={\theta ^*_a}^Tx(s_t)\le \ell$. Thus, we can eliminate action $a$ at state $s_t$ if $$\label{eq:el_thr}
\hat{\theta}_{t-1,a}^Tx(s_t)-\sqrt{\beta_{t-1}(\tilde{\delta})x(s_t)^T\bar{V}_{t-1,a}^{-1}x(s_t)}>\ell$$ This ensures that with probability $1-\delta$ we never eliminate any valid action. We emphasize that only the expectation of the elimination signal is linear in the context. The expectation does not have to be binary (while the signal itself is). For example, in conversational agents, if a sentence is not understood by 90$\%$ of the humans who hear it, it is still desirable to avoid saying it. We also note that we assume $\ell$ is known, but in most practical cases, choosing $\ell\approx 0.5$ should suffice. In the current formulation, knowing $u$ is not necessary, though its value will affect the overall performance.

Concurrent Learning
-------------------

We now show how the Q-learning and contextual bandit algorithms can learn simultaneously, resulting in the convergence of both algorithms, i.e., finding an optimal policy and a minimal valid action space. The challenge here is that each learning process affects the state-action distribution of the other. We first define Action Elimination Q-learning.

Action Elimination Q-learning is a Q-learning algorithm which updates 