Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce finite-action contextual bandits to an online regression oracle | MAIN · Realizable contextual bandits with adversarially chosen contexts | regret: 4√(KT·RegSquare) + 8√(KT log(2δ^{-1})) | Helped |
| Use the Vovk-Azoury-Warmuth regression oracle | MAIN · Low-dimensional linear contextual bandits | regret: O(√(dKT log(T/d))) versus O(√(dT log^3(KT))) | Mixed |
| Use Online Gradient Descent as the regression oracle | MAIN · High-dimensional linear contextual bandits | regret: O(K^{1/2}·T^{3/4}) | Mixed |
| Use the general GLMtron variant | MAIN · Generalized linear contextual bandits | regret: O(T^{3/4}) | Helped |
| Use second-order GLMtron and assume σ' ≥ cσ > 0 | MAIN · Generalized linear contextual bandits | regret: O(√(dKT log T/cσ^2)) | Helped |
| Adapt the regression oracle to metric entropy using a refining empirical cover | MAIN · Realizable contextual bandits with entropy growth ε^{-p} | regret: Õ((KT)^{(1+p)/(2+p)} + √(K^2T log(δ^{-1}))) | Helped |
| Allow ε-approximate realizability | MAIN · Misspecified contextual bandits with finite actions | pseudoregret: + ε·5√K T | Hurt |
| Allow losses to be ε-close to a class function under an adaptive adversary | MAIN · Misspecified contextual bandits with adaptive adversary | pseudoregret: + ε·√(2K)T | Hurt |
| Extend the reduction to actions in the d_A-dimensional unit ℓ_2 ball | INFINITE · Contextual bandits with continuous actions | regret: 18√(d_A T·RegSquare) + 90√(d_A T log(δ^{-1})) | Helped |
| Require logarithmic dependence on class size for gap-dependent regret | Any contextual bandit algorithm · Finite two-arm classes with uniform gap 1/4 | expected regret: ≥ 1/16√T | Hurt |
| Use an online regression oracle rather than an offline classification oracle | Oracle-based contextual bandit learning · Realizable contextual bandits | memory requirements | Helped |
Closest papers by meaning
- Practical Contextual Bandits with Regression Oracles (ICML 2018 · similarity 0.95)
- Contextual Online Decision Making with Infinite-Dimensional Functional Regression (ICML 2025 · similarity 0.92)
- Contextual Bandits with Online Neural Regression (ICLR 2024 · similarity 0.91)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.90)
- Efficient Contextual Bandits with Uninformed Feedback Graphs (ICML 2024 · similarity 0.90)
- Diffusion Models Meet Contextual Bandits (NeurIPS 2025 · similarity 0.89)
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.