Optimal selection of information with restricted storage capacity
Luc Pronzato · 2002
We consider the situation where n items have to be selected among a series of N presented sequentially, the information contained in each item being random. The problem is to get a collection of n items with maximal information. We consider the case where the information is additive, and thus need to maximize the sum of n independently identically distributed random variables x/sub k/ observed sequentially in a sequence of length N. This is a stochastic dynamic-programming problem, the optimal solution of which is derived when the distribution of the x/sub k/s is known. The asymptotic behaviour of this optimal solution (when N tends to infinity with n fixed) is considered. A (forced) certainty-equivalence policy is proposed for the case where the distribution is unknown and estimated on-line.