The parameters for determining the economic order quantity (EOQ) are often not well known or may change between order cycles in an unpredictable manner. We propose a distribution-free method to determine a relatively robust EOQ that guarantees optimal cost performance relative to the ex-post optimal cost that could have been achieved with perfect information about the unknown parameter values. Furthermore, we determine optimal Laplacian confidence intervals for the parameters which lead to a guaranteed in-model robustness of about 37.8% of the optimum when demand, holding cost, and order cost are unknown, and 81.6% when only one of these parameters, such as demand, is unknown. Accordingly, when all parameters are unknown, the optimal Laplacian confidence intervals vary by 79.5% around the respective central values, and when only one parameter is unknown, the remaining confidence interval varies by 86.6% around its central value.