acceptodds
Under review as a conference paper at ICLR 2027

Instance-Dependent Auto-Exploration for Tabular Online Discounted Reinforcement Learning

Abstract

In online discounted reinforcement learning from a single trajectory, a central cost is exploration: the time spent reaching states whose optimal action is still unknown. Existing auto-exploration guarantees for stochastic policy mirror descent charge every iteration the cost of reaching the hardest state, even once its optimal action is known, through a constant exponential in the mixing time of the optimal policy. We prove that the exploration cost is controlled instead by a certified hitting cost , which is equivalent up to constants to the worst-case expected time to reach under policies that keep mass at least on optimal actions. For the algorithm's , every iterate is such a policy with high probability. Each rollout stops once it covers the states where the policy keeps mass at least on two or more actions. Resolved states leave this set, so every iteration is charged only the largest over unresolved states. For accuracy and advantage gaps , the sample complexity is then at most an baseline plus the exploration cost , up to logarithmic and instance-independent factors. The only structural assumption is that some deterministic optimal policy induces an irreducible chain; the mixing regime and action-independent transitions are special cases with explicit bounds on . On an action-dependent family of states whose small gaps arise from transitions, the upper bound matches a lower bound with deterministic costs up to logarithmic factors, for a fixed discount factor. Charging the hardest state at every iteration gives .

Primary area:
learning theory
Keywords:
reinforcement learning, exploration–exploitation, learning theory, instance-dependent algorithms

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_Dhz2OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper focuses on improving the total sample complexity of stochastic policy mirror descent for online discounted reinforcement learning. Building on Ju & Lan (2025), the authors proposed an adaptive rollout length so that each iteration only needs to sufficiently explore states where multiple actions still have non-negligible probabilities. This yields an instance-dependent sample complexity bound based on statewise hitting times and advantage gaps, at the cost of an additional (1−γ)−2(1-\gamma)^{-2} factor in the iteration complexity. The authors also show that their algorithm achieves a matching upper and lower sample complexity bound, up to logarithmic factors, on a specific family of MDPs with a fixed discount factor.

Critical strengths

1, The proposed adaptive rollout length is interesting and seems to reduce the total sample complexity by avoiding unnecessary exploration of states whose optimal actions have already been identified.

2, The authors establish matching upper and lower sample complexity bounds on a constructed family of MDPs.

Critical weaknesses

1, The proposed analysis introduces an additional (1−γ)−2(1-\gamma)^{-2} factor in the iteration complexity compared with Ju & Lan (2025). Therefore, the resulting total sample complexity is not necessarily better than the previous guarantee.

2, Although the authors demonstrate a polynomial improvement over a global exploration charge on a specific family of MDPs, it remains unclear how much the general sample complexity bound improves over the original DexplD_{\mathrm{expl}}-dependent bound of Ju & Lan (2025).

Questions for authors

1, Can the authors provide a more quantitative comparison between their general sample complexity bound and the original DexplD_{\mathrm{expl}}-dependent bound of Ju & Lan (2025), beyond the constructed examples?

2, Can the authors characterize a broader class of MDPs for which the reduction in rollout complexity outweighs the additional (1−γ)−2(1-\gamma)^{-2} factor, leading to a provable improvement in total sample complexity?

3, Is the additional (1−γ)−2(1-\gamma)^{-2} dependence necessary for the proposed algorithm, or could it be avoided with a tighter convergence analysis?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Dhz2

We thank the reviewer for the review, and respond to the weaknesses and questions in the following.

[W1, Q3] The additional (1−γ)−2(1-\gamma)^{-2} factor: The analysis introduces an additional (1−γ)−2(1-\gamma)^{-2} factor in the iteration complexity compared with Ju & Lan (2025), so the total sample complexity is not necessarily better. Is this factor necessary, or could a tighter analysis avoid it?

The different dependence on γ\gamma comes from a different proof technique. The last-iterate analysis of Ju & Lan requires bias control along earlier iterates πt0\pi_{t_0}, whereas the bias control that is verified is relative to the optimal policy π∗\pi^*. We did not adopt that proof technique and instead prove last-iterate convergence directly. The direct argument has one additional factor (1−γ)−1(1-\gamma)^{-1} in the error of the last iterate, which becomes (1−γ)−2(1-\gamma)^{-2} in the iteration count. This is the only additional factor. Since the two analyses use different techniques, and theirs is not applicable when bias control along earlier iterates is not available, the two iteration counts are not directly comparable.

