On the Complexity of Representation Learning in Contextual Linear Bandits

• URL: http://arxiv.org/abs/2212.09429v1
• Date: Mon, 19 Dec 2022 13:08:58 GMT
• Title: On the Complexity of Representation Learning in Contextual Linear Bandits
• Authors: Andrea Tirinzoni, Matteo Pirotta, Alessandro Lazaric
• Abstract summary: We show that representation learning is fundamentally more complex than linear bandits. In particular, learning with a given set of representations is never simpler than learning with the worst realizable representation in the set.
• Score: 110.84649234726442
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In contextual linear bandits, the reward function is assumed to be a linear combination of an unknown reward vector and a given embedding of context-arm pairs. In practice, the embedding is often learned at the same time as the reward vector, thus leading to an online representation learning problem. Existing approaches to representation learning in contextual bandits are either very generic (e.g., model-selection techniques or algorithms for learning with arbitrary function classes) or specialized to particular structures (e.g., nested features or representations with certain spectral properties). As a result, the understanding of the cost of representation learning in contextual linear bandit is still limited. In this paper, we take a systematic approach to the problem and provide a comprehensive study through an instance-dependent perspective. We show that representation learning is fundamentally more complex than linear bandits (i.e., learning with a given representation). In particular, learning with a given set of representations is never simpler than learning with the worst realizable representation in the set, while we show cases where it can be arbitrarily harder. We complement this result with an extensive discussion of how it relates to existing literature and we illustrate positive instances where representation learning is as complex as learning with a fixed representation and where sub-logarithmic regret is achievable.

Related papers

• Learned feature representations are biased by complexity, learning order, position, and more [4.529707672004383]
  We explore surprising dissociations between representation and computation. We train various deep learning architectures to compute multiple abstract features about their inputs. We find that their learned feature representations are systematically biased towards representing some features more strongly than others.
  arXiv  Detail & Related papers  (2024-05-09T15:34:15Z)
• Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees [103.69464492445779]
  We propose BanditSRL, a representation learning algorithm that learns a realizable representation with good spectral properties. We prove that BanditSRL can be paired with any no-regret algorithm and achieve constant regret whenever an HLS representation is available.
  arXiv  Detail & Related papers  (2022-10-24T10:04:54Z)
• Fair Interpretable Learning via Correction Vectors [68.29997072804537]
  We propose a new framework for fair representation learning centered around the learning of "correction vectors" The corrections are then simply summed up to the original features, and can therefore be analyzed as an explicit penalty or bonus to each feature. We show experimentally that a fair representation learning problem constrained in such a way does not impact performance.
  arXiv  Detail & Related papers  (2022-01-17T10:59:33Z)
• Learning Algebraic Representation for Systematic Generalization in Abstract Reasoning [109.21780441933164]
  We propose a hybrid approach to improve systematic generalization in reasoning. We showcase a prototype with algebraic representation for the abstract spatial-temporal task of Raven's Progressive Matrices (RPM) We show that the algebraic representation learned can be decoded by isomorphism to generate an answer.
  arXiv  Detail & Related papers  (2021-11-25T09:56:30Z)
• DirectProbe: Studying Representations without Classifiers [21.23284793831221]
  DirectProbe studies the geometry of a representation by building upon the notion of a version space for a task. Experiments with several linguistic tasks and contextualized embeddings show that, even without training classifiers, DirectProbe can shine light into how an embedding space represents labels.
  arXiv  Detail & Related papers  (2021-04-13T02:40:26Z)
• Leveraging Good Representations in Linear Contextual Bandits [131.91060536108301]
  A contextual bandit problem may admit multiple linear representations. Recent works showed that there exist "good" representations for which constant problem-dependent regret can be achieved. We show that the regret is indeed never worse than the regret obtained by running LinUCB on the best representation.
  arXiv  Detail & Related papers  (2021-04-08T14:05:31Z)
• Predicting What You Already Know Helps: Provable Self-Supervised Learning [60.27658820909876]
  Self-supervised representation learning solves auxiliary prediction tasks (known as pretext tasks) without requiring labeled data. We show a mechanism exploiting the statistical connections between certain em reconstruction-based pretext tasks that guarantee to learn a good representation. We prove the linear layer yields small approximation error even for complex ground truth function class.
  arXiv  Detail & Related papers  (2020-08-03T17:56:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.