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

Nov 12, 2026

Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits

We study contextual bandits with KK actions, a class of NN policies, and i.i.d.\ contexts from a distribution that the learner can sample. For any sequence of loss functions fixed before play, we give an oracle-efficient algorithm with expected regret O(KTlog⁡(2N) log⁡(2KT))O(\sqrt{KT\log(2N)}\,\log(2KT)) against the best policy in hindsight on the realized contexts. This improves the T2/3T^{2/3} dependence on the horizon in prior oracle-efficient bounds and achieves the optimal regret rate in this setting up to logarithmic factors. Our algorithm perturbs policy scores using a Poisson sample of auxiliary contexts. At each sampled context, the perturbation assigned to an action is a Laplace noise draw multiplied by a scale specific to that context and action. We show that choosing these scales to minimize a convex objective determined by past observations yields the stated regret bound. We further approximate the minimizing scales by projected stochastic gradient descent using only an exact offline cost-sensitive optimization oracle that returns the optimum value. Since the table of scales can be large, the algorithm represents the SGD iterates implicitly by storing the random draws that determine each update and evaluates the scales only at queried contexts. Both the oracle complexity and the remaining resource bounds are polynomial in TT, KK, and log⁡(2N)\log(2N).
Oct 13, 2026

Optimal Online Regret for Context-Lumpable Bandits

We study stochastic contextual bandits with an unknown context-lumpable structure. The SS contexts are partitioned into rr blocks, and every arm has the same mean reward across contexts in the same block. Under arbitrary context distributions and without separation assumptions, we design an algorithm with expected regret O~(r(S+K)T)\widetilde{O}(\sqrt{r(S+K)T}), matching the lower bound of Lee et al. (2023) up to logarithmic factors and improving their previous upper bound by a factor of rr. The algorithm operates over dyadic accuracy levels, using a baseline policy and confidence-based early stopping to control exploration. It then performs cross-context elimination: since rewards are identical within a block, one selected arm eliminates all surviving records from that block, requiring at most rr selections at each level. Multi-scale exploration assigns finer accuracies to frequent blocks and coarser accuracies to rare blocks, yielding a near-optimal arm for every block while keeping the weighted policy error small.
Apr 1, 2026

Lipschitz Dueling Bandits over Continuous Action Spaces

We study for the first time, stochastic dueling bandits over continuous action spaces with Lipschitz structure, where feedback is purely comparative. While dueling bandits and Lipschitz bandits have been studied separately, their combination has remained unexplored. We propose the first algorithm for Lipschitz dueling bandits, using round-based exploration and recursive region elimination guided by an adaptive reference arm. We develop new analytical tools for relative feedback and prove a regret bound of O~(Tdz+1dz+2)\tilde O\left(T^{\frac{d_z+1}{d_z+2}}\right), where dzd_z is the zooming dimension of the near-optimal region. Further, our algorithm takes only logarithmic space in terms of the total time horizon, best achievable by any bandit algorithm over a continuous action space.