Efficient Online Proportional Sampling with Applications to Smoothed Online Learning

Jul 16, 2026

Efficient online proportional sampling is studied for a high-dimensional domain against a σ-smoothed adaptive adversary. Sampling comes from a dynamically evolving weight function induced by a growing sequence of piecewise-structured partitions, modeled via updates on regions separated by axis-parallel hyperplanes. A new data structure supports efficient updates and proportional sampling without explicit enumeration of the O(td) induced subregions. Tight O(√σT) depth bounds hold under σ-smoothed adversaries, with O(log T) under random-order adversaries. The framework yields no-regret online learning with piecewise-structured rewards under full-information and bandit feedback, with sublinear regret.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages74

Reading Time3 h 6 min

Abstract

Introduction

arXiv :2607 . 10963v 1 [ cs .LG] 13 Jul 2026 Efficient Online Proportional Sampling with Applications to Smoothed Online Learning Amirmahdi Mirfakhar 1 , Maria-Florina Balcan2 , and Hedyeh Beyhaghi 1 1 University of Massachusetts Amherst, 2 Carnegie Mellon University, Abstract We study the problem of efficient online proportional sampling from a high-dimensional domain under a σ-smoothed adversary, where the sampling distribution is induced by a dynamically evolving weight function defined over a sequence of piecewise-structured partitions. This setting captures a broad range of applications, including principal-agent games (e.g., pricing and contract design), and algorithm configuration and parameter tuning. The central challenge is maintaining an efficient data structure as the induced partition grows increasingly complex over time—naively, the number of subregions can grow as O (td ) by round t in d dimensions. We design a data structure that supports efficient updatesand proportional sampling while avoiding the cost of explicitly maintaining this exponential growth, where the discontinuities are structured from axis-parallel hyperplanes. Under a σ-smoothed adaptive adversary, we prove a tight O ( √σT) bound on the depth of our data structure, and an O(log T) bound under a random-order adversary—to our knowledge, the first such results for this class of problems. We apply this framework to online learning with piecewise-structured rewards, obtaining efficient no-regret algorithms under both full-information and bandit feedback, with provable sublinear regret guarantees. 1 Introduction Many sequential decision-making problems require a learner to repeatedly select actions from a continuous domain in response to an environment whose feedback is evolving over time. A natural and recurring structure in such settings is piecewise-continuous feedback: the reward function is piecewise-Lipschitz within regions of the action space, but changes abruptly across region boundaries. This structure arises organically in a broad range of applications—in principal-agent settings such as dynamic pricing [Balcan and Beyhaghi, 2024, Blum and Hartline, 2005] and contract design [Zhu et al., 2023], where the agent’s best response to the learner’s action creates sharp discontinuities in the reward function, and in algorithm configuration and parameter tuning [Balcan et al. , 2018, 2022, Balcan and Sharma, 2021, Gupta and Roughgarden, 2016], where an algorithm’s overall performance over instances as a function of its parameters is naturally piecewisecontinuous. Underlying all of these settings is a common computational primitive: proportional sampling from a dynamically evolving weight function. At each round, the learner must select an action with probability proportional to the cumulative rewards observed so far — a distribution that changes as new feedback arrives and the partition of the domain is refined. Proportional sampling is well-studied in static settings [Cochran, 1977, Brewer and Hanif, 1983, Cheung, 2014], and plays a central role in randomized algorithms [Motwani and Raghavan, 1995], online learning [Cesa-Bianchi and Lugosi, 2006], and importance sampling. However, the dynamic setting we consider is fundamentally different: each round introduces a new piecewisestructured update to the weight function, and as these updates accumulate over t rounds in a d-dimensional domain, the number of distinct regions induced by the partition grows as O(td ) . This combinatorial explosion makes naively maintaining the weight function and sampling from it computationally infeasible—and yet, to our knowledge, the question of how to do this efficiently has received almost no attention. Prior work on online learning with piecewise-structured rewards [Balcan et al., 2018] has focused primarily on regret minimization and sample complexity, either assuming access to a sampling oracle or ignoring computational efficiency altogether.

FAQs

What problem does the document address?

It addresses efficient online proportional sampling in a high-dimensional domain where the sampling distribution is defined by a dynamically evolving weight function induced by growing piecewise-structured partitions.

How does the work model the structure and changes over time?

The domain is partitioned each round into regions with piecewise-polynomial reward functions whose boundaries are defined by hyperplanes from fixed directions (e.g., axis-parallel hyperplanes). Cumulative weights from these updates refine the partition over time.

What theoretical results and learning applications are provided?

The document proves bounds on the depth of an efficient data structure under σ-smoothed adaptive adversaries (tight O(√σT)) and under random-order adversaries (O(log T)). It applies the framework to online learning with piecewise-structured rewards, obtaining efficient no-regret algorithms for both full-information and bandit feedback with sublinear regret.

Jul 16, 2026

Upload by Genevieve