- Rating
- 3
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies reinforcement learning with abstention, where an agent can terminate the current episode and receive a one-time, state-dependent fallback reward. This introduces a trade-off between continuing to interact with the environment and stopping to collect the fallback reward. The authors propose UCBVI-AG, an upper confidence bound algorithm whose regret guarantees can improve over the standard UCBVI-CH bound when abstention substantially reduces interactions. They establish regret upper and lower bounds that characterize the roles of the optimal effective horizon and the minimum suboptimality gap. They also provide detailed examples illustrating when abstention yields improved guarantees and when the bounds recover the standard full-horizon baseline.
Critical strengths
The paper is well organized and clearly presented. The theoretical results appear sound, and the findings are reasonable in light of existing work.
Critical weaknesses
RL with abstention can be formulated as an augmented MDP with an additional action leading to an absorbing state, making UCBVI-AG a relatively direct adaptation of standard optimistic planning. Its regret improvement requires a short effective horizon and a sufficiently large episode budget; otherwise, the guarantee recovers the UCBVI-CH baseline. These conditions limit the scope and significance of the improvement.
Although I have not checked every proof, the interaction-dependent analysis appears to rely largely on standard UCBVI arguments, with the treatment of early termination providing an additional analytical contribution.
Questions for authors
Examples 1 and 2 illustrate simple boundary cases, while Example 3 and its extension retain a specific transition and reward structure. Could the authors provide a more general family of examples, or tabular experiments with abstention, to demonstrate benefits across more diverse settings?
4 comments
Response to Reviewer ttgA (Part 2/2)
A2 (continued):
Across all three environments, both AG variants achieve lower mean cumulative regret than their corresponding no-abstention baselines with the same exploration bonus. Bernstein-AG also achieves lower mean cumulative regret than Hoeffding-AG in all three evaluated settings.
The interaction-length results further illustrate the effect of abstention. As shown below, the average number of interactions per episode for each AG variant over the final measurement interval closely matches the optimal effective interaction length in all three environments.
| Quantity | Synthetic | RiverSwim | CliffWalking |
|---|---|---|---|
| Optimal effective interaction length | |||
| Hoeffding-AG interactions per episode (final interval) | |||
| Bernstein-AG interactions per episode (final interval) |
Figures 3 and 4 in Appendix H of the revised manuscript provide the full learning curves for all four methods, showing interaction usage and cumulative regret, respectively. Full experimental settings and additional results are also provided in Appendix H.
Together, these experiments complement the theoretical examples by providing evidence of reduced regret under the stated comparators and interaction savings beyond Examples 1–3.
References
[1] Alexander L. Strehl and Michael L. Littman. An analysis of model-based Interval Estimation for Markov Decision Processes. Journal of Computer and System Sciences, 74(8):1309–1331, 2008.
[2] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. Second edition. MIT Press, 2018.
Finally, we thank the reviewer again for the helpful comments and suggestions for our work. We are more than happy to address any further questions that you may have during the discussion period.
I thank the authors for their detailed response and maintain my positive score.
We are glad to see the concerns have been resolved. Thank you so much for your prompt reply and active engagement during the review process!
Response to Reviewer ttgA (Part 1/2)
We thank Reviewer ttgA for careful review and constructive feedback. We address your questions below and have uploaded a revised manuscript for your reference, with the changes in blue.
A1: Thank you for these comments. We agree that abstention can be represented as an action leading to an absorbing state and that UCBVI-AG builds on standard optimistic planning. Our contribution is not the abstention setting itself, but an interaction-aware characterization of when and how the known abstention structure yields sharper regret guarantees. Both the transitions and payoff associated with abstention are known to the learner. Although this structure is preserved by the reduction, directly applying generic full-horizon UCBVI guarantees does not reveal how regret adapts to the number of real interactions.
To characterize this benefit, we first connect the regret bounds to the number of interaction Nint and then introduce two intrinsic complexity measures: the effective horizon length d⋆ and the excess-interaction suboptimality gap γlen. By controlling these excess interactions through their associated value losses, our analysis relates the learner-dependent interaction count Nint to these structural quantities. This connection is not obtained simply by invoking a generic full-horizon regret theorem.
Specifically, our revised Bernstein analysis yields
\min\\{ H\sqrt{SAKd^\star} +\frac{SAH^3}{\gamma_{\mathrm{len}}}, \sqrt{H^3SAK} \\} +S^2AH^3 ).$$ When $d^\star\ll H$ and $K$ is sufficiently large for the additive terms to be lower order, the interaction-aware leading term is $\sqrt{d^\star/H}$ times the generic full-horizon term. Thus, the improvement can be substantial. Beyond the upper bound, we establish **two lower bounds** that substantiate the relevance of these structural quantities to the difficulty of learning with abstention. In particular, the $d^\star$-dependent upper and lower bounds match up to logarithmic factors. **Our contribution therefore goes beyond adapting optimistic planning to early termination: we identify structural measures of interaction complexity and establishes upper and lower bounds that explain their role in learning with abstention.** > **Q2:** Could more general examples or tabular experiments demonstrate the benefits of abstention beyond the specific structures in Examples 1–3? **A2:** Thank you for this suggestion. Examples 1–3 were chosen for their easy interpretability. In particular, the simple transition and reward structure in Example 3 makes clear how abstention reduces unnecessary interactions and allows its benefits to be characterized explicitly. These illustrative choices do not restrict our general analysis. More generally, our analysis applies to any augmented MDP with a small effective interaction length $d^\star\ll H$ and an excess-interaction suboptimality gap $\gamma_{\mathrm{len}}$ bounded away from zero. For sufficiently large $K$, these conditions yield an improved regret guarantee relative to the generic full-horizon bound, without requiring a particular transition structure, a two-phase reward schedule, or a deterministic cutoff for abstention. **Following your suggestion, we have added experiments on Synthetic, RiverSwim, and CliffWalking in Appendix H.** We also include the Bernstein variant developed during this revision, alongside the original Hoeffding variant. The synthetic tabular MDP has a short effective interaction length, while RiverSwim [1] and CliffWalking [2] are adapted from previously established tabular RL environments by introducing an abstention option. The table below reports cumulative regret at the end of training. Entries are means $\pm$ sample standard deviations across random seeds. For each method, regret is measured against the optimal policy in its corresponding decision problem: the augmented MDP for AG methods and the original MDP for no-abstention baselines. | Method | Synthetic | RiverSwim | CliffWalking | | :--- | ---: | ---: | ---: | | Hoeffding—NoAbstention | $159{,}523.7 (\pm 497.9)$ | $5{,}724{,}701.9 (\pm 2{,}570.2)$ | $220{,}869.3 (\pm 100.5)$ | | Hoeffding-AG | $93{,}833.5 (\pm 178.1)$ | $466{,}283.1 (\pm 2{,}489.6)$ | $195{,}597.9 (\pm 35.5)$ | | Bernstein—NoAbstention | $32{,}010.0 (\pm 508.7)$ | $724{,}006.4 (\pm 612.3)$ | $168{,}774.5 (\pm 140.8)$ | | Bernstein-AG | $\boldsymbol{23{,}811.6} (\pm 228.1)$ | $\boldsymbol{338{,}724.3} (\pm 1{,}394.3)$ | $\boldsymbol{165{,}295.9} (\pm 244.8)$ |