Sharp Recovery Thresholds for Pairwise Self-Rewarded Softmax Updates

An evaluator can rank the optimal action above every alternative at every interior policy, yet a policy trained from sampled pairwise comparisons can still converge to a suboptimal action. We study this phenomenon for a finite softmax policy that samples two actions independently and updates its logits using their real-valued score difference. The evaluator may depend on the current policy, whereas the true rewards remain fixed. We control evaluator error by a uniform bound $ϵ$ on the policy-weighted standard deviation of bias and an $L$-Lipschitz bound on pairwise bias contrasts. We assume that the step sizes have a divergent sum and a finite sum of squares, and that the comparison noise has bounded conditional variance. Under these conditions, we derive the sharp worst-case recovery threshold ${\Psi }_L(\Delta )$, where $\Delta$ is the minimum true reward gap. Below this threshold, the sampled update converges almost surely to the optimal action from any full-support initialization. At the boundary $ϵ={\Psi }_L(\Delta )$ with $L>0$, recovery still holds for two or three actions, but the sampled update can fail with four or more actions even when the evaluator ranks the optimal action first at every interior policy. On such failure trajectories, the optimal action is compared infinitely often, yet the cumulative conditional drift toward it remains finite. A full-information update still recovers at this boundary for every finite action set, which shows that the sampled update can fail even when the evaluator retains enough information to identify the optimum. Finally, balanced queries with an importance-corrected update recover the optimal action for $ϵ<\Delta /2$ without a sensitivity bound, whereas evaluator feedback alone cannot guarantee identification when $ϵ\ge \Delta /2$.