Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees
This work addresses the challenge of efficient exploration-exploitation in bandit algorithms for researchers and practitioners, offering a method to reduce regret in contextual settings, though it builds incrementally on prior spectral property insights.
The paper tackles the problem of representation learning in stochastic contextual linear bandits by proposing BanditSRL, which learns realizable representations with good spectral properties to enable constant regret, achieving horizon-independent performance when such representations are available.
We study the problem of representation learning in stochastic contextual linear bandits. While the primary concern in this domain is usually to find realizable representations (i.e., those that allow predicting the reward function at any context-action pair exactly), it has been recently shown that representations with certain spectral properties (called HLS) may be more effective for the exploration-exploitation task, enabling LinUCB to achieve constant (i.e., horizon-independent) regret. In this paper, we propose BanditSRL, a representation learning algorithm that combines a novel constrained optimization problem to learn a realizable representation with good spectral properties with a generalized likelihood ratio test to exploit the recovered representation and avoid excessive exploration. We prove that BanditSRL can be paired with any no-regret algorithm and achieve constant regret whenever an HLS representation is available. Furthermore, BanditSRL can be easily combined with deep neural networks and we show how regularizing towards HLS representations is beneficial in standard benchmarks.