acceptodds
Under review as a conference paper at ICLR 2027

Almost Tight Regret Bounds for Reinforcement Learning with Abstention

Abstract

We study reinforcement learning (RL) with abstention, where an agent in a finite-horizon Markov decision process (MDP) may terminate an episode at any time and receive a fallback reward. We formulate this setting as an augmented MDP and propose an optimism-based algorithm that incorporates abstention into both value iteration and policy execution. We establish an interaction-dependent regret upper bound whose leading term depends on the realized number of interactions rather than the full decision budget , yielding a potentially sharper upper bound when abstention reduces interactions. To further characterize the MDPs in which such improvements occur, we introduce the optimal effective horizon length and the minimum sub-optimality gap over base actions. Our analysis shows that a shorter effective horizon can reduce regret, whereas a smaller gap increases the exploration cost. These effects are further illustrated through three concrete examples, including the boundary cases in which abstention is never beneficial or is uniformly optimal, as well as an intermediate setting in which the benefit of abstention varies with the problem parameters. Finally, complementary regret lower bounds show that dependence on and is unavoidable in general, supporting their role in characterizing the intrinsic learning difficulty of RL with abstention.

Primary area:
learning theory
Keywords:
Reinforcement learning, Abstention, Regret analysis, Instance-dependent bounds, Lower Bound

Reviews

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

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.

Q1: UCBVI-AG appears to be a direct adaptation of optimistic planning on an augmented MDP. Since its gains require a short effective horizon and sufficiently large KK, how broad and significant is the improvement? What is new in the interaction-dependent analysis beyond standard UCBVI arguments and the treatment of early termination?

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 NintN_\mathrm{int} and then introduce two intrinsic complexity measures: the effective horizon length d⋆d^\star and the excess-interaction suboptimality gap γlen\gamma_{\mathrm{len}}. By controlling these excess interactions through their associated value losses, our analysis relates the learner-dependent interaction count NintN_{\mathrm{int}} 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)$ |
AuthorsOpenReview ↗

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 d⋆d^\star in all three environments.

QuantitySyntheticRiverSwimCliffWalking
Optimal effective interaction length d⋆d^\star2.002.004.444.448.698.69
Hoeffding-AG interactions per episode (final interval)2.002.004.444.448.718.71
Bernstein-AG interactions per episode (final interval)2.002.004.444.448.708.70

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!

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

The paper studies finite-horizon episodic Markov decision processes (MDPs) with an abstention option, where the agent can terminate an episode at any time step and receive a fallback reward that depends on the current state and time step.

The authors propose a variant of UCBVI that incorporates the abstention option into the optimistic value function estimates.

The authors establish an instance-dependent upper bound for the proposed algorithm and a corresponding lower bound for the problem. The instance-dependent parameters include the expected number of interactions under an optimal policy and the minimum suboptimality gap.

Critical strengths
  • The problem setting is novel, and the paper is clearly written and well organized.
  • The theoretical analysis is generally well developed, providing both upper and lower bounds.
Critical weaknesses

A major concern is that the proposed setting may admit a straightforward reduction to a standard tabular MDP, potentially limiting the novelty and significance of the contributions. Whether this reduction preserves the relevant theoretical guarantees needs to be clarified by the authors during the rebuttal.

Questions for authors
  1. Reduction to a standard MDP. It seems that an MDP with abstention can be reduced to a standard finite-horizon MDP by augmenting the state space with an additional absorbing state. Specifically, one could introduce an abstention action that provides the corresponding state- and time-dependent fallback reward and transitions to the absorbing state. The resulting problem would then be a standard tabular MDP, for which extensive theoretical results already exist. Given this reduction, could the authors clarify what distinguishes the proposed setting from a standard MDP and which aspects of the theoretical contributions are not already covered by existing results? In particular, does this reduction preserve the instance-dependent complexity measures and the corresponding guarantees?

  2. Horizon dependence and minimax optimality. As mentioned in the paper, the dependence on the horizon could potentially be improved by employing Bernstein-type concentration inequalities. Would such a refinement be sufficient to achieve minimax-optimal regret bounds? If so, could the authors explain why this extension is left for future work? Alternatively, are there additional technical challenges that would prevent this approach from achieving minimax optimality?