Besides the iteration count, the comparison could be made on the total sample complexity. There, in terms of γ\gamma and ε\varepsilon, the bound of Ju & Lan is O~((1−γ)−5ε−2Dexpl)\widetilde O\big((1-\gamma)^{-5}\varepsilon^{-2}D_{\mathrm{expl}}\big), where the global constant Dexpl∝(1−γ)−2bˉD_{\mathrm{expl}}\propto(1-\gamma)^{-2\bar b} contains the mixing-time parameter bˉ\bar b and can be exponential in the mixing time. Our exploration term is O~((1−γ)−5max⁡sHθ(s)/max⁡(1−γ)ε,Δ(s)2)\widetilde O\big((1-\gamma)^{-5}\max_s H_\theta(s)/\max\\{(1-\gamma)\varepsilon,\Delta(s)\\}^{2}\big), which avoids this constant. Whether the additional factor that occurs in our analysis can be removed could be a possible future direction. The revised paper states this comparison in Remark 3.7 (lines 311–313) and explains where the factor arises in Section 5.1 (lines 463–464).

[W2, Q1, Q2] Improvement of the general bound over DexplD_{\mathrm{expl}}: Beyond the constructed family, how much does the general bound improve over the DexplD_{\mathrm{expl}}-dependent bound of Ju & Lan (2025)? Can a broader class of MDPs with a provable improvement be characterized?

The improvement holds for general MDPs, beyond the constructed family. The DexplD_{\mathrm{expl}}-dependent bound charges the hardest-to-reach state at every iteration, which is a global count, whereas our bound is a local count that charges each state only until it is locked. With the same hitting cost HθH_\theta, the two exploration terms are

max⁡sHθ(s)((1−γ)ε)2⏟global countandmax⁡sHθ(s)max⁡(1−γ)ε,Δ(s)2⏟local count.\underbrace{\frac{\max_s H_\theta(s)}{((1-\gamma)\varepsilon)^{2}}}_{\text{global count}}\qquad\text{and}\qquad\underbrace{\max_s\frac{H_\theta(s)}{\max\\{(1-\gamma)\varepsilon,\\ \Delta(s)\\}^{2}}}_{\text{local count}}.

The local count is never larger than the global one. The gain matters most in the high-precision regime. Once the accuracy (1−γ)ε(1-\gamma)\varepsilon falls below the gap of a state, that state is charged Δ(s)−2\Delta(s)^{-2} and its cost stops growing with 1/ε1/\varepsilon. For example, as ε\varepsilon approaches 00, the global count grows like ε−2\varepsilon^{-2} times the cost of the hardest state, whereas in the local count only the states whose gaps are still below the accuracy are charged ε−2\varepsilon^{-2}, and if all gaps are positive the exploration term becomes independent of ε\varepsilon. The improvement therefore appears whenever hard-to-reach states have gaps above the target accuracy.

The comparison above is made within our framework, with the same hitting cost HθH_\theta. In Ju & Lan, this cost is bounded through the mixing time of the intermediate policies, which gives DexplD_{\mathrm{expl}}. On the family we provide, DexplD_{\mathrm{expl}} grows exponentially in nn, whereas max⁡sHθ(s)=n2\max_s H_\theta(s)=n^2. The revised paper states this comparison in the introduction (lines 97–100) and discusses it in Section 3.5 (lines 322–350).

Thanks the authors for the rebuttal. However, my concerns still remain.

On the sample complexity of Ju & Lan According to Theorem 3.5 of Ju & Lan, isn't the sample complexity (1−γ)−3Dexplϵ−2(1-\gamma)^{-3}D_{expl}\epsilon^{-2}? Then the total complexity of this paper replace DD with a 'local' constant at the cost of additional (1−γ)−2(1-\gamma)^{-2}.

To address my concern, could the authors also provide a analysis on HH dependence on γ\gamma and other problem dependent constant?

On relation between DD and HH The authors claim a relation between DD and HH which shows that the local count is always smaller. However, I did not find a formal proof supporting the claim in paper. Further, I am asking about whether the benefit gain from local count can balance the additional (1−γ)−2(1-\gamma)^{-2} in iterate count so the total sample complexity is indeed smaller. To answer this, I believe it is necessary to expand every constant in terms of discount factor, problem dependent constant like mixing time so a clean comparison can be made.

Thanks a lot for your follow-up questions. We response as follows.

On the sample complexity of Ju & Lan

