Optimal Choice From Known Rewards With Uncertain Response

Consider a random permutation of a finite number $n$ of known elements representing rewards. These rewards will be made or not made with certain known probabilities. At any stage a reward made can be accepted or rejected, there is no recall and only one reward can be accepted. The problem is to maximize the expected reward accepted. We propose a computationally feasible approximation to the solution of the dynamic programming equation of the problem. Estimates of the error of the approximation are given recursively as well as in explicit form. Recursively the error of the approximation at any stage of the game is obtained in terms of the approximation and its error estimate at the following stage. In numerical examples the goodness of the approximation and its error estimates are found by comparison with the optimal solution.