A popular assumption for out-of-distribution generalization is that the\ntraining data comprises sub-datasets, each drawn from a distinct distribution;\nthe goal is then to "interpolate" these distributions and "extrapolate" beyond\nthem -- this objective is broadly known as domain generalization. A common\nbelief is that ERM can interpolate but not extrapolate and that the latter is\nconsiderably more difficult, but these claims are vague and lack formal\njustification. In this work, we recast generalization over sub-groups as an\nonline game between a player minimizing risk and an adversary presenting new\ntest distributions. Under an existing notion of inter- and extrapolation based\non reweighting of sub-group likelihoods, we rigorously demonstrate that\nextrapolation is computationally much harder than interpolation, though their\nstatistical complexity is not significantly different. Furthermore, we show\nthat ERM -- or a noisy variant -- is provably minimax-optimal for both tasks.\nOur framework presents a new avenue for the formal analysis of domain\ngeneralization algorithms which may be of independent interest.\n