Ignoring the factors in δ\delta, the complexity in Theorem 3.5 of Ju & Lan is O~(∣A∣2−p(Q^2+Mh2)(1−γ)−3ε−2Dexpl)\widetilde O\big(|\mathcal A|^{2-p}(\hat Q^2+M_h^2)(1-\gamma)^{-3}\varepsilon^{-2}D_{\mathrm{expl}}\big). Here Q^=1/(1−γ)\hat Q=1/(1-\gamma), and MhM_h is the Lipschitz constant of the regularizer. Our setting has no regularization, so Mh=0M_h=0, and Q^2\hat Q^2 contributes an additional (1−γ)−2(1-\gamma)^{-2}. Hence, their total complexity is

O~(∣A∣2−p(1−γ)−5ε−2Dexpl).\widetilde O\big(|\mathcal A|^{2-p}(1-\gamma)^{-5}\varepsilon^{-2}D_{\mathrm{expl}}\big).

The exploration term in our paper is O~(∣A∣2−p(1−γ)−5max⁡sHθ(s)/max⁡(1−γ)ε,Δ(s)2)\widetilde O\big(|\mathcal A|^{2-p}(1-\gamma)^{-5}\max_s H_\theta(s)/\max\\{(1-\gamma)\varepsilon,\\ \Delta(s)\\}^{2}\big). In the worst case, when all gaps are below (1−γ)ε(1-\gamma)\varepsilon, it becomes

O~(∣A∣2−p(1−γ)−7ε−2max⁡sHθ(s)).\widetilde O\big(|\mathcal A|^{2-p}(1-\gamma)^{-7}\varepsilon^{-2}\max_s H_\theta(s)\big).

As for the dependence of HθH_\theta on γ\gamma and on the other constants, under the geometric ergodicity assumption of Ju & Lan we have Hθ(s)≤2bˉ/(θbˉν∗(s))H_\theta(s)\le 2\bar b/(\theta^{\bar b}\nu^*(s)) with θ=Θ~((1−γ)/∣A∣)\theta=\widetilde\Theta((1-\gamma)/|\mathcal A|) (Corollary 3.10), where bˉ\bar b is the mixing parameter of the optimal policy and ν∗\nu^* its stationary distribution. In comparison, Dexpl=(∣A∣log⁡(1/δ)1−γ)2bˉ⋅1(1−ρ∗)(ν‾∗)3D_{\mathrm{expl}}=\big(\frac{|\mathcal A|\log(1/\delta)}{1-\gamma}\big)^{2\bar b}\cdot\frac{1}{(1-\rho^*)(\underline\nu^*)^{3}}. Hence, HθH_\theta carries (1−γ)−bˉ(1-\gamma)^{-\bar b}, whereas DexplD_{\mathrm{expl}} carries (1−γ)−2bˉ(1-\gamma)^{-2\bar b}.

Compared with Ju & Lan, our bound contains an additional (1−γ)−2(1-\gamma)^{-2} outside these constants. It comes from the different proof techniques mentioned above. In their paper, they check the bias control of πt\pi_{t} and π∗\pi^* while to apply it to get the result, they require the bias control of πt\pi_{t} and earlier intermediate πt0\pi_{t_0}, which requires additional verification. We therefore adopt another technique to control the last iterate, which pays an extra (1−γ)−1(1-\gamma)^{-1} in the error of the last iterate, and this becomes (1−γ)−2(1-\gamma)^{-2} in the iteration count after squaring. Hence, we think that the two bounds are not directly comparable in this factor.

On the relation between DexplD_{\mathrm{expl}} and HθH_\theta

The comparison between the local and the global count with the same HθH_\theta is Proposition 3.5. Ju & Lan consider the global count and use DexplD_{\mathrm{expl}} to build the global bound, which can be looser than the global count with Hθ(s)H_\theta(s). As compared earlier in this reply, under the geometric ergodicity regime of Ju & Lan we have Dexpl=O~((∣A∣/(1−γ))2bˉ/((1−ρ∗)(ν‾∗)3))D_{\mathrm{expl}}=\widetilde O\big((|\mathcal A|/(1-\gamma))^{2\bar b}/((1-\rho^*)(\underline\nu^*)^{3})\big) and Hθ(s)=O~(bˉ,(∣A∣/(1−γ))bˉ/ν∗(s))H_\theta(s)=\widetilde O\big(\bar b\\,(|\mathcal A|/(1-\gamma))^{\bar b}/\nu^*(s)\big). The upper bound on HθH_\theta is given in Corollary 3.10. Besides, on an explicit family (Section 4), we discuss how the uniform upper bounds on DexplD_{\mathrm{expl}} and on HθH_\theta can be loose: both grow exponentially with nn, while a careful analysis based on the structure of the MDP gives a polynomial bound via controlling Hθ(s)H_\theta(s).

