5 papers
Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems
Zhengjia Zhuo, Viswanath Nagarajan
We consider the task of learning an (approximately) optimal policy for stochastic optimization problems where the true distributions are unknown. In each period, the algorithm play…
Distributionally Robust -of- Sequential Testing
Rayen Tan, Viswanath Nagarajan
The -of- testing problem involves performing independent tests sequentially, in order to determine whether/not at least tests pass. The objective is to minimize the e…
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 Simple Approximation Algorithm for Optimal Decision Tree
Zhengjia Zhuo, Viswanath Nagarajan
Optimal decision tree (\odt) is a fundamental problem arising in applications such as active learning, entity identification, and medical diagnosis. An instance of \odt is given by…
Identifying Approximate Minimizers under Stochastic Uncertainty
Hessa Al-Thani, Viswanath Nagarajan
We study a fundamental stochastic selection problem involving independent random variables, each of which can be queried at some cost. Given a tolerance level , the goal is…