On Learning the Optimal Waiting Time
ALT, (2014)Abstract
Consider the problem of learning how long to wait for a bus before walking, experimenting each day and assuming
that the bus arrival times are independent and identically distributed random variables with an unknown distribution.
Similar uncertain optimal stopping problems arise when devising power-saving strategies, e.g., learning the optimal disk spin-down time for
mobile computers, or speeding up certain types of satisficing search procedures by switching from
a potentially fast search method that is unreliable, to one that is reliable, but slower.
Formally, the problem can be described as a repeated game. In each round of the game an agent is waiting for an event to occur.
If the event occurs while the agent is waiting, the agent suffers a loss that is the sum of the event's ``arrival time'' and some
fixed loss. If the agents decides to give up waiting before the event occurs, he suffers a loss that is the sum of the waiting time and some other
fixed loss. It is assumed that the arrival times are independent random quantities with the same distribution, which is unknown, while the agent knows the
loss associated with each outcome. Two versions of the game are considered. In the full information case the agent
observes the arrival times regardless of its actions, while
in the partial information case the arrival time is observed only if it does not exceed the waiting time. After
some general structural observations about the problem,
we present a number of algorithms for both cases that learn the optimal weighting time with nearly matching
minimax upper and lower bounds on their regret.