3 comments
AuthorsOpenReview ↗

Response to Reviewer TgtL

We thank Reviewer TgtL for the careful review and constructive feedback. We address your questions below and have uploaded a revised manuscript for your reference, with the changes highlighted in blue.

Q1: Since abstention can be represented as an additional action leading to an absorbing state, what contributions go beyond standard tabular MDP results? Does this reduction preserve the instance-dependent complexity measures and guarantees?

A1: Thank you for raising this point. We agree that an MDP with abstention can be represented as an augmented tabular MDP with an absorbing state. Importantly, the abstention action has known transitions and a known payoff, which the learner can exploit. Our contribution is therefore not the new abstention framework itself, but an interaction-aware analysis that exploits this known structure to obtain sharper, instance-dependent regret guarantees.

Intuitively, knowing the transitions and payoff associated with abstention allows the learner to avoid unnecessary interactions once stopping is preferable, which can lead to improved regret guarantees.

The generic regret guarantees for UCBVI-CH and UCBVI-BF are expressed in terms of the full horizon and total number of steps. Hence directly invoking these guarantees does not recover our dependence on NintN_\mathrm{int} d⋆d^\star and γlen\gamma_{\mathrm{len}}.

Specifically, our revised Bernstein analysis, detailed in the response below, yields

\min\\{ H\sqrt{SAKd^\star} +\frac{SAH^3}{\gamma_{\mathrm{len}}}, \sqrt{H^3SAK} \\} +S^2AH^3 ).$$ This bound improves on the generic full-horizon guarantee when $d^\star$ is small relative to $H$ and $K$ is sufficiently large relative to the other problem parameters. It thus quantifies when abstention can reduce the effective interaction burden and lead to a sharper regret guarantee. Beyond the upper bound, we introduce structural measures of interaction complexity $d^\star$ and $\gamma_{\mathrm{len}}$, and establish two lower bounds that demonstrate their relevance to the intrinsic difficulty of learning with abstention. In particular, the $d^\star$-dependent upper and lower bounds match up to logarithmic factors on a common hard family with constant $\gamma_{\mathrm{len}}$ for sufficiently large $K$. **Our contribution is therefore a structural characterization of when abstention improves learning guarantees, supported by upper and lower bounds, rather than merely a reformulation of abstention as an additional action.** > **Q2:** Would a Bernstein refinement improve the horizon dependence enough to achieve minimax-optimal regret? Why was it left for future work, and are there additional technical obstacles? **A2:** We thank the reviewer for this suggestion. We are pleased to share that **we have now completed this extension: Section 8 presents the Bernstein variant algorithm UCBVI-AG-B with regret bounds, and Appendix A provides the proofs**. UCBVI-AG-B has a high-probability interaction-dependent regret bound as $$\mathrm{Reg}(K)=\widetilde O( H\sqrt{SA N_{\mathrm{int}}(K)}+S^2AH^3),$$ whose leading interaction-dependent term is reduced by a factor of $\sqrt H$ compared with UCBVI-AG. The resulting instance-dependent bound is $$\widetilde O( \min\\{H\sqrt{SAKd^\star}+\frac{SAH^3}{\gamma_{\mathrm{len}}}, \sqrt{H^3SAK}\\}+S^2AH^3).$$ Here, we use the refined gap parameter $\gamma_{\mathrm{len}}$ in place of the original $\gamma_{\min}$, focusing on base actions that cause excess interaction. The detailed motivation and definition of $\gamma_{\mathrm{len}}$ can be found in Definition 3 in Section 5 of the revised manuscript and in our response A2 to Reviewer dCSa's Question 2. The Bernstein refinement removes the additional $\sqrt H$ and $H$ factors in the EHL and EISG terms, respectively. These two terms now match the polynomial dependence of the corresponding lower bounds. 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.

Thank you for your response. As the reviewer dCSa raised the similar question, it is essential to include the Bernstein-based sharper analysis to make it clear the contribution of the instance-dependent bound over standard/classic ucbvi analysis after the absorbing state reduction. I maintain my positive score given that the authors have clear path to the revision.

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!

