minimizing the elimination signal error. The main difficulty with this approach is that both models are strongly coupled, and each model affects the observations of the other model, such that the convergence of any of the models is not trivial. Next, we present a method that decouples the elimination signal from the MDP by using contextual multi-armed bandits. The contextual bandit learns a mapping from states (represented by context vectors $x(s)$) to the elimination signal $e(s,a)$ that estimates which actions should be eliminated. We start by introducing theoretical results on linear contextual bandits, and most importantly, concentration bounds for contextual bandits that require almost no assumptions on the context distribution. We will later show that under this model we can decouple the action elimination from the learning process in the MDP, allowing us to learn using standard Q-learning while eliminating actions correctly.

Action elimination with contextual bandits
------------------------------------------

Let $x(s_t)\in \mathbb{R}^d$ be the feature representation of state $s_t.$ We assume (realizability) that under this representation there exists a set of parameters $\theta^*_a\in \mathbb{R}^d$ such that the elimination signal in state $s_t$ is $e_t(s_t,a) = {\theta ^*_a}^T x(s_t)+\eta_t$, where $\norm*{\theta^*_a}_{2}\le S.$ $\eta_t$ is an $R$-subgaussian random variable with zero mean that 