Reinforcement Learning with Conformal Action Sets: An Application to Sequential Recommendation

• Fixed-cardinality slates cannot reflect changes in how many useful alternatives are available during a session.The proposed design criterion is to retain a compact set while controlling the risk of excluding all valuable actions.Source: §1 · p. 1
• RLCP uses critic scores, an online threshold, and binary proxy-target feedback to calibrate retention along adaptive trajectories.The update gives a deterministic bound on observed proxy miss frequency, not retention defined by the unknown optimal value function.Source: §1 · p. 1
• RLCP improves catalog diversity while maintaining competitive session depth under the same set size cap as the baselines.Figure 1 summarizes results across 19 experimental configurations.Source: Figure 1 · p. 2
• The value analysis separates discounted loss from filtering from loss due to selection among retained actions.Under stated proxy and critic conditions, the resulting finite-session reward guarantee also accounts for selection error and maximum-set-size truncation without requiring parameter convergence.Source: §1 · p. 2

2 PROBLEM FORMULATION

• The learner operates in a finite discounted MDP with bounded rewards, history-based updates, and state-action-dependent reward and transition laws.The state value and state-action value functions are defined for policies in the stationary Markov policy class.Source: §2 · p. 2
• The oracle target contains actions whose optimal continuation values are within ε of the best, but that target is unknown to the learner.Retention is evaluated under the discounted occupancy of the downstream policy, which can change when the execution set changes.Source: §2 · p. 2, §2.1 · p. 3

2.1 Action Filtering and Execution

• A learned score and threshold form the raw set; if it is empty, the minimum-score action is used so execution remains possible.The nonempty execution set restricts which actions the downstream policy may select.Source: §2.1 · p. 3
• The item-MDP setup assumes reward and transition no longer depend on the remaining collection once the selected item and current state are fixed.When departure depends on the collection itself, the collection must instead be modeled as the action.Source: §2.1 · p. 3
• Retention succeeds when the raw set contains an oracle-target action, and an empty raw set counts as a miss even if the fallback is valuable.The desired miss-rate condition limits the discounted occupancy mass of states where all oracle-target actions are removed.Source: §2.1 · p. 3
• The smallest score among oracle-target actions gives a scalar threshold condition, but its oracle margin depends on unknown optimal values.RLCP therefore calibrates a proxy margin from observable feedback instead.Source: §2.1 · p. 3

2.2 Policy-Dependent Action-Set Objective

• The threshold objective evaluates expected set size and retention under the occupancy of the best policy supported by the retained set.Because the threshold can change that policy and its state occupancy, the smallest feasible threshold need not minimize expected set size.Source: §2.2 · p. 4
• RLCP learns scores by value estimation and updates its threshold from proxy feedback, without assuming these coupled updates solve the benchmark optimization.The guarantees apply while the score and policy continue to change.Source: §2.2 · p. 4

3.1 Retention Calibration During Learning

• With bounded margin width and a constant step size, the deterministic calibration update gives an O(1/T) deviation of observed proxy-miss frequency from α, even as the critic and actor change.A miss raises the threshold and a hit lowers it; the guarantee concerns the realized sequence, not every state or convergence to a fixed population quantile.Source: §3.1 · p. 4
• A cap can remove every proxy-target action from a raw-set hit, so calibration of raw misses alone does not control cap-induced misses.The combined miss rate also depends on ranking and the cap.Source: §3.1 · p. 5

3.2 From Retention to Long-Horizon Value

• For any nonempty retained set and stationary policy, value loss equals discounted expected filtering loss plus selection loss under the policy’s state occupancy.The filtering term is the gap to the best retained action; the selection term is the remaining gap to the policy’s expected choice.Source: §3.2 · p. 5
• A proxy hit bounds filtering loss only when proxy-score gaps approximate optimal-value gaps; critic accuracy and within-set selection error separately bound selection loss.A critic that evaluates only the current policy need not approximate the unrestricted optimal action values.Source: §3.2 · p. 5

3.3 Adaptive Finite Session Guarantee