For comparison, as derived above, the two final bounds are

(1−γ)−2⋅bˉ,∣A∣bˉ+2−p(1−γ)bˉ+5,ε2,ν‾∗⏟oursand∣A∣2bˉ+2−p(1−γ)2bˉ+5,ε2,(1−ρ∗)(ν‾∗)3⏟Ju and Lan.\underbrace{(1-\gamma)^{-2}\cdot\frac{\bar b\\,|\mathcal A|^{\bar b+2-p}}{(1-\gamma)^{\bar b+5}\\,\varepsilon^{2}\\,\underline\nu^*}}_{\text{ours}}\qquad\text{and}\qquad\underbrace{\frac{|\mathcal A|^{2\bar b+2-p}}{(1-\gamma)^{2\bar b+5}\\,\varepsilon^{2}\\,(1-\rho^*)(\underline\nu^*)^{3}}}_{\text{Ju and Lan}}.

The factor (1−γ)−2(1-\gamma)^{-2} in front of our bound is the additional one from the different proof technique discussed above, and it may be not directly comparable. In the remaining factors, the powers of (1−γ)−1(1-\gamma)^{-1}, ∣A∣|\mathcal A| and 1/ν‾∗1/\underline\nu^* in our bound are all smaller.

My concerns have been addressed and I raised my score to 3.

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

This paper considers the following question: what is the sample complexity of exploration in discounted Q-learning. The sampling policy is allowed to change on-the-go. It derives a lower bound and a matching upper-bound. The bound grows as 1/acc.^2 and effective horizon^7 (here acc. = desired accuracy). There's a prefactor which grows as worst case hitting time (its one of the major findings in this work). The derivations and proofs seem fine.

Critical strengths

The problem studied is well motivated, though does not seem to be of much importance.

Critical weaknesses
  1. presentation is lacking. At many places the sentences seem to be mechanical and artificial, probably written by A.I. usage. Such sentences must be "smoothened." At places the paper is hard to understand, took me a while to understand what exactly is being studied. One more example of this: clearly describe the sampling model which generates state,actions and transitions at the very outset.

  2. Regret analysis is lacking. When the samples are generated sequentially, it is natural for one to seek a regret bound on the actual performance costs incurred during the "learning." I was expecting some results on this.

  3. Though the problem being studied is relevant, it does not add much value to the existing literature. Exploration in RL has been studied tremendously, and bounds of such form are well-known by now. It is also known that diameter of the MDPs decides the sample complexity in RL.

  4. A regret analysis would be useful.

  5. Moreover, there are already several works on discounted Q-learning which derive sample complexity of Q-learning. Some important such works have not been discussed, and not differentiated against the current work.

Questions for authors
  1. There are several works on discounted Q-learning which derive sample complexity of Q-learning. Please do a thorough literature survey of these, and compare them against your current work. Its hard to judge the novelty of current work in the absence of this comparison.

  2. Would it be possible to derive regret guarantees?

  3. Can you throw light on some new parameters of the problem instance which enter into the sample complexity. H theta seems to be new, but of the same order as diameter of the MDP. Since diameter is already known to enter in such complexity results, I find this to be not too surprising of a result.

8 comments
AuthorsOpenReview ↗

Response to Reviewer AbjD (Part 1)

We thank the reviewer for the review, and respond to the weaknesses and questions in the following.

[W1] Presentation: The writing is mechanical in places and hard to follow, and the sampling model should be described at the outset.

Thank you for pointing this out. The setting is online discounted reinforcement learning. In every iteration, SPMD acts with its current policy and collects a rollout of the Markov chain that this policy induces. It estimates the Q-values from this rollout and takes one mirror-descent step on them to obtain the policy of the next iteration. We have made this explicit in the first paragraph of the introduction (lines 36–45) and in Section 2 (lines 148–159).

We have revised the presentation of the paper. The introduction now shows the calculation of the global and the local count in the motivating example in more detail (lines 46–53), and states the background, the motivation, our approach and the contributions in the clearer order (lines 36–100). Section 2 describes the sampling process and the auto-exploration algorithm in detail (lines 148–194), which makes the setting and the baseline clear. Section 3 keeps the key technical terms and explains each core quantity of the analysis when it is introduced (lines 231–277), and the main theorem is followed by an explanation of its implications and of how it compares with previous work (lines 301–318). We also added more detail to the proof sketch in Section 5 (lines 421–497), which now describes more clearly the role of each step of the argument, its motivation and implications, and how it is derived, such as how the additional factor (1−γ)−1(1-\gamma)^{-1} arises (lines 463–464). In this revision, we also rewrote several very technical sentences to make the line of thought easier to follow.

