4 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…
Additively Competitive Secretaries
Mohammad Mahdian, Jieming Mao, Enze Sun +2
In the secretary problem, a set of secretary candidates arrive in a uniformly random order and reveal their values one by one. A company, who can only hire one candidate and hopes…
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…
On Simultaneous Two-player Combinatorial Auctions
Mark Braverman, Jieming Mao, S. Matthew Weinberg
We consider the following communication problem: Alice and Bob each have some valuation functions and over subsets of items, and their goal is to part…