Optimal stopping in urn models with payoff depending on maximal observed element

An urn contains N balls, labelled 1,...,N. Optimal stopping rules are considered for payoff functions f(k, m) where f(k, m) is the reward when stopping after k draws, and the largest number seen by then is m. f(k, m) is assumed nondecreasing im for each k. We show: (i) For any horizon n [less-than-or-equals, slant] N, under optimal stopping, sampling without replacement yields a larger expected value than sampling with replacement. (ii) A sufficient condition, both when sampling with or without replacement, for the optimal stopping rule to be of the form t =inf{k:Mk [greater-or-equal, slanted]qk} for some constants qk, where Mk is the maximal label [Delta](k, m) = f(k, m + 1) - f(k, m) be nonincreasing in k for each m. Better sufficient conditions are given, and several e such as reward minus cost of sampling, or discounted rewards, are considered. Some limiting results, as N -->[infinity], and prophet inequality considerations are included for the example where the payoff is reward minus cost of sampling.