Abstract
We address the online linear optimization problem when the decision set isthe entire $\{0,1\}^n$ hypercube. It was previously unknown if it is possibleto run the exponential weights algorithm on this decision set in polynomialtime. In this paper, we show a simple polynomial time algorithm which isequivalent to running exponential weights on $\{0,1\}^n$. In the FullInformation setting, we show that our algorithm is equivalent to both Exp2 andOnline Mirror Descent with Entropic Regularization. This enables us to prove atight regret bound for Exp2 on $\{0,1\}^n$. In the Bandit setting, we show thatour algorithm is equivalent to both Exp2 and OMD with Entropic Regularizationas long as they use the same exploration distribution. In addition, we show areduction from the $\{-1,+1\}^n$ hypercube to the $\{0,1\}^n$ hypercube for thefull information and bandit settings. This implies that we can also runexponential weights on $\{-1,+1\}^n$ in polynomial time, addressing the problemof sampling from the exponential weights distribution in polynomial time, whichwas left as an open question in Bubeck et al. (2012).