David C. Parkes and Lloyd G. Greenwald
We present a flexible procedure for a resource-bounded agent to allocate limited computational resources to on-line problem solving. Our APPROXIMATE AND COMPENSATE methodology extends a well-known greedy time-slicing approach to conditions in which performance profiles may be non-concave and there is uncertainty in the environment and/or problem-solving procedures of an agent. With this method, the agent first approximates problem-solving performance and problem parameters with standard parameterized models. Second, the agent computes a risk-management factor that compensates for the risk inherent in the approximation. The risk-management factor represents a mean-variance tradeoff that may be derived optimally off-line using any available information. Theoretical and experimental results demonstrate that APPROXIMATE AND COMPENSATE extends existing methods to new problems and expands the practical application of meta-deliberation.