Reviewer_dCSaOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the problem of online learning in MDPs with abstention. The paper frames the abstention problem as a tabular MDP with an extra action, which can terminate the episode at any step h and state s, paying an apriori known cost of G_h(s). The main idea of the paper is to specialize UCB-VI to this setting, with the optimistic value replaced by max(U, G), plus a gate that abstains whenever G ≥ U. The claimed contributions are

-Theorem 1: a regret bound that scales with the number of steps actually taken, NintN_{int}, instead of HK.

-Proposition 1: a bound on NintN_{int} in terms of an optimal effective horizon d∗d^\ast and a minimum base-action gap γmin\gamma_{min}.

-Theorem 2: the resulting instance-dependent bound, O~(minH3/2SAKd∗+SAH4/γmin,H2SAK)\widetilde{O}(min{H^{3/2}\sqrt{SAKd*} + SAH^4/\gamma_{min}, H^2\sqrt{SAK}}).

-Theorems 4 and 5: lower bounds showing that a dependence on γmin\gamma_{min} and on d∗d* is necessary in general.

The authors describe the upper and lower bounds as matching up to factors of H\sqrt{H} and H.

Critical strengths
  1. The abstention MDP is a reasonable model for problems like deferral and early stopping.
  2. Abstention is safe under optimism as the abstention value is known. With G known and U optimistic, the gate only abstains when abstaining is truly optimal. (this is a strength for the analysis, but potentially questionable in reality).
  3. The bounds are rigorous as far as I can tell. Prop 1. seems like a major structural insight for this class of mdps.
Critical weaknesses
  1. I'm not sure the d*-dependent bound improves on existing algorithms. I tried a simple sanity check on the setting of Section 6, where Gh(s)=(H−h+1)⋅rabsG_h(s) = (H − h + 1)·r_{abs}. Here, abstaining seems to be equivalent to moving to an absorbing state that pays rabs∈[0,1]r_{abs} \in [0, 1] at every remaining step. In that case, the abstention problem in Examples 1–3 is just a standard tabular mdp with one extra state and one extra action, and per-step rewards stay in [0,1][0, 1]. Let's look at what UCBVI already gives on this mdp. Table 1 compares against the Hoeffding variant (UCBVI-CH). Azar et al. (2017) give a Bernstein variant (UCBVI-BF) with a better rate. Applying the footnote-1 conversion to time-inhomogeneous transitions to UCBVI-BF, I get O~(H3/2SAK)\widetilde{O}(H^{3/2}\sqrt{SAK}) for large K. This seems consistent with the Ω(H3/2SAK)\Omega(H^{3/2}\sqrt{SAK}) lower bound cited in Remark 1. If this reasoning is correct, the comparison doesn't favor the paper. Theorem 3's leading term on Example 3 is H3/2SAKd∗H^{3/2}\sqrt{SAKd*}, and since d* ≥ 1, it's never smaller than what UCBVI-BF would give. The improvement over Table 1's baseline then seems to come from comparing against the Hoeffding variant, not from the abstention structure. Note that this also doesn't require that the costs are known apriori. Any real gain would seem to require the Bernstein refinement mentioned in Remark 1. I may be missing something about why this reduction or the UCBVI-BF bound doesn't apply here. If so, I'd appreciate it if the authors could explain where their bound improves on UCBVI-BF run on the augmented MDP.

  2. It's unclear whether there's any regime where the Kd∗\sqrt{Kd*} rate is both achieved and necessary. Theorem 2's d* branch only applies when γmin≫H5/2SA/(Kd∗)\gamma_min ≫ H^{5/2}\sqrt{SA/(Kd*)}. In Theorem 5's hard instances, the gaps shrink with K γmin=O(K−1/2)\gamma_{min} = O(K^{−1/2}). On those instances, Theorem 2 falls back to the worst-case H2SAKH^2\sqrt{SAK} bound. So the d* lower bound is proved on a family where the upper bound isn't in its d* regime, and "almost tight" holds term by term rather than on any single family of instances. In the other direction, when γmin\gamma_{min} is bounded away from zero, gap-dependent analyses (Simchowitz & Jamieson 2019; Xu et al. 2021) suggest regret of order SA⋅poly(H)⋅logK/gap on the augmented mdpSA·poly(H)·log K / \text{gap on the augmented mdp}. That would beat the Kd∗\sqrt{Kd*} branch wherever it's active. The one exception is when abstention gaps at reachable states are tiny, which is exactly where knowing G helps. Even there, the minimax comparison in weakness 1 still applies.