[W2, W4, Q2] Regret: A regret analysis is lacking. Since the samples are generated sequentially, a regret bound on the cost incurred during learning would be natural and useful. Would it be possible to derive regret guarantees?

The objective of this paper is sample complexity: how many samples an auto-exploring policy needs to return an ε\varepsilon-optimal policy from a single trajectory. This is also a cost of learning online, measured by the number of interactions spent while the trajectory is collected, so our concern is close in spirit to the one behind regret. In our work, we show that exploration and exploitation can be coupled state by state: once a hard-to-reach state has been explored enough, it is locked and no longer has to be reached, and the learned policy is still guaranteed to converge. Hence, in our analysis, the cost of such a state is paid only until it is locked, rather than at every iteration as in existing guarantees. This yields the first non-asymptotic instance-dependent bound in this setting, and it is matched by a lower bound on a family of instances that we construct. Since the objective is the number of samples needed to return an ε\varepsilon-optimal policy, these two bounds already characterize it, and a regret analysis is not needed for this purpose. Regret, which measures the loss accumulated during learning, is closely related to this cost and could be a possible future direction.

AuthorsOpenReview ↗

Response to Reviewer AbjD (Part 2)

[W3, Q3] Significance and novelty: The paper adds little to the existing literature: bounds of this form are well known, the diameter is known to govern the sample complexity, and HθH_\theta seems to be of the same order as the diameter.

The main difference from existing results is not that a reachability quantity appears, since any single-trajectory guarantee needs one, but how the exploration cost is counted. Auto-exploration (Ju & Lan, 2025) learns from a single trajectory with no resets, no simulator and no prior knowledge of mixing parameters, but its guarantee charges a global exploration cost, which gives (global constant) ×ε−2\times\\ \varepsilon^{-2}. We show that a state has to be paid for only until its optimal action is identified, which gives

max⁡sHθ(s)max⁡(1−γ)ε,Δ(s)2versusε−2max⁡sHθ(s).\max_s\frac{H_\theta(s)}{\max\\{(1-\gamma)\varepsilon,\\ \Delta(s)\\}^{2}}\quad\text{versus}\quad\varepsilon^{-2}\max_sH_\theta(s).

Our key observation is that hard-to-reach states with large gaps can stop being charged early. We show that in this case the learned policy is still guaranteed to be ε\varepsilon-optimal. On a family of instances, the bound is O~(n2+nε−2)\widetilde O(n^2+n\varepsilon^{-2}) against n2ε−2n^2\varepsilon^{-2}, and we show a lower bound that matches it, demonstrating the improvement.

Hθ(s)H_\theta(s) itself is the time needed to reach ss under the policies that the algorithm follows. Unlike the diameter, which is one global number, it is statewise, and this is what allows each state to be charged at its own gap. A quantity of this kind is implicit in previous analyses as well. Our focus is how to establish convergence when hard-to-reach states are locked at an early stage. To our knowledge, this is the first non-asymptotic instance-dependent bound for this setting.

[W5, Q1] Related work on Q-learning: Existing sample-complexity results for discounted Q-learning are not discussed or compared with the present work.

Our method is based on stochastic policy mirror descent (SPMD), not on Q-learning. SPMD has implicit exploration: it keeps the optimal action of every state in the support of the policy, which is what guarantees state exploration and efficient convergence without an exploration schedule, and what allows resolved states to be locked. Sample-complexity results for discounted Q-learning assume a generative model or a behavior policy that already covers all state-action pairs, and their bounds have the form (global coverage constant) ×ε−2\times\\ \varepsilon^{-2}. The on-policy analysis of Nanda & Chen (2025), discussed in Section 2, is the closest and also uses a global constant. Our bound differs in being instance-dependent, as described above. We have added this comparison to the related work in Section 2 (lines 114–116).

Reviewer_AbjDOpenReview ↗

response read

I have read the response of authors. They fail to address my concerns, and I stick to my score.

Reviewer_MbxXOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper investigates the sample complexity of learning an approximately optimal policy in a finite discounted MDP from a single trajectory, without resets. It modifies stochastic policy mirror descent so that each rollout need only collect sufficient observations at states where multiple actions still have substantial probability. This avoids repeatedly waiting for hard-to-reach states once their best action has effectively been identified. Under the assumption that some deterministic optimal policy induces an irreducible chain, the authors establish a high-probability, instance-dependent sample-complexity bound combining state-specific hitting costs and action gaps. The analysis justifies convergence despite incomplete sampling at inactive states and shows that sufficiently large-gap states eventually leave the active set. On a constructed family, the resulting bound improves from a global exploration charge of order (n^2\varepsilon^{-2}) to (\widetilde O(n^2+n\varepsilon^{-2})), matching a family-specific lower bound up to logarithmic factors. The improvement concerns exploration costs; general instance optimality and optimal discount-factor dependence are not established.

