CS Paper Radar

NCCL-BOT: Closing the Loop on NCCL's Cost Model with Online Bandits

Hanan Shteingart, Amedeo Sapio, Chen Avin, Devendar Bureddy, Manjunath Gorentla Venkata, Srivatsan Krishnan, Shie Mannor, Sreeram Potluri, Gil Shabat, Zsolt-Alon Wertheimer

cs.DC cs.LG ·submitted 2026-11-08 10:58 UTC · v1

Abstract

NCCL picks an algorithm-protocol pair for every collective from an analytic cost model (AUTO) that never sees a measured latency. The model is a strong prior but a brittle final decision: priced on forced-arm runs, its choice is exact on most contexts and badly wrong in a few. We built NCCL-BOT, a tuner plugin that closes the loop: a per-context bandit, warm-started from the model, learns from measured latencies. We replay a forced-arm H100 sweep, tuned at 4-8 nodes and scored at 16-32, and price the model's choice on the same forced arms; that sweep has no stock-NCCL run. The bandit cuts the contexts where the model's choice loses more than 10% from 19 to 1 (p99 103% to 9.9%, mean 6.1% to 1.6%; p=0.047 over nine scenarios after Holm correction). The prior and continued learning both matter: cold-started bandits, and committing after one probe of each arm, lose more on the mean in every scenario. Supervised selectors fit once on the same data and tuned with the same budget match the mean, and their heavier tail is not significant (7 against 1 contexts above 10%, p=0.06); at seen scales they match or beat online selection. With hyperparameters frozen from H100, UCB1 cuts AUTO's p99 from 60% to 23% and from 56% to 15% on two GB200 fabrics, but its contexts above 10% go from 16 to 8 on one and from 10 to 13 on the other, and scenario-level tests do not separate the two. Live, on two latency-emulated node sets of one H100 system with one run per policy, the learners repair most of a gross AUTO error on one (selection loss 31% to 6-8% for deterministic Greedy and UCB1; average all-reduce bandwidth 1.18-1.24x stock) but average 0.94-0.99x stock on the other, and on both lose to stock below 1 MiB (on the first through plugin overhead); on H100 the cost model is exact there offline, so small sizes can be left to it. We do not show a net end-to-end win.

Comment
46 pages, 13 figures, 38 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Odds-Ratio Thompson Sampling: A Specification and Design Guide for Contrast-Based Multi-Armed Bandits

cs.LG ·2026-09-17 ·Sulgi Kim
code/data similarity 0.68
Abstract · 25 pages, 7 figures, 2 tables in the main text; 2 figures and 3 tables in the supplement. Reference implementation at https://github.com/sul…

Batched multi-armed bandits update on a service's own schedule, and the usual implementation carries each arm's absolute reward rate from one update to the next. When the shared level moves between batches, that memory goes stale even though the comparisons between arms may not have. Odds-Ratio Thompson Sampling (OR-TS) instead carries the joint posterior over log-odds contrasts and fits the common level afresh in every batch, marginalizing it out. This paper specifies that update, places it inside a Bayesian bandit agent with two controls, decay for how much past evidence survives an update and aggressiveness for how sharply belief becomes allocation, and evaluates it against absolute-rate memory. Across 86 public A/B series the level varies about twenty-five times more than the contrast. In prespecified synthetic environments a moving level costs absolute-rate memory five times the regret and leaves the best arm below a majority of traffic in 7 of 20 runs, against none for OR-TS. In a policy simulation built from 71 real experiments, where the contrasts are too small to resolve, expected-click differences stay within 0.1% for 58 of them, yet contrast memory still ends on the better arm more than twice as often. Where the contrasts themselves move, the bet fails, and that case is reported too.

0.26

Learning When to Update: A Near-Optimal Timing Bandit Approach

cs.LG ·2026-09-29 ·Qiulin Lin, Junyan Su, Liyuan Wang, Minghua Chen
publishedtheory similarity 0.67
Abstract

