# Online Learning with Ordered Experts (via Two-point Feedback)

DevFeed: [Online Learning with Ordered Experts (via Two-point Feedback)](<https://devfeed.tech/articles/online-learning-with-ordered-experts-via-two-point-feedback-120639.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.07629>)

Author: Shiliang Zuo

Published: 2026-11-06T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Mixture of Experts (MoE)](<https://devfeed.tech/topics/mixture-of-experts-moe.md>)

Tags: [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [experts](<https://devfeed.tech/tags/experts.md>), [feedback](<https://devfeed.tech/tags/feedback.md>), [learning](<https://devfeed.tech/tags/learning.md>), [online](<https://devfeed.tech/tags/online.md>), [online-learning](<https://devfeed.tech/tags/online-learning.md>)

## AI overview

The paper gives regret guarantees for adversarial online learning with ordered actions when each round permits two paid observations. For separated losses composed of hidden nondecreasing and nonincreasing components, with each query revealing both separately, regret against the best of |𝒞| experts is O(log(|𝒞|T)√(T log|𝒞|)), within a logarithmic factor of the full-information bound. For bounded-variation losses where queries reveal only the loss, the bound is Õ(√T + |𝒞|). The method uses two observations to measure a loss increment along the order, then combines random-path telescoping estimates with a reversible pair sampler that preserves the intended action marginals. An application to dynamic pricing shows two-option menus attain the full-information rate up to logarithmic factors.

## Source excerpt

arXiv:2611.07629v1 Announce Type: new 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 \[ O\bigl(\log(|\cF|T)\sqrt{T\log|\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.