Allocation of computational resource in economic search (Q2740052)

The authors give the scheme of an abstract economic search and then the search problem is put into a Hilbert space. The authors do this to link the search problem with the incremental approximation theory in a Hilbert space. The following result is presented. NEWLINENEWLINENEWLINEAssume in the search problem that: \((i)\) the reward variables and the search variables are the same with bounded second moments; \((ii)\) the cost function is identically equal to 1; \((iii)\) there is no discounting. Then \(R_{n}=\widetilde R_{n}+O(n^{-1/2})\), where \(\widetilde R_{n}\) is the expected net reward from the incremental search with bound \(n\) on the number of samples, and \(R_{n}\) is the expected net reward from the optimal non-sequential search with the same bound.