• Under Assumption C.12, the finite-session guarantee accounts for proxy-hit and miss filtering loss, critic and selection errors, deviations from the target miss rate, and proxy hits removed by the cap.The bound is evaluated along the adaptive trajectory and does not require convergence.Source: §3.3 · p. 5

4 RLCP ALGORITHM

• At each step, RLCP retains actions whose estimated value gaps are below the online threshold, caps oversized sets by keeping the smallest-gap actions, and uses a critic-maximizer fallback for an empty set.The downstream selector then chooses from the resulting execution set.Source: §4 · p. 6
• The threshold update uses whether the raw set intersects the proxy target; neither the cap nor fallback changes the miss used for calibration.The verifier supplies this signal without revealing Q∗.Source: §4 · p. 6
• Interaction data update the critic and selector, while raw proxy misses update the threshold; calibration is updated more frequently than the critic in the implementation.The pathwise guarantee uses the unprojected update; substituting capped misses is a different procedure.Source: §4 · p. 6
• Pruning preserves a global critic maximizer, so an exactly greedy selector using the same critic and tie rule chooses the same action with or without pruning.The method instead regulates alternatives available to a stochastic actor, slate constructor, or user choice mechanism.Source: §4 · p. 6

5 EXPERIMENTS

• KuaiSim evaluates full-session policy interaction, with user feedback, rewards, and session departure generated during rollouts on KuaiRand-Pure and MovieLens 1M.MovieLens ratings above 3 map to positive feedback, ratings at most 3 to negative feedback, and day-level groups define sessions.Source: §5 · p. 6, §5.1 · pp. 6–7

5.1 Datasets and Simulator

• The modified leave module makes session length response-dependent, using click and like as rewards and larger patience decrements after no positive response.The compared settings are (p, q) = (1, 2) and (0.4, 2).Source: §5.1 · p. 7

5.2 Baselines and Metrics

• RLCP is compared with A2C, DDPG, TD3, and HAC using depth, reward, catalog diversity, ILD, and average admissible-set size.Full RLCP constrains a downstream slate actor, while RLCP-Single feeds the admissible set to the environment and uses its first rewarded item as the rollout action; both share online calibration and a minimum-set-size rescue.Source: §5.2 · p. 7, §5.3 · p. 7

5.3 Method Implementation

• Across all 19 configurations, at least one RLCP variant achieves the highest catalog diversity without requiring a larger retained set.The comparisons use matched set-size caps and shared simulator, reward, and patience settings.Source: §5.3 · p. 7
• On KuaiRand-Pure, RLCP-Single leads catalog diversity in all ten configurations, reaching 1.48× to 4.56× the strongest baseline.Its mean retained set is smaller than M in nine configurations, with a maximum reduction of 25.5%, and equals M in the remaining configuration; it attains or ties the highest depth in six and stays within 0.4 interactions of the best method otherwise. Full RLCP reports ILD 1.00 throughout.Source: §5.3 · p. 7, Figure 3 · p. 8
• On ML-1M, the stronger RLCP variant reaches 1.11× to 5.21× the strongest baseline’s catalog diversity; full RLCP leads in five configurations and RLCP-Single in the remaining four.Full RLCP attains or ties the highest depth in seven configurations, maintains ILD 1.00 throughout, and reduces mean set size below M in four; several methods reach the depth ceiling of 48 under longer patience.Source: §5.3 · pp. 7–8, Figure 4 · p. 8

6 CONCLUSION

• Across KuaiRand-Pure and ML-1M, an RLCP variant achieves the highest catalog diversity in every configuration, while full RLCP consistently has the highest within-slate diversity.RLCP remains competitive with fixed-slate baselines in session depth while using sets of equal or smaller size.Source: §6 · p. 8

A RELATED WORK