Systems operating in dynamic environments require timely updates to sustain performance. For resource-intensive systems such as machine learning models and digital twins, strategically timing updates is essential. Updating too frequently wastes resources, while updating too infrequently leads to costly performance degradation. The problem is particularly challenging when the system's degradation pattern is unknown a priori, as is common in new operating environments. We formalize this challenge as a novel \emph{timing bandit} problem, where each arm represents a candidate update interval with a fixed update cost and an unknown, stochastic degradation cost. Three structural properties distinguish this setting from standard multi-armed bandits: selecting an interval commits the learner to multiple time slots before the next update; arm costs are composed of per-step degradation costs and a fixed update cost; and selecting a longer interval naturally reveals degradation at every intermediate step, providing consecutive feedback relevant to shorter intervals. By exploiting these structures, we develop Balanced Consecutive Arm Elimination (BCAE). BCAE achieves $\tilde{O}(\sqrt{T})$ regret, improving upon the $\tildeΩ(K\sqrt{T})$ regret of standard bandit algorithms in this setting, where $K$ is the number of candidate update intervals. We further propose an Optimism-Enhanced variant (OE-BCAE) that integrates lower-confidence-bound principles to improve empirical adaptivity while preserving the same regret order. Moreover, the regret bound achieved by our algorithms matches the theoretical lower bound up to logarithmic factors. Simulation results demonstrate that our algorithms achieve low regret and remain stable as both the number of arms and the update cost vary.

0.24

Optimal Online Regret for Context-Lumpable Bandits

