Problem
A team ranks items on a page with a linear contextual bandit and treats every full ordering as one arm. Eight items in eight positions already give 40,320 arms, and ten give 3,628,800. Linear models learn across arms through shared features. The bottleneck is arm selection: the standard step scores every arm with a dot product and takes the maximum, which is too slow for real-time responses at this scale. Greedy hill-climbing is faster but returns only an approximation whose quality drops as the problem grows.
Example from the article: ordering 10 items into 10 positions, where exhaustive scoring is infeasible and Greedy Search is about 40 times slower than the method below.
Solution in brief
Encode each arm with indicators for context, item-at-position and context x item-at-position. Then the score of an ordering is a sum of independent item-position contributions, and picking the best ordering is an assignment problem. Build a score contribution matrix from the model weights and solve it with the Hungarian algorithm, which gives the exact best ordering in polynomial time.
Questions this case answers
- How to find the exact highest-scoring ordering of items for a linear scoring model within a low-latency budget when the number of orderings grows factorially
- How to choose a ranking in an online-learning bandit when exhaustive scoring of all candidate rankings is too slow and greedy search gives no guarantees
- How to pick the best ordering of items in a linear contextual bandit within real-time latency when the number of orderings explodes?
- How to get the exact top-scoring arm instead of a hill-climbing approximation in a ranking bandit?
Tools and methods
- Thompson Sampling for linear contextual bandits — the bandit whose arg max arm-selection step is replaced
- Assignment Solver (Hungarian / Kuhn-Munkres algorithm) — finds the maximum-sum item-to-position assignment exactly
- Score contribution matrix and coefficient look-up table — turn model weights into the matrix the solver needs
Google or a one-time email code. No password.