Questions for authors

Please comment on the weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer dCSa (Part 1/2)

We thank Reviewer dCSa for the careful review and constructive feedback. We address your questions below and have uploaded a revised manuscript for your reference, with the changes highlighted in blue.

Q1: In Examples 1–3, abstention reduces to a standard augmented MDP, where UCBVI-BF gives O~(H3/2SAK)\widetilde O(H^{3/2}\sqrt{SAK}). Does the proposed bound improve on this Bernstein baseline, rather than only on UCBVI-CH, and is a Bernstein refinement needed?

A1: Thank you for this suggestion. In Table 1 and in Example 3, we took UCBVI-CH as a baseline for fair comparison because our initial submission used a Hoeffding-type bonus. We have now completed a Bernstein variant with abstention to compare with UCBVI-BF. In our revision (change in blue color), Section 8 introduces UCBVI-AG-B, which changes the exploration bonus while preserving the value updates and abstention gate. Theorem 6 proves, with high probability, the regret of UCBVI-AG-B satisfies that

H\sqrt{SA N_{\mathrm{int}}(K)}+S^2AH^3).$$ Theorem 7 then gives the instance-dependent bound $$\mathrm{Reg}(K)=\widetilde O( \min\\{H\sqrt{SAKd^\star}+\frac{SAH^3}{\gamma_{\mathrm{len}}}, \sqrt{H^3SAK}\\}+S^2AH^3).$$ This closes the extra $\sqrt H$ factor in the EHL-dependent term, and $H$ factor in the gap-dependent term (we use the refined gap parameter $\gamma_{\mathrm{len}}$ in place of the original $\gamma_{\min}$, please see our **A2** to you below for details). In Example 3, when the gap-dependent term and the additive remainder are lower order, UCBVI-AG-B has leading regret term $H\sqrt{SAKd^\star}$, compared with $H\sqrt{SAKH}$ for UCBVI-BF. The ratio of these leading terms is $\sqrt{d^\star/H}$. Hence, our new Bernstein based bound improves on UCBVI-BF. > **Q2:** Is there a regime where the $\sqrt{Kd^\star}$ dependence is both achievable and necessary? The original EHL hard family has shrinking gaps, so the upper and lower bounds may not match on the same family. Conversely, could existing logarithmic gap-dependent bounds be sharper when the gap is bounded away from zero? **A2:** Thank you for raising these two points. **(i) Matching upper and lower bounds (Theorem 5) on the same family.** We agree that, in our original construction for lower bound EHL, $\gamma_{\min}=O(K^{-1/2})$, so that the $d^\star$-dependent term in our Theorem 2 bound is not strictly dominant in this hard instance. To address this issue, we refine the gap parameter by observing that **controlling excess interaction only requires the gaps of base actions that increase expected interaction length relative to the longest optimal continuation**. We explain the modification called excess-interaction suboptimality gap (EISG) below. The detailed definition is provided in **Definition 3 of Section 5** in the revision. Specifically, let $D_h(s)$ denote the largest expected remaining interaction length among optimal policies starting from $(h,s)$, with $D_{H+1}=0$. Define $$\ell_h(s,a) =1+(P_hD_{h+1})(s,a)-D_h(s),$$ and the excess-interaction suboptimality gap (EISG) as $$\gamma_{\mathrm{len}}:=\min_{\substack{h\in[H],s\in\mathcal S,a\in\mathcal A\\ \ell_h(s,a) > 0}}\{V_h^\star(s)-Q_h^\star(s,a)\}.$$ Here, $\ell_h(s,a) > 0$ means that taking $a$ and then following a longest optimal continuation yields a larger expected interaction length than any optimal policy starting from $(h,s)$. Every optimal base action satisfies $\ell_h(s,a)\leq0$. Consequently, the minimum defining $\gamma_{\mathrm{len}}$ is taken over a subset of suboptimal base actions, implying $\gamma_{\mathrm{len}}\geq\gamma_{\min}$. With this refined parameter, our upper bounds and both lower bounds retain their stated rates. The refinement also applies to the new Bernstein bound described in **A1** above. In particular, modifying the rewards and fallbacks in the EHL construction in Theorem 5 yields **a hard family with** $d^\star=\ell, \gamma_{\mathrm{len}}=\frac14$, while preserving the constant-probability lower bound $\mathrm{Reg}(K)=\Omega(H\sqrt{SAKd^\star})$. Because $\gamma_{\mathrm{len}}=1/4$, the $d^\star$-dependent term dominates the Bernstein upper bound in Theorem 7 for sufficiently large $K$, giving $\mathrm{Reg}(K)=\widetilde O(H\sqrt{SAKd^\star})$. Thus, **the upper and lower bounds match up to logarithmic factors on the same family**, establishing a regime in which the $\sqrt{Kd^\star}$ dependence is both achievable and necessary.
AuthorsOpenReview ↗

