Semiparametric Contextual Bandits

2018/03/12 by Akshay Krishnamurthy, Zhiwei Steven Wu, Krishnamurthy, Akshay +3 · 2 citations
Decision Sciences · Computer Science · Engineering · #Advanced Bandit Algorithms Research #Reinforcement Learning in Robotics #Smart Grid Energy Management

paper · pdf · doi:10.48550/arxiv.1803.04204

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 O(d√(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.

Citations

• The Nonstochastic Multiarmed Bandit Problem

Cited by

• Learning Linear Dynamical Systems with Semi-Parametric Least Squares
• The Nonstochastic Control Problem

Related

• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits
• Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
• Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms
• Catoni Contextual Bandits are Robust to Heavy-tailed Rewards