CS Paper Radar

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

Shiliang Zuo

cs.LG ·submitted 2026-11-05 08:14 UTC · 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 \[ 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry

cs.LG ·2026-10-31 ·Canzhe Zhao, Vincent Y. F. Tan
similarity 0.72
Abstract

We study \textit{best-of-both-worlds} (BOBW) algorithms for linear bandits, which aim to simultaneously guarantee $\gO(\sqrt T)$ regret in the adversarial regime and $\gO(\log T)$ regret in the stochastic regime over $T$ rounds. For finite action sets, we introduce \emph{information-acquisition follow-the-regularized-leader} (\IAFTRL{}), the first BOBW algorithm based purely on the follow-the-regularized-leader (FTRL) framework that attains an $\gO(\cstar\log T)$-type regret in the stochastic regime, where $\cstar$ is the information-acquisition complexity that characterizes instance-dependent optimality in linear bandits, while retaining the $\gO(\sqrt{T})$ regret guarantee in the adversarial regime. This resolves the open problem posed in~\cite{LeeEtAl2021,KongZ023,ItoT23,ZhaoItoLi2025}.

0.15

Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

cs.LG stat.ML ·2026-09-27 ·Gon Buzaglo, Elad Hazan
highly cited similarity 0.72
Abstract

We consider binary prediction with i.i.d. contexts from an unknown distribution and adaptively chosen losses. We show that a simple Follow-the-Perturbed-Leader algorithm using a Gaussian perturbation for each observed context achieves $\widetilde O(\sqrt{T\log N})$ regret for a class of $N$ experts, while requiring one optimization-oracle call per round and no explicit enumeration of the class. For an infinite hypothesis class $\mathcal H$, the same algorithm achieves $\widetilde O(\sqrt{T\operatorname{VC}(\mathcal H)})$ regret. This resolves an open problem posed by Lazaric and Munos (2012), showing that hybrid classification is computationally as easy as statistical learning. As an application, we reduce the problem of contextual bandits with $K$ actions to classification through uniform exploration, achieving $\widetilde O(K^{2/3}T^{2/3}(\log N)^{1/3})$ regret. This matches the best known dependence on the horizon while removing the context-distribution access required by prior oracle-efficient methods.

0.39

Near-Optimal $\sqrt{K}$-Regret for Online Learning in Uninformed Markov Games

cs.LG stat.ML ·2026-11-01 ·Junyan Liu, Haipeng Luo, Lillian J. Ratliff, Zihan Zhang
similarity 0.72
Abstract

We study online learning in two-player uninformed Markov games, where the opponent may follow an arbitrary, unknown policy in each episode and the learner does not observe the opponent's actions. [TWYS21] showed that achieving sublinear external regret requires an exponential dependence on the episode length $H$. Motivated by this limitation, they studied the weaker notion of Nash-value regret and obtained an $\widetilde{O}(K^{2/3})$ regret bound, where $K$ is the number of episodes. More recently, [LLZR26] introduced a stronger notion called empirical Nash-value regret and achieved an $\widetilde{O}(\sqrt{K})$ bound when the opponent's non-stationarity is moderate, including the case where the opponent follows a fixed policy. However, whether the $\sqrt{K}$ rate is achievable in the worst case remained open. In this paper, we resolve this open question by developing an algorithm that achieves $\widetilde{O}(H^{3/2}S\sqrt{AK})$ empirical Nash-value regret against arbitrary opponent policies, where $S$ is the number of states and $A$ is the number of learner's actions. Specifically, our algorithm combines global and local planning by maintaining a collection of candidate predictions of future losses, each associated with a policy. Global planning learns which candidates to favor across episodes, while local planning combines their policies differently at each state to make decisions. A key ingredient is to coordinate these two components to control the discrepancy between local loss estimates and the total loss of the executed policy, using only the learner's observed trajectories.

0.12

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

cs.LG stat.ML ·2026-08-25 ·Mengxiao Zhang
theory similarity 0.72
Abstract

In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games. Although previous works have shown that $o(\sqrt{T})$ alternating regret is achievable under various assumptions on the loss functions and feasible domains, the minimax regret rate has remained open even for the expert problem. In this paper, we resolve this question by showing matching lower and upper bounds for both the expert problem and general OCO. Somewhat surprisingly, for the $d$-expert problem, we show that the minimax alternating regret is $Θ(\log d)$ by providing both a lower bound and an algorithm achieving a matching upper bound. This significantly improves upon the $O(T^{1/3}\log^{2/3} d)$ established by [HLLZ25]. We further extend our results to general OCO over a $d$-dimensional compact convex set and prove that the worst-case minimax alternating regret is $Θ\left(d\log \left(1+\frac{T}{d}\right)\right)$, also significantly improving upon the $O((d\log T)^{2/3}T^{1/3})$ upper bound and resolving the open problem posed by [CCK+23,HLLZ25]. As a direct implication, our alternating dynamics achieve $O(\frac{\log d}{T})$ convergence to Nash equilibrium in two-player zero-sum games, matching the state of the art, and give the first such convergence rate to coarse correlated equilibrium in two-player general-sum games. Technically, our upper bound for the expert problem is achieved by a corrected variant of Hedge. We extend the same corrected-potential argument to continuous action sets to obtain the optimal alternating-regret rate for OCO. For the lower bounds, the construction for the expert problem repeatedly eliminates half of the candidate experts, while the OCO lower bound instance construction replaces this discrete elimination by a more involved multiscale construction on the unit disk.

0.26

Lower Bounds for Linear-Oracle Online Learning

cs.LG stat.MLmath.OC ·2026-09-29 ·Mohit Sinha
theory similarity 0.72
Abstract

Can a constant number of linear minimizations per round improve on the $T^{3/4}$ regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The learner receives an initial feasible point and a diameter bound, and must remain feasible on every domain consistent with its oracle replies. For $T$ rounds, at most $b$ calls between decisions, diameter bound $D$, and gradient norm bound $L$, we construct an instance in dimension $d=2b(T-1)+1$ with regret at least $2^{-1/4}LDb^{-1/4}T^{3/4}$. The adversary fixes the domain, initial point, deterministic tie rule and linear losses before play. The vertices form a path on which every point available before a decision has zero current loss, while the final vertex has negative loss on every round. For constant $b$, the result matches the known upper rate for dimension-independent guarantees. For one-call fixed schedules with a nonzero coefficient on the newest gradient, a second construction gives regret at least $3LDT^{3/4}/4$ with unique minimizers at every issued query. Exact-arithmetic certificates for the tuned schedule of Weibel et al. closely match their finite-horizon numerical worst cases, with unique oracle replies.

0.08

Tracking a Small Set of Experts in Online Convex Optimization

cs.LG math.OCstat.ML ·2026-10-14 ·Angelos Assos, Anand Brahmbhatt, Elad Hazan
similarity 0.71
Abstract

For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches $k$ times among only $m$ experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of $\widetilde{O}(md+k)$, while the best known efficient algorithm for this problem has regret $\widetilde{O}(dk)$. We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least $(k\sqrt d)^{1-o(1)}$ regret.

0.19

Online Convex Optimization with Dueling Feedback

cs.LG ·2026-08-15 ·Yiyang Lu, Hareshkumar Jadav, Mohammad Pedramfar, Ranveer Singh, Vaneet Aggarwal
similarity 0.70
Abstract

Noisy binary comparison between two candidates is a common interface between human and learning systems, especially in modern large language model (LLM) post-training alignment. We study online convex optimization with dueling (pairwise comparison) feedback, where the learner observes only a binary preference between two queried points. We consider adversarial sequences of convex losses and measure regret with the loss at both queried points, under a comparison link with a known nonzero slope at the origin. We propose a simple reduction that converts dueling feedback into approximate gradients, enabling the use of standard first-order methods. We show that regret guarantees transfer under this reduction, yielding $\mathcal O(T^{3/4})$ static and adaptive regret, and $\mathcal O(T^{3/4}\sqrt{1+P_T/D})$ dynamic regret with unknown comparator path length $P_T$. For strongly convex losses, the static and adaptive bounds improve to $\widetilde{\mathcal O}(T^{2/3})$. For smooth losses, we presents unified dueling ellipsoidal FTRL, and proves $\widetilde{\mathcal O}(T^{2/3})$ static regret, which improves to $\widetilde{\mathcal O}(\sqrt T)$ under additional strong convexity.

0.38

Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits

cs.LG stat.ML ·2026-11-03 ·Jongyeong Lee, Hyundam Yoo
similarity 0.70
Abstract · preprint

We study online learning with directed weakly observable feedback graphs and propose a Follow-the-Perturbed-Leader (FTPL) policy that achieves best-of-both-worlds guarantee with nearly linear expected time complexity. To preserve the simple structure of FTPL, we develop a novel graph-based loss estimator that combines forced exploration, conditional geometric resampling and adaptive learning rates with surrogate probabilities. Our policy achieves $\tilde{\mathcal{O}}(δ_*^{1/3} T^{2/3})$ regret for adversarial regimes as well as $\tilde{\mathcal{O}}(δ_* \log T / Δ_{\min}^2)$ regret for stochastic regimes, where $δ_*$ and $Δ$, respectively, denote the fractional weak domination number and the suboptimality gap. These results show that refined guarantees for problems with minimax regret of $Θ(T^{2/3})$ can be obtained through appropriately designed adaptive learning rates and loss estimators without sacrificing the simplicity of FTPL.

0.16