Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Contextual Online Decision Making with Infinite-Dimensional Functional Regression
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.
Proposes an infinite-dimensional functional regression oracle for contextual CDFs built from CDF basis functions, and an inverse-gap-weighting bandit-style algorithm whose regret depends on the eigendecay rate of the design integral operator.
Problem
Contextual sequential decision-making where utility is a functional of the full outcome distribution (CDF), so the regression target is infinite-dimensional and standard linear bandit methods give infinite regret.
Approach
Model each contextual CDF as a combination of context-dependent CDF basis functions, estimate the coefficient function via a truncated pseudo-inverse of a data-dependent design integral operator (truncated by eigenvalues at n^{-2/(γ+2)}), and reduce decision-making to a contextual bandit with epoch-wise IGW policies; regret depends on polynomial eigendecay parameter γ.
Key results
- Regret bound Õ(T^{(3γ+2)/(2(γ+2))}) under γ-dominating polynomial eigendecay, recovering Õ(√T) as γ→0 and exponential decay cases.
- Under no knowledge of γ (γ=1), the regret bound becomes Õ(T^{5/6}).
- Functional regression oracle is called only O(log T) times over the horizon.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use γ=0 for finite-dimensional problems | Proposed algorithm · Finite-dimensional contextual decision making | expected regret: \tilde{\cO}(T^{1/2}) | Helped |
| Set γ=1 when the eigendecay order is unknown | Proposed algorithm · Stochastic contextual decision making with unknown eigendecay order | expected regret: T^{\frac{5}{6}} | Helped |
| Use γ\searrow 0 for exponentially decaying eigenvalues | Proposed algorithm · Contextual decision making with exponentially decaying eigenvalues | expected regret: \tilde{\cO}\rbr{\sqrt{T}} | Helped |
Limitations
- Regret rate T^{(3γ+2)/(2(γ+2))} is worse than √T unless γ→0; minimax optimality of γ-dependence is open.
- Linear in the basis representation; nonlinear relationships between CDF and basis not handled.
- Requires Lipschitz objective functional and eigendecay assumption on the integral operator family.
Experimental setup
Metrics: utility regret
Baselines: linear contextual bandits
Builds on: inverse gap weighting linear contextual bandits
Closest papers by meaning
- Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles (ICML 2020 · similarity 0.92)
- Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.89)
- Contextual Bandits with Online Neural Regression (ICLR 2024 · similarity 0.88)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.88)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.88)
- Mixed-Effects Contextual Bandits (AAAI 2024 · similarity 0.88)
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.