Open Problem: First-Order Regret Bounds for Contextual Bandits - Agarwal, Alekh; Krishnamurthy, Akshay; Langford, John; Luo, Haipeng; Schapire, Robert E. (Conference on Learning Theory, 2017)
We describe two open problems related to first order regret bounds for contextual bandits. The first asks for an algorithm with a regret bound of where there are actions, policies, and is the cumulative loss of the best policy. The second asks for an optimization-oracle-efficient algorithm with regret . We describe some positive results, such as an inefficient algorithm for the second problem, and some partial negative results.