Leveraging Good Representations in Linear Contextual Bandits

Abstract

The linear contextual bandit literature is mostly focused on the design of efficient learning algorithms for a given representation. However, a contextual bandit problem may admit multiple linear representations, each one with different characteristics that directly impact the regret of the learning algorithm. In particular, recent works showed that there exist "good" representations for which constant problem-dependent regret can be achieved. In this paper, we first provide a systematic analysis of the different definitions of "good" representations proposed in the literature. We then propose a novel selection algorithm able to adapt to the best representation in a set of $M$ candidates. We show that the regret is indeed never worse than the regret obtained by running LinUCB on the best representation (up to a $\ln M$ factor). As a result, our algorithm achieves constant regret whenever a "good" representation is available in the set. Furthermore, we show that the algorithm may still achieve constant regret by implicitly constructing a "good" representation, even when none of the initial representations is "good". Finally, we empirically validate our theoretical findings in a number of standard contextual bandit problems.

References in corpus (12)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Bounds on the Lambert function and their application to the outage analysis of user cooperation
• A Survey on Practical Applications of Multi-Armed and Contextual Bandits
• Nonparametric Bandits with Covariates
• Contextual Bandit Learning with Predictable Rewards
• Gamification of Pure Exploration for Linear Bandits
• Adapting to Misspecification in Contextual Bandits
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL
• Regret Balancing for Bandit and RL Model Selection
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms
• Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits

Cited by in corpus (5)

• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• Universal and data-adaptive algorithms for model selection in linear contextual bandits