Critical strengths

• The paper addresses an important and comparatively understudied problem: learning an approximately optimal policy from a single continuous trajectory, without resets. • To the best of my knowledge, it provides the first non-asymptotic, instance-dependent sample-complexity guarantee for approximate policy identification in this setting. This complements earlier guarantees restricted to the asymptotic high-confidence regime.

Critical weaknesses

• The paper is difficult to follow. Technical definitions and proof ingredients appear before the underlying algorithmic bottleneck and the distinction between the algorithmic and analytical advances are sufficiently explained. The introduction is hard to follow and does not make a good job at introducing the problem. It identifies a potentially meaningful limitation of existing exploration guarantees, but does not sufficiently explain the underlying algorithmic problem before presenting its technical solution. In particular, it remains unclear whether the global exploration cost reflects unavoidable behavior of the previous algorithm or looseness in its analysis. A clearer description of the baseline algorithm, the source of unnecessary sampling, and the distinction between the algorithmic and analytical improvements would make the motivation and contribution substantially easier to assess. The contributions part of the introduction is also difficult to follow. It introduces several technical notions (certified hitting costs, certified policies, cumulative-gradient arguments, and dual coordinates) before providing a sufficiently clear explanation of their role. • Although the sample-complexity bound is stated explicitly, its full scaling is difficult to assess. Important dependencies are distributed across the threshold (\theta), the certified hitting costs (H_\theta), and other parameters. More transparent specializations and direct comparisons with existing bounds would help establish the significance of the improvement. • The analysis is restricted to tabular MDPs and assumes that some deterministic optimal policy induces an irreducible chain. These restrictions limit its scope, particularly for large state spaces requiring function approximation. • The practical relevance remains insufficiently demonstrated. The empirical evidence is confined to a constructed example.

Questions for authors

Could the authors provide a more explicit comparison with the sample-complexity bound of Al Marjani et al. (2021), beyond the distinction between finite-time approximate identification and asymptotic exact identification?

5 comments
AuthorsOpenReview ↗

Response to Reviewer MbxX (Part 1)

We thank the reviewer for the review, and respond to the weaknesses and questions in the following.

[W1] Presentation: The paper is difficult to follow. Technical notions appear before the algorithmic bottleneck is explained, and it remains unclear whether the global exploration cost reflects unavoidable behavior of the previous algorithm or looseness in its analysis.

Thank you for pointing this out.

Auto-exploration (Ju & Lan, 2025) learns from a single trajectory with no prior knowledge of mixing parameters, and guarantees exploration implicitly in each rollout. In each iteration, the algorithm follows the current policy πt\pi_t to collect a rollout, estimates QπtQ^{\pi_t} from it, and updates the policy to πt+1\pi_{t+1} by a mirror-descent step. The rollout ends only when the estimate is accurate at every state, which requires every state to be visited. Each iteration therefore pays the exploration cost of the hardest-to-reach state, even after the optimal action of that state has been identified. This is unavoidable behavior of the original algorithm. Motivated by this, we study whether a hard-to-reach state that is resolved early, thanks to a large gap, can stop being paid for afterwards, and whether convergence of the policy can still be guaranteed.

We answer both questions. With a minimal active-set-aware modification of the algorithm, a state is locked once the policy concentrates on its optimal action: it exits the active set and no longer contributes to the exploration cost. We show that the learned policy is still guaranteed to be ε\varepsilon-optimal, and that the global charge is replaced by a local one. The exploration cost is governed by reachability times unresolved duration, so that each state is charged only while its optimal action remains uncertain. We further construct an MDP family. We show that the local bound gives O~(n2+nε−2)\widetilde O(n^2+n\varepsilon^{-2}), which matches the lower bound up to logarithms, while the global one gives a suboptimal O~(n2ε−2)\widetilde O(n^2\varepsilon^{-2}).

