Multidimensional Binary Search for Contextual Decision-Making
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(d\log(d/\epsilon))$, 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingSimilar Papers 제목 키워드 기반
Contextual Search via Intrinsic Volumes
We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the value of a h…
Decision MakingContextual Search in the Presence of Adversarial Corruptions
We study contextual search, a generalization of binary search in higher dimensions, which captures settings such as feature-based dynamic pricing. Standard formulations of this problem assume that agents act in accordanc…
Learning TheoryHierarchical Modeling of Multidimensional Data in Regularly Decomposed Spaces: Main Principles
The described works have been carried out in the framework of a mid-term study initiated by the Centre Electronique de l'Armement and led by ADERSA, a French company of research under contract. The aim was to study the t…
AttributeDecision MakingManagementBias Mitigation Methods for Binary Classification Decision-Making Systems: Survey and Recommendations
Bias mitigation methods for binary classification decision-making systems have been widely researched due to the ever-growing importance of designing fair machine learning processes that are impartial and do not discrimi…
Binary ClassificationClassificationDecision MakingOn the Expressivity of Multidimensional Markov Reward
We consider the expressivity of Markov rewards in sequential decision making under uncertainty. We view reward functions in Markov Decision Processes (MDPs) as a means to characterize desired behaviors of agents. Assumin…
Decision MakingDecision Making Under UncertaintySequential Decision Making