cs.LG ·2026-10-13 ·Chenyu Lu, Zihan Zhang
theory similarity 0.66
Abstract

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 $\widetilde{O}(\sqrt{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.

0.16

Detection Augmented Learning In Non-Stationary Bandit Environments

cs.LG stat.ML ·2026-10-19 ·Argyrios Gerogiannis, Yu-Han Huang, Subhonmesh Bose, Venugopal V. Veeravalli
similarity 0.65
Abstract · 36 pages, 1 table, 5 figures, extension of https://arxiv.org/abs/2501.19401

We study the problem of non-stationary bandits without knowledge of the environmental changes. We propose Detection Augmented Learning (DAL) a black-box paradigm that comprises three modular components: a bandit algorithm, a change detector, and a forced exploration schedule. This modular design enables its applicability across a broad spectrum of bandit problems, from classical to highly structured settings. First, we provide theoretical insights into DAL's strong empirical performance: a single regret bound shows that DAL transfers the regret of its stationary input to the piecewise stationary setting, attaining or improving the best known bounds in every setting considered. We further identify conditions under which DAL performs well in drifting environments. Then, we showcase DAL's practical performance and versatility through extensive experimentation in which DAL consistently surpasses all state-of-the-art methods, both prior-free and prior-based, across diverse non-stationary scenarios in nine bandit settings. Finally, we investigate the effectiveness of the forced exploration and show that a bandit-driven strategy improves performance and shortens detection delay.

0.24

When Offline Evaluation Misleads: A Diagnostic Protocol for Reward and Policy Selection in Delayed-Feedback Contextual Bandits

cs.LG ·2026-08-12 ·Sang Su Lee, Vineeth Loganathan, Shishir Dash, Vijay Raghavan
publishedbenchmark similarity 0.65
Abstract · Accepted at the 5th Workshop on End-to-End Customer Journey Optimization (KDD 2026)

Personalizing marketing messages with contextual multi-armed bandits (CMABs) drives real business value, yet the objective that ultimately matters - a downstream conversion - is observed only weeks later, too late to drive online learning. Teams therefore train the bandit on a fast proxy reward, and separately must judge whether a contextual bandit is worth its complexity over sending one best message. Settling both decisions with the usual offline checks - a batch off-policy estimate, a marginal arm-discrimination test, a confidence interval - can mislead systematically under delayed feedback. We give an ordered diagnostic protocol that screens a reward-and-policy candidate on two axes, alignment (does optimizing the reward move the north-star?) and learnability (can the bandit identify the reward-optimal policy?), before trusting any reported lift. We validate it where the truth is known - a public off-policy-evaluation benchmark and a controllable synthetic generator - and illustrate it on a deployed large-marketplace push system (where, with five arms and one split, the evidence is directional rather than powered). Two lessons recur. (N1) A single offline number can mis-rank rewards: a denser reward signal gives the bandit more to learn from, so rewards that look tied in a static estimate pull apart once learning happens online. (N2) If you cannot tell in advance which single message is best, a per-user policy partly just avoids betting on the wrong one - that looks like personalization but is really robustness, so a "personalization premium" is easily overstated. Our contribution is methodological rather than algorithmic: the ordered protocol, the two lessons it surfaces, and the end-to-end experience of applying it to a delayed-feedback CMAB.

0.20

Conservative Dueling Bandits: Preference Learning under Baseline Constraints

cs.LG cs.AIstat.ML ·2026-10-27 ·Rohan Deb, Mohammad Ghavamzadeh, Arindam Banerjee
similarity 0.64
Abstract

Contextual dueling bandits learn from pairwise comparisons, the same feedback used to fine-tune language models from human preferences. Standard algorithms explore aggressively and can show users two poor options. We study conservative contextual dueling bandits, which require that, at every round, the cumulative score of the better displayed item stay above a $(1-α)$ fraction of a trusted baseline's. An item's score is its probability of beating the best available item, so the constraint depends only on utility differences and needs no absolute rewards. This also changes how safety can be certified: we show that transferring the safety test of the conservative bandit algorithm CLUCB unchanged can incur linear regret, even when the baseline's utilities are known exactly. For linear utilities, we develop MaxInP-BC, which certifies scores through utility gaps and, when it must fall back, pairs the baseline with an informative partner so that fallback rounds still drive learning. It is safe with high probability at all times, with regret $\tilde{O}(d\sqrt{T}/κ)$ plus an additive cost of conservatism that does not grow with the horizon. For general utility classes, we develop BTIGW-BC, which turns the guarantee of an online logistic-regression oracle into cumulative safety certificates. It is safe at all times, makes finitely many fallbacks, and has sublinear regret whenever the oracle's logistic regret is sublinear. In experiments, both satisfy the constraint, which their unconstrained counterparts often violate, at a moderate cost in regret.

0.13

Bandits with Probing: Optimal Coverage and the Role of Feedback

cs.LG cs.DSstat.ML ·2026-09-14 ·Yongjie Guan
similarity 0.64
Abstract · 40 pages, 1 table

In bandits with probing, a learner selects at most $k$ of $n$ arms per round, earns the largest of their rewards, and competes with the best fixed single arm. For independent arms with i.i.d. rewards in $[0,1]$ and $2\le k<n$, the minimax regret is $Θ\bigl(\frac{n-k}{n}\min\{T,n/k\}\bigr)$, the cost of locating an unknown good arm, and observing only the maximum suffices to attain it. In particular, two probes give $Θ(\min\{T,n\})$ regret, which resolves two open questions of Bhaskara et al. (2023) with weaker feedback. Our policy turns the probing surplus, the excess of the maximum over each probed arm, into exploration capital, and a permanent random core yields the sharp dependence on $k$. On arbitrary fixed reward arrays, same-round contrasts between blocks of arms attain the same rate, because the surplus pays for the stability of mirror descent. Winner feedback, the maximum together with its winning label, instead incurs an additional learning cost under joint i.i.d. rewards and on fixed arrays. We characterize this cost even when values are revealed only intermittently, using policies that know neither the horizon nor the revelation rate. For three independent arms and two probes, exact maxima, Bernoulli-rounded maxima with winning labels, and winning labels alone have minimax regret $Θ(1)$, $Θ(\sqrt T)$, and $Θ(T)$: rounding preserves conditional means but not the rate.

0.25

Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

cs.LG stat.ML ·2026-10-21 ·Yashaswini Kaluguri, Nikhil Karamchandani
theory similarity 0.63
Abstract

We propose a novel stochastic cascading bandit setup where probing an ordered shortlist of $K$ out of $L$ arms incurs position-dependent costs, and the learner observes only noisy feedback regarding each arm's true output. We identify a sub-class of noise models for which the optimal shortlist can be found by sorting arms according to a per-arm score: such a score exists for both selection and ordering when the channel has no false positives, and for ordering alone (but not selection) when measurements are costless; however in general neither selection nor ordering is separable once noise and cost are both present. For the case where both selection and ordering scores exist, we provide a UCB-based algorithm with $O((L-K)\log T)$ instance-dependent regret over a time horizon $T$, which matches an algorithm-agnostic lower bound (up to constant factors). For the more challenging scenario where scores don't exist, we develop a new algorithmic template, DP-UCB, that embeds optimism directly inside an exact dynamic program, yielding $O\big(LK\log T\big)$ regret. Finally, we validate our theoretical results through extensive numerical evaluations and simulations over both synthetic and real-world datasets.

0.08