# Experiment Planning with Function Approximation

arXiv: https://arxiv.org/abs/2401.05193 · HTML: https://mlsanity.com/paper/2401.05193/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 54 references that are in the map.
- First posted on arXiv 10 Jan 2024.

## Builds on (most cited first, 30 of 33)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Deep Reinforcement Learning for Dialogue Generation](https://mlsanity.com/paper/1606.01541/) (2016)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL](https://mlsanity.com/paper/2012.08005/) (2020)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Online Model Selection for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2011.09750/) (2020)
- [On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL](https://mlsanity.com/paper/2206.10770/) (2022)
- [Understanding the Eluder Dimension](https://mlsanity.com/paper/2104.06970/) (2021)
- [Design of Experiments for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2107.09912/) (2021)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [Bounded Regret for Finite-Armed Structured Bandits](https://mlsanity.com/paper/1411.2919/) (2014)
- [Safe Exploration for Efficient Policy Evaluation and Comparison](https://mlsanity.com/paper/2202.13234/) (2022)

## Built on by (most cited first, 5 of 5)

- [Second Order Bounds for Contextual Bandits with Function Approximation](https://mlsanity.com/paper/2409.16197/) (2024)
- [Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions](https://mlsanity.com/paper/2601.15353/) (2026)
- [Active Few-Shot Fine-Tuning](https://mlsanity.com/paper/2402.15441/) (2024)
- [The Fallacy of Minimizing Cumulative Regret in the Sequential Task Setting](https://mlsanity.com/paper/2403.10946/) (2024)
- [Bayesian Online Model Selection](https://mlsanity.com/paper/2602.17958/) (2026)

## Abstract (arXiv)

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.