# Multidimensional Binary Search for Contextual Decision-Making

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2016.

## Built on by (most cited first, 27 of 27)

- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Optimal Design for Reward Modeling in RLHF](https://mlsanity.com/paper/2410.17055/) (2024)
- [Logarithmic Regret in Feature-based Dynamic Pricing](https://mlsanity.com/paper/2102.10221/) (2021)
- [Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise](https://mlsanity.com/paper/2201.11341/) (2022)
- [Contextual Inverse Optimization: Offline and Online Learning](https://mlsanity.com/paper/2106.14015/) (2021)
- [Dynamic pricing and assortment under a contextual MNL demand](https://mlsanity.com/paper/2110.10018/) (2021)
- [Contextual Recommendations and Low-Regret Cutting-Plane Algorithms](https://mlsanity.com/paper/2106.04819/) (2021)
- [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024)
- [Dueling Optimization with a Monotone Adversary](https://mlsanity.com/paper/2311.11185/) (2023)
- [Fairness-aware Online Price Discrimination with Nonparametric Demand Models](https://mlsanity.com/paper/2111.08221/) (2021)
- [Learning to Price Against a Moving Target](https://mlsanity.com/paper/2106.04689/) (2021)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization](https://mlsanity.com/paper/2206.07528/) (2022)
- [Utility Fairness in Contextual Dynamic Pricing with Demand Learning](https://mlsanity.com/paper/2311.16528/) (2023)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [Learning from a Learning User for Optimal Recommendations](https://mlsanity.com/paper/2202.01879/) (2022)
- [Efficient Online Inverse Optimization with O(d) Regret](https://mlsanity.com/paper/2609.13440/) (2026)
- [Nonparametric Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12904/) (2026)
- [Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand](https://mlsanity.com/paper/2605.05609/) (2026)
- [Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights](https://mlsanity.com/paper/2609.26978/) (2026)
- [Active Learning for Contextual Search with Binary Feedbacks](https://mlsanity.com/paper/2110.01072/) (2021)
- [Margin-Independent Online Multiclass Learning via Convex Geometry](https://mlsanity.com/paper/2111.08057/) (2021)
- [Structured Dynamic Pricing: Optimal Regret in a Global Shrinkage Model](https://mlsanity.com/paper/2303.15652/) (2023)
- [Fast Interactive Search with a Scale-Free Comparison Oracle](https://mlsanity.com/paper/2306.01814/) (2023)
- [Contextual Dynamic Pricing with Heterogeneous Buyers](https://mlsanity.com/paper/2512.09513/) (2025)
- [Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time](https://mlsanity.com/paper/2605.08290/) (2026)
- [Privacy Preserving Reinforcement Learning with One-Sided Feedback](https://mlsanity.com/paper/2605.18246/) (2026)

## Abstract (arXiv)

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 ε away from the true answer. We construct a polynomial time algorithm that we call Projected Volume achieving regret O(dlog(d/ε)), which is optimal up to a log d factor. The algorithm combines a volume cutting strategy with a new geometric technique that we call cylindrification.