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
Feedback model
Upper bound
Reference
Non-contextual ( p=0)
Bandit
T1−d+21
( Kleinberg et al., 2008 )
Two-point bandit
T1−d1∨T
( Eldowa et al., 2026 )
Full information
T
( Rakhlin et al., 2015 )
Contextual ( p≥0)
Bandit
T1−d+p+21
( Slivkins, 2011 )
Two-point bandit
T1−d+p1∨T
( \Cref thm:concrete)
One-sided full information ( d=1 )
T1−p+2/31∨T
( Cesa-Bianchi et al., 2017 )
Table 1: Regret bounds (up to logs) in nonparametric adversarial bandits with Lipschitz losses according to the level of feedback. The results of Cesa-Bianchi et al. (2017) and Slivkins (2011) concern classes of Lipschitz policies. Underlined rates are minimax optimal. A matching lower bound for the contextual bandit setting was proved by Slivkins (2011) when the composite losses ℓt(f(⋅)) are assumed Lipschitz.
We study contextual bandits with K actions, a class of N 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)) against the best policy in hindsight on the realized contexts. This improves the T2/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 T, K, and log(2N).
We study stochastic contextual bandits with an unknown context-lumpable structure. The S contexts are partitioned into r 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), matching the lower bound of Lee et al. (2023) up to logarithmic factors and improving their previous upper bound by a factor of r. 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 r 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.
Chenyu Lu, Zihan Zhang
The Hong Kong University of Science and Technology
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+2dz+1), where dz 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.
Mudit Sharma, Shweta Jain, Vaneet Aggarwal +1
Indian Institute of Technology Ropar · Purdue University · Indian Institute of Technology Hyderabad