Suppose we are trying to find a parking space near a restaurant. This restaurant is on a long stretch of road, and our goal is to park as close to the restaurant as possible. There are T spaces leading up to the restaurant, one spot right in front of the restaurant, and T after the restaurant as follows:
Each spot can either be full (with probability, say, .9) or empty (.1). As we pass a spot, we need to make a decision to take the spot or try for another (hopefully better) spot. The value for parking in spot t is . If we do not get a spot, then we slink away in embarrasment at large cost M. What is our optimal decision rule?
We can have a stage for each spot t. The states in each stage are either e (for empty) or o (for occupied). The decision is whether to park in the spot or not (cannot if state is o). If we let and be the values for each state, then we have:
In general, the optimal rule will look something like, take the first empty spot on or after spot t (where t will be negative).