Semiparametric Contextual Bandits

Abstract

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.

References in corpus (8)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Towards minimax policies for online linear optimization with bandit feedback
• Double/Debiased Machine Learning for Treatment and Causal Parameters
• Efficient Algorithms for Adversarial Contextual Learning

Cited by in corpus (4)

• Learning Linear Dynamical Systems with Semi-Parametric Least Squares
• Power Constrained Bandits
• The Nonstochastic Control Problem
• Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles