acceptodds
Under review as a conference paper at ICLR 2027

The Price of Cross-Action Sharing: Regret Bounds and Information Limits in RL

Abstract

Observed environmental inputs can support cross-action reuse in reinforcement learning (RL), but an input sample alone does not reveal unexecuted outcomes when conditional responses are unknown. Which observations can then be pooled, and what does validating their reuse cost? We study finite episodic Markov decision processes with unknown input-sharing groups, conditional transition kernels, and reward means. A response-mediated transfer characterization distinguishes equal input laws from equal induced transitions and quantifies the bilinear interaction between input and response estimation errors. Certified Response-First Optimism (CRFO) separates group certification from estimation, retains individual estimates, and bounds conditional continuation values before averaging input laws. This ordering charges response uncertainty to executed transitions. Its separation-dependent, high-probability regret bound is at most twice the smaller of the complete individual-learning and certification-plus-pooling bounds, including identification, response, and reward costs. Targetwise confidence intersection can tighten jointly valid upper estimates without changing the proved regret order. A streaming temporal-difference extension reduces conditional-response storage through a distinct historical-target analysis. For two-policy selection with known reward formulas, matching information bounds reveal a sharper distinction. At a shared reference, let scale cancellation, be the common successor-mean gap, and the response contrast, so the policy gap is . Under uniform correctness over models admitting unequal input laws without positive separation, the pointwise optimal expected episode count is , versus when input-law equality is known, where is the error probability. A product-aware stopping rule attains these orders with reference-tuned initialization and adapts to unknown resolution with an explicit iterated-logarithmic overhead. At a fixed successor gap, vanishing response contrast changes the small-cancellation cost from inverse-square to inverse-first-power because the sharing-induced alternative requires joint input–response perturbations. Thus, neither group count nor policy-gap size alone determines sharing cost.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning theory, structured Markov decision processes, cross-action sharing, regret analysis, sample complexity

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_tioZOpenReview ↗
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
  1. 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
  1. 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.

  2. 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.

  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.

  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.

Questions for authors
  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?

  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?

  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?

  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?

4 comments

Weakness 1

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.

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.

  1. 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).

  2. 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).

  3. 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).

  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.

  5. Notation. Table 1 (p. 17), at the beginning of the appendices, collects the main notation and its definitions.

Weakness 2

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.

Response: Thank you for raising these points. We have clarified the motivating example and added experiments that directly test the fallbacks.

  1. 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.

  2. 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.40.4, so any 0<γ≤0.40<\gamma\le0.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 Reg⁡MB(K)≤min⁡HK,FMBA\operatorname{Reg}_{\mathrm{MB}}(K)\le\min\\{HK,F_{\mathrm{MB}}^A\\}. 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).

  3. 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,000K=100{,}000, its final regret was 1.1%–8.7% above individual learning across the tested regimes and test lengths.

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 O(HZCS)O(HZCS) to O(HZC)O(HZC). 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.

  1. Which costs are unavoidable? Appendix F gives separate constructions for three information requirements. First, on a fully shared instance, a learner achieving O(Kα)O(K^\alpha) regret on the non-shared alternatives, for α<1\alpha<1, must incur Ω((A−1)log⁡K/Δ)\Omega((A-1)\log K/\Delta) regret (Theorem 39). This requirement applies even if the learner never outputs a partition. Second, exact partition recovery requires Ω(γ−2log⁡(1/δ))\Omega(\gamma^{-2}\log(1/\delta)) samples from each alternative action in the Bernoulli construction of Proposition 40. Third, an unknown response can force regret of at least (H−1)AK/32(H-1)\sqrt{AK}/32, 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.

  2. 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 HH per episode. Together, these choices give the upper bound HAnγHAn_\gamma. 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.

  3. 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 0<γ<min⁡Δ,r∗0<\gamma<\min{\Delta,r_*}, the pointwise optimal decision cost in Theorem 5 is independent of γ\gamma, while exact partition recovery still requires order γ−2\gamma^{-2} 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 γ\gamma decreases, with its sampling budget scaling as γ−2\gamma^{-2}. 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 K=100,000K=100{,}000. 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 Θ(s\*−2log⁡(1/δ))\Theta(s_\*^{-2}\log(1/\delta)), where s\*=min⁡Δ,max⁡γ,r\*s_\*=\min\\{\Delta,\max\\{\gamma,r_\*\\}\\}. For fixed reference parameters and 0<γ<min⁡Δ,r\*0 < \gamma < \min\\{\Delta,r_\*\\}, this cost does not increase as γ\gamma decreases. By comparison, exact partition recovery in the Bernoulli construction of Proposition 40 requires Ω(γ−2log⁡(1/δ))\Omega(\gamma^{-2}\log(1/\delta)) 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 zz and continuation value VV, substituting one input law for another changes the continuation prediction by (μh,b−μh,a)⊤(PhV)(z,⋅)(\mu_{h,b}-\mu_{h,a})^\top(P_hV)(z,\cdot). 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.

