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
Figures














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
- 16. Karthik Mohan and Ofer Dekel. 2011. Online bipartite matching with partially- bandit feedback. In 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
Reinforcement learning for personalization: A systematic literature review
den Hengst, F., Grua, E. M., el Hassouni, A., & Hoogendoorn, M. (2020) · Data Science · doi:10.3233/ds-200028 · Cited by 83
“D om ai n Commerce [53, 60, 67, 72, 87, 89, 94, 96, 106, 111, 112, 119, 123, 129, 138, 151, 154, 155, 157, 164, 170, 171, 175, 178, 200, 201, 217, 220] Communication [81, 101, 103, 142]”
Moment-based quantile sketches for efficient high cardinality aggregation queries
Gan, E., Ding, J., Tai, K. S., Sharan, V., & Bailis, P. D. (2018) · Proceedings of the VLDB Endowment · doi:10.14778/3236187.3236212 · Cited by 66
Video Surveillance on Mobile Edge Networks—A Reinforcement-Learning-Based Approach
Hu, H. R., Shan, H., Wang, C., Sun, T., Zhen, X., Kunpeng, Y., Yu, L., Zhang, Z., & Quek, T. Q. S. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.2968941 · Cited by 47
“Generally, there are more sample efficient algorithms for the multiarmed bandit problem, such as Thompson sampling [38] and Bayesian estimation [39].”
MethodLACO: A Latency-Driven Network Slicing Orchestration in Beyond-5G Networks
Zanzi, L., Sciancalepore, V., García‐Saavedra, A., Schotten, H. D., & Costa-Perez, X. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.3027963 · Cited by 51
“The authors of [37] presented an algorithm for multivariate optimization on large decision spaces based on an innovative approach combining hill climbing optimization and Thompson sampling.”
MethodContinuous experimentation and A/B testing: a mapping study
Ros, R., & Runeson, P. (2018) · doi:10.1145/3194760.3194766 · Cited by 60
“contrast, other researchers take an optimization approach and automate experimentation with techniques such as metaheuristic search (genetic algorithms) [26] or multi-variate bandit optimization [16].”
MethodA Tutorial on Thompson SamplingPreprint
Russo, D., Roy, B. V., Kazerouni, A., et al. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.02038 · Cited by 35
Sun, J., Zhang, H., Zhou, A., et al. (2018) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2018.2865495 · Cited by 35
Beyond Preferences in AI Alignment
Zhi-Xuan, T., Carroll, M., Franklin, M., & Ashton, H. (2025) · Philosophical Studies · doi:10.1007/s11098-024-02249-w · Cited by 34
“…of recommender systems (Thorburn et al., 2022), with many papers modeling recommendation as the problem of showing items to users that they are most likely to engage with, which is presumed to be the item they find the most rewarding (Li et al., 2010; Hill et al., 2017; McInerney et al., 2018).”
BackgroundMulti-armed recommender system bandit ensembles
Cañamares, R., Redondo, M. G., & Castells, P. (2019) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/3298689.3346984 · Cited by 37
“In this line, we may say that bandit ensembles have been already used for A/B testing to select a winner between several candidates [11] –such winner is simply the algorithm that has been selected more times by the ensemble.”
MethodDai, X., Zhang, Z., Yang, P., Xu, Y., Liu, X., & Lui, J. C. S. (2024) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/3664647.3681269 · Cited by 25
“Defining 𝜆 as the integral ) 𝑑𝑥 with 𝐾 indicating”
Feedback-based self-learning in large-scale conversational AI agents
Ponnusamy, P., Ghias, A., Yi, Y., Yao, B., Guo, C., & Sarikaya, R. (2022) · AI Magazine · doi:10.1609/aimag.v42i4.15102 · Cited by 19
Page-level Optimization of e-Commerce Item Recommendations
Lo, C., Yu, H., Xin, Y., Shetty, K., He, C., Hu, K., Platz, J., Ilardi, A., & Madhvanath, S. (2021) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/3460231.3474242 · Cited by 28
“In general, page-level optimization needs to satisfy multiple important goals [13, 17, 21, 26].”
BackgroundHelleckes, L. M., Müller, C., Griesbach, T., Waffenschmidt, V., Moch, M., Osthege, M., Wiechert, W., & Oldiges, M. (2022) · Biotechnology and Bioengineering · doi:10.1002/bit.28261 · Cited by 17
“The broad range of applications includes the exploration of chemical design spaces (Hernández‐ Lobato et al., 2017), mobile health applications (Tomkins et al., 2021), or real‐time content selection for web pages (Hill et al., 2017).”
BackgroundWhole Page Optimization with Global Constraints
Ding, W., Govindaraj, D., & Vishwanathan, S. V. N. (2019) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3292500.3330675 · Cited by 22
“There is a vast literature on relevance ranking [2, 11, 12, 15, 17], and somewhat less has been written about diversity and whole-page effects [7, 10, 14, 18, 20, 26–28], and even fewer papers address enforcing business constraints [1, 8, 9, 16, 19, 29].”
BackgroundMethodResultInfluentialSelf-citationBayesian Meta-Prior Learning Using Empirical Bayes
Nabi, S., Nassif, H., Hong, J., Mamani, H., & Imbens, G. W. (2021) · Management Science · doi:10.1287/mnsc.2021.4136 · Cited by 29
“We further examine the performance of empirical Bayes prior on our Amazon live production system, using a TS generalized linear multi-armed bandit with a probit link function (Hill et al. 2017).”
BackgroundMethodInfluentialSelf-citationWill Digital Commerce and Analytics Be the Death of Traditional Brands?
Fulgoni, G. M. (2018) · Journal of Advertising Research · doi:10.2501/jar-2018-023 · Cited by 13
Recommender Systems for Personalized User Experience: Lessons learned at Booking.com
Kangas, I., Schwoerer, M., & Bernardi, L. (2021) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/3460231.3474611 · Cited by 16
“MAB have gained increased popularity during recent years to solve similar use-cases [2, 9, 12].”
BackgroundAutomated Creative Optimization for E-Commerce Advertising
Chen, J., Xu, J., Jiang, G., Ge, T., Zhang, Z., Lian, D., & Zheng, K. (2021) · International World Wide Web Conference (WWW) · doi:10.1145/3442381.3449909 · Cited by 36
“In a similar task, the optimal selection of layouts for web pages [10], the interactions between dierent elements are captured as the way in the Poly2 [4] model.”
MethodInfluentialIter8: Online Experimentation in the Cloud
Toslali, M., Parthasarathy, S., Oliveira, F., Huang, H. P., & Coskun, A. K. (2021) · ACM Symposium on Cloud Computing (SoCC) · doi:10.1145/3472883.3486984 · Cited by 15
“Online experimentation of Web and mobile applications (i.e., code running on browsers or mobile devices) is widely adopted, supported by mature solutions [22, 55, 69], and has been extensively studied [1, 2, 22, 25, 26, 31, 49, 51, 55, 59, 60, 75].”
BackgroundEnabling efficient and general subpopulation analytics in multidimensional data streams
Manousis, A., Zhuo, C., Basat, R. B., Liu, Z., & Sekar, V. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3551793.3551867 · Cited by 23
Soudain: Online Adaptive Profile Configuration for Real-time Video Analytics
Wu, K., Jin, Y., Miao, W., Zeng, Z., Qian, Z., Wang, J., Zhou, M., & Cao, T. (2021) · International Workshop on Quality of Service · doi:10.1109/iwqos52092.2021.9521328 · Cited by 17
Liu, C. H. B., Chamberlain, B. P., & McCoy, E. J. (2020) · Data Science and Engineering · doi:10.1007/s41019-020-00121-5 · Cited by 14
“Amazon [7] and Facebook [8] have also reported the use of various causal inference techniques to measure the incrementality of advertising campaigns.”
BackgroundMining Workflows for Anomalous Data Transfers
Tu, H., Papadimitriou, G., Kiran, M., Wang, C., Mandal, A., Deelman, E., & Menzies, T. (2021) · International Conference on Mining Software Repositories (MSR) · doi:10.1109/msr52588.2021.00013 · Cited by 13
“problems of how to maximize conversions on landing pages or click-through rates on search-engine result pages [40, 41, 42] has gathered interest.”
BackgroundDeep Reinforcement Learning for Web Crawling
Avrachenkov, K. E., Borkar, V. S., & Patil, K. (2021) · Indian Control Conference · doi:10.1109/icc54714.2021.9703160 · Cited by 11
Castells, P., & Jannach, D. (2024) · ACM eBooks · doi:10.1145/3674127.3674131 · Cited by 11
Research on the Optimization of A/B Testing System Based on Dynamic Strategy Distribution
Sheng, J., Liu, H., & Wang, B. (2023) · Processes · doi:10.3390/pr11030912 · Cited by 9
Multi-Agent Deep Reinforcement Learning for Dynamic Routing in MANETs Using Graph Neural Networks
Alanazi, F., & Zareei, M. (2025) · IEEE Access · doi:10.1109/access.2025.3601994 · Cited by 8
Sun, J., Zhao, Y., Zhang, N., et al. (2021) · IET Generation Transmission & Distribution · doi:10.1049/gtd2.12318 · Cited by 8
A Framework for Tunable Anomaly Detection
Alam, M. R., Gerostathopoulos, I., Prehofer, C., Attanasi, A., & Bureš, T. (2019) · IEEE International Conference on Software Architecture (ICSA) · doi:10.1109/icsa.2019.00029 · Cited by 10
“[4], Facebook [5], LinkedIn [6], Amazon [7] and Uber [8].”
BackgroundEfficient Optimal Selection for Composited Advertising Creatives with Tree Structure
Chen, J., Ge, T., Jiang, G., Zhang, Z., Lian, D., & Zheng, K. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i5.16516 · Cited by 17
“A more efficient method is multivariate bandit (Hill et al. 2017), which models interactions between elements of two different ingredients explicitly by defining the expected reward for each creative as follows: xTc θ = θ 0 + D∑ i=1 θ1i (c) + D∑ j=1 D∑ k=j+1 θ2j,k(c) (1) where θ0 is a common bias,…”
BackgroundMethodInfluentialChen, N., Zhang, S., Quan, S., Ma, Z., Qian, Z., & Lu, S. (2021) · Computer Networks · doi:10.1016/j.comnet.2021.108513 · Cited by 8
A Self-Learning Framework for Large-Scale Conversational AI Systems
Liu, X., Guo, C., Yao, B., & Sarikaya, R. (2024) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2024.3363971 · Cited by 11
“First, a multi-armed bandit approach [53], [54], [55], [56], [57] is adopted to balance exploration and exploitation.”
BackgroundContinuous Experimentation Scenarios: A Case Study in e-Commerce
Ros, R., & Bjarnason, E. (2018) · Euromicro Conference on Software Engineering and Advanced Applications (SEAA) · doi:10.1109/seaa.2018.00064 · Cited by 6
“The tools have employed optimisation methods such as genetic algorithms [7], [8] or multivariate-bandit optimization [5].”
MethodA Batched Multi-Armed Bandit Approach to News Headline Testing
Mao, Y., Chen, M., Wagle, A., Pan, J., Natkovich, M., & Matheson, D. (2018) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2018.8622399 · Cited by 10
“, with a multivariate MAB algorithm introduced in [20].”
BackgroundMethodInfluentialVibration-Based Indoor Human Sensing Quality Reinforcement via Thompson Sampling
Yu, T., Zhang, Y., Hu, Z., Xu, S., & Pan, S. (2021) · doi:10.1145/3458648.3460012 · Cited by 6
“To model the varying underlying structures and achieve efficient learning, existing works have proposed different parameterizations of the reward value, such as linear functions, polynomial functions and neural networks [2, 7, 21].”
BackgroundBiswas, A., Pham, T. T., Vogelsong, M., Snyder, B., & Nassif, H. (2019) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3292500.3330733 · Cited by 7
“This is a simplifying assumption which serves as a good baseline [6, 12].”
BackgroundSelf-citationExploiting Relevance for Online Decision-Making in High-Dimensions
Turğay, E., Bulucu, C., & Tekin, C. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3048223 · Cited by 5
“Moreover, our formulation allows us to deal with highdimensional and continuum sets of arms, which can be used in representing actions sets for drug dosage, online auctions [20], routing [21], web-based recommendations [22] and web page content optimization [23].”
MethodControlled experimentation in continuous experimentation: Knowledge and challenges
Auer, F., Ros, R., Kaltenbrunner, L., Runeson, P., & Felderer, M. (2021) · Information and Software Technology · doi:10.1016/j.infsof.2021.106551 · Cited by 76
“This is studied at Amazon [95] and Linkedin [96], particularly for environments were control is continuous deployment is hard (such as mobile app development).”
BackgroundMethodTrippas, J. R. (2024) · ACM eBooks · doi:10.1145/3674127.3674135 · Cited by 6
Data-driven software design with Constraint Oriented Multi-variate Bandit Optimization (COMBO)
Ros, R., & Hammar, M. (2020) · Empirical Software Engineering · doi:10.1007/s10664-020-09856-1 · Cited by 5
“Second, according to Hill et al. (2017), it enables personalization of software to users by having variables that describe users in the optimization (e.g., device type and location).”
BackgroundMethodInfluentialQuickAdapt: Scalable Adaptation for Big Data Cyber Security Analytics
Ullah, F., & Babar, M. A. (2019) · IEEE International Conference on Engineering of Complex Computer Systems (ICECCS) · doi:10.1109/iceccs.2019.00016 · Cited by 8
“Several recent studies [25-27] also faced the same issue of large adaptation time and proposed solutions accordingly.”
BackgroundMethodFair Data Generation and Machine Learning Through Generative Adversarial Networks
Wu, X., Xu, D., Yuan, S., & Zhang, L. (2022) · Intelligent systems reference library · doi:10.1007/978-3-030-91390-8_3 · Cited by 8
Weak Signal Asymptotics for Sequentially Randomized ExperimentsPreprint
Kuang, X., & Wager, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.09855 · Cited by 4
Learning to bid and rank together in recommendation systems
Ji, G., Jiang, W., Li, J., Fahid, F. M., Chen, Z., Li, Y., Xiao, J., Bao, C., & Zhu, Z. (2023) · Machine Learning · doi:10.1007/s10994-023-06444-4 · Cited by 4
“Another topic relevant to our paper is called whole-page presentation optimization (Wang et al., 2016; Hill et al., 2017; Jiang et al., 2018; Bello et al., 2018; Ding et al., 2019).”
Liu, C. H. B., & Chamberlain, B. P. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.06258 · Cited by 4
“Major technology companies such as Amazon [13], Airbnb [23], eBay [25], Facebook [1], Netflix [29] and Yandex [24] have all reported the extensive use of online controlled experiments to measure the impact of their products and guide business decisions.”
BackgroundMoment-Based Quantile Sketches for Efficient High Cardinality Aggregation QueriesPreprint
Gan, E., Ding, J., Tai, K. S., et al. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.01969 · Cited by 3
Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning
Namkoong, H., Daulton, S., & Bakshy, E. (2026) · Transactions on machine learning research · doi:10.48550/arxiv.2011.14266 · Cited by 9
“As in many production systems, we consider the setting where the policy is updated offline with batches of new data [27].”
BackgroundTemporal Extraction and Retrieval
Alonso, O., & Spaniol, M. (2024) · ACM eBooks · doi:10.1145/3674127.3674137 · Cited by 2
Tonellotto, N. (2024) · ACM eBooks · doi:10.1145/3674127.3674130 · Cited by 5
What is the Value of Experimentation & Measurement?
Liu, C. H. B., & Chamberlain, B. P. (2019) · Proceedings · doi:10.1109/icdm.2019.00151 · Cited by 3
“Amazon [7] and Facebook [8] have also reported the use of various causal inference techniques to measure the incrementality of advertising campaigns.”
BackgroundRapid and Scalable Bayesian AB Testing
Chennu, S., Maher, A., Pangerl, C. J., Prabanantham, S., Bae, J. H., Martin, J., & Goswami, B. (2023) · IEEE International Conference on Data Science and Advanced Analytics (DSAA) · doi:10.1109/dsaa60987.2023.10302590 · Cited by 3
“The general methodology of Bayesian linear modelling has been successfully applied to realise contextual optimisation using multi-armed bandits [14], [15].”
BackgroundMethodVerberne, S. (2024) · ACM eBooks · doi:10.1145/3674127.3674141 · Cited by 5
Ferro, N., & Maistro, M. (2024) · ACM eBooks · doi:10.1145/3674127.3674132 · Cited by 6
Privacy in Information Retrieval
Soboroff, I. M. (2024) · ACM eBooks · doi:10.1145/3674127.3674139 · Cited by 2
Automated conceptual design of mechanisms based on Thompson Sampling and Monte Carlo Tree Search
Mao, J., Zhu, Y., Chen, G., et al. (2024) · Applied Soft Computing · doi:10.1016/j.asoc.2024.112659 · Cited by 2
Sequential) Importance Sampling BanditsPreprint
Urteaga, I., & Wiggins, C. H. (2018) · arXiv (Cornell University) · Cited by 2
Intelligent Data Mining Techniques for Automatic Service Management
Wáng, Q. (2018) · FIU - Digital Commons (Florida International University) · doi:10.25148/etd.fidc007024 · Cited by 2
Accelerated learning from recommender systems using multi-armed banditPreprint
Hejazinia, M., Eastman, K. M., Shuqin, Y., Amirabadi, A., & Divvela, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.06158 · Cited by 6
“Authors from Amazon also have highlighted the use of contextual bandit for optimizing content on web pages [36].”
BackgroundTowards Capacity-Aware Broker Matching: From Recommendation to Assignment
Wei, S., Tong, Y., Zhou, Z., et al. (2023) · Proceedings - International Conference on Data Engineering · doi:10.1109/icde55515.2023.00065 · Cited by 1
“Li et al. [8] propose the LinUCB algorithm, which combines a linear predictor with upper bound confidence algorithms in 2010 and follow-up researchers extend the basic framework of LinUCB for efficient learning [52] and latent relations representation [53].”
MethodOn the Analysis of Two-Stage Stochastic Bandit
Liu, Y., Li, H., Zheng, Z., Wu, F., & Chen, G. (2024) · ACM International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (MobiHoc) · doi:10.1145/3641512.3686360 · Cited by 1
Self-citationeCommerce Search and Discovery
Kallumadi, S. T., & King, T. H. (2024) · ACM eBooks · doi:10.1145/3674127.3674140 · Cited by 1
Efficient Multivariate Bandit Algorithm with Path Planning
Nie, K., Zhang, Z., Yuan, T. T., Song, R., & Burke, P. B. (2020) · IEEE International Conference on Tools with Artificial Intelligence (ICTAI) · doi:10.1109/ictai50040.2020.00023 · Cited by 1
The Impact of Batch Learning in Stochastic Linear Bandits
Provodin, D., Gajane, P., Pechenizkiy, M., et al. (2022) · Proceedings · doi:10.1109/icdm54844.2022.00146 · Cited by 1
“As a consequence, it is now frequently a case in practice when the batch size is chosen for the purpose of computational accessibility rather than statistical evidence (Chapelle and Li, 2011; Hill et al., 2017).”
BackgroundLinear Contextual Bandits with Hybrid Payoff: Revisited
Das, N., & Sinha, G. (2024) · ECML/PKDD · doi:10.1007/978-3-031-70365-2_26 · Cited by 5
“The LinearCB problem is a popular choice to model sequential decision making scenarios such as news recommendations (Li et al., 2010), web-page optimization (Hill et al., 2017) etc.”
BackgroundThompson sampling for multi-armed bandits in big data environments
Kim, M. K., & Hwang, B. S. (2024) · Korean Journal of Applied Statistics · doi:10.5351/kjas.2024.37.5.663 · Cited by 1
Galuščáková, P., Oard, D. W., & Nair, S. (2024) · ACM eBooks · doi:10.1145/3674127.3674136 · Cited by 3
Gómez, E., Cuesta, H., Gkiokas, A., Gómez-Cañón, J. S., Porcaro, L., & Yesiler, F. (2024) · ACM eBooks · doi:10.1145/3674127.3702959 · Cited by 5
Baeza-Yates, R. A., Murgai, L., & Dudy, S. (2024) · ACM eBooks · doi:10.1145/3674127.3674138 · Cited by 1
Off-Policy Evaluation of Slate Policies under Bayes RiskPreprint
Vlassis, N., Gil, F. A., & Chandrashekar, A. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.02553 · Cited by 1
“…include Shalom et al. (2016) who apply OPE to a large scale real world recommender system that handles purchases from tens of millions of users, Hill et al. (2017) who present a method to optimize a message that is composed of separated widgets (slots) such as title text, offer details, image,…”
BackgroundEfficient Optimal Selection for Composited Advertising Creatives with Tree StructurePreprint
Chen, J., Ge, T., Jiang, G., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.01453 · Cited by 1
“A more efficient method is multivariate bandit (Hill et al. 2017), which models interactions between elements of two different ingredients explicitly by defining the expected reward for each creative as follows: xTc θ = θ 0 + D∑ i=1 θ1i (c) + D∑ j=1 D∑ k=j+1 θ2j,k(c) (1) where θ0 is a common bias,…”
BackgroundMethodInfluentialControl Variates for Slate Off-Policy EvaluationPreprint
Vlassis, N. A., Chandrashekar, A., Amat, F., & Kallus, N. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.07914 · Cited by 10
“…include Sar Shalom et al. (2016) who apply OPE to a large scale real world recommender system that handles purchases from tens of millions of users, Hill et al. (2017) who present a method to optimize a message that is composed of separated widgets (slots) such as title text, offer details, image,…”
BackgroundMarkov Decision Process modeled with Bandits for Sequential Decision Making in Linear-flowPreprint
Zeng, W., & Liu, Y. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.00204 · Cited by 1
“We model the transition probability matrix with contextual Bayesian Bandits [3], use Thompson Sampling (TS) as the exploration strategy, and apply exact Dynamic Programming (DP) to solve the MDP.”
MethodInfluentialSelf-citationModi, A., Dey, D., Agarwal, A., Swaminathan, A., Nushi, B., Andrist, S., & Horvitz, E. (2020) · AAAI Publications (The Association for the Advancement of Artificial Intelligence (AAAI)) · doi:10.1609/aaai.v34i04.5965 · Cited by 1
“This is akin to a greedy hill-climbing strategy, and has been used in many diverse applications of combinatorial optimization as an approximate heuristic, for instance in page layout optimization (Hill et al. 2017).”
MethodReinforcement Learning for Optimal Load Distribution Sequencing in Resource-Sharing SystemPreprint
Wu, F., Cao, Y., & Robertazzi, T. G. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.01899
“Such an algorithm is effective for rapid experimentation because it concentrates testing on actions that have the greatest potential power [13].”
BackgroundSeeker: Real-Time Interactive SearchPreprint
Biswas, A., Pham, T. T., Vogelsong, M., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.13125
“This is a simplifying assumption which serves as a good baseline [6, 12].”
BackgroundSelf-citationA Batched Multi-Armed Bandit Approach to News Headline TestingPreprint
Mao, Y., Chen, M., Wagle, A., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.06256
“, with a multivariate MAB algorithm introduced in [20].”
BackgroundMethodInfluentialAn Opportunistic Bandit Approach for User Interface ExperimentationPreprint
Bouacida, N., Pande, A., & Liu, X. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.11873
“However, researchers [15, 6] outlined several limitations with A/B testing.”
BackgroundMining Scientific Workflows for Anomalous Data TransfersPreprint
Tu, H., Papadimitriou, G., Kiran, M., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.12221
“problems of how to maximize conversions on landing pages or click-through rates on search-engine result pages [40, 41, 42] has gathered interest.”
BackgroundThe Use of Bandit Algorithms in Intelligent Interactive Recommender SystemsPreprint
Wang, Q. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.00161 · Cited by 1
A Map of Bandits for E-commercePreprint
Liu, Y., & Li, L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.00680 · Cited by 12
“Early applications were on optimizing webpage content suggestion such as news articles, advertisement, and marketing messages [4, 5].”
BackgroundSelf-citationDing, W., Tang, H., Feng, J., Yuan, L., Yang, S., Yang, G., Zheng, J., Wang, J., Su, Q., Zheng, D., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.09076 · Cited by 1
Self-citationThe Impact of Batch Learning in Stochastic BanditsPreprint
Provodin, D., Gajane, P., Pechenizkiy, M., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.02071
“As a consequence, it is now frequently a case in practice when the batch size is chosen for the purpose of computational accessibility rather than statistical evidence [Chapelle and Li, 2011, Hill et al., 2017].”
BackgroundNonparametric Bandits Leveraging Informational Externalities to Learn the Demand CurvePreprint
Weaver, I. C., & Kumar, V. (2022) · SSRN Electronic Journal · doi:10.2139/ssrn.4263133 · Cited by 1
“They have many uses beyond pric- ing including advertising (Schwartz et al. 2017), website optimization (Hill et al. 2017, Hauser et al. 2009), recommendation systems (Kawale et al. 2015), and arcade games (Osband et al. 2016).”
BackgroundStackelberg and MAB Models for Decision-Making Process
Almasri, M., Mansour, A., & White, L. (2022) · International Conference on Electrical, Computer, Communications and Mechatronics Engineering (ICECCME) · doi:10.1109/iceccme55909.2022.9988372
“…pages, the composition of a landing page may involve deciding which image to show or color background to display, etc.) [5], internet advertising [6]–[8], etc. MAB has been adopted by several companies, including Adobe, Amazon [5], Microsoft [6], LinkedIn [7], [8], Facebook, Google [9], [10].”
BackgroundMethodAdSEE: Investigating the Impact of Image Style Editing on Advertisement Attractiveness
Jiang, L., Li, C., Chen, H., Gao, X., Zhong, X., Qiu, Y., Ye, S., & Niu, D. (2023) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3580305.3599770 · Cited by 2
“Previous studies in this line of research use the bandit algorithm for the news recommendations [36], page optimization [59], and real online advertising [25].”
Automated web content personalization in the automotive sector: The SEAT case
Esteller-Cucala, M. (2021) · UPCommons institutional repository (Universitat Politècnica de Catalunya) · doi:10.5821/dissertation-2117-360342
Learning to Behave: Reinforcement Learning in Human Contexts
den Hengst, F. (2023) · doi:10.5463/thesis.390
Forecasting Conversion Rate for Real Time CPC Bidding With Target ROAS
Bulut, S., Avcı, E., & Bulut, A. (2023) · IEEE Access · doi:10.1109/access.2023.3338022
“It was used in revenue management [11], web site optimization [12], in online advertising [13], in selective data acquisition for improving machine learning models [14], and more interestingly in designing multi-armed bandits (MABs) [15].”
MethodSequential Monte Carlo bandits
Urteaga, I., & Wiggins, C. H. (2024) · Foundations of Data Science · doi:10.3934/fods.2024005 · Cited by 4
Quantifying customer interactions on ML optimized page layouts
Gupta, N., & Comar, P. M. (2023) · IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) · doi:10.1145/3625007.3627519 · Cited by 2
“In addition to probabilistic ranking models [33], contextual bandits [14] provide a natural framework to learn from user behavior.”
BackgroundPractical Batch Bayesian Sampling Algorithms for Online Adaptive Traffic Experimentation
Zhang, Z., & Yuan, T. T. (2024) · ACM Web Conference (WWW) · doi:10.1145/3589335.3648347
“Due to its simplicity and statistical property in regret, it has attracted a great deal of attention in Amazon[8], eBay[11], Google[14, 15], Meta[6], Microsoft[1, 2], Op-timizely, Yahoo[3], etc.”
BackgroundAlonso, O., & Baeza-Yates, R. (2024) · ACM eBooks · doi:10.1145/3674127.3674128
Searching Personal Collections
Bendersky, M., Metzler, D., Najork, M., & Wang, X. (2024) · ACM eBooks · doi:10.1145/3674127.3674142
Query-driven Search Functionality
Li, L. (2024) · ACM eBooks · doi:10.1145/3674127.3674133
Alonso, O., & Baeza-Yates, R. (2024) · ACM eBooks · doi:10.1145/3674127.3702962
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
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.