Abstract
Standard contextual bandit (CB) frameworks assume that all relevant information for decision-making is available at the moment an action is served. However, in many real-world applications like content recommendation or e-commerce, critical information—termed "post-serving context"—is only revealed after an action is taken (e.g., a user's watch time or a product review). This paper introduces poLinUCB, a novel algorithm that leverages these delayed signals by simultaneously learning reward parameters and the mapping between pre- and post-serving contexts. Supported by a new, robustified version of the Elliptical Potential Lemma, the authors demonstrate that poLinUCB achieves sublinear regret even in the presence of noisy feature estimation, significantly outperforming traditional bandit baselines in both synthetic and real-world environments.
Introduction
In the standard contextual bandit setting, a learner observes a context (such as a user profile), selects an action (an "arm"), and receives a reward. This paradigm assumes the initial context is sufficient to predict the reward. In practice, systems like YouTube or Amazon generate valuable data after a recommendation is served. For instance, while a user's profile is known upfront, the specific way they interact with a recommended video (the post-serving context) is a much stronger predictor of their ultimate satisfaction (the reward).
Ignoring these "follow-up" signals leads to model misspecification. If the reward depends on post-serving data that the model cannot see at decision time, a standard CB algorithm may suffer from "linear regret," meaning it never converges to an optimal policy. While one could attempt to predict these follow-up signals, existing methods often fail to account for the noise inherent in these predictions, leading to suboptimal exploration and performance.
The poLinUCB Framework
The authors propose poLinUCB (Post-serving Linear Upper Confidence Bound) to bridge this gap. The algorithm is built on two primary technical pillars:
- Dual Learning and Simultaneous Estimation: Unlike traditional models, poLinUCB does not treat the context as static. It learns a mapping function $\phi^*$ that predicts the expected post-serving context ($z$) from the pre-serving context ($x$). At every time step, the algorithm uses historical data to update both the reward parameters and this context-mapping function.
- Robustified Elliptical Potential Lemma (EPL): This represents the paper's core theoretical contribution. The standard EPL is a cornerstone for proving bandit convergence but assumes that features are noise-free. Because poLinUCB relies on estimated (and thus noisy) post-serving contexts, the standard proof breaks down. The authors developed a generalized version of the EPL that accommodates noisy feature vectors and varying learning rates ($\alpha$).
Theoretical and Empirical Results
The authors provide a rigorous theoretical guarantee, proving a regret bound of $\tilde{O}(T^{1-\alpha}d_u^\alpha + d_u\sqrt{TK})$. This bound is significant because it establishes a direct relationship between the learnability of the post-serving context ($\alpha$) and the overall performance. If the follow-up signal is easily predictable, the algorithm achieves the standard $\sqrt{T}$ regret; if it is harder to predict, the performance degrades gracefully rather than failing entirely.
Experimental Validation
The framework was evaluated across two main settings:
- Synthetic Benchmarks: The authors tested the algorithm in environments where the mapping from pre-serving to post-serving context followed polynomial, periodical, and linear patterns. poLinUCB demonstrated consistent robustness across these varying functional complexities.
- MovieLens Dataset: Using this classic recommendation dataset, the authors simulated a real-world pipeline by treating a portion of user/movie features as "pre-serving" and others as "post-serving."
In both settings, poLinUCB significantly outperformed standard LinUCB (which ignores post-serving data) and LinUCB ($\hat{\phi}$) (a naive version that estimates context but fails to account for estimation noise). Notably, poLinUCB's performance closely approached an "Oracle" baseline that has impossible access to post-serving context before making a decision.
Key Insights and Future Directions
The central insight of this work is that post-serving contexts act as a structured bridge, containing information that is often more "learnable" than the raw reward signal itself. By robustifying the mathematical foundations of bandit exploration, the authors have provided a framework for handling the uncertainty of these predicted contexts.
While the current work focuses on linear reward models, the authors identify several avenues for future research:
- Non-linear Extensions: Extending the post-serving logic to deep neural network-based bandits.
- Complex Dependencies: Exploring scenarios where the post-serving context has complex, non-linear dependencies on the specific actions taken.
- Learnability Limits: Further investigating cases where post-serving information might be independent of the initial context, which currently limits the model's improvement potential.
Summary updated