Experiment Planning with Function Approximation
This addresses the need for efficient experiment planning in distributed or human-in-the-loop systems, though it is incremental as it extends linear reward results to more complex models.
The paper tackles the problem of designing non-adaptive data collection policies for contextual bandits when adaptive algorithms are impractical, proposing two strategies for function approximation that achieve optimality guarantees based on eluder dimension and competitive rates for small action sets.
We study the problem of experiment planning with function approximation in contextual bandit problems. In settings where there is a significant overhead to deploying adaptive algorithms -- for example, when the execution of the data collection policies is required to be distributed, or a human in the loop is needed to implement these policies -- producing in advance a set of policies for data collection is paramount. We study the setting where a large dataset of contexts but not rewards is available and may be used by the learner to design an effective data collection strategy. Although when rewards are linear this problem has been well studied, results are still missing for more complex reward models. In this work we propose two experiment planning strategies compatible with function approximation. The first is an eluder planning and sampling procedure that can recover optimality guarantees depending on the eluder dimension of the reward function class. For the second, we show that a uniform sampler achieves competitive optimality rates in the setting where the number of actions is small. We finalize our results introducing a statistical gap fleshing out the fundamental differences between planning and adaptive learning and provide results for planning with model selection.