• Sequential recommendation methods address evaluation or selection, whereas RLCP asks which candidate actions should remain available and how retention affects sequential value.The item model does not cover every reward or transition rule that depends on a slate.Source: A RELATED WORK · p. 11
• Prior conformal recommendation adapts sets to calibrated targets, but such targets need not identify actions with high continuation value under an interacting policy.RLCP distinguishes proxy from oracle retention and states an approximation condition connecting them.Source: A RELATED WORK · p. 11
• RLCP applies an established scalar online-calibration update to changing policy-state distributions; its analysis makes the action-margin dependence explicit.Online miscoverage tracking itself is not presented as a new principle.Source: A RELATED WORK · p. 11
• RLCP is not distinguished by jointly learning a policy and adaptive conformal threshold, but by action filtering and the value analysis connecting proxy hits to oracle retention and selection.The value decomposition and finite-session bound do not assume convergence of coupled updates.Source: A RELATED WORK · p. 11

B ADDITIONAL MODELING DETAILS

• The modeling discussion relates an item-level MDP abstraction to recommendation pipelines, where retrieval and collection-based response rules impose additional conditions.The section frames how those pipeline stages affect applicability of the item-level results.Source: B ADDITIONAL MODELING DETAILS · p. 11

B.1 Sequential Recommendation Interpretation

• Retrieval and filtering have separate tolerance budgets: their value tolerances add, while miss probability includes retrieval failure and filtering failure conditional on retrieval success.A global tolerance ε requires the two value tolerances to sum to at most ε.Source: §B.1 · p. 12
• The item-level reduction matches pipeline trajectories when reward and transition depend on the state and item selected before feedback, not further on the collection or slate.When response-dependent selection breaks that ordering, the collection can instead be modeled as the action, but item-value results do not automatically transfer; click or like reward alone also does not establish a depth bound.Source: §B.1 · pp. 12–13

C ADDITIONAL SUPPORTING RESULTS

• The supporting results proceed from a population benchmark to set-size caps and conditions transferring proxy retention and approximate selection to value.The transfer requires explicit assumptions rather than following from calibration alone.Source: C ADDITIONAL SUPPORTING RESULTS · p. 13

C.1 Restricted Control and Existence

• For every nonempty retained-set map, restricted control has a unique value fixed point, attained by a stationary deterministic policy; the fixed-score threshold problem also attains a minimum.These existence results do not assert that critic or actor training finds the global solution.Source: §C.1 · p. 13

C.2 Threshold Characterization for a Fixed Policy

• For a fixed score and policy, the smallest threshold satisfying the retention condition also minimizes expected set size under that policy’s occupancy.The threshold is characterized by a quantile of the oracle margin; the population benchmark remains coupled because occupancy changes with the downstream response.Source: §C.2 · p. 14

C.3 Maximum Set Size

• After capping at K, proxy retention is feasible only when a proxy-target action ranks among the first K; calibration cannot repair a failed capacity condition.Capped misses include both raw misses and hits lost specifically through truncation.Source: §C.3 · p. 14

C.4 Additional Value Results

• In a one-state, two-action discounted MDP, a retained set can always contain an optimal action while a supported policy still has value gap (1 −γ)−1.The corollary averages hit-case filtering loss, at most the target tolerance, and miss-case loss, at most the largest action gap, while retaining a separate selection loss. The factor (1−γ)−1 accounts for accumulation along the discounted session.Source: §C.4 · pp. 14–15

C.5 Practical Proxy, Critic, and Recommendation Errors

• Pairwise proxy-gap fidelity makes a proxy-target hit imply a hit of an enlarged oracle target under any state distribution.The condition compares action gaps after allowing for scale, rather than requiring absolute agreement with Q∗.Source: §C.5 · p. 15
• An immediate-response proxy satisfies gap fidelity with λ = 1 and δprox = δdyn; response-model error δresp raises the latter to δdyn + 2δresp.The continuation-effect term is bounded by γ/(1−γ) times the maximum total-variation distance between action-conditioned transitions; an exact simulator response proxy can still have large continuation error.Source: §C.5 · pp. 15–16
• The combined practical bound assigns calibration to proxy misses, proxy fidelity to retained-action quality, and critic accuracy plus selection quality to remaining decision loss.These are conditional requirements; a critic for a current or restricted policy class need not be accurate relative to unrestricted Q∗.Source: §C.5 · p. 16

Then the collection-based rule satisfies

