next up previous contents
Next: About this document Up: Stochastic Dynamic Programming Previous: Uncertain States

``Linear'' decision making

. Many decision problems (and some of the most frustrating ones), involve choosing one out of a number of choices where future choices are uncertain. For example, when getting (or not getting!) a series of job offers, you may have to make a decision on a job before knowing if another job is going to be offered to you. Here is a simplification of these types of problems:

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 tex2html_wrap_inline1254 . 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 tex2html_wrap_inline1266 and tex2html_wrap_inline1268 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).

Michael A. Trick
Sun Jun 14 13:05:46 EDT 1998