Optimal Policies for Observing Time Series and Related Restless Bandit Problems

Understand

The trade-off between the cost of acquiring and processing data, and uncertainty due to a lack of data is fundamental in machine learning.

• A basic instance of this trade-off is the problem of deciding when to make noisy and costly observations of a discrete-time Gaussian random walk, so as to minimise the posterior variance plus observation costs.
• We present the first proof that a simple policy, which observes when the posterior variance exceeds a threshold, is optimal for this problem.
• The proof generalises to a wide range of cost functions other than the posterior variance.