Retail recommender systems usually rank items by relevance, yet retailers care about contribution margin: an upsell yields only the margin difference over the replaced item, while a cross‑sell yields its full margin. We introduce joint stochastic basket editing, a formulation where a single policy simultaneously selects replacement and addition offers for an existing basket, evaluates them through expected incremental contribution margin, and couples them via displayed‑offer, accepted‑offer, and joint‑acceptance response channels. To our knowledge this is the first model that couples upsell and cross‑sell responses; prior work corresponds to the zero‑coupling special case.
In simulations calibrated on five public basket datasets, StoBasket captures virtually all attainable offer margin: within 0.5% of the optimum in every default‑price setting and within 0.7% even when the true response lies outside the model family. Correct economic accounting yields the largest gain: margin‑weighted popularity leaves up to 11% of attainable margin unrealized, and a published next‑basket recommender leaves 11‑52% on the table. Joint selection adds 10.2% of attainable margin on Instacart, where premium tiers and add‑ons are strongly linked.
When offers must be paid together, common heuristics lose 64% of the margin, while exact search stays within 0.5%. For a structured subclass we characterize when staged policies fail and provide an exact optimizer that solves every tested real basket in 0.13 ms median and at most 111 ms. Profit saturates long before prediction accuracy: a correctly structured predictor trained on 5,000 randomized sessions reaches within 0.06% of perfect prediction, whereas a signal‑free model loses 38%. The same estimates enable a decision‑aware market‑basket analysis whose cost does not grow with association order.
Review