Thank you for the comment! We believe there are some misunderstandings, and have clarified them below. We hope the reviewer could reevaluate our paper, and are very happy to respond more questions during the reviewer-author discussion period.

Q1: What is $\pi^\bot$?

R1: $\pi^\bot$ represents a fixed default policy defined on state space $\mathcal{S}$. It can be understood as ``select an action arbitrarily" (Line 4 of Algorithm 1).

Q2: What does ``by playing an arbitrary action on states not in $\mathcal{S}^\bot$ compatible with $\Pi$, it extends the pruned policy $\pi_t^\bot$ to $\pi_t$'' mean?

R2: Note that $\pi_t^\bot$ is a function with domain $\mathcal{S}^\bot$, where an available policy $\pi_t$ needs to a function with domain $\mathcal{S}$. In this regard, given $\pi_t^\bot$, we need to ``lift'' the function domain from $\mathcal{S}^\bot$ to $\mathcal{S}$. This is achieved by playing an arbitrary action on states not in $\mathcal{S}^\bot$ compatible with $\Pi$.

Q3: What is the initial set of $\mathcal{S}^\bot$?

R3: As we explained in Lines 182-184, $\mathcal{S}^\bot$ includes all the identified $\epsilon$-reachable states and $H$ additional auxiliary states. Therefore, at the beginning of the game, since there is no identified $\epsilon$-reachable states, the initial set of $\mathcal{S}^\bot$ is $H$ additional auxiliary states.

Q4: What are inputs and outputs of ALG?

R4: As we explained in Lines 9-12 of Algorithm 1, the initial input of ALG is a state space, an action space, a policy set, and a confidence coefficient. At each round, ALG outputs a policy that operates within the given state and action space. Upon executing the policy, a trajectory is generated, which then serves as the new input for ALG. Such an interaction process is generally applicable to all existing online MDP algorithms.

Q5: Figure 1 is not really helpful to understand how the pruned space, dual trajectory, etc are obtained.

R5: We are disappointed to hear our figure wasn't helpful, we would love to hear the reviewer's ideas for improvement during the discussion period. We really want to understand what was confusing about this picture because we are committed to improve our paper's presentation to enhance clarity for the camera ready version.

Q6: Comparison of ``Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes''.

R6: Thanks for the additional reference! We will add this in the camera-ready version.

The problem studied in [1] is similar to the one considered in our work, i.e., how to achieve regret adaptive to $|\mathcal{S}^\Pi|$ instead of $|\mathcal{S}|$. However, [1] still requires knowing the possibly large set of available states $\mathcal{S}$. Specifically, as in its Theorem 1, the regret bound still has a term polynomial to the size of the large set of available states $|\mathcal{S}|$. In this regard, when $|\mathcal{S}|$ is large enough or infinite, its regret bound will become vacuous. Such a result aligns perfectly with our Observation 4.3: if the information of $\mathcal{S}$ is used as the input for the algorithm, using existing analysis framework, it is difficult to prevent the regret guarantee from a polynomial-level dependence on $|\mathcal{S}|$.

References:

[1]: Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes https://arxiv.org/abs/1807.02373

Thank you for the comment! We would like to respectfully ask the reviewer to reassess our paper in light of the rebuttal. We believe the reviewer's concern was peripheral to our main contributions and would like to receive a fair assessment of our work.

Q1: While I understand that the focus of this paper is on theories, it could still be informative to include some toy experiments. For example, how would a non state-free algorithm behave if given "wrong" or insufficient knowledge/estimates of the state space, and how would the corresponding state-free algorithm (via the reduction) behaves.

R1: This is a theoretical work, so there are no simulation experiments. Specifically, we are uncertain how existing non-state-free algorithms would perform in our state-free setting, making it challenging to design experiments. For example, consider a non-state-free algorithm running on $\mathcal{S}'$. During some rounds, it executes a policy $\pi$ and obtains a trajectory that includes a state $s \notin \mathcal{S}'$. In this case, it is unclear how does the algorithm update its policy.

Thank you for the instructive feedback! Below we address some of the questions raised by the reviewer.

Q1: I would encourage the authors to provide a clean comparison of the final bounds in the stochastic setting with the best available bounds. In particular, I'm wondering whether the restart leads to extra log terms.

