Paper deep dive
Demystifying the unreasonable effectiveness of online alignment methods
Enoch Hyunwook Kang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 6/21/2026, 9:20:41 AM
Summary
The paper investigates the discrepancy between the empirical success of greedy online alignment methods (like RLHF and DPO) and their theoretical $O(\log T)$ KL-regularized regret bounds. The authors propose a 'temperature-zero regret' criterion, which evaluates only the top-ranked response at inference time, effectively separating the statistical cost of learning from the stochasticity induced by the KL-regularizer. They prove that under this decision-centric notion, standard greedy online alignment achieves constant $O(1)$ cumulative regret, providing a sharper theoretical explanation for the efficiency of these methods.
Entities (6)
Relation Signals (3)
Online RLHF → isa → Greedy Online Alignment Method
confidence 100% · standard greedy online alignment methods, including online RLHF and online DPO
Online DPO → isa → Greedy Online Alignment Method
confidence 100% · standard greedy online alignment methods, including online RLHF and online DPO
Temperature-zero regret → providessharperexplanationfor → Online RLHF
confidence 90% · By isolating the cost of identifying the best response from the stochasticity induced by regularization, our results provide a sharper theoretical explanation for the practical superb efficiency of greedy alignment.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Iterative alignment methods based on purely greedy updates are remarkably effective in practice, yet existing theoretical guarantees of \(O(\log T)\) KL-regularized regret can seem pessimistic relative to their empirical performance. In this paper, we argue that this mismatch arises from the regret criterion itself: KL-regularized regret conflates the statistical cost of learning with the exploratory randomization induced by the softened training policy. To separate these effects, we study the traditional temperature-zero regret criterion, which evaluates only the top-ranked response at inference time. Under this decision-centric notion of performance, we prove that standard greedy online alignment methods, including online RLHF and online DPO, achieve constant \((O(1))\) cumulative regret. By isolating the cost of identifying the best response from the stochasticity induced by regularization, our results provide a sharper theoretical explanation for the practical superb efficiency of greedy alignment.
Tags
Links
- Source: https://arxiv.org/abs/2604.17207v1
- Canonical: https://arxiv.org/abs/2604.17207v1
Trouble viewing inline? Open PDF directly →
Full Text
139,349 characters extracted from source content.
Expand or collapse full text
Demystifying the Unreasonable Effectiveness of Online Alignment Methods Enoch Hyunwook Kang Foster School of Business University of Washington ehwkang@uw.edu Abstract Iterative alignment methods based on purely greedy updates are remarkably effective in practice, yet existing theoretical guarantees of O(logT)O( T) KL-regularized regret can seem pessimistic relative to their empirical performance. In this paper, we argue that this mismatch arises from the regret criterion itself: KL-regularized regret conflates the statistical cost of learning with the exploratory randomization induced by the softened training policy. To separate these effects, we study the traditional temperature-zero regret criterion, which evaluates only the top-ranked response at inference time. Under this decision-centric notion of performance, we prove that standard greedy online alignment methods, including online RLHF and online DPO, achieve constant (O(1))(O(1)) cumulative regret. By isolating the cost of identifying the best response from the stochasticity induced by regularization, our results provide a sharper theoretical explanation for the practical superb efficiency of greedy alignment. 1 Introduction A common online, i.e., iterative alignment loop is strikingly simple: deploy the current model, sample a small slate of responses, collect preference feedback, refit a preference model on the accumulated data, and redeploy the greedily improved policy induced by that model. This loop and its variants underlie much of modern preference-based post-training, and they have also become a central object of recent alignment theory (Zhu et al., 2023; Xiong et al., 2024; Ye et al., 2024; Zhao et al., 2024). The theoretical picture has sharpened substantially in the last two years. Recent analyses show that the regularizer can fundamentally change the statistical difficulty of learning, yielding logarithmic online regret in reward-based settings where one would classically expect slower rates (Zhao et al., 2024, 2025a, 2025b). More recent work further shows that these fast orders need not rely on optimistic or pessimistic confidence constructions: in both Bradley–Terry and more general preference models, purely greedy sampling can already attain the same O(logT)O( T) regret in terms of the KL-regularized regret criterion (Wu et al., 2025). Follow-up analyses also emphasize that on-policy coverage can improve over iterations, that sampling and reference choices shape iterative alignment dynamics, and that similarly fast phenomena can persist under richer, potentially intransitive preference structures (Kim et al., 2026; Chen et al., 2026; Lee et al., 2026). Accordingly, the point of this paper is not to claim that greedy alignment is efficient per se; that conclusion is already well supported by the recent literature. The question we ask is subtler: efficient with respect to what? Under the standard policy-based criterion, KL-regularized regret blends two distinct components of suboptimality. First, the learner may not yet have enough information to identify which response is truly top-ranked under the latent reward, so regret reflects the statistical cost of exploration and learning. Second, even after the correct top-ranked response has effectively been identified, the finite-temperature KL-tilted policy continues to randomize away from it, contributing regret that is induced by the regularizer rather than by continued uncertainty. To understand whether greedy alignment has learned the right best response, these two effects should be separated. Once evaluation is restricted to the first component of regret, greedy alignment begins to look familiar from a different literature. In contextual bandits, successful greedy learning has long been associated with the presence of implicit exploration supplied by the data distribution itself, via covariate diversity, smoothing, favorable margins, or local anti-concentration. Under such conditions, greedy procedures can achieve no-regret and polylogarithmic regret, and in favorable margin regimes even bounded regret (Hao et al., 2020; Papini et al., 2021b; Bastani et al., 2021; Tirinzoni et al., 2022; Kannan et al., 2018; Raghavan et al., 2023; Kim and Oh, 2024). Our key intuition is that KL-regularized alignment exhibits a closely related phenomenon once evaluation is focused on the decision-error component of regret, rather than on the stochasticity of the softened policy itself. Following this idea, in this paper, we study the standard greedy alignment loop under the traditional temperature-zero regret criterion. Let π0(⋅∣x) _0(· x) be the reference policy, and for any reward estimate R, define the induced KL-tilted policy by πR(a∣x)∝π0(a∣x)eηR(x,a), _R(a x) _0(a x)e^η R(x,a), where η is the regularization parameter, and define aR(x)∈argmaxa∈supp(π0(⋅∣x))R(x,a),a_R(x)∈ _a ( _0(· x))R(x,a), where supp(π0(⋅∣x))supp( _0(· x)) denotes the support of the reference policy. If R⋆R denotes the true latent reward, if d0d_0 denotes the context distribution, and if we write a⋆≔aR⋆a a_R and π⋆≔πR⋆π _R , then the one-step temperature-zero regret is X∼d0[R⋆(X,a⋆(X))−R⋆(X,aR(X))],E_X d_0\! [R (X,a (X))-R (X,a_R(X)) ], whereas the regret notion in (Wu et al., 2025) is the one-step KL-regularized regret, i.e., X∼d0[ _X d_0\! [ (A∼π⋆(⋅∣X)[R⋆(X,A)]−1ηKL(π⋆(⋅∣X)∥π0(⋅∣X))) (E_A π (· X)[R (X,A)]- 1ηKL\! (π (· X)\,\|\, _0(· X) ) ) −(A∼πR(⋅∣X)[R⋆(X,A)]−1ηKL(πR(⋅∣X)∥π0(⋅∣X)))]. - (E_A _R(· X)[R (X,A)]- 1ηKL\! ( _R(· X)\,\|\, _0(· X) ) ) ]. That is, temperature-zero regret is just a traditional regret notion used in the bandit setting, which asks only whether the learned reward induces the correct top-ranked response, whereas KL-regularized regret also charges the deliberate finite-temperature randomization of the deployed KL-tilted policy. Main contributions. • We formalize temperature-zero regret, in which only the final top-ranked response matters. • We theoretically and empirically demonstrate that the standard greedy online alignment loop achieves bounded (O(1)O(1)) cumulative temperature-zero regret. This yields a sharper interpretation of prior logarithmic-regret results, such as Wu et al. (2025): after finitely many rounds, the O(log(T))O( (T)) KL-regularized regret is driven entirely by the randomization of the KL-regularized policy itself, not by continued failure to identify the correct top-ranked response. The remainder of the paper is organized as follows. In Section 2, we formalize the interaction model for iterative alignment. Section 3 describes the standard greedy alignment procedures, including online RLHF and DPO. In Section 4, we state and prove our main theoretical results regarding bounded temperature-zero regret. Finally, Section 5 provides empirical validation of these results through a controlled simulation. Due to page limits, we discuss related works in Appendix A. 2 Setup 2.1 Contexts, actions, and reference policy Let X denote a context space (prompts, queries, or tasks), and let A denote an action space (responses). We allow A to be very large or infinite. Contexts arrive i.i.d. from an unknown distribution d0d_0 on X: X1,X2,…∼i.i.d.d0.X_1,X_2,… i.i.d. d_0. We are also given a fixed reference policy π0:→Δ(), _0:X→ (A), which represents the pre-alignment model, e.g. an SFT checkpoint. As in standard KL-regularized alignment, we restrict attention to policies that are absolutely continuous with respect to π0 _0: Π≔π:→Δ():π(⋅∣x)≪π0(⋅∣x)for every x∈. \π:X→ (A):π(· x) _0(· x)\ for every x \. This means that aligned policies are obtained by reweighting the reference model rather than assigning mass to actions that the reference policy never proposes. 2.2 Online preference feedback Fix a slate size K≥2K≥ 2. At round t, after observing the current context xtx_t, the deployed policy πt _t generates a slate t=(at,1,…,at,K)∈K,at,k∼i.i.d.πt(⋅∣xt),k=1,…,K.a_t=(a_t,1,…,a_t,K) ^K, a_t,k i.i.d. _t(· x_t), k=1,…,K. This is the mathematical idealization of the common “generate K candidates from the current model and ask for the favorite one” protocol. A human annotator, panel, or preference model then returns a preferred index yt∈1,…,K.y_t∈\1,…,K\. We model the feedback through an unknown conditional choice distribution P⋆:×K→Δ(1,…,K),P :X×A^K→ (\1,…,K\), so that yt∼P⋆(⋅∣xt,t).y_t P (· x_t,a_t). When K=2K=2, this reduces to pairwise preference feedback. Larger K covers best-of-K or slate-level preference collection. After t rounds, the accumulated dataset is t=(xs,as,1,…,as,K,ys):1≤s≤t.D_t= \(x_s,a_s,1,…,a_s,K,y_s):1≤ s≤ t \. 3 Greedy alignment procedures 3.1 Reward functions and empirical preference fitting A reward function is a measurable function R:×→ℝ.R:X×A . Let ℱF denote the candidate reward class used by the learner. We do not impose any statistical assumptions on ℱF yet; the theory section will introduce additional structure only when needed. Given a reward function R∈ℱR and a slate =(a1,…,aK),a=(a_1,…,a_K), define the reward vector R(x,)≔(R(x,a1),…,R(x,aK))∈ℝK.v_R(x,a) (R(x,a_1),…,R(x,a_K) ) ^K. Following standard preference-model training, the learner associates to R the multinomial logit choice model PR(y=k∣x,)=exp(R(x,ak))∑ℓ=1Kexp(R(x,aℓ)),k=1,…,K.P_R(y=k x,a)= (R(x,a_k)) _ =1^K (R(x,a_ )), k=1,…,K. Define the corresponding multinomial log-loss ℓ(,y)≔log(∑k=1Kevk)−vy,∈ℝK,y∈1,…,K. (v,y) \! ( _k=1^Ke^v_k )-v_y, ^K,\ y∈\1,…,K\. Thus the empirical preference risk after t rounds is ℒ^t(R)≔1t∑s=1tℓ(R(xs,s),ys)=1t∑s=1t[log(∑k=1KeR(xs,as,k))−R(xs,as,ys)]. L_t(R) 1t _s=1^t \! (v_R(x_s,a_s),y_s )= 1t _s=1^t [ \! ( _k=1^Ke^R(x_s,a_s,k) )-R(x_s,a_s,y_s) ]. (1) At the end of round t≥1t≥ 1, the ERM fits the current reward estimate by empirical risk minimization: R^t∈argminR∈ℱℒ^t(R). R_t∈ _R L_t(R). (2) We also set R^0≡0 R_0≡ 0, so that the initial policy equals the reference model. 3.2 Greedy policy improvement Fix a tilt parameter η>0η>0. Given the estimated reward R^t R_t, the next deployed policy is the KL-tilted exponential reweighting of the reference policy: πt+1(a∣x)=π0(a∣x)exp(ηR^t(x,a))∫π0(a′∣x)exp(ηR^t(x,a′))a′. _t+1(a x)= _0(a x) \! (η\, R_t(x,a) ) _A _0(a x) \! (η\, R_t(x,a ) )\,da . (3) We initialize π1←π0. _1← _0. Equation (3) is exactly the one-step greedy KL-regularized improvement of the current reward estimate. Indeed, for each fixed context x, πt+1(⋅∣x) _t+1(· x) is the unique maximizer over π(⋅∣x)≪π0(⋅∣x)π(· x) _0(· x) of A∼π(⋅∣x)[R^t(x,A)]−1ηKL(π(⋅∣x)∥π0(⋅∣x)).E_A π(· x)[ R_t(x,A)]- 1ηKL\! (π(· x)\,\|\, _0(· x) ). Thus the learner is greedy with respect to the current reward estimate, while the KL term keeps deployment close to the reference model. 3.3 The greedy online RLHF loop (Wu et al., 2025) Putting the pieces together, the greedy online alignment loop proceeds as follows. Initialize R^0≡0,π1←π0,0←∅. R_0≡ 0, _1← _0, _0← . For each round t=1,…,Tt=1,…,T: 1. Observe a context xt∼d0x_t d_0. 2. Sample a slate at,1,…,at,K∼i.i.d.πt(⋅∣xt).a_t,1,…,a_t,K i.i.d. _t(· x_t). 3. Obtain preference feedback yt∼P⋆(⋅∣xt,t).y_t P (· x_t,a_t). 4. Update the dataset t←t−1∪(xt,at,1,…,at,K,yt).D_t _t-1∪\(x_t,a_t,1,…,a_t,K,y_t)\. 5. Fit R^t R_t by solving (2). 6. Deploy the next policy πt+1 _t+1 via (3). This is the concrete online alignment rule studied throughout the paper: repeated preference collection under the current policy, repeated reward-model fitting on the cumulative dataset, and repeated greedy redeployment relative to a fixed reference model. 3.4 Equivalent policy-space view: greedy online DPO (Guo et al., 2024b) When the feedback is pairwise (K=2K=2), the same greedy loop can be written directly in policy coordinates in the style of direct preference optimization (DPO). For any reward class ℱF, define the induced policy class ΠℱDPO≔πR:R∈ℱ, _F^DPO \ _R:R \, where πR _R is the KL-tilted policy from (3). Given pairwise data (xs,as,1,as,2,ys),ys∈1,2,(x_s,a_s,1,a_s,2,y_s), y_s∈\1,2\, define the exact online DPO empirical loss of a policy π∈ΠℱDPOπ∈ _F^DPO by ℒ^tDPO(π)≔1t∑s=1t−logσ(1η[logdπ(⋅∣xs)dπ0(⋅∣xs)(as,ys)−logdπ(⋅∣xs)dπ0(⋅∣xs)(as,3−ys)]), L^DPO_t(π) 1t _s=1^t- σ\! ( 1η [ dπ(· x_s)d _0(· x_s)(a_s,y_s)- dπ(· x_s)d _0(· x_s)(a_s,3-y_s) ] ), (4) where σ(u)≔(1+e−u)−1σ(u) (1+e^-u)^-1. The exact online DPO update is then π^t∈argminπ∈ΠℱDPOℒ^tDPO(π),πt+1←π^t π_t∈ _π∈ _F^DPO L^DPO_t(π), _t+1← π_t (5) This is not a different algorithm. Indeed, if π=πRπ= _R, then for every context x and action a, 1ηlogdπR(⋅∣x)dπ0(⋅∣x)(a)=R(x,a)−1ηlog∫π0(a′∣x)eηR(x,a′)a′. 1η d _R(· x)d _0(· x)(a)=R(x,a)- 1η \! _A _0(a x)e^η R(x,a )\,da . Hence the normalization term cancels in pairwise differences, and for every realized example (xs,as,1,as,2,ys)(x_s,a_s,1,a_s,2,y_s), 1η[logdπR(⋅∣xs)dπ0(⋅∣xs)(as,ys)−logdπR(⋅∣xs)dπ0(⋅∣xs)(as,3−ys)]=R(xs,as,ys)−R(xs,as,3−ys). 1η [ d _R(· x_s)d _0(· x_s)(a_s,y_s)- d _R(· x_s)d _0(· x_s)(a_s,3-y_s) ]=R(x_s,a_s,y_s)-R(x_s,a_s,3-y_s). Therefore −logσ(R(xs,as,ys)−R(xs,as,3−ys))=log(eR(xs,as,1)+eR(xs,as,2))−R(xs,as,ys),- σ\! (R(x_s,a_s,y_s)-R(x_s,a_s,3-y_s) )= \! (e^R(x_s,a_s,1)+e^R(x_s,a_s,2) )-R(x_s,a_s,y_s), so ℒ^tDPO(πR)=ℒ^t(R)when K=2. L^DPO_t( _R)= L_t(R) K=2. 4 Temperature-zero regret of greedy online alignment methods We now formally introduce the temperature-zero regret criterion and analyze the greedy online alignment methods from Section 3. For the rest of this section, we assume that A is a separable metric space and interpret supp(π0(⋅∣x))supp( _0(· x)) as the topological support of π0(⋅∣x) _0(· x). Throughout this section, we work with π0 _0-centered rewards. This is without loss of generality: subtracting, for each context x, an a-independent constant from a reward leaves the MNL choice probabilities, the KL-tilted policy, and the temperature-zero selector unchanged; see Lemma 11 of Appendix D. 4.1 Temperature-zero regret For any centered reward R:×→ℝR:X×A , fix a measurable selector aR(x)∈argmaxa∈supp(π0(⋅∣x))R(x,a).a_R(x)∈ _a ( _0(· x))R(x,a). This measurable tie-breaking convention is used throughout. For truth p∈p , write ap(x)≔aRp(x).a_p(x) a_R_p(x). For any centered reward R, define the truth-centered expected one-step temperature-zero regret under truth p by p(R)≔X∼d0[Rp(X,ap(X))−Rp(X,aR(X))].G_p(R) _X d_0 [R_p (X,a_p(X) )-R_p (X,a_R(X) ) ]. (6) A learning rule A produces reward estimates R^0,R^1,R^2,…, R_0 A, R_1 A, R_2 A,…, where R^t R_t A is fitted from the first t rounds of data and is deployed on round t+1t+1. Its expected cumulative temperature-zero regret under truth p∈p is Regret0,p(T)≔∑t=0T−1p[p(R^t)].Regret_0,p A(T) _t=0^T-1E_p [G_p( R_t A) ]. (7) Remark 1. Temperature-zero regret is simply a traditional notion of regret commonly used in the bandit literature. By contrast, the KL-regularized regret studied in Wu et al. (2025) evaluates the full finite-temperature policy itself, and therefore also counts loss coming from randomization. 4.2 Model class Fix a compact class of possible truths P. Each p∈p induces a centered measurable reward function Rp:×→ℝ.R_p:X×A . Let ℱ≔Rp:p∈.F_P \R_p:p \. Under truth p, the preference feedback on a realized slate =(a1,…,aK)∈Ka=(a_1,…,a_K) ^K follows the MNL model PRp(y=k∣x,)=exp(Rp(x,ak))∑ℓ=1Kexp(Rp(x,aℓ)),k=1,…,K.P_R_p(y=k x,a)= (R_p(x,a_k)) _ =1^K (R_p(x,a_ )), k=1,…,K. For x∈x , write Sx≔supp(π0(⋅∣x)).S_x ( _0(· x)). We impose the following regularity conditions. (C1) Compact continuous reward class. The induced reward class ℱF_P is compact under ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0). Moreover, for every R∈ℱR _P, the map a⟼R(x,a)a R(x,a) is continuous on SxS_x for d0d_0-a.e. x∈x . (C2) Reward gap on P. There exists Δmin>0 _ ^P>0 such that for every truth p∈p , ap(X)a_p(X) is unique and Rp(X,ap(X))−supa∈SX,a≠ap(X)Rp(X,a)≥Δmind0-a.s.R_p (X,a_p(X) )- _a∈ S_X,\ a≠ a_p(X)R_p(X,a)≥ _ ^P d_0-a.s. Define also Δmax≔supp∈supx∈supa∈Sx(Rp(x,ap(x))−Rp(x,a)). _ ^P _p _x _a∈ S_x (R_p(x,a_p(x))-R_p(x,a) ). Condition (C1) is a compactness-based support-local regularity condition that subsumes the finite-class and bounded-covering-number assumptions commonly used in recent online alignment analyses (Xiong et al., 2024; Ye et al., 2024; Wu et al., 2025). Continuity in Condition (C1) is mild for standard parametric reward classes, including bounded-parameter linear and neural reward families with continuous activations; see Appendix D.1. Condition (C2) is a standard111Mathematically, it can be interpreted as a selector-stability assumption: it guarantees that the top-ranked action is locally robust to small reward perturbations. In bandit problems, such positive gaps typically appear with logarithmic instance-dependent regret, and bounded or sub-logarithmic regret arises only under additional self-exploration structures, such as optimal-arm spanning, HLS, covariate diversity, smoothed contexts, or local anti-concentration (Hao et al., 2020; Papini et al., 2021b; Tirinzoni et al., 2023; Bastani et al., 2021; Kannan et al., 2018; Raghavan et al., 2023; Kim and Oh, 2024).222Practically, Wang et al. (2024) reports low annotator agreement in practice, and discusses adaptive margins based on preference strength as the solution in practice. Qin et al. (2024); Kim et al. (2024) argue that preference pairs have heterogeneous strength and that explicit margin information improves reward models and aligned policies.reward modeling setup in practice in alignment literature (Wang et al., 2024), as we can often collapse imperceptible quality differences, since preference data exhibit heterogeneous strength and ambiguous low-margin pairs are often unreliable or uninformative (Qin et al., 2024; Kim et al., 2024). For any centered reward R, define the truth-centered population loss under truth p by ℒp(R)≔[ℓ(R,Y)],L_p(R) [ (v_R,Y) ], (8) where X∼d0,=(A1,…,AK)∼π0(⋅∣X)⊗K,Y∼PRp(⋅∣X,),X d_0, =(A_1,…,A_K) _0(· X) K, Y P_R_p(· X,A), and R≔(R(X,A1),…,R(X,AK)).v_R (R(X,A_1),…,R(X,A_K) ). For the rest of this section, we instantiate the ERM greedy learner from Section 3 with ℱ=ℱF=F_P. By Condition (C1) and continuity of R↦ℒ^t(R)R L_t(R) under ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0), the ERM objective in (2) admits a minimizer for each t≥1t≥ 1; fix a measurable ERM selection rule and continue to write R^t R_t for the resulting reward estimates. 4.3 Bounded cumulative regret in online RLHF Condition (C1) implies the uniform envelope B≔supR∈ℱ‖R‖∞,supp(π0)<∞.B_P _R _P\|R\|_∞,supp( _0)<∞. In particular, Δmax≤2B. _ ^P≤ 2B_P. Since every reward function in ℱF_P is bounded by B_P on supp(π0)supp( _0), Lemma 15 in Appendix D implies that the deployed policy satisfies β−1≤dπt+1(⋅∣x)dπ0(⋅∣x)(a)≤β,β≔e2ηB,β^-1≤ d _t+1(· x)d _0(· x)(a)≤β, β e^2η B_P, for d0d_0-a.e. x and π0(⋅∣x) _0(· x)-a.s. a. Lemma 2 (Automatic isolation of positive regret on ℱF_P). Assume (C1)–(C2). Then there exists a constant εiso>0 _iso^P>0 such that for every p,q∈p,q , p(Rq)∈0∪[εiso,∞).G_p(R_q)∈\0\∪[ _iso^P,∞). Lemma 3 (Zero truth-centered loss identifies the reward on the reference support). Assume (C1). Then for every truth p∈p and every R∈ℱR _P, ℒp(R)=ℒp(Rp)⟹R(x,a)=Rp(x,a)∀a∈Sx,d0-a.e. x.L_p(R)=L_p(R_p) R(x,a)=R_p(x,a) ∀ a∈ S_x, d_0-a.e.\ x. In particular, p(R)=0.G_p(R)=0. Lemma 4 (Automatic verification of the truth-centered loss gap). Assume (C1)–(C2). Fix any ε0>0 _0>0. Then there exists a finite constant γ,ε0>0 _P, _0>0 such that for every pair p,q∈p,q , p(Rq)≥ε0⟹ℒp(Rq)−ℒp(Rp)≥γ,ε0.G_p(R_q)≥ _0 _p(R_q)-L_p(R_p)≥ _P, _0. Theorem 5 (Bounded O(1)O(1) regret for online RLHF). Assume (C1)–(C2). Then supp∈supT≥1Regret0,pERM(T)<∞. _p _T≥ 1Regret_0,p^ERM(T)<∞. More precisely, set ε0≔εiso, _0 _iso^P, let γ≔β−Kγ,ε0,Nγ≔(ℱ,γ/32,∥⋅∥∞,supp(π0)),cγ≔γ2128(logK+2B)2γ β^-K _P, _0, N_γ \! (F_P,γ/32,\|·\|_∞,supp( _0) ), c_γ γ^2128( K+2B_P)^2 where (ℱ,ε,∥⋅∥)N(F, ,\|·\|) denotes the ε -covering number of ℱF under the displayed metric. Then supp∈supT≥1Regret0,pERM(T)≤Δmax(1+⌈1cγlog(2Nγ)⌉+1ecγ−1). _p _T≥ 1Regret_0,p^ERM(T)≤ _ ^P (1+ 1c_γ (2N_γ) + 1e^c_γ-1 ). Proof sketch.. Conditions (C1)–(C2) imply that, within ℱF_P, positive temperature-zero regret is isolated away from zero. Lemma 3 shows that zero excess population loss can occur only when the learned reward agrees with the truth on the entire reference support, hence only when the temperature-zero regret is zero. Compactness and continuity therefore turn any fixed positive regret level into a fixed positive population-loss gap. Since the KL tilt yields a uniform likelihood-ratio lower bound with respect to π0 _0, the same fixed loss gap persists under the on-policy slate distribution actually observed, up to a constant factor. Exact ERM and uniform concentration then give an exponentially small probability of an ε0 _0-substantial iterate, and summing over time yields bounded cumulative regret. Detailed proof is deferred to Appendix D. ∎ 4.4 Bounded O(1)O(1) regret for online DPO Specialize to pairwise feedback K=2K=2, and let (π^t)t≥0( π_t)_t≥ 0 denote the exact online DPO iterates from (5) with ℱ=ℱF=F_P. Define the extended class ΠDPO,0≔ΠDPO∪π0. _P^DPO,0 _P^DPO∪\ _0\. For π∈ΠDPOπ∈ _P^DPO, choose any R∈ℱR _P such that π=πRπ= _R, and define aπ(x)≔aR(x).a_π(x) a_R(x). This is well defined d0d_0-a.s. because any two such rewards differ on SxS_x only by an a-independent constant on SxS_x for d0d_0-a.e. x; see the proof of Theorem 6. For π=π0π= _0, define aπ0(x)≔a0(x),a_ _0(x) a_0(x), where 0 denotes the zero reward and the same measurable tie-breaking convention is used. Define, for π∈ΠDPO,0π∈ _P^DPO,0, pDPO(π)≔X∼d0[Rp(X,ap(X))−Rp(X,aπ(X))].G_p^DPO(π) _X d_0 [R_p(X,a_p(X))-R_p(X,a_π(X)) ]. Theorem 6 (Bounded temperature-zero regret for online DPO). Assume (C1)–(C2), and specialize to pairwise feedback K=2K=2. Then supp∈supT≥1∑t=0T−1p[pDPO(π^t)]<∞. _p _T≥ 1 _t=0^T-1E_p\! [G_p^DPO( π_t) ]<∞. More precisely, with the same constants ε0,γ,ε0,γ,Nγ,cγ _0,\ _P, _0,\ γ,\ N_γ,\ c_γ as in Theorem 5 specialized to K=2K=2, supp∈supT≥1∑t=0T−1p[pDPO(π^t)]≤Δmax(1+⌈1cγlog(2Nγ)⌉+1ecγ−1). _p _T≥ 1 _t=0^T-1E_p\! [G_p^DPO( π_t) ]≤ _ ^P (1+ 1c_γ (2N_γ) + 1e^c_γ-1 ). Proof deferred to Appendix D. 5 Experiment To isolate the paper’s main point, we exactly replicate the linear BT testbed experiment of Wu et al. (2025) except for the evaluation target: instead of measuring the softened policy used during data collection, we evaluate the temperature-zero action induced by the learned reward estimate. This directly tests the paper’s claim that the logarithmic KL-regularized regret reported in the literature is not due to exploration but is entirely attributable to the randomization induced by KL-regularization. 5.1 Setup We exactly replicate the linear BT testbed experiment of Wu et al. (2025): we consider the finite-action linear BT with k=5k=5, i.e., both contexts and actions are represented by five-dimensional feature vectors. We sample a fixed action set =a1,…,a6⊂[0,1]5A=\a_1,…,a_6\⊂[0,1]^5, together with a ground-truth matrix W⋆∈[0,1]5×5.W ∈[0,1]^5× 5. At round t, a fresh context xt∼Unif([0,1]5)x_t ([0,1]^5) is drawn, and the true latent reward of action a∈a is R⋆(xt,a)=xt⊤W⋆a.R (x_t,a)=x_t W a. The reference policy π0 _0 is uniform over all actions. We then run the standard greedy online alignment loop. We initialize π1=π0 _1= _0. At each round t, after observing xtx_t, the learner samples the first action from the current KL-tilted policy πt(a∣xt)∝π0(a)exp(ηR^t−1(xt,a)),R^t−1(xt,a)=xt⊤W^t−1a, _t(a x_t) _0(a) \! (η R_t-1(x_t,a) ), R_t-1(x_t,a)=x_t W_t-1a, samples the second action independently from π0 _0, observes the binary preference label, and then refits a Bradley–Terry maximum-likelihood estimate W^t W_t using all comparisons collected up to round t. We report results for η∈1,2,3η∈\1,2,3\, horizon T=200T=200, and 5050 independent trajectories for each value of η. Because the experiment is pairwise, we also overlay the corresponding online DPO iterates from the policy-space view in Section 3.4. Each fitted model W^t W_t induces a deterministic temperature-zero recommendation rule a^t(x)=argmaxa∈x⊤W^ta. a_t(x)= *arg\,max_a x W_ta. Most importantly, we evaluate the associated one-step temperature-zero regret x[R⋆(x,a⋆(x))−R⋆(x,a^t(x))],E_x\! [R (x,a (x))-R (x, a_t(x)) ], where a⋆(x)=argmaxa∈x⊤W⋆a (x)= *arg\,max_a x W a is the true optimal action. We estimate this expectation using Monte Carlo, drawing fresh evaluation contexts at each iteration, and report the cumulative sum of these one-step estimates along the trajectory, with a minimum probe gap of 0.2703. Appendix C records the exact sampling details and other minimum probe gap cases. 5.2 Results Figure 1 illustrates the same qualitative pattern, uniformly across all three regularization levels: the one-step temperature-zero regret falls rapidly to essentially zero well before round 100100, and the cumulative regret curves flatten after roughly the first 100100 rounds. This is exactly the bounded O(1)O(1) regret behavior predicted by Theorem 5: once the learned reward estimate induces the correct top-ranked action in almost all contexts, the remaining temperature-zero regret becomes zero, so the cumulative curve plateaus rather than continuing to grow throughout the horizon. Note that the online DPO curves are visually indistinguishable from the online RLHF curves at each η, exactly as predicted by the policy-space equivalence in the pairwise setting discussed earlier. It is useful to compare this with the results reported in Wu et al. (2025), which studies the same greedy online RLHF algorithm under the same finite-action linear Bradley–Terry simulation protocol. Their theory and experiments yield logarithmic KL-regularized cumulative regret. This highlights the important takeaway of this paper: after a finite number of time-steps, the logarithmic KL-regularized regret measured in Wu et al. (2025) was not due to exploration; rather, the regret was entirely from the randomization induced by the KL-regularized policy. Figure 1: Finite-action linear Bradley–Terry simulation experiment results replicating the experiment of Wu et al. (2025) except we use temperature-zero regret. Curves show the mean over 5050 repeated runs, and shaded bands denote the standard error. We overlay both online RLHF and online DPO; at each η, the two curves coincide. For all regularization levels η∈1,2,3η∈\1,2,3\, one-step temperature-zero regret (left image) rapidly collapses to zero and cumulative regret (right image) quickly plateaus. 6 Conclusion We revisited greedy online alignment through a temperature-zero lens, where performance is judged by the single response selected at inference time rather than by the full softened policy used during training and data collection. Under this decision-centric criterion, we showed that the effective regret in online alignment is bounded (O(1)O(1)) cumulative regret, and that the same conclusion carries over to the pairwise online DPO view. This sharpens the interpretation of existing logarithmic-regret guarantees: the previously known KL-regularized regret in the literature arises from randomizing the finite-temperature policy itself, rather than from a need for continued exploration. References Y. Bai, A. Jones, K. Ndousse, A. Askell, A. Chen, N. DasSarma, D. Drain, S. Fort, D. Ganguli, T. Henighan, N. Joseph, S. Kadavath, J. Kernion, T. Conerly, S. El-Showk, N. Elhage, Z. Hatfield-Dodds, D. Hernandez, T. Hume, S. Johnston, S. Kravec, L. Lovitt, N. Nanda, C. Olsson, D. Amodei, T. Brown, J. Clark, S. McCandlish, C. Olah, B. Mann, and J. Kaplan (2022) Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862. Cited by: Appendix A. H. Bastani, M. Bayati, and K. Khosravi (2021) Mostly exploration-free algorithms for contextual bandits. Management Science 67 (3), p. 1329–1349. External Links: Document, Link Cited by: Appendix A, §1, footnote 1. D. Calandriello, D. Guo, R. Munos, M. Rowland, Y. Tang, B. A. Pires, P. H. Richemond, C. Le Lan, M. Valko, T. Liu, R. Joshi, Z. Zheng, and B. Piot (2024) Human alignment of large language models through online preference optimisation. External Links: 2403.08635, Document, Link Cited by: Appendix A. L. Chen, J. Chen, C. Liu, J. Kirchenbauer, D. Soselia, C. Zhu, T. Goldstein, T. Zhou, and H. Huang (2025) OPTune: efficient online preference tuning. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: Appendix A. Y. Chen, Y. He, M. I. Jordan, and F. Yao (2026) How sampling shapes LLM alignment: from one-shot optima to iterative dynamics. External Links: 2602.12180, Document, Link Cited by: Appendix A, §1. N. Das, S. Chakraborty, A. Pacchiano, and S. R. Chowdhury (2024) Active preference optimization for sample efficient rlhf. arXiv preprint arXiv:2402.10500. Cited by: Appendix A. A. A. Deshmukh, S. Sharma, J. W. Cutler, M. Moldwin, and C. Scott (2018) Simple regret minimization for contextual bandits. arXiv preprint arXiv:1810.07371. Cited by: Appendix A. K. Dong and T. Ma (2022) Asymptotic instance-optimal algorithms for interactive decision making. arXiv preprint arXiv:2206.02326. Cited by: Appendix A. M. Dudík, K. Hofmann, R. E. Schapire, A. Slivkins, and M. Zoghi (2015) Contextual dueling bandits. In Proceedings of The 28th Conference on Learning Theory, P. Grünwald, E. Hazan, and S. Kale (Eds.), Proceedings of Machine Learning Research, Vol. 40, Paris, France, p. 563–587. External Links: Link Cited by: Appendix A. K. Ethayarajh, W. Xu, N. Muennighoff, D. Jurafsky, and D. Kiela (2024) KTO: model alignment as prospect theoretic optimization. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235. External Links: Link Cited by: Appendix A. M. Gheshlaghi Azar, Z. D. Guo, B. Piot, R. Munos, M. Rowland, M. Valko, and D. Calandriello (2024) A general theoretical paradigm to understand learning from human preferences. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 238, p. 4447–4455. External Links: Link Cited by: Appendix A. S. Guo, B. Zhang, T. Liu, T. Liu, M. Khalman, F. Llinares, A. Rame, T. Mesnard, Y. Zhao, B. Piot, J. Ferret, and M. Blondel (2024a) Direct language model alignment from online AI feedback. External Links: 2402.04792, Document, Link Cited by: Appendix A. S. Guo, B. Zhang, T. Liu, T. Liu, M. Khalman, F. Llinares, A. Rame, T. Mesnard, Y. Zhao, B. Piot, et al. (2024b) Direct language model alignment from online ai feedback. arXiv preprint arXiv:2402.04792. Cited by: §3.4. B. Hao, T. Lattimore, and C. Szepesvari (2020) Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics, p. 3536–3545. Cited by: Appendix A, §1, footnote 1. J. Hong, N. Lee, and J. Thorne (2024) ORPO: monolithic preference optimization without reference model. External Links: 2403.07691, Document, Link Cited by: Appendix A. A. Huang, A. Block, Q. Liu, N. Jiang, A. Krishnamurthy, and D. J. Foster (2025a) Is best-of-N the best of them? coverage, scaling, and optimality in inference-time alignment. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267. External Links: Link Cited by: Appendix A. A. Huang, W. Zhan, T. Xie, J. D. Lee, W. Sun, A. Krishnamurthy, and D. J. Foster (2025b) Correcting the mythos of KL-regularization: direct alignment without overoptimization via chi-squared preference optimization. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: Appendix A. K. Ji, J. He, and Q. Gu (2024) Reinforcement learning from human feedback with active queries. arXiv preprint arXiv:2402.09401. Cited by: Appendix A. E. H. Kang and P. Kumar (2024) Is o (log n) practical? near-equivalence between delay robustness and bounded regret in bandits and rl. Advances in Neural Information Processing Systems 37, p. 100270–100290. Cited by: Appendix A. E. H. Kang and P. Kumar (2023) Bounded (o (1)) regret recommendation learning via synthetic controls oracle. In 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton), p. 1–7. Cited by: Appendix A. S. Kannan, J. H. Morgenstern, A. Roth, B. Waggoner, and Z. S. Wu (2018) A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Advances in Neural Information Processing Systems, Vol. 31, p. 2231–2241. External Links: Link Cited by: Appendix A, §1, footnote 1. J. Kim, J. Yun, J. D. Lee, and K. Jun (2026) Coverage improvement and fast convergence of on-policy preference learning. External Links: 2601.08421, Document, Link Cited by: Appendix A, §1. K. Kim, A. J. Seo, H. Liu, J. Shin, and K. Lee (2024) Margin matching preference optimization: enhanced model alignment with granular feedback. In Findings of the Association for Computational Linguistics: EMNLP 2024, p. 13554–13570. Cited by: §4.2, footnote 2. S. Kim and M. Oh (2024) Local anti-concentration class: logarithmic regret for greedy linear contextual bandit. In Advances in Neural Information Processing Systems, Vol. 37, p. 77525–77592. External Links: Link Cited by: Appendix A, §1, footnote 1. S. K. Krishnamurthy, R. Zhan, S. Athey, and E. Brunskill (2023) Proportional response: contextual bandits for simple and cumulative regret minimization. arXiv preprint arXiv:2307.02108. Cited by: Appendix A. J. Lee, M. Hong, K. Jun, C. Yun, and S. Yun (2026) Regularized online RLHF with generalized bilinear preferences. External Links: 2602.23116, Document, Link Cited by: Appendix A, §1. Y. Meng, M. Xia, and D. Chen (2024) SimPO: simple preference optimization with a reference-free reward. External Links: 2405.14734, Document, Link Cited by: Appendix A. R. Munos, M. Valko, D. Calandriello, M. G. Azar, M. Rowland, Z. D. Guo, Y. Tang, M. Geist, T. Mesnard, A. Michi, M. Selvi, S. Girgin, N. Momchev, O. Bachem, D. J. Mankowitz, D. Precup, and B. Piot (2024) Nash learning from human feedback. External Links: 2312.00886, Document, Link Cited by: Appendix A. L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. F. Christiano, J. Leike, and R. Lowe (2022) Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems 35, p. 27730–27744. Cited by: Appendix A. M. Papini, A. Tirinzoni, A. Pacchiano, M. Restelli, A. Lazaric, and M. Pirotta (2021a) Reinforcement learning in linear mdps: constant regret and representation selection. Advances in Neural Information Processing Systems 34, p. 16371–16383. Cited by: Appendix A. M. Papini, A. Tirinzoni, M. Restelli, A. Lazaric, and M. Pirotta (2021b) Leveraging good representations in linear contextual bandits. In International Conference on Machine Learning, p. 8371–8380. Cited by: Appendix A, §1, footnote 1. B. Qi, P. Li, F. Li, J. Gao, K. Zhang, and B. Zhou (2024) Online DPO: online direct preference optimization with fast-slow chasing. External Links: 2406.05534, Document, Link Cited by: Appendix A. B. Qin, D. Feng, and X. Yang (2024) Towards understanding the influence of reward margin on preference model performance. arXiv preprint arXiv:2404.04932. Cited by: §4.2, footnote 2. R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn (2023) Direct preference optimization: your language model is secretly a reward model. In Advances in Neural Information Processing Systems, Vol. 36. External Links: Link Cited by: Appendix A. M. Raghavan, A. Slivkins, J. W. Vaughan, and Z. S. Wu (2023) Greedy algorithm almost dominates in smoothed contextual bandits. SIAM Journal on Computing 52 (2), p. 487–524. External Links: Document, Link Cited by: Appendix A, §1, footnote 1. C. Rosset, C. Cheng, A. Mitra, M. Santacroce, A. Awadallah, and T. Xie (2024) Direct nash optimization: teaching language models to self-improve with general preferences. External Links: 2404.03715, Document, Link Cited by: Appendix A. A. Saha and A. Krishnamurthy (2022) Efficient and optimal algorithms for contextual dueling bandits under realizability. In Proceedings of The 33rd International Conference on Algorithmic Learning Theory, S. Dasgupta and N. Haghtalab (Eds.), Proceedings of Machine Learning Research, Vol. 167, p. 968–994. External Links: Link Cited by: Appendix A. N. Stiennon, L. Ouyang, J. Wu, D. M. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. Christiano (2020) Learning to summarize from human feedback. arXiv preprint arXiv:2009.01325. Cited by: Appendix A. A. Sturm and S. Tschiatschek (2025) On constant regret for low-rank mdps. In Proceedings of the Forty-First Conference on Uncertainty in Artificial Intelligence, p. 4044–4079. Cited by: Appendix A. A. Tirinzoni, M. Papini, A. Touati, A. Lazaric, and M. Pirotta (2022) Scalable representation learning in linear contextual bandits with constant regret guarantees. Advances in Neural Information Processing Systems 35, p. 2307–2319. Cited by: Appendix A, §1. A. Tirinzoni, M. Pirotta, and A. Lazaric (2023) On the complexity of representation learning in contextual linear bandits. In International Conference on Artificial Intelligence and Statistics, p. 7871–7896. Cited by: Appendix A, footnote 1. A. J. Wagenmaker and D. J. Foster (2023) Instance-optimality in interactive decision making: toward a non-asymptotic theory. In The Thirty Sixth Annual Conference on Learning Theory, p. 1322–1472. Cited by: Appendix A. B. Wang, R. Zheng, L. Chen, Y. Liu, S. Dou, C. Huang, W. Shen, S. Jin, E. Zhou, C. Shi, et al. (2024) Secrets of rlhf in large language models part i: reward modeling. arXiv preprint arXiv:2401.06080. Cited by: §4.2, footnote 2. Y. Wang, Q. Liu, and C. Jin (2023) Is RLHF more difficult than standard RL? a theoretical perspective. In Advances in Neural Information Processing Systems, Vol. 36. External Links: Link Cited by: Appendix A. D. Wu, C. Shi, J. Yang, and C. Shen (2025) Greedy sampling is provably efficient for RLHF. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, External Links: Link Cited by: Appendix A, Figure 2, 2nd item, §1, §1, §3.3, §4.2, Figure 1, §5.1, §5.2, §5, Remark 1. Y. Wu, Z. Sun, H. Yuan, K. Ji, Y. Yang, and Q. Gu (2024) Self-play preference optimization for language model alignment. External Links: 2405.00675, Document, Link Cited by: Appendix A. T. Xie, D. J. Foster, A. Krishnamurthy, C. Rosset, A. Awadallah, and A. Rakhlin (2025) Exploratory preference optimization: harnessing implicit Q∗-approximation for sample-efficient RLHF. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: Appendix A. W. Xiong, H. Dong, C. Ye, Z. Wang, H. Zhong, H. Ji, N. Jiang, and T. Zhang (2024) Iterative preference learning from human feedback: bridging theory and practice for RLHF under KL-constraint. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 54715–54754. External Links: Link Cited by: Appendix A, §1, §4.2. J. Xu, A. Lee, S. Sukhbaatar, and J. Weston (2023) Some things are more CRINGE than others: iterative preference optimization with the pairwise cringe loss. External Links: 2312.16682, Document, Link Cited by: Appendix A. Y. Xu, R. Wang, L. F. Yang, A. Singh, and A. Dubrawski (2020) Preference-based reinforcement learning with finite-time guarantees. In Advances in Neural Information Processing Systems, Vol. 33. External Links: Link Cited by: Appendix A. C. Ye, W. Xiong, Y. Zhang, H. Dong, N. Jiang, and T. Zhang (2024) Online iterative reinforcement learning from human feedback with general preference model. In Advances in Neural Information Processing Systems, Vol. 37, p. 81773–81807. External Links: Link Cited by: Appendix A, §1, §4.2. Y. Zeng, G. Liu, W. Ma, N. Yang, H. Zhang, and J. Wang (2024) Token-level direct preference optimization. External Links: 2404.11999, Document, Link Cited by: Appendix A. L. H. Zhang and R. Ranganath (2025) Preference learning made easy: everything should be understood through win rate. In Proceedings of the 42nd International Conference on Machine Learning, External Links: Link Cited by: Appendix A. W. Zhang, Z. Fan, J. He, and Q. Gu (2024) Achieving constant regret in linear markov decision processes. Advances in Neural Information Processing Systems 37, p. 130694–130738. Cited by: Appendix A. Y. Zhang, G. Zhang, Y. Wu, K. Xu, and Q. Gu (2025) Beyond bradley–terry models: a general preference model for language model alignment. External Links: 2410.02197, Document, Link Cited by: Appendix A. H. Zhao, C. Ye, Q. Gu, and T. Zhang (2024) Sharp analysis for KL-regularized contextual bandits and RLHF. External Links: 2411.04625, Document, Link Cited by: Appendix A, §1, §1. H. Zhao, C. Ye, W. Xiong, Q. Gu, and T. Zhang (2025a) Logarithmic regret for online KL-regularized reinforcement learning. External Links: 2502.07460, Document, Link Cited by: Appendix A, §1. Q. Zhao, K. Ji, H. Zhao, T. Zhang, and Q. Gu (2025b) Nearly optimal sample complexity of offline KL-regularized contextual bandits under single-policy concentrability. External Links: 2502.06051, Document, Link Cited by: Appendix A, §1. B. Zhu, M. Jordan, and J. Jiao (2023) Principled reinforcement learning with human feedback from pairwise or K-wise comparisons. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 43037–43067. External Links: Link Cited by: Appendix A, §1. D. M. Ziegler, N. Stiennon, J. Wu, T. B. Brown, A. Radford, D. Amodei, P. Christiano, and G. Irving (2019) Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593. Cited by: Appendix A. Appendix A Related works Preference-based alignment. Early theory for RLHF established statistical guarantees for learning from pairwise and K-wise comparisons and clarified the role of reward-model estimation in preference-based control [Zhu et al., 2023]; adjacent work in preference-based RL studied finite-time guarantees and compared the intrinsic difficulty of RLHF to standard reward-based RL [Xu et al., 2020, Wang et al., 2023]. A complementary unifying view is given by Ψ , which treats RLHF, DPO, and identity-based objectives as special cases of a broader preference-learning framework and makes explicit when scalar-reward reductions are or are not faithful to the underlying preference problem [Gheshlaghi Azar et al., 2024]. Empirical RLHF lineage. Empirically, modern language-model RLHF was established through early systems that learned reward models from human comparisons and optimized policies against them, including stylistic continuation and summarization alignment in Ziegler et al. [2019], Stiennon et al. [2020]. Subsequent large-scale systems such as InstructGPT and Anthropic’s helpful–harmless assistant demonstrated the practical RLHF pipeline for instruction following and assistant alignment, helping motivate the iterative deployment-and-feedback loop that later theory seeks to understand [Ouyang et al., 2022, Bai et al., 2022]. KL-regularized iterative RLHF. A recent theory line studies the same KL-regularized contextual-bandit / RLHF objective considered here: Xiong et al. [2024] analyze offline, online, and hybrid iterative preference learning under KL-constraints, and Ye et al. [2024] extend the online analysis beyond Bradley–Terry to general preference oracles. Subsequent sharp analyses show that KL regularization can fundamentally change the local statistical difficulty, yielding O(1/ε)O(1/ ) or logarithmic rates in offline and online settings under suitable assumptions [Zhao et al., 2024, 2025a, 2025b]. Greedy and on-policy preference learning. Most closely related, Wu et al. [2025] show that greedy sampling itself can attain the same O(logT)O( T) order as confidence-based methods in RLHF, including under general preference models, so explicit optimism or pessimism is not always necessary. Kim et al. [2026], Chen et al. [2026], and Lee et al. [2026] refine this picture by analyzing coverage improvement in on-policy DPO, the effect of sampling and reference choices on iterative dynamics, and greedy learning under generalized bilinear or potentially intransitive preference models with strongly convex regularization. Contextual dueling bandits and active preference acquisition. From a learning-theoretic perspective, our setting is also closely connected to contextual dueling bandits, where the learner receives context, selects two actions, and observes only relative preference feedback. Classical contextual dueling-bandit work formalized this problem and later gave efficient regret guarantees under realizability [Dudík et al., 2015, Saha and Krishnamurthy, 2022]; more recent RLHF-specific work makes this connection explicit by formulating alignment as a contextual dueling-bandit or contextual preference-bandit problem and studying active-query or adaptive-sampling algorithms for reducing label complexity [Ji et al., 2024, Das et al., 2024]. Direct preference optimization and online variants. On the algorithmic side, DPO recasts KL-regularized preference optimization as a classification-style objective, and a large family of direct-alignment variants modifies the link function, regularizer, or granularity of the implicit reward, including ORPO, KTO, SimPO, TDPO, and χ2χ^2-preference optimization [Rafailov et al., 2023, Hong et al., 2024, Ethayarajh et al., 2024, Meng et al., 2024, Zeng et al., 2024, Huang et al., 2025b]. Several works also make direct preference optimization iterative or online. through online AI feedback, online IPO / IPO-MD, self-play or general-preference formulations such as NLHF, DNO, and GPO, exploratory bonuses, efficient online data selection, or explicit online DPO updates, suggesting that fresh on-policy preferences can materially improve empirical performance [Guo et al., 2024a, Calandriello et al., 2024, Munos et al., 2024, Rosset et al., 2024, Zhang et al., 2025, Wu et al., 2024, Xie et al., 2025, Chen et al., 2025, Qi et al., 2024, Xu et al., 2023]. Simple-regret objectives. Methodologically, our temperature-zero criterion is closer to simple-regret evaluation than to standard cumulative policy regret, because it scores the final recommended action rather than the full stochastic policy used during data collection. This objective has been studied in contextual bandits both in pure-exploration / exploitation formulations and in more recent algorithms that explicitly trade off cumulative and simple regret, providing a useful conceptual parallel to our decision-centric evaluation [Deshmukh et al., 2018, Krishnamurthy et al., 2023]. Deployment-centric views. Recent inference-time alignment work studies the top-of-ranking decision more directly, for example by analyzing best-of-N scaling, coverage, and reward hacking for response selection with a fixed reward model [Huang et al., 2025a]. Zhang and Ranganath [2025] argue that win rate is the canonical evaluation induced by preference data; our temperature-zero regret is different, but it is motivated by a similar shift away from the full training distribution toward the decision that is actually used at deployment. Classical greedy bandits. Our bounded temperature-zero regret result is also closely related in spirit to implicit-exploration results for greedy contextual bandits: covariate diversity, smoothing, and local anti-concentration can make purely greedy algorithms no-regret or polylogarithmic, substantially reducing or even eliminating the need for explicit exploration [Bastani et al., 2021, Kannan et al., 2018, Raghavan et al., 2023, Kim and Oh, 2024]. The main difference is that in KL-regularized alignment the learner continues to collect data with a softened policy, while our regret notion evaluates only the temperature-zero action induced by the learned reward estimate. Bounded-regret and sub-log-regret literature. More broadly, our bounded temperature-zero regret result fits a longer line of work asking when interactive decision problems admit faster-than-logarithmic, or even constant (bounded) regret. In linear contextual bandits, rich-context or covariate-diversity conditions, often called the HLS condition, can already yield sub-logarithmic regret for nearly greedy methods [Hao et al., 2020], while later representation-based analyses show that under realizability together with suitable spectral conditions, such as the HLS condition, constant regret can be achieved and even used for representation selection [Papini et al., 2021b, Tirinzoni et al., 2022, 2023]. Related reinforcement-learning work identifies analogous structural conditions in linear and low-rank MDPs: Papini et al. [2021a] introduce a necessary condition for constant regret in linear MDPs and show sufficiency for important low-rank / Bellman-closed settings, and more recent work studies constant-regret guarantees under good representations in low-rank or misspecified linear MDPs as well as in recommender-style formulations with repeated users [Sturm and Tschiatschek, 2025, Zhang et al., 2024, Kang and Kumar, 2023]. At a more general level, asymptotic and non-asymptotic instance-optimal frameworks based on Graves–Lai allocations and the allocation–estimation coefficient clarify when sub-logarithmic behavior is even possible, with recent work making explicit that the zero-complexity regime is precisely the one corresponding to bounded regret [Dong and Ma, 2022, Wagenmaker and Foster, 2023, Kang and Kumar, 2024]. Unlike these lines of work, we do not propose a new exploration rule, preference objective, or inference-time selection algorithm. Our contribution is instead to show that the standard greedy KL-regularized alignment loop can look substantially stronger once it is evaluated under a decision-centric, temperature-zero notion of regret. Appendix B Extended discussions Beyond BT and relation to more general preference models. This paper currently focuses on the MNL/BT preference model because it admits a tractable log-loss representation and a clean reward-to-policy correspondence. This leaves open robustness to intransitive preferences and more general preference structures. Recent preference-learning frameworks emphasize that scalar-reward reductions need not be faithful in full generality. Our theory does not attempt to resolve that general question. Instead, it isolates a regime in which the scalar-reward view is sufficient to prove a decision-centric bounded-regret statement. Extending the same temperature-zero perspective to generalized bilinear, non-BT, or intransitive preference models would help situate the result more broadly within recent analyses beyond Bradley–Terry. Large-scale practical relevance. No large-scale or semi-real LLM experiments are included in the current version. As a result, the paper should not be read as claiming immediate quantitative relevance for full production-scale alignment pipelines. The contribution is primarily conceptual and theoretical: it identifies a deployment-centric criterion under which greedy alignment can exhibit bounded cumulative regret, and it illustrates that phenomenon in a controlled simulation. Demonstrating the same separation between selector-identification error and KL-induced randomization in stronger empirical settings remains future work. Appendix C Experiment reproducibility details This appendix records the exact run used for the main simulation in Section 5. The released artifacts correspond to the directory Experiments/horizon200_gapforced_0p2_seed3500_rep50, generated by python Experiments/run_bt_temperature_zero.py \ --output-dir Experiments/horizon200_gapforced_0p2_seed3500_rep50 \ --seed 3500 \ --dimension 5 \ --num-actions 6 \ --horizon 200 \ --repeats 50 \ --eval-contexts 4096 \ --mle-maxiter 50 \ --mle-ftol 1e-9 \ --min-probe-gap 0.2 \ --gap-probe-contexts 20000 \ --problem-search-limit 1000 Problem-instance selection. Using the base seed 35003500, the script first draws a fixed bank of 20,00020,000 probe contexts from Unif([0,1]5)Unif([0,1]^5). It then scans candidate problem seeds 3500,3501,…3500,3501,… until it finds an instance whose minimum true top-two reward gap on that probe bank is at least 0.20.2. For the run used in Figure 1, the accepted candidate is the 4747-th one, with chosen problem seed 35463546. Its realized minimum probe-bank gap is 0.27030.2703, and the mean probe-bank gap is 1.90181.9018. Online data collection and fitting. The experiment uses k=5k=5-dimensional contexts, ||=6|A|=6 actions, horizon T=200T=200, and regularization coefficients η∈1,2,3η∈\1,2,3\. Each context xtx_t is drawn independently from Unif([0,1]5)Unif([0,1]^5). The first action is sampled from the current KL-tilted policy, the second action is sampled independently from the uniform reference policy on the six actions, and the binary preference is then drawn from the Bradley–Terry probability σ(xt⊤W⋆(at,1−at,2)).σ\! (x_t W (a_t,1-a_t,2) ). After each round, the estimate W^t W_t is refit on all comparisons collected so far by bounded L-BFGS-B maximum likelihood on the 2525-dimensional parameter vector, initialized from the previous iterate, with box constraints [0,1][0,1], maxiter=50=50, and ftol=10−9=10^-9. Evaluation and uncertainty reporting. For each η, we run 5050 independent trajectories. At every iteration t, the one-step temperature-zero regret is estimated on a fresh Monte Carlo batch of 40964096 evaluation contexts, independent of both the online trajectory and the probe bank. Figure 1 plots the mean across the 5050 trajectories, and the shaded bands are pointwise standard errors, computed as the sample standard deviation divided by 50 50. In the pairwise setting, the released DPO overlay is exactly identical to the RLHF trajectory data; the reported maximum absolute RLHF-versus-DPO difference is zero for both the step and cumulative curves at every η. Table 1: Final-iteration summary for the exact run used in Figure 1. η final step mean final step s.e. final cumulative mean final cumulative s.e. 11 0.000120.00012 0.000060.00006 7.50927.5092 0.78500.7850 22 0.000060.00006 0.000040.00004 5.94015.9401 0.50860.5086 33 0.000300.00030 0.000160.00016 5.48025.4802 0.54120.5412 Compute scale. The implementation is a single-process NumPy/SciPy/Matplotlib simulation and does not require a GPU. The dominant per-repeat evaluation tensor has shape (T+1)×4096×5(T+1)× 4096× 5, which is about 3333 MB in double precision, and the full run performs 3×50×200=30,0003× 50× 200=30,000 bounded L-BFGS-B solves in dimension 2525. This is a lightweight workstation-scale simulation rather than a large-model training run. Additional experiment results. Figure 2 shows a harder low-gap case to illustrate that the same qualitative plateau still appears when the true top-two reward gap is much smaller, although the flattening can occur later. Figure 2: Finite-action linear Bradley–Terry simulation experiment results with probe gap 0.0204, replicating the experiment of Wu et al. [2025] except we use temperature-zero regret. Curves show the mean over 5050 repeated runs, and shaded bands denote the standard error. In the pairwise setting, we overlay the online RLHF and online DPO curves; at each η, the two coincide. Again, for all regularization levels η∈1,2,3η∈\1,2,3\, one-step temperature-zero regret (left image) rapidly collapses to zero and cumulative regret (right image) plateaus. The online trajectory in this lower-gap case again uses fresh i.i.d. contexts xt∼Unif([0,1]5)x_t ([0,1]^5) for data collection, with regret estimated at each iteration on an additional fresh batch of 40964096 evaluation contexts, independent of both the probe bank and the online trajectory contexts. The cumulative curves in Figures 1 and 2 are the cumulative sums of these per-iteration Monte Carlo estimates. Appendix D Proofs for Section 4 We first record examples of reward families satisfying Condition (C1). D.1 Linear and neural reward families Write Sx≔supp(π0(⋅∣x)),Sπ0≔(x,a)∈×:a∈Sx.S_x ( _0(· x)), S_ _0 \(x,a) ×A:\ a∈ S_x\. Proposition 7 (Centered linear reward classes satisfy Condition (C1)). Let Θ⊂ℝd ^d be compact. Let ϕ:×→ℝdφ:X×A ^d be measurable and satisfy Mϕ≔sup(x,a)∈Sπ0‖ϕ(x,a)‖2<∞.M_φ _(x,a)∈ S_ _0\|φ(x,a)\|_2<∞. Assume also that for d0d_0-a.e. x, the map a⟼ϕ(x,a)a φ(x,a) is continuous on SxS_x. For θ∈Θθ∈ , define the centered linear reward Rθ(x,a)≔θ⊤ϕ(x,a)−A∼π0(⋅∣x)[θ⊤ϕ(x,A)].R_θ(x,a) θ φ(x,a)-E_A _0(· x)[θ φ(x,A)]. Then the class ℱΘlin≔Rθ:θ∈ΘF_ ^lin \R_θ:θ∈ \ is compact under ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0), and for every θ∈Θθ∈ , the map a↦Rθ(x,a)a R_θ(x,a) is continuous on SxS_x for d0d_0-a.e. x. Hence ℱΘlinF_ ^lin satisfies Condition (C1). Proof. Fix θ∈Θθ∈ . For d0d_0-a.e. x, the map a⟼θ⊤ϕ(x,a)a θ φ(x,a) is continuous on SxS_x, because it is a continuous linear functional of ϕ(x,⋅)φ(x,·). The centering term mθ(x)≔A∼π0(⋅∣x)[θ⊤ϕ(x,A)]m_θ(x) _A _0(· x)[θ φ(x,A)] does not depend on a. Hence a⟼Rθ(x,a)=θ⊤ϕ(x,a)−mθ(x)a R_θ(x,a)=θ φ(x,a)-m_θ(x) is continuous on SxS_x for d0d_0-a.e. x. Now fix θ,θ~∈Θθ, θ∈ . For every (x,a)∈Sπ0(x,a)∈ S_ _0, |Rθ(x,a)−Rθ~(x,a)|≤|(θ−θ~)⊤ϕ(x,a)|+|A∼π0(⋅∣x)[(θ−θ~)⊤ϕ(x,A)]|.|R_θ(x,a)-R_ θ(x,a)|≤|(θ- θ) φ(x,a)|+ |E_A _0(· x) [(θ- θ) φ(x,A) ] |. By Cauchy–Schwarz and the bound on ϕφ, |Rθ(x,a)−Rθ~(x,a)|≤2Mϕ‖θ−θ~‖2.|R_θ(x,a)-R_ θ(x,a)|≤ 2M_φ\|θ- θ\|_2. Taking the supremum over Sπ0S_ _0 yields ‖Rθ−Rθ~‖∞,supp(π0)≤2Mϕ‖θ−θ~‖2.\|R_θ-R_ θ\|_∞,supp( _0)≤ 2M_φ\|θ- θ\|_2. Therefore the map Θ→ℓ∞(Sπ0),θ↦Rθ, → _∞(S_ _0), θ R_θ, is continuous. Since Θ is compact, its image ℱΘlinF_ ^lin is compact under ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0). ∎ Proposition 8 (Centered neural reward classes satisfy Condition (C1)). Let Θ⊂ℝm ^m be compact. For each θ∈Θθ∈ , let fθ:Sπ0→ℝf_θ:S_ _0 be a bounded measurable function. Assume that: (i) for d0d_0-a.e. x and every θ∈Θθ∈ , the map a⟼fθ(x,a)a f_θ(x,a) is continuous on SxS_x; (i) the parameter-to-function map Θ→ℓ∞(Sπ0),θ⟼fθ, → _∞(S_ _0), θ f_θ, is continuous. Define the centered reward Rθ(x,a)≔fθ(x,a)−A∼π0(⋅∣x)[fθ(x,A)].R_θ(x,a) f_θ(x,a)-E_A _0(· x)[f_θ(x,A)]. Then the class ℱΘn≔Rθ:θ∈ΘF_ ^n \R_θ:θ∈ \ is compact under ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0), and for every θ∈Θθ∈ , the map a↦Rθ(x,a)a R_θ(x,a) is continuous on SxS_x for d0d_0-a.e. x. Hence ℱΘnF_ ^n satisfies Condition (C1). Proof. Fix θ∈Θθ∈ . By assumption, for d0d_0-a.e. x, the section a⟼fθ(x,a)a f_θ(x,a) is continuous on SxS_x. The centering term mθ(x)≔A∼π0(⋅∣x)[fθ(x,A)]m_θ(x) _A _0(· x)[f_θ(x,A)] does not depend on a. Hence a⟼Rθ(x,a)=fθ(x,a)−mθ(x)a R_θ(x,a)=f_θ(x,a)-m_θ(x) is continuous on SxS_x for d0d_0-a.e. x. Now fix θ,θ~∈Θθ, θ∈ . For every (x,a)∈Sπ0(x,a)∈ S_ _0, |Rθ(x,a)−Rθ~(x,a)| |R_θ(x,a)-R_ θ(x,a)| ≤|fθ(x,a)−fθ~(x,a)| ≤|f_θ(x,a)-f_ θ(x,a)| +|A∼π0(⋅∣x)[fθ(x,A)−fθ~(x,A)]| + |E_A _0(· x) [f_θ(x,A)-f_ θ(x,A) ] | ≤2‖fθ−fθ~‖∞,supp(π0). ≤ 2\|f_θ-f_ θ\|_∞,supp( _0). Therefore ‖Rθ−Rθ~‖∞,supp(π0)≤2‖fθ−fθ~‖∞,supp(π0).\|R_θ-R_ θ\|_∞,supp( _0)≤ 2\|f_θ-f_ θ\|_∞,supp( _0). Since θ↦fθ f_θ is continuous into ℓ∞(Sπ0) _∞(S_ _0), the map Θ→ℓ∞(Sπ0),θ↦Rθ, → _∞(S_ _0), θ R_θ, is also continuous. Because Θ is compact, its image ℱΘnF_ ^n is compact under ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0). ∎ Remark 9. A standard sufficient condition for Proposition 8 is the following: suppose Θ is compact, Sπ0S_ _0 is compact, and there exists a jointly continuous map f:Θ×Sπ0→ℝf: × S_ _0 such that fθ(x,a)=f(θ,x,a)f_θ(x,a)=f(θ,x,a). Then θ↦fθ f_θ is continuous into ℓ∞(Sπ0) _∞(S_ _0) by uniform continuity on the compact set Θ×Sπ0 × S_ _0. Hence any feedforward network with continuous activations (including ReLU), compact parameter set, and compact support graph Sπ0S_ _0 satisfies Proposition 8. Definition 10 (π0 _0-essential reward oscillation). Fix a reference policy π0(⋅∣x) _0(· x). For a measurable reward function r:×→ℝr:X×A , define oscπ0(r)(x)≔esssupa∼π0(⋅∣x)r(x,a)−essinfa∼π0(⋅∣x)r(x,a).osc_ _0(r)(x) *ess\,sup_a _0(· x)r(x,a)- *ess\,inf_a _0(· x)r(x,a). We say r is B-oscillation-bounded (with respect to π0 _0) if oscπ0(r)(x)≤2B∀x∈.osc_ _0(r)(x)≤ 2B ∀ x . Lemma 11 (π0 _0-centering is w.l.o.g. for MNL likelihoods). Fix any reward function R:×→ℝR:X×A and define its π0 _0-centered version R¯(x,a)≔R(x,a)−mR(x),mR(x)≔a′∼π0(⋅∣x)[R(x,a′)]. R(x,a) R(x,a)-m_R(x), m_R(x) _a _0(· x)[R(x,a )]. Then for every x and every slate =(a1,…,aK)a=(a_1,…,a_K): (i) PR(⋅∣x,)=PR¯(⋅∣x,)P_R(· x,a)=P_ R(· x,a), (i) πR(⋅∣x)=πR¯(⋅∣x) _R(· x)= _ R(· x) for KL-tilts, (i) argmaxa∈supp(π0(⋅∣x))R(x,a)=argmaxa∈supp(π0(⋅∣x))R¯(x,a) _a ( _0(· x))R(x,a)= _a ( _0(· x)) R(x,a). Moreover, oscπ0(R¯)(x)=oscπ0(R)(x)osc_ _0( R)(x)=osc_ _0(R)(x) for all x. Proof. Fix x and abbreviate c=mR(x)c=m_R(x), so R¯(x,a)=R(x,a)−c R(x,a)=R(x,a)-c. (i) For any k, eR¯(x,ak)∑ℓ=1KeR¯(x,aℓ)=eR(x,ak)−c∑ℓ=1KeR(x,aℓ)−c=eR(x,ak)∑ℓ=1KeR(x,aℓ). e R(x,a_k) _ =1^Ke R(x,a_ )= e^R(x,a_k)-c _ =1^Ke^R(x,a_ )-c= e^R(x,a_k) _ =1^Ke^R(x,a_ ). (i) For KL-tilts, πR¯(a∣x)∝π0(a∣x)eηR¯(x,a)=π0(a∣x)eηR(x,a)e−ηc, _ R(a x) _0(a x)e^η R(x,a)= _0(a x)e^η R(x,a)e^-η c, and the factor e−ηce^-η c cancels under normalization over a. (i) Subtracting an a-independent constant does not change the argmax. Finally, oscillation is invariant to adding a constant: esssupa∼π0(⋅∣x)(R(x,a)−c)−essinfa∼π0(⋅∣x)(R(x,a)−c)=esssupa∼π0(⋅∣x)R(x,a)−essinfa∼π0(⋅∣x)R(x,a). *ess\,sup_a _0(· x)(R(x,a)-c)- *ess\,inf_a _0(· x)(R(x,a)-c)= *ess\,sup_a _0(· x)R(x,a)- *ess\,inf_a _0(· x)R(x,a). ∎ Lemma 12 (Boundedness and Lipschitzness of the MNL log-loss). Let ℓ(,y)=log(∑k=1Kevk)−vy (v,y)= ( _k=1^Ke^v_k)-v_y be the MNL negative log-likelihood. If maxkvk−minkvk≤2B _kv_k- _kv_k≤ 2B, then for every y, 0≤ℓ(,y)≤logK+2B.0≤ (v,y)≤ K+2B. Moreover, for any ,′∈ℝKv,v ^K and any y, |ℓ(,y)−ℓ(′,y)|≤2‖−′‖∞.| (v,y)- (v ,y)|≤ 2\|v-v \|_∞. Proof. Let m=minkvkm= _kv_k and M=maxkvkM= _kv_k, so M−m≤2BM-m≤ 2B. Then ∑k=1Kevk≤KeM, _k=1^Ke^v_k≤ Ke^M, hence log∑k=1Kevk≤logK+M,−vy≤−m. _k=1^Ke^v_k≤ K+M, -v_y≤-m. Therefore ℓ(,y)≤(logK+M)−m=logK+(M−m)≤logK+2B. (v,y)≤( K+M)-m= K+(M-m)≤ K+2B. Also ℓ(,y)=−logpy (v,y)=- p_y for the softmax probability py∈(0,1]p_y∈(0,1], so ℓ(,y)≥0 (v,y)≥ 0. Let p=softmax()p=softmax(v). Then ∇ℓ(,y)=p−ey. _v (v,y)=p-e_y. Hence ‖∇ℓ(,y)‖1=∑k≠ypk+|py−1|=(1−py)+(1−py)=2(1−py)≤2.\| _v (v,y)\|_1= _k≠ yp_k+|p_y-1|=(1-p_y)+(1-p_y)=2(1-p_y)≤ 2. By the mean-value theorem, |ℓ(,y)−ℓ(′,y)|≤supθ∈[0,1]‖∇ℓ(′+θ(−′),y)‖1⋅‖−′‖∞≤2‖−′‖∞.| (v,y)- (v ,y)|≤ _θ∈[0,1]\|∇ (v +θ(v-v ),y)\|_1·\|v-v \|_∞≤ 2\|v-v \|_∞. ∎ Lemma 13 (One-step excess loss equals choice-model KL). Fix any realized (x,)(x,a), any truth reward R⋆R , and any candidate reward R. Let p⋆=PR⋆(⋅∣x,),p=PR(⋅∣x,).p =P_R (· x,a), p=P_R(· x,a). Then y∼p⋆[ℓ(R,y)−ℓ(R⋆,y)]=KL(p⋆∥p),E_y p [ (v_R,y)- (v_R ,y) ]=KL(p \|p), where R=(R(x,a1),…,R(x,aK)),R⋆=(R⋆(x,a1),…,R⋆(x,aK)).v_R=(R(x,a_1),…,R(x,a_K)), _R =(R (x,a_1),…,R (x,a_K)). Proof. y∼p⋆[ℓ(R,y)−ℓ(R⋆,y)]=∑k=1Kpk⋆(−logpk+logpk⋆)=∑k=1Kpk⋆logpk⋆pk=KL(p⋆∥p).E_y p [ (v_R,y)- (v_R ,y)]= _k=1^Kp_k (- p_k+ p_k )= _k=1^Kp_k p_k p_k=KL(p \|p). ∎ Lemma 14 (Slate expectation domination). Fix any x and any distribution π(⋅∣x)π(· x) such that π(a∣x)≥β−1π0(a∣x)π0(⋅∣x)-a.s.π(a x)≥β^-1 _0(a x) _0(· x)-a.s. Let ∼π(⋅∣x)⊗KA π(· x) K and 0∼π0(⋅∣x)⊗KA_0 _0(· x) K. Then for every nonnegative measurable g, [g()]≥β−K[g(0)].E [g(A) ]≥β^-K\,E [g(A_0) ]. Proof. For π0⊗K _0 K-a.e. =(a1,…,aK)a=(a_1,…,a_K), π⊗K(∣x)π0⊗K(∣x)=∏k=1Kπ(ak∣x)π0(ak∣x)≥β−K. π K(a x) _0 K(a x)= _k=1^K π(a_k x) _0(a_k x)≥β^-K. Therefore [g()]=∫g()π⊗K(∣x)≥β−K∫g()π0⊗K(∣x)=β−K[g(0)].E[g(A)]= g(a)\,π K(a x)\,da≥β^-K g(a)\, _0 K(a x)\,da=β^-KE[g(A_0)]. ∎ Lemma 15 (Likelihood-ratio bound for KL tilts). Fix a tilt parameter η>0η>0. Let R:×→ℝR:X×A satisfy oscπ0(R)(x)≤2B∀x∈.osc_ _0(R)(x)≤ 2B ∀ x . Let πR(a∣x)=π0(a∣x)exp(ηR(x,a))∫π0(a′∣x)exp(ηR(x,a′))a′. _R(a x)= _0(a x) (η R(x,a)) _A _0(a x) (η R(x,a ))\,da . Then e−2ηB≤dπR(⋅∣x)dπ0(⋅∣x)(a)≤e2ηB,π0(⋅∣x)-a.s.e^-2η B≤ d _R(· x)d _0(· x)(a)≤ e^2η B, _0(· x)-a.s. for every x∈x . Proof. Fix x∈x , and write mx≔essinfa∼π0(⋅∣x)R(x,a),Mx≔esssupa∼π0(⋅∣x)R(x,a).m_x *ess\,inf_a _0(· x)R(x,a), M_x *ess\,sup_a _0(· x)R(x,a). Then Mx−mx≤2BM_x-m_x≤ 2B. Let Zx≔∫π0(a′∣x)exp(ηR(x,a′))a′.Z_x _A _0(a x) (η R(x,a ))\,da . Since eηR(x,a′)∈[eηmx,eηMx]e^η R(x,a )∈[e^η m_x,e^η M_x] for π0(⋅∣x) _0(· x)-a.e. a′a , one has eηmx≤Zx≤eηMx.e^η m_x≤ Z_x≤ e^η M_x. Therefore, for π0(⋅∣x) _0(· x)-a.e. a, e−η(Mx−mx)≤eηR(x,a)Zx≤eη(Mx−mx)≤e2ηB.e^-η(M_x-m_x)≤ e^η R(x,a)Z_x≤ e^η(M_x-m_x)≤ e^2η B. Because dπR(⋅∣x)dπ0(⋅∣x)(a)=eηR(x,a)Zx, d _R(· x)d _0(· x)(a)= e^η R(x,a)Z_x, the claim follows. ∎ For the martingale arguments below, let HtH_t denote the interaction history through round t, and let ℋt≔σ(Ht) H_t σ(H_t) be the induced filtration. Lemma 16 (Deviation tail bound via an ϵε-net). Assume ℱF is bounded in ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0) by B, and that at each round every slate coordinate is sampled from a distribution absolutely continuous with respect to π0(⋅∣x) _0(· x). Let ℒt(R)≔1t∑s=1t[ℓs(R)∣ℋs−1],bt≔supR∈ℱ|ℒ^t(R)−ℒt(R)|.L_t(R) 1t _s=1^tE[ _s(R) H_s-1], b_t _R | L_t(R)-L_t(R) |. Fix ϵ>0ε>0 and let ϵC_ε be a finite ϵε-net of ℱF in ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0). Then for every t≥1t≥ 1 and every u>0u>0, ℙ(bt≥u+4ϵ)≤2|ϵ|exp(−tu22ℓmax2),ℓmax≔logK+2B.P (b_t≥ u+4ε )≤ 2\,|C_ε|\, \! (- tu^22 _ ^2 ), _ K+2B. Proof. Fix t and define Zs(R)=ℓs(R)−[ℓs(R)∣ℋs−1],s=1,…,t.Z_s(R)= _s(R)-E[ _s(R) H_s-1], s=1,…,t. For each fixed R, (Zs(R))s=1t(Z_s(R))_s=1^t is a martingale-difference sequence with respect to (ℋs)( H_s). By Lemma 12, 0≤ℓs(R)≤ℓmax,0≤ _s(R)≤ _ , so |Zs(R)|≤ℓmax|Z_s(R)|≤ _ almost surely. Azuma–Hoeffding therefore gives, for any fixed R and any u>0u>0, ℙ(|1t∑s=1tZs(R)|≥u)≤2exp(−tu22ℓmax2).P\! ( | 1t _s=1^tZ_s(R) |≥ u )≤ 2 \! (- tu^22 _ ^2 ). Apply a union bound over R∈ϵR _ε: ℙ(supR∈ϵ|ℒ^t(R)−ℒt(R)|≥u)≤2|ϵ|exp(−tu22ℓmax2).P\! ( _R _ε | L_t(R)-L_t(R) |≥ u )≤ 2|C_ε| \! (- tu^22 _ ^2 ). Now fix any R∈ℱR and choose R′∈ϵR _ε with ‖R−R′‖∞,supp(π0)≤ϵ.\|R-R \|_∞,supp( _0)≤ε. Because every slate coordinate is sampled from a distribution absolutely continuous with respect to π0(⋅∣xs) _0(· x_s), the realized actions lie in supp(π0(⋅∣xs))supp( _0(· x_s)) almost surely. Therefore, for each realized round s, |R(xs,as,k)−R′(xs,as,k)|≤ϵfor all k=1,…,K|R(x_s,a_s,k)-R (x_s,a_s,k)|≤ε all k=1,…,K almost surely. Define s(R)≔(R(xs,as,1),…,R(xs,as,K)).v_s(R) (R(x_s,a_s,1),…,R(x_s,a_s,K) ). Hence ‖s(R)−s(R′)‖∞≤ϵ\|v_s(R)-v_s(R )\|_∞≤ε almost surely. Lemma 12 yields |ℓs(R)−ℓs(R′)|≤2ϵ,| _s(R)- _s(R )|≤ 2ε, hence |ℒ^t(R)−ℒ^t(R′)|≤2ϵ,|ℒt(R)−ℒt(R′)|≤2ϵ.| L_t(R)- L_t(R )|≤ 2ε, |L_t(R)-L_t(R )|≤ 2ε. Consequently, |ℒ^t(R)−ℒt(R)|≤|ℒ^t(R′)−ℒt(R′)|+4ϵ. | L_t(R)-L_t(R) |≤ | L_t(R )-L_t(R ) |+4ε. Taking the supremum over R∈ℱR gives bt≤supR′∈ϵ|ℒ^t(R′)−ℒt(R′)|+4ϵ.b_t≤ _R _ε | L_t(R )-L_t(R ) |+4ε. Combining with the previous union bound proves the claim. ∎ Lemma 17 (ERM control of ε0 _0-substantial rounds from a loss gap). Let ℱF be a reward class that is compact under ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0) and bounded there by B: supR∈ℱ‖R‖∞,supp(π0)≤B. _R \|R\|_∞,supp( _0)≤ B. Fix a truth reward R⋆∈ℱR , let a⋆=aR⋆a =a_R , and define ⋆(R)≔X∼d0[R⋆(X,a⋆(X))−R⋆(X,aR(X))].G (R) _X d_0 [R (X,a (X))-R (X,a_R(X)) ]. From Lemma 4, let γ>0γ>0 be a witness to the following loss-gap condition: for every round t≥1t≥ 1, every realized history up to time t−1t-1, and every R∈ℱR satisfying ⋆(R)≥ε0G (R)≥ _0, [ℓt(R)−ℓt(R⋆)∣ℋt−1]≥γ.E [ _t(R)- _t(R ) H_t-1 ]≥γ. (9) Let ℓmax≔logK+2B,Nγ≔(ℱ,γ/32,∥⋅∥∞,supp(π0)),cγ≔γ2128ℓmax2. _ K+2B, N_γ \! (F,γ/32,\|·\|_∞,supp( _0) ), c_γ γ^2128\, _ ^2. Then: (i) For every t≥1t≥ 1, ℙ(⋆(R^t)≥ε0)≤2Nγe−cγt.P (G ( R_t)≥ _0 )≤ 2N_γe^-c_γt. (i) With probability 11, only finitely many t satisfy ⋆(R^t)≥ε0.G ( R_t)≥ _0. (i) Defining Nε0(∞)≔∑t=0∞⋆(R^t)≥ε0,N_ _0(∞) _t=0^∞1\G ( R_t)≥ _0\, one has [Nε0(∞)]≤1+⌈1cγlog(2Nγ)⌉+1ecγ−1.E[N_ _0(∞)]≤ 1+ 1c_γ (2N_γ) + 1e^c_γ-1. Proof. For the fixed truth reward R⋆R , define ℒt(R)≔1t∑s=1t[ℓs(R)∣ℋs−1],bt≔supR∈ℱ|ℒ^t(R)−ℒt(R)|.L_t(R) 1t _s=1^tE[ _s(R) H_s-1], b_t _R | L_t(R)-L_t(R) |. By definition of btb_t, for every R∈ℱR , ℒt(R)≤ℒ^t(R)+bt,ℒ^t(R)≤ℒt(R)+bt.L_t(R)≤ L_t(R)+b_t, L_t(R) _t(R)+b_t. Since R^t R_t is an ERM, ℒ^t(R^t)≤ℒ^t(R⋆). L_t( R_t)≤ L_t(R ). Combining gives, pathwise, ℒt(R^t)≤ℒ^t(R^t)+bt≤ℒ^t(R⋆)+bt≤ℒt(R⋆)+2bt,L_t( R_t)≤ L_t( R_t)+b_t≤ L_t(R )+b_t _t(R )+2b_t, hence ℒt(R^t)−ℒt(R⋆)≤2bt.L_t( R_t)-L_t(R )≤ 2b_t. (10) Let Etε0≔⋆(R^t)≥ε0.E_t _0 \G ( R_t)≥ _0\. Fix a sample path ω∈Etε0ω∈ E_t _0. By (9), for every s=1,…,ts=1,…,t, [ℓs(R^t(ω))−ℓs(R⋆)∣ℋs−1](ω)≥γ.E [ _s( R_t(ω))- _s(R ) H_s-1 ](ω)≥γ. Averaging over s=1,…,ts=1,…,t yields ℒt(R^t)(ω)−ℒt(R⋆)(ω)≥γ.L_t( R_t)(ω)-L_t(R )(ω)≥γ. If also bt(ω)<γ/4b_t(ω)<γ/4, then (10) gives ℒt(R^t)(ω)−ℒt(R⋆)(ω)≤2bt(ω)<γ/2,L_t( R_t)(ω)-L_t(R )(ω)≤ 2b_t(ω)<γ/2, a contradiction. Therefore Etε0⊆bt≥γ/4.E_t _0 \b_t≥γ/4\. Now take ϵ=γ/32ε=γ/32 and u=γ/8u=γ/8, so u+4ϵ=γ/4u+4ε=γ/4. Let γ/32C_γ/32 be a γ/32γ/32-net of ℱF with cardinality NγN_γ. Lemma 16 yields ℙ(bt≥γ/4)≤2Nγexp(−t(γ/8)22ℓmax2)=2Nγe−cγt,P(b_t≥γ/4)≤ 2N_γ \! (- t(γ/8)^22 _ ^2 )=2N_γe^-c_γt, where cγ=γ2128ℓmax2.c_γ= γ^2128\, _ ^2. This proves part (i). By part (i), ∑t=1∞ℙ(Etε0)≤2Nγ∑t=1∞e−cγt<∞. _t=1^∞P(E_t _0)≤ 2N_γ _t=1^∞e^-c_γt<∞. By Borel–Cantelli, ℙ(Etε0i.o.)=0,P(E_t _0\ i.o.)=0, which proves part (i). For part (i), [Nε0(∞)]=∑t=0∞ℙ(Etε0).E[N_ _0(∞)]= _t=0^∞P(E_t _0). Trivially, ℙ(E0ε0)≤1.P(E_0 _0)≤ 1. For t≥1t≥ 1, part (i) gives ℙ(Etε0)≤2Nγe−cγt.P(E_t _0)≤ 2N_γe^-c_γt. Hence [Nε0(∞)]≤1+∑t=1∞min1,2Nγe−cγt.E[N_ _0(∞)]≤ 1+ _t=1^∞ \1,2N_γe^-c_γt\. Set t0≔⌈1cγlog(2Nγ)⌉.t_0 1c_γ (2N_γ) . Then 2Nγe−cγt0≤12N_γe^-c_γt_0≤ 1. Therefore ∑t=1∞min1,2Nγe−cγt≤t0+∑t=t0+1∞2Nγe−cγt. _t=1^∞ \1,2N_γe^-c_γt\≤ t_0+ _t=t_0+1^∞2N_γe^-c_γt. For the tail sum, write t=t0+rt=t_0+r with r≥1r≥ 1: 2Nγe−cγt=(2Nγe−cγt0)e−cγr≤e−cγr.2N_γe^-c_γt=(2N_γe^-c_γt_0)e^-c_γr≤ e^-c_γr. Hence ∑t=t0+1∞2Nγe−cγt≤∑r=1∞e−cγr=1ecγ−1. _t=t_0+1^∞2N_γe^-c_γt≤ _r=1^∞e^-c_γr= 1e^c_γ-1. Combining the previous displays proves part (i). ∎ Lemma 18 (Expected one-step regret versus disagreement mass). Assume (C2). Then for every p,q∈p,q , Δmind0aq≠ap≤p(Rq)≤Δmaxd0aq≠ap. _ ^P\,d_0\a_q≠ a_p\ _p(R_q)≤ _ ^P\,d_0\a_q≠ a_p\. Proof of Lemma 18. Fix p,q∈p,q . Define Ep,q≔x∈:aq(x)≠ap(x)E_p,q \x :a_q(x)≠ a_p(x)\ and gp,q(x)≔Rp(x,ap(x))−Rp(x,aq(x)).g_p,q(x) R_p(x,a_p(x))-R_p(x,a_q(x)). By Condition (C2), there exists a measurable set Gp⊆G_p with d0(Gp)=1d_0(G_p)=1 such that for every x∈Gpx∈ G_p, Rp(x,ap(x))−supa∈supp(π0(⋅∣x)),a≠ap(x)Rp(x,a)≥Δmin.R_p(x,a_p(x))- _a ( _0(· x)),\ a≠ a_p(x)R_p(x,a)≥ _ ^P. If x∉Ep,qx∉ E_p,q, then aq(x)=ap(x)a_q(x)=a_p(x), so gp,q(x)=0.g_p,q(x)=0. If x∈Ep,q∩Gpx∈ E_p,q∩ G_p, then aq(x)≠ap(x)a_q(x)≠ a_p(x), hence by the defining gap on GpG_p, gp,q(x)≥Δmin.g_p,q(x)≥ _ ^P. Also, by definition of Δmax _ ^P, gp,q(x)≤Δmax∀x∈.g_p,q(x)≤ _ ^P ∀ x . Therefore Δmin 1Ep,q∩Gp(x)≤gp,q(x)≤Δmax 1Ep,q(x)∀x∈. _ ^P\,1_E_p,q∩ G_p(x)≤ g_p,q(x)≤ _ ^P\,1_E_p,q(x) ∀ x . Since d0(Gp)=1d_0(G_p)=1, one has Ep,q∩Gp=Ep,qd0-a.s.1_E_p,q∩ G_p=1_E_p,q d_0-a.s. Hence Δmin 1Ep,q(x)≤gp,q(x)≤Δmax 1Ep,q(x)d0-a.s. _ ^P\,1_E_p,q(x)≤ g_p,q(x)≤ _ ^P\,1_E_p,q(x) d_0-a.s. Taking expectations with respect to X∼d0X d_0 yields the claim. ∎ Lemma 19 (Local stability of the temperature-zero selector). Assume (C2). If p,q∈p,q satisfy ‖Rq−Rp‖∞,supp(π0)<Δmin2,\|R_q-R_p\|_∞,supp( _0)< _ ^P2, then aq(X)=ap(X)d0-a.s.a_q(X)=a_p(X) d_0-a.s. Proof. Let Ep,q≔x∈:aq(x)≠ap(x).E_p,q \x :a_q(x)≠ a_p(x)\. Suppose, toward a contradiction, that d0(Ep,q)>0.d_0(E_p,q)>0. By Condition (C2), there exists a measurable set Gp⊆G_p with d0(Gp)=1d_0(G_p)=1 such that for every x∈Gpx∈ G_p, Rp(x,ap(x))−supa∈supp(π0(⋅∣x)),a≠ap(x)Rp(x,a)≥Δmin.R_p(x,a_p(x))- _a ( _0(· x)),\ a≠ a_p(x)R_p(x,a)≥ _ ^P. Hence d0(Ep,q∩Gp)>0,d_0(E_p,q∩ G_p)>0, so we may choose x∈Ep,q∩Gpx∈ E_p,q∩ G_p. Then aq(x)≠ap(x)a_q(x)≠ a_p(x), and since aq(x)a_q(x) maximizes Rq(x,⋅)R_q(x,·) over supp(π0(⋅∣x))supp( _0(· x)), Rq(x,aq(x))≥Rq(x,ap(x)).R_q(x,a_q(x))≥ R_q(x,a_p(x)). Also, because x∈Gpx∈ G_p and aq(x)≠ap(x)a_q(x)≠ a_p(x), Rp(x,ap(x))≥Rp(x,aq(x))+Δmin.R_p(x,a_p(x))≥ R_p(x,a_q(x))+ _ ^P. Subtracting the second display from the first gives (Rq−Rp)(x,aq(x))−(Rq−Rp)(x,ap(x))≥Δmin. (R_q-R_p )(x,a_q(x))- (R_q-R_p )(x,a_p(x))≥ _ ^P. Therefore at least one of |Rq(x,aq(x))−Rp(x,aq(x))|,|Rq(x,ap(x))−Rp(x,ap(x))| |R_q(x,a_q(x))-R_p(x,a_q(x)) |, |R_q(x,a_p(x))-R_p(x,a_p(x)) | is at least Δmin/2 _ ^P/2. Hence ‖Rq−Rp‖∞,supp(π0)≥Δmin2,\|R_q-R_p\|_∞,supp( _0)≥ _ ^P2, contradicting the hypothesis. Therefore d0(Ep,q)=0d_0(E_p,q)=0, i.e. aq(X)=ap(X)d0-a.s.a_q(X)=a_p(X) d_0-a.s. ∎ Proof of Lemma 2. Define an equivalence relation on P by p∼q⟺ap(X)=aq(X)d0-a.s.p q a_p(X)=a_q(X) d_0-a.s. Let [p][p] denote the corresponding selector class. We first show that only finitely many selector classes can occur. Suppose, toward a contradiction, that there are infinitely many distinct selector classes. Then we may choose p1,p2,p3,⋯∈p_1,p_2,p_3,… such that [pi]≠[pj][p_i]≠[p_j] whenever i≠ji≠ j. For each i≠ji≠ j, one has d0api≠apj>0.d_0\a_p_i≠ a_p_j\>0. Hence, by the contrapositive of Lemma 19, ‖Rpi−Rpj‖∞,supp(π0)≥Δmin2for all i≠j.\|R_p_i-R_p_j\|_∞,supp( _0)≥ _ ^P2 all i≠ j. Thus Rpi:i≥1\R_p_i:i≥ 1\ is an infinite Δmin/2 _ ^P/2-separated subset of ℱF_P. But ℱF_P is compact under ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0) by Condition (C1), hence totally bounded, so no such infinite separated subset can exist. Therefore only finitely many selector classes occur. Let a(1),…,a(m)a^(1),…,a^(m) be representatives of these finitely many selector classes. If m=1m=1, then every pair p,q∈p,q satisfies ap(X)=aq(X)d0-a.s.a_p(X)=a_q(X) d_0-a.s. and therefore p(Rq)=0∀p,q∈.G_p(R_q)=0 ∀ p,q . In this case the conclusion holds for any positive choice of εiso>0; _iso^P>0; for concreteness, take εiso≔Δmin. _iso^P _ ^P. Assume now that m≥2m≥ 2. Define δ≔min1≤i<j≤md0a(i)≠a(j). _P _1≤ i<j≤ md_0\a^(i)≠ a^(j)\. Because the classes are distinct modulo d0d_0-a.s. equality, every term in this finite minimum is strictly positive, hence δ>0. _P>0. Set εiso≔Δminδ. _iso^P _ ^P\, _P. Fix any p,q∈p,q . If aq=apa_q=a_p d0d_0-a.s., then by definition p(Rq)=0.G_p(R_q)=0. Otherwise aqa_q and apa_p belong to two distinct selector classes, so d0aq≠ap≥δ.d_0\a_q≠ a_p\≥ _P. Applying Lemma 18 gives p(Rq)≥Δmind0aq≠ap≥Δminδ=εiso.G_p(R_q)≥ _ ^P\,d_0\a_q≠ a_p\≥ _ ^P\, _P= _iso^P. Therefore p(Rq)∈0∪[εiso,∞),G_p(R_q)∈\0\∪[ _iso^P,∞), as claimed. ∎ For the bounded-regret proof, it is convenient to introduce two proof-only quantities. Define the number of ε0 _0-substantial rounds up to horizon T by Np,ε0(T)≔∑t=0T−1p(R^t)≥ε0.N_p, _0(T) _t=0^T-11\G_p( R_t)≥ _0\. (11) To control these substantial-regret rounds, define a truth-centered population loss. Let X∼d0,=(A1,…,AK)∼π0(⋅∣X)⊗K,Y∼PRp(⋅∣X,).X d_0, =(A_1,…,A_K) _0(· X) K, Y P_R_p(· X,A). For any centered reward R, write R≔(R(X,A1),…,R(X,AK)),v_R (R(X,A_1),…,R(X,A_K) ), and define ℒp(R)≔[ℓ(R,Y)].L_p(R) [ (v_R,Y) ]. (12) Whenever R⋆=Rp∈ℱR =R_p _P is used as the truth reward, we also write R⋆(R)≔p(R),ℒR⋆(R)≔ℒp(R).G_R (R) _p(R), _R (R) _p(R). These quantities are well defined because both the MNL law and the temperature-zero selector depend only on the truth reward. Lemma 20 (Continuity of the truth-centered regret and risk maps). Assume (C1)–(C2). Then the maps (R⋆,R)⟼R⋆(R)and(R⋆,R)⟼ℒR⋆(R)−ℒR⋆(R⋆)(R ,R) _R (R) (R ,R) _R (R)-L_R (R ) are continuous on ℱ2F_P^2. Proof of Lemma 20. Let (Rn⋆,Rn)→(R⋆,R) (R_n ,R_n )→ (R ,R ) in ℱ2.in F_P^2. Then ‖Rn⋆−R⋆‖∞,supp(π0)→0,‖Rn−R‖∞,supp(π0)→0.\|R_n -R \|_∞,supp( _0)→ 0, \|R_n-R\|_∞,supp( _0)→ 0. Choose truths pn,p∈p_n,p and qn,q∈q_n,q such that Rn⋆=Rpn,R⋆=Rp,Rn=Rqn,R=Rq.R_n =R_p_n, R =R_p, R_n=R_q_n, R=R_q. By Lemma 19, for all sufficiently large n, aRn⋆=aR⋆andaRn=aRd0-a.s.a_R_n =a_R a_R_n=a_R d_0-a.s. Hence for all sufficiently large n, Rn⋆(Rn)=[Rn⋆(X,aR⋆(X))−Rn⋆(X,aR(X))].G_R_n (R_n)=E [R_n (X,a_R (X))-R_n (X,a_R(X)) ]. The integrand is uniformly bounded by 2B2B_P and converges pointwise d0d_0-a.s. to R⋆(X,aR⋆(X))−R⋆(X,aR(X)).R (X,a_R (X))-R (X,a_R(X)). Dominated convergence therefore yields Rn⋆(Rn)→R⋆(R).G_R_n (R_n) _R (R). We next prove continuity of (R⋆,R)↦ℒR⋆(R)−ℒR⋆(R⋆)(R ,R) _R (R)-L_R (R ). Fix a realized (x,)(x,a). Because the softmax map and the MNL log-loss are continuous in the reward vector, the integrand (R⋆,R,x,)⟼Y∼PR⋆(⋅∣x,)[ℓ(R,Y)−ℓ(R⋆,Y)](R ,R,x,a) _Y P_R (· x,a) [ (v_R,Y)- (v_R ,Y) ] is continuous in (R⋆,R)(R ,R). By Lemma 12, the absolute value of this integrand is uniformly bounded by 2(logK+2B)2( K+2B_P). Another application of dominated convergence yields the claimed continuity. ∎ Lemma 21 (Supportwise upgrade of almost-sure equality). Let (,d)(A,d) be a separable metric space, let μ be a Borel probability measure on A, and let S≔supp(μ)S (μ) be its topological support. If f:S→ℝf:S is continuous and f=0f=0 μ-a.s., then f≡0f≡ 0 on S. More generally, if f,g:S→ℝf,g:S are continuous and f=gf=g μ-a.s., then f=gf=g on S. Proof. Because A is separable metric, it is second countable, hence Lindelöf. Let O≔∖S.O S. By definition of the topological support, for every a∈Oa∈ O there exists an open neighborhood Va⊆V_a such that a∈Vaa∈ V_a and μ(Va)=0μ(V_a)=0. Thus Va:a∈O\V_a:a∈ O\ is an open cover of O. Since O is Lindelöf, there exist a1,a2,⋯∈Oa_1,a_2,…∈ O such that O⊆⋃m=1∞Vam.O _m=1^∞V_a_m. Therefore μ(O)≤∑m=1∞μ(Vam)=0.μ(O)≤ _m=1^∞μ(V_a_m)=0. Hence μ(∖S)=0.μ(A S)=0. Now let f:S→ℝf:S be continuous and suppose f=0f=0 μ-a.s. Assume for contradiction that there exists a0∈Sa_0∈ S with f(a0)≠0f(a_0)≠ 0. By continuity of f on the subspace S, there exist δ>0δ>0 and an open set U⊆U containing a0a_0 such that |f(a)|≥δ∀a∈U∩S.|f(a)|≥δ ∀ a∈ U∩ S. Because a0∈S=supp(μ)a_0∈ S=supp(μ), every open neighborhood of a0a_0 has positive μ-mass, so μ(U)>0.μ(U)>0. Since μ(∖S)=0μ(A S)=0, μ(U∩S)=μ(U)>0.μ(U∩ S)=μ(U)>0. But f=0f=0 μ-a.s., contradicting |f|≥δ|f|≥δ on U∩SU∩ S. Thus f≡0f≡ 0 on S. The second statement follows by applying the first statement to the continuous function f−gf-g. ∎ Proof of Lemma 3. Define Kp,R(x,)≔KL(PRp(⋅∣x,)∥PR(⋅∣x,)),=(a1,…,aK)∈K.K_p,R(x,a) \! (P_R_p(· x,a)\, \|\,P_R(· x,a) ), =(a_1,…,a_K) ^K. By Lemma 13, ℒp(R)−ℒp(Rp)=[Kp,R(X,)],L_p(R)-L_p(R_p)=E [K_p,R(X,A) ], where X∼d0,∼π0(⋅∣X)⊗K.X d_0, _0(· X) K. Assume ℒp(R)=ℒp(Rp).L_p(R)=L_p(R_p). Then [Kp,R(X,)]=0.E [K_p,R(X,A) ]=0. Since Kp,R≥0K_p,R≥ 0, Tonelli’s theorem yields 0=∫KKp,R(x,)π0(⋅∣x)⊗K(d)d0(dx).0= _X _A^KK_p,R(x,a)\, _0(· x) K(da)\,d_0(dx). Hence there exists a measurable set G⊆G with d0(G)=1d_0(G)=1 such that for every x∈Gx∈ G, Kp,R(x,)=0π0(⋅∣x)⊗K-a.e. .K_p,R(x,a)=0 _0(· x) K-a.e.\ a. Fix any x∈Gx∈ G such that both a⟼R(x,a)anda⟼Rp(x,a)a R(x,a) a R_p(x,a) are continuous on Sx≔supp(π0(⋅∣x))S_x ( _0(· x)). By Condition (C1), this holds for d0d_0-a.e. x. Define hx(a)≔R(x,a)−Rp(x,a),a∈Sx.h_x(a) R(x,a)-R_p(x,a), a∈ S_x. Because Kp,R(x,)=0K_p,R(x,a)=0, the two MNL laws coincide on a π0(⋅∣x)⊗K _0(· x) K-full set of slates. For every such slate =(a1,…,aK)a=(a_1,…,a_K), equality of the coordinate-11 and coordinate-22 odds gives PR(Y=1∣x,)PR(Y=2∣x,)=PRp(Y=1∣x,)PRp(Y=2∣x,). P_R(Y=1 x,a)P_R(Y=2 x,a)= P_R_p(Y=1 x,a)P_R_p(Y=2 x,a). Under the MNL model, PR(Y=1∣x,)PR(Y=2∣x,)=exp(R(x,a1)−R(x,a2)), P_R(Y=1 x,a)P_R(Y=2 x,a)= \! (R(x,a_1)-R(x,a_2) ), and similarly for RpR_p. Therefore hx(a1)−hx(a2)=0π0(⋅∣x)⊗K-a.e. .h_x(a_1)-h_x(a_2)=0 _0(· x) K-a.e.\ a. Since the event hx(a1)≠hx(a2)\h_x(a_1)≠ h_x(a_2)\ depends only on (a1,a2)(a_1,a_2), integrating out coordinates 3,…,K3,…,K yields π0(⋅∣x)⊗2(hx(a)≠hx(b))=0. _0(· x) 2\! (h_x(a)≠ h_x(b) )=0. Thus, if A,B∼i.i.d.π0(⋅∣x)A,B i.i.d. _0(· x), then hx(A)=hx(B)a.s.h_x(A)=h_x(B) .s. Because R,Rp∈ℱR,R_p _P, both are bounded on SxS_x; hence hx(A)∈L2h_x(A)∈ L^2. Using that A,BA,B are i.i.d., we obtain 0=[(hx(A)−hx(B))2]=2Var(hx(A)).0=E [(h_x(A)-h_x(B))^2 ]=2\,Var(h_x(A)). Therefore there exists cx∈ℝc_x such that hx(a)=cxπ0(⋅∣x)-a.s. a.h_x(a)=c_x _0(· x)-a.s.\ a. Both R and RpR_p are π0 _0-centered, so 0=∫hx(a)π0(da∣x)=cx.0= h_x(a)\, _0(da x)=c_x. Hence hx(a)=0π0(⋅∣x)-a.s. a.h_x(a)=0 _0(· x)-a.s.\ a. Since hxh_x is continuous on SxS_x, Lemma 21 yields hx(a)=0∀a∈Sx.h_x(a)=0 ∀ a∈ S_x. That is, R(x,a)=Rp(x,a)∀a∈Sx.R(x,a)=R_p(x,a) ∀ a∈ S_x. Since this holds for d0d_0-a.e. x, the two rewards agree on the entire feasible set on those contexts. Hence aR(x)=ap(x)d0-a.s.a_R(x)=a_p(x) d_0-a.s. under the common measurable tie-breaking convention, and therefore p(R)=X∼d0[Rp(X,ap(X))−Rp(X,aR(X))]=0.G_p(R)=E_X d_0 [R_p(X,a_p(X))-R_p(X,a_R(X)) ]=0. ∎ Proof of Lemma 4. Define Kε0≔(R⋆,R)∈ℱ2:R⋆(R)≥ε0.K_ _0 \(R ,R) _P^2:\ G_R (R)≥ _0 \. By Condition (C1), the set ℱ2F_P^2 is compact. By Lemma 20, the map (R⋆,R)⟼R⋆(R)(R ,R) _R (R) is continuous, so Kε0K_ _0 is closed in a compact set and therefore compact. If Kε0=∅K_ _0= , then the implication R⋆(R)≥ε0⟹ℒR⋆(R)−ℒR⋆(R⋆)≥γ,ε0G_R (R)≥ _0 _R (R)-L_R (R )≥ _P, _0 is vacuous for every choice of γ,ε0>0 _P, _0>0; for concreteness, choose γ,ε0=1 _P, _0=1. Assume now that Kε0≠∅K_ _0≠ . Define Ψ(R⋆,R)≔ℒR⋆(R)−ℒR⋆(R⋆). (R ,R) _R (R)-L_R (R ). By Lemma 20, Ψ is continuous on Kε0K_ _0, so Ψ attains its minimum there at some pair (R¯⋆,R¯)∈Kε0( R , R)∈ K_ _0. Suppose for contradiction that Ψ(R¯⋆,R¯)=0. ( R , R)=0. Write R¯⋆=Rp¯ R =R_ p for some p¯∈ p . Then ℒp¯(R¯)=ℒp¯(Rp¯),L_ p( R)=L_ p(R_ p), so Lemma 3 yields p¯(R¯)=0.G_ p( R)=0. Equivalently, R¯⋆(R¯)=0,G_ R ( R)=0, which contradicts (R¯⋆,R¯)∈Kε0( R , R)∈ K_ _0. Therefore min(R⋆,R)∈Kε0Ψ(R⋆,R)>0. _(R ,R)∈ K_ _0 (R ,R)>0. Choose γ,ε0≔min1,min(R⋆,R)∈Kε0Ψ(R⋆,R). _P, _0 \1,\ _(R ,R)∈ K_ _0 (R ,R) \. Then γ,ε0∈(0,∞) _P, _0∈(0,∞) and satisfies the stated implication. ∎ Lemma 22 (Fixed-scale control from a truth-centered loss gap). Assume (C1)–(C2), and fix ε0>0 _0>0. Let γ,ε0>0 _P, _0>0 be any finite witness from Lemma 4. Define γ≔β−Kγ,ε0,ℓmax≔logK+2B,γ β^-K _P, _0, _ K+2B_P, Nγ≔(ℱ,γ/32,∥⋅∥∞,supp(π0)),cγ≔γ2128ℓmax2,N_γ \! (F_P,γ/32,\|·\|_∞,supp( _0) ), c_γ γ^2128\, _ ^2, where (ℱ,ε,∥⋅∥)N(F, ,\|·\|) denotes the ε -covering number of ℱF under the displayed metric. Then Nγ<∞N_γ<∞, and for every truth p∈p and every t≥1t≥ 1, ℙp(p(R^t)≥ε0)≤2Nγe−cγt.P_p (G_p( R_t)≥ _0 )≤ 2N_γe^-c_γt. Consequently, supp∈p[Np,ε0(∞)]≤1+⌈1cγlog(2Nγ)⌉+1ecγ−1<∞, _p E_p[N_p, _0(∞)]≤ 1+ 1c_γ (2N_γ) + 1e^c_γ-1<∞, and, for every truth p∈p , only finitely many rounds satisfy p(R^t)≥ε0G_p( R_t)≥ _0 almost surely. Proof of Lemma 22. By Condition (C1), the reward class ℱ=Rp:p∈F_P=\R_p:p \ is compact under ∥⋅∥∞,supp(π0)\|·\|_∞,supp( _0). Hence Nγ=(ℱ,γ/32,∥⋅∥∞,supp(π0))<∞.N_γ=N\! (F_P,γ/32,\|·\|_∞,supp( _0) )<∞. Fix a truth p∈p . Consider any competitor R∈ℱR _P satisfying p(R)≥ε0.G_p(R)≥ _0. Condition on ℋt−1 H_t-1. By Lemma 13, [ℓt(R)−ℓt(Rp)∣ℋt−1]=[KL(PRp(⋅∣Xt,t)∥PR(⋅∣Xt,t))|ℋt−1].E [ _t(R)- _t(R_p) H_t-1 ]=E [KL (P_R_p(· X_t,A_t)\,\|\,P_R(· X_t,A_t) )\ |\ H_t-1 ]. The integrand is nonnegative. Since the ERM greedy learner deploys the KL-tilted policy (3), the bound ‖R‖∞,supp(π0)≤B\|R\|_∞,supp( _0)≤ B_P for R∈ℱR _P, and Lemma 15 imply that each slate coordinate is sampled from a distribution whose density ratio with respect to π0(⋅∣Xt) _0(· X_t) is bounded below by β−1β^-1. Applying Lemma 14 gives [ℓt(R)−ℓt(Rp)∣ℋt−1]≥β−K(ℒp(R)−ℒp(Rp)).E [ _t(R)- _t(R_p) H_t-1 ]≥β^-K (L_p(R)-L_p(R_p) ). Since γ,ε0 _P, _0 is a witness from Lemma 4, ℒp(R)−ℒp(Rp)≥γ,ε0,L_p(R)-L_p(R_p)≥ _P, _0, hence [ℓt(R)−ℓt(Rp)∣ℋt−1]≥β−Kγ,ε0=γ.E [ _t(R)- _t(R_p) H_t-1 ]≥β^-K _P, _0=γ. Thus γ=β−Kγ,ε0γ=β^-K _P, _0 is a witness to the loss-gap condition (9) in Lemma 17, with γ,ε0 _P, _0 supplied by Lemma 4. Together with Lemmas 13, 14, and 15, and the measurable ERM and tie-breaking conventions fixed earlier in this section, this verifies the hypotheses of Lemma 17 with R⋆=Rp,ℱ=ℱ,γ=β−Kγ,ε0.R =R_p, =F_P, γ=β^-K _P, _0. Applying Lemma 17 yields, for every t≥1t≥ 1, ℙp(p(R^t)≥ε0)≤2Nγe−cγt,P_p (G_p( R_t)≥ _0 )≤ 2N_γe^-c_γt, and also p[Np,ε0(∞)]≤1+⌈1cγlog(2Nγ)⌉+1ecγ−1.E_p[N_p, _0(∞)]≤ 1+ 1c_γ (2N_γ) + 1e^c_γ-1. Since the bound is uniform in p∈p , taking the supremum over truths gives the stated uniform bound. The almost-sure finiteness of ε0 _0-substantial rounds is the corresponding almost-sure conclusion of Lemma 17. ∎ Proof of Theorem 5. Let ε0≔εiso _0 _iso^P be the constant from Lemma 2. Fix any truth p∈p and any horizon T≥1T≥ 1. We first separate the initialization round t=0t=0, since R^0≡0 R_0≡ 0 need not belong to ℱF_P. By definition of Δmax _ ^P, 0≤p(R^0)≤Δmax.0 _p( R_0)≤ _ ^P. For every t≥1t≥ 1, however, the ERM estimator satisfies R^t∈ℱ. R_t _P. Hence Lemma 2 applies and yields p(R^t)>0⟹p(R^t)≥ε0.G_p( R_t)>0 _p( R_t)≥ _0. Since also 0≤p(R^t)≤Δmax,0 _p( R_t)≤ _ ^P, we obtain, for every t≥1t≥ 1, p(R^t)≤Δmax 1p(R^t)≥ε0.G_p( R_t)≤ _ ^P\,1\G_p( R_t)≥ _0\. Therefore Regret0,pERM(T)=p[p(R^0)]+∑t=1T−1p[p(R^t)]Regret_0,p^ERM(T)=E_p[G_p( R_0)]+ _t=1^T-1E_p[G_p( R_t)] ≤Δmax+Δmax∑t=1T−1ℙp(p(R^t)≥ε0).≤ _ ^P+ _ ^P _t=1^T-1P_p (G_p( R_t)≥ _0 ). Let γ,ε0>0 _P, _0>0 be any finite witness from Lemma 4, and define γ≔β−Kγ,ε0,Nγ≔(ℱ,γ/32,∥⋅∥∞,supp(π0)),cγ≔γ2128(logK+2B)2.γ β^-K _P, _0, N_γ \! (F_P,γ/32,\|·\|_∞,supp( _0) ), c_γ γ^2128( K+2B_P)^2. Applying Lemma 22 at this value of ε0 _0, we get for every t≥1t≥ 1, ℙp(p(R^t)≥ε0)≤2Nγe−cγt.P_p (G_p( R_t)≥ _0 )≤ 2N_γe^-c_γt. Hence Regret0,pERM(T)≤Δmax+Δmax∑t=1∞min1,2Nγe−cγt.Regret_0,p^ERM(T)≤ _ ^P+ _ ^P _t=1^∞ \1,2N_γe^-c_γt\. Set t0≔⌈1cγlog(2Nγ)⌉.t_0 1c_γ (2N_γ) . Then 2Nγe−cγt0≤12N_γe^-c_γt_0≤ 1, so ∑t=1∞min1,2Nγe−cγt≤t0+1ecγ−1. _t=1^∞ \1,2N_γe^-c_γt\≤ t_0+ 1e^c_γ-1. Therefore Regret0,pERM(T)≤Δmax(1+⌈1cγlog(2Nγ)⌉+1ecγ−1).Regret_0,p^ERM(T)≤ _ ^P (1+ 1c_γ (2N_γ) + 1e^c_γ-1 ). The bound is uniform in p∈p and T≥1T≥ 1, so taking the supremum completes the proof. ∎ Proof of Theorem 6. Fix the truth p∈p . We first verify that the selector aπa_π is well defined on ΠDPO _P^DPO. Let π∈ΠDPOπ∈ _P^DPO, and suppose π=πR=πR′for some R,R′∈ℱ.π= _R= _R some R,R _P. For each x∈x , write ZR(x)≔∫π0(a′∣x)eηR(x,a′)a′,ZR′(x)≔∫π0(a′∣x)eηR′(x,a′)a′.Z_R(x) _A _0(a x)e^η R(x,a )\,da , Z_R (x) _A _0(a x)e^η R (x,a )\,da . Since πR=πR′ _R= _R , their Radon–Nikodym derivatives with respect to π0(⋅∣x) _0(· x) agree π0(⋅∣x) _0(· x)-a.s., so for d0d_0-a.e. x, eηR(x,a)ZR(x)=eηR′(x,a)ZR′(x)π0(⋅∣x)-a.s. a. e^η R(x,a)Z_R(x)= e^η R (x,a)Z_R (x) _0(· x)-a.s.\ a. Taking logarithms, R(x,a)−R′(x,a)=1ηlogZR(x)−1ηlogZR′(x)π0(⋅∣x)-a.s. a.R(x,a)-R (x,a)= 1η Z_R(x)- 1η Z_R (x) _0(· x)-a.s.\ a. Thus there exists a scalar cxc_x such that R(x,a)−R′(x,a)=cxπ0(⋅∣x)-a.s. a.R(x,a)-R (x,a)=c_x _0(· x)-a.s.\ a. Because R−R′R-R is continuous on SxS_x for d0d_0-a.e. x, Lemma 21 implies R(x,a)−R′(x,a)=cx∀a∈Sx.R(x,a)-R (x,a)=c_x ∀ a∈ S_x. Therefore R(⋅,⋅)R(·,·) and R′(⋅,⋅)R (·,·) differ only by an a-independent constant on SxS_x, so aR(x)=aR′(x)d0-a.s.a_R(x)=a_R (x) d_0-a.s. Hence the definition aπ(x)≔aR(x)a_π(x) a_R(x) is well posed. We next compare the DPO empirical loss with the reward-space empirical loss. Fix any realized pairwise example (x,a1,a2,y)(x,a_1,a_2,y) with y∈1,2y∈\1,2\, and let R∈ℱR _P. For πR _R, 1η[logdπR(⋅∣x)dπ0(⋅∣x)(ay)−logdπR(⋅∣x)dπ0(⋅∣x)(a3−y)]=R(x,ay)−R(x,a3−y), 1η [ d _R(· x)d _0(· x)(a_y)- d _R(· x)d _0(· x)(a_3-y) ]=R(x,a_y)-R(x,a_3-y), because the normalizing term (1/η)logZR(x)(1/η) Z_R(x) cancels in the difference. Therefore the one-sample DPO loss equals −logσ(R(x,ay)−R(x,a3−y)).- σ\! (R(x,a_y)-R(x,a_3-y) ). Since −logσ(u−v)=log(eu+ev)−u,- σ(u-v)= (e^u+e^v)-u, we obtain, with u=R(x,ay)u=R(x,a_y) and v=R(x,a3−y)v=R(x,a_3-y), −logσ(R(x,ay)−R(x,a3−y))=log(eR(x,a1)+eR(x,a2))−R(x,ay)=ℓ(R(x,(a1,a2)),y).- σ\! (R(x,a_y)-R(x,a_3-y) )= \! (e^R(x,a_1)+e^R(x,a_2) )-R(x,a_y)= (v_R(x,(a_1,a_2)),y). Averaging over the first t rounds yields ℒ^tDPO(πR)=ℒ^t(R)∀R∈ℱ,t≥1. L^DPO_t( _R)= L_t(R) ∀ R _P,\ t≥ 1. Let R^t R_t be the measurable ERM selection fixed earlier in Section 4. Then πR^t _ R_t is a measurable exact minimizer of ℒ^tDPO L^DPO_t. Therefore, for t≥1t≥ 1, we may choose the exact online DPO iterate so that π^t=πR^t. π_t= _ R_t. Also, R^0≡0,πR^0=π0, R_0≡ 0, _ R_0= _0, so we may take π^0=π0=πR^0. π_0= _0= _ R_0. By the definition of aπa_π, aπ^t(x)=aR^t(x)d0-a.s.a_ π_t(x)=a_ R_t(x) d_0-a.s. for every t≥0t≥ 0. Therefore pDPO(π^t)=X∼d0[Rp(X,ap(X))−Rp(X,aπ^t(X))]=p(R^t).G_p^DPO( π_t)=E_X d_0 [R_p(X,a_p(X))-R_p(X,a_ π_t(X)) ]=G_p( R_t). Summing over t=0,…,T−1t=0,…,T-1, we get ∑t=0T−1p[pDPO(π^t)]=∑t=0T−1p[p(R^t)]=Regret0,pERM(T). _t=0^T-1E_p\! [G_p^DPO( π_t) ]= _t=0^T-1E_p\! [G_p( R_t) ]=Regret_0,p^ERM(T). Applying Theorem 5 now gives supp∈supT≥1∑t=0T−1p[pDPO(π^t)]≤Δmax(1+⌈1cγlog(2Nγ)⌉+1ecγ−1). _p _T≥ 1 _t=0^T-1E_p\! [G_p^DPO( π_t) ]≤ _ ^P (1+ 1c_γ (2N_γ) + 1e^c_γ-1 ). This proves the claim. ∎ NeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The abstract and introduction state the paper’s core contributions—formalizing temperature-zero regret and showing bounded O(1)O(1) cumulative temperature-zero regret for greedy online alignment—and these claims are exactly what the theory and simulation sections support. Guidelines: • The answer [N/A] means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 2. Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The paper discusses important scope limitations, including its focus on the MNL/BT preference model and the absence of large-scale or semi-real LLM experiments, in the “Extended discussions” appendix. Guidelines: • The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate “Limitations” section in their paper. • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: Each main theorem is stated with explicit assumptions, the main text provides proof sketches, and the appendix section “Proofs for Section 4” contains full proofs and supporting lemmas. Guidelines: • The answer [N/A] means that the paper does not include theoretical results. • All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 4. Experimental result reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Appendix C records the exact run underlying the main figure, including the reproduction command, the base seed 35003500, the accepted problem seed 35463546, the 20,00020,000-context probe-bank construction with target minimum gap 0.20.2 and realized minimum gap 0.27030.2703, the horizon T=200T=200, 5050 repeats, 40964096 evaluation contexts per iteration, and the precise Bradley–Terry fitting procedure (bounded L-BFGS-B with maxiter=50=50 and ftol=10−9=10^-9). Guidelines: • The answer [N/A] means that the paper does not include experiments. • If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: The supplemental repository contains the experiment driver Experiments/run_bt_temperature_zero.py, and Appendix C gives the exact command needed to regenerate them. Guidelines: • The answer [N/A] means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://neurips.c/public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.c/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results? Answer: [Yes] Justification: The main text specifies the synthetic Bradley–Terry setup and the appendix discloses the exact experimental details needed for reproduction: η∈1,2,3η∈\1,2,3\, dimension 55, 66 actions, horizon 200200, 5050 independent trajectories, fresh 40964096-context evaluation batches, the uniform reference policy, the pairwise data-collection rule, the accepted archived-run instance with seed 35463546 and realized minimum probe-bank gap 0.27030.2703, and the bounded L-BFGS-B maximum-likelihood fit for W^t W_t. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: The figures report the mean over 5050 independent trajectories, and Appendix C explicitly states that the shaded bands are pointwise standard errors computed as the sample standard deviation divided by 50 50; it also clarifies that the evaluation batches are independent of both the online trajectory and the probe bank. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates). • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Appendix C explains that the experiment is a lightweight single-process NumPy/SciPy/Matplotlib simulation that does not require a GPU, quantifies the dominant in-memory tensor at about 3333 MB in double precision, and reports the total optimization scale as 30,00030,000 bounded 2525-parameter L-BFGS-B solves, which is sufficient to characterize the practical compute footprint of the synthetic study. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper). 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.c/public/EthicsGuidelines? Answer: [Yes] Justification: The work is theoretical and simulation-based, does not involve human subjects or sensitive personal data, and the current draft does not appear to conflict with the NeurIPS Code of Ethics. Guidelines: • The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics. • If the authors answer [No] , they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [N/A] Justification: This is a theoretical paper that discusses existing algorithms. Guidelines: • The answer [N/A] means that there is no societal impact of the work performed. • If the authors answer [N/A] or [No] , they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)? Answer: [N/A] Justification: The paper does not release a high-risk pretrained model, scraped dataset, or comparable asset; the empirical component is a controlled synthetic simulation. Guidelines: • The answer [N/A] means that the paper poses no such risks. • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [N/A] Justification: The reported results do not appear to rely on externally distributed datasets, model checkpoints, or code assets whose licenses need to be documented in the paper; the empirical component is a synthetic simulation built for this work. Guidelines: • The answer [N/A] means that the paper does not use existing assets. • The authors should cite the original paper that produced the code package or dataset. • The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., C-BY 4.0) should be included for each asset. • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset’s creators. 13. New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [N/A] Justification: The current draft does not introduce or release a new dataset, model, or code asset alongside the submission. Guidelines: • The answer [N/A] means that the paper does not release new assets. • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [N/A] Justification: The paper does not involve crowdsourcing or research with human subjects; the preference feedback in the experiment is simulated. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [N/A] Justification: The paper does not involve human subjects research, so IRB approval or equivalent review is not applicable. Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 16. Declaration of LLM usage Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required. Answer: [N/A] Justification: The core method development and experiments do not use an LLM as an important or non-standard methodological component; LLMs appear only as application motivation. Guidelines: • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.