It isn’t clear why or in what sense such systems do better than deterministic systems built in some other way.

A specialized not-obviously-CSA for a specific problem can be better than any known CSA. Is it useful to model array-sorting algorithms as incrementally increasing some kind of "utility functions"? Shouldn't you narrow the problem domain a bit, for your statement to hold? But if we narrow it in the obvious way, we get tree-search with heuristics and there you have your answers nicely laid out mathematically.

without allowing predictions like “if I take action a_2, then the laws of physics will have been broken”.

Please exhibit a model agent (however simple) that can logically arrive at such a prediction, and then experience some kind of paradox/problem because of it. I say there's no way: the former makes the latter impossible.