R1: For the stochastic setting, our results suggest that existing algorithm UCBVI actually achieves weakly state-free learning, where its regret is only dependent on $|\mathcal{S}|$ on the log terms (Proposition 4.1). We also propose a straightforward technique, which effectively eliminates the logarithmic dependence on $|\mathcal{S}|$ under UCBVI framework (Proposition 4.2). These two propositions imply that there is no need to use our designed algorithm SF-RL for the stochastic setting.

Furthermore, in inhomogeneous finite-horizon MDP, it seems that UCBVI has achieved asymptotically optimal regret. In this regard, Proposition 4.2 suggests that UCBVI (with small modifications) can also achieve state-free asymptotically optimal regret, which matches the best available bound. Besides, there is no restart in UCBVI, thus there is no extra log terms.

Q2: Related the previous point, I suggest the authors to make explicit the bounds for simple doubling trick strategies, so as to have a point of comparison.

R2: If the reviewer are referring to apply doubling trick on the state space, we will encounter some issues in the analysis. In Theorem 6.2, when a state $s$ is placed into $\mathcal{S}$, we initialize its corresponding high probability event ($\delta(s)$). In this case, we need to know exactly which state s refers to (i.e., the index of $s$). However, under doubling trick strategies, the states generated each time we double are void, which makes it impossible to establish the corresponding high probability events.

Q3: What is exactly the role of epsilon? It looks like it can be directly set to $0$ and everything works the same.

R3: Good question! $\epsilon$ controls the tradeoff between the regret of ALG and the error incurred by the barely reachable states we discard. Specifically, when $|\mathcal{S}^\Pi|< \infty$, our results suggest that the optimal choice of $\epsilon$ should be $o(1/\sqrt{T})$ instead of $0$. For example, by setting $\epsilon=1/T$, Theorem 6.2 achieves regret bound $\tilde{\mathcal{O}}(H|\mathcal{S}^{\Pi, 1/T}|\sqrt{|\mathcal{A}|T}+H|\mathcal{S}^{\Pi}|)$. When $|\mathcal{S}^{\Pi, 1/T}|\ll |\mathcal{S}^{\Pi}|$, this regret will be much smaller than the regret under $\epsilon = 0$.

Q4: Comparison of ``Layered State Discovery for Incremental Autonomous Exploration''.

R4: The objective of [1] is fundamentally different to the objective of our work (even if we transform the infinite horizon setting to our finite horizon setting). In [1], the objective is to find all the incrementally L-controllable states. If we transform this to our finite-horizon setting, the objective should be to find all the incrementally $\epsilon$-reachable states. However, in our work, the objective is to minimize the regret. In this regard, our algorithm does not require to find all $\epsilon$-reachable states. Specifically, as described in Algorithm 1, if an $\epsilon$-reachable state has not been reached $\epsilon t$ times, it will not be included in $\mathcal{S}_t^\bot$. This implies that in our work the pruned space $\mathcal{S}_t^\bot$ may never be the same to $\mathcal{S}^{\epsilon, \Pi}$, even if $t$ goes to infinite.

Q5: Comparison of ``Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes''.

R5: The problem studied in [2] is similar to the one considered in our work, i.e., how to achieve regret adaptive to $|\mathcal{S}^\Pi|$ instead of $|\mathcal{S}|$. However, [2] still requires knowing the possibly large set of available states $\mathcal{S}$. Specifically, as in its Theorem 1, the regret bound still has a term polynomial to the size of the large set of available states $|\mathcal{S}|$. In this regard, when $|\mathcal{S}|$ is large enough or infinite, its regret bound will become vacuous. Such a result aligns perfectly with our Observation 4.3: if the information of $\mathcal{S}$ is used as the input for the algorithm, using existing analysis framework, it is difficult to prevent the regret guarantee from a polynomial-level dependence on $|\mathcal{S}|$.

Thanks for these additional references! We will add these comparisons in the camera-ready version.

References:

[1]: Layered State Discovery for Incremental Autonomous Exploration https://arxiv.org/pdf/2302.03789.

[2]: Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes https://arxiv.org/abs/1807.02373