  We extend the variational approach to regularity for optimal transport maps
initiated by Goldman and the first author to the case of general cost
functions. Our main result is an $\epsilon$-regularity result for optimal
transport maps between H\"older continuous densities slightly more quantitative
than the result by De Philippis-Figalli. One of the new contributions is the
use of almost-minimality: if the cost is quantitatively close to the Euclidean
cost function, a minimizer for the optimal transport problem with general cost
is an almost-minimizer for the one with quadratic cost. This further highlights
the connection between our variational approach and De Giorgi's strategy for
$\epsilon$-regularity of minimal surfaces.
