Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Oracle-efficient contextual bandits · 0 citations (OpenAlex)

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 CoRectron, a projection-free second-order perceptron-style algorithm for contextual recommendation (online inverse linear optimization) that achieves O(d log T) regret, is robust to suboptimal feedback without multiple learners, and extends to kernelized Hilbert-space settings.

Problem

Contextual recommendation from observed user actions (not rewards): achieving logarithmic regret efficiently, avoiding costly Mahalanobis projections required by prior Online Newton Step methods, and staying robust to suboptimal action feedback.

Approach

Exploit the improperness (scale invariance) of recommendations so predictions need no norm constraint; use a projection-free second-order update A_t^{-1} built from the Gram of cumulative residuals, with a sign condition from argmax optimality giving a cumulative-potential bound and a log-determinant regret bound that also holds under suboptimal feedback.

Key results

• Theory: regret bound R_T(u) <= B H_T + ||u|| sqrt(lambda H_T) with H_T = O(d log T) in finite dimensions, matching the ONS-based O(d log T) bound.
• Total time complexity O(T d^2 + sum tau_opt(t)), versus O(T d^omega + ...) for ONS and O(T d^2 + d^omega sqrt(T log T) + ...) for ONS with LightONS.
• Experiments on synthetic m-out-of-n problems (10 seeds) report CoRectron is typically faster than ONS while achieving competitive or smaller regret, and is stable across hyperparameters.

Surprising findings

• Unlike second-order perceptron mistake bounds in classification, which carry margin-dependent terms, the contextual recommendation analysis yields clean logarithmic regret bounds.

Limitations

• Guarantees assume an exact linear-optimization oracle over each feasible set.
• Exact kernelized implementation has O(t^2) per-round cost, requiring approximation or compression for long horizons.
• Experiments are limited to synthetic settings.

Experimental setup

Datasets: synthetic contextual m-out-of-n action sets (simulated)

Benchmarks: synthetic contextual m-out-of-n simulations (Linear and Kernel-RBF settings)

Metrics: cumulative regret runtime number of Mahalanobis projections

Baselines: ONS-based contextual recommendation (Sakaue et al. 2025) LightONS OGD KONS ONS

Builds on: Online Newton Step Sakaue et al. 2025 ONS contextual recommendation second-order perceptron MetaGrad LightONS

Closest papers by meaning

• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms (NeurIPS 2021 · similarity 0.89)
• Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.87)
• Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.86)
• Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood (NeurIPS 2024 · similarity 0.86)
• Efficient Contextual Bandits with Uninformed Feedback Graphs (ICML 2024 · similarity 0.86)
• Conservative Contextual Bandits: Beyond Linear Representations (ICLR 2025 · similarity 0.86)