Suppose you've taken up the game of squash and want to play at a health club. The club has two payment plans: $400 for a yearly membership or $20 for each use of the squash court. You'd like to play several times a week, but you're prone to injury and know you won't be able to play anymore if you get hurt. An oracle would be able to predict if and when you get injured and thus determine whether it would be more cost-effective to buy the yearly membership or pay for each use of the court. You are not clairvoyant, however, so you wish to devise a strategy for minimizing your "regret ratio"--the amount you spend divided by the amount that the oracle would have spent.
If you decide to buy a yearly membership right from the start and then get injured on your first day on the court, your regret ratio would be 20--the $400 you spent divided by the $20 that the oracle would have spent. If you decide to pay for each use for an entire year and you play 100 times and then get injured, your regret ratio would be 5--the $2,000 you spent divided by the $400 that the oracle would have spent. Is there a way to keep your regret ratio below 2 no matter when you get hurt?
This article was originally published with the title Bounded Regrets.