CoChat

An Efficient Bandit Algorithm for Realtime Multivariate Optimization

Open access
Hill, Daniel N., Nassif, Houssam, Liu, Yi, Iyer, Anand, Vishwanathan, S.V.N. · 2017 · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

The DOI matches its Crossref record; 32 of the 34 references it cites were found in a registry or an index; 3 of the 11 sources its claims cite were checked for support.

Abstract

Optimization is commonly employed to determine the content of web pages, such as to maximize conversions on landing pages or click-through rates on search engine result pages. Often the layout of these pages can be decoupled into several separate decisions. For example, the composition of a landing page may involve deciding which image to show, which wording to use, what color background to display, etc. Such optimization is a combinatorial problem over an exponentially large decision space. Randomized experiments do not scale well to this setting, and therefore, in practice, one is typically limited to optimizing a single aspect of a web page at a time. This represents a missed opportunity in both the speed of experimentation and the exploitation of possible interactions between layout decisions

Overview

CoChat Summary

TL;DR

The paper presents a multivariate bandit algorithm for realtime web-page layout optimization that models pairwise interactions between widgets, uses Thompson sampling for exploration, and hill climbing for efficient layout search. In a live Amazon experiment, it achieved a 21% conversion increase over the median layout after one week, though interaction effects were not significant on desktop and a simpler independent-widget approach performed comparably.

Key findings

  • In simulation with \(D=3\), \(N=8\) (512 layouts), hill climbing converged in \(6 \pm 2.4\) iterations, evaluating only \(6(N-1)+1=42\) distinct layouts; it reached the global optimum with probability \(p=0.35\), but mean regret fell from 0.112 for a random layout to 0.033 for the converged solution. With \(S=5\) random restarts, the global optimum was found with probability greater than 90% after at most \(42 \times 5 = 208\) layout evaluations.
  • In a 12-day live experiment on an Amazon promotional message with 48 total variations, MVT2 showed a 21% lift over the median layout and a 44% lift over the worst-performing layout. D-MABs converged in 3 days, MVT2 in 9 days, while \(N^D\)-MAB showed very little convergence.
  • A power analysis estimated that a traditional 48-treatment randomized experiment would require 66 days to detect a 5% effect with \(p<0.05\) and \(\beta<0.20\).
  • On desktop production data, likelihood ratio tests found 2nd-order (\(p=0.2577\)) and 3rd-order (\(p=0.428\)) interactions insignificant; in a mobile follow-up with 32 layouts, 2nd-order effects were significant (\(p=0.0096\)) but 3rd-order were not (\(p=0.1735\)).

Methods

  • The paper formulates contextual combinatorial bandit optimization over \(N^D\) layouts, using a Bayesian probit regression with pairwise widget interactions and optional context interactions; Thompson sampling selects layouts, and greedy hill climbing with random restarts approximates the argmax in realtime.
  • Simulations vary interaction strength (\(\alpha_2\)), number of variations per slot (\(N=2\) to 12), and context importance (\(\alpha_c\)), comparing MVT2, MVT2c, MVT1, and \(N^D\)-MAB over \(T=250{,}000\) steps with batch updates every 1000 iterations and 15 repetitions.
  • The live experiment randomly and equally distributed traffic across MVT2, \(N^D\)-MAB, and D-MABs for 12 days, with realtime Thompson sampling and daily batch model updates; analysis uses convergence, normalized success probability, regret, likelihood ratio tests, and power analysis.

Limitations

  • The paper states that widget contents are represented as identifiers, preventing generalization between related creatives; higher-order features should be regularized more heavily; complexity could be reduced via factorization machines or neural networks; and the impact of using hill climbing to approximate Thompson sampling on regret remains to be understood.
  • Evident from the text: on desktop, MVT2 and D-MABs converged to the same solution and 2nd/3rd-order interactions were insignificant, suggesting the interaction modeling provided little benefit in that experiment; D-MABs also converged faster and MVT2’s success rate was only comparable by day 6.
  • Evident from the text: without random restarts, hill climbing reached the global optimum only 35% of the time in simulation, and the live experiment’s positive result is from one Amazon service message, so generalization to other settings is not established.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1145/3097983.3098184

Cites

32 of 32 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

3 Valid · 0 Not valid · 5 Not checked · 69 Own results and interpretations

39 more claims

Create a free account to see all 77 claims and every source verdict.

See all claims — free account
  • Probably not a substantial claim. 14
  • It may state two separate claims as one. 24
  • The quote only partly states this claim. 3
  • Borderline: one of the tests for a substantial claim is unclear. 1

Create a free account to see these claims.

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

2 of 2

Citations

Cites

Show all 32 references

Research works printed but not linked: 1

  1. Karthik Mohan and Ofer Dekel 2011. Online bipartite matching with partially-bandit feedback Proceedings of NIPS workshop on Discrete optimization in Machine Learning. Granada Spain 1--7. Karthik Mohan and Ofer Dekel 2011. Online bipartite matching with partially-bandit feedback Proceedings of NIPS workshop on Discrete optimization in Machine Learning. Granada Spain 1--7.

Cited by

See all 113

Metadata

Authors
Hill, D. N., Nassif, H., Liu, Y., Iyer, A., & Vishwanathan, S. V. N.
Affiliations
Amazon (United States) (US)
Venue
Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Publisher
ACM
Published
2017-08-13
Pages
1813-1821
OpenAlex
W2743027853
Cited by
113
References
34
Citations by year
2026: 4 · 2025: 4 · 2024: 30 · 2023: 10 · 2022: 6 · 2021: 22 · 2020: 13 · 2019: 10 · 2018: 14
FWCI
16.74
Type
conference paper
Language
en
Open access
Locations
  • ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (publishedVersion, cc-by-nc-nd)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Simulation Techniques and Applications
  • Physical Sciences › Computer Science › Information Systems › Recommender Systems and Techniques
Keywords
multi-armed bandits, multivariate optimization, online experiments, landing pages, click-through rate, combinatorial optimization, real-time optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

A language model drew the claims from the paper on 2026-10-11, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-11 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Cited sources are checked with a language model’s help (gpt-6-sol).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: An Efficient Bandit Algorithm for Realtime Multivariate Optimization. https://app.cochat.ai/papers/10.1145/3097983.3098184
The paper
Hill, D. N., Nassif, H., Liu, Y., Iyer, A., & Vishwanathan, S. V. N. (2017). An Efficient Bandit Algorithm for Realtime Multivariate Optimization. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. https://doi.org/10.1145/3097983.3098184

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.