Bandit Feedback

Unlike supervised learning where a true label exists for every input, bandit feedback creates a severe information bottleneck. The environment only reveals the reward for the chosen arm. The outcomes of all other actions remain permanently unknown. This transforms the learning problem from a static function approximation task into a sequential decision-making problem under uncertainty, where the agent must actively manage its own data collection strategy.

The defining consequence of bandit feedback is the inability to answer the question: What would have happened if I had chosen differently? This counterfactual gap means:

• You cannot compute a true loss gradient across all actions
• You cannot directly observe if a better option was missed
• All evaluation of unchosen actions relies on statistical estimation This blindness is why off-policy evaluation methods like Inverse Propensity Scoring are critical for safe model iteration.

A single record of bandit feedback is a tuple containing exactly four elements:

• Context (x): The feature vector describing the decision point
• Action (a): The specific arm selected by the logging policy
• Reward (r): The observed scalar outcome (click, conversion, revenue)
• Propensity (p): The probability with which the action was chosen Crucially, this record contains no information about the rewards of actions a' ≠ a. The propensity score is essential for later debiasing.

Bandit feedback is often called partial label feedback to distinguish it from the full-information setting:

• Full Information: After a decision, you observe the reward for every possible action (e.g., weather prediction where the true outcome eventually materializes)
• Bandit Feedback: You observe the reward for only the action taken (e.g., showing an ad; you never know if the other ad would have been clicked) Most real-world personalization systems operate under strict bandit feedback.

Because the algorithm controls its own data generation, the logging policy directly determines the quality and coverage of the training data. A purely exploitative policy creates a rich-get-richer feedback loop where popular items receive all the impressions and new items never get a chance. This is why explicit exploration strategies like epsilon-greedy or Thompson Sampling are not optional optimizations—they are required to ensure the feedback mechanism doesn't collapse into a self-reinforcing bias.

Bandit feedback is often complicated by temporal separation between action and outcome:

• Immediate: A click happens within milliseconds
• Delayed: A purchase happens days after the initial recommendation
• Compound: The reward is a long-term metric like customer lifetime value (LTV) that aggregates many decisions Delayed rewards require credit assignment mechanisms to attribute the final outcome back to the specific decision that influenced it, often using temporal difference learning.

The primary statistical methodology for estimating the performance of a new policy using historical data collected under a different logging policy. Because bandit feedback only reveals the reward for the chosen action, counterfactual evaluation is essential for safely validating models offline before deployment. It addresses the fundamental missing data problem inherent in bandit feedback by correcting for the selection bias introduced by the logging policy.

An off-policy estimator that corrects for selection bias in logged bandit data by re-weighting observed rewards by the inverse probability of the action being taken by the logging policy. IPS is the foundational technique for making valid inferences from bandit feedback, but it can suffer from high variance when the logging policy assigns very low probabilities to certain actions.

An off-policy evaluation method that combines inverse propensity scoring with a direct reward model to provide unbiased estimates even if one of the two models is misspecified. This approach leverages the partial information in bandit feedback more efficiently than IPS alone, reducing variance while maintaining theoretical guarantees. It is the preferred estimator for production-grade counterfactual evaluation.

The fundamental dilemma in sequential decision-making where an agent must choose between trying new actions to gather information and selecting the best-known action to maximize immediate reward. Bandit feedback is the direct consequence of this trade-off: every time the agent exploits, it forgoes the opportunity to observe the outcomes of alternative actions, creating the partial feedback problem.

The numerical feedback received from the environment after taking an action, such as a click, conversion, or revenue metric, which the bandit aims to maximize. In bandit feedback, the reward signal is observed only for the chosen arm. The design of this signal is critical: it must be a faithful proxy for the true business objective and must be observable with minimal delay to enable effective learning.

A scenario where the outcome of an action is not immediately observable, requiring the bandit to attribute credit back to a past decision after a time lag. Delayed rewards compound the difficulty of bandit feedback because the learning algorithm must maintain a memory of past context-action pairs and correctly associate them with future outcomes. This is common in e-commerce where a product recommendation may lead to a purchase days later.