Reviewer_8UYWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies when sharing information across actions helps finite episodic reinforcement learning. Its model separates an action-specific distribution over observed input signatures from an unknown conditional response kernel, using a known nominal-state map. Actions with equal input laws can share input-frequency estimates. Such equality alone does not provide unobserved successors or justify reward pooling.

The principal contributions are:

• Discovery-aware control. Certified Response-First Optimism (CRFO) identifies valid sharing groups under a supplied separation promise, then learns from fresh samples. Its regret analysis accounts separately for discovery, input estimation, conditional-response estimation, and unknown rewards.

• Response-sensitive information limits. For identifying the better of two prescribed policies, Theorem 5 gives matching pointwise expected sample-complexity orders. The cost depends on how input-law differences interact with the response, with distinct first-order and second-order regimes. The flat- response case remains nontrivial because flatness is not supplied to the learner.

• Transfer and estimation refinements. The paper derives a bilinear transfer certificate, studies inter- sections of individual and pooled confidence sets, and develops a TD variant with smaller response memory. These clarify when pooling changes a valid backup and what information still requires direct observation.

Critical strengths

See the above contributions.

Critical weaknesses
  • The control bound is conservative and is not matched by a lower bound across all model parameters. The sharp information result concerns two prescribed policies in a restricted family. Its matching orders are pointwise infima over uniformly correct procedures; the single scale-agnostic procedure has an additional iterated-logarithm factor (Theorems 2 and 5; Appendices E-F).
  • Response-aware sharing gap. Proposition 1 and Appendix B.2 recognize that unequal input laws can induce identical transitions through response cancellation. CRFO nevertheless certifies input-law equality (or bounded input TV), not this broader response-dependent equivalence.
Questions for authors
  1. Lemma 41 needs equality of reward/additional-mark kernels conditional on the full realized history, or an explicit common Markov kernel conditioned on the observed transition tuple. Equality of tuple-conditioned marginal laws alone is insufficient under the paper's history-dependent reward model.

  2. The discussion omits Asadi et al., Model-Based Reinforcement Learning Exploiting State-Action Equivalence (ACML 2019) [1]. Its equivalence learning and confidence pooling are directly relevant.

3 comments

Thank you for the careful review and helpful comments. We address your concerns below.

Weakness 1

The control bound is conservative and is not matched by a lower bound across all model parameters. The sharp information result concerns two prescribed policies in a restricted family. Its matching orders are pointwise infima over uniformly correct procedures; the single scale-agnostic procedure has an additional iterated-logarithm factor (Theorems 2 and 5; Appendices E–F).