• The collection-based patience rule’s one-step bound uses the chance of any positive response, while pre-response item selection adds a selection term.No independence among item responses is required; these results do not by themselves extend to session depth without modeling patience evolution, transitions, and departure.Source: Then the collection-based rule satisfies · p. 17

C.6 Full Conditions for the Finite Session Bound

• The finite-session setup permits changing policies and scores without parameter convergence, using an online threshold and visited-state approximation conditions.The conditions require information available before action selection and bound proxy, critic, and selector errors; they explain performance effects but do not guarantee that learning updates make errors small.Source: §C.6 · p. 17, Let the threshold follow · p. 18

C.7 Greedy Preservation and Conditional Policy Recovery

• Threshold-and-cap pruning preserves the first global critic maximizer, so a greedy selector with matching tie-breaking chooses the same action with or without filtering.If βt < ∆min, a global critic maximizer is truly optimal; vanishing critic and selector errors imply value convergence, but these are conditional implications, not learning-update guarantees.Source: §C.7 · p. 19

D COMPLETE PROOFS

• The proofs establish Bellman identities and value bounds before deriving the benchmark, calibration, and value-loss arguments; they also establish existence of a stationary deterministic optimal policy.The proof roadmap ends with greedy preservation as the case where filtering does not change the selected action.Source: D COMPLETE PROOFS · p. 19, The optimal values satisfy · pp. 19, 21

The optimal values satisfy

• For every policy π, 0 ≤ Vπ(s), Qπ(s,a), V*(s), Q*(s,a) ≤ 1/(1−γ); consequently, 0 ≤ Δmax ≤ (1−γ)^−1.Source: The optimal values satisfy · p. 22

D.2 Proofs for the Bilevel Formulation

• For any nonempty retained action sets D, maximizing over supported policies is equivalent to a discounted-occupancy LP, and lexicographic selection fixes a unique optimal response.The occupancy formulation has optimal value (1 − γ)V*; the lexicographically smallest optimal occupancy supplies the response convention for the outer objective.Source: §D.2 · pp. 22, 24, 25, 26
• For fixed θ, only finitely many complete raw–operational designs arise as the threshold varies, and a minimizing feasible threshold exists because the all-action threshold is feasible.At that threshold, both the raw and operational sets equal A at every state, giving retention probability one.Source: §D.2 · pp. 26–27

D.3 Proof of the Quantile Characterization

• Under a fixed policy, coverage-valid thresholds are exactly [q, ∞), where q = τmin(θ, π), and q minimizes expected operational-set size.The operational sets are nested as the threshold increases, which gives the size-minimality result under the same fixed policy.Source: §D.3 · pp. 27–28

D.4 Proof of Pathwise Calibration

• For any adaptive sequence, the calibration update’s interval invariant yields a deterministic cumulative-miss bound, with convergence and constant-step consequences following from that bound.The proof first bounds the threshold within an interval determined by realized margins, then relates cumulative calibration error to threshold increments.Source: §D.4 · pp. 28–29

D.5 Proofs for the Value Results

• A set can contain an optimal action with certainty yet permit a policy that always chooses a suboptimal action and incurs the maximal value gap, 1/(1−γ).In the counterexample, the supported policy always chooses the suboptimal action and receives zero reward at every time.Source: §D.5 · p. 30
• The exact value-loss decomposition splits the supported policy’s Bellman residual into filtering and selection losses, rather than bounding them through separate trajectory comparisons.The proof shows both terms are nonnegative and their sum is the optimal Bellman residual.Source: §D.5 · p. 30
• Under pointwise retention of a target action at every state, the restricted optimal value is within ε0/(1−γ) of the unrestricted value at every initial state.The proof compares the restricted optimum with a supported policy that selects a near-optimal retained action.Source: §D.5 · pp. 32–33
• Proxy fidelity transfers proxy-target hits to an enlarged oracle target, while critic accuracy and within-set selection conditions bound the remaining selection loss.The combined bound applies these two transfers in sequence; the approximate-selection result assumes a nonempty retained set and a uniform critic error bound.Source: §D.5 · pp. 34–35
• For finite sessions, the proof separates each stage’s filtering and selection gaps and derives a performance bound while allowing the policy and critic to change during the session.Filtering is controlled through capped-miss calibration, and the remaining selection gap is bounded using the critic condition.Source: §D.5 · pp. 36–37
• The session value bound combines filtering and selection bounds over horizon H without requiring the policy, critic, or threshold to converge.The proof uses their stated stagewise information and error conditions.Source: §D.5 · p. 37

