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

• URL: http://arxiv.org/abs/2603.20826v1
• Date: Sat, 21 Mar 2026 13:57:29 GMT
• Title: Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness
• Abstract summary: We present a simple algorithm that is more efficient than the ONS-based method while achieving the same regret guarantee.<n>Our core idea is to exploit the improperness inherent in contextual recommendation, leading to an update rule akin to the second-order perceptron from online classification.
• Score: 18.046669772867443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Contextual recommendation is a variant of contextual linear bandits in which the learner observes an (optimal) action rather than a reward scalar. Recently, Sakaue et al. (2025) developed an efficient Online Newton Step (ONS) approach with an $O(d\log T)$ regret bound, where $d$ is the dimension of the action space and $T$ is the time horizon. In this paper, we present a simple algorithm that is more efficient than the ONS-based method while achieving the same regret guarantee. Our core idea is to exploit the improperness inherent in contextual recommendation, leading to an update rule akin to the second-order perceptron from online classification. This removes the Mahalanobis projection step required by ONS, which is often a major computational bottleneck. More importantly, the same algorithm remains robust to possibly suboptimal action feedback, whereas the prior ONS-based method required running multiple ONS learners with different learning rates for this extension. We describe how our method works in general Hilbert spaces (e.g., via kernelization), where eliminating Mahalanobis projections becomes even more beneficial.

Related papers

• Provably Optimal Learning Algorithms for Assistance Games [60.843021846414956]
  We provide the first provably efficient learning algorithms for repeated assistance games.<n>We present decentralized algorithms for both an informed human and the assistant.<n>We prove that achieving a regret approximation factor better than $(1-1/e)$ is computationally intractable.
  arXiv  Detail & Related papers  (2026-07-09T00:38:42Z)
• A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization [72.1530234801628]
  Online Newton Step (ONS) is a fundamental problem in online learning.<n>ONS faces a computational bottleneck due to the Mahalanobis projections at each round.<n>This paper proposes a simple variant of ONS, LightONS, which reduces the total runtime to $O(normd2 T + dsqrtTlog) while preserving an optimal regret.<n>This design enables LightONS to serve as an efficient plug-in replacement of ONS in broader scenarios.
  arXiv  Detail & Related papers  (2025-12-29T03:59:51Z)
• Stacey: Promoting Stochastic Steepest Descent via Accelerated $\ell_p$-Smooth Nonconvex Optimization [15.179519413549086]
  We introduce a new accelerated $ell_p$ steepest descent algorithm, called Stacey, to handle non-Euclidean smooth optimization tasks.<n>In addition to providing theoretical guarantees for the foundations of our algorithm, we empirically compare our approach against popular methods.
  arXiv  Detail & Related papers  (2025-06-07T00:47:07Z)
• Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces [51.513172647831745]
  We develop a form Thompson sampling for online learning under full feedback.<n>We show regret decomposes into regret the learner expected a priori, plus a prior-robustness-type term we call excess regret.
  arXiv  Detail & Related papers  (2025-02-20T18:10:12Z)
• Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning [13.429541377715296]
  We propose the first computationally efficient algorithm achieving rate-optimal regret guarantees in infinite-horizon discounted linear Markov decision processes.<n>We show that, combined with a regularized approximate dynamic-programming scheme, the resulting algorithm achieves a regret of order $tildemathcalO (sqrtd3 (1 - gamma)- 7 / 2 T)$, where $T$ is the total number of sample transitions, $gamma in (0,1)$ is the discount factor, and $d$ is the feature dimensionality.
  arXiv  Detail & Related papers  (2025-02-19T17:32:35Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  We study reinforcement learning with linear function approximation and adversarially changing cost functions. We present a computationally efficient policy optimization algorithm for the challenging general setting of unknown dynamics and bandit feedback.
  arXiv  Detail & Related papers  (2023-01-30T17:26:39Z)
• Trading Off Resource Budgets for Improved Regret Bounds [6.85316573653194]
  We propose an algorithm called Follow the Perturbed Multiple Leaders (FPML) for adversarial online learning problems. We show that FPML achieves expected regret $mathcalO(Tfrac1B+1ln(N)fracBB+1)$ over time horizon. We show how FPML can lead to new algorithms for Linear Programming which require stronger oracles.
  arXiv  Detail & Related papers  (2022-10-11T21:13:48Z)
• Online Prediction in Sub-linear Space [15.773280101995676]
  We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary) We also demonstrate a separation between oblivious and (strong) adaptive adversaries by proving a linear memory lower bound of any sub-linear regret algorithm against an adaptive adversary.
  arXiv  Detail & Related papers  (2022-07-16T16:15:39Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  We show that it is possible to obtain regret scaling as $mathcalO(sqrtV_1star K)$ in reinforcement learning with large state spaces. We demonstrate that existing techniques based on at least squares estimation are insufficient to obtain this result.
  arXiv  Detail & Related papers  (2021-12-07T00:29:57Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  We study the $K$ contextual dueling bandit problem, a sequential decision making setting in which the learner uses contextual information to make two decisions, but only observes emphpreference-based feedback suggesting that one decision was better than the other. We provide a new algorithm that achieves the optimal regret rate for a new notion of best response regret, which is a strictly stronger performance measure than those considered in prior works.
  arXiv  Detail & Related papers  (2021-11-24T07:14:57Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  We study a novel variant of online finite-horizon Markov Decision Processes with adversarially changing loss functions and initially unknown dynamics. In each episode, the learner suffers the loss accumulated along the trajectory realized by the policy chosen for the episode, and observes aggregate bandit feedback. Our main result is a computationally efficient algorithm with $O(sqrtK)$ regret for this setting, where $K$ is the number of episodes.
  arXiv  Detail & Related papers  (2021-01-31T16:49:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.