Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Contextual Linear Optimization with Bandit Feedback
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.
Adapts end-to-end induced empirical risk minimization (IERM) and SPO+ surrogates to contextual linear optimization with bandit (one-realized-cost) feedback, with fast-rate regret bounds under policy misspecification and simulated shortest-path experiments.
Problem
Contextual linear optimization where only the realized cost of a historical decision (a single projection Z^T Y of the random cost vector) is observed, rather than the full cost vector, so standard full-feedback CLO methods do not apply.
Approach
Identify the value of any policy via doubly-robust/direct/inverse-spectral-weighting score functions built from nuisance estimates, then run induced ERM over the plug-in policy class on these scores, using cross-fitting and SPO+ surrogates; derive a margin-dependent fast-rate regret bound allowing misspecification.
Key results
- SPO+ with DM score achieves about 0.16% relative regret at n=1600 versus 0.35% for ETO under a well-specified random logging setting.
- Under misspecified policy class, end-to-end SPO+ methods outperform ETO (e.g., 7.47% vs 8.34% at n=1600 for degree-4 misspecification in the policy class with well-specified nuisance), but advantage vanishes when the nuisance model is misspecified.
- Naive discrete-action extensions perform far worse (about 3.5% to 15% relative regret), showing the value of exploiting linear structure.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace ETO with end-to-end IERM using SPO+ DM | 5×5 stochastic shortest path with correctly specified F and FN · Random logging policy, n=400/1000/1600 | average relative regret ratio: 3.34% -> 2.30%; 0.74% -> 0.36%; 0.35% -> 0.16% | Helped |
| Use lambda regularization instead of the doubly robust pseudo-inverse (ablation) | SPO+ DR on the 5×5 stochastic shortest path · Random logging policy, correctly specified F and FN, n=400/1000/1600 | average relative regret ratio: 2.47% -> 2.23%; 0.59% -> 0.40%; 0.32% -> 0.18% | Helped |
| Clip small eigenvalues instead of using the doubly robust pseudo-inverse (ablation) | SPO+ DR on the 5×5 stochastic shortest path · Random logging policy, correctly specified F and FN, n=400/1000/1600 | average relative regret ratio: 2.47% -> 2.29%; 0.59% -> 0.44%; 0.32% -> 0.20% | Helped |
| Use the doubly robust pseudo-inverse score instead of the direct-method score (ablation) | SPO+ IERM on the 5×5 stochastic shortest path · Random logging policy, correctly specified F and FN, n=400/1000/1600 | average relative regret ratio: 2.30% -> 2.47%; 0.36% -> 0.59%; 0.16% -> 0.32% | Hurt |
| Treat feasible paths as discrete actions rather than leveraging linear cost structure | ETO and SPO+ methods on the 5×5 stochastic shortest path · Random logging policy, n=400/1000/1600 | average relative regret ratio: ETO 3.34% vs Naive ETO 15.03%; SPO+ DM 2.30% vs Naive SPO+ DM 15.05% | Hurt |
| Use end-to-end SPO+ DM instead of ETO with degree-2 misspecified F and well-specified FN | 5×5 stochastic shortest path · Random logging policy, n=400/1000/1600 | mean relative regret ratio: 11.04% -> 2.81%; 9.14% -> 0.80%; 8.34% -> 0.54% | Helped |
| Use end-to-end SPO+ DM instead of ETO with degree-4 misspecified F and well-specified FN | 5×5 stochastic shortest path · Random logging policy, n=400/1000/1600 | mean relative regret ratio: 12.35% -> 4.06%; 11.42% -> 2.21%; 10.39% -> 2.06% | Helped |
| Misspecify the nuisance model FN while retaining a well-specified policy-inducing model F (ablation) | SPO+ IERM on the 5×5 stochastic shortest path · Random logging policy, n=400 | mean relative regret ratio: SPO+ DM: 2.30% -> 10.01% (degree 2), 2.30% -> 12.51% (degree 4) | Hurt |
| Use DR score rather than DM when the nuisance model is misspecified (ablation) | SPO+ IERM on the 5×5 stochastic shortest path · Random logging policy with misspecified nuisance model FN | mean relative regret ratio | Mixed |
| Increase training data size | All evaluated methods on the 5×5 stochastic shortest path · Random logging policy | average relative regret ratio | Helped |
Surprising findings
- The doubly robust score with pseudo-inverse performs worst among SPO+ variants due to variance inflation, while the direct method performs best.
- End-to-end advantage over ETO disappears when the nuisance model is misspecified.
Limitations
- Primarily parametric induced policy classes; nonparametric classes left for future work.
- Focuses mainly on SPO+ surrogate; other surrogate losses not explored.
- End-to-end approach sensitive to nuisance model misspecification.
Experimental setup
Datasets: simulated stochastic shortest path data (5x5 grid, 40 edges, 70 feasible paths)
Benchmarks: simulated stochastic shortest path problem
Metrics: average relative regret ratio vs expected cost of optimal po
Baselines: ETO Naive ETO Naive SPO+
Builds on: SPO+ (Elmachtoub and Grigas) induced empirical risk minimization (Elmachtoub et al. / Hu et al.) doubly robust offline contextual bandit learning (Athey and Wager / Dudik et al. cross-fitting (Chernozhukov et al.)
Closest papers by meaning
- Breaking the $\sqrtT$ Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits (ICML 2022 · similarity 0.88)
- Conservative Contextual Bandits: Beyond Linear Representations (ICLR 2025 · similarity 0.88)
- Mixed-Effects Contextual Bandits (AAAI 2024 · similarity 0.87)
- Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach (ICML 2025 · similarity 0.87)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.87)
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.87)
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.