Bandit Feedback

## Two feedback regimes In ordinary supervised learning, every training example arrives with the answer attached. For a six-way classification problem you are told the true class, which means you can score all six candidate answers and compute a loss — cross-entropy, say — that is defined over *every* option, whether or not your model would have picked it. This is called **full-information feedback**: for each example, the payoff of every action is knowable. **Bandit feedback** is the weaker regime. Each round the world presents a situation, your system picks exactly one action out of a set, and the world returns a single number — the reward — for that action alone. The payoffs of the actions you did not take are never revealed, not late, not in aggregate, not ever. The name comes from the multi-armed bandit framing, where each option is one arm of a slot machine and pulling one arm tells you nothing about the others. ## The concrete shape of it Take a news homepage with one hero slot and six candidate headlines. On each visit the system serves one headline and records: the visitor context, which headline was served, and whether it was clicked. What is missing from that record is what any of the other five would have done **for that same visitor**. Scale does not repair this. After a billion visits you have click estimates for the headlines the policy served often, thin estimates for the ones it served rarely, and nothing at all for a headline it stopped serving on day one. ## Three consequences that matter in practice **1. There is no loss over all actions.** You cannot form a target vector across the six headlines and minimise the distance to it, because five of the six entries are unknown. Learning reduces to estimating a reward function `r(context, action)` from the (context, action, reward) triples you happened to log, then acting greedily or near-greedily on it. **2. The dataset is caused by the model.** In a supervised dataset the examples come from the world; here, which action gets an observation is decided by the policy that was running. If the old policy showed the sports headline mostly to visitors arriving from a sports referrer, then the sports headline's observed click rate mixes headline quality with audience composition. Comparing raw observed rates across actions is therefore a confounded comparison, not a measurement of the actions. **3. Exploration becomes a data-collection requirement, not a nicety.** An action that is never taken never gets an observation, so its estimate never updates. A policy that always serves what currently looks best can lock onto a mediocre option and remain self-confirming indefinitely, because the evidence that would refute it is exactly the evidence it declines to collect. ## Partial is not the same as noisy A common muddle is to call bandit feedback *noisy labels*. Noise means the observation you do get is a random draw around a true value: one visitor's click is a Bernoulli sample, not the headline's true rate. Missingness means there is no observation at all. More traffic averages away the noise on the actions you serve; it never fills in the actions you do not serve. Both problems exist at once, but only the second one defines the regime. It is also not the same as ordinary missing labels. In a normal dataset with gaps, the gaps arise from causes outside the model and each example still has one true label. Under bandit feedback each (context, action) pair has its own outcome, exactly one per round is revealed, and the choice of which one is made by the system itself — which is why imputation alone cannot rescue it. ## A ladder of feedback strength It helps to see the regimes as a ladder. Strongest is full information: every action's payoff is revealed. Next is bandit feedback: only the chosen action's payoff. Weaker still are settings where the reward is a comparison rather than a value, or an aggregate over many rounds. There is also an asymmetric case worth recognising: sometimes every action produces *some* observation (any headline shown is clicked or not), while in other problems one particular action produces no observation at all — a rejected loan applicant never repays and never defaults. The one-sided case is strictly harder, because the missing evidence is concentrated exactly where the policy is most confident. ## What a practitioner does about it Log the context, the action served, and the reward together as one record, and keep the identity of the action served rather than only the eventual winner. Keep a slice of traffic whose action is chosen independently of the model, so some evidence exists that the policy did not shape. And treat offline accuracy at predicting the reward of the logged action as weak evidence about a candidate policy that would take *different* actions, since that policy's behaviour lands in exactly the region where the log is thinnest.