Response:

  1. Control bound. Theorem 2 does not establish minimax-optimal control regret. Its guarantee is a comparison: under a known separation margin, CRFO's total regret bound is at most twice the smaller of the complete individual-learning and certification-plus-pooling bounds, including certification costs. Appendix F provides separate constructions showing that discovering sharing, exact certification, and response learning can incur unavoidable costs (Theorem 39, Proposition 40, and Eq. (86)). These results support accounting for these costs separately.

  2. Restricted two-policy family. We use two prescribed policies to isolate the cost of unknown sharing from the difficulty of policy search. We ask how much extra information a learner needs when input-law equality holds but is not known. For γ=0\gamma=0 and fixed Δ\Delta and δ\delta, Theorem 5 gives pointwise optimal costs of order ε−1\varepsilon^{-1} when κ=0\kappa=0 and ε−2\varepsilon^{-2} when κ>0\kappa>0 is fixed, although the policy gap is εΔ\varepsilon\Delta in both cases. Knowing input-law equality removes this dependence on ε\varepsilon. Thus, the policy gap and model dimensions alone do not determine the cost of unknown sharing. The result also explains why full certification can be conservative. For fixed reference parameters and 0<γ<min⁡Δ,r\*0 < \gamma < \min\\{\Delta,r_\*\\}, the decision cost Θ(s\*−2log⁡(1/δ))\Theta(s_\*^{-2}\log(1/\delta)) remains constant as γ\gamma decreases, while exact partition recovery in Proposition 40 retains an inverse-square dependence on γ\gamma. Within this family, selecting the better policy can therefore require less information than recovering the full partition.

  3. Pointwise infima and the iterated logarithm : The lower bound applies to every uniformly correct procedure at the reference instance. For the matching upper bound, every fixed initialization n0n_0 defines a uniformly correct procedure, but the choice n0=⌈s∗−2⌉n_0=\lceil s_*^{-2}\rceil that achieves the matching order depends on the reference instance (Lemma 38). This dependence affects efficiency, not the validity of the correctness guarantee. The single scale-agnostic rule uses n0=1n_0=1 and satisfies ET≤228s∗−2[log⁡(32/δ)+2log⁡(2+log⁡2(s∗−2))]\mathbb E T\le 2^{28}s_*^{-2}[\log(32/\delta)+2\log(2+\log_2(s_*^{-2}))] (Eq. (82)). It therefore provides adaptation with an additional iterated-logarithmic term.

Weakness 2

Response-aware sharing gap. Proposition 1 and Appendix B.2 recognize that unequal input laws can induce identical transitions through response cancellation. CRFO nevertheless certifies input-law equality (or bounded input TV), not this broader response-dependent equivalence.

Response:

CRFO uses input-law certificates because they support reuse across nominal states before the conditional responses are accurately estimated. Proposition 1 explains both the value of this choice and the additional opportunities offered by response information.

With d=μh,b−μh,ad=\mu_{h,b}-\mu_{h,a}, two input laws induce the same successor law at zz exactly when d⊤Pz=0d^\top P_z=0. This can hold at one nominal state and fail at another. A certificate based on this cancellation therefore needs information about the relevant responses. In contrast, input-law equality supports reuse of signature observations across nominal states, including those whose responses have not yet been observed. The conditional responses at those states still require their own observations.

Proposition 1 gives Dz(a,b)≤χ(Pz)TV⁡(μh,a,μh,b)\mathsf D_z(a,b)\le\chi(P_z)\operatorname{TV}(\mu_{h,a},\mu_{h,b}) and, for S≥2S\ge2, sup⁡PzDz(a,b)=TV⁡(μh,a,μh,b)\sup_{P_z}\mathsf D_z(a,b)=\operatorname{TV}(\mu_{h,a},\mu_{h,b}), where the supremum ranges over unrestricted response kernels. Thus, input-law equality is necessary and sufficient for zero transfer bias uniformly over these kernels. A bounded input-TV certificate similarly controls transfer without requiring response-specific information.

Proposition 1 bounds the difference between true and estimated transfer using input estimation error, response estimation error, and their interaction. Its bound includes 2eμmax⁡cecPspan⁡(v)2e_\mu\max_c e_c^P\operatorname{span}(v), where eμe_\mu combines the two input-law error bounds and ecPe_c^P bounds the error of response row cc. Appendix B.4 gives an example where the empirical transfer and both first-order terms vanish, but the true transfer remains nonzero. This explains why estimated cancellation requires uncertainty control.

