Research map / Learning theory and algorithms / Prediction and decision losses
The Non-linear $F$-Design and Applications to Interactive Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalizes G-optimal experimental design to non-linear function classes via an F-condition number, with computable bounds, a greedy argmax-oracle algorithm, and drop-in applications to confidence bands, contextual bandits, model-free RL, and active learning.
Problem
Experimental design for non-linear function classes, where classical G-optimal design theory (closed forms, sharp bounds) only applies to linear classes and local asymptotic criteria are used for non-linear ones.
Approach
Defines the F-condition number, a ratio of squared error at a query point to the design-averaged squared error over the difference class, which reduces to the G-optimal design criterion in the linear case; it bounds the optimal value via covering numbers and eluder dimension and yields a greedy argmax-oracle design algorithm.
Key results
- F-condition number of the optimal design equals d for linear classes and is bounded by O(N(DF, ||.||_inf, eps)) for general bounded classes (Theorem 3.2).
- Greedy Algorithm 1 returns a design with F-condition number O(d log(1/eps0)(log d + log log(1/eps0))) where d is the eluder dimension (Theorem 4.2).
- Cheating code example shows the optimal F-condition number can be at most 4k while the eluder dimension is at least 2k-1, an exponential gap.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the optimal F-design to guide exploration | Contextual bandits with realizability and infinite actions · Contextual Bandit | PAC regret: O(\sqrt{V^*\log |F|/T}) | Helped |
| Replace G-design with F-design for exploration | Model-free RL with realizability, Bellman rank, and infinite actions · Model-free RL | PAC regret: O(\log(|F|T)\sqrt{br \cdot V^*H/T}) | Helped |
| Use F-design for exploration | Model-free RL with Q⋆ smooth over actions · Model-free RL | PAC regret | Helped |
| Use F-design for exploration | Model-free RL with value-based Linear Quadratic Regulators · LQR | sample complexity | Helped |
| Use F-design to select queries | Pool-based active learning · Active Learning | query complexity: O(V^*(F, U; 0) \log(|F|/\delta)) | Helped |
| Use F-design for simultaneous confidence bands | Non-linear regression · Simultaneous Confidence Bands | prediction error: O(\sqrt{V(\rho_V, x)(\epsilon_0 + \|\hat f - f^*\|^2_{\rho_V,2})}) | Mixed |
| Apply the F-design bound through an L2 estimation error bound | Non-contextual Lipschitz bandits · Lipschitz bandit | PAC regret rate: T^{(2d+1)/(2d+2)}; T^{(d+1)/(d+2)} | Hurt |
Surprising findings
- The greedy argmax-oracle design can be exponentially suboptimal relative to the optimal F-condition number on the cheating code example, and the bound in Theorem 4.2 is unimprovable for a broad class of convex-hull-based algorithms.
Limitations
- Computing the optimal F-design in a way that scales sublinearly in the design space size is open; the argmax-based algorithms cannot achieve this in general.
- Bellman completeness assumption is needed for the non-linear RL result and its removal is open.
- Simultaneous confidence band rates for linear classes are worse than i.i.d. bounds by a factor of sqrt(d), and optimality is unresolved.
Experimental setup
Metrics: F-condition number PAC regret query complexity simultaneous confidence band width
Baselines: G-optimal design eluder dimension based methods OLIVE TS2-D Gentile et al. 2022 active learning
Builds on: G-optimal design eluder dimension OLIVE TS2-D Bellman rank
Closest papers by meaning
- Bilinear Classes: A Structural Framework for Provable Generalization in RL (ICML 2021 · similarity 0.85)
- Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient (ICLR 2023 · similarity 0.85)
- Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability (NeurIPS 2024 · similarity 0.84)
- FunBO: Discovering Acquisition Functions for Bayesian Optimization with FunSearch (ICML 2025 · similarity 0.84)
- Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm (NeurIPS 2024 · similarity 0.83)
- Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.