Response to Reviewer dCSa (Part 2/2)

A2 (continued): (ii) Relation to existing gap-dependent bounds.

We agree that the cited gap-dependent analyses can yield logarithmic regret when the standard minimum positive action gap of the augmented MDP is bounded away from zero (Simchowitz and Jamieson, 2019; Xu et al., 2021). However, this condition is stronger than requiring either γmin⁡\gamma_{\min} or γlen\gamma_{\mathrm{len}} to be bounded away from zero because of different definitions of gaps.

The standard minimum positive action gap Δ\Delta is defined over the entire augmented action space, including abstention. In contrast, γmin⁡\gamma_{\min} considers only positive base-action gaps, and γlen\gamma_{\mathrm{len}} further restricts attention to base actions with positive excess-length increments. Therefore, Δ≤γmin⁡≤γlen\Delta\leq\gamma_{\min}\leq\gamma_{\mathrm{len}}, and the inequalities can be strict.

To illustrate this distinction, we can consider an example where Δ\Delta can be arbitrarily small but γmin⁡\gamma_{\min} and γlen\gamma_{\mathrm{len}} are bounded away from zero. Consider an MDP with H=2H=2, a single absorbing state ss, two base actions a,ba,b with deterministic self-transitions, and an abstention action. Set $ r_1(a)=1/2, r_1(b)=1/4, r_2(a)=r_2(b)=0, $ and fallback reward $ G_1=1-\delta,G_2=\frac12, 0 < \delta < 1/4. $

At time step 2, abstention is optimal, and both base-action gaps equal 1/21/2. At time step 1, taking aa and then abstaining is optimal, with value 11. Action bb has value Q1⋆(s,b)=3/4Q_1^\star(s,b)=3/4, giving a gap of 1/41/4, whereas immediate abstention has gap δ\delta.

Moreover, D1(s)=1D_1(s)=1 and D2(s)=0D_2(s)=0, so ℓ1(s,a)=ℓ1(s,b)=0,ℓ2(s,a)=ℓ2(s,b)=1\ell_1(s,a)=\ell_1(s,b)=0, \ell_2(s,a)=\ell_2(s,b)=1. Consequently,

\gamma_{\min}=\frac14,\qquad \gamma_{\mathrm{len}}=\frac12.$$ The small abstention gap $\delta$ is excluded from both of our parameters, while the base-action gap $1/4$ at time step 1 is additionally excluded from $\gamma_{\mathrm{len}}$. Thus, the standard gap can be arbitrarily small even when both of our gap parameters remain bounded away from zero. As a result, even when $\gamma_{\min}$ or $\gamma_{\mathrm{len}}$ is bounded from zero, $\Delta$ can be $O(K^{-1/2})$, and hence the previous gap-dependent result $(\log K)/\Delta_K$ scales as $\sqrt K\log K$, and do not imply uniformly logarithmic regret over this class of instances. **References** [1] Max Simchowitz and Kevin G. Jamieson (2019). [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://proceedings.neurips.cc/paper_files/paper/2019/hash/10a5ab2db37feedfdeaab192ead4ac0e-Abstract.html). [2] Haike Xu, Tengyu Ma, and Simon S. Du (2021). [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://proceedings.mlr.press/v134/xu21a.html). 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.

Thanks for the effort. This looks like it genuinely closes the main issues in a principled way. I'm raising my score by a point, great job.

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!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.