Question 1

Lemma 41 needs equality of reward/additional-mark kernels conditional on the full realized history, or an explicit common Markov kernel conditioned on the observed transition tuple. Equality of tuple-conditioned marginal laws alone is insufficient under the paper's history-dependent reward model.

Response: Thank you for pointing this out. We have corrected Lemma 41 and its proof in Appendix F.1. Let η\eta denote the full pre-feedback history, including the chosen action, and let WW collect the reward and all additional observed marks, including the raw input when it differs from the category. We now require a common kernel Qk,h(dw∣η,c,s′)Q_{k,h}(dw\mid\eta,c,s') that is a version of the joint conditional law of WW under both models. Conditional on η\eta, the complete feedback law under the first model factors as μh,a(c),Ph(s′∣ϕh(s,a),c),Qk,h(dw∣η,c,s′).\mu_{h,a}(c),P_h(s'\mid\phi_h(s,a),c),Q_{k,h}(dw\mid\eta,c,s'). The second model has its own input and response factors and the same Qk,hQ_{k,h}. This common kernel contributes zero conditional KL. Applying the conditional KL chain rule and summing over actual observations gives Eq. (87).

Question 2

The discussion omits Asadi et al., Model-Based Reinforcement Learning Exploiting State-Action Equivalence (ACML 2019). Its equivalence learning and confidence pooling are directly relevant.

Response: Thank you for this reference. We now discuss Asadi et al. (2019) in the introduction (p. 2, lines 079–080) and in Appendix A.3 (lines 997–1004).

Reviewer_8UYWOpenReview ↗

Response to the authors

I would like to thank the authors for the detailed response, which addressed my concerns. The cross-action sharing is interesting, and I will maintain my positive rating.

Reviewer_fVurOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies reinforcement learning by decomposing state transitions into two components: an observed environmental input drawn from an action-dependent distribution, and a subsequent transition governed by an unknown conditional response kernel. The learner estimates both components while identifying actions whose input distributions are the same, allowing their input observations to be pooled so that the estimation error can be reduced. The paper proposed a new CRFO algorithm, by combining certified pooling with response-first optimistic planning. The paper establishes regret bounds that account separately for input estimation, response learning, and sharing identification. A complementary two-policy selection analysis characterizes the information cost of unknown sharing and shows how this cost depends on the sensitivity of conditional responses to the inputs.

Critical strengths

The paper studies a new setting in reinforcement learning and establishes solid theoretical guarantees. The idea of decomposing the transition based on shared information and the cost of unknown sharing structure is interesting.

Critical weaknesses
  • The paper analyzes a complicated variant of reinforcement learning problems. The motivation is still not very clear to me. In practice, it is not always clear where this decomposition comes from.
  • The key result --- regret analysis based on certified sharing --- depends crucially on the separation assumption, and it also requires the knowledge about the separation constant. This seems to be a fundamental limitation of the unknown sharing structure setting, but this limits the practical applicability of the result.
  • The paper motivates the setup using examples from queuing theory. I am not an expert in the area of queuing, but it seems that these problem might have specialized solving strategies, instead of trying to fit them into the MDP framework and viewing them as instances of a complicated variant of the RL.
Questions for authors

It would be helpful to provide more insights into the motivation of the framework. Additionally, the authors may want to clarify the dependence on the separation assumption and knowledge about the separation gap.

3 comments

Thank you for the careful review and helpful suggestions. We address your concerns below.

Weakness 1

The paper analyzes a complicated variant of reinforcement learning problems. The motivation is still not very clear to me. In practice, it is not always clear where this decomposition comes from.

Response: We have revised the introduction to explain our model through a dual-interface downlink scheduling example (pp. 1–2, lines 043–072, highlighted in blue; Figure 1). A base station serves buffered packets over sub-6 GHz and millimeter-wave links. We model the sub-6 GHz link as reliable within a known capacity, so serving packets on it leaves a known remaining backlog. Before transmitting over the millimeter-wave link, the base station obtains a reference-signal measurement on the selected beam and records its rate category. The category distribution depends on the beam and must be learned. Given the remaining backlog and rate category, packet delivery and new arrivals determine the next backlog through an unknown conditional distribution. This gives the three components of our model: a known buffer update, an observed input, and an unknown conditional response. We have also added an unmanned aerial vehicle (UAV) motion example in Appendix B.5.2 (pp. 28–29, lines 1561–1615). Here, a known kinematic model predicts the nominal motion, a sensor measures airflow, and the learner must estimate how that airflow affects the actual motion. Appendix B.5 explains the observations and assumptions needed for these examples to fit our model.

Weakness 2

The key result --- regret analysis based on certified sharing --- depends crucially on the separation assumption, and it also requires the knowledge about the separation constant. This seems to be a fundamental limitation of the unknown sharing structure setting, but this limits the practical applicability of the result.

Response: We agree that a known separation margin is additional information that may be unavailable in practice. It is required for our exact-certification procedure, but not for singleton learning or approximate certification. Below, we explain how a valid margin can be justified, what happens when it is small, and what the learner can do when it is unavailable.

  1. How to choose γ\gamma. The margin γ\gamma only needs to be a lower bound on the nonzero total-variation distances between input laws. Any smaller value is also valid, so a conservative choice is safe. In the downlink example, beams in different clusters follow physically different propagation paths, such as line of sight and reflection, whose rate-class distributions differ substantially. Such a bound can come from domain knowledge or from measurement logs of previous deployments. In the constructed instance of Appendix B.5.1, the distinct cluster laws are at least 0.40.4 apart, so any γ≤0.4\gamma\le0.4 is valid.

  2. What happens when γ\gamma is small. The dependence on γ\gamma is explicit in Theorem 2. Certification takes at most AnγAn_\gamma episodes, where nγ=⌈32LC/γ2⌉n_\gamma=\lceil32L_C/\gamma^2\rceil, and incurs regret at most HAnγHAn_\gamma. Equation (11) gives, with probability at least 1−δ1-\delta, $ \operatorname{Reg}_{\mathrm{MB}}(K) \le \min\left\{HK,\;2\min\left\{F_{\mathrm{MB}}^A,\;HAn_\gamma+F_{\mathrm{MB}}^m\right\}\right\}.$ Where FMBAF_{\mathrm{MB}}^A and FMBmF_{\mathrm{MB}}^m are the individual-input and true-group regret bounds. Section 4.1 runs certification only if Anγ<KAn_\gamma<K and HAnγ≤FMBAHAn_\gamma\le F_{\mathrm{MB}}^A. Otherwise , it returns singleton groups immediately. Giving Reg⁡MB(K)≤min⁡HK,FMBA\operatorname{Reg}_{\mathrm{MB}}(K)\le\min\\{HK,F_{\mathrm{MB}}^A\\} without any certification cost. Thus, a small valid margin can disable pooling rather than force an expensive test. Appendix H.3.2 confirms this behavior: with smaller valid margins, the gate skipped certification on every seed, and the learner coincided with individual learning.

  3. What happens when γ\gamma is unknown. The learner can use singleton groups immediately or run approximate certification (Lemma 18 and Appendix G.3). Approximate certification uses a fixed number nan_a of test cycles, with Ana<KAn_a<K, and assigns each returned group a diameter bound ϵh,G\epsilon_{h,G} instead of asserting equality. With valid diameter certificates and simultaneous confidence bounds for the input estimates, the general regret bound is Reg⁡MB(K)≤min⁡HK,;HAna+FMB(G),\operatorname{Reg}_{\mathrm{MB}}(K)\le\min\\{HK,\\;HAn_a+F_{\mathrm{MB}}(\mathfrak{G})\\}, where G\mathfrak G in (9) is the smaller of the individual input-error term and the pooled bound, including the mismatch term KϵhK\epsilon_h. Because the bias-aware radius λh,i=min⁡1,rC(nh,i)+ϵh,i\lambda_{h,i}=\min\\{1,r_C(n_{h,i})+\epsilon_{h,i}\\} keeps the individual stream available, an inaccurate group cannot make the bound worse than individual learning plus the test cost. We have added experiments on this case (Appendix H.6, Table 14, Figure 10).

Weakness 3

The paper motivates the setup using examples from queuing theory. I am not an expert in the area of queuing, but it seems that these problem might have specialized solving strategies, instead of trying to fit them into the MDP framework and viewing them as instances of a complicated variant of the RL.

Response: Specialized queueing methods typically assume that the system statistics are known. When they are unknown, the scheduling problem can becomes an MDP with an unknown transition kernel, and RL is an established approach to queue control in the queueing and networking literature. Liu, Xie, and Modiano [1] develop a model-based RL framework for optimal control of queueing networks with unknown dynamics, covering server allocation, routing, and switching. Dai and Gluzman [2] apply deep RL to multiclass queueing networks and obtain policies that match or outperform the best-known heuristics. Krishnasamy et al. [3] study scheduling with unknown service rates as a bandit problem and show that the queue structure changes the cost of learning. Cao, Sun, and Tsang [4] solve the delay-aware dual-interface scheduling problem of Yao et al. [5] by RL when the channel statistics are unknown. Walton and Xu [6] survey learning-based control of stochastic networks and queues, including RL. In wireless scheduling, post-decision-state RL learns buffer control under unknown arrival and channel statistics [7, 8]. We cite [1, 2, 4, 5, 7, 8] in the revised introduction (p. 1, lines 043–046). To make the motivation clearer, we have replaced the data-center admission queue in the introduction with a dual-interface downlink scheduling example (pp. 1–2, Figure 1). The data-center queue now appears in Appendix B.5.2 and remains the environment for the experiments in Appendix H.

References:

[1] B. Liu, Q. Xie, and E. Modiano. RL-QN: A reinforcement learning framework for optimal control of queueing systems. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 2022.

[2] J. G. Dai and M. Gluzman. Queueing network controls via deep reinforcement learning. Stochastic Systems, 2022.

[3] S. Krishnasamy, R. Sen, R. Johari, and S. Shakkottai. Learning unknown service rates in queues: A multiarmed bandit approach. Operations Research, 2021.

[4] Y. Cao, B. Sun, and D. H. K. Tsang. Delay-aware scheduling over mmWave/sub-6 dual interfaces: A reinforcement learning approach. IEEE ICC Workshops, 2020.

[5] G. Yao, M. Hashemi, and N. B. Shroff. Integrating sub-6 GHz and millimeter wave to combat blockage: Delay-optimal scheduling. WiOpt, 2019.

[6] N. Walton and K. Xu. Learning and information in stochastic networks and queues. INFORMS TutORials in Operations Research, 2021.

[7] N. Sharma, N. Mastronarde, and J. Chakareski. Accelerated structure-aware reinforcement learning for delay-sensitive energy harvesting wireless sensors. IEEE Transactions on Signal Processing, 2020.

[8] N. Mastronarde, N. Sharma, and J. Chakareski. Improving data-driven reinforcement learning in wireless IoT systems using domain knowledge. IEEE Communications Magazine, 2021.

Question 1

It would be helpful to provide more insights into the motivation of the framework. Additionally, the authors may want to clarify the dependence on the separation assumption and knowledge about the separation gap.

Response: We have revised the introduction around the downlink example and added the UAV example in Appendix B.5.3. Our responses to Weaknesses 1 and 3 explain where the decomposition comes from and why a learning formulation is needed. Our response to Weakness 2 explains how γ\gamma can be chosen, what happens when it is small, and how the method operates without it.

Thanks for the detailed response. The response addressed my comments about motivation etc, but the key theoretical question (gap-dependence) remains (which is critically, and does not admit an easy fix). I think this is a borderline paper, and I will consider my rating more carefully in the next phase.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.