Experiment Planning with Function Approximation
Aldo Pacchiano Jonathan N. Lee Emma Brunskill
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.