We thank you for the detailed and useful feedback! We plan to improve our paper taking your comments into account. Our response to your specific questions are summarized as follows.

Discussion on the practicality of known lower bounds for transition probabilities:

We agree with the reviewer that in a practice deriving $p_{min}$ might be challenging. However, all we need is to know a positive lower bound for the minimum transition probability, and not its exact value. Further, the assumption of knowing $p_{min}$ is strictly weaker than the other typical assumptions such as knowing the underlying connection graph of MDP, and there are already negative results in the literature regarding the consequences of not knowing $p_{min}$ for learning against infinite-horizon specifications. Consider a simple MDP with a state set $S = \set{s_{\text{init}}, G}$ and a singleton action set $A = \set{a}$, where the only outgoing transition from the initial state $s_{\text{init}}$ has transition probability $T(s_{\text{init}}, a, G) = \varepsilon$. It is easy to observe that, while the optimal value is one, selecting any $p_{min} > \varepsilon$ results in learning an MDP where the optimal value becomes zero. Hence, knowledge of $p_{min}$ is crucial for effectively learning in infinite-horizon tasks. In practice, domain-specific knowledge of the target system can be helpful in order to choose a sensible value for $p_{min}$.

Writing of section 4.1:

Section 4.1 is specifically dedicated to explaining various components of the main algorithm (Algorithm 1). In particular, the following components of Algorithm 1 are discussed in detail: (1) the application of Equation (4) for computing confidence intervals, which are then used to construct interval MDPs from the observed data; (2) the operation of our proposed Extended Value Iteration method (Algorithm 2); and (3) the use of Equation (9) to compute episode-specific deadlines. These explanations are provided in the respective subsections of Section 4.1. We appreciate the reviewer’s comment and will revise the writing in Section 4.1 to clarify the connections between these subsections at the outset.

Further clarification for Equation (4):

Equation (4) is used for computing confidence intervals used for constructing interval MDPs, and it is derived at earlier work (see Lemma 4.1). It provides a confidence bound for transitions for every state-action pair $(s,a)$, and is used to construct the interval MDPs. In the final version, we will include Equation (4) in the body of Lemma 4.1, and also give a brief explanation regarding the terms within Equation (4).

Experimental results:

As explained in Section 5, model checking for general LTL specifications over finite MDPs reduces to a reach-avoid problem over the corresponding product MDP. Therefore, regardless of the specific LTL specification, the final step always involves solving a reach-avoid problem in the product space. In response to the reviewer’s concern, we conducted an additional experiment using the same gridworld example described in the Appendix, but with a new LTL specification: “visit $G$ infinitely often while avoiding the walls.” The performance of our method remained consistent with the results reported in Figures 3, 4, and 5. Accordingly, we plan to revise the manuscript to replace the current reach-avoid task with this LTL specification. We will also include the corresponding Deterministic Rabin Automaton (DRA) and the structure of the resulting product MDP in the appendix. Finally, we would like to emphasize that the primary contribution of this paper is the development of the first regret-free controller synthesis algorithm. The experiments are primarily intended to provide insight into various aspects of the approach, including empirical performance, the gap between practical and theoretical sample complexity, and the effect of different episode lengths.

Proposed changes based on comments of reviewer 3:

• Improve writing of Section 4.1
• Include a remark on challenges related to estimating $p_{min}$ in practice
• Replace the current reach-avoid task with a more complex LTL specification and report the results, DRA and product MDP

Thank you for appreciating the depth and technical strength of our results. We plan to improve our paper taking your comments into account. Our response to your specific questions are summarized as follows.

Computational complexity:

The primary computational steps in Algorithm 1 involve two key tasks: (1) executing the EVI algorithm, and (2) calculating $H_k$. The computational complexity of these tasks, respectively, scales quadratically and cubically, with the size of the state space. As a result, the overall computational complexity of Algorithm 1 is cubic with respect to $|S^\times| = |S| \times |Q|$, where $S$ is the state space of the MDP, and $Q$ is the state space of the DRA that corresponds to the given LTL specification.

Discussion on the practicality of known lower bounds for transition probabilities:

We agree with the reviewer that in a practice deriving $p_{min}$ might be challenging. However, all we need is to know a positive lower bound for the minimum transition probability, and not its exact value. Further, the assumption of knowing $p_{min}$ is strictly weaker than the other typical assumptions such as knowing the underlying connection graph of MDP, and there are already negative results in the literature regarding the consequences of not knowing $p_{min}$ for learning against infinite-horizon specifications. Consider a simple MDP with a state set $S = \set{s_{\text{init}}, G}$ and a singleton action set $A = \set{a}$, where the only outgoing transition from the initial state $s_{\text{init}}$ has transition probability $T(s_{\text{init}}, a, G) = \varepsilon$. It is easy to observe that, while the optimal value is one, selecting any $p_{min} > \varepsilon$ results in learning an MDP where the optimal value becomes zero. Hence, knowledge of $p_{min}$ is crucial for effectively learning in infinite-horizon tasks. In practice, domain-specific knowledge of the target system can be helpful in order to choose a sensible value for $p_{min}$.

Experimental results:

• Clarification regarding the implementation: We implemented only Algorithm 1 to obtain the results presented in the Appendix, assuming that the underlying graph structure is known. This assumption is justified by the fact that, for a fixed system dynamics, Algorithm 5 needs to be executed only once to learn the corresponding graph with the desired confidence. The resulting graph can then be reused for verifying any LTL specification. We will ensure that this assumption and its justification are stated explicitly in the final version of the paper.

• Faster convergence compared to the $\omega$-PAC method: We believe that this is because our algorithm uses the intermediate confidence bounds, while the $\omega$-PAC algorithm waits until enough samples are collected, and only then starts updating its policy.

