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:
- 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.
- 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.
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.
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