Optimal Sequential Exploration: Bandits, Clairvoyants, and Wildcats
Authors:
- 1 June 2013
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 61 (3) , 644-665
Abstract
This paper was motivated by the problem of developing an optimal policy for exploring an oil and gas field in the North Sea. Where should we drill first? Where do we drill next? In this and many other problems, we face a trade-off between earning (e.g., drilling immediately at the sites with maximal expected values) and learning (e.g., drilling at sites that provide valuable information) that may lead to greater earnings in the future. These “sequential exploration problems” resemble a multiarmed bandit problem, but probabilistic dependence plays a key role: outcomes at drilled sites reveal information about neighboring targets. Good exploration policies will take advantage of this information as it is revealed. We develop heuristic policies for sequential exploration problems and complement these heuristics with upper bounds on the performance of an optimal policy. We begin by grouping the targets into clusters of manageable size. The heuristics are derived from a model that treats these clusters as independent. The upper bounds are given by assuming each cluster has perfect information about the results from all other clusters. The analysis relies heavily on results for bandit superprocesses, a generalization of the multiarmed bandit problem. We evaluate the heuristics and bounds using Monte Carlo simulation and, in the North Sea example, we find that the heuristic policies are nearly optimal.Keywords
This publication has 32 references indexed in Scilit:
- The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount RateMathematics of Operations Research, 2011
- Dynamic Portfolio Optimization with Transaction Costs: Heuristics and Dual BoundsManagement Science, 2011
- Bayesian networks for prospect analysis in the North SeaAAPG Bulletin, 2011
- Pathwise Stochastic Optimal ControlSIAM Journal on Control and Optimization, 2007
- Monte Carlo valuation of American optionsMathematical Finance, 2002
- Geometry of the Gass-Saaty parametric cost LP algorithmDiscrete & Computational Geometry, 1990
- Restless bandits: activity allocation in a changing worldJournal of Applied Probability, 1988
- Maintaining LU factors of a general sparse matrixLinear Algebra and its Applications, 1987
- On a sufficient condition for superprocesses due to whittleJournal of Applied Probability, 1982
- The computational algorithm for the parametric objective functionNaval Research Logistics Quarterly, 1955