[edit]
A Parameter-Free Algorithm for Misspecified Linear Contextual Bandits
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:3367-3375, 2021.
Abstract
We investigate the misspecified linear contextual bandit (MLCB) problem, which is a generalization of the linear contextual bandit (LCB) problem. The MLCB problem is a decision-making problem in which a learner observes d-dimensional feature vectors, called arms, chooses an arm from K arms, and then obtains a reward from the chosen arm in each round. The learner aims to maximize the sum of the rewards over T rounds. In contrast to the LCB problem, the rewards in the MLCB problem may not be represented by a linear function in feature vectors; instead, it is approximated by a linear function with additive approximation parameter ε≥0. In this paper, we propose an algorithm that achieves ˜O(√dTlog(K)+ε√dT) regret, where ˜O(⋅) ignores polylogarithmic factors in d and T. This is the first algorithm that guarantees a high-probability regret bound for the MLCB problem without knowledge of the approximation parameter ε.