D.6 Proof of Greedy Preservation and Conditional Recovery

• Thresholding, capping, and fallback preserve the global critic maximizer, so greedy selection returns the same item with or without filtering.The proof then expresses policy loss through pairwise critic error and the remaining selection gap.Source: §D.6 · p. 38
• When β_t < Δ_min, ranking consistency makes policies supported on critic maximizers optimal; as β_t → 0, exact greedy selection is eventually optimal when a positive gap exists.With a unique optimal action at each state, the action distribution is eventually a fixed point mass; with multiple optimal actions, convergence of the distribution is not required.Source: §D.6 · pp. 38–39

E EXPERIMENT DETAILS

• The reported metrics distinguish utility, catalog exposure, and retained set size, separately from the calibration guarantee.Source: E EXPERIMENT DETAILS · p. 39

E.1 Baseline Details

• The baselines include A2C (Mnih et al., 2016) and HAC (Liu et al., 2023), which uses latent-action slate generation.A2C uses advantage-weighted policy gradients and a state-value critic; HAC decomposes slate generation into hyper-action inference and effect-action selection.Source: §E.1 · p. 39
• DDPG (Lillicrap et al., 2016) is applied to continuous slate representations, while TD3 adds measures to mitigate value overestimation and improve training stability.TD3 uses clipped double Q-learning, delayed policy updates, and target policy smoothing.Source: §E.1 · p. 39

E.2 Evaluation Metrics

• Depth is the mean number of recommendation steps before departure, but does not indicate how much reward those interactions produce.A larger depth means more interactions in the simulated sessions.Source: §E.2 · p. 39
• Average reward weights sessions equally after averaging within each session, whereas total reward averages each session’s cumulative reward.The two measures distinguish reward per interaction from cumulative session reward.Source: §E.2 · p. 39
• Catalog diversity counts distinct items exposed across active requests, unlike the proxy retention probability controlled by calibration.The metric averages the distinct-item count across evaluation steps.Source: §E.2 · p. 40
• ILD measures mean pairwise dissimilarity within each evaluated collection, with the diversity term defined as zero for a one-item collection.The collection contains the items used at a particular request.Source: §E.2 · p. 40
• Average admissible set size records the number of items retained after filtering, but is not total computation because it excludes candidate scoring and proxy-label acquisition.The evaluation collection is defined consistently across methods; fixed-slate baselines have size M.Source: §E.2 · pp. 39–40

F FULL RESULTS

• Each configuration compares methods at the same maximum set size; boldface marks point-estimate extrema and does not imply statistical significance.The markings identify highest depth and catalog diversity and lowest mean set size, including ties.Source: F FULL RESULTS · p. 40
• Tables 2 and 3 cover KuaiRand-Pure with click reward, using patience settings (1, 2) and (0.4, 2), respectively.The displayed slate sizes are {3, 4, 5} for Table 2 and {4, 5} for Table 3.Source: Table 2 · p. 41, Table 3 · p. 41
• Tables 4 and 5 cover KuaiRand-Pure with like reward, using patience settings (1, 2) and (0.4, 2), respectively.The displayed slate sizes are {4, 5, 6} for Table 4 and {5, 6} for Table 5.Source: Table 4 · p. 42, Table 5 · p. 42
• Tables 6 and 7 cover ML-1M with click reward under patience settings (1, 2) and (0.4, 2), respectively.Both tables use displayed slate sizes {4, 5}.Source: Table 6 · p. 43, Table 7 · p. 43
• Tables 8 and 9 cover ML-1M with like reward under patience settings (1, 2) and (0.4, 2), respectively.Table 8 uses displayed slate sizes {4, 5, 6}; Table 9 uses {4, 5}.Source: Table 8 · p. 44, Table 9 · p. 44