cs.LGNov 13, 2026

Contextual Non-Convex Bandit Optimization with Two-Point Feedback

Authors: Khaled Eldowa, Pierre Gaillard

Organizations: Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK; Grenoble, France · Inria, D.I. École Normale Supérieure, CNRS, PSL Research University; Paris, France

Abstract

We study a non-stochastic contextual bandit problem with Lipschitz losses. At every round, the learner observes the context then picks two actions, observes the difference between their losses, and incurs their mean. The aim is to minimize the regret against a generic non-parametric comparator class of policies mapping contexts to actions; for example, Lipschitz policies and Hölder-smooth policies. We show how relying on a hierarchical discretization technique allows us to improve upon the regret rates achievable under one-point feedback, and even recover the full-information rate in some cases; notably, for sufficiently smooth policy classes or low-dimensional instances. Additionally, for Lipschitz policies, we present an algorithm whose per-round computational complexity is only logarithmic in the time horizon.

Figures & tables

Explore similar work

CardsList
  1. Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits

    Nov 12, 2026Kiarash Banihashem, MohammadTaghi HajiaghayiContextual BanditsAdversarial Bandits

  2. Optimal Online Regret for Context-Lumpable Bandits

    Oct 13, 2026Chenyu Lu, Zihan ZhangContextual Bandits

  3. Lipschitz Dueling Bandits over Continuous Action Spaces

    Apr 1, 2026Mudit Sharma, Shweta Jain, Vaneet Aggarwal +1Lipschitz BanditsDueling Bandits