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.