[Submitted on 5 Nov 2026 (v1), last revised 11 Nov 2026 (this version, v2)]
Abstract:We study adversarial online learning with expert recommendations in a totally ordered action space, where the experts’ recommendations may change and be reordered arbitrarily. Our focus is two-point feedback: on each round the learner plays two current recommendations, observes both, and pays their average. We study two problems. In the separated monotone problem, the loss is the sum of a hidden nondecreasing component and a hidden nonincreasing component, and a query reveals the two components separately. In the BV problem, the losses are bounded and have bounded variation (BV) along the order, and a query reveals only the loss.
In the separated monotone problem, two paid observations achieve [ Obigl(log(|cF|T)sqrt{Tlog|cF|}bigr) ] regret against the best of $|cF|$ experts, within a logarithmic factor of the classical full-information bound. For the BV problem, we obtain $wtO(sqrt T+|cF|)$ regret. We give an application in dynamic pricing with expert advice, showing that two-option menus matches the full information rate up to $log$ factors.
The main technical ingredient is a marginal-preserving endpoint flow estimator. Two observations reveal a loss increment along the order; random paths supply telescoping identities that turn this local information into unbiased loss estimates for all current recommendations. A reversible pair sampler preserves the learner’s intended marginal at both played actions. The estimator’s second-moment and stability bounds support online updates for both feedback models.
Submission history
From: Shiliang Zuo [view email]
[v1] Thu, 5 Nov 2026 08:14:00 UTC (31 KB)
[v2] Wed, 11 Nov 2026 06:30:26 UTC (32 KB)
