The Geometry of Unlearning in Semi-Bandits: Categories, Regret, and Exact Replay

We study exact unlearning in combinatorial semi-bandits, where a learner selects several items each round and observes their individual rewards. After exploration, it chooses a final action and stops collecting feedback. Removing an observation can change that stopping decision. How can learning remain stable, and how can an erased run be reconstructed from feedback already collected? We assign each protected action category a budget for changes in public event probabilities. For product actions with a unique optimum and comparable reward gaps, we prove matching regret bounds up to logarithmic factors. The cost separates finding the best action from keeping decisions stable. Category arrangement controls the second term: categories with equal entropy can leave different sampling opportunities. Our learner attains the bound without knowing the gaps. Its completion envelope uses the largest stopping probability over possible missing rewards. Shared random draws ensure that erased exploration ends no later than factual exploration, so retained feedback suffices for exact replay of this missing-data rule. Synthetic and preference-derived experiments measure regret, feedback collection, and reconstruction together.