Optimal Multiple Stopping Rule for Warm-Starting Sequential Selection
In this paper we present the Warm-starting Dynamic Thresholding algorithm, developed using dynamic programming, for a variant of the standard online selection problem. The problem allows job positions to be either free or already occupied at the beginning of the process. Throughout the selection process, the decision maker interviews one after the other the new candidates and reveals a quality score for each of them. Based on that information, she can (re)assign each job at most once by taking immediate and irrevocable decisions. We relax the hard requirement of the class of dynamic programming algorithms to perfectly know the distribution from which the scores of candidates are drawn, by presenting extensions for the partial and no-information cases, in which the decision maker can learn the underlying score distribution sequentially while interviewing candidates.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processes
Scaling hyperparameter optimisation to very large datasets remains an open problem in the Gaussian process community. This paper focuses on iterative methods, which use linear system solvers, like conjugate gradients, al…
Gaussian ProcessesContinuous-time Optimal Stopping through Deep Reinforcement Learning
Simulation based solvers for optimal stopping problems must discretize the stopping decision. Under classical dynamic programming, a coarse exercise grid with only a few stopping opportunities can materially undervalue t…
Computational EfficiencyReinforcement LearningOptimal Best-Arm Identification under Fixed Confidence with Multiple Optima
We study the problem of best-arm identification in stochastic multi-armed bandits under the fixed-confidence setting, with a particular focus on instances that admit multiple optimal arms. While the Track-and-Stop algori…
Multi-Armed BanditsAdaptive Stopping Rule for Kernel-based Gradient Descent Algorithms
In this paper, we propose an adaptive stopping rule for kernel-based gradient descent (KGD) algorithms. We introduce the empirical effective dimension to quantify the increments of iterations in KGD and derive an impleme…
Learning TheoryImplementability of Honest Multi-Agent Sequential Decision-Making with Dynamic Population
We study the design of decision-making mechanism for resource allocations over a multi-agent system in a dynamic environment. Agents' privately observed preference over resources evolves over time and the population is d…
Decision MakingSequential Decision Making