Learning to Search Better Than Your Teacher

Understand

Methods for learning to search for structured prediction typically imitate a reference policy, with existing theoretical guarantees demonstrating low regret compared to that reference.

• This is unsatisfactory in many applications where the reference policy is suboptimal and the goal of learning is to improve upon it.
• Can learning to search work even when the reference is poor? We provide a new learning to search algorithm, LOLS, which does well relative to the reference policy, but additionally guarantees low regret compared to deviations from the learned policy: a local-optimality guarantee.
• Consequently, LOLS can improve upon the reference policy, unlike previous algorithms.