Semiparametric Contextual Bandits
This work addresses a generalization of linear stochastic bandits with confounding effects, offering improved algorithms for scenarios with non-linear rewards, though it is incremental as it builds on existing bandit frameworks.
The paper tackles the semiparametric contextual bandits problem, where rewards have linear and non-linear confounding terms, by designing new algorithms that achieve $ ilde{O}(d\sqrt{T})$ regret, matching the best bounds for simpler cases and outperforming prior methods in empirical evaluations with non-linear confounding effects.
This paper studies semiparametric contextual bandits, a generalization of the linear stochastic bandit problem where the reward for an action is modeled as a linear function of known action features confounded by an non-linear action-independent term. We design new algorithms that achieve $\tilde{O}(d\sqrt{T})$ regret over $T$ rounds, when the linear function is $d$-dimensional, which matches the best known bounds for the simpler unconfounded case and improves on a recent result of Greenewald et al. (2017). Via an empirical evaluation, we show that our algorithms outperform prior approaches when there are non-linear confounding effects on the rewards. Technically, our algorithms use a new reward estimator inspired by doubly-robust approaches and our proofs require new concentration inequalities for self-normalized martingales.