7 papers
Optimally Pacing Budget Spending and Learning
Mark Braverman, Jingyi Liu, Jieming Mao +2
We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given a…
Coherence Mechanisms for Provable Self-Improvement
Mehryar Mohri, Jon Schneider, Yifan Wu
Self-improvement is a critical capability for large language models and other intelligent systems, enabling them to refine their behavior and internal consistency without external…
A New Benchmark for Online Learning with Budget-Balancing Constraints
Mark Braverman, Jingyi Liu, Jieming Mao +2
The adversarial Bandit with Knapsack problem is a multi-armed bandits problem with budget constraints and adversarial rewards and costs. In each round, a learner selects an action…
Best of Both Worlds: Regret Minimization versus Minimax Play
Adrian Müller, Jon Schneider, Stratis Skoulakis +2
In this paper, we investigate the existence of online learning algorithms with bandit feedback that simultaneously guarantee regret compared to a given comparator strategy,…
Rate-Preserving Reductions for Blackwell Approachability
Christoph Dann, Yishay Mansour, Mehryar Mohri +2
Abernethy et al. (2011) showed that Blackwell approachability and no-regret learning are equivalent, in the sense that any algorithm that solves a specific Blackwell approachabilit…
Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions
Rachitesh Kumar, Jon Schneider, Balasubramanian Sivan
Learning to bid in repeated first-price auctions is a fundamental problem at the interface of game theory and machine learning, which has seen a recent surge in interest due to the…
Optimal cross-learning for contextual bandits with unknown context distributions
Jon Schneider, Julian Zimmert
We consider the problem of designing contextual bandit algorithms in the ``cross-learning'' setting of Balseiro et al., where the learner observes the loss for the action they play…