Improved learning method reduces regret in stochastic optimization problems
Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems
Machine Learning
Summary
The paper tackles the challenge of learning the best way to solve problems involving uncertainty, where you only get partial feedback on decisions. The authors develop an algorithm that handles many types of problems where outcomes depend on random events and uses a mathematical measure called Hellinger distance to improve learning accuracy. Their method achieves nearly the best possible performance over time, outperforming previous approaches. This improvement helps in areas like decision-making under uncertainty and selecting optimal actions with limited information.
What this means in practice
- •For online advertising teams: Optimize ad selection strategies by efficiently learning from partial feedback on which ads perform best.
- •For supply chain planners: Better decide which uncertain supplies to order or test when only partial outcome information is available.
Authors
Zhengjia Zhuo, Viswanath Nagarajan
Abstract
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 plays a policy for the stochastic problem and observes semi-bandit feedback, i.e., it only receives new samples from the random variables that were selected by the policy. We obtain an algorithm that works for a large class of ``monotone'' stochastic problems, including prophet inequality, Pandora's box, series testing, stochastic knapsack and stochastic matching. We obtain $\tilde{O}(\sqrt{nkT})$ regret for ``weakly'' monotone problems and $\tilde{O}(\sqrt{nT})$ regret for ``strongly'' monotone problems, where $T$ is the number of periods, $n$ is the problem dimension (number of random variables) and $k$ is the maximum support size of any random variable. This improves over previous regret bounds by a $\sqrt{n}$ factor. In fact, our dependence on $n$ and $T$ is the best-possible due the $Ω(\sqrt{nT})$ lower bound for multi-armed-bandits. Our main technique is the use of Hellinger distance in bounding the ``error'' between the true and learned distributions, and the use of a constant-factor chain rule for the Hellinger distance of dependent random variables.