An Interplanetary Diner
An Interplanetary Diner
Optimal Stopping
Optimal Stopping
Exploring the optimal time to act in order to maximize reward.
June 22, 2017—Richard Hayes
On your way out of Mars’s orbit, after a quick visit to your alien cousin’s fidget-spinner farm, you stop at a small fast-food restaurant on Phobos to purchase one of the galaxy’s most delicious burgers. You’ve been here many times before and know the owner, a computational burger scientist, has very strict ordering rules; when it’s time for a customer to order, they’re presented with a parade of burgers of varying quality, and must answer “yes” or “no” on the spot. To you, a well-trained burger classifier, a burger’s quality is immediately identifiable. However, you can only determine the quality of a burger when it’s directly in front of you, and if you reject a burger, it’s cast into a four-dimensional trash compacter from IKEA, never to be seen again.
Graph a list of 1,000 random integers less than 100 that represent burger quality levels:
In[]:=
burgers=Table[RandomInteger[{1,100}],{i,1,1000},{j,1,1000}];BarChart[Take[burgers[[1]],15]]
Out[]=
The burgers’ qualities vary randomly. It’s unclear when to ideally place an order. Placing a random order proves to be a weak strategy.
We subtract the best burger in each list from the one we choose randomly:
In[]:=
proximity=Table[Max[burgers[[i]]]-burgers[[i]][[t]],{t,1,1000},{i,1,1000}];
In[]:=
BarChart[Take[Map[Total[#]/Length[#]&,proximity],50],PlotLabel"Adv stopping cost vs stopping time"]
Out[]=
The Theoretical Ideal Stopping Time
The Theoretical Ideal Stopping Time
Verifying the Theory with Experimentation
Verifying the Theory with Experimentation
FURTHER EXPLORATIONS
Optimal Stopping Theory
The Secretary Problem
Bellman Equations
The Odds-Algorithm
AUTHORSHIP INFORMATION
Richard Hayes
6/22/17
RESOURCES