daf8364f0715a41a469c677c0adc4754-Supplemental-Conference.pdf

Since weak learners perform only marginallybetter than random guesses, such subroutines constitute aweakerassumption than the availability of an accurate supervised learning oracle. Weprovethat the sample complexity and running time bounds of the proposed method do not explicitly dependonthenumberofstates. While existing results on boosting operate on convex losses, the value function over policies is non-convex.