On Optimal Ordering in the Optimal Stopping Problem
Shipra Agrawal, Jay Sethuraman, Xingyu Zhang
Abstract
Consider a player who can probe a sequence of n independent random variables X1, . . . , Xn with known distributions. After observing (the realized value of) Xi, the player needs to decide whether to stop and earn reward Xi, or reject the reward and probe the next variable Xi+1. The goal is to maximize the expected reward at the stopping time. This is an instance of the optimal stopping problem, which is a fundamental problem studied from many different aspects in mathematics, statistics, and computer science, and has found a wide variety of applications in sequential decision making and mechanism design.
Topics & Concepts
Optimal stoppingSequence (biology)Variety (cybernetics)Random variableComputer scienceValue (mathematics)Variable (mathematics)Stopping timeExpected valueMathematical optimizationMathematicsArtificial intelligenceStatisticsMachine learningBiologyGeneticsMathematical analysisOptimization and Search ProblemsAuction Theory and ApplicationsAdvanced Bandit Algorithms Research