Although failures are to be avoided by all means in safety-critical robot applications, there exist a wide range of scenarios in which failing is undesired, but not catastrophic. Because failures are informative about what should be avoided, we treat them as an additional learning source, and develop optimization algorithms that allow failures only when the information gain is worth the cost.