How does prioritized experience replay choose transitions, and why does it need importance-sampling weights?

## The problem prioritisation attacks A replay buffer holds a large number of past transitions `(s, a, r, s')`. Drawing a batch uniformly gives every stored transition the same chance of contributing to an update, which means most gradient steps are spent on transitions the network already fits well and learns nothing from. The transitions that carry information are the ones where the current prediction is wrong -- and in many environments those are also the rarest. An industrial process log makes this concrete. Millions of logged transitions are ordinary steady-state operation; a few thousand are the machine-fault events whose values the agent most needs to get right. Under uniform sampling a fault transition is drawn about as often as its share of the buffer, so the network sees each one a handful of times and the informative signal is diluted. ## Scoring transitions by surprise The temporal-difference error of a stored transition is `delta = r + gamma * (bootstrapped next-state value) - Q(s,a)`: the gap between the target and the current prediction. Its magnitude is a cheap, already-computed proxy for how much this transition would change the network. Prioritized replay stores `|delta|` for each transition when it is used, and samples in proportion to a power of it. **Proportional prioritisation** sets `p_i = |delta_i| + epsilon`, with a small positive `epsilon` so no transition can reach probability zero and become unreachable forever. **Rank-based prioritisation** sets `p_i = 1 / rank(i)`, where rank orders transitions by `|delta_i|`. Rank-based is less sensitive to outliers, because a single enormous error only moves a transition to the top of the ordering rather than dominating the mass; proportional reacts more sharply to error magnitude. Sampling probability is `P(i) = p_i^alpha / sum_k p_k^alpha`. The priority exponent `alpha` controls how aggressive the scheme is: at zero it reduces exactly to uniform sampling, at one it samples in direct proportion to priority. Newly stored transitions are inserted with the maximum priority currently in the buffer, guaranteeing each is replayed at least once before its priority becomes meaningful. Because priorities change only when a transition is sampled and its error recomputed, most stored priorities are **stale** -- they reflect a network several thousand updates old. This is accepted as the price of not rescoring the whole buffer, and it is one reason the scheme is usually run with a moderate rather than an extreme priority exponent. ## Why an uncorrected scheme is biased The update rule is derived as a stochastic approximation: the expected update, taken over transitions drawn from the buffer's distribution, is what determines the fixed point the value function moves towards. Replace uniform draws with draws that favour high-error transitions and you change the expectation being approximated. The result is a value function fitted to a reweighted objective -- systematically better on the loud transitions, systematically worse elsewhere -- and this is a bias in the solution, not just extra variance. It compounds badly in a bootstrapped setting, where the wrong values become the targets for other states. ## The importance-sampling correction The standard remedy for expectations under the wrong distribution is to reweight samples by the ratio of the distribution you wanted to the one you drew from. Here the desired distribution is uniform, `1/N` over `N` stored transitions, and the actual one is `P(i)`, giving a ratio `1 / (N * P(i))`. Prioritized replay applies it with an exponent: `w_i = (1 / (N * P(i)))^beta` and multiplies the sampled transition's update by `w_i`. At `beta = 0` there is no correction; at `beta = 1` the correction is full and the expected update matches uniform sampling again. In practice the weights are divided by the largest weight in the batch, so they only ever scale updates down. That matters because full importance weights can be large and would otherwise inflate the effective step size and destabilise training. `beta` is annealed from a value well below one up to one over the course of training. The reasoning: early on, updates are wildly non-stationary anyway and the bias hardly matters compared with the speed gained from focusing on informative transitions, whereas near convergence the bias is exactly what determines the final solution, so that is when the correction must be complete. ## Failure modes to name in an interview **Stochastic rewards.** If a transition's target is intrinsically noisy, its error stays large no matter how well the network has learned it. Priority then tracks irreducible noise rather than learnable signal, and the buffer starves the rest of the data to resample noise. Environments with high reward variance are where prioritisation most often disappoints. **Priority staleness.** A transition whose error has since collapsed keeps a high stored priority until it is next drawn, and one whose error has grown stays buried. The scheme is always chasing an out-of-date picture of what is surprising. **Interaction with the effective step size.** The weights scale updates, so turning prioritisation on effectively changes the learning rate distribution across the batch. Reusing a learning rate tuned under uniform sampling is a common reason a first prioritised run looks worse than the baseline. **Bookkeeping cost.** Sampling proportionally to changing priorities over a large buffer is done with a segment-tree structure giving logarithmic sampling and updates; the overhead is real but modest compared with the network's forward and backward passes. ## The short version Prioritise by how wrong the prediction was, control the aggressiveness with a priority exponent, and pay for the skew with an importance-sampling weight whose exponent you anneal to one. Report the extra hyperparameters honestly -- they are the main cost of the method.