4 papers
Learning Markov Decision Processes under Fully Bandit Feedback
Zhengjia Zhuo, Anupam Gupta, Viswanath Nagarajan
A standard assumption in Reinforcement Learning is that the agent observes every visited state-action pair in the associated Markov Decision Process (MDP), along with the per-step…
A Little Clairvoyance Is All You Need
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Sh…
The Average-Value Allocation Problem
Kshipra Bhawalkar, Zhe Feng, Anupam Gupta +3
We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to a…
Maintaining Matroid Intersections Online
Niv Buchbinder, Anupam Gupta, Daniel Hathcock +2
Maintaining a maximum bipartite matching online while minimizing recourse/augmentations is a well studied problem, motivated by content delivery, job scheduling, and hashing. A bre…