An Efficient Bandit Algorithm for Realtime Multivariate Optimization

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. 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.

KDD'17 Audience Appreciation Award

References in corpus (5)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Adaptive, Personalized Diversity for Visual Discovery
• Diversifying Music Recommendations

Cited by in corpus (28)

• Deep reinforcement learning for search, recommendation, and online advertising: a survey
• LACO: A Latency-Driven Network Slicing Orchestration in Beyond-5G Networks
• A Tutorial on Thompson Sampling
• Beyond Preferences in AI Alignment
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
• Automated Creative Optimization for E-Commerce Advertising
• Weak Signal Asymptotics for Sequentially Randomized Experiments
• Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learning
• Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries
• Online Controlled Experiments for Personalised e-Commerce Strategies: Design, Challenges, and Pitfalls
• Accelerated learning from recommender systems using multi-armed bandit
• Markov Decision Process modeled with Bandits for Sequential Decision Making in Linear-flow
• Off-Policy Evaluation of Slate Policies under Bayes Risk
• Control Variates for Slate Off-Policy Evaluation
• Linear Contextual Bandits with Hybrid Payoff: Revisited
• Efficient Optimal Selection for Composited Advertising Creatives with Tree Structure
• Efficient Multivariate Bandit Algorithm with Path Planning
• Searching Personal Collections
• AdSEE: Investigating the Impact of Image Style Editing on Advertisement Attractiveness
• Mining Scientific Workflows for Anomalous Data Transfers
• The Impact of Batch Learning in Stochastic Bandits
• A Batched Multi-Armed Bandit Approach to News Headline Testing
• The Use of Bandit Algorithms in Intelligent Interactive Recommender Systems
• Seeker: Real-Time Interactive Search
• An Opportunistic Bandit Approach for User Interface Experimentation
• Reinforcement Learning for Optimal Load Distribution Sequencing in Resource-Sharing System
• A Map of Bandits for E-commerce
• PASTO: Strategic Parameter Optimization in Recommendation Systems -- Probabilistic is Better than Deterministic