Multidimensional binary search for contextual decision-making

DOI10.1287/OPRE.2018.1722MaRDI QIDQ4971566zbMATH OpenOpenAlexWikidataFDO

Authors Ilan Lobel, Renato Paes Leme, Adrian Vladu

Publication date 12 October 2020

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.00829

zbMATH Keywords

contextual pricingonline algorithmsonline decision making

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Management decision making, including multiple objectives (90B50)

Abstract: We consider a multidimensional search problem that is motivated by questions in contextual decision-making, such as dynamic pricing and personalized medicine. Nature selects a state from a $d$-dimensional unit ball and then generates a sequence of $d$-dimensional directions. We are given access to the directions, but not access to the state. After receiving a direction, we have to guess the value of the dot product between the state and the direction. Our goal is to minimize the number of times when our guess is more than $epsilon$ away from the true answer. We construct a polynomial time algorithm that we call Projected Volume achieving regret $O(dlog(d/epsilon))$, which is optimal up to a $logd$ factor. The algorithm combines a volume cutting strategy with a new geometric technique that we call cylindrification.

Recommendations

• Contextual search via intrinsic volumes
• Dynamic learning and decision making via basis weight vectors
• Online decision making with high-dimensional covariates
• Dynamic pricing in high-dimensions
• Regret lower bound and optimal algorithm for high-dimensional contextual linear bandit

Cites work

• A simple polynomial-time rescaling algorithm for solving linear programs
• Approximating the centroid is hard
• Faster mixing via average conductance
• Hit-and-run mixes fast
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• On parallel complexity of nonsmooth convex optimization
• Online learning and online convex optimization
• Partitions of mass-distributions and of convex bodies by hyperplanes
• Solving convex programs by random walks

Cited in

(6)

• scientific article; zbMATH DE number 4162311 (Why is no real title available?)
• Dynamic incentive-aware learning: robust pricing in contextual auctions
• Optimal policy for dynamic assortment planning under multinomial logit models
• Contextual search via intrinsic volumes
• Contextual Search in the Presence of Adversarial Corruptions
• Dueling optimization with a monotone adversary

This page was built for publication: Multidimensional binary search for contextual decision-making

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4971566)