Paper deep dive
Reinforcement Learning with Conformal Action Sets: An Application to Sequential Recommendation
Wenwen Si, Honghao Wei
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Sequential recommenders typically use a fixed slate size even though the number of useful alternatives changes within a session. We propose Reinforcement Learning with Calibrated Pruning (RLCP), which adapts the retained action set using critic scores and an online threshold. The threshold is updated from binary feedback indicating whether the set contains an action in a proxy target. We prove a deterministic bound on the observed proxy miss rate along adaptive trajectories. To quantify the effect of pruning on reward, we derive an exact decomposition of value loss into filtering and selection losses. Under explicit proxy and critic approximation conditions, this decomposition yields a finite session reward bound that also accounts for imperfect selection and set truncation, without requiring the learning parameters to converge. Experiments on KuaiRand-Pure and MovieLens 1M compare two RLCP implementations with four RL baselines. In each of the 19 configurations, at least one RLCP variant achieves the highest catalog diversity, reaching $1.11\times$ to $5.21\times$ that of the strongest baseline, with competitive session depth and no larger retained sets.
Tags
Links
- Source: https://arxiv.org/abs/2610.08743v1
- Canonical: https://arxiv.org/abs/2610.08743v1
Trouble viewing inline? Open PDF directly →
Full Text
155,144 characters extracted from source content.
Expand or collapse full text
Reinforcement Learning with Conformal Action Sets: An Application to Sequential Recommendation Wenwen Si Honghao Wei University of Pennsylvania Washington State University Abstract Sequential recommenders typically use a fixed slate size even though the number of useful alternatives changes within a session. We propose Reinforcement Learning with Calibrated Pruning (RLCP), which adapts the retained action set using critic scores and an online threshold. The threshold is updated from binary feedback indicating whether the set contains an action in a proxy target. We prove a deterministic bound on the observed proxy miss rate along adaptive trajectories. To quantify the effect of pruning on reward, we derive an exact decomposition of value loss into filtering and selection losses. Under explicit proxy and critic approximation conditions, this decomposition yields a finite session reward bound that also accounts for imperfect selection and set truncation, without requiring the learning parameters to converge. Experiments on KuaiRand-Pure and MovieLens 1M compare two RLCP implementations with four RL baselines. In each of the 19 configurations, at least one RLCP variant achieves the highest catalog diversity, reaching 1.11×1.11× to 5.21×5.21× that of the strongest baseline, with competitive session depth and no larger retained sets. 1 Introduction Sequential recommendation aims to improve system utility over an entire user session, rather than optimize each interaction in isolation in a long-term deployment. Since a recommendation can affect both the current response and the user’s subsequent interests, reinforcement learning (RL) provides a natural framework for this objective (Afsar et al., 2022; Chen et al., 2021). Within this framework, many RL recommenders present a slate with a fixed predetermined number of items at every request (Zhao et al., 2018; Ie et al., 2019; Zhao et al., 2023). However, a fixed cardinality does not reflect how many useful alternatives are available and cannot account for changes in their quality. For example, a small set may suffice when preferences are clear, whereas a broader set can be valuable when several alternatives remain plausible. This mismatch motivates a different design criterion: retain a compact set while controlling the risk of excluding all valuable actions. Achieving this objective requires more than replacing the top M ranking rule with a threshold. First, the optimal long-term values used to define valuable actions are unknown. Although a learned critic can rank items, its score gaps are not themselves calibrated measures of retention. Second, filtering changes the available actions and, consequently, the states visited later in the session. As a result, a threshold calibrated under one policy need not satisfy a population retention requirement under another. Third, even when a valuable item is retained, the downstream actor or user choice mechanism may consistently select a poor alternative. Retention and selection must therefore be distinguished: keeping a valuable item does not by itself ensure a good decision. Together, these challenges call for an analysis that connects action set construction to sequential decision quality. To address these challenges, we introduce Reinforcement Learning with Calibrated Pruning (RLCP). In RLCP, a critic scores candidate items, an online threshold determines which items are retained, and a downstream selector chooses from the retained set. To calibrate the threshold, we update it using a binary signal indicating whether the raw set contains an action in a proxy target. Following adaptive conformal inference (Gibbs and Candes, 2021; Gibbs and Candès, 2024; Angelopoulos et al., 2024), this update gives a deterministic bound on the observed proxy miss frequency even as the critic, policy, and visited states change. The guarantee therefore concerns observable proxy retention, rather than retention defined by the unknown optimal value function. To account for how pruning affects future decisions, we evaluate expected set size under the state distribution of the policy that uses the retained actions. We prove that this policy’s value loss equals the discounted accumulation of two terms: the loss caused by filtering and the loss incurred by selecting among the retained actions. Under a condition relating proxy scores to optimal action values, calibration bounds the filtering loss, while critic accuracy and the downstream selection rule bound the selection loss. Combining these bounds gives a finite session reward guarantee, including the additional loss from imposing a maximum set size. The result allows the critic, policy, and threshold to change throughout the session and does not require their parameters to converge. Experiments in 19 simulator configurations show that RLCP can reach a broader item catalog while maintaining competitive session depth under the same set size cap as the baselines, as summarized in Figure 1. The main contributions are summarized below. Figure 1: Performance across the 19 experimental configurations. The axes are normalized, and set size is inverted so that larger values are preferable on every axis. RLCP improves catalog diversity while maintaining competitive session depth under the same set size cap as the baselines. The full detailed results and configurations are in Appendix F. Main contributions. 1. We develop RLCP to construct action sets through learned scores and online retention calibration. A bilevel formulation evaluates set size and retention under the policy induced by the retained actions, accounting for the effect of filtering on subsequent state visitation. 2. We establish a deterministic proxy miss bound and an exact value decomposition. Together, they give conditional bounds on discounted value and finite session reward that quantify the effects of proxy error, critic error, selection error, and set truncation. 3. We evaluate two RLCP implementations against four RL baselines on KuaiRand-Pure and MovieLens 1M. At least one variant achieves the highest catalog diversity in every configuration, with competitive session depth and mean retained sets no larger than the corresponding baseline slates. The conformal component builds on existing online calibration methods; our focus is how calibrated retention interacts with action filtering and sequential value. Appendix A places this contribution in the context of conformal recommendation and decision-making. Figure 2: RLCP framework. At state sks_k, critic scores gθk(sk,a)g_ _k(s_k,a) and threshold τk _k define the raw set Cθk,τk(sk)C_ _k, _k(s_k). A minimum score fallback ensures nonempty execution. The resulting set constrains the downstream actor in RLCP or supplies the simulator in RLCP Single. Proxy miss feedback updates the threshold more frequently than the critic is updated; this schedule is an implementation choice. 2 Problem Formulation We consider a finite discounted MDP ℳ=(,,P,r,γ,μ0)M=(S,A, P,r,γ, _0), where S and A are finite nonempty state and action spaces, P is the transition kernel, r(s,a)∈[0,1]r(s,a)∈[0,1] is the expected reward, γ∈[0,1)γ∈[0,1) is the discount factor, and μ0 _0 is the initial state distribution. At time t, the learner observes sts_t, selects ata_t, receives Rt∈[0,1]R_t∈[0,1], and observes st+1s_t+1. Let ℋtH_t contain the trajectory and all algorithmic information available before ata_t is sampled. The environment satisfies Pr(st+1=s′∣ℋt,at=a) (s_t+1=s _t,a_t=a) =P(s′∣st,a), =P(s s_t,a), (1) [Rt∣ℋt,at=a] [R_t _t,a_t=a] =r(st,a), =r(s_t,a), The learner may use the full history to update its policy, while the reward and transition laws depend only on the current state and action. Let Π be the set of stationary Markov policies. For π∈Ππ∈ , define the state value and state-action value functions as Vπ(s)=sπ[∑t=0∞γtRt],Qπ(s,a)=s,a∼π[∑t=0∞γtRt]. V^π(s)=E_s^π\! [ _t=0^∞γ^tR_t ],Q^π(s,a)=E_s,a π\! [ _t=0^∞γ^tR_t ]. (2) For a state distribution ν, write Vπ(ν)=s∼ν[Vπ(s)]V^π(ν)=E_s ν[V^π(s)]. The optimal values are V∗(s)=maxπ∈ΠVπ(s)V^*(s)= _π∈ V^π(s) and Q∗(s,a)=maxπ∈ΠQπ(s,a)Q^*(s,a)= _π∈ Q^π(s,a), with V∗(s)=maxaQ∗(s,a)V^*(s)= _aQ^*(s,a) and V∗(ν)=s∼ν[V∗(s)]V^*(ν)=E_s ν[V^*(s)]. We evaluate action sets under the normalized discounted state occupancy: dπ(s)=(1−γ)∑t=0∞γtPrπ(st=s∣s0∼μ0).d^π(s)=(1-γ) _t=0^∞γ^t ^π(s_t=s s_0 _0). (3) For a value tolerance ε≥0 ≥ 0, and α∈(0,1)α∈(0,1) is the target miss rate. Define the oracle target action set as ε∗(s)=a∈:Q∗(s,a)≥V∗(s)−ε.A^*_ (s)=\a :Q^*(s,a)≥ V^*(s)- \. (4) An action belongs to this set if its optimal continuation value is within ε of the best available value. This target specifies which actions should be retained, but it is unknown to the learner. 2.1 Action Filtering and Execution Since the oracle target ε∗(s)A^*_ (s) depends on the unknown Q∗Q^*, the learner cannot use it directly to filter actions. Instead, it uses a learned score gθ(s,a)∈ℝg_θ(s,a) , with smaller scores preferred. For a threshold τ∈ℝτ , the raw set consists of all actions whose scores do not exceed the threshold: Cθ,τ(s)=a:gθ(s,a)≤τ.C_θ,τ(s)=\a:g_θ(s,a)≤τ\. (5) When no action passes the threshold, the policy still needs an action to execute. We therefore fix an order on A and use the action with the smallest score as a fallback: aθmin(s)=first action in argminagθ(s,a).a_θ (s)=first action in _ag_θ(s,a). (6) The resulting execution set is always nonempty: C¯θ,τ(s)=Cθ,τ(s),Cθ,τ(s)≠∅,aθmin(s),Cθ,τ(s)=∅. C_θ,τ(s)= casesC_θ,τ(s),&C_θ,τ(s)≠ ,\\ \a_θ (s)\,&C_θ,τ(s)= . cases (7) The execution set determines which actions the downstream policy may select. To express this restriction, for any set map D satisfying ∅≠D(s)⊆ ≠ D(s) at every state, let Π(D)=π∈Π:suppπ(⋅∣s)⊆D(s),∀s∈ (D)=\π∈ :suppπ(· s) D(s),\ ∀ s \ denote the stationary policies supported on D. For the construction above, we therefore consider a downstream policy π∈Π(C¯θ,τ)π∈ ( C_θ,τ). In recommendation, D(s)D(s) represents an intermediate candidate set and need not coincide with the displayed slate. The item MDP applies when an item is selected before the current feedback is generated and, conditional on the current state and selected item, reward and transition no longer depend on the remaining collection. Appendix B.1 formalizes this requirement and explains when the collection itself must instead be modeled as the action. With execution specified, we next evaluate whether the threshold rule retains a valuable action. This evaluation uses the raw set Cθ,τ(s)C_θ,τ(s): retention succeeds when that set contains at least one action in the oracle target ε∗(s)A^*_ (s). The fallback serves a different purpose, namely, ensuring that execution remains possible. Thus an empty raw set counts as a retention failure even if the fallback action belongs to the oracle target, because no target action passed the threshold. Whether retention succeeds depends on the state. We therefore evaluate it under the normalized discounted occupancy dπd^π of the downstream policy π. For a target miss rate α∈(0,1)α∈(0,1), the desired retention condition is Prs∼dπ(Cθ,τ(s)∩ε∗(s)≠∅)≥1−α. _s d^π\! (C_θ,τ(s) ^*_ (s)≠ )≥ 1-α. (8) The condition allows the states where every oracle target action is removed to carry at most α of the discounted occupancy mass. The policy generating this occupancy is restricted by the execution set, so changing the threshold may change both the retained actions and the states on which retention is evaluated. Let mθ(s)=mina∈ε∗(s)gθ(s,a)m_θ(s)= _a ^*_ (s)g_θ(s,a) be the smallest score among oracle target actions. Retention succeeds exactly when this score passes the threshold: Cθ,τ(s)∩ε∗(s)≠∅⟺mθ(s)≤τ.C_θ,τ(s) ^*_ (s)≠ m_θ(s)≤τ. (9) This gives a scalar condition for threshold selection. The oracle margin is unavailable because its target depends on Q∗Q^*; RLCP will instead calibrate a proxy margin obtained from observable feedback. 2.2 Policy-Dependent Action-Set Objective A threshold determines which actions remain available throughout the session. The set size objective must therefore account for the policy that uses those actions. Fix a learned score gθg_θ and write Dθ,τ=C¯θ,τD_θ,τ= C_θ,τ. The best policy supported on this set has value Vθ,τ∗(μ0)=maxπ∈Π(Dθ,τ)Vπ(μ0).V^*_θ,τ( _0)= _π∈ (D_θ,τ)V^π( _0). (10) We denote the selected optimal response by πθ,τ∗π^*_θ,τ. A fixed lexicographic rule on optimal occupancies, together with a fixed action at states of zero occupancy, resolves ties; Appendix C gives the construction. We then minimize expected set size subject to retention under this response: Problem 2.1 (Occupancy-dependent threshold selection). For the score gθg_θ, consider minτ∈ℝ _τ Φθ(τ):=s∼dπθ,τ∗[|Dθ,τ(s)|] _θ(τ):=E_s d^π^*_θ,τ[|D_θ,τ(s)|] (11) s.t. .t. Prs∼dπθ,τ∗(Cθ,τ(s)∩ε∗(s)≠∅)≥1−α, _s d^π^*_θ,τ\! (C_θ,τ(s) ^*_ (s)≠ )≥ 1-α, πθ,τ∗∈argmaxπ∈Π(Dθ,τ)Vπ(μ0). π^*_θ,τ∈ _π∈ (D_θ,τ)V^π( _0). The inner problem determines how the retained actions are used, and the outer problem evaluates set size and retention under the resulting state occupancy. Consequently, a larger threshold may induce a different policy and change which states receive weight in the objective. The smallest feasible threshold need not minimize expected set size, unlike threshold selection under a fixed evaluation distribution. The score is fixed only when defining this benchmark. Allowing arbitrary scores in the outer optimization would admit the uninformative oracle solution of assigning the smallest score to one optimal action at each state and returning singleton sets. RLCP instead learns scores by value estimation and updates the threshold from proxy feedback. We do not assume that these coupled updates solve (11); the following guarantees apply while the score and policy continue to change. 3 Main Results In this section, we formally present our main results. We first bound the proxy miss frequency under the online threshold update. We then derive a value identity that separates the loss from filtering from the loss of selecting an action within the retained set. Combining the two results gives a reward bound for a policy that adapts during a finite session. Appendix C establishes the population benchmark, and the detailed proofs are deferred to Appendix D. 3.1 Retention Calibration During Learning When both the score and policy are fixed, the smallest threshold satisfying the retention requirement is the (1−α)(1-α) quantile of the oracle margin (Proposition C.3). During learning, however, updates to the score and policy can change the margin distribution, so a threshold calibrated at one stage need not remain valid later. To account for these changes, we adjust the threshold using observed misses rather than assuming a fixed margin distribution. A miss increases the threshold to make filtering less restrictive, whereas a hit decreases it. Specifically, we use the online calibration update (Gibbs and Candes, 2021; Angelopoulos et al., 2024) et=mt>τt,τt+1=τt+ηt(et−α).e_t=1\m_t> _t\, _t+1= _t+ _t(e_t-α). (12) Here mtm_t is a finite margin, ete_t is its miss indicator, and ηt>0 _t>0 is a nonincreasing step size. A miss raises the threshold by ηt(1−α) _t(1-α), making filtering less restrictive; a hit lowers it by ηtα _tα. Theorem 3.1 bounds the resulting miss frequency for any realized margin sequence. Theorem 3.1 (Pathwise miss-rate tracking). For any adaptive sequence of finite margins, define WT=maxτ1,m1,…,mT−minτ1,m1,…,mT.W_T= \ _1,m_1,…,m_T\- \ _1,m_1,…,m_T\. (13) Then, for every T≥1T≥ 1, |1T∑t=1Tet−α|≤WT+η1ηTT. | 1T _t=1^Te_t-α |≤ W_T+ _1 _TT. (14) If supTWT≤W<∞ _TW_T≤ W<∞ and ηTT→∞ _TT→∞, then T−1∑t=1Tet→αT^-1 _t=1^Te_t→α. If ηt≡η _t≡η, the always-valid finite-time form is |1T∑t=1Tet−α|≤WT+ηT, | 1T _t=1^Te_t-α |≤ W_T+η T, (15) and it is at most (W+η)/(ηT)(W+η)/(η T) under the uniform-width condition above. With bounded margin width and a constant step size, Theorem 3.1 gives an O(1/T)O(1/T) deviation of the observed miss frequency from α. The argument is deterministic: it requires neither independent margins nor a stationary margin distribution. It controls the average along the realized sequence, rather than retention at every state or convergence to a fixed population quantile. To apply the update without observing Q∗Q^*, RLCP uses a finite nonempty proxy target ~ε,t(st) A_ ,t(s_t). Its margin and miss indicator are m~t=mina∈~ε,t(st)gθt(st,a),e~t=m~t>τt. m_t= _a∈ A_ ,t(s_t)g_ _t(s_t,a), e_t=1\ m_t> _t\. (16) Setting mt=m~tm_t= m_t in Theorem 3.1 controls the observed proxy miss rate while the critic and actor change. The relation between this proxy target and actions with high optimal value determines what the guarantee implies for reward. A cap on set size can introduce misses even when the raw set retains a proxy target action. Let CtKC_t^K keep the K actions with the lowest scores in the raw set, or all actions if fewer than K are available. A capped miss is either a raw miss or a raw hit for which truncation removes every proxy target action. Calibration controls the former; the latter depends on the ranking and the cap. Appendix C.3 bounds the combined miss rate and characterizes feasibility under a fixed distribution. 3.2 From Retention to Long-Horizon Value Retaining a valuable action is not enough if the policy does not select it. Consider a single state with two actions giving rewards one and zero. Retaining both actions gives perfect retention, but a policy that always chooses the second receives zero reward (Proposition C.4). To account for this distinction, for a nonempty set map D and policy π∈Π(D)π∈ (D), define ΔD(s) _D(s) =V∗(s)−maxa∈D(s)Q∗(s,a), =V^*(s)- _a∈ D(s)Q^*(s,a), (17) ζπ,D(s) _π,D(s) =maxa∈D(s)Q∗(s,a)−∑a∈D(s)π(a∣s)Q∗(s,a). = _a∈ D(s)Q^*(s,a)- _a∈ D(s)π(a s)Q^*(s,a). The filtering loss ΔD _D is the gap between the best available action and the best retained action. The selection loss ζπ,D _π,D is the remaining gap between that retained action and the policy’s expected choice. The next identity shows how both losses accumulate under the states visited by the policy. Theorem 3.2 (Filtering–selection value identity). For every set map D satisfying D(s)≠∅D(s)≠ for every state and every stationary π∈Π(D)π∈ (D), V∗(μ0)−Vπ(μ0)=11−γs∼dπ[ΔD(s)+ζπ,D(s)].V^*( _0)-V^π( _0)= 11-γE_s d^π[ _D(s)+ _π,D(s)]. (18) Theorem 3.2 identifies where retention enters the control problem: it bounds the filtering term, while the downstream policy determines the selection term. Both losses use the same unrestricted optimal continuation values Q∗Q^*. A policy optimal under future action restrictions can therefore still have positive selection loss; this term is not just an error in optimizing the actor. For proxy retention to control filtering loss, the proxy must identify actions with small optimal value gaps. Suppose the proxy target consists of near maximizers of a score Q~ Q, and its pairwise gaps approximate those of Q∗Q^* up to a scale λ>0λ>0 and error δprox _prox (Assumption C.7). Proposition C.8 gives ~ε(s)⊆λε+δprox∗(s). A_ (s) ^*_λ + _prox(s). Thus a proxy hit retains an action whose optimal value gap is at most λε+δproxλ + _prox. For selection, a critic error bounded by δcrit _crit relative to Q∗Q^* and a maximization error δsel(s) _sel(s) within the retained set give ζπ,D(s)≤2δcrit+δsel(s) _π,D(s)≤ 2 _crit+ _sel(s). Substituting these bounds into the identity yields Corollary C.10. The approximation conditions are needed in addition to calibration: a critic trained to evaluate the current policy need not approximate the unrestricted Q∗Q^*. 3.3 Adaptive Finite Session Guarantee The preceding identity evaluates a stationary policy. During learning, however, the policy may change after every interaction. We handle these updates by applying the same loss decomposition at each stage and using the calibration bound along the resulting trajectory. Consider an undiscounted item MDP with H stages, rewards in [0,1][0,1], and optimal values Vh∗,Qh∗V_h^*,Q_h^*. Define ΔHmax _H =maxh,s,a[Vh∗(s)−Qh∗(s,a)], = _h,s,a[V_h^*(s)-Q_h^*(s,a)], εH _H =minλε+δprox,ΔHmax. = \λ + _prox, _H \. Here ΔHmax _H bounds the loss of any action, while εH _H bounds the loss of a retained proxy target under the stagewise proxy fidelity condition. Let δ¯sel,H δ_sel,H be the average expected selection error measured by the critic within the retained set, and let h¯HK h_H^K be the average probability that a raw proxy hit is lost under a cap of K actions. Appendix C.6 states the full information and approximation conditions. Theorem 3.3 (Finite-session proxy-to-value guarantee). Under Assumption C.12, let η1≥⋯≥ηH>0 _1≥·s≥ _H>0 and suppose the realized proxy-margin width is at most W almost surely. For V1RLCP(μ0)=[∑h=1HRh]V_1^RLCP( _0)=E[ _h=1^HR_h], V1∗(μ0)−V1RLCP(μ0) V_1^*( _0)-V_1^RLCP( _0) (19) ≤H[(1−α)εH+αΔHmax+2δcrit+δ¯sel,H ≤ H [(1-α) _H+α _H +2 _crit+ δ_sel,H +(ΔHmax−εH)(W+η1ηHH+h¯HK)]. +( _H - _H) ( W+ _1 _HH+ h_H^K ) ]. Without a size cap, take K=||K=|A| and h¯HK=0 h_H^K=0. The first two terms bound filtering loss on proxy hits and misses at the target rate α. The critic and selection errors account for the action chosen from the execution set. The final term adds the deviation from the target miss rate and the hits removed by the cap. All of these quantities are evaluated along the adaptive trajectory, so the bound does not require convergence of the critic, actor, or threshold. Its size still depends on the stated approximation errors. The reward determines what this bound measures. When reward indicates a nonterminal state and departure follows the item dynamics, it bounds truncated session depth. A bound for click or like reward does not imply the same depth guarantee, and a departure rule that depends on the entire collection requires a collection action model. Appendix B.1 discusses this distinction for recommendation. 4 RLCP Algorithm RLCP constructs the retained set from a critic Q^θt Q_ _t and an online threshold, as shown in Figure 2. At time t, the score of an action is its estimated value gap from the best candidate: gθt(s,a)=maxbQ^θt(s,b)−Q^θt(s,a).g_ _t(s,a)= _b Q_ _t(s,b)- Q_ _t(s,a). (20) Adding the same constant to all critic values at a state leaves these scores unchanged. Thresholding retains actions whose estimated gaps do not exceed τt _t. If the raw set exceeds the cap, we keep the actions with the smallest gaps; if it is empty, the fallback supplies a critic maximizer. The downstream selector then chooses from this execution set. Algorithm 1 gives the complete procedure. Algorithm 1 RLCP with Online Action-Set Calibration Input: target miss rate α; interaction budget T; threshold τ1 _1; nonincreasing ηt>0 _t>0; cap K≥1K≥ 1; critic Q^θ1 Q_ _1; selector πϕ1 _ _1; proxy-target verifier. 1 for t=1,…,Tt=1,…,T do 2 Observe sts_t and compute gθt(st,⋅)g_ _t(s_t,·) using (20). 3 Form Ct=a:gθt(st,a)≤τtC_t=\a:g_ _t(s_t,a)≤ _t\. 4 Keep the minK,|Ct| \K,|C_t|\ lowest-score actions to obtain CtKC_t^K. 5 Set Dt=CtKD_t=C_t^K if nonempty; otherwise set Dt=aθtmin(st)D_t=\a_ _t (s_t)\. 6 Define the proxy target for the current state and obtain the raw miss e~t=Ct∩~ε,t(st)=∅ e_t=1\C_t∩ A_ ,t(s_t)= \. 7 Sample at∼πϕt(⋅∣st,Dt)a_t _ _t(· s_t,D_t); observe Rt,st+1R_t,s_t+1. 8 Update τt+1=τt+ηt(e~t−α) _t+1= _t+ _t( e_t-α). 9 Update the critic and selector from interaction data. 10 end for Calibration feedback. The threshold update uses a binary signal indicating whether the raw set intersects the proxy target. This signal evaluates retention before the cap and fallback; neither operation changes the miss used for calibration. A verifier supplies the signal without revealing Q∗Q^*, and our simulator implements the verifier through its response model. For Theorem 3.3, the target must be defined before the current action is sampled, although the label may be revealed later. A target defined from the current realized responses can still be calibrated pathwise, but it does not satisfy this information condition. Feedback on the executed item alone generally cannot identify the required set event, so deployment requires a suitable verifier or counterfactual response model. Learning and selection. Interaction data update the critic and the selector, while raw proxy misses update the threshold. In our implementation, calibration is updated more frequently than the critic. The pathwise guarantee uses the unprojected update in (12); replacing raw misses with capped misses is a different procedure. The selector also determines whether pruning changes the executed action. The critic gap score, cap, and fallback all preserve a global critic maximizer. An exactly greedy selector using the same critic and tie rule therefore chooses the same action with or without pruning (Proposition C.13). RLCP instead regulates the alternatives available to a stochastic actor, slate constructor, or user choice mechanism. The experiments compare two such implementations. 5 Experiments We evaluate RLCP on the whole-session sequential recommendation task provided by the KuaiSim simulator (Zhao et al., 2023). This protocol emulates online policy interaction through full-session rollouts, in which KuaiSim generates user feedback, computes the corresponding rewards, and determines when the user leaves the session. Our experiments are designed to answer the following questions: • Q1: Can RLCP improve long-term recommendation performance under simulator-based sequential interaction? • Q2: Can RLCP produce reliable admissible action sets that contain high-quality recommendations while reducing the effective action space? 5.1 Datasets and Simulator We evaluate RLCP in the KuaiSim whole-session setting on KuaiRand-Pure (Gao et al., 2022), the dataset used to construct the original simulator, and on the MovieLens 1M migration demonstrated by KuaiSim (Harper and Konstan, 2015; Zhao et al., 2023). KuaiRand-Pure comes from Kuaishou logs in which uniformly sampled videos were inserted into ordinary feeds. KuaiSim contains six positive behaviors—click, long view, like, comment, follow, and forward—together with dislike and session departure. MovieLens 1M contains about 1M timestamped ratings. Following the KuaiSim migration, ratings above 3 are mapped to positive feedback (like), ratings at most 3 to negative feedback (hate), interactions are ordered chronologically, and day-level groups define sessions. Table 1 reports statistics for both datasets. Table 1: Statistics of the datasets used. Dataset Users Items Interactions Sessions Density KuaiRand -Pure 27,077 7,551 1,436,609 246,738 0.70% ML-1M 6,400 3,706 1,000,208 16,629 4.22% We modify KuaiSim’s leave module to make session length depend on the responses elicited by a recommendation. At each request, the recommender observes a user profile and recent interaction history, presents an item collection, and receives feedback from the immediate response model. We use is_click and is_like as reward signals. In our simulator inspection, click responses varied little across users, while like responses were more sensitive to user preferences. At step t, the leave module evaluates the admissible set Cθ,τ(st)C_θ,τ(s_t) for RLCP and the displayed slate for a baseline with fixed slate size. Patience decreases by p if the collection receives at least one positive response and by q>pq>p otherwise. The session ends when remaining patience falls below 11. We test (p,q)=(1,2)(p,q)=(1,2) and (0.4,2)(0.4,2), so a failure to elicit a positive response incurs the larger decrement in both settings. (a) Is_click, p,q=(1,2)p,q=(1,2). (b) Is_click, p,q=(0.4,2)p,q=(0.4,2). (c) Is_like, p,q=(1,2)p,q=(1,2). (d) Is_like, p,q=(0.4,2)p,q=(0.4,2). Figure 3: KuaiRand-Pure radar summaries for the four reward and patience configurations reported in Tables 2–5. Each panel averages over the baseline slate sizes in the corresponding table and shows depth, catalog diversity, intra-list diversity, and inverted set size, with larger radius indicating better performance. RLCP-Single gives the strongest catalog-diversity gains on KuaiRand-Pure while using equal or smaller admissible sets, whereas the full RLCP consistently attains the highest intra-list diversity. 5.2 Baselines and Metrics We compare RLCP with four whole-session sequential recommendation baselines provided by KuaiSim (Zhao et al., 2023): A2C (Mnih et al., 2016), DDPG (Lillicrap et al., 2016), TD3 (Fujimoto et al., 2018), and HAC (Liu et al., 2023); detailed descriptions are provided in Appendix E.1. We report session depth, average and total reward, catalog diversity, intra-list diversity (ILD), and average admissible-set size, following KuaiSim (Zhao et al., 2023). Depth is the primary session-level utility metric; catalog diversity measures the number of distinct items exposed across active user requests, ILD measures dissimilarity within a recommendation set, and set size measures filtering efficiency. Formal definitions are provided in Appendix E.2. 5.3 Method Implementation We instantiate RLCP with two variants that share the conformal set construction, online calibration objective, and coverage target. The realized state sts_t concatenates the user profile with the full within-session history of rollout actions (a0,a1,…,at−1)(a_0,a_1,…,a_t-1), so the critic and rollout policy condition on all previously executed actions. The variants differ only in how the admissible set becomes a rollout action. Full RLCP follows Algorithm 1: Cθ,τ(s)C_θ,τ(s) constrains a downstream slate actor trained through sequential rollouts, while τ is updated online to maintain the target miss rate for near-optimal items. Critic/score updates occur on the slow timescale, and slate-actor rollouts and threshold calibration on the fast timescale. (a) Is_click, p,q=(1,2)p,q=(1,2). (b) Is_click, p,q=(0.4,2)p,q=(0.4,2). (c) Is_like, p,q=(1,2)p,q=(1,2). (d) Is_like, p,q=(0.4,2)p,q=(0.4,2). Figure 4: ML-1M radar summaries for the four reward and patience configurations reported in Tables 6–9. Each panel averages over the baseline slate sizes in the corresponding table and uses the same normalized axes as Figure 3. On the denser ML-1M data, the full RLCP is more competitive in terms of depth and catalog diversity while maintaining maximal intra-list diversity, and the RLCP variants retain their overall diversity advantage over the fixed-slate baselines. RLCP-Single instead feeds the admissible set directly into the environment and uses the simulator’s first rewarded item as the rollout action, imitating real-world user behavior. This simplifies rollout while preserving the online calibration objective. Both variants target 1−α1-α coverage of ε -optimal items, apply a minimum-set-size rescue when required (usually 1), and use the same conformal mask logic to bound set size. Environment-Side Proxy. To operationalize the ε -optimal action set in (4), we use the Bernoulli success probability p^b(st,a) p_b(s_t,a) from the simulator’s immediate-response model and set Q~(st,a)=p^b(st,a), Q(s_t,a)= p_b(s_t,a), which induces ~ε(st)=a:Q~(st,a)≥maxjQ~(st,j)−ε A_ (s_t)= \a: Q(s_t,a)≥ _j Q(s_t,j)- \ as in (33). This conditional one-step expected reward is biased for the long-horizon Q∗Q^* in (4). The numerical value of Q~ Q is never exposed to the actor or critic; the simulator supplies only binary feedback indicating whether Cθt,τt(st)∩~ε(st)C_ _t, _t(s_t)∩ A_ (s_t) is nonempty. This emulates positive user feedback when a recommendation set contains a satisfactory item. Results. Across all 19 configurations, at least one RLCP variant achieves the highest catalog diversity without requiring a larger retained set. Within each configuration, the RLCP cap equals the baseline slate size M, and all methods share the simulator, reward signal, and patience setting. Appendix Tables 2 through 9 provide the full numerical results. These comparisons show broader catalog exposure with competitive session depth under matched set size budgets. As shown in Figure 3, RLCP-Single provides the strongest catalog exposure on KuaiRand-Pure. It achieves the highest catalog diversity in all ten configurations, reaching 1.48×1.48× to 4.56×4.56× that of the strongest baseline. Its mean retained set is smaller than M in nine configurations, with a maximum reduction of 25.5%25.5\%, and equals M in the remaining configuration. It also attains or ties the highest session depth in six configurations and stays within 0.40.4 interactions of the best method in the others. Full RLCP achieves the highest reported ILD of 1.001.00 throughout, but RLCP-Single generally provides a better balance between catalog exposure and session utility. As shown in Figure 4, the exposure advantage persists on ML-1M, where full RLCP becomes more competitive. It leads catalog diversity in five configurations, exceeds the strongest baseline in eight, and attains or ties the highest session depth in seven. It also maintains ILD 1.001.00 throughout and reduces mean set size below M in four configurations. RLCP-Single leads catalog diversity in the remaining four, giving the better variant in each configuration 1.11×1.11× to 5.21×5.21× the catalog diversity of the strongest baseline. Under the longer patience setting, this range is 3.17×3.17× to 5.21×5.21×, although several methods reach the depth ceiling of 4848. Thus the main benefit is broader exposure with competitive depth, rather than uniformly higher reward or a single variant that dominates every setting. 6 Conclusion We introduced RLCP, a conformal policy-learning framework for whole-session sequential recommendation. RLCP decouples critic-induced item scores from the calibrated threshold, producing state-dependent, variable-size sets rather than fixed-cardinality top-M slates. The threshold provides pathwise control of the realized average miss rate, while two-timescale learning jointly updates the score model, calibration threshold, and rollout policy. Across KuaiRand-Pure and ML-1M, RLCP remains competitive with fixed-slate baselines in session depth while using sets of equal or smaller size and improving diversity. An RLCP variant achieves the highest catalog diversity in every configuration, and full RLCP consistently achieves the highest within-slate diversity. These results support conformal policy learning for retaining near-optimal recommendations, controlling set size, and broadening exposure without fixing slate cardinality in advance. References Afsar et al. (2022) M. M. Afsar, T. Crump, and B. Far Reinforcement learning based recommender systems: a survey. ACM Computing Surveys 55 (7), p. 1–38. Cited by: Appendix A, §1. Angelopoulos and Bates (2023) A. N. Angelopoulos and S. Bates Conformal prediction: a gentle introduction. Foundations and Trends in Machine Learning 16 (4), p. 494–591. External Links: Document Cited by: Appendix A. Angelopoulos et al. (2023) A. N. Angelopoulos, K. Krauth, S. Bates, Y. Wang, and M. I. Jordan Recommendation systems with distribution-free reliability guarantees. In Proceedings of the Twelfth Symposium on Conformal and Probabilistic Prediction with Applications, Proceedings of Machine Learning Research, Vol. 204, p. 175–193. Cited by: Appendix A. Angelopoulos et al. (2024) A. N. Angelopoulos, R. Barber, and S. Bates Online conformal prediction with decaying step sizes. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 1616–1630. Cited by: Appendix A, §1, §3.1. Bastani et al. (2022) O. Bastani, V. Gupta, C. Jung, G. Noarov, R. Ramalingam, and A. Roth Practical adversarial multivalid conformal prediction. In Advances in Neural Information Processing Systems, Vol. 35, p. 29362–29373. Cited by: Appendix A. Chen et al. (2021) X. Chen, L. Yao, J. McAuley, G. Zhou, and X. Wang A survey of deep reinforcement learning in recommender systems: a systematic review and future directions. arXiv preprint arXiv:2109.03540. Cited by: Appendix A, §1. De Toni et al. (2025) G. De Toni, E. Purificato, E. Gomez, A. Passerini, B. Lepri, and C. Consonni You don’t bring me flowers: mitigating unwanted exposure in recommender systems. In Proceedings of the Nineteenth ACM Conference on Recommender Systems, p. 492–502. External Links: Document Cited by: Appendix A. Dixit et al. (2023) A. Dixit, L. Lindemann, S. X. Wei, M. Cleaveland, G. J. Pappas, and J. W. Burdick Adaptive conformal prediction for motion planning among dynamic agents. In Proceedings of the 5th Annual Learning for Dynamics and Control Conference, Proceedings of Machine Learning Research, Vol. 211, p. 300–314. Cited by: Appendix A. Fujimoto et al. (2018) S. Fujimoto, H. van Hoof, and D. Meger Addressing function approximation error in actor-critic methods. In Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 80, p. 1587–1596. Cited by: 3rd item, §5.2. Gao et al. (2022) C. Gao, S. Li, Y. Zhang, J. Chen, B. Li, W. Lei, P. Jiang, and X. He KuaiRand: an unbiased sequential recommendation dataset with randomly exposed videos. External Links: 2208.08696, Link Cited by: §5.1. Gibbs and Candès (2024) I. Gibbs and E. J. Candès Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research 25 (162), p. 1–36. External Links: Link Cited by: Appendix A, §1. Gibbs and Candes (2021) I. Gibbs and E. Candes Adaptive conformal inference under distribution shift. In Advances in Neural Information Processing Systems, Vol. 34, p. 1660–1672. Cited by: Appendix A, §1, §3.1. Harper and Konstan (2015) F. M. Harper and J. A. Konstan The movielens datasets: history and context. ACM Transactions on Interactive Intelligent Systems 5 (4), p. 19:1–19:19. External Links: Document Cited by: §5.1. Ie et al. (2019) E. Ie, V. Jain, J. Wang, S. Narvekar, R. Agarwal, R. Wu, H. Cheng, T. Chandra, and C. Boutilier SlateQ: a tractable decomposition for reinforcement learning with recommendation sets. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, p. 2592–2599. External Links: Document Cited by: Appendix A, §1. Kagita et al. (2022) V. R. Kagita, A. K. Pujari, V. Padmanabhan, and V. Kumar Inductive conformal recommender system. Knowledge-Based Systems 250, p. 109108. External Links: Document Cited by: Appendix A. Lillicrap et al. (2016) T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra Continuous control with deep reinforcement learning. In International Conference on Learning Representations, External Links: Link Cited by: 2nd item, §5.2. Liu et al. (2023) S. Liu, Q. Cai, B. Sun, Y. Wang, J. Jiang, D. Zheng, P. Jiang, K. Gai, X. Zhao, and Y. Zhang Exploration and regularization of the latent action space in recommendation. In Proceedings of the ACM Web Conference 2023, p. 833–844. External Links: Document Cited by: Appendix A, 4th item, §5.2. Mnih et al. (2016) V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu Asynchronous methods for deep reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 48, p. 1928–1937. Cited by: 1st item, §5.2. Si et al. (2025) W. Si, S. Jang, I. Lee, and O. Bastani Conformal constrained policy optimization for cost-effective LLM agents. arXiv preprint arXiv:2511.11828. External Links: 2511.11828, Document Cited by: Appendix A. Vovk et al. (2005) V. Vovk, A. Gammerman, and G. Shafer Algorithmic learning in a random world. Springer. External Links: Document Cited by: Appendix A. Wang et al. (2024) C. Wang, F. Wang, R. Guo, Y. Liang, and P. S. Yu Confidence-aware fine-tuning of sequential recommendation systems via conformal prediction. External Links: 2402.08976, Link Cited by: Appendix A. Wang et al. (2025) X. Wang, S. Liu, Q. Cai, X. Li, L. Hu, H. Li, and G. Xie Value function decomposition in markov recommendation process. In Proceedings of the ACM Web Conference 2025, p. 379–390. External Links: Document Cited by: Appendix A. Zhang et al. (2023) Y. Zhang, C. Shi, and S. Luo Conformal off-policy prediction. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 206, p. 2751–2768. Cited by: Appendix A. Zhao et al. (2023) K. Zhao, S. Liu, Q. Cai, X. Zhao, Z. Liu, D. Zheng, P. Jiang, and K. Gai KuaiSim: a comprehensive simulator for recommender systems. In Advances in Neural Information Processing Systems, Vol. 36, p. 44880–44897. Cited by: Appendix A, §1, §5.1, §5.2, §5.2, §5. Zhao et al. (2018) X. Zhao, L. Xia, L. Zhang, Z. Ding, D. Yin, and J. Tang Deep reinforcement learning for page-wise recommendations. In Proceedings of the 12th ACM conference on recommender systems, p. 95–103. Cited by: Appendix A, §1. Supplementary Materials Appendix A Related Work RLCP draws on sequential control, conformal recommendation, and online calibration. The distinction across these areas is what is calibrated and how that quantity is connected to the subsequent decision. We organize the comparison around this distinction rather than treating the combination of RL and calibration as new. RL for Sequential Recommendation. RL recommender systems optimize utility across a sequence of interactions rather than only immediate feedback (Afsar et al., 2022; Chen et al., 2021; Zhao et al., 2018). Within this framework, SlateQ makes slate optimization tractable by decomposing slate values under a user choice model (Ie et al., 2019), while HAC learns continuous slate representations and a mapping from latent actions to item lists (Liu et al., 2023). KuaiSim supplies whole session evaluation protocols and actor and critic baselines (Zhao et al., 2023), and work on value estimation further distinguishes policy randomness from user response randomness (Wang et al., 2025). These methods address how to evaluate or select recommendations. RLCP addresses a complementary question: which candidate actions should remain available to that selection rule, and how does their retention affect sequential value? Its item model does not cover every reward or transition rule that depends on a slate. Conformal Recommendation. Conformal methods provide a way to construct sets around a base prediction model while controlling a statistical error criterion (Vovk et al., 2005; Angelopoulos and Bates, 2023). In recommendation, inductive conformal methods attach conformal p-values to candidate items (Kagita et al., 2022), and distribution free recommendation sets calibrate ranking models against the false discovery rate (FDR) (Angelopoulos et al., 2023). Without explicitly optimizing long-term returns, CPFT incorporates conformal objectives into the fine tuning of sequential recommenders (Wang et al., 2024), while conformal risk control has been used to limit unwanted recommendations (De Toni et al., 2025). These approaches motivate adapting set size to a calibrated target. However, a recommendation target need not identify actions with high continuation value under an interacting policy. RLCP therefore distinguishes proxy retention from oracle retention and states the approximation condition needed to connect them. Online Calibration and Decision Making. Because RLCP changes the policy and the visited state distribution during learning, its calibration argument uses methods for changing data sequences. Adaptive conformal inference controls long-run empirical miscoverage under distribution changes (Gibbs and Candes, 2021; Gibbs and Candès, 2024). Multivalid methods provide richer guarantees across groups (Bastani et al., 2022), while methods with decaying step sizes combine guarantees for arbitrary sequences with population quantile consistency under stable sampling (Angelopoulos et al., 2024). RLCP uses this established scalar update principle. Theorem 3.1 makes its dependence on the realized action margin range explicit and supplies the calibration term used in the value analysis. Online miscoverage tracking itself is not presented as a new principle. Conformal methods also support motion planning (Dixit et al., 2023), return prediction for a policy different from the data collection policy (Zhang et al., 2023), and cost aware orchestration of LLM agents (Si et al., 2025). In particular, CCPO jointly trains a policy and an adaptive conformal threshold, so RLCP is not distinguished by that broad combination. The distinction lies in the action filtering formulation and the analysis connecting retention to value. A proxy hit must first be related to an oracle hit, and the retained action must then be used by the selector. The value decomposition and finite session bound describe these two steps without assuming convergence of the coupled updates. Appendix B Additional Modeling Details The main formulation treats an executed item as the MDP action. We now explain how this abstraction relates to a recommendation pipeline, where retrieval and collection based response rules introduce additional conditions. B.1 Sequential Recommendation Interpretation The first requirement concerns the state: it must contain the information needed to predict both immediate feedback and the next user state. A representative state is st=(xu,hta,hty,ℓt,ct),s_t=(x_u,h_t^a,h_t^y, _t,c_t), Here xux_u is a user profile, htah_t^a and htyh_t^y are action and response histories, ℓt _t is remaining patience, and ctc_t is request context. An absorbing state represents user departure. The finite state model is an analytical idealization; in a large system, a learned representation must approximate the same predictive information. The second requirement concerns retrieval. The finite action space can represent an eligible item pool, but pruning within that pool cannot recover an action already removed by retrieval. To separate these two losses, fix a state distribution ν, let ret(s)⊆A_ret(s) be a finite nonempty retrieved pool, and let C(s)⊆ret(s)C(s) _ret(s) be the raw set retained from it. Fix εret,εfilt≥0 _ret, _filt≥ 0 and ρ∈[0,1)ρ∈[0,1), and define Gret(s) G_ret(s) =maxa∈ret(s)Q∗(s,a)≥V∗(s)−εret, = \ _a _ret(s)Q^*(s,a)≥ V^*(s)- _ret \, Gfilt(s) G_filt(s) =∃a∈C(s) such that = \∃ a∈ C(s) such that Q∗(s,a)≥maxb∈ret(s)Q∗(s,b)−εfilt. 20.00003ptQ^*(s,a)≥ _b _ret(s)Q^*(s,b)- _filt \. If Prs∼ν(Gretc)≤ρ _s ν(G_ret^c)≤ρ and Prs∼ν(Gfiltc∣Gret)≤α _s ν(G_filt^c G_ret)≤α, then on Gret∩GfiltG_ret∩ G_filt the retained action has global optimality gap at most εret+εfilt _ret+ _filt. The law of total probability gives Prs∼ν(C(s)∩εret+εfilt∗(s)=∅)≤ρ+(1−ρ)α. _s ν\! (C(s) ^*_ _ret+ _filt(s)= )≤ρ+(1-ρ)α. Thus the value tolerances add, while the miss probability accounts first for retrieval failure and then for filtering failure conditional on retrieval success. To retain the global tolerance ε , the two tolerances must sum to at most ε . Alternatively, filtering can be calibrated directly against ε∗(s)∩ret(s)A^*_ (s) _ret(s) conditional on that intersection being nonempty. The final requirement concerns how a retained collection becomes an executed item. Let κ(a∣s,D)κ(a s,D) be a stationary Markov choice kernel supported on D, sampled before the current reward and next state are generated. This kernel may combine a downstream actor, slate construction, and user choice. For a stationary set map D, the induced item policy is πD,κ(a∣s)=κ(a∣s,D(s)). _D,κ(a s)=κ(a s,D(s)). (21) For this policy to reproduce the recommendation process, the selected item must account for the dependence of the current reward and next state on the collection. The following assumption states that requirement conditional on all information available before selection. Assumption B.1 (Pre-response item-mediated dynamics). There is an item-level reward and transition kernel K(dr,s′∣s,a)K(dr,s s,a) such that, under the pipeline law PrD _D induced by every stationary set map D with D(s)≠∅D(s)≠ for all s, the following factorization holds conditional on the full pre-action history ℋtH_t: PrD(at=a,Rt∈dr,st+1=s′∣ℋt)=κ(a∣st,D(st))K(dr,s′∣st,a). split& _D (a_t=a,R_t ,s_t+1=s _t )\\ & =κ(a s_t,D(s_t))K(dr,s s_t,a). split (22) The kernel agrees with the item-level MDP primitives: ∫K(dr,s′∣s,a) K(dr,s s,a) =P(s′∣s,a), =P(s s,a), (23) ∑s′∫rK(dr,s′∣s,a) _s r\,K(dr,s s,a) =r(s,a). =r(s,a). Thus, conditional on the state and executed item, the reward and next-state distribution do not depend further on the admissible set or displayed slate. Proposition B.2 (Recommendation pipeline reduction). Under Assumption B.1, πD,κ∈Π(D) _D,κ∈ (D), and the recommendation pipeline has the same reward and state-transition law as the item-level MDP controlled by πD,κ _D,κ. Hence all restricted-control and value results below apply to the induced policy. Proof. For every state, κ(⋅∣s,D(s))κ(· s,D(s)) is a probability distribution supported on D(s)D(s), so (21) defines a stationary policy in Π(D) (D). Conditional on the full pre-action history, factorization (22) gives the same one-step joint law of the action, reward, and next state as this item-level policy. Starting from the same initial distribution and applying this equality inductively establishes equality of the complete trajectory laws. ∎ The order in Assumption B.1 matters. For example, a rule that observes the current response vector and then selects the first rewarded item does not satisfy this order: conditioning on the selected item changes its response law because selection used that response. The process can instead be modeled with the retained set or ordered slate as the action and an environment kernel that jointly generates responses, the selected item, reward, and the next state. However, the item value results do not automatically transfer to this different MDP. The pathwise calibration result still concerns the realized proxy misses, and Proposition C.11 separately covers a leave rule based on any positive response in the collection. In summary, the item abstraction applies when an item selected before feedback determines the next interaction. When position, competition, or exposure to unchosen items also changes reward or transition, the collection must instead be the primitive action. In either model, a value bound concerns the specified reward: a click or like reward does not by itself establish a depth bound without an appropriate relation to departure. Appendix C Additional Supporting Results The supporting results follow the same order as the main argument. We first establish the population benchmark and its characterization under a fixed policy. We then account for a cap on set size and state the conditions that transfer proxy retention and approximate selection to value. C.1 Restricted Control and Existence Before optimizing a threshold, we must ensure that every nonempty execution set supports a well defined control problem. For a set map D satisfying D(s)≠∅D(s)≠ for every state, define (Dv)(s)=maxa∈D(s)[r(s,a)+γ∑s′P(s′∣s,a)v(s′)].(T_Dv)(s)= _a∈ D(s) [r(s,a)+γ _s P(s s,a)v(s ) ]. (24) This is the Bellman operator with maximization restricted to retained actions. The next result establishes its optimal value and an occupancy representation, which is also needed to select a unique response for the outer objective. Theorem C.1 (Restricted control is well defined). For every set map D satisfying D(s)≠∅D(s)≠ for all s, DT_D is a γ contraction and has a unique fixed point VD∗V_D^*. A stationary deterministic policy in Π(D) (D) attains this value. The lower problem also admits a normalized discounted occupancy-measure LP whose optimum is (1−γ)VD∗(μ0)(1-γ)V_D^*( _0), with attainment, zero duality gap, and a deterministic lexicographic rule that selects one optimal occupancy. Once that response is fixed, the outer problem reduces to comparing the finitely many set maps induced by the score thresholds. Proposition C.2 (Fixed-score outer existence). For every fixed θ, Problem (11) is feasible and attains its minimum over the thresholds induced by that score. A threshold retaining every action is feasible, so the outer comparison is nonempty. These results establish the benchmark for a given score. They do not assert that critic or actor training finds its global solution. C.2 Threshold Characterization for a Fixed Policy The threshold problem becomes simpler when the evaluation policy is held fixed as well. Fix θ and a stationary policy π, and define the distribution and quantile of the oracle margin by Fθ,π(x) F_θ,π(x) =Prs∼dπ(mθ(s)≤x), = _s d^π(m_θ(s)≤ x), (25) Fθ,π−1(u) F^-1_θ,π(u) =infx:Fθ,π(x)≥u. = \x:F_θ,π(x)≥ u\. Proposition C.3 (Smallest fixed-policy threshold). For fixed (θ,π)(θ,π), the smallest threshold satisfying (8) is τmin(θ,π)=Fθ,π−1(1−α). _ (θ,π)=F^-1_θ,π(1-α). (26) Among thresholds evaluated under the same policy, it also minimizes dπ[|C¯θ,τ(s)|]E_d^π[| C_θ,τ(s)|]. The quantile characterization follows from two facts: a hit is a margin threshold event, and the retained sets grow with the threshold under the same score. It therefore yields a smallest valid threshold and a minimum expected execution set size under a fixed occupancy. The population benchmark remains coupled because its occupancy changes with the downstream response. C.3 Maximum Set Size The calibration result controls the raw set, but execution may impose a maximum size. Suppose the cap keeps at most K actions with the smallest scores, using a fixed action order to resolve ties. Write the capped raw set as CtKC_t^K, and distinguish all capped misses from the hits removed specifically by truncation: etK e_t^K =CtK∩~ε,t(st)=∅, =1\C_t^K∩ A_ ,t(s_t)= \, (27) htK h_t^K =Ct∩~ε,t(st)≠∅,CtK∩~ε,t(st)=∅. =1\C_t∩ A_ ,t(s_t)≠ ,\ C_t^K∩ A_ ,t(s_t)= \. Then etK=e~t+htKe_t^K= e_t+h_t^K, because a capped miss is either already a raw miss or is created by truncation. Hence, when the threshold update uses the raw miss e~t e_t, 1T∑t=1TetK≤α+W~T+η1ηTT+1T∑t=1ThtK, 1T _t=1^Te_t^K≤α+ W_T+ _1 _TT+ 1T _t=1^Th_t^K, (28) Here W~T W_T is (13) for the proxy margins. The last term is not an error in tracking the raw miss rate. It records whether the ranking and available capacity preserve the proxy actions that passed the threshold. This distinction also determines whether the retention target is feasible after capping. In the finite state and action model, fix the score, proxy target, and state distribution. A finite threshold can meet the target after capping if and only if Pr(some proxy target action ranksamong the first K actions)≥1−α. \! ( gatheredsome proxy target action ranks\\ among the first K actions gathered )≥ 1-α. (29) Necessity follows because increasing the threshold cannot move a target action into the first K ranks. For sufficiency, a threshold at least as large as every score makes the capped set equal to the global top K at each state. Thus a failed capacity condition cannot be repaired by calibration alone. For the same reason, an update using capped misses does not generally satisfy the scalar margin proof: that proof requires a target of rank at most K, so that a sufficiently large finite threshold can produce a hit. C.4 Additional Value Results We next connect retained actions to value. The first example shows why the selection loss cannot be omitted, even when the retention condition is perfect. Proposition C.4 (Coverage alone is insufficient). There is a one-state, two-action discounted MDP in which the retained set always contains an optimal action, but a supported policy has value gap (1−γ)−1(1-γ)^-1. To quantify the filtering component separately, define the largest oracle action gap and the target tolerance capped at that gap: Δmax _ =maxs,a[V∗(s)−Q∗(s,a)], = _s,a[V^*(s)-Q^*(s,a)], (30) ε0 _0 =minε,Δmax. = \ , _ \. Corollary C.5 (Coverage bound). Let C(s)⊆D(s)C(s) D(s) for every state, assume D(s)≠∅D(s)≠ for every state, and let π∈Π(D)π∈ (D) satisfy Prs∼dπ(C(s)∩ε∗(s)≠∅)≥1−α. _s d^π\! (C(s) ^*_ (s)≠ )≥ 1-α. (31) With ζ¯π,D=dπ[ζπ,D(s)] ζ_π,D=E_d^π[ _π,D(s)], V∗(μ0)−Vπ(μ0)≤(1−α)ε0+αΔmax+ζ¯π,D1−γ.V^*( _0)-V^π( _0)≤ (1-α) _0+α _ + ζ_π,D1-γ. (32) On a hit, the filtering loss is at most the target tolerance; on a miss, it is at most the largest action gap. The corollary averages these two cases and retains the separate selection loss from Theorem 3.2. The factor (1−γ)−1(1-γ)^-1 then accounts for accumulation along the discounted session. Because the population benchmark imposes retention under its own downstream occupancy, the same bound applies directly to every feasible threshold in that benchmark. Corollary C.6 (Bilevel specialization). For the fixed score θ, every feasible threshold τ in Problem (11) satisfies Corollary C.5 with C=Cθ,τC=C_θ,τ, D=Dθ,τD=D_θ,τ, and π=πθ,τ∗π=π^*_θ,τ. C.5 Practical Proxy, Critic, and Recommendation Errors The preceding corollary assumes oracle retention. To apply it using observable feedback, we first replace the oracle target by the near maximizers of a finite proxy score Q~:×→ℝ Q:S×A : ~ε(s)=a:Q~(s,a)≥maxbQ~(s,b)−ε. A_ (s)=\a: Q(s,a)≥ _b Q(s,b)- \. (33) The proxy target is nonempty because it contains every maximizer of the finite score. Its membership depends only on differences between actions at the same state, so absolute agreement with Q∗Q^* is stronger than needed. This matters when, for example, the proxy is a response probability rather than a cumulative value. The following condition instead compares pairwise gaps after allowing for scale. Assumption C.7 (Proxy gap fidelity). There exist λ>0λ>0 and δprox≥0 _prox≥ 0 such that, for every state and pair of actions, |Q∗(s,a)−Q∗(s,b)−λ(Q~(s,a)−Q~(s,b))|≤δprox. |Q^*(s,a)-Q^*(s,b)-λ ( Q(s,a)- Q(s,b) ) |≤ _prox. (34) Under this condition, a small gap according to the proxy also implies a controlled gap according to the oracle. Proposition C.8 (Proxy-to-oracle target transfer). Under Assumption C.7, ~ε(s)⊆λε+δprox∗(s)∀s. A_ (s) ^*_λ + _prox(s) ∀ s. (35) Consequently, a hit of the proxy target is a hit of the enlarged oracle target under any state distribution. The condition has a concrete interpretation for the response proxy used in recommendation. An immediate response can differ from optimal action value because the action also changes the continuation state. The next result separates that continuation effect from response model error. Proposition C.9 (Immediate-response proxy). Suppose Q~(s,a)=r(s,a) Q(s,a)=r(s,a) is the expected immediate response. Define δdyn=γmaxs,a,b|∑s′[P(s′∣s,a)−P(s′∣s,b)]V∗(s′)|. _dyn=γ _s,a,b | _s [P(s s,a)-P(s s,b)]V^*(s ) |. (36) Then Assumption C.7 holds with λ=1λ=1 and δprox=δdyn _prox= _dyn. More generally, suppose Q~(s,a)=p^(s,a) Q(s,a)= p(s,a) and ‖p^−r‖∞≤δresp\| p-r\|_∞≤ _resp. Then the assumption holds with λ=1λ=1 and δprox=δdyn+2δresp _prox= _dyn+2 _resp. Using the convention TV(P1,P2)=12∑s′|P1(s′)−P2(s′)|TV(P_1,P_2)= 12 _s |P_1(s )-P_2(s )|, we also have δdyn≤γ1−γmaxs,a,bTV(P(⋅∣s,a),P(⋅∣s,b)). _dyn≤ γ1-γ _s,a,bTV\! (P(· s,a),P(· s,b) ). (37) Thus an immediate response score approximates optimal item gaps when actions have similar continuation effects and the response model is accurate. The term δdyn _dyn records the first requirement, while 2δresp2 _resp records the second. A proxy equal to the simulator’s exact Bernoulli parameter has zero response model error within that simulated MDP, but it can still have a large continuation error. Proxy retention is therefore not automatically retention of actions with high long term value. Having related proxy hits to oracle hits, we now account for approximate selection. The following bound combines proxy fidelity with a critic error relative to the optimal value and an error in maximizing that critic within the retained set. Corollary C.10 (Combined practical errors). Let C(s)⊆D(s)C(s) D(s) for every state, assume D(s)≠∅D(s)≠ for every state, and let π∈Π(D)π∈ (D). Suppose Prs∼dπ(C(s)∩~ε(s)≠∅)≥1−α, _s d^π\! (C(s)∩ A_ (s)≠ )≥ 1-α, (38) Assumption C.7 holds, ‖Q^−Q∗‖∞≤δcrit\| Q-Q^*\|_∞≤ _crit, and maxa∈D(s)Q^(s,a)−∑a∈D(s)π(a∣s)Q^(s,a)≤δsel(s). _a∈ D(s) Q(s,a)- _a∈ D(s)π(a s) Q(s,a)≤ _sel(s). (39) With δ¯sel=dπ[δsel(s)] δ_sel=E_d^π[ _sel(s)] and εrec=minλε+δprox,Δmax, _rec= \λ + _prox, _ \, (40) we have V∗(μ0)−Vπ(μ0) V^*( _0)-V^π( _0) ≤11−γ[(1−α)εrec+αΔmax ≤ 11-γ [(1-α) _rec+α _ (41) +2δcrit+δ¯sel]. +2 _crit+ δ_sel ]. The bound identifies what each component must supply: calibration controls proxy misses, proxy fidelity bounds retained action quality, and critic accuracy and selection quality control the remaining decision loss. These are conditional requirements. In particular, a critic that evaluates the current policy or a restricted policy class need not have small error relative to the unrestricted Q∗Q^*. For the simulator, it is also useful to study immediate patience changes without claiming a complete session value guarantee. The next result distinguishes a rule that tests the entire collection for a positive response from a rule that tests only an item selected before the response. Proposition C.11 (Response retention under two patience mechanisms). Suppose that, conditional on state s, a jointly distributed potential-response vector (Ya)a∈(Y_a)_a is defined and that D(s)D(s) is nonempty and determined before this vector is sampled. Let p(s,a)=Pr(Ya=1∣s),p∗(s)=maxap(s,a).p(s,a)= (Y_a=1 s), p^*(s)= _ap(s,a). For a collection-based response rule, define pDset(s)=Pr(⋃a∈D(s)Ya=1|s).p_D^set(s)= \! ( _a∈ D(s)\Y_a=1\\, |\,s ). For a pre-response item selector κ, assume that its internal randomization is conditionally independent of the potential-response vector given s and D(s)D(s), and define pD,κitem(s)=∑a∈D(s)κ(a∣s,D(s))p(s,a)p_D,κ^item(s)= _a∈ D(s)κ(a s,D(s))p(s,a) and δselp(s)=maxa∈D(s)p(s,a)−pD,κitem(s). _sel^p(s)= _a∈ D(s)p(s,a)-p_D,κ^item(s). Suppose that, under a state distribution ν, the set D(s)D(s) contains an action satisfying p(s,a)≥p∗(s)−εp(s,a)≥ p^*(s)- with probability at least 1−α1-α. Let εp=minε,1,δ¯selp=ν[δselp(s)]. _p= \ ,1\, δ_sel^p=E_ν[ _sel^p(s)]. Then the collection-based rule satisfies ν[1−pDset(s)]≤ν[1−p∗(s)]+(1−α)εp+α.E_ν[1-p_D^set(s)] _ν[1-p^*(s)]+(1-α) _p+α. (42) No independence among the item responses is required. The pre-response item selector satisfies ν[1−pD,κitem(s)]≤ν[1−p∗(s)]+(1−α)εp+α+δ¯selp.E_ν[1-p_D,κ^item(s)] _ν[1-p^*(s)]+(1-α) _p+α+ δ_sel^p. (43) If patience decreases by c+c_+ after a positive response and by c−>c+c_->c_+ otherwise, the excess expected one-step patience decrease relative to the best single item is at most (c−c+)[(1−α)εp+α](c_--c_+) [(1-α) _p+α ] (44) for the collection-based rule, and at most (c−c+)[(1−α)εp+α+δ¯selp](c_--c_+) [(1-α) _p+α+ δ_sel^p ] (45) for the pre-response item selector. The difference between the bounds again comes from selection. A positive response anywhere in the collection is at least as likely as a positive response from its best item, whereas a selector may choose a worse item and incur the additional selection term. Both conclusions concern one interaction. Extending either to session depth requires the full patience evolution, state transition, and departure model. C.6 Full Conditions for the Finite Session Bound The discounted results above concern stationary policies. Theorem 3.3 instead allows the policy and score to change within a session. To make that extension precise, the following assumption groups the information available before selection, the calibration and execution rules, and the approximation errors. It imposes no convergence requirement on the parameters that generate these quantities. Assumption C.12 (Finite-session information and approximation errors). Consider an undiscounted episodic MDP with finite nonempty state and action spaces S and A, initial state s1∼μ0s_1 _0, horizon H, rewards Rh∈[0,1]R_h∈[0,1], optimal functions Vh∗,Qh∗V_h^*,Q_h^*, and terminal value VH+1∗=0V_H+1^*=0. Let ℋhH_h be the sigma field containing the trajectory and all algorithmic information available immediately before the action at stage h is sampled. In particular, shs_h is ℋhH_h measurable. Let rh:×→[0,1]r_h:S×A→[0,1] and Ph(⋅∣s,a)P_h(· s,a) be the controlled stage reward mean and transition kernel, so that [Rh∣ℋh,ah] [R_h _h,a_h] =rh(sh,ah), =r_h(s_h,a_h), Pr(sh+1=s′CLOSE (s_h+1=s ∣ℋh,ah) _h,a_h) =Ph(s′∣sh,ah). =P_h(s s_h,a_h). Let ΔHmax=max1≤h≤Hmaxs,a[Vh∗(s)−Qh∗(s,a)]. _H = _1≤ h≤ H _s,a [V_h^*(s)-Q_h^*(s,a) ]. At every stage h, suppose that the threshold τh _h and the action-indexed quantities gh(a)=gθh(sh,a),Q~h(sh,a),Q^h(sh,a),a∈, gatheredg_h(a)=g_ _h(s_h,a), Q_h(s_h,a),\\ Q_h(s_h,a), a , gathered are finite and ℋhH_h measurable. Define the stage-dependent proxy target, proxy margin, raw set, and raw proxy miss by ~ε,h(sh) A_ ,h(s_h) =a∈:Q~h(sh,a)≥maxb∈Q~h(sh,b)−ε, = \a : Q_h(s_h,a)≥ _b Q_h(s_h,b)- \, m~h m_h =mina∈~ε,h(sh)gh(a), = _a∈ A_ ,h(s_h)g_h(a), Ch C_h =a∈:gh(a)≤τh, =\a :g_h(a)≤ _h\, e~h e_h =m~h>τh=Ch∩~ε,h(sh)=∅. =1\ m_h> _h\=1\C_h∩ A_ ,h(s_h)= \. Let the threshold follow τh+1=τh+ηh(e~h−α),h=1,…,H, _h+1= _h+ _h( e_h-α), h=1,…,H, (46) where η1≥η2≥⋯≥ηH>0 _1≥ _2≥·s≥ _H>0 is deterministic. Fix K∈1,…,||K∈\1,…,|A|\. Using the fixed action order to break ties, let ChKC_h^K contain the minK,|Ch| \K,|C_h|\ elements of ChC_h having the smallest scores ghg_h. Let ahmina_h be the first action in argmina∈gh(a) _a g_h(a) and define Dh=ChK,ChK≠∅,ahmin,ChK=∅.D_h= casesC_h^K,&C_h^K≠ ,\\ \a_h \,&C_h^K= . cases The tie-breaking rule makes ChKC_h^K and DhD_h ℋhH_h measurable. Conditional on ℋhH_h, the action is sampled from an ℋhH_h measurable probability kernel supported on DhD_h, before the current reward and next state are generated. In particular, Pr(ah∈Dh∣ℋh)=1. (a_h∈ D_h _h)=1. Define ehK e_h^K =ChK∩~ε,h(sh)=∅, =1\C_h^K∩ A_ ,h(s_h)= \, hhK h_h^K =Ch∩~ε,h(sh)≠∅,ChK∩~ε,h(sh)=∅, =1\C_h∩ A_ ,h(s_h)≠ ,\ C_h^K∩ A_ ,h(s_h)= \, W~H W_H =maxτ1,m~1,…,m~H−minτ1,m~1,…,m~H. = \ _1, m_1,…, m_H\- \ _1, m_1,…, m_H\. Assume that W~H≤W W_H≤ W almost surely for a deterministic finite constant W. Also assume that there exist λ>0λ>0, δprox≥0 _prox≥ 0, and δcrit≥0 _crit≥ 0 such that, almost surely, for every h and every a,b∈a,b , |Qh∗(sh,a)−Qh∗(sh,b)−λ(Q~h(sh,a)CLOSEOPEN−Q~h(sh,b))|≤δprox. split |Q_h^*(s_h,a)-Q_h^*(s_h,b)&-λ ( Q_h(s_h,a)\\[-1.07639pt] & 25.00003pt- Q_h(s_h,b) ) |≤ _prox. split (47) maxa∈|Q^h(sh,a)−Qh∗(sh,a)|≤δcrit. _a | Q_h(s_h,a)-Q_h^*(s_h,a) |≤ _crit. (48) Finally, suppose that δsel,h _sel,h is a nonnegative, integrable, ℋhH_h measurable random variable and that, almost surely, maxa∈DhQ^h(sh,a)−[Q^h(sh,ah)∣ℋh]≤δsel,h. _a∈ D_h Q_h(s_h,a)-E\! [ Q_h(s_h,a_h) _h ]≤ _sel,h. (49) Define εH _H =minλε+δprox,ΔHmax, = \λ + _prox, _H \, δ¯sel,H δ_sel,H =1H∑h=1H[δsel,h], = 1H _h=1^HE[ _sel,h], h¯HK h_H^K =1H∑h=1H[hhK]. = 1H _h=1^HE[h_h^K]. Taking K=||K=|A| represents the case without a cap and gives h¯HK=0 h_H^K=0. The information condition permits the critic and selector to depend on past observations. It excludes using the current action’s realized response to define the target or execution set for that same action. The approximation conditions then apply at the visited states, with critic error measured relative to unrestricted Qh∗Q_h^* rather than the current policy value. Thus the theorem explains how these errors affect performance; it does not establish that an arbitrary learning update makes them small. C.7 Greedy Preservation and Conditional Policy Recovery The previous results allow arbitrary supported selectors. For a selector greedy with respect to the scoring critic, however, a simpler boundary case applies: the critic gap score always gives a minimum score to a critic maximizer. To describe its consequences, fix finite critics Q^t Q_t, thresholds τt _t, and caps Kt≥1K_t≥ 1. Construct Dt(s)D_t(s) by thresholding the critic gap, keeping at most KtK_t actions with the smallest scores, and applying the minimum score fallback when needed. Use the same fixed action order for all ties. The remaining performance error can then be expressed using the critic’s pairwise error and the selector’s gap within the retained set. For a stationary policy πt _t supported on DtD_t, define ξt(s,a) _t(s,a) =Q^t(s,a)−Q∗(s,a), = Q_t(s,a)-Q^*(s,a), βt _t =maxs,a,b|ξt(s,a)−ξt(s,b)|, = _s,a,b| _t(s,a)- _t(s,b)|, σt(s) _t(s) =maxa∈Dt(s)Q^t(s,a)−∑a∈Dt(s)πt(a∣s)Q^t(s,a), = _a∈ D_t(s) Q_t(s,a)- _a∈ D_t(s) _t(a s) Q_t(s,a), σ¯t σ_t =s∼dπt[σt(s)]. =E_s d _t[ _t(s)]. If any strictly suboptimal state–action pair exists, let Δmin=mins,a:Q∗(s,a)<V∗(s)[V∗(s)−Q∗(s,a)]>0. _ = _s,a:\,Q^*(s,a)<V^*(s)[V^*(s)-Q^*(s,a)]>0. If all actions are optimal, set Δmin=+∞ _ =+∞. Proposition C.13 (Greedy preservation and conditional recovery). Every operational set Dt(s)D_t(s) contains the first global maximizer of Q^t(s,⋅) Q_t(s,·). Hence a greedy selector with the same tie-breaking rule returns the same action with or without filtering. Moreover, V∗(μ0)−Vπt(μ0)≤σ¯t+βt1−γ,βt≤2‖Q^t−Q∗‖∞.V^*( _0)-V _t( _0)≤ σ_t+ _t1-γ, _t≤ 2\| Q_t-Q^*\|_∞. If βt<Δmin _t< _ , every global critic maximizer is truly optimal. A policy greedy within DtD_t is then optimal. Consequently, βt+σ¯t→0 _t+ σ_t→ 0 implies value convergence; for exact greedy selection, βt→0 _t→ 0 implies eventual optimality in a finite MDP. These are conditional implications, not convergence guarantees for the learning updates. This result does not replace the calibration analysis. It identifies a case in which filtering leaves the chosen action unchanged, so any benefit from controlling the available alternatives must arise through a different downstream selection mechanism. The recovery implications remain conditional on critic and selector errors. Appendix D Complete Proofs The proofs follow the dependencies in the main analysis. Bellman identities first establish the reference values. Restricted control and occupancy arguments then justify the population benchmark. The calibration proof controls the miss sequence, while the value proofs convert misses and selection errors into reward loss. Finally, the greedy preservation argument identifies the boundary case in which filtering does not change the selected action. D.1 Bellman Identities and Value Bounds The following identities connect the trajectory definitions of value to the Bellman operators used in the later proofs. The bounded reward assumption then supplies the largest possible action and policy gaps. Lemma D.1 (Bellman identities). For every stationary policy π, Qπ(s,a) Q^π(s,a) =r(s,a)+γ∑s′P(s′∣s,a)Vπ(s′), =r(s,a)+γ _s P(s s,a)V^π(s ), (50) Vπ(s) V^π(s) =∑aπ(a∣s)Qπ(s,a). = _aπ(a s)Q^π(s,a). The optimal values satisfy Q∗(s,a) Q^*(s,a) =r(s,a)+γ∑s′P(s′∣s,a)V∗(s′), =r(s,a)+γ _s P(s s,a)V^*(s ), (51) V∗(s) V^*(s) =maxaQ∗(s,a). = _aQ^*(s,a). Any stationary policy supported on argmaxaQ∗(s,a) _aQ^*(s,a) at every state is optimal. Proof. We prove the policy identities first. Fix a stationary policy π, a state s, and an action a. By the forced-action definition, Qπ(s,a)=sa⊳π[R0+∑t=1∞γtRt].Q^π(s,a)=E_s^a π\! [R_0+ _t=1^∞γ^tR_t ]. The controlled reward model gives sa⊳π[R0]=r(s,a).E_s^a π[R_0]=r(s,a). For the remaining terms, condition on the next state and shift the time index: sa⊳π[∑t=1∞γtRt] _s^a π\! [ _t=1^∞γ^tR_t ] =γ∑s′P(s′∣s,a)s′π[∑j=0∞γjRj] =γ _s P(s s,a)E_s ^π\! [ _j=0^∞γ^jR_j ] =γ∑s′P(s′∣s,a)Vπ(s′). =γ _s P(s s,a)V^π(s ). The first equality uses (1) and the fact that the policy follows π from time one onward. Hence Qπ(s,a)=r(s,a)+γ∑s′P(s′∣s,a)Vπ(s′).Q^π(s,a)=r(s,a)+γ _s P(s s,a)V^π(s ). Under π, the time-zero action has distribution π(⋅∣s)π(· s). The trajectory law is therefore the corresponding mixture of the forced-action laws: Vπ(s) V^π(s) =∑aπ(a∣s)sa⊳π[∑t=0∞γtRt] = _aπ(a s)E_s^a π\! [ _t=0^∞γ^tR_t ] =∑aπ(a∣s)Qπ(s,a). = _aπ(a s)Q^π(s,a). This establishes (50). We next establish the optimal identities. Define (v)(s)=maxa∈[r(s,a)+γ∑s′P(s′∣s,a)v(s′)].(Tv)(s)= _a [r(s,a)+γ _s P(s s,a)v(s ) ]. For a stationary policy π, also define its Bellman operator by (πv)(s)=∑aπ(a∣s)[r(s,a)+γ∑s′P(s′∣s,a)v(s′)].(T^πv)(s)= _aπ(a s) [r(s,a)+γ _s P(s s,a)v(s ) ]. For arbitrary bounded functions v,wv,w, |(v)(s)−(w)(s)| |(Tv)(s)-(Tw)(s)| ≤maxa|γ∑s′P(s′∣s,a)[v(s′)−w(s′)]| ≤ _a |γ _s P(s s,a)[v(s )-w(s )] | ≤γ‖v−w‖∞. ≤γ\|v-w\|_∞. Taking the maximum over s gives ‖v−w‖∞≤γ‖v−w‖∞.\|Tv-Tw\|_∞≤γ\|v-w\|_∞. Thus T has a unique fixed point. Let V¯ V denote the unique fixed point of T. Set v0≡0v_0≡ 0 and vH=H0v_H=T^H0. Contraction of T gives vH⟶V¯in the sup norm.v_H V the sup norm. The iterates also have the standard finite-horizon interpretation: by induction, vH(s)v_H(s) is the largest expected discounted reward collected during the first H decision stages. We now identify V¯ V with the value V∗V^* defined as the maximum over stationary policies, without assuming in advance that a stationary optimal policy exists. Fix any stationary policy π. For every function v, πv≤vT^πv componentwise because an average over actions cannot exceed their maximum. Both operators are monotone, so induction from the zero function gives (π)H0≤H0=vHfor every H.(T^π)^H0 ^H0=v_H every H. The policy operator πT^π is a contraction, so its iterates converge to VπV^π. Letting H→∞H→∞ yields Vπ≤V¯.V^π≤ V. Since this holds for every stationary policy, V∗≤V¯.V^*≤ V. For the reverse inequality, choose a stationary deterministic policy π¯ π satisfying π¯(s)∈argmaxa∈[r(s,a)+γ∑s′P(s′∣s,a)V¯(s′)] π(s)∈ _a [r(s,a)+γ _s P(s s,a) V(s ) ] at every state. Such a choice exists because A is finite. Since V¯=V¯ V=T V, the greedy construction gives π¯V¯=V¯=V¯.T π V=T V= V. The operator π¯T π has the unique fixed point Vπ¯V π, and therefore Vπ¯=V¯.V π= V. Because π¯ π is stationary, V∗≥Vπ¯=V¯.V^*≥ V π= V. Combining both inequalities proves V∗=V¯=V∗.V^*= V=TV^*. This argument simultaneously proves existence of a stationary deterministic optimal policy. Define Q¯(s,a)=r(s,a)+γ∑s′P(s′∣s,a)V∗(s′). Q(s,a)=r(s,a)+γ _s P(s s,a)V^*(s ). It remains to connect this Bellman action value to the trajectory definition Q∗(s,a)=maxπQπ(s,a)Q^*(s,a)= _πQ^π(s,a). We establish the two inequalities separately. For every stationary policy π, the policy value satisfies Vπ≤V∗V^π≤ V^* componentwise. Therefore Qπ(s,a) Q^π(s,a) =r(s,a)+γ∑s′P(s′∣s,a)Vπ(s′) =r(s,a)+γ _s P(s s,a)V^π(s ) ≤r(s,a)+γ∑s′P(s′∣s,a)V∗(s′) ≤ r(s,a)+γ _s P(s s,a)V^*(s ) =Q¯(s,a). = Q(s,a). Taking the maximum over π gives Q∗(s,a)≤Q¯(s,a).Q^*(s,a)≤ Q(s,a). For the reverse inequality, choose a stationary policy π∗π^* whose support at every state is contained in argmaxb[r(s,b)+γ∑s′P(s′∣s,b)V∗(s′)]. _b [r(s,b)+γ _s P(s s,b)V^*(s ) ]. Such a policy exists because the action set is finite. Its policy Bellman operator satisfies π∗V∗=V∗=V∗.T^π^*V^*=TV^*=V^*. Since π∗T^π^* is a contraction with unique fixed point Vπ∗V^π^*, we have Vπ∗=V∗.V^π^*=V^*. Consequently, Qπ∗(s,a)=r(s,a)+γ∑s′P(s′∣s,a)V∗(s′)=Q¯(s,a).Q^π^*(s,a)=r(s,a)+γ _s P(s s,a)V^*(s )= Q(s,a). Because Q∗Q^* is the maximum over policies, Q∗(s,a)≥Qπ∗(s,a)=Q¯(s,a).Q^*(s,a)≥ Q^π^*(s,a)= Q(s,a). Combining the two inequalities gives Q∗(s,a)=r(s,a)+γ∑s′P(s′∣s,a)V∗(s′).Q^*(s,a)=r(s,a)+γ _s P(s s,a)V^*(s ). Substituting this identity into the fixed-point equation for V∗V^* yields V∗(s)=maxaQ∗(s,a).V^*(s)= _aQ^*(s,a). Finally, any stationary policy whose support is contained in argmaxaQ∗(s,a) _aQ^*(s,a) satisfies πV∗=V∗.T^πV^*=V^*. The unique fixed point of πT^π is VπV^π, so Vπ=V∗V^π=V^*. Such a policy is therefore optimal. ∎ Lemma D.2 (Value bounds). For every π∈Ππ∈ , state s, and action a, 0≤Vπ(s),Qπ(s,a),V∗(s),Q∗(s,a)≤11−γ.0≤ V^π(s),Q^π(s,a),V^*(s),Q^*(s,a)≤ 11-γ. Consequently, 0≤Δmax≤(1−γ)−10≤ _ ≤(1-γ)^-1. Proof. For every sample path, 0≤∑t=0∞γtRt≤∑t=0∞γt=11−γ.0≤ _t=0^∞γ^tR_t≤ _t=0^∞γ^t= 11-γ. Taking expectations under the corresponding controlled trajectory laws preserves both inequalities, proving the bounds for VπV^π and QπQ^π. Taking maxima over policies gives the same bounds for V∗V^* and Q∗Q^*. Finally, V∗(s)=maxbQ∗(s,b)≥Q∗(s,a)V^*(s)= _bQ^*(s,b)≥ Q^*(s,a), so each difference in (30) is nonnegative and at most (1−γ)−1(1-γ)^-1. ∎ D.2 Proofs for the Bilevel Formulation We first establish a supported optimal policy and its occupancy representation. The occupancy formulation then provides a deterministic choice among optimal responses, so that the outer objective has a definite value for every threshold. Proof of Theorem C.1. Fix a set map D satisfying D(s)≠∅D(s)≠ for every state. We will prove that control over this set is equivalent to maximizing reward over supported discounted occupancies. For reference, define max∑s,aρ∈(D)ρ(s,a)r(s,a), _ρ (D) _s,aρ(s,a)r(s,a), (52) where (D)=ρ≥0: (D)=\ρ≥ 0: ∑aρ(s,a)=(1−γ)μ0(s) _aρ(s,a)=(1-γ) _0(s) (53) +γ∑s′,a′P(s∣s′,a′)ρ(s′,a′),∀s, +γ _s ,a P(s s ,a )ρ(s ,a ),\ ∀ s, ρ(s,a)=0 for a∉D(s). ρ(s,a)=0 for a∉ D(s)\. The flow constraints record discounted state visitation and rule out actions outside D. The corresponding dual places an upper bound on reward plus continuation value for every retained action: minv _v (1−γ)∑sμ0(s)v(s) (1-γ) _s _0(s)v(s) (54) subject to to v(s)≥r(s,a)+γ∑s′P(s′∣s,a)v(s′), v(s)≥ r(s,a)+γ _s P(s s,a)v(s ), ∀s,a∈D(s). ∀ s,\ a∈ D(s). For each state s and action a∈D(s)a∈ D(s), define ha(v)=r(s,a)+γ∑s′P(s′∣s,a)v(s′).h_a(v)=r(s,a)+γ _s P(s s,a)v(s ). For any two finite families of real numbers xa\x_a\ and ya\y_a\, |maxaxa−maxaya|≤maxa|xa−ya|. | _ax_a- _ay_a |≤ _a|x_a-y_a|. Applying this inequality with xa=ha(v)x_a=h_a(v) and ya=ha(w)y_a=h_a(w) gives |Dv(s)−Dw(s)| |T_Dv(s)-T_Dw(s)| ≤maxa∈D(s)|γ∑s′P(s′∣s,a)[v(s′)−w(s′)]| ≤ _a∈ D(s) |γ _s P(s s,a)[v(s )-w(s )] | ≤γmax∑s′a∈D(s)P(s′∣s,a)|v(s′)−w(s′)| ≤γ _a∈ D(s) _s P(s s,a)|v(s )-w(s )| ≤γ‖v−w‖∞max∑s′a∈D(s)P(s′∣s,a) ≤γ\|v-w\|_∞ _a∈ D(s) _s P(s s,a) =γ‖v−w‖∞. =γ\|v-w\|_∞. Taking the maximum over s proves ‖Dv−Dw‖∞≤γ‖v−w‖∞.\|T_Dv-T_Dw\|_∞≤γ\|v-w\|_∞. Because γ<1γ<1, the Banach fixed-point theorem gives a unique fixed point, denoted VD∗V_D^*. For each state s, the set D(s)D(s) is finite and nonempty, so there exists aD∗(s)∈argmaxa∈D(s)[r(s,a)+γ∑s′P(s′∣s,a)VD∗(s′)].a_D^*(s)∈ _a∈ D(s) [r(s,a)+γ _s P(s s,a)V_D^*(s ) ]. Let πD∗ _D^* select aD∗(s)a_D^*(s) with probability one. Define the policy Bellman operator (πv)(s)=∑aπ(a∣s)[r(s,a)+γ∑s′P(s′∣s,a)v(s′)].(T^πv)(s)= _aπ(a s) [r(s,a)+γ _s P(s s,a)v(s ) ]. By the choice of aD∗(s)a_D^*(s), πD∗VD∗=DVD∗=VD∗.T _D^*V_D^*=T_DV_D^*=V_D^*. The operator πD∗T _D^* is a γ contraction by the same calculation as above, and its unique fixed point is VπD∗V _D^*. Hence VπD∗=VD∗.V _D^*=V_D^*. Now fix any π∈Π(D)π∈ (D). For every v and every state, (πv)(s) (T^πv)(s) =∑a∈D(s)π(a∣s)[r(s,a)+γ∑s′P(s′∣s,a)v(s′)] = _a∈ D(s)π(a s) [r(s,a)+γ _s P(s s,a)v(s ) ] ≤maxa∈D(s)[r(s,a)+γ∑s′P(s′∣s,a)v(s′)] ≤ _a∈ D(s) [r(s,a)+γ _s P(s s,a)v(s ) ] =(Dv)(s). =(T_Dv)(s). Both operators are monotone. Starting from the zero function and applying the preceding inequality inductively yields (π)n0≤Dn0for every n.(T^π)^n0 _D^n0 every n. The left side converges to VπV^π and the right side converges to VD∗V_D^* because both operators are contractions. Therefore Vπ≤VD∗V^π≤ V_D^* componentwise. This proves that πD∗ _D^* is optimal over Π(D) (D). For π∈Π(D)π∈ (D), define ρπ(s,a)=(1−γ)∑t=0∞γtPrπ(st=s,at=a∣s0∼μ0).ρ^π(s,a)=(1-γ) _t=0^∞γ^t ^π(s_t=s,a_t=a s_0 _0). Every component is nonnegative. If a∉D(s)a∉ D(s), then π(a∣s)=0π(a s)=0, and hence Prπ(st=s,at=a)=0 ^π(s_t=s,a_t=a)=0 for every t; therefore ρπ(s,a)=0ρ^π(s,a)=0. Let dπ(s)=∑aρπ(s,a).d^π(s)= _aρ^π(s,a). Using the law of total probability and the Markov property, dπ(s) d^π(s) =(1−γ)∑t=0∞γtPrπ(st=s) =(1-γ) _t=0^∞γ^t ^π(s_t=s) =(1−γ)μ0(s)+(1−γ)∑t=1∞γtPrπ(st=s) =(1-γ) _0(s)+(1-γ) _t=1^∞γ^t ^π(s_t=s) =(1−γ)μ0(s)+γ(1−γ)∑j=0∞γjPrπ(sj+1=s) =(1-γ) _0(s)+γ(1-γ) _j=0^∞γ^j ^π(s_j+1=s) =(1−γ)μ0(s) =(1-γ) _0(s) +γ(1−γ)∑j=0∞γj∑s′,a′Prπ(sj=s′,aj=a′)P(s∣s′,a′) +γ(1-γ) _j=0^∞γ^j _s ,a ^π(s_j=s ,a_j=a )P(s s ,a ) =(1−γ)μ0(s)+γ∑s′,a′P(s∣s′,a′)ρπ(s′,a′). =(1-γ) _0(s)+γ _s ,a P(s s ,a )ρ^π(s ,a ). Thus ρπ∈(D)ρ^π (D). Let ρ∈(D)ρ (D) and define d(s)=∑aρ(s,a).d(s)= _aρ(s,a). If d(s)>0d(s)>0, set πρ(a∣s)=ρ(s,a)d(s). _ρ(a s)= ρ(s,a)d(s). If d(s)=0d(s)=0, let πρ(⋅∣s) _ρ(· s) place probability one on the first action in D(s)D(s) under the fixed global action order. This action exists because D(s)≠∅D(s)≠ . The confinement constraints imply that πρ(a∣s)=0 _ρ(a s)=0 for every a∉D(s)a∉ D(s), so πρ∈Π(D) _ρ∈ (D). Define Pπρ(s′∣s)=∑aπρ(a∣s)P(s′∣s,a).P _ρ(s s)= _a _ρ(a s)P(s s,a). We claim that the flow constraints for ρ can be written as d=(1−γ)μ0+γ(Pπρ)⊤d.d=(1-γ) _0+γ(P _ρ) d. Indeed, if d(s′)>0d(s )>0, then d(s′)πρ(a∣s′)=ρ(s′,a)d(s ) _ρ(a s )=ρ(s ,a). If d(s′)=0d(s )=0, nonnegativity and ∑aρ(s′,a)=0 _aρ(s ,a)=0 imply ρ(s′,a)=0=d(s′)πρ(a∣s′)ρ(s ,a)=0=d(s ) _ρ(a s ) for every action. Consequently, ∑s′,a′P(s∣s′,a′)ρ(s′,a′) _s ,a P(s s ,a )ρ(s ,a ) =∑s′d(s′)∑a′πρ(a′∣s′)P(s∣s′,a′) = _s d(s ) _a _ρ(a s )P(s s ,a ) =∑s′Pπρ(s∣s′)d(s′), = _s P _ρ(s s )d(s ), which proves the vector equation. Because PπρP _ρ is row stochastic, ‖(Pπρ)⊤x‖1≤‖x‖1\|(P _ρ) x\|_1≤\|x\|_1 for every vector x. Hence ‖γ(Pπρ)⊤‖1→1≤γ<1,\|γ(P _ρ) \|_1→ 1≤γ<1, and the Neumann series [I−γ(Pπρ)⊤]−1=∑t=0∞γt[(Pπρ)⊤]t [I-γ(P _ρ) ]^-1= _t=0^∞γ^t [(P _ρ) ]^t converges. Thus the state-flow equation has the unique solution d=(1−γ)∑t=0∞γt[(Pπρ)⊤]tμ0,d=(1-γ) _t=0^∞γ^t [(P _ρ) ]^t _0, which is exactly the normalized discounted state occupancy of πρ _ρ. Multiplying this state occupancy by πρ(a∣s) _ρ(a s) shows that the state-action occupancy of πρ _ρ is d(s)πρ(a∣s)=ρ(s,a)d(s) _ρ(a s)=ρ(s,a) at every state and action. Therefore every point in (D)D(D) is generated by a policy in Π(D) (D). For any π∈Π(D)π∈ (D), ∑s,aρπ(s,a)r(s,a) _s,aρ^π(s,a)r(s,a) =(1−γ)∑t=0∞γt∑s,aPrπ(st=s,at=a)r(s,a) =(1-γ) _t=0^∞γ^t _s,a ^π(s_t=s,a_t=a)r(s,a) =(1−γ)∑t=0∞γtπ[r(st,at)] =(1-γ) _t=0^∞γ^tE^π[r(s_t,a_t)] =(1−γ)∑t=0∞γtπ[Rt] =(1-γ) _t=0^∞γ^tE^π[R_t] =(1−γ)Vπ(μ0). =(1-γ)V^π( _0). The third equality uses [Rt∣st,at]=r(st,at)E[R_t s_t,a_t]=r(s_t,a_t) and the tower property. Steps 3 and 4 give a correspondence between supported policies and feasible occupancies, so maximizing the LP is equivalent to maximizing Vπ(μ0)V^π( _0) over Π(D) (D). Its optimal value is therefore (1−γ)VD∗(μ0)(1-γ)V_D^*( _0). Summing the flow constraints over all states yields ∑s,aρ(s,a) _s,aρ(s,a) =(1−γ)∑sμ0(s) =(1-γ) _s _0(s) +γ∑s′,a′ρ(s′,a′)∑sP(s∣s′,a′) +γ _s ,a ρ(s ,a ) _sP(s s ,a ) =(1−γ)+γ∑s′,a′ρ(s′,a′). =(1-γ)+γ _s ,a ρ(s ,a ). Therefore ∑s,aρ(s,a)=1. _s,aρ(s,a)=1. The set (D)D(D) is defined by finitely many linear equalities, linear zero constraints, and nonnegativity constraints, so it is closed. The preceding identity and nonnegativity make it bounded. It is nonempty because any deterministic policy supported on D has a feasible occupancy. Hence (D)D(D) is compact, and the continuous linear objective attains its maximum. It is enough to regard ρ(s,a)ρ(s,a) for a∈D(s)a∈ D(s) as the primal variables. Associate an unrestricted dual variable v(s)v(s) with each flow equality. The coefficient of a primal variable ρ(x,a)ρ(x,a) in the equality indexed by s is s=x−γP(s∣x,a).1\s=x\-γ P(s x,a). The corresponding dual inequality is ∑sv(s)[s=x−γP(s∣x,a)]≥r(x,a), _sv(s)[1\s=x\-γ P(s x,a)]≥ r(x,a), which is equivalent to v(x)≥r(x,a)+γ∑sP(s∣x,a)v(s).v(x)≥ r(x,a)+γ _sP(s x,a)v(s). This gives the dual in (54). The primal is feasible and bounded. The dual is feasible: the constant vector v(s)=11−γv(s)= 11-γ satisfies, for every admissible action, r(s,a)+γ∑s′P(s′∣s,a)v(s′)≤1+γ1−γ=11−γ=v(s).r(s,a)+γ _s P(s s,a)v(s )≤ 1+ γ1-γ= 11-γ=v(s). The finite-dimensional linear-programming strong-duality theorem therefore gives equality of the primal and dual optimal values. Let DO_D be the set of primal optimizers. It is a nonempty closed subset of the compact set (D)D(D) and is therefore compact. Order the n=||||n=|S||A| coordinates as 1,…,n1,…,n. Set D(0)=DO_D^(0)=O_D. For j=1,…,nj=1,…,n, define mj=minρ∈D(j−1)ρj,D(j)=ρ∈D(j−1):ρj=mj.m_j= _ρ _D^(j-1) _j, _D^(j)=\ρ _D^(j-1): _j=m_j\. Each minimum is attained because D(j−1)O_D^(j-1) is nonempty and compact, so each D(j)O_D^(j) is again nonempty and compact. At the last step all coordinates are fixed, so D(n)O_D^(n) contains exactly one vector. This vector is the lexicographically smallest optimal occupancy and is denoted ρDlex _D^lex. Finally, reconstruct a policy from ρDlex _D^lex, using the first action in D(s)D(s) at every state with zero occupancy. The reconstructed policy has occupancy ρDlex _D^lex and attains the restricted optimal value. This supplies the unique response convention needed to evaluate the outer objective. ∎ Proof of Proposition C.2. Fix θ. Because S and A are finite, the collection of score values gθ(s,a):s∈,a∈\g_θ(s,a):s ,a \ is finite. As τ varies, a raw set changes only when τ crosses one of these values. The fallback action is also fixed by θ and the tie-breaking order. Hence only finitely many complete raw–operational designs G=(Cθ,τ,Dθ,τ)G=(C_θ,τ,D_θ,τ) can be induced by thresholds. For any induced design, the lower occupancy LP depends only on D. The lexicographic construction in Theorem C.1 therefore fixes one optimal occupancy and makes both the objective and coverage constraint functions of G alone. The feasible induced designs form a finite set, so the objective attains its minimum whenever this set is nonempty. It remains to prove nonemptiness. Since every score is finite, choose τall≥maxs,agθ(s,a). _all≥ _s,ag_θ(s,a). Then Cθ,τall(s)=Dθ,τall(s)=C_θ, _all(s)=D_θ, _all(s)=A for every state. The oracle target is nonempty, so the retention probability equals one. Thus τall _all is feasible, and a minimizing threshold exists. ∎ D.3 Proof of the Quantile Characterization The argument has two parts. The margin equivalence identifies the feasible thresholds, and nesting of the execution sets establishes size minimality under the same fixed occupancy. Proof of Proposition C.3. Fix θ and π. For every state s, Cθ,τ(s)∩ε∗(s)≠∅ C_θ,τ(s) ^*_ (s)≠ ⟺there exists a∈ε∗(s) with gθ(s,a)≤τ exists a ^*_ (s) with g_θ(s,a)≤τ ⟺mina∈ε∗(s)gθ(s,a)≤τ _a ^*_ (s)g_θ(s,a)≤τ ⟺mθ(s)≤τ. m_θ(s)≤τ. The minimum is well-defined because ε∗(s)A^*_ (s) is finite and nonempty. Taking probability under s∼dπs d^π gives Prs∼dπ(Cθ,τ(s)∩ε∗(s)≠∅)=Fθ,π(τ). _s d^π (C_θ,τ(s) ^*_ (s)≠ )=F_θ,π(τ). Thus τ satisfies the coverage requirement if and only if Fθ,π(τ)≥1−α.F_θ,π(τ)≥ 1-α. Let q=Fθ,π−1(1−α)=infx:Fθ,π(x)≥1−α.q=F^-1_θ,π(1-α)= \x:F_θ,π(x)≥ 1-α\. Because S is finite, the random variable mθ(s)m_θ(s) has finite support under dπd^π. Hence its CDF is a right-continuous step function and the set x:Fθ,π(x)≥1−α\x:F_θ,π(x)≥ 1-α\ has a smallest element. That element is q, so Fθ,π(q)≥1−αF_θ,π(q)≥ 1-α. If τ<qτ<q, then by the definition of the infimum and the fact that q is the smallest feasible support point, Fθ,π(τ)<1−α.F_θ,π(τ)<1-α. If τ≥qτ≥ q, monotonicity of the CDF gives Fθ,π(τ)≥Fθ,π(q)≥1−α.F_θ,π(τ)≥ F_θ,π(q)≥ 1-α. Therefore the feasible thresholds are exactly the interval [q,∞)[q,∞), and the smallest feasible threshold is q=τmin(θ,π)q= _ (θ,π). It remains to prove the set-size minimality under the same fixed policy. Let τ1≤τ2 _1≤ _2. The raw sets are nested: Cθ,τ1(s)⊆Cθ,τ2(s)for every s.C_θ, _1(s) C_θ, _2(s) every s. We now verify that the operational sets are also nested. If Cθ,τ1(s)≠∅C_θ, _1(s)≠ , then both operational sets equal their raw sets and C¯θ,τ1(s)=Cθ,τ1(s)⊆Cθ,τ2(s)=C¯θ,τ2(s). C_θ, _1(s)=C_θ, _1(s) C_θ, _2(s)= C_θ, _2(s). If Cθ,τ1(s)=∅C_θ, _1(s)= and Cθ,τ2(s)=∅C_θ, _2(s)= , then both operational sets equal the same singleton aθmin(s)\a_θ (s)\. Finally, suppose Cθ,τ1(s)=∅C_θ, _1(s)= but Cθ,τ2(s)≠∅C_θ, _2(s)≠ . Nonemptiness of the latter implies τ2≥minagθ(s,a)=gθ(s,aθmin(s)), _2≥ _ag_θ(s,a)=g_θ(s,a_θ (s)), so aθmin(s)∈Cθ,τ2(s)a_θ (s)∈ C_θ, _2(s). Hence C¯θ,τ1(s)=aθmin(s)⊆Cθ,τ2(s)=C¯θ,τ2(s). C_θ, _1(s)=\a_θ (s)\ C_θ, _2(s)= C_θ, _2(s). Thus |C¯θ,τ1(s)|≤|C¯θ,τ2(s)|| C_θ, _1(s)|≤| C_θ, _2(s)| for every state. Averaging with respect to the fixed distribution dπd^π preserves the inequality. Since every coverage-valid threshold is at least τmin(θ,π) _ (θ,π), that threshold minimizes the expected operational-set size among all thresholds evaluated under the same fixed policy. ∎ D.4 Proof of Pathwise Calibration The update cannot move arbitrarily far beyond the realized margin range: outside that range, its direction points back toward it. We first formalize this interval bound and then express the cumulative calibration error in terms of threshold increments. Proof of Theorem 3.1. Fix an arbitrary horizon T≥1T≥ 1 and define m¯T m_T =minτ1,m1,…,mT, = \ _1,m_1,…,m_T\, m¯T m_T =maxτ1,m1,…,mT. = \ _1,m_1,…,m_T\. Then WT=m¯T−m¯TW_T= m_T- m_T. Define τT−=m¯T−αη1,τT+=m¯T+(1−α)η1. _T^-= m_T-α _1, _T^+= m_T+(1-α) _1. We first prove by induction that τt∈[τT−,τT+]for every 1≤t≤T+1. _t∈[ _T^-, _T^+] every 1≤ t≤ T+1. (55) The base case holds because τ1∈[m¯T,m¯T] _1∈[ m_T, m_T]. Assume the claim holds for some t≤Tt≤ T. Since ηt≤η1 _t≤ _1, there are three cases. If τt<m¯T _t< m_T, then mt≥m¯T>τtm_t≥ m_T> _t, so et=1e_t=1 and τt+1=τt+(1−α)ηt. _t+1= _t+(1-α) _t. The update is nonnegative, so τt+1≥τt≥τT− _t+1≥ _t≥ _T^-. Also, τt+1 _t+1 <m¯T+(1−α)ηt < m_T+(1-α) _t ≤m¯T+(1−α)η1=τT+. ≤ m_T+(1-α) _1= _T^+. If m¯T≤τt≤m¯T m_T≤ _t≤ m_T, then et∈0,1e_t∈\0,1\ and τt−αηt≤τt+1≤τt+(1−α)ηt. _t-α _t≤ _t+1≤ _t+(1-α) _t. Using ηt≤η1 _t≤ _1 and the bounds on τt _t yields τT−≤τt+1≤τT+ _T^-≤ _t+1≤ _T^+. If τt>m¯T _t> m_T, then mt≤m¯T<τtm_t≤ m_T< _t, so et=0e_t=0 and τt+1=τt−αηt. _t+1= _t-α _t. The update is nonpositive, so τt+1≤τt≤τT+ _t+1≤ _t≤ _T^+. Moreover, τt+1 _t+1 >m¯T−αηt > m_T-α _t ≥m¯T−αη1=τT−. ≥ m_T-α _1= _T^-. This completes the induction. The invariant interval has width τT+−τT− _T^+- _T^- =(m¯T−m¯T)+η1 =( m_T- m_T)+ _1 (56) =WT+η1. =W_T+ _1. The interval bound now controls the accumulated misses. Rearranging (12) gives et−α=τt+1−τtηt.e_t-α= _t+1- _t _t. Let ct=1/ηtc_t=1/ _t. Because ηt _t is positive and nonincreasing, ctc_t is positive and nondecreasing. Therefore ST S_T =∑t=1T(et−α) = _t=1^T(e_t-α) =∑t=1Tct(τt+1−τt) = _t=1^Tc_t( _t+1- _t) =cTτT+1−c1τ1−∑t=2T(ct−ct−1)τt. =c_T _T+1-c_1 _1- _t=2^T(c_t-c_t-1) _t. Define ω1=c1cT,ωt=ct−ct−1cT(2≤t≤T). _1= c_1c_T, _t= c_t-c_t-1c_T (2≤ t≤ T). Each ωt≥0 _t≥ 0, and ∑t=1Tωt=c1+∑t=2T(ct−ct−1)cT=1. _t=1^T _t= c_1+ _t=2^T(c_t-c_t-1)c_T=1. Hence ST=cT(τT+1−∑t=1Tωtτt).S_T=c_T ( _T+1- _t=1^T _t _t ). The weighted sum is a convex combination of τ1,…,τT _1,…, _T. By (55), both this convex combination and τT+1 _T+1 lie in [τT−,τT+][ _T^-, _T^+]. Thus, using (56), |ST|≤cT(τT+−τT−)=WT+η1ηT.|S_T|≤ c_T( _T^+- _T^-)= W_T+ _1 _T. Dividing by T proves (14). Since the argument used only the update and the realized margin interval, the bound holds for an arbitrary adaptive sequence. The convergence condition and the constant step consequence follow directly from its right hand side. ∎ D.5 Proofs for the Value Results We begin with the counterexample separating retention from selection, then derive the exact value identity. The subsequent proofs bound its filtering and selection terms in turn, before combining them along an adaptive finite session. Proof of Proposition C.4. Consider one state s, two actions ag,aba_g,a_b, deterministic self-transitions, and rewards r(s,ag)=1,r(s,ab)=0.r(s,a_g)=1, r(s,a_b)=0. The optimal policy always chooses aga_g, so V∗(s)=∑t=0∞γt=11−γ.V^*(s)= _t=0^∞γ^t= 11-γ. The optimal action values are Q∗(s,ag) Q^*(s,a_g) =1+γV∗(s)=11−γ, =1+γ V^*(s)= 11-γ, Q∗(s,ab) Q^*(s,a_b) =γV∗(s)=γ1−γ. =γ V^*(s)= γ1-γ. Therefore 0∗(s)=agA^*_0(s)=\a_g\. Let D(s)=ag,abD(s)=\a_g,a_b\, so the set contains an optimal action with probability one. Let πb _b always choose aba_b. This policy belongs to Π(D) (D) and receives zero reward at every time, hence Vπb(s)=0V _b(s)=0. Its value gap is V∗(s)−Vπb(s)=11−γ.V^*(s)-V _b(s)= 11-γ. Lemma D.2 shows that no value gap can be larger, so the gap is maximal. ∎ Proof of Theorem 3.2. We first verify that both terms are losses, then express their sum as the optimal Bellman residual of the supported policy. Since D(s)D(s) is nonempty and V∗(s)=maxa∈Q∗(s,a)V^*(s)= _a Q^*(s,a), maxa∈D(s)Q∗(s,a)≤V∗(s), _a∈ D(s)Q^*(s,a)≤ V^*(s), so ΔD(s)≥0 _D(s)≥ 0. Also, an average cannot exceed the maximum of the averaged numbers: ∑a∈D(s)π(a∣s)Q∗(s,a)≤maxa∈D(s)Q∗(s,a), _a∈ D(s)π(a s)Q^*(s,a)≤ _a∈ D(s)Q^*(s,a), so ζπ,D(s)≥0 _π,D(s)≥ 0. Define the policy-averaged reward and transition kernel rπ(s) r^π(s) =∑aπ(a∣s)r(s,a), = _aπ(a s)r(s,a), Pπ(s′∣s) P^π(s s) =∑aπ(a∣s)P(s′∣s,a). = _aπ(a s)P(s s,a). For any function f on S, let (Pπf)(s)=∑s′Pπ(s′∣s)f(s′).(P^πf)(s)= _s P^π(s s)f(s ). To relate these local gaps to the total value loss, define the optimal Bellman residual of π by bπ(s)=V∗(s)−∑aπ(a∣s)Q∗(s,a).b_π(s)=V^*(s)- _aπ(a s)Q^*(s,a). Using (51), ∑aπ(a∣s)Q∗(s,a) _aπ(a s)Q^*(s,a) =∑aπ(a∣s)r(s,a) = _aπ(a s)r(s,a) +γ∑s′[∑aπ(a∣s)P(s′∣s,a)]V∗(s′) +γ _s [ _aπ(a s)P(s s,a) ]V^*(s ) =rπ(s)+γ(PπV∗)(s). =r^π(s)+γ(P^πV^*)(s). Lemma D.1 gives Vπ=rπ+γPπVπV^π=r^π+γ P^πV^π. Subtracting this identity from V∗V^* yields, state by state, V∗−Vπ V^*-V^π =V∗−rπ−γPπVπ =V^*-r^π-γ P^πV^π =[V∗−rπ−γPπV∗]+γPπ(V∗−Vπ) = [V^*-r^π-γ P^πV^* ]+γ P^π(V^*-V^π) =bπ+γPπ(V∗−Vπ). =b_π+γ P^π(V^*-V^π). Iterating this equality N times gives V∗−Vπ= V^*-V^π= ∑t=0N−1γt(Pπ)tbπ _t=0^N-1γ^t(P^π)^tb_π +γN(Pπ)N(V∗−Vπ). +γ^N(P^π)^N(V^*-V^π). A Markov operator is nonexpansive in the sup norm. Lemma D.2 therefore gives ‖γN(Pπ)N(V∗−Vπ)‖∞≤γN1−γ⟶0. \|γ^N(P^π)^N(V^*-V^π) \|_∞≤ γ^N1-γ 0. Consequently, V∗−Vπ=∑t=0∞γt(Pπ)tbπ.V^*-V^π= _t=0^∞γ^t(P^π)^tb_π. Average both sides over s0∼μ0s_0 _0. The definition (3) implies V∗(μ0)−Vπ(μ0) V^*( _0)-V^π( _0) =∑t=0∞γtπ[bπ(st)] = _t=0^∞γ^tE^π[b_π(s_t)] =11−γs∼dπ[bπ(s)]. = 11-γE_s d^π[b_π(s)]. Because π∈Π(D)π∈ (D), bπ(s) b_π(s) =V∗(s)−∑a∈D(s)π(a∣s)Q∗(s,a) =V^*(s)- _a∈ D(s)π(a s)Q^*(s,a) =V∗(s)−maxa∈D(s)Q∗(s,a) =V^*(s)- _a∈ D(s)Q^*(s,a) +maxa∈D(s)Q∗(s,a)−∑a∈D(s)π(a∣s)Q∗(s,a) + _a∈ D(s)Q^*(s,a)- _a∈ D(s)π(a s)Q^*(s,a) =ΔD(s)+ζπ,D(s). = _D(s)+ _π,D(s). Substitution proves (18). The decomposition is exact because it splits the same Bellman residual, rather than bounding filtering and selection through separate trajectory comparisons. ∎ Proof of Corollary C.5. Define the hit set H=s:C(s)∩ε∗(s)≠∅H=\s:C(s) ^*_ (s)≠ \ and its miss probability under the policy occupancy: απ=Prs∼dπ(s∉H). _π= _s d^π(s∉ H). Assumption (31) gives απ≤α. _π≤α. Fix a state s∈Hs∈ H. By definition of H, there exists at least one action aH(s)∈C(s)∩ε∗(s).a_H(s)∈ C(s) ^*_ (s). Since C(s)⊆D(s)C(s) D(s), aH(s)∈D(s).a_H(s)∈ D(s). Therefore maxa∈D(s)Q∗(s,a) _a∈ D(s)Q^*(s,a) ≥Q∗(s,aH(s)) ≥ Q^*(s,a_H(s)) ≥V∗(s)−ε, ≥ V^*(s)- , where the second inequality follows from aH(s)∈ε∗(s)a_H(s) ^*_ (s). Rearranging gives ΔD(s)=V∗(s)−maxa∈D(s)Q∗(s,a)≤ε. _D(s)=V^*(s)- _a∈ D(s)Q^*(s,a)≤ . By definition of Δmax _ , every nonempty set D(s)D(s) also satisfies 0≤ΔD(s)≤Δmax.0≤ _D(s)≤ _ . Hence, on the hit set, ΔD(s)≤minε,Δmax=ε0, _D(s)≤ \ , _ \= _0, while on the miss set, ΔD(s)≤Δmax. _D(s)≤ _ . Split the occupancy expectation over H and its complement: s∼dπ[ΔD(s)] _s d^π[ _D(s)] =[ΔD(s)s∈H] =E[ _D(s)1\s∈ H\] +[ΔD(s)s∉H] +E[ _D(s)1\s∉ H\] ≤ε0Pr(s∈H)+ΔmaxPr(s∉H) ≤ _0 (s∈ H)+ _ (s∉ H) =(1−απ)ε0+απΔmax =(1- _π) _0+ _π _ =ε0+απ(Δmax−ε0). = _0+ _π( _ - _0). Since Δmax−ε0≥0 _ - _0≥ 0 and απ≤α _π≤α, dπ[ΔD(s)] _d^π[ _D(s)] ≤ε0+α(Δmax−ε0) ≤ _0+α( _ - _0) =(1−α)ε0+αΔmax. =(1-α) _0+α _ . The exact decomposition in Theorem 3.2 gives V∗(μ0)−Vπ(μ0)=dπ[ΔD(s)]+ζ¯π,D1−γ.V^*( _0)-V^π( _0)= E_d^π[ _D(s)]+ ζ_π,D1-γ. Substituting the preceding bound proves (32). ∎ Proof of Corollary C.6. Feasibility of (θ,τ)(θ,τ) in Problem (11) gives Prs∼dπθ,τ∗(Cθ,τ(s)∩ε∗(s)≠∅)≥1−α. _s d^π^*_θ,τ (C_θ,τ(s) ^*_ (s)≠ )≥ 1-α. By construction, Cθ,τ(s)⊆Dθ,τ(s)C_θ,τ(s) D_θ,τ(s) and Dθ,τ(s)D_θ,τ(s) is nonempty for every state. The lower-level policy satisfies πθ,τ∗∈Π(Dθ,τ).π^*_θ,τ∈ (D_θ,τ). Thus every assumption of Corollary C.5 holds after setting C=Cθ,τ,D=Dθ,τ,π=πθ,τ∗.C=C_θ,τ, D=D_θ,τ, π=π^*_θ,τ. The stated bound follows directly. ∎ The occupancy bound concerns retention averaged under a specified policy. Under the stronger condition that every state retains a target action, we can instead compare the restricted and unrestricted optimal values at every initial state. Corollary D.3 (Pointwise retention). If D(s)∩ε∗(s)≠∅D(s) ^*_ (s)≠ for every state, then 0≤V∗(s)−VD∗(s)≤ε01−γ∀s.0≤ V^*(s)-V_D^*(s)≤ _01-γ ∀ s. (57) Proof of Corollary D.3. For every state s, choose aQ(s)∈argmaxa∈D(s)Q∗(s,a)a_Q(s)∈ _a∈ D(s)Q^*(s,a) using a fixed tie-breaking rule, and let πQ _Q be the deterministic policy that selects aQ(s)a_Q(s). Because aQ(s)∈D(s)a_Q(s)∈ D(s), πQ∈Π(D). _Q∈ (D). The pointwise retention assumption gives an action aH(s)∈D(s)∩ε∗(s)a_H(s)∈ D(s) ^*_ (s) at every state. Therefore maxa∈D(s)Q∗(s,a) _a∈ D(s)Q^*(s,a) ≥Q∗(s,aH(s)) ≥ Q^*(s,a_H(s)) ≥V∗(s)−ε. ≥ V^*(s)- . Together with ΔD(s)≤Δmax _D(s)≤ _ , this yields ΔD(s)=V∗(s)−maxa∈D(s)Q∗(s,a)≤ε0for every s. _D(s)=V^*(s)- _a∈ D(s)Q^*(s,a)≤ _0 every s. For the policy πQ _Q, the optimal Bellman residual is bπQ(s) b_ _Q(s) =V∗(s)−∑aπQ(a∣s)Q∗(s,a) =V^*(s)- _a _Q(a s)Q^*(s,a) =V∗(s)−Q∗(s,aQ(s)) =V^*(s)-Q^*(s,a_Q(s)) =ΔD(s) = _D(s) ≤ε0. ≤ _0. The residual identity derived in the proof of Theorem 3.2 gives V∗−VπQ=bπQ+γPπQ(V∗−VπQ).V^*-V _Q=b_ _Q+γ P _Q(V^*-V _Q). Taking sup norms, using ‖bπQ‖∞≤ε0\|b_ _Q\|_∞≤ _0, and using that a Markov operator is nonexpansive in the sup norm, we obtain ‖V∗−VπQ‖∞≤ε0+γ‖V∗−VπQ‖∞.\|V^*-V _Q\|_∞≤ _0+γ\|V^*-V _Q\|_∞. Rearranging gives ‖V∗−VπQ‖∞≤ε01−γ.\|V^*-V _Q\|_∞≤ _01-γ. By Theorem C.1, the restricted optimal value dominates every supported policy componentwise: VD∗≥VπQ.V_D^*≥ V _Q. Also VD∗≤V∗V_D^*≤ V^* because the restricted policy class is a subset of the unrestricted class. Hence, for every state, 0≤V∗(s)−VD∗(s)≤V∗(s)−VπQ(s)≤ε01−γ.0≤ V^*(s)-V_D^*(s)≤ V^*(s)-V _Q(s)≤ _01-γ. This proves (57). ∎ We now replace oracle retention by proxy retention. The key step is to compare any proxy target action with an oracle maximizer through the pairwise fidelity condition. Proof of Proposition C.8. Fix a state s, an action a∈~ε(s)a∈ A_ (s), and a∗(s)∈argmaxbQ∗(s,b)a^*(s)∈ _bQ^*(s,b). Proxy near-optimality implies Q~(s,a∗(s))−Q~(s,a) Q(s,a^*(s))- Q(s,a) ≤maxbQ~(s,b)−Q~(s,a) ≤ _b Q(s,b)- Q(s,a) ≤ε. ≤ . Apply Assumption C.7 to the pair (a∗(s),a)(a^*(s),a): V∗(s)−Q∗(s,a) V^*(s)-Q^*(s,a) =Q∗(s,a∗(s))−Q∗(s,a) =Q^*(s,a^*(s))-Q^*(s,a) ≤λ[Q~(s,a∗(s))−Q~(s,a)]+δprox ≤λ[ Q(s,a^*(s))- Q(s,a)]+ _prox ≤λε+δprox. ≤λ + _prox. Thus a∈λε+δprox∗(s)a ^*_λ + _prox(s), proving (35). If a set C(s)C(s) intersects the proxy target, an action in that intersection also belongs to the enlarged oracle target. This proves the stated hit-event implication under any state distribution. ∎ Proof of Proposition C.9. The optimal Bellman identity gives, for every state and action pair, Q∗(s,a)−Q∗(s,b)−[r(s,a)−r(s,b)] Q^*(s,a)-Q^*(s,b)-[r(s,a)-r(s,b)] =γ∑s′[P(s′∣s,a)−P(s′∣s,b)]V∗(s′). =γ _s [P(s s,a)-P(s s,b)]V^*(s ). Taking absolute values and then the maximum proves the pairwise condition with λ=1λ=1 and δprox=δdyn _prox= _dyn. For a learned response proxy p p, add and subtract the immediate-reward difference: |Q∗(s,a)−Q∗(s,b)−[p^(s,a)−p^(s,b)]| |Q^*(s,a)-Q^*(s,b)-[ p(s,a)- p(s,b)] | ≤|Q∗(s,a)−Q∗(s,b)−[r(s,a)−r(s,b)]| ≤ |Q^*(s,a)-Q^*(s,b)-[r(s,a)-r(s,b)] | +|r(s,a)−p^(s,a)|+|r(s,b)−p^(s,b)| +|r(s,a)- p(s,a)|+|r(s,b)- p(s,b)| ≤δdyn+2δresp. ≤ _dyn+2 _resp. This proves the stated extension. By Lemma D.2, the range of V∗V^* is at most (1−γ)−1(1-γ)^-1. For any two probability distributions P1,P2P_1,P_2 and any function f with range at most B, |P1f−P2f|≤BTV(P1,P2).|E_P_1f-E_P_2f|≤ B\,TV(P_1,P_2). Apply this inequality with f=V∗f=V^* and B=(1−γ)−1B=(1-γ)^-1, then maximize over (s,a,b)(s,a,b) and multiply by γ to obtain (37). ∎ Proxy fidelity controls the filtering term. The next consequence controls the selection term by transferring an approximate critic maximization guarantee to the true optimal action values. Corollary D.4 (Approximate within-set selection). Assume D(s)≠∅D(s)≠ for every state and let π∈Π(D)π∈ (D). Suppose ‖Q^−Q∗‖∞≤δcrit\| Q-Q^*\|_∞≤ _crit and the within-set condition (39) holds. Define δ¯sel=s∼dπ[δsel(s)] δ_sel=E_s d^π[ _sel(s)]. Then ζπ,D(s)≤2δcrit+δsel(s). _π,D(s)≤ 2 _crit+ _sel(s). (58) If (31) also holds, then V∗(μ0)−Vπ(μ0)≤(1−α)ε0+αΔmax+2δcrit+δ¯sel1−γ.V^*( _0)-V^π( _0)≤ (1-α) _0+α _ +2 _crit+ δ_sel1-γ. (59) Proof of Corollary D.4. Fix a state s and abbreviate Ds=D(s)D_s=D(s). The uniform critic error implies, for every a, Q∗(s,a)≤Q^(s,a)+δcritQ^*(s,a)≤ Q(s,a)+ _crit and Q∗(s,a)≥Q^(s,a)−δcrit.Q^*(s,a)≥ Q(s,a)- _crit. Taking a maximum in the first inequality gives maxa∈DsQ∗(s,a)≤maxa∈DsQ^(s,a)+δcrit. _a∈ D_sQ^*(s,a)≤ _a∈ D_s Q(s,a)+ _crit. Averaging the second inequality under π(⋅∣s)π(· s) gives ∑a∈Dsπ(a∣s)Q∗(s,a) _a∈ D_sπ(a s)Q^*(s,a) ≥∑a∈Dsπ(a∣s)[Q^(s,a)−δcrit] ≥ _a∈ D_sπ(a s)[ Q(s,a)- _crit] =∑a∈Dsπ(a∣s)Q^(s,a)−δcrit, = _a∈ D_sπ(a s) Q(s,a)- _crit, because ∑a∈Dsπ(a∣s)=1 _a∈ D_sπ(a s)=1. Subtracting the second bound from the first yields ζπ,D(s) _π,D(s) =maxa∈DsQ∗(s,a)−∑a∈Dsπ(a∣s)Q∗(s,a) = _a∈ D_sQ^*(s,a)- _a∈ D_sπ(a s)Q^*(s,a) ≤maxa∈DsQ^(s,a)−∑a∈Dsπ(a∣s)Q^(s,a)+2δcrit ≤ _a∈ D_s Q(s,a)- _a∈ D_sπ(a s) Q(s,a)+2 _crit ≤δsel(s)+2δcrit. ≤ _sel(s)+2 _crit. This proves (58). Average the statewise inequality under dπd^π: ζ¯π,D ζ_π,D =s∼dπ[ζπ,D(s)] =E_s d^π[ _π,D(s)] ≤2δcrit+s∼dπ[δsel(s)] ≤ 2 _crit+E_s d^π[ _sel(s)] =2δcrit+δ¯sel. =2 _crit+ δ_sel. Substituting this bound into Corollary C.5 proves (59). ∎ The combined bound now follows by applying these two transfers in sequence: proxy hits give an enlarged oracle target, and critic and selector errors bound the remaining selection loss. Proof of Corollary C.10. Proposition C.8 gives, for every state, ~ε(s)⊆λε+δprox∗(s). A_ (s) ^*_λ + _prox(s). Therefore the proxy coverage assumption (38) implies Prs∼dπ(C(s)∩λε+δprox∗(s)≠∅)≥1−α. _s d^π (C(s) ^*_λ + _prox(s)≠ )≥ 1-α. Apply Corollary C.5 with the tolerance ε′=λε+δprox. =λ + _prox. The truncated hit-state loss in that corollary is minε′,Δmax=εrec. \ , _ \= _rec. Thus V∗(μ0)−Vπ(μ0)≤(1−α)εrec+αΔmax+ζ¯π,D1−γ.V^*( _0)-V^π( _0)≤ (1-α) _rec+α _ + ζ_π,D1-γ. Corollary D.4 gives ζ¯π,D≤2δcrit+δ¯sel. ζ_π,D≤ 2 _crit+ δ_sel. Substitution proves (41). ∎ For patience, we use the same retention and selection distinction at a single interaction. The collection response is controlled by event inclusion, whereas the response of a selected item also includes the choice error. Proof of Proposition C.11. Let Hp=s:D(s) contains an action a with p(s,a)≥p∗(s)−ε.H_p= \s:D(s) contains an action a with p(s,a)≥ p^*(s)- \. Let αp=Prs∼ν(s∉Hp)≤α _p= _s ν(s∉ H_p)≤α. For every action a∈D(s)a∈ D(s), the event Ya=1\Y_a=1\ is contained in the union defining pDset(s)p_D^set(s). Hence pDset(s)≥maxa∈D(s)p(s,a)p_D^set(s)≥ _a∈ D(s)p(s,a) without any independence assumption. On HpH_p, this gives p∗(s)−pDset(s)≤εp.p^*(s)-p_D^set(s)≤ _p. Outside HpH_p, the same difference is at most one. Therefore ν[1−pDset(s)] _ν[1-p_D^set(s)] =ν[1−p∗(s)]+ν[p∗(s)−pDset(s)] =E_ν[1-p^*(s)]+E_ν[p^*(s)-p_D^set(s)] ≤ν[1−p∗(s)]+(1−αp)εp+αp _ν[1-p^*(s)]+(1- _p) _p+ _p ≤ν[1−p∗(s)]+(1−α)εp+α, _ν[1-p^*(s)]+(1-α) _p+α, where the last inequality uses εp≤1 _p≤ 1. For the pre-response item selector, p∗(s)−pD,κitem(s) p^*(s)-p_D,κ^item(s) =p∗(s)−maxa∈D(s)p(s,a)+δselp(s). =p^*(s)- _a∈ D(s)p(s,a)+ _sel^p(s). The first term is at most εp _p on HpH_p and at most one outside HpH_p. Taking expectations gives ν[p∗(s)−pD,κitem(s)]≤(1−α)εp+α+δ¯selp,E_ν[p^*(s)-p_D,κ^item(s)]≤(1-α) _p+α+ δ_sel^p, which proves (43). For either mechanism, denote its positive-response probability by pmech(s)p_mech(s). Its expected patience decrease is c+pmech(s)+c−[1−pmech(s)]=c++(c−c+)[1−pmech(s)].c_+p_mech(s)+c_-[1-p_mech(s)]=c_++(c_--c_+)[1-p_mech(s)]. The best single item replaces pmech(s)p_mech(s) by p∗(s)p^*(s). Subtracting and applying the corresponding no-response bound proves (44) and (45). ∎ Proof of Theorem 3.3. The proof combines a finite horizon performance identity with separate bounds for filtering and selection. Unlike the stationary argument, it conditions on the information available at each stage, so the policy and critic may change during the session. By the finite-horizon Bellman equation and the controlled Markov property, Qh∗(sh,ah) Q_h^*(s_h,a_h) =rh(sh,ah)+[Vh+1∗(sh+1)∣ℋh,ah], =r_h(s_h,a_h)+E\! [V_h+1^*(s_h+1) _h,a_h ], [Rh∣ℋh,ah] [R_h _h,a_h] =rh(sh,ah). =r_h(s_h,a_h). The tower property therefore gives [Vh∗(sh)−Qh∗(sh,ah)]=[Vh∗(sh)−Rh−Vh+1∗(sh+1)].E\! [V_h^*(s_h)-Q_h^*(s_h,a_h) ]=E\! [V_h^*(s_h)-R_h-V_h+1^*(s_h+1) ]. Summing from h=1h=1 to H, using s1∼μ0s_1 _0 and VH+1∗=0V_H+1^*=0, yields V1∗(μ0)−V1RLCP(μ0)=∑h=1H[Vh∗(sh)−Qh∗(sh,ah)].V_1^*( _0)-V_1^RLCP( _0)= _h=1^HE\! [V_h^*(s_h)-Q_h^*(s_h,a_h) ]. (60) For each stage, split the optimal action gap into the loss from the execution set and the loss from the selected action: Δh _h =Vh∗(sh)−maxa∈DhQh∗(sh,a), =V_h^*(s_h)- _a∈ D_hQ_h^*(s_h,a), ζh _h =maxa∈DhQh∗(sh,a)−Qh∗(sh,ah). = _a∈ D_hQ_h^*(s_h,a)-Q_h^*(s_h,a_h). Because DhD_h is nonempty and ah∈Dha_h∈ D_h almost surely, both gaps are nonnegative, Δh≤ΔHmax _h≤ _H , and Vh∗(sh)−Qh∗(sh,ah)=Δh+ζh.V_h^*(s_h)-Q_h^*(s_h,a_h)= _h+ _h. Suppose first that ehK=0e_h^K=0. Choose bh∈ChK∩~ε,h(sh)b_h∈ C_h^K∩ A_ ,h(s_h) and ah∗∈argmaxa∈Qh∗(sh,a)a_h^*∈ _a Q_h^*(s_h,a). Membership of bhb_h in the proxy target implies Q~h(sh,ah∗)−Q~h(sh,bh)≤maxa∈Q~h(sh,a)−Q~h(sh,bh)≤ε. Q_h(s_h,a_h^*)- Q_h(s_h,b_h)≤ _a Q_h(s_h,a)- Q_h(s_h,b_h)≤ . Applying (47) to (ah∗,bh)(a_h^*,b_h) gives Vh∗(sh)−Qh∗(sh,bh) V_h^*(s_h)-Q_h^*(s_h,b_h) =Qh∗(sh,ah∗)−Qh∗(sh,bh) =Q_h^*(s_h,a_h^*)-Q_h^*(s_h,b_h) ≤λ(Q~h(sh,ah∗)−Q~h(sh,bh))+δprox ≤λ ( Q_h(s_h,a_h^*)- Q_h(s_h,b_h) )+ _prox ≤λε+δprox. ≤λ + _prox. Since bh∈ChK⊆Dhb_h∈ C_h^K D_h, this proves Δh≤εH _h≤ _H on ehK=0\e_h^K=0\. On ehK=1\e_h^K=1\, the universal bound Δh≤ΔHmax _h≤ _H applies. Hence, pathwise, Δh≤εH+(ΔHmax−εH)ehK. _h≤ _H+( _H - _H)e_h^K. (61) By definition, a capped miss is either a raw miss or a raw hit removed by the cap, and these events are disjoint. Thus ehK=e~h+hhK.e_h^K= e_h+h_h^K. The recursion (46) has exactly the form required by Theorem 3.1. Since the step sizes are positive and nonincreasing and W~H≤W W_H≤ W, that theorem gives, almost surely, 1H∑h=1He~h≤α+W+η1ηHH. 1H _h=1^H e_h≤α+ W+ _1 _HH. Consequently, 1H∑h=1HehK≤α+W+η1ηHH+1H∑h=1HhhK. 1H _h=1^He_h^K≤α+ W+ _1 _HH+ 1H _h=1^Hh_h^K. Average (61) over stages and then take expectations. This yields 1H∑h=1H[Δh]≤ 1H _h=1^HE[ _h]≤ (1−α)εH+αΔHmax (1-α) _H+α _H (62) +(ΔHmax−εH)(W+η1ηHH+h¯HK). +( _H - _H) ( W+ _1 _HH+ h_H^K ). The remaining term is the gap between the best retained action and the action actually selected. Since DhD_h and Q^h Q_h are ℋhH_h measurable, the critic condition implies maxa∈DhQh∗(sh,a) _a∈ D_hQ_h^*(s_h,a) ≤maxa∈DhQ^h(sh,a)+δcrit, ≤ _a∈ D_h Q_h(s_h,a)+ _crit, [Qh∗(sh,ah)∣ℋh] \! [Q_h^*(s_h,a_h) _h ] ≥[Q^h(sh,ah)∣ℋh]−δcrit. \! [ Q_h(s_h,a_h) _h ]- _crit. Subtracting the second inequality from the first and using (49) gives [ζh∣ℋh]≤2δcrit+δsel,h.E[ _h _h]≤ 2 _crit+ _sel,h. The assumed integrability permits taking expectations. Averaging over stages gives 1H∑h=1H[ζh]≤2δcrit+δ¯sel,H. 1H _h=1^HE[ _h]≤ 2 _crit+ δ_sel,H. (63) Finally, the filtering and selection bounds control the two components of each gap in (60). Substituting (62) and (63), using Δh+ζh _h+ _h, and multiplying by H gives (19). No step requires the policy, critic, or threshold to converge; the argument uses their stated stagewise information and error conditions. ∎ D.6 Proof of Greedy Preservation and Conditional Recovery We first show that thresholding, capping, and fallback all preserve the same critic maximizer. We then use that preservation to express policy loss through pairwise critic error and the remaining selection gap. Proof of Proposition C.13. Fix t and s, and let a^t(s) a_t(s) be the first maximizer of Q^t(s,⋅) Q_t(s,·) under the fixed action order. Every score gt(s,a)g_t(s,a) is nonnegative, and gt(s,a^t(s))=0g_t(s, a_t(s))=0. If τt<0 _t<0, the raw set is empty and the minimum score fallback is exactly a^t(s) a_t(s). If τt≥0 _t≥ 0, the raw set contains every critic maximizer. Its first action in increasing score order is a^t(s) a_t(s), so every cap with Kt≥1K_t≥ 1 retains this action. In both cases, a^t(s)∈Dt(s),maxa∈Dt(s)Q^t(s,a)=maxaQ^t(s,a). a_t(s)∈ D_t(s), _a∈ D_t(s) Q_t(s,a)= _a Q_t(s,a). Thus the execution set preserves the global critic maximizer selected by the fixed action order. A greedy selector using that order consequently returns the same item with or without filtering. Choose any a∗(s)∈argmaxaQ∗(s,a)a^*(s)∈ _aQ^*(s,a). Substituting Q∗=Q^t−ξtQ^*= Q_t- _t into the optimal Bellman residual gives bπt(s) b_ _t(s) =Q∗(s,a∗(s))−∑aπt(a∣s)Q∗(s,a) =Q^*(s,a^*(s))- _a _t(a s)Q^*(s,a) =Q^t(s,a∗(s))−∑aπt(a∣s)Q^t(s,a) = Q_t(s,a^*(s))- _a _t(a s) Q_t(s,a) +∑aπt(a∣s)[ξt(s,a)−ξt(s,a∗(s))]. + _a _t(a s) [ _t(s,a)- _t(s,a^*(s)) ]. For the first difference, replace Q^t(s,a∗(s)) Q_t(s,a^*(s)) by its maximum over all actions, which equals its maximum over Dt(s)D_t(s) by the preceding argument. This upper bounds that difference by σt(s) _t(s). Every bracket in the final sum is at most βt _t, and the policy weights are nonnegative and sum to one. Consequently, 0≤bπt(s)≤σt(s)+βt.0≤ b_ _t(s)≤ _t(s)+ _t. The residual identity in the proof of Theorem 3.2 now gives V∗(μ0)−Vπt(μ0) V^*( _0)-V _t( _0) =11−γs∼dπt[bπt(s)] = 11-γE_s d _t[b_ _t(s)] ≤σ¯t+βt1−γ. ≤ σ_t+ _t1-γ. For every state and action pair, the triangle inequality gives |ξt(s,a)−ξt(s,b)|≤|ξt(s,a)|+|ξt(s,b)|≤2‖Q^t−Q∗‖∞.| _t(s,a)- _t(s,b)|≤| _t(s,a)|+| _t(s,b)|≤ 2\| Q_t-Q^*\|_∞. Maximizing shows that βt≤2‖Q^t−Q∗‖∞ _t≤ 2\| Q_t-Q^*\|_∞. Suppose a strictly suboptimal state and action pair exists. Finiteness makes the minimum of its positive gaps strictly positive, so Δmin>0 _ >0 is well defined. Let a^∈argmaxaQ^t(s,a) a∈ _a Q_t(s,a). Then V∗(s)−Q∗(s,a^) V^*(s)-Q^*(s, a) =Q^t(s,a∗(s))−Q^t(s,a^) = Q_t(s,a^*(s))- Q_t(s, a) +ξt(s,a^)−ξt(s,a∗(s)) + _t(s, a)- _t(s,a^*(s)) ≤βt, ≤ _t, because the first difference is nonpositive. If a a were suboptimal and βt<Δmin _t< _ , this would imply Δmin≤V∗(s)−Q∗(s,a^)≤βt<Δmin, _ ≤ V^*(s)-Q^*(s, a)≤ _t< _ , a contradiction. This proves ranking consistency for every state. Since Dt(s)D_t(s) contains a global critic maximizer, every critic maximizer within Dt(s)D_t(s) is also a global critic maximizer. A policy supported on these actions is therefore supported on the true optimal actions. Lemma D.1 proves its optimality. If no strictly suboptimal pair exists, every policy is supported on optimal actions, and the same lemma applies directly. Finally, the quantitative value convergence statement follows by taking limits in the value bound above. For exact greedy selection, βt→0 _t→ 0 implies βt<Δmin _t< _ at every sufficiently large index when a positive gap exists. At those indices the policy is optimal. A unique optimal action at each state forces the action distribution to be the same point mass at all such indices. If several actions are optimal, support on those actions imposes no requirement that the distribution converge. None of these steps uses convergence of a parameter vector or of the threshold. ∎ Appendix E Experiment Details This appendix describes the comparison methods and the reported metrics. The metric definitions distinguish utility, catalog exposure, and retained set size so that the numerical comparisons can be interpreted separately from the calibration guarantee. E.1 Baseline Details • A2C: an advantage actor–critic method that updates the policy using advantage-weighted policy gradients and trains the critic to estimate the state-value function (Mnih et al., 2016). • DDPG: an off-policy deterministic actor–critic algorithm designed for continuous action spaces, which is applied to continuous action representations for slate recommendation (Lillicrap et al., 2016). • TD3: an extension of DDPG that mitigates value overestimation and improves training stability through clipped double Q-learning, delayed policy updates, and target policy smoothing (Fujimoto et al., 2018). • HAC: a hyper-actor–critic method that represents recommendation slates in a latent action space and decomposes slate generation into hyper-action inference and effect-action selection (Liu et al., 2023). E.2 Evaluation Metrics The metrics below describe complete simulated sessions. Let N be the number of evaluated sessions, TnT_n the length of session n, and Rn,tR_n,t its reward at request t. Let Ln,tL_n,t denote the item collection used by the evaluation code at that request. A baseline with fixed slate size has |Ln,t|=M|L_n,t|=M, while the reported RLCP set size uses its retained execution collection. Catalog diversity and ILD require the evaluated collection to be defined consistently across methods. Depth. We first measure how long the interaction continues. Depth is the mean number of recommendation steps before departure: Depth=1N∑n=1NTn.Depth= 1N _n=1^NT_n. A larger value means that the simulated sessions contain more interactions; it does not specify how much reward those interactions produce. Average Reward. To measure the reward per interaction while giving equal weight to each session, we first average within sessions and then across sessions: AvgReward=1N∑n=1N1Tn∑t=1TnRn,t.AvgReward= 1N _n=1^N 1T_n _t=1^T_nR_n,t. Total Reward. In contrast, total reward records the cumulative reward of a session before averaging across sessions: TotalReward=1N∑n=1N∑t=1TnRn,t.TotalReward= 1N _n=1^N _t=1^T_nR_n,t. Diversity. To measure exposure across users, catalog diversity counts distinct items in the B active requests of an evaluation batch and averages this count over HevalH_eval evaluation steps, following KuaiSim: Diversity=1Heval∑h=1Heval|⋃j=1BLj,h|.Diversity= 1H_eval _h=1^H_eval | _j=1^BL_j,h |. The tables call this metric Diversity. It counts exposed items and is distinct from the proxy retention probability controlled by calibration. Intra List Diversity. Catalog diversity does not describe how similar the items within a request are. ILD measures that separate property through mean pairwise dissimilarity within each evaluated collection. Write Mn,t=|Ln,t|M_n,t=|L_n,t| and let eae_a be the embedding of item a. Then ILD =1∑n=1NTn∑n=1N∑t=1Tn2Mn,t(Mn,t−1) = 1 _n=1^NT_n _n=1^N _t=1^T_n 2M_n,t(M_n,t-1) ×∑1≤j<k≤Mn,td(e(Ln,t)j,e(Ln,t)k). × _1≤ j<k≤ M_n,td\! (e_(L_n,t)_j,e_(L_n,t)_k ). Here d(⋅,⋅)d(·,·) is the item dissimilarity function and Mn,tM_n,t is the number of items in the evaluated collection at request t of session n. For Mn,t=1M_n,t=1, the corresponding diversity term is defined as zero. Admissible Set Size. Finally, the average admissible set size records how many items remain after filtering, averaged over evaluation requests: SetSize=1∑n=1NTn∑n=1N∑t=1Tn|Ln,t|.SetSize= 1 _n=1^NT_n _n=1^N _t=1^T_n|L_n,t|. A smaller value indicates that fewer alternatives are retained. It is not a measure of total computation, since it excludes scoring the candidate pool and obtaining the proxy label. Appendix F Full Results The following tables report the complete measurements underlying Section 5. Each configuration fixes the dataset, reward signal, patience parameters, and baseline slate size M, with the matched cap K=MK=M for RLCP. Comparisons therefore concern the same maximum set size within a configuration. Boldface identifies the highest depth and catalog diversity and the lowest mean set size, including ties. These markings compare point estimates and do not imply statistical significance. Table 2: KuaiRand-Pure results under patience setting (p,q)=(1,2)(p,q)=(1,2) with is_click as the reward signal for displayed slate sizes M∈3,4,5M∈\3,4,5\. The final seven columns report behavior rates; set size is reported for RLCP variants when available. Method Depth Avg. reward Total reward Diversity ILD Set size Click Comment Follow Forward Hate Like Long view Slate size M=3M=3 DDPG 18.80 0.62 13.46 25.00 0.99 3.00 0.62 0.61 0.54 0.54 0.55 0.58 0.64 TD3 19.20 0.65 13.24 54.50 0.99 3.00 0.65 0.62 0.52 0.54 0.52 0.58 0.63 A2C 19.60 0.66 13.32 3.00 0.99 3.00 0.66 0.61 0.58 0.56 0.54 0.60 0.62 HAC 19.10 0.67 13.47 4.70 0.98 3.00 0.67 0.62 0.57 0.55 0.54 0.56 0.68 RLCP-Single 19.30 0.64 13.20 92.40 0.99 2.91 0.64 0.57 0.55 0.55 0.52 0.59 0.65 RLCP 19.40 0.61 12.77 28.50 1.00 3.00 0.61 0.58 0.56 0.55 0.54 0.57 0.59 Slate size M=4M=4 DDPG 19.60 0.66 13.55 19.50 0.99 4.00 0.66 0.61 0.58 0.58 0.52 0.58 0.65 TD3 19.70 0.61 13.49 84.40 0.99 4.00 0.61 0.61 0.55 0.52 0.54 0.56 0.61 A2C 19.90 0.67 13.35 15.50 0.99 4.00 0.67 0.65 0.59 0.57 0.55 0.63 0.66 HAC 19.60 0.67 13.62 6.60 0.99 4.00 0.67 0.59 0.58 0.54 0.50 0.61 0.65 RLCP-Single 19.90 0.64 13.52 126.40 0.99 4.00 0.64 0.61 0.59 0.55 0.54 0.60 0.64 RLCP 19.90 0.59 13.10 50.50 1.00 4.00 0.59 0.58 0.52 0.51 0.52 0.56 0.59 Slate size M=5M=5 DDPG 19.90 0.68 13.67 17.50 0.99 5.00 0.68 0.60 0.56 0.56 0.54 0.57 0.65 TD3 19.90 0.64 13.67 47.20 0.99 5.00 0.64 0.58 0.54 0.53 0.52 0.58 0.63 A2C 20.00 0.65 13.35 24.80 0.99 5.00 0.65 0.61 0.58 0.54 0.53 0.60 0.63 HAC 20.00 0.66 13.99 10.00 0.99 5.00 0.66 0.60 0.58 0.55 0.53 0.59 0.65 RLCP-Single 20.00 0.66 13.93 154.10 0.99 4.91 0.66 0.56 0.53 0.53 0.55 0.55 0.64 RLCP 20.00 0.63 13.03 36.40 1.00 5.00 0.63 0.56 0.56 0.53 0.54 0.56 0.63 Table 3: KuaiRand-Pure results under patience setting (p,q)=(0.4,2)(p,q)=(0.4,2) with is_click as the reward signal for displayed slate sizes M∈4,5M∈\4,5\. The final seven columns report behavior rates; set size is reported for RLCP variants when available. Method Depth Avg. reward Total reward Diversity ILD Set size Click Comment Follow Forward Hate Like Long view Slate size M=4M=4 DDPG 46.80 0.70 32.83 14.40 0.99 4.00 0.70 0.62 0.59 0.57 0.52 0.60 0.68 TD3 48.00 0.69 33.46 25.90 0.99 4.00 0.69 0.64 0.59 0.60 0.53 0.61 0.70 A2C 46.00 0.64 31.35 4.10 0.98 4.00 0.64 0.60 0.57 0.54 0.55 0.57 0.63 HAC 48.00 0.68 32.95 7.10 0.99 4.00 0.68 0.64 0.58 0.57 0.53 0.61 0.69 RLCP-Single 47.60 0.68 32.92 118.10 0.99 3.84 0.68 0.62 0.57 0.54 0.55 0.60 0.65 RLCP 47.20 0.62 31.91 41.60 1.00 3.91 0.63 0.57 0.58 0.55 0.54 0.59 0.62 Slate size M=5M=5 DDPG 48.00 0.68 33.63 20.00 0.98 5.00 0.68 0.62 0.60 0.58 0.52 0.61 0.66 TD3 48.00 0.68 33.74 37.90 0.99 5.00 0.68 0.64 0.58 0.57 0.54 0.60 0.69 A2C 48.00 0.63 32.49 5.00 0.98 5.00 0.63 0.57 0.57 0.54 0.53 0.58 0.64 HAC 48.00 0.59 31.45 5.40 0.98 5.00 0.59 0.57 0.55 0.51 0.53 0.57 0.60 RLCP-Single 48.00 0.69 33.51 149.90 0.99 4.94 0.69 0.64 0.58 0.58 0.56 0.60 0.69 RLCP 48.00 0.61 31.35 77.00 1.00 5.00 0.61 0.60 0.55 0.55 0.54 0.60 0.58 Table 4: KuaiRand-Pure results under patience setting (p,q)=(1,2)(p,q)=(1,2) with is_like as the reward signal for displayed slate sizes M∈4,5,6M∈\4,5,6\. The final seven columns report behavior rates; set size is reported for RLCP variants when available. Method Depth Avg. reward Total reward Diversity ILD Set size Click Comment Follow Forward Hate Like Long view Slate size M=4M=4 DDPG 19.80 0.61 12.79 24.00 0.99 4.00 0.66 0.60 0.58 0.55 0.54 0.61 0.65 TD3 19.80 0.60 12.69 51.80 0.99 4.00 0.62 0.60 0.59 0.57 0.56 0.60 0.62 A2C 19.70 0.60 12.83 4.00 0.98 4.00 0.62 0.60 0.59 0.55 0.53 0.60 0.59 HAC 20.00 0.58 12.84 8.60 0.99 4.00 0.64 0.59 0.56 0.57 0.53 0.58 0.66 RLCP-Single 19.80 0.61 12.85 119.70 0.99 3.91 0.63 0.59 0.57 0.57 0.54 0.61 0.63 RLCP 19.70 0.59 12.27 58.60 1.00 4.00 0.64 0.59 0.58 0.54 0.54 0.59 0.64 Slate size M=5M=5 DDPG 20.00 0.58 12.88 21.80 0.99 5.00 0.62 0.57 0.56 0.54 0.54 0.58 0.58 TD3 19.90 0.58 13.18 72.30 0.99 5.00 0.61 0.59 0.54 0.55 0.52 0.58 0.63 A2C 19.80 0.59 12.87 5.00 0.98 5.00 0.62 0.60 0.57 0.54 0.55 0.59 0.62 HAC 20.00 0.57 13.06 10.20 0.99 5.00 0.65 0.59 0.58 0.56 0.54 0.57 0.63 RLCP-Single 20.00 0.58 12.83 149.60 0.99 4.78 0.64 0.60 0.57 0.53 0.52 0.58 0.65 RLCP 20.00 0.56 11.98 64.40 1.00 5.00 0.62 0.57 0.57 0.53 0.54 0.56 0.62 Slate size M=6M=6 DDPG 20.00 0.57 12.62 25.50 0.99 6.00 0.59 0.59 0.55 0.55 0.53 0.57 0.57 TD3 20.00 0.59 12.51 60.70 0.99 6.00 0.65 0.61 0.55 0.55 0.55 0.59 0.63 A2C 20.00 0.62 12.74 6.00 0.99 6.00 0.66 0.62 0.58 0.54 0.53 0.62 0.64 HAC 20.00 0.62 12.76 9.10 0.99 6.00 0.63 0.59 0.57 0.56 0.55 0.62 0.61 RLCP-Single 19.90 0.60 12.83 155.80 0.99 4.47 0.66 0.61 0.57 0.55 0.54 0.60 0.64 RLCP 20.00 0.58 11.46 100.20 1.00 6.00 0.60 0.56 0.55 0.53 0.51 0.58 0.59 Table 5: KuaiRand-Pure results under patience setting (p,q)=(0.4,2)(p,q)=(0.4,2) with is_like as the reward signal for displayed slate sizes M∈5,6M∈\5,6\. The final seven columns report behavior rates; set size is reported for RLCP variants when available. Method Depth Avg. reward Total reward Diversity ILD Set size Click Comment Follow Forward Hate Like Long view Slate size M=5M=5 DDPG 47.60 0.57 31.62 35.20 0.99 5.00 0.65 0.60 0.57 0.55 0.57 0.57 0.67 TD3 48.00 0.60 31.93 53.90 0.99 5.00 0.69 0.64 0.57 0.58 0.56 0.60 0.71 A2C 45.60 0.60 30.79 5.00 0.98 5.00 0.64 0.62 0.58 0.56 0.55 0.60 0.66 HAC 47.20 0.61 29.78 5.10 0.98 5.00 0.63 0.59 0.59 0.52 0.54 0.61 0.63 RLCP-Single 48.00 0.62 31.09 151.70 0.99 4.84 0.70 0.63 0.61 0.57 0.55 0.62 0.70 RLCP 47.70 0.56 29.20 72.20 1.00 4.97 0.60 0.58 0.56 0.53 0.53 0.57 0.58 Slate size M=6M=6 DDPG 48.00 0.61 30.86 58.30 0.99 6.00 0.67 0.62 0.59 0.56 0.52 0.61 0.67 TD3 46.80 0.60 31.75 124.70 0.99 6.00 0.71 0.64 0.60 0.58 0.52 0.60 0.70 A2C 48.00 0.63 30.11 6.00 0.98 6.00 0.70 0.63 0.59 0.58 0.56 0.63 0.69 HAC 47.90 0.59 30.54 7.50 0.98 6.00 0.65 0.60 0.58 0.53 0.52 0.59 0.64 RLCP-Single 48.00 0.62 31.22 184.20 0.99 5.72 0.70 0.65 0.61 0.58 0.53 0.62 0.69 RLCP 48.00 0.59 28.52 85.50 1.00 6.00 0.61 0.55 0.55 0.54 0.53 0.60 0.57 Table 6: ML-1M results under patience setting (p,q)=(1,2)(p,q)=(1,2) with is_click as the reward signal for displayed slate sizes M∈4,5M∈\4,5\. The final three columns report behavior rates; set size is reported for RLCP variants when available. Method Depth Avg. reward Total reward Diversity ILD Set size Click Like Star Slate size M=4M=4 DDPG 19.90 0.69 13.95 23.90 0.99 4.00 0.69 0.69 0.70 TD3 19.90 0.73 14.90 15.90 0.99 4.00 0.73 0.72 0.70 A2C 19.20 0.58 11.97 46.30 0.99 4.00 0.58 0.61 0.62 HAC 20.00 0.68 14.30 4.80 0.99 4.00 0.68 0.66 0.66 RLCP-Single 19.80 0.58 11.85 119.40 0.99 4.00 0.58 0.58 0.58 RLCP 20.00 0.61 12.85 41.80 1.00 4.00 0.61 0.57 0.55 Slate size M=5M=5 DDPG 19.90 0.69 13.82 35.20 0.99 5.00 0.69 0.68 0.69 TD3 20.00 0.73 14.87 16.30 0.99 5.00 0.73 0.72 0.75 A2C 19.90 0.58 11.86 49.50 0.99 5.00 0.58 0.61 0.61 HAC 20.00 0.63 12.80 6.70 0.99 5.00 0.63 0.61 0.63 RLCP-Single 20.00 0.57 12.41 17.30 0.99 5.00 0.57 0.61 0.62 RLCP 19.80 0.60 13.71 54.90 1.00 4.53 0.64 0.59 0.57 Table 7: ML-1M results under patience setting (p,q)=(0.4,2)(p,q)=(0.4,2) with is_click as the reward signal for displayed slate sizes M∈4,5M∈\4,5\. The final three columns report behavior rates; set size is reported for RLCP variants when available. Method Depth Avg. reward Total reward Diversity ILD Set size Click Like Star Slate size M=4M=4 DDPG 46.80 0.69 33.76 12.90 0.99 4.00 0.69 0.71 0.73 TD3 46.80 0.71 35.13 14.30 0.99 4.00 0.71 0.71 0.73 A2C 44.00 0.59 26.76 31.20 0.99 4.00 0.59 0.64 0.64 HAC 45.20 0.61 29.02 9.70 0.99 4.00 0.61 0.64 0.65 RLCP-Single 45.60 0.57 26.56 119.30 0.99 3.97 0.57 0.59 0.63 RLCP 46.80 0.57 27.95 62.00 1.00 3.78 0.59 0.60 0.60 Slate size M=5M=5 DDPG 47.20 0.69 34.00 15.80 0.99 5.00 0.69 0.69 0.72 TD3 48.00 0.72 34.98 18.20 0.99 5.00 0.72 0.71 0.71 A2C 48.00 0.59 28.88 7.80 0.99 5.00 0.59 0.66 0.68 HAC 48.00 0.65 32.25 5.30 0.99 5.00 0.65 0.67 0.70 RLCP-Single 47.60 0.59 28.12 94.80 0.99 4.97 0.59 0.62 0.63 RLCP 48.00 0.63 30.64 45.10 1.00 4.97 0.63 0.63 0.62 Table 8: ML-1M results under patience setting (p,q)=(1,2)(p,q)=(1,2) with is_like as the reward signal for displayed slate sizes M∈4,5,6M∈\4,5,6\. The final three columns report behavior rates; set size is reported for RLCP variants when available. Method Depth Avg. reward Total reward Diversity ILD Set size Click Like Star Slate size M=4M=4 DDPG 19.80 0.65 13.21 32.80 0.99 4.00 0.63 0.65 0.67 TD3 19.80 0.66 13.71 20.80 0.99 4.00 0.65 0.66 0.66 A2C 19.60 0.60 12.83 4.10 0.99 4.00 0.57 0.60 0.60 HAC 19.90 0.64 13.31 13.90 0.99 4.00 0.67 0.64 0.63 RLCP-Single 19.80 0.63 12.75 7.70 0.99 4.00 0.58 0.63 0.62 RLCP 19.90 0.61 12.49 74.10 1.00 4.00 0.62 0.61 0.60 Slate size M=5M=5 DDPG 19.90 0.62 13.09 52.00 0.99 5.00 0.64 0.62 0.63 TD3 20.00 0.67 14.06 24.50 0.99 5.00 0.67 0.67 0.67 A2C 19.80 0.67 13.05 5.70 0.99 5.00 0.60 0.67 0.65 HAC 19.90 0.67 13.41 11.40 0.99 5.00 0.63 0.67 0.66 RLCP-Single 20.00 0.63 13.03 11.50 0.99 5.00 0.60 0.63 0.62 RLCP 20.00 0.62 12.34 64.60 1.00 5.00 0.63 0.62 0.60 Slate size M=6M=6 DDPG 20.00 0.66 13.46 59.10 0.99 6.00 0.63 0.66 0.67 TD3 20.00 0.69 13.73 26.20 0.99 6.00 0.65 0.69 0.70 A2C 19.80 0.65 13.19 9.60 0.99 6.00 0.62 0.65 0.69 HAC 20.00 0.63 13.34 28.60 0.99 6.00 0.61 0.63 0.64 RLCP-Single 20.00 0.61 12.67 173.70 0.99 5.94 0.56 0.61 0.61 RLCP 20.00 0.58 12.00 69.20 1.00 6.00 0.61 0.58 0.56 Table 9: ML-1M results under patience setting (p,q)=(0.4,2)(p,q)=(0.4,2) with is_like as the reward signal for displayed slate sizes M∈4,5M∈\4,5\. The final three columns report behavior rates; set size is reported for RLCP variants when available. Method Depth Avg. reward Total reward Diversity ILD Set size Click Like Star Slate size M=4M=4 DDPG 47.20 0.73 33.86 20.10 0.99 4.00 0.68 0.73 0.70 TD3 47.20 0.70 34.57 20.60 0.99 4.00 0.69 0.70 0.70 A2C 41.20 0.64 29.45 22.30 0.99 4.00 0.60 0.64 0.63 HAC 44.20 0.71 31.59 6.80 0.99 4.00 0.68 0.71 0.69 RLCP-Single 46.80 0.63 29.46 12.40 0.99 4.00 0.61 0.63 0.63 RLCP 45.60 0.57 28.28 70.60 1.00 3.84 0.58 0.58 0.60 Slate size M=5M=5 DDPG 48.00 0.70 34.83 22.40 0.99 5.00 0.71 0.70 0.70 TD3 48.00 0.73 34.48 11.60 0.99 5.00 0.71 0.73 0.72 A2C 47.70 0.64 31.75 7.40 0.99 5.00 0.62 0.64 0.65 HAC 47.20 0.65 32.45 25.10 0.99 5.00 0.65 0.65 0.68 RLCP-Single 48.00 0.62 31.27 8.50 0.99 5.00 0.63 0.62 0.62 RLCP 48.00 0.57 27.90 82.10 1.00 5.00 0.58 0.57 0.59