A full explanation to Newcomb's paradox.

The main place where I disagree with you here is that you make such a big distinction between "really good at figuring out personalities" (3) and "running a full or partial simulation of the situation" (4). As your phrase "full or partial" suggests, simulations have a large range of fidelity. To illustrate a bit:

1. Fully precise physical sim, in a physics which allows such a thing. (Quantum mechanics poses some problems for this in our universe.)
2. Simulation which is highly accurate down to the atomic level.
3. Simulation which is highly accurate down to the cell level.
4. Simulation which (like many modern fluid dynamic sims) identifies regions which need to be run at higher/lower levels of fidelity, meaning that in principle, some areas can be simulated down to the atomic level, while other areas may be simulated at a miles-large scale.
5. Like the above, but also accelerated by using a neural network trained on the likely outcome of all the possible configurations, allowing the simulation to skip forward several steps at a time instead of going one step at a time.
6. ...

Somewhere on this continuum sits "really good at figuring out personalities". So where do you draw the line? If it's a matter of degree (as seems likely), how do you handle the shift from taking both boxes (as you claim is right for scenario 3) to one box (as you claim is right for scenario 4)?

In scenario 3, you would get 1k, while a 2-boxer would get 1m. You can comfort yourself in the "correctness" of your decision, but you're still losing out. More to the point, a rational agent would prefer to self-modify to be the sort of agent that gets 1m in this kind of situation, if possible. So, your decision theory is not stable under self-reflection.

(All of this is just based on my understanding, no guarantees.)

Miri is studying decision theory in the context of embedded agency [LW · GW]. Embedded Agency is all about what happens if you stop having a clear boundary between the agent and the environment (and you instead have the agent as part of the environment, hence embedded). Decision problems where the outcome depends on your behavior in counter-factual situations are just one of several symptoms that come from being an embedded agent.

In this context, we care about things like "if an agent is made of parts, how can she ensure her parts are aligned" or "if an agent creates copies of herself, how can we make sure nothing goes wrong" or "if the agent creates a successor agent, how can we make sure the successor agent does what the original agent wants".

I say this because (3) and (4) suddenly sound a lot more plausible when you're talking about something like an embedded agent playing a newcomb-like game (or a counter-factual mugging type game or a prisonner-dilemma type game) with a copy of itself.

Also, I believe Timeless Decision Theory is outdated. The important decision theories are Updateless Decision Theory and Functional Decision Theory. Afaik, UDT is both better and better formalized than TDT.

I think the idea is that the 4th scenario is the case, and you can’t discern whether you’re the real you or the simulated version, as the simulation is (near-) perfect. In that scenario, you should act in the same way that you’d want the simulated version to. Either (1) you’re a simulation and the real you just won $1,000,000; or (2) you’re the real you and the simulated version of you thought the same way that you did and one-boxed (meaning that you get $1,000,000 if you one-box.)

Under some circumstances, it seems that option 4 would result in the predictor trying to solve the Halting Problem since figuring out your best option may in effect involve simulating the predictor.

(Of course, you wouldn't be simulating the entire predictor, but you may be simulating enough of the predictor's chain of reasoning that the predictor essentially has to predict itself in order to predict you.)

Our estimate of which of the four possibilities is correct is conditional on us living in a universe where we observe that the predictor always guesses correctly.  If we put aside cheating (which should almost always be our guess if we observe something happening that seems to defy our understanding of how the universe operates) we should have massive uncertainty concerning how randomness and/or causation operates and thus not assign too low a probability to either (2) or (3).  

I've been confused by the traditional description of CDT failing at the Newcomb problem. I understand CDT to be something like "pick the choice with the highest expected value". This is how I imagine such an agent reasoning about the problem:

"If I one-box, then I get $0 with epsilon probability and $1m with one-minus-epsilon probably for an expected value of ~$1m. If I two-box, then I get $1k + $1m with epsilon probability and $1k with one-minus-epsilon probably for an expected value of ~$1k. One-boxing has higher expected value, so I should one-box."

How does the above differ from actual CDT? Most descriptions I've heard have the agent considering Omega's prediction as a single unknown variable with some distribution and then showing that this cancels out of the EV comparison, but what's wrong with considering the two EV calculations independently of each other and only comparing the final numbers?

Regarding the topic of your last paragraph (how can we have choice in a deterministic universe): this is something Gary Drescher discusses extensively in his book.

Firstly, he points out that determinism does not imply that choice is necessarily futile. Our 'choices' only happen because we engage in some kind of decision or choice making process. Even though the choice may be fixed in advance, it is still only taken because we engage in this process.

Additionally, Gary proposes the notion of a subjunctive means-end link (a means-end link is a method of identifying what is a means to a particular end), wherein one can act for the sake of what would have to be the case if they take a particular action. For example, in newcomb's problem one can pick just a single box because it would then have to be the case that the big box contains a million.

Putting these two things together might help make sense of how our actions affect these kind of thought experiments.