An Efficient Bandit Algorithm for Realtime Multivariate Optimization
Open accessThe 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
Cites
Statistics
Verification
Claims the paper makes
3 Valid · 0 Not valid · 5 Not checked · 69 Own results and interpretations
Every source the paper cites for this claim was checked and supports it.
In the paper
“This property ensures that Thompson Sampling remains computationally efficient as long as we can efficiently solve arдmax A B ⊤ A,X W [2].”
§ An Efficient Bandit Algorithm for Realtime Multivariate Optimization > 3.1 Thompson Sampling
What the sources say
- Supportedcites [2] 2. Shipra Agrawal and Navin Goyal. 2013. Thompson Sampling for Contextual Bandits with Linear Payoffs. In Proceedings of the 30th International Conference on Machine Learning (ICML). JMLR, Atlanta, Georgia, 127-135. source
Section 2.2 (p. 6) says each step of the paper’s Thompson Sampling algorithm requires a Gaussian sample and an argmax, and that the algorithm is efficient when that argmax can be solved efficiently. The citing sentence applies this computational-efficiency condition to its layout-selection argmax. (LLM, conf=0.90)
plainstates a possible cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Despite not always converging to a global optimum, the mean regret was reduced from 0.112 for a random layout to 0.033 for the converged solution.”
§ An Efficient Bandit Algorithm for Realtime Multivariate Optimization > 4.3 Hill climbing impact
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The N D -MAB algorithm shows very little convergence throughout the course of the experiment.”
§ An Efficient Bandit Algorithm for Realtime Multivariate Optimization > 5.2 Analysis Of Results
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“We see superior performance for MVT2c over MVT2 for values of α c > 0.5.”
§ An Efficient Bandit Algorithm for Realtime Multivariate Optimization > 4.2 Simulation experiments
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Hill climbing converges quickly for this data set.”
§ An Efficient Bandit Algorithm for Realtime Multivariate Optimization > 4.3 Hill climbing impact
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
39 more claims
Create a free account to see all 77 claims and every source verdict.
- 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
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.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ An Efficient Bandit Algorithm for Realtime Multivariate Optimization > 4.3 Hill climbing impact
“As each run of hill climbing is independent, the probability of reaching the global peak after S restarts is 1 -(1 -p(дlobal optimum)) S .Therefore, with S = 5, the global optimum can be found with probability greater than 90% after a maximum of 42 * S = 208 distinct layout evaluations.”
§ An Efficient Bandit Algorithm for Realtime Multivariate Optimization > 4.3 Hill climbing impact
“However, this came at the cost that the hill climb reached the global optimum with a probability of p(дlobal optimum) = 0.35.”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
“This corresponds to only 6(N -1) + 1 = 42 distinct layouts being evaluated out of a total of 512 possible layouts.”
§ An Efficient Bandit Algorithm for Realtime Multivariate Optimization > 4.3 Hill climbing impact
Reported 42 · recomputed 43
Citations
Cites
Representation Learning: A Review and New Perspectives
Bengio, Y., Courville, A., & Vincent, P. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.50 · Cited by 13,001 · cited 1×
“The complexity of representing interactions could also be reduced through techniques such as factorization machines [18] and neural networks [3] that produce low-dimension embeddings out of high-order features.”
MethodCasella, G., & Berger, R. (2024) · Chapman & Hall/CRC eBooks · doi:10.1201/9781003456285 · Cited by 5,711
Rendle, S. (2010) · 2010 IEEE International Conference on Data Mining · doi:10.1109/icdm.2010.127 · Cited by 3,189 · cited 1×
“regularized more heavily than lower order features to reduce parametric complexity. The complexity of representing interactions could also be reduced through techniques such as factorization machines [18] and neural networks [3] that produce low-dimension embeddings out of high-order features. Finally, it still remain…”
MethodA contextual-bandit approach to personalized news article recommendation
Li, L., Chu, W., Langford, J., & Schapire, R. E. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772758 · Cited by 2,562
Statistics for experimenters: design, innovation, and discovery
(2006) · Choice Reviews Online · doi:10.5860/choice.43-3429 · Cited by 1,644
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986276 · Cited by 1,404
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S., & Cesa-Bianchi, N. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000024 · Cited by 1,295 · cited 2×
“We now define a stochastic contextual multi-armed bandit problem [5].”
BackgroundExperiments - Planning, Analysis and Parameter Design Optimization
(2001) · Journal of Tropical Pediatrics · doi:10.1093/tropej/47.2.126 · Cited by 1,124 · cited 1×
“One approach for efficiently learning to optimize a large decision space is fractional factorial design [4, 13].”
Background(2011) · Cited by 1,000
Analysis of Thompson Sampling for the multi-armed bandit problem
Agrawal, S., & Goyal, N. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.1797 · Cited by 819
Research works printed but not linked: 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
Chameleon: scalable adaptation of video analytics
Jiang, J., Ananthanarayanan, G., Bodik, P., Sen, S., & Stoica, I. (2018) · Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication · doi:10.1145/3230543.3230574 · Cited by 467
“al [19] use Thompson sampling [11] to optimize the layout of a multi-component web page; they use greedy hill climbing to select the next layout, similar to Chameleon, but Chameleon exploits more independence structure and monotonicity.”
BackgroundMethodInfluentialA Tutorial on Thompson Sampling
Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., & Wen, Z. (2018) · now publishers, Inc. eBooks · doi:10.1561/9781680834710 · Cited by 380
Finding Faster Configurations Using FLASH
Nair, V., Yu, Z., Menzies, T., Siegmund, N., & Apel, S. (2020) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2018.2870895 · Cited by 166
“Among numerous other problems which are similar to performance configuration optimization, the problem of how to maximize conversions on landing pages or click-through rates on search-engine result pages [4], [36], [37] has gathered interest.”
BackgroundZhao, X., Xia, L., Tang, J., & Yin, D. (2019) · ACM SIGWEB Newsletter · doi:10.1145/3320496.3320500 · Cited by 106
“In [Hill et al. 2017], bandit formulation is applied to explore the lay-out space efficiently and hill-climbing is used to select optimal content in real-time.”
MethodInformation Retrieval: Advanced Topics and Techniques
(2024) · ACM eBooks · doi:10.1145/3674127 · Cited by 88
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
- hybrid
- doi.org
- Licence
- 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.