This thesis studies Bayesian-robustness of algorithm design. The main perspective requires for a single fixed algorithm that its performance is an approximation of the optimal performance when its inputs are independent and identical draws (i.i.d.) from every unknown distribution which is an element of a known, large class of distributions....