We have revised the presentation of the paper. The introduction now shows the calculation of the global and the local count in the motivating example in more detail (lines 46–53), and states the background, the motivation, our approach and the contributions in the clearer order (lines 36–100). Section 2 describes the sampling process and the auto-exploration algorithm in detail (lines 148–194), which makes the setting and the baseline clear. Section 3 keeps the key technical terms and explains each core quantity of the analysis when it is introduced (lines 231–277), and the main theorem is followed by an explanation of its implications and of how it compares with previous work (lines 301–318). We also added more detail to the proof sketch in Section 5 (lines 421–497), which now describes more clearly the role of each step of the argument, its motivation and implications, and how it is derived, such as how the additional factor (1−γ)−1(1-\gamma)^{-1} arises (lines 463–464). In this revision, we also rewrote several very technical sentences to make the line of thought easier to follow.

[W2] Scaling of the bound: The full scaling of the bound is difficult to assess, since important dependencies are distributed across θ\theta, HθH_\theta and other parameters. More transparent specializations and direct comparisons with existing bounds would help.

Ignoring logarithmic and some other factors, our bound differs from the existing one in the exploration term, where a local count replaces the global one:

max⁡sHθ(s)ε2⏟global countandmax⁡sHθ(s)max⁡ε,Δ(s)2⏟local count.\underbrace{\frac{\max_s H_\theta(s)}{\varepsilon^{2}}}_{\text{global count}}\qquad\text{and}\qquad\underbrace{\max_s\frac{H_\theta(s)}{\max\\{\varepsilon,\\ \Delta(s)\\}^{2}}}_{\text{local count}}.

Here Hθ(s)H_\theta(s) is the expected time to reach ss under the policies that the algorithm follows. It is the cost that a single-trajectory learner has to pay before it can update the policy at ss. Replacing the global count by the local one is the technical core of the paper. Once locked states are no longer sampled, their estimates are not accurate. We show that the error at a locked state never favors a suboptimal action over the optimal one, which is what convergence requires, and that a state is indeed locked once the accuracy falls below its gap.

AuthorsOpenReview ↗

Response to Reviewer MbxX (Part 2)

