Double-Linear Thompson Sampling for Context-Attentive Bandits

Djallel Bouneffouf, Raphaël Féraud, Sohini Upadhyay, Yasaman Khazaeni, Irina RishOpenReview 2020 · DOI · OpenReview

Abstract

In this paper, we analyze and extend an online learning framework known as Context-Attentive Bandit, motivated by various practical applications, from medical diagnosis to dialog systems, where due to observation costs only a small subset of a potentially large number of context variables can be observed at each iteration; however, the agent has a freedom to choose which variables to observe. We derive a novel algorithm, called Context-Attentive Thompson Sampling (CATS), which builds upon the Linear Thompson Sampling approach, adapting it to Context-Attentive Bandit setting. We provide a theoretical regret analysis and an extensive empirical evaluation demonstrating advantages of the proposed approach over several baseline methods on a variety of real-life datasets.

Introduction

Standard contextual bandit problems assume that an agent observes a full context vector before choosing an action. However, in many real-world scenarios—such as medical diagnosis or complex dialog systems—observing every feature is costly, time-consuming, or impossible. For instance, a doctor must decide which specific, expensive medical tests to run before choosing a treatment. This introduces the Context-Attentive Bandit (CAB) problem: the agent must strategically select a small subset of hidden features to observe within a budget to maximize rewards. The challenge is two-fold: selecting the most informative features and choosing the best action based on limited information.

Methodology: Double-Linear Thompson Sampling

The proposed Context-Attentive Thompson Sampling (CATS) algorithm utilizes a "double-linear" approach, maintaining two distinct linear models:

  1. The Feature Model: Estimates the expected reward contribution of individual features. Using Thompson Sampling, the agent samples from the posterior distribution to select the top $U$ features to reveal.
  2. The Reward Model: Once features are revealed, the agent uses a second round of Thompson Sampling on the partial context to estimate action rewards and select the best arm.

Key Innovations

  • Base Context Support: CATS handles scenarios where a "base" context is always visible, which significantly improves the agent's ability to pick additional features.
  • Non-Stationarity (NCATS): A variant using weight decay to adapt to shifting environments by "forgetting" outdated data.
  • Theoretical Grounding: The authors provide the first lower bound for the CAB problem and prove a regret bound of $O(\sqrt{T})$.

Empirical Evaluation

The algorithm was tested on diverse datasets including Warfarin (medical), Covertype (cartographic), CNAE-9 (text), and a Customer Assistant dialog system.

Comparison of CATS/NCATS against TSRC/WTSRC in stationary and non-stationary settings as a function of context revealed.

Key Results

  • Superior Performance: CATS and NCATS consistently outperformed the previous state-of-the-art, TSRC (Thompson Sampling with Restricted Context). As shown in the figures, revealing even a small percentage of context leads to significant reward gains.
  • Robustness: In non-stationary environments, NCATS maintained high rewards while baselines collapsed, demonstrating the effectiveness of the weight decay mechanism.
  • Efficiency: On the Covertype dataset, active feature selection significantly outperformed random or fixed-feature baselines.
Performance evaluation on the Customer Assistant dataset, showing rewards as more skills are revealed in both stationary and non-stationary settings.

In the Customer Assistant task, CATS effectively managed a large number of "skills" by querying only the most relevant ones, reducing computational overhead without sacrificing quality.

Insights and Future Work

The success of CATS relies on the additive assumption, treating feature selection as parallel linear problems. Thompson Sampling's stochastic nature proves ideal for this nested exploration of what to see and what to do.

Future work includes incorporating non-uniform costs for different features (e.g., blood pressure vs. MRI), extending the framework to "Neural" Thompson Sampling using deep learning, and moving beyond the additive assumption to handle complex feature dependencies where features may be redundant or synergistic.

Summary updated

Abstract

In this paper, we analyze and extend an online learning framework known as Context-Attentive Bandit, motivated by various practical applications, from medical diagnosis to dialog systems, where due to observation costs only a small subset of a potentially large number of context variables can be observed at each iteration;however, the agent has a freedom to choose which variables to observe. We derive a novel algorithm, called Context-Attentive Thompson Sampling (CATS), which builds upon the Linear Thompson Sampling approach, adapting it to Context-Attentive Bandit setting. We provide a theoretical regret analysis and an extensive empirical evaluation demonstrating advantages of the proposed approach over several baseline methods on a variety of real-life datasets
BibTeX
@misc{bouneffouf2020double,
  author = {Djallel Bouneffouf and Raphaël Féraud and Sohini Upadhyay and Yasaman Khazaeni and Irina Rish},
  title = {{Double-Linear Thompson Sampling for Context-Attentive Bandits}},
  year = {2020},
  eprint = {2010.09473},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.09473},
  howpublished = {OpenReview},
}
Figure