- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The authors study when observations can be shared across actions in reinforcement learning. They propose an algorithm that certifies groups to pool input observations and keeps response and reward estimates separate. They provide regret guarantees. They study a two-policy selection problem and give matching information bounds showing how the cost of unknown sharing depends on the conditional responses.
Critical strengths
- I appreciate the lower-bound results, particularly the finding that the difficulty of exploiting sharing depends on how strongly the inputs affect outcomes.
Critical weaknesses
-
I found the presentation VERY difficult to follow. The paper is jam-packed with notation, technical distinctions, and caveats, and the prose often has a heavily AI-like, formulaic quality. The abstract attempts to cover several contributions and a substantial complexity formula before the reader has developed much intuition. The main guarantees require unpacking several auxiliary definitions. Together, these issues interfere substantially with comprehension.
-
The setting feels a bit contrived, and I am not convinced that the motivating examples establish a compelling practical use case. The exact-sharing control guarantee assumes a known separation margin. I know that the authors provide some fallbacks, but the usefulness of these fallbacks are not particularly demonstrated experimentally. It remains unclear how a useful, valid margin would be available in practice.
-
I am not convinced that the benefits justify the additional complexity compared with simpler approaches. The experiments show mixed results. The proposed method sometimes improves performance and sometimes makes it worse. The hybrid provides no additional benefit over the model-based method in the reported runs, and confidence intersection adds computation without a consistent improvement. These results leave the practical motivation for the additional machinery unclear. Comparisons with strong, simpler RL baselines would help.
-
The strongest matching information result concerns a small two-policy construction. Although this is informative theoretically, its implications for the general control algorithm are not very clear. I would like a clearer explanation of which costs of the proposed procedure are unavoidable and which arise from its particular certification and estimation design.
Questions for authors
-
Can the authors clarify how a valid separation margin could be obtained before learning in a practical application? Can the authors demonstrate useful sharing without this information, using their approximate-pooling procedure?
-
In what concrete regimes do the benefits of discovering sharing outweigh its sampling and computational costs? Could the authors compare against strong, simpler baselines, including conventional tabular RL methods, under comparable observation and computation budgets?
-
How do the sharp two-policy information bounds inform the design or efficiency of the general control algorithm? Could good control require less certification than recovering the full sharing partition?
-
Why is it necessary to discard all certification data, including conditional-response and reward observations, when those estimates are not pooled according to the selected input groups? Could retaining these observations reduce the cost of restarting estimation?
4 comments
Weakness 3
I am not convinced that the benefits justify the additional complexity compared with simpler approaches. The experiments show mixed results. The proposed method sometimes improves performance and sometimes makes it worse. The hybrid provides no additional benefit over the model-based method in the reported runs, and confidence intersection adds computation without a consistent improvement. These results leave the practical motivation for the additional machinery unclear. Comparisons with strong, simpler RL baselines would help.
Response: Thank you for these points. We have added comparisons with tabular RL baselines and examined how certification costs and the optional refinements affect performance.
In the earlier experiments, the learned-group method discarded all observations collected during certification and restarted estimation afterward. This restart caused the worse result in the two-law regime of Table 4. The revised Algorithm 1 retains all observations, including those collected during certification (p. 6, Algorithm 1, line 2), and Theorem 2 covers this version. With retained observations, CRFO improves on individual learning in both regimes with sharing. In the regime without sharing, the certification-cost gate skips certification, and CRFO coincides with individual learning (Appendix H.6, Table 13). The temporal-difference (TD) variant (Appendix D) reduces conditional-response storage from to . The hybrid and confidence intersection each take the smaller of two valid upper bounds, so they can tighten the optimistic estimate.
We have added UCBVI-Hoeffding and Q-learning with UCB-Hoeffding bonuses (Appendix H.6, lines 3991–4096, Table 13, Figure 10b). Neither baseline uses the observed input categories. The results show:
- When many actions share few input laws, exact CRFO attains the lowest regret among all learners that are not given the groups. UCBVI-Hoeffding is ahead early in the one-law regime, and CRFO overtakes it as pooled input estimates accumulate.
- When no input law is shared, UCBVI-Hoeffding attains substantially lower regret than CRFO. Without pooling, our factorized learner carries a separate input-law radius in addition to the conditional-response radius, while UCBVI-Hoeffding uses a single radius per state-action pair.
Weakness 4
The strongest matching information result concerns a small two-policy construction. Although this is informative theoretically, its implications for the general control algorithm are not very clear. I would like a clearer explanation of which costs of the proposed procedure are unavoidable and which arise from its particular certification and estimation design.
Response: Thank you for this question. The two-policy result helps distinguish the information needed for a correct decision from the additional information required by CRFO’s full-partition certification.
-
Which costs are unavoidable? Appendix F gives separate constructions for three information requirements. First, on a fully shared instance, a learner achieving regret on the non-shared alternatives, for , must incur regret (Theorem 39). This requirement applies even if the learner never outputs a partition. Second, exact partition recovery requires samples from each alternative action in the Bernoulli construction of Proposition 40. Third, an unknown response can force regret of at least , even with a single deterministic input law shared by all actions (Eq. (86)). These constructions explain why discovering sharing and learning responses require separate accounting.
-
CRFO’s design: CRFO’s exact-certification branch recovers the complete partition before pooling, samples actions in round-robin cycles, and bounds certification regret by per episode. Together, these choices give the upper bound . The certification lower bound establishes the inverse-square sampling dependence for exact recovery. Similarly, the separate input and response confidence bounds contribute to the dimensional dependence of Theorem 2, which the lower bounds do not fully match.
-
Theorem 5: Selecting between two policies requires determining which has higher value, and this can be possible before establishing exact input-law equality. For fixed reference parameters and , the pointwise optimal decision cost in Theorem 5 is independent of , while exact partition recovery still requires order samples. For CRFO, this motivates certification based on whether the remaining input uncertainty can change a value comparison, and explains a concrete source of conservatism in its current full-partition test.
Question 1
Can the authors clarify how a valid separation margin could be obtained before learning in a practical application? Can the authors demonstrate useful sharing without this information, using their approximate-pooling procedure?
Response: Thank you for these questions. A valid margin can be obtained before learning in two ways. In many applications, it follows from the physical structure that creates the sharing. In the downlink example, beams in different clusters follow physically different propagation paths, such as line of sight and reflection, so their rate-class distributions are separated by a gap that can be bounded from the link budget or from measurement logs of previous deployments. Since the margin only needs to be a lower bound on the nonzero total-variation distances between input laws, a conservative estimate is enough, and any smaller value is also valid. If the bound is so small that certification becomes too expensive, the gate in Section 4.1 skips certification and Theorem 2 still gives the individual-learning guarantee (lines 257–261). We tested approximate pooling without a margin (Appendix H.6, Tables 13–14, Figure 10a). Its performance remains close to individual learning, with final regret 1.1%–8.7% higher across the tested regimes and certification budgets.
Question 2
In what concrete regimes do the benefits of discovering sharing outweigh its sampling and computational costs? Could the authors compare against strong, simpler baselines, including conventional tabular RL methods, under comparable observation and computation budgets?
Response: Thank you for these questions. For our exact-certification procedure, the favorable regime combines many actions sharing few input laws, a valid margin large enough to make certification affordable, and enough learning episodes to amortize its cost. Pooling reduces only the input-estimation term, so its benefit is most substantial when input estimation contributes appreciably to the total learning cost. Certification becomes more expensive as decreases, with its sampling budget scaling as . The gate in Section 4.1 limits this expenditure relative to the individual-learning bound.
We added comparisons with UCBVI-Hoeffding and Q-learning with UCB-Hoeffding bonuses in Appendix H.6 (Table 13, Figure 10b). All methods use the same environment, an episode budget of . With eight actions sharing one or two input laws, exact CRFO achieves the lowest final regret among methods not given the groups, reducing regret relative to UCBVI-Hoeffding by 39.5% and 29.8%, respectively.
Question 3
How do the sharp two-policy information bounds inform the design or efficiency of the general control algorithm? Could good control require less certification than recovering the full sharing partition?
Response: Theorem 5 demonstrates this distinction in the two-policy setting. The pointwise optimal expected sample cost over uniformly correct procedures is , where . For fixed reference parameters and , this cost does not increase as decreases. By comparison, exact partition recovery in the Bernoulli construction of Proposition 40 requires samples from each alternative action.
The reason is that policy selection only needs to resolve input uncertainty that could change the preferred policy. At a fixed nominal state and continuation value , substituting one input law for another changes the continuation prediction by . Its importance therefore depends on how the response translates input differences into value differences. This suggests adapting certification to the value comparisons needed for control. Lemma 6 gives a concrete mechanism in the two-policy setting: it bounds the policy-gap estimation error, including the interaction between input and response errors. Once the resulting confidence interval excludes zero, the learner can select the better policy without recovering the partition. CRFO’s exact-certification branch instead recovers the full partition, allowing input reuse across nominal states and continuation values.
Question 4
Why is it necessary to discard all certification data, including conditional-response and reward observations, when those estimates are not pooled according to the selected input groups? Could retaining these observations reduce the cost of restarting estimation?
Response: Thank you for this suggestion. Discarding conditional-response and reward observations is unnecessary. The revised Algorithm 1 initializes their statistics using observations collected during certification, rather than restarting from zero (p. 6, line 273).
I thank the authors for their thoughtful responses and revisions. I agree that the revisions have made the work better. However, I still lean towards keeping my score. I would have increased my score if the scoring rubric was more fine-grained, but I feel that a jump from 2 to 3 is too big, and that the work still feels closer to a 2 for me.
Weakness 1
Response: Thank you for this frank assessment. We have rewritten most of the paper, and all revisions are highlighted in blue. The main changes are as follows.
Abstract. It now states the learning problem, the mechanism of CRFO, and the two main results in plain terms, without the complexity formula or the secondary extensions (p. 1, lines 011–027).
Introduction. We rewrote the opening of the introduction to state the problem directly, and illustrated it with a simpler dual-interface downlink queueing example (pp. 1–2, Figure 1, line 031-072).
Model, warm-up, and algorithm. Each definition is now introduced with its role in the example, and we removed caveats that did not affect the results (Sections 2–4).
Guarantees. Section 5 now states the leading costs of each theorem before the auxiliary quantities needed for the full bounds, and explains each theorem in words before stating it.
Notation. Table 1 (p. 17), at the beginning of the appendices, collects the main notation and its definitions.
Weakness 2
Response: Thank you for raising these points. We have clarified the motivating example and added experiments that directly test the fallbacks.
Motivating example. We have replaced the earlier motivation with a simplified dual-interface downlink example (pp. 1–2, lines 043–072, Figure 1). Sub-6 GHz service changes the backlog in a known way, the base station then measures a rate category on the selected mmWave beam, and packet delivery and arrivals determine the next backlog through an unknown conditional distribution. In this illustrative model, beams within a propagation cluster are assumed to share a rate-category distribution, while the beam-to-cluster assignment is unknown. Appendix B.5 (pp. 28–32, lines 1464–1720) specifies the observations and modeling assumptions required for this and the other examples.
How a valid margin can be obtained. The margin must be a positive lower bound on the nonzero total-variation distances between input laws. Such a bound can be supplied when domain knowledge restricts the input laws to separated admissible regimes—for example, a finite family of calibrated rate-category laws with an established minimum separation. Previous deployment logs can inform this calibration under assumptions that remain applicable to the current deployment. In the constructed instance of Appendix B.5.1, the minimum nonzero distance is 0.4, so any 0<γ≤0.4 is valid (lines 1491–1493). Choosing a smaller valid margin preserves the guarantee but increases the certification budget. If certification becomes too expensive, the gate skips it (Section 4.1, lines 257–261), retaining the high-probability individual-learning bound RegMB(K)≤minHK,FMBA. Appendix H.3.2 confirms this behavior for the smaller valid margins tested: the gate skipped certification on every seed, and the learner coincided with individual learning (lines 3607–3614).
Fallbacks without a margin. Approximate certification (Lemma 18; Appendix G.3) requires no margin. It assigns each group a certified diameter, includes that allowance in the pooled confidence radius, and retains individual estimates as planning candidates. We added experiments testing this fallback directly (Appendix H.6, Tables 13–14, Figure 10). At K=100,000, its final regret was 1.1%–8.7% above individual learning across the tested regimes and test lengths.