[W2] Scaling of the bound (Cont'd)

The local count is never larger than the global one. Once the accuracy ε\varepsilon falls below the gap of a state, that state is charged at its own gap, Δ(s)−2\Delta(s)^{-2}, and its cost stops growing with 1/ε1/\varepsilon. Hence, the global count grows like ε−2\varepsilon^{-2} times the cost of the hardest state, whereas in the local count only the states whose gaps are still below the accuracy are charged ε−2\varepsilon^{-2}.

We keep HθH_\theta in the theorem because it can be evaluated from the structure of the MDP. Under the mixing assumption of Ju & Lan, it admits a uniform upper bound, but this bound can be very loose. On the family above, HθH_\theta is n2n^2 for the bottleneck and of order nn for the other states, whereas the uniform upper bound contains factors that grow exponentially with nn.

In the revised paper, the introduction states the bound in this simplified form (lines 65–81). Section 3.3 explains how to understand the local count and states that it is never larger than the global one (lines 259–277), and Section 3.5 shows how HθH_\theta is bounded in concrete cases, including the regime of Ju & Lan (lines 322–350).

[W3] Scope: The analysis is restricted to tabular MDPs and assumes that some deterministic optimal policy induces an irreducible chain.

Compared with prior work (Ju & Lan, 2025), our assumption is weaker: we do not require geometric ergodicity, only irreducibility of the optimal policy. This ensures that every state keeps being reached along the trajectory, which learning without resets requires. In the tabular setting, the analysis is delicate: when locked states are no longer sampled, their estimates are not accurate, and we have to show that convergence is preserved and that states are indeed locked. As for function approximation, our focus is whether a hard-to-reach state can stop being paid for once it is resolved, which is a statewise question. Function approximation is therefore outside the scope of this paper and could be a possible future direction.

[W4] Practical relevance: The practical relevance remains insufficiently demonstrated. The empirical evidence is confined to a constructed example.

The auto-exploration algorithm has been shown to be effective on a range of tasks, including route planning, inventory control and classical control (Ju & Lan, 2025). Our work studies its exploration cost. In our numerical illustration, we show that this cost is reduced substantially: once the bottleneck is locked, rollouts become about 16 times shorter, and the saving grows with the target accuracy. The experiment details can be found in Appendix A.

[Q1] Comparison with Al Marjani et al. (2021): Could the authors provide a more explicit comparison with the sample-complexity bound of Al Marjani et al. (2021), beyond finite-time approximate versus asymptotic exact identification?

Al Marjani et al. (2021) study pure exploration: the learner is free to design its sampling rule, and the question is how few samples are needed to identify the optimal policy. They give an instance-specific lower bound and an algorithm with an instance-specific sample complexity in the asymptotic regime δ→0\delta\to0.

Our question is different. We are interested in policy optimization as it is run in practice, where the policy being learned also collects the data, with implicit exploration and without estimating a model or designing a separate exploration rule. We ask how much exploration costs such an on-policy method, and give a finite-sample bound for ε\varepsilon-optimal policies that is explicit in the reachability and the gap of each state. The two bounds therefore measure different things and are complementary: theirs characterizes the complexity of best-policy identification asymptotically, and ours is a non-asymptotic instance-dependent guarantee for policy optimization along a single trajectory. We have added this comparison to Section 2 (lines 135–137).

Reviewer_MbxXOpenReview ↗

After rebuttal comments

I would like to thank the authors for clarifying the contributions. I read the revised version of the paper, and indeed, clarity has improved. There is still space for improvement in terms of presentation. A lot have been changed already. I also acknowledge the remarks on the scaling of the sample complexity and the difference with off-policy RL results. The concerns about the relevance in practice remain. The numerical experiments are preliminary and on toy examples.

Comments on the paper

1 comment

We thank the reviewers and the AC for their time. We summarize here our answers to the main questions. The details are in the replies to each reviewer.

1. What does the bound add to the existing one, and does the improvement hold beyond the constructed family? (Reviewers AbjD, Dhz2)

The improvement holds for general MDPs, and it comes from how the exploration cost is counted. The bound of Ju & Lan (2025) charges the hardest-to-reach state in every iteration, which gives (global constant) × ε−2\times\ \varepsilon^{-2}. We show that a state has to be paid for only until its optimal action is identified, and that the policy still converges when such states are no longer sampled. The exploration term of Theorem 3.6 and the global count are

max⁡sHθ(s)max⁡{(1−γ)ε, Δ(s)}2andmax⁡sHθ(s)((1−γ)ε)2.\max_s\frac{H_\theta(s)}{\max\{(1-\gamma)\varepsilon,\ \Delta(s)\}^{2}}\qquad\text{and}\qquad\frac{\max_s H_\theta(s)}{((1-\gamma)\varepsilon)^{2}}.

The first is never larger than the second (Proposition 3.5). The gain appears whenever hard-to-reach states have gaps above the target accuracy, and if all gaps are positive, the exploration term stops growing with 1/ε1/\varepsilon. On a family of instances, it gives O~(n2+nε−2)\widetilde O(n^2+n\varepsilon^{-2}) against n2ε−2n^2\varepsilon^{-2}, with a matching lower bound (Section 4). To our knowledge, this is the first non-asymptotic instance-dependent bound in this setting.

2. Is HθH_\theta of the same order as the diameter? (Reviewers AbjD, MbxX)

Hθ(s)H_\theta(s) is statewise, while the diameter and DexplD_{\mathrm{expl}} are global numbers, and this is what allows each state to be charged at its own gap. On the family above, HθH_\theta is n2n^2 for the bottleneck and of order nn for the other states, whereas the uniform bound used in Ju & Lan carries a factor that is exponential in the mixing time (Section 3.5).

3. Is the assumption on the optimal policy restrictive? (Reviewer MbxX)

Our assumption is weaker than that of Ju & Lan (2025). We require only that the optimal policy is irreducible, and not geometric ergodicity.

4. Is the global cost unavoidable behavior of the previous algorithm, and is the saving relevant in practice? (Reviewer MbxX)

The global cost is the behavior of the previous algorithm, whose rollout ends only when every state has been visited again. We added experiments on the environments and tasks used in Ju & Lan (2025), with their code and settings (Section 4.1 and Appendix A.2). GridWorld is a route planning task on grids with 100 and 400 states, and GARNET-50 is a random MDP with 50 states. Our method reaches the same cost with 3.7, 1.6 and 1.6 times fewer samples. On GridWorld 10×1010\times 10, 70% of the samples of the original rule are spent on states that have already left the active set. Once the active set is empty, the original rule still uses about 20,000 samples per iteration, while ours uses 10.

5. Presentation (Reviewers AbjD, MbxX)

The introduction now computes the global and the local count on the motivating example and states the bound in its simplified form. Section 2 describes the sampling process and the auto-exploration algorithm. Section 3 explains each quantity of the analysis when it is introduced, and the main theorem is followed by its implications and its comparison with previous work. The proof sketch in Section 5 explains the role of each step.

In the revised PDF, the new experiments are in red and the other changes are in orange.

We thank the reviewers for their comments and suggestions, which helped us improve the paper. Since the discussion period will end soon, we would appreciate it if the reviewers could let us know whether their concerns have been addressed.

Best regards,

The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.