# An Efficient Bandit Algorithm for Realtime Multivariate Optimization

arXiv: https://arxiv.org/abs/1810.09558 · HTML: https://mlsanity.com/paper/1810.09558/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2018.

## Built on by (most cited first, 30 of 34)

- [POEM: Out-of-Distribution Detection with Posterior Sampling](https://mlsanity.com/paper/2206.13687/) (2022)
- [Beyond Preferences in AI Alignment](https://mlsanity.com/paper/2408.16984/) (2024)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [AgentA/B: Automated and Scalable Web A/BTesting with Interactive LLM Agents](https://mlsanity.com/paper/2504.09723/) (2025)
- [Weak Signal Asymptotics for Sequentially Randomized Experiments](https://mlsanity.com/paper/2101.09855/) (2021)
- [Control Variates for Slate Off-Policy Evaluation](https://mlsanity.com/paper/2106.07914/) (2021)
- [A Map of Bandits for E-commerce](https://mlsanity.com/paper/2107.00680/) (2021)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Efficient Optimal Selection for Composited Advertising Creatives with Tree Structure](https://mlsanity.com/paper/2103.01453/) (2021)
- [Linear Contextual Bandits with Hybrid Payoff: Revisited](https://mlsanity.com/paper/2406.10131/) (2024)
- [Compass: SLO-aware Query Planner for Compound AI Serving at Scale](https://mlsanity.com/paper/2504.16397/) (2025)
- [Theta-Resonance: A Single-Step Reinforcement Learning Method for Design Space Exploration](https://mlsanity.com/paper/2211.02052/) (2022)
- [AxiomVision: Accuracy-Guaranteed Adaptive Visual Model Selection for Perspective-Aware Video Analytics](https://mlsanity.com/paper/2407.20124/) (2024)
- [The Impact of Batch Learning in Stochastic Linear Bandits](https://mlsanity.com/paper/2202.06657/) (2022)
- [Off-Policy Evaluation of Slate Policies under Bayes Risk](https://mlsanity.com/paper/2101.02553/) (2021)
- [A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity](https://mlsanity.com/paper/2307.15154/) (2023)
- [Cooperative Multi-Agent Deep Reinforcement Learning in Content Ranking Optimization](https://mlsanity.com/paper/2408.04251/) (2024)
- [Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback](https://mlsanity.com/paper/2506.13163/) (2025)
- [Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning](https://mlsanity.com/paper/2011.14266/) (2020)
- [Page-level Optimization of e-Commerce Item Recommendations](https://mlsanity.com/paper/2108.05891/) (2021)
- [The Impact of Batch Learning in Stochastic Bandits](https://mlsanity.com/paper/2111.02071/) (2021)
- [Practical Batch Bayesian Sampling Algorithms for Online Adaptive Traffic Experimentation](https://mlsanity.com/paper/2305.14704/) (2023)
- [GenSERP: Large Language Models for Whole Page Presentation](https://mlsanity.com/paper/2402.14301/) (2024)
- [The Use of Bandit Algorithms in Intelligent Interactive Recommender Systems](https://mlsanity.com/paper/2107.00161/) (2021)
- [Markov Decision Process modeled with Bandits for Sequential Decision Making in Linear-flow](https://mlsanity.com/paper/2107.00204/) (2021)
- [PASTO: Strategic Parameter Optimization in Recommendation Systems -- Probabilistic is Better than Deterministic](https://mlsanity.com/paper/2108.09076/) (2021)
- [Recommender Systems: A Primer](https://mlsanity.com/paper/2302.02579/) (2023)
- [Rapid and Scalable Bayesian AB Testing](https://mlsanity.com/paper/2307.14628/) (2023)
- [AdSEE: Investigating the Impact of Image Style Editing on Advertisement Attractiveness](https://mlsanity.com/paper/2309.08159/) (2023)
- [Improving Reward-Conditioned Policies for Multi-Armed Bandits using Normalized Weight Functions](https://mlsanity.com/paper/2406.10795/) (2024)

## Abstract (arXiv)

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. Here we focus on multivariate optimization of interactive web pages. We formulate an approach where the possible interactions between different components of the page are modeled explicitly. We apply bandit methodology to explore the layout space efficiently and use hill-climbing to select optimal content in realtime. Our algorithm also extends to contextualization and personalization of layout selection. Simulation results show the suitability of our approach to large decision spaces with strong interactions between content. We further apply our algorithm to optimize a message that promotes adoption of an Amazon service. After only a single week of online optimization, we saw a 21% conversion increase compared to the median layout. Our technique is currently being deployed to optimize content across several locations at Amazon.com.