• Scalability against more complex LTL specifications: As explained in Section 5, model checking for general LTL specifications over finite MDPs reduces to a reach-avoid problem over the corresponding product MDP. Therefore, regardless of the specific LTL specification, the final step always involves solving a reach-avoid problem in the product space. In response to the reviewer’s concern, we conducted an additional experiment using the same gridworld example described in the Appendix, but with a new LTL specification: "visit $G$ infinitely often while avoiding the walls". The performance of our method remained consistent with the results reported in Figures 3, 4, and 5. Accordingly, we plan to revise the manuscript to replace the current reach-avoid task with this LTL specification. We will also include the corresponding Deterministic Rabin Automaton (DRA) and the structure of the resulting product MDP in the appendix. Finally, we would like to emphasize that the primary contribution of this paper is the development of the first regret-free controller synthesis algorithm. The experiments are primarily intended to provide insight into various aspects of the approach, including empirical performance, the gap between practical and theoretical sample complexity, and the effect of different episode lengths.

Initialization for $H_1$:

Actually, we compute $H_1$, rather than starting with a choice. This is because we first run EVI to get an optimistic policy $\tilde \pi_1$ and an optimistic MDP $\mathcal{\tilde M}_1$. A DTMC with transition probability matrix $\tilde{P}_1$ is induced by fixing $\tilde \pi_1$ over $\mathcal{\tilde M}_1$, and then we use Equation (10) to derive $\tilde{Q}_1$. Finally, we use $\tilde{Q}_1$ to compute $H_1$ by using Equation (9).

Proposed changes based on comments of reviewer 2:

• Include a remark on challenges related to estimating $p_{min}$ in practice
• Explicitly mention that the reported experimental results correspond to run of Algorithm 1
• Replace the current reach-avoid task with a more complex LTL specification and report the results, DRA and product MDP

We thank you for the detailed and useful feedback! We plan to improve our paper taking your comments into account. Our response to your specific questions are summarized as follows.

Assumptions used in the paper: We do not assume the SSP-communicating property for MDPs. Instead, we only make a weaker assumption of knowing a non-zero lower bound over minimum transition probability $p_{min}$, which enables application of our method to the general non-communicating MDPs​. To relax the communicating assumption in Tarbouriech et al. (2020), we leverage $p_{min}$​ to compute $\Lambda(s)$, which represents an upper bound on the minimum expected time required to reach $G$ from state $s$ in the (artificial) MDP $\mathcal{M}'$, constructed by connecting $B$ to $𝑠_{𝑖𝑛𝑖𝑡}​$. Note that $p_{min}$ can be used to compute the underlying graph to any desired accuracy, enabling us to check whether $G$ is reachable (which implies the boundedness of $\Lambda(s)$). These details are discussed in Lemma 4.2 and Remark 4.3. In particular, our results require no assumption other than knowing $p_{min}$. Also, it should be noted that assuming knowledge of $p_{min}$ is strictly weaker than the assumption of SSP-communication.

Presentation of Algorithm 1: Regarding referencing other algorithms and equations, we would like to highlight that Section 4.1 is specifically dedicated to explaining various components of the main algorithm (Algorithm 1). In particular, the following components of Algorithm 1 are discussed in detail: (1) the application of Equation (4) for “computing confidence intervals”, which are then used to construct interval MDPs from the observed data; (2) the operation of our proposed “Extended Value Iteration” method (Algorithm 2); and (3) the use of Equation (9) to compute “episode-specific deadlines”. These explanations are provided in the respective subsections of Section 4.1. That said, we appreciate the reviewer’s comment and will, in the final version of the paper, provide additional intuitive explanations of our Extended Value Iteration (Algorithm 2), include a brief description of Algorithm 3, and define the notation #{.}, which denotes set cardinality.

Clarity of Lemma 4.1: In Lemma 4.1, the event $\mathcal{E}$ refers to the scenario where the actual MDP lies within the interval MDP computed during the $k^{th}$ episode of learning. The notation $\mathbb{P}(\mathcal{E})$ represents the probability that this event occurs. The notation $Pr_{s_{init}}^{\pi}[\varphi]$ is explicitly defined in Section 3 under the heading “Maximum Probability of Satisfaction”, and refers to the probability of satisfying a given LTL specification $\varphi$, starting from the initial state $s_{init}$ and following policy $\pi$. In the camera-ready version of our paper, we will ensure that the notation $\mathbb{P}(.)$ is clearly explained, replace instances of $Pr[.]$ by $\mathbb{P}(.)$, and we will explicitly reference the relevant lemma adapted from (Tarbouriech et al., 2020, Lemma 3).

Comment on missing explanation for Equation (4): Equation (4) is used for computing confidence intervals necessary for constructing interval MDPs, and it is derived in earlier work (see Lemma 1). Specifically, the derivation relies on well-known probabilistic inequalities, and $max(1, N_k(s,a))$ serves to prevent division by zero, where $N_k(s,a)$ represents the number of visits to the state-action pair $(s, a)$. In the final version, we will include Equation (4) within the body of Lemma 4.1 and provide a brief explanation of the terms in Equation (4).

Proposed changes based on comments of reviewer 1:

• Provide additional intuitive explanation of our EVI (Algorithm 2), and give a brief explanation of Algorithm 3
• Integrate Equation (4) into Lemma 4.1, and provide a brief explanation of the terms within Equation (4)
• Explain the notation $\mathbb{P}(.)$ under the notations section
• Define the notation #{.}
• Provide citations for the definition of MDPs and interval MDPs (IMDPs), maximal end components (MECs), extended value iteration (EVI), and refer to the specific lemma from (Tarbouriech et al., 2020) for Lemma 4.1
• Define optimistic MDPs