Related Work.
The work in [1]} considers linear bandits with adversarial corruption and achieves a regret bound of \(\tilde{O}(d\sqrt{T}+d^{3/2}C)\)  with high probability for known corruption level \(C\)  and a regret bound of \(\tilde{O}(d\sqrt{T}+d^{3/2}C+C^2)\)  with high probability for a stronger adversary that observes the current action and unknown corruption level \(C\) , while the work in [2]} achieves a regret bound of \(\tilde{O}(d\sqrt{T}+d^{3/2}C)\)  with high probability for unknown corruption \(C\) . These algorithms have optimal dependency on \(T,C\)  but it is not known if the \(d^{3/2}\)  dependency is tight or not. The work in [3]} improves the dependency on \(d\)  for linearized corruption, by achieving a regret bound of \(\tilde{O}(d\sqrt{T}+C)\)  with high probability which is also nearly optimal [3]}. The proposed algorithms and analysis rely on the assumption that the action set is fixed, and as far as we know there are no known generalizations for changing action sets - beyond the work in [1]} that considers changing action sets but imposes a strong assumption on the context distribution. The work in [6]} considers a stronger adversary, that observes the current action, and achieves an \(\tilde{O}(d\sqrt{T})\)  regret bound for unknown \(C\le \sqrt{T}\)  and linear regret otherwise. The first paper to prove a regret bound with nearly optimal dependency on \(T,C\)  for linear bandits with changing action sets (linear contextual bandits) is [2]} which achieves a regret bound of \(\tilde{O}(d^{4.5}\sqrt{T}+d^4C)\)  with high probability for unknown \(C\) . While the dependency on \(T,C\)  is nearly optimal, the dependency on \(d\)  is clearly not - improving this was left as an open problem. Our results take a step in this direction by removing a factor of \(d^{3.5}\)  from the first term, by removing a factor of \(d^{2.5}\)  from the second term and by reducing the problem of further improving the dependency of \(d\)  in the second term to achieving this improvement over a linear bandit setup.
